====== Final Topics ====== * The systems perspective * **System**: A set of interconnected components that has a specified behavior observed at the interface with its environment * System characteristics * Emergent properties * Propagation of effects * Incommensurate scaling * Trade-offs * Coping with complexity: **Modularity** * Modularity goals * Performance * Robustness/fault-tolerance * Neutrality * Simplicity * An OS is software that provides programs with access to an abstract machine * Protection and sharing * Interface design * readc: from one line at a time, through one character at a time, to one buffer at a time * Layering to improve interface usability while keeping performance * Optimization strategies: Caching and prefetching * Virtual computer * Three fundamental abstractions: link, interpreter, memory * Von Neumann computer characteristics * Virtual I/O, virtual processor, virtual memory * Hard modularity through client/service interaction * The process abstraction * Memory layout * Isolation properties * System calls & implementation * Protection levels & protected control transfer * File descriptors * Unix process and file system calls * Bounded buffers and pipes * Process hierarchy & zombie processes * Context switches * Threads * Process vs. thread * pthread_create, pthread_join, pthread_exit * Threads, stacks, and shared state (How does pthread_create differ from fork and why?) * Interrupts & signals * Unix signal system calls * Race conditions * Synchronization * One-writer principle * Indivisibility & atomicity * Isolation atomicity: Two sequences of steps are **isolated** if their effect from the point of view of the invokers (observers) is the same as if the sequences occurred either //completely before// or //completely after// one another. * What is an observer? * Critical section * Minimal critical section * Bounded buffer * Enforcing critical sections * Read/write coherence * Atomic instructions * Mutual exclusion locks * Lock contention * Coarse-grained vs. fine-grained locking * Deadlock * Waits-for graph * Lock ordering * Read/write locks * Blocking wait * Sleep-wakeup race * Semaphores * Condition variables * Utilization * Virtual memory * Domains and isolation * Processor support * And protection levels * Fragmentation, external and internal * Paged virtual memory * Processor implementation (e.g., 2-level page tables) * Isolation * Swapping * Thrashing * Belady's anomaly * Performance * Demand paging * Dirty-only swapping * Locality of reference * Copy-on-write * Memory mapping * I/O and performance * Performance metrics * Latency * Throughput * Utilization * I/O strategies * Polling with programmed I/O * Interrupts * Direct memory access (DMA) * Polling with DMA * Optimization strategies * Batching * Dallying * Speculation * Data structure design * File systems * On-disk file system data structures * Superblock * File allocation table (FAT) * Direct & indirect block pointers * Free block bitmap * Directory entries * Inodes * Kernel implementation file system data structures * Virtual file system layer (VFS) * Mounting * File system correctness invariants - Every block is used for exactly one purpose - All referenced blocks are initialized (for inodes, all referenced inodes are initialized) - All referenced blocks are marked used (for inodes, all inodes have reference count >= number of references) - All unreferenced blocks are marked free (for inodes, all inodes have reference count == number of references) * Ordering strategies for robustness * Improving file system performance * Speculation: readahead * Dallying and batching * Disk scheduling * FCFS * SSTF (Starvation?) * Elevator * C-SCAN/circular elevator * Improving file system robustness * Journaling: commit records * RAID * MTTF: Mean Time To Failure * Networking/Distributed Systems * Differences from non-networked OS devices * Network effect * Receive livelock * Interrupts * Prioritization * Client/service architecture * Remote procedure call (RPC) * Synchronous * Asynchronous * Marshalling/unmarshalling * Distributed file systems/NFS * Performance * Consistency models: write-to-read, close-to-open * Security * Authenticity * Integrity * Authorization * Complete mediation * Principal * Trusted computing base (TCB) * Authentication (= authenticity + integrity) * Passwords * Cryptographic hash * Encryption: public key and private key * Signatures * Nonces * Authorization * Name-based * Tickets/capabilities * Access control lists (ACLs)