Chapter No:04 CPU Scheduling and Algorithms

Total Marks:14

CO: Apply Scheduling Algorithms to calculate Turn Around Time and Average
Waiting Time

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

Q1. Why Scheduling ??
In Multiprogramming systems,
 The Operating system schedules the processes on the CPU to have the maximum
utilization of it and this procedure is called CPU scheduling.
 In Multiprogramming, if the long term scheduler picks more I/O bound processes
then most of the time, the CPU remains idol.
 The task of Operating system is to optimize the utilization of resources and to keep
CPU busy all time
 If most of the running processes change their state from running to waiting then there
may always be a possibility of deadlock in the system
 Hence to reduce this overhead, the OS needs to schedule the jobs to get the
optimal utilization of CPU and to avoid the possibility to deadlock.
 The Operating System uses various scheduling algorithm to schedule the processes.
Q2. Define Scheduling
 Process -of allocating CPU to process known as scheduling
 CPU Scheduling is a process of determining which process will own CPU for execution
while another process is on hold.
 The main task of CPU scheduling is to make sure that whenever the CPU remains idle.
 Short term scheduler used for this
 Main objective is that to kept CPU busy and full utilization of CPU
 All resourced must be scheduled before they use
 It used for CPU and I/O device

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

Q3.Explain CPU and I/O burst cycle with the help of diagram.
 CPU burst cycle: - It is a time period when process is busy with CPU.
 I/O burst cycle: - It is a time period when process is busy in working with I/O resources.
 A process starts its execution when CPU is assigned to it, so process execution
begins with a CPU burst cycle.
 This is followed by an I/O burst cycle when a process is busy doing I/O
operations.
 A process switch frequently from CPU burst cycle to I/O burst cycle and vice
versa. The complete execution of a process starts with CPU burst cycle, followed
by I/O burst cycle, then followed by another CPU burst cycle, then followed by
another I/O burst cycle and so on.
 The final CPU burst cycle ends with a system request to terminate
execution

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

Q4. State any four criteria in CPU scheduling
CPU utilization: - In multiprogramming the main objective is to keep CPU as busy as
possible.
CPU utilization can range from 0 to 100 percent.
Throughput: - It is the number of processes that are completed per unit time.
Turnaround time:-The time interval from the time of submission of a process to the time of
completion of that process is called as turnaround time.
It is calculated as:
Turnaround Time = Waiting Time + Burst Time
or
Turnaround Time =Completion Time(End Time) – Arrival Time
Waiting time: - It is the sum of time periods spent in the ready queue by a process. It is
calculated as: Waiting Time = TurnAroundTime-Burst Time
Response time:-The time period from the submission of a request until the first response is
produced is called as response time.

Q5. Explain the pre-emptive and non-preemptive type of scheduling.

Pre-emptive Scheduling:-Even if CPU is allocated to one process, CPU can be preempted
to other process if other process is having higher priority or some other fulfilling criteria.
 Throughput is less
 Only the processes having higher priority are scheduled.
 It doesn’t treat all processes as equal.
 Algorithm design is complex.

Circumstances for preemptive

 Process switch from running to ready state
 Process switch from waiting to ready state
For e.g.: Round Robin, Priority algorithms
Non-Preemptive Scheduling
Once the CPU has been allocated to a process the process keeps the CPU until it releases
CPU either by terminating or by switching to waiting state.
 Throughput is high.
 It is not suitable for RTS.
 Processes having any priority can get scheduled.
 It treats all process as equal.
 Algorithm design is simple.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

Circumstances for Non preemptive
 Process switches from running to waiting state
 Process terminates
For e.g.: FCFS algorithm It is suitable for RTS.

Differentiate between pre-emptive and non-pre-emptive scheduling (any 4 points)

