CIS 307: Spinlocks and Semaphores

[TestAndSet], [Spinlocks] [Definition and initial implementation of Semaphores], [Comments], [Posix Semaphores], [Java Semaphores], [Nutt's Implementation]

TestAndSet

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

	int TestAndSet(int *x){
	   register int temp = *x;
	   *x = 1;
	   return temp;
	}

1. Read from x into a register temp
2. Write one to x

         void Exchange(int *a, int *b) {
            int temp = *a;
            *a = *b;
            *b = temp;
         }

         boolean CompareAndSwap(int *a, int old, int new) {
            if (*a != old) {
               *a = new;
               return true;
            } else 
               return false;
         }

SpinLocks

	Lock(mutex);
	Si;
	UnLock(mutex);

The pseudo code for implementing SpinLocks follows:

	typedef int SpinLock;

	void InitLock(SpinLock *L)
	{   *L = 0; }

	void Lock(SpinLock *L)
	{   while (TestAndSet(L)) 
		;
	}

	void UnLock(SpinLock *L)
	{   *L = 0; }

	lock(&s);
	n++;
	unlock(&s);
might be executed as
	lock(&s);
	*s = 0;
	n++;
because hardware reordering of instructions. It is  necessary in 
the unlock operation to insert a barrier instruction. [Same for lock.]

Here is a possible implementation of spinlocks using the Exchange instruction:

        typedef int SpinLock;
        void InitLock(SpinLock *s) {
           *s = 0;
        }
        void Lock (SpinLock *s) {
           int L = 1;
           do {
              Exchange(&L, s);
           } while (L == 1);
        }
        void UnLock (SpinLock *s) {
           *s = 0;
        }

        typedef int SpinLock;
        void InitLock(SpinLock *s) {
           *s = 0;
        }
        void Lock (SpinLock *s) {
           do {
           } while (CompareAndSwap(s, 1, 1));
        }
        void UnLock (SpinLock *s) {
           *s = 0;
        }

A big problem of the spinlock is that by repeatedly testandsetting a location in memory it can use a high percentage of the memory bus bandwidth, thus reducing the utilization of other procesors sharing the memory bus. This location that is repeatedly accessed is called a Hot Spot in the memory. A partial solution (in the case of cache-coherent shared memories) is to change the Lock operation as follows:

	void Lock(SpinLock *L)
	{   while (TestAndSet(L))
               while (*L == 1)
		  ;
	}

There is no guaranty of Fairness for spinlocks. 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 it is checked if another process is waiting and if yes the current process defers (gives up control of CPU) to it. Of course, in most situation this is an unwarranted precaution.

Spinlocks are dangerous to use in uniprocessor systems because of the Priority Inversion Problem. [A low priority process is in the critical region. A high priority process tries to enter the region. The low priority process cannot get the CPU which is held by the high priority process. The high priority process spins in the spinlock trying to enter the region being held by the low priority process. We have a deadlock. ]

Two possible solutions to the priority inversion problem:

• Determine the maximum priority among the processes that can execute these critical regions, then make sure that all processes execute the critical regions at this priority. Since now competing processes have the same priority, they cannot preempt each other.
• Execute the critical regions with masked interrupts. Thus the current process cannot be preempted (in the case we are considering there is only one processor).

A related problem is the formation of scheduling convoys. This occurs when a process ceases to run in the middle of a critical region [because of page fault, quantum expiration, external interrupt] and then all other processes sharing this region have to wait for its completion. A number of techniques are being introduced to deal with this problem, in particular Preemption-safe Locking and Non-blocking Algorithms. [Preemption-safe locking tries to avoid preemption during a critical region by having the kernel extend the quantum of a process in the critical region or by increasing its priority. Non-blocking algorithms, expecially for implementing shared counters and queues, make sure that if a process blocks within a critical region, it can be brought back to the beginning of the critical region and another process is allowed to enter the region.]

In general spinlocks with their busy waiting mechanism are desirable (as compared to non busy waiting mechanisms like semaphores) when the scheduling and context switching time are greater than the time required to execute the critical region, or when there are processors not required to do other tasks.

The efficient implementation of spinlocks is of great concern because spinlocks are the usual foundation for synchronization, expecially in multiprocessor systems. They are used everywhere and very frequently. As the use of multiprocessor systems increases so will the interest in efficient spinlocks and in alternative synchronization mechanisms

Definition and initial implementation of Semaphores

	type semaphore = record
			    count : integer;
  1.			    q     : queue of processes;
			 end record;
	procedure initsem (s : in out semaphore; n : integer) is
	begin
	   s.count := n; initialize s.q to the empty queue;
	end;
	procedure P(s : in out semaphore) is
	begin
  2.	   s.count := s.count - 1;
  3.	   if s.count < 0 then 
  4.	      Remove this process from Running, add it 
	              to s.q, and reschedule;
	end;
	procedure V(s : in out semaphore) is
	begin
  5.	   s.count := s.count + 1;
  6.	   if s.count <= 0 and s.q is not empty then
  7.	      Remove a process from s.q, add it to the Ready 
		      Queue, and reschedule;
	end;

Comments

• On line 1. we talk of a "queue of processes". A process is usually represented by a process id, a pointer or an index that refers to a Process Control Block (PCB). A PCB contains the relevant information about a process state.
• Lines 2., 3., and 4. form a critical region. The same is true for lines 5., 6., and 7.. As such they need to be enforced either by masking interrupts (in single processor systems) or by using spinlocks.
• The P operation is also called Down or Wait. The V operation is also called Up or Signal.
• Reschedule operates as follows: say A is the highest priority process in the Ready queue (you may assume that there is always one such process, at least a Null process).
  • If A has higher priority than the currently running process B, move B to the Ready queue and A to Running. [This is a pre-emption - in some cases, for efficiency, the switch is delayed until the time-slice expires or the current process blocks.]
  • If A does not have higher priority than the currently running process B, do nothing.
  • If there is no running process, move A to Running.
  In all cases, resume the (possibly new) running process.
• If initsem is called with the parameter n set to 0, we say that we have a Blocking Semaphore; if with 1, we say that we have a Boolean or Mutual Exclusion Semaphore; and if n is greater than 1, we say that we have a Counting Semaphore.
  Boolean semaphores are the non-busy-waiting analogs of spinlocks.

Using semaphores we can achieve a number of different behaviors:

• If S is a boolean semaphore, then we can implement related critical regions by prefixing them with the statement P(S); and affixing them with V(S);
• If S is a counting semaphore initialized to n (say, 10), then up to n (10) different processes could be executing a region enclosed by P(S)..V(S) statements.
• If S is a blocking semaphore, then we can make sure that a process completes execution of statement A before another process starts execution a statement B, by following A with the statement V(S) and preceding B with the statement P(S). This is for example one way of implementing the arc semantics in Precedence Graphs.

Semaphores do not suffer the same form of the Priority Inversion Problem as Spinlocks. You may see the kind of Priority Inversion Problem that can arise for Semaphores in the following note about the Mars Rover. We have a high priority process communicating with a low priority process using a small critical region. While the low priority process is in the critical region the high priority process waits in the semaphore protecting the region. If an intermediate, independent process starts running at this point, it preempts the low priority process and prevents the higher priority job to get on its important way.

Posix Semaphores

       #include < semaphore.h>

       int sem_init(sem_t *sem, int pshared, unsigned int value);
       int sem_wait(sem_t * sem);
       int sem_trywait(sem_t * sem);
       int sem_post(sem_t * sem);
       int sem_getvalue(sem_t * sem, int * sval);
       int sem_destroy(sem_t * sem);

Java Semaphores

Nutt's Implementation

#define	 N   ..         /* The number of semaphores */

int      value[N];	/* Keeps the count for the semaphores   */
boolean  sem[N];	/* Spinlocks to protect critical region */
			/*   of semaphore */
boolean  hold[N];	/* Used to temporarily "enqueue" tasks  */
			/* waiting on sem */

void initsem(int s, m) {
	value[s] = m; sem[s] = FALSE; hold[s] = TRUE;}
void P(int s) {
	while (TS(sem[s]));	/* Lock */
	value[s]--;
	if (value[s] < 0) {
	   sem[s] = FALSE;	/* Unlock */
	   while(TS(hold[s])) yield(Q); /* Here the process enters */
			/* a new Critical Region where it gives    */
			/* control to Q, a scheduler. It is a loop */
			/* since we may repeatedly be given control*/
			/* back from yield and find a blocked semaphore.*/
	}else
	   sem[s] = FALSE;}	/* Unlock */
void V(int s){
	while (TS(sem[s]));	/* Lock */
	value[s]++;
	if (value[s] <= 0){	/* Somebody is waiting in hold to enter CR*/
	   while (!hold[s]);	/* We check if there is a concurrent V. */
				/* It is a loop */
				/* because we might otherwise have two or more */
				/* consecutive V operations all setting (see next */
				/* statement) hold[s] to false. */
	   hold[s] = FALSE;	/* Here we free a process waiting in P,*/
				/* namely on hold[s].  */
	}
	sem[s] = FALSE;}	/* Unlock */