进程间通信

本文你会了解到计算机系统中一些锁的实现原理.文中进程和线程可以互相替换.

竞争条件

概念:两个或者多个进程(或线程)共享读写某块资源的时候,因为cpu的切换,进程的运行时序会发生变化,从而可能影响最后的读写结果.

举例:
有两台打印机A,B,需要对一个文件内的文件进行打印.假如打印到第5个文件之前都没发生错误,此时第5个文件首先被A标记为了要打印.这时候CPU发生切换,进程切换到了B,B此时也认为文件5可以打印,并且将下一个打印对象标记为文件6.此时A从中断过程中恢复了,于是将要打印的文件6覆盖为了文件5,然后继续执行.等B恢复了,之后发现之前标记文件6不见了,变成了文件5,那么这时候就出现了竞争问题.

临界区

临界区概念 : 对共享内存进行访问的程序片段.解决竞争的方式就是实现互斥,让两个进程不同时在临界区.

有四个条件:

• 任何时候两个进程不能同时处于临界区.
• 不应对CPU的数量和速度做任何假设.
• 临界区外运行的程序不能阻塞其他进程.
• 不得使进程无限期等待进入临界区

基于忙等待的互斥

1.忙等待

概念 : CPU在发生时钟中断或者其他中断的时候才会切换进程,可以利用这一点当一个进程在访问共享文件时,将中断屏蔽掉,等当前进程执行完毕之后再回复中断,这样就可以避免两个线程同处临界区了.

缺点 :

• 可能造成无限等待,万一某个进程不打开中断,后果可能会很严重.
• 如果是多核CPU,那么当前CPU屏蔽了中断,但其他CPU可能没屏蔽,那么依然可能会造成竞争条件.

2.锁变量

概念 : 设想有一个共享的锁变量,其初始值为0;当一个进程想进入临界区的时候,首先判断这把锁的值,如果是0就表明可以进入,并设置变量为1;如果当前变量是1,就等待变量为0.0就表示可以进入临界区,1表示需要等待不能进入.

缺点 : 如果进程A将锁变量设置为1前,发生了中断,B进程切换过来,发现当前变量为0,此时A,B都进入了临界区,也会产生竞争条件.

3.严格轮换法

概念 : 通过一个整形变量turn来标记当前哪个线程进入了临界区.开始时,进程0检查turn,发现为0,进入临界区.此时进程1也发现turn为0,于是不停的循环检查turn什么时候变为1.这个循环过程就是忙等待(比较浪费CPU时间,等待时间较短的情况下使用,又叫自旋锁).

缺点 : 当进程0是一个快速操作,而进程1是一个耗时操作时,如果进程0快速执行完操作后,将turn置为1,此时进程1依然在临界区外执行其他操作,那么这时候进程0就无法进入临界区了,直到进程1进入临界区并执行完毕.此种情况违背了上述情况3,临界区外阻塞了其他进程.

4.Peterson解法

概念 : 在使用进入临界区前,各个进程都使用其ID(0或1)作为参数来调用enter_region()这个函数.该函数在需要时将使进程等待,直到能安全进入临界区.进入临界区的进程完成临界区内的操作后,调用leave_region()这个函数表示操作完成,其他进程可进入临界区.

算法原型如下

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

int turn; // 该谁进入临界区
int interested[N]; // 保存当前进程是否要进入临界区的状态
void enter_region(int process){
    int other; // 其他进程
    other = 1 - process; // 其他进程id
    interested[process] = TRUE; // 当前进程要进入临界区
    turn = process; // 当前的轮次为process
    while(turn == process && interested[other] == TRUE); // 如果是其    他进程进入了,就空循环等待
}
// 直到调用了leave_region()方法,下一个进程才能进入
void leave_region(int process){
    interested[process] = FALSE;
}

分析:如果进程0先进入了enter_region()函数,那么运行到while的时候,此时

process = 0;
other = 1;
interested[process] = interested[0] = TRUE;
turn = process;
interested[other] = interested[1] = FALSE;

这里进程0,不进入空循环,于是进入了临界区开始工作.
此时进程1也进入了enter_region()函数,那么此时

process = 1;
other = 0;
interested[process] = interested[1] = TRUE;
turn = process;
interested[other] = interested[0] = TRUE;

这里interested[other] = interested[0] = TRUE,所以进入了空循环,那么进程1就在这里进行挂起,直到进程0调用leave_region()函数之后,才会进入临界区.

5.TSL指令

概念 : 这是需要硬件支持的一种方案.利用到汇编的一些指令:TSL RX,LOCK.它将一个内存字lock读到寄存器RX中,然后在该内存地址上存一个非零值.读和写必须是一体的,该指令结束前其他CPU不允许访问该lock.执行TSL指令的CPU将把内存总线锁住,从而禁止其他CPU在指令结束前访问内存.

这里屏蔽中断和锁总线是有区别的

• 当前CPU屏蔽中断之后,总线上其他CPU也可以访问临界区,中断屏蔽之后对其他CPU没有任何影响.
• 当前CPU锁住总线之后,其他CPU是没有办法在当前总线进行调度的,直到解锁.

enter_region:
TSL REGISTER,LOCK // 给lock变量赋值为1
CMP REGISTER,#0 // 判断lock是否为0
JNE enter_region // 不是 0就是说明有锁,继续等待循环
RET // 返回调用者,进入了临界区

leave_region:
MOVE LOCK,#0 // lock设为0
RET // 返回调用者

思路和忙等待差不多,只不过是通过硬件支持锁了总线而非屏蔽中断.

