Project 2: Java Blocking Queue

This project is derived from the Java BlockingQueue tutorial at http://tutorials.jenkov.com/java-util-concurrent/blockingqueue.html. This is a fundamental data structure needed to implement a producer/consumer parallel progamming pattern. In this project, you are going to implement a simplified version of a BlockingQueue that puts and takes Strings from many producer and many consumer threads. Another tutorial provides a simplified implementation based on a linked list http://tutorials.jenkov.com/java-concurrency/blocking-queues.html. Java itself provides many implementations of the BlockingQueue interface.

Implement BlockingQueue in an Array.

Clone the repository at https://github.com/randalburns/PP.Proj2.BlockingQueue into an environment that has a reasonable version of Java. This project was implemented on Java 11, but is pretty vanilla and so should work everywhere.

In the file BlockingQueue.java, fill out the sections labelled //TODO. In doing so you will:

• Implement a queue on top of an array.
  • use the variable head to point to the next available element in a list.
  • use the variable qlen to encode the number of items in the queue
  • define logic to wrap from the last element in the array to the first element in the array
    • you will need to consider this for both head and qlen.
    • limit is the maximum number of elements in the queue.
• Reimplement the wait/notify pattern of http://tutorials.jenkov.com/java-concurrency/blocking-queues.html. This code will:
  • have producers wait() when the queue is full
  • have consumers wait() when the queue is empty
  • have producers notifyAll() to activate consumers when putting an element into an empty list.
  • have consumer notifyAll() to activate producers when taking an element from a full list.

Debug your implementation on two threads and a small number of items. Then, make sure that it works correctly for many threads and a large number of items.

Questions:

1. When many threads are waiting on an empty queue, what happens when a thread puts a String and calls notifyAll()? Why is this thread safe?

2. Read the documentation for sycnhronized methods. Do synchronized methods synchronize on the object or the class? Why is this the right scope? (Consider that there may be multiple queues in an application.)

3. It is tempting to allow the String copy operations to proceed in parallel because they are expensive (see below). This is not thread safe. Why? Give an example.

• To allow String copies to occur in parallel one would
  • Remove the synchronized from the function definitions.
  • Implement a synchronized block within each function that makes accesses to head and qlen mutually exclusive.
  • Have only the following lines outside of mutual exclusion sections.

    // in put()
    this.queue[slot] = item;

    // in take()
    String ret_obj = this.queue[tail];
    queue[tail]=null;

How to turn in

Submit your implementation of BlockingQueue.java and a PDF with your solutions to the questions to Gradescrope using ….

Due date: Friday October 15, 2020. 11:59:59 pm.