OS之分布式系统中的同步问题.ppt

分布式系统中同步问题分布式系统中同步问题一、时钟同步一、时钟同步分布式系统特点：分布式系统特点：相关的信息分布在多台机器上相关的信息分布在多台机器上没没有有共共享享内内存存进进程程只只根根据据本本地地可可用用的的信信息息做做出决策出决策系系统统中中不不存存在在公公共共时时钟钟或或其其它它精精确确的的全全局局时时间源间源在集中式系统中，时间是很明确的在集中式系统中，时间是很明确的 时钟同步时钟同步例子例子UNIX的的Make，检查文件最后修改时间，检查文件最后修改时间创创建建input.o后后，源源input.C修修改改了了，要要重重新新编译编译input.C设设 ouput.o的的 修修 改改 时时 间间 是是 2000。创创 建建output.o后即修改了源后即修改了源output.c但但编编辑辑output.c的的机机器器时时钟钟慢慢，修修改改后后output.c时间被时间被1999make不不会会重重新新编编译译output.c，程程序序的的运运行行会出现问题会出现问题二、逻辑时钟二、逻辑时钟(1)只只关关心心时时钟钟内内部部一一致致性性，不不关关心心时时钟钟是是否否与与实际时间一致实际时间一致1978年年Lamport指指出出，系系统统中中的的时时钟钟并并不不需要绝对的同步需要绝对的同步重重要要的的不不是是进进程程有有完完全全一一致致的的时时间间，而而是是事事件发生的先后次序要一致件发生的先后次序要一致二、逻辑时钟二、逻辑时钟(2)发生之前（发生之前（happens-beforehappens-before）关系定义）关系定义表达式表达式a b读作读作“a发生在发生在b前前”即即所所有有进进程程都都认认为为事事件件a先先发发生生，然然后后才才发发生事件生事件b事件事件a，有一个时间值，有一个时间值C（a）如如果果a和和b是是同同一一进进程程中中的的事事件件，而而且且a发发生生在在b前前那么那么a b为为true,C（a）C（b）二、逻辑时钟二、逻辑时钟(3)传递性传递性 Happens-before关系具有传递性关系具有传递性 如如果果a b和和b c都都成成立立，a c也也成成立立并发事件：并发事件：如如果果事事件件x和和y发发生生在在不不同同的的进进程程中中，且且这这两两进程间不交换信息进程间不交换信息 那那么么x y和和y x都都不不成成立立。这这两两个个事事件件就就称为并发事件称为并发事件并并发发意意味味着着两两个个事事件件发发生生时时，无无法法确确定定哪哪个个事件先发生，或者说不需要考虑此事事件先发生，或者说不需要考虑此事时时钟钟时时间间C必必须须向向前前（不不断断增增加加），不不能能后后退（减小）退（减小）对对时时间间的的更更新新，只只能能是是在在时时钟钟上上加加一一个个正正数数，不能减正数不能减正数Lamport算法算法(1)：例子说明例子说明(1)三三个个进进程程运运行行在在不不同同的的有有自自己己时时钟钟的的机机器器上上，每个时钟按自己的速度运行每个时钟按自己的速度运行可可以以看看到到，进进程程0中中时时钟钟有有6次次嘀嘀嗒嗒时时，进进程程1已经有了已经有了8次，而进程次，而进程2已经有了已经有了10次次Lamport算法算法(2)：设设，计计时时器器每每秒秒生生成成60次次中中断断，每每次次中中断断称称为一个时钟嘀嗒为一个时钟嘀嗒从从进进程程2发发送送该该进进程程1的的消消息息C，其其发发送送时时刻刻为为60，到达时刻为，到达时刻为56同同样样，从从进进程程1到到进进程程0的的消消息息D，其其发发送送时时刻为刻为64，到达时刻为，到达时刻为54这这显显然然是是不不可可能能的的，也也是是必必须须避避免免出出现现的的情情况况例子说明例子说明(2)Lamport算法算法(3)：消消息息c的的发发送送时时间间为为60，它它的的到到达达时时间间一一定定在时刻在时刻61或或61之后之后让每条消息都携带发送者时钟的发送时刻让每条消息都携带发送者时钟的发送时刻当当消消息息到到达达接接收收时时，如如果果接接收收者者的的时时钟钟指指示示值先于发送消息的时间值先于发送消息的时间接接受受者者的的时时钟钟值值就就应应快快于于消消息息发发送送时时刻刻加加1之后时间值之后时间值例子说明例子说明(3)Lamport算法算法(4)：Lamport算法算法(5)：两个事件之间，时钟至少应间隔一个嘀嗒两个事件之间，时钟至少应间隔一个嘀嗒如如果果一一个个进进程程依依次次快快速速发发送送或或接接收收两两条条消消息息，就必须调整时钟就必须调整时钟使两个事件之间（至少）间隔一个时钟嘀嗒使两个事件之间（至少）间隔一个时钟嘀嗒附附加加条条件件,没没有有两两个个事事件件是是精精确确地地在在同同一一时时刻发生的：刻发生的：1.在同一进程中，如果在同一进程中，如果a在在b前面发生，前面发生，那么那么C(a)C(b)2.如果如果a与与b分别代表消息的发送和接收，分别代表消息的发送和接收，那么那么C(a)C(b)3.对于所有的事件对于所有的事件a与与b而言，而言，C(a)C(b)Lamport算法算法(6)：算法给出系统中所有事件的整体定序方法算法给出系统中所有事件的整体定序方法该算法在学术界中得到广泛认同该算法在学术界中得到广泛认同Lamport算法算法(7)：三、时钟三、时钟(1)在在某某些些系系统统中中，实实际际的的时时钟钟时时间间非非常常重重要要，需要物理时钟需要物理时钟如何使物理时钟与世界的时钟同步？如何使物理时钟与世界的时钟同步？物理时间之间如何保持同步？物理时间之间如何保持同步？原子钟可以准确度量时间原子钟可以准确度量时间世世界界时时（Universal Coordinated Time）简称简称UTCUTC是现代计时的基础是现代计时的基础National Institute of Standard TimeNIXT,国家标准时间组织短波电台，国家标准时间组织短波电台，WWV每每个个UTC秒秒的的起起始始时时刻刻，WWV就就发发送送一一个个短脉冲短脉冲WWV本身的误差大约为本身的误差大约为+-1毫秒毫秒物理时钟物理时钟(2)四、时钟同步算法四、时钟同步算法如果某台机器有如果某台机器有WWV接收器接收器时时钟钟同同步步的的目目的的是是使使其其它它机机器器与与这这台台机机器器同同步步时钟同步算法的基本模型时钟同步算法的基本模型(1)设设每每台台机机器器都都有有个个计计时时器器，该该计计时时器器每每秒秒中中断断H次次计计时时器器溢溢出出时时，中中断断处处理理程程序序就就将将软软件件时时钟钟加加1软软件件时时钟钟是是从从过过去去某某一一已已知知时时间间开开始始所所经经历历的的tick数数这这个个时时钟钟的的值值称称为为C。当当UTC时时间间为为t时时，机机器器p的时钟值为的时钟值为Cp(t)理想情况下理想情况下dC/dt应为应为1理理论论上上，当当H=60时时，计计时时器器应应每每小小时时生生成成216,000次次ticks实实际际上上，计计时时器器芯芯片片的的相相对对误误差差大大约约为为10-5，即即 每每 小小 时时 的的 tick数数 的的 范范 围围 为为 215,998到到216,002 准确地说，如果存在一个常数准确地说，如果存在一个常数p 1-dC/dt 1+成立，就可以认为计时器是正常工作的成立，就可以认为计时器是正常工作的时钟同步算法的基本模型时钟同步算法的基本模型(2)如果两个时钟偏离如果两个时钟偏离UTC的方向相反的方向相反那么在同步之后的那么在同步之后的t时刻时时刻时它们的时差为它们的时差为2 t要保证两个时钟间时间差不超过要保证两个时钟间时间差不超过必须至少每隔必须至少每隔/2秒重新同步秒重新同步Cristian算法算法(1)某台机器拥有某台机器拥有WWV接收器的系统的算法接收器的系统的算法时时钟钟同同步步的的目目的的就就是是使使其其它它机机器器与与有有WWV接收器的机器保持同步接收器的机器保持同步有有WWV接接收收器器的的机机器器称称为为时时间间服服务务器器（time server）Cristian算法算法(2)系系统统中中每每台台机机器器至至少少每每隔隔/2秒秒就就向向时时间间服服务器发送一条消息务器发送一条消息 查询当前时间查询当前时间服服务务器器尽尽快快将将携携带带当当前前时时间间CUTC的的消消息息返返回回给请求者给请求者一种近似方法一种近似方法 发发送送者者得得到到时时间间服服务务器器的的响响应应后后，直直接接将将其其时钟值设置为时钟值设置为CUTCCristian算法算法(3)笫一个问题：时间决不能倒退笫一个问题：时间决不能倒退 如果这个请求发送者的时钟比实际时间快如果这个请求发送者的时钟比实际时间快 这这时时仅仅将将CUTC设设置置为为时时钟钟的的当当前前值值会会引引起起严严重问题重问题Cristian算法算法(4)对时钟的调整必须逐步进行对时钟的调整必须逐步进行一种方法：假设计时器每秒中断一种方法：假设计时器每秒中断100次次 正正常常情情况况下下，每每次次中中断断将将时时钟钟时时间间增增加加10毫毫秒秒 如如果果要要使使时时钟钟慢慢下下来来，中中断断程程序序就就每每次次只只将将时间增加时间增加9 直到将时间矫正过来为止直到将时间矫正过来为止Cristian算法算法(5)同样，每次中断时将时间加同样，每次中断时将时间加11毫秒，毫秒，就会逐渐将时钟调快，就会逐渐将时钟调快，而不应直接将时钟值设快而不应直接将时钟值设快Cristian算法算法(6)第二个问题第二个问题 时时间间服服务务器器将将当当前前时时间间发发送送给给查查询询时时间间的的机机器需要时间器需要时间 这个延迟时间可能会很长，而且它也在变化这个延迟时间可能会很长，而且它也在变化 Cristian的的处处理理方方法法就就是是计计算算出出准准确确的的延延迟迟时间时间 为为了了提提高高估估计计值值的的准准确确性性，建建议议要要进进行行一一系系列的测量列的测量Berkeley UNIX算法算法(1)时时间间服服务务器器是是活活动动的的，它它定定期期向向其其他他机机器器查查询这些机器的时间询这些机器的时间根根据据得得到到的的响响应应，时时间间服服务务器器计计算算出出一一个个平平均值均值并通知其它机器调整其时钟并通知其它机器调整其时钟Berkeley UNIX算法算法(2)重复这个过程，直到达到一定的缩减量为止重复这个过程，直到达到一定的缩减量为止这这种种方方法法适适用用于于那那些些没没有有WWV接接收收器器的的系系统统在在这这样样的的系系统统中中，操操作作员员必必须须阶阶段段性性地地手手工工设置时间的时间设置时间的时间五、互斥问题五、互斥问题在分布式系统中，临界区和互斥如何实现在分布式系统中，临界区和互斥如何实现1.集中式算法集中式算法在在分分布布式式系系统统中中，实实现现互互斥斥的的最最简简单单算算法法是是模拟单处理机的情形模拟单处理机的情形集中式算法基本思路集中式算法基本思路一个进程作为协调者一个进程作为协调者其他进程要进入临界区须先发出请求消息其他进程要进入临界区须先发出请求消息 说明要进入哪一个临界区说明要进入哪一个临界区如果在那个临界区中，当前没有其他进程如果在那个临界区中，当前没有其他进程 那么协调者就发出批准那么协调者就发出批准当批准到达请求的机器后当批准到达请求的机器后 发出请求的进程就进入临界区发出请求的进程就进入临界区集中式算法评价集中式算法评价显然本算法中由协调者保证互斥显然本算法中由协调者保证互斥算法是公平的算法是公平的因因为为按按收收到到请请求求的的先先后后顺顺序序，考考虑虑是是否否发发出出回答回答不会出现有某个进程永远等待的现象不会出现有某个进程永远等待的现象算法的缺点，协调者是一个单点失效的机制算法的缺点，协调者是一个单点失效的机制 如如果果协协调调者者垮垮台台了了，是是“不不允允许许”呢呢，还还是是它自身垮台了呢？它自身垮台了呢？2.分布式算法分布式算法(1)Richart与与Agrawala(R&A)算法算法要求在系统中，对所有事件安排一个次序要求在系统中，对所有事件安排一个次序进程在进入临界区之前，先构造一条消息进程在进入临界区之前，先构造一条消息消消息息中中包包含含有有要要进进入入的的临临界界区区的的名名称称、进进程程编号以及当前时间编号以及当前时间把该消息发给所有其他的进程把该消息发给所有其他的进程分布式算法分布式算法(2)为为简简单单起起见见，假假定定消消息息的的发发送送是是可可靠靠的的，每每一进程都认可收到了此消息一进程都认可收到了此消息各个进程依据情况，发回消息各个进程依据情况，发回消息如如果果接接受受方方不不在在临临界界区区中中并并且且也也不不想想进进入入，那么发出那么发出OK如如果果接接受受方方已已在在临临界界区区内内，那那么么不不应应答答，并并把该消息放到队列中把该消息放到队列中如果接受方也想进临界区，但还没有进入如果接受方也想进临界区，但还没有进入 比较收到的消息和自己发出消息的时间戳比较收到的消息和自己发出消息的时间戳分布式算法分布式算法(3)如果收到消息中的时间戳早，则发出如果收到消息中的时间戳早，则发出OK如如果果自自己己的的消消息息较较早早，那那么么不不发发消消息息，并并把把请求送入队列请求送入队列请请求求的的进进程程要要等等到到所所有有其其他他进进程程回回送送允允许许消消息为止息为止当当所所有有的的允允许许消消息息都都到到达达后后，该该进进程程就就可可以以进入申请的临界区进入申请的临界区退退出出临临界界区区后后，该该进进程程向向在在其其队队列列中中的的所所有有其他进程发出其他进程发出OK分布式算法分布式算法(4)算法关键算法关键 当发生有冲突的申请时当发生有冲突的申请时 所有进程均同意有小时间戳一方取胜所有进程均同意有小时间戳一方取胜分布式算法评价分布式算法评价算法中不存在单点失效算法中不存在单点失效 却出来了多点失效却出来了多点失效一个进程垮台后，它不响应外来的请求一个进程垮台后，它不响应外来的请求 还阻塞了后续试图进入临界区的进程还阻塞了后续试图进入临界区的进程该该算算法法仅仅使使出出错错概概率率增增大大了了，而而且且还还要要占占用用大量网络资源大量网络资源分布式算法评价分布式算法评价(2)补救方法，在发送方设置有超时的反应机制补救方法，在发送方设置有超时的反应机制该机制不断询问直到有一个回答收到该机制不断询问直到有一个回答收到或或者者在在经经过过一一段段设设定定的的时时间间段段后后，得得出出结结论论，接收方有故障接收方有故障这个算法，速度慢，复杂，开销也大这个算法，速度慢，复杂，开销也大但至少表明了，分布式算法是可行的但至少表明了，分布式算法是可行的3.令牌环网算法令牌环网算法(1)一一个个分分布布式式系系统统，内内部部的的进进程程构构成成了了一一个个逻逻辑上的环形网辑上的环形网所有的进程都知道它的后续者是谁所有的进程都知道它的后续者是谁设令牌从进程设令牌从进程k传到进程传到进程k+1沿环传递沿环传递当当进进程程得得到到令令牌牌后后，首首先先看看是是否否需需要要进进入入临临界区界区如如果果需需要要，进进程程进进入入临临界界区区，进进行行所所需需的的操操作作在撤出临界区后，该进程让令牌沿环传递在撤出临界区后，该进程让令牌沿环传递令牌环网算法令牌环网算法(2)本本算算法法规规定定，进进程程不不允允许许用用同同一一张张令令牌牌进进入入第二个临界区第二个临界区如如果果一一个个进进程程得得到到了了令令牌牌，但但不不打打算算进进入入临临界区界区 那么它就继续传递令牌那么它就继续传递令牌如如果果没没有有进进程程想想进进入入临临界界区区，令令牌牌则则沿沿着着环环路高速循环路高速循环令牌环网算法评价令牌环网算法评价(1)算法的正确性是明显的算法的正确性是明显的因为任何时刻，只有一个进程持有令牌因为任何时刻，只有一个进程持有令牌在临界区中只可能有一个进程在临界区中只可能有一个进程由由于于巳巳经经规规定定好好令令牌牌传传递递次次序序，所所以以不不可可能能发生死锁发生死锁最最坏坏情情况况是是，排排在在最最后后的的进进程程要要等等到到其其他他进进程程都都进进入入临临界界区区，完完成成操操作作，并并离离开开之之后后，才轮到它才轮到它令牌环网算法评价令牌环网算法评价(2)算法的问题算法的问题 如如果果令令牌牌因因为为某某种种原原因因丢丢失失了了，就就必必须须重重新新生成一个生成一个但是如何探测令牌是否丢失，却是一件难事但是如何探测令牌是否丢失，却是一件难事令令牌牌在在一一小小时时之之内内没没有有传传递递，不不意意味味着着丢丢失失了，可能某个进程还在使用它了，可能某个进程还在使用它令牌环网算法评价令牌环网算法评价(3)另另一一个个问问题题，如如果果某某个个进进程程垮垮台台了了，算算法法也也会碰到麻烦会碰到麻烦补救方法，进程收到令牌后，给予认可补救方法，进程收到令牌后，给予认可在进程试图把令牌递交给邻居后在进程试图把令牌递交给邻居后 如如果果在在规规定定时时限限内内没没有有认认可可回回答答，就就判判定定该该邻居是死进程邻居是死进程于是令牌越过死进程，传到下一个进程中于是令牌越过死进程，传到下一个进程中六、典型选举算法：威力六、典型选举算法：威力(Bully)算法算法分布式系统需要有一个进程担当协调者分布式系统需要有一个进程担当协调者完成一些特别的工作任务完成一些特别的工作任务如何选择进程来担当协调者如何选择进程来担当协调者威力威力(Bully)算法算法(1)假定每台机器只有一个进程假定每台机器只有一个进程 每一进程都有一个单独的编号每一进程都有一个单独的编号还假定每一进程都了解其他进程的编号还假定每一进程都了解其他进程的编号选举算法的目的选举算法的目的 试试图图挑挑出出一一个个具具有有最最高高进进程程编编号号的的进进程程，委委任它为协调者任它为协调者确确认认如如下下规规则则，当当选选举举开开始始以以后后，它它会会得得出出结论结论威力威力(Bully)算法算法(2)所所有有的的进进程程都都同同意意某某个个进进程程将将担担任任新新的的协协调调者者当当某某一一个个进进程程P，发发现现协协调调者者不不再再响响应应请请求求后后 它积极发起一场竞选活动它积极发起一场竞选活动P，掌握着一场选举，掌握着一场选举威力威力(Bully)算法算法(3)规则：规则：首首先先，P发发出出选选举举消消息息给给所所有有比比它它更更高高级级别别编号的进程编号的进程其其次次，如如果果没没有有响响应应者者，那那么么P就就赢赢得得这这场场选举，成为新的协调者选举，成为新的协调者最后，如果更高编号中有一个进程响应最后，如果更高编号中有一个进程响应 那么这个更高编号的进程就赢得选举那么这个更高编号的进程就赢得选举 P也就完成了使命也就完成了使命威力威力(Bully)算法算法(4)一一个个进进程程可可能能从从小小编编号号的的进进程程中中收收到到选选举举消消息息这时，这个接收进程回送这时，这个接收进程回送OK消息给发送方消息给发送方从而表明它将接管选举工作从而表明它将接管选举工作接接收收方方大大员员然然后后掌掌管管这这场场选选举举活活动动，向向其其它它进程发出消息进程发出消息宣宣布布取取得得了了选选举举胜胜利利，并并开开始始其其协协调调者者的的工工作作威力威力(Bully)算法算法(5)如果有一个最高级编号进程在运行如果有一个最高级编号进程在运行它肯定会赢得选举并接管协调者的工作它肯定会赢得选举并接管协调者的工作最有势力的大亨总是取得胜利最有势力的大亨总是取得胜利小伙计可能是白忙一场小伙计可能是白忙一场这就是称之为这就是称之为“威力威力(Bully)算法算法”的原因的原因七、原子事务七、原子事务原子事务来自于商业领域原子事务来自于商业领域双双方方在在方方签签字字前前，可可以以自自由由退退出出，没没有有任何责任任何责任但但是是签签字字之之后后，就就无无法法再再反反悔悔了了，交交易易就必须进行下去就必须进行下去要么全部完成，要么全部取消要么全部完成，要么全部取消对主控磁带修改的可容错系统对主控磁带修改的可容错系统早期计算机事务处理早期计算机事务处理修改在线数据库的银行应用程序修改在线数据库的银行应用程序(1)客客户户利利用用一一台台带带有有调调制制解解调调器器的的PCPC机机呼呼叫银行服务叫银行服务打打算算从从一一个个帐帐户户中中提提取取钱钱存存入入另另一一个个帐帐户中户中操作分两步完成：操作分两步完成：提款（数量，帐户提款（数量，帐户1 1）存款（数量，帐户存款（数量，帐户2 2）修改在线数据库的银行应用程序修改在线数据库的银行应用程序(2)如果在第一个操作完成后如果在第一个操作完成后第二个操作开始前电话连接被中断第二个操作开始前电话连接被中断这笔钱已被记入第一个帐户的借方这笔钱已被记入第一个帐户的借方但是还没有记入第二个帐户贷方中但是还没有记入第二个帐户贷方中这笔钱就消失了这笔钱就消失了 修改在线数据库的银行应用程序修改在线数据库的银行应用程序(3)两两个个操操作作组组合合在在一一个个原原子子事事务务中中就就可可以以解解决这个问题决这个问题两两个个操操作作要要么么全全部部完完成成，要要么么一一个个也也不不执行执行关关键键是是在在事事务务失失败败时时，能能回回复复到到事事务务执执行前的初始状态行前的初始状态这是原子事务必须提供的功能这是原子事务必须提供的功能1.事务模型事务模型三类存储器三类存储器第一类第一类RAMRAM内存内存 在关机或机器崩溃时都要清除在关机或机器崩溃时都要清除RAMRAM内存的内容内存的内容第二类磁盘存储器第二类磁盘存储器 不不受受CPUCPU执执行行失失败败的的影影响响，但但是是磁磁头头破破坏坏后后也会丢失数据也会丢失数据最后一类稳定存储器最后一类稳定存储器除除了了重重大大事事故故如如自自然然界界中中的的洪洪水水和和地地震震外外,其其它原因都无法破坏稳定器中的内容它原因都无法破坏稳定器中的内容aastofhwaastofhw12aastofhwaastofhw12aastofhwaastofhw驱动器驱动器 1驱动器驱动器 2不良校验和不良校验和稳定存储器稳定存储器(a)(b)(c)稳定存储器的实现稳定存储器的实现(1)可以用一对普通的磁盘实现可以用一对普通的磁盘实现驱驱动动器器2 2每每个个扇扇区区是是驱驱动动器器1 1相相应应扇扇区区的的完全备份完全备份修修改改某某个个扇扇区区时时，首首先先更更新新1 1中中的的相相应应扇扇区并加以验证区并加以验证其次再更新验证其次再更新验证2 2中的相应扇区中的相应扇区稳定存储器的实现稳定存储器的实现(2)假定在修改假定在修改1 1之后，修改之后，修改2 2之前系统崩溃之前系统崩溃系系统统恢恢复复时时，可可以以逐逐个个比比较较两两个个驱驱动动器器中中的扇区的扇区 对应的两个扇区内容不同时对应的两个扇区内容不同时 可以假定驱动器可以假定驱动器1 1的内容是正确的的内容是正确的将正确内容从驱动器将正确内容从驱动器1 1复制到驱动器复制到驱动器2 2 恢恢复复过过程程结结束束之之后后，两两个个驱驱动动器器的的内内容容再再次保持一致次保持一致 稳定存储器的实现稳定存储器的实现(3)潜在的问题潜在的问题扇区损坏扇区损坏,灰尘或通常的磨损，划痕灰尘或通常的磨损，划痕出出现现错错误误时时，从从另另一一个个驱驱动动器器中中扇扇区区重重新生成内容新生成内容 稳定存储器用于高度容错性的应用稳定存储器用于高度容错性的应用将数据写入稳定存储器将数据写入稳定存储器并读出检查其书写正确后并读出检查其书写正确后数据被丢失的可能性就很小数据被丢失的可能性就很小 事务原语事务原语(1)原语由操作系统或语言的运行系统提供原语由操作系统或语言的运行系统提供原语的例子：原语的例子：BEGIN-TRANSACTION-BEGIN-TRANSACTION-开始一个事务命令开始一个事务命令 END-TEANSACTION-END-TEANSACTION-结束并提供事务的命令结束并提供事务的命令 ABORT-TRANSACTION-ABORT-TRANSACTION-中断事务；恢复原先数据中断事务；恢复原先数据 READ-READ-从文件从文件 (或其它对象中或其它对象中)读取数据读取数据 WEITE-WEITE-向文件向文件 (或其它对象或其它对象)写入数据写入数据 事务原语事务原语(2)原语集合由对象类型决定原语集合由对象类型决定在邮件系统中在邮件系统中 应该有发送，接收和转交邮件的原语应该有发送，接收和转交邮件的原语帐务系统中帐务系统中 READREAD和和WRITEWRITE是很典型的例子是很典型的例子 事务原语事务原语(3)航班订票系统航班订票系统BEGIN-TRANSACTION BEGIN-TRANSACTION保留保留 WP-JFK;保留保留 WP-JFK;保留保留JFK-Nairobi;保留保留JFK-Nairobi;保留保留Nairobi-Malindi;Nairobi-Malindi=ABORT-TRANSACTION;END-TRANSACTION END-TRANSACTION事务原语属性事务原语属性(1)三个必要属性：三个必要属性：序列化序列化 -并发的事务互不干扰并发的事务互不干扰 原原子子性性 -对对外外界界来来说说，事事务务的的执执行行是是不不可分割可分割 永永久久性性 -一一旦旦事事务务被被执执行行，它它所所做做的的修修改就永久生效改就永久生效 事务原语属性事务原语属性(2)事务第一个属性，序列化事务第一个属性，序列化保证两个或多个事务同时运行时保证两个或多个事务同时运行时对它们自己及其它进程而言对它们自己及其它进程而言最后的结果与这些事务按照某种次序次序最后的结果与这些事务按照某种次序次序与系统有关顺序运行时的结果一致与系统有关顺序运行时的结果一致 事务原语属性事务原语属性(3)第二个关键属性，原子性第二个关键属性，原子性每个事务要么全部发生，要么都不发生每个事务要么全部发生，要么都不发生如如果果事事务务发发生生，它它的的发发生生就就是是一一个个不不可可分割的瞬时动作分割的瞬时动作事事务务进进展展过过程程中中，其其它它进进程程都都看看不不到到事事务发生的中间状态务发生的中间状态 事务原语属性事务原语属性(3)第三个属性，永久性第三个属性，永久性一旦事务被提交一旦事务被提交,无论这时发生什么无论这时发生什么事务都会进行下去事务都会进行下去,其结果永久生效其结果永久生效 嵌套事务嵌套事务事务可以包含子事务事务可以包含子事务,子事务称为嵌套事务子事务称为嵌套事务 假定一个事务并行启动多个子事务假定一个事务并行启动多个子事务其中一个子事务已经提支其中一个子事务已经提支其操作结果在父事务中已经生效其操作结果在父事务中已经生效 在继续时，父事务被终止在继续时，父事务被终止要将整个系统恢复到顶层事务启动前的状态要将整个系统恢复到顶层事务启动前的状态 结果结果:已经提交的子事务的结果也必须被恢复已经提交的子事务的结果也必须被恢复 事务永久性就只适用于顶层事务了事务永久性就只适用于顶层事务了 事务管理措施事务管理措施 任何事务或子事务启动时任何事务或子事务启动时提供系统中所有对象私存拷贝，供其操作提供系统中所有对象私存拷贝，供其操作 如如果果事事务务被被终终止止，私私有有空空间间消消失失，好好象象从从没没存存在过在过 如如果果提提交交事事务务，该该事事务务私私有有空空间间代代替替父父事事务务私私有空间有空间 在提交一子事务后启动一新的子事务在提交一子事务后启动一新的子事务第二个子事务能看到第一个子事务执行结果第二个子事务能看到第一个子事务执行结果 2.原子事务实现原子事务实现-私有工作空间私有工作空间(1)第一种方法：在实例启动事务时第一种方法：在实例启动事务时为该进程提供一个实际的私有工作空间为该进程提供一个实际的私有工作空间 120 012索引索引自由块自由块120 03012原始索引原始索引012312 00123 3私有私有工作空间工作空间磁盘磁盘(a)(b)(c)私有工作空间私有工作空间(2)优化基础：读文件优化基础：读文件进程读文件，不修改该文件进程读文件，不修改该文件不需要这个文件的私有拷贝不需要这个文件的私有拷贝 只只要要使使用用实实际际的的文文件件即即可可（除除非非修修改改该该文文件）件）进程启动事务时，进程启动事务时，建建立立包包含含指指向向父父进进程程工工作作空空间间的的反反向向指指针针，空的私有工作空间空的私有工作空间私有工作空间私有工作空间(2)优化基础：写操作优化基础：写操作不不将将整整个个文文件件复复制制到到私私有有工工作作空空间间，只只复制文件的索引复制文件的索引首首次次修修改改一一个个文文件件块块时时，先先要要复复制制该该文文件件块块，然然后后将将复复制制块块的的地地址址插插入入文文件件索索引引复制后的新块有时称为影像块复制后的新块有时称为影像块 原子事务实现原子事务实现-写前日志写前日志(1)修修改改文文件件前前，先先在在稳稳定定存存储储器器日日志志上上写写入一个记录入一个记录 说明是哪个事务做的修改说明是哪个事务做的修改 正在修改哪个文件夹哪个块正在修改哪个文件夹哪个块 修改前和修改后的值修改前和修改后的值 只只有有在在正正确确完完成成日日志志的的写写操操作作之之后后，才才修改文件修改文件 x=0;y=0;Begin_transaction x=x+1;y=y+2;x=y*y;End_transcationx=0/1日志日志x=0/1日志日志y=0/2x=0/1日志日志y=0/2x=0/4(a)(b)(c)(d)写写前前日日志志原子事务实现原子事务实现-写前日志写前日志(1)事务成功地执行完毕并被提交之后事务成功地执行完毕并被提交之后要在日志中写入一个提交记录要在日志中写入一个提交记录如如果果终终止止事事务务，就就可可以以利利用用日日志志恢恢复复系系统的原始状态统的原始状态回回溯溯:从从最最后后一一条条日日志志记记录录开开始始向向前前，读读出出每每条条记记录录，取取消消该该记记录录中中描描述述的的操操作作 日志还可以用于从系统崩溃中恢复执行日志还可以用于从系统崩溃中恢复执行两段提交协议两段提交协议(1)两两段段提提交交协协议议(Gray,(Gray,1978)1978)使使用用最最广广泛泛的一种协议的一种协议 包含有关功能的一个进程作为协调者包含有关功能的一个进程作为协调者通常是执行事务的进程通常是执行事务的进程 两段提交协议两段提交协议(2)协调者写一条日志记录协调者写一条日志记录说明它要开始提交协议说明它要开始提交协议然然后后向向事事务务中中包包含含的的其其它它进进程程（从从属属）发送消息发送消息通知这些进程准备提交通知这些进程准备提交 在日志文件中写在日志文件中写“prepare”发送发送“prepare”消息消息收录所有回答收录所有回答写日志记录写日志记录发送发送“Commit”消息消息第一阶段第一阶段第第二二阶段阶段在日志文件中写在日志文件中写“Ready”发送发送“Ready”消息消息发送发送“Finished”消息消息在日志文件中写在日志文件中写“Commit”承诺承诺成功执行的两段提交协议成功执行的两段提交协议协调者协调者子协调子协调两段提交协议两段提交协议(3)从属进程接到消息后从属进程接到消息后检查自己是否就绪检查自己是否就绪将结果写入日志将结果写入日志并发送它的决定并发送它的决定 协调者接收到所有从属进程的响应后协调者接收到所有从属进程的响应后就可以确定提交还是终止事务就可以确定提交还是终止事务 两段提交协议两段提交协议(4)如果所有进程都已准备好提交如果所有进程都已准备好提交那么事务就提交那么事务就提交 如果有一个或几个进程不能提交如果有一个或几个进程不能提交事务中止事务中止 两段提交协议两段提交协议(5)无论提交或终止，协调者要写日志记录无论提交或终止，协调者要写日志记录将其决定知所有的从属将其决定知所有的从属 在在写写了了这这条条日日志志记记录录之之后后，才才真真正正地地提提交事务交事务 使使用用稳稳定定存存储储器器中中的的日日志志，协协议议在在崩崩溃溃时有较大的弹性时有较大的弹性 八、并发控制八、并发控制三种不同的并发控制算法三种不同的并发控制算法 1.并发控制并发控制-加锁加锁最古老也是最广泛使用的并发控制算法最古老也是最广泛使用的并发控制算法最简单的加锁形式最简单的加锁形式当进程在事务中要读或写某个文件时当进程在事务中要读或写某个文件时首先就为读文件加锁首先就为读文件加锁 加锁可以由单个集中式的锁管理器完成加锁可以由单个集中式的锁管理器完成也也可可以以在在每每台台机机器器上上利利用用本本地地的的锁锁管管理理器器管管理本地文件理本地文件锁管理器都维护一个被锁定文件的列表锁管理器都维护一个被锁定文件的列表用于拒绝其它进程试图锁定已加锁文件用于拒绝其它进程试图锁定已加锁文件 文文件件的的锁锁通通常常由由事事务务系系统统获获取取和和释释放放，不不需需要编程人员的处理要编程人员的处理 并发控制并发控制-加锁的改进加锁的改进方案太严格方案太严格可以通区分读操作锁和写操作锁可以通区分读操作锁和写操作锁改进改进读操作锁读操作锁为某文件设置了读操作锁为某文件设置了读操作锁仍允许为该文件设置其它的读操作锁仍允许为该文件设置其它的读操作锁读读操操作作锁锁用用于于保保证证读读文文件件的的过过程程中中文文件件不会被修改不会被修改但是没有理由拒绝其它事务读这个文件但是没有理由拒绝其它事务读这个文件写操作锁写操作锁锁定一个文件执行写操作时锁定一个文件执行写操作时不允许再为该文件设置任何类型的锁不允许再为该文件设置任何类型的锁 读读操操作作锁锁是是共共享享的的，而而写写操操作作锁锁是是互互斥斥的的 加锁的粒度加锁的粒度加锁的单位大小称为粒度加锁的单位大小称为粒度加锁的单位可是更小的单位加锁的单位可是更小的单位如单个的记录或页如单个的记录或页可能是更大的单位，如整个数据库可能是更大的单位，如整个数据库 粒粒度度越越细细，加加锁锁的的准准确确度度越越高高，能能够够达达到到的的并行性也更好，并行性也更好，细粒度的加锁操作需要更多的锁，代价更高细粒度的加锁操作需要更多的锁，代价更高而且更容易引起死锁而且更容易引起死锁 2.两段加锁方法两段加锁方法进程在它的成长阶段获取所需的全部锁进程在它的成长阶段获取所需的全部锁在收缩阶段释放这些锁在收缩阶段释放这些锁如如果果进进程程在在到到达达收收缩缩阶阶段段前前不不允允许许修修改改任何文件任何文件那那么么在在获获取取某某些些锁锁失失败败时时，可可以以直直接接释释放所有的锁放所有的锁稍待片刻后，再重断开始稍待片刻后，再重断开始 两段加锁两段加锁锁锁的的数数量量时间时间成长阶段成长阶段收缩阶段收缩阶段锁点峰锁点峰两段加锁方法被广泛应用的原因两段加锁方法被广泛应用的原因可可以以证证明明，如如果果所所有有事事务务都都使使用用两两段段加加锁方法锁方法那那么么将将这这些些事事务务交交叉叉后后形形成成的的时时间间表表是是序列化的序列化的严格的两段加锁机制严格的两段加锁机制收缩阶段在事务结束运行收缩阶段在事务结束运行而提交或终止之后才发生而提交或终止之后才发生 两段加锁的优点两段加锁的优点 每每个个事事务务读读到到的的值值都都是是由由已已经经提提交交的的事事务务修修改改过的值过的值不不会会因因为为基基于于一一个个还还不不能能使使用用的的文文件件的的原原因因，而终止该事务而终止该事务所有锁的分配和释放都由系统处理所有锁的分配和释放都由系统处理不需要事务了解这些过程：不需要事务了解这些过程：文件被访问时，系统为它加锁；文件被访问时，系统为它加锁；事务结束时，释放相关的锁事务结束时，释放相关的锁 避免了级连式的事务终止的情况发生：避免了级连式的事务终止的情况发生：由于使用了不该使用的文件而必须中止事务由于使用了不该使用的文件而必须中止事务 九、常用的避免死锁的方法九、常用的避免死锁的方法(1)以以某某种种规规范范的的顺顺序序分分配配锁锁，避避免免出出现现占占有一等待循环有一等待