Checkpoint synchronization: Difference between revisions
m (→{{header|Ada}}: whitespace/tidy up) |
No edit summary |
||
| Line 216: | Line 216: | ||
C is ready |
C is ready |
||
A is ready |
A is ready |
||
</pre> |
|||
=={{header|Tcl}}== |
|||
This implementation works by having a separate thread handle the synchronization (inter-thread message delivery already being serialized). The alternative, using a read-write mutex, is more complex and more likely to run into trouble with multi-core machines. |
|||
<lang tcl>package require Tcl 8.5 |
|||
package require Thread |
|||
namespace eval checkpoint { |
|||
namespace export {[a-z]*} |
|||
namespace ensemble create |
|||
variable members {} |
|||
variable waiting {} |
|||
variable event |
|||
# Back-end of join operation |
|||
proc Join {id} { |
|||
variable members |
|||
variable counter |
|||
if {$id ni $members} { |
|||
lappend members $id |
|||
} |
|||
return $id |
|||
} |
|||
# Back-end of leave operation |
|||
proc Leave {id} { |
|||
variable members |
|||
set idx [lsearch -exact $members $id] |
|||
if {$idx > -1} { |
|||
set members [lreplace $members $idx $idx] |
|||
variable event |
|||
if {![info exists event]} { |
|||
set event [after idle ::checkpoint::Release] |
|||
} |
|||
} |
|||
return |
|||
} |
|||
# Back-end of deliver operation |
|||
proc Deliver {id} { |
|||
variable waiting |
|||
lappend waiting $id |
|||
variable event |
|||
if {![info exists event]} { |
|||
set event [after idle ::checkpoint::Release] |
|||
} |
|||
return |
|||
} |
|||
# Releasing is done as an "idle" action to prevent deadlocks |
|||
proc Release {} { |
|||
variable members |
|||
variable waiting |
|||
variable event |
|||
unset event |
|||
if {[llength $members] != [llength $waiting]} return |
|||
set w $waiting |
|||
set waiting {} |
|||
foreach id $w { |
|||
thread::send -async $id {incr ::checkpoint::Delivered} |
|||
} |
|||
} |
|||
# Make a thread and attach it to the public API of the checkpoint |
|||
proc makeThread {{script ""}} { |
|||
set id [thread::create thread::wait] |
|||
thread::send $id { |
|||
namespace eval checkpoint { |
|||
namespace export {[a-z]*} |
|||
namespace ensemble create |
|||
# Call to actually join the checkpoint group |
|||
proc join {} { |
|||
variable checkpoint |
|||
thread::send $checkpoint [list \ |
|||
::checkpoint::Join [thread::id]] |
|||
} |
|||
# Call to actually leave the checkpoint group |
|||
proc leave {} { |
|||
variable checkpoint |
|||
thread::send $checkpoint [list \ |
|||
::checkpoint::Leave [thread::id]] |
|||
} |
|||
# Call to wait for checkpoint synchronization |
|||
proc deliver {} { |
|||
variable checkpoint |
|||
# Do this from within the [vwait] to ensure that we're already waiting |
|||
after 0 [list thread::send $checkpoint [list \ |
|||
::checkpoint::Deliver [thread::id]]] |
|||
vwait ::checkpoint::Delivered |
|||
} |
|||
} |
|||
} |
|||
thread::send $id [list set ::checkpoint::checkpoint [thread::id]] |
|||
thread::send $id $script |
|||
return $id |
|||
} |
|||
# Utility to help determine whether the checkpoint is in use |
|||
proc anyJoined {} { |
|||
variable members |
|||
expr {[llength $members] > 0} |
|||
} |
|||
}</lang> |
|||
Demonstration of how this works. |
|||
{{trans|Ada}} |
|||
<lang tcl># Build the workers |
|||
foreach worker {A B C D} { |
|||
dict set ids $worker [checkpoint makeThread { |
|||
proc task {name} { |
|||
checkpoint join |
|||
set deadline [expr {[clock seconds] + 2}] |
|||
while {[clock seconds] <= $deadline} { |
|||
puts "$name is working" |
|||
after [expr {int(500 * rand())}] |
|||
puts "$name is ready" |
|||
checkpoint deliver |
|||
} |
|||
checkpoint leave |
|||
thread::release; # Ask the thread to finish |
|||
} |
|||
}] |
|||
} |
|||
# Set them all processing in the background |
|||
dict for {name id} $ids { |
|||
thread::send -async $id "task $name" |
|||
} |
|||
# Wait until all tasks are done (i.e., they have unregistered) |
|||
while 1 { |
|||
after 100 set s 1; vwait s; # Process events for 100ms |
|||
if {![checkpoint anyJoined]} { |
|||
break |
|||
} |
|||
}</lang> |
|||
Output: |
|||
<pre> |
|||
A is working |
|||
C is working |
|||
B is working |
|||
D is working |
|||
B is ready |
|||
A is ready |
|||
D is ready |
|||
C is ready |
|||
B is working |
|||
A is working |
|||
D is working |
|||
C is working |
|||
D is ready |
|||
A is ready |
|||
C is ready |
|||
B is ready |
|||
B is working |
|||
D is working |
|||
A is working |
|||
C 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 |
|||
D is ready |
|||
A is ready |
|||
C is ready |
|||
B is ready |
|||
D is working |
|||
C is working |
|||
A is working |
|||
B is working |
|||
C is ready |
|||
A is ready |
|||
B is ready |
|||
D is ready |
|||
</pre> |
</pre> |
||
Revision as of 13:48, 11 August 2010
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. Note that a straightforward solution based on events is exposed to race condition. Let two tasks A and B need to be synchronized at a checkpoint. Each signals its event (EA and EB correspondingly), then waits for the AND-combination of the events (EA&EB) and resets its event. Consider the following scenario: A signals EA first and gets blocked waiting for EA&EB. Then B signals EB and loses the processor. Then A is released (both events are signaled) and resets EA. Now if B returns and enters waiting for EA&EB, it gets lost.
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
Tcl
This implementation works by having a separate thread handle the synchronization (inter-thread message delivery already being serialized). The alternative, using a read-write mutex, is more complex and more likely to run into trouble with multi-core machines. <lang tcl>package require Tcl 8.5 package require Thread
namespace eval checkpoint {
namespace export {[a-z]*}
namespace ensemble create
variable members {}
variable waiting {}
variable event
# Back-end of join operation
proc Join {id} {
variable members variable counter if {$id ni $members} { lappend members $id } return $id
}
# Back-end of leave operation
proc Leave {id} {
variable members set idx [lsearch -exact $members $id] if {$idx > -1} { set members [lreplace $members $idx $idx] variable event if {![info exists event]} { set event [after idle ::checkpoint::Release] } } return
}
# Back-end of deliver operation
proc Deliver {id} {
variable waiting lappend waiting $id
variable event if {![info exists event]} { set event [after idle ::checkpoint::Release] } return
}
# Releasing is done as an "idle" action to prevent deadlocks
proc Release {} {
variable members variable waiting variable event unset event if {[llength $members] != [llength $waiting]} return set w $waiting set waiting {} foreach id $w { thread::send -async $id {incr ::checkpoint::Delivered} }
}
# Make a thread and attach it to the public API of the checkpoint proc makeThread Template:Script "" {
set id [thread::create thread::wait] thread::send $id { namespace eval checkpoint { namespace export {[a-z]*} namespace ensemble create
# Call to actually join the checkpoint group proc join {} { variable checkpoint thread::send $checkpoint [list \ ::checkpoint::Join [thread::id]] } # Call to actually leave the checkpoint group proc leave {} { variable checkpoint thread::send $checkpoint [list \ ::checkpoint::Leave [thread::id]] } # Call to wait for checkpoint synchronization proc deliver {} { variable checkpoint # Do this from within the [vwait] to ensure that we're already waiting after 0 [list thread::send $checkpoint [list \ ::checkpoint::Deliver [thread::id]]] vwait ::checkpoint::Delivered } } } thread::send $id [list set ::checkpoint::checkpoint [thread::id]] thread::send $id $script return $id
}
# Utility to help determine whether the checkpoint is in use
proc anyJoined {} {
variable members expr {[llength $members] > 0}
}
}</lang> Demonstration of how this works.
<lang tcl># Build the workers foreach worker {A B C D} {
dict set ids $worker [checkpoint makeThread {
proc task {name} { checkpoint join set deadline [expr {[clock seconds] + 2}] while {[clock seconds] <= $deadline} { puts "$name is working" after [expr {int(500 * rand())}] puts "$name is ready" checkpoint deliver } checkpoint leave thread::release; # Ask the thread to finish }
}]
}
- Set them all processing in the background
dict for {name id} $ids {
thread::send -async $id "task $name"
}
- Wait until all tasks are done (i.e., they have unregistered)
while 1 {
after 100 set s 1; vwait s; # Process events for 100ms
if {![checkpoint anyJoined]} {
break
}
}</lang> Output:
A is working C is working B is working D is working B is ready A is ready D is ready C is ready B is working A is working D is working C is working D is ready A is ready C is ready B is ready B is working D is working A is working C 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 D is ready A is ready C is ready B is ready D is working C is working A is working B is working C is ready A is ready B is ready D is ready