Ericson博客

每天努力一点点

0%

从养金鱼到线程同步的哲学原理

发表于 更新于 分类于

前言

计算机操作系统是一门“人造的”系统；处处都透露这人类的思考惯性，人性的哲学原理。从人类本身的处理角度去理解操作系统中线程的各种原理是很有必要的，会让你对线程的理解更加深刻。

背景

如我们所知，进程是一段运转的程序，是为了CPU上实现多道编程而发明的一个概念。在操作系统层面，进程是一系列计算机指令的聚合。当进程遇到阻碍时，比如用户输入等，会阻塞整个进程；后续跟输入无关的指令也得不到执行；因此，把进程中的指令分为几份不同的功能；每一份就是所谓的“线程”。
线程模型

基于上述的描述，我们对线程进行定义：线程就是在进程里一个单独的顺序控制流。至于进程把哪些指令切分成进程，后面文章再进行分析。下面我们开始养金鱼。

养金鱼

有一间屋里有三个房间；其中两个房间住着人（Tom和Jerry），另一个房间养了条金鱼；金鱼需要两个人进行喂养，金鱼有个很大的特点，就是没有饱的感觉，会不停的吃直到撑死自己；如果两个人先后都喂养了金鱼，金鱼就会撑死；如果两个人先后都没有喂养金鱼，金鱼会饿死；（假设不考虑给两个人排班的情况，两个人的行为不受约束）。

上述的两个人就相当于两个线程，而金鱼则是临界资源；这就是一个线程同步的问题？线程同步的目的就是为了让多个线程不管执行的时候如何穿插，其运行结果都是正确的。

为了养好金鱼，Tom和Jerry只能做如下约定：
（1）每天喂鱼一次，且仅一次；
（2）如果今天Tom喂了鱼，Jerry今天就不能喂鱼了；反之亦然；
（3）如果今天有一人没有喂鱼；另一个必须喂鱼；不然鱼会饿死；

原始阶段

在非同步的情况下，Tom和Jerry只能靠经验来判断鱼是否已经被喂过；比如两个线程，Tom线程来查看鱼是否已喂的时候，发现鱼并没有喂，准备进行喂食；这个时候线程切换到Jerry，Jerry同样检查鱼的状态，发现鱼还没有喂，进行喂食；然后线程又切回Tom，Tom进行喂食；这样鱼撑死了。

时间 Tom Jerry
10:00 check feed status
10:05 check feed status
10:10 feed fish
10:15 feed fish

留字条阶段

由于上述两个线程都对鱼状态进行了数据竞争，同一时刻访问了同一个数据（鱼的状态）。要防止鱼撑死，Tom和Jerry开始商量如何防止数据竞争；最简单的方法就是同一时刻不让两个人查看鱼的状态，这就需要协调两个线程；只有一个线程可以进入临界区，这称为互斥。
那怎么确保一次只有一个人在临界区呢？
显而易见，自然是让两个人进行交谈；如果Tom和Jerry一个早班一个晚班，正常碰不到面，那最简单的办法就是留字条；

留字条的做法就相当于两个线程之间的共享内存，一个线程对内存的修改对另一个线程可见；

于是Tom和Jerry的流程就变成了先去检查字条；

1
2
3
4
5
6
7
8
## Tom, Jerry
if (noNote){
  leave note;
  if (noFeed){
    feed fish;
  }
  remove note;
}

上面的程序看似用了字条这样的互斥手段，实际并没有达到互斥的目的；金鱼依然有撑死的风险（当两个程序都进入了检查字条的条件中）；本方案并没有解决鱼撑死的问题，但有所改进，降低了鱼撑死的概率。

互斥留字条阶段

仔细分析上面留字条的程序，会发现程序没有解决的根本原因在于先检查字条，然后再留字条，这造成了一个空档，当第二个线程在空档时切换过去，就造成了鱼撑死。

如果修改下顺序，先留字条，然后再检查字条状态是否会有用？需要区分下是谁留的字条。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
## Tom
leave noteTom;
if (no noteJerry){
  if (no feed){
    feed fish;
  }
}
remove noteTom;

