并行程序設(shè)計(jì) 中文課件 12 并行計(jì)算系統(tǒng)一致性

ParallelProgrammingInstructor:ZhangWeizhe(張偉哲)ComputerNetworkandInformationSecurityTechniqueResearchCenter,SchoolofComputerScienceandTechnology,HarbinInstituteofTechnologyConsistency3Data-CentricConsistencyModelsI.e.,trytokeepdataconsistentacrossreplicasClient-CentricConsistencyModelsWeakerconditionOnlymaintainconsistencyforeachclientseparatelyOutline4以數(shù)據(jù)為中心的一致性模型即，嘗試使數(shù)據(jù)在復(fù)制品上保持一致以客戶為中心的一致性模型條件較弱只保持每個(gè)客戶端的一致性O(shè)utline5Data-CentricConsistencyModelsConsistencymodel(akaconsistencysemanticsorconstraints)ContractbetweenprocessesandthedatastoreIfprocessesobeycertainrules,datastorewillworkcorrectlyAllmodelsattempttoreturntheresultsofthelastwriteforareadoperationDifferinhow“l(fā)ast”writeisdetermined/defined6以數(shù)據(jù)為中心的一致性模型一致性模型（一致性語(yǔ)義或約束）流程和數(shù)據(jù)存儲(chǔ)之間的契約如果流程遵守某些規(guī)則，數(shù)據(jù)存儲(chǔ)將正常工作所有模型都嘗試返回最后寫(xiě)入的結(jié)果，以進(jìn)行讀取操作不同之處是“最后”寫(xiě)入如何確定/定義的7StrictConsistencyAnyreadalwaysreturnstheresultofthemostrecentwriteImplicitlyassumesthepresenceofaglobalclockAwriteisimmediatelyvisibletoallprocessesDifficulttoachieveinrealsystemsasnetworkdelayscanbevariable(a)Astrictlyconsistentstore.(b)Astorethatisnotstrictlyconsistent.8嚴(yán)格一致任何讀取總是返回最近寫(xiě)入的結(jié)果隱含地假定存在全局時(shí)鐘所有進(jìn)程都可以立即看到寫(xiě)入在實(shí)際系統(tǒng)中難以實(shí)現(xiàn)，因?yàn)榫W(wǎng)絡(luò)延遲是可變的(a)Astrictlyconsistentstore.(b)Astorethatisnotstrictlyconsistent.9SequentialConsistency(1)Adatastoreissequentiallyconsistentwhen:Theresultofanyexecutionisthesameasifthe(readandwrite)operationsbyallprocessesonthedatastore…wereexecutedinsomesequentialorderand…theoperationsofeachindividualprocessappear…inthissequenceintheorderspecifiedbyitsprogram.10順序一致性(1)數(shù)據(jù)存儲(chǔ)是順序一致的：

任何執(zhí)行的結(jié)果與數(shù)據(jù)存儲(chǔ)上的所有進(jìn)程的（讀取和寫(xiě)入）操作相同...被執(zhí)行了一些順序...每個(gè)進(jìn)程的操作出現(xiàn)...以這個(gè)順序按其程序指定的順序。11SequentialConsistency(2)Sequentialconsistency:weakerthanstrictconsistencyAssumesalloperationsareexecutedinsomesequentialorderandeachprocessissuesoperationsinprogramorderAnyvalidinterleavingisallowed AllagreeonthesameinterleavingEachprocesspreservesitsprogramorderNothingissaidabout“mostrecentwrite”12順序一致性(2)順序一致性：弱于嚴(yán)格的一致性假設(shè)所有操作都按照一定順序執(zhí)行，每個(gè)進(jìn)程按程序順序發(fā)出操作允許任何有效的交織所有人都同意相同的交錯(cuò)每個(gè)進(jìn)程保留其程序順序沒(méi)有關(guān)于“最近寫(xiě)的”13SequentialConsistency(3)(a)Asequentiallyconsistentdatastore.

(b)Adatastorethatisnotsequentiallyconsistent.14順序一致性(3)（a）順序一致的數(shù)據(jù)存儲(chǔ)。（b）不是順序一致的數(shù)據(jù)存儲(chǔ)。15CasualConsistency(1)Necessarycondition:

Writesthatarepotentiallycasuallyrelatedmustbeseenbyallprocessesinthesameorder.Concurrentwritesmaybeseeninadifferentorderondifferentmachines.Causallyrelatedwritesmustbeseenbyallprocessesinthesameorder.Concurrentwritesmaybeseenindifferentordersondifferentmachines16結(jié)果一致性(1)必要條件：

