Publications: 45 | Followers: 0

lec12-cv-sem

Publish on Category: Birds 0

Lecture12CV and Semaphores
ConditionVariables
Condition Variable: queue of sleeping threads.Threads add themselves to the queue with wait.Threads wake up threads on the queue with 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, doing nothing
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 (attempt 1)
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 (attempt 2)
voidthread_exit() {done = 1; //aCond_signal(&c);//b}voidthread_join() {Mutex_lock(&m);//wif (done == 0)//xCond_wait(&c, &m); // yMutex_unlock(&m);//z}
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 withCV’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) {buffer[fillptr] = value;fillptr= (fillptr+ 1) % max;numfull++;}intget() {inttmp= buffer[useptr];useptr= (useptr+ 1) % max;numfull--;returntmp;}
Solution v1
void *consumer(void *arg) {while(1) {Mutex_lock(&m); //c1while(numfull== 0) //c2Cond_wait(&C,&m);//c3inttmp=get();//c4Cond_signal(&C); //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(&C,&m); //p3put(i);//p4Cond_signal(&C); //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
Better solution (usually): usetwo CVsSolutionv2
void *consumer(void *arg) {while(1) {Mutex_lock(&m); //c1if (numfull== 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); //p1if (numfull== max) //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
Solutionv3
void *consumer(void *arg) {while(1) {Mutex_lock(&m); //c1while(numfull== 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 (numfull== max) //p2Cond_wait(&E,&m);//p3put(i); //p4Cond_signal(&F); //p5Mutex_unlock(&m); //p6}}
Solution v4
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}}
Semaphore
Semaphoreskeep extra state, so users sometimes don’t.UnlikeCV, signal was not lostdueto some race condition!Can be used as both locks and condition variables.
ActualDefinition
sem_init(sem_t*s,intinitval) {s->value =initval}sem_wait(sem_t*s) {s->value -= 1waitif s->value < 0}sem_post(sem_t*s) {s->value += 1wakeone waiting thread (if there are any)}
wait and post are atomic
value = 4: 4 waiting signals value = -3: 3 waiting threads
Joinwith CV
intdone =0;mutex_tm =MUTEX_INIT;cond_tc = COND_INIT;void *child(void *arg){Mutex_lock(&m);done = 1;cond_signal(&c);Mutex_unlock(&m);}intmain(intargc, char *argv[]) {pthread_tc;Pthread_create(c, NULL, child, NULL);Mutex_lock(&m);while(done == 0)Cond_wait(&c, &m);Mutex_unlock(&m);}
Joinwith Semaphore
sem_ts;void *child(void *arg){sem_post(&s);}intmain(intargc, char *argv[]) {sem_init(&s,?);pthread_tc;Pthread_create(c, NULL, child, NULL);sem_wait(&s);}
Buildlocks with semaphores
typedefstruct__lock_t{//whatever datastructsyou need goes here}lock_t;voidinit(lock_t*lock) {//initcode goes here}void acquire(lock_t*lock) {//lock acquire code goes here}void release(lock_t*lock) {//lock release code goes here}
Queue get/put
voidput(intvalue) {buffer[fillptr] = value;fillptr= (fillptr+ 1) % max;numfull++;}intget() {inttmp= buffer[useptr];useptr= (useptr+ 1) % max;numfull--;returntmp;}
P/C problemsemaphore v1
sem_tempty, full;void*consumer(void *arg) {inti,tmp= 0;while (tmp!= -1) {sem_wait(&full);//C1tmp= get();// C2sem_post(&empty); //C3printf("%d\n",tmp);}}
void*producer(void *arg) {inti;for (i= 0;i< loops;i++) {sem_wait(&empty); //P1put(i); // P2sem_post(&full);// P3}}
intmain(intargc, char *argv[]) {// ...sem_init(&empty,?);sem_init(&full,?);// ...}
P/C problemsemaphore v2
sem_tempty, full,mutex;void*consumer(void *arg) {inti,tmp= 0;while (tmp!= -1){sem_wait(&mutex);//C0sem_wait(&full);//C1tmp= get();// C2sem_post(&empty); //C3sem_post(&mutex);//C4printf("%d\n",tmp);}}
void*producer(void *arg) {inti;for (i= 0;i< loops;i++) {sem_wait(&mutex); //P0sem_wait(&empty); //P1put(i); // P2sem_post(&full);// P3sem_post(&mutex);//P4}}
intmain(intargc, char *argv[]) {// ...sem_init(&empty,MAX);sem_init(&full,0);sem_init(&mutex,1);// ...}
P/C problemsemaphore v3
sem_tempty, full,mutex;void*consumer(void *arg) {inti,tmp= 0;while (tmp!= -1){sem_wait(&full);//C1sem_wait(&mutex);//C1.5tmp= get();// C2sem_post(&mutex);//C2.5sem_post(&empty);//C3printf("%d\n",tmp);}}
void*producer(void *arg) {inti;for (i= 0;i< loops;i++) {sem_wait(&empty);//P1sem_wait(&mutex);//P1.5put(i); // P2sem_post(&mutex); // P2.5sem_post(&full);//P3}}
intmain(intargc, char *argv[]) {// ...sem_init(&empty,MAX);sem_init(&full,0);sem_init(&mutex,1);// ...}
Reader-Writer Locks
The Dining Philosophers
Build semaphoreswithlocks and CV’s
typedefstruct__sem_t{intvalue;cond_tcond;lock_tlock;}sem_t;voidsem_init(sem_t*s,intvalue) {s->value = value;Cond_init(&s-&gt;cond);Lock_init(&s-&gt;lock);}voidsem_wait(sem_t*s){…}voidsem_post(sem_t*s){…}
Next: Concurrency bugs

0

Embed

Share

Upload

Make amazing presentation for free
lec12-cv-sem