1

OPERATING
SYSTEMS
[CS2204T]

PREPARED BY
PROF. R. G. KHEDKAR
JSPM’S RSCOE
OPERATING SYSTEMS SL LAB
2

UNIT-II

Process Scheduling

Content

 Process Scheduling: Foundation and Scheduling objectives, Process

Scheduling Queues, Types of Schedulers

• Scheduling criteria: CPU utilization, Throughput, Turnaround Time,

Waiting Time, and Response Time.

• Scheduling algorithms: Pre-emptive and non-pre-emptive, FCFS, SJF,

Priority, RR.

• Real Time CPU scheduling: Rate Monotonic Scheduling (RM) and

Earliest Deadline First (EDF).

• Self-Study: Multiple-processor Scheduling

OPERATING SYSTEMS SL LAB

3

Process Scheduling

• Definition

• The process scheduling is the activity of the process manager that handles the removal
of the running process from the CPU and the selection of another process on the basis of
a particular strategy.

• Process scheduling is an essential part of a Multiprogramming operating systems.

• Such operating systems allow more than one process to be loaded into the executable
memory at a time and the loaded process shares the CPU using time multiplexing.

• Process scheduling is allocating resources to tasks so that the tasks can be completed in
an efficient and timely manner.

• Objectives of Process Scheduling

• Optimize the use of resources present.

• Keep the CPU busy and have maximum utilization of the CPU.

• Minimum response time for executing a process means the shortest possible time for
process execution.

• Be Fair while allocating resources to the processes

• Maximize throughput of the system

OPERATING SYSTEMS SL LAB

4

Process Scheduling Queues

• The OS maintains all Process Control Blocks (PCBs) in Process Scheduling Queues.

• The OS maintains a separate queue for each of the process states and PCBs of all
processes in the same execution state are placed in the same queue.

• When the state of a process is changed, its PCB is unlinked from its current queue and
moved to its new state queue.

• The Operating System maintains the following three important process scheduling
queues –

1. Job queue
2. Ready queue
3. Device queues/ Waiting queues

OPERATING SYSTEMS SL LAB

5

1. Job queue –

• This queue keeps all the processes in the system.

• In starting, all the processes get stored in the job queue.

• It is maintained in the secondary memory.

• The long term scheduler (Job scheduler) picks some of the jobs and put them in the
primary memory.

2. Ready queue –

• This queue keeps a set of all processes residing in main memory, ready and waiting to
execute.

• A new process is always put in this queue.

• Ready queue is maintained in primary memory.

• The short term scheduler picks the job from the ready queue and dispatch to the CPU for
the execution.

3. Device queues/ Waiting queues –

• The processes which are blocked due to unavailability of an I/O device constitute this
queue.

• When the process needs some IO operation in order to complete its execution, OS
changes the state of the process from running to waiting.

• The context (PCB) associated with the process gets stored on the waiting queue which
will be used by the Processor when the process finishes the IO.

OPERATING SYSTEMS SL LAB

6

Types of Schedulers

• Schedulers are special system software which handle process scheduling in various
ways.

• Their main task is to select the jobs to be submitted into the system and to decide which
process to run.

• It helps to keep all computer resources busy and allows multiple users to share system
resources effectively.

• There are three types of process schedulers:

1. Long-Term Scheduler (LTS)/Job Scheduler

2. Short-Term Scheduler (STS)/CPU Scheduler

3. Medium-Term Scheduler (MTS)/ swapping scheduler

OPERATING SYSTEMS SL LAB

7

1. Long-Term Scheduler (LTS)/Job Scheduler

• It brings the new process to the ‘Ready State’.

• It controls the Degree of Multi-programming, i.e., the number of processes present in a

ready state at any point in time.

• It is important that the long-term scheduler make a careful selection of both I/O and
CPU-bound processes.

• I/O-bound tasks are which use much of their time in input and output operations while
CPU-bound processes are which spend their time on the CPU.

