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

// Author: Julie Petrusa (991339)                                             //

// Due date: March 22, 2002                                                   //

// Project description: Small Operating System Simulator                      //

// -Console: Provides reading and writing ability. The user specifies the     //

//           source of input, and the destination of output.                  //

// -CPU: Responsible for keeping track of the currently running process and   //

//       whether or not the CPU is idle.                                      //

// -Interrupt: Responsible for converting a string of input into an interrupt //

//             number plus an array of arguments.                             //

// -IODevice: Maintains the waiting queue for a particular device. It also    //

//            looks to the waiting queue each time the device become idle to  //

//            see if a request must be initiated.                             //

// -Memory: Memory management system that uses a page table. Maintains 64     //

//          frames of size 1k.                                                //

// -OS: Sets up system. Processes interrupts until end of file or shut down   //

//      request. Shuts down system. Contains main.                            //

// -PCB: Responsible for creating and maintaining Process Control Blocks. The //

//       state, priority, burst time, and page table are set and read here.   //

// -Queue: Uses Java's linked list to implement FIFO queues.                  //

// -Scheduler: Responsible for maintaining the ready queue for the CPU, and   //

//             for dispatching jobs to the CPU. The ready queue is a multiple //

//             level feedback queue with three levels: Q0, Q1, and Q2. Q0 has //

//             the highest priority and Q2 has the lowest.                    //

// Known bugs: none                                                           //

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



import java.io.*;

import java.util.*;

import java.util.Iterator;

import java.util.StringTokenizer;

import java.lang.Integer;



/******************************************************************************/

/******************************************************************************/



class Console

   {

   //---------------------------------------------------------------------------

   // fields

         // this reader is used to read from the keyboard

         private InputStreamReader reader = new InputStreamReader(System.in);

         private BufferedReader keyboardReader = new BufferedReader(reader);



         // reader for the input file

         private FileReader fr = null;



         // reader for keyboard or file

         private BufferedReader stdin = null;

         private int fromKeyboard = 0;



         // similar setup for the output

         private FileOutputStream fw = null;

         private PrintStream stdout = null;

         private int toScreen = 0;

   //---------------------------------------------------------------------------

   // constructor

   // -sets up the input and output streams

   // -determines from where the user wants the input read

   // -determines to where the user wants the output to go

         public Console()

            {

            String inputString;

            System.out.println("\nInitializing console ...");

            do    // does user want console bound to keyboard or file for input

               {

               System.out.print("To read from: ");

               System.out.print("the keyboard enter 0; a file enter 1: ");

               try

                  {

                  inputString = keyboardReader.readLine();

                  fromKeyboard = Integer.parseInt(inputString);

                  }

               catch (IOException e)

                  {

                  System.err.println("Oops! Expecting an integer");

                  }

               if ((fromKeyboard < 0) || (fromKeyboard > 1))

                  {

                  System.err.println("Expecting a 0 or a 1");

                  }

               } while ((fromKeyboard < 0) && (fromKeyboard > 1));

            if (fromKeyboard == 1)  // user wants to read from a file

               {

               System.out.print("Enter the name of the input file: ");

               inputString = "";

               try

                  {

                  inputString = keyboardReader.readLine();

                  }

               catch (IOException e)

                  {

                  System.err.println("Problems reading input file name.");

                  System.exit(-1);

                  }

               System.out.println("Opening file "+inputString+" for input.");

               try

                  {

                  fr = new FileReader(inputString);

                  }

               catch (FileNotFoundException e)

                  {

                  System.err.println("File not found.");

                  System.exit(-1);

                  }

               stdin = new BufferedReader(fr);

               }

            else  // user wants to read from the keyboard

               stdin = keyboardReader;

            do    // setting up the output

               {  // does user want console bound to keyboard or file for input

               System.out.print("To write to: the screen enter 0; ");

               System.out.print("a file enter 1; both enter 2: ");

               inputString = "";

               try

                  {

                  inputString = keyboardReader.readLine();

                  toScreen = Integer.parseInt(inputString);

                  }

               catch (IOException e)

                  {

                  System.err.println("Oops! Expecting an integer");

                  }

               if ((toScreen < 0) || (toScreen > 2))

                  {

                  System.err.println("Expecting 0, 1, or 2");

                  }

               } while ((toScreen < 0) && (toScreen > 2));

            if (toScreen > 0)  // wants to write to file (possibly screen too)

               {

               System.out.print("Enter the name of the output file: ");

               inputString = "";

               try

                  {

                  inputString = keyboardReader.readLine();

                  }

               catch (IOException e)

                  {

                  System.err.println("Problems reading output file name.");

                  System.exit(-1);

                  }

               System.out.println("Opening file "+inputString+" for output.");

               try

                  {

                  fw = new FileOutputStream(inputString);

                  }

               catch (IOException e)

                  {

                  System.err.println("Problems opening file for output.");

                  System.exit(-1);

                  }

               stdout = new PrintStream(fw);

               }

            else  // user wants to write to the screen

               stdout = System.out;

            }

   //---------------------------------------------------------------------------

   // method readLine

   // -reads a line from the input device

         public String readLine()

            {

            String s = null;

            try

               {

               s = stdin.readLine();

               }

            catch (IOException e)

               {

               }

            return s;

            }

   //---------------------------------------------------------------------------

   // method print

   // -prints s on output device(s)

         public void print(String s)

            {

            stdout.print(s);

            if (toScreen == 2)

               System.out.print(s);

            }

   //---------------------------------------------------------------------------

   // method println

   // -prints s plus a line feed on output device(s)

         public void println(String s)

            {

            stdout.println(s);

            if (toScreen == 2)

               System.out.println(s);

            }

   //---------------------------------------------------------------------------

   }  // end Console



