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

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