操作系统-进程互斥和同步

背景

avatar

为什么会有同步和互斥？因为计算机系统中有多个进程存在，多个进程间进行交互，会引起它们对 共享资源的访问，如果这些资源处理不当，就可能出现一些意想不到的情况，比如说 饥饿，死锁等一系列问题。

为什么会出现 饥饿，死锁问题，主要还是和进程调度相关。如果进程相对独立，彼此之间没有共享资源，彼此不需要发送数据或者通知对方干某些事情，那么进程和线程的执行过程是确定的，可重复的，那就不存在上述问题。但是如果不独立，彼此间需要进行交互，那么这种情况下，由于 调度系统的管理，有可能一会先调用这个进程，一会又先调用另一个进程，由于进程调度顺序不确定，可能导致对于单个进程而言，执行过程出现不确定性和不可重复性，因此会引入一些很难发现的 bug，导致系统出现不稳定的现象。

上述现象，称为Race Condition(竞态条件)。虽然有上述问题，但是进程间交互，共享资源又是必不可少的，因此我们需要引入同步和互斥来解决上述不确定性问题。

一些基本概念

Atomic Operation (原子操作)
原子操作是指一次不存在任何中断或者失败的执行。
Critical Section (临界区) ：满足互斥，前进，有限等待
临界区是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不会被执行的代码区域。(简单说：访问共享资源的一段代码)
Mutual exclusion (互斥)
当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源。(简单说：不允许多个进程进入临界区去访问)
Dead lock (死锁)
两个或以上的进程，在相互等待完成特定任务，而最终没法将自身任务进行下去。(简单说：两个进程需要等待对方的资源而导致无法向下执行)
Starvation (饥饿)
一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行。

临界区代码的保护方法 (锁的设计方法)

禁用硬件中断
时钟中断，进行进程调度，执行临界区时屏蔽中断

缺点：
- 临界区执行时间过长，对系统整体执行效率影响很大
- 多CPU并行执行，屏蔽一个CPU中断不管用，无法解决互斥

基于软件的解决方法
除了用在一般操作系统中，也用在分布式系统当中。

皮特森(Peterson)算法
flag表示本进程已经准备好了想进去，然后如果两个进程都想进那么就要设立一个turn标志，
turn表示如果两个进程都想进去临界区，turn=i就允许i进程进临界区。因为turn只能是一个值，
所以也保证了两个进程竞争时只能有一个进去。如果不竞争，那turn无意义。（可使用反证法证明）
Dekker算法
针对双线程
Bakery算法
针对n线程临界区问题解决方案

Peterson 算法大致代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#define true 1
#define false 0
typedef int bool;
bool flag[2];
int turn;

void procedure0()
{
        while(true)
        {
                flag[0] = true;
                turn = 1;
                while(flag[1] && turn == 1)//退出while循环的条件就是，要么另一个线程
                                          //不想要使用关键区，要么此线程拥有访问权限。
                {
                    sleep(1);
                    printf("procedure0 is waiting!\n");
                }
                //critical section
                flag[0] = false;
        }
}

void procedure1()
{
        while(true)
        {
                flag[1] = true;
                turn = 0;
                while(flag[0] && turn == 0)
                {
                    sleep(1);
                    printf("procedure1 is waiting!\n");
                }
                //critical section
                flag[1] = false;
        }
}

void main()
{
        pthread_t t1,t2;
        flag[0] = flag[1] = false;
        int err;
        turn = 0;
        err =  pthread_create(&t1,NULL,(void*)procedure0,NULL);
        if(err != 0) exit(-1);
        err = pthread_create(&t2,NULL,(void*)procedure1,NULL);
        if(err != 0 ) exit(-1);
        pthread_join(t1,NULL);
        pthread_join(t2,NULL);
        exit(0);
}

Dekker 算法大致代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#define true 1
#define false 0
typedef int bool;
bool flag[2];
int turn;

