Scheduling

Wikipedia · Scheduling (computing) · CC BY-SA 4.0

The scheduler decides which process gets the CPU next. The algorithm determines fairness, throughput, and response time. There is no single best policy: every choice is a tradeoff.

First-Come, First-Served (FCFS)

The simplest policy: processes run in arrival order. No preemption. Problem: a long job blocks everyone behind it (the convoy effect).

Shortest Job First (SJF)

Run the process with the shortest burst time next. Optimal for minimizing average waiting time, but requires knowing burst lengths in advance. In practice, the OS estimates them.

Round-Robin

Each process gets a fixed time quantum. When the quantum expires, the process goes to the back of the ready queue. Good for time-sharing. Small quantum means more context switches. Large quantum degrades to FCFS.

Scheme

; Round-robin scheduling simulation
; Each process: (name . burst-remaining)

(define (round-robin procs quantum)
  (define (step queue time log)
    (if (null? queue)
        log
        (let* ((proc (car queue))
               (name (car proc))
               (burst (cdr proc))
               (run (min burst quantum))
               (remaining (- burst run))
               (new-time (+ time run))
               (entry (string-append name ":["
                        (number->string time) "-"
                        (number->string new-time) "]")))
          (if (> remaining 0)
              (step (append (cdr queue) (list (cons name remaining)))
                    new-time
                    (append log (list entry)))
              (step (cdr queue)
                    new-time
                    (append log (list entry)))))))
  (step procs 0 '()))

(define procs (list (cons "P1" 4) (cons "P2" 3) (cons "P3" 5)))

(display "Round-Robin (quantum=2):") (newline)
(for-each (lambda (e) (display "  ") (display e) (newline))
          (round-robin procs 2))

; Round-robin scheduling simulation
; Each process: (name . burst-remaining)

(define (round-robin procs quantum)
  (define (step queue time log)
    (if (null? queue)
        log
        (let* ((proc (car queue))
               (name (car proc))
               (burst (cdr proc))
               (run (min burst quantum))
               (remaining (- burst run))
               (new-time (+ time run))
               (entry (string-append name ":["
                        (number->string time) "-"
                        (number->string new-time) "]")))
          (if (> remaining 0)
              (step (append (cdr queue) (list (cons name remaining)))
                    new-time
                    (append log (list entry)))
              (step (cdr queue)
                    new-time
                    (append log (list entry)))))))
  (step procs 0 '()))

(define procs (list (cons "P1" 4) (cons "P2" 3) (cons "P3" 5)))

(display "Round-Robin (quantum=2):") (newline)
(for-each (lambda (e) (display "  ") (display e) (newline))
          (round-robin procs 2))

Priority scheduling

Each process has a priority. Highest priority runs first. Risk: starvation of low-priority processes. Solution: aging, which gradually increases priority of waiting processes.

Multilevel queues

Multiple ready queues, each with its own scheduling algorithm. Foreground processes get round-robin. Background processes get FCFS. A multilevel feedback queue lets processes move between queues based on behavior.

Metrics

Turnaround time = completion time minus arrival time. Waiting time = turnaround time minus burst time. Response time = first run minus arrival time. Good schedulers minimize all three, but tradeoffs are inevitable.

Scheme

; FCFS vs SJF: compare average waiting times
; Processes: (name burst-time)

(define (avg-wait-fcfs bursts)
  (define (helper bs wait total count)
    (if (null? bs)
        (/ total count)
        (helper (cdr bs) (+ wait (car bs))
                (+ total wait) (+ count 1))))
  (helper bursts 0 0 0))

(define (avg-wait-sjf bursts)
  (avg-wait-fcfs (sort bursts <)))

(define bursts '(6 2 8 3))

(display "Bursts: ") (display bursts) (newline)
(display "FCFS avg wait: ") (display (avg-wait-fcfs bursts)) (newline)
(display "SJF  avg wait: ") (display (avg-wait-sjf bursts))
; SJF always wins on average waiting time

Neighbors

⚙ Sorting — scheduling is sorting by priority, burst time, or arrival
🎛 Control Ch.3 — PID control: CPU schedulers like CFS use feedback from CPU utilization to adjust time-slice allocation
♟ Game Theory Ch.13 — volunteer's dilemma and priority: scheduler priority queues solve a coordination game about who runs first
⚙ Algorithms Ch.7 — greedy and priority-queue algorithms: EDF and priority scheduling are greedy algorithms on a priority queue

Foundations (Wikipedia)

← Processes by june.kim Threads and Concurrency →