Coupon Accepted Successfully!



A process migrates among the various scheduling queues throughout its lifetime. The operating system must select, for scheduling purposes, processes from these queues in some fashion. The selection process is carried out by the appropriate scheduler.
There are two types of Scheduler.
1. Long term Scheduler
2. Short term Scheduler
Often, in a batch system, more processes are submitted than can be executed immediately. These processes are stored to a mass-storage device(representing a queue) where they are kept for later execution. The long-term scheduler, or job scheduler, selects processes from this pool and loads them into memory for execution. The short-term scheduler, or CPU scheduler, selects from among the processes that are ready to execute and allocates the CPU to one of them.
The primary distinction between these two schedulers lies in frequency of execution. The shortterm scheduler must select a new process for the CPU frequently. A process may execute for only a few milliseconds before waiting for an I/O request. Often, the short-term scheduler executes at least once every 100 milliseconds. Because of the short time between executions, the short-term scheduler must be fast. If it takes 10 milliseconds to decide to execute a process for 100 milliseconds, then 10/(100 + 10) = 9 percent of the CPU is being used (wasted) simply for scheduling the work. The long-term scheduler executes much less frequently; minutes may separate the creation of one new process and the next.
The long-term scheduler controls the degree of multiprogramming (the number of processes in memory). If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system. Thus, the long-term scheduler may need to be invoked only when a process leaves the system. Because of the longer interval between executions, the long-term scheduler can afford to take more time to decide which process should be selected for execution. It is important that the longterm scheduler make a careful selection and provide a good mix of I/O bound and CPU bound processes. An I/O-bound process is one that spends more of its time doing I/O than it spends doing computations. A CPU-bound process, in contrast, generates I/O requests infrequently, using more of its time doing computations.

Scheduling Criteria

Many criteria exist for comparing and deciding on CPU scheduling algorithms. Which characteristics are used for comparison can make a substantial difference in which algorithm is judged to be best. The criteria include the following:
1. CPU utilization. We want to keep the CPU as busy as possible. Conceptually, CPU utilization can range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily used system).
2. Throughput. If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes that are completed per time unit, called throughput. For long processes, this rate may be one process per hour; for short transactions, it may be 10 processes per second.
3. Turnaround time. From the point of view of a particular process, the important criterion is how long it takes to execute that process. The interval from the time of submission of a process to the time of completion is the turnaround time. Turnaround time is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.
4. Waiting time. The CPU scheduling algorithm does not affect the amount of time during which a process executes or does I/O; it affects only the amount of time that a process spends waiting in the ready queue. Waiting time is the sum of the periods spent waiting in the ready queue.
5. Response time. In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response. The turnaround time is generally limited by the speed of the output device.
It is needed to maximize the CPU utilization and the throughput and also to minimize turnaround time, waiting time, and response time. In most cases, we optimize the average measure.

Scheduling Algorithms

1. First Come First Serve Scheduling
The simplest of all scheduling algorihm is the first come first serve algorithm also known as FCFS. It implies that, the process that request for CPU firsts, gets the CPU allocated to it firsts. It can be easily implemented using a Queue(FIFO).
Average Waiting time is usually high in case of FCFS.


Example 1:

Let processes come in order P1, P2, P3 and request for CPU

Process Burst Time
P1 - 20
P2 - 5
P3 - 3
CPU allocated in order : P1, P2, P3
0 - 20 - 25 - 28
So waiting time for P1 is 0 , for P2 it’s 20 mseconds, and for P3 it’s 25 mseconds. Hence Avg.
Waiting time = (0+20+25)/3 = 15 mseconds.
If Processes had arrived in any other order , say P3, P2, P1 then results would have been much
0 - 3 - 8 - 28
The waiting time in this case would have been (0+3+8)/3 = 3.67 ms.


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. The FCFS algorithm is thus particularly troublesome for time-sharing systems, where it is important that each user get a share of the CPU at regular intervals. It would be disastrous to allow one process to keep the CPU for an extended period.

Shortest Job First Scheduling

This algorithm associates with each process the length of the process's next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie. Note that a more appropriate term for this scheduling method would be the shortest-next-CPU-burst algorithm, because scheduling depends on the length of the next CPU burst of a process, rather than its total length.
The SJF scheduling algorithm is optimal, in that it gives the minimum average waiting time for a given set of processes. Moving a short process before a long one decreases the waiting time of the short process more than it increases the waiting time of the long process. Consequently, the average waiting time decreases.
But, the real difficulty with the SJF algorithm is knowing the length of the next CPU request. Although the SJF algorithm is optimal, 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, but we can predict it; i.e. we may not know the length of the next CPU burst, but we may be able to predict its value. We expect that the next CPU burst will be similar in length to the previous ones. Thus, by computing an approximation of the length of the next CPU burst, we can pick the process with the shortest predicted CPU burst.
T(n+1) = x.T(n) + (1-x).T(n-1) + (1-x)2.(n-2) + (1-x)3. T (n-3) + ….. so on
The SJF algorithm may be preemptive or non-preemptive depending on the kernel, or CPU requirement.


