Question

Description In this homework, you are asked to implement a multithreaded program that will allow us to measure the performance (i.e, CPU utilization, Throughput, Turnaround time, and Waiting time in Ready Queue) of the four basic CPU scheduling algorithms (namely, FIFO, SJE PR, and RR). Your program will be emulating/simulating the processes whose priority, sequence of CPU burst time(ms) and I'O burst time(ms) will be given in an input file. Assume that all scheduling algorithms except RR will be non-preemptive, and all scheduling algorithms except PR will ignore process priorities i.e., all processes have the same priority in FIFO, SJF and RR). Also assume that there is only one IO device and all IO requests will be served using that device in a FIFO manner Your program will take the name of the scheduling algorithm, related parameters (if any), and an input file name from command line. Here how your program should be executed: prog-alg [F1 FOI SJFİ PRIRR] [-quantum [integer (ms)11 -input [file name] The output of your program will be as follows: Input File Name CPU Scheduling Alg CPU utilization Throughput Avg. Turnaround time Avg. Waiting time in R queue : file name FIFOISUFI PRIRR (quantum) The input file is formatted such that each line starts with proc, sleep, stop keywords. Following proc, there will be a sequence of integer numbers: the first one represents the priority (1: lowest, 5: normal, ., 10: highest). The second number shows the number of remaning integers representing CPU burst and L/O burst times (ms) in an alternating manner. The last number will be the last CPU burst time after which that process exits. Following sleep, there will be an integer number representing the time (ms) after which there will be another process. So one of the threads in your program (e.g., FileRead thread0) would be responsible for processing this file as follows. As long as it reads proc, it will create a new process and put it in a ready queue (clearly this process is not an actual one, it will be just a simple data structure (similar to PCB) that contains the given priority and the sequence of CPU burst and LO burst times, and other fields when this thread reads sleep x, it will sleep x ms and then try to read new processes from the e Upon reading stop hist read w quit. …………-…-…-…-…-………-…-…-… Here is a sample input file (copy/paste this to create an inputl.txt you can create other similar files too): Here is a sample input file (copy/paste this to create an input1.txt you can create other similar files too): proc 1 7 10 20 10 50 20 40 10 proc 5 50 10 30 20 40 sleep 50 proc 2 3 20 50 20 stop In this program you need at least three threads: As described above, one thread (say FileRead thread) will read the above file, create a process (not a real process just a data structure representing the characteristic of the process that will be emulated/simulated), and puts it in a ready queue CPU scheduler thread will check ready queue; if there is a process, it will pick one according to the scheduling algorithm from ready queue and hold CPU resource for the given CPU burst time (or for quantum time if the scheduling algorithm is RR). That means CPU thread will simply sleep for the given CPU burst time to emulate/simulate the process. Then it will release CPU resource and put this process into IO queue (or ready queue if RR is used) or just terminate if this is the last CPU burst. Then CPU scheduler thread will check ready queue again and repeat the same for the next process. IO system thread will check IO queue; if there is a process, it will sleep for the given IO burst time to emulate/simulate the usage of IO device. It then puts this process back into ready queue. Finally it will check k IO queue and repeat the same Basically you will have at least the above mentioned three threads and the main one. These threads need to be synchronized as they cooperate to collect data for performance measures and share data through ready and IO queues. Main thread will wait until the file reading thread is done and the ready queue and IO queue are empty, then it will print the performance evaluation results and terminate the program... You are free to design and implement this program in C ++ or Java but if you use Java, DO NOT use the·synchronized◆ methods or high-level thread-safe Java classes. Instead use some form of semaphore or basic synchronization mechanisms in Java. Also synchronized (obj) structure is OK to use for protecting critical sections in your methods). Also you can use any data structures in different parts of your program and share them along with new variables; but when it comes to maintaining the list of processes in ready queue or IO queue, we would like you to use double linked list, as this is the case in many practical OS If you still need extra help, click here

Answer 1

Simulator.java

