Operating Systems 2026F Lecture 13

Video

Video from the lectures given on November 5th and 6th, 2026 are now available:

• Lecture 13A
• Lecture 13B

Notes

Lecture 13A

Lecture 13A
-----------
Concurrency

Original UNIX didn't have threads -
 it only had processes

So what's the difference?

A thread is an execution context
A process is one or more execution contexts +
  an address space

an execution context is CPU state
 - the value of all the registers (basically)
 - function stack
 - plus any associated kernel context

Threads were introduced when we got SMP systems
 - symmetric multiprocessing, e.g., multiple cores

You're sharing memory between threads
 - how do you keep them from messing with each other?

Concurrent access to any data in memory is inherently dangerous
 - TOCTTOU errors abound
   "time of check to time of use"

if (x) {
  do blah
}

If the inside of the if statement isn't safe if the value of x changes after the check...you're in trouble.

It might seem like everything would be fine, but for any variable x, there can be multiple values
 - every thread can have its own value of x
 - even if there's only supposed to be one copy of it

The multiple copies come from the memory hierarchy
 - we make copies to make things fast
 - but those copies come back to bite us when
   we do concurrent programming
 - remember the fastest caches are core specific!

My general advice is to use processes with shared memory
 - only share exactly what you need
 - rather than share everything


Concurrency is not parallelism
 - parallel processing is inherently concurrent
 - but even with one CPU you can have concurrency

concurrent systems have multiple logical execution contexts that can interfere with each other

signal handlers are concurrent but they are not parallel
 - the regular process pauses while the signal handler executes
 - but because they are in the same address space,
   they can interfere with each other


Concurrency arises when you have scheduling of CPUs
 - sharing between multiple running programs

Assume we have processes A, B, and C running on a system with a single core/single CPU

One way to handle sharing is for each process to run to completion before the other starts.
 - this is batch processing

BATCH PROCESSING
----------------
A starts
A finishes
B starts
B finishes
C starts
C finishes

But Linux is built on the idea of *time sharing*
 - each process gets a "slice" of CPU time
 - when it is done with its slice, another process is
   allowed to run (or the kernel does its work)

We want the computer to multitask, i.e. do multiple things at the same time by splitting its attention between the tasks

Two basic ways to multitask
 - cooperatively
 - preemptive multitasking

With cooperative multitasking, each program has to be "polite"
  - it does some work but then gives up the CPU
    before it has spent too much time
  - if it has a lot of work to do, it splits it up
    into pieces that fit within a reasonable share

with preemptive multitasking
  - there's a timer set every time a process starts working
  - when the timer goes off (it has used up its time slice), the process is put to sleep and another process is allowed to run

pipes
 - a kernel implementation of the producer-consumer pattern, using file descriptors

Think of two people doing dishes
 - one washing, one drying
 - if either gets too far behind or ahead, the other
   will have to say stop

Why not use pipes for all inter-process communication?
 - it is easy to use but potentially slow
 - but it really isn't that slow!

Going back to filesystems

Why inodes?

Because directories are then just maps between names and inodes
 - and inodes are where the complexity of storing file contents comes in

superblock
 - it is the "head node" of the filesystem data structure
 - has info on the structure of the filesystem
 - stored redundantly to guard against corruption

Lecture 13B

Lecture 13B
-----------

Concurrency

Concurrency is not parallelism
 - parallel computing is concurrent
 - concurrency can happen without parallelism

Concurrency means that multiple computations can interact with each other
 - we can do this without parallelism with shared resources

Signal handlers involve concurrency
 - because the handler interrupts the regular program flow
 - and this interruption could disrupt program flow
   if you aren't careful

It is all about side effects

Consider TOCTTOU
 - time of check to time of use

if (x) {
  do blah
}

Implicitly with such code we assume that whatever the condition x was, it holds when we do blah.

But what if something came in and changed x after we tested it but before doing blah?

The entire point of the process model is to avoid concurrency as much as possible

But we've got to talk about threads

A thread is an execution context
A process is one or more execution contexts
  + an address space

What is an execution context?
 - all the state associated with an executing program,
   outside of global shared memory
 - CPU registers + stack + kernel state

Original UNIX didn't have threads

I don't like threads
 - most of the time, you're better off with processes
 - if you need shared memory, share just what you need!

Threads became more popular once we had SMP systems
 - symmetric multiprocessing, i.e., multiple cores
 - without threads, any process is limited to a single core at a time

But threads involve sharing all of a process's memory
 - even the parts that shouldn't be shared!
 - any error by one thread will propagate to other threads,
   in potentially very difficult to debug ways

concurrency bugs are hard to track down because they depend on the relative timing of multiple computations

Regular applications should try to avoid concurrency whenever possible...but the operating system has to live in a wold of concurrency
 - so how do we do it?

We need the operating system to enable multitasking

Two kinds: cooperative and preemptive

Cooperative multitasking
 - each computation splits up its work so it can be
   a good sharer
 - if any computation is selfish the entire system can
   come to a halt

Preemptive multitasking
 - timer limiting the "slice" of resources any computation
   gets
 - if one needs more time, it must wait its turn

Strategies for managing multitasking are known as scheduling algorithms or schedulers
 - many, many ways to build schedulers
 - simplest schemes such as first come first serve
   work pretty well, but with lots of annoying corner cases

UNIX provides a very nice way to manage concurrency between processes: pipes

What is a pipe?
 - implementation of producer/consumer using file descriptors
 
Think of two people doing dishes: one washing, one drying
 - this is producer consumer

For the producer, there's only so much space to store intermediate results (wet but clean dishes)
 - when the storage space is full, producer must pause
 - but when there is room, the producer should start work again

For the consumer, when there's no work to do they should take a break
 - but when there is work to do, the consumer should get back to work

That's the tricky part of concurrent systems: coordination

With pipes, coordination is taken care of by the kernel
 - it manages the buffers
 - it wakes up the producer (allows a write to finish)
 - it wakes up the consumer (allows a read to finish)

pipes are a basic building block on UNIX systems because
it allows multiple programs to be combined to do a task

Note that while multithreaded programs can be very efficient, they don't have to be, and often times a multi-process implementation with pipes or some other IPC can be remarkably efficient
 - with less complex code!

Why is parallel access to memory so bad?
Because of the memory hierarchy

We make copies of data to make things faster
 - but that means there are multiple copies!
 - and so different computations could be working with
   multiple copies of the same data, and so if the
   program acts like there is just one version...chaos


inodes

A directory just associates names with inodes
 - easy way to get nested directories,
   since directories are just a kind of inode


Filesystems consist of a few kinds of blocks:
 - data blocks
 - inode blocks <--- file contents metadata
    - directory inodes
 - superblocks

What's a superblock?
 - block that describes a filesystem
 - without a superblock you can't mount a filesystem

You technically only need one superblock, but multiple copies are stored just in case