Scheduling Algorithms in Operating Systems | OS Tutorials

When a computer is multiprogrammed, it frequently has multiple processes competing for the CPU at the same time. When more than one process is in the ready state, and there is only one CPU available, the operating system must decide which process to run first. The part of the operating system that makes the choice is called the scheduler; the algorithm it uses is called the scheduling algorithm.

Scheduling Algorithms

CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CPU. There are many different CPU scheduling algorithms.

Classification of Scheduling Algorithm

FCFS (First Come First Serve) Scheduling

The simplest scheduling policy is first-come, first-served (FCFS), also known as first-in, first-out (FIFO), a strict queueing scheme, run-to-completion, or run-until-done scheduling. The FCFS scheduling algorithm is Nonpreemptive. Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O.

• In this scheme, the process that requests the CPU first is allocated the CPU first. The implementation of the FCFS policy is easily managed with a FIFO queue.
• When a process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue.
• The Running process is then removed from the queue. It is simple to understand, but the average waiting time under the FCFS policy is often quite long.
• FCFS performs much better for long processes than short ones.
• An example of FCFS scheduling is a Batch Processing system in which jobs are ordered according to their arrival times, and results of a job are released to a user immediately upon completion of a job.
• Consider the following set of processes that arrive at time 0, with the length of the CPU burst given in milliseconds.

If the processes arrive in the order W, X, Y, and Z and are served in FCFS order, we get the result shown in the following Gantt Chart (bar chart), illustrating the start and finish times of each of the participating processes.

• The Waiting time is 0 milliseconds for process W.
• The Waiting time is 5 milliseconds for process X.
• The Waiting time is 15 milliseconds for process Y.
• The Waiting time is 33 milliseconds for process Z.

Thus, the average waiting time is (0 + 5 + 15 + 33)/4 = 53/4 = 13.25 milliseconds.

If the processes arrive in the order Z, W, X, Y, the results will be shown in the following Gantt chart.

• Waiting time for process Z = 0 milliseconds
• Waiting time for process W = 2 milliseconds
• Waiting time for process X = 7 milliseconds
• Waiting time for process Y = 17 milliseconds

Thus Average Waiting time = (0+2+7+17)/4 = 36/4 = 9 millisecond

This reduction is substantial. Thus, the average waiting time under an FCFS policy is generally not minimal and may vary substantially if the processes’ CPU burst times vary greatly.

Performance of FCFS Scheduling in Dynamic Situation

Assuming we have one CPU-bound process and many I/O bound processes. As the processes flow around the system, the CPU-bound process will get the CPU and hold it. During this time, all the other processes will finish their I/O and move into the ready queue, waiting for the CPU. While the processes wait in the ready queue, the I/O devices are idle. Eventually, the CPU-bound process finishes its CPU burst and moves to an I/O device.

All the I/O bound processes, which have very short CPU bursts, execute quickly and move back to the I/O queues.
At this point, the CPU sits idle. The CPU-bound process will then move back to the ready queue and allocate the CPU. All the I/O processes end up waiting in the ready queue until the CPU-bound process is done.

Convoy Effect

• When all I/O devices are idle even when the system contains lots of I/O jobs, OR we can say that when CPU idle, even though the system contains CPU-bound jobs, it is called as Convoy effect.
• Short jobs stuck waiting for long jobs.
• This effect results in lower CPU utilization and also lower device utilization.
• Convoy effect is a result of one log CPU bound process and many other CPU bound processes are waiting.

Shortest Job First (SJF) Scheduling

It is also known as Shortest Process Next (SPN) or Shortest Next CPU Burst scheduling because the scheduling is done by examining the length of the next CPU burst rather than its total length. It is also a non-preemptive policy. It assumes that the run times are known in advance by associating with each process the length of the process’s next CPU burst. When a CPU is available, it is assigned to the process that has the smallest next CPU burst. If two processes have the same length next CPU burst, then to break the tie, FCFS scheduling is used.

Consider the following set of processes with the length of the CPU burst time given in milliseconds:

Since Process P₁ has the shortest CPU time (i.e., 3), which is followed by P₂, P_3, and P₁. If we rearrange according to the shortest CPU time, then it will be as follows:

Gantt Chart is look like

Average Waiting Time is calculated as,

• Average Waiting time for P₁ = 0 ms
• Average Waiting time for P₂ = 3 ms
• Average Waiting time for P₃ = 9 ms
• Average Waiting time for P₁ = 16 ms

