Implementing a Counting Semaphore for RTOS

In article <kDspf.10181$ph.8569@read2.cgocable.net>,
roman  <news@ziak.com> wrote:
>ssubbarayan wrote:
>>
>> <snip>
>>
>> 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

Op Sat, 31 Dec 2005 13:30:01 +0100 schreef Morten Reistad  
<first@last.name>:

> 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/