15-410, F’04- 1 -Synchronization #2Sep. 20, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL09_Synch15-410“Strangers in the night...”15-410, F’04- 2 -SynchronizationProject 1 due tonightProject 1 due tonight(but you knew that)Project 0 feedback progressProject 0 feedback progressRed ink on paper: available Friday in classGoing over yours is importantCode quality not a major part of P0 gradeWill be part of P1 gradeWill be part of your interaction with your P2/P3 partnerNumerical score (test results)Will appear in 410/usr/$USER/grades/p0Target: this evening15-410, F’04- 3 -SynchronizationRegister your project partnerRegister your project partner“Partner registration” page on Projects pageIf you know your partner today, please register todayYou'll get your shared AFS space soonerYour classmates will appreciate it15-410, F’04- 4 -OutlineLast timeLast timeTwo building blocksThree requirements for mutual exclusionAlgorithms people don't use for mutual exclusionTodayTodayWays to really do mutual exclusionNext timeNext timeInside voluntary deschedulingProject 2 – thread library15-410, F’04- 5 -Mutual Exclusion: ReminderProtects an atomic instruction sequenceProtects an atomic instruction sequenceDo "something" to guard againstCPU switching to another threadThread running on another CPUAssumptionsAssumptionsAtomic instruction sequence will be “short”No other thread “likely” to compete15-410, F’04- 6 -Mutual Exclusion: GoalsTypical case (no competitor) should be fastTypical case (no competitor) should be fastAtypical case can be slowAtypical case can be slowShould not be “too wasteful”15-410, F’04- 7 -Interfering Code SequencesCustomer Deliverycash = store->cash; cash = store->cash;cash += 50; cash -= 2000;wallet -= 50; wallet += 2000;store->cash = cash; store->cash = cash;Which sequences interfere?“Easy”: Customer interferes with CustomerAlso: Delivery interferes with Customer15-410, F’04- 8 -Mutex aka Lock aka LatchSpecify interfering code sequences via Specify interfering code sequences via objectobjectData item(s) “ protected by the mutex”Object methods encapsulate entry & exit protocolsObject methods encapsulate entry & exit protocols mutex_lock(&store->lock); cash = store->cash cash += 50; personal_cash -= 50; store->cash = cash; mutex_unlock(&store->lock);What's inside?What's inside?15-410, F’04- 9 -Mutual Exclusion: Atomic ExchangeIntel x86 XCHG instructionIntel x86 XCHG instructionintel-isr.pdf page 754xchg (%esi), %edixchg (%esi), %ediint32 xchg(int32 *lock, int32 val) { register int old; old = *lock; /* bus is locked */ *lock = val; /* bus is locked */ return (old);}15-410, F’04- 10 -Inside a MutexInitializationInitializationint lock_available = 1;Try-lockTry-locki_won = xchg(&lock_available, 0);Spin-waitSpin-waitwhile (!xchg(&lock_available, 0) /* nothing */ ;UnlockUnlockxchg(&lock_available, 1); /*expect 0*/15-410, F’04- 11 -Strangers in the Night, Exchanging 0's1Thread0?Thread?015-410, F’04- 12 -And the winner is...0Thread0Thread115-410, F’04- 13 -Does it work?[What are the questions, again?][What are the questions, again?]15-410, F’04- 14 -Does it work?Mutual ExclusionMutual ExclusionProgressProgressBounded WaitingBounded Waiting15-410, F’04- 15 -Does it work?Mutual ExclusionMutual ExclusionOnly one thread can see lock_available == 1ProgressProgressWhenever lock_available == 1 a thread will get itBounded WaitingBounded WaitingNoA thread can lose arbitrarily many times15-410, F’04- 16 -Ensuring Bounded WaitingLockLockwaiting[i] = true; /*Declare interest*/got_it = false;while (waiting[i] && !got_it) got_it = xchg(&lock_available, false);waiting[i] = false;15-410, F’04- 17 -Ensuring Bounded WaitingUnlockUnlockj = (i + 1) % n;while ((j != i) && !waiting[j]) j = (j + 1) % n; if (j == i) xchg(&lock_available, true); /*W*/ else waiting[j] = false;15-410, F’04- 18 -Ensuring Bounded WaitingVersus textbookVersus textbookExchange vs. TestAndSet“ Available” vs. “ locked”Atomic release vs. normal memory write Text does “ blind write” at point “ W” lock_available = true; This may be illegal on some machines Unlocker may be required to use special memory accessExchange, TestAndSet, etc.15-410, F’04- 19 -EvaluationOne awkward requirementOne awkward requirementOne unfortunate behaviorOne unfortunate behavior15-410, F’04- 20 -EvaluationOne awkward requirementOne awkward requirementEverybody knows size of thread population Always & instantly! Or uses an upper boundOne unfortunate behaviorOne unfortunate behaviorRecall: expect zero competitorsAlgorithm: O(n) in maximum possible competitorsIs this criticism too harsh?Is this criticism too harsh?After all, Baker's Algorithm has these misfeatures...15-410, F’04- 21 -Looking DeeperLook beyond abstract semanticsLook beyond abstract semanticsMutual exclusion, progress, bounded waitingConsiderConsiderTypical access patternRuntime environmentEnvironmentEnvironmentUniprocessor vs. Multiprocessor Who is doing what when we are trying to lock/unlock?Threads aren't mysteriously “ running” or “ not running” Decision made by scheduling algorithm with properties15-410, F’04- 22 -Uniprocessor EnvironmentLockLockWhat if xchg() didn't work the first time?Some other process has the lock That process isn't running (because we are) xchg() loop is a waste of time We should let the lock-holder run instead of usUnlockUnlockWhat about bounded waiting?When we mark mutex available, who wins next? Whoever runs next..only one at a time! (“ Fake competition” ) How unfair are real OS kernel thread schedulers? If scheduler is vastly unfair, the right thread will never run!15-410, F’04- 23 -Multiprocessor EnvironmentLockLockSpin-waiting probably justified (why?)UnlockUnlockNext xchg() winner “ chosen” by memory hardwareHow unfair are real memory controllers?15-410, F’04- 24 -Test&Setboolean testandset(int32 *lock) {register boolean old; old = *lock; /* bus is locked */ *lock = true; /* bus is locked */ return (old);}Conceptually simpler than XCHG?Conceptually simpler than XCHG?Or not15-410, F’04- 25 -Load-linked, Store-conditionalFor multiprocessorsFor multiprocessors“ Bus locking considered harmful”Split XCHG into halvesSplit XCHG into
View Full Document
Unlocking...