Producer-Consumer with Peterson algorithm in java

Question

Producer-consumer problem in Java with a circular buffer of N positions.

• There is a single thread representing the producer that will produce consecutive integer elements
• There is a dimensioned circular buffer shared by the producer and the consumer to produce and consume the elements. The elements will have the following attributes:
  • elem: array with the elements of the buffer.
  • p: indicates the position by which it is produced.
  • c: indicates the position by which it is consumed.
  • nelem: number of valid elements contained in the buffer
• There is a single consumer that will display the elements deposited in the buffer.

Edited code:

import java.util.concurrent.atomic.AtomicBoolean;
public class ProducerConsumer
{
 public static final int bufferSize = 6;
 private static CircularBuffer buffer = new CircularBuffer (bufferSize);
 public static void main (String[] args)
 {
 if ( args.length != 1 ) {
 String className = ProductorConsumidor.class.getSimpleName();
 throw new RuntimeException ("Usage: java " + className + " number");
 }
 int numElems = Integer.parseInt (args[0]);
 Consumer consumer = new Consumer (buffer, numElems);
 Producer producer = new Producer (buffer, numElems);
 consumer.start(); producer.start();
 }
 public static class Peterson
 {
 private static volatile int turn;
 private static AtomicBoolean[] flag = { new AtomicBoolean(),
 new AtomicBoolean() };
 private int id;
 public Peterson (int i)
 {
 id = i;
 }
 private int other ()
 {
 return id == 0 ? 1 : 0;
 }
 public void lock ()
 {
 flag[id].set (true);
 turn = other ();
 while ( turn == other() && flag[other()].get() )
 Thread.yield ();
 }
 public void unlock ()
 {
 flag[id].set (false);
 turn = other ();
 }
 }
 public static class CircularBuffer
 {
 private volatile int[] elem;
 private volatile int nElems;
 private int producerPosition;
 private int consumerPosition;
 private Peterson pt0 = new Peterson (0);
 private Peterson pt1 = new Peterson (1);
 public CircularBuffer (int bufferSize)
 {
 elem = new int[bufferSize];
 producerPosition = 0;
 consumerPosition = 0;
 nElems = 0;
 }
 public void produce (int element)
 {
 while ( nElems == bufferSize )
 ; // wait while full
 produceNewElement (element);
 }
 public void produceNewElement (int element)
 {
 pt0.lock ();
 elem[producerPosition] = element;
 producerPosition = (producerPosition + 1) % bufferSize;
 ++nElems;
 pt0.unlock ();
 }
 public int consume ()
 {
 while ( nElems == 0 )
 ; // wait while empty
 return consumeNewElement ();
 }
 public int consumeNewElement ()
 {
 pt1.lock ();
 int ret;
 ret = elem[consumerPosition];
 consumerPosition = (consumerPosition + 1) % bufferSize;
 --nElems;
 pt1.unlock ();
 return ret;
 }
 }
 public static class Producer extends Thread
 {
 private CircularBuffer buffer;
 private int numElems;
 public Producer (CircularBuffer b, int m)
 {
 buffer = b;
 numElems = m;
 }
 @Override
 public void run ()
 {
 for ( int i = 0; i < numElems; ++i ) {
 buffer.produce (i);
 }
 }
 }
 public static class Consumer extends Thread
 {
 private CircularBuffer buffer;
 private int numElems;
 public Consumer (CircularBuffer b, int m)
 {
 buffer = b;
 numElems = m;
 }
 @Override
 public void run ()
 {
 int data, previousData;
 data = buffer.consume ();
 for ( int i = 0; i < numElems - 1; ++i ) {
 System.out.printf (data + " ");
 previousData = data;
 data = buffer.consume ();
 if ( previousData > data )
 throw new RuntimeException ("Incorrect data order");
 }
 System.out.printf (data + " ");
 }
 }
}

Original code:

import java.util.concurrent.atomic.AtomicBoolean;
public class ProducerConsumer
{
 public static void main (String[] args)
 {
 if ( args.length != 1 ) {
 throw new RuntimeException ("Usage: fileName number");
 }
 int N = 6; // Size of circular buffer
 int max = Integer.parseInt (args[0]); // number of elements to produce
 CircularBuffer buf = new CircularBuffer (N);
 Consumer cons = new Consumer (buf, max);
 Producer produ = new Producer (buf, max);
 cons.start(); produ.start();
 }
 public static class Peterson
 {
 private volatile int turn;
 private AtomicBoolean[] flag = new AtomicBoolean[2];
 private int id;
 public Peterson (int i)
 {
 id = i;
 }
 private int other ()
 {
 return id == 0 ? 1 : 0;
 }
 public void lock ()
 {
 flag[id].set (true);
 turn = other ();
 while ( turn == other() && flag[id].get() )
 Thread.yield ();
 }
 public void unlock ()
 {
 flag[id].set (false);
 turn = other ();
 }
 }
 public static class CircularBuffer
 {
 private volatile int[] elem;
 private volatile int nelem; // control elements in buffer
 private int p; // consumer position
 private int c; // producer position
 private Peterson pt0 = new Peterson (0);
 private Peterson pt1 = new Peterson (1);
 // Shared circular buffer
 public CircularBuffer (int N)
 {
 elem = new int[N];
 p = 0;
 c = 0;
 nelem = 0;
 }
 public void produce (int e)
 {
 while ( nelem == elem.length ); // while full
 pt0.lock (); // lock
 elem[p] = e; // produce new element
 p = (p + 1) % elem.length; // new position in the circular array
 ++nelem; // increment number of elements in the shared buffer
 pt0.unlock (); // unlock
 }
 public int consume ()
 {
 while ( nelem == 0 ); // while empty
 pt1.lock (); // lock
 int ret; // variable to return
 ret = elem[c]; // assignment
 c = (c + 1) % elem.length; // new position in the circular array
 --nelem; // decrement number of elements in the shared buffer
 pt1.unlock (); // unlock
 return ret;
 }
 }
 public static class Producer extends Thread
 {
 private CircularBuffer buf;
 private int max;
 public Producer (CircularBuffer b, int m)
 {
 buf = b;
 max = m;
 }
 public void run ()
 {
 for ( int i = 0; i < max; ++i ) {
 buf.produce (i);
 }
 }
 }
 public static class Consumer extends Thread
 {
 private CircularBuffer buf;
 private int max;
 public Consumer (CircularBuffer b, int m)
 {
 buf = b;
 max = m;
 }
 public void run ()
 {
 int data, previousData;
 data = buf.consume ();
 for ( int i = 0; i < max - 1; ++i ) {
 System.out.printf (data + " ");
 previousData = data;
 data = buf.consume ();
 if ( previousData > data )
 throw new RuntimeException ("Incorrect data order");
 }
 System.out.printf (data + " ");
 }
 }
}

