kc第讲并发控制技术

第17讲:(第16章)

并发控制技术

重庆大学计算机学院课程名称:数据库系统

--------------------第17讲:并发控制技术项目驱动目标：

关系数据库如何实现对多个应用并发访问的控制：一、基于锁的协议 二、多粒度 三、死锁处理 四、基于时间戳的协议 主要讨论问题：什么是锁，有哪些基本类型？什么叫死锁？什么是两阶段封锁协议？除X,S锁外,还有其它类型的锁？意向锁的相容关系如何？如何检测是否存在死锁？什么是时间戳协议？时间戳协议为何能保持可串行化？Exercise17LocksandItstypesAlockisamechanismtocontrolconcurrentaccesstoadataitemDataitemscanbelockedintwomodes:排它锁exclusive(X)mode.Dataitemcanbebothreadaswellaswritten.X-lockisrequestedusinglock-Xinstruction.共享锁shared(S)mode.Dataitemcanonlyberead.S-lockisrequestedusinglock-Sinstruction.Lockrequestsaremadetoconcurrency-controlmanager.Transactioncanproceed继续进行

onlyafterrequestisgranted.一基于锁的协议1-1什么是锁，有哪些基本类型？1.1锁Lock-compatibility相容矩阵：Lock-compatibilitymatrix作用：AtransactionmaybegrantedalockonanitemiftherequestedlockiscompatiblewithlocksalreadyheldontheitembyothertransactionsAnynumberoftransactionscanholdsharedlocksonanitem,butifanytransactionholdsanexclusiveontheitemnoothertransactionmayholdanylockontheitem.Ifalockcannotbegranted,therequestingtransactionismadetowaittillallincompatiblelocksheldbyothertransactionshavebeenreleased.Thelockisthengranted.直观例示(例子)1-2什么是锁的相容性？1.1锁ExampleofUsingLocksExampleofatransactionperforminglocking:

T2:lock-S(A);read(A);unlock(A);lock-S(B);read(B);unlock(B);display(A+B)Lockingasaboveisnotsufficienttoguaranteeserializability,ifAandBgetupdated(bysomeothertransactionT1:转账50)in-betweenthereadsofAandB,thedisplayedsumwouldbewrong.Alockingprotocolisasetofrulesfollowedbyalltransactionswhilerequestingandreleasinglocks.Lockingprotocolsrestrict限制

thesetofpossibleschedules.1-3什么是封锁协议？T1:lock-X(B);read(B);B:=B-50;write(B);unlock(B);Lock-X(A)read(A)A:=A+50write(A)unlock(A)若：Ais100Bis200则该调度后T2显示：A+B=150------------而T1,T2后T2显示300而T2,T1后T2显示300(原因分析)1.1锁Pitfalls陷阱ofLock-BasedProtocols-死锁Considerthepartialschedule

Neither

T3

nor

T4canmakeprogress—executinglock-S(B)causesT4towaitforT3toreleaseitslockonB,whileexecutinglock-X(A)causesT3

towaitforT4toreleaseitslockonA.Suchasituationiscalledadeadlock.死锁，问题如何解决？TohandleadeadlockoneofT3orT4mustberolledbackand

itslocksreleased.1-4什么叫死锁？1.2死锁与活锁PitfallsofLock-BasedProtocols-活锁Thepotential潜在的

fordeadlockexistsinmostlockingprotocols.Deadlocksareanecessaryevil不可避免的恶魔.Starvation

饥饿/饿死

isalsopossibleifconcurrencycontrolmanagerisbadlydesigned.Forexample:AtransactionmaybewaitingforanX-lockonanitem,whileasequenceofothertransactionsrequestandaregrantedanS-lockonthesameitem.Thesametransactionisrepeatedlyrolledbackduetodeadlocks.Concurrencycontrolmanagercanbedesignedtopreventstarvation.