import java.util.LinkedList;
import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Simulator {

   private FileReader readerThread;
   private CPU cpuThread;
   private IO ioThread;
   private String fileName;
   private Algorithm algorithm;

   /*
   * Process queues and lists
   */
   public volatile LinkedList<Process> readyQueue = new LinkedList<>();
   public volatile LinkedList<Process> ioQueue = new LinkedList<>();
   public volatile LinkedList<Process> doneList = new LinkedList<>();

   /*
   * Synchronization info
   */
   public volatile int totalProcesses = 0;
   public volatile int finishedProcesses = 0;
   // public final Lock statLock = new ReentrantLock();
   // public final Lock readyLock = new ReentrantLock();
   // public final Lock ioLock = new ReentrantLock();
   public final Lock lock = new ReentrantLock(true);
   public final Semaphore doneFlag = new Semaphore(0);

   /*
   * Process statistics
   */

   public Simulator(String fileName, Algorithm algorithm, int quantum) {
      
       if (quantum <= 0 && algorithm == Algorithm.RR) {
           System.err.println("Invalid quantum specified for RR");
           System.exit(-1);
       }
      
       this.fileName = fileName;
       this.algorithm = algorithm;
       readerThread = new FileReader(this, fileName);
       cpuThread = new CPU(this, algorithm, quantum);
       ioThread = new IO(this);

   }

   public void startSimulation() {

       //System.err.println("Beginning sim...");

       cpuThread.start();
       ioThread.start();
       readerThread.start();

       //System.err.println("Threads started");

       try {
           doneFlag.acquire(3);
       } catch (InterruptedException e) {
           e.printStackTrace();
       }

       //System.err.println("All threads done");

       //System.err.println("Simulation complete");

       long totalCPUTime = 0;
       long totalWaitingTime = 0;
       long totalIOTime = 0;
       long totalTime = 0;

       // All threads have completed execution
       for (Process p : doneList) {
           totalCPUTime += p.cpuTime;
           totalWaitingTime += p.waitingTime;
           totalIOTime += p.ioTime;
           totalTime += p.turnaroundTime;
           //System.out.println(p);
       }

       double averageTurnaround = (double) totalTime / doneList.size();
       double throughputPerSecond = 1000 / averageTurnaround;
       double avgWait = (double) totalWaitingTime / doneList.size();

       System.out.printf("Input File Name     : %s\n", fileName);
       System.out.printf("CPU Scheduling Alg : %s\n", algorithm);
       System.out.printf("CPU utilization     : %.2f%%\n", ((double) totalCPUTime / totalTime) * 100);
       System.out.printf("Throughput          : %.2f processes per second\n", throughputPerSecond);
       System.out.printf("Turnaround time     : %.2f ms (average) %d ms (total)\n", averageTurnaround, totalTime);
       System.out.printf("Waiting time        : %.2f ms (average) %d ms (total)\n", avgWait, totalWaitingTime);

   }

}

Algorithm.java

public enum Algorithm {
  
   FIFO,
   SJF,
   PR,
   RR

}

CPU.java

public class CPU extends Thread {

   Simulator sim;
   Algorithm algorithm;
   int quantum;

   /**
   *
   * @param algorithm
   * @param quantum
   */
   public CPU(Simulator sim, Algorithm algorithm, int quantum) {
       this.sim = sim;
       this.algorithm = algorithm;
       this.quantum = quantum;
   }