/******************************************************************************/

/******************************************************************************/



class CPU

   {

   //---------------------------------------------------------------------------

   // fields

         private PCB runningProcess;

         private boolean idle;

   //---------------------------------------------------------------------------

   // constructor

   // -initially the CPU is idle and no process is running

         public CPU()

            {

            idle = true;

            runningProcess = null;

            }

   //---------------------------------------------------------------------------

   // method currentProcess

   // -returns PCB of currently running process

   // -it could be null

         public PCB currentProcess()

            {

            return runningProcess;

            }

   //---------------------------------------------------------------------------

   // method isIdle

   // -returns true if and only if CPU is idle

         public boolean isIdle()

            {

            return idle;

            }

   //---------------------------------------------------------------------------

   // method runProcess

   // -makes p the running process and CPU non idle

   // -if something else is running, p will overwrite it (should probably call

   //  stopProcess first)

   // -if p is not null, set its state appropriately, and set idle to indicate

   //  the CPU is running a process

         public void runProcess(PCB p)

            {

            runningProcess = p;

            if (p != null)

               {

               p.setStateRunning();

               idle = false;

               }

            }

   //---------------------------------------------------------------------------

   // method stopProcess

   // -stops the current process

   // -current process is removed from CPU

   // -CPU becomes idle

   // -running process become null

   // -returns process that was running

         public PCB stopProcess()

            {

            PCB currentProcess = runningProcess;

            runningProcess = null;

            idle = true;

            return currentProcess;

            }

   //---------------------------------------------------------------------------

   }  // end CPU



/******************************************************************************/

/******************************************************************************/



class Interrupt

   {

   //---------------------------------------------------------------------------

   // fields

         private int value;

         private ArrayList args = new ArrayList();

   //---------------------------------------------------------------------------

   // default constructor

   // -initializes interrupt to the 0 interrupt

   // -should call string2Interrupt before using the interrupt

         public Interrupt()

            {

            value = 0;

            }

   //---------------------------------------------------------------------------

   // method argument

   // -returns (as a string) argument number i (count from 1)

   // -must call string2Interrupt before this can be used

   // -throws outOfBoundsException

         public String argument(int i)

            {

            return (String)args.get(i-1);

            }

   //---------------------------------------------------------------------------

   // method numberOfArguments

   // -returns number of arguments after the interrupt number

   // -must call string2Interrupt before this can be used

         public int numberOfArguments()

            {

            return args.size();

            }

   //---------------------------------------------------------------------------

   // method string2Interrupt

   // -converts a string of the form "iterrupt_number argument_1 argument_2 ...

   //  argument_k" to an integer interrupt number (value), and an array of

   //  arguments stored as strings

         public void string2Interrupt(String s)

            {

            StringTokenizer tokenizer = new StringTokenizer(s);

            String token;

            if (tokenizer.hasMoreTokens())  // try to read the first integer

               {

               token = tokenizer.nextToken();

               try

                  {

                  value = Integer.parseInt(token);

                  System.out.println(value);

                  }

               catch (NumberFormatException e)

                  {

                  System.out.print("Expecting an integer value for interrupt");

                  System.out.println();

                  System.exit(-1);

                  }

               }

            else

               {

               System.out.println("No interrupt on this input line.");

               System.exit(-1);

               }

            args.clear();  // read the arguments and put them in the array

            while (tokenizer.hasMoreTokens())

               {

               token = tokenizer.nextToken();

               args.add(token);

               }

            }

   //---------------------------------------------------------------------------

   // method value

   // -returns interrupt number as an integer

   // -must be called after string2Interrupt

         public int value()

            {

            return value;

            }

   //---------------------------------------------------------------------------

   }  // end Interrupt



