Wednesday, 17 September 2014

Semaphore

A semaphore is a variable used to control access to a resource by multiple processes. There are three categories of semaphores.
    a. Binary Semaphore
    b. Counting Semaphore
    c. Mutex semaphore

a. Binary Semaphore
Binary semaphore is a synchronization object, that has only two states.
    1. Take
    2. Release

Take state
Taking a binary semaphore brings it in the “taken” state, trying to take a semaphore that is already taken enters the invoking thread into a waiting queue.

Release state
Once a thread done with the resource, it release the semaphore. If there is any other thread waiting for this semaphore, then a thread is removed from the queue and resumed with the semaphore.

b. Counting Semaphore
Counting semaphores are used to restrict the number of threads to access resource. With the semaphore count initialized to the number of free resources, threads then atomically increment the count when resources are in use and atomically decrement the count when thread done with the resource. When the semaphore count becomes zero, then the threads needs this resource will wait in wait queue.

Concurrent package provides Semaphore class, it is implementation of counting semaphore. Provides methods like acquire() : blocks if necessary permit is available, and then takes it, release() : adds a permit, potentially releasing a blocking acquirer.

Semaphore class provides below constructors to create a Semaphore instance.

public Semaphore(int permits)
Creates a Semaphore with the given number of permits and nonfair fairness setting.

public Semaphore(int permits, boolean fair)
Creates a Semaphore with the given number of permits and the given fairness setting. If fais is set to true, then this semaphore will guarantee first-in first-out granting of permits under contention.

Lets take an example, where there are 5 resources, and multiple threads are competing for this resources.

import java.util.concurrent.Semaphore;
import java.util.Random;

public class Task implements Runnable{
    static Object[] obj = new Object[5];
    static int flag[] = new int[5];
    static Semaphore sem = new Semaphore(5);
    static Random rand = new Random();
    
    static{
        for(int i=0; i<5; i++)
            obj[i] = new Object();
    }
        
    @Override
    public void run(){
        int temp=0;
        try {
            sem.acquire();
            
            /* Assign resource to the thread */
            for(int i=0; i<5; i++){
                if(flag[i] == 0){
                    flag[i] = 1;
                    temp = i;
                    break;
                }
            }
            System.out.println(Thread.currentThread().getName() + ": acquired resource " + temp);
            
        } catch (InterruptedException ex) {
        }
        long sleepTime = 1000 * rand.nextInt(10);
        try {
            Thread.sleep(1000);
        } catch (InterruptedException ex) {
        }
        sem.release();
        flag[temp] = 0;
    }    
}

public class SemaphoreEx {
    public static void main(String args[]){
        Task p1 = new Task();
        
        int i=0;
        Thread t1;
        
        while(i<100){
            t1 = new Thread(p1);
            t1.setName("Thread : "+ i);
            i++;
            t1.start();
        }
    }
}

Sample Output
Thread : 1: acquired resource 1
Thread : 0: acquired resource 0
Thread : 3: acquired resource 2
Thread : 5: acquired resource 3
Thread : 2: acquired resource 4
Thread : 4: acquired resource 1
Thread : 6: acquired resource 0
Thread : 7: acquired resource 3
Thread : 8: acquired resource 4
Thread : 9: acquired resource 0
Thread : 11: acquired resource 1
Thread : 13: acquired resource 2
Thread : 10: acquired resource 0
Thread : 12: acquired resource 0
Thread : 17: acquired resource 3




Prevoius                                                 Next                                                 Home

No comments:

Post a Comment