Operating Systems Internal designs and Principles ACSC404

Module-2
Types of process scheduling: Long-term scheduling, short-term scheduling, medium-
term scheduling. Scheduling algorithms: FCFS, SJF, Round Robin, Priority, SPN, SRT,
and HRRN Feedback. T2: Chapter 9 (Sections 9.1, 9.2)

Chapter 9
Uniprocessor Scheduling
The primary goal of scheduling is the efficient allocation of processor time to processes. This is done
to satisfy specific performance criteria:
● Response Time: Minimizing the delay for interactive users.
● Throughput: Maximizing the number of processes completed over time.
● Processor Efficiency: Keeping the CPU busy as much as possible.

Scheduling activity is broken down into as follows:

1. Long-Term Scheduling (LTS)
The "gatekeeper" of the system, determining which programs are admitted and converted into active
processes.
● Main Function: Controls the degree of multiprogramming (how many processes are active
at once).
● Admission Decisions:
○ When: Usually triggered when a job terminates or when processor idle time exceeds
a certain threshold.
○ Which: Based on FCFS (First-Come-First-Served) or performance criteria like
priority, expected execution time, and I/O requirements.
● Strategy: It aims for a balanced mix of processor-bound and I/O-bound processes to keep
all system resources busy.
● Interactive Systems: Instead of queuing users, the system typically accepts all authorized
users until a "saturation" point is reached, then rejects new connections.

2. Medium-Term Scheduling (MTS)

This function is integrated with the swapping mechanism of the operating system.
● Main Function: Manages the degree of multiprogramming and memory by deciding which
processes to move between main memory and the disk (swapped-out state).
● Context: Especially critical in systems without virtual memory to ensure enough physical
memory is available for executing processes.

3. Short-Term Scheduling (The Dispatcher)

The most frequently executed scheduler, making millisecond-by-millisecond decisions.
● Main Function: Selects which "Ready" process will be executed by the CPU next.

EWIT
1
Operating Systems Internal designs and Principles ACSC404

● Triggers: Invoked by events that might block the current process or allow for preemption,
such as:
○ Clock interrupts (time-slice expiration).
○ I/O interrupts.
○ Operating system calls.
○ Signals (like semaphores).

Summary Comparison Table

Scheduler Frequency Key Decision

Long-Term Infrequent Which programs become processes? (Admission)

Medium-Term Moderate Which processes stay in main memory? (Swapping)

Short-Term Very Frequent Which process gets the CPU right now? (Dispatching)

Scheduling Algorithm:
Short-term scheduling criteria:These are used to decide how CPU time should be given to
processes so that the system performs well. These criteria are classified in two ways:

EWIT
2
Operating Systems Internal designs and Principles ACSC404

1. User-oriented criteria
These focus on what the user experiences.
Example: response time — the time between submitting a request and seeing the first output.
Goal: give users fast and satisfactory service.
2. System-oriented criteria
These focus on overall system efficiency.
Example: throughput — the number of processes completed in a given time.
Goal: use the processor effectively and complete more work.

3. Performance-related criteria
These are measurable and quantitative.
Examples: response time, throughput, processor utilization.

4. Non-performance-related criteria
These are qualitative and harder to measure.
Example: predictability — the system should behave consistently over time, even when workload
changes

The Use of Priorities:

In many operating systems, each process is assigned a priority level. The CPU scheduler always
selects the process with the highest priority for execution. Instead of one ready queue, the system
may maintain multiple ready queues arranged by priority, such as:

RQ₀ (highest priority)

RQ₁
RQ₂
…
RQₙ (lowest priority)

When scheduling occurs:

1. The scheduler first checks the highest-priority queue (RQ₀).
2. If it contains processes, one process is selected using a scheduling policy.
3. If it is empty, the scheduler checks the next lower priority queue, and so on.

Drawbacks:
● A drawback of pure priority scheduling is starvation.

EWIT
3
Operating Systems Internal designs and Principles ACSC404

