Unit 4: CPU Scheduling and Algorithms

Q.1] What is CPU Scheduling

CPU Scheduling:
CPU Scheduling is a process of determining which process
will own CPU for execution while another process is on hold.
Q.2] What is Scheduling Objectives
Scheduling Objectives:
1. Maximize throughput.
2. Maximize number of users receiving acceptable response times.
3. Be predictable
4. Balance resource use.
5. Avoid indefinite postponement.
6. Enforce Priorities.
Q.3] CPU and I/O Burst Cycle
CPU Burst Cycle:
A CPU burst is a period when a process is actively executing
instructions on the CPU.
I/O Burst Cycle:
An I/O burst occurs when a process is waiting for input or
output operations to complete.
Q.4] Describe different scheduling criteria.
1. CPU utilization:
The main objective of any CPU scheduling algorithm is to
keep the CPU as busy as possible. Theoretically, CPU utilisation can range from
0 to 100 but in a real-time system, it varies from 40 to 90 percent depending on
the load upon the system.
2. Throughput:
A measure of the work done by CPU is the number of processes
being executed and completed per unit time. This is called throughput. The
throughput may vary depending upon the length or duration of processes.
3. Turnaround time:
For a particular process, an important criteria is how long it
takes to execute that process. The time elapsed from the time of submission of a
process to the time of completion is known as the turnaround time. Turn-around
time is the sum of times spent waiting to get into memory, waiting in ready queue,
executing in CPU, and waiting for I/O.
Turn Around Time = Completion Time – Arrival Time.
4. Waiting time:
A scheduling algorithm does not affect the time required to
complete the process once it starts execution. It only affects the waiting time of a
process i.e. time spent by a process waiting in the ready queue.
Waiting Time = Turnaround Time – Burst Time.
5. Response time:
In an interactive system, turn-around time is not the best
criteria. A process may produce some output fairly early and continue computing
new results while previous results are being output to the user. Thus, another
criteria is the time taken from submission of the process of request until the first
response is produced. This measure is called response time
Response Time = CPU Allocation Time(when the CPU
was allocated for the first) – Arrival Time
6. Completion Time
The completion time is the time when the process stops executing, which
means that the process has completed its burst time and is completely executed.
 Important Criteria:
1] Arrival Time:
The specific time at which a process is submitted to the system
and becomes ready for execution.
2] Burst Time:
The total amount of time a process requires on the CPU to
complete its execution, from start to finish.
Q.5] Explain types of Scheduling Algorithm
Types of Scheduling Algorithm:
1. First Come First Serve (FCFS)
2. Shortest Job First (SJF)
3. Priority Scheduling
4. Round Robin Algorithm
1] FCFS Algorithm:
▪ FCFS is a Non Preemptive algorithm.
▪ It is easy to implement for CPU scheduling.
▪ The process which requests first is allocated to CPU first.
▪ When Process enters for processing its PCB is connected to ready queue.
▪ Jobs are executed on first come, first serve basis.
▪ Easy to understand and implement.
▪ Its implementation is based on FIFO queue.
▪ Poor in performance as average wait time is high.
Characteristics of FCFS:

1. FCFS executes processes in the order they arrive.

2. It is a non-preemptive scheduling algorithm.
3. Waiting time can vary significantly based on arrival order.
4. The algorithm does not prioritize any process over another.
5. It is straightforward and easy to implement.
6. The average waiting time can be high, especially with long processes.

Advantages of FCFS:
1. FCFS is easy to implement and understand.
2. It promotes fairness by serving processes in arrival order.
3. The algorithm prevents starvation, ensuring all processes run.
 4. The execution order is predictable, aiding performance analysis.
Disadvantages of FCFS:
1. It can cause the convoy effect, leading to inefficiencies.
2. Average waiting times are often high, especially with long processes.
3. FCFS is non-preemptive, so processes cannot be interrupted.
4. It is not suitable for time-sharing systems needing quick responses.
Example:

2] SJF Algorithm:
▪ Process which has 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)

Characteristics of SJF:

1. SJF executes processes with the shortest burst time first.

2. It can be preemptive or non-preemptive.
3. The algorithm minimizes average waiting and turnaround times.
4. Longer processes may be delayed if shorter ones keep arriving.
5. Accurate burst time estimation is crucial for scheduling.
6. It can lead to starvation for longer processes.

