分布式操作系统课件

第3章分布式系统的同步

中国科技大学软件学院丁箐1第3章分布式系统的同步中国科技大学软件学院1主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁2主要内容3.1时钟同步2主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁3主要内容3.1时钟同步33.1时钟同步分布式算法的特点相关信息散布在多个场地上每个进程只能基于本地信息做决定应避免因单点故障造成整个系统的失败不存在公共时钟或精确的全局时间43.1时钟同步分布式算法的特点4时钟同步问题例：makefile误差时间output.o：cc–Coutput.c5时钟同步问题例：makefile误差时间output.o：逻辑时钟计时器：石英晶体+计数器时钟偏差（clockskew）逻辑时钟：相对时间物理时钟：真实时间“之前”关系:事件a在b之前出现，则aba为发送消息m，b为接收m，则ab具有传递性：ab,bc,则ac并发事件（concurrent）6逻辑时钟计时器：石英晶体+计数器6Lamport算法对每一事件a，在所有进程中都认可给它分配一个时间值C(a）ifab;则C(a)<C(b)a,bC(a)C(b)C是递增的校正算法ab，ifC(b)<C(a),则C(b)=C(a)+17Lamport算法对每一事件a，在所有进程中都认可给它分配一Lamport算法时间慢快慢快8Lamport算法时间慢快慢快8物理时钟与现实时钟（1）如何用现实世界的时钟将它们同步起来；（2）如何使各时钟之间保持同步。

太阳日：连续的两次日中天的时间太阳秒：solar-day/86400平均太阳秒：如，格林威治时间9物理时钟与现实时钟（1）如何用现实世界的时钟将它们同步起来；现实时钟铯原子钟：9192631770次跃迁=1秒TAI秒：国际原子时间UTC秒：世界时间（在TAI秒中加入闰秒）时间服务：WWV电台、GEOS卫星102010现实时钟铯原子钟：9192631770次跃迁=1秒10201时钟同步算法如何与现实时钟同步如何使不同机器之间相互同步设机器时钟值Cp(t),t为UTC时间最大偏移率精确时钟：dC/dt=1快时钟：dC/dt〉1慢时钟：dC/dt<111时钟同步算法如何与现实时钟同步11Christian’s算法--逐步调整法时间服务器，可接受WWV的UTC时间每隔δ/2ρ校准时间（允许误差δ，存在误差ρ）两个问题：时间决不能倒退,延迟假设：每秒产生100次中断，每次中断将时间加10毫秒若调慢时钟，中断服务程序每次只加9毫秒；若加快时钟，则加11毫秒。传播时间12Christian’s算法--逐步调整法时间服务器，Berkeley算法–主动式方法时间监控器定期查询其他机器时间计算出平均值通知其他机器调整时间13Berkeley算法–主动式方法时间监控器定期查询其他平均值算法–非集中式方法将时间划分成固定长度的再同步间隔，第i次间隔开始于T0+iR，而结束于T0+(i+1)R所有机器广播自己的时钟时间启动本地计时器收集在S时间间隔中到达的其他机器广播的时间执行平均时间计算算法，得到新的时间值（取平均值，去掉两端值）14平均值算法–非集中式方法将时间划分成固定长度的再同步间隔多个外部时间源法例：OSFDCE方法接受所有时间源的当前UTC区间去掉与其他区间不相交的区间将相交部分的中点作为校准时间时间15多个外部时间源法例：OSFDCE方法时间15使用同步时钟最多一次消息提交每个消息携带一个ID和一个时间印ts（timestamp）服务器的表T中，记录每个连接C最近的时间印t如果到达的消息m，ts(m)<t,则拒绝m

服务器要一直保存一个全局变量G=CurrentTime–MaxLifetime–MaxClockSkew所有<G的时间印从表T中清除对于具有新的ID的到达消息m,如果ts(m)<G则拒绝m,否则，接受m按照一定时间间隔T，定期地将G写入磁盘。当系统重启后，G’=G+T16使用同步时钟最多一次消息提交服务器要一直保存一个全使用同步时钟基于时钟的缓存一致性当客户读取一个副本到缓存时，设置一个租期（lease）在租期过期之前，客户可更新副本，重续租期如果已经过期，缓存中的副本失效改进的一致性协议当客户修改文件时，只需将所有没有到期的缓存副本设为无效如果某个客户崩溃，则等待直到该客户的租期过期17使用同步时钟基于时钟的缓存一致性改进的一致性协议1主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁18主要内容3.1时钟同步183.2互斥基本概念当一个进程使用某个共享资源，其他进程不允许对这个资源操作临界区（CriticalSection）：对共享资源进行操作的程序段基本方法：信号量、管程问题：死锁活锁饥饿193.2互斥基本概念19集中式算法（仿照单处理机系统的方法）协调者：确定那个进程可进入临界区通信量：3个消息：请求-许可-释放缺点：单点失败单协调者会成为执行的瓶颈

CCC20集中式算法（仿照单处理机系统的方法）协调者：确定那个进程可WinThread临界区CreateMutex()WaitForSingleObject()ReleaseMutex()InitializeCriticalSection()EnterCriticalSection()LeaveCriticalSection()21WinThread临界区CreateMutex()21分布式算法（Ricart-Agrawala算法）要求系统中所有事件都是全序的1.在一个进程P打算进入临界区R之前，向所有其他进程广播消息<临界区R名、进程号、时间印>2.当一个进程P’收到消息后，做如下决定：若P’不在临界区R中，也不想进入R，它就向P发送OK消息；若P’已经在临界区R中，则不回答，并将P放入请求队列；若P’也同时要进入临界区R，但是还没有进入时，则将发来的消息和它发送给其余进程的时间戳对比。如果P时间印小，则P发送OK消息;否则，不回答，并将P放入请求队列；3.当P收到所有的OK消息后，进入R。否则，等待。4.当P退出R时，如果存在等待队列，则取出请求者，向其发送OK消息。22分布式算法（Ricart-Agrawala算法）要求系统中所分布式算法举例举例：

共有0，1，2三个进程。进程0，2申请进入临界区02002223分布式算法举例举例：共有0，1，2三个进程。0200222分布式算法评价缺点：n点失败n点瓶颈2（n-1)个消息改进方案：超时重发组通信简单多数同意比原来集中式算法慢，复杂，昂贵，而且不健壮。24分布式算法评价缺点：24令牌环算法构造一个逻辑环，得到令牌才可进入临界区325令牌环算法构造一个逻辑环，得到令牌才可进入临界区325三种互斥算法的比较算法每次进出需要的消息进入前的延迟（按消息次数）存在问题集中式32协调者崩溃分布式2（n-1）2（n-1）任何一个进程崩溃令牌环1到∞0到n-1丢失令牌，进程崩溃26三种互斥算法的比较算法每次进出进入前的延迟（按消息次数）存在主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁27主要内容3.1时钟同步273.3选举算法许多分布式算法需要一个进程充当协调者，发起者，排序者或其他特定的角色。作用：做出统一的的决定例如：确定协调者283.3选举算法许多分布式算法需要一个进程充当协调者，发起欺负（Bully）算法将进程进行排序P向高的进程发E消息如果没有响应，P选举获胜如果有进程Q响应,则P结束，Q接管选举并继续下去。45656465629欺负（Bully）算法将进程进行排序45656465629环算法所有进程按逻辑或物理次序排序，形成一个环当一个进程P发现协调者C失效后，向后续进程发送E消息每个进程继续向后传递E消息，直到返回PP在将新确定的协调者C’传给所有进程5230环算法所有进程按逻辑或物理次序排序，形成一个环5230主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁31主要内容3.1时钟同步313.4原子性（Atomic）事务原子性：组成原子事务的一组操作要么全部执行，要么一个也不执行，并且事务失败后能返回到最初状态例1：老式磁带系统（备份）例2：汇款（提款存款）323.4原子性（Atomic）事务原子性：组成原子事务的事务模型稳定存储器（StableStorage）：通过一对双工磁盘实现33事务模型稳定存储器（StableStorage）：33事务原语（1）BEGIN_TRANSACTION：标记一个事务的开始；（2）END_TRANSACTION：结束事务并设法提交；（3）ABORT_TRANSACTION：取消事务并恢复旧值；（4）READ：从一个文件（或其他类型的对象，如数据库）读取数据；（5）WRITE：将数据写入一个文件（或其他类型的对象，如数据库）34事务原语（1）BEGIN_TRANSACTION：标记一个事务举例BEGINTRANSACTIONreserveWP－JFKreserveJFK－NairobireserveNairobi－MalindiENDTRANSACTION

