How to simulate semaphores with Ada's tasks?

How to simulate semaphores with Ada's tasks?

[Andrew Shvets]

From what I've read, tasks do not have semaphores that can permit it to lock a piece of memory and prevent it from being accessed, is this correct?

If so, then the best possible way to simulate this is to have tasks send messages to one another and synchronize when something is locked/unlocked.  Is there a better approach?

Re: How to simulate semaphores with Ada's tasks?

[Jeffrey R. Carter]

On 08/24/2016 05:41 PM, Andrew Shvets wrote:
> 
> If so, then the best possible way to simulate this is to have tasks send
> messages to one another and synchronize when something is locked/unlocked.
> Is there a better approach?

Yes, you use protected objects.

-- 
Jeff Carter
"He had no conception of the instrument. He
was blowing into it."
Take the Money and Run
135

Re: How to simulate semaphores with Ada's tasks?

[Andrew Shvets]

On Wednesday, August 24, 2016 at 9:04:50 PM UTC-4, Jeffrey R. Carter wrote:
> On 08/24/2016 05:41 PM, Andrew Shvets wrote:
> > 
> > If so, then the best possible way to simulate this is to have tasks send
> > messages to one another and synchronize when something is locked/unlocked.
> > Is there a better approach?
> 
> Yes, you use protected objects.
> 
> -- 
> Jeff Carter
> "He had no conception of the instrument. He
> was blowing into it."
> Take the Money and Run
> 135

Noted.  Reading up on it right now.

Thank you.

Re: How to simulate semaphores with Ada's tasks?

[Andrew Shvets]

On Wednesday, August 24, 2016 at 9:04:50 PM UTC-4, Jeffrey R. Carter wrote:
> 
> Yes, you use protected objects.
> 
> -- 
> Jeff Carter
> "He had no conception of the instrument. He
> was blowing into it."
> Take the Money and Run
> 135

Hello Jeff,

I do have a question now.  I've written an (at the bottom of this message) example on using a protected type.

My current understanding is that the protected type is a way to encapsulate a piece of data and then regulate which values can be assigned its insides (similar to how in Java there is a way to create a piece of code where only one thread at a time can run at any given moment.)  The example below has 5 tasks and each one tries to update the same unbounded string.  The goal was to create a small application with 5 tasks and each one fighting to update the same value.

Does my description make sense?  Or am I completely off-base?

https://gist.githubusercontent.com/anonymous/c8eee56143d534d837281953d86ac501/raw/cd2603babab42132cea68f71997960dd925fc4e8/gistfile1.txt

Re: How to simulate semaphores with Ada's tasks?

[Jeffrey R. Carter]

On 08/27/2016 02:36 PM, Andrew Shvets wrote:
> 
> My current understanding is that the protected type is a way to encapsulate a
> piece of data and then regulate which values can be assigned its insides
> (similar to how in Java there is a way to create a piece of code where only
> one thread at a time can run at any given moment.)  The example below has 5
> tasks and each one tries to update the same unbounded string.  The goal was
> to create a small application with 5 tasks and each one fighting to update
> the same value.
> 
> Does my description make sense?  Or am I completely off-base?

In general, a protected object encapsulates a set of operations that are
mutually exclusive. Only one call to one operation may proceed at a time. (This
is not strictly correct, but it's close enough, it's simple, and an
implementation that works this way conforms to the standard.) It may also
encapsulate and hide some optional data that the operations operate on.

The PO in your example, as written, implements a standard monitor with a default
initial value for Unbounded_String (the default initial value is ""). A monitor
stores one value; calls to Put a new value overwrite the existing value; calls
to Get the value leave the value unaffected, and future calls to Get can return
the same value. This is sometimes described as having a destructive Put and
non-destructive Get. A queue, on the other hand, has a non-destructive Put and a
destructive Get. Your Empty component serves no purpose. If you had barriers
using Empty as in your comments, then your PO would be a bounded, blocking queue
with a maximum length of 1.

So from that point of view, you seem to understand how to use POs.

There's special syntax for singleton POs like yours:

protected Protected_01 is
   ...
end Protected_01;

This is equivalent to

protected type /anonymous/ is
   ...
end /anonymous/;

Protected_01 : /anonymous/;