● This happens when low-priority processes never get CPU time because higher-priority
processes keep arriving.
● To prevent starvation, the system may change priorities over time.
For example, the priority of a process may increase as it waits longer in the system (called
aging).

Alternative Scheduling Policies:

Scheduling algorithms choose the next process using a selection function. This function may depend
on:
● Priority of the process
● Resource requirements
● Execution characteristics

Three important time values are used:

● w = time the process has been waiting in the system

● e = time the process has already executed
● s = total service time required by the process (usually estimated)

Example:

max[w] → means the process that has waited the longest is selected, which corresponds to FCFS
scheduling.
The decision mode determines when the scheduling algorithm selects the next process to run. It
specifies the points in time when the selection function is applied. There are two main types:

1. Non-Preemptive Scheduling

● Once a process enters the Running state, it continues executing until:

○ The process terminates, or
○ The process blocks itself (e.g., waiting for I/O or requesting an OS service).
● The CPU cannot be taken away from the running process by the operating system.

Advantages

● Simple to implement
● Low overhead (fewer context switches)

Disadvantages

● A long process may keep the CPU for a long time

● Poor response time for short or interactive processes

2. Preemptive Scheduling

● The operating system can interrupt a running process and move it back to the Ready state.

EWIT
4
Operating Systems Internal designs and Principles ACSC404

● Preemption may occur when:

○ A new process arrives
○ An interrupt occurs that makes a blocked process ready
○ A clock interrupt periodically forces rescheduling
Advantages:
● Prevents one process from monopolizing the CPU
● Provides better responsiveness, especially in interactive systems
Disadvantages:
● Higher overhead due to context switching
However, the overhead can be reduced by:
● Efficient process-switching mechanisms
● Hardware support for context switching
● Large main memory so more programs stay in memory

Key Terms:
● Service Time(s): It refers to the total CPU time required by a [Link] batch jobs, it
represents the total execution [Link] interactive systems, it may represent CPU time required
for one processing cycle.

● Turnaround Time (TAT): Turnaround time is the total time a process spends in the system.
TAT=Waiting Time+Service Time
In queueing theory, it is also called residence time (Tr).
● Normalized Turnaround Time: It measures the relative delay experienced by a
process.
Normalized TAT=Service Time Turn around Time

● Minimum value = 1.0 (best case)

● Larger values indicate greater delay
● Longer processes can tolerate more delay, so normalized turnaround time
helps fairly compare different processes.

First-Come-First-Served (FCFS) Scheduling

FCFS is the simplest CPU scheduling algorithm. It is also called:
● FIFO (First-In-First-Out)
● Strict queue scheduling
Working Principle
● Processes are executed in the order in which they arrive in the ready queue.
● When a process becomes ready, it is placed at the end of the ready queue.
● The scheduler always selects the process that has been waiting the longest.

Thus, the first process that enters the ready queue is the first one to run.
Example:
Suppose processes arrive in this order:

EWIT
5
Operating Systems Internal designs and Principles ACSC404

P1 → P2 → P3
Execution order will be:
P1 → P2 → P3
No process can interrupt another once it starts running. Therefore, FCFS is a non-preemptive
scheduling algorithm.

Advantages of FCFS

● Very simple to understand and implement

● Requires minimal scheduling overhead
● Fair in terms of arrival order

Disadvantages of FCFS
1. Convoy Effect (Problem for Short Processes)
FCFS performs better for long processes than short processes.
If a long process arrives first, all short processes must wait behind it.
Example:
If a long job runs first, short jobs that arrive later experience very large waiting and turnaround times.
This leads to poor service for short jobs.
2. Large Normalized Turnaround Time
Short processes may experience a very high normalized turnaround time, meaning they wait much
longer compared to their actual execution time.
3. Poor Handling of I/O-Bound Processes
FCFS tends to favor CPU-bound processes over I/O-bound processes.
Consider:
● One CPU-bound process (uses CPU heavily)
● Many I/O-bound processes (frequently perform I/O)
When the CPU-bound process runs:
● I/O-bound processes must wait in the ready queue
● Many I/O devices may remain idle
Later:
● I/O-bound processes quickly execute and block for I/O again
● If all processes are waiting for I/O, the CPU becomes idle
Thus FCFS may cause inefficient utilization of CPU and I/O devices. Because of these problems,
FCFS alone is not an ideal scheduling policy for a uniprocessor system. However, it is often used in
combination with priority scheduling.
Example:
● The system maintains multiple priority queues
● Each queue uses FCFS internally

