Concurrent ProgrammingReading AssignmentConcurrency The Promise of ConcurrencyExample: Rendering a Web pageThe Challenges of ConcurrencyLanguage Support for ConcurrencyInter-Process CommunicationExplicit vs. Implicit Concurrencycobegin / coendProperties of cobegin/coendRace ConditionsCritical SectionLocks and WaitingDeadlockImplementing Mutual ExclusionSemaphoresSimple Producer-ConsumerProducer-ConsumerMonitorsExample of a MonitorJava Threadsjava.lang.ThreadMethods of Thread ClassRunnable InterfaceTwo Ways to Start a ThreadWhy Two Ways?Interesting “Feature”Interaction Between ThreadsSynchronized MethodsWait, Notify, NotifyAllUsing SynchronizationExample: Shared QueueExample: Producer-ConsumerSlide Number 35Solving Producer-ConsumerImplementation in Stack<T>Condition RechecksNested Monitor Lockout ProblemNested Monitor Lockout ExamplePreventing Nested Monitor DeadlockSynchronized BlocksLocks Are RecursiveSynchronizing with Join() States of a Java ThreadConcurrent Garbage CollectionLimitations of Java 1.4 PrimitivesPOSIX ThreadsExample of Using POSIX ThreadsThread StacksJava-Style Synchronization in C++Using C++ ThreadsThread Safety of ClassesExample: RGBColor ClassProblems with RGBColor ClassMaking Classes Thread-SafeThread-Safe WrapperComparison Why Not Synchronize Everything?Inheritance AnomalyExamples of Inheritance AnomalyExample: Buffer ClassProblems in Derived Class util.concurrentSyncChannelExecutorjava.util.CollectionJava Memory ModelMemory HierarchyProgram and Locking OrderRace Conditions Races in ActionMemory Model QuestionInstruction ReorderingExample Program with Data RaceSequential Reordering + Data RaceAllowed Sequential ReorderingWant To Prevent ThisSummary of Memory ModelExample: Concurrent Hash MapConcurrentHashMapConcurrentHashMap TricksAtomicityLimitations of Race-Freedom (1)Limitations of Race-Freedom (2)AtomicityAtomJavaslide 1Vitaly ShmatikovCS 345Concurrent Programmingslide 2Reading AssignmentMitchell, Chapter 14slide 3Concurrency Multiprogramming• Single processor runs several programs at the same time• Each program proceeds sequentially• Actions of one program may occur between two steps of anotherMultiprocessors• Two or more processors• Programs on one processor communicate with programs on another• Actions may happen simultaneouslyTwo or more sequences of events occur “in parallel”Process: sequential program running on a processorslide 4The Promise of ConcurrencySpeed• If a task takes time t on one processor, shouldn’t it take time t/n on n processors?Availability• If one process is busy, another may be ready to helpDistribution• Processors in different locations can collaborate to solve a problem or work together Humans do it so why can’t computers?• Vision, cognition appear to be highly parallel activitiesslide 5Example: Rendering a Web pagePage is a shared resourceMultiple concurrent activities in the Web browser• Thread for each image load• Thread for text rendering• Thread for user input (e.g., “Stop” button)Cannot all write to page simultaneously!• Big challenge in concurrent programming: managing access to shared resourcesslide 6The Challenges of ConcurrencyConcurrent programs are harder to get right• Folklore: need at least an order of magnitude in speedup for concurrent program to be worth the effort Some problems are inherently sequential• Theory – circuit evaluation is P-complete• Practice – many problems need coordination and communication among sub-problemsSpecific issues• Communication – send or receive information• Synchronization – wait for another process to act• Atomicity – do not stop in the middle and leave a messslide 7Language Support for ConcurrencyThreads• Think of a thread as a system “object” containing the state of execution of a sequence of function calls• Each thread needs a separate run-time stack (why?)• Pass threads as arguments, return as function resultsCommunication abstractions• Synchronous communication• Asynchronous buffers that preserve message orderConcurrency control• Locking and mutual exclusion• Atomicity is more abstract, less commonly providedslide 8Inter-Process CommunicationProcesses may need to communicate• Process requires exclusive access to some resources• Process need to exchange data with another processCan communicate via:• Shared variables• Message passing• Parametersslide 9Explicit vs. Implicit ConcurrencyExplicit concurrency• Fork or create threads / processes explicitly• Explicit communication between processes– Producer computes useful value– Consumer requests or waits for producerImplicit concurrency• Rely on compiler to identify potential parallelism• Instruction-level and loop-level parallelism can be inferred, but inferring subroutine-level parallelism has had less successslide 10cobegin / coendLimited concurrency primitive– Concurrent Pascal [Per Brinch Hansen, 1970s]x := 0;cobeginbegin x := 1; x := x+1 end;begin x := 2; x := x+1 end;coend;print(x);execute sequentialblocks in parallelx := 0x := 2x := 1print(x)x := x+1x := x+1Atomicity at level of assignment statementslide 11Properties of cobegin/coendSimple way to create concurrent processesCommunication by shared variablesNo mutual exclusionNo atomicityNumber of processes fixed by program structureCannot abort processes• All must complete before parent process can go onslide 12Race ConditionsRace condition occurs when the value of a variable depends on the execution order of two or more concurrent processes (why is this bad?)Exampleprocedure signup(person)beginnumber := number + 1;list[number] := person;end;signup(joe) || signup(bill)slide 13Critical SectionTwo concurrent processes may access a shared resourceInconsistent behavior if processes are interleavedAllow only one process in critical sectionIssues• How to select which process is allowed to access the critical section?• What happens to the other process?slide 14Locks and Waiting<initialize concurrency control>Process 1: <wait> signup(joe); // critical section<signal>Process 2:<wait>signup(bill); // critical section<signal>Need atomic operations to implement waitslide 15DeadlockDeadlock occurs when a process is waiting for an event that will never happenNecessary conditions for a deadlock to exist:• Processes claim exclusive access to resources• Processes