Programming Languages Design Specification and Implementation G22 2210 001 Rob Strom November 30 2006 Readings week 1 Theoretical and Historical Papers on Concurrency The Readers Writers Problem http 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 synchronization http 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 Toc53985862 Readings week 2 Problems with the Memory Model Java Memory model is Broken http 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 html Programming 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 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 nonconcurrent implementation did e g things shouldn t spontaneously disappear or appear in multiple places 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 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 Ada protected type Signal Object is entry Wait procedure Signal function Is Open return Boolean private Open Boolean False 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 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 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 Java public class ProducerConsumer int Q queue of integers int in 0 next free index in queue int out 0 first used index if count 0 int count 0 number of items on queue Invariant in out mod Q length count ProducerConsumer 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 wait int r Q out out out 1 Q length if count Q length notifyAll return r Memory Model in Java Defines what happens when multiple threads access the same values without synchronizing How can this happen Through static variables Static variables are considered harmful but not forbidden Through object references that are shared but not synchronized The results are counter intuitive and attempts have been made to fix the model Too weak a model breaks many programming idioms Too strong a model inhibits many optimizations The first sign of trouble prescient stores Assume thread 1 calls m1 thread 2 calls m2 What traces are possible a 0 b 0 a 0 b 2 a 2 b 0 a 2 b 2 If allowed breaks many assumptions If disallowed prevents many compiler optimizations and still may fail on some architectures unless barrier synchronizations are used More bad news for optimizers Reads kill Suppose p x 2 A second thread updates q x to 3 q is an alias of p Can I see i 2 j 3 k 2 If yes this violates the original JMM and breaks some programming idioms If no this inhibits the ability to save values in registers Worse news Suppose P2 saw