## Jerry
leave noteJerry;
if (no noteTom){
  if (no feed){
    feed fish;
  }
}
remove noteJerry;

这样不管线程怎么穿插，总有一个留字条的动作在检查这个字条之前，这样就避免了鱼撑死的可能。
那这个程序成功了？NO。
如果上述程序两个穿插执行，那么将没有一个人去喂鱼，鱼会饿死。因此程序还是不对的，没有达到最终的效果。但是对于计算机而言，饿死对于撑死是一种改善：如果撑死，程序运行可能出错；而饿死，大家都拿不到资源，线程处于阻塞状态，停止推进，不一定会产生错误。

循环等待阶段

分析上面的饿死原因，因为没有人进入临界区；互斥是保证同一时间只有一个线程进入临界区；现在是互斥过头了，两个线程没有一个进入临界区，导致没有人喂食，鱼饿死了。
这个时候就必须保证有一个人一定进入临界区，怎么办？
当你去买喜茶时，一直买不到，能怎么办，一直等呗。最粗暴最简单的方法。
在这边也是，为了能有一个人进入临界区，保证鱼一定有人喂；因此需要有一个人一直等待，我们暂定Tom。

1
2
3
4
5
6
7
8
9
## Tom
leave noteTom;
while(noteJerry){
  do nothing;
}
if (no feed){
  feed fish;
}
remove noteTom;

检查下发现，现在鱼不会出现饿死和撑死的情况了，是否大功告成了?

对称之美

上面的程序解决了金鱼的生计问题；但是会带来两个问题：
（1）Tom一直在空等待，浪费资源；

空等待还可以造成线程优先级倒挂的问题；高优先级的空等待等待低优先级的资源；就像总统要听平民的话一样；

（2）Tom和Jerry都是喂金鱼的，但是程序不一样，不是对称的；Tom要多做事；不美观，两套维护逻辑；
此外，不对称的程序会增加理论证明的困难，这边不详细展开。

那怎么解决这两个问题呢？
不好解决。如果去除了空等待，则会出现饿死的情况；如果要对称，两边都是空等待，一样会造成饿死情况。推进似乎走到了尽头。

锁阶段

我们再看看留字条阶段，之所以出现撑死的原因在于：检查字条和留字条之间出现了空档，正是这个空档的存在，导致鱼可能会撑死。
从人的角度出发思考，显而易见的会想如果这个空档不出现，是否就不会撑死了???

之前我们的思考都是基于指令级的，在一个非常低的层次上打转；因为是指令层的，所以就没办法消除指令之间的空档；现在指令层次已经无能为力了，应该提高抽象层次，将思路上升到一组指令的控制。
在金鱼问题中，我们陷入了金鱼和字条贴鱼缸的层次来思考怎么同步养金鱼；那是否可以上升一个层次从放置鱼缸的房间的层次来考虑养金鱼的问题。

基于上面的分析，检查字条和留字条我们当成一个操作，变相的就是房间上锁的操作，只能保证一个人进入房间（进入房间唯一做的事就是喂金鱼）；这样问题就转换为：
（1）如果保证同时只有一个人进房间；（防止撑死）
（2）每天必须有一个人进房间；（防止饿死）

这在生活中最常见的做法就是：一个人进去后锁门，那么另一个人一定进不去该房间。这就是锁的概念。

1
2
3
4
5
6
7
8
9
10
11
12
13
##Tom
lock();
if (no feed){
  feed fish;
}
unlock();

##Jerry
lock();
if (no feed){
  feed fish();
}
unlock();

由上述程序可以看出，同一时间只会有一个人进入房间进行喂食，鱼不会撑死；当程序执行时，总有一个人会进入房间进行喂食，鱼不会饿死；并且程序还是对称的；完美~~

