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

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

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

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

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

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

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

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

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

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

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

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