第八章并发控制-北京尧图网络

第八章并发控制8.1 基于锁的协议8.1.1 锁的基本概念锁是控制对数据项并发访问的机制。两种锁模式模式符号允许操作请求指令排他锁X可读可写lock-X(D)共享锁S只读lock-S(D)锁请求提交给并发控制管理器事务仅在请求被授予后才能继续执行。8.1.2 锁相容矩阵SXS✓ 相容✗ 不相容X✗ 不相容✗ 不相容任意数量的并发事务可持有同一数据项的共享锁但若某事务持有排他锁其他事务不能持有任何锁。8.1.3 仅靠加锁不够以下示例说明仅加锁并不足以保证可串行化T2: lock-S(A); read(A); unlock(A); lock-S(B); read(B); unlock(B); display(AB)若 A 值在unlock(A)后、read(B)前被另一事务修改AB 的结果反映的将是不一致的快照。8.1.4 锁协议锁协议是所有事务在请求和释放锁时遵循的一组规则通过限制可能的调度集合来强制可串行化。概念定义合法调度由一组遵循协议的并发事务生成的调度协议确保可串行化该协议下所有合法调度都是可串行化的8.2 死锁与饥饿8.2.1 死锁考虑以下部分调度时刻T3T41lock-X(B)2read(B)3B : B - 504write(B)5lock-S(A)6read(A)7lock-S(B)←等待8lock-X(A)←等待T4 持有 A 的 S 锁等待 B 的 S 锁被 T3 的 X 锁阻塞T3 持有 B 的 X 锁等待 A 的 X 锁被 T4 的 S 锁阻塞两者互相等待→死锁处理死锁回滚 T3 或 T4 中的一个释放其持有的锁。8.2.2 饥饿若并发控制管理器设计不当可能出现饥饿某事务一直在等待某数据项的 X 锁但一连串其他事务不断请求并获取该数据项的 S 锁 →永远等不到 X 锁同一事务因死锁被反复回滚并发控制管理器可设计为避免饥饿。8.3 两阶段锁协议8.3.1 基本两阶段锁 (2PL)确保冲突可串行化的协议。阶段规则阶段 1增长阶段事务可获取锁但不能释放任何锁阶段 2收缩阶段事务可释放锁但不能获取新锁可串行化保证事务按锁点事务获取最后一次加锁的时刻的顺序串行化。2PL 的不足不能保证无死锁不能保证可恢复性或无级联回滚8.3.2 扩展两阶段锁协议规则保证严格两阶段锁事务必须持有所有排他锁直到 commit/abort可恢复无级联强两阶段锁事务必须持有所有锁含 S 锁直到 commit/abort按提交顺序串行化大多数数据库实现强两阶段锁但简称其为两阶段锁。8.3.3 锁转换带锁转换的 2PL阶段允许的操作增长阶段获取 S 锁获取 X 锁将 S 锁升级为 X 锁收缩阶段释放 S 锁释放 X 锁将 X 锁降级为 S 锁锁转换协议同样确保可串行化。8.4 锁的自动获取事务只需发出标准的read/write指令无需显式调用锁操作。read(D) 的处理流程if Ti 已在 D 上有锁 then read(D) else 等待直到无其他事务持有 D 上的 X 锁授予 Ti 在 D 上的 S 锁 read(D)write(D) 的处理流程if Ti 已在 D 上有 X 锁 then write(D) else 等待直到无其他事务持有 D 上的任何锁 if Ti 已在 D 上有 S 锁 then 将 D 上的锁升级为 X 锁 else 授予 Ti 在 D 上的 X 锁 write(D)所有锁在 commit 或 abort 后释放强 2PL。8.5 锁管理的实现锁管理器可实现为独立进程事务通过消息发送锁和解锁请求锁管理器回复锁授予消息或在死锁时回复回滚消息请求事务等待直到收到回复锁表锁管理器在内存中维护一个锁表数据结构记录内容说明已授予的锁深色标记等待中的请求浅色标记锁类型记录授予或请求的锁类型操作规则新请求添加到等待队列末尾若与所有已授予锁相容则立即授予解锁导致该请求从队列中删除后续请求重新检查相容性事务中止时其所有等待/已授予锁的请求全部删除8.6 基于图的协议8.6.1 基本思想对所有数据项D { d 1 , d 2 , … , d h } D \{d_1, d_2, \ldots, d_h\}D{d1,d2,…,dh}施加偏序→ \to→若d i → d j d_i \to d_jdi→dj则任何同时访问两者的事务必须先访问d i d_idi再访问d j d_jdj。将 D 视为有向无环图——称为数据库图。8.6.2 树协议树协议是图协议的最简形式规则说明仅排他锁只允许 X 锁首次加锁任意T i T_iTi的第一个锁可在任意数据项上父节点先锁后续锁定数据项 Q 必须先锁定 Q 的父节点随时解锁数据项可随时解锁不可重锁已锁定并解锁的数据项不能再次锁定8.6.3 树协议 vs 2PL优势劣势确保冲突可串行化且无死锁协议不保证可恢复性或无级联可更早解锁→ 等待时间更短、并发度更高事务可能被迫锁定不需要访问的数据项 → 增加锁开销无需死锁回滚需要引入提交依赖来保证可恢复性树协议和两阶段锁各自可生成对方无法生成的调度。8.7 死锁处理系统处于死锁状态存在一组事务集合其中每个事务都在等待该集合中的另一个事务。8.7.1 死锁预防策略 1预声明——要求每个事务在执行之前锁定其所有数据项。策略 2偏序加锁——对所有数据项施加偏序事务只能按偏序指定的顺序锁定数据项图协议。策略 3Wait-Die 方案非抢占事务角色行为旧事务等待新事务✓ 允许等待新事务等待旧事务✗ 不允许新事务回滚die一个事务可能死多次才能成功获取锁。回滚后使用原始时间戳重启。策略 4Wound-Wait 方案抢占事务角色行为旧事务等待新事务✗ 旧事务伤害强制回滚新事务新事务等待旧事务✓ 允许等待Wound-Wait 比 Wait-Die 有更少的回滚。两种方案均保证旧事务优先于新事务 → 避免饥饿。策略 5超时方案事务等待锁仅等待指定时间超时即回滚简单但可能无故回滚无死锁时也超时难以确定合适的超时间隔可能发生饥饿8.7.2 死锁检测等待图顶点事务从T i → T j T_i \to T_jTi→Tj的有向边T i T_iTi在等待T j T_jTj持有的锁冲突模式系统处于死锁状态⟺ \iff⟺等待图中有环。检测方式周期性地调用死锁检测算法寻找环。检测到死锁后的恢复步骤做法选择牺牲者选择代价最小的事务回滚回滚全部回滚中止事务然后重启部分回滚仅回滚到释放所需锁的位置避免饥饿死锁集合中最老的事务永远不会被选为牺牲者本章重点锁是并发控制的核心机制——理解 S 锁/X 锁的相容矩阵、两阶段锁增长/收缩如何保证可串行化、严格 2PL 与强 2PL 的重要性可恢复无级联、锁管理器与锁表的实现、树协议的无死锁特性及其与 2PL 的取舍、Wait-Die/Wound-Wait 两种抢占策略的区别旧事务优先、以及等待图死锁检测的环判定原则。

第八章并发控制

相关推荐

行业内专业的工业电源厂商

硬件工程师工具网站2024精选：9大场景30+站点实测与效率对比

STM32 SPI 模式配置实战：W25Q64 Flash 读写时序与 CPOL/CPHA 寄存器详解

更多资讯

如何做好网站搜索引擎优化免费工具推荐

网页制作用什么工具选哪家好

《投资入门指南》如何快速开始定投标普500？普通人的简单又可靠的捷径

当自动驾驶遇见纽北：极限赛道测试背后的技术逻辑与架构选型

USB转I2C与Excel联动：3400KHz高速I2C总线扫描测试

瑞芯微RV1126B SDK移植实战：从DDR配置到USB调试

今日更新

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？