BEGINTRANSACTIONreserveWP－JFKreserveJFK－Nairobi

Nairobi－MalindifullABORTTRASACTION

当第三个航班的机票预定失败后事务中止预定三个航班机票：中转站是JFK、Nairobi35事务举例BEGINTRANSACTION预定三个航班机票：事务的特性

原子性（Atomic）：对外部世界来说，事务的发生是不可分割的；一致性（Consistent）：事务不会破坏系统的恒定；隔离性（Isolated）：并发的事务之间不会互相干扰；可串行性（Serializable）:多个事务并发执行的结果，与它们顺序地执行效果相同。持久性（Durable）：一旦一个事务提交，它的更新结果不会因故障而丢失。36事务的特性原子性（Atomic）：对外部世界来说，事务的发隔离性（Isolated）37隔离性（Isolated）37事务的实现

私有工作空间与影子更新：当进程启动事务T时，分配一个私有工作空间W，在提交或中止T前所有的读写操作都是在W中进行0‘3‘影子块38事务的实现私有工作空间与影子更新：0‘3‘影子块38先写日志（WAL）就地更新（in-place）日志纪录〈事务标识，文件标识，块号，前像，后像〉例：39先写日志（WAL）就地更新（in-place）39先写日志协议回滚（Rollback）:反做（undo）废弃事务的更新结果只有当日志成功地写入稳存之后，才可以修改文件。如果事务执行成功并被提交，则它的提交记录将被写入日志。如果事务异常中止，则用日志来备份初始状态。从日志的未尾开始，向回逐个读取日志记录，反做记录中描述的修改，即回滚处理。在系统崩溃后,日志也可用来进行的恢复。40先写日志协议回滚（Rollback）:40示例(a)一个事务(b)-(d)每条语句执行前的日志41示例(a)一个事务(b)-(d)每条语句执行前的两阶段提交协议（two-phasecommitprotocol）

