Operating System | Scheduling Algorithms Type | FCFS | SJF | Priority | Round Robin (RR)

Scheduling Algorithms

We'll discuss four major scheduling algorithms here which are following :

1. First Come First Serve(FCFS) Scheduling
2. Shortest-Job-First(SJF) Scheduling
3. Priority Scheduling
4. Round Robin(RR) Scheduling
5. Multilevel Queue Scheduling
6. Multilevel Feedback Queue Scheduling

First Come First Serve(FCFS) Scheduling

• Jobs are executed on first come, first serve basis.
• It is a non-preemptive, pre-emptive scheduling algorithm.
• Easy to understand and implement.
• Its implementation is based on FIFO queue.
• Poor in performance as average wait time is high.

#reference

Wait time of each process is as follows −

Process	Wait Time : Service Time - Arrival Time
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	8 - 2 = 6
P3	16 - 3 = 13

Average Wait Time: (0+4+6+13) / 4 = 5.75

Shortest-Job-First(SJF) Scheduling

• This is also known as shortest job first, or SJF
• This is a non-preemptive, pre-emptive scheduling algorithm.
• Best approach to minimize waiting time.
• Easy to implement in Batch systems where required CPU time is known in advance.
• Impossible to implement in interactive systems where required CPU time is not known.
• The processer should know in advance how much time process will take.

#reference

In Preemptive Shortest Job First Scheduling, jobs are put into ready queue as they arrive, but as a process with short burst time arrives, the existing process is preempted.

#reference

Priority Scheduling

• Priority scheduling is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems.
• Each process is assigned a priority. Process with highest priority is to be executed first and so on.
• Processes with same priority are executed on first come first served basis.
• Priority can be decided based on memory requirements, time requirements or any other resource requirement.

Round Robin(RR) Scheduling

• Round Robin is the preemptive process scheduling algorithm.
• A fixed time is allotted to each process, called quantum, for execution.
• Once a process is executed for given time period that process is preemptied and other process executes for given time period.
• Context switching is used to save states of preemptied processes.

Some useful facts about Scheduling Algorithms:
1) FCFS can cause long waiting times, especially when the first job takes too much CPU time.

2) Both SJF and Shortest Remaining time first algorithms may cause starvation. Consider a situation when long process is there in ready queue and shorter processes keep coming.

3) If time quantum for Round Robin scheduling is very large, then it behaves same as FCFS scheduling.

4) SJF is optimal in terms of average waiting time for a given set of processes,i.e., average waiting time is minimum with this scheduling, but problems is, how to know/predict time of next job.