Home » Operating System

Semaphores Solutions in Operating System

In this tutorial, we will learn about the semaphore, types of semaphore, its disadvantages, and some hardware solution to critical section problem. By Prerana Jain Last updated : May 07, 2023

The hardware-based solution is complicated for application programmers to use overcome this, we can use a synchronization tool called semaphore.

Semaphore

The solution which we providing for critical section problem it is not easy that to generalize it is more complex problems. So To overcome this difficulty we use a special type of tool called semaphore. The integer variable S that apart from initialization and it is accessed only through two standard atomic operation wait and the signal then this variable is called semaphore. These operations were originally termed P for wait from dutch problem to test.

The definition is given as follows:

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

signal(s)
{
    s++;
}

All modification to wait() and signal() must be done individually/ atomically.

Types of semaphore

There are mainly two types of semaphore:

• Counting semaphore unrestricted domain
• Binary semaphore/mutex lock range 0,1

Binary Semaphore

The semaphore construct described in the previous section is commonly known as a counting semaphore since its integer value can range over an unrestricted domain. A binary semaphore is a semaphore which has an integer value and their range only between 0and 1. A binary semaphore can be simpler to implement than a counting semaphore, depending on the underlying hardware architecture. In this semaphore can have only two values 1, 0. The wait and signal definition is:

wait(semaphore s)
{   
    if(s.value ==1)
        s.value = 0;
    else
        block process and place its PCB in the suspend list()
}

signal(semaphore s)
{  
    if(suspend () list is empty
        s.value = 1;
    else
    {  
        select * process from suspend list and wakeup ();
    }
}

Usage

Semaphore are used to solve synchronization problems like:

Do
{   
    wait(mutex);
    Critical section	
    Signal(mutex);
}

Spin Lock

Semaphore - process spin while waiting for the lock.

Disadvantages

Busy waiting - while a process is in a critical section, any other process that tries to enter into the critical section must loop continuously in the entry code. Busy waiting waste CPU cycles.

Modification to definition of wait() and signal()

wait is defined as:

    wait( semaphore * S)
    {
	    S -> value--;
	    if( S -> value<0)
	    {   
		    add this process to S -> list;
		    block();
	    }
    }

signal is defined as:

    signal (semaphore * S)
    {  
	    S -> value ++;
	
	    if( S -> value <=0)
	    {    
		    Remove process p from S -> list;
		    wakup(p);
	    }
    }

Note: block() and wait() operation spinlocks. Here semaphore value can go to indicating the number of process waiting for that semaphore.

Hardware Solution to Critical Section

The software-based solution is 2 processes also they are not guaranteed to work on modern computers architecture. The critical section problem could be solved simply in a uniprocessor environment if we prevent interrupts from occurring from uniprocessor environment.

In multiprocessor environment disabling any interrupts that occur on a multiprocessor, it is a time-consuming process so a message is passed to all processor. The modern computers system provide a special type of hardware that allows to test and set or swap the contents of words.

1. Test and Set

It is an automatic instruction that is if two test and set instruction are excelled simultaneously they will be executed sequentially in some arbitrary order.

Definition of test and set()

boolean Test and set (Boolean * targe)
{ 
    boolean rv = * target;
    return rv;
}

Mutual exclusion using test and set()

do
{   
    while( test and set (& locks);
    critical section
    look = false;
}

Here, lock is initialized to false. It satisfies mutual exclusion, progress but no bounded waiting.

2. Swap

It can also be used to implement mutual exclusion as following:

do{
    key = true;
    while( key = = true)
    swap ( & lock, &keys);
    critical section
    lock = false;	
}while(true);

It also satisfies mutual exclusion and progress.