Shortest Job First (SJF)

Shortest Job First (SJF)is a CPU scheduling algorithm in which the process with the smallest
CPU burst time is selected for execution first.

EWIT
6
Operating Systems Internal designs and Principles ACSC404

● It is mainly a non-preemptive scheduling algorithm.

● The scheduler selects the process that requires the least amount of CPU time.
● It helps in reducing the average waiting time among processes.

Process Arrival Time Burst Time

P1 0 6

P2 0 2

P3 0 8

P4 0 3

Since all processes arrive at the same time, the scheduler selects the shortest burst time first.

Execution Order

Burst times: 2, 3, 6, 8

Order:
P2 → P4 → P1 → P3

| P2 | P4 | P1 | P3 |
0 2 5 11 19

Process Waiting Time

P2 0

P4 2

P1 5

P3 11

Average Waiting Time=40+2+5+11=4.5

Advantages of SJF
1. Minimum Average Waiting Time compared to many scheduling algorithms.
2. Efficient for batch processing systems.
3. Short processes are completed quickly.
4. Improves system throughput.

Disadvantages of SJF
1. Starvation Problem
Long processes may wait indefinitely if short processes keep arriving.

EWIT
7
Operating Systems Internal designs and Principles ACSC404

2. Difficult to Predict Burst Time

The system must know the CPU burst time in advance, which is often not possible.
3. Not Suitable for Interactive Systems
It may delay important processes.
4. Implementation Complexity
Maintaining the shortest job order requires additional overhead.

Round Robin (RR) Scheduling:

Round Robin (RR) is a preemptive CPU scheduling algorithm designed to reduce the waiting time of
short processes in FCFS scheduling.

It uses clock-based preemption:

● A clock interrupt occurs at regular intervals.

● Each process receives a fixed time quantum (time slice).
● When the time quantum expires, the running process is preempted and moved to the end of
the ready queue.
● The next process in the queue is selected using FCFS order.

Because each process gets only a limited time, this technique is called time slicing.

Working Principle

1. Processes enter the ready queue.

2. The first process runs for a fixed time quantum (q).
3. If the process finishes within the quantum → it leaves the system.
4. If it does not finish → it is preempted and placed at the end of the queue.
5. The next process gets the CPU.

Example: P1 → P2 → P3 → P1 → P2 → P3

EWIT
8
Operating Systems Internal designs and Principles ACSC404

The time quantum (q) is the most important parameter in Round Robin scheduling.
If the quantum is very small
● Short processes finish quickly
● But many context switches occur
● Leads to high overhead
If the quantum is very large
● Preemption rarely happens
● RR behaves like FCFS
Therefore, the quantum should be slightly larger than the average CPU burst time.
Advantages of Round Robin

● Provides fair CPU sharing

● Prevents any process from monopolizing the processor
● Good response time
● Suitable for time-sharing systems

Disadvantages of Round Robin

1. Context Switching Overhead: Frequent clock interrupts cause many context switches, increasing
overhead.

2. Unfairness between CPU-bound and I/O-bound processes: Round Robin may treat processes
differently depending on their behaviour

CPU-bound processes: Use the entire time quantum and Immediately return to the ready queue
I/O-bound processes: Use the CPU briefly and Quickly block for I/O

As a result:

● CPU-bound processes get more CPU time

● I/O devices may remain underutilized
● Response time may vary significantly

Virtual Round Robin (VRR): To improve fairness, a modified version called Virtual Round Robin
(VRR) is used. An auxiliary queue is added.

