ClarkCheung
ClarkCheung

I'm writing something about Computer Science, especially some basic knowledges.

操作系统:进程间通信

竞态条件

进程常常需要与其他进程通信。例如,排队系统中,每个用户进程可能需要跟系统进程通信来得知他们的位置。而进程的并发执行可能会带来一些问题。

例如,有两个进程并行执行下列语句:

new_pid = next_pid++;

如果next_pid = 100,那么其中一个进程的得到的pid应该是100,另一个的pid是101,而next_pid的值应该增加到102。

但如果进程在某些特殊时刻抢占,则结果可能不同,如下图:

图1 进程竞态条件

在这种情况下,两个或多个进程读写某些共享数据,而最后的结果取决于进程运行的精确时序,我们把这种情况称作竞态条件。

互斥

实际运行中,我们希望尽可能地避免竞态条件,从而使程序具备可重复性。这要求一个进程在使用一个共享变量或文件时,其他进程不能做同样的操作。我们把这种情况称为互斥。

或者我们可以用一种更抽象的描述。我们把访问共享内存的程序片段称为临界区,如果我们安排得当,使两个进程不可能同时处于临界区之中,我们就能够避免竞态条件。

尽管有多种方法能够避免竞态条件,但我们希望在避免竞态条件的同时,进程能够正确高效地运行。为此有以下四个条件:

  1. 任何两个进程不能同时处于其临界区。
  2. 不应对CPU的数量和速度做任何假设。
  3. 临界区外运行的进程不得阻塞其他进程。
  4. 不得使进程无限期等待进入临界区。

一些解决方案

屏蔽硬件中断

这是一种最简单的方法。当一个进程进入临界区后,立即屏蔽硬件中断直到其运行结束。这种方案的缺点也非常明显。整个系统都需要等待这个进程主动地开启中断。

锁变量

一种软件解决方案。设想有一个共享(锁)变量,其初始值为0,当一个进程想进入临界区的时候,它首先测试这个变量,如果为0,就把锁置为1并进入临界区,若锁的值为1,则该进程等待直到其值变为0。

但这种方法并不能严格保证临界区内只有一个进程。比如第一个进程读锁变量之后立即中断,第二个进程读锁变量进入临界区,恢复中断后第一个进程也会随即进入临界区。

严格轮换法

设定一个整型值turn,turn的初始值为0,只有进程号和turn的进程相等的情况下,进程才能进入临界区。每个进程退出临界区的时候,将turn的值置为下一个要进入临界区的进程号。在临界区外的进程则循环测试turn的值,看它的值何时会变为自己的进程号。

这种方法乍一看很公平,但是会导致忙等——例如,进程0第二次需要用临界区的时候,进程1还未使用过临界区,此时进程0不得不等待进程1进入临界区,即使临界区内的资源无人使用。

peterson算法

#define FALSE 0
#define TRUE 1
#define N 2
int turn;//现在轮到谁?
int interested[N];//所有值初始化为0.(哪个进程需要访问临界区?)
void enter_region(int process){
int other;//另一进程号

other  = 1-process;
interested[process] = TRUE;
turn = process;
while(turn == process&&interested[other]==TRUE);
}
void leave_region(int process){
interested[process] = FALSE;//离开临界区
}
CC BY-NC-ND 2.0 版权声明

喜欢我的文章吗?
别忘了给点支持与赞赏,让我知道创作的路上有你陪伴。

加载中…

发布评论