void visit(int num)
{
        sleep(1);
        printf("P%d is visting\n",num);
}

void P0()
{
        while(true)
        {
                flag[0] = true;//P0想使用关键区。
                while(flag[1])//检查P1是不是也想用？
                {
                        if(turn == 1)//如果P1想用，则查看P1是否具有访问权限？
                        {
                                flag[0] = false;//如果有，则P0放弃。
                                while(turn == 1);//检查turn是否属于P1。
                                flag[0] = true;//P0想使用。
                        }
                }
                visit(0); //访问Critical Partition。
                turn = 1; //访问完成，将权限给P1。
                flag[0] = false;//P0结束使用。
        }
}

void P1()
{
        while(true)
        {
                flag[1] = true; //P1想使用关键区。
                while(flag[0]) //检查P0是不是也想用？
                {
                        if(turn == 0) //如果P0想用，则查看P0是否具有访问权限？
                        {
                                flag[1] = false; //如果有，则P1放弃。
                                while(turn == 0); //检查turn是否属于P0。
                                flag[1] = true; // P1想使用。
                        }

                }
                visit(1); //访问Critical Partition。
                turn = 0; //访问完成，将权限给P0。
                flag[1] = false; //P1结束使用。
        }
}

void main()
{
        pthread_t t1,t2;
        flag[0] = flag[1] = false;
        turn = 0;
        int err;
        err =  pthread_create(&t1,NULL,(void*)P0,NULL);
        if(err != 0) exit(-1);
        err = pthread_create(&t2,NULL,(void*)P1,NULL);
        if(err != 0 ) exit(-1);
        pthread_join(t1,NULL);
        pthread_join(t2,NULL);
        exit(0);
}

更高级的抽象 (基于硬件原子操作指令，将下述两个流程封装成了机器指令，执行过程中不允许执行中断和切换)
Test-and-Set

boolean TestAndSet(boolean *target)
{
  boolean rv = *target;
  *target = TRUE;
  return rv;
}

具体使用例子：
class Lock{
int value = 0;
Acquire();
Realease();
};

Lock::Acquire(){
while(test-and-set(value))
;//spin (当有进程执行，将value设置成1，其他进程再来执行的时候就一直是1，进入while循环自旋，直到value = 0)
}

Lock::Realease(){
value = 0;
}

Exchange

void Exchange(boolean *a, boolean *b)
{
  boolean temp = *a;
  *a = *b;
  *b = temp;
}

共享数据：
  int lock = 0;
线程Ti
 int key;
 do{
    key = 1;
    while(key == 1) Exchange(lock, key);
    critical section
    lock = 0;
    remainder section
 }

如果觉得进程自旋忙等浪费CPU性能，而且临界区执行时间较长，那可以通过上下文切换，使得等待进程进入阻塞睡眠，当临界区进程执行完，再进行唤醒。是采用忙等还是进行上下文切换让进程进入睡眠，需要看一下临界区执行时间是否很长，如果执行时间长，则让进程进入睡眠。如果临界区执行时间很短，反而上下文切换对CPU损耗时间更长，则采用忙等。

信号量

同步机制，临界区多个线程和进程来执行，进入临界区只是做读操作而不是写操作，如果只是读操作，那就没必要只是限制一个进程或者线程执行，可以有多个线程或者进程执行。多个进程或线程那么就要引入信号量来解决这个问题。

数据抽象
-> 一个整形(sem)，两个原子操作
-> P(): sem减1，如果sem < 0，等待，否则继续执行
-> V(): sem加1，如果sem <= 0, 唤醒一个等待的P
信号量特点
- 信号量是有符号整数
  一开始我们会设置成一个大于 0 的数，多次进行P()操作，一旦信号量小于0，则执行P()操作的
  进程不能再向下执行，该进程就需要挂在该信号量上面。直到有其他进程执行V()操作，而且信
  号量还小于等于0，则判断有进程挂在该信号量上面，因此唤醒一个进程