   @Override
   public void run() {

       Process process;

       while (sim.readyQueue.isEmpty()) {
           try {
               Thread.sleep(1);
           } catch (InterruptedException e) {
               // TODO Auto-generated catch block
               e.printStackTrace();
           }
       }

       for (;;) {

           if (!sim.readyQueue.isEmpty()) {

               switch (algorithm) {
               case FIFO:
                   /**
                   * Pick the first process
                   */

                   synchronized (sim.readyQueue) {
                       process = sim.readyQueue.removeFirst();
                   }
                   //System.out.println("choose process " + process.processID + " to run");

                   try {
                       Thread.sleep(process.burst());
                   } catch (InterruptedException e) {
                       e.printStackTrace();
                   }

                   process.turnaroundTime += process.burst();
                   process.cpuTime += process.burst();

                   // The time that this process used should be added to the
                   // waiting time of any other processes in the readyQueue
                   synchronized (sim.readyQueue) {

                       for (Process p : sim.readyQueue) {
                           p.waitingTime += process.burst();
                           p.turnaroundTime += process.burst();
                       }

                       //System.out.println("process " + process.processID + " cpu bursted for " + process.burst());

                   }

                   // Prepare process for next io burst
                   process.nextBurst();

                   if (process.done) {
                       sim.finishedProcesses++;
                       synchronized (sim.doneList) {
                           //System.out.println("process " + process.processID + " done!");
                           sim.doneList.add(process);
                       }
                   } else {
                       synchronized (sim.ioQueue) {
                           sim.ioQueue.add(process);
                           //System.out.println("sent process " + process.processID + " to ioqueue");
                       }
                   }

                   break;
               case SJF:
                   /**
                   * Pick the shortest burst time first
                   */

                   synchronized (sim.readyQueue) {

                       process = sim.readyQueue.peekFirst();

                       for (Process p : sim.readyQueue) {
                           if (p.burst() < process.burst()) {
                               process = p;
                           }
                       }

                       sim.readyQueue.remove(process);

                   }

                   try {
                       Thread.sleep(process.burst());
                   } catch (InterruptedException e) {
                       e.printStackTrace();
                   }
                  
                   process.turnaroundTime += process.burst();
                   process.cpuTime += process.burst();
                  
                   // The time that this process used should be added to the
                   // waiting time of any other processes in the readyQueue
                   synchronized (sim.readyQueue) {

                       for (Process p : sim.readyQueue) {
                           p.waitingTime += process.burst();
                           p.turnaroundTime += process.burst();
                       }

                       //System.out.println("process " + process.processID + " cpu bursted for " + process.burst());

                   }

                   process.nextBurst();

                   if (process.done) {
                       // process.turnaroundTime = System.currentTimeMillis() -
                       // process.startTimestamp;
                       sim.finishedProcesses++;
                       synchronized (sim.doneList) {
                           sim.doneList.add(process);
                       }
                   } else {
                       synchronized (sim.ioQueue) {
                           sim.ioQueue.add(process);
                       }
                   }

                   break;
               case PR:
                   /**
                   * Choose highest priority process
                   */
                   synchronized (sim.readyQueue) {

                       process = sim.readyQueue.peekFirst();

                       for (Process p : sim.readyQueue) {
                           if (p.priority < process.priority) {
                               process = p;
                           }
                       }

                       sim.readyQueue.remove(process);

                   }

                   try {
                       Thread.sleep(process.burst());
                   } catch (InterruptedException e) {
                       e.printStackTrace();
                   }
                  
                   process.turnaroundTime += process.burst();
                   process.cpuTime += process.burst();
                  
                   // The time that this process used should be added to the
                   // waiting time of any other processes in the readyQueue
                   synchronized (sim.readyQueue) {

                       for (Process p : sim.readyQueue) {
                           p.waitingTime += process.burst();
                           p.turnaroundTime += process.burst();
                       }

                       //System.out.println("process " + process.processID + " cpu bursted for " + process.burst());

                   }

                   process.nextBurst();

                   if (process.done) {
                       // process.turnaroundTime = System.currentTimeMillis() -
                       // process.startTimestamp;
                       sim.finishedProcesses++;
                       synchronized (sim.doneList) {
                           sim.doneList.add(process);
                       }
                   } else {
                       synchronized (sim.ioQueue) {
                           sim.ioQueue.add(process);
                       }
                   }
                  
                   break;
               case RR:
                   /**
                   * First-come-first-serve, however each burst is limited to
                   * min(quantum, p.burst()). If there is still burst left, we
                   * keep the process here and add it back to the end of the
                   * ready queue
                   */
                  
                   synchronized (sim.readyQueue) {
                       process = sim.readyQueue.removeFirst();
                   }
                  
                   int burst = Math.min(quantum, process.burst());

                   try {
                       Thread.sleep(burst);
                   } catch (InterruptedException e) {
                       e.printStackTrace();
                   }
                  
                   process.turnaroundTime += burst;
                   process.cpuTime += burst;
                  
                   // The time that this process used should be added to the
                   // waiting time of any other processes in the readyQueue
                   synchronized (sim.readyQueue) {

                       for (Process p : sim.readyQueue) {
                           p.waitingTime += burst;
                           p.turnaroundTime += burst;
                       }

                       //System.out.println("process " + process.processID + " cpu bursted for " + process.burst());

                   }

                   process.bursts[process.burstIndex] -= burst;
                  
                   if (process.burst() < 0) {
                       System.err.println("Internal error: below 0 burst time");
                       System.exit(-1);
                   } else if (process.burst() == 0) {          
                       // CPU burst is done, send process to ioQueue
                      
                       process.nextBurst();
                      
                       if (process.done) {
                           // process.turnaroundTime = System.currentTimeMillis() -
                           // process.startTimestamp;
                           sim.finishedProcesses++;
                           synchronized (sim.doneList) {
                               sim.doneList.add(process);
                           }
                       } else {
                           synchronized (sim.ioQueue) {
                               sim.ioQueue.add(process);
                           }
                       }
                      
                   } else {
                       // CPU burst isn't done, put this process at the end of the queue
                      
                       synchronized (sim.readyQueue) {
                           sim.readyQueue.add(process);
                       }
                      
                   }      
                  
                   break;
               }

           }

           if (sim.finishedProcesses == sim.totalProcesses) {
               break;
           }

       }

       sim.doneFlag.release();

   }

}

