Review what is an operating system? what illusions does the operating system provide to applications? how do devices tell the processor there's something to do? how does the processor get information from devices? what's a pipe? a named pipe? a socket? what's the difference between a system call and a library call? what's a microkernel? what are the challenges with a microkernel? what are the advantages of a microkernel? what's an interrupt? how does it differ from a trap? how do interrupts help with preemtive multitasking? what's a real time system? what characterizes the apps in a real time system? what characterizes the scheduling in a real time system? what do embedded systems lack? what's a file? a file descriptor? a file system? what is the interface of a file system? what's a shell? how does a shell start (not on geekos)? what's a process? contrast thread. what does a process have? what are its states? what is stored in the PCB? what's a pid? what's a zombie? how much state is needed by a zombie? where are page tables stored? how does a context switch happen? why not switch frequently? what's thrashing? what's a quantum? what are short, medium, and long term scheduling? what distinguishes dispatcher from scheduler? which processes live forever? what does "init" do? what is a daemon? how does a process become a daemon? how is system() implemented? pipe()? how does a shell implement the | operator? why separate processes by pipes not threads? why use shared memory? what is sigpipe? what's the diference between UNIX domain sockets and Internet protocol sockets? why use one over the other? (unix domain is not udp.) know the socket system calls. accept, bind, read, write, close, shutdown, connect, listen. user level threads. what that means. what process is required to create a user level thread, and what (arch-dependent) calls are involved in creating a new user level thread. distinguish from kernel thread. scheduler activations. what and why. thread pool. what and why cpu scheduler goals. types: FCFS, SJF (SRTF), MLFQ. adjusting quantum. detecting i/o bound. what it means to block on i/o or give up the quantum. is fairness good? reentrant functions. don't hold state across invocations. what does signal() do? contrast kill(). alarm(). multiprocessor scheduling: affinity, load balancing. SMT. memory stalls. synchronization, race conditions, locks. reader/writer locks. starvation for whom? the critical section problem: four goals/criteria. Peterson's solution. Applicability. Insight. Bakery algorithm. metaphor. insight. key mechanism. test-and-set/TSL. how to implement lock and unlock. swap/xchg/swp. how to implement lock and unlock. why these primitives aren't enough. semaphores. P/V proberen/verhogen wait/signal how implemented (you know this well.) implement producer/consumer bounded buffer. what does the producer wait for? what does the consumer wait for? implement reader/writer locks. who starves? condition variables and monitors condition variable operations motivation for monitors. implementation of semaphores with condition variables and monitors. implementation of monitors and condition variables with semaphores. producer/consumer with monitors. signal-and-(continue vs. wait) dining philosophers solution with condition variables. transactions: ACID. name each, what they mean, how they are ensured. two-phase locking. what it's for, how it works. when locks can be released. undo and redo logging. deadlock: four conditions. prevention, avoidance, and detection. mechansims for each. incl. banker's alg. how to decide which processes to kill == end of pre-midterm content == memory management: stall, protection, address space. overlays (old school) contiguous allocation, limitations. fragmentation: internal, external. segmentation vs. paging. process address space layout. page table. multilevel page table. page directories. page table bits. TLB. what it does. why page size matters. inverted page tables, hashed page tables. PAE. position-independent code. relative addressing, indirect addressing. why have PIC? what's a page fault? what's the task of te pager? page replacement strategies: FIFO, OPT, LRU, Second chance, Clock, MFU, LFU, working set contrast insight, goals, weaknesses. page buffering, how to decide when to write dirty pages out. page allocation, minimum pages required, global allocation, fairness, proportional, priority. memory mapped files. kernel memory allocation: buddies and slabs. three states of a slab. prepaging: what it is, how it helps. contrast medium-term scheduling. OOM. file systems: interfaces. disk geometry, performance properties. file metadata. berkeley study conventional wisdom about files. contiguous allocation, linked allocation, FAT, indexed allocation, multilevel indexed, early unix file system (very gfs2), fast file system and what made it faster. ext2. NTFS and extents. understand a File Allocation Table. Free blocks bitmaps. why they're good. preallocation. the buffer cache. contrast unified buffer cache, page cache. the log structured file system: motivating insight(s). implementation issues: cascading changes to update a block of data. the ifile and storage of atime. the cleaner. journaling file systems. insight. writeback, ordered, data. redo/undo distinction to log structured. i/o scheduling: FIFO, SSTF/SATF/SPTF, SCAN/Elevator/LOOK, C-SCAN, deadline, anticipatory. what each is good for. what can go wrong. does it help to have deeper queues? what makes more than one block show up on the queue? RAID: levels 0, 1, 5. cost. mirror, stripe, parity. NFS: RPC, XDR, statelessness. access control (uid reporting, exports file) operations. rfc 1094. Security: Thompson, Tenex, /etc/passwd salt. public/private keys, signatures, certificates. block chaining importance. authentication protocol. BAN logic ops: nonce verification, freshness, message meaning, jurisdiction, Two-phase commit. Byzantine generals. Lamport logical clocks.