可能的相關(guān)隨機(jī)寫(xiě)入必須以相同的順序被所有進(jìn)程看到。并行寫(xiě)入可以在不同的機(jī)器上以不同的順序看到。所有進(jìn)程必須以相同的順序看到結(jié)果相關(guān)的寫(xiě)入。并行寫(xiě)入可以在不同的機(jī)器上以不同的順序看到17CasualConsistency(2)Thissequenceisallowedwithacasually-consistentstore,butnotwithsequentiallyorstrictlyconsistentstore.18結(jié)果一致性(2)這個(gè)序列允許隨機(jī)一致的存儲(chǔ)，但不是按順序或嚴(yán)格一致的存儲(chǔ)。19CasualConsistency(3)Aviolationofacasually-consistentstore.Acorrectsequenceofeventsinacasually-consistentstore.20結(jié)果一致性(3)一個(gè)違反結(jié)果一致的存儲(chǔ)一個(gè)符合結(jié)果一致的正確存儲(chǔ)序列21FIFOConsistency(1)NecessaryCondition:

Writesdonebyasingleprocessareseenbyallotherprocessesintheorderinwhichtheywereissued,butwritesfromdifferentprocessesmaybeseeninadifferentorderbydifferentprocesses.22FIFOConsistency(1)必要條件：所有其他進(jìn)程按單個(gè)進(jìn)程執(zhí)行的寫(xiě)入按照發(fā)布順序可以看到，但不同進(jìn)程的寫(xiě)入可能按不同的進(jìn)程以不同的順序顯示。23FIFOConsistency(2)AvalidsequenceofeventsofFIFOconsistency24FIFOConsistency(2)AvalidsequenceofeventsofFIFOconsistency25WeakConsistency(1)Properties:AccessestosynchronizationvariablesassociatedwithadatastorearesequentiallyconsistentNooperationonasynchronizationvariableisallowedtobeperformeduntilallpreviouswriteshavebeencompletedeverywhereNoreadorwriteoperationondataitemsareallowedtobeperformeduntilallpreviousoperationstosynchronizationvariableshavebeenperformed.26弱一致性(1)屬性：訪問(wèn)與數(shù)據(jù)存儲(chǔ)相關(guān)聯(lián)的同步變量是順序一致的允許執(zhí)行同步變量的操作，直到所有以前的寫(xiě)入都到處都完成在執(zhí)行對(duì)同步變量的所有先前操作之前，都不允許執(zhí)行對(duì)數(shù)據(jù)項(xiàng)的讀取或?qū)懭氩僮鳌?7WeakConsistency(2)Avalidsequenceofeventsforweakconsistency.Aninvalidsequenceforweakconsistency.28ReleaseConsistency(1)Avalideventsequenceforreleaseconsistency.29ReleaseConsistency(2)Rules:Beforeareadorwriteoperationonshareddataisperformed,allpreviousacquiresdonebytheprocessmusthavecompletedsuccessfully.Beforeareleaseisallowedtobeperformed,allpreviousreadsandwritesbytheprocessmusthavecompletedAccessestosynchronizationvariablesareFIFOconsistent(sequentialconsistencyisnotrequired).30ReleaseConsistency(2)規(guī)則：在執(zhí)行對(duì)共享數(shù)據(jù)的讀或?qū)懖僮髦?，進(jìn)程完成的所有以前的獲取必須已經(jīng)成功完成。在允許執(zhí)行釋放之前，進(jìn)程的所有以前的讀取和寫(xiě)入都必須已經(jīng)完成訪問(wèn)同步變量是FIFO一致的（不需要順序一致性）。31EntryConsistency(1)Conditions:Anacquireaccessofasynchronizationvariableisnotallowedtoperformwithrespecttoaprocessuntilallupdatestotheguardedshareddatahavebeenperformedwithrespecttothatprocess.Beforeanexclusivemodeaccesstoasynchronizationvariablebyaprocessisallowedtoperformwithrespecttothatprocess,nootherprocessmayholdthesynchronizationvariable,noteveninnonexclusivemode.Afteranexclusivemodeaccesstoasynchronizationvariablehasbeenperformed,anyotherprocess'snextnonexclusivemodeaccesstothatsynchronizationvariablemaynotbeperformeduntilithasperformedwithrespecttothatvariable'sowner.32準(zhǔn)入一致性(1)條件：不允許同步變量的獲取訪問(wèn)相對(duì)于進(jìn)程執(zhí)行，直到對(duì)該進(jìn)程已經(jīng)執(zhí)行了對(duì)被保護(hù)的共享數(shù)據(jù)的所有更新。在允許進(jìn)程對(duì)異步模式訪問(wèn)同步變量進(jìn)行相對(duì)于該進(jìn)程的執(zhí)行之前，沒(méi)有其他進(jìn)程可能保持同步變量，甚至不是非排他性的模式。在執(zhí)行對(duì)同步變量的獨(dú)占模式訪問(wèn)之后，任何其他進(jìn)程的下一個(gè)非排他性模式對(duì)該同步變量的訪問(wèn)可能不會(huì)執(zhí)行，直到相對(duì)于該變量的所有者執(zhí)行。33EntryConsistency(2)Avalideventsequenceforentryconsistency.34EntryConsistency(2)Avalideventsequenceforentryconsistency.35SummaryofConsistencyModelsConsistencyDescriptionStrictAbsolutetimeorderingofallsharedaccessesmatters.LinearizabilityAllprocessesmustseeallsharedaccessesinthesameorder.Accessesarefurthermoreorderedaccordingtoa(nonunique)globaltimestampSequentialAllprocessesseeallsharedaccessesinthesameorder.AccessesarenotorderedintimeCausalAllprocessesseecausally-relatedsharedaccessesinthesameorder.FIFOAllprocessesseewritesfromeachotherintheordertheywereused.Writesfromdifferentprocessesmaynotalwaysbeseeninthatorder(a)ConsistencymodelsnotusingsynchronizationoperationsConsistencyDescriptionWeakShareddatacanbecountedontobeconsistentonlyafterasynchronizationisdoneReleaseShareddataaremadeconsistentwhenacriticalregionisexitedEntryShareddatapertainingtoacriticalregionaremadeconsistentwhenacriticalregionisentered.(b)Modelswithsynchronizationoperations.36SummaryofConsistencyModelsConsistencyDescriptionStrict共享事務(wù)按絕對(duì)時(shí)間組織Linearizability所有進(jìn)程必須以相同的順序查看所有共享訪問(wèn)。還可以根據(jù)（非唯一）全局時(shí)間戳對(duì)訪問(wèn)進(jìn)行排序Sequential所有進(jìn)程以相同的順序查看所有共享訪問(wèn)。訪問(wèn)不記錄Causal所有進(jìn)程都以相同的順序查看結(jié)果相關(guān)的共享訪問(wèn)。FIFO所有進(jìn)程按照它們使用的順序相互寫(xiě)入。來(lái)自不同進(jìn)程的寫(xiě)入可能并不總是以該順序被看到(a)不使用同步操作的一致性模型ConsistencyDescriptionWeak只有在同步完成后，共享數(shù)據(jù)才能被統(tǒng)計(jì)為一致Release當(dāng)退出關(guān)鍵區(qū)域時(shí)，共享數(shù)據(jù)保持一致Entry關(guān)鍵區(qū)域的共享數(shù)據(jù)在進(jìn)入關(guān)鍵區(qū)域時(shí)保持一致。