• The job scheduler increases efficiency by maintaining a balance between the two.

• They operate at a high level and are typically used in batch-processing systems.

2. Short-Term Scheduler (STS)/CPU Scheduler

• It is responsible for selecting one process from the ready state for scheduling it on the
running state.

• Note: Short-term scheduler only selects the process to schedule it doesn’t load the
process on running. Here is when all the scheduling algorithms are used.

• The CPU scheduler is responsible for ensuring no starvation due to high burst time
processes.

OPERATING SYSTEMS SL LAB

8

• The dispatcher is responsible for loading the process selected by the Short-term
scheduler on the CPU (Ready to Running State) Context switching is done by the
dispatcher only.

• A dispatcher does the following:

• Switching context.

• Switching to user mode.

• Jumping to the proper location in the newly loaded program.

3. Medium-Term Scheduler

• It is responsible for suspending and resuming the process. It mainly does swapping
(moving processes from main memory to disk and vice versa).

• Swapping may be necessary to improve the process mix or because a change in memory
requirements has overcommitted available memory, requiring memory to be freed up.

• It is helpful in maintaining a perfect balance between the I/O bound and the CPU bound.
It reduces the degree of multiprogramming.

https://www.youtube.com/watch?v=DtQ9_WPezNA

OPERATING SYSTEMS SL LAB

9

Scheduling criteria

a. CPU utilization:
• The main purpose of any CPU algorithm is to keep the CPU as busy as possible.
• 40 to 90 percent depending on the system load.

b. Throughput:
• The average CPU performance is the number of processes performed and completed
during each unit. This is called throughput.
• The output may vary depending on the length or duration of the processes.

c. Turn round Time:

• For a particular process, the important conditions are how long it takes to perform that
process.
• The time elapsed from the time of process delivery to the time of completion is known
as the conversion time.
• Conversion time is the amount of time spent waiting for memory access, waiting in line,
using CPU, and waiting for I / O.

d. Waiting Time:
• The Scheduling algorithm does not affect the time required to complete the process once
it has started performing.
• It only affects the waiting time of the process i.e. the time spent in the waiting process in
the ready queue.

e. Response Time:
• In a collaborative system, turn around time is not the best option.
• The process may produce something early and continue to computing the new results
while the previous results are released to the user.
• Therefore another method is the time taken in the submission of the application process
until the first response is issued. This measure is called response time.
https://www.youtube.com/watch?v=bWHFY8-
rL5I&list=PLBlnK6fEyqRitWSE_AyyySWfhRgyA-rHk&index=4

OPERATING SYSTEMS SL LAB

10

Scheduling algorithms:
• There are two categories of scheduling:

1. Non-preemptive:

2. Preemptive:

1. Non-preemptive:

• Non-preemptive Scheduling is used when a process terminates, or a process switches

from running to waiting state.
• In this scheduling, once the resources (CPU cycles) is allocated to a process, the process
holds the CPU till it gets terminated or it reaches a waiting state.
• In case of non-preemptive scheduling does not interrupt a process running CPU in
middle of the execution.
• Instead, it waits till the process complete its CPU burst time and then it can allocate the
CPU to another process.
2. Preemptive:

• Preemptive scheduling is used when a process switches from running state to ready state
or from waiting state to ready state.
• The resources (mainly CPU cycles) are allocated to the process for the limited amount
of time and then is taken away, and the process is again placed back in the ready queue if
that process still has CPU burst time remaining.
• That process stays in ready queue till it gets next chance to execute.
https://www.youtube.com/watch?v=4DhFmL-
6SDA&list=PLBlnK6fEyqRitWSE_AyyySWfhRgyA-rHk&index=3

Different terminologies in CPU Scheduling algorithm

• Arrival Time: Time at which the process arrives in the ready queue.

• Completion Time: Time at which process completes its execution.

• Burst Time: Time required by a process for CPU execution.

