SKEDSOFT

MULTIPROCESSOR SYNCHRONIZATION
Multiprocessor system facilitates parallel program execution and read/write sharing of data and thus may cause the processors to concurrently access location in the shared memory. Therefore, a correct and reliable mechanism is needed to serialize this access. This is called synchronization mechanism. The mechanism should make access to a shared data structure appear atomic with respect to each other. In this section, we introduce some new mechanism and techniques suitable for synchronization in multiprocessors.

Test-and-Set: The test-and-set instruction automatically reads and modifies the contents of a memory location in one memory cycle. It is as follows:
function test-and-set (var m: Boolean); Boolean;
begin
test-and set:=m;
m:=rue
end;
The test-and-set instruction returns the current value of variable m (memory location) and sets it to true. This instruction can be used to implement P and V operations (Primitives) on a binary semaphore, S, in the following way (S is implemented as a memory location):

P(S): while Test-and-Set (S) do nothing;
V(S): S:=false;
Initially, S is set to false. When a P(S) operation is executed for the first time, test-and-set(S) returns a false value (and sets S to true) and the “while” loop of the P(S) operation terminates. All subsequent executions of P(S) keep looping because S is true until a V(S) operation is executed.

Compare-and-Swap
The compare and swap instruction is used in the optimistic synchronization of concurrent updates to a memory location. This instruction is defined as follows (r1and r2 are to registers of a processor and m is a memory location):
function test-and-set (var m: Boolean); Boolean;
var temp: integer;
begin
temp:=m;
if temp = r1 then {m:= r2;z:=1}
else [r1:= temp; z:=0}
end;
If the contents of r1 and m are identical, this instruction assigns the contents of r2 to m and sets z to 1. Otherwise, it assigns the contents of m to r1 and set z to 0. Variable z is a flag that indicates the success of the execution. This instruction can be used to synchronize concurrent access to a shared variable.

Fetch-and-Add
The fetch and add instruction is a multiple operation memory access instruction that automatically adds a constant to a memory location and returns the previous contents of the memory location. This instruction is defined as follows:
Function Fetch-and-add (m: integer; c: integer);
Var temp: integer;
Begin
Temp:= m;
M:= m c;
Return (temp)
end;

This instruction is executed by the hardware placed in the interconnection network not by the hardware present in the memory modules. When several processors concurrently execute a fetch-and-add instruction on the same memory location, these instructions are combined in the network and are executed by the network in the following way:

• A single increment, which is the sum of the increments of all these instructions, is added to the memory location.
• A single value is returned by the network to each of the processors, which is an arbitrary serialisation of the execution of the individual instructions.
• If a number of processors simultaneously perform fetch-and-add instructions on the same memory location, the net result is as if these instructions were executed serially in some unpredictable order.

The fetch-and-add instruction is powerful and it allows the implementation of P and V operations on a general semaphore, S, in the following manner:
P(S): while (Fetch-add-Add(S, -1)< 0) do
begin
Fetch-and-Add (S, 1);
while (S<0) do nothing;
end;

The outer “while-do” statement ensures that only one processor succeeds in decrementing S to 0 when multiple processors try to decrement variable S. All the unsuccessful processors add 1 back to S and try again to decrement it. The “while-do” statement forces an unsuccessful processor to wait (before retrying) until S is greater then 0.
V(S): Fetch-and-Add (S, 1).