/******************************************************************************/

/******************************************************************************/



class IODevice

   {

   //---------------------------------------------------------------------------

   // fields

         private Console console;

         private boolean idle = true;

         private Queue requestQueue = new Queue();

         private int whoAmI;

   //---------------------------------------------------------------------------

   // constructor

   // -creates a device with number deviceNumber

   // -sets up the console for message printing

         public IODevice(int deviceNumber, Console con)

            {

            whoAmI = deviceNumber;

            console = con;

            }

   //---------------------------------------------------------------------------

   // method addToRequestQueue

   // -adds the process p to the request queue for this device

   // -if the device is idle, a request for p is initiated on the device

   // -sets the state of p to waiting

   // -prints a status message to console

         public void addToRequestQueue(PCB p)

            {

            if (p == null)

               {

               return;  // don't add null process

               }

            console.print("  Add process "+p+" to queue for device ");

            console.println(whoAmI+".");

            requestQueue.put(p);

            p.setStateWaiting();

            if (idle)

               this.initiate();

            }

   //---------------------------------------------------------------------------

   // method currentRequest

   // -returns the PCB of the process whose request is currently being processed

         public PCB currentRequest()

            {

            return (PCB)requestQueue.front();

            }

   //---------------------------------------------------------------------------

   // method initiate

   // -initiates IO on the device

   // -selects a process to service from its wait queue

   // -the queue is FIFO, and the device is assumed to be idle when the method

   //  is called

   // -if a process is waiting, the device is not idle after the call

   // -prints a status message to console

         public void initiate()

            {

            if (!requestQueue.isEmpty())

               {

               console.print("  IO initiated on device "+whoAmI);

               console.println(" for process "+(PCB)requestQueue.front()+".");

               idle=false;

               }

            else

               {

               console.print("  IO device "+whoAmI+" has no requests. ");

               console.println("Device idle.");

               }

            }

   //---------------------------------------------------------------------------

   // method isIdle

   // -returns true if and only if the device is idle

         public boolean isIdle()

            {

            return idle;

            }

   //---------------------------------------------------------------------------

   // method iterator

   // -returns an iterator for the request queue

         public Iterator iterator()

            {

            return requestQueue.iterator();

            }

   //---------------------------------------------------------------------------

   // method removeRequest

   // -removes the current request and initiates a new one

   // -returns the PCB of the process currently being serviced

   // -assumes a nonnull process is being serviced, i.e. idle = false

   // -will be idle after the call

   // -initiates IO

         public PCB removeRequest()

            {

            PCB currentRequest = (PCB)requestQueue.get();

            console.print("  Request for IO device "+whoAmI);

            console.println(" by process "+currentRequest+" is terminated.");

            idle = true;

            this.initiate();  // start the next request

            return currentRequest;

            }

   //---------------------------------------------------------------------------

   }  // end IODevice



/******************************************************************************/

/******************************************************************************/