• Turn Around Time: Time Difference between completion time and arrival time.

• Turn Around Time = Completion Time – Arrival Time

• Waiting Time(W.T): Time Difference between turn around time and burst time.

• Waiting Time = Turn Around Time – Burst Time

OPERATING SYSTEMS SL LAB
11

Scheduling Algorithm

(a) First Come First Serve (FCFS)

In FCFS Scheduling

 The process which arrives first in the ready queue is firstly assigned the CPU.
 In case of a tie, process with smaller process id is executed first.
 It is always non-preemptive in nature.
 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.

Advantages-

 It is simple and easy to understand.

 It can be easily implemented using queue data structure.
 It does not lead to starvation.

Disadvantages-
 It does not consider the priority or burst time of the processes.
 It suffers from convoy effect i.e. processes with higher burst time arrived before the
processes with smaller burst time.
https://www.youtube.com/watch?v=7DoP1L9nAAs&list=PLBlnK6fEyqRitWSE_Ay
yySWfhRgyA-rHk&index=5

OPERATING SYSTEMS SL LAB

12

Example 1:

Example 2:
Consider the processes P1, P2, P3 given in the below table, arrives for execution in the same
order, with Arrival Time 0, and given Burst Time,
PROCESS ARRIVAL TIME BURST TIME
P1 0 24
P2 0 3
P3 0 3
Gantt chart

P1 P2 P3
0 24 27 30

OPERATING SYSTEMS SL LAB

13

TURN AROUND
PROCESS WAIT TIME TIME
P1 0 24
P2 24 27
P3 27 30

Total Wait Time = 0 + 24 + 27 = 51 ms

Average Waiting Time = (Total Wait Time) / (Total number of processes) = 51/3 = 17 ms

Total Turn Around Time: 24 + 27 + 30 = 81 ms

Average Turn Around time = (Total Turn Around Time) / (Total number of processes)
= 81 / 3 = 27 ms
Throughput = 3 jobs/30 sec = 0.1 jobs/sec

Example 3:
Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution in the
same order, with given Arrival Time and Burst Time.
PROCESS ARRIVAL TIME BURST TIME
P1 0 8
P2 1 4
P3 2 9
P4 3 5

Gantt chart
P1 P2 P3 P4
0 8 12 21 26

PROCESS WAIT TIME TURN AROUND TIME

P1 0 8–0=8
P2 8–1=7 12 – 1 = 11
P3 12 – 2 = 10 21 – 2 = 19
P4 21 – 3 = 18 26 – 3 = 23

Total Wait Time:= 0 + 7 + 10 + 18 = 35 ms

Average Waiting Time = (Total Wait Time) / (Total number of processes)= 35/4 = 8.75 ms

Total Turn Around Time: 8 + 11 + 19 + 23 = 61 ms

Average Turn Around time = (Total Turn Around Time) / (Total number of processes)
61/4 = 15.25 ms

Throughput: 4 jobs/26 sec = 0.15385 jobs/sec

OPERATING SYSTEMS SL LAB

14

(b) Shortest Job First (SJF)

 Process which have the shortest burst time are scheduled first.
 If two processes have the same bust time, then FCFS is used to break the tie.
 This is a non-pre-emptive, 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.
 Pre-emptive mode of Shortest Job First is called as Shortest Remaining Time First
(SRTF).

Advantages-

 SRTF is optimal and guarantees the minimum average waiting time.

 It provides a standard for other algorithms since no other algorithm performs better
than it.

Disadvantages-

 It can not be implemented practically since burst time of the processes can not be
known in advance.
 It leads to starvation for processes with larger burst time.
 Priorities can not be set for the processes.
 Processes with larger burst time have poor response time.
https://www.youtube.com/watch?v=t0g9b3SJECg&list=PLBlnK6fEyqRitWSE_AyyyS
WfhRgyA-rHk&index=8

OPERATING SYSTEMS SL LAB

15

