Brief Virtual Memory Goal: each process with illusion (own large private memory) Three techniques Base/Bounds & Segmentation Variable-sized allocation External Fragmentation Paging Fixed-sized units (pages) No external fragmentation Too slow Too big Structure of Page Table: Linear (Arrays) One entry in Page table per virtual page V: valid bit (set by OS) Protection: R/W/X Problem: Large Virtual Address Space (32bit, 64bit) 32 Bit, 4KB Page => ~1 Million ($2^{20}$) Virtual Pages Size: $2^{20}; \times$ PTE size (4 Byte) = 4MB 300 Processes = 300 $\times$ 4 MB = ~1....

Brief Hard Drive: today Later: Flash-based SSD RAID: (Redundant Array of Independent Drives) Collection => faster, more reliable Hard Drive Persistent Storage $T_{i/o}=T{seek}+T{rotate}+T{transfer}$ $T_{seek}$: Move arm to correct track $T_{rotate}$: Wait Performance Random, small I/Os: Really bad (spend most time in seek rotate) Sequential, large I/Os: better perf (most time is spent in transfer) Disk Scheduling: Disk: queue of request How to schedule them? What order? Strategies: FIFO (not so good) SSTF: Shortest seek time first Variants: SCAN (elevator) or C-SCAN SPTF/SATF: Shortest positioning (access) time first (Accounts for seek & rotate) Not “optimal” but used in practice Problem Starvation Solutions Bounded SATF Window of requests (some fixed number) Services all requests in window before subsequent requests RAID Evaluate: Different Approaches to RAID organization...

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