From the theory i read there are two types
1)Binary :- 0 or 1 as value or in other words only one thread allowed to inside critical section(or maybe i didn't interpret it correctly)
2)Counting :- Allows only k out of n threads to access k resources [k= no of resources , n=no of threads always n >k]
- Why Binary Semaphore ?
If Binary Semaphore's i.e
Semaphore sem = new Semaphore(1);
are used where only one thead is allowed inside don't they do the same thing as any normal LOCK? i.e only one thread allowed inside then how is
sem.aquire(); //since count=1 only one thread enters
try
{
//Important Stuff which can be accessed only by one thread
}
finally{sem.release();}
any diffrent from this?
lock.lock()
try
{
//Again only one thread allowed here same as binary semaphore
}
finally{lock.unlock();}
- Why Counting Semaphore ?
Now let's say there are
a) 3 Resources R1,R2,R3 and an resource can be used by only 1 thread at a time
b) 9 Threads T1,T2.....T9
c) Here is how each threads uses these resources
-> T1,T2,T3 => Wants R1
-> T4,T5,T6 => Wants R2
-> T5,T6,T7 => Wants R3
One would say counting semaphore would allow only 3 threads to aquire max 3 resources which would work fine provided each thread tries to aquire an unique resource but clearly not the case in this example. Lets say if T1,T2,T3 all entered the critical section T1 gets R1 and R1 is now removed from the list of available resources Now T2,T3 will crash because R1 is unavailable now.
You could put an lock on every method of the resource and not remove it from the resource queue to ensure if an resource is shared only one thread gets to use it but not only does that defeat the purpose of an semaphore but now we have overhead of both the semaphore and the lock.
How does an semaphore solve the problem of N Threads accessing 1 Resource i.e N->k where k is an resource in an queue of k1,k2,k3...kn resources?
My solution
Not perfect but it does not require locks and is fair
private final class Resource
{
private static final HashMap<Integer,Resource> instances=new HashMap(); //An map keeping track of available resources
private static final Object aquireLock=new Object(); //allow only one thread to aquire an resource and add itself to the waiting queue if it was not available at a time
private static final ArrayList<QueueObject> waiting=new ArrayList();//list of threads waiting to aquire an resource
private static void init() //Only 3 resources
{
instances.put(0,new Resource());
instances.put(1,new Resource());
instances.put(2,new Resource());
}
private static void use(int index,Consumer<Resource> action)
{
Resource res=null;
boolean doWait=false;
synchronized(aquireLock)
{
if(instances.containsKey(index)){res=instances.remove(index);}//remove resource to make it unavailable
else{doWait=true;}//not available? then wait
}
if(doWait)
{
QueueObject wait=new QueueObject(index); //store the name[index] of the resource it was asking so it can be woken up when that resource is available
synchronized(waiting){waiting.add(wait);} //now wait in queue
wait.doWait();
waiting.remove(wait);//wait over remove itself from queue
}
if(res==null){res=instances.remove(index);}//after wait again try to get resource[if it already has resource res wont be null]
try{action.accept(res);}//do stuff with resource
finally
{
synchronized(aquireLock){instances.put(index,res);}//Resource utilized now return it back to the queue
synchronized(waiting)
{
waiting.stream()
.filter(obj->obj.resID==index) //find the 1st thread in queue that was asking for this resource and wake it up so it can use it now
.findFirst()
.ifPresent(QueueObject::doNotify);
}
}
}
private static final class QueueObject
{
private boolean isNotified = false;
private final int resID;
private QueueObject(int resID){this.resID=resID;}
private synchronized void doWait()
{
while(!isNotified) //protection against missed signals and spurious wake up's
{
try{this.wait();}
catch(InterruptedException ex){}
}
this.isNotified = false;
}
private synchronized void doNotify()
{
this.isNotified = true;
this.notify();
}
}
}
So with Binary semaphore's doing the same stuff an an lock and counting semaphores having the issue of protecting 1 resource[in an queue of k resources] from N threads what additional benifit does an semaphore serve?
