Back to Subject
Practice MCQ

Unit 2 - Notes

CSE316

Unit 2: CPU Scheduling

1. Introduction to CPU Scheduling

CPU scheduling is the basis of multiprogrammed operating systems. By switching the CPU among processes, the operating system can make the computer more productive.

The CPU-I/O Burst Cycle

Process execution consists of a cycle of CPU execution and I/O wait. Processes alternate between these two states. Process execution begins with a CPU burst followed by an I/O burst, then another CPU burst, and so on. Eventually, the final CPU burst ends with a system request to terminate execution.

2. The CPU Scheduler

Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is carried out by the CPU Scheduler (also called the Short-Term Scheduler).

The scheduler selects a process from the processes in memory that are ready to execute and allocates the CPU to that process.

The Dispatcher

The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves:

  • Switching context: Saving the state of the old process and loading the state of the new process.
  • Switching to user mode.
  • Jumping to the proper location in the user program to restart that program.

Dispatch Latency: The time it takes for the dispatcher to stop one process and start another running. This must be as fast as possible.

3. Preemptive vs. Non-Preemptive Scheduling

CPU scheduling decisions may take place under the following four circumstances:

  1. When a process switches from the running state to the waiting state (e.g., I/O request).
  2. When a process switches from the running state to the ready state (e.g., an interrupt/timer expiration).
  3. When a process switches from the waiting state to the ready state (e.g., I/O completion).
  4. When a process terminates.

Non-Preemptive Scheduling

  • Occurs under circumstances 1 and 4 only.
  • Once the CPU has been allocated to a process, the process keeps the CPU until it releases it either by terminating or by switching to the waiting state.
  • Pros: Simple to implement; low overhead.
  • Cons: Poor response time; bugs can freeze the machine.

Preemptive Scheduling

  • Occurs under circumstances 2 and 3 (in addition to 1 and 4).
  • The OS can interrupt a currently running process and move it to the Ready queue to run a different process.
  • Pros: Essential for time-sharing systems and real-time systems; better responsiveness.
  • Cons: Incurs overhead (context switching); requires synchronization mechanisms to prevent race conditions on shared data.

4. Scheduling Criteria

To compare CPU scheduling algorithms, the following characteristics are used:

  1. CPU Utilization: Keep the CPU as busy as possible (range 0% to 100%).
  2. Throughput: The number of processes that complete their execution per time unit.
  3. Turnaround Time: The amount of time to execute a particular process.
    • Formula: Turnaround Time = Completion Time - Arrival Time
  4. Waiting Time: The amount of time a process has been waiting in the ready queue.
    • Formula: Waiting Time = Turnaround Time - CPU Burst Time
  5. Response Time: The amount of time it takes from when a request was submitted until the first response is produced (time to start responding, not time to finish).

Goal: Maximize CPU utilization and throughput; minimize turnaround time, waiting time, and response time.

5. Scheduling Algorithms

A. First-Come, First-Served (FCFS)

The simplest scheduling algorithm. The process that requests the CPU first is allocated the CPU first.

  • Type: Non-preemptive.
  • Implementation: FIFO Queue.
  • Pros: Simple to write and understand.
  • Cons:
    • High average waiting time.
    • Convoy Effect: Short processes wait behind one long process (like traffic waiting behind a slow truck), leading to lower CPU and device utilization.

B. Shortest-Job-First (SJF)

Associates with each process the length of its next CPU burst. The CPU is assigned to the process having the smallest next CPU burst.

  • Type: Can be Preemptive or Non-preemptive.
  • Optimality: SJF is optimal; it gives the minimum average waiting time for a given set of processes.
  • Challenge: Difficult to know the length of the next CPU burst in advance. It is often predicted using exponential averaging of previous bursts.

Variants:

  1. Non-preemptive SJF: Once the CPU is given to the process, it cannot be preempted until it completes its CPU burst.
  2. Preemptive SJF (Shortest Remaining Time First - SRTF): If a new process arrives with a CPU burst length less than the remaining time of the current executing process, preempt.

C. Priority Scheduling

A priority number (integer) is associated with each process. The CPU is allocated to the process with the highest priority. (Convention: strictly defined by the OS, usually lowest number = highest priority).

  • Type: Preemptive or Non-preemptive.
  • Problem - Starvation (Indefinite Block): Low-priority processes may never execute in a heavily loaded system.
  • Solution - Aging: Gradually increase the priority of processes that wait in the system for a long time.