(b)使用同步操作的一致性模型37Data-CentricConsistencyModelsI.e.,trytokeepdataconsistentacrossreplicasClient-CentricConsistencyModelsWeakerconditionOnlymaintainconsistencyforeachclientseparatelyOutline38以數(shù)據(jù)為中心的一致性模型即，嘗試使數(shù)據(jù)在復(fù)制品上保持一致以客戶為中心的一致性模型條件較弱只保持每個(gè)客戶端的一致性O(shè)utline39EventualConsistencyModelssuchassequentialconsistencyweredevelopedinthecontextofparallelprogramsrunningontightlycoupledshared-memorymultiprocessorswithpossiblymanyconcurrentreaders/writers;suchmodelsarenotwellsuitedfordistributedsystemswithsignificantinterprocessorcommunicationdelaysIndistributedsystems,muchweakerformsofconsistency,withmorerestrictiveusepatternsoftheshareddatastoreareoftenacceptable,e.g.,Onlyafew(orevenone)possiblewritersofdata,and/orRead-mostlydata(seldommodified),and/orStaledatamaybeacceptable(e.g.,web)EventualconsistencyIfnoupdatestakeplaceforalongtime,allreplicaswilleventuallybecomeconsistent40最終一致性在緊密耦合的共享存儲(chǔ)器多處理器（可能還有許多并發(fā)讀寫(xiě)器）上運(yùn)行的并行程序的上下文中開(kāi)發(fā)了諸如順序一致性的模型;這種模型不太適合具有顯著的處理器間通信延遲的分布式系統(tǒng)在分布式系統(tǒng)中，共享數(shù)據(jù)存儲(chǔ)的更嚴(yán)格的使用模式的一致性較弱的形式通常是可接受的，例如，只有少數(shù)（甚至一個(gè)）可能的數(shù)據(jù)作者，和/或讀取主要數(shù)據(jù)（很少修改）和/或陳舊數(shù)據(jù)可能是可接受的（例如，網(wǎng)頁(yè)）最終一致性如果長(zhǎng)時(shí)間不進(jìn)行更新，所有副本將最終變得一致41EventualConsistencyMobileuserspresentachallengeClientmayaccessreplica1,makesomeupdatesClientmoves,accessesreplica2Modificationstoreplica1maynothavemigratedtoreplica2yet!42EventualConsistency移動(dòng)用戶面臨挑戰(zhàn)客戶端可以訪問(wèn)副本1，進(jìn)行一些更新客戶端移動(dòng)、訪問(wèn)副本2對(duì)副本1的修改可能沒(méi)有遷移到副本243NotationNote:writesdonotnecessarilycompletelyoverwritedata(mayonlyupdatepartofthedata)xi[t]:versionofdataitemXatlocalcopyLiattimetWS(xi[t]):setofwriteoperationsonxatlocationLifrominitializationuntiltimetVariablexhastakenintoaccount(atleast)writesatLiuntiltimetWS(xi[t1];xj[t2]):setofwriteoperationsonxatlocationsLiuntiltimet1andLjuntiltimet2Variablexhastakenintoaccount(atleast)writesatLiuntiltimet1andwritesatLjuntilt2Here,inmostcasesomit“t”-clearbycontext44Notation注意：寫(xiě)入不一定完全覆蓋數(shù)據(jù)（可能只更新部分?jǐn)?shù)據(jù)）xi[t]：時(shí)間t為本地副本Li的數(shù)據(jù)項(xiàng)X的版本W(wǎng)S（xi[t]）：從初始化到時(shí)間t，在位置Li處的x上的寫(xiě)入操作的集合變數(shù)x考慮到（至少）在李直到時(shí)間t寫(xiě)入WS（xi[t1];xj[t2]）：在位置Li處的x到時(shí)間t1和時(shí)間t2之間的寫(xiě)入操作集合變量x考慮到（至少）在Li直到時(shí)刻t1（至少）寫(xiě)入到Lj直到t2在這里，大多數(shù)情況下省略“t”-通過(guò)上下文來(lái)清除45MonotonicReads(1)Adatastoreissaidtoprovidemonotonic-readconsistencyifthefollowingconditionholds:Ifaprocessreadsthevalueofadataitemx…anysuccessivereadoperationonxbythatprocesswillalwaysreturnthatsamevalueoramorerecentvalue.46單調(diào)讀(1)如果滿足以下條件，則數(shù)據(jù)存儲(chǔ)據(jù)稱提供單調(diào)讀取一致性：如果進(jìn)程讀取數(shù)據(jù)項(xiàng)x的值...任何通過(guò)該進(jìn)程對(duì)x進(jìn)行的連續(xù)讀取操作將始終返回相同的值或更新的值。47MonotonicReads(2)ThereadoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastore.

