Home » Operating Systems

Operating system solutions by semaphore

In this article, we will learn about the semaphore and the types of semaphore, its disadvantages and some hardware solution to critical section problem.
Submitted by Prerana Jain, on August 22, 2018

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

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.


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 ();
	    }
    }

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.






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL







Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.