Figures

Chapter 1: Introduction

• Figure 1.1: The operation of a web server
• Figure 1.2: A general-purpose operating system.
• Figure 1.3: A general-purpose operating system with more detail.
• Figure 1.4: A guest operating system inside a virtual machine.
• Figure 1.5: Cloud computing software.
• Figure 1.6: A web browser.
• Figure 1.7: A database.
• Figure 1.8: Computer performance over time.
• Figure 1.9: Operating system genealogy.

Chapter 2: The Kernel Abstraction

• Figure 2.1: User-level and kernel-level operation.
• Figure 2.2: Edit/compile/run a user program in a process.
• Figure 2.3: CPU operation.
• Figure 2.4: CPU operation with kernel/user mode bit.
• Figure 2.5: Base and bound memory protection.
• Figure 2.6: Virtual address mapping.
• Figure 2.7: Code illustrating physical versus virtual addresses.
• Figure 2.8: Interrupt vector table.
• Figure 2.9: Kernel and user stacks.
• Figure 2.10: x86 CPU state before an interrupt.
• Figure 2.11: x86 CPU state at the start of the interrupt handler.
• Figure 2.12: x86 CPU state after the interrupt handler has started running.
• Figure 2.13: System call stubs.
• Figure 2.14: User-level system call stub.
• Figure 2.15: Kernel-level system call stub.
• Figure 2.16: CPU state before a UNIX signal handler starts running.
• Figure 2.17: CPU state after a UNIX signal handler starts running.
• Figure 2.18: Steps in booting an operating system.
• Figure 2.19: Emulation of a virtual machine.

Chapter 3: The Programming Interface

• Figure 3.1: Operating system kernel and user-level library.
• Figure 3.2: System call API as thin waist.
• Figure 3.3: Windows CreateProcess excerpt.
• Figure 3.4: Operation of UNIX fork/exec.
• Figure 3.5: UNIX code to fork a process.
• Figure 3.6: A pipe for interprocess communication.
• Figure 3.8: Code for a UNIX shell.
• Figure 3.9: One way interprocess communication.
• Figure 3.10: Client-server interprocess communication.
• Figure 3.11: Client-server code.
• Figure 3.12: Server-side code.
• Figure 3.13: A monolithic operating system.
• Figure 3.14: Device drivers in a guest operating system.

Chapter 4: Concurrency and Threads

• Figure 4.1: Thread abstraction.
• Figure 4.2: Multi-threaded earth visualization.
• Figure 4.3: Several possible code paths for one thread.
• Figure 4.4: Several possible interleavings of three threads.
• Figure 4.6(left): Code to fork 10 threads to print hello.
• Figure 4.6(right): One possible output of code to fork hello.
• Figure 4.7: Code to fork threads to zero memory.
• Figure 4.8: Per-thread versus shared state.
• Figure 4.9: Thread life cycle.
• Figure 4.11: Multi-threaded kernel with single-threaded processes.
• Figure 4.12: Multi-threaded kernel with multi-threaded processes.
• Figure 4.13: Code to implement thread create.
• Figure 4.14: Code to implement thread switch and thread yield.
• Figure 4.16: Asynchronous file read on Linux.
• Figure 4.17: Server use of UNIX select.
• Figure 4.18: Event-driven versus threaded implementations of a server.
• Figure 4.19: Matrix multiply.

Chapter 5: Synchronizing Access to Shared Objects

• Figure 5.1: Threads versus shared objects.
• Figure 5.2: Layers of synchronization primitives.
• Figure 5.3(a): Thread-safe bounded queue header.
• Figure 5.3(b): Thread-safe bounded queue code.
• Figure 5.4: Three instances of a shared queue.
• Figure 5.5: Code to create and test the thread-safe bounded queue.
• Figure 5.6: Polling version of thread-safe queue.
• Figure 5.7: Condition variable design pattern.
• Figure 5.8(a): Thread-safe blocking bounded queue header.
• Figure 5.8(b): Thread-safe blocking bounded queue code.
• Figure 5.9: Reader-writers lock header.
• Figure 5.10: Reader-writers lock code.
• Figure 5.11: MapReduce using synchronization barriers.
• Figure 5.12: One-use barrier.
• Figure 5.13: Re-usable barrier.
• Figure 5.14: FIFO bounded buffer.
• Figure 5.15: Uniprocessor queueing lock.
• Figure 5.16: Multiprocessor spinlock.
• Figure 5.17(a): Multiprocessor queueing lock.
• Figure 5.17(b): Multiprocessor scheduler.
• Figure 5.18: Condition variable implementation.

