Operating System Scheduling algorithms

Operating System Scheduling algorithms

A Process Scheduler schedules various processes that are to be allocated to the CPU based on complex scheduling algorithms. We will discuss six common process scheduling algorithms in this chapter-

• First-Come, First-Served (FCFS) Scheduling
• Shortest-Job-Next (SJN) Scheduling
• Priority Scheduling
• Shortest Remaining Time
• Round Robin(RR) Scheduling
• Multiple-Level Queues Scheduling

They are either non- preemptive or preemptive algorithms. Non-preemptive algorithms are designed to prevent a process from entering the running state before it completes its allocated time, while preemptive scheduling is based on priority where a scheduler will preempt a low-priority running process if a high-priority process enters a ready state.

First Come First Serve (FCFS)

• Jobs are executed on first come , first serve basis.
• It is a non-preemptive, pre-emptive scheduling algorithm.
• Simple to comprehend and execute.
• Its implementation is in accordance with the FIFO queue.
• Bad in results since high average waiting time.

Wait time of each process is as follows −

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

Shortest Job Next (SJN)

• This is also known first as shortest work, or SJF
• This is an algorithm for pre-emptive, non-preemptive scheduling.
• Best way to keep waiting time to a minimum.
• Simple to implement where required Processor time is known before that in Batch systems.
• Impossible to implement in interactive systems where Processor time is not understood as required.
• The processor should know in advance how much time it will take to process.

Given: Table of processes, and their Arrival time, Execution time

Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Priority Based Scheduling

• Priority scheduling is a non-preemptive algorithm and one of the most popular algorithms in batch scheduling systems.
• It assigns a priority to each operation. First and so forth, method with the highest priority must be performed.
• Processes with the same importance are carried out on the first come first served basis.
• Priority may be determined on the basis of memory requirements, time requirements or some other requirement for resources

Given: Table of processes, and their Arrival time, Execution time, and priority. Here we are considering 1 is the lowest priority.

Waiting time of each process is as follows −

Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6

Shortest Remaining Time

• The preemptive variant of the SJN algorithm is the shortest remaining time (SRT).
• The processor is assigned to the jobs closest to completion but a newer ready job with shorter time to completion will preempt it.
• Impossible to implement in interactive systems where Processor time is not understood as required.
• Often it is used in batch environments where priority needs to be given to short jobs.

Round Robin Scheduling

• Round Robin is the scheduling algorithm for preemptive procedures.
• process is given a fixed execution time, it's called a quantum.
• When a process is executed for a given period of time, it is preempted and executes other processes for a given period of time.
• Context switching is used for saving preempted process states.

Wait time of each process is as follows −

Average Wait Time: (9+2+12+11) / 4 = 8.5

Multiple-Level Queues Scheduling

Multi - level queues are not an independent algorithm for the scheduling. They make use of other existing algorithms to group and schedule jobs that have similar features.

• For processes with similar features several queues are maintained.
• Could queue can have its own algorithms to schedule it.
• queue is assigned priority.

For eg, CPU-bound jobs in one queue and all I / O-bound jobs in another queue will be scheduled. The Process Scheduler then selects jobs from each queue alternately and assigns them to the CPU based on the algorithm assigned to that queue.