class Memory

   {

   //---------------------------------------------------------------------------

   // fields

         private int totalFrames;

         private int freeFrames;

         private String[] frames;

   //---------------------------------------------------------------------------

   // constructor

   // -system has 64 frames of size 1K

         public Memory()

            {

            totalFrames = 64;

            freeFrames = 64;

            frames = new String[totalFrames];

            }

   //---------------------------------------------------------------------------

   // method allocate

   // -allocates memory

   // -creates and returns a page table

   // -decrements the number of free frames

         public int[] allocate(PCB p, int nPages)

            {

            int[] pageTable = new int[nPages];

            for (int i=0; i<nPages; i++)

               for (int j=0; j<totalFrames; j++)

                  if (frames[j] == null)

                     {

                     pageTable[i] = j;

                     frames[j] = "PID "+p+" - Page "+i;

                     freeFrames--;

                     break;

                     }

            return pageTable;

            }

   //---------------------------------------------------------------------------

   // method more

   // -allocates additional memory

   // -uses the old page table to create the new one

         public int[] more(PCB p, int nPages)

            {

            int oldNPages = p.getPageTable().length;

            nPages += oldNPages;

            int[] pageTable = new int[nPages];

            for (int i=0; i<oldNPages; i++)

               pageTable[i] = p.getPageTable()[i];

            for (int i=oldNPages; i<nPages; i++)

               for (int j=0; j<totalFrames; j++)

                  if (frames[j] == null)

                     {

                     pageTable[i] = j;

                     frames[j] = "PID "+p+" - Page "+i;

                     freeFrames--;

                     break;

                     }

            return pageTable;

            }

   //---------------------------------------------------------------------------

   // method release

   // -releases memory

   // -uses the process' page table

         public int[] release(PCB p)

            {

            int nPages = p.getPageTable().length;

            for (int i=0; i<nPages; i++)

               {

               frames[p.getPageTable()[i]] = null;

               freeFrames++;

               }

            int[] pageTable = new int[0];

            return pageTable;

            }

   //---------------------------------------------------------------------------

   // method enoughFree

   // -returns true if there is enough free memory, false otherwise

         public boolean enoughFree(int nPages)

            {

            return ((freeFrames - nPages) > 0);

            }

   //---------------------------------------------------------------------------

   // method getFramesStr

   // -returns a string for printing

         public String getFramesStr()

            {

            String str = "";

            for (int i=0; i<totalFrames; i++)

               str += "|Frame "+i+": "+frames[i]+"| ";

            return str;

            }

   //---------------------------------------------------------------------------

   }  // end Memory



/******************************************************************************/

/******************************************************************************/



