Project objective
Implement the solution to the bounded buffer problem from the section titled Semaphores, but without any P or V operations. Observe and eliminate a race condition.
Description
- The buffer is a large array of n integers, initialized to all zeros.
- The producer and the consumer are separate concurrent threads in a process.
- The producer executes short bursts of random duration. During each burst of length k1, the producer adds a 1 to the next k1 slots of the buffer, modulo n.
- The consumer also executes short bursts of random duration. During each burst of length k2, the consumer reads the next k2 slots and resets each to 0.
- If any slot contains a number greater than 1, then a race condition has been detected: The consumer was unable to keep up and thus the producer has added a 1 to a slot that has not yet been reset.
- If any slot that consumer reads contains a number 0, then a race condition has been detected: The producer was unable to keep up and thus the consumer try to read data in a slot that has not yet been added.
- Both producer and consumer sleep periodically for random time intervals to emulate unpredictable execution speeds.
| producer thread: while (1) get random number k1 for i from 0 to k1-1 buffer[(next_in + i) mod n] = 1 next_in = (next_in + k1) mod n get random number t1 sleep for t1 seconds | consumer thread: while(1) get random number t2 sleep for t2 seconds get random number k2 for i from 0 to k2-1 data = buffer[(next_out + i) mod n] if (data > 1) exit and report race condition that consumer too slow else if (data == 0) exit and report race condition that producer too slow else buffer[(next_out + i) mod n] = 0 next_out = next_out + k2 mod n |
Assignment
- Experiment with different values of n, k, and t until a race condition is observed.
- Modify the solution by including the necessary P and V operations in the code. If general P and V operations are not provided by the thread library then first implement P and V using binary semaphores (mutex lock or spin locks.)
****There is an error,
In pseudo code of consumer in version 2, in for loop, shall be "release a permit for emptyBuffer", not occupiedBuffer********
5 Understand the question Two versions. Version One: Experiment with different values of n, k, and t until a race condition is observed. No semaphore functionality is used Version Two: Modify the solution by including the necessary P and V operations in the code. . If general P and operations are not provided by the thread library then first implement P and V using binary semaphores (mutex lock or spin locks.) In this version, producer will not write data if there is no empty buffer slot. Consumer will not read data if there is no data in buffer 6 Java Runnable Interface The Runnable interface should be implemented by any class whose instances are intended to be executed by a thread. The class must define a method of no arguments called run. . This method defines how the function shall be executed 7 Java Thread class A thread is a thread of execution in a program. The Java Virtual Machine allows an application to have multiple threads of execution running concurrently. It implements Runnable interface. i.e. the run method is implemented. However, this run method really does nothing. . If this thread was constructed using a separate Runnable run object, then that Runnable object's run method is called; otherwise, this method does nothing and returns. 8 Two ways to create a thread There are two ways to create a new thread of execution. . One is to declare a class to be a subclass of Thread. This subclass should override the run method of class Thread. The other way to create a thread is to declare a class that implements the Runnable interface. That class then implements the run method. . We will use the second way implicitly 9 Methods in Thread class (1) .start() Causes this thread to begin execution; the Java Virtual Machine calls the run method of this thread. . The result is that two threads are running concurrently: the current thread (which returns from the call to the start method) and the other thread (which executes its run method). It is never legal to start a thread more than once. In particular, a thread may not be restarted once it has completed execution. join() . Waits for this thread to die. InterruptedException - if any thread has interrupted the current thread. The interrupted status of the current thread is cleared when this exception is thrown. 10 Methods from Thread Class (11) sleepllong millis) Causes the currently executing thread to sleep (temporarily cease execution) for the specified number of milliseconds, subject to the precision and accuracy of system timers and schedulers. The thread does not lose ownership of any monitors. . Even though we cannot use sleep function to solve the race problem, the producer and consumer both need to sleep random time intervals to emulate unpredictable execution speeds. 11 Structure for version one public class RaceProblen static int [] buffer new int [186]: static int next_in., next_out - ; static int count - 2; // count how many rounds no race condition public static void main(String] args) throws InterruptedException // Create producer thread t1 then Create consumer thread t2 // Start both threads: t1.start(): t2.start(): 1/ join both thread: t1.join(); t2.join(); > public static void producer() throws InterruptedException) public static void consumer() throws InterruptedException) 12 Version One Producer public static void producer() throws InterruptedException while(true) { 1/ random k 1 int k1 = (int) (Math.random() * buffer.length/3) + 1; // write kl data to buffer. Regardless if buffer is full or not for (int i = 0; i 1) consumer too slow System.out.println("Race condition detected! Consumer too slow): System.exit(1); ) else if (data -- 0) producer too slow System.out.println("Race condition detected Producer too slow"); Systen.exit(1); ) else buffer(next out + 1) buffer.length); clear buffer next out = (next out + k2) buffer.length; System.out.println("Round ". **count. no race condition detected yet): 14 Create a thread for producer Similarly, create a Thread t2 for consumer // Create producer thread Thread t1 = new Thread(new Runnable() { @Override public void run() { try ( producer(); > catch (InterruptedException e) { e.printStackTrace(): ) }); 15 Version Two Idea In version two, we need to ensure the following things: If there is not empty buffer, producer has to wait . If there is no data in buffer, consumer has to wait Idea: Use java semaphore. One for emptyBuffer. One for occupiedBuffer 16 Structure for version two import java.util.concurrent. Senaphore: public class RaceProbleModifiedv2 static final int BUFFER_SIZE = 10; default buffer size static final int ROUND - 20: 1 default run 28 round static int Il buffer = new int [BUFFER_SIZE]: static int limit. ROUND: // after this time, program end static int next_in- . next out - ; static Semaphore emptyBuffer - new Semaphore(buffer.length): static Senaphore occupiedBuffer new Senaphore(8): static int count = 0; static boolean done - false; // use to control last round public static void main(String) args) throws InterruptedException { } public static void produce() throws InterruptedException { } public static void consume() throws InterruptedException( 17 Java Semaphore class (1) . main function has no change from version 1 To implement produce function and consume function, we use java semaphore . Constructors Semaphore(int permits) . Creates a semaphore with the given number of permits and nonfair fairness setting. Semaphore(int permits, Boolean fair) Creates a semaphore with the given number of permits and the given fairness setting. . Parameters: permits-the initial number of permits available. This value may be negative, in which case releases fair-true if this semaphore will guarantee first-in first-out granting of permits under contention, else false. 18 Java Semaphore class (II) public void acquire() throws InterruptedException Equivalent P method in zybook Acquires a permit from this semaphore, blocking until one is available, or the thread is interrupted . public void releasel) Equivalent to V method in zybook . Releases a permit, returning it to the semaphore. We don't need their overloaded versions . public void acquire(int permits) throws InterruptedException . public void release(int permits) . 19 Pseudo code for producer public static void produce() throws InterruptedException while (!done) { generate randon number 1 between 1 and half of buffer size for i fronte 11 acquire one perndt froncnotyouffer set corresponding buffer value to be Notice that limit is also shared data. It it possible not consistent. Hart Pseudo code for producer public static void produce() throws InterruptedException { while (!done) { // generate random number k1 between 1 and half of buffer size // for i from 0 to k1 - 1 { // acquire one permit from emptyBuffer // set corresponding buffer value to be 1 // release one permit to occupiedBuffer } Notice that limit is also shared data. It it possible not consistent. However, we don't handle it here. It is easy to handle. Just one more semaphore. // udpate next_in 11 print out message // update limit // if limit public static void producer() throws InterruptedException) public static void consumer() throws InterruptedException) 12 Version One Producer public static void producer() throws InterruptedException while(true) { 1/ random k 1 int k1 = (int) (Math.random() * buffer.length/3) + 1; // write kl data to buffer. Regardless if buffer is full or not for (int i = 0; i 1) consumer too slow System.out.println("Race condition detected! Consumer too slow): System.exit(1); ) else if (data -- 0) producer too slow System.out.println("Race condition detected Producer too slow"); Systen.exit(1); ) else buffer(next out + 1) buffer.length); clear buffer next out = (next out + k2) buffer.length; System.out.println("Round ". **count. no race condition detected yet): 14 Create a thread for producer Similarly, create a Thread t2 for consumer // Create producer thread Thread t1 = new Thread(new Runnable() { @Override public void run() { try ( producer(); > catch (InterruptedException e) { e.printStackTrace(): ) }); 15 Version Two Idea In version two, we need to ensure the following things: If there is not empty buffer, producer has to wait . If there is no data in buffer, consumer has to wait Idea: Use java semaphore. One for emptyBuffer. One for occupiedBuffer 16 Structure for version two import java.util.concurrent. Senaphore: public class RaceProbleModifiedv2 static final int BUFFER_SIZE = 10; default buffer size static final int ROUND - 20: 1 default run 28 round static int Il buffer = new int [BUFFER_SIZE]: static int limit. ROUND: // after this time, program end static int next_in- . next out - ; static Semaphore emptyBuffer - new Semaphore(buffer.length): static Senaphore occupiedBuffer new Senaphore(8): static int count = 0; static boolean done - false; // use to control last round public static void main(String) args) throws InterruptedException { } public static void produce() throws InterruptedException { } public static void consume() throws InterruptedException( 17 Java Semaphore class (1) . main function has no change from version 1 To implement produce function and consume function, we use java semaphore . Constructors Semaphore(int permits) . Creates a semaphore with the given number of permits and nonfair fairness setting. Semaphore(int permits, Boolean fair) Creates a semaphore with the given number of permits and the given fairness setting. . Parameters: permits-the initial number of permits available. This value may be negative, in which case releases fair-true if this semaphore will guarantee first-in first-out granting of permits under contention, else false. 18 Java Semaphore class (II) public void acquire() throws InterruptedException Equivalent P method in zybook Acquires a permit from this semaphore, blocking until one is available, or the thread is interrupted . public void releasel) Equivalent to V method in zybook . Releases a permit, returning it to the semaphore. We don't need their overloaded versions . public void acquire(int permits) throws InterruptedException . public void release(int permits) . 19 Pseudo code for producer public static void produce() throws InterruptedException while (!done) { generate randon number 1 between 1 and half of buffer size for i fronte 11 acquire one perndt froncnotyouffer set corresponding buffer value to be Notice that limit is also shared data. It it possible not consistent. Hart Pseudo code for producer public static void produce() throws InterruptedException { while (!done) { // generate random number k1 between 1 and half of buffer size // for i from 0 to k1 - 1 { // acquire one permit from emptyBuffer // set corresponding buffer value to be 1 // release one permit to occupiedBuffer } Notice that limit is also shared data. It it possible not consistent. However, we don't handle it here. It is easy to handle. Just one more semaphore. // udpate next_in 11 print out message // update limit // if limit
