经典互斥算法1
需积分: 0 26 浏览量
2022-08-04
12:55:07
上传
评论
收藏 192KB PDF 举报
经典互斥算法
郑思遥
*
2013 年 1 月 4 日
摘要
本文用较为轻松的方式介绍了几个经典的互斥算法：
Dekker 算法、Dijkstra 提出的算法、Peterson 算法和面包
店算法，并简单地给出了每一个算法的正确性证明和相
关的讨论。
1 互斥问题的定义
互斥（mutual exclusive）是我们现在进行多线程编程
的一个基本工具。本文探寻分布式计算历史上的几个非
常有名非常经典的互斥算法，尽管这些算法几乎是所有
操作系统、分布式系统或多线程编程课本中必介绍的算
法，可是由于这些算法由于性能问题已经被现代的算法
或机制替代了，实际中不会有人使用这些算法。尽管如
此，了解这些算法可以帮助我们理解同步领域的基本原
理。此外，了解这些算法的正确性证明可还可以训练并发
算法正确性推导的思维。
互斥问题最早是 Edsger W. Dijkstra
1
在 1965 年的 ACM
通讯中正式提出的 [Dij65]。文中的问题描述如下：有 N
台计算机都在重复执行某项任务，这项任务中有一段称
为 “临界区”，要求同一时刻这 N 台计算机中只能有一台
在临界区中。计算机之间可以通过共享的存储空间协调
访问临界区。写入和读取临界区的操作是不可分割的。解
决方法必须满足以下特点：
1. N 台计算机是对称的，没有指定的优先级；
*
zhengsyao@gmail.com，http://weibo.com/zhengsyao/
1
Edsger W. Dijkstra 是计算机发展历史上的重要人物，除了耳熟能详
的计算最短路径的 Dijkstra 算法，他也是分布式计算领域的开创者，重
要成果包括信号量和哲学家就餐问题。Dijkstra 卒于 2002 年，同年其
1974 年的论文 “Self-stabilizing systems in spite of distributed control” 被授
予 ACM PODC（Symposium on Principles of Distributed Computing）最有
影响力论文奖。为了纪念这位科学家，PODC 最有影响力论文奖在 2003
年更名为 Dijkstra 奖。
2. 对 N 台计算机的速度不做任何假设，甚至同一台计
算机的速度也不一定是固定不变的；
3. 如果某台计算机在临界区之外停机了，那么不允许
导致其他计算机阻塞；
4. 不允许发生 “Aer you”–“Aer you” 阻塞，也就是说，
如果所有计算机都没有在临界区中，那么必须允许
一个——只允许一个——计算机进入临界区。
这个问题看上去挺简单，其实不容易，因为每一台计算机
每一次只能发出一次读写请求，按照现在的话说，就是在
缺少 read-modify-write 这类原子操作的情况下要实现互
斥是很难的。
在那个没有多核处理器或多处理器计算机的年代，
一台 “计算机” 同时只能执行一个线程，所以原文中的 “计
算机” 用现在的话来说就是一个处理器或多核处理器中的
一个核心或一个硬件线程，“共享的存储空间” 可以是线
程或进程间的共享内存，访问共享内存的方式可以是直
接在总线上访问或通过互联网络访问或通过多核处理器
内部的互联网络访问。为了统一术语，本文使用最常用的
多线程编程使用的术语。
2 经典互斥算法
2.1 Dekker 算法
Dekker 算法是第一个正确地通过软件方法解决两
线程互斥问题的算法，该算法最早由 Dijkstra 在 [Dij68a]
中描 述， 算 法 1 就 是 Dekker 算法。 算 法中 的 status[1]
和 status[2] 分 别 表 示 两 个 线程 的 状 态， 状态 可 以 取值
competing 和 out。如果状态取值 competing，表示当前线
程处于正在竞争进入临界区的状态；如果状态取值为 out，
则表示这个线程放弃尝试进入临界区或已经退出临界区。
1
资源评论
