进程互斥的软件解法

2016-10-21

前言

在写这篇文章前，我曾花了一段时间仔细读了学校的教材，在经历了无数次迷茫与痛苦后，我终于确定了这并非是我的理解问题或者是智商问题。确实是学校的教材真的有毒

就像伟大的爬墙爱好者源氏所言:” 我曾在这里荒废了许多时间.”

所以这即是一个总结，也是一个体会，更是一个对自己的警醒。同学，你受教材的毒害太深了！

关于互斥

事实上在很多经典的书以及网课上，关于进程互斥的解决方法大多重点阐述了硬件与信号量的机制。而在软件算法实现上却鲜有提之，当然我校的教材更是提都没提。

在观看了北大的网课以及读了OS：IDP一书以后，有幸领略了通过软件算法来控制进程互斥。而我也将以从最初的形态到完善的算法慢慢推导。事实上算法解法更重要的是一种思想，这里我以OS:IDP一书代码为例。

互斥的三大要求

我们都知道，互斥有着最基本的三大要求。如果不满足这三个要求，则不能满足互斥。

临界区内不能有多个进程
临界区外的进程不能干涉其他进程
临界区的进程不能出现被无限延迟的情况。

最简单的实现

算法一

我们以全局变量turn来决定谁来进入临界区，

当 turn = x 时 ，即进程号为x的进程进入临界区

while(turn !=x){
    do nothing
}
critical section
turn = other

这个算法简单有效的保证了共享属性。但是他却有两个致命的缺陷。考虑到进程的并发性，这种算法的执行效率将以较慢的进程所决定。假设进程1以1小时10次的速率进入进程，进程2以一小时1000次的速率进入进程。那么进程2就必须适应进程1的步调。
另一方面，假设某一进程被终止了，则会造成其他进程的永久阻塞。

算法二

算法一虽然解决了决定进入进程的进程号，但是实际上为了保证一个进程失败，其他进程也能进入进程，我们还需要进程的状态。

所以我们通过布尔数字变量来联系进程的状态，当进入临界区时flag[x] = true，反之为false

while(flag[other]){
    do nothing
}
flag[x] = true
critical section 
flag[x] = false

这个算法虽然解决了进程失败会影响到其他进程的问题，但是如果以并发的角度考虑，这个算法并没有保证互斥的要求。假设有两个进程并发的执行

p0执行while语句发现flag[1]为false
p1执行while语句发现flag[0]为false
p0设置flag[0]为true，并进入临界区
p1设置flag[1]为true，并进入临界区

显然，以这样的顺序执行，程序出错。

算法三

算法二失败的原因在于，在一个进程可以在另一个进程检查完他的状态后，再改变自己的状态。只要修正了个这个错误即可，所以简单的我们只需将自身状态的改变移动到检查他人状态之前即可

flag[x] =true
while(flag[other]){
    do nothing
}
critical section 
flag[x] = false

但是在这样修改了以后同样出现了新的问题，同样以并发的角度考虑两个进程。

当进程P1与进程P0都想要进入临界区时，同时将在自己flag置于true时，然后在检查其他人状态时发现其他人都想进入。

这就会造成P0进程等待P1进程释放flag，P1进程等待P0进程释放flag,造成死锁。

算法四

为了解决算法三的死锁问题，我们引入了一种使得进程在发现其他进程也同样想进入临界区时，可以回退自己状态的“谦让机制” ,即当发现其他进程要进入临界区时，将自己的flag区设置为false,过段时间将自己回设置到true

flag[x] = true
while(flag[other]){
    flag[x] = false
    delay
    flag[x] = true
}
critical section 
flag[x] = false

这个问题虽然解决了算法三的死锁问题，但是如果我们考虑到以这样的顺序并发执行:

P0设置flag[0]为true
P1设置flag[1]为true
P0检查P1
P1检查P0
P0设置flag[0]为false
P1设置flag[1]为false
P0设置flag[0]为true
P1设置flag[1]为true

显然，程序会以这样的顺序无限循环下去。但是严格的讲，由于循环可能会被程序交替执行的速度所打破，所以可以称作是一个活锁。

Dekker算法

算法四的进程满足了互斥，解决了死锁问题，留有一个互相谦让的活锁。当两个进程的互相前让对方进入临界区时，我们可以借鉴算法一的思想，通过一个全局变量turn来指定一个进程进入临界区，这样既可满足所以要求。也就是Dekker算法的核心思想。

boolean flag[] 
int turn;

void PX(){
    while( true){
        flag[X] = true
        while(flag[other]){
            if(turn == other){
                flag[X] = false;
                while(turn == 1) do nothing
                flag[X] = true;
            }
        }
        critical section
        turn = other;
        flag[X] = false;
    }
}

Peterson算法

在Dekker算法的思想下，Peterson算法用了一种更为简答出色的方式。

void PX(){

    while(true){
        flag[x] = true;
        turn  = other;
        while(flag[other] && turn == other) do nothing
        critical section
        flag[0] = false

    }
}

从并发的角度考虑Peterson算法，当多个进程都需要进入临界区时，全局变量会被最后一个运行的进程所覆盖掉值，从而制定了某个进程进入临界区，而其他进程在临界区外等待。同样其他进程执行完以后，将flag[other]置为false。那么当前进程也不会进入while循环，而是进入临界区，则不会造成阻塞的现象。

总结

从算法的角度考虑互斥保护，要时时刻刻以并发的角度，从不同执行顺序上来思考程序会不会死锁，活锁等问题。

另外一点是，从所有的程序中可以看出，软件解法存在一个问题在于：当一个进程进入临界区时，其他进程必须不停的去检查自己是否能进入临界区，这同样造成了CPU开销。从这方面可以看出，为何我们后面还会再去引入硬件机制与信号量的概念。