public class OS

   {

   //---------------------------------------------------------------------------

   // fields

         private boolean powerOn = true;

         private boolean invokedStandalone = false;

         private IODevice[] ioDevice;

         private int numberOfIODevices;

         private CPU theCPU;

         private Scheduler[] theScheduler;

         private int numberOfLevels = 3;

         private Interrupt event = new Interrupt();

         private Memory memory = new Memory();

         private InputStreamReader reader = new InputStreamReader(System.in);

         private BufferedReader stdin = new BufferedReader(reader);

         private Console console;

         private int clock = 0;  // system clock that counts "ticks" since boot

   //---------------------------------------------------------------------------

   // constructor

         public OS()

            {

            }

   //---------------------------------------------------------------------------

   // main method

   // -initializes the console for io

   // -initializes the system

   // -reads and processes interrupts

   // -shuts down the system

         public static void main(String[] args) throws IOException

            {                                                  // display banner

            System.out.println("\n\nAuthor: Julie Petrusa (991339)");

            System.out.println("Due date: March 22, 2002");

            System.out.print("Project description: Small Operating System ");

            System.out.println("Simulator");

            OS oS = new OS();

            oS.invokedStandalone = true;

            System.out.println("\n\nStarting System ...");

            oS.console = new Console();  // need to know where to print messages

            oS.initSystem();

            oS.console.println("\nSystem running ...");

            String input = "";

            do

               {

               System.out.print("Interrupt ID ");

               System.out.print("(1/16/32+/33+/34/35/40+/254/255): ");

               input = oS.console.readLine();

               oS.event.string2Interrupt(input);

               oS.handleInterrupt(oS.event);

               } while ((input != null) && oS.powerOn);

            oS.shutdownSystem();

            System.in.read();

            }

   //---------------------------------------------------------------------------

   // method initSystem

   // -does a Sysgen, creates queues, plus creates the initial process

   // -when the initial process is created, allocates 1 page of memory to it

   // -I/O Queue info is read from stdin, NOT the console

   // -returns void

         public void initSystem()

            {

            String input;

            System.out.println("\nInitializing System ...");

            System.out.print("Enter number of IO devices: ");

            try                                            // set up IO devices

               {

               input = stdin.readLine();

               numberOfIODevices = Integer.parseInt(input);

               }

            catch (IOException e)

               {

               }

            console.println("Setting up IO queues for devices 0 to "+

            new Integer(numberOfIODevices-1).toString());

            ioDevice = new IODevice[numberOfIODevices];

            for (int i=0; i<numberOfIODevices; i++)

               ioDevice[i] = new IODevice(i, console);

            theCPU = new CPU();  // create CPU and scheduler

            theScheduler = new Scheduler[numberOfLevels];

            for (int i=0; i<numberOfLevels; i++)

               theScheduler[i] = new Scheduler(i, theCPU, console);

            theCPU.runProcess(new PCB());  // create initial process and run it

            console.println("Initial process created and running.");

            PCB current = theCPU.currentProcess();

            current.setPageTable(memory.allocate(current, 1));

            }

   //---------------------------------------------------------------------------

   // method shutdownSystem

   // -prints a message that system is shutdown

   // -returns void

         public void shutdownSystem()

            {

            System.out.println("Time elapsed = "+clock+" ticks.");

            System.out.println("\nShutting down System ...");

            System.out.println("It is now safe to turn off the computer.");

            }

   //---------------------------------------------------------------------------

   // method handleInterrupt

   // -this is simply an interrupt vector

   // -returns void

         private void handleInterrupt(Interrupt event)

            {

            switch (event.value())

               {

               case 1: powerFailure();

                  break;

               case 16: timer();

                  break;

               case 32: requestIO();

                  break;

               case 33: finishIO();

                  break;

               case 34: createProcess();

                  break;

               case 35: terminateProcess();

                  break;

               case 40: requestPages();

                  break;

               case 254: shutDown();

                  break;

               case 255: displaySystem();

                  break;

               default: System.err.print("Bad interrupt number: ");

               }

            }

   //---------------------------------------------------------------------------

   // method powerFailure

   // -switches off power

         public void powerFailure()

            {

            console.println("Power Failure.");

            powerOn=false;

            }

   //---------------------------------------------------------------------------

   // method timer

   // -timer interrupt

   // -increments the length of the current CPU burst

   // -when a process' CPU burst exceeds 3 time units (3 timer interrupts), it

   //  moves to Q1

   // -when a process' CPU burst exceeds 9 time units it moves to Q2 (3 units

   //  in Q0, and 6 units in Q1)

   // -a context change occurs only if a process moves to a lower priority

   // -increments the clock

         private void timer()

            {

            console.println("Timer interrupt:");

            PCB current = theCPU.currentProcess();

            int temp = current.getPriority();

            current.incrementBurstTime();

            if (current.getBurstTime() > 3 && current.getPriority() == 0)

               current.setPriority(1);

            if (current.getBurstTime() > 9 && current.getPriority() == 1)

               current.setPriority(2);

            int priority = current.getPriority();

            if (priority != temp)

               {

               console.println("  Context change.");

               for (int i=0; i<priority+1; i++)

                  {

                  boolean done = theScheduler[i].dispatch();

                  if (done == true)

                     {

                     theScheduler[priority].addToReadyQueue(current);

                     break;

                     }

                  else

                     {

                     console.println("  Running process "+current+".");

                     }

                  }

               }

            clock++;

            }

   //---------------------------------------------------------------------------

   // method getDeviceNumber

   // -is used by requestIO and finishIO to read the device number from the

   //  interrupt arguments

         private int getDeviceNumber()

            {

            if (event.numberOfArguments() < 1)

               {

               System.err.println("Expecting a device number.");

               System.exit(-1);

               }

            int device = -1;

            try

               {

               device = Integer.parseInt(event.argument(1));

               }

            catch (NumberFormatException e)

               {

               System.err.println("Expecting a device number (integer).");

               System.exit(-1);

               }

            if ((device < 0) || (device > numberOfIODevices))

               {

               System.err.println("Bad device number.");

               System.exit(-1);

               }

            return device;

            }

   //---------------------------------------------------------------------------

   // method requestIO

   // -gets the device number

   // -passes the (not null) request to the ioDevice

   // -dispatches a new process to run

         private void requestIO()

            {

            console.println("IO request:");

            int device = getDeviceNumber();

            PCB runningProcess = theCPU.stopProcess();

            if (runningProcess != null)       // stop process that requested IO

               ioDevice[device].addToRequestQueue(runningProcess);

            else

               console.println("  No running process made this request!");

            for (int i=0; i<numberOfLevels; i++)  // dispatch a process to run

               {

               boolean done = theScheduler[i].dispatch();

               if (done == true)

                  break;

               }

            }

   //---------------------------------------------------------------------------

   // method finishIO

   // -termination of IO

   // -when a request for I/O is made, the CPU burst is over

   // -when the process returns to the ready queue, it will re-enter Q0 with

   //  its time reset to 0

         private void finishIO()

            {

            console.println("IO completion:");

            int device = getDeviceNumber();

            if (ioDevice[device].isIdle())

               {

               console.print("  No process was waiting for IO on device ");

               console.println(device+".");

               }

            else

               {

               PCB doneProcess = ioDevice[device].removeRequest();

               doneProcess.resetBurstTime();

               theScheduler[0].addToReadyQueue(doneProcess);

               PCB current = theCPU.currentProcess();

               if (current.getPriority() > 0)

                  {

                  console.println("  Context change.");

                  theScheduler[0].dispatch();

                  theScheduler[current.getPriority()].addToReadyQueue(current);

                  }

               }

            }

   //---------------------------------------------------------------------------

   // method abortIO

   // -same as finishIO except the request is forced by OS, and thus the

   //  device must be named

         private void abortIO(int device)

            {

            console.println("Aborting IO on device "+device+":");

            if (ioDevice[device].isIdle())

               {

               console.print("  No process was waiting for IO on device ");

               console.println(device+".");

               }

            else

               {

               PCB doneProcess = ioDevice[device].removeRequest();

               doneProcess.resetBurstTime();

               theScheduler[0].addToReadyQueue(doneProcess);

               }

            }

   //---------------------------------------------------------------------------

   // method getNPages

   // -is used by createProcess and requestPages to read the number of pages

   //  from the interrupt arguments

         private int getNPages()

            {

            if (event.numberOfArguments() < 1)

               {

               System.err.println("Expecting number of pages.");

               System.exit(-1);

               }

            int nPages = -1;

            try

               {

               nPages = Integer.parseInt(event.argument(1));

               }

            catch (NumberFormatException e)

               {

               System.err.println("Expecting a number (integer).");

               System.exit(-1);

               }

            if ((nPages < 0) || (nPages > 64))

               {

               System.err.println("Bad number of pages.");

               System.exit(-1);

               }

            return nPages;

            }

   //---------------------------------------------------------------------------

   // method createProcess

   // -creates a new PCB and gives it to the scheduler

   // -processes added to the ready queue always enter Q0

   // -the system is preemptive

   // -if a process of higher priority than the running process becomes ready,

   //  then the currently running process is preempted

   // -prints a message that the process was successfully created or that the

   //  creation failed

   // -in the case of successful creation, also prints the page table created

   //  for the process

   // -creation will succeed if there is enough free memory

         private void createProcess()

            {

            console.println("Create process:");

            int nPages = getNPages();

            if (memory.enoughFree(nPages))

               {

               PCB newProcess = new PCB();

               newProcess.setPageTable(memory.allocate(newProcess, nPages));

               console.println("  Creating process "+newProcess+".");

               console.println("  Page Table: "+newProcess.getPageTableStr());

               theScheduler[0].addToReadyQueue(newProcess);

               PCB current = theCPU.currentProcess();

               if (current.getPriority() > 0)

                  {

                  console.println("  Context change.");

                  theScheduler[0].dispatch();

                  theScheduler[current.getPriority()].addToReadyQueue(current);

                  }

               }

            else

               console.println("  Creation failed, not enough free memory.");

            }

   //---------------------------------------------------------------------------

   // method terminateProcess

   // -terminates process and schedules something new

   // -releases the process' memory

         private void terminateProcess()

            {

            PCB runningProcess = theCPU.stopProcess();

            if (runningProcess != null)

               {

               console.println("Terminating process "+runningProcess+":");

               runningProcess.setStateTerminated();

               runningProcess.setPageTable(memory.release(runningProcess));

               }

            for (int i=0; i<numberOfLevels; i++)

               {

               boolean done = theScheduler[i].dispatch();

               if (done == true)

                  break;

               }

            }

   //---------------------------------------------------------------------------

   // method requestPages

   // -a request from the currently running process for n more pages of memory

   // -if there are n free frames, allocates them and prints the new page table

   // -if not, prints a message that the request for memory failed

         private void requestPages()

            {

            PCB current = theCPU.currentProcess();

            int nPages = getNPages();

            console.println("Request for "+nPages+" more pages of memory:");

            if (current != null)

               {

               if (memory.enoughFree(nPages))

                  {

                  current.setPageTable(memory.more(current, nPages));

                  console.println("  Page Table: "+current.getPageTableStr());

                  }

               else

                  {

                  console.print("  Request for more memory failed, not enough");

                  console.println(" free memory.");

                  }

               }

            else

               console.println("  No running process made this request!");

            }

   //---------------------------------------------------------------------------

   // method shutDown

   // -aborts all IO requests

   // -terminates all the process in the ready queue

         private void shutDown()

            {

            this.powerOn = false;

            console.println("Please wait while all processes terminate.");

            for (int i=0; i<numberOfIODevices; i++)  // abort all IO

               while(!ioDevice[i].isIdle())

                  abortIO(i);

            while(!theCPU.isIdle())  // terminate all running, ready processes

               terminateProcess();

            console.println("System is halted.");

            }

   //---------------------------------------------------------------------------

   // method displaySystem

   // -displays running process, ready processes, io queues, and all processes

   // -displays the memory map, i.e. for each frame prints the owner pid and

   //  what page the frame is in the processes logical memory

         private void displaySystem()

            {

            Iterator iter;

            console.println("State of the system:");

            console.print("  Running Process: ");

            if (theCPU.currentProcess() != null)

               console.println(""+theCPU.currentProcess());

            else

               console.println("");

            for (int i=0; i<numberOfLevels; i++)

               {

               console.print("  Ready Queue - Priority Level "+i+": ");

               iter = theScheduler[i].iterator();

               while (iter.hasNext())

                  console.print((PCB)iter.next()+" ");

               console.println("");

               }

            for (int i=0; i<numberOfIODevices; i++)

               {

               console.print("  IO Device "+i+": ");

               iter = ioDevice[i].iterator();

               while (iter.hasNext())

                  console.print((PCB)iter.next()+" ");

               console.println("");

               }

            console.println("  Memory Map: "+memory.getFramesStr());

            iter = theCPU.currentProcess().iterator();

            PCB process = null;

            console.print("Process      State\t\tPriority\tBurst Time");

            console.println("\tPage Table");

            while (iter.hasNext())

               {

               process = (PCB)iter.next();

               console.print("   "+process+"         "+process.getState());

               console.print("\t\t"+process.getPriority());

               console.print("\t\t"+process.getBurstTime());

               console.println("\t\t"+process.getPageTableStr());

               }

            }

   //---------------------------------------------------------------------------

   }  // end OS



