Programming Languages Design Specification and Implementation G22 2210 001 Rob Strom November 16 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 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 program 2 If x y 0 preserves invariant x y if executed serially but not when executed concurrently y gets 2y x 1 x gets x 1 x gets x 1 y gets y 1 Shared 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 ordered Traces 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 R1 R2 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 Lamport 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 Critical section Pour milk into bowl Invariant Bowl and pan free Add eggs into bowl on entry and exit may not be free Add flour into bowl in the middle Pour mix from bowl to pan cook empty pan Eat pancakes Make it easy to do critical sections Locks Semaphores P V The following won t work if criticalSectionFree criticalSectionFree false do critical section criticalSectionFree true testAndSet lock Set the value of the lock bit to 1 Return the value the lock bit previously had No other processor can change the lock bit between the test and the set The following might work but not guaranteed fair while testAndSet lockbit 1 do critical section lockbit 0 Herlihy proved that testAndSet cannot be implemented from atomic registers The abstraction of the combination of locking and waiting is called a semaphore The simplest was defined by Dijkstra P if semaphore 0 decrement it else wait until 0 P proberen test V increment semaphore V verhogen increment You only access shared resources in a critical section between P and V If for any reason you leave the critical section abnormally including a crash you must issue V These are higher level than assembler but still dangerous You need to guarantee that Brinch Hansen http brinch hansen net papers 1993a pdf suggested putting the safe capabilities into a programming language Let s look at two ways Ada Java Ada Tasks Rendezvous task type Simple Task is