Basis for
heduling Non Preemptive Scheduling
Comparison
Once resources are allocated to a
The resources are allocated to a process, the process holds it till it
Basic
process for a limited time. completes its burst time or switches to
waiting state.
Process can be interrupted in Process can not be interrupted till it
Interrupt
between. terminates or switches to waiting state.
If a high priority process
If a process with long burst time is
frequently arrives in the ready
Starvation running CPU, then another process with
queue, low priority process may
less CPU burst time may starve.
starve.
Preemptive scheduling has
Non-preemptive scheduling does not
Overhead overheads of scheduling the
have overheads.
processes.
Flexibility Preemptive scheduling is flexible. Non-preemptive scheduling is rigid.
Preemptive scheduling is cost Non-preemptive scheduling is not cost
Cost
associated. associative.
For e.g.: Round Robin,
Example For e.g.: FCFS Algorithm
Priority Algorithms

 Completion Time: Time at which process completes its 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

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

Explain first come first served (FCFS) algorithm. Give one example. State any one
advantages and one disadvantage.
First-Come - First-Served (FCFS) Scheduling FCFS scheduling is non preemptive algorithm.
 Once the CPU is allocated to a process, it keeps the CPU until it releases the CPU,
either by terminating or by requesting I/O.
 In this algorithm, a process, that a request the CPU first, is allocated the CPU first.
FCFS scheduling is implemented with a FIFO queue.
 When a process enters the ready queue, its PCB is linked to the tail of the queue.
 When the CPU is available, it is allocated to the process at the head of the queue.
Once the CPU is allocated to a process, that process is removed from the queue.
 The process releases the CPU by its own.
Example:

Suppose that the processes arrive in the order: P1, P2, P3 Gantt Chart:

Average waiting time: (0 + 24 + 27)/3 = 17

Average turnaround time: (24 + 27 + 30)/3 = 27

Advantage:
It is simple to implement.

Disadvantage:

 This scheduling method is non preemptive, that is, the process will run until it
finishes. Because of this non preemptive scheduling, short processes which are at the
back of the queue have to wait for the long process at the front to finish.
 It is not suitable for real time systems.
 Average waiting time and average turnaround time is more comparatively.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
Example: Consider the following table:

Process no. Arrival Time Burst Time

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

Find the average waiting time and average turn arround time using FCFS algorithm?

Solution:

Using FCFS process scheduling algorithm, gantt chart is:

Therefore,

Waiting Turn Completion Process Arrival Burst

Time Around Time No. Time Time
Time
6-6=0 6-0=6 6 P1 0 6
5-1=4 7-2=5 7 P2 2 1
7-4=3 11 - 4 = 7 11 P3 4 4
9-3=6 14 - 5 = 9 14 P4 5 3

Average Turn Arround Time = (6 + 5 + 7 + 9) / 4 = 6.75

Average Waiting Time = (0 + 4 + 3 + 6) / 4 = 3.25

PROCESS ARRIVAL BURST TIME

TIME
P1 0 24
P2 0 3
P3 0 3

Gantt chart

P1 P2 P3
0 24 27 30

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

PROCESS WAIT TIME TURN AROUND
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

In the above example, if order of process arriving is p2, p3, p1 instead of p1, p2, p3 then

Gantt chart

P2 P3 P1
0 3 6 30

PROCESS WAIT TIME TURN AROUND

TIME
P1 6 30
P2 0 3
P3 3 6

Total Wait Time

6 + 0 + 3 = 9 ms

Average Waiting Time = (Total Wait Time) / (Total number of processes)

9/3 = 3 ms

Total Turn Around Time

30 + 3 + 6 = 39 ms

Average Turn Around time = (Total Turn Around Time) / (Total number of processes)
39 / 3 = 13 ms

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

PROCESS ARRIVAL TIME BURST TIME
P1 0 80
P2 0 20
P3 0 10
P4 0 20
P5 0 50

Gantt chart

P1 P2 P3 P4 P5
0 80 100 110 130 180

PROCESS WAIT TIME TURN AROUND

TIME
P1 0 80
P2 80 100
P3 100 110
P4 110 130
P5 130 180

Total Wait Time

0 + 80 + 100 + 110 + 130 = 420 ms

Average Waiting Time = (Total Wait Time) / (Total number of processes)

420/5 = 84 ms

Total Turn Around Time

80 + 100 + 110 + 130 + 180 = 600 ms

