操作系统中对信号量的保护

背景

信号量的引入使得线程/进程之间同步活动。但是对于操作信号量的接口调用代码必须是原子的，否则可能会使得信号量的内容不能够反映出资源的真实情况。这种必须为原子操作的代码块称为临界区(CS, critical section)。即，不同线程/进程中（以下将线程和进程统称为进程，因为在本文讨论的内容中它们没有区别）没有两个任务可以在它们的临界区内同时执行。

对信号量的保护便属于一个临界区问题(critical-section problem)，对于临界区问题的解决方案应同时满足以下三个要求：

• 互斥进入(mutual exclusion, 简写为mutex)：如果进程Pi在其临界区内执行，那么其他进程都不能在其临界区内执行。
• 有空让进(progress)：如果没有进程处于临界区内且有进程请求进入临界区，则应该能让某个请求进程进入临界区执行，即不发生资源的死锁情况。
• 有限等待(bounded waiting)：当一个进程提出进入临界区请求后，最多需要等待临界区被使用有限次以后，该进程就可以进入临界区。这样，任何一个进程对临界区的等待时间都是有限的，即不出现因等待临界区而造成的饥饿情况。

解决方案（软件实现）

1.轮换法与标记法

采用轮换法，任何时候就只有一个进程有权利进入临界区，只有这个进程退出临界区后才能轮换到其他进程，显然这满足了互斥性。其代码如下：

以P0为当前进程为例，如果它发现现在轮到的是P1而不是自己，则不停地自旋等待直到时间片用尽切换到进程P1；P1发现现在是轮到自己，于是执行CS代码段，执行完后将turn置为0表示该轮到P0了。

轮换法只是一个简单prototype，其的缺点是很明显的。比如：P0得到进入CS代码段的决定权在P1中，如果P1进程被销毁，则P0则不再可能获得进入CS的机会。即，轮换法没有实现有空让进。

标记是另一种朴素的解决方法。进程P0想要进入CS就做一个标记。做完标记以后扫描其他进程是否要进入CS，如果有这样的进程，则P0自旋等待。其代码如下：

这种方案显然也是不可行的，如果两个进程都想进入CS，它们就会互相等待而没任何一个可以进入CS，即出现了死锁，无法满足有限等待。

这两种朴素解决方案各自可以解决三个要求中的两个，将它们进行简单的组合便可以同时满足三个要求，这就是Peterson算法。

2.Peterson算法

还是从进程P0出发，其想要进入CS，则将其flag置为1，同时将访问权设为P1而不是自己，此时如果P1也想进入则进入自旋等待。过了一会P0的时间片用尽，操作系统调度到进程P1，P1从头开始执行，将自己的flag置为1，将访问权设为P0，然后也进入自旋等待。过了一会再调度到P0执行，此时的turn已经被进程P1设置为P0，所以P0可以进入CS。其进入CS后将自己的flag再置为false，P1得以进入CS。

上面讨论的这种执行顺序（事实上有很多可能的执行顺序）有点像两个人在互相谦让，A对B说：虽然我想访问，但还是你先来吧；B对A说，虽然我也想访问，但还是你先来吧；A不再推辞，便进行了访问。A访问后B也得到了访问的机会。

下面来看看Peterson算法是否满足临界区问题的三个要求。
一、互斥性：假设P0和P1能够同时执行CS的代码，则显然turn即等于1又等于0，所以显然是不可能的。所以满足互斥性
二、有空让进：假如两个进程中有一个不想进入临界区，则另一个进程便不会自旋等待，可以进入临界区。假如两个进程都想进入临界区，那么按照上面的讨论得知会有一个进程可以进入临界区。所以满足有空让进。
三、有限等待：假设操作系统不断地调度到P1，那么在P1执行完CS的代码后，会将flag置为0,。此时P1再次执行的话就会不停地自旋等待，从而可以调度到其他生产者进程执行。矛盾，所以满足有限等待。

3.Lamport面包店算法

面包店算法由Leslie Lamport提出。他将临界区控制问题直观地类比为多个顾客去面包店采购的问题，这里每个顾客是一个进程，面包店一次只能接待一位顾客采购，显然是一种互斥，所以采购动作对应的就是临界区代码。面包店的做法是：N个顾客要进入面包店采购，首先按照次序给每个顾客安排一个号码，顾客按照其号码由小到大依次进行购买，完成购买的顾客号码置为0，这样完成购买的顾客如果想要再次购买，就必须重新排队。基于这样的思想编写出相应的进入区代码和退出区代码。下面是其代码实现：

//Lamport Algorithm
do
{
	choosing[i] = true;
	number[i] = max(number[0], number[1], ..., number[n-1]) + 1; //选取号码
	choosing[i] = false;
	for (j = 0; j < n; j++) 
	{
		while (choosing[j]);
		while ((number[j] != 0) && (number[j], j) < (number[i], i));
		//这里(a, b) < (c, d)表示 a < c || (a == c && b < d)
	}
	//Critical Section
	number[i] = 0;
} while (true);

面包店算法是Peterson算法是一个推广，因为Peterson算法只能应用于两个进程的情况，而面包店算法可以应用于多个进程是情况。但是其思想是相同的，都是标记+轮换。在面包店算法中，选号的过程相当于做标记，表示某个进程想要访问，其获得的标记决定了其执行顺序；而标号最小的进程可以进入CS，这相当于轮换，只不过轮换对象是整个队列。