Average Waiting time = $\frac{0+3+9+16}{4} = \frac{28}{4} = 7ms$

Average turnaround time is calculated as (TAT is the time required to complete the process)

• Turnaround time for P₁ = 3
• Turnaround time for P₂ = 9
• Turnaround time for P₃ = 16
• Turnaround time for P₄ = 24

Average Turnaround Time $\frac{3+9+16+24}{4} = \frac{52}{4} = 13ms$

• If we were using the FCFS scheduling scheme, then the average waiting time would be 10.25 milliseconds.
• We observe that SJF scheduling is more optimal than FCFS, since it gives the minimum average waiting time for a given set of processes. The average time decreases.

Drawbacks of SJF Scheduling

• The difficulty with the SJF algorithm is knowing the length of the next CPU request.
• Since SJF is optimal, even then it cannot be implemented at the level of short-term CPU scheduling. There is no way to know the length of the next CPU burst. One Solution is to predict its value.

Approximating SJF Scheduling

• Since we do not know the length of the next CPU burst, we may be able to predict its value. We expect that the next CPU burst will be similar in length to the previous one.
• Thus, by computing an approximation of the length of the next CPU burst, we can pick the process with the shortest predicted CPU burst.
• A predicted formula may be used to predict the amount of time for which CPU may be required by a process.
• Let t_n be the length of the n^th CPU burst, and let $\tau_{n+1}$ be our predicted value for the next CPU burst.
• Defining a parameter $\alpha$ that controls the relative weight of recent and past history in our production such that $0 \leq \alpha \leq 1$, then a formula is derieved called as Exponential Average, which is defined as,

Where t_n contains our most recent information, and $\tau_n$ stores the history. Parameter $\alpha$ controls the relative weight of recent & past history in our prediction.

• If $\alpha$ = 0, then $\tau_{n+1} = \tau_n$ (Recent history has no effect)
• If $\alpha$ =1, then $\tau_{n+1} = \tau_n$ (Most recent CPU burst matter)
• If $\alpha$ = 1/2, then recent and past history are equally weighted.

SJF Algorithm may be Preemptive and Non-Preemptive

• The choice arises when a process arrives at the ready queue while a previous process is executing.
• A Preemptive SJF algorithm will preempt (terminate) the currently executing process and start the execution of the newly entered process.
• Whereas, a Nonpreemptive SJF algorithm will allow the currently running process to finish its CPU bursts.
• Preemptive SJF scheduling is sometimes called Shortest-Remaining-Time-First (SRTF) scheduling.
• Example: Preemptive SJF or SRTF Scheduling. Consider the following four processes, with the weight of CPU burst time (in milliseconds):

If we apply Preemptive SJF scheduling, then it is depicted in the following Gantt chart:

• Process P₁ is started at time 0. Since it is the only process in the queue, it executes for 1 ms.
• After 1 ms, process P₂ arrives and executes for the next 1 ms. After executing for 1 millisecond, process P₃ arrives; since process P₃ has the shortest CPU time, it executes for their 3 milliseconds CPU burst; a total of 5 ms is executed.
• After 5 milliseconds, process P₄ arrives; since process P₄ also has the shortest CPU time among the remaining processes, it executes for 4 milliseconds.
• After 9 milliseconds, (P₁-8, P₂-7), process P3 and P4 are executed completely, and among P1 and P2, Process P2 (7 milliseconds) has the shortest CPU time compared to P₁ (8 milliseconds).
• Hence, process P₂ is preempted and scheduled for 7 milliseconds; after 16 milliseconds, process P₁ is preempted and scheduled.
• Therefore, Average Waiting Time can be calculated as
  • Waiting time for Process P₁ = 0+(16-1) = 15ms
  • Waiting time for Process P₂ = 0+(9-2) = 7ms
  • Waiting time for Process P₃ = 2-2 = 0ms
  • Waiting time for Process P₄ = 5-3 = 2ms
  • Average waiting time =(15+7+0+2)/4=24/4 =6ms
• If we apply Non-Preemptive SJF Scheduling, then it is depicted in the following Gantt Chart

• At time = 0 ms, only one process, i.e., P₁, is in the ready queue. Since in a non-preemptive scheme, when a process starts its execution, it is not preempted unless the burst time is completed
• So, P₁, P₂, P₃, and P₄ processes are executed one after the other.
• Average waiting time can be calculated as,
  • Waiting time for Process P₁ = 0
  • Waiting time for Process P₂ =(9-1)=8ms
  • Waiting time for Process P₃ =(17-2)=15ms
  • Waiting time for Process P₄ =(20-3)=17ms
  • Average waiting time =(0+8+15+17)/4 = 40/4 =10 ms