Process movement:

1. New processes enter the main ready queue.

2. If a process blocks for I/O, it goes to the I/O queue.
3. When I/O completes, the process goes to the auxiliary queue instead of the ready queue.
4. The scheduler gives priority to the auxiliary queue.

Execution Rule: A process from the auxiliary queue runs only for the remaining portion of its time
quantum.

EWIT
9
Operating Systems Internal designs and Principles ACSC404

Example:

Time quantum = 4
Process used 1 unit before I/O → remaining quantum = 3

It runs for 3 units when returning from I/O.

VRR improves: Fairness and Performance for I/O-bound processes

Round Robin works best in:Time-sharing systems, Interactive systems & Transaction processing
systems

Priority Scheduling

Priority Scheduling is a CPU scheduling algorithm in which each process is assigned a priority.
The CPU is allocated to the process with the highest priority first.

● Higher priority processes execute before lower priority ones.

EWIT
10
Operating Systems Internal designs and Principles ACSC404

● Priority can be assigned internally (by the system) or externally (by the user).

● It can be preemptive or non-preemptive.

Process Burst Time Priority

P1 10 3

P2 1 1

P3 2 4

P4 1 2

(Assume smaller number = higher priority)

Execution Order

Priority order:

1→2→3→4

So the order becomes:

P2 → P4 → P1 → P3

Gantt Chart
| P2 | P4 | P1 | P3 |
0 1 2 12 14

Process Waiting Time

P2 0

EWIT
11
Operating Systems Internal designs and Principles ACSC404

P4 1

P1 2

P3 12

Average WT=40+1+2+12=3.75

Advantages
1. Important processes are executed first.
2. Suitable for real-time systems.
3. Provides flexibility by assigning priorities based on importance.
4. Improves system control over task execution.

Disadvantages

1. Starvation Problem
Low-priority processes may wait indefinitely.

2. Priority Inversion
A low-priority process may hold resources needed by a high-priority process.

3. Complex Priority Assignment

Determining correct priorities is difficult.

Shortest Process Next (SPN) Scheduling

Shortest Process Next (SPN) is a non-preemptive CPU scheduling algorithm.

● The scheduler selects the process with the shortest expected processing time.
● Short processes are allowed to jump ahead of longer processes in the ready queue.

This policy is also commonly known as Shortest Job First (SJF).

Working Principle

1. All ready processes are examined.

2. The process with the smallest predicted execution time is selected.
3. Once it starts running, it continues until completion (no preemption).

Example queue:

Process Burst Time

P1 8

EWIT
12
Operating Systems Internal designs and Principles ACSC404

P2 4

P3 2

Execution order:

P3 → P2 → P1

Advantages of SPN
1. Reduces bias of FCFS: Unlike FCFS, short jobs do not wait behind long jobs.
2. Improved response time:Short processes are completed earlier, improving average turnaround time.
3. Efficient for batch systems: Works well when execution times are known.

Disadvantages of SPN

1. Need to Estimate Processing Time

The system must know or estimate the execution time of each process.

Possible approaches:

● Programmers estimate execution time for batch jobs.

● The OS collects statistics from previous runs.
● For interactive systems, the OS predicts CPU burst times.

Predicting CPU Burst Time

The operating system estimates the next burst time using past execution times.

Simple Average

Problem: Every past value gets equal weight.

Exponential Averaging (Better Method)

EWIT
13
Operating Systems Internal designs and Principles ACSC404

A commonly used prediction method is exponential averaging:

Where:

● (Tn) = actual recent CPU burst

● (Sn) = previous predicted burst
● ( alpha ) = weighting factor (0 < α < 1)

Interpretation of α

If α is large (close to 1)
● Recent observations get more importance
● Prediction changes quickly
If α is small
● Older observations influence prediction
● Prediction changes slowly
Example when α = 0.8:
Sn+1=0.8Tn+0.16Tn−1+0.032Tn−2+...
Older values have less influence.

