We know that if we want guard a critical section(shared resource),so that a single thread can access it,
we use synchronize block for the critical section.So that in a multi threaded environment we will not face any lost update problem.There are number of ways to make a shared resource thread safe.Like we all know one of them is by using synchronize keyword.In java ,there are some constructs and tools to help the developer to achieve this goal..Example of some such constructs are Semaphore,CountDownLatch,CyclicBarrier,Concurrent HashMap,HashTable,wait,notify,notifyAll.By using all the tools and constructs we can achieve our goal,ie to guard a shared resource(critical section) in a multi threaded environment.From now Onwards we will call such constructs as synchronizes.
Mutex(One Thread at a Time):
Assume the scenario that there is a small library having only chair to sit and read.But there are N number of students are waiting in queue.So the first student will come and take the key and enters the room.Till then all other students are waiting.When he will complete he will come out and give the key to the next student in the queue.Then only the next student will enter the room and will start the study.Here the study room is the critical resource.And all the students are threads.They are accessing the critical section one by one,in sequential manner.
Here mutex is the perfect candidate to apply. Because here mutually exclusion is desired.
A mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process) can acquire the mutex. It means there is ownership associated with mutex, and only the owner can release the lock (mutex).Here in our example student is the owner of the resource(library room) and after the completion of the study,he will release the room(the shared resource).
Here mutex is the perfect candidate to apply. Because here mutually exclusion is desired.
A mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process) can acquire the mutex. It means there is ownership associated with mutex, and only the owner can release the lock (mutex).Here in our example student is the owner of the resource(library room) and after the completion of the study,he will release the room(the shared resource).
A mutex(lock) has the concept
of ownership so it may be reentrant. That means that a thread that holds
a lock, is allowed to call a critical section again where same lock is
required. Because the thread already holds the lock and is allowed to
reenter it.
Semaphores(Number Of Specified threads at a time):
As we saw in mutex only one thread can access the critical section at a time.But In contrary to this more than one thread can access the critical section at the same time.Let's come to our previous example.Assume we have a large library room having capacity for 100 students.There are 100 chairs and and 100 students can read at the same time togeather.Assume here that the room is the critical section, and students are threads.Initially we define the semaphore count as hundred.When one student will go inside he will increase the permit(say total number of working threads) by one.Similarly when second student will go inside, he will increase the permit by one.And so on.Before giving permission to a student to enter the room , the total number of permit will be checked.If it is less than 100 ,then only the particular student will be allowed to go inside.Otherwise he will wait till some student to come and decrease the permit by one.
In Java , Semaphores have no notion of ownership, so they cannot be reentrant.One property of Semaphores in Java is that release doesn’t have to be called by the same thread as acquire.In a scenario assume we have a code that creating threads in a pool if and only if semaphore.acquire() succeed.Now after this those threads will start and call semaphore.release() when they complete.This is a useful property that we don’t have with mutexes(lock) in Java.A thread can succeeded in semaphore.acquire(), if there is at least one permit is available.
Now let's try to understand semaphore with the help of an example.The below example is a modified version of the example of semaphore as given in java doc.
class Pool {
private static final int MAX_AVAILABLE = 10;
private final Semaphore available = new Semaphore(MAX_AVAILABLE, true);
public Object getItem() throws InterruptedException {
System.out.println("Going to acquire lock for thread id "+Thread.currentThread().getId()+" available permit "+available.availablePermits() +" ");
available.acquire();
// System.out.println("lock acquired for thread id "+Thread.currentThread().getId()+" available permit "+available.availablePermits() +" ");
return getNextAvailableItem();
}
public void putItem(Object x) {
if (markAsUnused(x))
available.release();
System.out.println("lock released for thread id "+Thread.currentThread().getId());
}
// Not a particularly efficient data structure; just for demo
protected String[] items ={"a","b","c","d","e","f","g","h","i","j"};
protected boolean[] used = new boolean[MAX_AVAILABLE];
protected synchronized Object getNextAvailableItem() {
for (int i = 0; i < MAX_AVAILABLE; ++i) {
if (!used[i]) {
used[i] = true;
return items[i];
}
}
return null; // not reached
}
protected synchronized boolean markAsUnused(Object item) {
for (int i = 0; i < MAX_AVAILABLE; ++i) {
if (item == items[i]) {
if (used[i]) {
used[i] = false;
return true;
} else
return false;
}
}
return false;
}
}
}
public class PoolTest {
public static void main(String[] args) throws InterruptedException {
Pool t1=new Pool();
for(int i=0;i<200 i="" p="">
new Thread(
new Runnable(){
public void run(){
try {
Thread.currentThread().setName(new Object().toString());
System.out.println(t1.getItem().toString()+" for thread id "+Thread.currentThread().getId());
}
catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
t1.putItem("a");
}
}).start();
}
}
}
Explanation:
If no permit is available then the current thread becomes disabled for thread scheduling purposes and lies idle until one of two things happens:
Some other thread invokes the release() method on the same semaphore and the current thread is next to be assigned a permit; or
Some other thread interrupts the current thread. And then we call the method getNextAvailableItem().It returns an item from the items array defined in pool class.
The thread call the putItem(Object x) method.This method takes the item and mark it as unused.Then call the realease method on the semaphore.
Releases a permit, increasing the number of available permits by one. If any threads are trying to acquire a permit, then one is selected and given the permit that was just released. That thread is (re)enabled for thread scheduling purposes.
There is no requirement that a thread that releases a permit must have acquired that permit by calling acquire() method.
Wrong Uses Of Semaphore:
But note one thing here that, we are always returning the string "a" in putItem(Object x) method.But we taking every item from the array.so there will be a case where all the items a,b,c,d,e,f,g,h,i,j will be consumed from the array but only a will be retuned.so,in that case number of permits will be 1 only.Here this is a case where permits are taken but never returned.That is only acquire occurs but no release.This is a misuse of semaphore.
Also one more thing to note here that we should alway call release() method in finally block.If some exception occurs before calling the release method,then also release can be called safely.And number of permit can be increased.
Fairness In Semaphore:
Java's built-in concurrency tools (synchronized, wait(), notify())
do not mention which thread should be get turn for getting the access to the critical section when a lock is released. It
is up to the implementation of the JVM to decide..Fairness gives us more control: when the lock is released, the thread with the longest wait time is given the lock (FIFO processing). Without fairness we might have a situation where a thread is always waiting for the lock because other threads are continuously requesting for the same.
Semaphores can be initialized with constructor Semaphore(int permits) or Semaphore(int permits,boolean fair).Semaphore(int permits,boolean fair) creates a semaphore with fairness setting.When fair is set to true,the semaphore gives permit to access the critical section in the order the threads have ask for it (FIFO).And when fair is set as false,then semaphore can grant access to the the thread asking for it rather than the thread which is waiting before.To avoid starving fair should be set to true.
How TO Break Fairness Policy:
There is a method with signature public boolen tryAcquire().This method acquires a permit from this semaphore,only if one is available at the time of invocation. This method Acquires a permit, if one is available and returns immediately, with the value true, reducing the number of available permits by one.If no permit is available, then the method will return immediately with value false. Even when this semaphore has been set to use a fair ordering policy, a call to tryAcquire() will immediately acquire a permit if one is available, whether or not other threads are currently waiting. This (rude) "barging" behavior can be useful in certain circumstances, even though it breaks fairness. If we want to respect the fairness setting that we set in constructor, then we should usetryAcquire(0, TimeUnit.SECONDS)Acquire and Release multiple permits at same time:
There is a method with signature public boolean tryAcquire(int permits).When the method is called, acquires the given number of permits, if they are available, and
returns immediately, with the value
true,
reducing the number of available permits by the given amount.
If insufficient permits are available then this method will return
immediately with the value
Similarly we can release more than one permit in one go with the help of below method
public void release(int permits)
false and the number of available
permits is unchanged.Similarly we can release more than one permit in one go with the help of below method
public void release(int permits)
Releases the given number of permits, increasing the number of
available permits by that amount.
If any threads are trying to acquire permits, then one
is selected and given the permits that were just released.
If the number of available permits satisfies that thread's request
then that thread is (re)enabled for thread scheduling purposes;
otherwise the thread will wait until sufficient permits are available.
If there are still permits available
after this thread's request has been satisfied, then those permits
are assigned in turn to other threads trying to acquire permits.There is no requirement that a thread that releases a permit must
have acquired that permi
t.
Create a custom Semaphore:
Finally, let's take a look how to create a custom semaphore with minimal setting.
public class MySemaphore {
private int permit;
public MySemaphore () {
this(0);
}
public MySemaphore (int i) {
if (i < 0)
throw new IllegalArgumentException(i + " < 0");
counter = i;
}
public synchronized void release() {
this.notify();
permit++;
}
public synchronized void acquire() throws InterruptedException {
while (permit== 0) {
this.wait();
}
permit--;
}
}
No comments:
Post a Comment