Simulating OS semaphore behavior

Simulating OS semaphore behavior

[REH]

I am porting some code from VxWorks and Ada 83 to another OS using Ada
95.  VxWorks' has a sempahore API I want to replicate with purely Ada
95 constructs, such as protected types.  The function is semFlush which
basically will release all the tasks currently blocked on the semaphore
but leave it locked, thus any new tasks that attempt to take the
semaphore will block.  I just cannot figure out a simple way to do it.

Abstractly, I want to allow an arbitrary number tasks to wait for a
particular event, and when the event occurs, wake all those tasks.
Thereafter, tasks can again block waiting for the next occurrence.
Something like:

protected type Event is
  entry Wait;
  procedure Signal;
end Event;

Implementing the above for one task seems simple enough, but how would
it been done for an arbitrary number such that the behavior is:
1. Wait's guard is initially false.
2. some tasks call Wait.
3. Signal is called.
4. Wait's guard becomes true.
5. all tasks currently queued on Wait are allowed to continue.
6. Wait's guard becomes false.

Any ideas would be greatly appreciated,

REH

Re: Simulating OS semaphore behavior

[Dmitry A. Kazakov]

On 25 Aug 2006 08:00:48 -0700, REH wrote:

> Abstractly, I want to allow an arbitrary number tasks to wait for a
> particular event, and when the event occurs, wake all those tasks.
> Thereafter, tasks can again block waiting for the next occurrence.
> Something like:
> 
> protected type Event is
>   entry Wait;
>   procedure Signal;
> end Event;
> 
> Implementing the above for one task seems simple enough, but how would
> it been done for an arbitrary number such that the behavior is:
> 1. Wait's guard is initially false.
> 2. some tasks call Wait.
> 3. Signal is called.
> 4. Wait's guard becomes true.
> 5. all tasks currently queued on Wait are allowed to continue.
> 6. Wait's guard becomes false.

That looks like a classic automatic event for multiple tasks. Make Signal
an entry:

   protected body Event is
      entry Wait when Signal'Count > 0 is
      begin
         null;
      end Wait;
      entry Signal when Wait'Count = 0 is
      begin
         null;
      end Signal;
   end Event;

Signal is blocked until all waiting tasks get released. There is no race
condition because fresh attempts to Wait are blocked if a signal is
pending.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simulating OS semaphore behavior

[REH]

Dmitry A. Kazakov wrote:
> That looks like a classic automatic event for multiple tasks. Make Signal
> an entry:
>
>    protected body Event is
>       entry Wait when Signal'Count > 0 is
>       begin
>          null;
>       end Wait;
>       entry Signal when Wait'Count = 0 is
>       begin
>          null;
>       end Signal;
>    end Event;
>
> Signal is blocked until all waiting tasks get released. There is no race
> condition because fresh attempts to Wait are blocked if a signal is
> pending.
> 

Ah, just what I love: simple and elegant.  Thank you!

REH

Re: Simulating OS semaphore behavior

[Jean-Pierre Rosen]

Dmitry A. Kazakov a �crit :
> That looks like a classic automatic event for multiple tasks. Make Signal
> an entry:
> 
>    protected body Event is
>       entry Wait when Signal'Count > 0 is
>       begin
>          null;
>       end Wait;
>       entry Signal when Wait'Count = 0 is
>       begin
>          null;
>       end Signal;
>    end Event;
> 
> Signal is blocked until all waiting tasks get released. There is no race
> condition because fresh attempts to Wait are blocked if a signal is
> pending.
> 

However, this will cause the signaling task to wait until some task 
calls wait. Generally, if there is no waiting task, Signal should do 
nothing. The classical barrier is as follows:

protected type Barrier is
	entry Wait;
	procedure Signal;
	function Count return Natural;
private
	Arrived : Boolean := False;
end Barrier;

protected body Barrieris
	entry Wait when Arrived is
	begin
		if Wait'COUNT = 0 then
			Arrived := False;
		end if;
	end Wait;

	procedure Signal is
	begin
		if Wait'COUNT > 0 then
			Arrived := True;
		end if;
	end Signal;

	function Count return Natural is
	begin
		return Wait'COUNT;
	end Count;
end Barrier;
-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Simulating OS semaphore behavior

[Dmitry A. Kazakov]

On Fri, 25 Aug 2006 19:31:53 +0200, Jean-Pierre Rosen wrote:

> Dmitry A. Kazakov a �crit :
>> That looks like a classic automatic event for multiple tasks. Make Signal
>> an entry:
>> 
>>    protected body Event is
>>       entry Wait when Signal'Count > 0 is
>>       begin
>>          null;
>>       end Wait;
>>       entry Signal when Wait'Count = 0 is
>>       begin
>>          null;
>>       end Signal;
>>    end Event;
>> 
>> Signal is blocked until all waiting tasks get released. There is no race
>> condition because fresh attempts to Wait are blocked if a signal is
>> pending.
> 
> However, this will cause the signaling task to wait until some task 
> calls wait.

Why? The Signal's barrier is open when the Wait's queue is empty.

Surely there are subtleties with the above:

1. The same task might get the same event twice if it anew queues itself to
Wait before emptying the queue.

2. There is no guaranty that all signals will be delivered to all tasks,
some might be still running while the event is pulsed.

In general it is not a reliable publisher-subscriber service, but just a
pulse event. Under system load, events might get lost or ghosted.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simulating OS semaphore behavior

[REH]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1519 bytes --]


"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:1gx5jdfxrewj6.19ufu2gqaakge.dlg@40tude.net...
> On Fri, 25 Aug 2006 19:31:53 +0200, Jean-Pierre Rosen wrote:
>
>> Dmitry A. Kazakov a �crit :
>>> That looks like a classic automatic event for multiple tasks. Make 
>>> Signal
>>> an entry:
>>>
>>>    protected body Event is
>>>       entry Wait when Signal'Count > 0 is
>>>       begin
>>>          null;
>>>       end Wait;
>>>       entry Signal when Wait'Count = 0 is
>>>       begin
>>>          null;
>>>       end Signal;
>>>    end Event;
>>>
>>> Signal is blocked until all waiting tasks get released. There is no race
>>> condition because fresh attempts to Wait are blocked if a signal is
>>> pending.
>>
>> However, this will cause the signaling task to wait until some task
>> calls wait.
>
> Why? The Signal's barrier is open when the Wait's queue is empty.
>
> Surely there are subtleties with the above:
>
> 1. The same task might get the same event twice if it anew queues itself 
> to
> Wait before emptying the queue.

I want to avoid this.

How about:

protected type Event is
    entry Wait;
    procedure Signal;
private:
    Arrived : Boolean := False;
    entry Wait_More;
end Event;

protected body Event is
    entry Wait when not Arrived is
        requeue Wait_More;
    end Wait;

    procedure Signal is
    begin
        Arrived := True;
    end Signal;

    entry Wait_More when Arrived is
        Arrived := Wait_More'Count > 0;
    end Wait_More;
end Event;

Re: Simulating OS semaphore behavior

[jimmaureenrogers]

You might be interested in a little article I wrote some time ago on
shared resource design patterns. The article can be found at
http://home.att.net/~jimmaureenrogers/Shared_Resource_Design_Patterns.html

Jim Rogers

Re: Simulating OS semaphore behavior

[Dmitry A. Kazakov]

On Sat, 26 Aug 2006 13:34:50 GMT, REH wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
> news:1gx5jdfxrewj6.19ufu2gqaakge.dlg@40tude.net...
>> On Fri, 25 Aug 2006 19:31:53 +0200, Jean-Pierre Rosen wrote:
>>
>>> Dmitry A. Kazakov a �crit :
>>>> That looks like a classic automatic event for multiple tasks. Make 
>>>> Signal
>>>> an entry:
>>>>
>>>>    protected body Event is
>>>>       entry Wait when Signal'Count > 0 is
>>>>       begin
>>>>          null;
>>>>       end Wait;
>>>>       entry Signal when Wait'Count = 0 is
>>>>       begin
>>>>          null;
>>>>       end Signal;
>>>>    end Event;
>>>>
>>>> Signal is blocked until all waiting tasks get released. There is no race
>>>> condition because fresh attempts to Wait are blocked if a signal is
>>>> pending.
>>>
>>> However, this will cause the signaling task to wait until some task
>>> calls wait.
>>
>> Why? The Signal's barrier is open when the Wait's queue is empty.
>>
>> Surely there are subtleties with the above:
>>
>> 1. The same task might get the same event twice if it anew queues itself 
>> to
>> Wait before emptying the queue.
> 
> I want to avoid this.
> 
> How about:
> 
> protected type Event is
>     entry Wait;
>     procedure Signal;
> private:
>     Arrived : Boolean := False;
>     entry Wait_More;
> end Event;
> 
> protected body Event is
>     entry Wait when not Arrived is
>         requeue Wait_More;
>     end Wait;
> 
>     procedure Signal is
>     begin
>         Arrived := True;
>     end Signal;
> 
>     entry Wait_More when Arrived is
>         Arrived := Wait_More'Count > 0;
>     end Wait_More;
> end Event;

