首先还是看这张图,对我们当前正在学习的地方做一个定位:

上一篇笔记我们已经讲了进程的相关概念和进程控制的知识,这篇笔记则涉及到了进程同步与进程互斥。

1. 进程同步与进程互斥

1.1 进程同步

问题:

在多道批处理系统中,多个进程是并发执行的,而并发执行的进程具有异步性,也就是说,各个进程以各自独立的、不可预知的速度向前推进。这样会带来什么问题呢?如果有 AB 两个进程分别进行读写数据的操作,那么写数据应该发生在读数据之前,而实际上,由于异步性的存在,可能会发生先读后写的情况,而此时由于缓冲区为空,该读数据进程就会被阻塞。

解决方案:

所以,我们要通过进程同步来解决此类问题。

与进程同步相关的也就是直接制约关系,指的是多个进程一起完成某个任务,这些进程因为合作、因为需要在某些位置上协调他们的工作次序而产生了某些制约关系。

1.2 进程互斥

问题:

在多道批处理系统中,多个进程是并发执行的,而并发执行的进程不可避免地需要共享一些系统资源(比如内存、打印机、摄像头等)。这样会带来什么问题呢?实际上,有些资源在一个时间段内只允许一个进程使用,诸如各种物理设备、变量、数据、内存缓冲区等,这些称之为临界资源 —— 也就是说,一方面,并发执行的进程需要共享资源;另一方面,临界资源的访问又必须是互斥地进行(不能同时共享),很显然,这会导致资源访问上的矛盾。

解决方案:

所以,我们要通过进程互斥来解决此类问题。

与进程互斥相关的也就是间接制约关系,指的是当 A 进程在访问某个临界资源时,另一个也想要访问该资源的 B 进程就必须等着,直到 A 进程访问结束并释放资源后,B 进程才能去访问。

基本实现逻辑:

为了实现临界资源的互斥访问,可以在逻辑上将一个进程对临界资源的访问过程分为四个部分:

do {
    extry section;       // 进入区
    critical section;    // 临界区
    exit section;        // 退出区
    remainder section;   // 剩余区
} while(true)
  • 进入区:A 进程想要访问临界资源,首先会在进入区检查是否可以进入,由于此时没有其它进程占用临界资源,所以检查通过,同时它设置了一个 Flag 标志当前自己正在访问临界资源;
  • 临界区:实际访问临界资源的那段代码
  • 退出区:负责解除之前的 Flag
  • 剩余区:其它处理

对于 B 进程,如果此时它也想要访问这个资源,同样就会在进入区做一个检查,它知道了 A 进程正在访问,所以自己就不能访问了。这样就实现了资源访问的互斥。

四个原则:

更加具体的细节,我们需要用四个原则来约束这个互斥的过程:

  • 空闲让进:临界区空闲时,说明没有进程使用临界资源,此时应该让想要进入临界区的进程立刻进来
  • 忙则等待:如果已经有进程进入临界区,则其它同样想要进入的进程只能等着
  • 有限等待:不能让进程一直干等着,要保证他在有限的时间内可以进入临界区
  • 让权等待:当 A 进程进入临界区而导致 B 进程不能进入自己的临界区时,应该立刻释放处理机,防止进程陷入“忙等”状态。

2. 如何实现进程互斥

2.1 软件层面如何实现进程互斥

① 单标志法:

单标志法的核心是用一个 Flag 来标志哪个进程可以进入临界区,在初始给定 Flag 的情况下,一定可以确保是 Flag 对应的进程可以进入临界区。而在该进程顺利进入并完成自己的任务后,它会将 Flag 改指向另一个进程。我们通过一个例子来说明:

int turn = 0;

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

