9.4 ReadersWriters Problem
|
| < Day Day Up > |
|
9.4 Readers/Writers Problem
The readers/writers problem is a classical case of how the synchronization in a program can greatly affect the speed of the program. In the readers/writers problem, a number of activities must be read or written to a buffer. Obviously, one way to make the buffer safe would be to allow only one reader or writer in the buffer at a time; however, because the readers do not change the buffer, we have no reason to limit the number of readers accessing the buffer to one at a time. The possibility of a race condition does not exist, and allowing multiple readers to access the buffer concurrently allows for more concurrency in the program, thus allowing the readers to finish sooner and the program to run faster. On the other hand, the writers will modify the buffer, which could result in a race condition if any other reader or writer accessed the buffer concurrently with a writer; thus, only one thread can be allowed in the monitor if it is a writer.
A number of policies can be used to optimize a readers/writers program. One of the simplest is to allow readers to access the buffer until a writer requests the buffer to write to it. When the writer requests the buffer, readers currently using the buffer are allowed to finish using the buffer, but no new readers are allowed to start. When all the current readers have finished, the writer uses the buffer and then releases it to allow readers and/or writers to access it again. Note that this is not an optimal strategy, as it only tracks one writer. Because the largest delay in the program is the time required to clear the buffer of readers before allowing a writer exclusive access, a more optimal strategy would be to allow not just one but all waiting writers to acquire the buffer before leaving the readers access to it again. However, the policy here is to inform only one writer when the buffer is free, and the more optimal solution is left as an exercise.
The state diagram necessary to implement the single writer policy is given in Exhibit 4. Note that the doRead method is not synchronized and so is not included in the state diagram. By not synchronizing the method, multiple readers can be accessing the object concurrently, but it also makes the doRead method unsafe. To safely access the doRead method, it should only be called after a successful call to beginRead, and endRead should always be called when it is completed; however, that policy is not enforced in any way in the buffer object. Also, a write should consist of a requestWrite followed by a doWrite method, but once again this policy is not enforced. If the state diagram is implemented so that it can be accessed directly from an implementing program, it becomes incumbent upon the programmer to follow the correct procedure of calling the methods in the proper order; however, it is not advised to rely on a programmer to implement a procedure consistently and correctly, particularly when the program is accessing a critical region. Exhibit 5 (Program9.3a) implements the buffer for this solution, and Exhibit 6 (Program9.3b) uses the buffer. The remainder of this section looks at how to handle this situation to ensure that the calls are correct and discusses why the actual implementation of the solution is not as simple as the steps laid out in Chapter 3.
Exhibit 4: Readers/Writers State Diagram
 |
