CS61A Lecture 21Clicker poll Dining PhilosophersSlide 4Problems with ConcurrencyBELOW the line…What if these “happened” one after the otherIf these execute in parallel: Possibility for Incorrect Results!How many possible outcomes?EVERY ordering!If these execute in parallel… Write out the sequence of eventsSlide 12Possible outcomesOur definition of a “correct answer”?Protecting from incorrectnessSerializers protect things And make things they protect serial (def: taking place in a series)Slide 17Slide 18Slide 19We’ve seen INCORRECT… now INEFFICIENCYYou’ve seen INCORRECT and INEFFICIENT… now DEADLOCKSlide 22Slide 23Implementing SerializersWrinkles and I want to shareWrite make-mutex(make-mutex)SolutionPowerPoint PresentationSlide 29clear!Write test-and-set!test-and-set! SOLUTIONSlide 33“Correct answers”CS61A Lecture 212011-07-25Colleen Lewis1Clicker poll Are you allowed to talk about the midterm on piazza or in public yet?A)YesB)No2Dining PhilosophersPhilosophers are sitting around a large round table, each with a bowl of Chinese food in front of him/her. Between periods of deep thought they may start eating whenever they want to, with their bowls being filled frequently. But there are only 5 chopsticks available, one to the left of each bowl. When a philosopher wants to start eating, he/she must pick up the chopstick to the left of his bowl and the chopstick to the right of his bowl. 3Dining PhilosophersA) Heard of it before (and know the point)B) Never heard of it before (but get it)C) Never heard of it before (but going to get it)4Problems with Concurrency•Incorrectness•Inefficiency•Deadlock•Unfairness5BELOW the line…(set! x (+ 1 x))•Lookup x•Add 1 to x•Set x6Actually one set! is composed of 3 stepsWhat if these “happened” one after the other(set! x (+ 1 x)) (set! x (+ 1 x))•P1: Lookup x•P1: Add 1 to x•P1: Set x7•P2: Lookup x•P2: Add 1 to x•P2: Set xX: 100If these execute in parallel:Possibility for Incorrect Results! (set! x (+ 1 x)) (set! x (+ 1 x))•P1: Lookup x•P1: Add 1 to x•P1: Set x8•P2: Lookup x•P2: Add 1 to x•P2: Set xX: 100 Within a process they are NEVER re-ordered!Only interleaved with another processHow many possible outcomes?(define x 100)(parallel-execute (lambda() (set! x (+ x 6)))(lambda() (set! x (+ x 5))))A)1 possible outcomeB)2 possible outcomesC)3 possible outcomesD)4 possible outcomesE)5 possible outcomes9Thunk: Lambda of with no argumentsEVERY ordering!•1 1 2 2•1 2 1 2•2 1 1 2•1 2 2 1•2 1 2 1•2 2 1 110P1 then P2P2 then P1P2 clobbers P1P1 clobbers P2If these execute in parallel… Write out the sequence of events(define x 10)(set! x (+ x x)) (set! x (+ 1 x))•P1: Lookup x•P1: Lookup x•P1: Add x to x•P1: Set x11•P2: Lookup x•P2: Add 1 to x•P2: Set xA) 2 possible outcomes for xB) 3 possible outcomes for xC) 4 possible outcomes for xD) 5 possible outcomes for xE) More than 5Critical sectionEVERY ordering!•1 1 1 2 2•1 1 2 1 2•1 2 1 1 2•2 1 1 1 2•1 1 2 2 1•1 2 1 2 1•2 1 1 2 1•1 2 2 1 1•2 1 2 1 1•2 2 1 1 1 12P1 then P2P2 then P1P2 clobbers P1P1 clobbers P2P2 between P1’s lookupsPossible outcomes(set! x (+ x x)) (set! x (+ 1 x))P1 then P2•P1: Lookup x•P1: Lookup x•P1: Set x•P2: Lookup x•P2: Set x13P2 then P1•P2: Lookup x•P2: Set x •P1: Lookup x•P1: Lookup x•P1: Set xP2 between P1’s lookups•P1: Lookup x•P2: Lookup x•P2: Set x •P1: Lookup x•P1: Set xP2 clobbers P1•P1: Lookup x•P1: Lookup x•P2: Lookup x•P1: Set x•P2: Set x P1 clobbers P2•P1: Lookup x•P1: Lookup x•P2: Lookup x•P2: Set x •P1: Set xOur definition of a “correct answer”?(define x 10)(parallel-execute (lambda() (set! x (+ x x)))(lambda() (set! x (+ 1 x))))Correct answers:21 (line 1 first)22 (line 2 first)14“Ensure that a concurrent system produces the same result as if the processes had run sequentially in some order.”Protecting from incorrectness15Serializers protect thingsAnd make things they protect serial(def: taking place in a series)(define stephanie (make-serializer))(define phill (make-serializer))(define hamilton (make-serializer))16Occupied. You’ve got to wait!Serializers protect thingsAnd make things they protect serial(def: taking place in a series)(define stephanie-x (make-serializer))(parallel-execute (stephanie-x (lambda()(set! x (+ x 1))) (stephanie-x (lambda()(set! x (+ x x))) (stephanie-x (lambda()(set! x (+ x 9))))Serializer stephanie-x will make sure nothing she protects happen concurrently. 17“Ensure that a concurrent system produces the same result as if the processes had run sequentially in some order.”Serializers protect thingsAnd make things they protect serial(def: taking place in a series)(define hamilton-x (make-serializer))(define phill-y (make-serializer))(parallel-execute (hamilton-x (lambda()(set! x (+ x 1))) (hamilton-x (lambda()(set! x (+ x x))) (phill-y (lambda()(set! y (+ y 1))) (phill-y (lambda()(set! y (+ y y))) (hamilton-x (lambda()(set! x (+ x 9))))18Serializers protect thingsAnd make things they protect serial(def: taking place in a series)(define x 10)(define stephanie-x (make-serializer))(define hamilton-x (make-serializer))(parallel-execute (stephanie-x (lambda()(set! x (+ x 1))) (hamilton-x (lambda()(set! x (+ x x)))))Will this ensure the answer will be 21 or 22?A. Yes B. No C. Not sure19We’ve seen INCORRECT… now INEFFICIENCY20(define phill-xy (make-serializer))(parallel-execute (phill-xy (lambda()(set! x (+ x 1))) (phill-xy (lambda()(set! x (+ x x))) (phill-xy (lambda()(set! y (+ y 1))) (phill-xy (lambda()(set! y (+ y y))) (phill-xy (lambda()(set! x (+ x 9))))It would be correct to interleave x’s and y’sYou’ve seen INCORRECT and INEFFICIENT… now DEADLOCK(define serial-x (make-serializer))(define serial-y (make-serializer))(parallel-execute (serial-x (lambda()(set! x (+ x 1))) (serial-y (lambda()(set! y (+ y y)(set! y (+ y 1))) (serial-y (serial-x (lambda () (set! y (+ y 1))(set! x (+ x 1))))))21Critical sectionYou’ve seen INCORRECT and INEFFICIENT… now DEADLOCK(define serial-x (make-serializer))(define serial-y (make-serializer))(parallel-execute (serial-y (serial-x (lambda () (set! y (+ y 1))(set! x (+ x 1))))) (serial-x (serial-y (lambda () (set! y (+ y 1))(set! x (+ x 1))))))22Problems with Concurrency•Incorrectness•Inefficiency•Deadlock•Unfairness23Implementing SerializersWith a mutex24Wrinkles and I
View Full Document
Unlocking...