CSC 539: Operating Systems Structure and Design
Spring 2005

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