DOC PREVIEW
CMU CS 15410 - Lecture

This preview shows page 1-2-3-20-21-40-41-42 out of 42 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 4215-410, F’04- 1 -Synchronization #3Sep. 22, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL10a_Synch15-410“...Arguably less wrong...”15-410, F’04- 1 -Road MapTwo Fundamental operationsTwo Fundamental operations Atomic instruction sequence Voluntary de-scheduling15-410, F’04- 1 -OutlineSynch 1Synch 1–Two building blocks–Three requirements for mutual exclusion–Algorithms people don't use for mutual exclusionSynch 2Synch 2–How mutual exclusion is really implementedSynch 2Synch 2–Condition variables●Under the hood●The atomic-sleep problem–Semaphores, monitors – overview15-410, F’04- 1 -Voluntary de-schedulingThe SituationThe Situation–You hold lock on shared resource–But it's not in “the right mode”Action sequenceAction sequence–Unlock shared resource–Write down “wake me up when...”–Go to sleep until resource changes state15-410, F’04- 1 -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- 1 -What not to doWhy is this wrong?Why is this wrong?–Make sure you understand!–See previous two lectures–Do not do this in P2 or P315-410, F’04- 1 -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- 1 -Arguably less wrongDon't do this eitherDon't do this either–How wrong is “a while”?●N-1 times it's much too short●Nth time it's much too long●It's wrong every time–What's the problem?●We don't really want a duration!●We want to wait for a condition15-410, F’04- 1 -Something is missingMutex protects shared stateMutex protects shared state–Also encapsulates “interfering code sequence” as object–GoodHow 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- 1 -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- 1 -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- 1 -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- 1 -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-safe–Many threads may call condition_wait() at same time–Many threads may call condition_signal() at same time–Say, those look like “interfering sequences”...15-410, F’04- 1 -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 lock–You'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- 1 -Inside a Condition Variablecvar->queue - of sleeping processescvar->queue - of sleeping processes–FIFO or more exoticcvar->mutexcvar->mutex–Protects queue against interfering wait()/signal() calls–This isn't the client's mutex (locking client's world state)–This is our secret invisible mutex15-410, F’04- 1 -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- 1 -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- 1 -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- 1 -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- 1 -Achieving wait() AtomicityP2 challengesP2 challenges–Understand the issues!●mutex, cvar–Understand the host kernel we give you–Put the parts together●Don't use “wrong” or “arguably less wrong” approaches!●Seek solid, clear solutions15-410, F’04- 1 -OutlineLast timeLast time–How mutual exclusion is really implementedCondition variablesCondition variables–Under the hood–The atomic-sleep problem SemaphoresSemaphoresMonitorsMonitors15-410, F’04- 1 -Semaphore ConceptSemaphore is a different encapsulation objectSemaphore is a different encapsulation object–Can produce mutual exclusion–Can produce sleep-until-it's-timeIntuition: counted resourceIntuition: counted resource–Integer represents “number available”●Semaphore object initialized to a particular count–Thread blocks until it is allocated an instance15-410, F’04- 1 -Semaphore Conceptwait(), aka P(), aka proberen (“wait”)wait(), aka P(), aka proberen (“wait”)–wait until value > 0–decrement value (“taking” one instance)signal(), aka V(), aka


View Full Document

CMU CS 15410 - Lecture

Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?