请选择 进入手机版 | 继续访问电脑版

今天,进程告诉我线程它它它它不想活了

[复制链接]
天一教育培训寐 发表于 2020-4-9 10:25:44 | 显示全部楼层 |阅读模式
今天,进程告诉我线程它它它它不想活了-1.jpg

这是Java建设者的第 67 篇原创文章

上一篇文章我们解剖了进程和线程的本质,进程和线程的实现方式,这篇文章我们来探讨它们是如何通信的,进程告诉我说线程不想活了,我不管它死活,我只想知道我是谁?进程是怎么告诉我的?进程的出现和线程的死亡和我有必然联系吗?文章为你揭露哟上一篇文章我们解剖了进程和线程的本质,进程和线程的实现方式,这篇文章我们来探讨它们是如何通信的,进程告诉我说线程不想活了,我不管它死活,我是谁?进程是怎么告诉我的?进程的出现和线程的死亡和我有必然联系吗?文章为你揭露哟...
进程间通信


进程是需要频繁的和其他进程进行交流的。例如,在一个 shell 管道中,第一个进程的输出必须传递给第二个进程,这样沿着管道进行下去。因此,进程之间如果需要通信的话,必须要使用一种良好的数据结构以至于不能被中断。下面我们会一起讨论有关 进程间通信(Inter Process Communication, IPC) 的问题。

关于进程间的通信,这里有三个问题
    上面提到了第一个问题,那就是一个进程如何传递消息给其他进程。第二个问题是如何确保两个或多个线程之间不会相互干扰。例如,两个航空公司都试图为不同的顾客抢购飞机上的最后一个座位。第三个问题是数据的先后顺序的问题,如果进程 A 产生数据并且进程 B 打印数据。则进程 B 打印数据之前需要先等 A 产生数据后才能够进行打印。

需要注意的是,这三个问题中的后面两个问题同样也适用于线程

第一个问题在线程间比较好解决,因为它们共享一个地址空间,它们具有相同的运行时环境,可以想象你在用高级语言编写多线程代码的过程中,线程通信问题是不是比较容易解决?

另外两个问题也同样适用于线程,同样的问题可用同样的方法来解决。我们后面会慢慢讨论这三个问题,你现在脑子中大致有个印象即可。
竞态条件


在一些操作系统中,协作的进程可能共享一些彼此都能读写的公共资源。公共资源可能在内存中也可能在一个共享文件。为了讲清楚进程间是如何通信的,这里我们举一个例子:一个后台打印程序。当一个进程需要打印某个文件时,它会将文件名放在一个特殊的后台目录(spooler directory)中。另一个进程 打印后台进程(printer daemon) 会定期的检查是否需要文件被打印,如果有的话,就打印并将该文件名从目录下删除。

假设我们的后台目录有非常多的 槽位(slot),编号依次为 0,1,2,...,每个槽位存放一个文件名。同时假设有两个共享变量:out,指向下一个需要打印的文件;in,指向目录中下个空闲的槽位。可以把这两个文件保存在一个所有进程都能访问的文件中,该文件的长度为两个字。在某一时刻,0 至 3 号槽位空,4 号至 6 号槽位被占用。在同一时刻,进程 A 和 进程 B 都决定将一个文件排队打印,情况如下
今天,进程告诉我线程它它它它不想活了-2.jpg

墨菲法则(Murphy) 中说过,任何可能出错的地方终将出错,这句话生效时,可能发生如下情况。

进程 A 读到 in 的值为 7,将 7 存在一个局部变量 next_free_slot 中。此时发生一次时钟中断,CPU 认为进程 A 已经运行了足够长的时间,决定切换到进程 B 。进程 B 也读取 in 的值,发现是 7,然后进程 B 将 7 写入到自己的局部变量 next_free_slot 中,在这一时刻两个进程都认为下一个可用槽位是 7 。

进程 B 现在继续运行,它会将打印文件名写入到 slot 7 中,然后把 in 的指针更改为 8 ,然后进程 B 离开去做其他的事情

现在进程 A 开始恢复运行,由于进程 A 通过检查 next_free_slot也发现 slot 7 的槽位是空的,于是将打印文件名存入 slot 7 中,然后把 in 的值更新为 8 ,由于 slot 7 这个槽位中已经有进程 B 写入的值,所以进程 A 的打印文件名会把进程 B 的文件覆盖,由于打印机内部是无法发现是哪个进程更新的,它的功能比较局限,所以这时候进程 B 永远无法打印输出,类似这种情况,即两个或多个线程同时对一共享数据进行修改,从而影响程序运行的正确性时,这种就被称为竞态条件(race condition)。调试竞态条件是一种非常困难的工作,因为绝大多数情况下程序运行良好,但在极少数的情况下会发生一些无法解释的奇怪现象。不幸的是,多核增长带来的这种问题使得竞态条件越来越普遍。
临界区


不仅共享资源会造成竞态条件,事实上共享文件、共享内存也会造成竞态条件、那么该如何避免呢?或许一句话可以概括说明:禁止一个或多个进程在同一时刻对共享资源(包括共享内存、共享文件等)进行读写。换句话说,我们需要一种 互斥(mutual exclusion) 条件,这也就是说,如果一个进程在某种方式下使用共享变量和文件的话,除该进程之外的其他进程就禁止做这种事(访问统一资源)。上面问题的纠结点在于,在进程 A 对共享变量的使用未结束之前进程 B 就使用它。在任何操作系统中,为了实现互斥操作而选用适当的原语是一个主要的设计问题,接下来我们会着重探讨一下。

