Prof Cox CISC 3320 Homework 3

CPU Scheduling Simulation Due: November 15

This assignment addresses the implementation of CPU-scheduling algorithms in an operating system.

Each process in an operating system is managed by using a data structure called the Process Control Block (PCB). A PCB contains the process ID, arrival timestamp, total burst time, execution start time, execution end time, remaining burst time and the priority of the process in the system. The PCB class is defined as follows and is accessible from the rest of the code in this project:

public class PCB {

public int processID;

public long arrivalTimeStamp;

public long totalBurstTime;

public long executionStartTime;

public long executionEndTime;

public long remainingBurstTime;

public int processPriority;

}

The set of processes in the operating system that are ready to execute are maintained in a data structure called the Ready Queue. This data structure is a List of PCBs of the processes that are waiting for the CPU to become available so that they can execute.

To determine the schedule of execution for the processes in an operating system, we consider three policies:

1. Priority-based Preemptive Scheduling (PP)

2. Shortest-Remaining-Time-Next Preemptive Scheduling (SRTP)

3. Round-Robin Scheduling (RR)

In order to implement the above policies, we need to develop methods that handle arrival of processes for execution and the completion of process execution. Whenever a process arrives for execution, it can either join the ready queue and wait for its chance to execute or execute immediately (if there is no other process currently executing or if the currently-running process can be preempted). Whenever a process completes execution, another process from the ready queue is chosen to execute next, based on the scheduling policy. The details of these methods are described below in the specification and you need to develop code for these methods that follows the specification.

I recommend using an event queue of process arrivals ordered by arrival time (read from a file.) The next event is the currently running process end time or the next arrival, whichever is earlier. The current time is set to that event.

handleProcessArrival_PP:

This method implements the logic to handle the arrival of a new process in a Priority-based Preemptive Scheduler. Specifically, it takes four inputs: 1) the ready queue (a List of PCB objects), 2) the PCB of the currently running process, 3) the PCB of the newly arriving process, and 4) the current timestamp. The method determines the process to execute next and returns its PCB.

If there is no currently-running process (i.e., the second argument is NULL), then the method returns the PCB of the newly-arriving process, indicating that it is the process to execute next. In this case, the PCB of the new process is modified so that the execution start time is set to the current timestamp, the execution end time is set to the sum of the current timestamp and the total burst time and the remaining burst time is set to the total burst time.

If there is a currently-running process, the method compares the priority of the newly-arriving process with the currently-running process. If the new process has lower priority (smaller integers for the priority field in the PCB indicate higher priority), then its PCB is simply added to the ready queue and the return value is the PCB of the currently-running process. As the newly-arriving process is added to the ready queue, its execution start time and execution end time are set to 0, and the remaining burst time is the same as its total burst time.

If the new process has higher priority, then the PCB of the currently-running process is added to the ready queue and the return value is the PCB of the new process. In this case, the PCB of the new process is modified so that the execution start time is set to the current timestamp, the execution end time is set to the sum of the current timestamp and the total burst time and the remaining burst time is set to the total burst time. Also, the PCB of the currently-running process is added to the ready queue after marking its execution start time and execution end time as 0, and adjusting its remaining burst time.

handleProcessCompletion_PP:

This method implements the logic to handle the completion of execution of a process in a Priority-based Preemptive Scheduler. Specifically, it takes two inputs: 1) the ready queue (a List of PCB objects) and 2) the current timestamp. The method determines the process to execute next and returns its PCB.

If the ready queue is empty, the method returns null, indicating that there is no process to execute. Otherwise, the method finds the PCB of the process in the ready queue with the highest priority (smaller integers for the priority field in the PCB mean higher priorities), removes this PCB from the ready queue and returns it. Before returning the PCB of the next process to execute, it is modified to set the execution start time as the current timestamp and the execution end time as the sum of the current timestamp and the remaining burst time.

handleProcessArrival_SRTP:

This method implements the logic to handle the arrival of a new process in a Shortest-Remaining-Time-Next Preemptive Scheduler. Specifically, it takes four inputs: 1) the ready queue (a List of PCB objects), 2) the PCB of the currently-running process, 3) the PCB of the newly-arriving process, and 4) the current timestamp. The method determines the process to execute next and returns its PCB.