Example:
Example:

Advantages of SJF:
1. SJF minimizes average waiting time.
2. It optimizes turnaround time for arriving processes.
3. Shorter processes are prioritized, improving responsiveness.
4. The algorithm is simple to implement.
Disadvantages of SJF:
1. It can cause starvation for longer processes.
2. Estimating burst times accurately is difficult.
3. SJF is non-preemptive, preventing interruption of running processes.
4. It may struggle with mixed workloads of short and long processes.
3] Priority Scheduling:
▪ Priority scheduling is a non-preemptive algorithm and one of the most
common scheduling algorithms in batch systems.
▪ Each process is assigned a priority. Process with highest priority is to be
executed first and so on.
▪ Processes with same priority are executed on first come first served basis.
▪ Priority can be decided based on memory requirements, time requirements
or any other resource requirement

Characteristics of Priority Scheduling:

1. Priority scheduling executes processes based on their priority levels.

2. It can be either preemptive or non-preemptive.
3. Higher priority processes are served before lower-priority ones.
4. Priorities can be static or dynamic, affecting scheduling.
5. It can lead to starvation for low-priority processes.
6. The algorithm requires careful design to maintain fairness

Advantages of Priority Scheduling:

1. Priority scheduling executes important tasks first.

2. It improves resource utilization for critical processes.
3. The algorithm can be tailored to specific system needs.
4. It helps time-sensitive tasks meet their deadlines.

Disadvantages of Priority Scheduling:

1. It can cause starvation for low-priority processes.

2. Setting appropriate priorities can be complex.
3. Higher priority processes may monopolize CPU time.
4. Dynamic priority changes can complicate scheduling
Example:

4] Round Robin Algorithm:

▪ It is preemptive scheduling algorithm. A small unit of time known as a time
quantum or time slice is used for pre-emption of a currently running
process. Ready queue is implemented as a circular queue.
▪ CPU is assigned to the entire processes one by one, on first come first serve
basis, for a specific time period. Every process executes for specified time
period and CPU is given to the next process when time quantum expires.
A new process is added at the tail of the ready queue when it enters the
system.
▪ CPU scheduler selects first process from head of the ready queue and
executes it for a specified time quantum. Once the time quantum expires,
dispatcher is invoked to pre-empt current running process and CPU is
given to the next process placed at the head of the ready queue.
▪ If burst time of running process is longer than time quantum then, context
switch occurs and the process is place at the tail of ready queue for
remaining burst time execution.
Characteristics:
1. Round Robin allocates a fixed time slice (quantum) to each process.
2. It operates in a cyclic manner, moving to the next process when the time
expires.
3. The algorithm is preemptive, allowing interruptions of running processes.
4. It improves responsiveness in time-sharing systems.
5. The choice of time quantum impacts performance.
6. All processes receive equal CPU time, preventing starvation
Advantages of Round Robin Algorithm:
1. Round Robin ensures fair CPU time allocation.
2. It improves response time for interactive tasks.
3. The fixed time quantum is easy to implement.
4. It prevents starvation by allowing all processes to run.
Disadvantages of Round Robin Algorithm:
1. Very small-time quanta can lead to high context switching overhead.
2. Longer processes may face increased turnaround time.
3. Choosing the optimal time quantum can be challenging.
4. Frequent context switches can reduce overall system efficiency.
Example:
Q.6] Explain deadlock? What are necessary conditions for deadlock?
Deadlock:
A deadlock is a situation where a set of processes is blocked
because each process is holding a resource and waiting for another resource
acquired by some other process.
Deadlock condition
1. Mutual Exclusion:
One or more than one resource are non-sharable means
Only one process can use at a time. In the diagram below, there is a single
instance of Resource 1 and it is held by Process 1 only.

2. Hold and Wait:

A process is holding at least one resource and waiting for
another resources. In the diagram given below, Process 2 holds Resource 2
and Resource 3 and is requesting the Resource 1 which is held by Process
1.

3. No Pre-emption:
The process which once scheduled will be executed till
the completion. No other process can be scheduled by the scheduler
meanwhile. In the diagram below, Process 2 cannot preempt Resource 1
from Process 1. It will only be released when Process 1 relinquishes it
voluntarily after its execution is complete.
 4. Circular Wait:
All the processes must be waiting for the resources in a
cyclic manner so that the last process is waiting for the resource which is
being held by the first process. For example: Process 1 is allocated
Resource2 and it is requesting Resource 1. Similarly, Process 2 is allocated
Resource 1 and it is requesting Resource 2. This forms a circular wait loop.

Advantages of Deadlock:
1. Effective resource usage until resolved.
2. Simplifies resource management.
3. Maintains process consistency.
4. Allows prioritization of critical tasks.
Disadvantages of Deadlock:
1. Causes indefinite process blocking.
2. Increases system complexity.
3. Leads to resource starvation.
4. Difficult to identify and resolve.

Q.7] Explain Deadlock Handling:

Deadlock handling in operating systems refers to the
techniques and strategies used to manage situations where processes are unable
to continue because they are each waiting for resources held by one another.
Q.8] Explain Methods of Handling Deadlocks
Methods of Handling Deadlocks
1. Deadlock Prevention
2. Deadlock Avoidance
1] Deadlock Prevention:
Deadlock prevention is a strategy aimed at ensuring that
deadlock situations never occur by eliminating one or more of the necessary
conditions for deadlock.
Describe conditions for deadlock prevention.
1. No Mutual Exclusion
2. No Hold and Wait
3. Removal of No Preemption
4. Removal of Circular Wait
1. No Mutual Exclusion:
It means more than one process can have access to
a single resource at the same time. It’s impossible because if multiple
processes access the same resource simultaneously, there will be chaos.
Additionally, no process will be completed. So, this is not feasible. Hence,
the OS can’t avoid mutual exclusion.
2. No Hold and Wait:
To avoid the hold and wait, there are many ways to
acquire all the required resources before starting the execution. But this is
also not feasible because a process will use a single resource at a time.
Here, the resource utilization will be very less.
Before starting the execution, the process does not
know how many resources would be required to complete it. In addition to
that, the bus time, in which a process will complete and free the resource,
is also unknown.
3. Removal of No Preemption:
One of the reasons that cause the deadlock is
the no preemption. It means the CPU can’t take acquired resources from
any process forcefully even though that process is in a waiting state. If we
can remove the no preemption and forcefully take resources from a waiting
process, we can avoid the deadlock. This is an implementable logic to
avoid deadlock.
 4. Removal of Circular Wait:
In the circular wait, two processes are stuck in
the waiting state for the resources which have been held by each other. To
avoid the circular wait, we assign a numerical integer value to all resources,
and a process has to access the resource in increasing or decreasing order.
If the process acquires resources in increasing order,
it’ll only have access to the new additional resource if that resource has a
higher integer value.
Advantages of Deadlock Prevention:
1. Eliminates the possibility of deadlocks, ensuring reliability.
2. Simplifies system design with strict resource allocation.
3. Provides predictable resource usage.
4. Improves performance by avoiding resolution costs.

Disadvantages of Deadlock Prevention:

1. May lower resource utilization due to longer wait times.
2. Introduces complexity in resource allocation.
3. Restricts process flexibility with strict protocols.
4. Can create unnecessary overhead, impacting performance.
2] Deadlock Avoidance:
Deadlock Avoidance is a process used by the Operating
System to avoid Deadlock.
▪ The deadlock Avoidance method is used by the operating system in order
to check whether the system is in a safe state or in an unsafe state and in
order to avoid the deadlocks, the process must need to tell the operating
system about the maximum number of resources a process can request in
order to complete its execution.
▪ The Deadlock Avoidance Algorithm is designed to minimize the chances
of a deadlock occurring, although it cannot guarantee that a deadlock will
never occur.
Two techniques to avoid deadlock:
1. Process initiation denial
2. Resource allocation denial
Advantages of Deadlock Avoidance:
1. Enables efficient, dynamic resource allocation.
2. Adapts to varying workloads for flexibility.
3. Enhances performance in resource contention scenarios.
4. Reduces the likelihood of indefinite blocking.
Disadvantages of Deadlock Avoidance:
1. Requires detailed prior knowledge of resource needs.
2. Involves complex and costly algorithms.
3. Increases overhead for continuous monitoring.
4. May still allow temporary deadlocks if not managed.