Operating Systems: Virtualization, Concurrency & Persistence/

...

/

Covering Conditions

Covering Conditions

Let's discuss one last use case of the condition variables, the covering conditions.

We'll cover the following...

We’ll now look at one more example of how condition variables can be used. This code study is drawn from Lampson and Redell’s paper on Pilot“Experience with Processes and Monitors in Mesa” by B.W. Lampson, D.R. Redell. Communications of the ACM. 23:2, pages 105-117, February 1980. A terrific paper about how to actually implement signaling and condition variables in a real system, leading to the term “Mesa” semantics for what it mzshortns to be woken up; the older semantics, developed by Tony Hoare, then became known as “Hoare” semantics, which is hard to say out loud in class with a straight face., the same group that first implemented the Mesa semantics described above (the language they used was Mesa, hence the name).

The problem

The problem they ran into is best shown via simple example, in this case in a simple multi-threaded memory allocation library. Given below is a code snippet that demonstrates the issue.

Press + to interact
// how many bytes of the heap are free?
int bytesLeft = MAX_HEAP_SIZE;
// need lock and condition too
cond_t c;
mutex_t m;
void * allocate(int size) {
  Pthread_mutex_lock(&m);
  while (bytesLeft < size)
    Pthread_cond_wait(&c, &m);
  void *ptr = ...; // get mem from heap
  bytesLeft -= size;
  Pthread_mutex_unlock(&m);
  return ptr;
}
void free(void *ptr, int size) {
  Pthread_mutex_lock(&m);
  bytesLeft += size;
  Pthread_cond_signal(&c); // whom to signal??
  Pthread_mutex_unlock(&m);
}

As you might see in the code, when a thread calls into the memory allocation code, it might have to wait in order for more memory to become free. Conversely, when a thread frees memory, it signals that more memory is free. However, this code above has a problem: which waiting thread (there can be more than one) should be woken up?

Consider the following scenario. Assume there are zero bytes free; thread TaT_a ...