semaphores

tags: synchronization multithreading multiprocessing mutual-exclusion

Semaphores are the mechanism to synchronize operations in multithreading or concurrent programming. It can be used solve race conditions, produce consumer problem, etc.

Semaphores is a variable that maintains non-negative value and allows only two atomic operations, down and up.

In down operation, the value of semaphore decreases. If it’s value is 0, then the process is put to sleep and value remains 0.

In up operation, the value of semaphore is increased. If any process is sleeping associated with the semaphore is get awakend.

Solving producer consumer problem

The main problem with producer and consumer is the accessing the shared buffer. So, we have put the process to sleeping state if some other process is currently using it. That is, we have to manage the control regions.

We can solve this using enter_region and exit_region mechanism but it starts the infinity loop which is CPU intensive.

Let’s use semaphore to solve this issue.

#define N 100
typedef int semaphore
 
semaphore mutex = 0;
semaphore empty = N;
semaphore full = 0;
 
void producer() {
    int item;
 
    while (TRUE) {
        item = produce_item();
        down(&empty);
        down(&mutex);    // entering critical region
        insert_item(item);
        up(&mutex);    // leaving critical region
        up(&full);
    }
}
 
 
void consumer() {
    while (TRUE) {
        down(&full);
        down(&mutex);
        item = remote_item();
        up(&mutex);
        up(&empty);
        consume_item(item);
    }
}

Let’s understand this pesudo program. There are three semaphores, mutex, empty and full.

mutex is used for critical region. Before going into critical region, we are doing down(&mutex). If mutex is 0 then the process is put to sleeping state as shared buffer is already is in use. mutex can only contain one of two values, 0 or 1. This is called Binary Semaphore. mutex is used to ensure mutual exclusion.

Semaphores full and empty are used to make sure the producer stops running if buffer is full and consumer stops running if the buffer is empty.

Mutexes are specially used for mutual exclusion. These are used for entering and exiting the critical region.