进程同步通信经典问题—读者写者问题的算法分析与设计

2021-07-22曾思源徐艳

电子测试 2021年12期

曾思源，徐艳

（四川大学锦城学院计算机与软件学院，四川成都，611731）

关键字：读者和写者；同步通信；PV操作算法

0 引言

一个共享的数据集合，会面临同时被多个进程访问的情况。一个存储器，一个数据库，亦或是内存中的一个寄存器，都可以成为这个数据集合。其中一类进程只有读取数据的需求，且不会对数据进行修改，我们称此类进程为读进程。而另外一类进程会对数据集中的数据进行修改，我们称之为写进程。

无论是多少个读进程存在，都不会对数据进行修改，因此读进程是被允许同时访问的。但是写进程是不会被允许与其他读/写进程同时访问数据集，因为这将违反Bernstein条件,破坏数据的完整性、正确性。

1 读者写者问题的算法分析

1.1 信号量控制

要实现读写进程之间的互斥，我们首先想到的就是添加信号量。

在操作系统中，信号量在解决多种多样的进程同步问题起到了至关重要的作用，比如，信号量能够保证两个或者多个临界区不被并发调用。同时，信号量本质上代表的，是某种资源的可利用数量。

信号量只能通过初始化和两个标准的原语来访问--作为OS核心代码执行，不受进程调度的打断[1]。P操作减少一个信号量的值，如果它的值大于零，进程继续执行，否则就睡眠，等待唤醒；而V操作增加它的值，若有进程在此信号量上睡眠，则唤醒之[2]。

在该问题当中，我们首先尝试使用信号量rw来达到我们的需求。因为读写算法相同，所以以写算法为例。信号量rw初始值赋为1。算法如下：

写进程：

1.2 存在的问题

假如此时有个读进程A进入程序，首先会通过P(rw)拿走资源，然后进入临界区进行读文件操作。在此同时，写进程B也试图进入程序，由于读进程A还没有进行V(rw)，所以写进程B会被阻塞，只有当读进程A通过V(rw)释放掉资源，写进程B才能进入临界区。

此算法的确解决了读写进程之间的互斥问题，但在此同时，多个读进程之间也变成互斥访问了，并不满足引言中所提出的需求，因此这种算法不能达到要求。

1.3 改进算法——读者程序加入计数器实现读者优先

我们通过1.1发现，只加入一组信号量不能解决问题。因此，在这里引入一个变量count，用来记录当前正在访问数据集的进程的数量，进而能更方便的解决后面的问题。所有信号量初值均赋为1，count初值赋为0，写进程算法与1.1相同，因此不再赘述。实现如下：

可以很明显的看出，该算法与1.1最大的区别是在P(rw)和V(rw)操作的两侧，加入了带if检测的count计数器。Count代表的是访问该进程的读进程数量，进入程序/退出程序时会进行自动的加减。If语句中的条件，目的是判断当前还有多少个读进程在访问临界资源，如果是第一个进程，便会通过P(rw)操作将写进程给阻塞掉。同时，因为有if的存在，不满足条件的后来的读进程不会因为前一个读进程而阻塞在P(rw)，从而实现了读进程之间的同步访问。

需要特别注意的是，在控制count加减和加/解锁操作的两侧，都加入了新信号量mutex，保证count的增减和加/解锁操作的连贯性。试想，假如没有该信号量，此时进来读进程A，刚进行了P(rw)的操作，还没来得及进行count++的操作，又进来另一个读进程B，此时的count还是为零，满足if判断的结果，试图用P操作上锁，但由于前一个进程A没有执行V操作释放信号量，所以进程B就被阻塞了，这是不能被允许的。

1.4 读者优先存在的问题

这种算法，基本实现了引言中的需求。但是弊端也很明显，当读者进程源源不断的进入，写者进程会一直处于等待资源的状态，也就是说，写进程会被“饿死”。因此这种算法不算是完美的，是一种优先服务读进程的算法。

1.5 进一步改进算法——写者程序加入计数器实现写者优先

在1.3中，单独在读进程中加入带检测的count变量，虽然解决了一部分问题，但也带来了新的问题。所以我们现在试着将count计数器变量加在写者进程。需要特别注意的是，要同时满足引言中读-读同步访问的要求的话，我们就不能像在1.3中，将count单独加入到写进程中。因此，我们要在1.3的基础上，在写进程这边添加带if检测的count变量。

count在写进程中也是起到统计其进程数量的作用，当写进程的数量满足条件的时候，我们能让其主动的做一定的操作，而不是被动的将资源让给一直涌入的读进程。以下变量初值与1.3相似，读进程算法与1.3相同，在此不再赘述。实现如下：

在这里，读写进程的count变量起到了类似的作用，下面以实例验证之。

假如此时有三个程序：读进程A，写进程B，读进程C依次进入队列。我们假设读进程A此时已经进入临界区，正在读取数据，那该进程一定经过了P(mutex2)，P(mutex1)，P(mutex)，P(rw)，V(mutex)，V(mutex1)，V(mutex2) 这些操作。此时如果写进程B也想访问临界区资源，由于此时写进程B是第一个到达的该类进程，能通过if的检测，将会占用信号量mutex1。但是由于读进程还在临界区，并没有释放信号量rw，所以写进程会被阻塞。在此同时，新加入的读进程C，一定会经过P(mutex2),但是由于写进程没有释放mutex1，所以读进程C也会被阻塞。只有当读进程A释放掉信号量P(rw)的时候，才会将写进程B唤醒，进行写操作。写进程B完成操作后，会再次检测后面是否还有写进程，如果没有，才会释放掉信号量mutex1。后面的读进程才有机会进行临界区。

1.6 写者优先存在的问题

显然，这种算法是一种写者优先的算法。只要存在写进程，就会阻塞后来的读进程。同时假如存在多个读写程序，系统也会优先唤醒写进程。

2 另一种公平的读者写者算法

上面的所有算法，在实现需求的同时，都有所偏袒，面对极端情况下会出现问题。所以我们决定按照进程到达的先后顺序，进行算法的实现，以下算法变量初值与前篇类似。此算法部分内容与1.3有重复之处，同时由于篇幅有限，因此在此简单描述增加的信号量：在1.3的写进程基础上，首尾增加信号量w；在1.3读进程的第一个信号量mutex前后增加信号量w。

下面是该算法的分析。

在1.3中，我们发现只要有读进程存在，信号量rw的使用权就会一直在读进程手中，这种情况在加入信号量w后发生了改变：我们发现，即使是后进来的写进程，也能通过抢占信号量w来保证自己不被“饿死”，且进程之间的执行顺序完全是按照抢占w的顺序，即进入队列的先后顺序。同时此算法也满足引言中的其他需求，类似于是一种“先来先服务”的算法，不会造成读/写进程的“饥饿”，也能提高系统的效率。