Comprehensive Study Notes on CPU Scheduling, Deadlocks, and Process Synchronization

Overview of CPU Scheduling Algorithms

CPU Scheduling addresses the critical problem of deciding which process within the ready queue is to be allocated the CPU for execution. This management task is foundational to operating system performance. The primary algorithms studied in this context include First Come, First Served (FCFS) Scheduling, Round Robin (RR) Scheduling, Shortest Job First (SJF) Scheduling, Shortest Remaining Time (SRT) Scheduling, and Priority Scheduling.

First Come, First Served (FCFS) Scheduling

The First Come, First Served (FCFS) algorithm is the simplest approach to CPU scheduling. In this scheme, the process that requests the CPU first is allocated the CPU first. Its implementation is handled through a First-In, First-Out (FIFO) queue structure. When a process enters the ready queue, its Process Control Block (PCB) is linked to the rear of the queue. While conceptually straightforward and fair, the average waiting time under FCFS is often quite long.

There are several distinct advantages and disadvantages to FCFS. On the positive side, it is easy to implement without complex logic, ensures every task is executed in a predictable sequence via the FIFO queue, and is inherently fair because it does not prioritize random tasks. However, it suffers from the "convoy effect," where processes with low burst times are blocked behind a process with a very high burst time, causing significant delays. Because it is non-preemptive, it does not release the CPU until the current task is complete, making it unsuitable for time-sharing systems.

Shortest Job First (SJF) and Shortest Remaining Time (SRT)

The Shortest Job First (SJF) algorithm, also known as Shortest-Process-Next (SPN), associates the CPU with the process that has the smallest predicted next CPU burst. This is specifically referred to as "shortest next CPU burst" scheduling because decision-making is based on the length of the upcoming burst rather than the total process length. In its non-preemptive form (SJF), once a job begins, it runs until its burst is finished.

Shortest-Remaining-Time (SRT) is the preemptive counterpart of SJF and is much more useful in time-sharing environments. In SRT, the system evaluates the estimated runtime to completion for all processes, including new arrivals. If a new process arrives with a shorter estimated remaining time than the currently running process, the current process is preempted. While SRT allows small processes to run almost immediately, it introduces higher overhead because the operating system must constantly track elapsed time and manage preemptions. Additionally, longer jobs may experience even longer mean waiting times under this scheme.

Priority and Round Robin Scheduling

In Priority Scheduling, each process is assigned an integer representing its priority. The CPU is allocated to the process with the highest priority, where traditionally a smaller integer represents a higher priority level. Processes with equal priority are scheduled using the FCFS method. SJF is technically a form of priority scheduling where the priority is defined as the predicted length of the next CPU burst. A major problem with priority scheduling is starvation, where low-priority processes may never execute. This is resolved through "aging," a technique where the priority of a process is gradually increased the longer it remains in the queue. Priority can be defined either internally (based on measurable quantities like memory limits) or externally (based on criteria like importance or political factors).

Round Robin (RR) Scheduling is specifically designed for time-sharing systems. It functions similarly to FCFS but adds a preemption condition that allows the system to switch between processes. This is achieved using a small unit of time known as a "quantum time" or "time slice." While RR provides better responsiveness for interactive users, the average waiting time under this policy is also relatively long.

Comparative Analysis of Preemptive and Non-Preemptive Scheduling

Scheduling algorithms are categorized as either preemptive or non-preemptive. In preemptive scheduling, resources are allocated for a limited time, and processes can be interrupted during execution. This approach is flexible but expensive due to high overhead. Examples include Round Robin and SRT. In contrast, non-preemptive scheduling allows a process to hold the CPU until it completes its burst time or enters a 'wait' state. While less expensive and lacking overhead, it is not flexible and can cause starvation if a process with a very long burst time takes over the CPU. Examples include FCFS and SJF.

CPU Scheduling Metrics and Mathematical Definitions

To evaluate scheduling algorithms, several metrics are utilized to calculate performance:

Arrival Time (AT) is the point in time at which a process enters the ready queue.

Burst Time (BT) or CPU Time is the specific duration required for a process to complete its execution.

Completion Time (CT) is the time at which the process terminates its execution.

Turn-around Time (TAT) is the total time elapsed from arrival until completion. It is calculated using the following formulas: $TAT = CT - AT$ $TAT = BT + WT$

Waiting Time (WT) is the amount of time a process spends waiting in the ready queue while another process uses the CPU: $WT = TAT - BT$

Response Time (RT) is the time from the arrival of the process until the CPU is first allocated to it. In non-preemptive scheduling, RT is generally equivalent to WT.

A Gantt Chart is utilized as a visualization tool to solve scheduling problems, showing how processes are allocated over time.

Scheduling Calculation Examples

Problem 1: Consider a set of processes with the following attributes:

P1: $AT = 2$ , $BT = 2$ , $CT = 13$ , $TAT = 11$ , $WT = 9$ , $RT = 9$
P3: $AT = 5$ , $BT = 6$ , $CT = 19$ , $TAT = 14$ , $WT = 8$ , $RT = 8$
P4: $AT = 0$ , $BT = 4$ , $CT = 4$ , $TAT = 4$ , $WT = 0$ , $RT = 0$
P5: $AT = 7$ , $BT = 4$ , $CT = 23$ , $TAT = 16$ , $WT = 12$ , $RT = 12$

Average Waiting Time Calculation: $\text{Average WT} = \frac{9 + 8 + 0 + 4 + 12}{5} = \frac{33}{5} = 6.6\,ms$

Average Turn-around Time Calculation: $\text{Average TAT} = \frac{11 + 14 + 4 + 11 + 16}{5} = \frac{56}{5} = 11.2\,ms$

Problem 2: For a second set of data, the following averages were determined after scheduling: Average WT: $\text{Average WT} = \frac{0 + 0 + 2 + 4 + 8}{5} = \frac{14}{5} = 2.8\,ms$

Average TAT: $\text{Average TAT} = \frac{2 + 1 + 5 + 9 + 13}{5} = \frac{30}{5} = 6\,ms$

Note: During idle CPU periods, where no process is scheduled, the Gantt chart remains void for that duration.

Deadlocks and Necessary Conditions

A deadlock is a state where a set of processes are stuck indefinitely because each holds a resource while waiting for another resource held by another process. This results in permanent blocking and is common in scenarios involving database locks or multi-threaded resource management. For a deadlock to occur, four conditions (Coffman Conditions) must hold simultaneously:

Mutual Exclusion: At least one resource must be held in a non-shareable mode.
Hold and Wait: A process holds at least one resource and is waiting for another.
No Preemption: Resources cannot be forcibly taken; they must be released voluntarily.
Circular Wait: A circular chain of processes exists where each process is waiting for a resource held by the next process in the chain.

Methods for Deadlock Management

Deadlock Prevention aims to eliminate one of the four necessary conditions. To eliminate mutual exclusion, one can use spooling (simultaneous peripheral operations online) to make devices effectively shareable. To eliminate hold and wait, systems can use "pre-allocation" (requesting all resources at once) or "release before request." To eliminate no preemption, the OS can forcibly preempt resources from a waiting process. To eliminate circular wait, a total ordering of all resource types is imposed, requiring processes to request resources in increasing order.

Banker’s Algorithm is a resource allocation and deadlock avoidance algorithm. It tests for safety by simulating the allocation of the maximum possible resources. It determines if a "safe sequence" exists; if allocating a resource leads to a state where no such sequence is possible, the resource is not allocated. This ensures the system never enters a deadlock state.

Process Synchronization and Mutexes

Processes are categorized as Independent (one does not affect others) or Cooperative (affects or is affected by others). Cooperative processes often share resources, leading to the process synchronization problem and potential race conditions. A race condition is when multiple operations attempt to run simultaneously, leading to inconsistency.

The Critical Section Problem involves designing a mechanism for cooperative processes to access shared code segments without creating data inconsistencies. A valid solution must satisfy three requirements:

Mutual Exclusion: Only one process in the critical section at a time.
Progress: Selection of the next process to enter cannot be postponed indefinitely if the section is free.
Bounded Waiting: There must be a limit on how many times other processes can enter before a specific request is granted.

A Mutex (mutual exclusion object) is a synchronization primitive acting as a binary lock. A thread must acquire the lock via lock() or acquire() and release it via unlock() or release(). Only the owner who locked the mutex can unlock it. If the mutex is already locked, any other thread attempting to access it is blocked or placed in a waiting state.

Peterson’s Solution and Semaphores

Peterson’s Solution is a software-based approach for two processes. It uses two variables: boolean flag[i] (indicating interest) and int turn (indicating whose turn it is). While it satisfies the three requirements of critical section solutions, it involves busy waiting (which wastes CPU cycles), is limited to two processes, and is incompatible with modern architectures.

Semaphores provide a signaling mechanism using two atomic operations: wait() (also called P(S)) and signal() (also called V(S)): $\text{wait(S): } \text{while } (S \le 0); S--;$ $\text{signal(S): } S++;$

There are two types of semaphores:

Binary Semaphores: Range from 0 to 1; used as mutex locks to provide mutual exclusion.
Counting Semaphores: Can hold any value; used to manage access to resources with multiple instances. The semaphore is initialized to the number of available instances.

Advantages of semaphores include allowing multiple threads in the section if needed, machine independence, and flexible resource management. However, disadvantages include the risk of priority inversion, the need for the OS to track all calls, and the complexity that may lead to deadlocks if the wait and signal operations are not executed in the correct order.