Advantages of Exponential Averaging

● Quickly adapts to changes in process behaviour

● Requires less computation
● Uses recent burst times effectively

Problems with SPN

1. Starvation:Long processes may wait indefinitely if short processes keep arriving.

2. Lack of Preemption: Since SPN is non-preemptive, a long process that starts executing cannot be
interrupted.

Therefore, SPN is not ideal for interactive or time-sharing systems.

SPN generally provides:

● Low average waiting time

● Low average turnaround time
● Poor predictability for long jobs

EWIT
14
Operating Systems Internal designs and Principles ACSC404

Short processes benefit greatly, while long processes may suffer large delays.

● SPN selects the shortest expected job first.

● It is a non-preemptive scheduling algorithm.
● Requires burst time prediction.
● Prediction is often done using exponential averaging.
● May cause starvation of long processes.
● Not suitable for time-sharing systems.

Shortest Remaining Time (SRT) Scheduling:

Shortest Remaining Time (SRT) is a preemptive CPU scheduling algorithm and the preemptive
version of Shortest Process Next (SPN).

● The scheduler always selects the process with the shortest remaining execution time.
● If a new process arrives with a shorter remaining time than the currently running process, the
OS preempts the current process and runs the new one.

Working Principle

1. The scheduler estimates the remaining processing time of each process.

2. The process with the smallest remaining time is selected.
3. If a new process arrives with a shorter remaining time, the running process is interrupted.

Advantages of SRT

● Removes the bias toward long processes found in FCFS scheduling.

● Provides better turnaround time than SPN because short jobs are immediately executed.
● No additional clock interrupts are required unlike Round Robin, reducing overhead.

Disadvantages of SRT

● Requires accurate estimation of processing time.

● There is a possibility of starvation for long processes if short processes continue to arrive.
● Some overhead occurs because the system must track elapsed service times.

Highest Response Ratio Next (HRRN) Scheduling:

Highest Response Ratio Next (HRRN) is a non-preemptive CPU scheduling algorithm that selects the
process with the highest response [Link] aim is to reduce waiting time and avoid starvation, while
still giving preference to shorter jobs.

EWIT
15
Operating Systems Internal designs and Principles ACSC404

When the CPU becomes free (after a process finishes or blocks):

1. Calculate the response ratio (R) for all ready processes.

2. Select the process with the highest value of R.
3. Execute that process next.

Minimum Value of Response Ratio

● The minimum value of R is 1.0.

● This occurs when a process just enters the system and has not waited yet.

Why HRRN is Useful

1. Considers Waiting Time (Aging)

As a process waits longer:

● w increases
● Therefore R increases

This ensures that long processes eventually get executed.

2. Favors Short Jobs

Since s is in the denominator, processes with shorter service time tend to have a higher response ratio
and are executed earlier.

Advantages

● Reduces starvation of long processes

● Balances short job preference and fairness
● Improves overall system performance

Disadvantages

● Requires estimation of service time

● Slightly more complex than FCFS or SPN

Feedback Scheduling (Multilevel Feedback Queue)

EWIT
16
Operating Systems Internal designs and Principles ACSC404

Feedback scheduling is used when the system does not know the execution time of processes.
Instead of predicting the remaining time (as in SPN, SRT, or HRRN), the system gives preference to
shorter jobs by penalizing processes that use the CPU for a long [Link] method is also called
Multilevel Feedback Queue Scheduling (MLFQ).

● Scheduling is preemptive and uses time quanta.

● Multiple ready queues are maintained with different priority levels.

Example queues:

RQ₀ → Highest priority

RQ₁
RQ₂
…
RQₙ → Lowest priority

Working Mechanism
Step 1: Process Entry: When a new process enters the system, it is placed in the highest priority queue
(RQ₀).
Step 2: Preemption: If the process uses its entire time quantum and is not finished:

● It is preempted
● Moved to the next lower priority queue

EWIT
17
Operating Systems Internal designs and Principles ACSC404

