Three Examples in solving Synchronization

Note: This post is summary of learning Operation System Internals and Design Principles (Ninth Edition) Chapter 5

As we know the Peterson Algorithms that allows two or more (actually it can) processes to share a single-use resource without conflict by using the busy waiting method to solve Mutual Exclusion Problems. The limitation is busy waiting, it causes time-consuming so it is actually in low efficiency. Moreover, Test() Set() the hardware-based methods are hard for users in programming. Semaphore is a powerful tool in solving Synchronization.

Semaphore

A semaphore is simply a variable.

Except for initializing, wait() and signal() functions should be opearted in atom time.

A trivial semaphore is a plain variable that is changed depending on programmer-defined conditions.

We can realize semaphore as used in the real world. Such as the traffic lights or Flare guns, which participate in the role of notifying.

To solve Synchronization using semaphore, we can consider the following example.

using namespace std;
typedef struct{
    int value;
    struct process *queue; // PCB pointer
} semaphore;

void wait(semaphore *S){
    S->value--;
    if (S->value < 0){
        // No avaliable sources，Pushing process into semaphore waiting queue
        block();
    }
}
void signal(semaphore *S){
    S->value++;
    if (S->value <= 0){
        // Wake up a process from semaphore waiting queue
        wakeup(P);
    }
}

// Thread 0
void t0() {
  wait(semaphore);
  // Enter Critical Section
  signal(semaphore);
}

// Thread 1
void t1() {
  wait(semaphore);
  // Enter Critical Section
  signal(semaphore);
}

The key point of semaphore is that it can be executed in atomic time, in a single processor, it can stop interrupt when invoking wait() and signal(), but in multiprocessor, it is needed to add Count Down Latch.

Causing DeadLock and Starvation

• When two or more processes wait for an event that can only be triggered by the waiting processes. Deadlock happens.
• When in LIFO sequence is used to add and remove processes. Starvation could happen.

Synchronization Problems

Producer and Consumer Problem

For the problem detailed description, it can be found at Oracle.

Producer can produce an item and append it to shared buffer.

Consumer can take an item from the shared buffer and consume it.

Solving by using 3 semaphores mutex, empty and full .

• Semaphore mutex protects in accessing the buffer pool.
• Counting Semaphore empty and full represent a number of empty buffers and full buffer.

empty = 7 // Assuming buffer size is 7
full = 0
// producer
do {
    p = produce();
    wait(empty); // wait if empty slots in buffer <= 0 (buffer full)
    wait(mutex);
    buffer.push_back(p);
    signal(mutex);
    signal(full); // tell others that it creating a new full buffer slot
} while(true);

// consumer
do {
    wait(full); // wait if full slots in buffer <= 0
    wait(mutex);
    p = buffer.pop();
    signal(mutex);
    signal(empty); // tell others that it creating a new empty buffer slot
  	consume(p);
} while(true);

Readers and Writers Problem

For this question, consider as File I/O, there could be several processes that read a shared resource at the same time. But it cannot be permitted that two or more processes write that resource simultaneously. This problem is discussed under the status of one processor.

Solving by using 2 semaphores mutex and wrt to control processes running into the Critical Section.

For write, simply add a mutex wrt surrounding the write() method.

wait(wrt);
write();
signal(wrt);

But when it comes to read, not so easy to solve these problems

1. It can satisfy two or more processes reading simultaneously.
2. It must prevent writing processes from getting into the Critical Section.

If we do the same as write,

wait(mutex);
read();
signal(mutex);

It works with [2] but it does not support [1]. But this idea works, what we do is to modify something. StartRead() and EndRead() methods contain some code that focuses on controlling the gate of writer processes.

StartRead();
read();
EndRead();

It is obvious that when the first reader comes in successfully, the gate of writer must be shutting down but the gate for the other writers stills open. The first reader should modify a specific global variable readCnt, and that variable counts the number of readers who are reading simultaneously.

readCnt = 0; // initialize reader counter

void StartRead() {
  wait(mutex); // Mutex to protect readCnt Critical Section
  readCnt++;
  if (readCnt == 1) // The first reader in charge of preventing writers from entering
    wait(wrt);
  wait(mutex); // Mutex to protect readCnt Critical Section
}

void EndRead() {
  wait(mutex); // Mutex to protect readCnt Critical Section
  readCnt--;
  if (readCnt == 0) // The last reader in charge of freeing writers
    signal(wrt);
  wait(mutex); // Mutex to protect readCnt Critical Section
}

do {
  StartRead();
  read(); // Critical Section
  EndRead();
} while(true);

do {
  wait(wrt); // Mutex make sure only one writer process in Critical Section
  write(); // Critical Section
  signal(wrt); // Mutex
} while(true);

Goer Problem

Two people play Go, Give Two situations of:

1. Black sente
2. The first color sente

Solution for situ.1

Semaphore black = 1;
Semaphore white = 0;

while (playing) {
  wait(black);
  black();
  signal(white);
}

while (playing) {
  wait(white);
  white();
  signal(black);
}

Solution for situ.2

Semaphore mutex = 1;
int turn = 0;

while (playing) {
  wait(mutex);
  if (turn != 2)
    black();
  turn = 2;
  signal(mutex);
}

while (playing) {
  wait(mutex);
  if (turn != 1)
    white();
  turn = 1
  signal(mutex);
}