29 Inefficient Spinning

• Consider the simple mutual exclusion mechanism we just saw :

do {
	while (TestAndSet(&lock)) ; // wait until we successfully
	// change lock from false to true
		[critical section]
	lock = FALSE; // Release lock
		[remainder section]
} while (TRUE);

• This guarantees mutual exclusion but with a high cost : that while loop spins constantly (using up CPU cycles) until it manages to enter the critical section.
• This is a huge waste of CPU cycles and it not acceptable, particularly for user processes where the critical section may be occupied for some time.

Sleep and Wakeup

• Rather than having a process spin and around, checking if it can proceed into the critical section, suppose we implement some mechanism whereby it sends itself to sleep and then is awoken only when there is a chance it can proceed.
• Functions such as sleep() and wakeup() are often available via a threading library or as kernel service calls.

Mutual Exclusion with sleep() : A first Attempt

• If constant spinning is a problem, suppose a process puts itself to sleep in the body of the spin.
• Then whoever won the competition will wake all processes before releasing the lock -so they can all try again.

do {
	while (TestAndSet(&lock)) { // If we can't get the lock, sleep.
		sleep();
	}
		[critical section]
	wake_up(all); // Wake all sleeping threads.
	lock = FALSE; // Release lock
		[remainder section]
} while (TRUE);

Towards Solving The Missing Wakeup Problem

• Somehow, we need to make sure that when a process decides that it will go to sleep (if it failed to get the lock) it actually goes to sleep without interruption, so the wake-up signal is not missed by the no-yet-sleeping process.
• In other words, we need to make the check-if-need-to-sleep and go-to-sleep operations happen atomically with respect to other threads in the process.
• Perhaps we could do this by making use of another variable, say deciding_to_sleep.
• Since we now have two locks, for clarity rename lock to mutex_lock.

while (True) {
// Spinning entry loop.
	while (True) {
	// Get this lock, so a wake signal cannot be raised before we actually sleep.
	while(TestAndSet(&deciding_to_sleep));
	// Now decide whether or not to sleep on the lock.
		if (TestAndSet(&mutex_lock)) {
			sleep();
		} else {
		// We are going in to critical section.
			deciding_to_sleep = False;
			break;
		}
		deciding_to_sleep = False; // Release the sleep mutex for next attempt.
	}
	[critical section]
	while(TestAndSet(&deciding_to_sleep)); // Don't issue 'wake' if a thread is
	// deciding whether or not to sleep.
	mutex_lock = False; // Open up the lock for the next guy.
	wake_up(all); // Wake all sleeping threads so they may compete for entry.
	deciding_to_sleep = False;
	[remainder section]
}

Question

We have overlooked something here ?

Sleeping with the Lock

• We’ve encountered an ugly problem - in fact, there are several problems with the previous example that are all related.
  • As we said before, we need to decide to sleep and then sleep in an atomic action (with respect to other threads/processes).
  • But in the previous example, when a thread goes to sleep it keeps hold of the deciding_to_sleep lock which sooner or later will result in deadlock!
  • And if we release the deciding_to_sleep lock immediately before sleeping, then we have not solved the original problem
• The solution to this problem implemented in modern operating systems, such as Linux, is to release the lock during the kernel service call sleep(), such that it is released prior to the context switch, with a guarantee there will be no interruption.
• The lock is then reacquired upon wakeup, prior to the return from the sleep() call
• .Since we have seen how this can all get very complicated when we introduce the idea of sleeping (to avoid wasteful spinning), kernels often implement a sleeping lock, called a semaphore, which hides the gore from us.