It is the "lounge" pattern, which, as well, can be done without the Arrived
state. But that's rather a matter of taste.

The problem of this thing is: when the tasks are on the move from the
waiting room (Wait) to the service room (Wait_More), and amidst of this,
Signal gets called, it will shut the door before those unfortunate, who
hadn't yet managed through. The effect is that they will miss the event,
though they had been queued *before* the event happened.

An aside rant: You should carefully analyze your requirements, because an
"ideal" synchronization object just does not exist. In general, when the
publisher-subscriber relation is not DAG, 100% delivery and absence of
deadlocks are mutually exclusive. The requirements: no order inversions, no
ghosts, no misses are all contradictory. And event is a too low-level
thing, you'll probably never be satisfied with it.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simulating OS semaphore behavior

[REH]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:vgico14h6y95$.16dyzynqvydsk$.dlg@40tude.net...
> On Sat, 26 Aug 2006 13:34:50 GMT, REH wrote:

> It is the "lounge" pattern, which, as well, can be done without the 
> Arrived
> state. But that's rather a matter of taste.
>

Is there a reference (book, website, other) you could point me to that has 
these synchronization patterns in it?  I'm getting the impression that my 
problems have been solved many times over, and I'm am just re-inventing the 
wheel.

Thanks,
REH

Re: Simulating OS semaphore behavior

[Simon Wright]

Very useful resource, thanks!

Re: Simulating OS semaphore behavior

[Dmitry A. Kazakov]

On Sat, 26 Aug 2006 20:29:40 GMT, REH wrote:

> Is there a reference (book, website, other) you could point me to that has 
> these synchronization patterns in it?

Take a look at Jim Rogers' page.

I know many books on distributed/concurrent computing, Tannenbaum's book is
one to mention. But, honestly, they end where Ada just starts.

> I'm getting the impression that my 
> problems have been solved many times over, and I'm am just re-inventing the 
> wheel.

I don't think so. The issue is complicated and the silver bullet hasn't
been yet forged.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Simulating OS semaphore behavior

[Simon Wright]

"REH" <me@you.com> writes:

> Is there a reference (book, website, other) you could point me to
> that has these synchronization patterns in it?  I'm getting the
> impression that my problems have been solved many times over, and
> I'm am just re-inventing the wheel.

Concurrency in Ada?

http://www.amazon.com/gp/product/052162911X/104-4198498-4283156?v=glance&n=283155

Re: Simulating OS semaphore behavior

[REH]

"Simon Wright" <simon@pushface.org> wrote in message 
news:m2k64u83by.fsf@grendel.local...
> "REH" <me@you.com> writes:
>
>> Is there a reference (book, website, other) you could point me to
>> that has these synchronization patterns in it?  I'm getting the
>> impression that my problems have been solved many times over, and
>> I'm am just re-inventing the wheel.
>
> Concurrency in Ada?
>
> http://www.amazon.com/gp/product/052162911X/104-4198498-4283156?v=glance&n=283155

Thanks.  I've got that one.  Great book.  I'm referring to it constantly as 
of last.

REH

Re: Simulating OS semaphore behavior

[Anh Vo]

>>> "REH" <spamjunk@stny.rr.com> 8/25/2006 8:25 AM >>>

Dmitry A. Kazakov wrote:
> That looks like a classic automatic event for multiple tasks. Make
Signal
> an entry:
>
>    protected body Event is
>       entry Wait when Signal'Count > 0 is
>       begin
>          null;
>       end Wait;
>       entry Signal when Wait'Count = 0 is
>       begin
>          null;
>       end Signal;
>    end Event;
>
> Signal is blocked until all waiting tasks get released. There is no
race
> condition because fresh attempts to Wait are blocked if a signal is
> pending.
> 

Ah, just what I love: simple and elegant.  Thank you!

It is just simply beautiful, sweet and elegant solution. I had
implemented similar to Jean-Pierre's. I already changed to Dmitry's
implementation. This is another reason that Ada is in my heart.

AV