Operating System Concepts: Scheduling, Synchronization, and Deadlock Management

Posted on Nov 8, 2025 in Telecommunication Sciences and Technologies

CPU Scheduling Fundamentals

CPU scheduling is the process of allocating the CPU (Central Processing Unit) to different processes or threads in a computer system. The primary goal of CPU scheduling is to maximize system performance, efficiency, and responsiveness.

Key CPU Scheduling Criteria

  • Throughput: The number of processes completed per unit time.
  • Turnaround Time: The total time taken for a process to complete, from submission to completion.
  • Waiting Time: The time a process spends waiting in the ready queue.
  • Response Time: The time taken for a process to respond to user input (especially critical in interactive systems).
  • Fairness: Ensuring each process receives a fair share of CPU time.

Levels of CPU Scheduling

  1. Long-Term Scheduling: Determines which processes are admitted to the system (Job Scheduler).
  2. Short-Term Scheduling: Determines which process is executed next by the CPU (CPU Scheduler).
  3. Medium-Term Scheduling: Determines which processes are swapped in and out of memory (Swapper).

Common CPU Scheduling Algorithms

  1. FCFS (First-Come-First-Served): Executes processes strictly in the order they arrive.
  2. SJF (Shortest Job First): Executes the process with the shortest burst time remaining.
  3. Priority Scheduling: Executes processes based on their assigned priority level.
  4. RR (Round Robin): Executes processes in a circular order, with each process receiving a fixed time slice (quantum).
  5. Multilevel Feedback Queue (MLFQ): Uses multiple queues with different priorities and time slices, allowing processes to move between queues.

Multiple Processor Scheduling

  • Symmetric Multiprocessing (SMP): Multiple processors share a common ready queue and self-schedule.
  • Asymmetric Multiprocessing (AMP): A master processor handles all scheduling decisions, and other processors execute user code.
  • Load Balancing: Techniques used to distribute processes across processors to ensure efficient utilization and prevent idle CPUs.

Evaluating Scheduling Algorithms

  1. Performance Metrics: Analyzing key metrics like throughput, turnaround time, waiting time, and response time.
  2. Simulation: Modeling system behavior using trace data to evaluate algorithm performance under realistic conditions.
  3. Analytical Modeling: Using mathematical models (e.g., queuing theory) to evaluate algorithm performance theoretically.

Why CPU Scheduling Matters

  • Efficient Resource Utilization: Maximizes CPU utilization, preventing idle time.
  • Improved System Performance: Enhances overall system responsiveness and throughput.
  • Better User Experience: Provides faster response times and improved system interaction.

In summary, CPU scheduling is a critical component of operating system design. Various algorithms and techniques are employed to optimize system performance and efficiency.

Process Synchronization

Synchronization refers to the coordination of multiple processes or threads accessing shared resources or data. This coordination ensures consistency and correctness, preventing conflicts and ensuring the system behaves predictably.

The Critical Section Problem

A critical section is a segment of code where shared resources or data are accessed. The critical section problem occurs when multiple processes or threads attempt to access the same shared resource concurrently, potentially leading to data inconsistencies or race conditions.

Synchronization Primitives: Semaphores

A semaphore is a synchronization primitive used to control access to shared resources. It acts as a gatekeeper, allowing only a limited number of processes or threads to access the resource simultaneously.

Types of Semaphores

  • Binary Semaphore (Mutex): Functions as a mutual exclusion lock, allowing only one process or thread to access the resource at a time.
  • Counting Semaphore: Allows a specified, finite number of processes or threads to access the resource concurrently.

Classical Synchronization Problems

  1. Producer-Consumer Problem: Requires synchronization to ensure the consumer does not attempt to consume data before the producer has generated it.
  2. Reader-Writer Problem: Requires synchronization to allow multiple readers simultaneous access while ensuring writers have exclusive access.
  3. Dining Philosophers Problem: A classic theoretical problem demonstrating the challenges of resource allocation and the potential for deadlock in concurrent systems.

