《现代操作系统》读书笔记之——进程间通信1

    很多时候，进程需要和其他的进程进行通信。比如shell中的管道命令：ps -ef | grep nginx，一个命令的输出，作为另一个进程的输入，这就是进程间通信（Interprocess Communication）。

    进程间通信主要需要解决三个问题：

    1.一个进程如何给另一个进程传递信息

    2.如何确保进程之间不互相干扰、妨碍

    3.当进程间出现依赖关系时，该如何处理。

    尽管这里讨论的是进程之间的通信，但其实对于线程来说，他们之间的通信需要解决后两个问题。由于多个线程处在相同的进程，因此也处在同一个地址空间中，所以第一个问题自然很好解决。但是第二个、第三个问题还是存在的，当然解决的方案其实与进程间通信在处理这两个问题上采取的方案也是类似的。下面的内容会涉及上面的三个问题。

    1.竞争条件（Race Condition）

    在一些操作系统中，多个进程会共享一部分内存，每个进程都可以对他们进行读写操作。共享的内存有可能再内存中，也可能是一个共享的文件。为了看看进程间通信之间的竞争条件，举个简单的例子加以说明：打印池。假如一个进程想打印一个文件，于是他将文件名输入打印池目录中。有一个负责打印的进程——打印机守护进程——每隔一段时间会查看一下打印池目录中有没有需要打印的文件。有的话就打印，没有拉到。

    打印机目录的示意图如下：

    图中的每个小格子可以存放一个待打印的文件名（实际上应该是需要打印的文件的指针，这里只是为了说明问题做的假设）。同样，还需要假设两个共享的变量：一个叫out 存储下一个轮到打印的文件的文件名；另一个叫in  存储上图中下一个可以存放待打印文件文件名的小空格。这两个变量可能被存储再一个文件中，而这个文件共享给了所有的进程。

    上图所示的时刻，单元1、2、3已经空了，也就是说，之前存在里面的文件已经打印了。而5-9号空格还是空的，也就是说接下来需要打印的文件依次存放在下面的单元中。这一时刻，变量in存储的应该是5。假设这时候，进程A读取变量in，得到的值是5。于是，进程A将这个值存储到他的局部变量next_free_slot中，这时候，恰好CPU时间片到了，进程A重新回到可运行状态，而此时进程B获得了时间片，开始运行，它也有文件需要打印，那么它读取in，获得的值是5，于是它也将5这个值存储进他的局部变量next_free_slot中。然后它根据这个变量的值，将它需要打印的文件的文件名，假设是ccc.txt存储进单元格5中。等待打印。然后进程B开始干别的事情了。又过了一段时间，进程B的CPU时间片用完了。而进程A又获得了CPU时间片。它开始继续运行，先读取next_free_slot的值，得到的是5，于是，可怕的事情发生了，它把自己需要打印的文件名写入单元格5，也就是说，覆盖掉了进程B之前放置的需要打印的文件ccc.txt。进程B可能一直在等待打印的输出，但是永远都等不到了。

    类似这种情况，再两个或者多个进程在读或者写共享的数据，而结果取决于具体谁在运行，就叫做进程情况（Race Condition）

    2.临界区（Critical Regions）

    如何避免竞争条件？避免出现这种麻烦，或者说在任何涉及到共享内存、文件或者其他一切共享资源的情况下的处理策略是防止多于一个进程在同一时刻读写共享数据。换句话说，互斥（Mutual Exclusion）。 

    对于大多数的操作系统来说，选择合适的原语来实现互斥是一个主要的涉及手段。临界区（Critical Region/Critical Section）是指进程中那些访问共享内存并且可能导致竞争状态的部分。要防止竞争状态的出现，我们可以理解成要防止两个需要共享同一块内存的进程不要同时进入自己的临界区。

    但是仅仅如此是不够的，需要坚持下面的四个原则：

• 不允许两个进程同时进入各自的临界区
• 不要对任何关于CPU速度和CPU数量的假设
• 不允许运行在自己临界区外的进程阻塞别的进程
• 不允许任何进程无休止的等待进入自己的临界区

    上面描述的是一种抽象的解决问题的思路，可以简单的使用一个图作为例子来描述使用临界区则个概念来体现互斥操作。

    3.实现互斥的几种方案之——禁用中断（Disable Interrupt）

    在单处理器系统中，这时最为简单的方案。也就是当进程进入临界区后，禁用中断，等它离开临界区再开启。CPU能够切换进程的前提是可以发生时钟中断或者其他中断。这就意味着，当一个进程进入临界区，他就不可能被剥夺CPU使用权，直到它离开临界区。

    这种方案显然没有吸引力，其缺点有两点：

