15-410, F’04- 1 -Synchronization #1Sep. 17, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL08b_Synch15-410“My computer is 'modern'!”15-410, F’04- 2 -SynchronizationProject 0 feedback planProject 0 feedback planFirst step: red ink on paperSoon: scores (based mostly on test outcomes)Project 1 alertsProject 1 alerts“make print” must workPlease check for completenessDoxygen documenation must buildPlease check for completeness15-410, F’04- 3 -Project 0 Common ThemesStyle/structureStyle/structureIntegers instead of #defined tokens“2” is not better than “TYPE_DOUBLE”It is much much much worseDon't ever do that“Code photocopier” - indicates a problem, often seriousBad variable/function namesinitialize() should not terminateint i; /* number of frogs */ ⇐ Don't apologize; fix the problem!Excessively long functionswhile(1) should be rare Don't make us read...False comments, dead code, extra copies of codeHarry Bovik did not help you write your P015-410, F’04- 4 -Project 0 Common ThemesStyle/structureStyle/structureCode is read by peopleUsYour partnerYour manager...Don't make it painful for usor else...15-410, F’04- 5 -Project 0 Common ThemesRobustnessRobustnessNot checking syscall returns (e.g., tmpfile())Not finding last function / not handing unnamed functionMemory leak (no need for malloc() at all!)File-descriptor leak15-410, F’04- 6 -Project 0 Common ThemesNot following specNot following specHand-verifying addresses (compare vs. 0x0804... 0xc000...)Approximating arg-offset infoInstead of getting it from the table!!Give up via exit() ⇐ caller never authorized that!Stopping trace at hard-coded function nameSemantic mismatchSemantic mismatch\b is a “backspace character”Clever hack to “undo” a comma in the output stream?Only when the output stream is a terminal!!!Instead of fixing the wrong thing, do the right thing15-410, F’04- 7 -OutlineMe vs. Chapter 7Me vs. Chapter 7Mind your P's and Q'sAtomic sequences vs. voluntary de-scheduling “ Sim City” exampleYou will need to read the chapterHopefully my preparation/review will clarify it15-410, F’04- 8 -OutlineAn intrusion from the “ real world”An intrusion from the “ real world”Two fundamental operationsTwo fundamental operationsThree necessary critical-section propertiesThree necessary critical-section propertiesTwo-process solutionTwo-process solutionN-process “Bakery Algorithm”N-process “Bakery Algorithm”15-410, F’04- 9 -Mind your P's and Q'sWhat you writeWhat you write choosing[i] = true; number[i] = max(number[0], number[1], ...) + 1; choosing[i] = false;What happens...What happens... number[i] = max(number[0], number[1], ...) + 1; choosing[i] = false;15-410, F’04- 10 -Mind your P's and Q'sWhat you writeWhat you write choosing[i] = true; number[i] = max(number[0], number[1], ...) + 1; choosing[i] = false;Or maybe this happens...Or maybe this happens... choosing[i] = false; number[i] = max(number[0], number[1], ...) + 1;“ Computer Architecture for $200, Dave” ...“ Computer Architecture for $200, Dave” ...15-410, F’04- 11 -My computer is broken?!No, your computer is No, your computer is "modern""modern"Processor "write pipe" queues memory stores...and coalesces "redundant" writes!Crazy?Crazy?Not if you're pounding out pixels!CPUMemorychoosing[i] falsenumber[i] 45choosing[i] true15-410, F’04- 12 -My computer is broken?!Magic "memory barrier" instructions available...Magic "memory barrier" instructions available......stall processor until write pipe is emptyOk, now I understandOk, now I understandProbably not! http://www.cs.umd.edu/~pugh/java/memoryModel/ “ Double-Checked Locking is Broken” DeclarationSee also "release consistency"Textbook's memory modelTextbook's memory model...is “ what you expect”Ok to use simple model for homework, exams15-410, F’04- 13 -Synchronization FundamentalsTwo fundamental operationsTwo fundamental operationsAtomic instruction sequenceVoluntary de-schedulingMultiple implementations of eachMultiple implementations of eachUniprocessor vs. multiprocessorSpecial hardware vs. special algorithmDifferent OS techniquesPerformance tuning for special casesBe Be very clearvery clear on features, differences on features, differences15-410, F’04- 14 -Synchronization FundamentalsMultiple client abstractionsMultiple client abstractionsTextbook coversTextbook coversSemaphore, critical region, monitorVeryVery relevant relevantMutex/condition variable (POSIX pthreads)Java "synchronized" keyword (3 uses)15-410, F’04- 15 -Synchronization FundamentalsTwo Fundamental operationsTwo Fundamental operations⇒ Atomic instruction sequence Voluntary de-scheduling15-410, F’04- 16 -Atomic instruction sequenceProblem domainProblem domainShort sequence of instructionsNobody else may interleave same sequenceor a "related" sequence“Typically” nobody is competing15-410, F’04- 17 -Non-interferenceMultiprocessor simulation (think: “Sim City” )Multiprocessor simulation (think: “Sim City” )Coarse-grained “ turn” (think: hour)Lots of activity within turnThink: M:N threads, M=objects, N=#processorsMostMost cars don't interact in a game turn... cars don't interact in a game turn...Must model those that do!15-410, F’04- 18 -CommerceCustomer 0 Customer 1cash = store->cash; cash = store->cash;cash += 50; cash += 20;wallet -= 50; wallet -= 20;store->cash = cash; store->cash = cash;Should the store call the police?Is deflation good for the economy?15-410, F’04- 19 -Commerce – ObservationsInstruction sequences are “ short”Instruction sequences are “ short”Ok to force competitors to waitProbability of collision is "low"Probability of collision is "low"Many non-colliding invocations per secondMust not use an expensive anti-collision approach!Oh, just make a system call...Common (non-colliding) case must be fast15-410, F’04- 20 -Synchronization FundamentalsTwo Fundamental operationsTwo Fundamental operations Atomic instruction sequence ⇒ Voluntary de-scheduling15-410, F’04- 21 -Voluntary de-schedulingProblem domainProblem domain“Are we there yet?”“Waiting for Godot”Example - "Sim City" disaster daemonExample - "Sim City" disaster daemonwhile (date < 1906-04-18)
View Full Document
Unlocking...