再论“读者优先”

摘要

本文指出了读写问题中传统半读者优先算法的局限性，并设计了新的全读者优先算法，在不抢占资源的情况下将读者的优先级提高到了理论最高优先级。本文对全读者优先算法进行了实验验证。

读者写者问题

对读者写者问题的描述参见：计算机与操作系统-06-并发程序设计：7.2 读者/写者问题。

传统读者优先算法

对传统读者优先算法的描述参见：计算机与操作系统-06-并发程序设计：7.2.1 读者优先。

该算法来自《操作系统教程（第 5 版）》（高等教育出版社）第 142 页，书中内容如下：

半读者优先实例

对上述算法，给出一个实例：

进程	到达时间/秒	工作时间/秒
W1	0	4
W2	2	4
R1	3	2

按照传统算法，W1 占用 wmutex 时，W2 先到达，并对 wmutex 排队；R1 后到达，也对 wmutex 进行排队；
按照互斥信号量 wmutex 的等待队列，必然是 W2 比 R1 先开始运行，即后来的读者 R1 不能对先到的写者 W2 进行插队（指比先到的写者 W2 先开始工作），我们将这种“读者优先”称为半读者优先（Half-Reader First，HRF）；
相应的，如果后来的读者 R1 能对先到的写者 W2 进行插队，我们将这种算法称之为全读者优先（Full-Reader First，FRF）。

读者优先定义

结合以上实例，我们对半读者优先和全读者优先给出形式化的定义：

全读者优先定义

正在等待的进程不能抢占运行中的进程；
如果等待队列中只有写者，并且当前没有进程在运行，则选择其中最早到达的写者开始运行；
如果等待队列中有读者，并且当前没有写者在运行，则读者开始运行（即使等待队列中可能还有更早到达的写者）。

半读者优先定义

正在等待的进程不能抢占运行中的进程；
如果等待队列队头是写者，并且当前没有进程在运行，则该写者开始运行；
如果等待队列中有读者 \(R_2\)，并且当前有读者 \(R_1\) 在运行，则该读者 \(R_2\) 开始运行；
如果等待队列队头是读者，并且当前没有进程在运行，则该读者开始运行。

设计全读者优先算法

有些写者到来时，没有任何进程在使用将要被写的资源，我们将这样的写者称为先驱者（pioneer）；其余的写者，即到来时已经有读者或写者在使用将要被写的资源，被称为后来者（follower）。

在上述实例中，引入新的信号量 rwmutex，用于阻塞后来者。重新设计的算法保证：任何一个读者到来时，没有任何后来者正在对 wmutex 排队。因此，当前使用 wmutex 的进程结束之后，该读者可以马上开始工作。即，后来的读者可以对先来的写者插队。

容易证明：该算法在不抢占资源的情况下将读者的优先级提高到了理论最高优先级：即当前进程工作完成后，读者可以紧随其后开始工作，并不需要等待其他写者。

semaphore rmutex = 1; // 控制对 read_count 的互斥访问
semaphore wmutex = 1; // 控制对文件内容的互斥写
semaphore rwmutex = 1; // 用于阻塞后来者
int read_count = 0;

process reader_i() {
	while (true) {
		P(rmutex);	// rmutex 用于互斥访问 read_cout
		if (read_count == 0)
			P(wmutex);	// 如果当前是第一个读者，阻塞写者，以保证读到的数据不被更改
		++read_count;
		V(rmutex);

		read();

		P(rmutex);
		if (--read_count == 0)
			V(wmutex);	// 如果当前结束的是最后一个读者，允许开始写
		V(rmutex);
	}
}

process writer_i() {
	while (true) {
		P(rwmutex); // 增加了这一互斥信号量
		P(wmutex);	// wmutex 用于互斥访问
		write();
		V(wmutex);
		V(rwmutex); // 增加了这一互斥信号量
	}
}

实验验证

在《计算机与操作系统》第四次实验的代码基础之上，笔者进行了修改，实验配置和实验结果如下。

实验配置

进程	实验结果中的位置	启动时间	运行时间
读者 B	左数第 1 列	t = 3 时刻	4 秒
读者 C	左数第 2 列	关闭了该进程	关闭了该进程
读者 D	左数第 3 列	关闭了该进程	关闭了该进程
写者 E	左数第 4 列	t = 0 时刻	4 秒
写者 F	左数第 5 列	t = 2 时刻	2 秒

实验结果

实验结果描述：Z 表示该进程未开启或未到来，X 表示该进程正在阻塞，O 表示该进程正在运行。

传统半读者优先算法（HRF）	全读者优先算法（FRF）
写者 E 结束后，写者 F 抢在读者 B 之前开始工作，读者 B 没能够成功插队。	写者 E 结束后，读者 B 在写者 F 之前开始工作，读者 B 成功插队，实现了全读者优先。

结论

改进后的 FRF 算法比传统 HRF 算法更能够提高读者的优先级，在不抢占资源的情况下将读者的优先级提高到了理论最高优先级：即当前进程工作完成后，读者可以紧随其后开始工作，并不需要等待其他写者。