Semaphore: a synchronization tool based on the value of a variable, Dijkstra (1968).

In theory there must be two atomic operations on a semaphore:

• P(s) (proberen) waits until s is positive, then decreases its value (blocking).
• V(s) (vrijgeven) increases the value of s (non-blocking).

In practice a semaphore has 2 or more states.

The functions are usually implemented as Test_and_set... or Set... .

Thread() {
  Noncritical section
  ...
  P(s);
  Critical section
  V(s);
  ...
  Noncritical section
}

Categories of Semaphores

Binary versus general. A binary semaphore can take only 2 values: 0 or 1 (also called red and green). A general semaphore can take any kind of value > 0.

Binary semaphore: asymmetric versus symmetric.

For both types, the value can be decreased only if it is >0 and it is done with a Test_and_set... function.

For an asymmetric semaphore, increasing the value is non-blocking and done with a function Set... .

For a symmetric semaphore, the value can be increased only if it is 0 and it's also done with a Test_and_set... .

Asymmetrical semaphores are equivalent to mutexes.

Symmetric-Asymmetric Semaphores

Asymetric semaphore: red = 0, green = 1.

    
Test_and_set_red(&sem);  // while (sem == 0 ); sem = 0;
Set_green(&sem);         // sem = 1;

Symmetric semaphore:

Test_and_set_red(&sem);   // while (sem == 0 ); sem = 0;
Test_and_set_green(&sem); // while (sem == 1 ); sem = 1;

The type of entry protocol for the critical section with a loop is called a spin lock.

Mutex Based Semaphores

const int red=0, green = 1;
struct semaphore
{
  int light;
  pthread_mutex_t mutex;
};

void Semaphore_init(semaphore &sem, int value)
{
  light = value;
  pthread_mutex_init(&sem.mutex, NULL);
}

Asymmetric Semaphore

void Test_and_set_red(semaphore &sem) 
{
  pthread_mutex_lock(&sem.mutex);
  while (sem.light == red) {
  pthread_mutex_unlock(&sem.mutex);
  pthread_mutex_lock(&sem.mutex);
}

void Set_green(semaphore &sem) 
{
  pthread_mutex_lock(&sem.mutex);
  sem.light = green;
  pthread_mutex_unlock(&sem.mutex);
}

Symmetric Semaphore

void Test_and_set_green(semaphore &sem) 
{
  pthread_mutex_lock(&sem.mutex);
  while (sem.light == green) {
    pthread_mutex_unlock(&sem.mutex);
    pthread_mutex_lock(&sem.mutex);
  }
  sem.light = green;
  pthread_mutex_unlock(&sem.mutex);
}

POSIX Semaphores

#include 

// If pshared is 0, the semaphore is local to the current process.
// The semaphore is then shared only by the threads created
// by that process.
int sem_init(sem_t *sem, int pshared, unsigned int value);

int sem_wait(sem_t * sem);    // P(sem);
int sem_trywait(sem_t * sem); // V(sem);

int sem_post(sem_t * sem);
int sem_getvalue(sem_t * sem, int * sval);
int sem_destroy(sem_t * sem);

Dependency Graphs

Dependency graph: given a set of processes, each process must wait for a number of other processes to finish their task before it can start its own task.

Solution with General Semaphores

Introduce a semaphore s_j corresponding to each non-initial process P_j.

Let the initial value of s_j be defined by d_j, the number of immediate predecessors of P_j.

Each process must wait to begin their task on

Test_and_inc(sj);

After performing their task, each process must decrease the semaphores of all the successors.

Example

Init(s1, 0); Init(s2, 1); Init(s3, 2),
Init(s4, 1), Init(s5, 2);
P1' : T&Inc(s1); P1, Dec(s2); Dec(s3); Dec(s4);
P2' : T&Inc(s2); P2, Dec(s3);
P3' : T&Inc(s3); P3, Dec(s5);
P4' : T&Inc(s4); P4; Dec(s5);
P5' : T&Inc(s1); P5;