04_CPU_Scheduling.md

CPU Scheduling

CPU and I/O Bursts in Program Execution

Distribution of CPU-burst Time

Classification of Process Characteristics

Processes are classified into the following two types based on their characteristics

• CPU bound job
  • Tasks that use the CPU for long periods and I/O for short periods
    • few very log CPU bursts
  • Computation-intensive jobs
  • e.g.) Cases where long computations are performed such as scientific calculations
• I/O bound job
  • Tasks that use the CPU for short periods and I/O for long periods
    • many short CPU bursts
  • Jobs that require more time for I/O than for CPU computation
  • e.g.) Cases with heavy interaction with humans

The Need for CPU Scheduling

• CPU Scheduling is needed because various kinds of jobs (=processes) are mixed together
  • Appropriate response should be provided for interactive jobs
    • Jobs that interact with humans
  • System resources such as CPU and I/O devices should be used evenly and efficiently
• The goal is to allow I/O bound jobs to acquire the CPU quickly
  • Because they need to get the CPU first to use it quickly and move on
  • Fast response is needed since they interact with humans
  • If the CPU cannot be given while I/O work is pending after CPU usage

CPU Scheduler & Dispatcher

CPU Scheduler

• The code within the operating system that performs CPU scheduling
• Selects which process to give the CPU to from among the Ready state processes

Dispatcher

• Hands CPU control to the process selected by the CPU Scheduler
• This process is called a context switch

Cases When CPU Scheduling is Needed

When the following state changes occur for a process

1. Running → Blocked (e.g. system call requesting I/O)
2. Running → Ready (e.g. timer interrupt due to allocation time expiry)
3. Blocked → Ready (e.g. interrupt after I/O completion)
4. Terminate

→ Scheduling in cases 1 and 4 is nonpreemptive (= voluntarily surrendered, not forcefully taken)

→ All other scheduling is preemptive (= forcefully taken)

Scheduling Criteria

Performance Index (= Performance Measure)

• CPU Utilization
  • keep the CPU as busy as possible
  • Higher CPU utilization is better, without leaving the CPU idle
• Throughput
  • number of processes that complete their execution per time unit
  • Higher throughput is better
• Turnaround Time
  • amount of time to execute a particular process
  • Total time from starting a CPU burst until going out for an I/O burst
    • Time waited in the ready queue + actual CPU usage time
• Waiting Time
  • amount of time a process has been waiting in the ready queue
  • Not just the first waiting time, but the total sum of all waiting times when coming to use the CPU
• Response Time

  • amount of time it takes from when a request was submitted until the first response is produced, not output

    (for time-sharing environment)

  • The time from when a process comes to use the CPU until it first uses it

    • NOT the time from when the process starts until it first uses the CPU!!

Scheduling Algorithms

FCFS (First-Come First-Served)

• Description
  • Executes processes in the order they arrive in the ready queue
• Problem
  • Convoy effect
    • short process behind long process
    • Short processes take a long time because a long-running process arrived first and uses the CPU for an extended period

SJF (Shortest Job First)

• Description

  • Uses the next CPU burst time of each process for scheduling
  • Schedules the process with the shortest CPU burst time first
    • Gives the CPU first to the job that wants to use it the shortest

• Types

  Two schemes

  • Non-preemptive
    • Once the CPU is acquired, it is not preempted until the CPU burst is completed
  • Preemptive
    • If a new process arrives with a shorter CPU burst time than the remaining burst time of the currently executing process, the CPU is taken away
    • This method is also called Shortest-Remaining-Time-First (SRTF)

• Characteristics

  • SJF is optional
    • Guarantees minimum average waiting time for the given processes
    • Optimal in terms of waiting time
  • A priority number (integer) is associated with each process
    • CPU allocated to the process with high priority
      • (smallest integer = high priority)
  • SJF is a type of priority scheduling
    • priority = predicated next CPU burst time

• Problems

  • Starvation
    • low priority processes may never executed
  • Aging
    • as time progresses increase the priority of the process

• Predicting the next CPU Burst Time

  How can we know the next CPU burst time? (input data, branch, user ...)

  • Only estimation is possible
  • Estimated using past CPU burst times (exponential averaging)

Priority Scheduling

A priority number (integer) is associated with each process

• Characteristics
  • CPU is allocated to the process with the highest priority
    • smallest integer == highest priority
  • SJF is a type of priority scheduling