High-Level Synchronization: Monitors

A monitor is a high-level synchronization construct designed to simplify concurrent programming. It encapsulates the shared resource and provides a set of synchronized methods for accessing that resource.

Benefits of Using Monitors

  • Provides built-in mutual exclusion and synchronization mechanisms.
  • Simplifies programming by abstracting away low-level synchronization details (like semaphore operations).
  • Reduces the risk of common concurrency errors and deadlocks compared to manual semaphore usage.

Importance of Process Synchronization

  • Ensures Data Consistency: Prevents race conditions, data corruption, and inconsistencies in shared data.
  • Prevents Conflicts: Avoids conflicts between processes or threads attempting simultaneous access to critical resources.
  • Improves System Reliability: Enhances overall system reliability and stability in concurrent environments.

In summary, synchronization is essential for ensuring the correctness and consistency of systems involving multiple processes or threads accessing shared resources. Various primitives and constructs, such as semaphores and monitors, are utilized to achieve effective synchronization.

Deadlock Management and Resolution

A deadlock is a critical situation in a computer system where two or more processes are blocked indefinitely. Each process is waiting for a resource held by another process in the set, resulting in a complete standstill where none of the processes can continue execution.

Necessary Conditions for Deadlock

Deadlock can only occur if all four of the following conditions hold simultaneously (Coffman conditions):

  1. Mutual Exclusion: At least one resource must be held in a non-shareable mode.
  2. Hold and Wait: A process must be holding at least one resource and 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 set of processes must exist where P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, …, and Pn is waiting for a resource held by P0, forming a closed loop.

Strategies for Handling Deadlocks

  1. Deadlock Prevention: Structuring the system to ensure that at least one of the four necessary conditions can never hold.
  2. Deadlock Avoidance: Requiring processes to provide information about their resource needs so the OS can dynamically decide whether a resource allocation request will lead to an unsafe state (e.g., Banker’s Algorithm).
  3. Deadlock Detection and Recovery: Allowing deadlocks to occur, detecting them using algorithms, and then recovering the system state.

Implementing Deadlock Prevention

  • Negating Mutual Exclusion: Make resources shareable whenever possible (though often impractical for devices like printers).
  • Negating Hold and Wait: Require processes to request all necessary resources at once, or release all held resources before requesting new ones.
  • Negating No Preemption: Allow the operating system to preempt resources from a process if it is waiting for additional resources.
  • Negating Circular Wait: Impose a total ordering (linear sequence) on all resource types, requiring processes to request resources in increasing order of enumeration.

Deadlock Avoidance Techniques

  • Safe State Analysis: The system only grants resource requests if the resulting state is a “safe state,” meaning there exists a sequence in which all processes can finish execution without causing a deadlock.
  • Resource Allocation Graph Algorithm: Used for systems with single instances of each resource type.
  • Banker’s Algorithm: Used for systems with multiple instances of each resource type.

Detection and Recovery

  1. Detection: Employ algorithms (like the Wait-For Graph algorithm) to periodically check the system state and identify if a deadlock has occurred.
  2. Recovery: Once a deadlock is detected, the system must recover by taking actions such as:
    • Aborting one or more deadlocked processes (usually the one that incurred the least cost).
    • Preempting resources from one or more processes and allocating them to others.
    • Rolling back processes to a safe checkpoint state and restarting them.

Why Deadlock Handling is Essential

  • Prevents System Failure: Deadlocks can lead to system freezes or crashes if not managed.
  • Ensures System Reliability: Proper handling mechanisms guarantee system stability and continuous operation.
  • Improves System Performance: Resolving resource contention quickly improves overall system throughput and responsiveness.

In summary, deadlocks represent a critical challenge in concurrent computer systems. Effective handling—through prevention, avoidance, or detection and recovery—is essential to maintain system reliability, stability, and performance.