| Author |
Message |
ssubbarayan
Guest
|
 Posted:
Mon Dec 19, 2005 9:15 am Post subject:
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 |
|
| Back to top |
|
 |
David Kanter
Guest
|
| Posted:
Mon Dec 19, 2005 9:15 am Post subject:
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 |
|
| Back to top |
|
|
roman
Guest
|
| Posted:
Mon Dec 19, 2005 9:15 am Post subject:
Re: Implementing a Counting Semaphore for RTOS |
|
|
ssubbarayan wrote:
| Quote: |
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.
| Quote: | 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.
| Quote: | 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 ?
| Quote: | 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 ?
| Quote: | 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.
| Quote: |
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
| Quote: | 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
|
|
|
| Back to top |
|
|
ssubbarayan
Guest
|
| Posted:
Mon Dec 19, 2005 5:15 pm Post subject:
Re: Implementing a Counting Semaphore for RTOS |
|
|
David Kanter wrote:
| Quote: | 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 |
|
| Back to top |
|
|
Joe Seigh
Guest
|
| Posted:
Mon Dec 19, 2005 5:15 pm Post subject:
Re: Implementing a Counting Semaphore for RTOS |
|
|
ssubbarayan wrote:
| Quote: | 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.
| Quote: | 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
| Quote: | 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.
| Quote: | 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.
| Quote: | 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. |
|
| Back to top |
|
|
Prafulla Harpanhalli
Guest
|
| Posted:
Mon Dec 19, 2005 5:15 pm Post subject:
Re: Implementing a Counting Semaphore for RTOS |
|
|
| Quote: | 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. |
| Quote: | Typically it takes a)A count value-an integer
short int maybe, for reaons you have pointed out. |
| Quote: | 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)
| Quote: | 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) |
| Quote: | 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. |
| Quote: | 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.
| Quote: | 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 ? |
| Quote: | 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.
| Quote: | 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.
| Quote: | 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 |
|
| Back to top |
|
|
Thad Smith
Guest
|
| Posted:
Mon Dec 19, 2005 5:15 pm Post subject:
Re: Implementing a Counting Semaphore for RTOS |
|
|
ssubbarayan wrote:
| Quote: | 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.
| Quote: | 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.
| Quote: | 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?
| Quote: | 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.
| Quote: | 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.
| Quote: | 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.
| Quote: | 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.
| Quote: | 4)How to come out with worst case possibility for maximum number of
tasks that pend on this queue?
|
Number of TCBs.
| Quote: | 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 |
|
| Back to top |
|
|
Hans-Bernhard Broeker
Guest
|
| Posted:
Mon Dec 19, 2005 5:15 pm Post subject:
Re: Implementing a Counting Semaphore for RTOS |
|
|
[F'up2 cut down --- neglected by OP]
In comp.arch.embedded ssubbarayan <ssubba@gmail.com> wrote:
| Quote: | 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.
| Quote: | 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.
| Quote: | 1)What should be maximum size of task addition queue used with in this
datastructure ?
[...] |
Impossible to tell from what little detail you gave.
| Quote: | 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. |
|
| Back to top |
|
|
Alex Colvin
Guest
|
| Posted:
Mon Dec 19, 2005 6:24 pm Post subject:
Re: Implementing a Counting Semaphore for RTOS |
|
|
| Quote: | 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 |
|
| Back to top |
|
|
Kurt Harders
Guest
|
| Posted:
Mon Dec 19, 2005 11:43 pm Post subject:
Re: Implementing a Counting Semaphore for RTOS |
|
|
Hello,
ssubbarayan wrote:
| Quote: | 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 |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in