避免竞争问题的条件可以用一种抽象的方式去描述。大部分时间,进程都会忙于内部计算和其他不会导致竞争条件的计算。然而,有时候进程会访问共享内存或文件,或者做一些能够导致竞态条件的操作。我们把对共享内存进行访问的程序片段称作 关键区域(critical region) 或 临界区(critical section)。如果我们能够正确的操作,使两个不同进程不可能同时处于临界区,就能避免竞争条件,这也是从操作系统设计角度来进行的。

尽管上面这种设计避免了竞争条件,但是不能确保并发线程同时访问共享数据的正确性和高效性。一个好的解决方案,应该包含下面四种条件
    任何时候两个进程不能同时处于临界区不应对 CPU 的速度和数量做任何假设位于临界区外的进程不得阻塞其他进程不能使任何进程无限等待进入临界区
今天,进程告诉我线程它它它它不想活了-3.jpg

从抽象的角度来看,我们通常希望进程的行为如上图所示,在 t1 时刻,进程 A 进入临界区,在 t2 的时刻,进程 B 尝试进入临界区,因为此时进程 A 正在处于临界区中,所以进程 B 会阻塞直到 t3 时刻进程 A 离开临界区,此时进程 B 能够允许进入临界区。最后,在 t4 时刻,进程 B 离开临界区,系统恢复到没有进程的原始状态。
忙等互斥


下面我们会继续探讨实现互斥的各种设计,在这些方案中,当一个进程正忙于更新其关键区域的共享内存时,没有其他进程会进入其关键区域,也不会造成影响。
屏蔽中断


在单处理器系统上,最简单的解决方案是让每个进程在进入临界区后立即屏蔽所有中断,并在离开临界区之前重新启用它们。屏蔽中断后,时钟中断也会被屏蔽。CPU 只有发生时钟中断或其他中断时才会进行进程切换。这样,在屏蔽中断后 CPU 不会切换到其他进程。所以,一旦某个进程屏蔽中断之后,它就可以检查和修改共享内存,而不用担心其他进程介入访问共享数据。

这个方案可行吗?进程进入关键区域是由谁决定的呢?不是用户进程吗?当进程进入关键区域后,用户进程关闭中断,如果经过一段较长时间后进程没有离开,那么中断不就一直启用不了,结果会如何?可能会造成整个系统的终止。而且如果是多处理器的话,屏蔽中断仅仅对执行 disable 指令的 CPU 有效。其他 CPU 仍将继续运行,并可以访问共享内存。

另一方面,对内核来说,当它在执行更新变量或列表的几条指令期间将中断屏蔽是很方便的。例如,如果多个进程处理就绪列表中的时候发生中断,则可能会发生竞态条件的出现。所以,屏蔽中断对于操作系统本身来说是一项很有用的技术,但是对于用户线程来说,屏蔽中断却不是一项通用的互斥机制。
锁变量


作为第二种尝试,可以寻找一种软件层面解决方案。考虑有单个共享的(锁)变量,初始为值为 0 。当一个线程想要进入关键区域时,它首先会查看锁的值是否为 0 ,如果锁的值是 0 ,进程会把它设置为 1 并让进程进入关键区域。如果锁的状态是 1,进程会等待直到锁变量的值变为 0 。因此,锁变量的值是 0 则意味着没有线程进入关键区域。如果是 1 则意味着有进程在关键区域内。我们对上图修改后,如下所示
今天,进程告诉我线程它它它它不想活了-4.jpg

这种设计方式是否正确呢?是否存在纰漏呢?假设一个进程读出锁变量的值并发现它为 0 ,而恰好在它将其设置为 1 之前,另一个进程调度运行,读出锁的变量为0 ,并将锁的变量设置为 1 。然后第一个线程运行,把锁变量的值再次设置为 1,此时,关键区域就会有两个进程在同时运行。
今天,进程告诉我线程它它它它不想活了-5.jpg

也许有的读者可以这么认为,在进入前检查一次,在要离开的关键区域再检查一次不就解决了吗?实际上这种情况也是于事无补,因为在第二次检查期间其他线程仍有可能修改锁变量的值,换句话说,这种 set-before-check 不是一种 原子性 操作,所以同样还会发生竞争条件。
严格轮询法


第三种互斥的方式先抛出来一段代码,这里的程序是用 C 语言编写,之所以采用 C 是因为操作系统普遍是用 C 来编写的(偶尔会用 C++),而基本不会使用 Java 、Modula3 或 Pascal 这样的语言,Java 中的 native 关键字底层也是 C 或 C++ 编写的源码。对于编写操作系统而言,需要使用 C 语言这种强大、高效、可预知和有特性的语言,而对于 Java ,它是不可预知的,因为它在关键时刻会用完存储器,而在不合适的时候会调用垃圾回收机制回收内存。在 C 语言中,这种情况不会发生,C 语言中不会主动调用垃圾回收回收内存。有关 C 、C++ 、Java 和其他四种语言的比较可以参考

