Multithreaded and Distributed Programming -- Classes of ProblemsThe Essence of Multiple Threads -- reviewOpportunities & ChallengesFocus in this courseMultiprocessing monkey wrenchRecall from multiprogram systemsWhy write as multithreaded?Many applications, 5 basic paradigmsIterative parallelismRecursive parallelismProducers and consumersClients & ServersDistributed “procedures” and “calls”Common exampleClient/Server exampleReaders/Writers -- many facetsConsider a query on the WWWClients/Servers -- on same or separateCommunication in client/server appInteracting peersAmong the 5 paradigms are certain characteristics common to distributed environments. Distributed memory Properties of parallel applications Concurrent computationDistributed memory implicationsExample of a parallel applicationProperties of parallel applicationsConcurrent computationDifferences: sequential vs. concurrentPowerPoint PresentationSlide 28Slide 29Slide 30Role of coordinatorSlide 32Message passing primitivesPeer approachSlide 35Worker algorithmWorker algorithm (cont.)Worker algorithm (cont. 2)ComparisonsSummaryShared-memory programmingShared-Variable ProgrammingNeed to communicateSome termsTerms -- continuedTerms – continued furtherHow can we verify?Assertional ReasoningWarningWhy synchronize?Slide 51Slide 52How to implement synchronizationDesirable Traits and Bad StatesDesirable Traits and Bad states (cont.)Logical property of mutual exclusionCoarse-grain solutionDoes it avoid the problems?Liveness guaranteed?Three “spin lock” solutionsDistributed-memory programmingDistributed-memory architectureNecessary first steps to write programs for a dist.-memory arch.Slide 64CharacteristicsImplications of no shared variablesPatterns of process interactionHow relatedMatch Examples with Paradigms and Process Interaction categoriesMultithreaded and Distributed Programming -- Classes of ProblemsECEN5053 Software Engineering of Distributed SystemsUniversity of ColoradoFoundations of Multithreaded, Parallel, and Distributed Programming, Gregory R. Andrews, Addison-Wesley, 2000revised 9/8/2002 ECEN5053 SW Eng of Distributed Systems, University of Colorado2The Essence of Multiple Threads -- reviewTwo or more processes that work together to perform a taskEach process is a sequential programOne thread of control per processCommunicate using shared variables Need to synchronize with each other, 1 of 2 waysMutual exclusionCondition synchronizationrevised 9/8/2002 ECEN5053 SW Eng of Distributed Systems, University of Colorado3Opportunities & ChallengesWhat kinds of processes to useHow many parts or copiesHow they should interactKey to developing a correct program is to ensure the process interaction is properly synchronizedrevised 9/8/2002 ECEN5053 SW Eng of Distributed Systems, University of Colorado4Focus in this courseImperative programsProgrammer has to specify the actions of each process and how they communicate and synchronize. (Java, Ada)Declarative programs (not our focus)Written in languages designed for the purpose of making synchronization and/or concurrency implicitRequire machine to support the languages, for example, “massively parallel machines.”Asynchronous process executionShared memory, distributed memory, networks of workstations (message-passing)revised 9/8/2002 ECEN5053 SW Eng of Distributed Systems, University of Colorado5Multiprocessing monkey wrenchThe solutions we addressed last semester presumed a single CPU and therefore the concurrent processes share coherent memoryA multiprocessor environment with shared memory introduces cache and memory consistency problems and overhead to manage it.A distributed-memory multiprocessor/multicomputer/network environment has additional issues of latency, bandwidth, administration, security, etc.revised 9/8/2002 ECEN5053 SW Eng of Distributed Systems, University of Colorado6Recall from multiprogram systemsA process is a sequential program that has its own thread of control when executedA concurrent program contains multiple processes so every concurrent program has multiple threads, one for each process.Multithreaded usually means a program contains more processes than there are processors to execute themA multithreaded software system manages multiple independent activitiesrevised 9/8/2002 ECEN5053 SW Eng of Distributed Systems, University of Colorado7Why write as multithreaded?To be cool  (wrong reason)Sometimes, it is easier to organize the code and data as a collection of processes than as a single huge sequential programEach process can be scheduled and executed independentlyOther applications can continue to execute “in the background”revised 9/8/2002 ECEN5053 SW Eng of Distributed Systems, University of Colorado8Many applications, 5 basic paradigmsIterative parallelismRecursive parallelismProducers and consumers (pipelines)Clients and serversInteracting peersEach of these can be accomplished in a distributed environment. Some can be used in a single CPU environment.revised 9/8/2002 ECEN5053 SW Eng of Distributed Systems, University of Colorado9Iterative parallelismExample?Several, often identical processesEach contains one or more loopsTherefore each process is iterativeThey work together to solve a single programCommunicate and synchronize using shared variablesIndependent computations – disjoint write setsrevised 9/8/2002 ECEN5053 SW Eng of Distributed Systems, University of Colorado10Recursive parallelismOne or more independent recursive proceduresRecursion is the dual of iterationProcedure calls are independent – each works on different parts of the shared dataOften used in imperative languages for Divide and conquer algorithmsBacktracking algorithms (e.g. tree-traversal)Used to solve combinatorial problems such as sorting, scheduling, and game playingIf too many recursive procedures, we prune.revised 9/8/2002 ECEN5053 SW Eng of Distributed Systems, University of Colorado11Producers and consumersOne-way communication between processesOften organized into a pipeline through which info flowsEach process is a filter that consumes the output of its predecessor and produces output for its successorThat is, a producer-process computes and outputs a stream of resultsSometimes implemented with a shared bounded buffer as the pipe, e.g. Unix stdin and