Implementing a Counting Semaphore for RTOS - VxWorks

This is a discussion on Implementing a Counting Semaphore for RTOS - VxWorks ; Gurus, For reasons undisclosed,We are asked by our clients to design a counting semaphore for their propreitory RTOS.I have some ideas presented here,I would like to know all your expert opinion whether this could be a proper design to go ...

+ Reply to Thread
Results 1 to 12 of 12

Thread: Implementing a Counting Semaphore for RTOS

  1. Implementing a Counting Semaphore for RTOS

    Gurus,

    For reasons undisclosed,We are asked by our clients to design a
    counting semaphore for their propreitory RTOS.I have some ideas
    presented here,I would like to know all your expert opinion whether
    this could be a proper design to go ahead and implement.I have few
    hiccups which till now I am not clear how to overcome.Heres what I
    planned to proceed like:

    The actual expectation from us is to come with a counting semaphore
    which schedules the requesters according to FIFO and also which at any
    point of time will help us to query how many tasks are pending for them
    and also give primitives for taking and giving them with timeout
    feature incorporated into it.

    My design:
    Implement a semaphore datastructure:
    Typically it takes a)A count value-an integer
    b)A queue data structure to load all the
    tasks requesting for semaphore
    c)A taskid data structure to store the taskid
    or process id of task currently
    owning the semaphore
    d)A timeout parameter to store the time value
    a requester has to wait till he
    gets the semaphore

    Now the creator will intialise the count value according to his
    requirement.When ever some task requests it,and value is greater then
    0,he gets it.If value is less then zero,he will wait for timeout
    parameter value.Taking a semaphore decreaments the count value and
    Giving a semaphore will increament the count value.The task requesting
    the semaphore needs to update the queue incase he is not successful in
    receiving the semaphore at time of request and also process/taskid
    updation when he is successful in aquiring it.

    Now the moment he is successful in aquiring,before the count value is
    updated,he will execute a task lock to lock the scheduler to make the
    operation atomic.once he has updated the count,lock is released.

    Now I have the following doubts/hiccups:

    1)What should be maximum size of task addition queue used with in this
    datastructure ?
    2)Suppose we use an integer datatype for count of semaphores,will it
    not make the task request 32768(max int=32767) failure?How to deal with
    this situation?
    3)Should the queue data structure be dynamic?or we should restrict the
    size of queue in our design?
    4)How to come out with worst case possibility for maximum number of
    tasks that pend on this queue?
    5)How should I schedule the tasks with in the semaphore data structure
    or semtake/semgive call to move them to pended state when semaphores
    are not available at time of request and reschedule them to running
    state incase semaphore is available.Should I explicitly invoke the
    scheduler by OS calls ?

    I would like to get some links or any valuable inputs on this design
    and it will be helpful if any one of you can throw some ideas on this
    implementation .
    It would also be greatly appreciated if any one can point me to a
    existing implementation of counting semaphores for RTOS,so that I can
    come up with a good design of the same.

    Incase this is not the right group to discuss this issue,please excuse
    me and direct me to a right group.


    Looking farward for all your replys and advanced thanks for the same,

    Regards,
    s.subbarayan


  2. Re: Implementing a Counting Semaphore for RTOS

    You know, usually we aren't that receptive to homework problems.
    However, you have clearly taken things one step further. You want help
    with a problem you are solving for a client? Why shouldn't we charge
    you for the answer?

    DK


  3. Re: Implementing a Counting Semaphore for RTOS

    ssubbarayan wrote:
    >
    >
    >
    > Now I have the following doubts/hiccups:
    >
    > 1)What should be maximum size of task addition queue used with in this
    > datastructure ?


    Maybe it should not be a magic number but limited only by available memory.

    > 2)Suppose we use an integer datatype for count of semaphores,will it
    > not make the task request 32768(max int=32767) failure?How to deal with
    > this situation?


    You could deal with it by argument checking. And maybe you could use the
    unsigned integer instead. In semaphore you are very likely to check
    requested number of counts to remaining number of counts, so you may
    easily prevent roll-over or negative number of counts.

    Otherwise if you keep using signed integer, the requested negative
    number of counts will pass through argument check (requested <
    remaining) unless you have check for negative numbers also - extra code
    not being necessary if unsigned argument used.

    > 3)Should the queue data structure be dynamic?or we should restrict the
    > size of queue in our design?


    In RTOS you are most likely already using queues in other objects. Why
    not reuse them ?

    > 4)How to come out with worst case possibility for maximum number of
    > tasks that pend on this queue?


    Again, why magic number ? How about a linked list ?

    > 5)How should I schedule the tasks with in the semaphore data structure
    > or semtake/semgive call to move them to pended state when semaphores
    > are not available at time of request and reschedule them to running
    > state incase semaphore is available.Should I explicitly invoke the
    > scheduler by OS calls ?


    It depends on your design. If you are by design absolutely sure that
    your task owning a semaphore is the highest priority task with ready
    state: for example the fact that CPU is executing the task entering the
    semaphore guarantees that this task is currently one of highest priority
    tasks. If your scheduler is cooperative, then it may be good idea to
    call it here.

    >
    > I would like to get some links or any valuable inputs on this design
    > and it will be helpful if any one of you can throw some ideas on this
    > implementation .
    > It would also be greatly appreciated if any one can point me to a
    > existing implementation of counting semaphores for RTOS,so that I can
    > come up with a good design of the same.


    It's been some time since I studied RTOS and implemented semaphore, so I
    only offer to you as my probably obsolete opinion and your google-ing is
    at these conditions as good as mine.

    Regards
    Roman

    > Incase this is not the right group to discuss this issue,please excuse
    > me and direct me to a right group.
    >
    >
    > Looking farward for all your replys and advanced thanks for the same,
    >
    > Regards,
    > s.subbarayan
    >


  4. Re: Implementing a Counting Semaphore for RTOS


    David Kanter wrote:
    > You know, usually we aren't that receptive to homework problems.
    > However, you have clearly taken things one step further. You want help
    > with a problem you are solving for a client? Why shouldn't we charge
    > you for the answer?
    >
    > DK

    Hi DK,
    I am not looking for a homework solution from others.Its a genuine
    technical doubt I am looking to get expert opinion on.If really you
    need a charge for this,you are quite welcome to Join my company and
    provide your guidance with a charge.
    Please avoid circaustic replys in future.
    Regards,
    s.subbarayan


  5. Re: Implementing a Counting Semaphore for RTOS

    ssubbarayan wrote:
    > Gurus,
    >
    > For reasons undisclosed,We are asked by our clients to design a
    > counting semaphore for their propreitory RTOS.I have some ideas
    > presented here,I would like to know all your expert opinion whether
    > this could be a proper design to go ahead and implement.I have few
    > hiccups which till now I am not clear how to overcome.Heres what I
    > planned to proceed like:
    >
    > The actual expectation from us is to come with a counting semaphore
    > which schedules the requesters according to FIFO and also which at any
    > point of time will help us to query how many tasks are pending for them
    > and also give primitives for taking and giving them with timeout
    > feature incorporated into it.
    >

    [...]
    >
    > Now the moment he is successful in aquiring,before the count value is
    > updated,he will execute a task lock to lock the scheduler to make the
    > operation atomic.once he has updated the count,lock is released.
    >
    > Now I have the following doubts/hiccups:
    >
    > 1)What should be maximum size of task addition queue used with in this
    > datastructure ?


    Unless you have an api that lets the users determine this, it
    should be dynamic w/ appropiate return codes. You should have some
    minimum queue size required to have a useable system, especially
    given that there are probably RT guarantees on stuff.

    > 2)Suppose we use an integer datatype for count of semaphores,will it
    > not make the task request 32768(max int=32767) failure?How to deal with
    > this situation?


    error return codes

    > 3)Should the queue data structure be dynamic?or we should restrict the
    > size of queue in our design?


    dynamic w/ error return codes if you run out of resources.


    > 4)How to come out with worst case possibility for maximum number of
    > tasks that pend on this queue?


    Depends on what you are guaranteeing.

    > 5)How should I schedule the tasks with in the semaphore data structure
    > or semtake/semgive call to move them to pended state when semaphores
    > are not available at time of request and reschedule them to running
    > state incase semaphore is available.Should I explicitly invoke the
    > scheduler by OS calls ?


    The RTOS should have an internal scheduler api for this. If it does
    not have support for kernel threads, RUN AWAY!

    I am really suprised that something that claims to be an RTOS does not
    have support for sempahores already given that semaphores are traditional
    and tend to be put in even if people aren't really sure why they're there.



    --
    Joe Seigh

    When you get lemons, you make lemonade.
    When you get hardware, you make software.

  6. Re: Implementing a Counting Semaphore for RTOS

    > The actual expectation from us is to come with a counting semaphore
    > which schedules the requesters according to FIFO and also which at any
    > point of time will help us to query how many tasks are pending for them
    > and also give primitives for taking and giving them with timeout
    > feature incorporated into it.
    >
    > My design:
    > Implement a semaphore datastructure:

    I presume you mean Semaphore Control Block.

    > Typically it takes a)A count value-an integer

    short int maybe, for reaons you have pointed out.

    >b)A queue data structure to load all the tasks requesting for semaphore

    In a particular implementation, i have seen a list kept sorted (either
    priority wise or FIFO)

    >c)A taskid data structure to store the taskid or process id of task currently owning the >semaphore

    This could be an int (or tid_t)

    >d)A timeout parameter to store the time value a requester has to wait till he gets the semaphore
    >
    >The task requesting
    > the semaphore needs to update the queue incase he is not successful in
    > receiving the semaphore at time of request and also process/taskid
    > updation when he is successful in aquiring it.

    This is not task's responsibility.

    > 1)What should be maximum size of task addition queue used with in this
    > datastructure ?

    As i said, this can be a list kept sorted based on the samphore's
    creation option. I mean the option that allows the tasks to be blocked
    in either FIFO/Proirity basis.

    > 2)Suppose we use an integer datatype for count of semaphores,will it
    > not make the task request 32768(max int=32767) failure?How to deal with
    > this situation?

    Short int ?

    > 5)How should I schedule the tasks with in the semaphore data structure
    > or semtake/semgive call to move them to pended state when semaphores
    > are not available at time of request and reschedule them to running
    > state incase semaphore is available.Should I explicitly invoke the
    > scheduler by OS calls ?

    For this, you will have to tamper the TCB and update the status of the
    respective tasks. And as far as invoking the scheduler goes.
    re-enabling interrupts is the trick AFAIK.

    > I would like to get some links or any valuable inputs on this design
    > and it will be helpful if any one of you can throw some ideas on this
    > implementation .
    > It would also be greatly appreciated if any one can point me to a
    > existing implementation of counting semaphores for RTOS,so that I can
    > come up with a good design of the same.

    Execellent reference would be Stanford University student Ben Pfaff's
    pintos. Googling should take you there easily. I strongly suggest you
    read the Copyright and other guidelines before proceeding.

    > Incase this is not the right group to discuss this issue,please excuse
    > me and direct me to a right group.

    Since you are extending your client's propritery RTOS, you are off
    topic here. You may wish to visit comp.os.research or other similar
    newsrooms for this.

    --
    Prafulla Harpanhalli


  7. Re: Implementing a Counting Semaphore for RTOS

    ssubbarayan wrote:

    > For reasons undisclosed,We are asked by our clients to design a
    > counting semaphore for their propreitory RTOS.


    This is strange. Semaphores are normally integral to an RTOS.

    > I have some ideas
    > presented here,I would like to know all your expert opinion whether
    > this could be a proper design to go ahead and implement.I have few
    > hiccups which till now I am not clear how to overcome.Heres what I
    > planned to proceed like:
    >
    > The actual expectation from us is to come with a counting semaphore
    > which schedules the requesters according to FIFO and also which at any
    > point of time will help us to query how many tasks are pending for them
    > and also give primitives for taking and giving them with timeout
    > feature incorporated into it.


    This will not provide all your features, but may give you some ideas.
    In the past, when memory was scarce, I used an RTOS which provided
    counting semaphores. Each semaphore had a 16-bit value. One bit
    specified whether the value was positive or negative. If positive, the
    other bits contained the positive count. If negative, the other bits
    contained a pointer (at an even address) of the TCB of the first task
    waiting for service. If a task performed a P operation on a semaphore
    with non-positive count, it was added to the waiting queue. Each task
    could only wait on a single semaphore, so the next pointer in the TCB
    contained a pointer to the next task waiting for the same semaphore (or
    next in some other queue, such as ready queue). A new task waiting
    would be placed in the queue in priority order. I don't think there was
    a timeout capability.

    When a task performed the V operation, if there was a task waiting, it
    was removed from the head of the semaphore queue and placed on the ready
    queue in priority order. If it was the highest priority in the ready
    queue and greater priority than the currently executing task, then the
    current task was retired to the ready queue and the new task was made
    the current task.

    > My design:
    > Implement a semaphore datastructure:
    > Typically it takes a)A count value-an integer
    > b)A queue data structure to load all the
    > tasks requesting for semaphore


    Could you use pointers to chain TCBs and not have a separate queue?

    > c)A taskid data structure to store the taskid
    > or process id of task currently
    > owning the semaphore


    A bare semaphore does not have an owner, but that would be useful for
    locks constructed of semaphores. The major use for a positive semaphore
    count is to implement producer-consumer synchronization: the producer
    increments the count when it produces something. The consumer
    decrements the count before consuming an item. If the count it zero,
    the consumer waits. The producer can produce several items before the
    consumer runs, though, giving a positive semaphore count. Note that
    this is not the same as using it for a resource lock, so there is no
    owner. This usage works with multiple producers and consumers for the
    same item type.

    > d)A timeout parameter to store the time value
    > a requester has to wait till he
    > gets the semaphore


    Because you have multiple requestors, this needs to be stored per task.
    If the task can only do a timed wait on a single semaphore at a time,
    consider placing it into the TCB.


    > 2)Suppose we use an integer datatype for count of semaphores,will it
    > not make the task request 32768(max int=32767) failure?How to deal with
    > this situation?


    This should be sufficient for normal semaphore use. You can provide an
    error return to the increment operation on attempted overflow.

    > 3)Should the queue data structure be dynamic?or we should restrict the
    > size of queue in our design?


    Use a linked list of TCBs.

    > 4)How to come out with worst case possibility for maximum number of
    > tasks that pend on this queue?


    Number of TCBs.

    > 5)How should I schedule the tasks with in the semaphore data structure
    > or semtake/semgive call to move them to pended state when semaphores
    > are not available at time of request and reschedule them to running
    > state incase semaphore is available.Should I explicitly invoke the
    > scheduler by OS calls ?


    The primitive you need is to spend the currently executing task. The
    scheduler will activate the ready task with the highest priority.

    --
    Thad


  8. Re: Implementing a Counting Semaphore for RTOS

    [F'up2 cut down --- neglected by OP]

    In comp.arch.embedded ssubbarayan wrote:

    > For reasons undisclosed,We are asked by our clients to design a
    > counting semaphore for their propreitory RTOS.I have some ideas
    > presented here,I would like to know all your expert opinion whether
    > this could be a proper design to go ahead and implement.


    If you must ask, I'm afraid you're out of your depth. So is your
    client.

    If somebody believes they should be making their own proprietary RTOS,
    yet feels the need to refer to outside expertise to implement such a
    fundamental feature of an RTOS instead of doing it themselves, *and*
    that outside expert doesn't have enough expertise on the subject to
    trust his own judgement more than a random Usenet poll, those are at
    least two strong signs of serious trouble in project management.

    More bluntly put: if that thing doesn't already have fully functional
    semaphores, it's probably not worth being called an RTOS to begin
    with. And if they need outside help to do it, they shouldn't be
    trying to make their own RTOS.

    > b) A queue data structure to load all the tasks requesting for semaphore


    That IMHO has nothing to do with the implementation of the semaphore.
    That only concerns how the RTOS *uses* the semaphore. A semaphore can
    be used by a scheduler --- it's not a scheduler in and of itself.

    This looks like you're being asked to write the entire RTOS for them,
    not just the semaphore.

    > 1)What should be maximum size of task addition queue used with in this
    > datastructure ?

    [...]

    Impossible to tell from what little detail you gave.

    > Incase this is not the right group to discuss this issue,please excuse
    > me and direct me to a right group.


    Which "this" group are you asking that about? You posted to three.

    --
    Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
    Even if all the snow were burnt, ashes would remain.

  9. Re: Implementing a Counting Semaphore for RTOS

    Hello,

    ssubbarayan wrote:

    > For reasons undisclosed,We are asked by our clients to design a
    > counting semaphore for their propreitory RTOS.I have some ideas
    > presented here,I would like to know all your expert opinion whether
    > this could be a proper design to go ahead and implement.I have few
    > hiccups which till now I am not clear how to overcome.Heres what I
    > planned to proceed like:


    [...] lots of nice thoughts.

    Why not having a look at the Posix implementation of semaphores? They
    solved all thinking for you including the problems arising when a
    process dies...

    Regards, Kurt
    --
    Kurt Harders
    PiN -Prńsenz im Netz GITmbH
    mailto:news@kurt-harders.de
    http://www.pin-gmbh.com

  10. Re: Implementing a Counting Semaphore for RTOS

    >> For reasons undisclosed,We are asked by our clients to design a
    >> counting semaphore for their propreitory RTOS.


    presumably your RTOS comes with a (non-counting) binary semaphore.
    Use the binary semaphore to control tests and updates to the count.
    Then use another binary semaphore to queue blocked tasks in the usual way.

    --
    mac the na´f

  11. Re: Implementing a Counting Semaphore for RTOS

    In article ,
    roman wrote:
    >ssubbarayan wrote:
    >>
    >>
    >>
    >> Now I have the following doubts/hiccups:


    First I want to point you to proper theory. This was added to multics
    as a core function, and inherited by Primos. Look for "dijstra semaphores".

    Dijstra uses Dutch vocabulary, P() and V() for "Proberen" and "Verhogen",
    and papers tend to respect this. Primos didn't, and call them sem$nf and
    sem$wt.

    >> 1)What should be maximum size of task addition queue used with in this
    >> datastructure ?

    >
    >Maybe it should not be a magic number but limited only by available memory.


    Primos allowed you to use a file as a semaphore, and the queue was thus
    represented inside the file, and could grow similarly. You had to initialise
    the file with sem$ini, and that would zap contents of the file. Using this
    method you get access control to the semaphore for free.

    >> 2)Suppose we use an integer datatype for count of semaphores,will it
    >> not make the task request 32768(max int=32767) failure?How to deal with
    >> this situation?

    >
    >You could deal with it by argument checking. And maybe you could use the
    >unsigned integer instead. In semaphore you are very likely to check
    >requested number of counts to remaining number of counts, so you may
    >easily prevent roll-over or negative number of counts.
    >
    >Otherwise if you keep using signed integer, the requested negative
    >number of counts will pass through argument check (requested <
    >remaining) unless you have check for negative numbers also - extra code
    >not being necessary if unsigned argument used.
    >
    >> 3)Should the queue data structure be dynamic?or we should restrict the
    >> size of queue in our design?

    >
    >In RTOS you are most likely already using queues in other objects. Why
    >not reuse them ?


    Go read about Dijstra's work. It has been available since the 1960 publication,
    and has been standard issue in CS courses since their inception in the mid
    1970s.

    >> 4)How to come out with worst case possibility for maximum number of
    >> tasks that pend on this queue?

    >
    >Again, why magic number ? How about a linked list ?


    >
    >> 5)How should I schedule the tasks with in the semaphore data structure
    >> or semtake/semgive call to move them to pended state when semaphores
    >> are not available at time of request and reschedule them to running
    >> state incase semaphore is available.Should I explicitly invoke the
    >> scheduler by OS calls ?

    >
    >It depends on your design. If you are by design absolutely sure that
    >your task owning a semaphore is the highest priority task with ready
    >state: for example the fact that CPU is executing the task entering the
    >semaphore guarantees that this task is currently one of highest priority
    >tasks. If your scheduler is cooperative, then it may be good idea to
    >call it here.


    here the recycl() call is useful. This just dispatch you to the end of
    the run queue again, with a minimum sleep involved.

    If you are waiting in a critical loop in user space code such a call
    is really useful in the P() / sem$wt code.

    >> I would like to get some links or any valuable inputs on this design
    >> and it will be helpful if any one of you can throw some ideas on this
    >> implementation .
    >> It would also be greatly appreciated if any one can point me to a
    >> existing implementation of counting semaphores for RTOS,so that I can
    >> come up with a good design of the same.

    >
    >It's been some time since I studied RTOS and implemented semaphore, so I
    >only offer to you as my probably obsolete opinion and your google-ing is
    >at these conditions as good as mine.


    I just point you at theory. I cannot force you to drink it.

    -- mrr

  12. Re: Implementing a Counting Semaphore for RTOS

    Op Sat, 31 Dec 2005 13:30:01 +0100 schreef Morten Reistad
    :

    > as a core function, and inherited by Primos. Look for "dijstra


    > Dijstra uses Dutch vocabulary, P() and V() for "Proberen" and "Verhogen",


    > Go read about Dijstra's work. It has been available since the 1960


    Dijkstra, with a K please. (No, not related


    --
    Gemaakt met Opera's revolutionaire e-mailprogramma:
    http://www.opera.com/mail/

+ Reply to Thread