进程 0 的代码
while(TRUE){
  while(turn != 0){
    /* 进入关键区域 */
    critical_region();
    turn = 1;
    /* 离开关键区域 */
    noncritical_region();
  }
}
进程 1 的代码
while(TRUE){
  while(turn != 1){
    critical_region();
    turn = 0;
    noncritical_region();
  }
}
在上面代码中,变量 turn,初始值为 0 ,用于记录轮到那个进程进入临界区,并检查或更新共享内存。开始时,进程 0 检查 turn,发现其值为 0 ,于是进入临界区。进程 1 也发现其值为 0 ,所以在一个等待循环中不停的测试 turn,看其值何时变为 1。连续检查一个变量直到某个值出现为止,这种方法称为 忙等待(busywaiting)。由于这种方式浪费 CPU 时间,所以这种方式通常应该要避免。只有在有理由认为等待时间是非常短的情况下,才能够使用忙等待。用于忙等待的锁,称为 自旋锁(spinlock)。

进程 0 离开临界区时,它将 turn 的值设置为 1,以便允许进程 1 进入其临界区。假设进程 1 很快便离开了临界区,则此时两个进程都处于临界区之外,turn 的值又被设置为 0 。现在进程 0 很快就执行完了整个循环,它退出临界区,并将 turn 的值设置为 1。此时,turn 的值为 1,两个进程都在其临界区外执行。

突然,进程 0 结束了非临界区的操作并返回到循环的开始。但是,这时它不能进入临界区,因为 turn 的当前值为 1,此时进程 1 还忙于非临界区的操作,进程 0 只能继续 while 循环,直到进程 1 把 turn 的值改为 0 。这说明,在一个进程比另一个进程执行速度慢了很多的情况下,轮流进入临界区并不是一个好的方法。

这种情况违反了前面的叙述 3 ,即 位于临界区外的进程不得阻塞其他进程,进程 0 被一个临界区外的进程阻塞。由于违反了第三条,所以也不能作为一个好的方案。
Peterson 解法


荷兰数学家 T.Dekker 通过将锁变量与警告变量相结合,最早提出了一个不需要严格轮换的软件互斥算法

后来, G.L.Peterson 发现了一种简单很多的互斥算法,它的算法如下
#define FALSE 0
#define TRUE  1
#define N     2\t\t\t\t\t\t\t\t\t/* 进程数量 */

int turn;\t\t\t\t\t\t\t\t\t\t/* 现在轮到谁 */
int interested[N];\t\t\t\t\t\t\t\t/* 所有值初始化为 0 (FALSE) */

void enter_region(int process){\t\t\t\t\t/* 进程是 0 或 1 */

  int other;\t\t\t\t\t\t\t\t\t/* 另一个进程号 */

  other = 1 - process;\t\t\t\t\t\t\t/* 另一个进程 */
  interested[process] = TRUE;\t\t\t\t\t\t/* 表示愿意进入临界区 */
  turn = process;
  while(turn == process
        && interested[other] == true){}                                /* 空循环 */

}

void leave_region(int process){

  interested[process] == FALSE;\t\t\t\t     /* 表示离开临界区 */
}
在使用共享变量时(即进入其临界区)之前,各个进程使用各自的进程号 0 或 1 作为参数来调用 enter_region,这个函数调用在需要时将使进程等待,直到能够安全的临界区。在完成对共享变量的操作之后,进程将调用 leave_region 表示操作完成,并且允许其他进程进入。

现在来看看这个办法是如何工作的。一开始,没有任何进程处于临界区中,现在进程 0 调用 enter_region。它通过设置数组元素和将 turn 置为 0 来表示它希望进入临界区。由于进程 1 并不想进入临界区,所以 enter_region 很快便返回。如果进程现在调用 enter_region,进程 1 将在此处挂起直到 interested[0] 变为 FALSE,这种情况只有在进程 0 调用 leave_region 退出临界区时才会发生。

那么上面讨论的是顺序进入的情况,现在来考虑一种两个进程同时调用 enter_region 的情况。它们都将自己的进程存入 turn,但只有最后保存进去的进程号才有效,前一个进程的进程号因为重写而丢失。假如进程 1 是最后存入的,则 turn 为 1 。当两个进程都运行到 while 的时候,进程 0 将不会循环并进入临界区,而进程 1 将会无限循环且不会进入临界区,直到进程 0 退出位置。
TSL 指令


现在来看一种需要硬件帮助的方案。一些计算机,特别是那些设计为多处理器的计算机,都会有下面这条指令
TSL RX,LOCK\t
称为 测试并加锁(test and set lock),它将一个内存字 lock 读到寄存器 RX 中,然后在该内存地址上存储一个非零值。读写指令能保证是一体的,不可分割的,一同执行的。在这个指令结束之前其他处理器均不允许访问内存。执行 TSL 指令的 CPU 将会锁住内存总线,用来禁止其他 CPU 在这个指令结束之前访问内存。

很重要的一点是锁住内存总线和禁用中断不一样。禁用中断并不能保证一个处理器在读写操作之间另一个处理器对内存的读写。也就是说,在处理器 1 上屏蔽中断对处理器 2 没有影响。让处理器 2 远离内存直到处理器 1 完成读写的最好的方式就是锁住总线。这需要一个特殊的硬件(基本上,一根总线就可以确保总线由锁住它的处理器使用,而其他的处理器不能使用)

