CSC 539: Operating Systems Structure and Design
Spring 2006
Test 2 Review
TEST 1 MATERIAL
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 management
files
attributes: name, type, protection, size, location, ...
operations: create, read, write, delets, reposition, ...
structures:sequential vs. direct vs. indexed access
directories
structure: partitions, device directory, file sharing
implementation: contiguous vs. linked vs. indexed allocation