CSC 539: Operating Systems Structure and Design
Fall 2002

Final Exam Review

OS overview history single-user --> batch --> multiprogramming --> time-sharing --> desktop user interfaces: command line vs. GUI new architectures: multiprocessor, distributed, real-time, ... computer system structures I/O: interrupts, I/O structures, device-status table memory: DMA, memory hierarchy (primary vs. secondary), caching hardware protection: modes, privileged instructions, timer interrupts, ... networking: LAN (e.g., Ethernet) vs. WAN (e.g., Internet) operating system structures components: process mgmt, memory mgmt, file mgmt, I/O mgmt, ... services: program execution, I/O, file system, communications, ... organization: simple vs. layered vs. microkernel, virtual machines Processes & threads processes process states, process control block (PCB), scheduling queues schedulers: short-term (CPU scheduler), long-term (job scheduler) I/O bound vs. CPU-bound jobs, medium-term scheduler CPU context switching operations: creation (e.g., fork), termination (e.g., exit), others (e.g., execvp, wait), coordination/communication threads lightweight process advantages: responsiveness, resource sharing, economy, concurrency CPU scheduling CPU & I/O bursts, burst distribution preemptive vs. nonpreemptive scheduling scheduling criteria CPU utilization, turnaround, waiting, response time, fairness, ... scheduling algorithms FCFS, SJF, priorities (starvation), RR (quantum size), multilevel queue, multilevel feedback queue, real-time scheduling scheduling algorithm evaluation deterministic models, simulation, queuing models, implementation CPU synchronization producer/consumer problems, race conditions critical section problem solution characteristics: mutual exclusion, progress, bounded waiting Bakery algorithm, synchronization hardware semaphores, busy waiting vs. waitless high-level constructs: critical regions, monitors deadlock nec. conditions: mutual exclusion, hold&wait, no preemption, circular wait system resource allocation graph prevention: difficult/costly in practice, circular wait best candidate avoidance: safe state, safe sequence resource allocation graph algorithm (if one of each resource) Banker's algorithm (if multiple resource instances) detection: wait-for graph (if one of each resource) deadlock detection algorithm (if multiple resource instances) recovery: either preempt resources or abort processes Memory management logical vs. physical addresses contiguous memory allocation, dynamic allocation (first/best/worst-fit) external fragmentation, internal fragmentation paging page table, translation look-aside buffer (TLB), valid/invalid bit multilevel paging, shared pages paging vs. segmentation, hybrid approaches virtual memory demand paging, page fault, effective access time page replacement: FIFO (Belady's anomaly), OPT, LRU LRU approximation: reference bits, second chance thrashing: working-set model, page fault frequency File & I/O management file systems file attributes, file operations, sequential vs. direct access directory structure: partitions, device directory directory implementation: contiguous vs. linked vs. indexed allocation I/O systems device controllers, handshaking, interrupts, direct memory access (DMA) disk scheduling: FCFS, SSTF, C-LOOK disk reliability: RAID, mirroring, striping