并行程序设计 中文课件 12 并行计算系统一致性

ParallelProgrammingInstructor:ZhangWeizhe(张伟哲)ComputerNetworkandInformationSecurityTechniqueResearchCenter,SchoolofComputerScienceandTechnology,HarbinInstituteofTechnologyConsistency3Data-CentricConsistencyModelsI.e.,trytokeepdataconsistentacrossreplicasClient-CentricConsistencyModelsWeakerconditionOnlymaintainconsistencyforeachclientseparatelyOutline4以数据为中心的一致性模型即，尝试使数据在复制品上保持一致以客户为中心的一致性模型条件较弱只保持每个客户端的一致性Outline5Data-CentricConsistencyModelsConsistencymodel(akaconsistencysemanticsorconstraints)ContractbetweenprocessesandthedatastoreIfprocessesobeycertainrules,datastorewillworkcorrectlyAllmodelsattempttoreturntheresultsofthelastwriteforareadoperationDifferinhow“last”writeisdetermined/defined6以数据为中心的一致性模型一致性模型（一致性语义或约束）流程和数据存储之间的契约如果流程遵守某些规则，数据存储将正常工作所有模型都尝试返回最后写入的结果，以进行读取操作不同之处是“最后”写入如何确定/定义的7StrictConsistencyAnyreadalwaysreturnstheresultofthemostrecentwriteImplicitlyassumesthepresenceofaglobalclockAwriteisimmediatelyvisibletoallprocessesDifficulttoachieveinrealsystemsasnetworkdelayscanbevariable(a)Astrictlyconsistentstore.(b)Astorethatisnotstrictlyconsistent.8严格一致任何读取总是返回最近写入的结果隐含地假定存在全局时钟所有进程都可以立即看到写入在实际系统中难以实现，因为网络延迟是可变的(a)Astrictlyconsistentstore.(b)Astorethatisnotstrictlyconsistent.9SequentialConsistency(1)Adatastoreissequentiallyconsistentwhen:Theresultofanyexecutionisthesameasifthe(readandwrite)operationsbyallprocessesonthedatastore…wereexecutedinsomesequentialorderand…theoperationsofeachindividualprocessappear…inthissequenceintheorderspecifiedbyitsprogram.10顺序一致性(1)数据存储是顺序一致的：

任何执行的结果与数据存储上的所有进程的（读取和写入）操作相同...被执行了一些顺序...每个进程的操作出现...以这个顺序按其程序指定的顺序。11SequentialConsistency(2)Sequentialconsistency:weakerthanstrictconsistencyAssumesalloperationsareexecutedinsomesequentialorderandeachprocessissuesoperationsinprogramorderAnyvalidinterleavingisallowed AllagreeonthesameinterleavingEachprocesspreservesitsprogramorderNothingissaidabout“mostrecentwrite”12顺序一致性(2)顺序一致性：弱于严格的一致性假设所有操作都按照一定顺序执行，每个进程按程序顺序发出操作允许任何有效的交织所有人都同意相同的交错每个进程保留其程序顺序没有关于“最近写的”13SequentialConsistency(3)(a)Asequentiallyconsistentdatastore.

(b)Adatastorethatisnotsequentiallyconsistent.14顺序一致性(3)（a）顺序一致的数据存储。（b）不是顺序一致的数据存储。15CasualConsistency(1)Necessarycondition:

Writesthatarepotentiallycasuallyrelatedmustbeseenbyallprocessesinthesameorder.Concurrentwritesmaybeseeninadifferentorderondifferentmachines.Causallyrelatedwritesmustbeseenbyallprocessesinthesameorder.Concurrentwritesmaybeseenindifferentordersondifferentmachines16结果一致性(1)必要条件：

可能的相关随机写入必须以相同的顺序被所有进程看到。并行写入可以在不同的机器上以不同的顺序看到。所有进程必须以相同的顺序看到结果相关的写入。并行写入可以在不同的机器上以不同的顺序看到17CasualConsistency(2)Thissequenceisallowedwithacasually-consistentstore,butnotwithsequentiallyorstrictlyconsistentstore.18结果一致性(2)这个序列允许随机一致的存储，但不是按顺序或严格一致的存储。19CasualConsistency(3)Aviolationofacasually-consistentstore.Acorrectsequenceofeventsinacasually-consistentstore.20结果一致性(3)一个违反结果一致的存储一个符合结果一致的正确存储序列21FIFOConsistency(1)NecessaryCondition:

Writesdonebyasingleprocessareseenbyallotherprocessesintheorderinwhichtheywereissued,butwritesfromdifferentprocessesmaybeseeninadifferentorderbydifferentprocesses.22FIFOConsistency(1)必要条件：所有其他进程按单个进程执行的写入按照发布顺序可以看到，但不同进程的写入可能按不同的进程以不同的顺序显示。23FIFOConsistency(2)AvalidsequenceofeventsofFIFOconsistency24FIFOConsistency(2)AvalidsequenceofeventsofFIFOconsistency25WeakConsistency(1)Properties:AccessestosynchronizationvariablesassociatedwithadatastorearesequentiallyconsistentNooperationonasynchronizationvariableisallowedtobeperformeduntilallpreviouswriteshavebeencompletedeverywhereNoreadorwriteoperationondataitemsareallowedtobeperformeduntilallpreviousoperationstosynchronizationvariableshavebeenperformed.26弱一致性(1)属性：访问与数据存储相关联的同步变量是顺序一致的允许执行同步变量的操作，直到所有以前的写入都到处都完成在执行对同步变量的所有先前操作之前，都不允许执行对数据项的读取或写入操作。27WeakConsistency(2)Avalidsequenceofeventsforweakconsistency.Aninvalidsequenceforweakconsistency.28ReleaseConsistency(1)Avalideventsequenceforreleaseconsistency.29ReleaseConsistency(2)Rules:Beforeareadorwriteoperationonshareddataisperformed,allpreviousacquiresdonebytheprocessmusthavecompletedsuccessfully.Beforeareleaseisallowedtobeperformed,allpreviousreadsandwritesbytheprocessmusthavecompletedAccessestosynchronizationvariablesareFIFOconsistent(sequentialconsistencyisnotrequired).30ReleaseConsistency(2)规则：在执行对共享数据的读或写操作之前，进程完成的所有以前的获取必须已经成功完成。在允许执行释放之前，进程的所有以前的读取和写入都必须已经完成访问同步变量是FIFO一致的（不需要顺序一致性）。31EntryConsistency(1)Conditions:Anacquireaccessofasynchronizationvariableisnotallowedtoperformwithrespecttoaprocessuntilallupdatestotheguardedshareddatahavebeenperformedwithrespecttothatprocess.Beforeanexclusivemodeaccesstoasynchronizationvariablebyaprocessisallowedtoperformwithrespecttothatprocess,nootherprocessmayholdthesynchronizationvariable,noteveninnonexclusivemode.Afteranexclusivemodeaccesstoasynchronizationvariablehasbeenperformed,anyotherprocess'snextnonexclusivemodeaccesstothatsynchronizationvariablemaynotbeperformeduntilithasperformedwithrespecttothatvariable'sowner.32准入一致性(1)条件：不允许同步变量的获取访问相对于进程执行，直到对该进程已经执行了对被保护的共享数据的所有更新。在允许进程对异步模式访问同步变量进行相对于该进程的执行之前，没有其他进程可能保持同步变量，甚至不是非排他性的模式。在执行对同步变量的独占模式访问之后，任何其他进程的下一个非排他性模式对该同步变量的访问可能不会执行，直到相对于该变量的所有者执行。33EntryConsistency(2)Avalideventsequenceforentryconsistency.34EntryConsistency(2)Avalideventsequenceforentryconsistency.35SummaryofConsistencyModelsConsistencyDescriptionStrictAbsolutetimeorderingofallsharedaccessesmatters.LinearizabilityAllprocessesmustseeallsharedaccessesinthesameorder.Accessesarefurthermoreorderedaccordingtoa(nonunique)globaltimestampSequentialAllprocessesseeallsharedaccessesinthesameorder.AccessesarenotorderedintimeCausalAllprocessesseecausally-relatedsharedaccessesinthesameorder.FIFOAllprocessesseewritesfromeachotherintheordertheywereused.Writesfromdifferentprocessesmaynotalwaysbeseeninthatorder(a)ConsistencymodelsnotusingsynchronizationoperationsConsistencyDescriptionWeakShareddatacanbecountedontobeconsistentonlyafterasynchronizationisdoneReleaseShareddataaremadeconsistentwhenacriticalregionisexitedEntryShareddatapertainingtoacriticalregionaremadeconsistentwhenacriticalregionisentered.(b)Modelswithsynchronizationoperations.36SummaryofConsistencyModelsConsistencyDescriptionStrict共享事务按绝对时间组织Linearizability所有进程必须以相同的顺序查看所有共享访问。还可以根据（非唯一）全局时间戳对访问进行排序Sequential所有进程以相同的顺序查看所有共享访问。访问不记录Causal所有进程都以相同的顺序查看结果相关的共享访问。FIFO所有进程按照它们使用的顺序相互写入。来自不同进程的写入可能并不总是以该顺序被看到(a)不使用同步操作的一致性模型ConsistencyDescriptionWeak只有在同步完成后，共享数据才能被统计为一致Release当退出关键区域时，共享数据保持一致Entry关键区域的共享数据在进入关键区域时保持一致。