Chapter 6: Advanced Synchronization

• Figure 6.2: Ownership design pattern.
• Figure 6.3: Staged design pattern.
• Figure 6.4: Overhead of lock implementations.
• Figure 6.5: MCS queueing lock code.
• Figure 6.6: MCS in operation.
• Figure 6.7: RCU timeline.
• Figure 6.9: RCU in operation.
• Figure 6.10: Header file for linked list using an RCU lock.
• Figure 6.11: Implementation of linked list using an RCU lock.
• Figure 6.12: Code implementing an RCU lock.
• Figure 6.13: Acquire all/release all design pattern.
• Figure 6.14: Deadlock at an intersection.
• Figure 6.15: Five dining philosophers.
• Figure 6.16: Deadlocked dining.
• Figure 6.17: Non-deadlocked dining.
• Figure 6.18: Safe, unsafe, and deadlock states.
• Figure 6.19: Banker's Algorithm state.
• Figure 6.20: Banker's Algorithm code.
• Figure 6.21: Banker's Algorithm code.
• Figure 6.22: Deadlock detection.
• Figure 6.23: Coffman test for deadlock.

Chapter 7: Scheduling

• Figure 7.1: FIFO and SJF scheduling.
• Figure 7.2: Round Robin scheduling.
• Figure 7.3: FIFO, SJF, and Round Robin scheduling on equal length tasks.
• Figure 7.4: Round Robin with I/O and compute tasks.
• Figure 7.5: Multi-level feedback queue.
• Figure 7.6: Per-processor multi-level feedback queue.
• Figure 7.7: Oblivious scheduling.
• Figure 7.8: Bulk synchronous design pattern.
• Figure 7.9: Producer-consumer design pattern.
• Figure 7.10: Critical path.
• Figure 7.11: Gang scheduling.
• Figure 7.12: Speedup of different parallel programs.
• Figure 7.13: Space sharing.
• Figure 7.14: Value of response time for interactive tasks.
• Figure 7.15: Value of response time for real-time tasks.
• Figure 7.16: Queueing system.
• Figure 7.17: Best case performance for a queueing system.
• Figure 7.18: Worst case performance for a queueing system.
• Figure 7.19: Exponential distribution.
• Figure 7.20: Markov model of queueing system.
• Figure 7.21: Response time versus utilization of a queueing system.
• Figure 7.23: Web service architecture.

Chapter 8: Address Translation

• Figure 8.2: Base and bounds address translation.
• Figure 8.3: Segment table address translation.
• Figure 8.4: Segment tables with shared segments.
• Figure 8.5: Logical view of page table translation.
• Figure 8.6: Page table address translation.
• Figure 8.7: Segmented page table address translation.
• Figure 8.8: Multi-level page translation.
• Figure 8.9: Hash table page translation.
• Figure 8.10: Translation lookaside buffer.
• Figure 8.11: TLB and page translation.
• Figure 8.12: TLB with superpages.
• Figure 8.13: TLB interaction with framebuffer.
• Figure 8.14: TLB with process ID's.
• Figure 8.15: TLB shootdown.
• Figure 8.16: Virtually addressed cache, TLB, and page translation.
• Figure 8.17: Virtually and physically addressed caches.
• Figure 8.18: Software-based fault isolation.
• Figure 8.19: Kernel packet filter.
• Figure 8.20: Javascript execution.
• Figure 8.21: Mesa operating system architecture.

Chapter 9: Caching and Virtual Memory

