Lesson 5 (CPU Scheduling)

• Basic Concepts:

  • Maximum CPU utilization obtained with multiprogramming
  • CPU – I/O Burst Cycle: Process execution consists of a cycle of CPU execution and I/O wait
  • CPU burst followed by I/O burst
  • CPU burst distribution is of main concern
  • Characterized with a large number of short CPU bursts and a small number of long CPU bursts
  • I/O bound program typically has many short CPU bursts
  • CPU bound program might have a few long CPU bursts
• Scheduling Criteria:

  • CPU utilization – keep the CPU as busy as possible
  • Throughput – number of processes that complete their execution per time unit
  • Turnaround time – amount of time to execute a particular process
  • Waiting time – amount of time a process has been waiting in the ready queue
  • Response time – amount of time it takes from when a request was submitted until the first response is produced
• Scheduling Algorithms:

  • First-Come, First-Served Scheduling (FCFS):
  • Simplest CPU-scheduling algorithm
  • Process that requests the CPU first is allocated the CPU first
  • Average waiting time under the FCFS policy is often quite long
  • Shortest-Job-First (SJF) Scheduling:
  • Associate with each process the length of its next CPU burst
  • Two schemes: nonpreemptive and preemptive
  • SJF is optimal and gives minimum average waiting time for a given set of processes
• Determining Length of Next CPU Burst:

  • Can only estimate the length – should be similar to the previous one
  • Pick process with shortest predicted next CPU burst
  • Exponential averaging is used to predict the length of the next CPU burst
• Priority Scheduling:

  • A priority number (integer) is associated with each process
  • CPU is allocated to the process with the highest priority
  • SJF is a special case of priority scheduling algorithm where priority is the inverse of predicted next CPU burst time
• Dispatcher:

  • Dispatcher module gives control of the CPU to the process selected by the short-term scheduler
  • Involves switching context, switching to user mode, and jumping to the proper location in the user program to restart that program
  • Dispatch latency – time it takes for the dispatcher to stop one process and start another running
• Priority Scheduling Issues:

  • Starvation: low priority processes may never execute
  • Indefinite blocking: can leave some low priority processes waiting indefinitely
• Solution to Priority Scheduling Issues:

  • Aging: as time progresses, increase the priority of the process
• Round Robin (RR):

  • Each process gets a small unit of CPU time (time quantum q), usually 10 - 100 milliseconds
  • Designed especially for time-sharing systems
  • If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once
  • No process waits more than (n - 1)q time units
  • Timer interrupts every quantum to schedule the next process
  • Performance:
  • q large → FIFO
  • q small → q must be large with respect to context switch, otherwise overhead is too high
• Multilevel Queue:

  • Ready queue is partitioned into separate queues (e.g., foreground (interactive) and background (batch))
  • Each queue has its own scheduling algorithm (foreground – RR, background – FCFS)
  • Scheduling must be done between the queues using fixed priority scheduling
  • Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes (e.g., 80% to foreground in RR, 20% to background in FCFS)
• Scheduling Policies and Starvation:

  • Different scheduling policies (FCFS, Round Robin, SJF, SRT, Priority, Multilevel, Multilevel Feedback)
  • Each policy has a selection function, decision mode, throughput, response time, overhead, and effect on processes
  • Starvation can occur in some scheduling policies, penalizing low priority processes
• Real-Time CPU Scheduling:

  • Challenges in real-time systems (soft and hard real-time)
  • Two types of latencies affecting performance: interrupt latency and dispatch latency
• Priority-Based Scheduling:

  • For real-time scheduling, scheduler must support preemptive, priority-based scheduling
  • Processes with periodic characteristics require CPU at constant intervals
  • Processing time (t), deadline (d), period (p) must follow certain constraints
• Rate Monotonic Scheduling:

  • Priority assigned based on the inverse of the period
  • Shorter periods receive higher priority, longer periods lower priority
  • CPU utilization formula and limitations
• Linux Scheduling:

  • Two algorithms: time-sharing and real-time
  • Time-sharing algorithm uses prioritized credit-based system
  • Real-time scheduling includes soft real-time and POSIX.1b compliant classes (FCFS and RR)
  • Completely Fair Scheduler (CFS) in Linux version 2.6.23+
  • Real-time tasks have static priorities mapped into a global priority scheme
• Linux Scheduling (Cont.):

  • CFS scheduler specifics, including scheduling classes, priority calculation, target latency, virtual run time, and decision-making process
  • Real-time scheduling according to POSIX.1b standards
• Questions?