CIS 307: TOPIC: Machine Instructions for Concurrency. Spinlocks

These topics are not treated in Tanenbaum (only TestAndSet is)

We consider some machine instructions that support concurrency.
TestAndSet and Swap are used (one or the other) for implementing spinlocks when more than one processor is used (hence interrupt masking is not sufficient). These two instructions, and all other instructions used for implementing spinlocks, do some reads and some writes to memory in a single atomic action.
Yield is used to support simple forms of context switching.
Always be conscious of the hardware support for Operating Systems functions. There are a number of reasons for this support. It may be the only way to solve the problem and, always, it allows solutions that are more efficient than purely software solutions.

TestAndSet

 We can think of the TestAndSet instruction as a function implemented atomically in hardware. Here is this function:

	function TestAndSet(x : in out integer) : boolean is
	begin
	   TestAndSet := x;
	   x          := 1;
	   return TestAndSet;
	end;

Swap

 The Swap instruction can also be thought of as a procedure implemented atomically in hardware. Here is this procedure:

	procedure Swap (a : in out integer; b : in out integer);
	   Local Variable temp : integer;
	begin
	   temp := a;
	   a    := b;
	   b	:= temp;
	end;

It is easy to see that Swap can be used to implement TestAndSet. [Just store 1 in b, swap, and return value of b.] Swap can be implemented in terms of TestAndSet but it is more difficult [you need to create a critical region].

Yield

 Also the Yield instruction can be thought of as a procedure implemented in hardware.

	procedure Yield (a : address; b : address);
	begin
	   MEMORY[a] := ProgramCounter;
	   ProgramCounter := MEMORY[b];
	end;

Yield is used to switch from one process to another. Let's represent with P^ the location where in a process P we save its PC at the time of the switch, and let's represent with * the location P^ of the current process P. Then the switch from process P to process Q can be effected with

It is easy to use Yield to implement Co-routine structures. For example, the "RESUME Q^" statement is replaced simply by "Yield *, Q^".
Equally easy is to implement a non-preemptive scheduler. Say that the location for the scheduler S is S^ and S manages the ready queue. Then a process gives up control with "Yield *, S^" and S will dispatch the selected ready process R with "yield *, R^".
Of course we have simplified our discussion by not worrying about the hardware context of processes (not even about the content of the General Purpose Registers).

SpinLocks

Spinlocks are abstract data types, or classes, that support the Busy-Wait solution of the Mutual Exclusion Problem.
The operations on spinlocks are InitLock, Lock, and UnLock.
If mutex is a spinlock that has been initialized using InitLock, then Critical Regions S1, S2, .., Sn can be protected from each other by preceding each region by a call to Lock and following it by a call to UnLock. So the region Si becomes: 
	Lock(mutex);
	Si;
	UnLock(mutex);

The pseudo code for implementing SpinLocks follows: 


	TYPE SpinLock is boolean;

	PROCEDURE InitLock(L : in out SpinLock);
	BEGIN
	   L := false;
	END;

	PROCEDURE Lock(L : in out SpinLock);
	BEGIN
	   WHILE TestAndSet(L) DO null;
	END;

	PROCEDURE UnLock(L : in out SpinLock);
	BEGIN
	   L := false;
	END;
As you can see, the implementation is quite simple and with no system overhead. It works because of the properties of the TestAndSet instruction.
Notice that this solution involves Busy Waiting.
There is no guaranty of Fairness. That is, if two processes P and Q are trying to enter a critical region protected by a locked spinlock mutex, then there is no guaranty that they will be serviced in FIFO order. Their order of entry will be random. More serious is the problem that the process P may use the spinlock within a loop and use the lock repeatedly while Q is unable to acquire it. [How can this happen?] This behavior could be avoided by giving a "Nice" behavior to the UnLock operation: when the Unlock is executed, a Yield instruction is used to check if another process is waiting and if yes, to defer to it. Of course, in most situation this is an unwarranted precaution.

Spinlocks also are dangerous to use because of the Priority Inversion Problem. See the discussion of this issue in Tanenbaum, page 39.
Two possible solutions to this problem:

ingargiola.cis.temple.edu