在一开始我们置 Flag 指向 0 号进程。设想有两种可能:一种是 P0 进程先上处理机,那么此时不满足 while 条件,则顺利进入自己的临界区;另一种是 P1 进程先上处理机,尽管如此,由于满足 while 条件,所以陷入了死循环,一直无法进入临界区,直到消耗完了自己的时间片,轮到了 P0 运行。P0 由于不满足循环条件,所以顺利进入临界区。值得注意的是,在这个过程中,即使由于 P0 消耗完了时间片而导致处理机使用权转让给了 P1,P1 也不会实际进入临界区,而是不断循环 —— 这就确保了整个过程中,即使进程不断来回切换,始终都只有 P0 在使用临界资源,也就是做到了我们所要的“互斥访问资源”

但问题在于,观察整个过程会发现,P0 完成任务后将“使用权限“(Flag)转交给 P1,而 P1 完成后也转交给 P0,所以整个过程一直都是 P0 ——> P1 ——> P0 ——> P1… 这样交替进行,也就是说,即使 P0 运行完之后想要再次运行,它也不得不先等待 P1 的完成

另一个问题是,P0 如果一直不访问临界区,那么就算此时临界区空闲、且 P1 有意愿想要访问临界资源,P1 也无法访问,也就是**”空闲不让进“**。这很明显违背了上面所说的”空闲让进“原则。

② 双标志先检查法:

双标志法不是用一个 Flag 来指示哪个进程可以进入临界区,而是为每个进程都设置一个可以起到开关作用的 Flag。它的核心是,初始所有的进程 Flag 都为 false,表示暂时都不想进入临界区。某一时刻有个进程想要进入了,他首先会检查当前是否有其他进程正在占用,有的话就作罢,自己慢慢等,没有的话就自己进入,一进入就马上打开 Flag 开关为 true,相当于”上了一把锁“,这期间只有自己拥有占有权,其他进程都是进不来的。在自己完成任务后,再置 Flag 为 false,相当于释放了占有权(把锁打开)。我们通过一个例子来说明:

bool flag[2];
flag[0] = false;
flag[1] = false;

P0 进程:                        P1 进程:
while (flag[1]);                while (flag[0]);
flag[0] = true;                 flag[1] = true;
critical section;               critical section;
flag[0] = false;                flag[1] = false;
remainder section;              remainder section;

这里的过程还是和之前一样的,即使其它进程被调度,也会陷入死循环而消耗完自己的时间片,所以看起来是可以实现互斥的了。

而且,注意这里单个进程释放”权限“的不同。单标志法的释放”权限”,是把“权限”交给一个指定的进程,这说明了另一个进程想要得到“权限”,必须经过这个进程的同意(所以才有了交替运行的问题);但是由于双标志法设置的是可以起到开关作用的 Flag,所以所谓释放“权限”不过是放开了自己的权限,其它进程想要进入临界区只管进入就可以,不用非要这个进程进行指定,所以,这个方法不会有交替运行的问题,他在一定程度上做到了解耦。

问题在于,检查上锁 并不是一个原子操作,它是可以被打断的 —— 这意味着,在检查之后、没来得及上锁之前,如果进程突然切换到 B 进程,那么 B 进程就会在 A 进程“上锁”之前抢先跳过本该陷入的死循环。之后,不管进程有没有再次切换回去,对于 A、B 进程来说,它们都跳过了循环,这意味着它们都可以顺利进入临界区,进而同时使用临界资源。换句话说,双标志先检查法并不能保证互斥访问资源,它违背了“忙则等待”的原则。

③ 双标志后检查法

双标志后检查法与先检查法的区别在于,它是先“上锁”后“检查”。也就是说,先检查法的问题在于“上锁”上得太慢,给其他进程可乘之机,所以后检查法决定不管怎么样,先上了锁再说。看下面这个例子:

bool flag[2];
flag[0] = false;
flag[1] = false;

P0 进程:                        P1 进程:
flag[0] = true;                 flag[1] = true;
while (flag[1]);                while (flag[0]);
critical section;               critical section;
flag[0] = false;                flag[1] = false;
remainder section;              remainder section;

后检查法解决了“忙则等待”的问题,但又违背了“空闲让进”和“有限等待”的原则 —— 由于非原子操作而引起的根本问题并未得到解决,因此极有可能导致两个进程都无法进入临界区。

