1

Operating Systems Study Notes

Chapter 2, Section 2.1: CPU Scheduling
1. Introduction to CPU Scheduling
CPU scheduling is a fundamental concept in operating systems that deals with the allocation of CPU time to different processes. The
main objectives of CPU scheduling are:
• To keep the CPU as busy as possible
• To maximize CPU utilization
• To allocate CPU fairly among processes
• To maximize throughput
• To minimize turnaround time, waiting time, and response time
• To avoid starvation of processes
CPU scheduling becomes necessary in multiprogramming environments where multiple processes compete for CPU time. The OS must
decide which process to run next when the CPU becomes available.
2. Types of Schedulers
There are three main types of schedulers in an operating system:

Scheduler Type Function Frequency Key Points

Long-Term (Job) Selects processes from secondary Infrequent (per new - Controls degree of multiprogramming- Balances
Scheduler memory for ready queue job) I/O-bound and CPU-bound processes
Short-Term (CPU) Selects process from ready queue Very frequent - Must be fast- Uses scheduling algorithms- Critical
Scheduler for CPU allocation (milliseconds) for fairness and preventing starvation
Medium-Term Handles swapping of processes Moderate - Reduces degree of multiprogramming- Improves
Scheduler between main memory and disk process mix in memory
2

2.1 Long-Term Scheduler (Job Scheduler)

• Function: Selects processes from the pool (secondary memory) and loads them into the ready queue in primary memory.
• Frequency: Invoked infrequently, maybe once per new job.
• Controls the degree of multiprogramming (number of processes in memory).
• Aims to maintain a good mix of I/O-bound and CPU-bound processes.
• Some modern time-sharing systems (like Windows and UNIX) don’t have a long-term scheduler.
2.2 Short-Term Scheduler (CPU Scheduler)
• Function: Selects a process from the ready queue and allocates the CPU to it.
• Frequency: Invoked very frequently (milliseconds) → must be fast.
• Uses scheduling algorithms to determine which process runs next.
• Critical in preventing starvation and ensuring fair CPU allocation.

2.3 Medium-Term Scheduler

• Function: Handles swapping of processes between main memory and disk.
• Used for reducing the degree of multiprogramming.
• Swaps out processes from memory to disk to free up space, and swaps them back in when needed.
• Useful for improving the mix of I/O-bound and CPU-bound processes in memory.
3. Process Scheduling Queues

The OS maintains several queues to manage processes:

1. Job Queue: Contains all processes in the system.
2. Ready Queue: Contains all processes in main memory, ready and waiting to execute.
3. Device Queues: Processes waiting for specific I/O devices.
The OS uses these queues to manage the state of processes. When a process changes state, its Process Control Block (PCB) is moved to
the appropriate queue.
3

4. Scheduling Criteria
To evaluate and compare CPU scheduling algorithms, several criteria are used:

Criterion Definition Goal Formula (if applicable)

CPU Utilization Fraction of time CPU is busy Maximize (40-90% in real (Busy Time / Total Time) * 100%
systems)
Throughput Number of processes completed per unit Maximize Processes Completed / Time Unit
time
Turnaround Time from process submission to Minimize Completion Time - Arrival Time
Time completion
Waiting Time Time spent by a process in the ready Minimize Turnaround Time - Burst Time
queue
Response Time Time from submission to first response Minimize First CPU Allocation Time - Arrival
Time

4.1 CPU Utilization

• Definition: The fraction of time the CPU is busy.
• Goal: Keep the CPU as busy as possible.
• Theoretical range: 0 to 100%
• Practical range in real systems: 40% to 90%

4.2 Throughput
• Definition: Number of processes completed per unit time.
• Goal: Maximize throughput.
• Depends on the length and mix of processes.
4.3 Turnaround Time
• Definition: Time from process submission to completion.
• Includes execution time and all waiting times.
4

• Formula: Turnaround Time = Completion Time - Arrival Time

• Alternatively: Turnaround Time = Burst Time + Waiting Time

