第6章进程同步

6.1 背景

进程能并发执行
并发时数据共享可能导致数据不一致
需要机制来保证协作进程的有序执行，从而保证数据一致
例子：生产者-消费者问题中的计数器counter

竞争条件：两个进程同时试图修改一个共享内存的内容，最后的结果依赖于两个进程的执行顺序和时机

6.2 临界区问题

考虑一个具有$n$个进程${p_0, …, p_{n-1}}$的系统，每个进程都有一段称作临界区（critical section）的代码，在临界区内，进程可能改变共同变量、更新一个表、写一个文件等
至多只允许一个进程进入临界区
进程需要请求进入临界区的许可，这段请求许可的代码叫做进入区（entry section）
临界区之后可能有退出区（exit section），最后是剩余区（remainder section）

临界区问题的解决方案必须满足下面三个要求：

互斥（mutual exclusion）：同一时间，临界区最多存在一个进程
前进（progress）：如果现在临界区里没有进程，且有一个进程想要进入临界区，那它一定会进入临界区
有限等待（bounded waiting）：如果进程$P_i$处于入口区，那么在$P_i$的请求被接受之前，其他进程进入临界区的次数有上限

假设每个进程都以非零的速度执行，但不对这$n$个进程之间的相对速度作任何假设

OS解决临界区问题的两种方式：

抢占式内核
非抢占式内核

在内核模式下不可能出现竞争条件（抢占式就不一定了）

但人们还是倾向于抢占式内核，因为它响应度更高、适合实时编程

6.3 Peterson算法

并不保证能在现代架构上运行，但这是一个很好的解决临界问题的算法描述

限制条件：

2个进程，$P_0$和$P_1$
假设load和store都是原子操作

两个进程共享两个变量：

int turn; 表示现在允许谁进入临界区
boolean flag[2]; 表示$P_i$想不想进入临界区

Peterson算法（对进程$P_i$）：

证明三个要求满足：

满足互斥：仅当flag[j]==false或turn=i时，$P_i$能进入临界区。这就意味着要么$P_j$不想进入临界区，要么没挨到$P_j$进入临界区，所以两个进程不会同时在临界区内，互斥成立
满足前进性：若$P_j$并不打算进入临界区，则flag[j]=false，继续在循环里待着。当$P_i$想要进入临界区时，flag[i]=true，turn=i，$P_i$可以进入临界区
满足有限等待：若两个进程都打算进入临界区，假设turn=j，则$P_j$先进入临界区。一旦$P_j$结束，flag[j]=false，$P_i$就可以进入临界区

Peterson可能不能在现代结构上运行的原因：

为了提升系统性能，处理器或编译器可能对读写操作重新排序，这对单线程应用没有影响，但会影响多线程应用

6.4 硬件同步

6.4.1 内存屏障（Memory Barriers）

内存模型（memory model）是计算机架构对应用程序做出的内存保证。

内存模型的种类：

强排序（strongly ordered）：一个处理器的内存修改马上对其它所有处理器可见
弱排序（weakly ordered）：可能不是马上对其他所有处理器可见

内存屏障就是强制内存中任何修改都要传给其它所有处理器的一条指令

e.g.

// Thread 1
while (!flag)
	memory_barrier();
print x

// Thread 2
x = 100;
memory_barrier();
flag = true;

对于Peterson方法来说，在入口区的flag和turn赋值中间加上内存屏障就可以避免语句重排造成的问题了

6.4.2 硬件指令

Test-and-Set：

把输入的逻辑值设为true，并返回它本来的值

boolean test_and_set(boolean *target) {
	boolean rv = *target;
	*target = true;
	
	return rv;
}

应用：

循环，直到lock的值是false

这意味着：
1. lock在test_and_set里又被设为true了
2. 之所以lock原来的值是false，是因为某个进程离开了临界区，将lock还原为了false
进入临界区
lock还原为false
剩余区

do {
	while (test_and_set(&lock))
	; /* do nothing */
	/* critical section */
	lock = false;
	/* remainder section */
} while (true);

Compare-and-Swap

