5.3 Bounded Buffers


5.3 Bounded Buffers

Buffers are frequently used in concurrent systems to smooth out information transfer rates between the producers of data and the consumers of that data. Consider, for example, a keyboard device driver that is supplying characters typed at a keyboard to an editor program. The editor can consume characters at a much faster rate, on average, than a person can type at a keyboard. However, some characters can take longer than others to process, for example a character that causes the screen to scroll or a keyboard command that invokes a formatting command. When the editor is processing a character that takes a long time to process, it is necessary to buffer characters from the keyboard, otherwise they would be lost. This buffer is sometimes referred to as the type-ahead buffer. It is an example of the sort of buffer that we describe in the following.

In this section we model and program a bounded buffer, which consists of a fixed number of slots. Items are put into the buffer by a producer process and removed by a consumer process. The buffer is organized so that the first item put into it will be the first item out (FIFO).

Figure 5.10 depicts the display of our example system in which a producer process communicates characters to a consumer process via a five-slot buffer. The small circle above the buffer indicates the next free slot into which the producer process can place a character. The circle below the buffer indicates the next slot from which the consumer process can take a character. The reader may note the similarity between this example and the initial car park example in section 5.1. In fact, the synchronization requirements are the same. The producer is only allowed to put a character into the buffer when there is a free slot and the consumer process can only get a character when there is at least one in the buffer. These are exactly the requirements for the car park, if we substitute space for slot and car for character. What is different between the two examples is the FIFO discipline enforced by the buffer, in contrast to the car park where cars can occupy any free space and need not leave in arrival order.

image from book
Figure 5.10: Bounded buffer display.

5.3.1 Bounded Buffer Model

The producer – consumer system with a bounded buffer is an example of a program that handles data items without altering them. In addition, the behavior of the producer, the consumer and the buffer itself are not affected by the value of the items they handle. In other words, they do not test the value of these data items. The behavior is said to be data-independent. If data independence can be established then models can be simplified by omitting the detailed representation of parameters and data structures. This leads to much smaller and more tractable models. The get and put operations in Figure 5.11 are simple actions that do not have parameters. The LTS for the bounded buffer system, depicted in Figure 5.12, should be compared with the car park LTS of Figure 5.3 to see the similarity between the synchronization behavior of the two systems.

image from book
Figure 5.11: Bounded buffer model.

image from book
Figure 5.12: Bounded buffer LTS.

5.3.2 Bounded Buffer Program

The BUFFER of the model becomes a monitor in the Java implementation, with synchronized methods put and get (Program 5.6). We have separated the interface of the buffer from its implementation since we will provide an alternative implementation in the next section.

Program 5.6: Buffer interface and BufferImpl class.

image from book
 public interface Buffer<E> {   public void put(E o)     throws InterruptedException; //put object into buffer   public E get()     throws InterruptedException; //get object from buffer } public class BufferImpl<E> implements Buffer<E> {   protected E[] buf;   protected int in = 0;   protected int out= 0;   protected int count= 0;   protected int size;   public BufferImpl(int size) {     this.size = size;     buf = (E[])new Object[size];   }   public synchronized void put(E o)             throws InterruptedException {     while (count==size) wait();     buf[in] = o;     ++count;     in=(in+1) % size;     notifyAll();   }   public synchronized E get()            throws InterruptedException {     while (count==0) wait();     E o = buf[out];     buf[out]=null;     --count;     out=(out+1) % size;     notifyAll();     return (o);   } }
image from book

The buffer has been implemented as a general-purpose class that can buffer any type of Java object. The buffer data structure is a fixed size array buf, indexed by in which points to the next free slot and out which points to the next slot to be emptied. These indexes are incremented modulo the size of the buffer. The code for the producer and consumer programs is listed in Program 5.7.

Program 5.7: Producer and Consumer classes.

image from book
 class Producer implements Runnable {   Buffer<Character> buf;   String alphabet= "abcdefghijklmnopqrstuvwxyz";   Producer(Buffer<Character> b) {buf = b;}   public void run() {     try {       int ai = 0;       while(true) {         ThreadPanel.rotate(12);         buf.put(alphabet.charAt(ai));         ai=(ai+1) % alphabet.length();         ThreadPanel.rotate(348);       }     } catch (InterruptedException e){}   } } class Consumer implements Runnable {   Buffer<Character> buf;   Consumer(Buffer<Character> b) {buf = b;}   public void run() {     try {       while(true) {         ThreadPanel.rotate(180);         Character c = buf.get();         ThreadPanel.rotate(180);       }     } catch(InterruptedException e ){}   } }
image from book




Concurrency(c) State Models & Java Programs
Concurrency: State Models and Java Programs
ISBN: 0470093552
EAN: 2147483647
Year: 2004
Pages: 162

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net