Example-01:
Consider the set of 5 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

P1 3 1
P2 1 4
P3 4 2
P4 0 6
P5 2 3

Solution-
If the CPU scheduling policy is SJF non-preemptive, calculate the average waiting time
and average turnaround time.
Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Process Id Exit time Turn Around time Waiting time

P1 7 7–3=4 4–1=3
P2 16 16 – 1 = 15 15 – 4 = 11
P3 9 9–4=5 5–2=3
P4 6 6–0=6 6–6=0
P5 12 12 – 2 = 10 10 – 3 = 7

Now,
 Average Turn Around time = (4 + 15 + 5 + 6 + 10) / 5 = 40 / 5 = 8 unit
 Average waiting time = (3 + 11 + 3 + 0 + 7) / 5 = 24 / 5 = 4.8 unit

OPERATING SYSTEMS SL LAB

16

Example-02:
Consider the set of 5 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

P1 3 1
P2 1 4
P3 4 2
P4 0 6
P5 2 3

If the CPU scheduling policy is SJF pre-emptive, calculate the average waiting time and average
turnaround time.
Solution-
Gantt Chart-

Process Id Exit time Turn Around time Waiting time

P1 4 4–3=1 1–1=0
P2 6 6–1=5 5–4=1
P3 8 8–4=4 4–2=2
P4 16 16 – 0 = 16 16 – 6 = 10
P5 11 11 – 2 = 9 9–3=6

Now,

 Average Turn Around time = (1 + 5 + 4 + 16 + 9) / 5 = 35 / 5 = 7 unit

 Average waiting time = (0 + 1 + 2 + 10 + 6) / 5 = 19 / 5 = 3.8 unit

OPERATING SYSTEMS SL LAB

17

Example-03:

Consider the set of 6 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

P1 0 7
P2 1 5
P3 2 3
P4 3 1
P5 4 2
P6 5 1

If the CPU scheduling policy is shortest remaining time first, calculate the average waiting time
and average turnaround time.
Solution-
Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Process Id Exit time Turn Around time Waiting time

P1 19 19 – 0 = 19 19 – 7 = 12
P2 13 13 – 1 = 12 12 – 5 = 7
P3 6 6–2=4 4–3=1
P4 4 4–3=1 1–1=0
P5 9 9–4=5 5–2=3
P6 7 7–5=2 2–1=1

Now,
 Average Turn Around time = (19 + 12 + 4 + 1 + 5 + 2) / 6 = 43 / 6 = 7.17 unit
 Average waiting time = (12 + 7 + 1 + 0 + 3 + 1) / 6 = 24 / 6 = 4 unit

OPERATING SYSTEMS SL LAB

18

Example -04:

Consider the set of 3 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

P1 0 9
P2 1 4
P3 2 9

If the CPU scheduling policy is SRTF, calculate the average waiting time and average turn
around time.

Solution- Gantt
Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Process Id Exit time Turn Around time Waiting time

P1 13 13 – 0 = 13 13 – 9 = 4

P2 5 5–1=4 4–4=0

P3 22 22- 2 = 20 20 – 9 = 11

Now,
 Average Turn Around time = (13 + 4 + 20) / 3 = 37 / 3 = 12.33 unit
 Average waiting time = (4 + 0 + 11) / 3 = 15 / 3 = 5 unit

OPERATING SYSTEMS SL LAB

19

Example-05:

Consider the set of 4 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

P1 0 20
P2 15 25
P3 30 10
P4 45 15

If the CPU scheduling policy is SRTF, calculate the waiting time of process P2.

Solution-

Gantt Chart-

Now, we know-

 Turn Around time = Exit time – Arrival time

 Waiting time = Turn Around time – Burst time

Thus,

 Turn Around Time of process P2 = 55 – 15 = 40 unit

 Waiting time of process P2 = 40 – 25 = 15 unit

OPERATING SYSTEMS SL LAB

20

