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

>>     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&#4294967295;f

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&#4294967295;senz im Netz GITmbH
mailto:news@kurt-harders.de
http://www.pin-gmbh.com

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

[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.

> 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

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.

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