CPU Scheduling

CPU Scheduling Concepts

• Objective of Multiprogramming

  • Maximize CPU utilization by selecting and running one process from the ready queue when the CPU is available.

• Process Execution Cycle

  • Alternation between CPU execution and I/O wait forms the process execution cycle.
  • Process types:
  • CPU-bound Process:
    • Characterized by very long CPU bursts.
  • I/O-bound Process:
    • Characterized by short CPU bursts.

• Process Flow

  • A simple flow might involve the following operations:
  • x := 0;
  • read from file;
  • x := x + y;
  • write to file;
  • Wait for I/O;
  • Alternates between CPU bursts and I/O bursts.

Switching CPU States

• State Transitions
  • From running to waiting state: Triggered by I/O requests or waiting for resources.
  • From running to ready state: Happens on timer interruptions or when preemption occurs.
  • Process termination: Frees up CPU resources.

CPU Scheduler Types

• Short Term Scheduler (STS):

  • Chooses from the processes in memory that are ready for execution.
  • Must act quickly, managing the ready queue efficiently, which can be FIFO, priority-based, etc.

• Medium Term Scheduler (MTS):

  • Manages swapping processes in and out of memory to optimize CPU usage.

• Long Term Scheduler (LTS):

  • Controls the entry of processes into the memory for execution.
  • Usually invoked when a job finishes executing.
  • Affects multiprogramming by choosing between CPU-bound and I/O-bound jobs.

Preemption

• Preemptive vs Non-preemptive Scheduling
  • Non-preemptive: Process retains CPU until it voluntarily relinquishes it by terminating or waiting. Example: Windows 3.x.
  • Preemptive: Process can be interrupted and resumed later; requires special hardware support (like timers) and can lead to race conditions.

Dispatcher

• Role:
  • Switches control of CPU to the selected process.
  • Responsible for context switching, managing user mode transitions, and executing the selected process’s code.
• Dispatch Latency:
  • The time taken to stop one process and start another; should be minimized.

Scheduling Criteria

• Metrics for Evaluation:
  • CPU Utilization: Higher usage is preferable.
  • Throughput: Number of processes completed per time unit.
  • Turnaround Time: Total time taken to execute a process from submission to completion.
  • Waiting Time: Total time spent waiting in the ready queue.
  • Response Time: Time until the first response is produced for a request, particularly in interactive systems.
  • Aim to minimize variance and maximum response time.

Scheduling Algorithms

FCFS (First Come First Served)

• Processes are executed in the order they arrive.
• Characteristics:
  • Non-preemptive, easy implementation.
  • Generally leads to poor performance in waiting time, turnaround time, and response time.

SJF (Shortest Job First)

• Processes are scheduled based on the length of their next CPU burst.
• Non-preemptive: Once a process starts, it runs to completion.
• Preemptive: A new process can interrupt the current one if it has a shorter burst.
• Optimality: Provides minimum average waiting time and turnaround time.

Priority Scheduling

• Each process is assigned a priority, and those with higher priority are executed first.
• Can be preemptive or non-preemptive. Risks include potential starvation of low-priority processes.

Round Robin (RR) Scheduling

• Assigns a fixed time quantum for each process.
• Handles processes on a first-come, first-served basis within each time quantum.
• Performance Consideration: Turnaround time and waiting time depend significantly on the size of the time quantum.

Multilevel Queue Scheduling

• Separates ready queues into different categories, with each queue having its own scheduling algorithm.

Multilevel Feedback Queue Scheduling

• Allows processes to move between queues to prevent starvation, adjusting based on process behavior.

Real-time Scheduling

• Used in systems requiring guaranteed timing for tasks.
• Hard real-time: Must complete within time limits.
• Soft real-time: Prioritizes critical processes in a system general-purpose multitasking setting.

Linux Scheduling Example

• Linux has varying approaches across versions (2.2, 2.5, 2.6.23) that evolve from priority-based scheduling systems to the Completely Fair Scheduler (CFS) which aims to distribute CPU time proportionally based on process priority and interactivity.
• Current Approach (CFS):
  • Tasks are assigned CPU time based on their “nice” values and virtual run time, which prioritize responsiveness in general multitasking environments.