Schedule c A B T1 T2 2525 Read(A;A←-A+100 Write(a) 125 Read(A;A←-Ax2 Write(a) 250 Read(B);B←B+100 Write B) 125 Read(B);B←B×2; Write B) 250 250250 这是一个非串行的可串行化调度
11 Schedule C T1 T2 Read(A); A ← A+100 Write(A); Read(A);A ← A×2; Write(A); Read(B); B ← B+100; Write(B); Read(B);B ← B×2; Write(B); A B 25 25 125 250 125 250 250 250 这是一个非串行的可串行化调度
Schedule d A B T1 T2 2525 Read(A;A←-A+100 Write(a) 125 Read(A;A←-Ax2 Write(a) 250 Read(B);B←B×2; Write B; 50 Read (B:b< B+100 Write B) 150 250150 这是一个非可串行化调度
12 Schedule D T1 T2 Read(A); A ← A+100 Write(A); Read(A);A ← A×2; Write(A); Read(B);B ← B×2; Write(B); Read(B); B ← B+100; Write(B); A B 25 25 125 250 50 150 250 150 这是一个非可串行化调度
简记 ·重要操作的简记法:r(x),w(x) 事务的简记法:T; yu Ti: ri(A); wi(A); ri(B); wi(B); 调度的简记法:只写出read和 write序列,忽 略 inputi和 output序列 如: Sc=rI(A)wi(ar2(a)w2(A)ri(b)wi br(B)w2B)
13 • 重要操作的简记法： ri(x)，wi(x) • 事务的简记法：Ti – 如：Ti：ri(A)；wi(A)；ri(B)；wi(B)； • 调度的简记法：只写出read和write序列，忽 略input和output序列 – 如: Sc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) 简记
概念 突的操作:涉及同一数据元素,且至少有 写操作,即包括: r1(A)∠W2(A)/W1(A) w2(A)r1(A)w2(A) 如果通过一系列相邻动作的非冲突交换能将他 们中的一个转换为另一个,我们说两个调度是 冲突等价的。 如果二个调度冲突等价于一个串行调度,我们 说该调度是冲突奇串行化的。 冲突可串行性是可串行性的充分条件,是商用 练中的妻务调度器在需要保证可串行性时通
14 概念 • 冲突的操作：涉及同一数据元素，且至少有一 个写操作，即包括： r1(A) w2(A) w1(A) w2(A) r1(A) w2(A) • 如果通过一系列相邻动作的非冲突交换能将他 们中的一个转换为另一个，我们说两个调度是 冲突等价的。 • 如果一个调度冲突等价于一个串行调度，我们 说该调度是冲突可串行化的。 • 冲突可串行性是可串行性的充分条件，是商用 系统中的事务调度器在需要保证可串行性时通 常使用的条件
优先图P(S) 用优先图描述操作的先后顺序 结点:表示调度S中的事务 弧:当下列条件成立时,可画弧I→T ·pi(A),q(A)是S中的操作(即:来自不同事务的两 个操作涉及同一元素) ·pi(A)<sqi(A)(即:p(A)发生在q(A)之前) pi和q中至少一个是写操作 判断调度S是否冲突可串行化的简单规则 构造S的优先图,并判断其中是否有环。如果有,则S 不是冲突可串行化的,否则,S是冲突可串行化的。 考虑有向无环图的拓扑排序问题
15 • 用优先图描述操作的先后顺序 – 结点：表示调度S中的事务 – 弧：当下列条件成立时， 可画弧Ti → Tj • pi(A), qj(A) 是S中的操作 （即：来自不同事务的两 个操作涉及同一元素） • pi(A) <S qj(A) （即： pi(A)发生在qj(A)之前 ） • pi和qj中至少一个是写操作 • 判断调度S是否冲突可串行化的简单规则 – 构造S的优先图，并判断其中是否有环。如果有，则S 不是冲突可串行化的，否则，S是冲突可串行化的。 优先图 P(S) 考虑有向无环图的拓扑排序问题