05-事务和并发控制概论.ppt

锁 对某一对象 被请求的锁 read write 已设置的锁 none OK OK read OK write 等待 等待 等待 锁 死锁(一) 死锁场景示例 　两个事务都在等待并且只有对方释放锁后才能继续执行 事务T 事务U 操作 锁 操作 锁 a.deposit(100); 给A加锁 b.deposit(200) 给B加写锁 b.withdraw(100) 等待事务U a.withdraw(200); 等待事务T 在B上的锁 在A上的锁 锁 死锁(二) 定义 　死锁是一种状态，在该状态下一组事务中的每一个事务都在等待其它事务释放某个锁。 等待图 　表示事务之间的等待关系。 B A 等待 持有 持有 T U U T 等待 锁 预防死锁 每个事务在开始运行时锁住它要访问的所有对象 　　- 一个简单的原子操作 　 - 不必要的资源访问限制 　　- 无法预计将要访问的对象 预定次序加锁 　　- 过早加锁 - 减少并发度 更新锁 避免死锁 在数据项上加更新锁的事务可以读该数据项，但该锁与加在同一数据项上的更新相冲突。 锁 死锁检测 维护等待图 检测等待图中是否存在环路 若存在环路，则选择放弃一个事务 锁超时：解除死锁最常用的方法之一 每个锁都有一个时间期限 超过时间期限的锁成为可剥夺锁 若存在等待可剥夺锁保护的对象，则对象解锁。 第5章 事务和并发控制 事务 锁 乐观并发控制 时间戳排序 并发控制方法的比较 小结 乐观并发控制 锁机制的缺点 维护开销大 会引起死锁 并发度低 乐观策略 基于事实：在大多数应用中，两个客户事务访问同一个对象的可能性很低。 方法 - 访问对象时不作检查操作 　 - 事务提交时检测冲突 　　- 若存在冲突，则放弃一些事务 乐观并发控制 事务的三个阶段 工作阶段 　- 每个事务拥有所修改对象的临时版本 - 每个事务维护访问对象的两个集合：读集合和写集合 验证阶段 - 在收到closeTransaction请求，判断是否与其它事务存在冲突。 更新阶段 - 提交通过验证的事务 乐观并发控制 事务的验证 事务号 　- 每个事务在进入验证阶段前被赋予一个事务号 - 事务号是整数，并按升序分配 　- 事务按事务号顺序进入验证阶段 - 事务按事务号提交 冲突规则 　- 事务Tv的验证测试 　- Ti和Tv之间的存在冲突 - 事务Tv对事务Ti而言是可串行化的 乐观并发控制 Tv Ti 规则 write read 1. Ti不能读取Tv写的对象 read write 2. Tv不能读取Ti写的对象 write write 3. Ti不能写Tv写的对象, 并且Tv不能写Ti写的对象 由于验证和更新过程较短，每次仅允许一个事务处于验证和更新阶段。 乐观并发控制 向后验证 检查它的读集是否和其它较早重叠事务的写集是否重叠 算法 　- startTn: Tv进入工作阶段时已分配的最大事务号码 　- finishTn: Tv进入验证阶段时已分配的最大事务号码 验证失败后，冲突解决方法 　　放弃当前进行验证的事务 Boolean valid = true For ( int Ti = startTn +1; Ti = finishTn; Ti ++) { if (read set of Tv intersects write set of Ti) valid = false } 乐观并发控制 向后验证(续) 事务的验证过程 　 - T1、 T2、T3是较早开始的事务 - T1在Tv开始之前提交 　 - T2、T3在Tv完成其工作阶段前提交 - startTn+1=T2，finishTn=T3 乐观并发控制 较早提交的事务 工作阶段 验证阶段 更新阶段 T 1 T v 正在验证的事务 T 2 T 3 以后的活动事务 active 1 active 2 向后验证过程必须比较Tv的读集和T2、T3的写集 乐观并发控制 向前验证 比较Tv的写集合和所有重叠的活动事务的读集合 算法 　- 设活动事务具有连续的事务标示符active1~activeN 验证失败后，冲突解决方法 　 - 放弃当前进行验证事务 - 推迟验证 　 - 放弃所有冲突的活动事务，提交已验证事务。 Boolean valid = true for ( int Tid = active1 ; Tid = activen; Tid ++){ if (write set of Tv intersects read set of