Programming Languages: Design, Specification, and ImplementationReadings (week 1)Readings (week 2)Programming Project on Concurrency – due Nov. 30Programming Languages Core ExamWhy ConcurrencyWhat’s hardShared VariablesTracesSurprise: Multiple atomic registers don’t imply causal consistency!!!!Lamport’s “happens before”Critical SectionsLocks, Semaphores, P/VAda Tasks, RendezvousGuardsAda: Producer and ConsumerProtected Objects in AdaMonitors – Synchronized MethodsWait and NotifyProducer/consumer in JavaProgramming Languages:Design, Specification, and ImplementationG22.2210-001Rob StromNovember 16, 2006Readings (week 1)Theoretical and Historical Papers on Concurrency•The “Readers/Writers” Problemhttp://www.md.chalmers.se/~ptrianta/SynC+Co/LIT/lamp77.pdf.gz•Shared Registers (Part II)http://users.ece.gatech.edu/~dblough/6102/lamport_consistency.pdf•Wait-free synchronizationhttp://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf•Partially-ordered time.http://research.microsoft.com/users/lamport/pubs/time-clocks.pdfConcurrency models in object-oriented languages•Ada Reference Manual Section 9•Java Reference Manual Chapter 17•Thinking in C++, chapter 11•http://web.mit.edu/merolish/ticpp/TicV2.html#_Toc53985862Readings (week 2)Problems with the Memory Model•Java Memory model is Brokenhttp://www.cs.umd.edu/~pugh/java/broken.pdfThread-Safe Programming•Compiler-Enforced Thread-Safety (Guava): http://researchweb.watson.ibm.com/people/d/dfb/papers/Bacon00Guava.ps •Safe Reader-Writer Parallelism (Optimistic Readers): http://www.research.ibm.com/distributedmessaging/paper13.htmlProgramming Project on Concurrency – due Nov. 30Extend the room world of the previous assignment so that multiple people can enter rooms and do things•Each thing someone does is an atomic unit of work, e.g.•Get things from factories and put them in the room•Pick up a bunch of objects and put them in a container•Pick up 2 containers and a funnel and transfer liquid from one container to the other•Don’t deadlock•Anticipate contention – e.g. you’ve picked up object A and try to pick up object B, but discover it’s gone because someone else picked up object B. You may need to give up your scripted action.•The implementation should have the same realism properties as the non-concurrent implementation did: e.g. things shouldn’t spontaneously disappear or appear in multiple places.You may use any one of C++, Java, or Ada (probably the same language you used for previous assignment, but this is not required)Programming Languages Core ExamSyntactic issues: regular expressions, context-free grammars (CFG), BNF. Imperative languages: program organization, control structures, exceptionsTypes in imperative languages: strong typing, type equivalence, unions and discriminated types in C and Ada. Block structure, visibility and scoping issues, parameter passing. Systems programming and weak typing: exposing machine characteristics, type coercion, pointers & arrays in C. Run-time organization of block-structured languages: static scoping, activation records, dynamic and static chains, displays. Programming in the large: abstract data types, modules, packages and namespaces in Ada, Java, and C++. Functional programming: list structures, higher order functions, lambda expressions, garbage collection, metainterpreters in Lisp and Scheme. Type inference and ML. Object-Oriented programming: classes, inheritance, polymorphism, dynamic dispatching. Constructors, destructors and multiple inheritance in C++, interfaces in Java. Generic programming: parametrized units and classes in C++, Ada and Java. Concurrent programming: threads and tasks, communication, race conditions and deadlocks, protected methods and types in Ada and Java.Why ConcurrencyImproving the performance of an algorithm that could have been written without concurrencyThe problem is intrinsically distributed, with actors initiating different things in different locations.It’s easier to decompose some problems into separate tasks even though they might be scheduled sequentially – e.g. a pipelined process.What’s hardInterference between reads and writesInvariants break, e.g.•program 1•y gets 2y - x + 1•x gets x + 1•program 2 •x gets x + 1•y gets y + 1•If x=y=0, preserves invariant x=y if executed serially, but not when executed concurrentlyShared VariablesSome shared registers, from weakest to strongest (assumes global time):•Safe: reads overlapping writes may see any value; reads not overlapping writes must see the correct value.•Regular: reads overlapping writes will see either an old value or a new value•Atomic: reads and writes behave as if totally orderedTracesSafe: could return (5, 99, 86)Regular: could return (5, 6, 5)Atomic: only (5, 5, 5), (5, 5, 6), or (5, 6, 6)•It’s been proven that you can implement an n-bit atomic register out of safe registers. •But you need LOTS more than n-bits, the algorithm is complicated and the proof is HARD Surprise: Multiple atomic registers don’t imply causal consistency!!!!Process 1 reads R2, then R1, and sees 6, 5Process 2 reads R1, sees 6. Now it reads R2. Must it see 6?NO! R1 could see P1’s 2nd read, then P2’s 1st read. And R2 could see P2’s 2nd read, then P1’s 1st read. They only promised to put the reads in some total order, not necessarily a causally consistent one!R1 R2Lamport’s “happens before”Critical in discussing distributed and concurrent systemsA partial order relation on eventsA memory system is causally consistent if there is a “happens before” relationship such that if a write happens before a read, the reader must see the new value, and if a read happens before a write, the reader must see the old value.Critical SectionsLots of people are preparing and eating pancakes, but there’s only one bowl/pan:•Think•Pour milk into bowl•Add eggs into bowl•Add flour into bowl•Pour mix from bowl to pan; cook; empty pan•Eat pancakesMake it easy to do critical sectionsCritical section:Invariant: Bowl and pan freeon entry and exit;may not be freein the middleLocks, Semaphores, P/VThe following won’t work:if (criticalSectionFree) { criticalSectionFree = false; /* do critical section */ criticalSectionFree = true;}The following might work (but not guaranteed fair):while (testAndSet(lockbit)