Chapter 13Chapter 13 TopicsIntroductionMultiprocessor ArchitecturesCategories of ConcurrencyMotivations for the Use of ConcurrencyIntroduction to Subprogram-Level ConcurrencyTwo General Categories of TasksTask SynchronizationKinds of synchronizationNeed for Competition SynchronizationSchedulerTask Execution StatesLiveness and DeadlockDesign Issues for ConcurrencyMethods of Providing SynchronizationSemaphoresCooperation Synchronization with SemaphoresCooperation Synchronization with Semaphores (continued)Slide 20Semaphores: Wait and Release OperationsProducer and Consumer TasksCompetition Synchronization with SemaphoresProducer Code for SemaphoresConsumer Code for SemaphoresEvaluation of SemaphoresMonitorsCompetition SynchronizationCooperation SynchronizationEvaluation of MonitorsMessage PassingMessage Passing RendezvousC/C++ process & threadJava ThreadsControlling Thread ExecutionThread PrioritiesCompetition Synchronization with Java ThreadsCooperation Synchronization with Java ThreadsJava’s Thread EvaluationC# ThreadsSynchronizing ThreadsC#’s Concurrency EvaluationStatement-Level ConcurrencyHigh-Performance Fortran (HPF)SummaryChapter 13ConcurrencyCopyright © 2012 Addison-Wesley. All rights reserved. 1-2Chapter 13 Topics•Introduction•Introduction to Subprogram-Level Concurrency•Semaphores•Monitors•Message Passing•C/C++ Support for Concurrency (process & thread)•Java Threads•C# Threads•Concurrency in Functional Languages•Statement-Level ConcurrencyCopyright © 2012 Addison-Wesley. All rights reserved. 1-3Introduction•Concurrency can occur at four levels:–Machine instruction level–High-level language statement level–Unit level–Program level•Because there are no language issues in instruction-level and program-level concurrency, they are not addressed hereCopyright © 2012 Addison-Wesley. All rights reserved. 1-4Multiprocessor Architectures•Late 1950s - one general-purpose processor and one or more special-purpose processors for input and output operations•Early 1960s - multiple complete processors, used for program-level concurrency•Mid-1960s - multiple partial processors, used for instruction-level concurrency•Single-Instruction Multiple-Data (SIMD) machines•Multiple-Instruction Multiple-Data (MIMD) machines •A primary focus of this chapter is shared memory MIMD machines (multiprocessors)Copyright © 2012 Addison-Wesley. All rights reserved. 1-5Categories of Concurrency•Categories of Concurrency:–Physical concurrency - Multiple independent processors ( multiple threads of control)–Logical concurrency - The appearance of physical concurrency is presented by time-sharing one processor (software can be designed as if there were multiple threads of control) •Coroutines (quasi-concurrency) have a single thread of control•A thread of control in a program is the sequence of program points reached as control flows through the programCopyright © 2012 Addison-Wesley. All rights reserved. 1-6Motivations for the Use of Concurrency•Multiprocessor computers capable of physical concurrency are now widely used•Even if a machine has just one processor, a program written to use concurrent execution can be faster than the same program written for nonconcurrent execution•Involves a different way of designing software that can be very useful—many real-world situations involve concurrency•Many program applications are now spread over multiple machines, either locally or over a networkCopyright © 2012 Addison-Wesley. All rights reserved. 1-7Introduction to Subprogram-Level Concurrency•A task or process or thread is a program unit that can be in concurrent execution with other program units•Tasks differ from ordinary subprograms in that:–A task may be implicitly started–When a program unit starts the execution of a task, it is not necessarily suspended–When a task’s execution is completed, control may not return to the caller•Tasks usually work togetherCopyright © 2012 Addison-Wesley. All rights reserved. 1-8Two General Categories of Tasks•Heavyweight tasks execute in their own address space •Lightweight tasks all run in the same address space – more efficient•A task is disjoint if it does not communicate with or affect the execution of any other task in the program in any wayCopyright © 2012 Addison-Wesley. All rights reserved. 1-9Task Synchronization•A mechanism that controls the order in which tasks execute•Two kinds of synchronization–Cooperation synchronization–Competition synchronization•Task communication is necessary for synchronization, provided by:- Shared nonlocal variables- Parameters- Message passingCopyright © 2012 Addison-Wesley. All rights reserved. 1-10Kinds of synchronization•Cooperation: Task A must wait for task B to complete some specific activity before task A can continue its execution, e.g., the producer-consumer problem•Competition: Two or more tasks must use some resource that cannot be simultaneously used, e.g., a shared counter–Competition is usually provided by mutually exclusive access (approaches are discussed later)Copyright © 2012 Addison-Wesley. All rights reserved. 1-11Need for Competition SynchronizationTask A: TOTAL = TOTAL + 1Task B: TOTAL = 2 * TOTAL- Depending on order, there could be four different resultsCopyright © 2012 Addison-Wesley. All rights reserved. 1-12Scheduler•Providing synchronization requires a mechanism for delaying task execution•Task execution control is maintained by a program called the scheduler, which maps task execution onto available processorsCopyright © 2012 Addison-Wesley. All rights reserved. 1-13Task Execution States•New - created but not yet started•Ready - ready to run but not currently running (no available processor)•Running •Blocked - has been running, but cannot now continue (usually waiting for some event to occur)•Dead - no longer active in any senseCopyright © 2012 Addison-Wesley. All rights reserved. 1-14Liveness and Deadlock•Liveness is a characteristic that a program unit may or may not have- In sequential code, it means the unit will eventually complete its execution•In a concurrent environment, a task can easily lose its liveness•If all tasks in a concurrent environment lose their liveness, it is called deadlockCopyright © 2012 Addison-Wesley. All rights reserved. 1-15Design Issues for Concurrency•Competition and cooperation synchronization*•Controlling task scheduling•How can