(a)Amonotonic-readconsistentdatastore.48MonotonicReads(2)在同一數(shù)據(jù)存儲(chǔ)的兩個(gè)不同本地副本上由單個(gè)進(jìn)程P執(zhí)行的讀取操作。（a）單調(diào)讀取一致的數(shù)據(jù)存儲(chǔ)。49MonotonicReads(3)ThereadoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastore.

(b)Adatastorethatdoesnotprovidemonotonicreads.50MonotonicReads(3)在同一數(shù)據(jù)存儲(chǔ)的兩個(gè)不同本地副本上由單個(gè)進(jìn)程P執(zhí)行的讀取操作。（b）不提供單調(diào)讀數(shù)的數(shù)據(jù)存儲(chǔ)。51MonotonicWrites(1)Inamonotonic-writeconsistentstore,thefollowingconditionholds:Awriteoperationbyaprocessonadataitemx…iscompletedbeforeanysuccessivewriteoperationonxbythesameprocess.52MonotonicWrites(1)在單調(diào)寫(xiě)入一致存儲(chǔ)中，以下條件成立：

對(duì)于數(shù)據(jù)項(xiàng)x上的進(jìn)程的寫(xiě)入操作在通過(guò)相同進(jìn)程對(duì)x進(jìn)行任何連續(xù)寫(xiě)入操作之前完成。53MonotonicWrites(2)ThewriteoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastore.(a)Amonotonic-writeconsistentdatastore.

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