Teaching a tiny kernel to share fairly
Inside PintOS, a teaching operating system. Fixing what happens when a low-priority thread holds the lock a high-priority one needs.
- Built with
- C, PintOS, QEMU
The question
A kernel scheduler sounds simple: run the most important thread. What happens when the most important thread is stuck waiting on a lock that an unimportant thread is holding?
What I tried
With a small team, I worked through the threads project of PintOS, Stanford’s teaching kernel:
- No more busy waiting: sleeping threads used to burn CPU while they waited, so I replaced that with a queue the timer interrupt wakes up.
- Priority scheduling with donation: a thread waiting on a lock lends its priority to the holder, even across chains of nested locks.
- A multi-level feedback queue scheduler: priorities decay over time based on recent CPU use. The kernel has no floating point, so all of it runs on fixed-point arithmetic I wrote by hand.
fixed-point math at 2am hits different.
What I kept
Priority inversion is the bug where the important thing waits on the unimportant thing. It shows up far outside kernels, in queues, teams and on-call rotations. Donation is the fix there too: whoever is blocked lends their urgency to whoever is holding the lock.