Enforced Synchronization Mechanisms

Tom Kelliher, CS42

Oct. 16, 1996

The Problem with Semaphores

Also locks and condition variables.

1. May forget to use them (one or both).

2. May reverse them.

3. May replace one with the other.

In short, no enforcement of mutual exclusion.

Critical Regions

• Programming language construct.

• All shared variables must be declared so.

• Language ensures mutual exclusion.

• Does this cover everything?

Syntax

(C style)

shared T v;

...

region v when B do S;

Semantics

1. v may only be accessed within a region.

2. If boolean condition B is false, process waits.

3. S is the body of the exclusive region.

Producer-Consumer Example

shared struct
{
   item pool[N];
   int count = 0, in = 0, out = 0;
} buffer;

producer:

while (1)
{
   produce into next;

   region buffer when count < N
   {
      pool[in] = next;
      in = ++in % N;
      ++count;
   }
}


consumer:

while(1)
{
   region buffer when count > 0
   {
      next = pool[out];
      out = ++out % N;
      --count;
   }

   consume next;
}

Implementation

Associated, by compiler, with each shared variable:

1. Semaphores: mutex, firstDelay, secondDelay.

2. int counts: firstCount, secondCount.

Uses of compiler variables:

• firstDelay: Holding place when B false.

• secondDelay: Holding place for re-testing B.

• ``Passing the mutex baton.''

Implementation:

mutex.wait();
while (!B)
{
   ++firstCount;
   if (secondCount > 0)
      secondDelay.signal();
   else
      mutex.signal();

   firstDelay.wait();
   --firstCount;
   ++secondCount;
   if (firstCount > 0)
      firstDelay.signal();
   else
      secondDelay.signal();

   secondDelay.wait();
   --secondCount();
}

S;

if (firstCount > 0)
   firstDelay.signal();
else if (secondCount > 0)
   secondDelay.signal();
else
   mutex.signal();

Monitors

Critical region problem: programmer, not designer, decides how shared variables are used once obtained.

Monitor, A C++ class with:

• Mutual exclusion.

• Condition variables. (No associated locks. Why not?)

• Class controls how variables used.

• Condition variables with wait and signal.

• Design question: who continues on a signal?

Syntax

Like a class, with condition variables.

Semantics

1. Mutual exclusion guaranteed.

2. Shared variables can be modified only in designer-specified manner.

3. Process ``leaves'' monitor on wait and sleeps.

4. If process A signals condition waited on by process B:
   1. Process A leaves monitor and sleeps (in high-priority queue).

   2. Process B resumes within monitor.

   3. If process B waits again or leaves monitor, processes in high-priority queue get first shot at monitor.

Producer-Consumer Example

monitor buffer
{
   item pool[N];
   int count, in, out;
   condition nonFull, nonEmpty;

 public:

   buffer();
   void produce(item next);
   item consume(void);
};

buffer::buffer()
{
   count = in = out = 0;
}

void buffer::produce(item next)
{
   if (count == N)
      nonFull.wait();

   pool[in] = next;
   in = ++in % N;
   ++count;
   nonEmpty.signal();
}
      
item buffer::consume(void)
{
   item temp;

   if (count == 0)
      nonEmpty.wait();

   temp = pool[out];
   out = ++out % N;
   --count;
   nonFull.signal();
   return temp;
}

Implementation

Additional variables for each class instance:

1. mutex semaphore.

2. priority semaphore for signalers.

3. priorityCount int to count signalers.

Each class method, m(), implemented:

mutex.wait();
m();
if (priorityCount > 0)
   priority.signal();
else
   mutex.signal();

Condition wait ( c.wait()):

++cCount;
if (priorityCount > 0)
   priority.signal();
else
   mutex.signal();
cSem.wait();
--cCount;

Condition signal ( c.signal()):

if (cCount > 0)
{
   ++priorityCount;
   cSem.signal();
   priority.wait();
   --priorityCount;
}

Sun's Solaris 2

Multiprocessor support --- can't disable interrupts to achieve mutual exclusion.

Adaptive mutex:

• Semaphore implemented as spinlock. Why spinlock?
  1. Spin if thread holding lock is running.

  2. Sleep otherwise.

  Tradeoff: sleep overhead vs. CPU cycles wasted spinning.

• Always sleep on uniprocessors.