Semaphore Basics

Semaphore is a mechanism to achieve mutual exclusion in multi threaded application. The way to make threads synchronized. Semaphore is introduces by Edsger Dijkstra. This sample implementation uses an integer as the semaphore variable which can have any of the two values at any point of time – 1 (FREE) or 0 (BUSY).

Each time when a thread needs to enter the critical region/critical section, it will check whether the semaphore status is free. Otherwise it needs to wait until semaphore status becomes free. There may be multiple threads waiting to enter the critical region/critical section. As the semaphore status becomes free any of the waiting thread will get the lock on the semaphore and can execute the critical region.

Different thread can have different priority and the lock can be given to the threads based on their priority. In this code block I haven’t put priority based scheduling.

For more details: http://en.wikipedia.org/wiki/Semaphore_(programming)

Critical section:
Critical section is a block of code which tries to access or modify any of the shared resources with the system. The shared resources can be files, common variables, hardware devices like printer, disk drives etc.

Mutual exclusion:
Mutual exclusion is the inability of different threads to access the critical section simultaneously.

Semaphore Implementation:

package subin.rnd.thread;
public class Semaphore extends Thread 
{ 
    static int _semaphore; 
    static int _busy = 0; 
    static int _free = 1; 
    
    static 
    { 
        _semaphore = _free; 
    } 
    
    public static void main(String[] args) 
    { 
        for (int i = 0; i < 5; i++) 
            new Semaphore(i + 1).start(); 
    } 
    
    private int id; 
    
    public Semaphore(int id) 
    { 
        this.id = id; 
    } 
    
    public void run() 
    { 
        _wait(this.id);  

        // Critical section 
        
        try 
        { 
            System.out.println(this.id + ": doing something"); 
            Thread.sleep(3000); 
            System.out.println(this.id + ": unlock"); 
        } 
        catch (InterruptedException e) 
        { 
            e.printStackTrace(); 
        }  

        // End of critical section  
       
        _unlock(); 
    } 
    
    static void _wait(int id) 
    { 
        System.out.println(id + ": waiting"); 
        while(_semaphore != _free); 
        _semaphore = _busy; 
    } 
    
    static void _unlock() 
    { 
        _semaphore = _free; 
    } 
}

Sample output:

1: waiting 
1: doing something 
3: waiting 
2: waiting 
5: waiting 
4: waiting 
1: unlock 
4: doing something 
4: unlock 
2: doing something 
2: unlock 
3: doing something 
3: unlock 
5: doing something 
5: unlock

					
Advertisements