The operating system and the hardware
With the FIFO algorithm, giving a program more memory can make it fault more. This is Belady’s anomaly, and it shows up with twelve references.
01A general-purpose operating system
A real-time operating system promises deadlines. A general-purpose one, such as Linux, Windows or macOS, promises other things: that many programs share the machine fairly, that none can harm the others or the system, and that each sees more memory than there is. Keeping those promises is not possible with software alone: it needs processor mechanisms. The general concepts of the operating system were covered in operating systems, in Computer Science.
| System promise | Hardware mechanism |
|---|---|
| Isolation between programs and from the kernel | Privilege modes: user code cannot execute privileged instructions or touch the hardware |
| Sharing of the processor | A timer that interrupts and returns control to the scheduler |
| Private memory for each process | The memory management unit (MMU) translates virtual addresses to physical ones |
| Efficient input and output | Peripheral interrupts and DMA |
02Modes, system calls and interrupts
The processor has at least two modes. In user mode, a privileged instruction or an access to a protected page causes an exception that passes control to the kernel. A program requests services from the kernel with a system call, a special instruction that changes mode and jumps to a fixed address. Peripherals signal with interrupts: the processor saves its state, runs the driver routine and returns. For large transfers, the DMA copies the data between the peripheral and memory and interrupts only when it finishes. Peripheral registers appear as memory addresses, which the kernel maps and protects.
03Virtual memory
Each process sees its own address space, divided into pages, typically 4 KB. The MMU translates each address with the process’s page table, which says in which frame of physical memory each page is, with what permissions, or whether it is not loaded. Since reading the table on every access would double the time, the MMU keeps recent translations in a cache, the TLB. If the page is not in memory, a page fault occurs: the kernel brings it from disk, which costs millions of times an access. Physical memories were covered in electronic memories.
04Which page to evict
When memory is full and a fault occurs, the system has to choose a page to evict. The optimal algorithm, by Belady, evicts the one that will be used furthest in the future: it cannot be implemented because it requires knowing the future, but it serves as a reference. FIFO evicts the oldest; LRU the one least recently used, and it takes advantage of the locality of programs, which tend to return to what they just used. Real systems approximate LRU with a reference bit set by the MMU, in the clock algorithm.
A sequence of page references and a number of physical memory frames. Each column is a reference; the cells show which page is in each frame, and the highlighted columns are page faults.
The Belady sequence shows a surprise: with FIFO, adding a frame can increase the faults. LRU and the optimal algorithm do not have that anomaly. With a loop only slightly larger than memory, LRU and FIFO fault on every reference.
05In the laboratory
On Linux, measure the page faults of a program that traverses a large matrix by rows and by columns, using the performance statistics command. Explain the difference.
Trace the system calls of a simple program with strace and identify those for reading, writing and memory mapping.
Write a minimal Linux driver for an LED on a board with an ARM processor, exposing a file in /dev to turn it on from user space.
06Common mistakes
- Believing that virtual memory is only for having more memory. Its main function is to isolate processes.
- Ignoring the cost of a page fault. One fault per hundred thousand accesses already doubles the effective time.
- Thinking that more memory always reduces faults. With FIFO that may not be so.
- Accessing the hardware from a user program. It is done with a driver in the kernel or by mapping memory with permissions.
07Self-assessment
How many entries does the page table of a 4 GB address space with 4 KB pages have, in a single level?
\( 2^{32}/2^{12} = 2^{20} \), one million.
With 100 ns memory and a 95% TLB hit rate, with no page faults, what is the effective time?
\( 0.95 \cdot 100 + 0.05 \cdot 200 = 105 \) ns, neglecting the TLB.
What is Belady’s anomaly?
That with FIFO, more memory frames can produce more page faults.
Which processor mechanism prevents a user program from disabling interrupts?
Privilege modes: that instruction executes only in kernel mode.
08Further reading
- Abraham Silberschatz, Peter B. Galvin and Greg Gagne. Operating System Concepts. 10th ed., Wiley, 2018. Virtual memory, page replacement and the relationship with the hardware.
- Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Operating Systems: Three Easy Pieces. Arpaci-Dusseau Books, 2018. A clear, freely available book, with chapters on the TLB and replacement.
- Jonathan Corbet, Alessandro Rubini and Greg Kroah-Hartman. Linux Device Drivers. 3rd ed., O'Reilly, 2005. How Linux kernel drivers are written.