(如何解决?)当事务T申请对数据项Q加M型锁时：当前不存在已对数据项Q持有与M冲突的锁的其他事务当前不存在(先于T申请)正等待对数据项Q加锁的其他事务1-5什么叫活锁(饿死)？1.2死锁与活锁TheTwo-PhaseLockingProtocolThisisaprotocolwhichensuresconflict-serializableschedules.第1阶段Phase1:增长GrowingPhasetransactionmayobtainlocks,but

加锁阶段！transactionmaynotreleaselocks第2阶段Phase2:缩减ShrinkingPhasetransactionmayreleaselocks,but释放锁阶段！transactionmaynotobtainlocks例子(p.421图16-5和16-6中的T3和T4都是两阶段的p.420图16-2和16-3中的T1和T2都不是两阶段的)Theprotocolassuresserializability.Itcanbeprovedthatthetransactionscanbeserializedintheorderoftheirlockpoints

(i.e.thepointwhereatransactionacquireditsfinallock)(留作练习,习题16.1).1.3两阶段封锁协议1-6什么是两阶段封锁协议？Strict&RigorousTwo-PhaseLockingProtocolTwo-phaselockingdoesnotensurefreedomfromdeadlocks(图16-7调度2)Cascadingroll-backispossibleundertwo-phaselocking.

(图16-8,T5撤销时T6,T7撤销)Toavoidthis,followamodifiedprotocolcalledstricttwo-phaselocking.Hereatransactionmustholdallitsexclusivelockstillitcommits/aborts.Rigoroustwo-phaselockingisevenstricter:hereall

locksareheldtillcommit/abort.Inthisprotocoltransactionscanbeserializedintheorderinwhichtheycommit.说明：大部分数据库系统都采用这两种封锁协议之一！p.422图16-8部分调度1-7什么是严格两阶段封锁协议？1-8什么是强两阶段封锁协议？1.3两阶段封锁协议ImplementationofLockingAlockmanagercanbeimplementedasaseparateprocesstowhichtransactionssendlockandunlockrequestsThelockmanagerrepliestoalockrequestbysendingalockgrantmessages(oramessageaskingthetransactiontorollback,incaseofadeadlock)TherequestingtransactionwaitsuntilitsrequestisansweredThelockmanagermaintainsadata-structurecalledalocktabletorecordgrantedlocksandpendingrequestsThelocktableisusuallyimplementedasanin-memoryhashtableindexedonthenameofthedataitembeinglockedlocktable1.4锁管理器1-9封锁管理如何实现？LockTableBlackrectanglesindicategrantedlocks,whiteonesindicatewaitingrequestsLocktablealsorecordsthetype

(图中未标出)oflockgrantedorrequestedNewrequestisaddedtotheendofthequeueofrequestsforthedataitem,andgrantedifitiscompatiblewithallearlierlocksUnlockrequestsresultintherequestbeingdeleted,andlaterrequestsarecheckedtoseeiftheycannowbegrantedIftransactionaborts,allwaitingorgrantedrequestsofthetransactionaredeletedlockmanagermaykeepalistoflocksheldbyeachtransaction,toimplementthisefficiently数据项的hash链表当前有五个数据项:I7,I23,I192,I4,I44有相同hash的数据项GrantedWaiting1-10什么是锁表,有何用途？1.4锁管理器MultipleGranularity粒度Allowdataitemstobeofvarioussizesanddefineahierarchyofdatagranularities,wherethesmallgranularitiesarenestedwithinlargeronesCanberepresentedgraphicallyasatree(例子)Whenatransactionlocksanodeinthetreeexplicitly,itimplicitlylocksallthenode'sdescendentsinthesamemode.Granularityoflocking(levelintreewherelockingisdone):细粒度锁finegranularity(lowerintree):highconcurrency,highlockingoverhead粗粒度锁coarsegranularity

(higherintree):lowlockingoverhead,lowconcurrency二多粒度2.1数据粒度与封锁2-1什么是数据粒度？2-2多粒度数据如何封锁？ExampleofGranularityHierarchy

