并发控制 Concurrency control 夏英 (xiaying@cqupt.edu.cn) 重庆邮电大学计算机学院
1 并发控制 Concurrency Control 夏英 (xiaying@cqupt.edu.cn) 重庆邮电大学计算机学院
主要内容 并发操作 并发控制的目的 ·可串行化调度,优先图 并发控制的主要技术 封锁 时间戳 有效性检查
2 主要内容 • 并发操作 • 并发控制的目的 • 可串行化调度,优先图 • 并发控制的主要技术 – 封锁 – 时间戳 – 有效性检查
多事务并发的应用环境 T1 T2 Tn DB (一致的) 各事务宏观上并行,徽观上串行
3 多事务并发的应用环境 T1 T2 … Tn DB (一致的) 各事务宏观上并行,微观上串行
问题的提出 导致数据库状态不一致的可能原因 故障发生 并发事务对数据的共享 并发操作可能引起的数据不一致 现象:丢失修改、不可重复读、读脏数据 原因:事务的隔离性被破坏,事务间相互干扰
4 问题的提出 • 导致数据库状态不一致的可能原因 – 故障发生 – 并发事务对数据的共享 • 并发操作可能引起的数据不一致 – 现象:丢失修改、不可重复读、读脏数据 – 原因:事务的隔离性被破坏,事务间相互干扰
并发控制 功能:控制并发事务的执行步骤,保证并 发事务都能正确执行,从而保证数据库的 致性。 实施部件:事务管理器中的调度器
5 并发控制 • 功能:控制并发事务的执行步骤,保证并 发事务都能正确执行,从而保证数据库的 一致性。 • 实施部件:事务管理器中的调度器
基本概念 事务:一个读r(x)/写w(x)操作序列 调度:一个或多个事务的重要操作按时间顺 序执行的一个序列。 串行调度:不同事务在执行过程中没有交叉 的调度(一定是正确的调度)
6 基本概念 • 事务: 一个读ri(x) / 写wi(x) 操作序列 • 调度: 一个或多个事务的重要操作按时间顺 序执行的一个序列。 • 串行调度: 不同事务在执行过程中没有交叉 的调度(一定是正确的调度)
可串行化的调度 可串行性:多个事务的并发执行是正确的,当且 仅当其结果与按某一次序串行地执行它们时的结 果相同。 可串行性是并发事务操作是否正确的判别准则。 为了保证并发执行的事务能保持数据库的正确性, DBMS的并发控制机制必须提供一定的手段来保 证调度是可串行化的。 并发控制的思想:调度器可能推迟一些操作的执 行,甚至可能中断一个事务
7 可串行化的调度 • 可串行性 :多个事务的并发执行是正确的 ,当且 仅当其结果与按某一次序串行地执行它们时的结 果相同 。 • 可串行性是并发事务操作是否正确的判别准则 。 • 为了保证并发执行的事务能保持数据库的正确性 , DBMS的并发控制机制必须提供一定的手段来保 证调度是可串行化的 。 • 并发控制的思想 :调度器可能推迟一些操作的执 行 ,甚至可能中断一个事务
例如:已知两个事务,一个约束条件 T1: Read(a, t) T2: Read(a,s) t<t+100 s<s×2 Write(a, t) Write(A,s) Read(b, t) Read(b, s) t<t+100 S<s×2 Write(B, t) Write(B,s) Constraint: A=B
8 例如: 已知两个事务,一个约束条件 T1: Read(A,t) T2: Read(A,s) t ← t+100 s ← s×2 Write(A,t) Write(A,s) Read(B,t) Read(B,s) t ← t+100 s ← s×2 Write(B,t) Write(B,s) Constraint: A=B
调度( Schedule)A A B T1 T2 Read(A;A←-A+100 Write(a; 125 Read Bi b< B+100 Write B) 125 Read(A: a< Ax2: Write(a) 250 Read(B);B←B×2; Write (B 250 250250 这是一个串行调度
9 调度(Schedule) A T1 T2 Read(A); A ← A+100 Write(A); Read(B); B ← B+100; Write(B); Read(A);A ← A×2; Write(A); Read(B);B ← B×2; Write(B); A B 25 25 125 125 250 250 250 250 这是一个串行调度
Schedule b A B T1 T2 2525 Read(A;A←-Ax2 Write(a) 50 Read(B);B←B×2; Write; 50 Read (A;a<A+100 Write(a) 150 Read (B:b< B+100 Write B) 150 150150 这也是一个串行调度
10 Schedule B T1 T2 Read(A);A ← A×2; Write(A); Read(B);B ← B×2; Write(B); Read(A); A ← A+100 Write(A); Read(B); B ← B+100; Write(B); A B 25 25 50 50 150 150 150 150 这也是一个串行调度