If I were implementing the same functionality, I'd probably use String
externally and only use Unbounded_String when needed to store a String value:

protected Protected_String is
   procedure Put (Value : in String);
   function Value return String;
private -- Protected_String
   Current : Unbounded_String;
end Protected_String;

The body would convert as needed.

Looking at the rest of the example, your task is confused. The loop is executed
exactly once, so there's no reason for it. Your select has only a single
alternative, so there's no reason for it. Stripped of the output statements,
it's functionality is

begin
   accept Start ...;
   accept Quit;
   Protected_01.Insert ...;
end;

The default value of an uninitialized Unbounded_String is the null string, so given

V : Unbounded_String;

V's value is "" and there's no reason to explicitly initialize it to that.
However, if you do need to refer to the null string value, you can use
Null_Unbounded_String, which is probably clearer and better than
To_Unbounded_String ("").

There's no guarantee that multiple tasks writing to the same
Ada.Text_IO.File_Type will give you useful results.

-- 
Jeff Carter
"Monsieur Arthur King, who has the brain of a duck, you know."
Monty Python & the Holy Grail
09

Re: How to simulate semaphores with Ada's tasks?

[Andrew Shvets]

On Saturday, August 27, 2016 at 9:04:26 PM UTC-4, Jeffrey R. Carter wrote:
> On 08/27/2016 02:36 PM, Andrew Shvets wrote:
> > 
> > My current understanding is that the protected type is a way to encapsulate a
> > piece of data and then regulate which values can be assigned its insides
> > (similar to how in Java there is a way to create a piece of code where only
> > one thread at a time can run at any given moment.)  The example below has 5
> > tasks and each one tries to update the same unbounded string.  The goal was
> > to create a small application with 5 tasks and each one fighting to update
> > the same value.
> > 
> > Does my description make sense?  Or am I completely off-base?
> 
> In general, a protected object encapsulates a set of operations that are
> mutually exclusive. Only one call to one operation may proceed at a time. (This
> is not strictly correct, but it's close enough, it's simple, and an
> implementation that works this way conforms to the standard.) It may also
> encapsulate and hide some optional data that the operations operate on.
> 
> The PO in your example, as written, implements a standard monitor with a default
> initial value for Unbounded_String (the default initial value is ""). A monitor
> stores one value; calls to Put a new value overwrite the existing value; calls
> to Get the value leave the value unaffected, and future calls to Get can return
> the same value. This is sometimes described as having a destructive Put and
> non-destructive Get. A queue, on the other hand, has a non-destructive Put and a
> destructive Get. Your Empty component serves no purpose. If you had barriers
> using Empty as in your comments, then your PO would be a bounded, blocking queue
> with a maximum length of 1.
> 
> So from that point of view, you seem to understand how to use POs.
> 
> There's special syntax for singleton POs like yours:
> 
> protected Protected_01 is
>    ...
> end Protected_01;
> 
> This is equivalent to
> 
> protected type /anonymous/ is
>    ...
> end /anonymous/;
> 
> Protected_01 : /anonymous/;
> 
> If I were implementing the same functionality, I'd probably use String
> externally and only use Unbounded_String when needed to store a String value:
> 
> protected Protected_String is
>    procedure Put (Value : in String);
>    function Value return String;
> private -- Protected_String
>    Current : Unbounded_String;
> end Protected_String;
> 
> The body would convert as needed.
> 
> Looking at the rest of the example, your task is confused. The loop is executed
> exactly once, so there's no reason for it. Your select has only a single
> alternative, so there's no reason for it. Stripped of the output statements,
> it's functionality is
> 
> begin
>    accept Start ...;
>    accept Quit;
>    Protected_01.Insert ...;
> end;
> 
> The default value of an uninitialized Unbounded_String is the null string, so given
> 
> V : Unbounded_String;
> 
> V's value is "" and there's no reason to explicitly initialize it to that.
> However, if you do need to refer to the null string value, you can use
> Null_Unbounded_String, which is probably clearer and better than
> To_Unbounded_String ("").
> 
> There's no guarantee that multiple tasks writing to the same
> Ada.Text_IO.File_Type will give you useful results.
> 
> -- 
> Jeff Carter
> "Monsieur Arthur King, who has the brain of a duck, you know."
> Monty Python & the Holy Grail
> 09