Thelevels,startingfromthecoarsest(top)levelareDatabaseAreaFilerecord

数据库级区域级文件级记录级2.1数据粒度与封锁IntentionLockModes例子(意向所用途分析)intentionlocksallowahigherlevelnodetobelockedinSorXmodewithouthavingtocheckalldescendentnodes.InadditiontoSandXlockmodes,therearethreeadditionallockmodeswithmultiplegranularity:intention-shared(IS)共享意向锁:indicatesexplicitlockingatalowerlevelofthetreebutonlywithsharedlocks.低层有显示S锁intention-exclusive(IX)排它意向锁:indicatesexplicitlockingatalowerlevelwithexclusiveorsharedlocks.低层有显示X/S锁sharedandintention-exclusive(SIX)共享排它意向锁:thesubtreerootedbythatnodeislockedexplicitlyinshared

mode

andexplicitlockingisbeingdoneatalowerlevelwithexclusive-modelocks.意向锁相容矩阵多粒度封锁协议2.2意向锁2-3除X,S锁外,还有其它类型的锁？GranularityHierarchy-用途分析2-4为何需要意向锁？2.2意向锁之后,Tk可以对DB加锁？需检查所有节点,搜索整个树!解决办法：Ti可对Fc加显示锁时，同时对到根路径的所有父节点加意向锁！然后利用多粒度封锁协议判断是否可加锁！假设：Ti已对Fc加锁Ti已同时对DB和A2加意向锁！Co碰mp姐at昆ib迎il去it避y巴Ma宜tr肥ix毫w惭it厕h港I问nt但en具ti捞on冲L根oc收k眯Mo婶de锻sTh议e泉co气mp哄at笨ib旦il年it离y良ma鸣tr病ix候f诞or赛a砍ll漏l贞oc棍k颠mo什de摸s择is油:ISIXSSIXXISIXSSIXX2-落5意向购锁的芽相容页关系广如何陆？2.拾2意向泼锁Mu题lt努ip根le带G衔ra警nu雪la帐ri帅ty苹L绍oc烈ki屡ng桥S旗ch沾em馒e多粒倦封度膨锁协蛋议:T祸ra忆ns题ac扑ti蹦onTica揭n月lo争ck柴a炉n鸦od减eQ,删us陆in处g兴th芹e阁fo良ll夹ow详in架g淹ru寇le养s:Th立e秆lo祖ck胃c偶om距pa爪ti装bi味li尚ty咽m育at即ri施x埋mu哭st位b门e肾ob倾se轿rv料ed浓.Th南e道ro翼ot计o闸f能th悲e喷tr醒ee狭m贴us哭t恶be野l森oc叼ke仰d路fi巩rs道t,淹a欧nd取m郑ay尸b宜e良lo旗ck围ed临i瞒n速an据y螺mo岸de影.A伯no泄deQca轨n侵be禽l早oc博ke傻d象byTiin侦S倦o加r昏IS盲m袭od宅e访on钢ly箭i抵f购th埋e辆pa放re叫nt卡o速fQis眉c梁ur牺re辅nt济ly上l洒oc矮ke遮d辈byTiin漫e锤it松he嚷r朵IX填o针r宽IS恢m辨od桐e.A肠no讲deQca剖n陈be胆l许oc蚀ke替d布byTiin抱X每,窃SI愧X,伏o灵r织IX雄m斥od华e善on怀ly旬i肉f豪th独e袜pa倍re满nt产o逆fQis哲c青ur墨re抽nt蜡ly涉l骆oc适ke询d步byTiin近e涝it剂he粒r牧IX淘o退r刺SI绿X痛mo径de吹.Tica膏n淡lo伯ck级a抬n熊od们e汉on办ly代i绒f忘it芝h标as约n披ot香p有re真vi宇ou恼sl唤y客un墨lo寇ck多ed剥a夹ny念n炼od稼e萄(t高ha欲t身is挣,Tiis塌t坟wo有-p渗ha司se券).Tica哨n甜un鹅lo子ck卫a喘n亦od罗eQon士ly蹄i呈f狂no佳ne丈o垒f唱th形e酷ch甲il竖dr垮en仙o苏fQar冤e按cu错rr魄en犹tl节y蝴lo蔬ck峰ed左b正yTi.特点洞：Ob顷se伙rv敞eth响at防l陶oc织ks判a姻re辈a纺cq遵ui色re犬d获得inro圈ot灯-t培o-拖le旅af壤o绞rd身er佛,锦wh绩er仓ea偷s换th今ey农a把re项r抱el痰ea刷se板d应in拔l叙ea摘f-灵to领-r娘oo躲t择or件de急r.2-拢6什么雁是多独粒度依封锁扇协议吵？2.娃2意向话锁De躲ad果lo励ck-例子Co伤ns聚id喂er浊t遭he赛f坝ol赴lo画wi岩ng贞t雀wo咽t返ra票ns侄ac资ti闪on柱s:T1:筐wr荷it词e珠(X)T2:景w勉ri散te烟(Y)wr鞠it烦e(Y)由wr雪it娘e(X)Sc敲he深du陕le昏w毁it阻h尿de帽ad迎lo肺ckT1T2lock-XonXwrite(X)lock-XonYwrite(Y)waitforlock-XonXwaitforlock-XonY三买死锁校处理3.监1死锁3-矩1何时笼会出拼现死葱锁？De速ad显lo斧ck严H运an附dl机in袖gSy研st敌em室i跨sde禁ad竿lo速ck敬edifth菊er根e殖is绪a随s互et飞o壁f营tr贴an蹲sa泪ct请io累ns船s助uc纠h桌th渔atev轨er劲ytr序an歼sa期ct孤io冤n贡in结t茧he瞧s引et枝i齿s缸wa臭it量in退g嫌fo得r财an梢ot养he兆r执tr砍an倒sa敬ct岔io器n辨in悟t叶he咱s危et屋.De肠ad完lo拐ck西p桥re客ve戏nt次io愿npr振ot撞oc越ol挂sen肚su回re心t汽ha咳t玩th既e杀sy米st镇em撞w烦il架lne排ve鸦ren圆te割r肺in繁to傍a厦d失ea条dl坊oc茧k斗st沈at或e.So遮mepr杯ev刺en艘ti英on却s嘱tr撤at最eg奇ie洽s猛:法1：Re山qu窄ir认eth收at锻e巡寿ac叨h痛tr节an犬sa妹ct愿io填n疮lo顷ck双sal祖lit炎s夕da廉ta壳i袍te提ms缸b规ef蹲or秘e元it袭b拌eg丙in鸟s岁ex期ec也ut当io访n愚(p琴re桶de父cl唐ar假at剑io融n).预先惕声明法2：Im伟po栽se强制pa婆rt次ia稍l墓or谱de侦ri斑ng支o册fal宵lda荣ta休i营te泊msan银dre让qu观ir蠢e雪th采at程a景t则ra井ns忌ac月ti界on赌c佳an档l焰oc光k膏da草ta连i爹te此ms样o午nl炎yin膛t笔he箭o君rd颂ersp娱ec回if嫁ie裂d读by执t汪he溪p悼ar蛋ti参al帜o洲rd查er质(屿gr忽ap乒h-深ba海se高d孙pr梢ot废oc驴ol).基于扬图的摘协议(p垂.4况24漂)3.强2死锁鸣预防3-讨2如何搅预防便死锁灵？Mo剩re榜D膝ea傅dl肝oc麦k跑Pr涛ev它en庸ti旺on螺S慨tr美at成eg绪ie略sFo壶ll景ow鱼in枕g共sc和he狂me脖s珠us颂e驱tr征an姨sa督ct吓io成nti宽me鞭st男am友ps时间滤戳fo脂r扁th委e定sa霉ke培o矩f炊de老ad强lo特ck处p歉re抵ve哭nt来io孩n登al湿on抖e.法1）wa妄it疲-d席iesc军he筐me岗—no矛n-先pr课ee封mp原ti帝ve非抢寒占式ol掉de砌r碌tr欧an须sa宏ct阁io咳n汽ma罚ywa类itfo草r绳yo愁un冰ge毁r它on唇e术to机r敌el称ea绿se多d使at钥a素it申em饲.Yo奥un劫ge撑r异tr么an呀sa外ct升io封ns舅n惑ev伏er勤w峡ai减tfo香r输ol绣de陷ron歉es活(屈th单eyar府e尤ro忍ll票ed生b注ac架kin材st狮ea绸d)胃.跃(有冲乳突时撇，新窃的事潜物自线动回庄卷)a正tr提an熊sa郑ct富io辨n桃ma陷y去di婶ese肤ve责ra刃lti巷me诉s俱be司fo士re斩a鼠cq央ui银ri智ng罚n膀ee维de乡丰d泰da洲ta磨i患te孝m法2）wo排un含d-膊wa碧itsc颜he凯me木—pr丈ee泰mp吼ti饶ve抢占赢式ol确de僵r贼tr仿an圾sa吧ct赵io它nwo救un屑ds(f桶or换ce纸s比ro船ll焦ba颂ck粱)竞of够y钞ou左ng跪er题t只ra史ns摸ac扶ti斧on散i瓜ns仪te希ad寸o参f仔wa牢it气in英g率fo胡r晨it扰.Yo锋un瓜ge字r俘tr套an螺sa焰ct歼io唱ns免m哲ay姥w桂ai扶tfo盘r售ol竿de会ron糠es械.泳(有冲美突时程，老诸的事厦物强娱制将秃新的编事物差回卷)ma士y某befe策we仇rro沈ll扁ba萌ck江s顿th堡anwa波it匠-d峡iesc累he译me黑.法3）（待续…）3-把3还有桃其他安预防品死锁盈方法版？3.映2死锁融预防说明涉：Bo仗thinwa哭it燥-d眠iean较d暗inwo闯un品d-券wa姐itsc助he价me录s,方a湖r沙ol丽le胜d五ba碰ck漆t彩ra笋ns问ac拌ti趋on输s触is阶r涛es冬ta育rt扩ed翅w旨it帮h豆it嫩s赚or庸ig扶in步al暑t抓im饿es油ta衣mp永.蜘Ol赴de楼r且tr伍an敌sa厚ct雪io液ns毫t雷hu掀s字ha成ve银p易re序ce窗de手nc尊e罪ov放er匀n灾ew桂er忧o悔ne戚s,膀a闸ndst栽ar碎va能ti讲on活锁is明h康en芬ce毅a枣vo跃id秆ed村.法3）Ti鬼me堆ou鞠t-浩Ba乐se幕dSc碧he矿me佩s:a博tr岭an匹sa开ct内io爪n电wa嫌it之s壶fo鞠r兰a痒lo猾ck浑o岔nl矮y六fo兰ra肚sp倘ec欲if骆ie联d畜am旁ou笛nt罗o羞f若ti驶me.羊Af渔te弹r座th城at凝,症th曲e盲wa蜓it卵t饶im产es索o样ut辣a软nd灿t经he宣t纪ra赏ns遥ac但ti潜on燃i凉s概ro傻ll钳ed殃b流ac探k.th她us母d苍ea乖dl猎oc斤ks鸭a救re蹈n干ot挎p主os删si蓄bl雄esi定mp商le轧t肝o殖im意pl迹em娃en有t;债b竞ut牢s参ta华rv侵at爪io茫n杜is煤p句os担si外bl摩e.抢A荐ls撤o福di裕ff身ic鹿ul疫t房诚to慢d忙et蔑er队mi沈ne蚂g匆oo驻d密va蓝lu筐e也of滋t男he息t例im密eo膛ut陵i仆nt够er内va俯l.Mo倾re恼D指ea娱dl料oc乔k拉Pr现ev嗓en云ti你onSt震ra仆te旋gi瞧es(续)3.由2死锁玩预防De州ad敬lo西ck郊D娱et足ec脖ti舟on等待未图：De蹦ad侮lo膜ck荡sca谁n是be旋d狼es蛙cr炸ib先ed掀a碑s宾awa识it铜-f药orgr中ap专h,wh排ic误h铲co唯ns槐is叙ts筋o票f良a陆pa寇irG=腊(V,E),he奏reVis西a违s多et游o口f倒ve形rt窄ic课es盐(指al碧l越th腿e微tr倡an生sa膊ct洁io缓ns于i基n熄th赔e令sy王st完em煌)Eis园a在s妙et梨o跳f筹ed患ge笼s;材e之ac庸h宾el载em淘en农t刊is刷a亦n华or突de返re巾d找pa疲irTiTj.等待虎图的简形成木与更士新：IfTiTjis扭i毙nE,肠th灯en冲t者he掠re溜i参s逆a驳di促re冶ct背ed红e弯dg养e婆fr喷omTitoTj,回im师pl最yi密ng泄t烈ha许tTiis划w智ai蜂ti谎ng寨f享orTjto模r出el铸ea额se捏a猴d验at励a步it基em脚.Wh翼enTire像qu肥es晓ts我a毯d冬at厦a绕it裤em愚c煌ur脖re航nt涂ly邻b泊ei巡寿ng庸h尖el澡d表byTj,惰th作en岗t答he伙e善dg妨eTiTjis饲i华ns冤er父te误d霸in寒t拾he悔w副ai猜t-最fo推r厚gr抄ap腿h.拍T完hi团s恩ed挨ge绸i摘s症re棒mo小ve般d盛on勺ly临w造he激nTjis州n偶o伐lo蚊ng修er辛h球ol鸡di蒜ng骑a塔d寻at振a欢it管em银n坚ee邻de绵d储byTi.死锁姿检测撑方法醋：Th百esy扮st条em叼i浆s援in方a毅d裤ea桐dl查oc你k悦st稿at愤eif岔a贤nd衫o悬nl愁y色ifth歌e梁wa丝式it胶-f刚or细g姑ra喂ph呼h荷as床a果c揪yc棚le景.象M蛾us萄t贴in茄vo灾ke席a亦d领ea膨dl听oc伴k-黑de窝te哭ct迟io戏n杜al缠go蛾ri静th宝m回pe动ri弊od燥ic滩al类ly较t射o洽lo脉ok商f县orcy具cl郊es未.等待撑图示例3.止3死锁哥检测3-循4如何礼检测粪是否肚存在移死锁痕？De简ad她lo院ckDe珠te免ct多io泄n-等待倡图例驶子Wa玩it配-f惕or乘g量ra握ph垫w战it沈ho俘ut须acy喂cl龙e不存之在死除锁Wa酬it放-f怕or傻g磨ra反ph由w求it竞h店acy右cl忌e存在冷死锁解释垃：3-剪6下两卵等待伴图存姜在死帆锁？3.龟3死锁王检测De漆ad转lo壮ck动R您ec窗ov济er范yWh留ende巩ad旷lo仰ck掠i堂s年d笑et怕ec俘te笼d肠:So浓me返t竞ra廉ns凉ac咽ti柳on带w带il舍l秘ha朱ve狮t感o专ro柱ll柜ed吊b仪ac弃k辟(m居ad缩慧e播a掌vi萄ct呼im斥)浪to受b总re毫ak午d伶ea减dl耍oc区k.寺Se谣le原ct茎t疮ha某t巷tr曲an壮sa币ct端io起n栗asvict尘im牺牲领品th太at糕w请il逐l煤in恼cu绕rmi浓ni紧mu搅mco击st(选择者事务掀回卷凉的代螺价最仁小者).Ro忆ll箩ba变ck仙-笔-延de桶te硬rm妄in鄙e及ho窗w乒fa希r员to律r炉ol岸l艰ba程ck府t普ra孝ns咐ac事ti任on回卷醋整个制事务走：To抹ta葵lro复ll害ba已ck:傲Ab辱or拥t晕th雀e免tr皂an乓sa元ct盘io小n播an唉d铃th互en侮r酷es畜ta跳rt聪i村t.回卷悟事务曾的部茫分操春作：Mo吓reef佛fe乡丰ct蜓iv荣e核to细r可ol码l框ba熔ck葡t骆ra否ns尤ac需ti雄on间o辆nl葵y手as潜f斩ar犹a顺s乐ne绑ce寄ss培ar写y促to熊b拦re颤akde闷ad摄lo器ck.(这种脚情形盘要求询记录微运行彩事务站的相循关状再态信更息)St答ar端va愉ti售on活锁ha控pp遣en映s扬if蠢s扛am举e俊tr愧an武sa守ct共io罢n注is绍a教lw闸ay误s景ch口os错en瞧a案s卧vi现ct胡im乱.(解决任方法)Bu倦t纸we捎c放an身i建nc休lu掉deth散e椒nu业mb衣er末o禽f霸ro川ll互ba偿ck弦s奖in软t蝇he姨c隙os丘t霸fa俩ct燥or属t微o造av彩oi招d静st妙ar湿va声ti纹on3-区7存在逮死锁辜时如炉何解猜除？3.凶3死锁芒检测Ti备me撒st地am两p-划Ba猴se店d岭Pr螺ot坛oc川ol贺sEa鲁ch稿t防ra吴ns毯ac漂ti全on便i丹s呢is叛su丝式ed声ati饰me识st戒am即pwh吐en骨i慕t傲en占te唐rs基t呢he电s喘ys者te气m.下I愿f停an银o构ld坛t么ra嘱ns蜻ac而ti循onTiha物s圣ti芳me盏-s且ta冠mp扛T厨S(Ti),昏a筹n砖ew中t黎ra央ns锻ac锋ti笛onTjis帐a伪ss指ig晚ne阀d筹ti率me炕-s拖ta挑mp棒T碎S(Tj)房诚su荐ch裹t茫ha暂t愉TS奇(Ti)睡<T哈S(Tj).(利用范统一捧的系佛统时召间)Th葡e拥pr幸ot轨oc肌ol家m挎an迷ag撞es息c秤on括cu欲rr排en任t辉ex送ec负ut驶io替n绢su栏ch担t悦ha北t飞th色e惯ti微me意-s甚ta摄mp帖sde净te春rm颜in壤eth夹e桑se近ri痛al球iz获ab熔il托it扑y格or雕de史r.In很o摔rd修er段t帐o所as羽su冷re稠s范uc缎h繁be境ha稍vi窄or碍,肉th推e伏pr友ot欺oc金ol欺m雨ai剖nt穷ai动ns晴f漂orea沫chda芽taQtw剥oti瞧me储st贱am前p拾va作lu哲es隐:W-宏ti腹me庸st活am怕p(Q)迎is说t利hela慌rg花es欠tti磁me需-s鸽ta价mp柔o掉f盐an关y锦tr盐an炭sa恋ct迈io达n陡th捞at强e构xe标cu怒te绞dwr壳it博e(Q)滥su构cc勉es抢sf日ul怀ly度.R-狐ti屈me指st仗am近p(Q)厚is弄t养hela翅rg她es针tti宗me叨-s役ta附mp狠o彻f茫an分y捕tr领an恋sa袋ct喝io进n管th较at赏e俯xe栋cu嘉te臣dre付ad(Q)切su亮cc屠es勤sf房诚ul看ly干.四耍基于姥时间潮戳的辽协议4-亡1什么席是时结间戳扑协议独？4.嘉1数据羊项的抹时间垦戳Ti炎me丈st泻am坦p-喂Ba驶se没d却Pr菊ot弱oc翻ol句s-规则芝说明Th征e侮ti旨me命st薪am科p蚁or申de踏ri烈ng局p脑ro索to灭co刻len誉su顽re尤sth给at伴a康ny比c子on执fl扒ic它ti门ngre重adan页dwr乓it房诚eop云er贫at骄io喜ns插a膨re仇e裁xe患cu洗te订d时in福t舟im珍es接ta驼mp姓o铃rd率er牲.协议动规则哀说明颜：读数胡据的艰处理:湾Su膨pp泻os尘ea拐tr滴an妙sa脚ct物io董n汪Tiis蔬su锈es屋are育ad(Q)1）IfTS歼(Ti)W-t秤im敌es该ta态mp纪(Q),途t幕he苹nTine化ed慌s棒to应r尚ea宏d罗a此va河lu托e铅ofQth春at缴w校asal差re捷ad肝yov始er汉wr疑it堂te超n.老事苏务Ti读到熊新事迷务写字的数昨据-异常He碰nc城e,符th咐ere菌adop唐er烧at刻io讨n桐isre慢je极ct炮ed,扩an划dTiis贞r害ol衰le忠dba梯ck撕.2）IfTS尝(Ti)W-t兆im倒es狡ta馅mp乔(Q),活t敏he揉n崖th碎ere辽adop惹er羞at冒io部n涨is损e躬xe劲cu扁te删d,an丈dR-提ti惑me滴st西am否p(Q)isse龄t西toma临x(R便-t叔im站es舱ta冷mp险(Q),TS墙(Ti))假.新事炎务Ti读老器事务闹写的抱数据-O脊K写数义据的处尸理:直观秀例示杜（例子）4-超2时间邻戳协稀议为蠢何能捷保持鹿可串葡行化确？4.右2时间仿戳协及议规柳则Ti敲me拒st吗am答p-柿Ba李se黑d档Pr絮ot听oc伍ol翁s-规则幻玉说明(续)写数加据的烤处理淡：Su也pp匀os萝eth妖at瓣t糠ra发ns赠ac质ti误onTiis育su横eswr茅it则e(Q).1）IfTS妹(Ti)包<R-t美im搜es席ta义mp符(Q),滔t笛he座n曾th驴e讽va侮lu牺e辈ofQth认atTiis匆p悄ro笛du执ci坝ng光w版as无n竿ee启de扛d蜜pr穴ev仰io铅us任ly险,姻an撇d鸡th箭e文sy属st幅emas残su大me反dth瓜atva脱lu铜ewo妖ul敬d仓ne裹ve具r访bepr逗od天uc索ed蜡.新事突务未电能读抵到老锡事务Ti写的下数据-异常He归nc疮e,饶t嚼hewr押it倒eop姿er灭at古io闯n呼isre脸je抱ct苦ed,我an脏dTiis植r饱ol鄙le柿d钩ba雨ck文.2）IfTS使(Ti)规<W-t从im沾es芳ta殃mp怠(Q),离t胳he堵nTiis呈a制tt坦em每pt烘in蜓g永to茎w箱ri圈te期a案nob校so药le锐te已过抚时的va骗lu蔑eofQ.若老皇事务Ti再次碍读自锡己所雄写Q,必误很读-异常He结nc胸e,外t泡hi牛swr缓it伴eop钳er位at锈io哗n帖isre嗽je滋ct补ed,斜an蔽dTiis抽r左ol唱le厨d扣ba仰ck窜.3)惊Ot困he尊rw岛is诉e,把th某ewr佳it被eop暖er蝴at室io怀n催is祖e勤xe访cu违te悲d,瓶a慎nd却W使-t糕im咏es爸ta茅mp饶(Q)is氧s赌et蹲t功oTS搂(Ti).新事垮务Ti在老蒜事务块读写助后进乖