(c) Round Robin Scheduling

 CPU is assigned to the process on the basis of FCFS for a fixed amount of time.
 This fixed amount of time is called as time quantum or time slice.
 After the time quantum expires, the running process is preempted and sent to the ready
queue.
 Then, the processor is assigned to the next arrived process.
 It is always preemptive in nature.

Advantages-

 It gives the best performance in terms of average response time.

 It is best suited for time sharing system, client server architecture and
interactive system.

Disadvantages-

 It leads to starvation for processes with larger burst time as they have to repeat the
cycle many times.
 Its performance heavily depends on time quantum.
 Priorities can not be set for the processes.
https://www.youtube.com/watch?v=YzBBJYfwdi8&list=PLBlnK6fEyqRitWSE_AyyySWfhRgyA
-rHk&index=14

OPERATING SYSTEMS SL LAB

21

With decreasing value of time quantum,

 Number of context switch increases
 Response time decreases
 Chances of starvation decreases

Thus, smaller value of time quantum is better in terms of response time.

With increasing value of time quantum,

 Number of context switch decreases
 Response time increases
 Chances of starvation increases

Thus, higher value of time quantum is better in terms of number of context switch.

 With increasing value of time quantum, Round Robin Scheduling tends to

become FCFS Scheduling.
 When time quantum tends to infinity, Round Robin Scheduling becomes FCFS
Scheduling.
 The performance of Round Robin scheduling heavily depends on the value of time
quantum.
 The value of time quantum should be such that it is neither too big nor too small.

Example-01:

Consider the set of 5 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

P1 0 5

P2 1 3

P3 2 1

P4 3 2

P5 4 3

If the CPU scheduling policy is Round Robin with time quantum = 2 unit, calculate the
average waiting time and average turnaround time.
Solution-
Ready Queue- P5, P1, P2, P5, P4, P1, P3, P2, P1

OPERATING SYSTEMS SL LAB

22

Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time
Process Id Exit time Turn Around time Waiting time

P1 13 13 – 0 = 13 13 – 5 = 8

P2 12 12 – 1 = 11 11 – 3 = 8

P3 5 5–2=3 3–1=2

P4 9 9–3=6 6–2=4

P5 14 14 – 4 = 10 10 – 3 = 7

Now,
 Average Turn Around time = (13 + 11 + 3 + 6 + 10) / 5 = 43 / 5 = 8.6 unit
 Average waiting time = (8 + 8 + 2 + 4 + 7) / 5 = 29 / 5 = 5.8 unit

Problem-02:

Consider the set of 6 processes whose arrival time and burst time are given below-
Process Id Arrival time Burst time

P1 0 4

P2 1 5

P3 2 2

P4 3 1

P5 4 6

P6 6 3

If the CPU scheduling policy is Round Robin with time quantum = 2, calculate the average
waiting time and average turnaround time.
Solution-
Ready Queue- P5, P6, P2, P5, P6, P2, P5, P4, P1, P3, P2, P1

OPERATING SYSTEMS SL LAB

23

Gantt chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Process Id Exit time Turn Around time Waiting time

P1 8 8–0=8 8–4=4
P2 18 18 – 1 = 17 17 – 5 = 12
P3 6 6–2=4 4–2=2
P4 9 9–3=6 6–1=5
P5 21 21 – 4 = 17 17 – 6 = 11
P6 19 19 – 6 = 13 13 – 3 = 10

Now,
 Average Turn Around time = (8 + 17 + 4 + 6 + 17 + 13) / 6 = 65 / 6 = 10.84 unit
 Average waiting time = (4 + 12 + 2 + 5 + 11 + 10) / 6 = 44 / 6 = 7.33 unit

Problem-03:

Consider the set of 6 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time

P1 5 5
P2 4 6
P3 3 7
P4 1 9
P5 2 2
P6 6 3

OPERATING SYSTEMS SL LAB

24

If the CPU scheduling policy is Round Robin with time quantum = 3, calculate the average
waiting time and average turnaround time.