为了使用 TSL 指令,要使用一个共享变量 lock 来协调对共享内存的访问。当 lock 为 0 时,任何进程都可以使用 TSL 指令将其设置为 1,并读写共享内存。当操作结束时,进程使用 move 指令将 lock 的值重新设置为 0 。

这条指令如何防止两个进程同时进入临界区呢?下面是解决方案
enter_region:
\t\tTSL REGISTER,LOCK           | 复制锁到寄存器并将锁设为1
  \t\tCMP REGISTER,#0\t\t | 锁是 0 吗?
  \t\tJNE enter_region\t        | 若不是零,说明锁已被设置,所以循环
  \t\tRET\t\t\t\t   \t\t | 返回调用者,进入临界区

leave_region:
\t\t\tMOVE LOCK,#0\t\t| 在锁中存入 0
  \t\tRET\t\t\t\t\t\t | 返回调用者
我们可以看到这个解决方案的思想和 Peterson 的思想很相似。假设存在如下共 4 指令的汇编语言程序。第一条指令将 lock 原来的值复制到寄存器中并将 lock 设置为 1 ,随后这个原来的值和 0 做对比。如果它不是零,说明之前已经被加过锁,则程序返回到开始并再次测试。经过一段时间后(可长可短),该值变为 0 (当前处于临界区中的进程退出临界区时),于是过程返回,此时已加锁。要清除这个锁也比较简单,程序只需要将 0 存入 lock 即可,不需要特殊的同步指令。

现在有了一种很明确的做法,那就是进程在进入临界区之前会先调用 enter_region,判断是否进行循环,如果lock 的值是 1 ,进行无限循环,如果 lock 是 0,不进入循环并进入临界区。在进程从临界区返回时它调用 leave_region,这会把 lock 设置为 0 。与基于临界区问题的所有解法一样,进程必须在正确的时间调用 enter_region 和 leave_region ,解法才能奏效。

还有一个可以替换 TSL 的指令是 XCHG,它原子性的交换了两个位置的内容,例如,一个寄存器与一个内存字,代码如下
enter_region:
\t\tMOVE REGISTER,#1\t\t\t\t\t| 把 1 放在内存器中
\t\tXCHG REGISTER,LOCK\t\t\t\t| 交换寄存器和锁变量的内容
\t\tCMP REGISTER,#0\t\t\t\t\t| 锁是 0 吗?
\t\tJNE enter_region\t\t\t\t\t\t| 若不是 0 ,锁已被设置,进行循环
\t\tRET\t\t\t\t\t\t\t\t\t| 返回调用者,进入临界区
\t
leave_region:\t\t\t\t\t\t\t\t\t\t
\t\tMOVE LOCK,#0\t\t\t\t\t\t| 在锁中存入 0
\t\tRET\t\t\t\t\t\t\t\t\t| 返回调用者
XCHG 的本质上与 TSL 的解决办法一样。所有的 Intel x86 CPU 在底层同步中使用 XCHG 指令。
睡眠与唤醒


上面解法中的 Peterson 、TSL 和 XCHG 解法都是正确的,但是它们都有忙等待的缺点。这些解法的本质上都是一样的,先检查是否能够进入临界区,若不允许,则该进程将原地等待,直到允许为止。

这种方式不但浪费了 CPU 时间,而且还可能引起意想不到的结果。考虑一台计算机上有两个进程,这两个进程具有不同的优先级,H 是属于优先级比较高的进程,L 是属于优先级比较低的进程。进程调度的规则是不论何时只要 H 进程处于就绪态 H 就开始运行。在某一时刻,L 处于临界区中,此时 H 变为就绪态,准备运行(例如,一条 I/O 操作结束)。现在 H 要开始忙等,但由于当 H 就绪时 L 就不会被调度,L 从来不会有机会离开关键区域,所以 H 会变成死循环,有时将这种情况称为优先级反转问题(priority inversion problem)。

现在让我们看一下进程间的通信原语,这些原语在不允许它们进入关键区域之前会阻塞而不是浪费 CPU 时间,最简单的是 sleep 和 wakeup。Sleep 是一个能够造成调用者阻塞的系统调用,也就是说,这个系统调用会暂停直到其他进程唤醒它。wakeup 调用有一个参数,即要唤醒的进程。还有一种方式是 wakeup 和 sleep 都有一个参数,即 sleep 和 wakeup 需要匹配的内存地址。
生产者-消费者问题


作为这些私有原语的例子,让我们考虑生产者-消费者(producer-consumer) 问题,也称作 有界缓冲区(bounded-buffer) 问题。两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者(producer),将信息放入缓冲区, 另一个是消费者(consumer),会从缓冲区中取出。也可以把这个问题一般化为 m 个生产者和 n 个消费者的问题,但是我们这里只讨论一个生产者和一个消费者的情况,这样可以简化实现方案。

如果缓冲队列已满,那么当生产者仍想要将数据写入缓冲区的时候,会出现问题。它的解决办法是让生产者睡眠,也就是阻塞生产者。等到消费者从缓冲区中取出一个或多个数据项时再唤醒它。同样的,当消费者试图从缓冲区中取数据,但是发现缓冲区为空时,消费者也会睡眠,阻塞。直到生产者向其中放入一个新的数据。