Step 3: Further Execution: Each time the process is preempted, it moves down to a lower-priority
[Link]:

● Short processes finish quickly in higher queues.

● Long processes gradually move to lower queues.

Queue Scheduling Rules

● Within each queue (except the lowest one), scheduling is done using FCFS.
● The lowest-priority queue uses Round Robin scheduling.

This ensures that long processes still get CPU time.

Example Behaviour:

Short process:

● Executes quickly
● Finishes in higher-priority queues

Long process:

● Uses more CPU time

● Gradually moves down the queue hierarchy

Thus the system automatically favors short jobs.

Multilevel Feedback Concept

The name feedback comes from the fact that:

● After each execution or preemption, the process is fed back into a queue
● Its priority changes dynamically

This allows the operating system to adapt based on process behavior.

Improving the Scheme

A simple version uses the same time quantum for all [Link], this can cause long processes
to experience very large turnaround times.

To improve performance, different time quanta can be used:

Queue Time Quantum

RQ₀ 1 unit

RQ₁ 2 units

EWIT
18
Operating Systems Internal designs and Principles ACSC404

RQ₂ 4 units

RQ₃ 8 units

General rule:

Time Quantum = 2^i, where i = queue level.

Lower-priority queues get longer execution time.

Problem: Starvation

Even with increasing time quantum, long processes may still suffer starvation if many new processes
arrive.

Solution: Priority Promotion (Aging)

To avoid starvation:

● If a process waits too long in a queue,

● It is promoted to a higher-priority queue.

This ensures fairness.

Advantages

● Works well without knowing process execution time

● Automatically favors short processes
● Adaptive scheduling based on behavior
● Widely used in modern operating systems

Disadvantages

● More complex to implement

● Improper parameter selection can cause starvation
● Requires careful tuning of queue levels and time quanta

Problems:

Example 1: Apply scheduling algorithm for same processes:

Process Arrival Time (AT) Burst Time (BT)

EWIT
19
Operating Systems Internal designs and Principles ACSC404

P1 0 8

P2 1 4

P3 2 2

P4 3 1

Formulae

● Completion Time (CT) = finishing time

● Turnaround Time (TAT) = CT − AT
● Waiting Time (WT) = TAT − BT
● Response Time (RT) = first start time − AT

1) FCFS – First Come First Served

FCFS executes processes in the order of arrival. It is non-preemptive.
Step 1: Order of execution
Arrival order: P1 → P2 → P3 → P4
Gantt Chart

0 | P1 | 8 | P2 | 12 | P3 | 14 | P4 | 15

Completion Times

● P1 = 8
● P2 = 12
● P3 = 14
● P4 = 15

Process AT BT CT TAT = CT-AT WT = TAT-BT

P1 0 8 8 8 0

P2 1 4 12 11 7

P3 2 2 14 12 10

P4 3 1 15 12 11

● Average TAT = (8 + 11 + 12 + 12) / 4 = 10.75

● Average WT = (0 + 7 + 10 + 11) / 4 = 7.00

2) RR – Round Robin

EWIT
20
Operating Systems Internal designs and Principles ACSC404

Round Robin is preemptive and uses a fixed time quantum. Let q = 2.

Step-by-step execution

● Time 0–2: P1 runs, remaining = 6

● Time 2–4: P2 runs, remaining = 2
● Time 4–6: P3 runs, completes
● Time 6–8: P1 runs, remaining = 4
● Time 8–9: P4 runs, completes
● Time 9–11: P2 runs, completes
● Time 11–13: P1 runs, remaining = 2
● Time 13–15: P1 runs, completes

Gantt Chart

0 | P1 | 2 | P2 | 4 | P3 | 6 | P1 | 8 | P4 | 9 | P2 | 11 | P1 | 13 | P1 | 15

Completion Times

● P1 = 15
● P2 = 11
● P3 = 6
● P4 = 9

Process AT BT CT TAT WT

P1 0 8 15 15 7