4.4 Waiting Time

• Definition: Total time a process spends waiting in the ready queue.
• Goal: Minimize waiting time.
• Formula: Waiting Time = Turnaround Time - Burst Time

4.5 Response Time

• Definition: Time from submission of a request until the first response is produced.
• Important in interactive systems.
• Formula: Response Time = Time of First CPU Allocation - Arrival Time
5. Types of CPU Scheduling
There are two main types of CPU scheduling:

Type Description Advantages Disadvantages

Preemptive OS can forcibly remove a - More reliable- Better response time- - Higher computational overhead- Context
process from CPU Good for multi-programming switching overhead- Potential for starvation
Non- Process keeps CPU until it - Less overhead- Simpler to implement- - Poor response times- Potential CPU
Preemptive releases voluntarily High throughput for long CPU-bound jobs monopolization

5.1 Preemptive Scheduling

• Definition: The OS can forcibly remove a process from the CPU.
• Used when:
– A process switches from running state to ready state
– A process switches from waiting state to ready state
• Advantages:
– More reliable (prevents process monopolization)
– Better average response time
5

– Good for multi-programming environments

• Disadvantages:
– Requires more computational resources
– Context switching overhead
– Can lead to starvation of low-priority processes
5.2 Non-Preemptive Scheduling
• Definition: Once the CPU is allocated to a process, it keeps the CPU until it releases it voluntarily.
• Used when:
– A process terminates
– A process switches from running to waiting state
• Advantages:
– Less computational overhead
– Simple to implement
– High throughput for long CPU-bound jobs
• Disadvantages:
– Can lead to poor response times
– Potential for one process to monopolize the CPU
6. CPU Scheduling Algorithms

6.1 First-Come, First-Served (FCFS)

• Simplest CPU scheduling algorithm
• Non-preemptive
• Processes are executed in the order they arrive in the ready queue
• Implemented with a FIFO queue
• Easy to implement and understand
Example: Given processes P1, P2, P3 with burst times 24, 3, 3 respectively:
6

Process Burst Time Arrival Time Completion Time Turnaround Time Waiting Time
P1 24 0 24 24 0
P2 3 0 27 27 24
P3 3 0 30 30 27

Calculations: 1. Completion Time (CT): P1: CT = 24 P2: CT = 24 + 3 = 27 P3: CT = 27 + 3 = 30

2. Turnaround Time (TAT): P1: TAT = 24 - 0 = 24 P2: TAT = 27 - 0 = 27 P3: TAT = 30 - 0 = 30

3. Waiting Time (WT): P1: WT = 24 - 24 = 0 P2: WT = 27 - 3 = 24 P3: WT = 30 - 3 = 27

4. Average Waiting Time = (0 + 24 + 27) / 3 = 17 Average Turnaround Time = (24 + 27 + 30) / 3 = 27

Advantages of FCFS Disadvantages of FCFS

- Simple to implement- Fair in order of arrival - Convoy effect- Not suitable for time-sharing- Unresponsive for interactive processes

7. Important Concepts in CPU Scheduling

Concept Definition
CPU Burst Period of continuous CPU execution for a process
I/O Burst Period when a process is waiting for I/O completion
CPU-I/O Burst Cycle Alternation between CPU and I/O bursts in a process
CPU-bound Process Process with long CPU bursts (computation-intensive)
I/O-bound Process Process with short CPU bursts (I/O-intensive)
Dispatcher Module that gives CPU control to the selected process
Dispatch Latency Time to stop one process and start another
Context Switch Saving state of one process and loading another
1. CPU Burst: Period of time during which a process is continuously executing on the CPU.

2. I/O Burst: Period of time during which a process is waiting for I/O operations to complete.
7

3. CPU-I/O Burst Cycle: Processes alternate between CPU and I/O bursts.

4. CPU-bound Process: Spends more time doing computations (long CPU bursts).

5. I/O-bound Process: Spends more time doing I/O (short CPU bursts).