• yuri: What is your question exactly? There are also already several related topics dealing with this, maybe those can be of help to you?
• 200_success: @yuri If there is no question, then we review the code in general.
• user61445: What name could I give the other method?

Answer 1

Completely broken, part 1

You must never have run your program, because I ran it and immediately got a null pointer exception. The problem is here:

 private AtomicBoolean[] flag = new AtomicBoolean[2];

This creates an array of two null objects. Later, when you do flag[0] = true, you get a null pointer exception because flag[0] is null. You can initialize the two objects like this instead:

 private AtomicBoolean[] flag = { new AtomicBoolean(),
 new AtomicBoolean() };

Completely broken, part 2

After fixing your null pointer exception, your lock() function hangs:

 public void lock ()
 {
 flag[id].set (true);
 turn = other ();
 while ( turn == other() && flag[id].get() )
 Thread.yield ();
 }

Imagine the first thread (id = 0) tries to call lock() for the first time. It sets flag[0] = true and turn = 1. Then it enters the while loop and it will loop forever because the condition will be true from the values set by the previous two lines.

The correct Peterson algorithm has this condition for the while loop:

 while ( turn == other() && flag[other()].get() )

Notice that it checks the other flag, not this id's flag.

Completely broken, part 3

Even after fixing the hang, your Peterson algorithm is still broken. The problem is that your producer and consumer need to be sharing the same flag array and turn variable, but currently, each is creating its own flag and turn. Therefore, the lock() function always permits each side to immediately proceed, without doing any locking.

To fix this, you could make flag and turn be static. This will cause the producer and consumer to share the same variables. However, it also will limit your Peterson class to only ever supporting one producer-consumer pair. If you wanted to have more than one producer-consumer pair, you would need to modify your Peterson class in some other way.

Answer 2

Naming

You don't need to comment your variables if you use significative names.

Don't write

int N = 6; // Size of circular buffer

but

int circularBufferSize = 6;

Moreover it's a constant so it should be final and moved to a static field

public static final int CIRCULAR_BUFFER_SIZE = 6;

buf, cons and produ become buffer,consumer and producer

int c; // consumer position becomes int consumerPosition; and so on...

Comments

No need to comment each line of consume/produce methods, you can split your code into simpler methods, example:

public void produce(int element) {
 waitConsumer();
 produceNewElement(element);
}
private void waitConsumer() {
 while (nelem == elem.length) {
 // BUSY WAITING
 ;
 }
}
private void produceNewElement(int element) {
 pt0.lock();
 elem[p] = e;
 p = (p + 1) % elem.length;
 nelem++;
 pt0.unlock();
}

• Kalle Richter: Talking variable names can replace a simple comment explaining what the name otherwise does. I wouldn't suggest to remove comments in the code flow, like BUSY WAITING, though, as long as they make up less than 40% of the code at all (BUSY WAITING is gone in the question meanwhile).

Answer 3

Space

Usually, programmers not putting in enough tabs, spaces and newlines is a problem, but with your code, it's just the other way around. Here are some suggestions:

• Generally, using two or more spaces before anything is considered an overkill. A single space will do fine in all but the rarest instances.
• Avoid splitting methods from their parentheses. There is no reason to write main (String[] args) where main(String[] args) makes it a lot clearer that the stuff inside the parentheses is an argument to your function. The same goes for constructors.
• Leaving space after an opening paren and before a closing paren is generally discouraged.
• Indenting variable names to all start on the same horizontal position is not wrong, yet it is a practice not seen too often (at least not by me). Usually, just leaving a single space before each variable name should suffice, but ultimately, this one boils down to personal preferences.

All of these points are of course somewhat depending on one's coding style. However, if somebody else is required to read your code, it makes a lot of sense if they can expect you to loosely adhere to some common style guide because they tend to make reading and understanding easier and most programmers are used to them. Do not make your reviewer's life harder than it must be, because they are probably already at full capacity understanding what your code does.

To improve your style, I suggest that you maybe take a look at one of the many style guides available, such as Google's.