P2 1 4 11 10 6

P3 2 2 6 4 2

P4 3 1 9 6 5

● Average TAT = (15 + 10 + 4 + 6) / 4 = 8.75

● Average WT = (7 + 6 + 2 + 5) / 4 = 5.00

3) SPN – Shortest Process Next

SPN is non-preemptive. It selects the process with the shortest expected burst time among ready
processes.

At time 0, only P1 is available, so P1 must run first.

● Time 0–8: P1 completes

● At time 8, ready processes are P2(4), P3(2), P4(1)

EWIT
21
Operating Systems Internal designs and Principles ACSC404

● Shortest is P4
● Then P3
● Then P2

Gantt Chart

0 | P1 | 8 | P4 | 9 | P3 | 11 | P2 | 15

Completion Times

● P1 = 8
● P4 = 9
● P3 = 11
● P2 = 15

Process AT BT CT TAT WT

P1 0 8 8 8 0

P2 1 4 15 14 10

P3 2 2 11 9 7

P4 3 1 9 6 5

● Average TAT = (8 + 14 + 9 + 6) / 4 = 9.25

● Average WT = (0 + 10 + 7 + 5) / 4 = 5.50

4) SRT – Shortest Remaining Time

SRT is the preemptive version of SPN. A newly arrived shorter process can preempt the running
process.

● Time 0–1: P1 runs, remaining = 7

● Time 1: P2 arrives with BT 4, which is shorter than P1’s remaining 7, so preempt P1
● Time 1–2: P2 runs, remaining = 3
● Time 2: P3 arrives with BT 2, shorter than P2’s remaining 3, so preempt P2
● Time 2–4: P3 runs and completes
● Time 3: P4 arrives with BT 1; at time 4 compare P1(7), P2(3), P4(1), choose P4
● Time 4–5: P4 completes
● Time 5–8: P2 completes
● Time 8–15: P1 completes

Gantt Chart

0 | P1 | 1 | P2 | 2 | P3 | 4 | P4 | 5 | P2 | 8 | P1 | 15

EWIT
22
Operating Systems Internal designs and Principles ACSC404

Completion Times

● P1 = 15
● P2 = 8
● P3 = 4
● P4 = 5

Process AT BT CT TAT WT

P1 0 8 15 15 7

P2 1 4 8 7 3

P3 2 2 4 2 0

P4 3 1 5 2 1

● Average TAT = (15 + 7 + 2 + 2) / 4 = 6.50

● Average WT = (7 + 3 + 0 + 1) / 4 = 2.75

5) HRRN – Highest Response Ratio Next

HRRN is non-preemptive. It chooses the ready process with the highest value of:

R = w+s/s
where (w) is waiting time and (s) is service time.

At time 0, only P1 is present.

● Time 0–8: P1 runs

At time 8:

● P2: w = 8-1 = 7, s=4)

R = 7+4/4 = 2.75
● P3: (w = 8-2 = 6,\s=2)
R = 6+2/2 = 4
● P4: (w = 8-3 = 5,s=1)
R = 5+1/1 = 6 So choose P4.
● Time 8–9: P4 runs

At time 9:

● P2: (w = 9-1 = 8, s=4)

R = 8+4/4 = 3

EWIT
23
Operating Systems Internal designs and Principles ACSC404

● P3: (w = 9-2 = 7, s=2)

R = 7+2/2 = 4.5

So choose P3.

● Time 9–11: P3 runs

● Time 11–15: P2 runs

Gantt Chart

0 | P1 | 8 | P4 | 9 | P3 | 11 | P2 | 15

Completion Times

● P1 = 8
● P4 = 9
● P3 = 11
● P2 = 15

Process AT BT CT TAT WT

P1 0 8 8 8 0

P2 1 4 15 14 10

P3 2 2 11 9 7

P4 3 1 9 6 5

● Average TAT = 9.25

● Average WT = 5.50

6) Feedback Scheduling

Feedback scheduling uses multiple queues and dynamic priorities. New processes start in the highest-
priority queue and are demoted after preemption.