Average Turn Around time = (Total Turn Around Time) / (Total number of processes)
600/5 = 120 ms

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

PROCESS ARRIVAL TIME SERVICE 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

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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 notknown.
 The processer should know in advance how much time process will take.
 Pre-emptive mode of Shortest Job First is called as Shortest Remaining
TimeFirst (SRTF).

Advantages-
 SRTF is optimal and guarantees the minimum average waiting time.
 It provides a standard for other algorithms since no other algorithm
performsbetter than it.

Disadvantages-
 It can not be implemented practically since burst time of the processes
can notbe 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.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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,

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

 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

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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 repeatthe cycle
many times.
Its performance heavily depends on time quantum.
Priorities can not be set for the processes.

With decreasing value of time quantum,

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

With increasing value of time quantum, Round Robin Scheduling tends tobecome
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 toosmall.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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, calculatethe
average waiting time and average turnaround time.

Solution-
Ready Queue- P5, P1, P2, P5, P4, P1, P3, P2, P1
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:

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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 averagewaiting
time and average turnaround time.

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

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 aregiven

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

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
If the CPU scheduling policy is Round Robin with time quantum = 3, calculate theaverage
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
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

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

Multilevel Queue Scheduling
Another class of scheduling algorithms has been created for situations in which processes are easily
classified into different groups.
For example:
 A common division is made between foreground(or interactive) processes and background (or
batch) processes.
 These two types of processes have different response-time requirements, and so might have
different scheduling needs. In addition, foreground processes may have priority over background
processes.
 A multi-level queue scheduling algorithm partitions the ready queue into several separate queues.
The processes are permanently assigned to one queue, generally based on some property of the
process, such as memory size, process priority, or process type.
 Each queue has its own scheduling algorithm.
For example: separate queues might be used for foreground and background processes. The foreground
queue might be scheduled by Round Robin algorithm, while the background queue is scheduled by an
FCFS algorithm.
In addition, there must be scheduling among the queues, which is commonly implemented as fixed-
priority preemptive scheduling. For example: The foreground queue may have absolute priority over the
background queue.

Let us consider an example of a multilevel queue-scheduling algorithm with five queues:

1. System Processes
2. Interactive Processes
3. Interactive Editing Processes
4. Batch Processes
5. Student Processes

 Each queue has absolute priority over lower-priority queues.

 No process in the batch queue, for example, could run unless the queues for system processes,
interactive processes, and interactive editing processes were all empty.
 If an interactive editing process entered the ready queue while a batch process was running, the
batch process will be preempted.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

Define deadlock.
 Deadlock is a situation where a set of processes are blocked because each process isholding a
resource and waiting for another resource acquired by some other process.
 For example, in the below diagram, Process 1 is holding Resource 1 and waiting forresource 2
which is acquired by process 2, and process 2 is waiting for resource 1.

Example:

 Here the road is the resource required by cars and cars getting to the other side of the road can be
considered a process.
 Now, none of the cars can move further and have entered a waiting state.
 As it is a one-way road, both cars cannot move forward at the same time.
 We can say that the road is a single instance resource (only one unit of resource is available).

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge



Describe any four condition for deadlock.

1. Mutual exclusion: Only one process at a time can use non-sharable resource.
2. Hold and wait: A process is holding at least one resource and is waiting to acquire additional resources
held by other processes.
3. No pre-emption:
 A resource can be released only willingly by the process holding it after that process completes its
task.
 No Context Switching
4. Circular wait: There exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a
resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a
resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

List four Deadlock prevention condition and explain the following terms.

1) Removal of “No preemption” condition.

2) Elimination of “Circular wait” related to deadlock prevention condition.

3) Eliminating Mutual Exclusion Condition

4) Eliminating Hold and Wait Condition

Deadlock prevention conditions:-

1. Preventing Mutual exclusion condition

2. Preventing Hold and wait condition

3. Preventing No preemption condition

4. Preventing Circular wait condition

Deadlocks can be prevented by preventing at least one of the four required conditions:

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

1. Deadlock Prevention
 Deadlocks can be prevented by preventing at least one of the four required
