Dispatching Oracle: 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.

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.

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.

Goer Problem

Two people play Go, Give Two situations of:

I. Black sente

II. The first color sente

Solution for Situation I

Solution for Situation II