Example: Preemptive SJF also known as Shortest remaining time first
Process Arrival Time Burst time
P1 0 7
P2 2 3
P3 4 8
P4 6 5
The Gantt chart of the Jobs can be drawn as
0 2 5 10 15 23
Waiting time for P1: 5 – 2 = 3 ms
Waiting time for P2: 0 ms
Waiting time for P3: 15-4=11ms
Waiting time for P4: 10-6=4ms
Therefore Average waiting time = 18 /4 =4.5 ms.

Priority Scheduling

In this CPU scheduling algorithm, a priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order. We can think of priority algorithm as simply a SJF algorithm where the priority (p) is the inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower the priority, and vice versa. Thus only difference is we decide on scheduling in terms of high priority and low priority. Priorities are generally indicated by some fixed range of numbers, such as 0 to 4095.
Priority scheduling can be either preemptive or non-preemptive. 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 P1 P2 P1 P4 P3 arrived process is higher than the priority of the currently running process. A non-preemptive priority scheduling algorithm will simply put the new process at the head of the ready queue. A major problem with priority scheduling algorithms is of starvation. 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. This is highly undersirable, and this problem can be solved by using the concept of Aging of a process, which means that as the processwaits in ready queue, it’s priority gradually keeps on increasing. This ensures that even low priority process get CPU allocated to it, after some waiting time.

Round Robin Scheduling

The round-robin CPU scheduling algorithm is basically a preemptive scheduling algorithm designed for time-sharing systems. One unit of time is called a time slice. Duration of a time slice may range between 10 msecs. and about 100 msecs. The CPU scheduler allocates to each process in the ready queue one time slice at a time in a round-robin fashion. Hence the name round-robin.
The ready queue in this case is a FIFO queue with new processes joining the tail of the queue. The CPU scheduler picks processes from the head of the queue for allocating the CPU. The first process at the head of the queue gets to execute on the CPU at the start of the current time slice and is deleted from the ready queue. The process allocated the CPU may have the current CPU burst either equal to the time slice or smaller than the time slice or greater than the time slice. In the first two cases, the current process will release the CPU on its own and there by the next process in the ready queue will be allocated the CPU for the next time slice. In the third case, the current process is preempted, stops executing, goes back and joins the ready queue at the tail there by making way for the next process.
Process Burst time (msecs)
P1 24
P2 3
P3 3
Let the duration of a time slice be 4 msecs, which is to say CPU switches between processes every 4 msecs in a round-robin fashion. The Gantt chart below shows the scheduling of processes.
0 4 7 10 14 18 22 26 30
Average waiting time = (4 + 7 + (10 – 4)) / 3 = 17/ 3 = 5.66 msecs.
If there are 5 processes in the ready queue that is n = 5, and one time slice is defined to be 20 msecs that is q = 20, then each process will get 20 msecs or one time slice every 100 msecs.
Each process will never wait for more than (n – 1) x q time units. The performance of the RR algorithm is very much dependent on the length of the time slice. If the duration of the time slice is indefinitely large then the RR algorithm is the same as FCFS algorithm. If the time slice is too small, then the performance of the algorithm deteriorates because of the effect of frequent context switching.
P1 P2 P3 P1 P1 P1 P1 P1


Multilevel Queue Scheduling

Processes can be classified into groups. For example, interactive processes, system processes, batch processes, student processes and so on. Processes belonging to a group have a specified priority. This algorithm partitions the ready queue into as many separate queues as there are groups. Hence the name multilevel queue. Based on certain properties is process is assigned to one of the ready queues. Each queue can have its own scheduling algorithm like FCFS or RR. For example, Queue for interactive processes could be scheduled using RR algorithm where queue for batch processes may use FCFS algorithm. An illustration of multilevel queues is shown below.

Queues themselves have priorities. Each queue has absolute priority over low priority queues, that is a process in a queue with lower priority will not be executed until all processes in a queue with higher priority have finished executing.
This priority on the queues themselves may lead to starvation. To overcome this problem, time slices may be assigned to queues when each queue gets some amount of CPU time. The duration of the time slices may be different for queues depending on the priority of the queues.

Multilevel Feedback Queue Scheduling

