Spring 2000, CSE 428: Assignment 5


Distributed: Mar 3.
Due: Mar 21 in class.
Total maximum score: 100 points.
The purpose of this assignment is to provide experience with OO programming and Threads in Java.


A requests handler

Consider the following problem: in a certain office, there are four employes, Sam, Sue, John and Jane. The job of Sam and Sue consists in receiving requests; the job of John and Jane consists in handling them. Each request is associated with a number from 0 to 4 representing its priority. The requests have to be handled according to FIFO+priority discipline, meaning that the requests with higher priority must be handled first, and requests with the same priority must be handled according to the FIFO discipline.

A possible program representing the above situation is given below. The four employes are four threads working in parallel and sharing a common priority queue. Sue and Sam receive the requests from a Requests Generator, which generates requests at random intervals and with random priority. Each time they receive a request, they insert it in the queue by using the insert(Request) method. These requests are then retrieved by John and Jane by using the Request pop() method.

Object of the assignment

The assignment consists in defining the Priority Queue class. Please make sure that race conditions and busy waiting are avoided. Each time the operations insert and pop are performed, please print the name of the specific operation (insert or pop) and the content of the queue at that moment, so that we can see the trace of the program when we test it.

Format of the solution

Please give an hard copy of your source code to the instructor by the due date. Furthermore, you should also email your source code to cg428@cse.psu.edu by the due date, so to allow us to check that your program runs correctly. Please send the code as an attachment (not by "cut-and-paste"), and use as filename the name "RequestsHandler", followed by the last 4 digits of your student id and then by ".java". Example: if the last digits of your id are 1001, then the file should have name RequestsHandler1001.java.

Please make sure that your program can be compiled and executed on Unix and that it is self-contained. Namely, it should contain all the definitions and the main function. Note that the main class (i.e. the class containing the function main()) should have name RequestsHandler followed by the last 4 digits of your student id. Example: RequestsHandler1001.

Testing the solution

To test your program, you need first to compile your program in Java bitcode and then run the compiled code. This is done by the following two instructions (assuming the name of the file is RequestsHandler1001.java):
   > javac RequestsHandler1001.java
   > java RequestsHandler1001
A compiled program, completed with the definition of the priority queue, is available for you to test what the behaviour of the solution should be. To run this program, do the following:

The program

///////////////////////////////////////////////////////////////////////
////                Requests Handler                  /////////////////
//// File RequestsHandlerXXXX.java  (XXXX is your id) /////////////////
///////////////////////////////////////////////////////////////////////
  
public class RequestsHandlerXXXX {  // Replace XXXX with your Id
   public static void main(String[] args) {
      PriorityQueue q = new PriorityQueue();
      RequestsGenerator g = new RequestsGenerator();
      new Receiver("Sam",q,g).start();
      new Receiver("Sue",q,g).start();
      new Handler("John",q).start();
      new Handler("Jane",q).start();
   }
}

///////////////////////////////////////////////////////////////////////

class Receiver extends Thread {
   private String name;
   private PriorityQueue queue;
   private RequestsGenerator gen;
   public Receiver(String s, PriorityQueue q, RequestsGenerator g) { 
      name = s; 
      queue = q; 
      gen = g;
   }
   public void run() {
      try {
         while (!isInterrupted()) {
            Request r = gen.getRequest(); // get new request
            System.out.println(name + " has received a new request R" + 
                               r.getIde() + " with priority " + 
                               r.getPriority());
            queue.insert(r); // insert the request in the queue
         }
      } 
      catch (InterruptedException e) { 
         return; // an interruption ends the thread
      }
   }
}

///////////////////////////////////////////////////////////////////////

class Handler extends Thread {
   private String name;
   private PriorityQueue queue;
   public Handler(String s, PriorityQueue q) { 
      name = s; 
      queue = q; 
   }
   public void run() {
      try {
         while (!isInterrupted()) {
            Request r = queue.pop(); // get new request from the queue
            System.out.println(name + " is going to handle request R" +  
                               r.getIde());
            sleep((long)(Math.random()*1000)); // handle request
         }
      } 
      catch (InterruptedException e) { 
         return; // an interruption ends the thread
      }
   }
}

///////////////////////////////////////////////////////////////////////

class Request{
    private int ide;
    private int priority;
    public Request(int n, int p){ ide = n; priority = p; }
    public int getIde(){ return ide; }
    public int getPriority(){ return priority; }
}

///////////////////////////////////////////////////////////////////////

class RequestsGenerator{
    private int nextIde;
    public RequestsGenerator(){ nextIde = 1; }
    public synchronized Request getRequest()
       throws InterruptedException  // interrupted exceptions are caused by wait()
    { 
       wait((long)(Math.random()*1000)); // requests are generated at random 
       int priority = (int)(Math.random()*5); // random priority in [0-4]
       Request r = new Request(nextIde++,priority);
       return r;
    }
}

///////////////////////////////////////////////////////////////////////

class PriorityQueue {

// The definition of this part is the object of the assignment
// In particular, you need to define the methods insert(Request) and
// Request pop(). 

}     

///////////////////////////////////////////////////////////////////////