Building Operating System Components in C
Five systems written from scratch in C: a Unix shell, a scheduler running on two simulated cores, a virtual memory manager with a TLB and demand paging, a FAT32 reader working on raw disk bytes, and a Turing machine interpreter.
What this is
Coursework for IFT 2245, the operating systems course at Université de Montréal. Five assignments across one semester, each building the thing the course had just finished explaining. Not simulations of the idea in a high-level language: the shell forks, the scheduler runs threads on a shared queue, and the memory manager evicts pages to a backing store because it has fewer frames than pages.
The common thread is that every one of them fails loudly if the memory handling is wrong, which is most of what makes them worth having written.
How it was graded
Hidden test suites on every submission, run automatically. The scheduler went further: it was scored on measured performance against reference implementations, with memory errors subtracted from the total. That combination is unusual for coursework, because passing the tests was not enough on its own.
The five systems
Turing machine interpreter
Parses a machine description into transition records, then simulates the tape.
- The standard library helpers were off limits, so string length, memory copying and line reading were written by hand
- First project of the course, and where the habit of pairing every allocation with its free started
Unix shell
Tokenizer, parser and executor, written from scratch.
- Pipelines of any length, plus
;,&&and||with short-circuit evaluation - Exit status propagated like a real shell, including the convention for a child killed by a signal
- Hardest part: the parent has to close each pipe's write end, or the reader never sees end of file and the pipeline hangs
Scheduler on two cores
A ready queue shared by two worker threads, scored on speed rather than just correctness.
- Guarded by a mutex and a condition variable, with waiting in a loop so a spurious wake-up cannot pop an empty queue
- Shutdown travels through the queue as a sentinel, not a flag every thread polls
- Dequeued nodes are freed after the unlock, keeping the critical section short
- Judged against First Come First Served, Shortest Job First and Round Robin, plus references we never saw
- Tuning: swept the time quantum across eight values on the fifty-process benchmark. Too small and context switches eat the gain, too large and it degrades to first come first served
Virtual memory manager
Paging over a 16-bit address space: 256 pages of 256 bytes, against only 32 physical frames.
- Addresses split with a mask and a shift
- Resolved through the TLB, then the page table, then a fault that loads from a backing store file
- A reverse frame-to-page map lets an eviction invalidate the right page table entry, and only dirty pages get written back
- Reports its own TLB hit rate and page fault count, which is what makes the cost of a miss concrete
FAT32 reader
Reads a real filesystem image as raw bytes.
- Fields assembled byte by byte rather than casting a struct over the buffer, so host byte order does not matter
- Sector size and cluster geometry read from the boot block instead of assumed
- Walks the cluster chain to resolve a path, normalising short names and skipping deleted and long-filename entries
What these exercises actually teach
A cache miss stops being abstract
When your own code prints the TLB hit rate every run, you watch it move as you change the replacement policy.
Lock scope is a decision, not a style
Whether a free happens inside or outside the critical section is how long every other thread waits.
Defaults deserve a benchmark
A time quantum looks like a constant somebody already chose correctly. It is a parameter with a measurable objective attached.
Course coverage
| Area | Topics |
|---|---|
| Processes | Process control blocks, state transitions, context switching, fork and exec, inter-process communication, shared memory, pipes |
| Threads | Threads versus processes, user and kernel threads and the mappings between them, pthreads, thread pools, thread-local storage, Amdahl's law |
| Synchronisation | Race conditions, critical sections, mutexes, semaphores, condition variables, classic synchronisation problems |
| Scheduling | First come first served, shortest job first, shortest remaining time, round robin, priority and multilevel feedback queues, burst estimation, real-time scheduling, processor affinity and load balancing, Little's law |
| Deadlocks | The four necessary conditions, resource allocation graphs, prevention versus avoidance, the banker's algorithm, detection and recovery |
| Memory | Base and limit registers, address binding, paging and segmentation, page table sizing, the memory management unit |
| Virtual memory | Demand paging, page fault handling and cost, replacement policies, working sets, thrashing |
| Storage | File system interfaces and implementation, allocation methods, free space management, disk scheduling, containerisation |
| C itself | Memory layout across text, data, heap and stack, struct alignment and padding, dynamic allocation and the discipline around it, debugging with gdb and Valgrind |