D. Round Robin (RR)

Designed specifically for time-sharing systems. Similar to FCFS, but preemption is added to enable the system to switch between processes.

  • Mechanism: A small unit of time, called a Time Quantum (or Time Slice), is defined (e.g., 10–100 ms). The ready queue is treated as a circular queue. The scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.
  • Scenarios:
    • Burst < Quantum: Process releases CPU voluntarily.
    • Burst > Quantum: Timer interrupt occurs, context switch happens, and process is put at the tail of the ready queue.
  • Performance: Depends heavily on the size of the time quantum.
    • Large Quantum: Becomes FCFS.
    • Small Quantum: Processor sharing (looks like each process has its own slow processor), but context switch overhead becomes high.

E. Multilevel Queue Scheduling

Used when processes can be easily classified into different groups (e.g., Foreground/Interactive processes vs. Background/Batch processes).

  • Structure: The ready queue is partitioned into separate queues.
  • Algorithm: Each queue has its own scheduling algorithm (e.g., RR for foreground, FCFS for background).
  • Inter-queue Scheduling: Scheduling must be done between the queues (e.g., Fixed priority preemption—foreground queue always runs before background queue).

F. Multilevel Feedback Queue (MLFQ) Scheduling

Allows a process to move between queues. The idea is to separate processes according to the characteristics of their CPU bursts.

  • Logic: If a process uses too much CPU time, it is moved to a lower-priority queue. If a process waits too long in a lower-priority queue, it may be moved to a higher-priority queue (aging).
  • Parameters defining MLFQ:
    1. Number of queues.
    2. Scheduling algorithm for each queue.
    3. Method used to determine when to upgrade a process.
    4. Method used to determine when to demote a process.
  • Example:
    • Queue 0: RR with quantum 8ms (Highest Priority).
    • Queue 1: RR with quantum 16ms.
    • Queue 2: FCFS (Lowest Priority).

6. Thread Scheduling

Most modern operating systems schedule kernel-level threads, not processes.

Scope of Contention

  1. Process-Contention Scope (PCS):
    • Occurs in Many-to-One and Many-to-Many models.
    • The thread library schedules user-level threads to run on an available LWP (Lightweight Process).
    • Scheduling is internal to the process.
  2. System-Contention Scope (SCS):
    • Occurs in One-to-One models (Windows, Linux).
    • The kernel decides which kernel-level thread to schedule onto a CPU.
    • Competition is among all threads in the system.

7. Multiprocessor Scheduling

Scheduling becomes more complex when multiple CPUs are available.

Approaches

  1. Asymmetric Multiprocessing: Only one processor (the master) accesses the system data structures, reducing the need for data sharing. Other processors execute only user code. Simple, but the master is a bottleneck.
  2. Symmetric Multiprocessing (SMP): Each processor is self-scheduling. All processors may be in a common ready queue, or each may have its own private queue. This is the standard for modern OS (Windows, Linux, macOS).

Issues in SMP

  • Processor Affinity: A process has an affinity for the processor on which it is currently running because the cache contains the process's data.
    • Soft Affinity: OS attempts to keep process on same CPU but doesn't guarantee it.
    • Hard Affinity: System calls allow specifying a subset of CPUs a process can run on.
  • Load Balancing: Keeps the workload evenly distributed across all processors.
    • Push Migration: A specific task checks load and pushes processes from overloaded to idle CPUs.
    • Pull Migration: An idle processor pulls a waiting task from a busy processor.

8. Real-Time Scheduling

Real-time systems are defined by their ability to produce results within a specified deadline.

Types of Real-Time Systems

  1. Soft Real-Time: Critical real-time processes receive preference over non-critical processes, but there is no guarantee they will finish by a deadline.
  2. Hard Real-Time: A task must be serviced by its deadline; service after the deadline has expired is the same as no service at all.

Characteristics

  • Event Latency: The amount of time that elapses from when an event occurs to when it is serviced.
  • Interrupt Latency: Time from arrival of interrupt to start of ISR (Interrupt Service Routine).

Algorithms

  • Rate Monotonic Scheduling: A static priority policy. Tasks with shorter periods (higher frequency) get higher priorities.
  • Earliest Deadline First (EDF): A dynamic priority policy. The task with the absolute closest deadline gets the highest priority. Priorities change as deadlines approach.