CPUScheduler.java

import java.io.IOException;

public class CPUScheduler {
  
   public static void main(String[] args) throws IOException {
      
       /*
       * Possible command line flags:
       *
       * required: -alg [FIFO|SJF|PR|RR] (2)
       * required: -input [file name] (2)
       * optional: -quantum [int milliseconds] (2)
       *
       * We could do some more robust command line argument parsing here
       * but that's not the point of this assignment...
       */
      
       if (args.length < 4 || args.length > 6) {
           usageExit("Invalid arguments");
       }
      
       String algorithmStr = null;
       Algorithm algorithm;
       String fileName = null;
       int quantum = -1;
      
       for (int i = 0; i < args.length; i++) {
           switch (args[i]) {
           case "-alg":
               if (i + 1 == args.length) {
                   usageExit("No algorithm specified. Options: [FIFO|SJF|PR|RR]");
               }
               algorithmStr = args[i + 1];
               i++;
               break;
           case "-input":
               if (i + 1 == args.length) {
                   usageExit("No input file name specified");
               }
               fileName = args[i + 1];
               i++;
               break;
           case "-quantum":
               if (i + 1 == args.length) {
                   usageExit("No quantum time specified");
               }
               try {
                   quantum = Integer.parseInt(args[i + 1]);
               } catch (NumberFormatException e) {
                   usageExit("Quantum must be an integer in milliseconds");
               }
               i++;
               break;
           default:
               usageExit("Invalid arguments");
           }
       }
      
       if (algorithmStr == null) {
           usageExit("Algorithm flag is required");
       }
      
       algorithm = Algorithm.valueOf(algorithmStr);
      
       if (fileName == null) {
           usageExit("Input flag is required");
       }
      
       Simulator simulator = new Simulator(fileName, algorithm, quantum);
       simulator.startSimulation();
      
   }
  
   public static void usageExit(String message) {
       System.err.println(message);
       System.err.println("Usage: java CPUScheduler -alg [FIFO|SJF|PR|RR] [-quantum [integer(ms)]] -input [file name]");
       System.exit(-1);
   }

}

FileReader.java

import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.util.LinkedList;

public class FileReader extends Thread {

   File inputFile;
   Simulator sim;

   /**
   * Constructs a new FileReader to read input from the given file
   */
   public FileReader(Simulator sim, String fileName) {
       this.sim = sim;
       this.inputFile = new File(fileName);
   }

   @Override
   public void run() {

       /*
       * Input file format:
       *
       * proc <priority> <<cpu burst> <io burst>> ... (repeated) <cpu burst>
       * sleep <milliseconds> stop
       *
       */
       try {
           Files.lines(inputFile.toPath()).forEachOrdered(line -> {

               line = line.trim();

               if (!line.isEmpty()) {

                   // System.out.println(line);

                   String[] parse = line.split("\\s+");

                   switch (parse[0]) {
                   case "proc":

                       synchronized (sim.readyQueue) {

                           //System.out.println("added process " + sim.totalProcesses + " to readyqueue");
                           sim.readyQueue.add(new Process(sim.totalProcesses, line));
                           sim.totalProcesses++;

                       }

                       break;
                   case "sleep":

                       int time = Integer.parseInt(parse[1]);
                       try {
                           Thread.sleep(time);
                       } catch (InterruptedException e) {
                           System.err.println("Interrupted file reader thread while sleeping!");
                           e.printStackTrace();
                       }

                       break;
                   case "stop":
                       sim.doneFlag.release();
                       return; // stop thread by returning from run
                   default:
                       System.err.println("Unknown command in input file");
                       System.exit(-1);
                   }

               }

           });
       } catch (IOException e) {
           // TODO Auto-generated catch block
           e.printStackTrace();
       }

       sim.doneFlag.release();

   }

}

