Programming Languages: Design, Specification, and ImplementationReadings (week 1)Readings (week 2)Programming Project on Concurrency – due Nov. 30Programming Languages Core ExamMonitors – Synchronized MethodsProtected Objects in AdaWait and NotifyProducer/consumer in JavaMemory Model in JavaThe first sign of trouble: “prescient” storesMore bad news for optimizers: “Reads kill”Worse newsWhat is Guava?Component ModelJava and Guava typesGuava changes: summaryMonitors, Values, ObjectsRegion Analysis: lent, keptRegion Analysis: new, in RUpdate and GlobalProgramming Languages:Design, Specification, and ImplementationG22.2210-001Rob StromNovember 30, 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.Monitors – Synchronized MethodsThreads are active•Started by calling start() method on a subclass of ThreadObjects are always passiveA synchronized method has these properties:•Critical section: locked before, unlocked after•Lock guaranteed to be released on termination•Causality respected: every action in method follows the locking; every action after completion of method follows the unlocking.Protected Objects in Adaprotected type Signal_Object is entry Wait; procedure Signal; function Is_Open return Boolean; private Open : Boolean := False; end Signal_Object; protected body Signal_Object is entry Wait when Open is begin Open := False; end Wait; procedure Signal is begin Open := True; end Signal; function Is_Open return Boolean is begin return Open; end Is_Open; end Signal_Object;•Behaves like a task that repeatedly loops and accepts entries. But can be implemented without multiple threads.•But multiple reads (functions) may execute concurrently•Only one write (procedure or entry call) may be active at once. •But entry calls may queue up if their guard is false•Queued entry calls will run when their guard becomes true. •They take priority over any calls that enter later.Wait and NotifyA caller invokes a synchronized method: but discovers some essential condition is false.It issues wait() on the object (You must hold the lock to do this)This releases the lock and lets other callers call other methodsWhen the condition is made true, notifyAll() is called on the object (or notify() if you want Java to pick a waiter)That terminates the wait(), and lets all waiters (or the selected waiter) try to compete for the lock again.Other callers may have made the condition false again, so it is important to check the condition once again!Not guaranteed to be fair (same waiter can lose the battle to get the lock each time)Producer/consumer in Javapublic class ProducerConsumer {int[] Q; // queue of integersint in = 0; // next free index in queueint out = 0; // first used index if count > 0int count = 0; // number of items on queue. // Invariant: in-out (mod Q.length) = countProducerConsumer(int size) {Q = new int[size];}synchronized public void enq (int qe) throws InterruptedException{while (count >= Q.length) {wait();}Q[in] = qe;in = (in+1)%Q.length;if (count++ == 0) notifyAll(); }synchronized public int deq() throws InterruptedException {while (count == 0)