1. Many threads can read values from the resource simultaneously
2. Only one thread may write changes to the resource at any one time, and no other threads should be allowed to write changes until the first thread finishes (allowing them to make all their changes atomically).
3. If a thread is in the process of writing changes, no thread should be allowed to read the resource until the write operation has finihed.
Solutions to the Reader-Writer problem are critical within an Operating System, where access to shared resources (such as the file system) must be optimised, and where many competing threads are fighting for access. Solutions are also critical for database applications, caches, and many other user level applications.
Although the problem is relatively simple, an optimal solution can be complex once certain considerations are taken into account:
1. If there are both waiting readers and waiting writers when a write lock is released, who should be given the lock first? If either readers and writers are always preferred ahead of the other, what happens in cases of high utilization? Either readers or writers may be starved from the resource completely.
2. If there are both waiting readers and waiting writers when a read lock is released, who should be given the lock first? The same considerations apply as in point one.
3. If a thread holds a write lock, should it be allowed to convert this into a read lock? This has potential implications for waiting writers.
Creating a "fair", but also optimal solution to the Reader-Writer ultimately depends on the specific situation. For instance, the soution may be different for a case where reads are very common and writes are very rare compared to a case where writes occur more often than reads.
The 1.5 release of Java includes an Interface for providing a solution to the Reader-Writer problem called ReadWriteLock. There is also an implementation called ReentrantReadWriteLock. Although the low level concurrency operations in Java (synchronized block, wait/notify functionality) ease the creation of an implementation, the ReentrantReadWriteLock class provides a well tested implementation that will suit most needs.
The following is an example of using a ReadWriteLock to control access to a HashMap. Many threads can simultaniously read values from the Map, but an exclusive Write Lock must be obtained before writing a new value for a key.
+++++++++++++++BEGIN CODE+++++++++++++++
import java.lang.Thread;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class LockedHashMap {
//This is the shared object we are controlling access to
private Map
/*
* This is the lock we are using to control shared access. Passing a value
* of true tells the ReadWriteLock to fairly allocate the locks.
*/
private ReentrantReadWriteLock theLock = new ReentrantReadWriteLock(true);
public static void main(String[] args) {
LockedHashMap lhm = new LockedHashMap();
lhm.testLocking();
}
public LockedHashMap() {
// Initialise the Map with some initial values
theMap.put("Key1", "Value1");
theMap.put("Key2", "Value2");
theMap.put("Key3", "Value3");
}
private void testLocking() {
/*
* These are the threads that will simultaniously attempt to access the shared object
*/
HashMapReader hmr1 = new HashMapReader("One", "Key1");
HashMapReader hmr2 = new HashMapReader("Two", "Key2");
HashMapReader hmr3 = new HashMapReader("Three", "Key3");
HashMapReader hmr4 = new HashMapReader("Four", "Key1");
HashMapReader hmr5 = new HashMapReader("Five", "Key2");
HashMapReader hmr6 = new HashMapReader("Six", "Key3");
HashMapReader hmr7 = new HashMapReader("Seven", "Key1");
HashMapWriter hmw1 = new HashMapWriter("One", "Key1", "Value_new1");
HashMapWriter hmw2 = new HashMapWriter("Two", "Key2", "Value_new2");
HashMapWriter hmw3 = new HashMapWriter("Three", "Key3", "Value_new3");
new Thread(hmr1).start();
new Thread(hmw1).start();
new Thread(hmr2).start();
new Thread(hmr3).start();
new Thread(hmw2).start();
new Thread(hmr4).start();
new Thread(hmw3).start();
new Thread(hmr5).start();
new Thread(hmr6).start();
new Thread(hmr7).start();
}
/**
* A Reader takes the key of the object it is attempting to access,
* gets the value, and prints the result. It Sleeps for 2 seconds while
* holding the lock to simulate a more long running operation.
*/
private class HashMapReader implements Runnable {
private String name;
private String key;
public HashMapReader(String theName, String theKey) {
name = theName;
key = theKey;
}
public void run() {
try {
theLock.readLock().lock();
String value = theMap.get(key);
System.out.println("The Reader " + name + " has read the key " + key + " with a value " + value);
try {
Thread.sleep(2000);
} catch (InterruptedException e) {}
} finally {
theLock.readLock().unlock();
}
}
}
/**
* A Writer takes ta key and a value, and updates the value of the key,
* and then prints the result. It Sleeps for 4 seconds while
* holding the lock to simulate a more long running operation.
*/
private class HashMapWriter implements Runnable {
private String name;
private String key;
private String value;
public HashMapWriter(String theName, String theKey, String theValue) {
name = theName;
key = theKey;
value = theValue;
}
public void run() {
try {
theLock.writeLock().lock();
theMap.put(key, value);
System.out.println("The Writer " + name + " has written the key " + key + " with the value "+ value);
try {
Thread.sleep(4000);
} catch (InterruptedException e) {
}
} finally {
theLock.writeLock().unlock();
}
}
}
}
+++++++++++++++END CODE+++++++++++++++
A couple of points to note regarding this example are as follows:
The constructor for ReentrantReadWriteLock takes a boolean indicating whether it should be "fair" with the locks. To be fair in this case basically means to give out locks primarily in the order that they were requested. Although this policy should avoid starvation, it is not necessarily the most efficient approach: in the above example, using a fair policy takes approximately twice as long as an unfair one.
In the worst case, a fair policy may mean every read needs to wait on a write (assuming reads and writes were requested in an alternating manner). An unfair (but efficient) policy will attempt to group as many reads together as possible, since they will not block each other. Although this may prove optimal, as mentioned above, there is a risk starvation could occur.
Another point to note is that it is critical that locks are released in a finally block. If a thread acquired a write lock, but due to an exception, never released it, a deadlock situation would be created.
No comments:
Post a Comment