锁应该具备的特性：

  • 锁的初始状态是打开状态；
  • 进入临界区前必须获得锁；
  • 出临界区时必须打开锁；
  • 如果别人持有锁，则必须等待；
    留字条就相当于锁，但是它不满足于第四个条件，别人持有锁时，没有等待，所以不能互斥；

锁优化阶段

上述程序完美的实现了Tom和Jerry的需求，金鱼可以很好的生活了；但是运行了一段时间后，Tom发现一个问题；当Jerry进入房间喂鱼时，Tom需要一直等待在外面，而Jerry喂鱼比较慢，Tom觉得很浪费时间，怎么办？？？
去除锁是很不现实的，因为就是靠锁来保证互斥；但是我们可以减少锁的时间；喂鱼这个耗时动作没必要放在锁里；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
## Tom
lock();
if (no noteJerry){
  leave noteTom;
}
unlock();
if (no noteJerry){
  if (no feed){
     feed fish;
  }
  remove note;
}

## Jerry
lock();
if (no noteTom){
  leave noteJerry;
}
unlock();
if (no noteTom){
  if (no feed){
    feed fish();
  }
  remove note;
}

这个程序把喂食独立出了锁，相当于锁门只是为了再鱼缸上贴个字条，然后在后续的任意时间段根据字条来喂食；现在加锁的步骤只有贴字条，这个动作很快。

睡觉和叫醒阶段

不管上述程序锁的内容多么精简，依然存在这锁等待的情况；占用CPU资源在空跑，那么怎么解决这种现象？？？
在日常人类生活中，如果需要长时间等待，则最常见的做法是先去做其他事，等过段时间再来看看等待的事有没有好；或者让等待完成的事通知你。
计算机的思想也是一样的，如果出现等待，那么这个等待的线程需要让出CPU给其他线程执行，这样才能保证CPU资源利用率最大化。如果对方持有锁，则不需要等待，而是直接去睡觉；等对方释放锁的时候再唤醒你。这就是最典型的生产者和消费者的场景。

现在问题升级了！！！
Tom和Jerry为了保持鱼的活性，在房间里装了很多通水的管子，鱼可以在房间里任意游动；那么生产者和消费者在这边是什么场景？
鱼缸是一个固定的投食点，Tom和Jerry是生产者，鱼是消费者，Tom和Jerry每天定时生产饲料；鱼则每天消费饲料。
当投食点里没有食物时，鱼就去游动或者睡觉；然后每天会自动通知Tom和Jerry进行生产饲料；当饲料生产出来后，Tom和Jerry会通过超声波通知鱼来吃饭。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int  count=0;
void producer(){
  while(true){
    produce item;
    if (count == 1){
       sleep();
    }
    insert item;
    count = count+1;
    if (count == 1){
       wakeup(consumer);
    }
  }
}

void consumer(){
  while(true){
    if (count==0) sleep();
    remove item;
    count = count - 1;
    if (count == 0) wakeup(producer);
  }
}

上述程序是一个典型的生产者和消费者的简易代码；会有什么问题吗？（count共享变量应该要加锁控制，这边不展示）
比如，消费者先执行，当它判断现在count==0时，也就是现在还没有生产任何物品，这个时候CPU切换到了producer；producer生产物品，并一直执行到最后的wakeup，由于现在消费者还没有执行sleep操作，wakeup相当于做了个无用功；之后CPU又切换到了consumer，然后执行sleep操作；这样再执行producer时，也会因为物品已满而sleep；问题就来了，producer和consumer都sleep了；整个流程阻塞了，死锁了。

这个问题的根源在哪？？？
因为之前的wakeup操作丢失了，如果这个wakeup操作没有丢失，而是保存着，当consumer sleep后操作又被执行，问题就不存在了。

信号量

信号量：能够将系统发送的信号累积起来的操作系统原语。
简单的来说，信号量就是一个计数器，其值就是信号累积的数量。如果将信号量的值限制为0和1，则该信号量就是一把锁。
上述生产者和消费者的问题就可以通过三个信号量来解决。

  • mutex：互斥信号量，保证只有一个线程操作缓冲区；
  • full：缓冲区计数信号量，商品数量；
  • empty：缓冲区计数信号量，缓冲区空位数量；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int mutex = 1;