Solution-
Ready Queue- P3, P1, P4, P2, P3, P6, P1, P4, P2, P3, P5, P4
Gantt chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time
(d)
Process Id Exit time Turn Around time Waiting time
P1 32 32 – 5 = 27 27 – 5 = 22
P2 27 27 – 4 = 23 23 – 6 = 17
P3 33 33 – 3 = 30 30 – 7 = 23
P4 30 30 – 1 = 29 29 – 9 = 20
P5 6 6–2=4 4–2=2
P6 21 21 – 6 = 15 15 – 3 = 12

Now,
 Average Turn Around time = (27 + 23 + 30 + 29 + 4 + 15) / 6 = 128 / 6 = 21.33 unit
 Average waiting time = (22 + 17 + 23 + 20 + 2 + 12) / 6 = 96 / 6 = 16 unit

OPERATING SYSTEMS SL LAB

25

(e) Priority Scheduling

 Out of all the available processes, CPU is assigned to the process having the
highest priority.
 In case of a tie, it is broken by FCFS Scheduling.
 Priority Scheduling can be used in both preemptive and non-preemptive mode.

 The waiting time for the process having the highest priority will always be zero in
preemptive mode.
 The waiting time for the process having the highest priority may not be zero in non-
preemptive mode.
Priority scheduling in preemptive and non-preemptive mode behaves exactly same under
following conditions-
 The arrival time of all the processes is same
 All the processes become available

Advantages-
 It considers the priority of the processes and allows the important processes to run
first.
 Priority scheduling in pre-emptive mode is best suited for real time operating
system.

Disadvantages-
 Processes with lesser priority may starve for CPU.
 There is no idea of response time and waiting time.

https://www.youtube.com/watch?v=yKD3pcFvGmY&list=PLBlnK6fEyqRitWSE_AyyySWfh
RgyA-rHk&index=11

OPERATING SYSTEMS SL LAB

26

Problem-01:
Consider the set of 5 processes whose arrival time and burst time are given below-
Process Id Arrival time Burst time Priority

P1 0 4 2

P2 1 3 3

P3 2 1 4

P4 3 5 5

P5 4 2 5

If the CPU scheduling policy is priority non-preemptive, calculate the average waiting time
and average turnaround time. (Higher number represents higher priority)

Solution-
Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Process Id Exit time Turn Around time Waiting time

P1 4 4–0=4 4–4=0

P2 15 15 – 1 = 14 14 – 3 = 11

P3 12 12 – 2 = 10 10 – 1 = 9

P4 9 9–3=6 6–5=1
P5 11 11 – 4 = 7 7–2=5

Now,
 Average Turn Around time = (4 + 14 + 10 + 6 + 7) / 5 = 41 / 5 = 8.2 unit
 Average waiting time = (0 + 11 + 9 + 1 + 5) / 5 = 26 / 5 = 5.2 unit

OPERATING SYSTEMS SL LAB

27

Problem-02:
Consider the set of 5 processes whose arrival time and burst time are given below-

Process Id Arrival time Burst time Priority

P1 0 4 2
P2 1 3 3

P3 2 1 4

P4 3 5 5

P5 4 2 5

If the CPU scheduling policy is priority preemptive, calculate the average waiting time and
average turn around time. (Higher number represents higher priority).

Solution-
Gantt Chart-

Now, we know-
 Turn Around time = Exit time – Arrival time
 Waiting time = Turn Around time – Burst time

Process Id Exit time Turn Around time Waiting time

P1 15 15 – 0 = 15 15 – 4 = 11

P2 12 12 – 1 = 11 11 – 3 = 8

P3 3 3–2=1 1–1=0

P4 8 8–3=5 5–5=0

P5 10 10 – 4 = 6 6–2=4