Hence, Preemptive SJF scheduling is considered more optimal than Non-Preemptive SJF scheduling.

Shortest Remaining Time Scheduling (SRTS)

• The shortest remaining time (SRT) policy is a preemptive version of SJF.
• In this case, the scheduler always chooses the process that has the shortest expected remaining processing time.
• When a new process joins the ready queue, it may have a shorter remaining time than the currently running process. Accordingly, the scheduler may preempt the current process when a new process becomes ready.
• SRTF does not have the bias in favor of long processes found in FCFS.
• SRTF should also give superior turnaround time performance to SJF, because a short job is given immediate preference over a running longer job.

Priority Scheduling

• In the priority scheduling algorithm, a priority is associated with each process, and the CPU is allocated to the process with the highest priority.
• If two processes have the same priority, the tie should be broken by applying FCFS order. Main features of priority scheduling are:
  • A mix of CPU-bound and I/O bound processes exists in the system.
  • An I/O bound process has a higher priority than a CPU-bound process.
  • Process priorities are static, i.e., they do not change with time.
  • Process scheduling is preemptive; a low-priority running process is preempted if a higher-priority process becomes ready. In effect, a low-priority process cannot be running if a higher-priority process exists in the ready state.
• An SJF is simply a priority algorithm where the priority is the inverse of the predicted next CPU burst. The larger the CPU burst, the lower the priority and vice versa.
• The Scheduler can maintain separate lists of ready and blocked processes and always select the highest-priority process from the ready queue.
• The Scheduler can maintain a single list of PCBs in which PCBs are arranged in the order of reducing priorities.
• The scheduler can scan this list and simply select the first ready process it finds. This is the highest priority ready process in the system.
• In addition to the PCB list, the scheduler maintains a pointer called the Currently Running Process pointer (CRP pointer). This pointer points to the PCB of the process that is in the running state.
• Generally, priorities are some fixed range of numbers, such as 0 to 7, or 0 to 4095. Some systems use low numbers to represent low priority; others use low numbers for high priority. Normally, we assume low numbers represent high priority.

Example based on Priority Scheduling

Consider the following set of processes, assumed to have arrived at time 0, in the order A, B, C, D, and E, with the length of the CPU burst time given in milliseconds.

If we apply priority scheduling, then it is depicted in the following Gantt chart:

Average Waiting time can be calculated as,

• Waiting time for Process A = 6 ms
• Waiting time for Process B = 0 ms
• Waiting time for Process C = 16ms
• Waiting time for Process D = 18ms
• Waiting time for Process E = 1ms
• Average waiting time = (6+0+16+18+1)/5=41/5 = 8.2 ms

Internal and External Priorities

Priorities can be defined either internally or externally:

• Internally defined priorities use some measurable quantity or quantities to compute the priority of a process. For example, Time limits, Memory requirements, etc have been used in computing priorities.
• External priorities are set by criteria that are external to the operating system, such as the importance of the process, etc.

Priority Scheduling is either Preemptive or Non-Preemptive:

• Priority scheduling can be either preemptive or nonpreemptive. When a process arrives at the ready queue, its priority is compared with the priority of the currently running process.
• A preemptive priority scheduling algorithm will preempt the CPU if the priority of the newly arrived process is higher than the priority of the process currently running in the system.
• A Nonpreemptive priority scheduling algorithm will simply put the new process at the head of the ready queue.

Drawback of Priority Scheduling

The major problem with the priority scheduling algorithm is Indefinite Blocking/Starvation.

Starvation

• Starvation is a resource management problem where a process does not get the resources it needs for a long time because the resources are being allocated to other processes.
• A Process that is ready to run but waiting for the CPU can be considered blocked. A priority scheduling algorithm can leave some low-priority processes waiting indefinitely.
• In a heavily loaded computer system, a steady stream of higher-priority processes can prevent a low-priority process from ever getting the CPU.
• A solution to the problem of indefinite blockage of low-priority processes is aging.

Aging

Aging is a technique of gradually increasing the priority of processes that wait in the system for à long time. As a job is waiting, raise its priority, so eventually it will have the maximum priority. This prevents starvation (assuming all jobs terminate or the policy is preemptive).

