DBMS中的调度类型

顾名思义，日程安排是一个将事务排成一行并逐个执行的过程。当有多个事务以并发方式运行，并且需要设置操作顺序，以便操作不会相互重叠时，调度将发挥作用，并相应地对事务进行计时。中讨论了事务和日程安排的基础 并发控制（简介） 和 DBMS中的事务隔离级别 文章。这里我们将讨论各种类型的时间表。

1. 系列时间表： 事务以非交错方式执行的调度，即串行调度是指在运行的事务结束之前不启动任何事务的调度，称为串行调度。

   例子： 考虑以下两个交易T的时间表 _1. 和T _2. .

   T 1.	T 2.
   R（A）
   W（A）
   R（B）
   	W（B）
   	R（A）
   	R（B）

   其中R（A）表示对某个数据项“A”执行读取操作 这是一个串行计划，因为事务按顺序T串行执行 _1. ->T _2.

2. 非序列时间表： 这是一种调度类型，其中多个事务的操作是交错的。这可能会导致并发问题的增加。事务以非串行方式执行，保持最终结果正确且与串行计划相同。与一个事务必须等待另一个事务完成其所有操作的串行计划不同，在非串行计划中，另一个事务在不等待前一个事务完成的情况下继续进行。这种日程安排不提供并发事务的任何好处。它可以分为两种类型，即可序列化和不可序列化计划。

   非串行调度可进一步分为可串行和不可串行。

   1. 可序列化： 这用于维护数据库的一致性。它主要用于非串行调度，以验证调度是否会导致任何不一致。另一方面，串行调度不需要可串行化，因为只有在前一个事务完成时，它才会跟随一个事务。只有当n个事务的非串行调度与串行调度等价时，才称其为可串行调度。由于在这种情况下允许并发，因此多个事务可以并发执行。可串行化的时间表有助于提高资源利用率和CPU吞吐量。这有两种类型：
      1. 冲突可序列化： 如果可以通过交换非冲突操作将计划转换为串行计划，则该计划称为冲突序列化。如果所有条件都满足，则两个操作称为冲突：
         • 它们属于不同的交易
         • 它们对同一数据项进行操作
         • 其中至少有一个是写操作
      2. 可序列化视图： 如果计划的视图等同于串行计划（无重叠事务），则该计划称为view serializable。冲突计划是可序列化的视图，但如果可序列化性包含盲写入，则可序列化的视图不可序列化冲突。
   2. 不可序列化： 不可串行化调度分为可恢复调度和不可恢复调度两种。
      1. 可收回时间表： 事务只有在其读取的更改提交之后才提交的计划称为可恢复计划。换句话说，如果某个事务 _J 读取值是否由其他事务更新或写入 _我 ，然后是T的提交 _J 必须在提交T之后发生 _我 .

         例如—— 考虑以下两个交易T的时间表 _1. 和T _2. .

         T 1.	T 2.
         R（A）
         W（A）
         	W（A）
         	R（A）
         犯罪
         	犯罪

         这是自T _1. 在T之前提交 _2. ，这使得T读取值 _2. 对的

         可回收计划可分为三种类型：

         1. 级联时间表：

            也称为避免级联中止/回滚（ACA）。当一个事务中出现故障，导致回滚或中止其他依赖事务时，这种调度称为级联回滚或级联中止。例子：

         2. 无梯级时间表： 事务只有在其更改将被读取并提交的所有事务之后才读取值的调度称为无级联调度。避免单个事务中止导致一系列事务回滚。防止级联中止的策略是禁止事务从同一计划中的另一事务读取未提交的更改。

            换句话说，如果某个事务 _J 想要读取由其他事务更新或写入的值 _我 ，然后是T的提交 _J 必须在T提交后阅读 _我 .

            例子： 考虑以下两个交易T的时间表 _1. 和T _2. .

            T 1.	T 2.
            R（A）
            W（A）
            	W（A）
            犯罪
            	R（A）
            	犯罪

            这个日程安排很简单。因为 A. 是T读的 _2. 仅在更新事务后，即 _1. 承诺。

            例子： 考虑以下两个交易T的时间表 _1. 和T _2. .

            T 1.	T 2.
            R（A）
            W（A）
            	R（A）
            	W（A）
            中止
            	中止

            它是一个可恢复的计划，但不能避免级联中止。可以看出，如果 _1. 中止 _2. 也必须中止，以保持时间表的正确性 _2. 已读取T写入的未提交值 _1. .

         3. 严格的时间表： 如果对任何两个事务T，则时间表是严格的 _我 T _J ，如果T的写入操作 _我 在T的冲突操作之前 _J （读或写），然后T的提交或中止事件 _我 也在T的冲突操作之前 _J . 换句话说，T _J 可以读取或写入T的更新或写入值 _我 只有在T之后 _我 提交/中止。

            例子： 考虑以下两个交易T的时间表 _1. 和T _2. .

            T 1.	T 2.
            R（A）
            	R（A）
            W（A）
            犯罪
            	W（A）
            	R（A）
            	犯罪

            这是一个严格的时间表，因为T _2. 读写由T写的A _1. 只有在T _1. .

      2. 不可收回时间表： 例子： 考虑以下两个交易T的时间表 _1. 和T _2. .
         

         T 1.	T 2.
         R（A）
         W（A）
         	W（A）
         	R（A）
         	犯罪
         中止

         T _2. 读T写的A的值 _1. ，并承诺。T _1. 后来中止，因此T读取的值 _2. 这是错误的，但自从 _2. 承诺，这个时间表是 不可恢复 .

注—— 可以看出：

1. 无级联计划比可恢复计划更严格，或者是可恢复计划的子集。
2. 严格计划比无级联计划更严格，或者是无级联计划的子集。
3. 串行调度满足所有可恢复、无级联和严格调度的约束，因此是严格调度的子集。

各种类型的时间表之间的关系可以描述为：

例子： 考虑以下时间表：

S:R1(A), W2(A), Commit2, W1(A), W3(A), Commit3, Commit1 

以下哪项是正确的？ （A） 该调度是视图可串行化调度和严格可恢复调度 （B） 该调度为不可串行调度和严格可恢复调度 （C） 该计划是不可序列化的计划，不是严格的可恢复计划。 （D） 该计划是可串行化计划，不是严格的可恢复计划

解决方案： 该计划可以改写为：-

首先，它是一个视图可序列化的调度，因为它具有视图相等的串行调度T _1. ->T _2. ->T _3. 满足视图序列化所需的变量A的初始和更新读取和最终写入。现在我们可以看到事务T完成了写-写对 _1. 然后是T _3. 这违反了上述严格时间表的条件 _3. 只应在T之后执行写入操作 _1. 在给定计划中被违反的提交。因此，给定的调度是可序列化的，但不是严格可恢复的。 因此，选项（D）是正确的。