/******************************************************************************/

/******************************************************************************/



class PCB

   {

   //---------------------------------------------------------------------------

   // fields

         public final int PID;  // process ID number, initialized in constructor

         private static int nextFreePID = 0;  // used in constructor

         private int state = 0;

         private int priority = 0;

         private int burstTime = 0;

         private int[] pageTable;

         private static ArrayList allPCB = new ArrayList();

   //---------------------------------------------------------------------------

   // constructor

   // -assigns the PID to the process

   // -the nextFreePID variable is static

   // -it keeps (for all instances of PCB) the value of the next PID

         public PCB()

            {

            PID = nextFreePID++;

            allPCB.add(this);     // keep an array of all processes

            }

   //---------------------------------------------------------------------------

   // method setStateRunning

   // -sets the state to running

         public void setStateRunning()

            {

            state = 1;

            }

   //---------------------------------------------------------------------------

   // method setStateReady

   // -sets the state to ready

         public void setStateReady()

            {

            state = 2;

            }

   //---------------------------------------------------------------------------

   // method setStateWaiting

   // -sets the state to waiting

         public void setStateWaiting()

            {

            state = 3;

            }

   //---------------------------------------------------------------------------

   // method setStateTerminated

   // -sets the state to terminated

         public void setStateTerminated()

            {

            state = 4;

            }

   //---------------------------------------------------------------------------

   // method getState

   // -returns the state as a string

         public String getState()

            {

            switch (state)

               {

               case 0: return ("New");

               case 1: return ("Running");

               case 2: return ("Ready");

               case 3: return ("Waiting");

               case 4: return ("Terminated");

               }

            return ("");  // default

            }

   //---------------------------------------------------------------------------

   // method setPriority

   // -sets the priority

   // -highest priority is 0, lowest priority is 2

         public void setPriority(int level)

            {

            priority = level;

            }

   //---------------------------------------------------------------------------

   // method getPriority

   // -returns the priority

         public int getPriority()

            {

            return priority;

            }

   //---------------------------------------------------------------------------

   // method incrementBurstTime

   // -increments the burst time

         public void incrementBurstTime()

            {

            burstTime++;

            }

   //---------------------------------------------------------------------------

   // method resetBurstTime

   // -resets the burst time to 0

         public void resetBurstTime()

            {

            burstTime = 0;

            }

   //---------------------------------------------------------------------------

   // method getBurstTime

   // -returns the burst time

         public int getBurstTime()

            {

            return burstTime;

            }

   //---------------------------------------------------------------------------

   // method setPageTable

   // -sets the page table

         public void setPageTable(int[] pt)

            {

            int nPages = pt.length;

            pageTable = new int[nPages];

            for (int i=0; i<nPages; i++)

               pageTable[i] = pt[i];

            }

   //---------------------------------------------------------------------------

   // method getPageTable

   // -returns the page table

         public int[] getPageTable()

            {

            return pageTable;

            }

   //---------------------------------------------------------------------------

   // method getPageTableStr

   // -returns the page table as a string

         public String getPageTableStr()

            {

            String ptStr = "";

            for (int i=0; i<pageTable.length; i++)

               ptStr += "|Page "+i+": "+pageTable[i]+"| ";

            return ptStr;

            }

   //---------------------------------------------------------------------------

   // method toString

   // -allows easy printing

         public String toString()

            {

            return new Integer(PID).toString();

            }

   //---------------------------------------------------------------------------

   // method iterator

   // -returns an iterator

         public Iterator iterator()

            {

            return allPCB.iterator();

            }

   //---------------------------------------------------------------------------

   }  // end PCB



