Operating Systems 2026F Lecture 15

Video

Video from the lectures given on November 12th and 13th, 2026 are now available:

• Lecture 15A
• Lecture 15B

Notes

Lecture 15A

Lecture 15A
-----------
Semaphores &
condition variables

kernel modules

A2 is graded
A3 will be posted today

Mutual exclusion
 - think a stretch of railroad track, you
   only want one train on it at a time
 - so you want trains to have exclusive access
   to a track. Thus the presence of one
   excludes the presence of another


Mutual exclusion refers to critical sections of code
 - code interacting with shared resources

regular code   <-- can run as many copies in parallel
                   as we want
...
critical code   <-- only one copy of this can run
                    at any time
...
regular code

Why bother with critical sections?
 - because we don't want corrupted data structures

Typical way to protect critical sections of code and their associated data is to use mutexes, or binary semaphores

semaphores are the "signalling lights" of computation to prevent trains from running into each other
 - and a mutex is just a stop and go signal
 - general semaphores can have many values (numbers)

Mutexs are normally talked about as "locks"
 - code grabs a lock before accessing key data
   or other resources
 - code releases the lock when done

What happens if someone else has the lock?
 - either grabbing the lock fails,
 - or you block (wait)  <--- common version

What does it mean for a process to sleep?
 - it means the process is no longer running on any core

The kernel has many processes active:
 - some are actively running (using a core)
 - some are ready to run (waiting for a core)
 - some are sleeping/blocked (waiting for an event)

When a process goes to sleep
 - the process sets a handler to be called when
   an event occurs
 - it then gives up the CPU it is using

It takes time (CPU cycles) to put a process to sleep
and wake it up again

Why?
 - because there's a lot of state associated with a running program, and that all has to be saved and then restored