• Problem
  • Starvation : low priority process may never execute
• Solution
  • Aging : as time progresses, increase the priority of the process

Round Robin (RR)

• Characteristics

  • Each process has an equal allocation time (time quantum)

    • Generally 10 - 100 ms

  • When the allocation time expires, the process is preempted and goes to the back of the ready queue to wait again

  • If n processes are in the ready queue with an allocation time of q time units, each process gets 1/n of the CPU time in units of at most q time units

    → No process waits more than (n-1)q time units
    

• Performance

  • q large → FCFS
  • q small → context switch overhead increases

• Advantages

  • Generally has longer average turnaround time than SJF, but response time is shorter

Multilevel Queue

• Ready queue is split into multiple queues

  • foreground
    • interactive job
  • background
    • batch job (no human interaction)

• Each queue has an independent scheduling algorithm

  • foreground
    • RR
  • background
    • FCFS

• Scheduling for the queues is needed

  Assigning wait to each queue

  • Fixed priority scheduling
    • Divides into two priority groups (foreground, background)
    • serve all from foreground then from background
      • All processes in the foreground are executed first, then processes in the background group are executed
    • possibility of starvation
  • Time slice
    • Allocates CPU time to each queue in appropriate proportions
    • e.g.
      • 80% to foreground in RR
      • 20% to background in FCFS

• Queue distribution by Priority

  

  Once a queue is assigned, it does not change

Multilevel Feedback Queue

• Processes can move to different queues

  • Higher queues have higher priority
  • Lower queues are filled only when upper queues are empty

• Aging can be implemented in this manner

  • Sending aged jobs to upper queues

• Parameters that define a Multilevel feedback queue scheduler

  1. Number of queues
  2. Scheduling algorithm for each queue
  3. Criteria for sending a process to an upper queue
  4. Criteria for demoting a process to a lower queue
  5. Criteria for determining which queue a process enters when it comes for CPU service

• e.g.

  

• Three queues

  • Q0 - time quantum 8 ms
  • Q1 - time quantum 16 ms
  • Q2 - FCFS

• Scheduling Flow

  • A new job enters queue Q0
  • It acquires the CPU and runs for the allocation time of 8ms
  • If it cannot finish within 8ms, it is demoted to Q1
  • It waits in line at Q1, acquires the CPU, and runs for 16ms
  • If it cannot finish within 16ms, it is demoted to Q2

Multiple-Processor Scheduling

• Scheduling becomes more complex when there are multiple CPUs

• In the case of Homogeneous processes

  CPUs where everyone has the same processing capability

  • Can line up in a single queue and have processors pick from it
  • but, if there are processes that must be executed on a specific processor, the problem becomes more complex

• Load sharing (= Load balancing)

  • A mechanism is needed to appropriately share the load to prevent jobs from being concentrated on some processors
  • Separate queues vs shared queue approach

• Symmetric Multiprocessing (SMP)

  • Each processor makes its own scheduling decisions
  • For uniform tasks across multiple processors, it may be more efficient not to have a coordinating processor

• Asymmetric multiprocessing

  • One processor takes responsibility for system data access and sharing, and the other processors follow it

Real-Time Scheduling

• Hard real-time systems
  • Must be scheduled to finish within a specified time
  • For this purpose, there are cases where the CPU arrival times of processes are known in advance for scheduling (off-line scheduling)
    • ↔ online scheduling
      • The system dynamically schedules processes during execution
      • Since decisions are made at the point when tasks arrive, only information available at execution time can be used
• Soft real-time computing
  • Must ensure higher priority compared to general processes
  • e.g. Raising the priority of the video playback process so it can acquire the CPU first and prevent video stuttering

Thread Scheduling

Multiple CPU execution units within a single process

• Local Scheduling
  • In the case of User level threads, the user-level thread library determines which thread to schedule
• Global Scheduling
  • In the case of Kernel level threads, the kernel's short-term scheduler determines which thread to schedule, just like regular processes

Algorithm Evaluation

• Queueing models
  • Calculates various performance index values using arrival rate and service rate given as probability distributions
• Implementation & Measurement
  • Implements the algorithm in an actual system and measures performance against actual workloads for comparison
• Simulation
  • Writes the algorithm as a simulation program and compares results using trace as input
  • What is trace?
    • Data that serves as input for the simulation
    • Must be credible (should be representative of actual program behavior)