Implementation of Lock using spinlocks in Anderson's Operating Systems Principles and Practice

Question

Given the following pseudocode on a multiprocessor system:

class SpinLock {
   private:
     int value = 0; // 0 = FREE; 1 = BUSY
 
   public:
     void acquire() {
         while (test_and_set(&value)) // while BUSY
             ; // spin
     }
 
     void release() {
         value = 0;
         memory_barrier();
     }
 }

where the test-and-set instruction atomically reads a value from memory to a register and writes the value 1 to that memory location.

Now they implement Locks the following way:

class Lock {
    private:
      int value = FREE;
      SpinLock spinLock;
      Queue waiting;
    public:
      void acquire();
      void release();
 }
 
 Lock::acquire() {
     spinLock.acquire();
     if (value != FREE) {
         waiting.add(runningThread);
         scheduler.suspend(&spinLock);
        // scheduler releases spinLock
     } else {
         value = BUSY;
         spinLock.release();
     }
 }
 
 void Lock::release() {
     TCB *next;
 
     spinLock.acquire();
     if (waiting.notEmpty()) {
         next = waiting.remove();
         scheduler.makeReady(next);
     } else {
         value = FREE;
     }
     spinLock.release();
 }
 class Scheduler {
   private:
     Queue readyList;
     SpinLock schedulerSpinLock;
   public:
     void suspend(SpinLock *lock);”
     void makeReady(Thread *thread);
 }
 
 void
 Scheduler::suspend(SpinLock *lock) {
     TCB *chosenTCB;
 
     disableInterrupts();
     schedulerSpinLock.acquire();
     lock->release();
     runningThread->state = WAITING;
     chosenTCB = readyList.getNextThread();
     thread_switch(runningThread,
                   chosenTCB);
     runningThread->state = RUNNING;
     schedulerSpinLock.release();
     enableInterrupts();
 }
 
 void
 Scheduler::makeReady(TCB *thread) {
     disableInterrupts();
     schedulerSpinLock.acquire();
     readyList.add(thread);
     thread->state = READY;
     schedulerSpinLock.release();
     enableInterrupts();
 }

I don't understand how this works. Assume we are in thread A when we call acquire() and the Lock is owned by some other thread B.

We acquire the spinlock of the Lock object, add the thread to the waiting list and call scheduler.suspend with the Lock's spinlock as argument. In the suspend method we will acquire the spinlock of the scheduler, assuming this is free, we then release the spinlock of the Lock, change the state of the running thread A to waiting, get a thread C from the ready queue and then perform a context switch.

I don't understand how the scheduler's spinlock is released now. In the context switch the stackpointer is changed to that of the new thread C, also the registers are exchanged, specifically also the instruction pointer, so the statement after thread_switch aren't executed until the old thread C is allocated CPU time again, correct? So let's assume the scheduler's spinlock is not free, but is held by the thread A.

Assume that thread B releases its lock. It acquires the Lock's spinlock, which is free, and there is at least one thread in the waiting queue, namely A. Suppose that A is chosen as next, so we call scheduler.makeReady with thread A as argument. But now inside makeReady there's a call to acquire the scheduler's spinlock, which wasn't released, because we performed a context switch before schedulerSpinlock.release() was called inside Scheduler::suspend() when we were executing thread A. So how can thread A release the scheduler's spinlock now, if we cannot run it again?

Answer 1

[caveat: I haven’t read Anderson].

Thread_switch() stops the execution of one thread, and resumes the execution of another. This other will immediately return, on its own stack, to the instruction after the call it made to thread_switch() which stopped it.

If we assume every thread which is not running became not running because of calling suspend, then the freshly woken thread will release the scheduler spinlock that was acquired by the one that suspended itself. If we can’t make that assumption, but can assume that every call to thread_switch is of the form:

 schedulerSpinLock.acquire();
 ...
 thread_switch(cur, new);
 ...
 schedulerSpinLock.release();

Then it is sufficient to ensure that the scenario you envisioned will not happen -- schedulerSpinLock will be released by C either because C is exiting suspend, or some other function which repeats the pattern of suspend.

The goodness of this design may be debatable. Whether you should release a spinlock() in one thread that was allocated in another is probably a topic of hot debate in some circles. Rest assured, most kernel’s have a some bit of juggling pure semantics to handle the transition when something is technically suspended but still executing, or technically running, yet still suspended.