Class

Today Crashes What? Why for FS? Crash (Unexpected interruption) Power loss OS bug hard reset Example file append -> file exists add block to it File System Image --------------------------------------------------- |S|IB|DB| inodes | Data blocks | --------------------------------------------------- S: Super block IB: Inode bitmap DB: Data bitmap Need to change: DB, Inode, Data block Possible write ordering: ------> D(1) I(2) DB D(3) DB(4) I I(5) DB(6) D I D DB DB I D DB D I lose data inconsistency lose data inconsistency (Space leak) inconsistency consistent (garbage) Solution Lazy: File system checker Eager: Write-ahead loggin (journaling) File System Checker (fsck) run checker after reboot (crash) scan entire file system -> SLOWt find inconsistencies fix them Write-ahead Logging (WAL) [Journaling] Idea: Before update, record some info Then do update If crash use info to recover -------------------------------------------- |S|Journal|IB|DB| inodes | Data blocks | -------------------------------------------- Protocol for update Assumptions: 512-bytes sector write is atomic (all or none) if issue many writes, happen in any order Example: File append (update DB, I, D) (memory) | -------------------------------------------------- (disk) | Journal Tb|DB|I|D|Te Tb: transaction begin Te: transaction end Split step 1 1a write Tb, contents (wait to complete) 1b write Te (512 bytes) Step 2 update in place (checkpointing) Problem: too slow (1/2 speed for data intensive workloads) Metadata-only Journaling write data only once how/when to write data

Distributed File Systems Sun Network File System (NFS) Server crash recovery design of network protocol Distributed Systems Client/Server One Server Replicated Servers Many servers Different Than “local” System? machine crash network lose packets performance latency, bandwidth resource sharing policies NFS Basics Protocol from protocol to FS API idempotency: key to failure handling performance: caching Server Crashes: How to Handle? lead to unavailibility key idea: when there is a problem => retry File Handle 3 parts: <volume#, inode #, generation #> volume: which fs?...

CPU Virtualization Mechanisms: How Policies: Scheduling How to “Time-Share” Problem: What if process $P$ wants to do something restricted? See prev Note Problem: Process may run for a long time Q: How does OS regain control of CPU? A: timer interrupt @Boot: set this up interrupt the CPU every X milliseconds Why not shorter? A: Context switch overhead, Cache miss OS responsibility for each process: track current state Running Ready (Not running, but could be) Problem: What if Process does something “Slow”?...

Brief CPU Virtualization Mechanism => Limited Direct Execution Policy => Scheduling Q) How to build a scheduling policy? Memory Virtualization Scheduling Metric #1: Turnaround Time ($T_{completes} - T_{arrives}$) “Run to completion” FIFO (FCFS) Bad (Short jobs stuck behind long jobs) SJF Process does not all arrive at $T_0$ STCF (Shortest Time to Completion First) “Generalized” SJF Metric #2: Response Time: ($T_{firstruns} - T_{arrives}$) Round Robin ABCABC….ABC (Switch frequently) Time Slice (Quantum): Multiple of how often Timer goes off “Real” Scheduler Don’t know job length (How to learn?...

Brief MMU Base/bounds (Dynamic relocation) 2 Registers OS role: When process is created: allocate (contiguous) memory for address space Keep track of Process List: $P_A$ base 2048 and bound Free List: which parts of physical memory are free When process runs: Before it run, set base and bounds on MMU then, run process When Context switch: $P_A$ running -> Timer interrupt -> Want to run $P_B$ -> need to set base/bounds for $P_B$ When Process wants to grow its address space: System call: ask OS for more memory OS: Update its free list change the bounds register to new new size Pros/Cons Pros: Fast SImple Cons: Inflexible Doesn’t support large “sparse” virtual address space Segmentation (Generalization of Base/Bounds) For each segment: keep <base, bounds> Pro: “Very large” virtual address space now possible Cons: External fragmentation => memory is hard to manage Paging