Now,
 Average Turn Around time = (15 + 11 + 1 + 5 + 6) / 5 = 38 / 5 = 7.6 unit
 Average waiting time = (11 + 8 + 0 + 0 + 4) / 5 = 23 / 5 = 4.6 unit

OPERATING SYSTEMS SL LAB

Real Time scheduling
• Real-time systems execute the specified tasks with the needed deadline based on the
time-sharing approach.

• It uses scheduling algorithms based on static or dynamic methods where the number of
tasks and workload may vary.

• Preemptive or non-preemptive approaches are used to select the highest priority tasks to
be executed first compared with the lower priority tasks.

1. Rate monotonic scheduling

• Rate monotonic scheduling is a priority algorithm that belongs to the static priority
scheduling category of Real Time Operating Systems.

• It is preemptive in nature. The priority is decided according to the cycle time of the
processes that are involved.

• If the process has a small job duration, then it has the highest priority. Thus if a process
with highest priority starts execution, it will preempt the other running processes.

• The priority of a process is inversely proportional to the period it will run for. A set of
processes can be scheduled only if they satisfy the following equation:

Where n is the number of processes in the process set, Ci is the computation time of the process,
Ti is the Time period for the process to run and U is the processor utilization.
1

Example:

An example to understand the working of Rate monotonic scheduling algorithm

Processes Execution Time (C) Time period (T)

P1 3 20

P2 2 5

P3 2 10

• It is less than 1 or 100% utilization. The combined utilization of three processes is less
than the threshold of these processes which means the above set of processes is
schedulable and thus satisfies the above equation of the algorithm.

• Scheduling time – For calculating the Scheduling time of the algorithm we have to take
the LCM of the Time period of all the processes.

• LCM ( 20, 5, 10 ) of the above example is 20.

• Thus we can schedule it by 20-time units.

• Priority – As discussed above, the priority will be the highest for the process which has
the least running time period.

• Thus P2 will have the highest priority, and after that P3 and lastly P1.

• P2>P3>P1

• Representation and flow is as follows:

OPERATING SYSTEMS SL LAB

2

• The above figure says that Process P2 will execute two times for every 5 time units,
Process P3 will execute two times for every 10 time units and Process P1 will execute
three times in 20 time units. This has to be kept in mind for understanding the entire
execution of the algorithm below.

• Process P2 will run first for 2 time units because it has the highest priority.

• After completing its two units, P3 will get the chance and thus it will run for 2 time
units.

• As we know that process P2 will run 2 times in the interval of 5 time units and process
P3 will run 2 times in the interval of 10 time units, they have fulfilled the criteria and thus
now process P1 which has the least priority will get the chance and it will run for 1 time.
And here the interval of five time units have completed.

• Because of its priority P2 will preempt P1 and thus will run 2 times. As P3 have
completed its 2 time units for its interval of 10 time units, P1 will get chance and it will
run for the remaining 2 times, completing its execution which was thrice in 20 time units.

OPERATING SYSTEMS SL LAB

3

• Now 9-10 interval remains idle as no process needs it. At 10 time units, process P2 will
run for 2 times completing its criteria for the third interval ( 10-15 ).

• Process P3 will now run for two times completing its execution. Interval 14-15 will again
remain idle for the same reason mentioned above. At 15 time unit, process P2 will
execute for two times completing its execution.This is how the rate monotonic scheduling
works.

• Conditions: The analysis of Rate monotonic scheduling assumes few properties that
every process should possess. They are :

• Processes involved should not share the resources with other processes.

• Deadlines must be similar to the time periods. Deadlines are deterministic.

• Process running with highest priority that needs to run, will preempt all the other
processes.

• Priorities must be assigned to all the processes according to the protocol of Rate
monotonic scheduling.

• Advantages:

• It is easy to implement.

• If any static priority assignment algorithm can meet the deadlines then rate monotonic
scheduling can also do the same. It is optimal.

• It consists of a calculated copy of the time periods, unlike other time-sharing algorithms
as Round robin which neglects the scheduling needs of the processes.