/******************************************************************************/

/******************************************************************************/



class Queue

   {

   //---------------------------------------------------------------------------

   // fields

         private LinkedList list = new LinkedList();

   //---------------------------------------------------------------------------

   // method put

         public void put(Object v)

            {

            list.addLast(v);

            }

   //---------------------------------------------------------------------------

   // method get

         public Object get()

            {

            return list.removeFirst();

            }

   //---------------------------------------------------------------------------

   // method front

         public Object front()

            {

            return list.getFirst();

            }

   //---------------------------------------------------------------------------

   // method isEmpty

         public boolean isEmpty()

            {

            return list.isEmpty();

            }

   //---------------------------------------------------------------------------

   // method iterator

         public Iterator iterator()

            {

            return list.iterator();

            }

   //---------------------------------------------------------------------------

   }  // end Queue



/******************************************************************************/

/******************************************************************************/



class Scheduler

   {

   //---------------------------------------------------------------------------

   // fields

         private CPU myCPU;

         private Console console;

         private Queue readyQueue = new Queue();

         private int whoAmI;

   //---------------------------------------------------------------------------

   // constructor

   // -creates a ready queue with priority priorityLevel

   // -needs to receive a CPU and a console

   // -schedules the CPU and prints to the console

         public Scheduler(int priorityLevel, CPU processor, Console con)

            {

            whoAmI = priorityLevel;

            myCPU = processor;

            console = con;

            }

   //---------------------------------------------------------------------------

   // method addToReadyQueue

   // -puts process p in the ready queue and makes its state ready

   // -if the CPU is idle (and job is not null), then p is dispatched

   // -prints status messages

         public void addToReadyQueue(PCB p)

            {

            if (p == null)

               {

               return;  // do not add null process

               }

            if (myCPU.isIdle())

               {

               console.println("  Running process "+p+".");

               p.setPriority(whoAmI);

               myCPU.runProcess(p);

               }

            else

               {

               console.print("  Add process "+p+" to ready queue at priority ");

               console.println("level "+whoAmI+".");

               p.setStateReady();

               p.setPriority(whoAmI);

               readyQueue.put(p);

               }

            }

   //---------------------------------------------------------------------------

   // method dispatch

   // -makes the first ready process the running process

   // -prints a status message

   // -assumes CPU is idle before method is called

   // -returns true if a process was dispatched, false otherwise

         public boolean dispatch()

            {

            if (!readyQueue.isEmpty())

               {

               myCPU.runProcess((PCB)readyQueue.get());

               console.println("  Running process "+myCPU.currentProcess()+".");

               return true;

               }

            else

               {

               console.print("  No process is ready at priority level "+whoAmI);

               console.println(". CPU remains idle.");

               return false;

               }

            }

   //---------------------------------------------------------------------------

   // method iterator

   // -returns an iterator for the ready queue

         public Iterator iterator()

            {

            return readyQueue.iterator();

            }

   //---------------------------------------------------------------------------

   }  // end Scheduler



/******************************************************************************/

/******************************************************************************/