int compare_and_swap(int *value, int expected, int new_value) {
	int temp = *value;
	if (*value == expected)
		*value = new_value;
	return temp;
}

当value是expected的时候，把value设为new_value（若value的值不是expected，就保持不变）；返回value本身的值

应用：

把lock初始为0

若lock是0，则设为1，退出循环

若lock是1，则返回1，继续循环

while (true) {
	while (compare_and_swap(&lock, 0, 1) != 0)
	; /* do nothing */
	/* critical section */
	lock = 0;
	/* remainder section */
}

（注意：以上应用不满足有限等待的要求）

6.4.3 原子变量

compare_and_swap()一般作为构建其它解决临界区问题工具的基本模块。

其中一种工具是原子变量，它为基本数据类型（例如int和bool）提供不能被打断的原子更新

e.g. 对原子变量sequence执行increment()操作，保证sequence在没有被打断的情况下增加：increment(&sequence)

void increment(atomic_int *v) {
	int temp;
	do {
		temp = *v;
	}while (temp != (compare_and_swap(v,temp,temp+1));
}

6.5 互斥锁

以上基于硬件的解决方案都比较复杂，而且对应用程序员不可见

OS设计者构建了更高层次的软件工具来解决临界区问题

最简单的就是互斥锁（mutex lock）（mutex = mutual exclusion）

进入临界区之前要acquire()锁，出来要release()锁

acquire()和release()都必须是原子操作

while (true) {
    acquire();
    // critical section
    release();
    // remainder section
}

在互斥锁中，变量available指示锁是不是可用

acquire() {
	while (!available)
	; /* busy wait */
	available = false;
}

release() {
	available = true;
}

缺陷：

忙碌等待（或称自旋，busy waiting）浪费了CPU周期，这种锁也叫自旋锁（spinlock）

6.6 信号量（Semaphores）

（表现得和互斥锁差不多，但比互斥锁更高级）

信号量$S$是一个int型变量，只能被wait()（或者说P）和signal()（或者说V）两个原子操作访问

wait(S) {
	while (S <= 0)
	; // busy wait
	S--;
}

signal(S) {
	S++;
}

6.6.1 信号量的用法

计数型信号量：$S$可以在无限制的定义域里取值
二元信号量：$S$只能取0或1（和互斥锁一样啦）

6.6.2 信号量的应用

有忙碌等待的信号量应用不太好，就不讲了

无忙碌等待的信号量应用：

每个信号量都有一个关联的等待队列
等待队列里每一项都有两部分：int型的值、指向下一个进程的指针

两种操作：

block：把引起操作的进程放在合适的等待队列中
wakeup：把等待队列中的某个进程出队，然后放进就绪队列

wait(semaphore *S) {
	S->value--;
	if (S->value < 0) {
		add this process to S->list;
		block();
	}
}

signal(semaphore *S) {
	S->value++;
	if (S->value <= 0) {
		remove a process P from S->list;
		wakeup(P);
	}
}

信号量的问题：用错操作

6.7 管程（Monitor）

一种能为进程同步提供方便且高效机制的高层次抽象

6.7.1 管程用法

管程是一种抽象数据结构，在管程内定义的函数只能访问管程内的局部变量，同样，局部变量也只能被管程内的函数访问

在管程内某个时刻只有一个进程是活动的，所以程序员不需要显式地编写同步代码。但程序员也可以用condition类自己写特定的同步方案。condition类只有两种操作：wait()和signal()

condition x, y;
x.wait();
x.signal();

x.wait()表示，调用操作的进程被挂起，直到另一个进程调用x.signal()操作

x.signal()重新启动一个悬挂的进程。但如果没有x.wait()，则x.signal()就无效（区分信号量里的signal，会影响信号量的状态）

e.g. 假设现在进程P调用了x.signal()，进程Q和x相关联。如果Q继续执行，那么P必须等待，否则管程里就有两个进程了。所以两种情况：

唤醒并等待（Signal and wait）：P等待，直到Q离开管程，或者等待另一个条件
唤醒并继续（Signal and continue）：Q等待，直到P离开管程，或者等待另一个条件

6.7.2 基于信号量的管程实现

每个管程都有一个信号量mutex，初始化为1。进程在进入管程前必须执行wait(mutex)，在离开管程后必须执行signal(mutex)

这里用唤醒并等待。因为信号进程（执行了signal的进程）必须等待，直到重新启动的进程离开或等待，所以引入了另一个信号量next，初始化为0，以供信号进程挂起自己。另外还提供了一个int型变量next_count，对挂起在next上的进程数量进行计数。因此每个外部子程序F会替换成

wait(mutex);
	...
	body of F
	...
if (next count > 0)
	signal(next);
else
	signal(mutex);

这样就确保了管程内的互斥

condition变量的实现:

对每个condition变量x，引入信号量x_sem和int型变量x_count，两者均初始化为0，则x.wait()可实现如下：

wait(){
    x count++;
    if (next count > 0)
        signal(next);
    else
        signal(mutex);
    wait(x sem);
    x count--;
}

x.signal()可实现如下：

signal(){
    if (x count > 0) {
        next count++;
        signal(x sem);
        wait(next);
        next count--;
    }
}

这种实现适用于Hoare和Brinch-Hansen所给出的管程定义。然而，在某些情况下，这种实现过于通用，效率有很大改进空间

6.7.3 管程内的进程重启

这里讨论管程内进程重新启动的顺序：如果多个进程悬挂在condition x上，且某个进程执行了x.signal()，怎么决定谁先被唤醒？

FCFS（first-come, first-served 谁先睡的谁先起）：太简单了，不太够
条件等待（conditional-wait）：x.wait(c)，c是优先值，c小的优先级高，先醒

6.8 活性（Liveness）

进程可能无限等待互斥锁/信号量

无限等待违背了前进和有限等待准则

liveness指一组系统必须满足的性质，保证进程的前进

无限等待是liveness failure的一种

6.8.1 死锁（Deadlock）

死锁指两个及以上进程无限等待一个事件，该事件由其中一个等待的进程引起

e.g.

若$P_0$先执行wait(S)，$P_1$执行了wait(Q)。

在$P_0$执行wait(Q)之前，必须等$P_1$执行signal(Q)。

但$P_1$又在等$P_0$执行signal(S)

所以$P_0$和$P_1$就死锁了

其他形式的死锁：

饥饿（starvation）：无限阻塞
优先级倒置（priority inversion）：低优先级的进程有一个高优先级进程需要的锁

6.8.2 优先级倒置

定义见上

避免方法：优先级继承协议（priority-inheritance protocol）

所有访问高优先级进程所需资源的进程继承高的优先级，直到访问结束

进程同步

Operating System Notes

第6章进程同步

6.1 背景

6.2 临界区问题

6.3 Peterson算法

6.4 硬件同步

6.4.1 内存屏障（Memory Barriers）

6.4.2 硬件指令

6.4.3 原子变量

6.5 互斥锁

6.6 信号量（Semaphores）

6.6.1 信号量的用法

6.6.2 信号量的应用

6.7 管程（Monitor）

6.7.1 管程用法

6.7.2 基于信号量的管程实现

6.7.3 管程内的进程重启

6.8 活性（Liveness）

6.8.1 死锁（Deadlock）

6.8.2 优先级倒置

FEATURED TAGS

FRIENDS

第6章 进程同步

6.1 背景

6.2 临界区问题

6.3 Peterson算法

6.4 硬件同步

6.4.1 内存屏障（Memory Barriers）

6.4.2 硬件指令

6.4.3 原子变量

6.5 互斥锁

6.6 信号量（Semaphores）

6.6.1 信号量的用法

6.6.2 信号量的应用

6.7 管程（Monitor）

6.7.1 管程用法

6.7.2 基于信号量的管程实现

6.7.3 管程内的进程重启

6.8 活性（Liveness）

6.8.1 死锁（Deadlock）

6.8.2 优先级倒置

FEATURED TAGS

FRIENDS

第6章进程同步