lec12-cv

Lecture 12CV
Last lecture
Controlling interruptsTestand set (atomic exchange)Compare and swapLoad linkedandstore conditionalFetch and addandticket locks
typedefstruct__lock_t{intflag;intguard;queue_t*q;}lock_t;voidlock_init(lock_t*m) {m->flag = 0;m->guard = 0;queue_init(m->q);}
voidlock(lock_t*m) {while (TestAndSet(&m->guard, 1) == 1); //acquire guard lock by spinningif (m->flag == 0) {m->flag = 1; // lock is acquiredm->guard = 0;}else {queue_add(m->q,gettid());setpark();m->guard = 0;park();}}
voidunlock(lock_t*m) {while(TestAndSet(&m->guard, 1) == 1); //acquire guard lock by spinningif (queue_empty(m->q))m->flag = 0; // let go oflock; noone wants itelse// hold lock (for next thread!)unpark(queue_remove(m->q));m->guard = 0;}
Different Support on Linux
OnLinux,OS provides two calls:futex_wait(address,expected)putsthe calling thread to sleep, assuming the value at address is equal to expected. If it is not equal, the call returnsimmediately.futex_wake(address)wakes one thread that is waiting on the queue.
voidlock(lock_t*m) {intv;/*Bit 31 was clear, we got themutex(fastpath) */if(atomic_bit_test_set(m,31) ==0) return;atomic_increment(m);while (1) {if (atomic_bit_test_set(m,31) == 0) {atomic_decrement(m); return;}/*We have to wait now. First make sure thefutexvaluewe are monitoring is truly negative (i.e. locked). */v=*m;if(v >= 0)continue;futex_wait(m,v);}}
voidunlock(lock_t*m) {/*Adding 0x80000000 to the counter results in0 if& only if thereare not other interested threads */if(atomic_add_zero(mutex, 0x80000000))return;/* There are other threads waiting for thismutex,wake one of them up. */futex_wake(mutex);}
Lock Usage Examples
ConcurrentCountersConcurrent LinkedListsConcurrent QueuesConcurrent Hash Table
Concurrency Objectives
Mutual exclusion (e.g., A and B don’t run at same time)solvedwith locksOrdering (e.g., B runs after A)solvedwith condition variables
Condition Variables
CV’s are more like channels than variables.B waits for a signal on channel before running.A sends signal when it is time for B to run.A CV also has a queue of waiting threads.A CV is usually PAIRED with some kind statevariable.
wait and signal
wait(cond_t*cv,mutex_t*lock)assumesthe lock is held when wait() is calledputscaller to sleep + releases the lock (atomically)whenawoken, reacquires lock before returningsignal(cond_t*cv)wakea single waiting thread (if >= 1 thread is waiting)ifthere is no waiting thread, just return w/o doing anything
Ordering Example: Join
pthread_tp1, p2;printf("main: begin [balance = %d]\n", balance);Pthread_create(&p1, NULL,mythread, "A");Pthread_create(&p2, NULL,mythread, "B");// join waits for the threads to finishPthread_join(p1, NULL);Pthread_join(p2, NULL);printf("main: done\n [balance: %d]\n [should: %d]\n",balance, max*2);return 0;
Implementing Join with CV’s(Correct)
voidthread_exit() {Mutex_lock(&m);done = 1; //aCond_signal(&c);//bMutex_unlock(&m);}voidthread_join() {Mutex_lock(&m);//wwhile(done == 0)//xCond_wait(&c, &m); // yMutex_unlock(&m);//z}
Implementing Join with CV’s(wrong 1)
voidthread_exit() {done = 1; //aCond_signal(&c);//b}voidthread_join() {Mutex_lock(&m);//wif (done == 0)//xCond_wait(&c, &m); // yMutex_unlock(&m);//z}
Implementing Join with CV’s(wrong 2)
voidthread_exit() {Mutex_lock(&m);//aCond_signal(&c);//bMutex_unlock(&m);//c}voidthread_join() {Mutex_lock(&m);//xCond_wait(&c, &m); // yMutex_unlock(&m);// z}
Implementing Join with CV’s (wrong3)
voidthread_exit() {done = 1; //aCond_signal(&c);//b}voidthread_join() {if (done == 0) // xCond_wait(&c, &m); //y}
Good Rule of Thumb
Keep state in addition to CV’s!CV’s are used to nudge threads when state changes.If state is already as needed, don’t wait for a nudge!Always do wait and signal while holding the lock!
Implementing Join with CV’s (Correct?)
voidthread_exit() {Mutex_lock(&m);done = 1; //aCond_signal(&c); // bMutex_unlock(&m);}voidthread_join() {Mutex_lock(&m);//wif (done == 0)//xCond_wait(&c, &m); // yMutex_unlock(&m);//z}
Implementing Join with CV’s (Correct?)
voidthread_exit() {Mutex_lock(&m);done = 1; //aMutex_unlock(&m);Cond_signal(&c);// b}voidthread_join() {Mutex_lock(&m);//wif (done == 0)//xCond_wait(&c, &m); // yMutex_unlock(&m);//z}
Implementing Join withCV’s(Correct?)
voidthread_exit(){done = 1; //aMutex_lock(&m);Cond_signal(&c);//bMutex_unlock(&m);}voidthread_join() {Mutex_lock(&m);//wif (done == 0)//xCond_wait(&c, &m); // yMutex_unlock(&m);//z}
Producer/Consumer ProblemExample: UNIXPipes
A pipe may have many writers and readers.Internally, there is a finite-sized buffer.Writers add data to the buffer.Readers remove data from the buffer.Implementation:reads/writesto buffer requirelockingwhenbuffers are full, writers must waitwhenbuffers are empty, readers must wait
Producer/ConsumerProblem
Producers generate data (like pipe writers).Consumers grab data and process it (like pipe readers).Producer/consumer problems are frequent in systems.PipesWeb serversMemory allocatorsDevice I/O…
Queue get/put
voidput(intvalue) {assert(count == 0);count = 1;buffer = value;}intget() {assert(count == 1);count = 0;return buffer;}
Solutionv0
void *consumer(intloops) {for (inti=0;i< loops;i++){inttmp=get(i);printf("%d\n",tmp);}}
void *producer(intloops){for(inti=0;i< loops;i++){put(i);}}
Solution v1
void *consumer(intloops) {for (inti=0;i< loops;i++){Mutex_lock(&m); //c1if (count == 0) //c2Cond_wait(&C, &m); //c3inttmp= get(); //c4Cond_signal(&C); //c5Mutex_unlock(&m); //c6printf("%d\n",tmp);}}
void *producer(intloops) {for(inti=0;i< loops;i++){Mutex_lock(&m); //p1if (count == 1) //p2Cond_wait(&C, &m); //p3put(i); //p4Cond_signal(&C); //p5Mutex_unlock(&m); //p6}}
Solution v2
void *consumer(intloops) {for (inti=0;i< loops;i++){Mutex_lock(&m); //c1while (count == 0) //c2Cond_wait(&C, &m); //c3inttmp= get(); //c4Cond_signal(&C); //c5Mutex_unlock(&m); //c6printf("%d\n",tmp);}}
void *producer(intloops) {for(inti=0;i< loops;i++){Mutex_lock(&m); //p1while (count == 1) //p2Cond_wait(&C, &m); //p3put(i); //p4Cond_signal(&C); //p5Mutex_unlock(&m); //p6}}
Better solution (usually): usetwo CVsSolutionv3
void *consumer(intloops) {while(1) {Mutex_lock(&m); //c1while (count == 0) //c2Cond_wait(&F,&m);//c3inttmp=get();//c4Cond_signal(&E); //c5Mutex_unlock(&m);//c6printf("%d\n",tmp);}}
void *producer(intloops) {for(inti=0;i< loops;i++){Mutex_lock(&m); //p1while (count == 1) //p2Cond_wait(&E, &m); //p3put(i);//p4Cond_signal(&F); //p5Mutex_unlock(&m); //p6}}
Summary: rules of thumb
Keep state in addition to CV’sAlways do wait/signal with lock heldWhenever you acquire a lock, recheck state
Queue get/put
voidput(intvalue) {buffer[fill]= value;fill= (fill+ 1) % max;count++;}intget() {inttmp=buffer[use];use= (use+ 1) % max;count-;returntmp;}
Solutionv4 (final)
void *consumer(void *arg) {while(1) {Mutex_lock(&m); //c1while(count == 0)//c2Cond_wait(&F,&m);//c3inttmp=get();//c4Cond_signal(&E); //c5Mutex_unlock(&m);//c6printf("%d\n",tmp);}}
void *producer(void *arg) {for(inti=0;i< loops;i++){Mutex_lock(&m); //p1while(count ==max ) //p2Cond_wait(&E,&m);//p3put(i); //p4Cond_signal(&F); //p5Mutex_unlock(&m); //p6}}
Solutionv5
void *consumer(void *arg) {while(1) {Mutex_lock(&m); //c1while(numfull== 0)//c2Cond_wait(&F,&m);//c3Mutex_unlock(&m);//c3ainttmp=get();//c4Mutex_lock(&m);//c5aCond_signal(&E); //c5Mutex_unlock(&m);//c6printf("%d\n",tmp);}}
void *producer(void *arg) {for(inti=0;i< loops;i++){Mutex_lock(&m); //p1while (numfull== max) //p2Cond_wait(&E,&m);//p3Mutex_unlock(&m); //p3aput(i); //p4Mutex_lock(&m); //p5aCond_signal(&F); //p5Mutex_unlock(&m); //p6}}
How to wake the right thread?
wait(cond_t*cv,mutex_t*lock)assumes the lock is held when wait() is calledputs caller to sleep + releases the lock (atomically)when awoken, reacquires lock before returningsignal(cond_t*cv)wake a single waiting thread (if >= 1 thread is waiting)if there is no waiting thread, just return, doing nothingbroadcast(cond_t*cv)wakeall waiting threads (if >= 1 thread is waiting)ifthere are no waiting thread, just return, doing nothing
Next: Concurrency bugs