6. Dispatcher: Module that gives control of the CPU to the process selected by the short-term scheduler.

7. Dispatch Latency: Time it takes for the dispatcher to stop one process and start another.

8. Context Switch: Process of saving the state of a process and loading the saved state of another process.

Remember to review these concepts thoroughly and practice applying them to different scenarios. Good luck with your exam!
CPU Scheduling Algorithms
1. Introduction to CPU Scheduling
CPU scheduling is a crucial aspect of operating systems that determines which process gets the CPU for execution. The main objectives
of CPU scheduling are:
• Maximize CPU utilization
• Minimize response time
• Maximize throughput
• Minimize waiting time
• Ensure fairness among processes

2. Types of CPU Scheduling Algorithms

2.1 Shortest Job First (SJF) Scheduling
SJF is an algorithm where the process with the smallest execution time is chosen for the next execution. There are two types of SJF:

2.1.1 Non-Preemptive SJF

In non-preemptive SJF, once the CPU is allocated to a process, it holds it until it reaches a waiting state or terminates.
Example:
Consider the following five processes:

Process Arrival Time Burst Time

P1 0 7
P2 1 5
P3 3 1
 P4 5 2
P5 6 3

Gantt Chart:
0 7 12 13 15 18
| P1 | P2 |P3|P4 | P5 |

Calculations: - Completion Time: P1 = 7, P2 = 12, P3 = 13, P4 = 15, P5 = 18 - Turnaround Time = Completion Time - Arrival Time -
Waiting Time = Turnaround Time - Burst Time

Process Turnaround Time Waiting Time

P1 7 0
P2 11 6
P3 10 9
P4 10 8
P5 12 9

Average Waiting Time = (0 + 6 + 9 + 8 + 9) / 5 = 6.4 ms Average Turnaround Time = (7 + 11 + 10 + 10 + 12) / 5 = 10 ms

2.1.2 Preemptive SJF (Shortest Remaining Time First)

In Preemptive SJF, if a process with a shorter burst time arrives, the current process is preempted, and the shorter job is allocated the
CPU.
Example:
Consider the following five processes:

Process Arrival Time Burst Time

P1 0 8
P2 1 4
 P3 2 9
P4 3 5
P5 4 2

Gantt Chart:
0 1 5 7 9 14 23
|P1 |P2 |P5|P2 | P4 | P1 | P3 |

Calculations: - Completion Time: P1 = 14, P2 = 7, P3 = 23, P4 = 14, P5 = 7 - Turnaround Time = Completion Time - Arrival Time - Waiting
Time = Turnaround Time - Burst Time

Process Turnaround Time Waiting Time

P1 14 6
P2 6 2
P3 21 12
P4 11 6
P5 3 1

Average Waiting Time = (6 + 2 + 12 + 6 + 1) / 5 = 5.4 ms Average Turnaround Time = (14 + 6 + 21 + 11 + 3) / 5 = 11 ms

2.2 Round Robin (RR) Scheduling

Round Robin is a preemptive algorithm where each process gets a fixed time slice called a time quantum. If a process’s remaining burst
time exceeds the time quantum, it’s moved to the end of the ready queue.
Characteristics: - Preemptive algorithm - Time slices are assigned to each process in a cyclic manner - Widely used in traditional
operating systems
Example:
Consider the following processes with a time quantum of 2 units:
 Process Arrival Time Burst Time
P1 0 5
P2 1 4
P3 2 2
P4 4 1

Gantt Chart:
0 2 4 6 8 10 12 13 14 16
|P1 |P2 |P3 |P1 |P2 |P1 |P2 |P4 |P1 |P2 |

Calculations: - Completion Time: P1 = 14, P2 = 16, P3 = 6, P4 = 13 - Turnaround Time = Completion Time - Arrival Time - Waiting Time =
Turnaround Time - Burst Time

Process Turnaround Time Waiting Time

P1 14 9
P2 15 11
P3 4 2
P4 9 8

