CSCE 313 Lecture 11

« previous | Tuesday, February 21, 2012 | next »

Classical Problems

Readers and Writers

Common Variables:

Semaphore *mutex, *wrt; // 1
int nreaders; // 0

Reader:

P(mutex);
  nreaders++;
  if (nreaders == 1) P(wrt);
V(mutex);

// do the reading...

P(mutex);
  nreaders--;
  if (nreaders = 0) V(wrt);
V(mutex);

Writer:

P(wrt);

// do the writing...

V(wrt);

Monitors and Conditions

Semaphores have been the "GOTO" of synchronization primitives

Higher-abstraction primitives are available:

• Monitors
• synchronized primitive in Java (only one thread can be in function at a time)

Only one process can be active in a monitor

Additional synchronization through conditions

Condition c;

c.cwait() suspend execution of calling process and enqueue it on condition c. The monitor now is available for other processes

c.csignal() resume a process enqueued on c. Do nothing if nothing is queued

These operations are different from P & V on semaphores; cwait always waits, and csignal wakes another process up only if there's one waiting.

Example

monitor BinSemaphore {
    bool locked; // FALSE
    condition idle;

    entry void P() {
        if (locked) idle.cwait();
        locked = TRUE;
    }

    entry void V() {
        locked = FALSE;
        idle.csignal();
    }
}

Bounded Buffer Producer/Consumer

monitor boundedbuffer {
    Item buffer[N]; // buffer has N items
    int nextin; // 0
    int nextout; // 0
    int count; // 0
    condition notFull;
    condition notEmpty;

    void deposit(Item x) {
        if (count == N) notfull.cwait();
        buffer[nextin] = x;
        nextin = (nextin + 1) mod N
        // ...
    }

    // ...
}

POSIX Thread Synchronization

real implementation (not pseudocode).

Mutex Locks

#include <pthread>
pthread_mutex_t mylock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&mylock);
// critical section
pthread_mutex_unlock(&mylock);

Only use for short periods of time!

Use condition variable for longer periods of time:

Condition Variables

We're waiting for a particular condition: while (x != y)

correct strategy:

pthread_mutex_lock(&mylock);
while (x != y) pthread_cond_wait(&mycond, &mylock);
// critical section...
pthread_mutex_unlock(&mylock);