The final exam for this course will take place on Thursday, December 15, at 8:30 AM, in our regular classroom. The exam will be about six pages long, and should take about one and a half hours to complete for most people.
The exam will concentrate heavily on material that we have covered since the first test. However, there will probably be some general questions about major ideas from the first part of the course.
There will be no actual coding on the test, although you might be asked to give pseudocode outlines of some operating system algorithms. There might be some quantitative problems (such as using a page table to convert a virtual address to a physical address or asking how many blocks will be used to store a a file of a given length). However, the majority of the test will be essay-type questions including definitions, short-answer questions, and longer essays. You can expect at least one very general essay question at the end.
Here are some of the things that we have covered since Test 1...
deadlock dining philosophers problem conditions for deadlock: 1. bounded resources 2. no preemption 3. wait while holding 4. cycle of waiting ordering resources to avoid deadlock two-phase locking: acquire locks as needed, release them all at the end breaking deadlock by killing a process or rolling back a transaction process scheduling compute-bound tasks versus I/O-bound tasks scheduling algorithms FIFO (First-in, first-out), low overhead; can be bad for average response time SJF (Shortest Job First), best average responce time; possibility of starvation Round-robin, optimal fairness for compute-bound tasks, bad for I/O-bound tasks MLFQS, attempts fairness for all processes MLFQS heuristic: increase priority of threads that don't use an entire time slice address translation: convert virtual address to physical address a process has its own virtual address space, inaccessible to other processes segmented memory: segment table contains segment number with base, bound, access info a virtual address consists of a segment number and an offset a program can use a code segment, global data segment, stack segment, etc. paged memory: virtual and physical address spaces divided into equal-sized tables a page table maps virtual pages to physical pages (plus access info) a virtual address consists of a page number and an offset multilevel page tables, can deal with very large virtual address spaces combining segmentation with paging TLB (translation lookaside buffer), a cache for page table lookups TLB records contain virtual page number, physical page number, access info TLB "shootdowns" for maintaining TLB consistency across multiple processors multi-level caching: virtually-addressed (level 1) cache; TLBs; physically addressed per-processor (level 2) cache; level 3 cache caching in general cache hits and cache misses temporal locality spatial locality (and why memory caches load blocks of memory) write-through cache vs. write-back cache working-set model, hit rate levels off as cache size increases Ziph model ("long" or "heavy" tail), many hits on rarely-accessed items cache replacement policies: Random, FIFO, LRU (least recently used), LFU (least frequently used) files and file systems directories (map file names to file numbers) directory structures (lists, trees, hash tables) file metadata (such as owner, permissions, creation time) hard links (multiple directory entires to the same actual file) block devices memory-mapped I/O (map memory addresses to registers on I/O devices) DMA (Direct Memory Access) magnetic disks (physical structure: surfaces, tracks and sectors) accessing a sector: seek time, settle time, rotation delay why sequential disk accesses are much faster than random accesses disk scheduling alorithms: FIFO, SSTF (shortest seek time first), elevator SSDs, "flash" memory (physical structure: erase blocks and pages) must erase before writing; erasing is done in large blocks problem of "wear out" from too many writes to the same page mapping of logical page numbers to physical pages moving data around to mitigate wear-out and erasure time file system structure FAT: linked list of blocks FFS, ext2, ext3: inode tree, fixed-size data blocks NTFS: list of variable-sized "extents" ZFS: a COW (Copy-on-Write) file system inodes: fixed array of available inodes; an inode contains metadata, direct pointers, and an indirect, a doubly-indirect and a triply-indirect pointer COW file systems: blocks never modified in place how COW file systems support file versions, snapshots, cloning ZFS structure: uberblock array (256 slots for the uberblock) expandable dnode array, stored in a file a file can use from zero to six levels of indirect pointers batched updates for efficiency redo log containing update records, commit records (and maybe rollback records) crash recovery by replaying a redo log (and why update operations are idempotent) transactions in a file system; atomic operation is writing one sector how COW file systems like ZFS are built to support transactions
Here are some major topics from the first part of the course...
functions of operating systems the kernel user mode versus kernel mode interrupts the timer interrupt and preemptive multitasking threads and processes and how they differ synchronization issues (race conditions, locks, and condition variables)