CS537

Brief Concurrency Atomicity (Data) OS Support + hardware support Ordering (Control - When code runs) New primitive: condition variable What makes a good lock? Correctness Overhead Fairness (extreme: starvation - never get lock) Problems: (Focus on overhead) Spin lock (xchg-based) T1 enter critical section, T2 spin How to reduce waste of spinning OS Support yield() System Call when thread calls yield moves calling thread from RUNNING to READY (Push to back of scheduling queue) while (AtomicExchange(&m->lock, 1) == 1) { yield(); } Worst case w/o yield $waste = num;of;threads \times length;of;time;slice$ $T_1$ in middle of critical section -> timer interrupt -> switch to $T_2$ spin -> $T_3$ spin … With yield $waste = num;of;threads \times context;switch;cost$ Worst case with yield is much faster than just spinning Using Queue with Spin-lock typedef struct __lock_t { int flag; // state of lock: 1=held, 0=free int guard; // use to protect flag, queue queue_t *q; // explicit queue of waiters } lock_t; void lock_init(lock_t *lock) { lock->flag = lock->guard = 0; lock->q = queue_init(); } void lock(lock_t *lock) { while (xchg(&lock->guard, 1) == 1) ; // spin if (lock->flag == 0) { // lock is free: grab it!...

Fork/Join Problem Incorrect Implementation pthread_cond_t c = PTHREAD_COND_INITIALIZER; pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; int done = 0; void *child(void *arg) { printf("child\n"); sleep(1); Mutex_lock(&m); done = 1; Cond_signal(&c); Mutex_unlock(&m); return NULL; } int main(int argc, char *argv[]) { pthread_t p; printf("parent: begin\n"); Pthread_create(&p, NULL, child, NULL); Mutex_lock(&m); while (done == 0) Cond_wait(&c, &m); // releases lock when going to sleep Mutex_unlock(&m); printf("parent: end\n"); return 0; } Issue: After line 19, switch to child, parent wait inf Correct Implementation pthread_cond_t c = PTHREAD_COND_INITIALIZER; pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; int done = 0; void *child(void *arg) { printf("child\n"); sleep(1); Mutex_lock(&m); done = 1; Cond_signal(&c); Mutex_unlock(&m); return NULL; } int main(int argc, char *argv[]) { pthread_t p; printf("parent: begin\n"); Pthread_create(&p, NULL, child, NULL); Mutex_lock(&m); while (done == 0) Cond_wait(&c, &m); // releases lock when going to sleep Mutex_unlock(&m); printf("parent: end\n"); return 0; } Producer/Consumer Problem (Bounded Buffer) Producer threads Consumer threads Share a fixed size (bounded) queue Worries: Atomicity of the queue, Ordering Example: unix pipe $ cat file....

Brief Locks: Atomicity Condition Variables: Ordering Fork/Join Producer/Consumer Semaphore Lock + CV in one Mutual Exclusion Lock version lock(); crtical section unlock(); Semaphore Version sem_wait(&lock) critical section sem_post(&lock); Initialization: to use semaphore as lock Initialize it to 1 Fork/Join child() { ... sem_post(&s); } main() { sem_init(&s, 0); pthread_create(child); sem_wait(&s); } Reader/Writer Starvation

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