CPU Process Scheduling

CPU Process Scheduling Algorithms

Two types - Preemptive & Non-Preemptive

Pre-Emptive Algorithms	Non Pre-Emptive Algorithms
1. SRTF(Shortest Remaining Time First)	1. FCFS(First Come First Serve)
2. LRTF(Longest Remaining Time First)	2. SJF(Shortest Job First)
3. Round Robin	3. LJF(Longest Job First)
4. Priority based	4. HRRN(Highest Response Ratio Next)
	5. Multilevel Queue

Criteria : Arrival Time.
Mode : Non-Preemptive.
Use Gantt Chart to solve numericals.
Based on given Arrival and Burst Times of various processes, we find out their completion time, turnaround time, waiting time, response time using their formulas.
Also, find the average completion time, average turnaround time and average waiting time.
Response time will be equal to waiting time because FCFS is non-preemptive.

Criteria : Processes with least Burst Time.
Mode : Non - Preemptive.
Similar to FCFS, based on given arrival and burst times, we find out their completion time, turnaround time, waiting time, and response time.
Plot the Gantt Chart for processes being executed in CPU.
Calculate the average timings.
In non-preemptive algorithms, waiting time is always equal to response time.

SJF with Preemption is also known as Shortest Remaining Time First(SRTF) Scheduling Algorithm.
Criteria : Burst Time.
Mode : Preemptive.
More complicated numericals as you have to check the least burst time among all processes in the ready queue at every step.
If two processes have equal burst time, then consider their arrival times. The process with lower arrival time gets executed first.
Response time will be different than waiting time, because of preemption.

Criteria : Time Quantum
Mode : Preemptive
Use two Gantt charts for Ready Queue and Running Queue. Based on the given Time Quantum value, the arrival and burst times of processes, we calculate the CT, TAT, WT, RT.
Context switching happens when a running process is preempted back into the Ready Queue from the Running Queue when it has run for the specified Time Quantum value. The context of the Process Control Block of the running process is saved and the process is sent back to the Ready Queue and a new process is brought in to be executed.

Criteria : Priority.
Mode : Pre-Emptive.
Wether Higher Number = Higher Priority OR Lower Number = Higher Priority. Will be given in the question.
Based on the priority of processes, arrival and burst times, we calculate the CT, TAT, WT. Use Gantt chart for Running Queue.
In case of equal priority of two processes, use their arrival time. The one with lower arrival time gets executed first.

Processes can be of different types, and there are different Ready Queues for them.
System Processes have highest priority and are scheduled using Round Robin algorithm.
Interactive Processes like media players have medium priority scheduled using SJF algorithm and have a separate Ready queue.
Batch Processes are background processes, have lowest priority scheduled using FCFS algorithm.
Drawback is that the response times of batch processes will be very high, because the system processes will keep the CPU occupied leaving less time for interactive and batch processes to execute. This is the problem of starvation. This drawback is overcome by Multilevel Feedback Queue Scheduling.

Lowest priority processes face the problem of starvation, which can be solved by feedback, where a low priority processes is progressively upgraded to a higher priority queue each time it is executed for a defined time quantum.
Processes which are already high priority do not face the problem of starvation.
The lowest priority process is executed for some time quantum, or it can be any algorithm for that matter. It is then given an upgrade to a queue having a higher priority and this process continues to the highest priority queue till the process has been executed completely.