知识库

数据库原理：并发控制

12/31/2023 数据库

目录

参考：

# 数据库原理：并发控制

# 一、并发控制概述

事务是并发控制的基本单位，事务读数据x一般记为R(x)，写数据x一般记为W(x)。

并发控制用于保证事务的隔离性和一致性。

如果不对并发操作进行正确调度，可能导致数据的不一致性问题，包括丢失修改、不可重复读、读脏数据等，原因是并发操作破坏了事务的隔离性。

  1. 丢失修改（WW并发）：两个事务读入同一数据并修改，其中一个事务的修改会丢失。

  2. 不可重复读（RW并发）：事务T1读取数据后，T2执行更新操作，使T1无法再现前一次读取结果。

  3. 读脏数据（WR并发）：“脏”数据指事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤销，则T2读取到的数据就为“脏”数据，即不正确的数据。

# 二、并发控制的实现技术

并发控制的主要技术有**封锁（locking)、时间戳（timestamp)、乐观控制法（optimistic scheduler)、多版本开发控制（multi-version coneurreney control,MVCC)**等。

# 封锁（locking)

封锁即事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁。加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其他的事务不能更新此数据对象。

锁类型

排它锁（写锁，X锁）：若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。这就保证了其他事务在T释放A上的锁前不能再读取和修改A。

共享锁（读锁，S锁）：若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁而不能加X锁，直到T释放A上的S锁。这就保证了其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。

封锁协议

封锁协议（Locking Protocol）即对数据对象加锁时约定的一些规则，如：何时申请封锁、持锁时间、何时释放锁等。

  1. 一级封锁协议：事务T在修改数据R之前必须先对其加X锁，直到事物结束才释放。解决WW丢失修改。
  2. 二级封锁协议：在一级封锁协议的基础上增加事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。解决WW丢失修改和WR读脏数据。
  3. 三级封锁协议：在一级封锁协议的基础上增加事务T在读取数据R之前必须先对其加S锁，直到事物结束才释放。解决WW丢失修改和WR读脏数据和RW不可重复读。

死锁

活锁即一个事务可能永远等待（系统总是先批准其他事务的锁请求），可以采用先来先服务的策略解决。

死锁即两个事务互相申请对方锁住的资源导致两个事务永远不能结束。

死锁的预防策略：

  1. 一次性封锁法：一次性封锁法要求每个事务必须一次将所有要使用的数据全部加锁。缺点：势必扩大封锁的范围，从而降低了系统的并发度；

  2. 顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。缺点；难以事先确定封锁顺序

死锁的解除策略：

  1. 超时法：如果一个事务的等待时间超过了规定的时限，就认为发生了死锁；缺点：可能误判死锁，事务因为其他原因使等待时间超过时限；若时限设置得太长，死锁发生后不能及时发现。

  2. 等待图法：并发控制子系统周期性地生成事务等待图，并进行检测，如果发现图中存在回路，则发生了死锁。如果检测到死锁，一般采用的方法是选择一个处理死锁代价较小的事务，将其撤销，释放此事务持有的所有的锁，之后对撤销的事务所执行的数据修改操作必须加以恢复。

20190629194256202

并发调度的可串行性

可串行化调度：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同，称这种调度策略为可串行化(serializable) 调度。

可串行性（Serializability）是并发事务正确调度的准则，按这个准则规定，一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。

冲突可串行化调度

冲突操作是指：

  1. 不同的事务对同一个数据的读写操作和写写操作：

    • Ri (x)与Wj(x) ，事务Ti读x，Tj写x，其中i≠j

    • Wi(x)与Wj(x)，事务Ti写x，Tj写x，其中i≠j

  2. 不能交换(Swap)的动作：

    • 同一事务的两个操作

    • 不同事务的冲突操作

一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到 另一个调度Sc’ ，如果Sc’是串行的，称调度Sc 为冲突可串行化的调度。

一个调度是冲突可串行化的，那么它一定是可串行化的调度，因此，可以用这种方法来判断一个调度是否是冲突可串行化的。

冲突可串行化调度是可串行化调度的充分条件，不是必要条件，还有不满足冲突可串行化条件的可串行化调度。

两段锁协议

两段锁协议是最常用的一种封锁协议，使用两段锁协议产生的是可串行化调度（充分条件）。

两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁：

  1. 在对任何数据进行读、写操作之前，首先要申请并获取对该数据的封锁。

  2. 在释放一个封锁之后，事务不得再申请和获得任何其他封锁。

简单来说，申请锁和释放锁必须是连续的

上次更新时间: 9/25/2024, 1:17:45 AM

数据库原理：1、绪论