• Disadvantages:

• It is very difficult to support aperiodic and sporadic tasks under RMA.

• RMA is not optimal when the task period and deadline differ.

https://www.youtube.com/watch?v=xgW8VhEOpFg

OPERATING SYSTEMS SL LAB

4

2. Earliest Deadline First (EDF)

• Earliest Deadline First (EDF) is an optimal dynamic priority scheduling algorithm used
in real-time systems.

• It can be used for both static and dynamic real-time scheduling.

• EDF uses priorities to the jobs for scheduling. It assigns priorities to the task according to
the absolute deadline. The task whose deadline is closest gets the highest priority. The
priorities are assigned and changed in a dynamic fashion. EDF is very efficient as
compared to other scheduling algorithms in real-time systems. It can make the CPU
utilization to about 100% while still guaranteeing the deadlines of all the tasks.

• EDF includes the kernel overload. In EDF, if the CPU usage is less than 100%, then it
means that all the tasks have met the deadline. EDF finds an optimal feasible schedule.
The feasible schedule is one in which all the tasks in the system are executed within the
deadline. If EDF is not able to find a feasible schedule for all the tasks in the real-time
system, then it means that no other task scheduling algorithms in real-time systems can
give a feasible schedule. All the tasks which are ready for execution should announce
their deadline to EDF when the task becomes runnable.

• EDF scheduling algorithm does not need the tasks or processes to be periodic and also
the tasks or processes require a fixed CPU burst time. In EDF, any executing task can be
preempted if any other periodic instance with an earlier deadline is ready for execution
and becomes active. Preemption is allowed in the Earliest Deadline First scheduling
algorithm.

• Example: Consider two processes P1 and P2.

• Let the period of P1 be p1 = 50

Let the processing time of P1 be t1 = 25

• Let the period of P2 be period2 = 75

Let the processing time of P2 be t2 = 30

OPERATING SYSTEMS SL LAB

5

• Steps for solution:

• Deadline pf P1 is earlier, so priority of P1>P2.

• Initially P1 runs and completes its execution of 25 time.

• After 25 times, P2 starts to execute until 50 times, when P1 is able to execute.

• Now, comparing the deadline of (P1, P2) = (100, 75), P2 continues to execute.

• P2 completes its processing at time 55.

• P1 starts to execute until time 75, when P2 is able to execute.

• Now, again comparing the deadline of (P1, P2) = (100, 150), P1 continues to execute.

• Repeat the above steps…

• Finally at time 150, both P1 and P2 have the same deadline, so P2 will continue to
execute till its processing time after which P1 starts to execute.

• Advantages of the EDF scheduling algorithm:

• Meeting Deadlines: EDF ensures that tasks with the earliest deadlines are executed first.
By prioritizing tasks based on their deadlines, EDF minimizes the chances of missing
deadlines and helps meet real-time requirements.

• Optimal Utilization: EDF maximizes CPU utilization by allowing tasks to execute as

soon as their deadlines arrive, as long as the CPU is available. It optimizes the use of
system resources by minimizing idle time.

OPERATING SYSTEMS SL LAB

6

• Responsiveness: EDF provides a high level of responsiveness for time-critical tasks. It

ensures that tasks are scheduled and executed promptly, reducing response times and
improving system performance.

• Predictability: EDF provides predictability in terms of task execution times and

deadlines. The scheduling decisions are deterministic and can be analyzed and predicted
in advance, which is crucial for real-time systems.

• Flexibility: EDF can handle both periodic and aperiodic tasks, making it suitable for a
wide range of real-time systems. It allows for dynamic task creation and scheduling
without disrupting the execution of existing tasks.

• Limitations of EDF scheduling algorithm:

• Transient Overload Problem

• Resource Sharing Problem

• Efficient Implementation Problem

https://www.youtube.com/watch?v=ejPXTOcMRPA

OPERATING SYSTEMS SL LAB