IO.java

public class IO extends Thread {

   Simulator sim;

   /**
   */
   public IO(Simulator sim) {
       this.sim = sim;
   }

   @Override
   public void run() {

       Process process;

       while (sim.ioQueue.isEmpty()) {
           try {
               Thread.sleep(1);
           } catch (InterruptedException e) {
               // TODO Auto-generated catch block
               e.printStackTrace();
           }
       }

       for (;;) {

           if (!sim.ioQueue.isEmpty()) {

               synchronized (sim.ioQueue) {

                   process = sim.ioQueue.removeFirst();
                   //System.out.println("choose process " + process.processID + " for io");

               }

               try {
                   Thread.sleep(process.burst());
               } catch (InterruptedException e) {
                   // TODO Auto-generated catch block
                   e.printStackTrace();
               }

               process.turnaroundTime += process.burst();
               process.ioTime += process.burst();

               // The time that this process used should be added to the
               // waiting time of any other processes in the ioQueue
               synchronized (sim.ioQueue) {

                   for (Process p : sim.ioQueue) {
                       p.waitingTime += process.burst();
                       p.turnaroundTime += process.burst();
                   }

               }

               //System.out.println("process " + process.processID + " io bursted for " + process.burst());

               process.nextBurst();

               synchronized (sim.readyQueue) {
                   sim.readyQueue.add(process);
               }
              
               //System.out.println("sent process " + process.processID + " to readyqueue");

           }

           if (sim.finishedProcesses == sim.totalProcesses) {
               break;
           }

       }

       sim.doneFlag.release();

   }

}

Process.java

public class Process {

   public int processID;

   /**
   * Priority of this process, where 1 is the lowest priority and 10 is the
   * highest priority.
   */
   public volatile int priority;

   /**
   * Alternating CPU and IO burst numbers, always with an odd length and
   * ending with a final CPU burst.
   */
   public volatile int[] bursts;

   /**
   * Internal index representing which burst should be processed next.
   */
   public volatile int burstIndex = 0;

   /**
   * True if this process has completed all bursts.
   */
   public volatile boolean done = false;

   public final long startTimestamp = System.currentTimeMillis();

   public volatile long turnaroundTime = 0;
   public volatile long cpuTime = 0;
   public volatile long ioTime = 0;
   public volatile long waitingTime = 0;

   /**
   * Constructs a new Process from a "proc ..." command representing a virtual
   * process for simulation by the CPU and IO threads.<br>
   * <br>
   *
   * A proc command has the following format:<br>
   *
   * proc [priority] [[cpu burst] [io burst]] ... (repeated) [cpu burst]
   *
   * @param creationString
   *            A "proc ..." command to build this process
   */
   public Process(int processID, String creationString) {

       this.processID = processID;

       String[] split = creationString.split("\\s+");

       int finalBurst = Integer.parseInt(split[split.length - 1]);
       priority = Integer.parseInt(split[1]);

       bursts = new int[split.length - 2];

       int i;
       for (i = 2; i < split.length - 1; i++) {
           bursts[i - 2] = Integer.parseInt(split[i]);
       }

       bursts[i - 2] = finalBurst;

   }

   public int burst() {
       return this.bursts[burstIndex];
   }

   public void nextBurst() {
       this.burstIndex++;
       if (burstIndex >= bursts.length) {
           this.done = true;
       }
   }

   @Override
   public String toString() {

       return String.format("[id: %d, cpu: %d, io: %d, waiting: %d, turnaround: %d]", this.processID, this.cpuTime,
               this.ioTime, this.waitingTime, this.turnaroundTime);

   }

}