If there is no currently-running process (i.e., the second argument is NULL), then the method returns the PCB of the newly-arriving process, indicating that it is the process to execute next. In this case, the PCB of the new process is modified so that the execution start time set to the current timestamp, the execution end time is set to the sum of the current timestamp and the total burst time and the remaining burst time is set to the total burst time.

If there is a currently-running process, the method compares the remaining burst time of the currently-running process and the total burst time of the newly-arriving process. If the new process does not have a shorter burst time, then its PCB is simply added to the ready queue and the return value is the PCB of the currently running process. As the newly-arriving process is added to the ready queue, its execution start time and execution end time are set to 0, and the remaining burst time is set to the total burst time.

If the new process has a shorter burst time, then the PCB of the currently-running process is added to the ready queue and the return value is the PCB of the new process. In this case, the PCB of the new process is modified so that the execution start time is set to the current timestamp, the execution end time is set to the sum of the current timestamp and the total burst time and the remaining burst time is set to the total burst time. Also, the PCB of the currently-running process is added to the ready queue, after marking its execution start time and execution end time as 0, and adjusting its remaining burst time.

handleProcessCompletion_SRTP:

This method implements the logic to handle the completion of execution of a process in a Shortest-Remaining-Time Preemptive Scheduler. Specifically, it takes two inputs: 1) the ready queue (a List of PCB objects) and 2) the current timestamp. The method determines the process to execute next and returns its PCB.

If the ready queue is empty, the method returns null, indicating that there is no process to execute next. Otherwise, the method finds the PCB of the process in the ready queue with the smallest remaining burst time, removes this PCB from the ready queue and returns it. Before returning the PCB of the next process to execute, it is modified to set the execution start time as the current timestamp and the execution end time as the sum of the current timestamp and the remaining burst time.

handleProcessArrival_RR:

This method implements the logic to handle the arrival of a new process in a Round-Robin Scheduler. Specifically, it takes five inputs: 1) the ready queue (a List of PCB objects), 2) the PCB of the currently-running process, 3) the PCB of the newly-arriving process , 4) the current timestamp, and 5) the time quantum. The method determines the process to execute next and returns its PCB.

If there is no currently-running process (i.e., the second argument is null), then the method returns the PCB of the newly-arriving process, indicating that it is the process to execute next. In this case, the PCB of the new process is modified so that the execution start time is set to the current timestamp, the execution end time is set to the sum of the current timestamp and the smaller of the time quantum and the total burst time. The remaining burst time is set to the total burst time.

If there is a currently-running process, the method simply adds the PCB of the newly-arriving process to the ready queue and the return value is the PCB of the currently running process. As the newly-arriving process is added to the ready queue, its execution start time and execution end time are set to 0, and the remaining burst time is set to the total burst time.

handleProcessCompletion_RR:

This method implements the logic to handle the completion of execution of a process in a Round-Robin Scheduler. Specifically, it takes three inputs: 1) the ready queue (a list of PCB objects), 2) the current timestamp, and 3) the time quantum. The method determines the process to execute next and returns its PCB.

If the ready queue is empty, the method returns null, indicating that there is no process to execute next. Otherwise, the method finds the PCB of the process in the ready queue with the earliest arrival time, removes this PCB from the ready queue and returns it. Before returning this PCB, it is modified to set the execution start time as the current timestamp and the execution end time as the sum of the current timestamp and the smaller of the time quantum and the remaining burst time.

handleEndOfTimeQuantum_RR:

This method implements the logic to handle the completion of a time quantum in a Round-Robin Scheduler. Specifically, it takes four inputs: 1) the ready queue (a list of PCB objects), 2) the PCB of the currently running process, 3) the current timestamp, and 4) the time quantum. The method determines the process to execute next and returns its PCB.

If there is a currently-running process (i.e., the second argument is not null), its PCB is added to the ready queue. Its execution start time and execution end time are set to 0 and its remaining burst time is reduced by the time quantum. The arrival time of its PCB is set to the current timestamp, as if the process is just entering the ready queue now for the first time. The method then finds the PCB of the process in the ready queue with the earliest arrival time, removes this PCB from the ready queue and returns it. Before returning this PCB, it is modified to set the execution start time as the current timestamp and the execution end time as the sum of the current timestamp and the smaller of the time quantum and the remaining burst time.