conditions:
Mutual Exclusion
 All resources are in shared mode then do not lead to deadlocks.
 Shared resources such as read-only files
 Unfortunately, some resources, such as printers and tape drives, require exclusive
access by a single process.
Hold and Wait
 To prevent this condition processes must be prevented from holding one or more resources
while simultaneously waiting for one or more others.
No Preemption
 Preemption of process resource allocations can prevent this condition of deadlocks,when it is
possible.
Circular Wait
 One way to avoid circular wait is to number all resources, and to require that processesrequest
resources only in strictly increasing ( or decreasing ) order

Q.Explain Deadlock Avoidance with example.

 Most prevention algorithms have poor resource utilization, and hence result in reduced
throughputs.
 Instead, we can try to avoid deadlocks by making use prior knowledge about the usage of
resources by processes including resources available, resources allocated, future requests and
future releases by processes.
 Most deadlock avoidance algorithms need every process to tell in advance the maximum number
of resources of each type that it may need.
 Based on all this info we may decide if a process should wait for a resource or not and thus avoid
chances for circular wait.

Banker’s Algorithm:
 This algorithm calculates resources allocated, required and available before allocating resources to
any process to avoid deadlock.
 It contains two matrices on a dynamic basis. Matrix A contains resources allocated to different
processes at a given time.
 Matrix B maintains the resources which are still required by different processes at the same time.
 Algorithm F: Free resources
Step 1: When a process requests for a resource, the OS allocates it on a trial basis.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

Step 2: After trial allocation, the OS updates all the matrices and vectors. This updating can be done by
the OS in a separate work area in the memory.
Step 3: It compares F vector with each row of matrix B on a vector to vector basis.
Step 4: If F is smaller than each of the row in Matrix B i.e. even if all free resources are allocated to any
process in Matrix B and not a single process can complete its task then OS concludes that the system is in
unstable state.
Step 5: If F is greater than any row for a process in Matrix B the OS allocates all required resources for
that process on a trial basis. It assumes that after completion of process, it will release all the recourses
allocated to it. These resources can be added to the free vector.
Step 6: After execution of a process, it removes the row indicating executed process from both matrices.
Step 7: This algorithm will repeat the procedure step 3 for each process from the matrices and finds that
all processes can complete execution without entering unsafe state. For each request for any resource by a
process OS goes through all these trials of imaginary allocation and updation. After this if the system
remains in the safe state, and then changes can be made in actual matrices.

Deadlock Detection
 Detection and Recovery: If deadlocks do occur, the operating system must detect and resolve them.
Deadlock detection algorithms, such as the Wait-For Graph, are used to identify deadlocks, and
recovery algorithms, such as the Rollback and Abort algorithm, are used to resolve them. The
recovery algorithm releases the resources held by one or more processes, allowing the system to
continue to make progress.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge
Important Questions
Question for 2 Marks
1 Define Deadlock.
2 List Different types of CPU scheduling algorithm.
3 State two features of preemptive scheduling.
4 State different scheduling criteria.
Question for 4 Marks
1 Explain FCFS scheduling algorithm with example.
2 Explain SJF scheduling algorithm with example.
3 Explain Priority scheduling algorithm with example.
4 Explain Round Robin scheduling algorithm with example.
5 Describe Deadlock Prevention and Avoidance.
6 Explain deadlock? What are necessary conditions for deadlock?
7 Describe CPU burst cycle and I/O burst cycle.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge

Assignment No:04
Question for 2 Marks
1. Define Deadlock.
2. List Different types of CPU scheduling algorithm.
3. State two features of preemptive scheduling.
4. State different scheduling criteria.
5. List the scheduling algorithms
Questions for 4 Marks
1. Explain Priority scheduling algorithm with example.
2. Explain Round Robin scheduling algorithm with example.
3. Describe Deadlock Prevention and Avoidance.
4. Explain deadlock? What are necessary conditions for deadlock?
5. Describe CPU burst cycle and I/O burst cycle.

CPU SCHEDULING & ALGORITHMS | Mr. C. R. Ghuge