这个逻辑听起来比较简单,而且这种方式也需要一种称作 监听 的变量,这个变量用于监视缓冲区的数据,我们暂定为 count,如果缓冲区最多存放 N 个数据项,生产者会每次判断 count 是否达到 N,否则生产者向缓冲区放入一个数据项并增量 count 的值。消费者的逻辑也很相似:首先测试 count 的值是否为 0 ,如果为 0 则消费者睡眠、阻塞,否则会从缓冲区取出数据并使 count 数量递减。每个进程也会检查检查是否其他线程是否应该被唤醒,如果应该被唤醒,那么就唤醒该线程。下面是生产者消费者的代码
#define N 100\t\t\t\t\t\t/* 缓冲区 slot 槽的数量 */
int count = 0\t\t\t\t\t\t/* 缓冲区数据的数量 */

// 生产者
void producer(void){
  int item;

  while(TRUE){\t\t\t\t\t/* 无限循环 */
    item = produce_item()\t\t\t\t/* 生成下一项数据 */
    if(count == N){
      sleep();\t\t\t\t\t\t/* 如果缓存区是满的,就会阻塞 */
    }

    insert_item(item);\t\t\t\t/* 把当前数据放在缓冲区中 */
    count = count + 1;\t\t\t\t/* 增加缓冲区 count 的数量 */
    if(count == 1){
      wakeup(consumer);\t\t\t\t/* 缓冲区是否为空?*/
    }
  }
}

// 消费者
void consumer(void){

  int item;

  while(TRUE){\t\t\t\t\t/* 无限循环 */
  \tif(count == 0){\t\t\t/* 如果缓冲区是空的,就会进行阻塞 */
      sleep();
    }
   \titem = remove_item();\t\t\t/* 从缓冲区中取出一个数据 */
    count = count - 1\t\t\t\t\t/* 将缓冲区的 count 数量减一 */
    if(count == N - 1){\t\t\t\t/* 缓冲区满嘛?*/
      wakeup(producer);\t\t
    }
    consumer_item(item);\t\t\t\t/* 打印数据项 */
  }

}
为了在 C 语言中描述像是 sleep 和 wakeup 的系统调用,我们将以库函数调用的形式来表示。它们不是 C 标准库的一部分,但可以在实际具有这些系统调用的任何系统上使用。代码中未实现的 insert_item 和 remove_item 用来记录将数据项放入缓冲区和从缓冲区取出数据等。

现在让我们回到生产者-消费者问题上来,上面代码中会产生竞争条件,因为 count 这个变量是暴露在大众视野下的。有可能出现下面这种情况:缓冲区为空,此时消费者刚好读取 count 的值发现它为 0 。此时调度程序决定暂停消费者并启动运行生产者。生产者生产了一条数据并把它放在缓冲区中,然后增加 count 的值,并注意到它的值是 1 。由于 count 为 0,消费者必须处于睡眠状态,因此生产者调用 wakeup 来唤醒消费者。但是,消费者此时在逻辑上并没有睡眠,所以 wakeup 信号会丢失。当消费者下次启动后,它会查看之前读取的 count 值,发现它的值是 0 ,然后在此进行睡眠。不久之后生产者会填满整个缓冲区,在这之后会阻塞,这样一来两个进程将永远睡眠下去。

引起上面问题的本质是 唤醒尚未进行睡眠状态的进程会导致唤醒丢失。如果它没有丢失,则一切都很正常。一种快速解决上面问题的方式是增加一个唤醒等待位(wakeup waiting bit)。当一个 wakeup 信号发送给仍在清醒的进程后,该位置为 1 。之后,当进程尝试睡眠的时候,如果唤醒等待位为 1 ,则该位清除,而进程仍然保持清醒。

然而,当进程数量有许多的时候,这时你可以说通过增加唤醒等待位的数量来唤醒等待位,于是就有了 2、4、6、8 个唤醒等待位,但是并没有从根本上解决问题。
信号量


信号量是 E.W.Dijkstra 在 1965 年提出的一种方法,它使用一个整形变量来累计唤醒次数,以供之后使用。在他的观点中,有一个新的变量类型称作 信号量(semaphore)。一个信号量的取值可以是 0 ,或任意正数。0 表示的是不需要任何唤醒,任意的正数表示的就是唤醒次数。

Dijkstra 提出了信号量有两个操作,现在通常使用 down 和 up(分别可以用 sleep 和 wakeup 来表示)。down 这个指令的操作会检查值是否大于 0 。如果大于 0 ,则将其值减 1 ;若该值为 0 ,则进程将睡眠,而且此时 down 操作将会继续执行。检查数值、修改变量值以及可能发生的睡眠操作均为一个单一的、不可分割的 原子操作(atomic action) 完成。这会保证一旦信号量操作开始,没有其他的进程能够访问信号量,直到操作完成或者阻塞。这种原子性对于解决同步问题和避免竞争绝对必不可少。



原子性操作指的是在计算机科学的许多其他领域中,一组相关操作全部执行而没有中断或根本不执行。

