Class

Bugs Atomicity Violation (forgot to use locks) Ordering Violations (forgot to use cond. variable) Deadlock What is it? How it arises? How to avoid? Conditions Mutual exclusion Hold + Wait Acquire one lock, then try to acquire another one No preemption (of the lock) Once held, held until release is called Circular wait Use avoidance to prevent deadlock Contrast: detect + recover Best Solution: Lock Ordering Avoiding Circular wait Avoiding Hold + Wait Hold a mega lock Preemption use try locks Complex Inefficient Livelock Lock-free Data Struct list_insert(int value) { node_t *n = malloc(sizeof(node_t)); assert(n !...

Preview FS API open, read, write, close, link, unlink, mkdir, rmdir, etc. Implementation Simple Implementation On-disk data structures Access methods --------------------------------------------- | | D A T A | -------------------------------------------- close up first part: -------------------------------------------------------------- |Super block|Inode BM|Data BM| I N O D E S | -------------------------------------------------------------- math: true BM = bitmap Superblock = meta-info about FS Inode: (~256 bytes) ------------- | type | | size | | #of blocks| (size smaller than block size, sparse file) | owner | | permission| | addresses | | of data blocks (direct pointer) ------------- Questions: Access?...

Brief Memory Volatile, not persistent Poweroff => info lost Persistence ----- -------- | CPU | <----------> | Memory | ----- | -------- ------ math: true net <---- | I/O |------> Hard drive, PCI | Chip | SATA SSD ------ | | USB mice, keyboards Today: Device interaction (I/O) How? Efficient? Specific Device: Hard Drive Future: Device up => OS: File Systems Generic Device: Hardware interface (generalization) Command Register (What to do) Data Register Status register How does OS read and write these?...

Today Flash-based SSD Solid State => Circuitry persistent storage basic characteristics from “row” flash => storage device Basics NAND Flash “trap” charge, encode bit(s) Bank/Chip operations read (page) (~2KB, 4KB) --------------------------------- | |page| | | --------------------------------- | block | erase (block) (~256KB) program (page) to write erase entire block then, you can program each page within block exactly once if you want to overwrite, must erase/prog again Performance read 10s of microseconds much faster then hard drive erase a few milliseconds program 100s of microseconds Reliability “wear out” once you erase/program block “too many” times it stops working “to many”: 10k ~ 100k times SSD: Block-level Device API: read, write block Map to read, erase/program Parallel storage device |------------------------ | ------------ ------ | | |Controller| |DRAM| | | ------------ ------ | | --- --- | | |F| |F| ....

Today File Systems implementation Static on-disk structures ---------------------------------- | (1) | inode | Data | ---------------------------------- (1) superblock, inode bitmap, data bitmap Performance Problem Example: new file creation (1 block) creat("/foo") Reads Writes x x inode bitmap x x data bitmap x x inode (foo) x x inode (root dir) x x data (root dir) x data (foo) lots of small, random I/O (Bad) Solutions caching (reads) write buffering (writes) doesn’t remove write in general Dynamic: Log-structured File System Disk --------------------------------------- |write|write|write|....