比方说,P0 想要进入临界区,那么他就会抢先“上锁”,而由于“上锁”和“检查”之间有空隙,如果进程 P0 在这段空隙切换到了 P1,那么 P1 也会进行“上锁”。此后,无论进程是否有切换回去,双方都会陷入死循环无法自拔(因为此时双方都拿到了“上锁”的机会,锁死别人,也锁死了自己),进而导致谁都无法进入临界区,产生“饥饿”现象。

④ Peterson 算法

Peterson 算法实际上同时结合了单标志法和双标志后检查法,它的核心就是:在一开始还是和后检查法一样,抢先进行“上锁”,但是上锁之后又将 turn 置为对方线程,表示自己虽然想要进入临界区,但是不介意“将这个机会让给对方”。尽管如此,由于 while 的限制条件增加了,而 turn 又是公用的,所以保证了最后只会有一方的 while 满足条件。既做到了互斥访问资源,也避免了双方都访问不到资源。

还是来看下面这个例子:

bool flag[2];  flag[0] = false;  flag[1] = false;
int turn = 0;     

P0 进程:                        P1 进程:
flag[0] = true;                 flag[1] = true;
turn = 1;                       turn = 0;
while (flag[1] && turn == 1);   while (flag[0] && turn == 0);
critical section;               critical section;
flag[0] = false;                flag[1] = false;
remainder section;              remainder section;

首先进入后检查法的情况,即:P0 首先表示想要进入临界区,因此它的 Flag 为 true,之后进程切换来到了 P1,P1 也表示自己想要进入临界区,因此它的 Flag 也是 true。

在后检查法中,这种情况注定了双方都陷入死循环,谁也无法进入。但是 Peterson 算法却不一样。

在这个算法中,**对方进程想进入、且最后一个做出“谦让”的进程最终将无法进入临界区。**继续上面的例子,此时可能:

  • 继续执行 turn = 0,while (flag[0] && turn == 0),由此进入了死循环,于是时间片用完后来到了 P0,P0 执行 turn = 1,while (flag[1] && turn == 1),同样进入了死循环,于是时间片用完后来到了 P1,注意,此时对于 P1 来说,它的 while 条件不满足,所以顺利进入了临界区,直到运行完释放“权限”,P0 的才有机会跳出自己的死循环。

    这种情况,由于 P0 是最后一个“谦让”的,所以是对方 P1 进入临界区

  • 或者,切换到 P0 执行 turn = 1,while (flag[1] && turn == 1), 由此进入了死循环,于是时间片用完后来到了 P1,执行 turn = 0,while (flag[0] && turn == 0),同样进入了死循环,于是时间片用完后来到了 P0,此时对于 P0 来说,while 条件已经不满足,所以 P0 得以顺利进入临界区。

    这种情况,由于 P1 是最后一个“谦让”的,所以是对方 P0 进入临界区

  • And others …

考虑到进程并发的异步性,其实有很多种排列组合的情况,但是不管哪种情况,可以肯定的是:即使双方都想进入临界区,由于 turn 只有一个,也肯定有一方可以顺利跳出死循环,进入临界区。这就避免了“饥饿”现象的产生;同时,只要自己进程临界区没执行完,就永远不会释放”权限“,意味着对方进程不会乘机抢着进入临界区,这就保证了”互斥“。

用一个生活案例来解释,可能更好理解:

甲乙两个人同时去图书馆借一本书,甲说:”我很想看这本书,但是你想看的话,我不介意让你先看“,而乙也说:”我也很想看这本书,但是你这么谦让我都不好意思了,还是你先看吧“,双方就这样互相你来我往。到最后甲也累了,于是在听到乙再次说了”让你先看“之后,甲拍了拍乙的肩膀,同时把书拿了过来,说:”好吧,那我先看吧,我看完,你再看。“

Peterson 算法解决了空闲让进、忙则等待、有限等待的问题,但还是没有解决让权等待的问题。也就是说,P1 进程尽管无法进入临界区,但是在时间片轮到自己的时候还是会做无意义的死循环,白白占用了处理机,而这些资源本该是给 P0 使用的。