Average Waiting Time = (9 + 11 + 2 + 8) / 4 = 7.5 ms Average Turnaround Time = (14 + 15 + 4 + 9) / 4 = 10.5 ms

Advantages of Round Robin Scheduling: - Fair allocation of CPU to all processes - No starvation or convoy effect - Predictable
response times - Easy to implement
Disadvantages of Round Robin Scheduling: - Performance depends on the choice of time quantum - Higher context switching
overhead - No priority setting for processes

2.3 Priority Scheduling

In Priority scheduling, each process is assigned a priority number. The process with the highest priority (lowest number in some
systems) is executed first.
Example:
Consider the following processes:

Process Arrival Time Burst Time Priority

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

Gantt Chart:
0 3 7 9 13 19
|P1 |P3 |P4 | P5 | P2 |

Calculations: - Completion Time: P1 = 3, P2 = 19, P3 = 7, P4 = 9, P5 = 13 - Turnaround Time = Completion Time - Arrival Time - Waiting
Time = Turnaround Time - Burst Time

Process Turnaround Time Waiting Time

P1 3 0
P2 18 12
P3 4 0
P4 4 2
P5 7 3

Average Waiting Time = (0 + 12 + 0 + 2 + 3) / 5 = 3.4 ms Average Turnaround Time = (3 + 18 + 4 + 4 + 7) / 5 = 7.2 ms

3. Multiprocessor Scheduling
Multiprocessor scheduling involves designing scheduling functions for systems with more than one processor. It’s more complex than
single processor scheduling.

3.1 Types of Multiprocessor Systems

1. Symmetric Multiprocessing (SMP): All processors are identical, and any process can run on any processor.
2. Asymmetric Multiprocessing: One processor (master) handles all scheduling decisions and I/O processing, while others
(slaves) only execute user code.

3.2 Approaches to Multiprocessor Scheduling

1. Processor Affinity: Keeping a process running on the same processor to utilize cache memory effectively.
– Soft Affinity: OS tries to keep a process on the same processor but doesn’t guarantee it.
– Hard Affinity: Process specifies a subset of processors on which it may run.
2. Load Balancing: Distributing the workload evenly across all processors.
– Push Migration: Periodically checking and redistributing the load.
– Pull Migration: Idle processors pull waiting tasks from busy processors.
3.3 Challenges in Multiprocessor Scheduling
1. Locking System: Protecting shared resources for safe access among multiple processors.
2. Shared Data: Maintaining data consistency when multiple processors access the same data.
3. Cache Coherence: Ensuring a coherent view of shared data stored in multiple local caches.

4. Conclusion
CPU scheduling is a critical component of operating systems that significantly affects system performance. Different scheduling
algorithms cater to various system requirements and workloads. Understanding these algorithms and their characteristics is essential
for optimizing system performance and resource utilization.
Operating Systems - Chapter 2, Section 2.3 Notes
2.3.1 Performance Evaluation of Scheduling
Performance evaluation of scheduling algorithms is crucial in determining their efficiency and effectiveness in managing process
execution.

Key Metrics for Evaluation:

1. CPU Utilization:
– Measures the percentage of time the CPU is actively executing processes.
– Higher CPU utilization indicates better resource utilization.
2. Throughput:
– Evaluates the number of processes completed in a unit of time.
– Higher throughput implies a more efficient scheduling algorithm.
3. Turnaround Time:
– Calculates the total time taken to execute a process from submission to completion.
– Lower turnaround time is generally desirable.
4. Waiting Time:
– Assesses the total time a process spends waiting in the ready queue before being executed.
– Minimizing waiting time leads to better responsiveness.
5. Response Time:
– Measures the time it takes for a system to respond to a user request.
– Low response time is crucial for interactive systems.
6. Fairness:
– Evaluates how evenly resources are distributed among processes.
– Fair scheduling ensures that no process is unfairly starved of resources.
7. Context Switching Overhead:
– Examines the overhead introduced by context switching between processes.
 – Lower context switching overhead is generally preferred for performance.