• 给用户进程权利去禁用中断是不明智的，如果有进程禁用了中断并且再也不开启，那系统最后将会死掉。
• 如果多个CPU，当一个进程禁用中断，只是它正在使用的CPU会被影响，而此时，另外的CPU上的进程可能还是会访问临界区，进入修改共享内存的内容 

   尽管如此，对于操作系统的内核来说，这却是一个很方便的技巧。当内核正在更新就绪进程表时，它可能会在几个指令的时间内禁用中断。

   此外，现在使用这种方式实现互斥越累越少了，毕竟，现在的机器都是多核的。

    4.实现互斥的几种方案之——锁变量（Lock Variables）

    这种方案的原理是设计一个所变量，初始化为0，某个进程要进入临界区，先查看该变量的值，如果是0，则可以进入临界区，并且将该变量的值设置为1，等它离开临界区再将这个变量设置为0.简而言之，这个变量为0代表没有进程正处在临界区，1代表有进程处在临界区。

    但是这个方案存在的问题和前面举例的那个打印机问题一样。

    5.实现互斥的几种方案之——严格变更（strict alternation）

    这个方案的基本原理如下面的两段代码所示：

while(TRUE) {
	while(turn != 0) {
	}
	critical_region();
	turn = 1;
	noncritical_region();
}

while(TRUE) {
	while(turn != 1) {
	}
	critical_region();
	turn = 0;
	noncritical_region();
}      

    整型变量turn,用来跟踪到底那个进程当前可以进入自己的临界区。对于进程0来说，不断检测turn是否等于0，如果是则它可以进入自己的临界区，如果turn不等于0，那么它就继续等待，并且持续的检测这个变量的值。如果进程0进入了临界区，当它出来之后，它将turn设置为1，也就是轮到进程1（另外的一个进程）进入临临界区了。

    对于进程1来说，它执行的是第二段代码，但是原理一样。对于进程来说，必须不断的检查一个变量的值来判断是否轮到自己进入临界区，这种情况叫做忙等待（busy waiting）。这种情况是应该被避免的，因为它很浪费CPU的时间。使用忙等待实现的锁，叫做自旋锁（spin lock）。

    这种方案还有一个问题。如果两个进程执行的速度差距很大。我们假设进程0执行速度远远快于进程1。一开始，turn的值为0，进程0进入临界区，很快，进程0离开临界区，将turn设置为1，这时候，进程1开始进入临界区，而此时进程0可能会已经离开非临界区，并且又持续监测turn的值。进程1一离开临界区，将turn再次设置为0，进程0又进入临界区，而进程1进入非临界区。由于进程0执行速度很快，它很快再次执行完临界区的代码，将turn设置为1，然后执行非临界区代码。由于进程0非常快，进程1很慢，很可能进程1还在第一次的非临界区，这时，进程0已经执行完第二次非临界区的代码，而此时turn还是它刚才设置的值——0，而其实另一个进程，进程1，并没有在临界区，而是在非临界区挣扎。这种情况下，进程0却只能干等。

    所以，很明显，这种方案非常不适合多个进程之间执行速度差距很大的情况。而我们这一节的标题叫做strict alternation，举个例子说，就是像前面提到的打印池，strict alternation不允许一个进程一次提交大于1个需要打印的文件。这可能也是为了不要是进城之间的执行速度差距过大吧。

    6.实现进程互斥的几种方案之——Peterson方案

    这个方案的历史我们这里略过不说，其基本原理如下面的实例代码：

#define FALSE 0
#define TRUE 1
#define N 2

int turn;
int interested[N];

void enter_region(int process) {
	int other;
	other = 1 - process;
	interested[process] = TRUE;
	turn = process;
	while(turn==process && intrested[other] == TRUE)
}
void leave_region(int process) {
	intrested[process] = FALSE;
}

    进程在进入 临界区之前，需要执行enter_region函数，并将自己的进程号作为参数传递进去。当进程离开临界区，需要执行和leave_region函数。

    我们具体看看原理：对于进程0和进程1。一开始谁都没有在临界区，现在进程0调用enter_region函数。首先，进程0将对应于自己的数组元素intrested[0]设置为TRUE，并且将turn的值设置为自己的进程号，也就是0。然后这一步很关键，做一个循环的检查，如果轮到了自己（turn==process）但是另一个进程也很感兴趣（intrested[other]==TRUE）。如果使这样的话，那么什么也不做，等着。否则的话，真正开始进入临界区。

    如果进程0执行完了临界区代码，那么就将intrested[0]设置为FALSE，也就是说表示自己此刻不需要再进入临界区了。

    这种方案会不会发生两个进程都在干等着，最后死锁呢？我们看看。假设进程0和进程1几乎同时执行到turn=process代码，假设进程0先执行这条语句，紧接着进程1也执行这条语句，从而擦除之前进程0设置的值。那么接下来进程0就只能在那个while循环里面等着了，而进程1则真的进入自己的临界区。这也是为什么我在上面说这个里层的while循环很重要了。