下面来翻译一下这段代码。
首先如果某个进程想要访问CS，对应着面包店实例中的购买，则其需要排队（取一个号），这个号比当前所有在排队的进程的号都大，使得其在队列的尾部。完成取号后，将choosing置为false，表示其已经取号完毕，进入队列。
接着依次访问在队列中的进程的信息，如果某个进程在取号，则需要当前进程自旋等待，因为有可能那个进程已经取到了号码，但是还没有将choosing置为false就被调度了。所以我们便无法得知那个进程的号码和当前号码比谁大谁小，所以不确定是否是该轮到当前进程了。
然后再确认这个进程的确是在排队（choosing != 0），并保证要么这个进程的号码比自己大，要么两个号码一样大但是自己的ID比那个进程小。
所有可能的进程都要进行上述检验，不满足任何一个检验过程都会使当前进程自旋等待。

容易证明面包店算法是满足三个要求的。

但是其缺点也是非常明显的，那就是其检测开销太大了，并且号码是有可能被取完的，因此要进行号码的维护。在计算机系统中，当软件实现变得很复杂时，通常会想到的方法就是让硬件来简化操作，提高效率。

解决方案（硬件实现）

1.关中断

关中断的基本思想是：由某个进程P0切换到另一个进程P1需要进入内核调用schedule()函数，而要进入内核则需要中断。所以当某个进程在执行CS之前能够禁止中断，再在其执行完CS后恢复中断，那么就保证了CS操作的原子性。

其中，禁止中断的指令是cli，允许中断的指令是sti。cli的工作原理是执行这条指令的cpu会将其CPU EFLAGS寄存器中的中断允许标志位IF(interrupt flag)置为0，这个CPU就不会再每次执行完指令时检查并处理中断了。

但是对于一个多CPU计算机（多核或多处理器）系统，因为每个CPU都自带其寄存器组，仅仅关闭当前线程的CPU中断就无效了，因为有可能其他CPU正在运行着另一个竞争进程。所以要达到相同的目的需要关闭所有CPU的中断，但这样对于一个操作系统来说开销实在是太大了。

2.硬件原子指令法

互斥信号量mutex = 0 or 1实现了互斥访问的控制，那么我们可不可以用另一个信号量来保证临界区代码中信号量的互斥访问呢？这显然就形成了一个套娃，因为这个信号量也需要被保护。

但是如果对外层这个“信号量”的操作是原子的呢？也就是说它仅需一条指令就可以完成呢？幸运的是，硬件架构提供了这样的原子指令。

很多CPU都支持TestAndSet这一硬件指令。这条指令有一个操作数，是一个布尔变量的指针，如果该内存中的变量为false，该指令会返回false，并且将内存中的变量置为true（即返回没有上锁的状态并上锁）；如果在内存中的变量为true，则返回true（已经上锁，不做任何操作）。其指令相当于一下代码：

function TestAndSet(boolean &lock) {
	boolean initial = *lock;
	*lock = true;
	return initial;
}

有了这样一条硬件指令来处理lock，我们就可以利用lock来保护临界区了。代码如下：

这里有一个例外情况，那就是在多核系统中如果多个进程刚好都在同一瞬间执行指令TestAndSet操作lock，会出现意料之外的后果。硬件设计师在设计TestAndLock时也考虑到了这种情况，因此在执行这条指令时，CPU会锁住内存总线，禁止其他CPU在这条指令结束之前访问内存，这样就不会有多个CPU在同一时间执行这个指令了。

上述硬件加锁的方法保证了互斥，但是没有满足有限等待，由上述讨论过的面包店算法可以类似地写出满足有限等待的TestAndSet实现。进程Pi对应的代码如下：

do {
	waiting[i] = true;
	key = true;
	while (waiting[i] && key)
		key = TestAndSet(&lock);
	waiting[i] = false;

	
	
	j = (i + 1) % n; //all processes are in an array
	while ((j != i) && !waiting[j])
		j = (j + 1) % n;
	//判断为何跳出循环
	if (j == i)
		lock = false;
	else // j is waiting
		waiting[j] = false;
} while (true)

上述代码中共用的数据结构为布尔变量boolean lock和布尔数组boolean waiting[n]，它们一开始全部赋值为false。

下面证明这个算法满足三个要求：
一、互斥：只有waiting[i] == false 或者 key == false时，进程Pi才能进入临界区，只有当执行TestAndSet时，key的值才变成false。执行TestAndSet的第一个进程会发现key==false并将其置为true；所有其他进程必须等待。只有另一进程离开临界区时，变量waiting[i]的值才能变成false；每次只有一个waiting[i]被置为false，以满足互斥要求。
二、有空让进：进程在退出临界区时将lock置为false，或者将waiting[j]置为false，这两种情况都使得等待进程不再自旋，从而进入临界区。
三、有限等待：当一个进程退出临界区时，它会循环扫描数组(i+1, i+2, …, n-1, 0, …, i-1)，并根据这一顺序而指派第一个等待进程(waiting[i]==true)作为下次进入临界区的进程。所以任何等待进入临界区的进程只需等待n-1次。