8. Predictability:
– Assesses how well the scheduling algorithm can provide predictable behavior.
– Predictable scheduling is important for real-time systems.
9. Priority Inversion:
– Evaluates how well the algorithm handles priority inversion scenarios.
– Priority inversion occurs when a lower-priority task holds a resource needed by a higher-priority task.
10. Scalability:
– Measures the algorithm’s performance as the system scales with an increasing number of processes or threads.
– A scalable algorithm can handle larger workloads efficiently.

Methods for Performance Evaluation:

1. Simulation and Modeling:
– Use simulation tools or mathematical models to simulate different scenarios and evaluate algorithm performance under
various conditions.
2. Benchmarking:
– Compare the scheduling algorithm against other well-known algorithms using benchmark tests.
– Standard benchmark suites can help in assessing the relative strengths and weaknesses of different algorithms.
3. Workload Characteristics:
– Consider the characteristics of the workload the system is expected to handle.
– Some algorithms may perform better under certain types of workloads.
4. Power Consumption:
– Evaluate the impact of the scheduling algorithm on overall power consumption.
– Energy-efficient scheduling is crucial for battery-powered devices.
5. Real-world Testing:
– Conduct real-world testing in a production-like environment to observe the scheduling algorithm’s behavior in practical
scenarios.
2.3.2 Inter-Process Communication (IPC)
Inter-Process Communication (IPC) is a mechanism provided by the operating system to allow processes to communicate and
synchronize their actions.

Types of Processes:
1. Independent Process:
– Not affected by the execution of other processes.
– Characteristics:
• No shared state
• No synchronization needed
• No communication with other processes
• Isolation
• Parallel execution possible
2. Cooperating Process:
– Can be affected by other executing processes.
– Characteristics:
• Information sharing
• Modularity
• Computation speedup
• Convenience

IPC Methods:
1. Shared Memory:
– Fastest IPC mechanism
– Memory shared between two or more processes
– Operating system maps a memory segment in the address space of several processes
– Processes can read and write in the shared segment without calling operating system functions
Working of Shared Memory:
 – Process P1 establishes a shared memory region in its address space
– Process P2 attaches itself to the shared address space of P1
– Processes exchange information by reading and writing data in the shared segment
Advantages:
– Faster IPC system
– Allows concurrent access to shared data
– Speeds up computation power
– Achieves modularity
– Enables users to perform multiple tasks simultaneously
2. Message Passing:
– Processes exchange messages to coordinate activities and exchange data
– No shared memory used
– Each process has a unique identifier (process ID)
– Messages are sent using the recipient’s process ID
Types of Message Passing:
a) Direct Message Passing:
• Receiver identity is known
• Message sent directly to the receiving process
• Limited modularity
b) Indirect Message Passing:
• Messages sent to a mailbox (or port) bound to a receiving process
• Multiple processes can send messages to the same mailbox
• Provides flexibility in application design
Advantages of Message Passing:
– No shared state
– Suitable for distributed systems
– Enhances scalability
Disadvantages of Message Passing:
 – Can introduce overhead
– Complexity in asynchronous communication
– Potential latency, especially in distributed systems

2.3.3 Critical Section Problem

The critical section is a part of a program that tries to access shared resources. The critical section problem involves designing protocols
to ensure that race conditions among processes do not arise.

Critical Section Diagram:

[Entry Section] -> [Critical Section] -> [Exit Section]
|
[Remainder Section]

Problems in Critical Section:

• Multiple processes trying to enter the critical section simultaneously
• Data inconsistency when shared variables are accessed by multiple processes
Solutions to the Critical Section Problem:
Any solution must meet three key requirements:
1. Mutual Exclusion:
– When one process is executing in its critical section, no other process should be allowed to enter its critical section.
2. Progress:
– If no process is in its critical section and some processes wish to enter their critical section, only those processes not in
their remainder section can participate in deciding which will enter the critical section next.
3. Bounded Waiting:
– There must be a bound on the number of times other processes are allowed to enter their critical sections after a process
has made a request to enter its critical section and before that request is granted.
2.3.4 Semaphores
Semaphores are integer variables used to solve the critical section problem by using two atomic operations: wait and signal.

