Required reading: Eliminating receive livelock

Notes based on prof. Morris's lecture on scheduling (6.824, fall'02).


In short, scheduling is a system problem. There are many schedulers; they interact. The CPU scheduler is usually the easy part. The hardest part is system structure. For example, the existence of interrupts is bad for scheduling. Conflicting goals may limit effectiveness.

Case study: UNIX in 1990

What did UNIX scheduling look like at time of Livelock paper?
  No spin-locks in kernel

Different contexts:
  Process, user half
  Process, kernel half
  Soft interrupts
  Device ("hard") interrupts

Rules for context transitions:
  Hardware can force hard interrupt any most times except in a hard intr
  Hardware can force soft interrupt except during a soft or hard intr
  Interrupt must complete before interrupted code can continue
    Interrupt shares stack
  Timer interrupt does *not* switch kernel halves
    Only voluntary switch via sleep()
  Never runs a user half if any kernel half wants to run
  User halfs pre-emptable via timer interrupt

Thus this priority structure:
  hard intr > soft intr > kernel half > user half

Why no pre-emptable kernel halves?
  To avoid most locks (remember -- uniprocessor)
  Only have to worry about concurrency from interrupts
  So kernel halves disable interrupts in critical sections

Why soft interrupts?
  For time-consuming processing in response to hard interrupts
  Hard interrupt does time-critical stuff, schedules soft interrupt
    More hard interrupts can occur during soft int
  Short hard interrupts avoid input overruns
  Example: generating TCP ACKs (don't want to wait for some kernel half...)
Paper's application is packet forwarding
  How did that work?

Receive interrupt
  Copy incoming packet to memory
  Append packet pointer to IP Input queue
  Schedule IP soft interrupt

IP soft interrupt
  For each packet in IP input queue
    Decide what to do with it
    Forward out a different network interface?
      Append packet pointer to output Q
      Give packet to output i/f h/w if idle
    Deliver to a user program?
      Append packet pointer to socket Q
      Wake up process

Transmit interrupt
  Free last packet buffer
  Copy packet from output Q to h/w
  Tell h/w to transmit

Network interface hardware (e.g. ethernet)
  Has small receive buffer on interface h/w (a few packets)
  Raises receive interrupt for each received packet
  Has small output buffer (a few packets)
  Transmit-complete interrupts

Why the input queue?

Why the output queue?

Is this a good arrangement?

Paper discussion