Required reading: Fast mutual exclusion for uniprocessors


We revisit the topic of mutual-exclusion coordination: the techniques to protect variables that shared among multiple threads. These techniques allows programmers to implement atomic sections so that one thread can safely update the shared variables without having to worry that another thread intervening.

We focus today on uniprocessors. Even on uniprocessor one has to provide mutual-exclusion coordination, because the scheduler might schedule another thread in response to a hardware interrrupt (e.g., end of a time slice).

The technique for mutual-exclusion coordination used in v6 is disabling/enabling interrupts in the kernel. In v6, the only program with multiple threads is the kernel, thus that is the only program that needs need mutual-exclusion mechanism. User-level processes don't share data directly.

As we discussed last lecture, microkernels force server programs to deal with many similar issues as monolithic kernels, and they therefore require concurrent handling of events. This organizational requirement raises the question "How to handle multiple events concurrently at a user-level?"

  1. Use a thread package that doesn't preempt threads. Thus, the scheduler always resumes the thread that was running before preemption unless the thread released the processor explicitly. A number of systems use this approach, but it is not without challenges either: If a thread calls printf in a section of code that must be executed atomically, how do i know that printf doesn't release the processor?
  2. Use a thread package that provides primitives to mark critical sections atomically (e.g., acquire and release lock). These primitives must be implemented as atomic instructions, which can be done with, for example, a hardware try-set-and-lock (TSL) instruction.
  3. Use events. Structure program as a single loop that process events (e.g., network packet arrival, disk read completion). Each event is handled atomically.

To implement any three of these options we need to avoid blocking system calls. The kernel must support asynchronous system calls or scheduler activations.

Can we use a thread package that use the v6 kernel approach? That is, can we allow a user-level thread to disable and reenable interrupts? (Answer: not, if we care about fault isolation.)

List and insert example:

struct List {
  int data;
  struct List *next;

List *list = 0;

insert(int data) {
  List *l = new List;
  l->data = data;
  l->next = list;
  list = l;

fn() {

main() {
  thread_create(..., fn);
  thread_create(..., fn);

The paper

The paper addresses how to provide mutual-exclusion primitives that are completed implemented in software. The motivation is that some uniprocessors don't provide a hardware-level atomic instructions. It turns out, however, that the approach advocated in the paper is in general a good one, because software implementations are often more efficient than hardware implementations.

The paper describes several ways to implement test-and-set in software:

Paper discussion

  • Figure 6. Should we use RAS in the lab? If so, where would it be useful?