Principles of Concurrent and Distributed Programmi

PrinciplesofConcurrentandDistributedProgramming(SecondEdition)Addison-Wesley,2006Mordechai(Moti)Ben-Ari–1.2-time(nanoseconds)→0100200300400500HumanTimePrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–1.3-time(seconds)→0100200300400500ConcurrencyinanOperatingSystemPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–1.4time→ComputationI/OstartI/OendI/O66InterleavingasChoosingAmongProcessesPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.1p3,...cpp6q2,...cpq6r2,...cpr6p1,r1,p2,q1 @@@IPossibleInterleavingsPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.2p1→q1→p2→q2,p1→q1→q2→p2,p1→p2→q1→q2,q1→p1→q2→p2,q1→p1→p2→q2,q1→q2→p1→p2.PrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.3Algorithm2.1:Trivialconcurrentprogramintegern←0pqintegerk1←1integerk2←2p1:n←k1q1:n←k2PrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.4Algorithm2.2:Trivialsequentialprogramintegern←0integerk1←1integerk2←2p1:n←k1p2:n←k2StateDiagramforaSequentialProgramPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.5-sp1:n←k1k1=1,k2=2n=0'&$%p2:n←k2k1=1,k2=2n=1'&$%(end)k1=1,k2=2n=2'&$%--StateDiagramforaConcurrentProgramPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.6?rp1:n←k1q1:n←k2k1=1,k2=2n=0'&$%(end)q1:n←k2k1=1,k2=2n=1'&$%(end)(end)k1=1,k2=2n=2'&$%p1:n←k1(end)k1=1,k2=2n=2'&$%(end)(end)k1=1,k2=2n=1'&$% ?@@@@R?ScenarioforaConcurrentProgramPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.7ProcesspProcessqnk1k2p1:n←k1q1:n←k2012(end)q1:n←k2112(end)(end)212MultitaskingSystemPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.8*CPURegXXXXXXXXXXXXXXzRegRegRegRegRegOperatingSystemProgram1Program2Program3Program4MultiprocessorComputerPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.9LocalMemoryCPULocalMemoryCPULocalMemoryCPUGlobalMemoryInconsistencyCausedbyOverlappedExecutionPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.10LocalmemoryLocalmemory000000000000000100000000000000100000000000000011Globalmemory*HHHYDistributedSystemsArchitecturePrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.11NodeNodeNodeNode-6??-6 @@@@@R@@@@@INodeNodeNodeNode-6?PrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.12Algorithm2.3:Atomicassignmentstatementsintegern←0pqp1:n←n+1q1:n←n+1ScenarioforAtomicAssignmentStatementsPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.13ProcesspProcessqnp1:n←n+1q1:n←n+10(end)q1:n←n+11(end)(end)2ProcesspProcessqnp1:n←n+1q1:n←n+10p1:n←n+1(end)1(end)(end)2PrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.14Algorithm2.4:Assignmentstatementswithoneglobalreferenceintegern←0pqintegertempintegertempp1:temp←nq1:temp←np2:n←temp+1q2:n←temp+1CorrectScenarioforAssignmentStatementsPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.15ProcesspProcessqnp.tempq.tempp1:temp←nq1:temp←n0??p2:n←temp+1q1:temp←n00?(end)q1:temp←n10?(end)q2:n←temp+1101(end)(end)201IncorrectScenarioforAssignmentStatementsPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.16ProcesspProcessqnp.tempq.tempp1:temp←nq1:temp←n0??p2:n←temp+1q1:temp←n00?p2:n←temp+1q2:n←temp+1000(end)q2:n←temp+1100(end)(end)100PrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.17Algorithm2.5:StoptheloopAintegern←0booleanflag←falsepqp1:whileflag=falseq1:flag←truep2:n←1−nq2:PrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.18Algorithm2.6:Assignmentstatementforaregistermachineintegern←0pqp1:loadR1,nq1:loadR1,np2:addR1,#1q2:addR1,#1p3:storeR1,nq3:storeR1,nRegisterMachinePrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.19RegistersMemory······RegistersMemory······RegistersMemory······001011?6LoadStoreScenarioforaRegisterMachinePrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.20ProcesspProcessqnp.R1q.R1p1:loadR1,nq1:loadR1,n0??p2:addR1,#1q1:loadR1,n00?p2:addR1,#1q2:addR1,#1000p3:storeR1,nq2:addR1,#1010p3:storeR1,nq3:storeR1,n011(end)q3:storeR1,n111(end)(end)111PrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.21Algorithm2.7:Assignmentstatementforastackmachineintegern←0pqp1:pushnq1:pushnp2:push#1q2:push#1p3:addq3:addp4:popnq4:popnStackMachinePrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.22StackMemory······StackMemory······StackMemory·········01AAU0···10···1AAK1PushPopPrinciplesofConcurrentandDistributedProgramming.Slidesc2006byM.Ben-Ari.Slide–2.23Algorithm2.8:Volatilevariablesintegern←