up 操作会使信号量的值 + 1。如果一个或者多个进程在信号量上睡眠,无法完成一个先前的 down 操作,则由系统选择其中一个并允许该程完成 down 操作。因此,对一个进程在其上睡眠的信号量执行一次 up 操作之后,该信号量的值仍然是 0 ,但在其上睡眠的进程却少了一个。信号量的值增 1 和唤醒一个进程同样也是不可分割的。不会有某个进程因执行 up 而阻塞,正如在前面的模型中不会有进程因执行 wakeup 而阻塞是一样的道理。
用信号量解决生产者 - 消费者问题


用信号量解决丢失的 wakeup 问题,代码如下
#define N 100\t\t\t\t\t\t\t\t/* 定义缓冲区槽的数量 */
typedef int semaphore;\t\t\t\t\t\t/* 信号量是一种特殊的 int */
semaphore mutex = 1;\t\t\t\t\t\t/* 控制关键区域的访问 */
semaphore empty = N;\t\t\t\t\t\t/* 统计 buffer 空槽的数量 */
semaphore full = 0;\t\t\t\t\t\t\t/* 统计 buffer 满槽的数量 */

void producer(void){

  int item;

  while(TRUE){\t\t\t\t\t\t\t/* TRUE 的常量是 1 */
    item = producer_item();\t\t\t\t\t/* 产生放在缓冲区的一些数据 */
    down(&empty);\t\t\t\t\t\t\t/* 将空槽数量减 1  */
    down(&mutex);\t\t\t\t\t\t\t/* 进入关键区域  */
    insert_item(item);\t\t\t\t\t\t/* 把数据放入缓冲区中 */
    up(&mutex);\t\t\t\t\t\t\t/* 离开临界区 */
    up(&full);\t\t\t\t\t\t\t\t/* 将 buffer 满槽数量 + 1 */
  }
}

void consumer(void){

  int item;

  while(TRUE){\t\t\t\t\t\t\t/* 无限循环 */
    down(&full);\t\t\t\t\t\t\t\t/* 缓存区满槽数量 - 1 */
    down(&mutex);\t\t\t\t\t\t\t/* 进入缓冲区 */
    item = remove_item();\t\t\t\t\t\t/* 从缓冲区取出数据 */
    up(&mutex);\t\t\t\t\t\t\t/* 离开临界区 */
    up(&empty);\t\t\t\t\t\t\t/* 将空槽数目 + 1 */
    consume_item(item);\t\t\t\t\t\t/* 处理数据 */
  }

}
为了确保信号量能正确工作,最重要的是要采用一种不可分割的方式来实现它。通常是将 up 和 down 作为系统调用来实现。而且操作系统只需在执行以下操作时暂时屏蔽全部中断:检查信号量、更新、必要时使进程睡眠。由于这些操作仅需要非常少的指令,因此中断不会造成影响。如果使用多个 CPU,那么信号量应该被锁进行保护。使用 TSL 或者 XCHG 指令用来确保同一时刻只有一个 CPU 对信号量进行操作。

使用 TSL 或者 XCHG 来防止几个 CPU 同时访问一个信号量,与生产者或消费者使用忙等待来等待其他腾出或填充缓冲区是完全不一样的。前者的操作仅需要几个毫秒,而生产者或消费者可能需要任意长的时间。

上面这个解决方案使用了三种信号量:一个称为 full,用来记录充满的缓冲槽数目;一个称为 empty,记录空的缓冲槽数目;一个称为 mutex,用来确保生产者和消费者不会同时进入缓冲区。Full 被初始化为 0 ,empty 初始化为缓冲区中插槽数,mutex 初始化为 1。信号量初始化为 1 并且由两个或多个进程使用,以确保它们中同时只有一个可以进入关键区域的信号被称为 二进制信号量(binary semaphores)。如果每个进程都在进入关键区域之前执行 down 操作,而在离开关键区域之后执行 up 操作,则可以确保相互互斥。

现在我们有了一个好的进程间原语的保证。然后我们再来看一下中断的顺序保证
    硬件压入堆栈程序计数器等硬件从中断向量装入新的程序计数器汇编语言过程保存寄存器的值汇编语言过程设置新的堆栈C 中断服务器运行(典型的读和缓存写入)调度器决定下面哪个程序先运行C 过程返回至汇编代码汇编语言过程开始运行新的当前进程

在使用信号量的系统中,隐藏中断的自然方法是让每个 I/O 设备都配备一个信号量,该信号量最初设置为0。在 I/O 设备启动后,中断处理程序立刻对相关联的信号执行一个 down 操作,于是进程立即被阻塞。当中断进入时,中断处理程序随后对相关的信号量执行一个 up操作,能够使已经阻止的进程恢复运行。在上面的中断处理步骤中,其中的第 5 步 C 中断服务器运行 就是中断处理程序在信号量上执行的一个 up 操作,所以在第 6 步中,操作系统能够执行设备驱动程序。当然,如果有几个进程已经处于就绪状态,调度程序可能会选择接下来运行一个更重要的进程,我们会在后面讨论调度的算法。

上面的代码实际上是通过两种不同的方式来使用信号量的,而这两种信号量之间的区别也是很重要的。mutex 信号量用于互斥。它用于确保任意时刻只有一个进程能够对缓冲区和相关变量进行读写。互斥是用于避免进程混乱所必须的一种操作。