• Figure 9.1: Memory cache read.
• Figure 9.2: Memory cache write.
• Figure 9.4: Cache hit rate versus cache size.
• Figure 9.5: Phase change cache behavior.
• Figure 9.6: Cache aware memory sort.
• Figure 9.7: Zipf distribution.
• Figure 9.8: Zipf cache hit rate.
• Figure 9.9: Fully associative lookup.
• Figure 9.10: Direct mapped cache lookup.
• Figure 9.11: Set associative cache lookup.
• Figure 9.12: Page coloring.
• Figure 9.17: Memory pages before a page fault.
• Figure 9.18: Memory pages after a page fault.
• Figure 9.19: TLB and page table when a page is clean.
• Figure 9.20: TLB and page table when a page is dirty.
• Figure 9.21: Clock algorithm.
• Figure 9.22: Code for program to touch all pages.

Chapter 10: Applications of Memory Management

• Figure 10.1: Kernel-user transitions to serve a web page.
• Figure 10.2: Zero copy I/O.
• Figure 10.3: Virtual machine page tables.
• Figure 10.4: Shadow page table.
• Figure 10.5: Virtual machine page de-duplication.
• Figure 10.6: Virtual machine checkpointing.
• Figure 10.7: Incremental checkpointing.
• Figure 10.8: User-level page handling.

Chapter 11: File Systems: Introduction and Overview

• Figure 11.2: File naming with directories.
• Figure 11.3: File naming with hard links.
• Figure 11.4: USB volume.
• Figure 11.5: File mounting.
• Figure 11.7: I/O system layers.
• Figure 11.8: Physical arrangement of I/O devices.
• Figure 11.9: Memory-mapped I/O devices.

Chapter 12: Storage Systems

• Figure 12.1: Picture of a disk drive.
• Figure 12.2: Schematic of a disk drive.
• Figure 12.4: Disk scheduling algorithms.
• Figure 12.5: Flash memory transistor.
• Figure 12.7: Flash memory transistor.

Chapter 13: Files and Directories

• Figure 13.1: File name and offset translation.
• Figure 13.2: File directory.
• Figure 13.3: File hierarchy.
• Figure 13.4: List implementation of a directory.
• Figure 13.5(a): Tree implementation of a directory.
• Figure 13.5(b): Physical layout of tree implementation.
• Figure 13.6: Directory tree with hard links.
• Figure 13.7: Directory with hard links.
• Figure 13.9: FAT file layout.
• Figure 13.10: FFS file layout.
• Figure 13.11: Small FFS file.
• Figure 13.12: Sparse FFS file.
• Figure 13.13: FFS block groups.
• Figure 13.14: Placement of file data within an FFS block group.
• Figure 13.15: NTFS basic file layout.
• Figure 13.16: NTFS small file layout.
• Figure 13.16: NTFS large file layout.
• Figure 13.18: NTFS giant file layout.
• Figure 13.19: Copy-on-write file layout.
• Figure 13.20: Location independence in FFS.
• Figure 13.21: Location independence in copy-on-write.
• Figure 13.22: Copy-on-write update.
• Figure 13.23: ZFS file layout.
• Figure 13.24: ZFS update.
• Figure 13.25: File directory lookup.

Chapter 14: Reliable Storage

• Figure 14.2: Code for using a transactional file system.
• Figure 14.3: Redo logging example.
• Figure 14.4: Redo log and volatile memory.
• Figure 14.5(top): Copy-on-write data update.
• Figure 14.5(middle): Copy-on-write metadata update.
• Figure 14.5(bottom): Copy-on-write commit.
• Figure 14.6: Copy-on-write batch commit.
• Figure 14.7: Bathtub model of device lifetime.
• Figure 14.8: Mirroring, RAID level 1.
• Figure 14.9: RAID level 5.
• Figure 14.10: Data integrity segment.
• Figure 14.11(top): ZFS Merkle tree.
• Figure 14.11(bottom): ZFS Merkle tree update.
• Figure 14.13: Double parity RAID design.