Checkpoint synchronization
You are encouraged to solve this task according to the task description, using any language you may know.
The checkpoint synchronization is a problem of synchronizing multiple tasks. Consider a workshop where several workers (tasks) assembly details of some mechanism. When each of them completes his work they put the details together. There is no store, so a worker who finished its part first must wait for others before starting another one. Putting details together is the checkpoint at which tasks synchronize themselves before going their paths apart.
The task
Implement checkpoint synchronization in your language. Make sure that the solution is race condition-free. When a worker is ready it shall not continue before others finish. A typical implementation bug is when a worker is counted twice within one working cycle causing its premature completion. This happens when the quickest worker serves its cycle two times while the laziest one is lagging behind.
If you can, implement workers joining and leaving.
Ada
<lang Ada> with Ada.Calendar; use Ada.Calendar; with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random; with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Checkpoint is
protected Checkpoint is
entry Deliver;
entry Join (Label : out Character);
entry Leave;
private
Signaling : Boolean := False;
Ready_Count : Natural := 0;
Worker_Count : Natural := 0;
Unused_Label : Character := 'A';
entry Lodge;
end Checkpoint;
protected body Checkpoint is
entry Join (Label : out Character) when not Signaling is
begin
Label := Unused_Label;
Unused_Label := Character'Succ (Unused_Label);
Worker_Count := Worker_Count + 1;
end Join;
entry Leave when not Signaling is
begin
Worker_Count := Worker_Count - 1;
end Leave;
entry Deliver when not Signaling is
begin
Ready_Count := Ready_Count + 1;
requeue Lodge;
end Deliver;
entry Lodge when Ready_Count = Worker_Count or Signaling is
begin
Ready_Count := Ready_Count - 1;
Signaling := Ready_Count /= 0;
end Lodge;
end Checkpoint;
task type Worker;
task body Worker is
Dice : Generator;
Label : Character;
Shift_End : Time := Clock + 2.0; -- Trade unions are hard!
begin
Reset (Dice);
Checkpoint.Join (Label);
loop
Put_Line (Label & " is working");
delay Duration (Random (Dice) * 0.200);
Put_Line (Label & " is ready");
Checkpoint.Deliver;
exit when Clock >= Shift_End;
end loop;
Checkpoint.Leave;
end Worker;
Set : array (1..4) of Worker;
begin
null; -- Nothing to do here
end Test_Checkpoint; </lang> Sample output:
A is working B is working C is working D is working A is ready C is ready B is ready D is ready D is working C is working A is working B is working D is ready B is ready A is ready C is ready C is working B is working D is working A is working D is ready A is ready C is ready B is ready D is working A is working C is working B is working A is ready D is ready B is ready C is ready A is working D is working C is working B is working A is ready D is ready C is ready B is ready A is working C is working D is working B is working A is ready C is ready D is ready B is ready A is working D is working C is working B is working D is ready C is ready B is ready A is ready A is working D is working C is working B is working D is ready C is ready B is ready A is ready D is working C is working B is working A is working C is ready B is ready D is ready A is ready C is working B is working D is working A is working C is ready B is ready A is ready D is ready B is working A is working D is working C is working B is ready A is ready D is ready C is ready C is working D is working B is working A is working C is ready D is ready B is ready A is ready C is working D is working B is working A is working C is ready B is ready D is ready A is ready C is working B is working D is working A is working C is ready D is ready B is ready A is ready C is working D is working A is working B is working C is ready D is ready B is ready A is ready C is working D is working A is working B is working C is ready B is ready A is ready D is ready B is working A is working D is working C is working B is ready D is ready C is ready A is ready