文档章节

并发编程的艺术03-Bakery互斥锁算法

黑帽子技术
 黑帽子技术
发布于 03/22 21:16
字数 1936
阅读 2.5K
收藏 5

导读

本章会介绍Bakery互斥锁算法,涉及到并发下的公平性问题,有界计数器和无界计数器问题, 存储单元数量下界问题。

 

公平性

无饥饿特性能够保证每一个调用 lock() 函数的线程最终都将进入临界区,但并不能保证进入临界区需要多长时间。理想情况下如果线程 A 在线程 B 之前调用 lock() 函数,那么 A 应该在 B 之前进入临界区。然而,运用现有的工具无法确定那个线程首先调用 lock() 函数。取而代之的做法是,将 lock() 函数代码划分为两个部分:
1. 门廊区: 其执行区间由有限个操作步组成。
2. 等待区: 其执行区间可能包扩无穷个操作步。

 

门廊区应该在有限步数内完成一种强约束条件。称这种约束为有界无等待演进特性。对于公平的定义:满足下面条件的锁称为先到先服务的:如果线程 A 门廊区的结束在线程 B 门廊区的开始之前完成,那么线程 A 比定不会被线程 B 赶超。

 

按照我们的惯例来举一个生活中的例子来帮助读者理解这种计算机术语都抽象描述。

QQ截图20200320142018.jpg

 

timg (2).jpg

 

大多数人都去银行办理过业务,如图1所示很多人都在等待,他们等待的依据是什么呢?总得有个先来后到吧,要不然有人插队岂不是要发生争吵了。于是银行想了一个办法给每一个来办理业务的顾客发一个号码,这个号码就是大家排队的依据。银行按照先到先服务(First-Come-First-Served)这里的“先到”指的是谁先获取到号码而不是谁先进入银行)的准则来控制当前该叫到那个号码的持有者来办理业务。这种做法就是一种保障公平性的机制。在这个例子中银行中的取号机可以抽象为前文提到的"门廊区",而客户坐在椅子上等待可以抽象为前文提到的"等待区"。

 

Bakery 算法

 

在了解了公平性之后对 Bakery 算法就很容易理解了,因为 Bakery 保证公平性的方式和前文中举的银行排号例子原理是一样的。每个线程在门廊区得到一个序号,然后一直等待,直到再也没有序号比自己更早的线程尝试进入临界区止。

该算法中 flag[A] 是一个布尔型标志,表示线程 A 是否想要进入临界区;

lable[A] 是一个整数型,说明线程进入面包店的相对次数。

Bakery 算法是无死锁的,正在等待的线程中,比定存在某一个线程 A具有最小的 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;
    }
}

 

image.png

 

有界计数器和无界计数器

在理解了 Bakery 算法后,我们再来仔细看看这个算法中的问题。首先就是存在的一个 bug ,就是 label[i] 的值会出现溢出的可能

 

image.png

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 值获取看起来像是这样:这个数是随着时间无限向后增长的,显然它是无限的 ,直到出现溢出问题。

image.png

 

为了解决这个溢出问题我们考虑使用有界的 lable 值获取,类似这样(这是只有两个线程的情况):

image.png

 

在这个有向环中是一系列的节点 n0 , n1 , ... , nk ,其中有一条边从 n0到n1,有一条边从n1到n2,最后一条边从n(k - 1) 到 nk ,并有一条边从nk返回n0。边定义结果集上的次序关系为:0 < 1 , 1 < 2 , 2 < 0。两个线程的 lable 在 0 , 1 , 2 三个节点中不断的轮转改变。

N 个 线程的情况较为复杂暂时不进行讨论,只是说明结论。

image.png

 

存储单元数量下界


还记得我们之前说过的么,会介绍一些经典但是不实用的互斥锁算法,Bakery算法就是其中之一。及时 Bakery 算法十分的简洁,无饥饿,无死锁,而且公平,那么它为什么不实用呢?最主要的问题是要读写 N 个不同的存储单元。(N 是线程的最大个数)

那么是否有更好的基于读/写存储器的锁算法可以避免这种开销呢?答案是否定的。也就是说任何一种无死锁的锁算法在最坏情况下至少需要读/写 N 个不同的存储单元。正是因为如此,才促使我们的多处理器计算机中,增加了一些功能要比读/写更强大的同步操作,并以这些操作作为互斥算法的基础。

