Three Examples in solving Synchronization

Note: This post is a note of learning Operation System Internals and Design Principles (Ninth Edition) Chapter 5, is based on my understanding. Wrong would be occurred, Thanks for indicating.

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 busy waiting method to solve Mutual Exclusion Problems. The limitation is busy waiting, it causes time consuming so it actually in low efficiency. Moreover Test() Set() the hardware based methods is hard for user in programming. Semaphore (Chinese: 信号量) is a powerful tool in solving Synchroniaztion.

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 real-world. Such as the traffic lights or Flare guns, it participates in the role of notifying.

To solve Synchronization using semaphore, we can consider this 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 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 waiting for an event which can only be triggered by the waiting processes. Deadlock (Chinese: 死锁) happens.
  • When in LIFO sequence is used to add and remove processes. Starvation (Chinese: 饥饿) could happens.

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 number of empty buffer 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 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 status of one processor.

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

For write, simply add 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 contains some code that focus on controlling the gate of writer processes.

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

It is obviously that when the first reader comes in successfully, the gate of writer must be shutten down but the gate for the other writers stills open. The first reader should modify a specific global variable readCnt, and thta variable counts the number of reader 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 (Chinese: 围棋), 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);
}