Types of Semaphores:
1. Binary Semaphore:
– Only two values: 0 and 1
– If value is 1, process can enter the critical section
– If value is 0, process cannot enter the critical section
2. Counting Semaphore:
– Values can be greater than or equal to zero
– If value is greater than or equal to 1, process can enter the critical section
– If value is 0, process cannot enter the critical section
Semaphore Operations:
1. Wait Operation (P Function):
– Decides if a process can enter the critical section or must wait
– If semaphore value > 0, process enters critical section and value is decremented
– If semaphore value = 0, process must wait
2. Signal Operation (V Function):
– Updates the semaphore value when processes exit the critical section
– Increments the semaphore value
Advantages of Semaphores:
• Machine independent
• Enforce mutual exclusion
• No resource loss due to busy waiting
• Good resource management
• Prevent multiple processes from entering the critical section simultaneously
Disadvantages of Semaphores:
• Possible priority inversion
• Complex design to avoid deadlocks
• Challenging to program correctly
• Risk of not achieving mutual exclusion if not implemented properly

2.3.5 Mutual Exclusion

Mutual Exclusion is a property of process synchronization that states that no two processes can exist in the critical section at any given
point in time.

Need for Mutual Exclusion:

• Arises with concurrency
• Types of concurrent execution:
– Interrupt handlers
– Interleaved, preemptively scheduled processes/threads
– Multiprocessor clusters with shared memory

Importance:
• Prevents race conditions
• Ensures data consistency in shared resources

2.3.6 Deadlock Conditions

A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another
resource acquired by some other process.
Four Necessary Conditions for Deadlock:
1. Mutual Exclusion:
– At least one resource must be held in a non-sharable mode.
2. Hold and Wait:
 – A process must be holding at least one resource while waiting to acquire additional resources held by other processes.
3. No Preemption:
– Resources cannot be forcibly taken away from a process; they must be released voluntarily.
4. Circular Wait:
– A circular chain of two or more processes, each waiting for a resource held by the next member in the chain.
Methods of Handling Deadlock:
1. Deadlock Prevention:
– Ensure that at least one of the four necessary conditions cannot hold.
2. Deadlock Avoidance:
– Make decisions about resource allocation to ensure the system never enters an unsafe state.
3. Deadlock Detection and Recovery:
– Allow deadlocks to occur, detect them, and take action to recover.
4. Deadlock Ignorance:
– Ignore the problem altogether; used if deadlocks are very rare.

Deadlock Prevention and Recovery:

Recovery methods: 1. Manual Intervention 2. Automatic Recovery: - Process Termination: a) Abort all deadlocked processes b) Abort
one process at a time

2.3.7 Banker’s Algorithm

The Banker’s Algorithm is a deadlock avoidance algorithm used in operating systems.

Key Data Structures:

• Available: Vector of length m indicating the number of available resources of each type.
• Allocation: n×m matrix defining the number of resources of each type currently allocated to each process.
• Request: n×m matrix indicating the current request of each process.
Steps of the Banker’s Algorithm:
1. Initialize Work vector and Finish boolean array.
2. Find an index i such that both Finish[i] = false and Request[i] ≤ Work.
3. If found, perform Work = Work + Allocation[i] and set Finish[i] = true. Go to step 2.
4. If no such i exists, go to step 5.
5. If Finish[i] = true for all i, the system is in a safe state.
Advantages of Deadlock Detection Algorithms:
• Improved system stability
• Better resource utilization
• Relatively easy implementation for some algorithms
Disadvantages of Deadlock Detection Algorithms:
• Performance overhead
• Complexity in implementation for some algorithms
• Possibility of false positives and negatives
The choice of deadlock detection algorithm depends on specific system requirements, performance-complexity trade-offs, and risk
tolerance.