Forums

Implementing a Counting Semaphore for RTOS

Started by ssubbarayan December 19, 2005
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

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

ssubbarayan wrote:
> > <snip> > > 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 >
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
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.
> 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
[F'up2 cut down --- neglected by OP]

In comp.arch.embedded ssubbarayan <ssubba@gmail.com> 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.
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
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&#2013265924;senz im Netz GITmbH mailto:news@kurt-harders.de http://www.pin-gmbh.com
>> 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&#2013265935;f