5.1 进程同步

一、进程同步的概念

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约的关系。为了协调进程之间的相互制约的关系，引入进程同步的概念。

1.临界资源

虽然多个进程可以共享系统中的各种资源，但其中许多资源依次只能为一个进程所使用，这类资源称为临界资源。许多物理设备都属于临界资源，例如打印机、磁带机。此外，全局变量，静态变量、数据等都可以被若干进程共享，也属于临界资源。

对临界资源的访问，必须互斥地进行。在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可以把临界资源的访问分成四个部分。

do{
    entry section;//进入区
    critical section;//临界区
    exit section;//退出区
    remainder section;//剩余区
} while (true);

• 进入区
  为了进入临界区使用临界资源，在进入区要检查可否进入临界区，如果可以进入，则应该设置在访问临界区的标志，以阻止其他进程同时进入临界区。
• 临界区
  进程中访问临界资源的代码段，又称为临界段
• 退出区
  将正在访问临界区的标志清除
• 剩余区
  进程代码中其余部分

2.同步

同步亦称为直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系源于它们之间相互的合作。

例如，输入进程A通过单缓冲向进程B提供数据。当该缓冲区空时，进程B不能获得所需数据而阻塞，一旦进程A将数据送入缓冲区，进程B被唤醒。反之，当缓冲区满时，进程A被阻塞，仅当进程B取走缓冲数据时，才唤醒进程A。

可以用下图简单表示：

3.互斥

互斥亦称为间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许区访问此临界资源。

例如，在仅有一台打印机的系统中，有两个进程A和进程B，如果进程A需要打印时, 系统已将打印机分配给进程B,则进程A必须阻塞。一旦进程B将打印机释放，系统便将进程A唤醒，并将其由阻塞状态变为就绪状态。

为禁止两个进程同时进入临界区，同步机制应遵序以下准则：

• 空闲则让
  临界区空闲时，可以允许一个请求进入空闲区的进程立即进入临界区
• 忙则等待
  当已有进程进入临界区时，其他试图进入临界区的进程必须等待
• 有限等待
  对请求访问的进程，应保证能在优先时间内进入临界区
• 让权等待
  当进程能进入临界区，应立即释放处理器，防着进程忙等待

二、临界区的实现

1.软件实现方法

在进入区设置和检查一些标志来标明是否有进程在临界区中，如果已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

接下来介绍两种软件解决方案：Peterson算法与Dekker算法。

• Dekker算法

bool flag[2];
int turn;//访问权限
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想使用。
            }
        }
        do_something();//访问critical section
        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是否属于P1
                flag[1] = true; // P1想使用。
            }
        }
        do_something();//访问critical section
        turn = 0; //访问完成，将权限给P0
        flag[1] = false; //P1结束使用
    }
}

• Peterson算法

bool flag[2];//访问请求
int turn;//访问权
void* procedure0(void *){
    while (true){
        flag[0] = true;
        turn = 1;
        while (flag[1] && turn == 1){
            //P1需要访问且拥有访问权时，P0等待
            //当P1不想访问或者不具备权限时推出
            Sleep(1);
            printf("procedure0 is waiting!\n");
        }
        do_something();//访问critical section
        flag[0] = false;
    }
}
void* procedure1(void *){
    while (true){
        flag[1] = true;
        turn = 0;
        while (flag[0] && turn == 0){
            //P0需要访问且拥有访问权时，P1等待
            //当P0不想访问或者不具备权限时推出
            Sleep(1);
            printf("procedure1 is waiting!\n");
        }
        do_something();//访问critical section
        flag[1] = false;
    }
}

2.硬件实现方法

计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。通过硬件支持临界区访问的方法或称为元方法。

硬件实现方法主要有两种：中断屏蔽方法和硬件指令方法。

• 中断屏蔽方法
  当某进程正在执行其临界区代码时，为防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，称之为屏蔽中断或关中断。由于CPU只在发生中断时引起进程切换，中断的屏蔽便可保证当前进程顺利执行完临界区代码，进而保证互斥。其典型模式为：
  …
  关中断;
  临界区;
  开中断;
  …
  中断屏蔽的实现方式代价很高。如果临界区比较大的话会限制并发能力，不适用与多处理器，适用于操作系统本身，不适用与用户进程

• 硬件指令方法
  1）TSL（TestAndSetLock）指令
  这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。指令的功能描述如下：

enter_region:
    TSL REGISTER, LOCK
    CMP REGISTER, #0
    JINE enter_region
    RET
leave_region
    MOVE LOCK, #0
    RET

2）XCHG（EXCHANGE）指令
该指令的功能是交换两个字节的内容。其功能描述如下：

enter_region:
    MOVE REGISTER, #1
    XCHG REGISTER, LOCK
    CMP REGISTER, #0
    JINE enter_region
    RET
leave_region
    MOVE LOCK, #0
    RET