Semaphores
Synchronization tool that does not require busy waiting.
Semaphore S represents an integer variable that can only be accessed via two indivisible (atomic) operations.
semaphore는 다수의 thread 사이의 병행성 유지를 위해 OS 단위에서 제공되는 기법이다.
기본적인 작동 원리는 특정 thread가 특정 signal을 수신할 때까지 정해진 위치에서 waiting하도록 강제하는 것이다.
Two Types of Semaphores
Counting semaphore – integer value can range over an unrestricted domain.
Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement than counting semaphore; also known as mutex lock.
mutex semaphore라고도 부르며 변수가 0 또는 1의 binary 값만 갖는 semaphore이다.
In general, busy waiting wastes CPU cycles that some other process might be able to use productively.
Spinlock – process spins while waiting for the lock.
- Have an advantage in that no context switch is required.
- When locks are expected to be held for short times, spinlocks are useful.
- Often employed on multiprocessor systems.
Using Semaphores
Deadlock and Starvation
Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes.
Let S and Q be two semaphores initialized to 1.
Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.
Monitors
High-level synchronization construct that allows the safe sharing of an abstract data type among concurrent processes (e.g., synchronized in Java).
Monitors with Condition Variables
To allow a process to wait within the monitor, a condition variable must be declared, as condition x, y;
Condition variable can only be used with the operations wait and signal (e.g., wait and notify in Java).
- The operation x.wait(); means that the process invoking this operation is suspended until another process invokes x.signal();
- The x.signal operation resumes exactly one suspended process. If no process is suspended, then the x.signal operation has no effect.
More on Condition Variables
Suppose that when the x.signal() operation is invoked by a process P, there is a suspended process Q associated with condition x (already in the monitor).
Possible solutions
- P either waits until Q leaves the monitor, or waits for another condition. (Hoare’s semantic) – a condition is true at a particular instant in time when the signal occurs (signal and wait method).
- Q either waits until P leaves the monitor, or waits for another condition. Q continues its execution in the monitor by rechecking the condition. (Brinch Hansen’s semantic or Mesa monitor semantic) – there will be fewer context switches than with the Hoare approach (signal and continue method) – common case (e.g., Pthread)
Classical Problems of Synchronization
- Bounded-Buffer Problem
- Readers and Writers Problem
- Dining-Philosophers Problem
Bounded-Buffer Problem
Readers-Writers Problem
Dining-Philosophers using Semaphore (1)
Dining-Philosophers using Semaphore (2)
This solution guarantees that no two neighbors are eating simultaneously.
However, it has the possibility of a deadlock.
Possible remedies to the deadlock problem.
- Allow at most 4 philosophers to be sitting simultaneously at the table.
- Allow a philosopher to pick up her chopsticks only if both chopsticks are available.
- Use an asymmetric solution; an odd philosopher picks up first her left chopsticks and then her right chopstick, whereas an even philosopher picks up her right chopstick and then her left chopstick.
A deadlock-free solution does not necessarily eliminates the possibility of starvation.
Dining Philosophers using Monitor