In the previous multilevel queue scheduling algorithm, processes one assigned to queues do not move or change queues. Multilevel feedback queues allow a process to move between queues. The idea is to separate out processes with different CPU burst lengths. All processes could initially join the highest priority queue. Processes requiring longer CPU bursts are pushed to lower priority queues. I/O bound and interactive processes remain in higher priority queues.
Aging could be considered to move processes from lower priority queues to higher priority to avoid starvation. An illustration of multilevel feedback queues is shown below:


Highest priority
Queue 0
Queue 1
Queue 2
Lowest priority
RR scheduling (q = 8)
RR scheduling (q = 16)

FCFS scheduling


A process entering the ready queue joins queue 0. RR scheduling algorithm with q = 8 is used to schedule processes in queue 0. If the CPU burst of a process exceeds 8 msecs., then the process preempted, deleted from queue 0 and joins the tail of queue 1. When queue 0 becomes empty, then processes in queue 1 will be scheduled. Here also RR scheduling algorithm is used to schedule processes but q = 16. This will give processes a longer time with the CPU. If a process has a CPU burst still longer, then it joins queue 3 on being preempted. Hence highest priority processes (processes having small CPU bursts, that is I/O bound processes) remain in queue 1 and lowest priority processes (those having long CPU bursts) will eventually sink down. The lowest priority queue could be scheduled using FCFS algorithm to allow processes to complete execution.
Multilevel feedback scheduler will have to consider parameters such as number of queues, scheduling algorithm for each queue, criteria for upgrading a process to a higher priority queue, criteria for downgrading a process to a lower priority queue and also the queue to which a process initially enters.

Precedence Graphs

A PRECEDENCE GRAPH is a directed, acyclic graph where nodes represent sequential activities and where arcs, say from node i to node j, require that activity i complete before activity j can start. A node in a precedence graph could be a software task, as recognised by the operating system, or could be statements within a program that can be executed concurrently with respect to each other [see example below], or could describe some activity taking place during the execution of a single machine instruction. People refer to the different "sizes" of these concurrent activities, as the CONCURRENCY GRAIN of the representation. It goes from COARSE (the concurrency of operating systems task), to fine (the concurrency of single instructions, or of groups of instructions, as done for example in superscalar processors), to very fine (concurrency in the hardware during the execution of the single instruction). we may have concurrent processes within a single program.
Consider this short program.


read (a );
b := sin(2.0);
c := a +b ;
write (c );
It doesn’t matter which order the first two statements are executed in. They could even be executed concurrently.
A precedence graph shows the order in which activities can execute.
read (a )
b :=
sin (2.0)
c :=
a +b

write (c )


Notice the precedence graphs are acyclic, that is, they do not have loops. Thus they cannot represent cyclic computations. Since many of the computations in operating systems are cyclical, this is a strong restriction. There are two ways out. One, represent each cycle with an acyclic graph; you will lose possible concurrency across two successive cycles, but you will be able to deal fully with concurrency within a single cycle. Two, give up on precedence graphs and use instead Petri.

Fork and Join

FORK and JOIN were introduced in 1966 by Dennis and VanHorne. Though Fork has the same name as an operation in Unix, you should think of them as totally unrelated.
When the statement:
Fork(label); is executed by a thread of control, a second thread of control is started from the statement with the specified label. The two threads execute concurrently


while ( w>0)
y = read();
count =
count = 2;
A = y * y;
goto L4;
L1: r = y + 20;
Goto L3;
L2: s = y - 1;


w = 100;
while ( w>0)
y = read();
a = y * y;
r = y + 20;
s = y – 10;
b = r * s;
c = a - b;
w = w –1;

When the statement:

is executed, where count is an integer variable, the value of count is decremented. If the resulting value is positive the executing thread is terminated. The join operation is always indivisible.
The above program shows how a Basic code, is analyzed through a precedence graph and then expressed without loss of concurrency [remember that any precedence graph could be executed as a sequential program, but at a loss in concurrency.

Race Condition

When several processes access and manipulate the same data concurrently, the outcome of the execution depends on the particular order in which the access takes place, is called race condition.


Example – Let’s take a common variable counter which is shared by 2 processes P1 and P2. At any instance, value of counter is 7.

Also counter++ may be implemented in machine language as

register1 = counter
register1 = register1 + 1
counter= register1.
counter-- can be implemented in the same way.
Now P1 executes counter++ and at the same time P2 executes counter--.
The concurrent execution of both statements may be sequentially implemented as
register1 = counter
register1 = register1 + 1
register2 = counter
register2= register2 – 1
counter = register1
counter = register2
Thus depending on which statement gets executed first the value of counter, after the execution of counter++ and counter-- simultaneously, is 6, 7 or 8 i.e. unpredictable. Thus processes race to modify the shared variable and this condition is called Race Condition.


Test Your Skills Now!
Take a Quiz now
Reviewer Name