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
  1. Every block is used for exactly one purpose
  2. All referenced blocks are initialized (for inodes, all referenced inodes are initialized)
  3. All referenced blocks are marked used (for inodes, all inodes have reference count >= number of references)
  4. 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)