另外一个信号量是关于同步(synchronization)的。full 和 empty 信号量用于确保事件的发生或者不发生。在这个事例中,它们确保了缓冲区满时生产者停止运行;缓冲区为空时消费者停止运行。这两个信号量的使用与 mutex 不同。
互斥量


如果不需要信号量的计数能力时,可以使用信号量的一个简单版本,称为 mutex(互斥量)。互斥量的优势就在于在一些共享资源和一段代码中保持互斥。由于互斥的实现既简单又有效,这使得互斥量在实现用户空间线程包时非常有用。

互斥量是一个处于两种状态之一的共享变量:解锁(unlocked) 和 加锁(locked)。这样,只需要一个二进制位来表示它,不过一般情况下,通常会用一个 整形(integer) 来表示。0 表示解锁,其他所有的值表示加锁,比 1 大的值表示加锁的次数。

mutex 使用两个过程,当一个线程(或者进程)需要访问关键区域时,会调用 mutex_lock 进行加锁。如果互斥锁当前处于解锁状态(表示关键区域可用),则调用成功,并且调用线程可以自由进入关键区域。

另一方面,如果 mutex 互斥量已经锁定的话,调用线程会阻塞直到关键区域内的线程执行完毕并且调用了 mutex_unlock 。如果多个线程在 mutex 互斥量上阻塞,将随机选择一个线程并允许它获得锁。
今天,进程告诉我线程它它它它不想活了-6.jpg

由于 mutex 互斥量非常简单,所以只要有 TSL 或者是 XCHG 指令,就可以很容易地在用户空间实现它们。用于用户级线程包的 mutex_lock 和 mutex_unlock 代码如下,XCHG 的本质也一样。
mutex_lock:
\t\t\tTSL REGISTER,MUTEX\t\t\t\t| 将互斥信号量复制到寄存器,并将互斥信号量置为1
\t\t\tCMP REGISTER,#0\t\t\t\t\t| 互斥信号量是 0 吗?
\t\t\tJZE ok\t\t\t\t\t\t\t\t| 如果互斥信号量为0,它被解锁,所以返回
\t\t\tCALL thread_yield\t\t\t\t\t\t| 互斥信号正在使用;调度其他线程
\t\t\tJMP mutex_lock\t\t\t\t\t\t| 再试一次
ok: \tRET\t\t\t\t\t\t\t\t\t\t\t| 返回调用者,进入临界区

mutex_unlcok:
\t\t\tMOVE MUTEX,#0\t\t\t\t\t\t| 将 mutex 置为 0
\t\t\tRET\t\t\t\t\t\t\t\t\t| 返回调用者
mutex_lock 的代码和上面 enter_region 的代码很相似,我们可以对比着看一下
今天,进程告诉我线程它它它它不想活了-7.jpg

上面代码最大的区别你看出来了吗?
    根据上面我们对 TSL 的分析,我们知道,如果 TSL 判断没有进入临界区的进程会进行无限循环获取锁,而在 TSL 的处理中,如果 mutex 正在使用,那么就调度其他线程进行处理。所以上面最大的区别其实就是在判断 mutex/TSL 之后的处理。在(用户)线程中,情况有所不同,因为没有时钟来停止运行时间过长的线程。结果是通过忙等待的方式来试图获得锁的线程将永远循环下去,决不会得到锁,因为这个运行的线程不会让其他线程运行从而释放锁,其他线程根本没有获得锁的机会。在后者获取锁失败时,它会调用 thread_yield 将 CPU 放弃给另外一个线程。结果就不会进行忙等待。在该线程下次运行时,它再一次对锁进行测试。

上面就是 enter_region 和 mutex_lock 的差别所在。由于 thread_yield 仅仅是一个用户空间的线程调度,所以它的运行非常快捷。这样,mutex_lock 和 mutex_unlock 都不需要任何内核调用。通过使用这些过程,用户线程完全可以实现在用户空间中的同步,这个过程仅仅需要少量的同步。

我们上面描述的互斥量其实是一套调用框架中的指令。从软件角度来说,总是需要更多的特性和同步原语。例如,有时线程包提供一个调用 mutex_trylock,这个调用尝试获取锁或者返回错误码,但是不会进行加锁操作。这就给了调用线程一个灵活性,以决定下一步做什么,是使用替代方法还是等候下去。
Futexes


随着并行的增加,有效的同步(synchronization)和锁定(locking) 对于性能来说是非常重要的。如果进程等待时间很短,那么自旋锁(Spin lock) 是非常有效;但是如果等待时间比较长,那么这会浪费 CPU 周期。如果进程很多,那么阻塞此进程,并仅当锁被释放的时候让内核解除阻塞是更有效的方式。不幸的是,这种方式也会导致另外的问题:它可以在进程竞争频繁的时候运行良好,但是在竞争不是很激烈的情况下内核切换的消耗会非常大,而且更困难的是,预测锁的竞争数量更不容易。

有一种有趣的解决方案是把两者的优点结合起来,提出一种新的思想,称为 futex,或者是 快速用户空间互斥(fast user space mutex),是不是听起来很有意思?
今天,进程告诉我线程它它它它不想活了-8.jpg