准备阶段：取得一致决定执行阶段：执行命令（提交或废弃）42两阶段提交协议（two-phasecommitproto并发控制(ConcurrencyControl)加锁法正确性标准：可串行性（serializable）封锁加锁：获得资源上的封锁解锁：释放已拥有的锁封锁的类型和相容性读锁(R)写锁(W)锁的粒度细粒度：如字段粗粒度：如文件RWR√☓W☓☓43并发控制(ConcurrencyControl)加锁法RW两阶段封锁协议(2PL)恰好在需要或不再需要锁时去请求或释放锁可能会导致不一致和死锁？

加锁阶段开锁阶段严格的2PL与2PC结合避免级联废弃（cascadedabort)死锁：等待图（WFG）

检查是否有环路

超时检测（timeout)44两阶段封锁协议(2PL)恰好在需要或不再需要锁时去请求或释放乐观法(Optimistic)最适合于基于私有工空间的情况读阶段：将文件读入私有工作区确认阶段：提交前，检查是否有冲突有，则废弃事务，重启。无，则提交事务写阶段：如可以提交，则将修改内容从私有工作区，写入文件。45乐观法(Optimistic)最适合于基于私有工空间的情况时间戳(Timestamp)每个事务的操作带有该事务的时间戳每个文件带有对它操作的最后一个提交事务的读时间戳、写时间戳算法：如果当前事务T的时间戳〉文件的时间戳，则执行；否则，废弃T;46时间戳(Timestamp)每个事务的操作带有该事务的时间戳时间戳法示例设有三个事务α，β，γ。T(α)<T(β)<T(γ)TT(φ)47时间戳法示例设有三个事务α，β，γ。T(α)<T(β)<T(三种方法比较并发度死锁性能2PL低有中乐观法高无高（废弃度低时）时间印法较高无较高48三种方法比较并发度死锁性能2PL低有中乐观法高无高（废弃度低主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁49主要内容3.1时钟同步493.5分布式系统的死锁处理通信死锁和资源死锁死锁解决策略鸵鸟法：（忽略问题，留给用户考虑）检测法：（允许死锁发生，在检测到后想办法恢复）预防法：（静态的使死锁在结构上是不可能发生的）避免法：（在运行中，通过仔细的分配资源以避免死锁）实际在分布式系统中从来都不采用

银行家算法[Dijkstra,1965]P<has,max>,free503.5分布式系统的死锁处理通信死锁和资源死锁50检测方法：集中式一台中心机器拥有整个系统（所有资源图的集合）的资源图

进程-资源等待图节点：进程P、资源R有向边:(1)PR请求关系;(2)RP拥有关系;死锁检测协调者负责检测死锁资源图的维护策略：当资源图中，有一条边加入/删除时，通知协调者每个进程周期性地向协调者发送图的更新消息协调者在需要时，向参入者请求51检测方法：集中式一台中心机器拥有整个系统（所有资源图的集合）检测方法：集中式举例假死锁问题：B释放R,请求T。若请求T消息先到达协调者(a)机器0初始资源图(b)机器1初始资源图(c)协调者对系统的观察(d)延迟信息后的系统情况

解决方案一：协调者确认（消息的全局时序）52检测方法：集中式举例假死锁问题：B释放R,请求T。若请求T消检测方法：分布式Chandy－Misra－Haas分布式死锁检测算法，探测消息：〈阻塞Pid，请求Pid，接收Pid〉e.g.（0,2,3）,（0,4,6）,（0,5,7）,（0,8,0）构成死锁53检测方法：分布式Chandy－Misra－Haas分布式死锁分布式深度限制算法（DWDL）90%的死锁发生在两个进程之间算法：//p1为请求者;L(p1)为p1的寿命1)if(waitQueue=p2->p1->p0)thenif(L(p1)<L(p2)orL(p1))<L(p0)thenrestartp1;elserestartp0;2)if(waitQueue=p1->p1'->p0)thenif(L(p'1)<L(p1)orL(p'1)<L(p0))thenrestartp'1;elserestartp0;3)if(waitQueue=p2->p1->p'1->p0)thenif(L(p1)<L(p2)orL(p1)<L(p0))thenrestartp1;elserestartp'1;54分布式深度限制算法（DWDL）90%的死锁发生在两个进程之间等-死算法(wait-die)设请求进程0的时间印t0,拥有资源的进程1的时间印t1如果t0<t1,0等待;否则，撤销0分布式死锁预防55等-死算法(wait-die)分布式死锁预防55分布式死锁的预防伤-等算法（wound-wait)设请求进程0的时间印t0,拥有资源的进程1的时间印t1如果t0<t1，撤销1;否则，0等待56分布式死锁的预防伤-等算法（wound-wait)56第3章分布式系统的同步

中国科技大学软件学院丁箐57第3章分布式系统的同步中国科技大学软件学院1主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁58主要内容3.1时钟同步2主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁59主要内容3.1时钟同步33.1时钟同步分布式算法的特点相关信息散布在多个场地上每个进程只能基于本地信息做决定应避免因单点故障造成整个系统的失败不存在公共时钟或精确的全局时间603.1时钟同步分布式算法的特点4时钟同步问题例：makefile误差时间output.o：cc–Coutput.c61时钟同步问题例：makefile误差时间output.o：逻辑时钟计时器：石英晶体+计数器时钟偏差（clockskew）逻辑时钟：相对时间物理时钟：真实时间“之前”关系:事件a在b之前出现，则aba为发送消息m，b为接收m，则ab具有传递性：ab,bc,则ac并发事件（concurrent）62逻辑时钟计时器：石英晶体+计数器6Lamport算法对每一事件a，在所有进程中都认可给它分配一个时间值C(a）ifab;则C(a)<C(b)a,bC(a)C(b)C是递增的校正算法ab，ifC(b)<C(a),则C(b)=C(a)+163Lamport算法对每一事件a，在所有进程中都认可给它分配一Lamport算法时间慢快慢快64Lamport算法时间慢快慢快8物理时钟与现实时钟（1）如何用现实世界的时钟将它们同步起来；（2）如何使各时钟之间保持同步。

太阳日：连续的两次日中天的时间太阳秒：solar-day/86400平均太阳秒：如，格林威治时间65物理时钟与现实时钟（1）如何用现实世界的时钟将它们同步起来；现实时钟铯原子钟：9192631770次跃迁=1秒TAI秒：国际原子时间UTC秒：世界时间（在TAI秒中加入闰秒）时间服务：WWV电台、GEOS卫星102066现实时钟铯原子钟：9192631770次跃迁=1秒10201时钟同步算法如何与现实时钟同步如何使不同机器之间相互同步设机器时钟值Cp(t),t为UTC时间最大偏移率精确时钟：dC/dt=1快时钟：dC/dt〉1慢时钟：dC/dt<167时钟同步算法如何与现实时钟同步11Christian’s算法--逐步调整法时间服务器，可接受WWV的UTC时间每隔δ/2ρ校准时间（允许误差δ，存在误差ρ）两个问题：时间决不能倒退,延迟假设：每秒产生100次中断，每次中断将时间加10毫秒若调慢时钟，中断服务程序每次只加9毫秒；若加快时钟，则加11毫秒。传播时间68Christian’s算法--逐步调整法时间服务器，Berkeley算法–主动式方法时间监控器定期查询其他机器时间计算出平均值通知其他机器调整时间69Berkeley算法–主动式方法时间监控器定期查询其他平均值算法–非集中式方法将时间划分成固定长度的再同步间隔，第i次间隔开始于T0+iR，而结束于T0+(i+1)R所有机器广播自己的时钟时间启动本地计时器收集在S时间间隔中到达的其他机器广播的时间执行平均时间计算算法，得到新的时间值（取平均值，去掉两端值）70平均值算法–非集中式方法将时间划分成固定长度的再同步间隔多个外部时间源法例：OSFDCE方法接受所有时间源的当前UTC区间去掉与其他区间不相交的区间将相交部分的中点作为校准时间时间71多个外部时间源法例：OSFDCE方法时间15使用同步时钟最多一次消息提交每个消息携带一个ID和一个时间印ts（timestamp）服务器的表T中，记录每个连接C最近的时间印t如果到达的消息m，ts(m)<t,则拒绝m

服务器要一直保存一个全局变量G=CurrentTime–MaxLifetime–MaxClockSkew所有<G的时间印从表T中清除对于具有新的ID的到达消息m,如果ts(m)<G则拒绝m,否则，接受m按照一定时间间隔T，定期地将G写入磁盘。当系统重启后，G’=G+T72使用同步时钟最多一次消息提交服务器要一直保存一个全使用同步时钟基于时钟的缓存一致性当客户读取一个副本到缓存时，设置一个租期（lease）在租期过期之前，客户可更新副本，重续租期如果已经过期，缓存中的副本失效改进的一致性协议当客户修改文件时，只需将所有没有到期的缓存副本设为无效如果某个客户崩溃，则等待直到该客户的租期过期73使用同步时钟基于时钟的缓存一致性改进的一致性协议1主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁74主要内容3.1时钟同步183.2互斥基本概念当一个进程使用某个共享资源，其他进程不允许对这个资源操作临界区（CriticalSection）：对共享资源进行操作的程序段基本方法：信号量、管程问题：死锁活锁饥饿753.2互斥基本概念19集中式算法（仿照单处理机系统的方法）协调者：确定那个进程可进入临界区通信量：3个消息：请求-许可-释放缺点：单点失败单协调者会成为执行的瓶颈

CCC76集中式算法（仿照单处理机系统的方法）协调者：确定那个进程可WinThread临界区CreateMutex()WaitForSingleObject()ReleaseMutex()InitializeCriticalSection()EnterCriticalSection()LeaveCriticalSection()77WinThread临界区CreateMutex()21分布式算法（Ricart-Agrawala算法）要求系统中所有事件都是全序的1.在一个进程P打算进入临界区R之前，向所有其他进程广播消息<临界区R名、进程号、时间印>2.当一个进程P’收到消息后，做如下决定：若P’不在临界区R中，也不想进入R，它就向P发送OK消息；若P’已经在临界区R中，则不回答，并将P放入请求队列；若P’也同时要进入临界区R，但是还没有进入时，则将发来的消息和它发送给其余进程的时间戳对比。如果P时间印小，则P发送OK消息;否则，不回答，并将P放入请求队列；3.当P收到所有的OK消息后，进入R。否则，等待。4.当P退出R时，如果存在等待队列，则取出请求者，向其发送OK消息。78分布式算法（Ricart-Agrawala算法）要求系统中所分布式算法举例举例：

共有0，1，2三个进程。进程0，2申请进入临界区02002279分布式算法举例举例：共有0，1，2三个进程。0200222分布式算法评价缺点：n点失败n点瓶颈2（n-1)个消息改进方案：超时重发组通信简单多数同意比原来集中式算法慢，复杂，昂贵，而且不健壮。80分布式算法评价缺点：24令牌环算法构造一个逻辑环，得到令牌才可进入临界区381令牌环算法构造一个逻辑环，得到令牌才可进入临界区325三种互斥算法的比较算法每次进出需要的消息进入前的延迟（按消息次数）存在问题集中式32协调者崩溃分布式2（n-1）2（n-1）任何一个进程崩溃令牌环1到∞0到n-1丢失令牌，进程崩溃82三种互斥算法的比较算法每次进出进入前的延迟（按消息次数）存在主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁83主要内容3.1时钟同步273.3选举算法许多分布式算法需要一个进程充当协调者，发起者，排序者或其他特定的角色。作用：做出统一的的决定例如：确定协调者843.3选举算法许多分布式算法需要一个进程充当协调者，发起欺负（Bully）算法将进程进行排序P向高的进程发E消息如果没有响应，P选举获胜如果有进程Q响应,则P结束，Q接管选举并继续下去。45656465685欺负（Bully）算法将进程进行排序45656465629环算法所有进程按逻辑或物理次序排序，形成一个环当一个进程P发现协调者C失效后，向后续进程发送E消息每个进程继续向后传递E消息，直到返回PP在将新确定的协调者C’传给所有进程5286环算法所有进程按逻辑或物理次序排序，形成一个环5230主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁87主要内容3.1时钟同步313.4原子性（Atomic）事务原子性：组成原子事务的一组操作要么全部执行，要么一个也不执行，并且事务失败后能返回到最初状态例1：老式磁带系统（备份）例2：汇款（提款存款）883.4原子性（Atomic）事务原子性：组成原子事务的事务模型稳定存储器（StableStorage）：通过一对双工磁盘实现89事务模型稳定存储器（StableStorage）：33事务原语（1）BEGIN_TRANSACTION：标记一个事务的开始；（2）END_TRANSACTION：结束事务并设法提交；（3）ABORT_TRANSACTION：取消事务并恢复旧值；（4）READ：从一个文件（或其他类型的对象，如数据库）读取数据；（5）WRITE：将数据写入一个文件（或其他类型的对象，如数据库）90事务原语（1）BEGIN_TRANSACTION：标记一个事务举例BEGINTRANSACTIONreserveWP－JFKreserveJFK－NairobireserveNairobi－MalindiENDTRANSACTION

BEGINTRANSACTIONreserveWP－JFKreserveJFK－Nairobi

Nairobi－MalindifullABORTTRASACTION

当第三个航班的机票预定失败后事务中止预定三个航班机票：中转站是JFK、Nairobi91事务举例BEGINTRANSACTION预定三个航班机票：事务的特性

原子性（Atomic）：对外部世界来说，事务的发生是不可分割的；一致性（Consistent）：事务不会破坏系统的恒定；隔离性（Isolated）：并发的事务之间不会互相干扰；可串行性（Serializable）:多个事务并发执行的结果，与它们顺序地执行效果相同。持久性（Durable）：一旦一个事务提交，它的更新结果不会因故障而丢失。92事务的特性原子性（Atomic）：对外部世界来说，事务的发隔离性（Isolated）93隔离性（Isolated）37事务的实现

私有工作空间与影子更新：当进程启动事务T时，分配一个私有工作空间W，在提交或中止T前所有的读写操作都是在W中进行0‘3‘影子块94事务的实现私有工作空间与影子更新：0‘3‘影子块38先写日志（WAL）就地更新（in-place）日志纪录〈事务标识，文件标识，块号，前像，后像〉例：95先写日志（WAL）就地更新（in-place）39先写日志协议回滚（Rollback）:反做（undo）废弃事务的更新结果只有当日志成功地写入稳存之后，才可以修改文件。如果事务执行成功并被提交，则它的提交记录将被写入日志。如果事务异常中止，则用日志来备份初始状态。从日志的未尾开始，向回逐个读取日志记录，反做记录中描述的修改，即回滚处理。在系统崩溃后,日志也可用来进行的恢复。96先写日志协议回滚（Rollback）:40示例(a)一个事务(b)-(d)每条语句执行前的日志97示例(a)一个事务(b)-(d)每条语句执行前的两阶段提交协议（two-phasecommitprotocol）

准备阶段：取得一致决定执行阶段：执行命令（提交或废弃）98两阶段提交协议（two-phasecommitproto并发控制(ConcurrencyControl)加锁法正确性标准：可串行性（serializable）封锁加锁：获得资源上的封锁解锁：释放已拥有的锁封锁的类型和相容性读锁(R)写锁(W)锁的粒度细粒度：如字段粗粒度：如文件RWR√☓W☓☓99并发控制(ConcurrencyControl)加锁法RW两阶段封锁协议(2PL)恰好在需要或不再需要锁时去请求或释放锁可能会导致不一致和死锁？

加锁阶段开锁阶段严格的2PL与2PC结合避免级联废弃（cascadedabort)死锁：等待图（WFG）

检查是否有环路

超时检测（timeout)100两阶段封锁协议(2PL)恰好在需要或不再需要锁时去请求或释放乐观法(Optimistic)最适合于基于私有工空间的情况读阶段：将文件读入私有工作区确认阶段：提交前，检查是否有冲突有，则废弃事务，重启。无，则提交事务写阶段：如可以提交，则将修改内容从私有工作区，写入文件。101乐观法(Optimistic)最适合于基于私有工空间的情况时间戳(Timestamp)每个事务的操作带有该事务的时间戳每个文件带有对它操作的最后一个提交事务的读时间戳、写时间戳算法：如果当前事务T的时间戳〉文件的时间戳，则执行；否则，废弃T;102时间戳(Timestamp)每个事务的操作带有该事务的时间戳时间戳法示例设有三个事务α，β，γ。T(α)<T(β)<T(γ)TT(φ)103时间戳法示例设有三个事务α，β，γ。T(α)<T(β)<T(三种方法比较并发度死锁性能2PL低有中