单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据库并发控制技术,数据库并发控制技术,10：00，A订票点读出航班目前的机票余额数，设为10张,10：02，B订票点读出航班目前的机票余额数，也为10张,10：05，A订票点订出6张机票，修改机票余额为10-6=4，并将4写回到数据库中,10：06，B订票点订出5张机票，修改机票余额为10-5=5，并将5写回到数据库中,10：00，A订票点读出航班目前的机票余额数，设为10张,事务,事务是数据库处理的一个逻辑工作单元，它由用户定义的一个或多个访问数据库的操作组成，这些操作一般一般包括检索（读）、插入（写）、删除和修改数据。一个事务内的所有语句被作为一个整体，要么全部执行，要么全部不执行。,如果事务中的数据库操作仅涉及数据的检索，而不更新数据库，那么这样的事务就称为只读事务；否则，称为读写事务。,事务事务是数据库处理的一个逻辑工作单元，它由用户定义的一个或,描述事务处理概念的数据库模型,一条数据库记录,整个磁盘块,某个记录的字段（属性）值,数据项的粒度,-,数据项的大小,-,命名数据项的集合,描述事务处理概念的数据库模型一条数据库记录数据项的粒度-,数据库访问操作,Read_item(X),：将数据库项,X,读取到程序变量,Write_item(X),：将程序变量的值写入数据库项,X,中,数据库访问操作Read_item(X)：将数据库项X读取到程,两个事务的示例,T1,read_item(X);,X:=X-N;,Write_item(X);,Read_item(Y);,Y:=Y-N;,Write_item(Y),T2,Read_item(X);,X:=X+M;,Write_item(X),两个事务的示例T1T2,事务的特性,原子性,一致性,隔离性,持久性,事务的特性原子性,事务状态和附加,操作,BEGIN_TRANSACTION,READ,或,WRITE,END_TRANSACTION,COMMIT_TRANSACTION,ROLLBACK(ABORT),事务状态和附加操作BEGIN_TRANSACTION,活动,开始事务,结束事务,部分提交,提交,部分提交,失败,撤销,终止,读、写,撤销,事务执行状态的状态转换图,活动开始事务结束事务部分提交提交部分提交失败撤销终止读、写撤,调度,n个事务T1,T2,TN的,调度,S,，是这些事务的操作的一个执行顺序。来自不同事务的操作可以在调度,S,中交替执行。但是，对于参与调度,S,的事务,Ti,，,Ti,出现在调度中,S,中的操作，必须与它们在,Ti,中出现的顺序一致，也就是说,S,中的操作必须是全序的。,调度n个事务T1,T2,TN的调度S，是这些事务的操作的,操作冲突的条件,属于不同的事务,访问同一数据项,至少有一个操作是,write_item(X),操作冲突的条件属于不同的事务,并发控制的概念,数据库中的数据是可以共享的资源，因此会有很多用户同时使用数据库中的数据。也就是说，在多用户系统中，可能同时运行着多个事务，而事务的运行需要时间，并且事务中的操作需要在一定的数据上完成。当系统中同时有多个事务运行时，特别是当这些事务使用同一段数据时，彼此之间就有可能产生相互干扰。并发控制通过对并发操作进行正确的调度保证事务的,ACID,特性。,并发控制的概念数据库中的数据是可以共享的资源，因此会有很多用,并发控制的必要性,更新丢失,暂时更新（脏读）,错误求和,不可重复读,并发控制的必要性更新丢失,项,X,的值是错误的，,因为,T1,对它的更新丢失了,项X的值是错误的，,事务,T1,因故障而必须将,X,值,改变回其旧值，但,T2,已经,读取了,X,的错误值,事务T1因故障而必须将X值,T3,在,X,减去,N,之后读,X,，而,在,Y,加,N,之前读,Y,；因此产生了错误的求和结果,T3在X减去N之后读X，而,并发控制的加锁技术,二进制锁,共享,/,排他锁（读,/,写锁）,并发控制的加锁技术二进制锁,二进制锁,一个二进制锁可以有两个状态或值：已加锁和未加锁（或简化记为,1,和,0,）。每个数据项,X,都与一个不同的锁相关联。,Lock_item(X),unlock_item(X),二进制锁一个二进制锁可以有两个状态或值：已加锁和未加锁（,图,二进制锁的加锁和解锁操作,图二进制锁的加锁和解锁操作,二进制锁的实现,二进制变量,LOCK,关联于数据库中的每个数据项,X,包含三个字段的记录,队列存放等待访问该项的事务,系统维护锁表，仅存放当前已加锁的数据项的相应记录,二进制锁的实现二进制变量LOCK关联于数据库中的每个数据项X,规则,事务,T,在执行其任何,read_item(X),或,write_item(X),操作之前，必须先发出一个,lock_item(X),操作,事务,T,中所有,read_item(X),和,write_item(X),操作执行完之后，都必须发出一个,unlock_item(X),操作,规则事务T在执行其任何read_item(X)或write_,共享,/,排他（读,/,写）锁,Read_lock(X),Write_lock(X),解锁（释放）：,Unlock(X),共享/排他（读/写）锁Read_lock(X),图共享,/,排他的加锁和解锁操作,图共享/排他的加锁和解锁操作,共享,/,排他锁的实现,包含四个字段的记录,变量,LOCK,关联于数据库中的每个数据项,X,，,存放读锁定,/,写锁定,/,未锁定相应的编码,Locking_transaction,中存放持有锁的一个事务或列表,No_of_reads,中存放当前对该数据项进行读操作的事务数量,队列存放等待访问该项的事务,系统维护锁表，仅存放当前已加锁的数据项的相应记录,共享/排他锁的实现包含四个字段的记录,规则,事务,T,在执行其任何,read_item(X),操作之前，必须先发出,read_lock(X),或,write_lock(X),操作,事务,T,在执行其任何,write_item(X),操作之前，必须先发出,write_lock(X),操作,事务,T,中所有,read_item(X),和,write_item(X),操作执行完之后，都必须发出,unlock(X),操作,规则事务T在执行其任何read_item(X)操作之前，必须,死锁,事务,T1,对数据,R1,封锁之后，又要求对数据,R2,封锁,而事务,T2,已经获得对数据,R2,的封锁之后，又要求对数据,R1,封锁,这两个事务处于互相等待状态，发生死锁,事务,T1,时间,事务,T2,1,。,对,R1,加锁,t1,2,。,t2,对,R2,加锁,3,。,请求对,R2,加锁,t3,等待,4,。,等待,t4,请求对,R1,加锁,等待,等待,死锁事务T1对数据R1封锁之后，又要求对数据R2封锁事务T1,死锁的诊断,方法一.等待图法,数据库周期性地生成事务等待关系有向图，,若图中存在有向回路，则表明产生死锁，如：,死锁的诊断 方法一.等待图法,方法二.超时法,若一个事务的等待时间超过了规定的时限，则系统认为产生了死锁,缺点：规定时限设置过短，则容易误判；,设置过长，则不能及时处理死锁。,方法二.超时法 若一个事务的等待时间超过了规定的时限，,破除死锁方法,某些事务必须回滚以破除死锁，一般选择回滚 带来代价最小的事务，释放该事务所持有的全部锁，并撤销其对数据的修改操作。,破除死锁方法 某些事务必须回滚以破除死锁，一般选择回滚,死锁的预防,方法一.一次性封锁法,每个事务执行时，一次性对其要使用到的数据项全部加锁，否则不能继续执行（缺一不可，只要有一个锁不能加锁，则释放已经加好的锁，继续等待）,例子：,如果T1将R1和R2一次性全部加锁，,则T2要加锁时只能等待直到T1释放锁,事务,T1,时间,事务,T2,1,。,对,R1,加锁,t1,2,。,t2,对,R2,加锁,3,。,请求对,R2,加锁,t3,等待,4,。,等待,t4,请求对,R1,加锁,等待,等待,死锁的预防方法一.一次性封锁法例子：事务T1时间事务T21,方法二.顺序加锁法,预先对数据项规定一个加锁排序，所以加锁操作都要按顺序，释放锁时按照逆序,例子：,如果规定加锁顺序先R1再R2，,则T2要对R2加锁之前，需要先对R1加锁，即T2需要等待T1先释放R2再释放R1,事务,T1,时间,事务,T2,1,。,对,R1,加锁,t1,2,。,t2,对,R2,加锁,3,。,请求对,R2,加锁,t3,等待,4,。,等待,t4,请求对,R1,加锁,等待,等待,方法二.顺序加锁法预先对数据项规定一个加锁排序，所以加锁操作,时间戳方法,基于时间戳排序的并发控制,时间戳方法基于时间戳排序的并发控制,时间戳概念,每个事物开始执行时，系统会给“他/她”分配一个时间戳，通常是基于系统时钟的。,越晚启动的事务其时间戳数值越大。,每个数据库项 X 也有2个时间戳：读和写：,read_TS(X),=TS(,T,最晚读,)，即,T,最晚读,为成功读取X的最晚的事务；,write_TS(X),=TS(,T,最晚写,)，即,T,最晚写,为成功写入X的最晚的事务；,时间戳概念每个事物开始执行时，系统会给“他/她”分配一个时间,时间戳排序,（1）写：,当事物T1发出write_item(X)操作，需检查：,a.若read_TS(X)TS(T1),或者write_TS(X)TS(T1)，则拒绝write操作，撤销并回滚T1,原因：这说明某个时间戳大于T1的事物T2（比T1晚启动），在T1要写X之前，T2已经读或写了X的数据；,时间戳排序（1）写：,如果是T2先写，则T1的写操作将覆盖了较晚启动的T2的写操作，即T2写操作无效,无效,如果是T2先写，则T1的写操作将覆盖了较晚启动的T2的写,如果是T2先读，则T2读的是未经T1修改写入的数据，但实际上较晚启动的T2读的应该是T1修改后的数据。,对：错：,X未经T1修改,如果是T2先读，则T2读的是未经T1修改写入的数据，但实,以上都违反了时间戳顺序。,b.若,以上,(a)中的条件没有发生，则执行T1的写操作，并将write_TS(X)的值设置为TS(T1).,以上都违反了时间戳顺序。,（2）读：,当事务T1发出read_item(X)操作，需检查：,a.若write_TS(X)TS(T1)，则拒绝read操作，撤销并回滚T1,（2）读：,原因：说明在T1要读X之前，比T1晚启动的T2已经修改了X的数据，所以X已经不再是T1启动时的数据值了。,对：错：,X被T2修改,X被T2修改,b.若(a)中的条件没有发生，则执行T1的读操作，,并将read_TS(X)的值设置为TS(T1)和当前的read_TS(X)中的最大值。,这是因为在T1读X前后，其他事务（如T2）都可以读X。,b.若(a)中的条件没有发生，则执行T1的读操作，,乐观,的并发控制方法,提取和修改,检验,提交和写回,乐观 的并发控制方法提取和修改,事务,T,将数据,X从数据库中提取出来，保存在临时副本中,事务,T对数据X所做的所有修改都保存在临时副本中,提取和修改,事务T将数据X从数据库中提取出来，保存在临时副本中提取和修改,检验,事务执行完毕后，提交到数据库之前需要检验：,IF.数据X被在T从数据库中提取出之后，又被其他事务提取且,修改,了，则冲突，T回滚，T的临时副本被删除。,ELSE.检验通过,检验事务执行完毕后，提交到数据库之前需要检验：,检验通过，才能,提交和写回,在临时副本中修改的数据X提交成功，写回到数据库中，使数据库中的X相应地改变。事务执行结束,检验通过，才能 提交和写回,That is all,Q&A,That is allQ&A,