Two-phase Commit Presumed Nothing Protocol coordinator sends PREPARE to notify transaction is terminated Each cohort send COMMIT-VOTE or ABORT-VOTE Coordinator collect response Coordinator send result ABORT or COMMIT Cohort Activity Abort? Client mark first action of a transaction, cohort mark the transaction active when see first. If terminate and not active -> ABORT Client and cohort record number of actions Client send count to coordinator If not match -> ABORT Force Write Before COMMIT-VOTE (because cohort need to ask for outcome if crashed) Before ACK (because coordinator might forget outcome after ACK) Protocol Database Transactions cohorts & state: committed, aborted, active ACK, not ACK Coordinator Activity Coordinator force result to disk before sending `` Write END after all cohorts ACK (not force) No need to restore Conclusion coordinator 2 log write, 1 forced 2 messages cohort 2 log write, all forced 2 messages Presumed Abort No log if transaction aborted No ack for ABORT Message count same as PrN Presumed Commit Coordinator force write when init Remove when complete Cohort force prepare, but non-force write before commit because forgetting = commit coordinator (when commit) 2 log write, 2 forced 2 messages cohort 2 log write, 1 forced 1 messages Read-only Transaction Coordinator sent PREPARE PrA: no log writes because data not forced write, forget = abort PrC: 2 write, 1 force 1 when init 1 to mark it delete Cohorts send READ-ONLY-VOTE no log writes PrC Optimization MaintainIN Store permanently Might not have initiated Assume abort IN = REC - (COM & REC) COM committed transaction REC $REC = {tid | tid_l < tid < tid_h}$ tid_stable Highest committed tid Recovering IN tid_h Method 1: set tid_h = tid_stable + fixed amount Method 2: dynamic set tid_h but log to disk tid_l if oldest transaction: increment tid_l and log to disk COM & REC Scan from tid_h to tid_l and check if committed store in bit vector or list nPRC Protocol Abort Coordinator send PREPARE Cohort send COMMIT-VOTE, one send ABORT-VOTE Coordinator send ABORT Cohort send ACK Coordinator possibly write increase tid_l 4 msgs, 1 soft write Update Coordinator send PREPARE Cohort send COMMIT-VOTE Coordinator send COMMIT Coordinator write increase tld_l & commit 3 msgs, 1 force write Read Only Coordinator send PREPARE Cohort send READ-ONLY-VOTE 2 msgs Recalcitrant Transaction Transaction too long (or cohort crash) Fall back to PrC for that transaction Write init info to disk Garbage Collect Maintain all corhort Send ABORT to all

Operations are executed in order Query after update should see update

Virtualization Build an illusion (as many CPU & RAM as you want) Goals Efficiency Security Isolation Abstraction What changes when a program runs? registers memory I/O CPU: How to Virtualize Run $N$ proceses “at once” even though we have $M$ CPUs $(N > M)$ General idea: If 1 CPU, 2 processes (A, B) Run as ABABABAB… (interleave) aka “time sharing” Mechanisms: low-level how Policies: whilch process to run? First Attempt: Direct Execution Boottime: (Start up) OS is the first program to run...

math: true How Do Computers Work? CPU excute intruction / fetch data from memory Von Neumann architecture What is an OS? Virtualization turn one physical “thing” into many virtual ones Each process has illusion of its own CPU + own memory Concurrency Persistent How Does This Class Work

Brief Virtual Memory illusion: large, sparse address space ease of programming Q1: What if a process uses a lot of memory (more than what exists in physical memory) Q2: What if many programs use too much memory? Mechanisms Policies Mechanisms Add persistent storage device (Hard drive, SSD)  Properties Slow Cheaper (per byte) Larger Hardware Support Disk Swap Space (Disk space to hold pages of process’s address spaces that don’t fit in memory) Page Table Support (Per process) Page Table Entry |V|P|prot|------PFN------| V: Valid P: Present (if 1 -> in phys mem, if 0 -> not) When P = 0, can use PFN for swap address New Case Valid, not present: What happens?...