Let us use this rule:

● Q0 quantum = 1
● Q1 quantum = 2
● Q2 = FCFS
● New processes enter Q0

Q0

● Time 0–1: P1 runs, remaining = 7, move to Q1

EWIT
24
Operating Systems Internal designs and Principles ACSC404

● Time 1–2: P2 runs, remaining = 3, move to Q1

● Time 2–3: P3 runs, remaining = 1, move to Q1
● Time 3–4: P4 runs, completes

Q1

Queue order: P1, P2, P3

● Time 4–6: P1 runs for 2 units, remaining = 5, move to Q2

● Time 6–8: P2 runs for 2 units, remaining = 1, move to Q2
● Time 8–9: P3 runs for 1 unit, completes

Q2

Queue order: P1, P2

● Time 9–14: P1 runs, completes

● Time 14–15: P2 runs, completes

Gantt Chart

0 | P1 | 1 | P2 | 2 | P3 | 3 | P4 | 4 | P1 | 6 | P2 | 8 | P3 | 9 | P1 | 14 | P2 | 15

Completion Times

● P1 = 14
● P2 = 15
● P3 = 9
● P4 = 4

Process AT BT CT TAT WT

P1 0 8 14 14 6

P2 1 4 15 14 10

P3 2 2 9 7 5

P4 3 1 4 1 0

● Average TAT = (14 + 14 + 7 + 1) / 4 = 9.00

● Average WT = (6 + 10 + 5 + 0) / 4 = 5.25

Final Comparison Table

EWIT
25
Operating Systems Internal designs and Principles ACSC404

Algorithm Avg WT Avg TAT

FCFS 7.00 10.75

RR (q=2) 5.00 8.75

SPN 5.50 9.25

SRT 2.75 6.50

HRRN 5.50 9.25

Feedback 5.25 9.00

EWIT
26
Operating Systems Internal designs and Principles ACSC404

Sample Questions:
1. Explain the criteria used for short-term scheduling in operating systems.
2. Discuss the decision modes in CPU scheduling with examples.
3. Explain the First-Come-First-Served (FCFS) scheduling algorithm with advantages and
disadvantages.
4. Describe the Round Robin scheduling algorithm and explain how the time quantum affects
system performance.
5. Explain the Shortest Process Next (SPN) scheduling algorithm. Why does it require burst
time estimation?
6. Discuss the Shortest Remaining Time (SRT) scheduling algorithm and its advantages over
SPN.
7. Explain the Highest Response Ratio Next (HRRN) scheduling algorithm with the response
ratio formula.
8. Describe the multilevel feedback queue scheduling algorithm and its working mechanism.

EWIT
27
Operating Systems Internal designs and Principles ACSC404

9. Compare SPN, SRT, and HRRN scheduling algorithms.

10. Explain how exponential averaging is used to estimate CPU burst time.

Problems:
1)Consider the following processes:
Process Arrival Time Burst Time
P1 0 5
P2 1 3
P3 2 8
P4 3 6
Using FCFS scheduling:
● Draw the Gantt chart
● Calculate waiting time and turnaround time.
2)For the following processes:
Process Arrival Time Burst Time
P1 0 6
P2 1 4
P3 2 2
P4 3 1
Using Round Robin scheduling with time quantum = 2:
● Draw the Gantt chart
● Calculate average waiting time.
3)Using SPN scheduling, schedule the following processes:
Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4
Calculate waiting time and turnaround time.

4)Consider the following processes:

Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 2
P4 3 1
Apply Shortest Remaining Time (SRT) scheduling and compute:
● Completion time
● Turnaround time
● Waiting time.
5)For the following processes:
Process Arrival Time Burst Time
P1 0 3

EWIT
28
Operating Systems Internal designs and Principles ACSC404

Process Arrival Time Burst Time

P2 2 6
P3 4 4
P4 6 5
Apply HRRN scheduling and determine the order of execution.

EWIT
29