现在我们要说明为什么这种线性下界是解决互斥问题时锁固有的。要记得一点只能通过读/写指令访问存储单元具有一个重要限制:一个线程向某个指定单元写的任何信息,在其他线程读取之前可能会被覆盖。下面是证明过程

 

image.png

 

image.png

 

image.png

 

image.png

image.png

image.png

 

image.png

 

 

image.png

image.png

image.png

image.png

 

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

 

到这里Bakery算法就讲完了,希望对你有帮助,如果觉得有收获还请点击"再看"自持作者。本人才疏学浅,如果文中有不当之处还请留言指正。

看完本文有收获?请分享给更多人

微信关注「黑帽子技术」加星标,看精选 IT 技术文章

© 著作权归作者所有

黑帽子技术

黑帽子技术

粉丝 93
博文 140
码字总数 150952
作品 2
东城
程序员
私信 提问
加载中

评论(0)

Bakery算法的简单测试程序 - 知乎

为了更好地理解Bakery算法(特别是choosing这个bool变量的作用),我们用C++实现了两个线程之间,基于Bakery算法的互斥(Bakery算法原理的讲解,请参考课堂讲解、课程PPT和我们的课本:Attiy...

算法主义
2019/10/21
0
0
linux设备驱动系列:如何处理竞态关系

综述 在上一篇介绍了linux驱动的调试方法,这一篇介绍一下在驱动编程中会遇到的并发和竟态以及如何处理并发和竞争。 首先什么是并发与竟态呢?并发(concurrency)指的是多个执行单元同时、并行...

东辉在线
2015/04/11
142
0
mark一下,以前对synchronized的理解可以扔掉了

synchronized: 有三种定义 1:普通同步方法 锁是当前实例对象 2:静态同步方法 锁是当前实例的class对象 3:同步方法块 锁定的是括号内的对象 volitle : 1:处理器会对volitle对象的写操作增加 ...

peipei巴比
03/31
0
0
linux设备驱动第五篇:驱动中的并发与竟态

综述 在上一篇介绍了linux驱动的调试方法,这一篇介绍一下在驱动编程中会遇到的并发和竟态以及如何处理并发和竞争。 首先什么是并发与竟态呢?并发(concurrency)指的是多个执行单元同时、并行...

HAOMCU
2015/04/11
624
1
互联网架构多线程并发编程高级教程(上)

基础篇幅: 线程基础知识、并发安全性、JDK锁相关知识、线程间的通讯机制、 JDK提供的原子类、并发容器、线程池相关知识点 高级篇幅: ReentrantLock源码分析、对比两者源码,更加深入理解读...

小D课堂
2018/11/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

郑州哪哪里可以开工程款发票-郑州_新闻网

【电薇同步;1.3.8 - 2.7.4.1 - 5.2.9.7.】张生、诚、信、合、作,保、真、售、后、保、障、长、期、有、效。adb的全称为Android Debug Bridge,是Android手机通用...

yyqqvip
今天
30
0
Nginx 反向代理访问

在Nginx 配置 server { listen 80; server_name www.xiaocx.org www.xiaocx.org www.xiaocx.org; root /Users/maison/work/xiaocx/dist; index i......

韩庚庚
今天
33
0
python笔记:环境变量已设置CMD中一直报错"python"不是内部命令,也不是可运行的程序或批处理文件

这些天虽然也写了几个小工具,但是打包都是在anaconda prompt中完成的,因为CMD中一直报错"python"不是内部命令,也不是可运行的程序或批处理文件,各种查度,千篇一律的是环境变量配置的问题...

小玲_001
今天
13
0
AI+BI服务模式

术语与缩写解释 缩写、术语 解 释 BI 商业智能(Business Intelligence,简称:BI),又称商业智慧或商务智能,指用现代数据仓库技术、线上分析处理技术、数据挖掘和数据展现技术进行数据分析...

zoegu228
今天
28
0
leetcode1227(面试题 17.09. 第 k 个数)--C语言实现

求: 有些数的素因子只有 3,5,7,请设计一个算法找出第 k 个数。注意,不是必须有这些素因子,而是必须不包含其他的素因子。例如,前几个数按顺序应该是 1,3,5,7,9,15,21。 示例 1:...

拓拔北海
今天
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部