We try to achieve optimum parameters by using a combination of existing scheduling algorithms. The main criteria for judging CPU scheduling algorithms are:
- CPU Utilisation: CPU should be used all times to get good results, i.e, CPU utilisation should be high.
- Throughput: The number of processes that are executed completely per unit time should be high.
- Waiting Time: The time for which a process waits for execution should be low.
- Turnaround Time: The time taken by the CPU to completely execute a process should be low.
- Response Time: The total amount of time CPU takes to respond to a request should be low.
In this scheduling algorithm, the processes are executed in the increasing order of their burst time. However, it may face a problem when there are processes with large burst time in the ready queue, as such process may not get executed leading to “Starvation.” This algorithm gives the most optimized values in all parameters like waiting, turnaround, and context switching.
This scheduling assigns every process with a priority number. CPU then executes the processes in decreasing order of priority regardless of their burst time. This type of scheduling may also lead to starvation.
In this algorithm,a time quantum is set which permits the process to utilize the CPU to its full extent, thereby giving equal importance to all the elements in the ready queue. Starvation is eliminated in this manner. The waiting times, context switching and turnaround times are not optimised but the throughput of the system is increased and the response time decreases.
The proposed model works by combining aspects of three existing algorithms (SJF, Round Robin, Priority) into one. In addition to this, to overcome the problem of choosing an appropriate quantum time that is not too long or too short for the given processes, we dynamically calculate the quantum time at every second. We also evaluate whether the remaining CPU burst time of a process is less than the quantum time and if so, continue to let it run in the CPU. This is done to minimise the context switching. The algorithm is detailed below and the proposed workflow is on the next page.
- Input the number of processes.
- Input the Process ID, Arrival Time, CPU Burst,I/O Burst and Priority for each process.
- Initialise timer to zero.
- Check if any processes arrive in the Ready Queue (Ready State) and sort them in ascending order of their CPU Burst Time (note that this is an implementation of the Shortest Job First Algorithm).
- Calculate the mean of the burst times of the pro-cesses in the ready queue and equate the Quantum Time(QT) to this value.
- Sort the processes in the Ready Queue into three groups based on their Priority - LOW, MEDIUM and HIGH (note that this is an implementation of the Priority Algorithm).
- Check if there is a process in CPU. If there isn’t, allot the CPU to the first process in the Ready Queue (i.e, the one with the shortest CPU Burst Time) Running State. Assign a new Quantum Time to this process based on the Priority flag of this process -
- LOW: QT L = 0.8 ∗ QT
- MEDIUM: QT M = QT
- HIGH: QT H = 1.2 ∗ QT
- Let this process run for the assigned quantum time (simultaneously increase the timer) or till the process is over. If the process is not completed before the quantum time is over, then compare the remaining CPU Burst Time with the Quantum Time and if the Quantum Time is greater, then let the process continue running in the CPU till it completes itself. However, if the Quantum Time is lesser than the CPU Burst Time, then send the process to the Ready Queue and begin again from Step 5.
- Once the process is completed, if there is a non-zero I/O Burst Time, send it to the I/O Queue (Waiting State) where it will follow FCFS Algorithm. How- ever, if the I/O Burst Time is zero, then the process enters the Terminated State.
- Once the I/O processes are completed, the process is put back into Ready Queue (Ready State) and we begin again from Step 5.
