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