并发编程的艺术03-Bakery互斥锁算法
导读
本章会介绍Bakery互斥锁算法,涉及到并发下的公平性问题,有界计数器和无界计数器问题, 存储单元数量下界问题。
公平性
门廊区应该在有限步数内完成一种强约束条件。称这种约束为有界无等待演进特性。对于公平的定义:满足下面条件的锁称为先到先服务的:如果线程 A 门廊区的结束在线程 B 门廊区的开始之前完成,那么线程 A 比定不会被线程 B 赶超。
按照我们的惯例来举一个生活中的例子来帮助读者理解这种计算机术语都抽象描述。
大多数人都去银行办理过业务,如图1所示很多人都在等待,他们等待的依据是什么呢?总得有个先来后到吧,要不然有人插队岂不是要发生争吵了。于是银行想了一个办法给每一个来办理业务的顾客发一个号码,这个号码就是大家排队的依据。银行按照先到先服务(First-Come-First-Served)(这里的“先到”指的是谁先获取到号码而不是谁先进入银行)的准则来控制当前该叫到那个号码的持有者来办理业务。这种做法就是一种保障公平性的机制。在这个例子中银行中的取号机可以抽象为前文提到的"门廊区",而客户坐在椅子上等待可以抽象为前文提到的"等待区"。
Bakery 算法
在了解了公平性之后对 Bakery 算法就很容易理解了,因为 Bakery 保证公平性的方式和前文中举的银行排号例子原理是一样的。每个线程在门廊区得到一个序号,然后一直等待,直到再也没有序号比自己更早的线程尝试进入临界区止。
lable[A] 是一个整数型,说明线程进入面包店的相对次数。
class BakeryLock implements Lock { private boolean[] flag; private int[] label; private int n; public BakeryLock(int n) { this.n = n; flag = new boolean[n]; label = new int[n]; for (int i = 0;i < n; i++) { flag[i] = false; label[i] = 0; } } public void lock() { int i = ThreadID.get(); flag[i] = true; label[i] = max(label) + 1; for (int k = 0; k < n; k++) { while ((k != i) && flag[k] && ((label[k] < label[i]) || ((label[k] == label[i]) && k < i))) { } } } public void unlock() { flag[ThreadID.get()] = false; } private int max(int[] elementArray) { int maxValue = Integer.MIN_VALUE; for (int element : elementArray) { if (element > maxValue) { maxValue = element; } } return maxValue; } }
有界计数器和无界计数器
在理解了 Bakery 算法后,我们再来仔细看看这个算法中的问题。首先就是存在的一个 bug ,就是 label[i] 的值会出现溢出的可能。
lable 值是无限增长的,因此在生命周期很长的系统中不得不考虑溢出的问题。如果某个线程的 lable 在其他线程都不知情的情况下从一个很大的数返回到 0 ,那么公平性将被破坏。例如到2038年1月18日,Unix 的 time_t 数据结构将会溢出,因为其秒数值是从 1970 年 1 月开始计算的,而在那一刻将会超过 2 的 32 次方。大多数采用 64-bit 计数器的应用程序在其声明周期内是不可能发生这种“回零”问题的。
Bakery 算法保证公平性的做法是确保某个线程在另一个线程之前得到一个 lable 值,那么后一个线程的 lable 值一定比前者大。通过仔细观察 Bakery 算法代码,我们可以得出一个线程需要具备两种能力:
1. 读取其他线程的 lable (扫描)。
2. 为自己设置一个更大的 lable (标记)。
这时候的 Bakery 算法中的 lable 值获取看起来像是这样:这个数是随着时间无限向后增长的,显然它是无限的 ,直到出现溢出问题。
为了解决这个溢出问题我们考虑使用有界的 lable 值获取,类似这样(这是只有两个线程的情况):
在这个有向环中是一系列的节点 n0 , n1 , ... , nk ,其中有一条边从 n0到n1,有一条边从n1到n2,最后一条边从n(k - 1) 到 nk ,并有一条边从nk返回n0。边定义结果集上的次序关系为:0 < 1 , 1 < 2 , 2 < 0。两个线程的 lable 在 0 , 1 , 2 三个节点中不断的轮转改变。
N 个 线程的情况较为复杂暂时不进行讨论,只是说明结论。
存储单元数量下界
还记得我们之前说过的么,会介绍一些经典但是不实用的互斥锁算法,Bakery算法就是其中之一。及时 Bakery 算法十分的简洁,无饥饿,无死锁,而且公平,那么它为什么不实用呢?最主要的问题是要读写 N 个不同的存储单元。(N 是线程的最大个数)。
那么是否有更好的基于读/写存储器的锁算法可以避免这种开销呢?答案是否定的。也就是说任何一种无死锁的锁算法在最坏情况下至少需要读/写 N 个不同的存储单元。正是因为如此,才促使我们的多处理器计算机中,增加了一些功能要比读/写更强大的同步操作,并以这些操作作为互斥算法的基础。
现在我们要说明为什么这种线性下界是解决互斥问题时锁固有的。要记得一点只能通过读/写指令访问存储单元具有一个重要限制:一个线程向某个指定单元写的任何信息,在其他线程读取之前可能会被覆盖。下面是证明过程
到这里Bakery算法就讲完了,希望对你有帮助,如果觉得有收获还请点击"再看"自持作者。本人才疏学浅,如果文中有不当之处还请留言指正。
看完本文有收获?请分享给更多人
微信关注「黑帽子技术」加星标,看精选 IT 技术文章
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
现实比理论要复杂
我们试想一个实际问题,春天到了,我们要买衣服了,同时,作为服装厂商,也要开始发布新的衣服了,如果你作为一个服装厂商的技术顾问,请你分析出什么样的衣服属于今年的流行趋势,你会怎么做? 首先,作为技术宅男的你,我不认为你会对流行元素有那么多的关注,不会去看什么巴黎时装周,你能做的就是根据各种各样的数据进行分析预测。你可能会在店铺中进行一些扫码填写调查表发放一些优惠券,还可能去各大时尚网站去扒一些评论分析文章,还可能去微博这种公开的社交平台扒一些时尚博主的自拍分享等,你可以想尽办法获取各种各样的数据,你要做的是用好这些数据分析出流行趋势。 对于这种分析预测深度学习无疑是适合的模型工具,问题是既有这种调查表得来的数据,适合普通的层堆叠进行训练的模型,还有这种评论分析文章这种文本数据,适合循环神经网络的文章,还有各种图片需要分析,适合卷积神经网络的模型,这可怎么办?根据我们现有的知识,我们可以考虑分别训练不同的网络模型,对他们进行加权分析,这固然是一种方法,但是这个权也太随机了,各个数据之间也都割裂开了,分别处理算不上好的方法。那怎么办? 将他们联合起来,进行联合学习,大致的样子就是这样: 当然...
- 下一篇
RetroArch 1.8.5 发布,跨平台模拟器
RetroArch 1.8.5 发布了。RetroArch 是款功能强大的跨平台模拟器,不但能够模拟许多不同的游戏主机,还能在 Windows、MacOS、Linux、Android、iOS 以及多种游戏主机上执行。 主要更新内容如下: 新的默认菜单——Ozone 根据官方之前举行的投票结果,Ozone 成为了 RetroArch 的默认菜单驱动程序。如果仍然想使用上一个菜单(XMB),可以转到“设置”,“驱动程序”,将“菜单”更改为 “xmb”,然后重新启动 RetroArch。 Ozone 菜单的缩放比例也进行了一些重要更改。现在,它可以基于 DPI 进行缩放,并且还可以将缩放比例配置为适合自己的首选项的内容。现在,小部件/通知也已适当缩放。 重要的错误修复/崩溃修复 修复了一个重要错误,该错误会阻止 RetroArch 在 64 位 x86 Chromebook 硬件上启动。 Linux 上的线程视频驱动程序以前对于 OpenGL 非常不稳定。官方表示已设法解决了大多数此类问题。 更多详情见发布公告: https://www.libretro.com/index.php/retr...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS7,CentOS8安装Elasticsearch6.8.6
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- Red5直播服务器,属于Java语言的直播服务器
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS8编译安装MySQL8.0.19
- CentOS关闭SELinux安全模块
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作