You are correct, the loop runs only once.  It should be like so:

else
  Ada.Text_IO.Put_Line("Task is inserting!");
  Protected_01.Insert(Task_Custom_String);
  delay 0.0;
end select;

Re: How to simulate semaphores with Ada's tasks?

[Dmitry A. Kazakov]

On 25/08/2016 02:41, Andrew Shvets wrote:
> From what I've read, tasks do not have semaphores that can permit it
> to lock a piece of memory and prevent it from being accessed, is this
> correct?

It is unclear what you mean here. Semaphore blocks a resource, not 
necessarily memory. Technically you cannot block memory at the language 
level, e.g. using memory management registers. It is too low-level. So 
it is operations that are blocked with memory encapsulated somewhere 
into an object or a package.

> If so, then the best possible way to simulate this is to have tasks
> send messages to one another and synchronize when something is
> locked/unlocked.

That is called "monitor". It can be used to implement the semaphore too, 
but nobody does that. In most cases monitor is better than semaphore 
when that comes in question.

Semaphore has little if no use when k>1. Only mutex (semaphore k=1) is 
actively used.

> Is there a better approach?

Sometimes monitor is better sometimes mutex is.

Regarding mutex what kind of are you looking for? Plain? Reentrant? 
Read-write mutex? Arrays of mutexes?

In Ada synchronization objects like mutex are implemented using 
protected object. A plain mutex or semaphore is trivial to implement.

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

Re: How to simulate semaphores with Ada's tasks?

[Andrew Shvets]

On Thursday, August 25, 2016 at 3:39:50 AM UTC-4, Dmitry A. Kazakov wrote:
> On 25/08/2016 02:41, Andrew Shvets wrote:
> > From what I've read, tasks do not have semaphores that can permit it
> > to lock a piece of memory and prevent it from being accessed, is this
> > correct?
> 
> It is unclear what you mean here. Semaphore blocks a resource, not 
> necessarily memory. Technically you cannot block memory at the language 
> level, e.g. using memory management registers. It is too low-level. So 
> it is operations that are blocked with memory encapsulated somewhere 
> into an object or a package.
> 
> > If so, then the best possible way to simulate this is to have tasks
> > send messages to one another and synchronize when something is
> > locked/unlocked.
> 
> That is called "monitor". It can be used to implement the semaphore too, 
> but nobody does that. In most cases monitor is better than semaphore 
> when that comes in question.
> 
> Semaphore has little if no use when k>1. Only mutex (semaphore k=1) is 
> actively used.
> 
> > Is there a better approach?
> 
> Sometimes monitor is better sometimes mutex is.
> 
> Regarding mutex what kind of are you looking for? Plain? Reentrant? 
> Read-write mutex? Arrays of mutexes?
> 
> In Ada synchronization objects like mutex are implemented using 
> protected object. A plain mutex or semaphore is trivial to implement.
> 
> -- 
> Regards,
> Dmitry A. Kazakov
> http://www.dmitry-kazakov.de

Hello Dmitry,

Yes, resources is a better term.  What I'm looking for -- well, still learning about it, I'm quite new to this -- is really to learn more about mutexes.  I think I got my terminologies mixed up.  What I really meant is a mutex, not a semaphore (I want to be able to lock down a resource so that only one task has access to it at a time.)

A plain mutex is something that I'd like to start off with.  Thanks for your help, but for now I'd like to figure things out on my own, if I hit a wall I will post here.

Re: How to simulate semaphores with Ada's tasks?

[G.B.]

On 25.08.16 02:41, Andrew Shvets wrote:
> From what I've read, tasks do not have semaphores that can permit it to lock a piece of memory and prevent it from being accessed, is this correct?
>
> If so, then the best possible way to simulate this is to have tasks send messages to one another and synchronize when something is locked/unlocked.  Is there a better approach?
>

The thing is called Suspension_Object in Ada, see
Ada.Synchronous_Task_Control (RM D.10).

But, as others have said, it might be a good idea to
consider the use case and arrive at a protected resource.


-- 
"HOTDOGS ARE NOT BOOKMARKS"
Springfield Elementary teaching staff