futex 是 Linux 中的特性实现了基本的锁定(很像是互斥锁)而且避免了陷入内核中,因为内核的切换的开销非常大,这样做可以大大提高性能。futex 由两部分组成:内核服务和用户库。内核服务提供了了一个 等待队列(wait queue) 允许多个进程在锁上排队等待。除非内核明确的对他们解除阻塞,否则它们不会运行。
今天,进程告诉我线程它它它它不想活了-9.jpg

对于一个进程来说,把它放到等待队列需要昂贵的系统调用,这种方式应该被避免。在没有竞争的情况下,futex 可以直接在用户空间中工作。这些进程共享一个 32 位整数(integer) 作为公共锁变量。假设锁的初始化为 1,我们认为这时锁已经被释放了。线程通过执行原子性的操作减少并测试(decrement and test) 来抢占锁。decrement and set 是 Linux 中的原子功能,由包裹在 C 函数中的内联汇编组成,并在头文件中进行定义。下一步,线程会检查结果来查看锁是否已经被释放。如果锁现在不是锁定状态,那么刚好我们的线程可以成功抢占该锁。然而,如果锁被其他线程持有,抢占锁的线程不得不等待。在这种情况下,futex 库不会自旋,但是会使用一个系统调用来把线程放在内核中的等待队列中。这样一来,切换到内核的开销已经是合情合理的了,因为线程可以在任何时候阻塞。当线程完成了锁的工作时,它会使用原子性的 增加并测试(increment and test) 释放锁,并检查结果以查看内核等待队列上是否仍阻止任何进程。如果有的话,它会通知内核可以对等待队列中的一个或多个进程解除阻塞。如果没有锁竞争,内核则不需要参与竞争。
Pthreads 中的互斥量


Pthreads 提供了一些功能用来同步线程。最基本的机制是使用互斥量变量,可以锁定和解锁,用来保护每个关键区域。希望进入关键区域的线程首先要尝试获取 mutex。如果 mutex 没有加锁,线程能够马上进入并且互斥量能够自动锁定,从而阻止其他线程进入。如果 mutex 已经加锁,调用线程会阻塞,直到 mutex 解锁。如果多个线程在相同的互斥量上等待,当互斥量解锁时,只有一个线程能够进入并且重新加锁。这些锁并不是必须的,程序员需要正确使用它们。

下面是与互斥量有关的函数调用
今天,进程告诉我线程它它它它不想活了-10.jpg

向我们想象中的一样,mutex 能够被创建和销毁,扮演这两个角色的分别是 Phread_mutex_init 和 Pthread_mutex_destroy。mutex 也可以通过 Pthread_mutex_lock 来进行加锁,如果互斥量已经加锁,则会阻塞调用者。还有一个调用Pthread_mutex_trylock 用来尝试对线程加锁,当 mutex 已经被加锁时,会返回一个错误代码而不是阻塞调用者。这个调用允许线程有效的进行忙等。最后,Pthread_mutex_unlock 会对 mutex 解锁并且释放一个正在等待的线程。

除了互斥量以外,Pthreads 还提供了第二种同步机制:条件变量(condition variables) 。mutex 可以很好的允许或阻止对关键区域的访问。条件变量允许线程由于未满足某些条件而阻塞。绝大多数情况下这两种方法是一起使用的。下面我们进一步来研究线程、互斥量、条件变量之间的关联。

下面再来重新认识一下生产者和消费者问题:一个线程将东西放在一个缓冲区内,由另一个线程将它们取出。如果生产者发现缓冲区没有空槽可以使用了,生产者线程会阻塞起来直到有一个线程可以使用。生产者使用 mutex 来进行原子性检查从而不受其他线程干扰。但是当发现缓冲区已经满了以后,生产者需要一种方法来阻塞自己并在以后被唤醒。这便是条件变量做的工作。

下面是一些与条件变量有关的最重要的 pthread 调用
今天,进程告诉我线程它它它它不想活了-11.jpg

上表中给出了一些调用用来创建和销毁条件变量。条件变量上的主要属性是 Pthread_cond_wait 和 Pthread_cond_signal。前者阻塞调用线程,直到其他线程发出信号为止(使用后者调用)。阻塞的线程通常需要等待唤醒的信号以此来释放资源或者执行某些其他活动。只有这样阻塞的线程才能继续工作。条件变量允许等待与阻塞原子性的进程。Pthread_cond_broadcast用来唤醒多个阻塞的、需要等待信号唤醒的线程。



需要注意的是,条件变量(不像是信号量)不会存在于内存中。如果将一个信号量传递给一个没有线程等待的条件变量,那么这个信号就会丢失,这个需要注意

下面是一个使用互斥量和条件变量的例子
#include
#include

#define MAX 1000000000\t\t\t\t\t\t/* 需要生产的数量 */
pthread_mutex_t the_mutex;
pthread_cond_t condc,condp;\t\t\t\t\t\t/* 使用信号量 */
int buffer = 0;

void *producer(void *ptr){\t\t\t\t\t\t/* 生产数据 */

  int i;

  for(int i = 0;i




上一篇:小米10的UFS 3.0真的强吗?小米10 Pro真机对比小米9
下一篇:OPPO Reno3 Pro印度版参数曝光 打孔屏依旧
回复

使用道具 举报

全部回复0 显示全部楼层

发表回复

您需要登录后才可以回帖 登录 | 立即注册  

本版积分规则

楼主

联系客服 关注微信 下载APP 返回顶部 返回列表