CS537

Brief RAID S/W (file system) H/W (hardware) disks, RAIDs, SSD File System API Internals RAID Why? Performance Capacity Reliability (Durability) Failure model entire drive: Working or (Completely) failed Easily detected (by RAID controller) RAID “Levels” Level 0: no redundancy （striping / JBOD) Disk 0 Disk 1 Disk 2 Block 0 1 2 3 4 5 No redundancy: can’t handle failure Level 1: Mirroring For each block, have copies on some other drive Disk 0 Disk 1 Disk 2 Disk 3 0 0 1 1 2 2 3 3 More advanced failure model: Block could become corrupt Solutions have > 2 copies, vote Checksum Good: Performance (1 logical write => 2 physical write) Tolerate failure Bad: Capacity (1/2 for 2 way mirror) Level 4: Parity Bit level example, each row has even # of 1’s Disk 0 Disk 1 Disk 2 Parity Disk 0 1 0 1 0 0 0 0 “Full stripe write” Write: Disk 0,1,2 => RAID controller, compute parity Do all writes in parallel Random write: 1 block Disk 0 Disk 1 Disk 2 Parity 0 1 2 P0,1,2 3 4 5 P3,4,5 6 7 8 P6,7,8 How to write 4?...

Today FS API FS Implementation FS API File byte array has low-level name (number) Directory Map human-readable names -> low-level names e.g. file “main.c” low-level #: 1000 directory: “main.c” -> 1000 Access open, read, close Grow open, write, close Write to arbitrary point in the file: lseek Delete unlink FS: tracks info about each file “Meta data” What info is there per file? Directory Just a special type of file metadata: inode data: contents of directory Map: “main....

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?...