CS537

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

Brief What is concurrency? What are the major issues? (atomicity and ordering) To begin: Abstraction of running program Process (Virtual address space, Registers) One thing at at time Multi-Threaded Process To do many things at a time (concurrently)  When context switch - no need to change page table base ptr Why Have Multi-threaded Program? Parallelism: to use $N$ CPUs ($N$ > 1), to work on one problem faster I/O: Waiting for an I/O => thread blocked (but others can run) Problems: (Synchronization) Atomicity sequence of actions: happen “all at once” (not interrupted) Ordering one thing happens before the other Atomicity Sequence of instructions: load addr, reg add 1, reg store reg, addr Problem: Data Race (Race condition) Outcome: indeterminate (outcome is not deterministic) CPU1 CPU2 Memory load => reg (100) load => reg (100) balance: 100 add 1 => reg(101) add 2 => reg (101) store => 101 store => 101 balance: 101 Can even happen on 1 CPU Thread1 Thread2 load => reg (100) add 1 => reg (101) OS: Switch Thread load => reg (100) add => 101 store 101 OS: Switch Tread store => 101 Desire: section of code (Critical Section)=> atomically (all at once) Use lock: (lock/unlock or acquire/release) How to build?...

Brief Concurrency Problems Atomicity (data) Arises when: concurrent updates to shared data Ordering (control) $T_2$ wait until $T_1$ has executed $x$ Atomicity classic example: balance++ => load + add + store another example: list insert (shared data structure) node_t *head = NULL; typedef struct node { int value; node_t *next; } node_t; void list_insert(int v) { // malloc is thread safe (multiple threads can call it w/o locking) node_t *tmp = malloc(sizeof(node_t)); assert(tmp !...