- 信号量是被保护的变量
  -> 初始化完成后，唯一改变一个信号量的值得办法是通过P()和V()
  -> 操作必须是原子的
- P() 能够阻塞, V() 不会阻塞
- 我们假定信号量是 “公平的”
  FIFO先进先出队列管理挂在信号量上面的进程
- 两种类型的信号量
  -> 二进制信号量: 可以是0或者1 (可以完成锁机制功能)
  -> 一般/计数信号量: 可取任何非负值 (允许多个执行P()操作的进程进入临界区)
  -> 两者相互表现(给定一个可以实现另一个)
- 信号量可以用在2个方面
  -> 互斥
  -> 条件同步 (调度约束 – 一个线程等待另一个线程的事情发生)

信号量使用 (解决生产者-消费者问题)
生产者-消费者正确性要求：

在任何一个时间只能有一个线程操作缓冲区(互斥)
当缓冲区为空，消费者必须等待生产者(调度/同步约束)
当缓冲区满，生产者必须等待消费者(调度/同步约束)

示例伪代码：

class BoundedBuffer{
     mutex = new Semaphore(1);
     fullBuffers = new Semaphore(0); // 初值为 0
     emptyBuffers = new Semaphore(n); // 初值为 n 
   }

   BoundedBuffer::Deposit(c){
     emptyBuffers->P();  
     mutex->P();
     Add c to the buffer;
     mutex->V();
     fullBuffers->V();
   }

   BoundedBuffer::Remove(c){
     fullBuffers->P();
     mutex->P();
     Remove c to the buffer;
     mutex->V();
     emptyBuffers->V();
   }

信号量的实现
大致代码：

class Semaphore{
  int sem;
  WaitQueue q;
}

Semaphore::P(){
  sem--;
  if(sem < 0){
    Add this thread t to q;
    block(t);
  }
}

Semaphore::V(){
  sem++;
  if(sem <= 0){
    Remove a thread t from q;
    wakeup(t);
  }
}

管程

由于信号量机制的缺点：进程自备同步操作，P(S)和V(S)操作大量分散在各个进程中，不易管理，易发生死锁。
因此引入管程的概念，这是一种比信号量更高的抽象。或者说并没有这种实体存在于系统或编程语言中，更多的是一种机制，一种解决方法，但是编程语言和操作系统都提供了实现管程的重要部件条件变量。

管程特点：管程封装了同步操作，对进程隐蔽了同步细节，简化了同步功能的调用界面。用户编写并发程序如同编写顺序(串行)程序。
目的：分离互斥和条件同步的关注
什么是管程：
-> 一个锁：指定临界区
-> 0或者多个条件变量：等待通知信号量用于管理并发访问共享数据

avatar

管程具体的执行流程图

进程或线程以队列方式进入临界区前，执行wait(), 如果不能满足条件变量，则将进程或线程挂在相应条件变量队列上，直到有其他进程或线程执行完临界区，执行Signal(), 唤醒相应队列中的进程或线程继续执行。
管程实现

其中wait()需要释放 lock，是由于在进入管程接口时，会先加锁，确保同一时刻只能有一个进程或者线程调用。
实现生产者消费者问题

总结

主要介绍了锁，信号量，管程(管程依赖于锁和条件变量)。这三种机制可以解决同步互斥问题。需要注意的是，即使是有同步互斥方法来解决这些问题，但是由于不确定性现象的存在，使得对它进行调试分析很困难，出错了需要知道是怎么错的，因为下次重复操作的时候，问题可能不会重复出现，那么这种情况下，就需要我们 仔细的去设计和分析相应的同步互斥的操作过程，才能够解决此类问题。

总的来说，想要用好同步互斥，需要我们仔细的去分析问题，设计相应的操作流程，才能够有效的解决同步互斥的问题。