4
\$\begingroup\$

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 + " ");
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ What is your question exactly? There are also already several related topics dealing with this, maybe those can be of help to you? \$\endgroup\$ – yuri May 31 '17 at 13:12
  • \$\begingroup\$ @yuri If there is no question, then we review the code in general. \$\endgroup\$ – 200_success May 31 '17 at 14:34
  • \$\begingroup\$ What name could I give the other method? \$\endgroup\$ – Arturo Jun 1 '17 at 8:53
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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();
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Karl Richter May 31 '17 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.