CSC 539: Operating Systems Structure and Design
Spring 2006

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 Process management 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 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 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, file sharing directory implementation: contiguous vs. linked vs. indexed allocation I/O systems device controllers, handshaking, interrupts, direct memory access (DMA) disk scheduling: FCFS, SSTF, SCAN, C-SCAN, C-LOOK disk reliability: RAID, mirroring, striping Protection & security protection: domain structure, access matrix (access vs. capability lists) security: authorization, encryption program threats (Trojan horse, trap door, stack/buffer overflow) system threats (worm, virus, denial-of-service) threat monitoring, firewalls Distributed systems networked vs. distributed operating systems, LAN vs. WAN Distributed File Systems (DFS's) naming, remote file access, caching, stateless vs. stateful example: AFS distributed mutual exclusion: centralized vs. fully distributed