进程同步的基本概念：临界资源、同步和互斥

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。

为了协调进程之间的相互制约关系，引入了进程同步的概念。

临界资源

虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次仅允许一个进程使用的资源称为临界资源。

许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。

对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。

访问过程

为了保证临界资源的正确使用，可以把临界资源的访问过程分成四个部分：

进入区。为了进入临界区使用临界资源，在进入区要检查可否进入临界区，如果可以进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。

临界区。进程中访问临界资源的那段代码，又称临界段。

退出区。将正在访问临界区的标志清除。

剩余区。代码中的其余部分。

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

同步

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

进程间的直接制约关系就是源于它们之间的相互合作。

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

互斥

互斥亦称间接制约关系。

当一个进程进入临界区使用临界资源时，另一个进程必须等待, 当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

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

准则

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

  • 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。

  • 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。

  • 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。

  • 让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

实现临界区互斥的基本方法

软件实现方法

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

1) 算法一：单标志法。

该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号，即若turn=0，则允许P0进程进入临界区。

该算法可确保每次只允许一个进程进入临界区。

但两个进程必须交替进入临界区，如果某个进程不再进入临界区了，那么另一个进程也将进入临界区（违背“空闲让进”）这样很容易造成资源利用的不充分。

// P0进程
while(turn!=0);
critical section;
turn=1;
remainder section;

// P1进程
while(turn!=1);  // 进入区
critical section;  // 临界区
turn = 0;  // 退出区
remainder section;  // 剩余区

2) 算法二：双标志法先检查。

该算法的基本思想是在每一个进程访问临界区资源之前，先查看一下临界资源是否正被访问，若正被访问，该进程需等待；否则，进程才进入自己的临界区。

为此，设置了一个数据flag[i]，如第i个元素值为FALSE，表示Pi进程未进入临界区，值为TRUE，表示Pi进程进入临界区。

// Pi 进程
while(flag[j]);  // ①    
flag[i]=TRUE;  // ③  
critical section;   
flag[i] = FALSE; 
remainder section;

// Pj 进程
while(flag[i]);  // ② 进入区
flag[j] =TRUE;  // ④ 进入区
critical section;  // 临界区
flag[j] = FALSE;  // 退出区
remainder section;  // 剩余区

优点：不用交替进入，可连续使用；

缺点：Pi和Pj可能同时进入临界区。按序列①②③④ 执行时，会同时进入临界区（违背“忙则等待”)。即在检查对方flag之后和切换自己flag 之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行。

3) 算法三：双标志法后检查。

算法二是先检测对方进程状态标志后，再置自己标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后，同时进入临界区。

为此，算法三釆用先设置自己标志为TRUE后,再检测对方状态标志，若对方标志为TURE，则进程等待；否则进入临界区。

// Pi进程
flag[i] =TRUE;
while(flag[j]);
critical section;
flag[i] =FLASE;
remainder section;

// Pj进程
flag[j] =TRUE;  // 进入区
while(flag[i]);  // 进入区
critical section;  // 临界区
flag [j] =FLASE;   // 退出区
remainder section;  // 剩余区

当两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态（执行while语句），发现对方也要进入临界区，于是双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。

4)算法四：Peterson’s Algorithm。

为了防止两个进程为进入临界区而无限期等待，又设置变量turn，指示不允许进入临界区的进程编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入。

这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区，只允许一个进程进入临界区。

// Pi进程
flag[i]=TURE; turn=j;
while(flag[j]&&turn==j); 
critical section;
flag[i]=FLASE;
remainder section;

// Pj进程
flag[j] =TRUE;turn=i;  // 进入区
while(flag[i]&&turn==i);   // 进入区
critical section;  // 临界区
flag[j]=FLASE;  // 退出区
remainder section;  // 剩余区

本算法的基本思想是算法一和算法三的结合。

利用flag解决临界资源的互斥访问，而利用turn解决“饥饿”现象。

硬件实现方法

本节对硬件实现的具体理解对后面的信号量的学习很有帮助。

计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。

通过硬件支持实现临界段问题的低级方法或称为元方法。

1) 中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，或称之为屏蔽中断、关中断。

因为CPU只在发生中断时引起进程切换，这样屏蔽中断就能保证当前运行进程将临界区代码顺利地执行完，从而保证了互斥的正确实现，然后再执行开中断。

其典型模式为：

…
关中断;
临界区;
开中断;
…

这种方法限制了处理机交替执行程序的能力，因此执行的效率将会明显降低。

对内核来说，当它执行更新变量或列表的几条指令期间关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断之后不再开中断，则系统可能会因此终止。

2) 硬件指令方法

TestAndSet指令：这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。

指令的功能描述如下：

boolean TestAndSet(boolean *lock){
    boolean old;
    old = *lock;
    *lock=true;
    return old;
}

可以为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态：true表示正被占用，初值为false。

在进程访问临界资源之前，利用TestAndSet检查和修改标志lock；若有进程在临界区，则重复检查，直到进程退出。

利用该指令实现进程互斥的算法描述如下：

while TestAndSet (& 1ock);
// 进程的临界区代码段;
lock=false;
// 进程的其他代码

Swap指令：该指令的功能是交换两个字节的内容。

其功能描述如下。

Swap(boolean *a, boolean *b){  
    boolean temp;
    Temp=*a;
    *a = *b;
    *b = temp;
}

注意：以上对TestAndSet和Swap指令的描述仅仅是功能实现，并非软件实现定义，事实上它们是由硬件逻辑直接实现的，不会被中断。

应为每个临界资源设置了一个共享布尔变量lock，初值为false；在每个进程中再设置一个局部布尔变量key，用于与lock交换信息。

在进入临界区之前先利用Swap指令交换lock 与key的内容，然后检查key的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。

利用Swap指令实现进程互斥的算法描述如下：

key=true;
while(key!=false)
Swap(&lock, &key); 
// 进程的临界区代码段；
lock=false;
// 进程的其他代码；

硬件方法的优点：适用于任意数目的进程，不管是单处理机还是多处理机；简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。

硬件方法的缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

参考资料

操作系统的基本概念

https://lgwain.gitbooks.io/os/content/unit11.html