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?