|
Exhibit 5: Program9.3a: Readers/Writers Buffer Implementation
|
public class Buffer { private HiddenBuffer hb = new HiddenBuffer(); // The actual buffer used. Access to this buffer is only // through the read and write methods. /** * Read an object from the buffer. Note that to make this * work the intention to read the buffer must first be * declared by calling beginRead. The unsynchronized method * doRead can then be called. Finally, the thread must say * that it is finished by calling endRead. * * Because this is all encapsulated in this method, the user * of this buffer needs only to call this method as "Object * * = buffer.read()," and the details will be handled. */ public Object read() { System.out.println("Reader waiting for buffer"); hb.beginRead(); System.out.println("Reader got buffer"); Object returnObject = hb.doRead(); hb.endRead(); System.out.println("Reader finished"); return returnObject; } /** * Write an object to the buffer. Note that first the * intention to write to the buffer must be declared by * calling requestWrite. When the buffer is safe, the doWrite * method is called, allowing the write to finish. */ public void write(Object o) { System.out.println("Writer requesting buffer"); hb.requestWrite(); hb.doWrite(new Object()); System.out.println("Writer done with buffer"); } /** * This is the actual buffer object. */ private class HiddenBuffer { // Buffer state variables. private static final int READABLE = 0; private static final int WAITING_TO_WRITE = 1; private static final int WRITING = 2; private int state = READABLE; private int numberOfReaders = 0; private Object notifyObject = new Object(); // Note: Only a single notification object is used so only // a single writer can be notified. Also, note that we // cannot use the object to be written as the notification // object, as the user could have that one locked already. /** * This method declares the intent of a thread to do a read. * It protects the doRead method and returns when it is safe * to call the doRead method. */ public synchronized void beginRead() { while(! (State = = READABLE) { try { wait(); } catch(InterruptedException e) { } } numberOfReaders++; // No post-condition, as state will not change. } /** * This method reads the data from the buffer and returns * the object. Note this is only simulated here by a * .5-second delay. Also note that this method is * unsynchronized, allowing multiple simultaneous readers. */ public Object doRead() { try { Thread.sleep(500);// .5 second delay } catch(InterruptedException e) { } return new Object(); } /** * This method declares the thread to have completed * reading the buffer. If any thread is waiting to write, * when the numberOfReaders becomes 0, allow the writer * thread to continue. */ public synchronized void endRead() { while (! ((state = = READABLE) || (state = = WAITNG_TO_WRITE))) { try { wait(); } catch(InterruptedException e) { } } numberOfReaders -- ; if ((numberOfReaders = = 0) && (state = = WAITING_TO_WRITE)) { state = WRITING; synchronized(notifyObject) { notifyObject.notify(); } } } /** * This method allows a writer thread to declare its intent * to read from the buffer. This method will return when it * is safe to call the doWrite method. */ public void requestWrite() { Object temp = new Object(); synchronized (temp) { synchronized(this) { notifyObject = temp; // Can only requestWrite from state READABLE. This // means only one writer can be waiting at a time; // others must wait here. // Note that the wait drops the lock on the // HiddenBuffer object but holds it on the temp // object. This is not a problem, as the temp object // does not have scope outside of this method yet. while (! (state = = READABLE)) { try { wait(); } catch(InterruptedException e) { } } // Post Conditions if (numberOfReaders = = 0) { state = WRITING; // notifyAll(); // Not needed. notifyObject = null; } else { state = WAITING_TO_WRITE; // notifyAll();// Not needed. } } // Note that we have to do the waiting to write here // while we still hold the notifyObject lock. if (notifyObject ! = null){ try { notifyObject.wait(); } catch(InterruptedException e) { } } } } /** * This method writes the data from the buffer and returns * the object. Note that this is only simulated here by a * .5-second delay. */ public synchronized void doWrite(Object o) { while(! (state = = WRITING)) { try { wait(); } catch(InterruptedException e) { } } // The write would be done here. try { Thread.sleep(500); } catch(InterruptedException e) { } // Post-condition state = READABLE; notifyAll(); } } } |
Exhibit 6: Program9.3b: Using the Readers/Writers Buffer
|
import java.util.*; public class ReadersWriters { public static void main(String args[]) { Buffer buffer = new Buffer(); for (int i = 0; i < 50; i++) (new Thread(new Reader(buffer, i))).start(); for (int i = 0; i < 3; i++) (new Thread(new Writer(buffer, i+50))).start(); } } /** * This class implements a reader thread. */ class Reader implements Runnable { private Buffer buffer; private int readerNumber; private Random random; public Reader(Buffer buffer, int readerNumber) { this.buffer = buffer; this.readerNumber = readerNumber; random = new Random(readerNumber); } public void run() { try { while(true) { Thread.sleep(random.nextInt(5000)); buffer.read(); } } catch(InterruptedException e) { } } } /** * This class implements a writer thread. */ class Writer implements Runnable { private Buffer buffer; private int writerNumber; private Random random; public Writer(Buffer buffer, int writerNumber) { this.buffer = buffer; this.writerNumber = writerNumber; random = new Random(writerNumber); } public void run() { try { while(true) { Thread.sleep(random.nextInt(50000)); buffer.write(new Object()); } } catch(InterruptedException e) { } } } |
9.4.1 Confinement
In order to implement the readers/writers buffer correctly, the read must always execute the methods beginRead, doRead, and finally endRead, in that order. The write must also execute the requestWrite and doWrite methods in order. If a programmer is allowed direct access to the readers/writers buffer, the programmer has to make sure to always execute the statements in this order. The most dangerous part of allowing a programmer direct access to this buffer is that the doRead method is not synchronized, but instead is protected by the calls to beginRead and endRead. If a programmer accesses this unsynchronized method directly, the possibility of a race condition is introduced into the program; therefore, this method should not allow programmers direct access.
One way to protect the unsynchronized method and ensure that it is not called incorrectly is to encapsulate or hide the buffer inside of another object that will implement the correct behavior. When this object is not able to leak information outside of the program, it is called confinement. In Exhibit 3 (Program9.2), the Buffer class is the external representation of the buffer, but the actual buffer represented by the state diagram in Exhibit 4 is the inner class called HiddenBuffer. Inner classes are covered in more detail in Chapter 12, but for now just realize that this class cannot be accessed except through objects of the Buffer class; hence, the HiddenBuffer is confined to the Buffer and is safe as long as the Buffer is implemented correctly.
Using this scheme, the Buffer class can implement a read method that correctly calls beginRead, doRead, and endRead on the Hidden-Buffer, thus ensuring that the semantics of the read are correct. The method also ensures that the doRead method is not called unsafely, as no objects except the Buffer class can access this method.
This confinement has one other nice property. The calling program does not need to know more than what it wants to read or write to the Buffer. All the semantics of properly using the Buffer are contained in the read and write methods, so a calling program only needs to call a simple read or write to make the program work correctly. This makes using the buffer easier for the programmer, and the code for accessing the buffer is cleaner and clearer. It also means that if a more effective locking scheme is developed for accessing the buffer, the object using the buffer need only refer to this new object, as all the details are hidden.
9.4.2 Notification Objects
The other important property in the HiddenBuffer class is the use of notification objects to optimize the running of the buffer. This optimization involves carefully deciding what threads must be notified when states change and limiting the notification to only those threads that are affected. The reason this is an important and potentially large savings is that when a notify (or worse, notifyAll) call is made, a potentially large number of threads are moved from a wait list to the ready set. While on the wait list, these threads are idle and consume no processor time. When the threads are notified and moved to the ready set, these threads will have to be run, which causes a context switch for each thread. These threads must also attempt to regain the lock on the monitor object, as that is the first activity of a thread when it starts to run after a call to wait. Both of these operations have relatively high overhead, so calls to notify or notifyAll are fairly expensive. Further, if the only possible outcome of the call is for the thread to be put back in the wait state immediately, it is an expensive call that really does not need to be made. So, anytime a notify or notifyAll call can be removed safely from a program, it can represent a fairly substantial savings of resources. This is especially true in the case of the readers/writers problem, where a large number of readers might be waiting until a writer has written, so if they are notified their only action is simply to go back to a wait state.
The optimization done in the readers/writers problem is achieved by recognizing that, while having every thread wait on the monitor is a correct solution, it does incur significant useless overhead; therefore, only notify and notifyAll calls on the object will be done when they are specifically needed. In cases where only a single thread can run as the result of a state change, that thread will be notified specifically using a notification object.
This type of optimization can be used very effectively in the readers/ writers problem. To see how this optimization can be done, consider first the transition (or method) endRead. If the endRead method is called when the HiddenBuffer monitor is in the state READABLE, there is no transition to another state so a notifyAll call does not need to be done. However, if the HiddenBuffer monitor is in the WAITING_TO_WRITE state, the only waiting thread that would ever be able to execute is the one writer thread that moved into the WAITING_TO_WRITE state, so it is notified specifically using a notification object when the number-OfReaders is zero. Because the notifyAll call in this method would have occurred once for each thread that needed to complete a read, and each notification could have potentially moved each thread waiting to read to the ready list, the savings in potential context switching and contention for the lock on the object could be quite large.
Next consider the requestWrite method. First, if no readers are currently using the buffer (numberOfReaders = 0), the Writer thread does not need to wait when running this method. Further, because this writer thread requires exclusive use of the buffer when running, any thread that might be notified would have to be put back to sleep immediately, so a notifyAll does not need to be done when moving to the WRITING state. Second, the only reader threads that are able to run once a requestToWrite call has been made are currently executing reader threads; therefore, no threads that are waiting can run. When moving to a WAITING_TO_WRITE state, then, no threads should have to be notified and a notifyAll is simply wasted.
This new version of the monitor is more complex than the one derived directly from the state diagram; however, the improvement in performance is probably worth the extra complexity if that complexity is implemented correctly. Doing so is not easy, though, and when improving the performance of a monitor it is best to start with one derived directly from the rules in Chapter 3 and then modify it carefully to improve performance. Keep in mind two old saws about programming:
Make it right then make it fast.
and
It is easier to make a correct program fast than to make a fast program correct.
Often a monitor with a notification object represents a good solution to a problem, but some more complex problems are more difficult, if not impossible, to implement. For example, it is difficult to write a program where a thread listens to two monitors for the first to become free. In these cases, designs using the Java Event Model are much better, as is shown in the improved gas station simulation in Section 9.5.
|
| < Day Day Up > |
|
EAN: 2147483647
Pages: 162