CPS110: Ordering constraintsToo much milk solutionToo much milk “w/o waiting”?Review of invariantsMore on invariantsIntro to ordering constraintsRelease lock before spinning?One more tryIdeal solutionRelease the lock before sleep?Slide 11Slide 12Slide 13Two types of synchronizationCourse administrationSlide 16Monitor synchronizationLocks and condition variablesCondition variable operationsCVs and invariantsMulti-threaded queueSlide 22Slide 23Slide 24Slide 25Mesa vs. Hoare monitorsHoare semanticsTips for using monitorsProducer-consumer problemSlide 30Use a soda machine as a bufferSolving producer-consumerProducer-consumer codeVariations: looping producerVariations: resting producerVariations: one CV?Slide 37Slide 38Slide 39Broadcast vs signalCPS110: Ordering constraintsLandon CoxJanuary 21, 2009Too much milk solutionleave noteLandonwhile (noteMelissa){ do nothing}if (noMilk){ buy milk;}remove noteLandonleave noteMelissaif (no noteLandon){ if (noMilk){ buy milk; }}remove noteMelissaToo much milk “w/o waiting”?lock ()if (noNote && noMilk){ leave note “at store” unlock () buy milk lock () remove note unlock ()} else { unlock ()}Only hold lock while handling shared resource.lock ()if (noNote && noMilk){ leave note “at store” unlock () buy milk lock () remove note unlock ()} else { unlock ()}Not holdinglockReview of invariantsWhat is an invariant?A “consistent/sane state”Something that is “always” trueWhen can an invariant be broken?Can only be broken while lock is heldAnd only by thread holding the lockReally a “public” invariantWhat is the data’s state in when the lock is freeLike having a room tidy before guests arriveHold a lock whenever manipulating shared dataMore on invariantsWhat about reading shared data?Still must hold lockElse another thread could break invariant(Thread A prints Q as Thread B enqueues)Hold a lock whenever reasoning about shared dataIntro to ordering constraintsSay you want dequeue to wait while the queue is emptyCan we just busy-wait?No!Still holding lockdequeue () { lock (qLock); element=NULL; while (head==NULL) {} // remove head element=head->next; head->next=NULL; unlock (qLock); return element;}Release lock before spinning?dequeue () { lock (qLock); element=NULL; unlock (qLock); while (head==NULL) {} lock (qLock); // remove head element=head->next; head->next=NULL; unlock (qLock); return element;}What can go wrong? Another dequeuer could “steal” our element Head might be NULL when we try to remove entryOne more tryDoes it work?Seems okWhy?ShS protectedWhat’s wrong?Busy-waitingWastefuldequeue () { lock (qLock); element=NULL; while (head==NULL) { unlock (qLock); lock (qLock); } // remove head element=head->next; head->next=NULL; unlock (qLock); return element;}Ideal solutionWould like dequeueing thread to “sleep”Add self to “waiting list”Enqueuer can wake up when Q is non-emptyProblem: what to do with the lock?Why can’t dequeueing thread sleep with lock?Enqueuer would never be able to addRelease the lock before sleep?dequeue () { acquire lock … if (queue empty) { release lock add self to wait list sleep } … release lock}enqueue () { acquire lock find tail of queue add new element if (dequeuer waiting){ remove from wait list wake up dequeuer } release lock}Does this work?Release the lock before sleep?dequeue () { acquire lock … if (queue empty) { release lock add self to wait list sleep } … release lock}enqueue () { acquire lock find tail of queue add new element if (dequeuer waiting){ remove from wait list wake up dequeuer } release lock}213Thread can sleep foreverOther problems? Wait list is shared and unprotected. (bad idea)Release the lock before sleep?dequeue () { acquire lock … if (queue empty) { add self to wait list release lock sleep } … release lock}enqueue () { acquire lock find tail of queue add new element if (dequeuer waiting){ remove from wait list wake up dequeuer } release lock}Release the lock before sleep?dequeue () { acquire lock … if (queue empty) { add self to wait list release lock sleep } … release lock}enqueue () { acquire lock find tail of queue add new element if (dequeuer waiting){ remove from wait list wake up dequeuer } release lock}213Problem: missed wake-upNote: this can be fixed, but it’s messyTwo types of synchronizationAs before we need to raise the level of abstraction1.Mutual exclusionOne thread doing something at a timeUse locks2.Ordering constraintsDescribes “before-after” relationshipsOne thread waits for anotherUse monitorsCourse administrationProject 03/12 have perfect scoresIf you are struggling with P0, think about whyC++ language/Linux environment issues?Coding before thinking?Not reading the spec closely enough?Time management (i.e. not starting early enough)?Group management?Fix any non-language issues before Project 1(language issues will get fixed with practice)Project 0 questions?Course administrationProject 1 will be posted today (due February 18th)Project 1 data structuresSTL (less coding , more learning)Roll-your-own (less learning, more coding)Either is acceptableReminder: office hours (come talk to us!)Me: 1-250 on Fridays in D304Ryan: 1:30-2:30 on Tu, 430-530 on Th in North BldgNiko: 7-9 on Wednesdays in von der HeydenMatt: 415-615 on Tu on 3rd floor of LSRCExtra hours near project deadlinesOther questions or concerns?Monitor synchronization1. Mutual exclusionOne thread doing something at a timeUse locks2. Ordering constraintsDescribes “before-after” relationshipsOne thread waits for anotherMonitor: a lock + its condition variableLocks and condition variablesCondition variablesLets threads sleep inside a critical sectionInternal atomic actions (for now, by definition)CV State = queue of waiting threads + one lock// begin atomicrelease lockput thread on wait queuego to sleep// end atomicCondition variable operationswait (){ release lock put thread on wait queue go to sleep // after wake up acquire lock}signal (){ wakeup one waiter (if any)}broadcast (){ wakeup all waiters (if any)}AtomicAtomicAtomicLock always heldLock usually heldLock usually heldLock