|
Laboratory 4
Ada95: Protected Objects
- If you did not get to task rendezvous in L3, go back and look at this section.
- This week you should aim to complete up the end of condition synchronization. You can leave entry calls and barriers until next week.
- More generally - the labs are designed to make you think. It is not expected that you will complete them in 2 hours. Rather I would expect most of you to take around 4.5 hours - 0.5 hours to read it before your lab, 2 hours in your assigned lab, and 2 hours afterwards. If you have questions concerning a previous lab, ask your tutor in the lab, or come and talk to me (Uwe). Also, if you want to drop in on any other lab session, that is possible, providing room is available.
- The gnat environment is only available on the linux systems. To work from home you must ssh to machine partch.
Protected Objects
A protected unit may be declared as a type or as a single instance; it has a specification and a body. The interface can contain functions, procedures and entries:
protected_type_declaration ::=
protected type identifier [discriminant-part] [is protected_definition];
single_protected_declaration ::= protected defining_identifier is protected_definition;
protected_definition ::=
{protected_operation_declaration}
[private
{protected_element_declaration}]
end identifier;
protected_operation_declaration ::= subprogram_declaration | entry_declaration
protected_element_declaration ::=
protected_operation_declaration | component_declaration
The body, which may be compiled separately from the specification, is declared using the following syntax:
protected_body ::=
protected body identifier is
{protected_operation_item}
end identifier
protected_operation_identifier ::=
subprogram_declaration | subprogram_body | entry_body
entry_body ::=
entry identifier entry_body_formal_part entry_barrier is
declarative part
begin
sequence-of-statements
end identifier;
entry_body_formal_part ::=
[(entry_index_specification)] parameter_profile
entry_barrier ::= when condition
entry_index_specification ::=
for defining_identifier in discrete_subtype_definition
Like task types, protected types are limited types.
Protected Types and Mutual Exclusion
The following code shows how a protected type can be used to provide simple mutual exclusion
- File protected_shared_natural.ads
package Protected_Shared_Natural is
protected type Shared_Natural(Initial_Value : Natural) is
function Read return Natural;
procedure Write (New_Value : in Natural);
procedure Increment (By : in Natural);
private
The_Data : Natural := Initial_Value;
end Shared_Natural;
end Protected_Shared_Natural;
- File protected_shared_natural.adb
package body Protected_Shared_Natural is
protected body Shared_Natural is
function Read return Natural is
begin
return The_Data;
end Read;
procedure Write (New_Value : in Natural) is
begin
The_Data := New_Value;
end Write;
procedure Increment (By : in Natural) is
begin
The_Data := The_Data + By;
end Increment;
end Shared_Natural;
end Protected_Shared_Natural;
All that is done is to have a single protected shared natural, but this natural is encapsulated and can only be access by the three subprograms: read, write and increment.
To demonstrate the use of this protected variable the following program creates several tasks, has each task increment the variable 10 times with an increment that depends on the task id before terminating. The master task prints out the value of the shared variable before and after task termination.
ACTIONS
- Compile mutual.adb and verify that it works.
- Run the code several times. Is the output deterministic, non-deterministic or mixed?
- Modify the code to include a counter that is incremented each time the shared data is read, and a new function that will print out the value of this counter. Have the master task call this function after all tasks have terminated. (You will encounter a fundamental problem in trying to do this which will mean that your modifications will have to be more extensive than you might have expected at first sight.)
Condition synchronization
A protected entry is similar to a protected procedure in that it is guaranteed to execute in mutual exclusion and has read/write access to the encapsulated data. However, a protected entry is guarded by a boolean expression (called a barrier) inside the body of the protected object: if this barrier evaluates to false when the entry call is made, the calling task is suspended until the barrier evaluates to true and no other tasks are currently active inside the protected object. Hence protected objects can be used to implement condition synchronization.
If more than one task is queued on a particular protected entry, then by default queued entries are ordered in a first-in-first-out fashion. This is similar to task entry queues.
Example Use of Protected Objects: Semaphores
Using protected objects we can easily construct a semaphore. Recall that a semaphore is a protected shared counter, such that a call to wait will
- if the counter is positive, decrement the counter and allow the task to continue
- if the counter is zero, suspend the task and wait until you are awoken by a signal.
while a call to signal will increment the shared counter and
- if there are waiting threads release ONE of them (not defined which) and then continue execution
- if there are no waiting threads the value of the counter is just incremented before the calling thread continues execution.
Implementation of a semaphore is now very easy:
- File semaphore_package.ads
package Semaphore_Package is
protected type Semaphore (Initial : Natural := 0) is
entry Wait; -- P operation
procedure Signal; -- V operation;
private
Value : Natural := Initial;
end Semaphore;
end Semaphore_Package;
- File semaphore_package.adb
package body Semaphore_Package is
protected body Semaphore is
entry Wait when Value > 0 is
begin
Value := Value - 1;
end Wait;
procedure Signal is
begin
Value := Value + 1;
end Signal;
end Semaphore;
end Semaphore_Package;
ACTIONS
In last weeks lab you implemented a code that summed integers from 1..N using a number of tasks. Each task was allocated a distinct sub-range adding the numbers in this sub-range together to produce a sub-total. The sub-totals were then summed to produce the final grand-total. Exactly how this was done was up to you, but the only synchronization primitive that you had access to was atomic read/write to shared variables.
From this exercise the take home message should have been - "yes we can do this, but it is very messy, and took me at least 6 hours to complete the lab. Isn't there an easier way?" Of course there is!
- Repeat last weeks lab exercise to sum integers from 1..N, but now use semaphores to synchronize the start and termination of the tasks, and a protected shared integer to hold the sum. In designing your code give careful consideration to efficiency. Have your tutor check your final solution. (NOTE: as you will see shortly we should not be using semaphores at all, rather we should include the synchronization within the shared object.)
In general there are three common uses of semaphores:
- Locks: A binary semaphore with options of 0 and 1 is equivalent to a simple lock (multiple calls to signal only ever increment the counter to 1). Thus if the semaphore is initialized to one a call to wait will correspond to a request to lock, while a call to signal corresponds to unlock.
- Countdown and Lock: By setting the semaphore to a specific value we can limit the number of tasks executing a specific block of code. For example if the semaphore is initialized to 10 the first 10 requests to wait will proceed without problems. The 11th will, however, stall. If on exit from the critical region a task calls signal it will release any other task waiting on entry. This is like being the owner of a pub and having a bouncer on the door to ensure that only 75 persons are in your pub at any one time!
- Notification: If we want one thread to inform one or more other threads that an event has occurred we can initialize the tread to zero, this causes threads calling wait to stall, until the notifying thread calls signal to increment the counter. Note, however, multiple calls top signal would be required to release all waiting threads.
You can leave the following until next week if you run out of time
Entry calls and barriers
At any instant in time, a protected entry is either open or closed. It is open if, when checked, the boolean expression evaluates to true; otherwise it is closed. Recall from lectures entry barriers for protected objectes are evaluated:
- on calling a protected entry, and then only those parts of the barrier which might have changed since the last evaluation
- on leaving a protected procedure or entry, related barriers with tasks queued are evaluated (again only those parts that might have changed).
The Count Attribute
There are many examples when we might want to queue requests and process them in batches, e.g. email may only be sent when there are a certain number of messages ready to be transferred (or if we fail to meet that number within a set time send the messages anyway). We can do this using the count attribute of a protected object. This gives the current number of tasks queued on the specified entry.
ACTIONS
In the second part of last weeks lab you wrote a program to synchronize multiple tasks using the accept construct and a number of pairwise synchronizations. Noting the count attribute you decide that a much easier way to achieve this effect would be to have all tasks wait on an entry point to a protected object until the right number of tasks were in the queue and then release them all. To test this you write the following code:
with Ada.Text_IO ; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
procedure Global is
protected type Blocker (Group_Size : Positive) is
entry Synchronize;
private
Size : Positive := Group_Size;
end Blocker;
protected body Blocker is
entry Synchronize when Synchronize'Count = Size is
begin
null;
end Synchronize;
end Blocker;
Blocker_Instance : Blocker (4);
task type Child_Task (Id : Integer);
task body Child_Task is
begin
Put("Hello From Task "); Put( Id); New_Line;
delay 0.5;
Blocker_Instance.Synchronize;
Put("End Synchronize 1 from Task "); Put( Id); New_Line;
delay 0.5;
Blocker_Instance.Synchronize;
Put("Bye From Task "); Put( Id); New_Line;
end Child_Task;
Child_1 : Child_Task (1);
Child_2 : Child_Task (2);
Child_3 : Child_Task (3);
begin
Blocker_Instance.Synchronize;
Put("End Synchronize 1 from Master "); New_Line;
delay 0.5;
Blocker_Instance.Synchronize;
Put("Bye from Master");
end Global;
unfortunately the code either deadlocks or livelocks - well it hangs!!
- Why does the code hang and is it livelock or deadlock?
- In principle we can provide synchronization of multiple tasks using the above code, but it requires slight modification to the protected object (see lecture notes chapter 3, "synchronization by protected objects in Ada95", and "operations on entry queues"). Make these modifications and verify that the code now works.
- Now return to the problem of adding numbers 1-N that you worked on above. Instead of using a protected object and a semaphore, include synchronisation constructs within the protected object. That is when a task has completed adding its local sum to the protected object it should queue on an entry point until all other tasks have also completed their partial sums.
For the swift, the brave and the foolish here is a little bit on entry families. If you don't look at this, don't worry, we will come back to it next week.
Entry Families
A protected type can also declare a family of entries by placing a discrete subtype definition in the specification of the entry declaration. This is like having a separate entry point for each member of the family. The barrier associated with the entry can use the index of the family (usually to index into an array of booleans).
To give an example of the use of an entry family consider the following program. This defines a protected type that is used to communicate data between the various tasks. A group type is defined with number_of_children+1 elements. The protected procedure send_to_group sends a data_item to a particular group, while a family of entries is used to retrieve data from a particular group. Within this family entry 0 is used by the Master to broadcast data to all the child tasks, while entries 1-N and used to communicate with a specific child of the same number.
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
procedure Multi_Cast is
Number_Of_Children : constant Positive := 3;
subtype Children is Positive range 1..Number_Of_Children;
type Group is new Natural range 0..Number_Of_Children;
type Group_Data_Arrived is array (Group) of Boolean;
protected Type Group_Controller is
procedure Send (To_Group: in Group; This_Data : in Integer);
entry Receive (Group) (Data : out Integer);
private
Arrived : Group_Data_Arrived := (others => False);
The_Data : Integer;
end Group_Controller;
protected body Group_Controller is
procedure Send (To_Group: in Group; This_Data : in Integer) is
begin
if Receive (To_Group)'Count > 0 then
Arrived (To_Group) := True;
The_Data := This_Data;
end if;
end Send;
entry Receive (for From in Group) (Data : out Integer)
when Arrived (From) is
-- this is a family of entries
begin
if Receive(From)'Count = 0 then
Arrived(From) := False;
end if;
Data := The_Data;
end Receive;
end Group_Controller;
Controller_Instance : Group_Controller;
task type Child_Task is
entry Child_Id (Id : in Children);
end Child_Task;
Task_Array : array (Children) of Child_Task;
task body Child_Task is
Local_Data : Integer;
Local_Id : Children;
begin
accept Child_Id (Id : in Children) do
Local_Id := Id;
end Child_Id;
Put("Hello From Task "); Put (Local_Id); New_Line;
-- receive broadcasted data
Controller_Instance.Receive (Group(0)) (Local_Data);
Put("Task and Data "); Put(Local_Id); Put(Local_Data); New_Line;
-- read individual data
Controller_Instance.Receive (Group(Local_Id)) (Local_Data);
Put("Task and Data "); Put(Local_Id); Put(Local_Data); New_Line;
end Child_Task;
begin
for i in Task_Array'Range loop
Task_Array (i).Child_Id (i);
end loop;
-- broadcast data
delay 2.0;
Controller_Instance.Send (0,999);
-- communicate individual data
delay 2.0;
for i in Task_Array'Range loop
Controller_Instance.Send (Group (i), i+10);
end loop;
end Multi_Cast;
When the master sends data to a particular group, the send procedure looks to see if any tasks are waiting on the receive entry for that particular member of the family. If tasks are waiting, it sets a boolean flag associated with the member to true. On exit from the procedure, the barriers associated with the receive family entries are re-evaluated. The appropriate groups boolean evaluates to true so that entry of the family is open. The entry body is executed and, if only one task is waiting the boolean is set to false; in either case the data is sent to the first queued task. If the guard is still open, the entry body is executed again, and so on until all tasks queued for the group are released with the multi-cast value. Note that, once a task is executing inside the protected object, no other task can join an entry queue or be removed from an entry queue.
ACTIONS
- Compile and run the above multi_cast code. It should work as expected. However, now remove the delay statements from the master task and try again. You should find that the code now hangs. What you have observed is called a race condition. Explain what is happening.
Next Week
More on entry families, requeue and select.
|