int empty = 1;
int full = 0;
void producer(){
  while(true){
    produce item;
    empty--;
    mutex--;
    insert item;
    mutex++;
    full++;
  }
}

void consumer(){
  while(true){
    full--;
    mutex--;
    remove item;
    mutex++;
    empty++;
  }
}

只有full==0和empty==0同时成立，才会出现生产者和消费者同时睡眠的情况，显然是不成立的。

为啥需要full和empty两个信号量，因为生产者和消费者等待的信号不同，需要在不同的信号量上睡眠。

为了实现线程同步，我们引入了锁；但是锁又带来循环等待的问题，为此我们又引入了睡觉与叫醒；但又带来了死锁的问题，又引入了信号量；操作系统的演化深深的反映着“人造”这两个字。
那么信号量是不是就是操作系统终极原语了？？？

我们先来看下信号量对于生产者和消费者的代码：
如果将消费者的full–和mutex–顺序交换下，会出现啥问题；消费者先互斥进入缓冲区，然后full–，发现没有物品，则等待；这个时候生产者开始执行，先empty–，然后mutex–；由于这个时候消费者已经在缓存区了，生产者将不能进入缓存区；死锁；
由此可见信号量的操作顺序非常重要，稍有不慎，就容易死锁；如果一个程序中有几十个信号量，那么他们之间的顺序将非常复杂，编写这样的信号量代码将是非常反人类的，那有什么办法解决？？？

管程

由于信号量编写和维护的复杂性，很难真正的被应用。在人类的哲学中，每个人擅长的东西不一样，比如家里的洗衣机坏了，你不会自己去修，而是找专门的人来修，这就是术业有专攻（你不行的时候，把困难交给别人）。因此在操作系统中，信号量的组织工作自己做不了，就交给一个专门的构造来负责，程序员就解脱了。这个构造就是管程。

管程是一个程序语言级别的构造，它的正确运行是通过编译器保障的。管程的英文是monitor；是一组子程序、变量和数据结构组成，把需要同步的代码至于管程中，由编译器保证任何时候只有一个线程在管程中运行。

管程有两种同步机制：锁和条件变量。锁用来控制互斥；条件变量就是线程等待的东西，用来控制执行的顺序。

一个管程包含了：

  • 多个彼此可以交互并且共享资源的线程；
  • 多个与资源使用相关的变量；
  • 一个互斥锁；
  • 条件变量；
    管程其实就是对信号量的面向对象的封装。东尼·霍尔证明了管程与信号量是等价的。管程比信号量更加安全可控，容易差错。

消息传递

那么管程有没有什么问题呢？
管程最大的问题就是对编译器的依赖。编译器在编译管程时，需要在其前后加上同步原语。
另一个问题是：管程只适用于单机系统；现在的分布式系统完全不适用。

如果需要在网络环境下进行同步，靠的是消息传递。消息传递分为send和receive两个操作系统的系统调用。
以生产者消费者为例，生产者先等待空盒消息，如果有空盒，则生成物品，放入盒子，并发送给消费者；消费者先发送空盒消息，然后等待生产者发送的物品消息，最后再发送空盒消息，消费物品。

消息传递的优点有很多，是当前使用非常普遍的线程同步机制。同事消息传递也有很大的缺点：最大的问题就是消息的丢失和身份识别。
消息在网络环境丢失的概率还是很大的；而且也需要确定你收到的消息确实是你想要的人发送的。于是就诞生了很多可靠的协议，比如TCP；以及用于身份识别的数字签名和对称加密技术。

总结

计算机操作系统演进的过程中处处透露出人类的哲学；从问题分析到解决问题，然后引入问题，再转移问题，解决问题，呈现一个螺旋式上升的过程；明白了这些技术演进的过程，有助于了解技术适用的基本场景，也有助于更深刻的理解一门技术。