首页 > 代码库 > 聊聊高并发(三)锁的一些基本概念

聊聊高并发(三)锁的一些基本概念

理解并发编程的一些基本概念很重要,给我们思考问题指明一个基本的方向。这篇说一说锁的一些基本概念。

在通常情况下我们说的锁都指的是“互斥”锁,因为在还存在一些特殊的锁,比如“读写锁”,不完全是互斥的。这篇文章说的锁专指互斥锁。


锁是处理并发的一种同步手段。单线程程序和并发程序的最终目的都是要保证程序的正确性,但是最大的区别是:

  • 单线程程序的正确性只关注程序的运行结果和目标是一致的
  • 并发程序的正确性除了运行结果正确外,还包含了活性的特性,所谓活性,指的就是程序无死锁,无饥饿

所以考察一个锁,也需要从三个方面考察:

1. 互斥性

2. 无死锁

3. 无饥饿


最简单的锁只保证互斥性,而互斥性本质上可以用一个布尔值表示,即一个二元状态。

互斥是保证并发程序正确性的一种特性,和互斥相关的一个专用名词就是临界区

临界区指的是“某个时刻仅能被一个线程执行的代码段”,也就是通常锁的被锁保护的代码段。


一个互斥锁的定义通常如下

interface Lock {
     public void lock();
     public void unlock();
}

线程必须用指定的方式使用锁,lock动作必须在try块之前调用,如果lock在try里面执行,可能会在取到锁之前抛出异常,导致执行了unlock动作,从而发生错误。

熟悉Java显示锁的同学肯定知道使用ReentryLock就是如下的用法。

mutex.lock();
try{
 ...临界区
}finally{
    mutex.unlock()
}

互斥意味着串行,也意味着等待。 这引出了著名的Amdahl定律

Amdahl定律: 即完成一个工作能获得的加速比,受限于这个工作中必须被串行的部分。(通常串行部分都是因为被互斥锁保护了)

加速比的定义是一个处理器完成一个工作的时间和采用n个处理器并发完成该工作的时间比。

Amdahl定律给出的加速比如下

S = 1 / ( 1 - p + p/n)

S为加速比
1为完成工作的时间
p指可以并行的部分
n指处理器个数

从Amdahl定律可以看出,串行的工作越多,获得的加速比就越小。

Amdahl给我们编程实际启示有:

1. 尽量减小互斥锁的粒度,锁粒度越小表示串行的部分越少

2. 能不用锁,就不要用锁。不用锁表示串行的部分越少


接下来说说活性相关的概念。

死锁意味者系统冻结最终相关的所有线程都永久地停滞等待。

饥饿则是总有一些线程能够运行一小部分线程永久停滞等待


所以无饥饿意味着肯定无死锁。但是无死锁不意味着无饥饿。


《多处理器编程的艺术》一书中给出了几种锁的实现,其中Peterson算法可以保证两个线程使用锁的时候锁具备互斥,无死锁,无饥饿特性。

class Peterson implements Lock {
     private boolean[] flag = new boolean[2];
     private int victim;
     public void lock(){
           int i = ThreadID.get();
           int j = 1 - i;
           flag[i]= true;  // 保证两个线程先后运行不死锁,实现互斥 
           victim = i;  // 保证两个线程同时运行时不死锁,实现互斥
           while(flag[j] && victim == i){}  // 互斥意味着等待
     }

     public void unlock(){
           int i = ThreadID.get();
           flag[i] = false;
    }

}

Bakery锁支持n个线程的互斥协议。通过数学证明了:

n线程的无死锁互斥算法需要n个不同的存储单元(变量)来保存中间状态。






聊聊高并发(三)锁的一些基本概念