(b)使用同步操作的一致性模型37Data-CentricConsistencyModelsI.e.,trytokeepdataconsistentacrossreplicasClient-CentricConsistencyModelsWeakerconditionOnlymaintainconsistencyforeachclientseparatelyOutline38以数据为中心的一致性模型即，尝试使数据在复制品上保持一致以客户为中心的一致性模型条件较弱只保持每个客户端的一致性Outline39EventualConsistencyModelssuchassequentialconsistencyweredevelopedinthecontextofparallelprogramsrunningontightlycoupledshared-memorymultiprocessorswithpossiblymanyconcurrentreaders/writers;suchmodelsarenotwellsuitedfordistributedsystemswithsignificantinterprocessorcommunicationdelaysIndistributedsystems,muchweakerformsofconsistency,withmorerestrictiveusepatternsoftheshareddatastoreareoftenacceptable,e.g.,Onlyafew(orevenone)possiblewritersofdata,and/orRead-mostlydata(seldommodified),and/orStaledatamaybeacceptable(e.g.,web)EventualconsistencyIfnoupdatestakeplaceforalongtime,allreplicaswilleventuallybecomeconsistent40最终一致性在紧密耦合的共享存储器多处理器（可能还有许多并发读写器）上运行的并行程序的上下文中开发了诸如顺序一致性的模型;这种模型不太适合具有显着的处理器间通信延迟的分布式系统在分布式系统中，共享数据存储的更严格的使用模式的一致性较弱的形式通常是可接受的，例如，只有少数（甚至一个）可能的数据作者，和/或读取主要数据（很少修改）和/或陈旧数据可能是可接受的（例如，网页）最终一致性如果长时间不进行更新，所有副本将最终变得一致41EventualConsistencyMobileuserspresentachallengeClientmayaccessreplica1,makesomeupdatesClientmoves,accessesreplica2Modificationstoreplica1maynothavemigratedtoreplica2yet!42EventualConsistency移动用户面临挑战客户端可以访问副本1，进行一些更新客户端移动、访问副本2对副本1的修改可能没有迁移到副本243NotationNote:writesdonotnecessarilycompletelyoverwritedata(mayonlyupdatepartofthedata)xi[t]:versionofdataitemXatlocalcopyLiattimetWS(xi[t]):setofwriteoperationsonxatlocationLifrominitializationuntiltimetVariablexhastakenintoaccount(atleast)writesatLiuntiltimetWS(xi[t1];xj[t2]):setofwriteoperationsonxatlocationsLiuntiltimet1andLjuntiltimet2Variablexhastakenintoaccount(atleast)writesatLiuntiltimet1andwritesatLjuntilt2Here,inmostcasesomit“t”-clearbycontext44Notation注意：写入不一定完全覆盖数据（可能只更新部分数据）xi[t]：时间t为本地副本Li的数据项X的版本WS（xi[t]）：从初始化到时间t，在位置Li处的x上的写入操作的集合变数x考虑到（至少）在李直到时间t写入WS（xi[t1];xj[t2]）：在位置Li处的x到时间t1和时间t2之间的写入操作集合变量x考虑到（至少）在Li直到时刻t1（至少）写入到Lj直到t2在这里，大多数情况下省略“t”-通过上下文来清除45MonotonicReads(1)Adatastoreissaidtoprovidemonotonic-readconsistencyifthefollowingconditionholds:Ifaprocessreadsthevalueofadataitemx…anysuccessivereadoperationonxbythatprocesswillalwaysreturnthatsamevalueoramorerecentvalue.46单调读(1)如果满足以下条件，则数据存储据称提供单调读取一致性：如果进程读取数据项x的值...任何通过该进程对x进行的连续读取操作将始终返回相同的值或更新的值。47MonotonicReads(2)ThereadoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastore.

(a)Amonotonic-readconsistentdatastore.48MonotonicReads(2)在同一数据存储的两个不同本地副本上由单个进程P执行的读取操作。（a）单调读取一致的数据存储。49MonotonicReads(3)ThereadoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastore.

(b)Adatastorethatdoesnotprovidemonotonicreads.50MonotonicReads(3)在同一数据存储的两个不同本地副本上由单个进程P执行的读取操作。（b）不提供单调读数的数据存储。51MonotonicWrites(1)Inamonotonic-writeconsistentstore,thefollowingconditionholds:Awriteoperationbyaprocessonadataitemx…iscompletedbeforeanysuccessivewriteoperationonxbythesameprocess.52MonotonicWrites(1)在单调写入一致存储中，以下条件成立：

对于数据项x上的进程的写入操作在通过相同进程对x进行任何连续写入操作之前完成。53MonotonicWrites(2)ThewriteoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastore.(a)Amonotonic-writeconsistentdatastore.

54MonotonicWrites(3)ThewriteoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastore.(b)Adatastorethatdoesnotprovidemonotonic-writeconsistency.55ReadYourWrites(1)Adatastoreissaidtoprovideread-your-writesconsistency,ifthefollowingc