For example, if priorities range from 127 (low) to 0 (high), we could increase the priority of an awaiting process by 1 every 15 minutes. There may be many processes with the maximum priority. If so, we can use FIFO among those with max priority (risks starvation if a job doesn’t terminate), or we can use RR.

Round Robin (RR) scheduling

• The Round Robin (RR) scheduling is designed especially for a time-sharing system.
• It is similar to FCFS scheduling, but preemption is added to enable the system to switch between processes; for that, each process is assigned a time interval called its quantum, which is allowed to run.
• If the process is still running at the end of the quantum, the CPU is preempted and given to another process.
• If the process has blocked or finished before the quantum has elapsed, the CPU switch is done when the process blocks.
• A time quantum is generally from 10 to 100 milliseconds in length. The Ready queue is treated as a circular queue.
• The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.
• Round Robin scheduling is preemptive.
• To implement the RR scheduling, we keep the ready queue as a FIFO queue of processes. New processes are added to the tail of the ready queue.
• The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process.
• The only interesting issue with round robin is the length of the quantum.
• Switching from one process to another requires a certain amount of time for doing the administration for saving and loading registers, etc.
• The average waiting time under the RR policy is often long.

Example based on Round Robin Scheduling:

Consider the following set of processes that arrive at time 0, with the length of the CPU burst given in milliseconds.

• If we use a time quantum of 3 milliseconds, then process X gets the first 3 milliseconds. Since it requires another 15 milliseconds, it is preempted after the first time quantum, and the CPU is given to the next process in the queue, i.e., process Y.
• It is depicted in the following Gantt Chart:

• Process Y executes for 3 milliseconds, and it requires 6 milliseconds more. Hence, it is preempted after the first time quantum and gives the CPU to the next process Z.
• The same process is implemented by Z until all the processes are executed.
• Average waiting time is calculated as,
  • Waiting time for Process X = (0+(9-3)+(17-12)+(23-20)=14
  • Waiting time for Process Y = (3+(12-6)+(20-15)) = 14
  • Waiting time for Process Z = 6+(15-9) = 12
  • Average waiting time = (14+14+12)/3 = 40/3 = 13.33 (approx)
• In the RR scheduling algorithm, no process is allocated the CPU for more than 1 time quantum in a row, unless it is the only runnable process.
• If a process’s CPU burst exceeds 1 time quantum, that process is preempted and is put back in the ready queue.

For n number of processes

• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units.
• Each process must wait no longer than (n-1)/q time units until its next time quantum.

Performance of Round Robin Algorithm

• The Performance of the RR algorithm depends heavily on the size of the time quantum.
• If the time quantum is extremely large, the RR policy is the same as the FCFS policy.
• If the time quantum is extremely small (say 1 ms), then the RR algorithm is called a Processor Sharing.
• Turnaround time also depends on the size of the time quantum.

Variants of Round Robin

• State dependent RR
  • Same as RR but q is varied dynamically depending on the state of the system.
  • Favor processes holding important resources.
    • For example, non-swappable memory.
    • Perhaps this should be considered medium-term scheduling since you probably do not recalculate q each time.
    • External priorities: RR, but a user can pay more and get bigger q. That is, one process can be given a higher priority than another. But this is not an absolute priority: the lower priority (i.e., less important) process does get to run, but not as much as the higher priority process.

Performance Analysis

The performance of the various scheduling policies is a critical factor in the choice of a scheduling policy. The quantitative measurement of the scheduling efficiency is based on response time, turnaround time, system throughput, etc. Queuing analysis and simulation modeling are used to determine the performance.

When to Schedule Algorithm

There are a variety of situations in which scheduling may occur. First, scheduling is absolutely required on two occasions:

1. When a process exits.
2. When a process blocks on I/O or a semaphore.

In each of these cases the process that had most recently been running becomes unready, so another must be chosen to run next. There are three other occasions when scheduling is usually done, although logically it is not necessary at these times.

1. When a new process is created.
2. When an I/O interrupt occurs.
3. When a clock interrupt occurs.

• In the case of a new process, it makes sense to reevaluate priorities at this time.
• In the case of an I/O interrupt, this usually means that an I/O device has now completed its work. So some process that was blocked waiting for I/O may now be ready to run.
• In the case of a clock interrupt, this is an opportunity to decide whether the currently running process has run too long.

Comparison of the Characteristics of the Scheduling Methods

w = time spent in waiting
e = time spent in execution so far
s = total service time required by the process, including e