1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to creaate a priority queue using print queue

  1. Apr 12, 2012 #1
    1. The problem statement, all variables and given/known data
    Its a lot but here is the assignment:

    You are going to implement an event driven simulation of a priority queue serving a printer. Each job will have one of 5 priorities:
    enum Priority { development, client, preferred, highest, scheduled };
    The printer will be assumed to print at the rate of 10 pages per minute (slow, but it simplifies the math.) As a result, the simulation will maintain the time to the nearest tenth of a minute. Here is the input information for the simulation. The simplest approach is to input all this information into the event list before the simulations begins. The simulation will begin with the first event in the event list, and will end at time 125. The lowest priority level is development, and the highest priority is scheduled. No job will enter the system with priority scheduled; it can only result from the job being scheduled by the console. Try to output only one or two lines per event. Thus, your output should be only a few pages. The printer will have two states, busy, and idle, and the simulation will begin with the printer idle. Here is the program input:
    4 Required Classes – (Instance data in the Event and QueueEntry classes is similar, not identical.)
    EventList class & Event class. The EventList will be a list of Event objects ordered by time stamp. The next event to be processed in the simulation will always be the first event in the EventList. Actually, it is not necessary to remove items from the EventList as they are processed, just keep moving down the list if you like.
    PrintQueue class & QueueEntry class. There will be 5 print queues, one for each priority level. Each print queue will hold the QueueEntries matching that priority level. Each print queue will operate in FIFO order. Together, the 5 print queues will operate as a priority queue. The VAX/VMS operating system ready process scheduler worked exactly like this except there were 32 priority levels (queues).
    Required Data Structures –
    1 EventList containing objects of the Event class ordered by time. I suggest you create an ArrayList of <Event>.
    5 PrintQueues containing objects of the QueueEntry class. I suggest you create each PrintQueue as an ArrayList of <QueueEntry>. Each print queue will generally operate FIFO, but boost, kill, or schedule event may require an entry be removed from one list and perhaps moved to another.
    Simulation Overview –
    The EventList controls the simulation. I suggest you begin your program by inputting all the events on the previous page into your event list. The event list will, of course, be updated as the simulation progresses.
    When a job arrives, it will begin printing if the printer is idle. Otherwise, the job will enter the appropriate print queue. Usually, a boost event will also be added to the event list at a later time.
    When a job begins printing, a print termination event will be inserted in the event list at the appropriate time.
    When the current print job terminates, the next job to be printed will always be the first job in the highest priority non-empty print queue.
    The simulation must also have the ability to respond to a boost event by removing a job entry from its print queue, boosting its priority, incrementing the boost count, inserting the job entry at the rear of the next priority level print queue, and (usually) inserting another boost event for the same job at some time in the future.
    The response to a schedule command is similar. The job will be moved to the rear of the scheduled print queue and its boost count will be updated by the correct amount.
    The simulation must also respond to user kill and console kill commands. Either of these will terminate the job if it is printing, and remove the job from the print queue if it is found there. Otherwise, the job has already left the system and no action takes place.
    The event descriptions below give a more complete description of each type of event, including REQUIRED OUTPUT IS SHOWN BELOW IN RED.
    Event Types – Each of these should generate one or two lines of output, but BeginPrint need not be placed in the event list.
    JobArrival – Output a job arrival event line. If the printer is idle, perform a BeginPrint on the job immediately. If the printer is busy, enter the job at the rear of the appropriate print queue, and insert a boost event for the job as dictated by the boost paragraph below.
    Display at least: event type, job number, number of pages, entry time, and priority.
    EndPrint - Output a print termination line. Detach the first job from the highest priority non-empty print queue. Insert a Print Termination event for it in the EventList at the appropriate time. Then perform a BeginPrint for the new job. If all the print queues are empty, set the printer status to idle.
    If not dead, display at least: event type, job number, number of pages printed, entry time, exit time, and number of boosts.
    If dead, display event type, job number, time flagged dead.
    Boost – This feature is added to reduce the likelihood of starvation. If a development job stays in the queue 30 minutes, boost its priority to client. The same for boosting a client job to preferred, but the boost occurs after only 25 minutes, and the same for boosting a preferred job to highest, but wait only 20 minutes. There are no boost events associated with highest or scheduled jobs. No boost event is inserted if the printer was idle when the job arrived.
    If the printer is busy, the implementation will be as follows: When a development job arrives, add a boost event to the EventList timed 30 minutes after the arrival time. If this boost event is reached and has not been flagged dead, the job’s priority will be changed to client. Move the job from the development print queue to the rear of the client print queue, increment the boost counter, output a line indicating that a priority boost has occurred, and finally, insert a new boost event for the job that would occur 25 minutes after the current time (the correct wait for a client job). The other cases will be handled similarly.
    If the job begins printing before the boost event is reached, or the job is killed, or scheduled, flag the boost event dead. Do not remove it as it should still generate output when reached.
    A low priority job could be boosted more than once under this scheme. No boost events are inserted for highest or scheduled priority jobs. One of the pieces of member data associated with each print queue entry is the number of times the job has been boosted.
    If not dead, display at least: event type, job number, entry time, new priority, and number of boosts.
    If dead, display event type, job number, time flagged dead.
    BeginPrint – Detach the first entry in the first non-empty print queue. Flag any boost events for this job dead. Insert a PrintTermination event in the event list at the appropriate time. Begin printing the job (output the line).
    Display at least: event type, job number, time begin printing, priority, and number of boosts.
    UserKill - If the job is found waiting in a print queue, detach it from the queue, and flag
    any boost events for the job dead. If found printing, terminate printing immediately, and flag the existing PrintTermination event dead. Begin printing the next job. If not found, nothing is changed.
    If found, display at least: event type, job number, entry time, time of death.
    If not found, display event type, job number and “not found”.
    ConsoleKill – Do the same as you would for a user kill.
    Schedule print job from console – If the job is found in a print queue, change the priority of the job to scheduled, and move it to the rear of that queue. Adjust the boost number according to the number of steps up made. Flag any boost events for the job dead. If not in a print queue, do nothing.
    If already in scheduled queue, do nothing.
    If found in another queue, display at least: job number, entry time, new priority, and number of boosts.
    If not found, display event type, job number and “not found”.
    Notes: You should first decide what data needs to be stored in the nodes in each structure, and what operations need to be supported on each structure.
    Most of these tasks are best implemented by a hierarchy of smaller tasks (methods). Still other low level tasks are implied by these higher level tasks. For example, “find the boost event for job()” is not listed, but you will need it.
    The next page shows an excel spreadsheet describing the first 60 minutes of the simulation. Remember, your simulation ends at time 125. I suppose it could end earlier if all the print queues become empty and the printer is idle.
    Do not replicate the output format on the given spreadsheet. The requirements above also demand more information than is displayed. Therefore, your output should be formatted much better. Also, the spreadsheet is written as a check, not as a template. Also, if you find an error in the spreadsheet, please let me know, so that I can inform the others. Be sure to check your answers beyond 60 seconds.

    2. Relevant equations



    3. The attempt at a solution
    I have not yet coded anything yet but rather I just want some clarification how do I creat a PQ using 5 Queues do I create 5 queues and link them using a linked list or something am I on the right track or not?
     
  2. jcsd
  3. Apr 13, 2012 #2
    wow wow wow no one guys I just wanted to know if I was on the right track
     
  4. Apr 14, 2012 #3

    rcgldr

    User Avatar
    Homework Helper

    You create 5 separate queues. These queues would not be linked to each other, other than your code would scan the 5 queues. You might want to use an array of queues for the 5 queues. It's not clear how you manage events. The description implies that boost events are somehow manually "added later", then goes on to describe what appears to be a set of rules for boost events as opposed to boost events being manually added. If the boost events are rule based, then you do the equivalent of starting a timer event each time you add an item to an empty queue or remove an item from a queue that doesn't end up empty, or stop the timer if the queue was emptied. You could scan the timer events after each print job completion to check for queue movement.
     
    Last edited: Apr 14, 2012
  5. Apr 14, 2012 #4
    Thanks man I will try to work from that
     
  6. Apr 15, 2012 #5
    Is my queue ok?
    Code (Text):

    class Queue
    {
       private static final int DEFAULT_SIZE = 5;
       private int size;
       private int front;
       private int back;
       private int[] values;
       public Queue()
       {
          this(DEFAULT_SIZE);
       }
       public Queue(int size)
       {
          this.size = size;
          values = new int[size];
          front = 0;
          back = 0;
       }
       public boolean isFull()
       {
          if( (back+1) % size == front)
          {
             return true;
          }
          else
          {
             return false;
          }
       }
       public boolean isEmpty()
       {
          if(back == front)
          {
             return true;
          }
          else
          {
            return false;
          }
       }
       public void enqueue(int x)
       {
          if(!isFull())
          {
             back = (back+1) % size;
             values[back] = x;
          }
       }
       public int dequeue()
       {
          if(!isEmpty())
          {
             front = (front+1) % size;
             return values[front];
          }
          return 0;
       }
    }
     
     
  7. Apr 16, 2012 #6

    rcgldr

    User Avatar
    Homework Helper

    This looks ok, but it would be more flexible to use a linked list instead of a circular buffer, in which case you would allocate elements to enque, and free elements after they completed printing.

    It's not clear from the problem statement how close to a real world situation this is supposed to be. Are you supposed to use some form of multi-threaded (or interrupt driven) code to handle the print jobs, queues, and event timers?
     
  8. Apr 16, 2012 #7
    On top of me sucking at programming yes I agree it is completley confusing and we have not even gone over this in class yet he expects us to do it. I believe he is pushing the due date back because no one has done it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How to creaate a priority queue using print queue
  1. Destroying a queue (Replies: 1)

  2. Not printing (Replies: 4)

Loading...