MUTUAL EXCLUSION ================ *Compile mutual.adb and verify that it works. It works * Run the code several times. Is the output deterministic, non-deterministic or mixed? The values printed depend on the way in which accesses to the read and increment facilities of the protected object are interleaved. The presence of entries will enforce some sort of ordering. No writes take place until at least one Incrementer task has passed its accept statement. The first task to do this will be Incrementer_03, and hence the initial values of Master and Incrementer_03 are fixed. Other values can change, depending on the scheduling of the tasks. * 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.) Requires quite some modification as functions in Ada are pure and not permited to modify an internal data structure (ie the counter). So we must change this into a procedure, although we can still use a function to read the counter. package Protected_Shared_Natural is -- a simple natural protected type Shared_Natural(Initial_Value : Natural) is function Read_Counter return Natural; procedure Read(Return_Value: out Natural); procedure Write(New_Value:Natural); procedure Increment(By : Natural); private The_Data : Natural := Initial_Value; Counter : Natural := 0; end Shared_Natural; end Protected_Shared_Natural; package body Protected_Shared_Natural is protected body Shared_Natural is Procedure Read(Return_Value : out Natural) is begin Return_Value := The_Data; Counter := Counter + 1; end Read; function Read_Counter return Natural is begin return Counter; end Read_Counter; Procedure Write(New_Value : Natural) is begin The_Data := New_Value; end Write; Procedure Increment(By : Natural) is begin the_Data := The_Data + By; end Increment; end Shared_Natural; end Protected_Shared_Natural; with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Protected_Shared_Natural; use Protected_Shared_Natural; procedure Mutual is task type Incrementer (Increment : Natural) is entry Start; entry Finish; end Incrementer; Protected_Data : Shared_Natural (42); task body Incrementer is Local_Value : Natural; begin Protected_Data.Read( Local_Value ); Put_Line ("Initial Value on Incrementer " & Positive'image (Increment) & " is " & Positive'image (Local_Value)); accept Start; for I in 1..10 loop Protected_Data.Increment (Increment); delay 0.0; end loop; Protected_Data.Read( Local_Value ); Put_Line ("Final Value on Incrementer " & Positive'image (Increment) & " is " & Positive'image (Local_Value)); accept Finish; end Incrementer; Global_Value : Natural; Incrementer_03 : Incrementer (3); Incrementer_17 : Incrementer (17); Incrementer_42 : Incrementer (42); begin Protected_Data.Read( Global_Value ); Put ("Initial Value on Mutual "); Put (Global_Value); New_Line; Incrementer_03.Start; Incrementer_17.Start; Incrementer_42.Start; Protected_Data.Read( Global_Value ); Put("Final Value on Mutual "); Put (Global_Value); New_Line; Incrementer_03.Finish; Incrementer_17.Finish; Incrementer_42.Finish; Put_Line("Num reads : " &Protected_Data.Read_Counter'Img ); end Mutual; USE OF PROTECTED OBJECTS: SEMAPHORES ==================================== * 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.) Efficiency - minimize write accesses to the protected object (aka choke point). In particular still sum into a single local variable, then add this to the protected object. Exact form of the solution will depend on whether they use the original protected_shared_natural or the modified version (with the counter). with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Semaphore_Package; use Semaphore_Package; with Protected_Shared_Natural; use Protected_Shared_Natural; procedure Sum_ints is Max_Task : constant Integer := 10; Start_Semaphore : Semaphore; Stop_Semaphore : Semaphore; Grand_Total : Shared_Natural(0); task type adder(Id : Integer; first : Integer; last : Integer); task body adder is Local_Total : Integer; begin Start_Semaphore.Wait; Local_Total := 0; for I in first..last loop Local_Total := Local_Total + I; end loop; Grand_Total.Increment(Local_Total); Stop_Semaphore.Signal; end Adder; type Adder_Ptr is access Adder; My_Task_Array : array(Integer range 1..Max_Task) of Adder_Ptr; Value, Total1, Total2 : Integer; V_Low, V_High : Integer; Ntask : Positive range 1..Max_Task; begin Put("Input value of N"); New_Line; Get(Value); Put("Value of N "); Put(Value); New_Line; Put("Input number of tasks"); New_Line; Get(Ntask); Put("Number of tasks "); Put(Ntask); New_Line; for I in 1..Ntask loop V_Low := ((Value+Ntask-1)/Ntask)*(I-1)+1; V_high := ((Value+Ntask-1)/Ntask)*I; if V_High > Value then V_High := Value; end if; Put_Line("Task " & I'Img & " Summing from " & V_Low'Img & " to " & V_High'Img ); My_Task_Array(i) := new Adder(i, V_Low, V_High); end loop; for I in 1..Ntask loop Start_Semaphore.Signal; end loop; for I in 1..Ntask loop Stop_Semaphore.Wait; end loop; Grand_Total.Read(Total1); Put("Computed Sum "); Put(Total1); New_Line; Total2 := Value * (Value+1)/2; Put("Expected Sum "); Put(Total2); New_Line; end Sum_Ints; THE COUNT ATTRIBUTE =================== * Why does the code hang and is it livelock or deadlock? To see why the code hangs, consider what the queue on the Synchronize attribute looks like as the program progresses. Recall the queue is FIFO by default (in the above, we have assumed that the child tasks reach the synchronize barrier calls in a particular order. The specific ordering doesn't matter, because the master will always be first, and that is all that is required.) Step: Queue: Released: -------------------------------------------- 0 {} None 1 Master None 2 Master, Child_1 None 3 Master, Child_1, Child_2 None 4 Master, Child_1, Child_2, Child_3 Master 5 Child_1, Child_2, Child_3, Master Child_1 6 Child_2, Child_3, Master, Child_1 Child_2 7 Child_3, Master, Child_1, Child_2 Child_3 8 Master, Child_1, Child_2, Child_3 Master 9 Child_1, Child_2, Child_3 None 10 Child_1, Child_2, Child_3 None 11 Child_1, Child_2, Child_3 None ... inf Child_1, Child_2, Child_3 None When the master terminates, there are only three tasks left queued on the entry. No more tasks arrive, so Synchronize'Count will never be 4, and no tasks will progress. As to what kind of lockup this is, note that the tasks will be blocked until one of the variables in the entry barrier changes. In this case, then, they will all be blocked. So this could be classed as a deadlock, since no one is executing any code. Note that there is a different cause from most deadlocks - i.e: there is no resource contention. * 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 "synchronization by protected objects in Ada95", and "operations on entry queues"). Make these modifications and verify that the code now works. We need to have another barrier condition in the form a boolean (initialsed to false) and consider either this boolean OR the count for entry to the protected object. Thus when the number of queued tasks reaches the required count one task is released, executes the body of the protected object and sets the boolean to true. This ensures all waiting tasks execute, until the last task enters at which stage the number of queued tasks is zero enters and resets the boolean to false. Note that we need to guard against the following scenario: Tasks 1 through 3 are queued on Blocker.Synchronize. Task 4 arrives, changing the barrier to True. Task 1 is then released, sets the boolean flag to True, and finishes. Task 1 then calls Blocker.Synchronize again. If we're not careful, Task 1 will fall through again. (In this case, the liberal scattering of delay statements means this won't happen. In general, though, it's possible). There are a couple of ways to work around this. In one of them, the boolean is replaced with a counter, and only a pre-determined number of tasks are released. The way we use below is to employ different barriers at different points of the program. 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; Triggered : Boolean := False; end Blocker; protected body Blocker is entry Synchronize when Synchronize'Count = Size or Triggered is begin if Synchronize'Count = 0 then Triggered := False; else Triggered := True; end if; end Synchronize; end Blocker; Blocker_One : Blocker (4); Blocker_Two : 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_One.Synchronize; Put("End Synchronize 1 from Task "); Put( Id); New_Line; delay 0.5; Blocker_Two.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_One.Synchronize; Put("End Synchronize 1 from Master "); New_Line; delay 0.5; Blocker_Two.Synchronize; Put("Bye from Master"); end Global; ( Note: The semantics of how Ada handles queues on protected entries means that the above is not necessary. In particular, once an entry is activated, every entry barrier is re-evaluated, and if one is open with pending tasks, one of these tasks is woken up. Any entry call that is made while these re-evaluations are occurring is not able to be woken until either a) all of the already queued tasks have been dequeued, or b) all of the barriers are false. Relying on this behaviour is somewhat fragile, though) * 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. package Protected_Shared_Natural is -- a simple natural protected type Shared_Natural(Initial_Value : Natural; Group_Size : Positive) is function Read_Counter return Natural; procedure Read(Return_Value: out Natural); procedure Write(New_Value:Natural); procedure Increment(By : Natural); entry Synchronize; private The_Data : Natural := Initial_Value; Counter : Natural := 0; Size : Positive := Group_Size; Release : Boolean := False; end Shared_Natural; end Protected_Shared_Natural; package body Protected_Shared_Natural is protected body Shared_Natural is Procedure Read(Return_Value : out Natural) is begin Return_Value := The_Data; Counter := Counter + 1; end Read; function Read_Counter return Natural is begin return Counter; end Read_Counter; Procedure Write(New_Value : Natural) is begin The_Data := New_Value; end Write; Procedure Increment(By : Natural) is begin the_Data := The_Data + By; end Increment; entry Synchronize when (Synchronize'Count = Size or Release) is begin if Synchronize'Count = 0 then Release := False; else Release := True; end if; end Synchronize; end Shared_Natural; end Protected_Shared_Natural; with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Protected_Shared_Natural; use Protected_Shared_Natural; procedure Sum_ints is Max_Task : constant Integer := 10; type Shared_Natural_Ptr is access Shared_Natural; Grand_Total : Shared_Natural_Ptr; task type adder(Id : Integer; first : Integer; last : Integer); task body adder is Local_Total : Integer; begin Grand_Total.synchronize; Local_Total := 0; for I in first..last loop Local_Total := Local_Total + I; end loop; Grand_Total.Increment(Local_Total); Grand_Total.synchronize; end Adder; type Adder_Ptr is access Adder; My_Task_Array : array(Integer range 1..Max_Task) of Adder_Ptr; Value, Total1, Total2 : Integer; V_Low, V_High : Integer; Ntask : Positive range 1..Max_Task; begin Put("Input value of N"); New_Line; Get(Value); Put("Value of N "); Put(Value); New_Line; Put("Input number of tasks"); New_Line; Get(Ntask); Put("Number of tasks "); Put(Ntask); New_Line; Grand_Total := new Shared_Natural(Group_Size=>Ntask+1, Initial_Value=>0); for I in 1..Ntask loop V_Low := ((Value+Ntask-1)/Ntask)*(I-1)+1; V_high := ((Value+Ntask-1)/Ntask)*I; if V_High > Value then V_High := Value; end if; Put (V_Low); Put(V_High); New_Line; My_Task_Array(i) := new Adder(i, V_Low, V_High); end loop; Grand_Total.synchronize; Grand_Total.Synchronize; Grand_Total.Read(Total1); Put("Computed Sum "); Put(Total1); New_Line; Total2 := Value * (Value+1)/2; Put("Expected Sum "); Put(Total2); New_Line; end Sum_Ints;