睡眠与唤醒

Peterson和TSL算法都是正确的思路,但都是基于忙等待的.本质就是:当一个进程想进入临界区的时候,先检查是否允许进入,不允许就让进程等待,直到允许为止.可以想象,如果等待时间较长,那么很容易浪费CPU时间,并且还有优先级反转问题.

1.优先级反转问题
很简单的例子,有两条进程:HIGH和LOW,HIGH优先级高于LOW.当LOW进入临界区的时候,HIGH此时也想进入,于是进行忙等,如果LOW无法离开临界区,此时HIGH就在一直等待.

2.生产者-消费者问题
先明白两个概念:
sleep : 将一个引起系统阻塞的进程挂起,直到另一个进程将其唤醒.
wakeup : 唤醒某个进程.

生产者和消费者的概念:
假定在一个工厂内,有生产者,消费者,和一个仓库.

• 生产者 : 生产产品然后放入仓库.
• 消费者 : 从仓库内拿出产品.
• 仓库 : 拥有一个容积的标识:count,标识产品数量.

如果当前仓库产品数量已满,那么此时生产者发现仓库满了,于是进入睡眠状态.此时消费者在睡眠,被唤醒后,判断仓库容积是否为0,如果为0,就进入睡眠,不为0就拿出产品.如此反复.C语言代码原型如下:

#define N 100 // 仓库容量

int count = 0; // 当前产品数量
// 生产者函数
void producer(){
    int item; // 新的产品
    while(TRUE){
        item = produce_item(); // 生产新产品
        if (count == N) sleep(); // 仓库满了,就睡眠
        insert_item(item); // 未满,假如仓库
        count += 1; // 数量加一
        if (count == 1) wakeup(consumer); // 仓库有货了,唤醒消费者
   }
}
// 消费者函数
void consumer(){
    int item; // 消费的产品
    while(TRUE){
        if (count == 0) sleep(); // 仓库空了,睡眠
        item = remove_item(); // 要消费的产品
        count -= 1; // 数量减一
        if (count == N - 1) wakeup(producer); // 仓库不满了,唤醒生产者
        consume_item(item); // 消费货物
    }
}

这里由于没有对count加以限制,也可能会产生竞争条件.

• 如果仓库为空,消费者刚读取到的仓库信息为0.
• 此时程序发生了中断,暂停消费者并且启动生产者.生产者向仓库添加了一个产品,此时count为1.
• 这时候生产者判断刚才count为0,所以消费者一定在睡眠,于是调用wakeup()来唤醒消费者.
• 但此时消费者因为发生了中断,实际上并没有进入睡眠状态中,于是之前生产者发送的wakeup()信号会丢失掉.
• 当中断结束后,系统重新调度消费者时,消费者之前读到的count为0,所以立即进入睡眠中.
• 而生产者迟早会将仓库填满,进入睡眠,于是两个进程都会进入到睡眠中.

如何解决这种情况呢,比较容易想到的就是给还未睡眠的进程加一个标识status,又叫唤醒等待位.

• 当wakeup()信号发给一个清醒的进程A时,将status置为1.
• 如果进程A此时要进入睡眠状态,并且status为1,则将该status置为0.这里实际上是把wakeup()信号保存在了status里,从而让它不丢失.此时消费者因为有这个status的标识,就知道自己收到了一个唤醒信号,所以也不会进入睡眠.

问题似乎解决了,但这种情况下又会产生另外一个问题,如果有多个进程的话,可能就需要多个唤醒等待位了.很明显,这种方式缺少灵活性.

信号量(semaphore)

概念 : 使用一个整型的变量来累计唤醒次数,供以后使用.

对信号量有两个操作:down和up,通常来说对应sleep和wakeup.
先明白原子操作的概念:指一组相关联的操作要么都不简短地执行,要么都不执行

• down : 检查信号量的值是否大于0,若大于0,就将其值减1(用掉一个保存的唤醒信号).若值为0了,进程就将进入睡眠,此时down操作并未结束.整个过程是一个原子操作过程,信号量操作开始之后到完成前,其他进程是无法访问这个信号量的.
• up : 对信号量的值加1.如果一个或多个进程想进入临界区,因为该信号量值为0,所以这些进程都将被阻塞.等当前临界区的进程完成临界区的操作之后,会执行up操作,信号量的值加1,同时唤醒某个进程进入临界区(唤醒的进程是系统进行调度选择的一个更为重要的进程).这个过程也是原子操作.

信号量与忙等的区别在于:信号量执行的只需要几个毫秒,而忙等待可能需要的时间会更长

互斥量(mutex)

概念 : 互斥量是一个可以处于两态之一的变量:加锁和解锁.通常0表示解锁,其他值表示加锁.一般用于处理线程操作.

调用过程:

• 当一个线程需要访问临界区的时候,调用mutex_lock.如果该互斥量是0,则线程允许进入临界区.
• 如果该互斥量已经加锁,则要进入临界区的线程被阻塞,直到临界区的线程完成并调用mutex_unlock.此时如果遇到忙等,导致时钟超时,那么系统将随机选择一个线程获得锁,从而保证锁迟早能被释放接触.

互斥量和TSL操作的区别就在于:如果发生忙等,导致时钟超时后,互斥量算法中会调度另一个线程(thread_yield)获得锁,从而避免了忙等.iOS中的pthread_mutex就是利用互斥量实现的.

后面还有消息发送和屏障(barrier)两种方式,暂时不介绍了,有兴趣的可以自行去了解.

参考来源:计算机组成原理第三版