这门课使用了斯坦福的 Pintos 项目，我觉得是一个很不错且有趣的项目。后半学期老师逐渐脱离教材，开始自由发挥……

Virtual Memory

1. Page and frame replacement algorithms:
   1. FIFO: Can suffer from Belady’s Anomaly: More available frames can cause more page faults.
   2. Optimal Algorithm: Replace page that will not be used for longest period of time: Not possible because can’t read the future.
   3. LRU: Generally good & frequently used.
   4. Second-Chance Algorithm: Clock replacement. If a page has reference bit set to be 0, replace it; Otherwise, set the reference bit to 0, and check the next page.
   5. Enhanced Second-Chance Algorithm: Consider (reference, modify).
   6. Counting Algorithms: Keep a counter of number of references for each page:
      1. LFU: Replace page with the smallest count.
      2. MFU: Based on the argument that page with the smallest count was probably just brought in.
2. Working Set: The set of resources, e.g. objects in memory, that are needed to work on the current task.
3. Thrashing: Page fault to get page, replace existing frame, but quickly need the replaced frame back: ∑ size of locality > total memory size.
   • △ = working-set window = a fixed number of page references;
   • WSS_i (working set of process P_i) = total number of pages referenced in the most recent △;
   • D = ∑ WSS _i = total demand frames: Approximation of locality;
   • D > m: Thrashing.
4. Stack growing down, heap growing up.

Mass-Storage Systems

1. Disk scheduling algorithms:
   1. FCFS.
   2. SCAN: Also called elevator algorithm.
   3. C-SCAN: When it reaches the other end, it immediately returns to the beginning of the disk, without servicing any requests on the return trip.
   4. SSTF: Shortest seek time first.

2. Latencies:

   L1, L2, L3 cache	DRAM	SSD	Hard disk drive	Networking
   1ns, 3ns, 30ns	100ns	100μs	10ms	100ms

3. Write amplification: A single write to a Flash-based SSD requires multiple writes and data movement:
   • Wear leveling: There is a limited number of times to which a unit of physical FLASH memory can be written. So, to maximize the capacity of an SSD drive by avoiding wearing parts out, when a block is written, if it has been written a lot recently, it is relocated.
   • Garbage collection: Data is written in smaller units than it is erased. So, as blocks are erased they are wasted until the larger unit that includes them can be erased. To free up space, blocks may need to be moved.

File Systems

1. Caches:
   1. Name cache (directory cache): Every time we look an inode # up, we cache it.
   2. Block cache: a.k.a buffer cache or request cache, cache a block.
      • Unified cache: Page and block have the same size. This is a preferred solution for general-purpose OSes because flexibility is too important for a mixed workload with needs that vary over time.
      • Unified caches provide flexibility but it’s possible that one could starve the other: Data starving the processing that drives it.
   3. Inode cache: Inodes for open files are always kept in memory (up to any resource limit, then LRUed out memory):
      • Because inode is needed every time an access to the file data is made.
2. Optimizations of organization of directory files:
   1. A list of <name, inode#> tuples: For a few entries.
   2. A tree (B-tree) of the same:
      • Dense on disk: Many comparisons per page;
      • Self-balancing;
      • Easy way to do in-order listing.
3. fsck: File system check: Verifies and makes consistent the FS metadata.
4. Ext4 Journaling: For consistency checking at start-up. Without it all metadata needs to be checked. With it, only open transactions need to be checked.
   1. Journaled: Both metadata & file data.
   2. Ordered: Only metadata, but data are written to disk before the metadata is logged (or flushed into the FS).
   3. Writeback: Only metadata and no control on the order.
5. Per process file descriptor table: It exists to allow processes to share the same open file table entry. This might, for example, be the case with fork()s. Consider, for example the case of a pipe. The parent creates the two file descriptors, one for read and one for write, and each child gets its own copy. This enables one child to write into the pipe and another child to read from it.
6. System-wide open file table: It keeps track of file sessions. For example, what mode(s), e.g. read, write, read-write, etc, are permitted for the session, and the current offset into the file.

Virtual Machines & Containers

1. Why VM is important for cloud: Sharing of resources, fungibility, isolation, elasticity, robustness, metering.
2. Full-virtualization & paravirtualization:
   • Full-virtualization: Virtual machines runs entirely as a program in guest OS without any special support from guest OS.
   • Paravirtualization: Host OS modified to provide an API to enable VM to request the host to perform operations on behalf of the guest.
3. Hardware support: Eliminate problems for traps, hardware access like I/O, supervisor vs user mode.
4. Guest OS maintains a page table (shadow page table). When accesses fault, real OS looks in shadow page table, translates, fixes the page table, and operation resumes. Effectively, these are read-only page tables for the guest as they can only be updated by the host.
5. Containers: Maintain one host OS and share it for efficiency.
6. Mount points are the points where one file system grafted into another file system.
7. Hard link: It is the name -> inode mapping in a directory file. Soft link: The soft linked file has a separate inode value that points to the original file.