2.2 硬件层面如何实现进程互斥

① 中断屏蔽方法

在双标志方法中,有可能出现两个进程同时进入临界区的情况,而中断屏蔽方法可以很好地避免这种情况。

它和原语的原理很像,一样是通过”开/关中断指令“,来实现原子操作。具体地说,就是让进程在进入临界区之前先执行关中断指令”上锁“,保证了此后整个执行过程不会被中断,自然也不会发生进程切换、两个进程同时访问临界资源的情况,在访问完临界区之后,再通过开中断指令”解锁“,这样其它进程才有机会访问临界区。

中断屏蔽方法的优点是简单高效,但是它不适用于多处理机,并且由于涉及到了开/关中断这两个特权指令的使用,所以其实这种方法只适用于内核进程,不能用于用户进程。

② TestandSetLock 指令

TestAndSetLock /TestAndSet 指令也叫 TSL/TS 指令。双标志方法的根本问题出在”上锁“和”检查“是非原子操作,导致某个进程可以利用这两个操作的空隙,而 TSL 指令将两个操作变成了原子操作(一气呵成,不留空隙),同时它也做到了像中断屏蔽指令那样,一旦进入临界区,执行过程就无法被中断。

虽然这是硬件操作,不过我们暂且用伪代码来进行理解:

bool TestAndSet (bool *lock){
    bool old;
    old = *lock;
    *lock = true;
    return old;
}
P0:                                        P1:
while (TestAndSet(&lock));                 while (TestAndSet(&lock));
critical section;                          critical section;
lock = false;                              lock = false;
remainder section;                         remainder section;

其中,lock 是全局变量,记录当前临界区是否”上锁“。

首先,进程 P0 想要访问临界区,那么就会来到 while 循环,在这个循环里,它一气呵成完成了”上锁“和”检查“的工作 —— 循环里执行了 TSL 函数,一方面将全局 lock 改为 true,一方面返回旧的值为 false 的 lock 给自己。所以,对自己来说,由于返回的是 false,它得以跳过循环进入临界区;而对 P1 进程来说,每次切换到它这里,它在 while 里企图”上锁“和”检查“的时候,都会由于之前全局 lock 已经被置 true 而陷入死循环。

因此,整个过程就保证了 P0 的”上锁“和”检查“是一气呵成的原子操作,同时也让 P0 执行时绝对不会被切换。在 P0 执行完之后,全局 lock 再次置 false,以此类推。

TSL 指令的方法实现简单,无需严格检查逻辑,也适用于多处理机环境,但是它仍然不满足”让权等待“的原则 —— 从伪代码可以看出,P1 在无法如愿进入临界区后仍然可能白白地占用处理机,导致”忙等“。

③ Wrap 指令

Swap 指令或称 Exchange / XCHG 指令,它的逻辑其实和 TSL 指令差不多:

P0:                             P1:
bool old = true;                bool old = true;  
while (old == true)             while (old == true)
	Swap(&lock,&old)  ;        	    Swap(&lock,&old)  ;  
critical section;               critical section;
lock = false;                   lock = false;
remainder section;              remainder section;

一开始全局 lock 还是 false,P0 想要进入临界区,首先置 old 为 true,后面用 Swap 完成交换,所以得以跳出循环进入临界区;而对于 P1 进程,由于它共享全局 lock,全局 lock = 自身 old = true,所以陷入了死循环,无法进入临界区。

和 TSL 指令一样,Swap 指令也无法解决“让权等待”的问题。

那么,是否有更加完善的方法来解决这个问题呢?


操作系统系列学习笔记:

操作系统学习笔记-1:基础概念

操作系统学习笔记-2:体系结构和运行机制

操作系统学习笔记-3:初识进程和进程控制

操作系统学习笔记-4:进程同步与进程互斥(一)

操作系统学习笔记-5:进程同步与进程互斥(二):信号量机制

操作系统学习笔记-6:进程同步与进程互斥(三):经典问题

操作系统学习笔记-7:进程通信

操作系统学习笔记-8:线程

操作系统学习笔记-9:调度