《[计算机软件及应用]数据库课件》由会员分享，可在线阅读，更多相关《[计算机软件及应用]数据库课件（33页珍藏版）》请在金锄头文库上搜索。
1、9. Concurrency Control,JongHoon Kim,DATABASE SYSTEM IMPLEMENTATION HECTOR GARCIA-MOLINA JEFFRY D. ULLMAN JENIFER WIDOM,General process of assuring that transactions preserve consistency when executing simultaneously.,Transaction manager,Scheduler,Buffers,Read/Write requests,Reads and writes,Concurre
2、ncy Control,Schedules,Correctness principle If executed in isolation, every transaction will transform any consistent state to another consistent state. However, transactions often run concurrently with other transactions, so the correctness principle doesnt apply directly. schedules : time-ordered
3、sequence of the actions taken by one or more transactions - guaranteed do produce the same result as if transactions executed one-at-a-time When studying concurrency control, the important read and write actions take place in the main-memory buffers, not disk,the only consistency constraint on the d
4、atabase state is that A=B. each transaction, run in isolation, will preserve consistency,Schedules Ex. 9.1,Serial Schedules,: A schedule S is serial if for any two transactions T and T, if any action of T precedes any action of T, then all actions of T precedes all actions of T,Serializable Schedule
5、s,every serial schedule will preserve consistency of database state serializable : if its effect on the database state is the same as that of some serial schedule, regardless of what the initial state of the database is,A serializable, but serial, schedule,Nonerializable Schedule,The Effect of Trans
6、action Semantics,A schedule that is serializable only because of the detailed behavior of the transactions,A Notation for Transactions & Schedules,Represent transactions and schedules by a shorthand notation : rT (x) / wT (x) Example 9.5 : The transaction of fig 9.2 can be written T1: r1 (A);w1 (A);
7、r1 (B);w1 (B); T2: r2(A);w2 (A);r2 (B);w2 (B); The transaction of fig 9.5 can be written r1(A);w1(A);r2(A);w2(A); r1(B);w1(B);r2(B);w2(B);,Conflict-Serializability,Conflict : a pair of consecutive actions in a schedule such that, if their order is interchanged, then the behavior of at least one of t
8、he transactions involved can change. Condition of Conflict 1. Two actions of the same transaction, ri(X);wi(Y) conflict. 2. Two writes of the same database element by different transaction conflict wi(X);wj(X) conflict. 3. A read and write of the same database element by different transactions also
9、conflict. ri(X); wj(X) and wi(X); rj(X) conflict Conflict-equivalent : if they can be turned one into the other by a sequence of non-conflicting swaps of adjacent actions Conflict-serializable : if it is conflict-equivalent to a serial schedule,r1(A);w1(A);r2(A);w2(A); r1(B);w1(B);r2(B);w2(B); from
10、example 9.5 - This schedule is serializable : all of T1s actions precede all those of T2 - Converting a conflict- serializable schedule to a serial schedule by swap of adjacent actions : r1(A); w1(A); r2 (A); w2(A); r1(B); w1(B); r2(B); w2(B); r1(A); w1(A); r2(A); r1(B); w2(A); w1(B); r2(B); w2(B);
11、r1(A); w1(A); r1(B); r2(A); w2(A); w1 (B); r2(B); w2(B); r1(A); w1(A); r1(B); r2 (A); w1 (B); w2(A); r2(B); w2(B); r1(A); w1(A); r1(B); w1(B); r2(A); w2(A); r2(B); w2(B);,Conflict-Serializability Ex. 9.6,Precedence Graph for Conflict-Serializability,Given a schedule S, involving transactions T1 and
12、T2, if there are actions A1 of T1 and A2 of T2, such that 1. A1 is ahead of A2 in S 2. Both A1 and A2 involve the same database element 3. At least one of A1 and A2 is write action - these are exactly the conditions under which we cannot swap the order of A1 and A2 - T1 takes precedence over T2 : T1
13、 S T2 Construct the precedence graph for S and ask if there are any cycle S is not conflict-serializable,S1: r1(B);w1(B);r2(A);w2(A);r2(B);w2(B);r3(A);w3(A);,: acyclic, schedule S is conflict-serializable(acyclic) S2: r2(A);r1(B);w2(A);r2(B);r3(A);w1 (B);w3(A);w2(B);,: cyclic precedence graph: its s
14、chedule is not conflict-serializable,Precedence Graph Ex. 9.8, 9.9,Enforcing Serializability by Locks,What does serializibility means? Collection of transactions performing their actions Formation of schedule Scheduler prevents order of actions that leads to unserializable schedule Locks are impleme
15、nted on database elements.,Locks,Request and release locks for reading and writing.,Consistency of Transactions: A transaction can only read or write an element if it requested a lock on that element and hasnt yet released the lock. If a transaction locks an element, it must latter unlock that eleme
16、nt. Legality of Schedules: No two transactions may have locked the same without one having first released the lock.,Li(x): Transaction Ti request a lock on database element X. Ui(x): Transaction Ti releases its lock on database element X. Consistency of Transactions: Whenever a transaction Ti has an action ri(x), then there is a previous action li(x) with no intervening action ui(x), and there is subsequent ui(x). Legality of Schedules: If there are action