So when the expected wait is short, we busy wait
 (that's what spinlocks do)

Condition variables are used to coordinate behavior
 - wake up other threads/processes when
   they were waiting for an event


You don't want to implement condition variables, semaphores, or mutexs on your own. They are very tricky to get right. Why?

 - the memory hierarchy!

Remember a variable in your code maps to multiple values in memory
 - registers, L1-L3 cache, main memory, maybe even swap
   (will explain swap later)
 - registers, L1-L3 are duplicated between cores

It is possible to keep the copies perfectly in sync,
but then there's (almost) no point in keeping copies!

To do any kind of concurrency coordination, you need
reliable communication. If you're doing it with
shared memory, you have to make sure state is REALLY shared
 - so you have to use special CPU instructions

We have two kinds of instructions
 - test & set  <- if + assignment
 - swap        <- swap two variables (values in memory)

Both of these work "atomically"
 - as if they are indivisible

transactions in databases are used to get atomic-like semantics
 - if we get interrupted in the middle of a transaction,
   any changes get undone

Transactions
 - think about buying airline tickets
   (or concert tickets with reserved seating)
 - it inherently involves multiple steps
   - pay for the ticket
   - reserve the actual seat
   - update customer information,
     show they own the ticket
 - we want the purchase to happen atomically, but
   in practice it involves lots of steps
 - so with a transaction, we keep records so we can undo intermediate steps
   - only on a "commit" is the purchase completed
     and it can't be undone
 
 
Swap two values in X and Y

 Z = X
 X = Y
 Y = Z

Linux kernel modules
 - real kernel programming!

So, what's a kernel module?

The linux kernel is big program
 - so we want to decompose it

One way to decompose a kernel is into multiple processes
 - "microkernel architecture"
 - what is actually running in supervisor mode is
   a relatively small bit of code
 - everything else runs in regular processes

The linux kernel is a "monolithic" kernel
 - everything is in the same address space
   (like a process, but not quite)

A kernel module is just code that gets loaded into the address space of the kernel

so is a kernel module the same as eBPF?
 - eBPF has restrictions, limitations
 - kernel modules can do everything and anything
   (and there are almost no checks)

Most modules are for device drivers

What's a device driver?

The kernel abstracts system hardware
 - to give a uniform interface to regular applications

The core kernel implements the basic abstractions
device drivers implement the mapping between
the abstractions and the specifics of the hardware
 - different hardware, different device driver

One peculiarity of the Linux kernel is it doesn't provide a stable API or ABI to kernel modules
 - VERY different from Windows or macOS

Lecture 15B

Lecture 15B
-----------
A2 is graded
 - will upload today

Midterms are almost there
 - will be finished in the next few days

A3 is almost done
 - you'll get a week
 - it is just a file copy program based on T6 code

Mutexs are binary semaphores
 - used to enforce mutual exclusion, hence the name

Mutexes are like the ad-hoc traffic lights used when only one lane is available for traffic
 - actually it is all traffic lights!

Semaphores, esp mutexs, are for enforcing mutual exclusion
condition variables are used to "wake up" another process/thread
that is waiting (for a condition to be reached)

CPUs (cores) are shared resources

When a process "sleeps", it is giving up its current CPU (that it was running on) and is allowing another process to run (or thread)
 - so this means the process is relying on some event to happen,
   and when that event happens it wants to be woken up
   (i.e., get the CPU back)

So what sort of events?
 - timer going off
 - I/O to be completed
 - another process to communicate
 - network traffic to arrive
 - (any system call to complete)

Deciding which process or thread should get access to which CPU is the problem of CPU scheduling
 - will discuss more soon!

Going to sleep only makes sense if the wait is long enough
 - giving up and getting back on a CPU takes some work
   (have to save and restore CPU state, including caches and address space)

So for short waits, what do you do?
 - you spin!
 - i.e., you run a tight loop that checks for the condition to be true
 - there are kinds of mutexs known as spinlocks that do this
   (mostly used in the kernel)

DO NOT WRITE MUTUAL EXCLUSION PRIMITIVES FROM SCRATCH
 - they require carefully written assembly to work properly!

Why? the memory hierarchy!
 - many copies of in-use variables
   (between caches, registers, main memory)
 - and for concurrency we need those variables to have the same
   value at the same time
   - so the copies have to be kept in sync!
   - but we can't even see many of the copies from our code!

To get around these issues, you need to use special assembly language instructions
 - test & set
 - swap

The idea of these instructions is they do a set of operations "atomically" which normally would not be

atomic = indivisible (original greek?)

We need this atomic property to make sure we don't have TOCTTOU

if (x) then y

How do we know x is still true when we do y?


To swap the value of X and Y

 Z = X
 X = Y
 Y = Z

If you can make a swap atomic, you can grab a lock by just swapping a value and checking the old value to see whether the lock was available

the general form of making groups of operations atomic is transactions
 - from databases


KERNEL MODULES
 - that's next week!

kernel modules let us add and remove code from a running kernel
 - but don't we already have that with eBPF?

eBPF is limited in its functionality
 - designed to monitor the system, not provide raw functionality
   (but that is changing)
 - limited by a verifier

How do we decompose kernel functionality?
 - because its a big program dealing with complex problems!

Why can't we just use processes?
 - some do! microkernels!

so some code has to be in the kernel (managing CPU & address spaces)
 - but rest can go in processes
 - what code is the rest?

Big advantage of microkernels is they can be easier to debug
 - you can trace, restart processes easily

Linux uses a "monolithic" architecture instead
 - kernel only uses one address space, rather than many
   that are separated by protection boundaries (e.g. processes)

Linux kernel modules are just code that is loaded into the kernel's address space
 - no real protections against this code doing whatever it wants,
   for good or ill

Most kernel modules are for device drivers

Device drivers are adaptors between the specifics of hardware and the abstractions of the kernel

Why are all of the modules duplicated between even minor versions of the kernel?
 - because the Linux kernel doesn't offer a stable API or ABI to
   kernel modules

Android is a mess in part because of this lack of a stable API and ABI
 - not Linux's fault, it is Google's fault!