进程同步与互斥

基本概念

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

进程的异步性：进程的执行次序无法预知。

临界资源

虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。

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

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

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

互斥

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

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

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

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

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

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

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

同步

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

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

进程互斥的软件实现

单标志法
双标志先检查
双标志后检查
Peterson算法

单标志法

该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号，即若turn=0，则允许P0进程进入临界区。该算法可确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，如果某个进程不再进入临界区了，那么另一个进程也将无法进入临界区（违背“空闲让进”的同步机制准则）这样很容易造成资源利用的不充分。

while(turn!=0);
critical section;
turn=1;
remainder section;

引用《操作系统：精髓与设计原理》P122关于其缺点的一段话：

这种解决方案保证了互斥属性，但有两个缺点。第一，进程必须严格交替使用它们的临界区，因此执行的步调由二者中较慢的进程决定。。若P0在1小时内仅使用临界区1次而P1要以1000次/小时的速率使用临界区，则P1必须适应P0的节奏。更为严重的问题是，若一个进程终止，另一个进程就会被永久阻塞。无论进程是在临界区内终止还是在临界区外终止，都会发生这种情况。

忙等待(busy waiting)/自旋等待(spin waiting)

进程中之一想要进入临界区执行时必须先检查turn的内容。若turn的值等于进程号，则进程可以进入它的临界区；否则该进程被强制等待。等待进程重复地读取turn的值，知道被允许进入临界区。这一过程就称为忙等待/自旋等待。

双标志先检查

该算法的基本思想是在每一个进程访问临界区资源之前，先查看一下临界资源是否正被访问，若正被访问，该进程需等待；否则，进程才进入自己的临界区。为此，设置了一个数据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 之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行。

双标志后检查

算法二是先检测对方进程状态标志后，再置自己标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后，同时进入临界区。为此，算法三釆用先设置自己标志为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语句），发现对方也要进入临界区，每个进程都会认为另一个已经进入临界区，引发死锁。

解决了互斥问题，但和前面两个一样，若一个进程在临界区内及控制临界区的flag设置代码处失败，则另一个进程就会被阻塞。（也就是违反了“空闲让进“和”有限等待“准则，解决了”忙则等待“）

Peterson算法

bool flag[2];
int turn = 0;//表示优先让哪个进程访问临界区

// 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解决死锁现象。

小结

以上几种算法中，Peterson算法是最好的了。但是它仍然有一个不足：其保证了四个准则中的前三条，但并没有保证“让权等待“的准则。

进程互斥的硬件实现

中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换，这样屏蔽中断就能保证当前运行进程将临界区代码顺利地执行完，从而保证了互斥的正确实现，然后再执行开中断。

其典型模式为：

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

这种方法限制了处理机交替执行程序的能力，因此执行的效率将会明显降低。对内核来说，当它执行更新变量或列表的几条指令期间关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断之后不再开中断，则系统可能会因此终止。

优点：简单高效

缺点：不适用于多处理机系统，只适用于操作系统内核进程，不适用于用户进程（因为开关中断指令只能运行在内核态，交给用户随意使用非常危险）

硬件指令方法/锁方法

TestAndSet指令

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

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

可以为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态：true表示正被占用，初值为false。在进程访问临界资源之前，利用TestAndSet检查和修改标志lock；若有进程在临界区，则重复检查，直到进程退出。利用该指令实现进程互斥的算法描述如下：

    while TestAndSet (&lock);
    // 进程的临界区代码段;
    lock=false;
    // 剩余区代码段;

相比软件方法实现，TS指令把“上锁”和“检查"操作用硬件方式变成了“一气呵成”的原子操作。

优点：实现简单，无需像软件方式那样严格检查是否存在逻辑漏洞。适用于多处理机。

缺点：也不满足“让权等待”准则，暂时无法进入临界区的等待进程会占用CPU并循环执行TS指令导致“忙等”。

Swap指令

或称Exchange/XCHG指令。同样用硬件实现，不允许中断。

以下为使用C语言描述的逻辑：

//功能描述
Swap(boolean *a, boolean *b){  
    boolean temp;
    Temp=*a;
    *a = *b;
    *b = temp;
}

bool old=true;
while(old==true)
    swap(&lock,&old);
//进程的临界区代码段；
lock=false;
//剩余区代码段；

逻辑上来看Swap和TS/TSL指令并无区别，特点同上。

最后更新于3年前