Semaphore

Semaphore is a simply a variable. This variable is used to solve critical section problem and to achieve process synchronization in the multi processing environment.
The two most common kinds of semaphores are counting semaphores and binary semaphores. Counting semaphore can take non-negative integer values and Binary semaphore can take the value 0 & 1. only.

Semaphore have below API functions

wait(S s) {
    while(s <= 0) ;
    s--;
}

signal(S s) {
    s++;
}

init(S, A) {
    S = A;
}

Below are some problems to understand how it works.

1. Design multiple readers or 1 writer at a time


2. Dog and Master Problem: Master initialise N food in bucket.  Only one Dog at a time can get the food. When food get empty, Dog notify to Master. When get notified, master put +N food when food get empty and food should not overflow. Only one Master/Dog can access the resource at a time.

//Inicialize Semaphores
init(D, 1) //Semaphore to track Dog threads
init(M, 0) // Semaphore to track Master threads
init(WaitForFood, 0) //Semaphore to track if master has filled the food

Food = N //Initially food is full

getFood {
    wait(D) //Dog is waiting to get lock
    
    if(Food == 0) {//check if food is zero
         signal(M) //Master get notified and get lock to put food
         wait(WaitForFood) //Wait until master put food
    }

    Food--

    signal(D)
}

putFood {
    wait(M)
    Food += N
    signal(WaitForFood)
}


3. Creating H2O problem: There are 2 processes, Oxygen and Hydrogen. We have to make sure 2 molecule of Oxygen and 1 molecule of Hydrogen access mutual context at the same time to make H2O (water)

//Inicialize Semaphores
init(H, 1) //Semaphore to track Hydrogen molecules
init(O, 0) ////Semaphore to track Oxygen molecule
init(WaitForO2, 0) //Semaphore to make sure 1st Oxygen molecule wait for pair before access mutual code
init(WaitForH, 0) //Semaphore to wait for Hydrogen molecule
hCount = 0

Hydrogen {
   wait(H)

    hCound++

    if(hCount == 1) {
        //treat 1st Hydrogen molecule
        signal(O) //release Oxygen lock to get pair
        wait(WaitForO2)//wait for Oxygen pairing
    } else {
        signal(H) // release lock for Hydrogen molecule
        wait(WaitForH) //wait for Hydrogen molecule
        signal(WaitForO2) // signal 1st Hydrogen molecule to proceed
    }

    bound()
}

Oxygen {
    wait(O)

    signal(WaitForH) //signal that Oxygen molecule is ready for reaction

    bound();

    hCount = 0 //resetting hCount
    signal(H) //signal H for next reaction 

}