15-410, F’04- 1 -Synchronization #3Sep. 22, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL10a_Synch15-410“...Arguably less wrong...”15-410, F’04- 2 -Road MapTwo Fundamental operationsTwo Fundamental operations√ Atomic instruction sequence⇒ Voluntary de-scheduling15-410, F’04- 3 -OutlineSynch 1Synch 1Two building blocksThree requirements for mutual exclusionAlgorithms people don't use for mutual exclusionSynch 2Synch 2How mutual exclusion is really implementedSynch 2Synch 2Condition variablesUnder the hoodThe atomic-sleep problemSemaphores, monitors – overview15-410, F’04- 4 -Voluntary de-schedulingThe SituationThe SituationYou hold lock on shared resourceBut it's not in “the right mode”Action sequenceAction sequenceUnlock shared resourceWrite down “wake me up when...”Go to sleep until resource changes state15-410, F’04- 5 -What not to dowhile (!reckoning) { mutex_lock(&scenario_lk); if ((date >= 1906-04-18) && (hour >= 5)) reckoning = true; else mutex_unlock(&scenario_lk);}wreak_general_havoc();mutex_unlock(&scenario_lk);15-410, F’04- 6 -What not to doWhy is this wrong?Why is this wrong?Make sure you understand!See previous two lecturesDo not do this in P2 or P315-410, F’04- 7 -Arguably Less Wrongwhile (!reckoning) { mutex_lock(&scenario_lk); if ((date >= 1906-04-18) && (hour >= 5)) reckoning = true; else { mutex_unlock(&scenario_lk); sleep(1); }}wreak_general_havoc();mutex_unlock(&scenario_lk);15-410, F’04- 8 -Arguably less wrongDon't do this eitherDon't do this eitherHow wrong is “ a while” ?N-1 times it's much too shortNth time it's much too longIt's wrong every timeWhat's the problem?We don't really want a duration!We want to wait for a condition15-410, F’04- 9 -Something is missingMutex protects shared stateMutex protects shared stateAlso encapsulates “ interfering code sequence” as objectGoodHow can we sleep for the How can we sleep for the rightright duration? duration?Get an expert to tell us!Encapsulate “ the right duration”...into a condition variable object15-410, F’04- 10 -Once more, with feeling!mutex_lock(&scenario_lk);while (cvar = wait_on()) { cond_wait(&scenario_lk, &cvar);}wreak_general_havoc(); /* locked! */mutex_unlock(&scenario_lk);15-410, F’04- 11 -wait_on()?if (y < 1906) return (&new_year);else if (m < 4) return (&new_month);else if (d < 18) return (&new_day);else if (h < 5) return (&new_hour);else return (0);15-410, F’04- 12 -What wakes us up?for (y = 1900; y < 2000; y++) for (m = 1; m <= 12; m++) for (d = 1; d <= days(m); d++) for (h = 0; h < 24; h++) ... cond_broadcast(&new_hour); cond_broadcast(&new_day); cond_broadcast(&new_month); cond_broadcast(&new_year);15-410, F’04- 13 -Condition Variable RequirementsKeep track of threads asleep “ for a while”Keep track of threads asleep “ for a while”Allow notifier thread to wake sleeping thread(s)Allow notifier thread to wake sleeping thread(s)Must be thread-safeMust be thread-safeMany threads may call condition_wait() at same timeMany threads may call condition_signal() at same timeSay, those look like “interfering sequences” ...15-410, F’04- 14 -Why two parameters?condition_wait(&mutex, &cvar);Lock required to access/modify the “ world” stateLock required to access/modify the “ world” stateWhoever awakens you will need to hold that lockWhoever awakens you will need to hold that lockYou'd better give it up.When you wake up, you will need to hold it againWhen you wake up, you will need to hold it again“Convenient” for condition_wait() to un-lock/re-lockBut there's something more subtleBut there's something more subtle15-410, F’04- 15 -Inside a Condition Variablecvar->queue - of sleeping processescvar->queue - of sleeping processesFIFO or more exoticcvar->mutexcvar->mutexProtects queue against interfering wait()/signal() callsThis isn't the client's mutex (locking client's world state)This is our secret invisible mutex15-410, F’04- 16 -Inside a Condition Variablecond_wait(mutex, cvar){ lock(cvar->mutex); enq(cvar->queue, my_thread_id()); unlock(mutex); ATOMICALLY { unlock(cvar->mutex); kernel_please_pause_this_thread(); }}What is this “ ATOMICALLY” stuff?What is this “ ATOMICALLY” stuff?15-410, F’04- 17 -What We Hope Forcond_wait(m, c); cond_signal(c);enq(c->que, me);unlock(m);unlock(c->m);kern_thr_pause();lock(c->m);id = deq(c->que);thr_wake(id);unlock(c->m);15-410, F’04- 18 -Pathological Execution Sequencecond_wait(m, c); cond_signal(c);enq(c->que, me);unlock(m);unlock(c->m);lock(c->m);id = deq(c->que);thr_wake(id);unlock(c->m);kern_thr_pause();thr_wake(id) ⇒ ERR_NOT_ASLEEP15-410, F’04- 19 -Achieving wait() AtomicityDisable interrupts (if you are a kernel)Disable interrupts (if you are a kernel)Rely on OS to implement condition variablesRely on OS to implement condition variables(Why not?)Have a better kernel thread-sleep interfaceHave a better kernel thread-sleep interface15-410, F’04- 20 -Achieving wait() AtomicityP2 challengesP2 challengesUnderstand the issues! mutex, cvarUnderstand the host kernel we give youPut the parts together Don't use “ wrong” or “ arguably less wrong” approaches! Seek solid, clear solutions15-410, F’04- 21 -OutlineLast timeLast timeHow mutual exclusion is really implementedCondition variablesCondition variablesUnder the hoodThe atomic-sleep problem⇒⇒SemaphoresSemaphoresMonitorsMonitors15-410, F’04- 22 -Semaphore ConceptSemaphore is a different encapsulation objectSemaphore is a different encapsulation objectCan produce mutual exclusionCan produce sleep-until-it's-timeIntuition: counted resourceIntuition: counted resourceInteger represents “ number available” Semaphore object initialized to a particular countThread blocks until it is allocated an instance15-410, F’04- 23 -Semaphore Conceptwait(), aka P(), aka proberen (“ wait” )wait(), aka P(), aka proberen (“ wait” )wait until value > 0decrement value (“ taking” one instance)signal(), aka V(), aka verhogen (“ increment” )signal(), aka V(), aka verhogen (“ increment” )increment value (“ releasing” one instance)Just one small issue...Just one small issue...wait() and signal() must be atomic15-410, F’04- 24 -“ Mutex-style” Semaphoresemaphore
View Full Document