操作系统基础16-读者写者问题
2020-11-12 00:56·重学IT的老猫
进程同步问题是一个非常重要且相当有趣的问题，本篇我们对其中比较有名的读者-写者问题来进行学习。
读者-写者
问题描述
假设一个数据库为多个并发进程所共享。有的进程可能只需要读数据库，而另一些进程可能更新(即读和写)数据库。为了区分这两种类型的进程，我们称前者为读者(Reader)，称后者为写者(Writer)。显然，如果多个读者同时访问共享数据，而不会产生副作用。但如果某个写者和其他进程**(或读者或写者)**同时访问数据库时可能导致数据不一致的错误。
为了确保不会出现数据不一致的问题，要求写者在写入数据库时具有共享数据库独占的访问权限。这一同步问题称为读者-写者问题(reader-writer problem)。
所以读者-写者问题要求：
- 允许多个读者同时执行读操作；
- 不允许多个写者同时操作；
- 不允许读者、写者同时操作。
解决策略
读者-写者问题要解决： 读、读共享；写、写互斥；写、读互斥。
写者是比较简单的，它与任何线程互斥，用互斥信号量的 P操作、V 操作即可解决。
读者的问题比较复杂，它必须实现与写者的互斥，多个读者还可以同时读。仅仅简单的一对P操作、V操作是无法解决的。
可以有三种策略：读者优先、写者优先、读写公平。
读者优先
读进程只要看到有其他读进程正在访问文件，就可以继续作读访问；写进程必须等待所有读进程都不访问时才能写文件，即使写进程可能比一些读进程更早提出申请。可以使用一个计数器read_count记录读者总数目（包含等待和正在读的数目），如果read_count > 0 则写者等待，而读者直接读。当read_count = 0 写者与写者、写者与第一个读者抢占读写操作，这可以用一个二元信号量rw_mutex进行互斥访问。因为多个读者线程都要访问计数器，则使用一个二元信号量mutex进行互斥访问。
需要用到的共享变量：
int read_count = 0; // 系统当前读者进程数量
semaphore rw_mutex = 1; // 读者与写者互斥访问共享数据的互斥信号量
semaphore mutex = 1; // 多个读者进程互斥修改当前读者进程数量的信号量
写者进程结构
do {
P(rw_mutex);
...
/* 修改共享数据 */
...
V(rw_mutex);
}while(true);
读者进程结构
do {
P(mutex); //获取修改读者进程数量的互斥信号量，该操作在请求rw_mutex之前，防止出现死锁
read_count++;
if(read_count == 1) //判断当前是否为第一个读者进程
P(rw_mutex); //如果是就需要请求访问共享数据的互斥信号量
V(mutex); //read_count修改后 释放信号量
...
/* 读取数据 */
...
P(mutex); //获取修改读者进程数量的互斥信号量
read_count--;
if(read_count == 0) //判断当前进程是否为最后一个读者进程
V(rw_mutex); //如果是则释放共享数据的互斥信号量，以允许写者进程操作共享数据
V(mutex);
}while(true);
读者优先有可能导致写者进程产生饥饿现象，当系统中不断出现读者进程时，写者进程始终无法进入临界区。
写者优先
需要用到的共享变量：
int read_count = 0; // 系统当前读者进程数量
int write_count = 0; // 系统当前写者进程数量
semaphore rw_mutex = 1; // 读者与写者互斥访问共享数据的互斥信号量
semaphore r_mutex = 1; // 互斥修改当前读取文件的进程数
semaphore w_mutex = 1; // 互斥修改当前修改文件的进程数
semaphore enter_mutex = 1; // 获取申请访问文件的权限
写者进程结构
do {
P(w_mutex); //P操作 新的写者进程进入，上锁进行写者计数更新
write_count++; //更新写者计数器
if(write_count == 1) // 判断当前是否为第一个写者进程
P(enter_mutex); //P操作 则抢enter_mutex的锁,阻断后续到达的读者进程
V(w_mutex); //V操作
P(rw_mutex); //获取访问文件的权限，文件可能被其它写者进程占用，或者等待最后一个读者进程释放
...
/* 修改数据 */
...
V(rw_mutex);
P(w_mutex);
write_count--;
if(write_count == 0) // 当所有写者进程都放弃使用文件时，运行读者进程申请访问文件
V(enter_mutex);
V(w_mutex);
}while(true);
读者进程结构
do {
P(enter_mutex); // 获取申请访问文件的权限
P(r_mutex); //上锁进行读者计数更新
read_count++; //更新读者计数器
if(read_count == 1) // 判断当前是否为第一个读者进程
P(rw_mutex); // 占用文件
V(r_mutex);
V(enter_mutex); //
...
/* 读取数据 */
...
P(r_mutex);
read_count--;
if(read_count == 0)
P(rw_mutex); // 释放文件
P(r_mutex);
}while(true);
写者优先有可能导致读者进程产生饥饿现象，当系统中不断出现写者进程时，读者进程始终无法进入临界区。
读写公平
需要用到的共享变量：
int read_count = 0; // 系统当前读者进程数量
semaphore rw_mutex = 1; // 读者与写者互斥访问共享数据的互斥信号量
semaphore r_mutex = 1; // 互斥修改当前读取文件的进程数
semaphore enter_mutex = 1; // 获取申请访问文件的权限
写者进程结构
do {
P(enter_mutex); // 阻断后续到达的读者进程
P(rw_mutex);
...
/* 修改数据 */
...
V(rw_mutex);
V(enter_mutex);
}while(true);
读者进程结构
do {
P(enter_mutex); // 获取申请访问的权限，这里与写者优先的区别在于，写者放弃占用文件时，所有读者 都可以与写者进程进行再次竞争
P(r_mutex);
read_count++;
if(read_count == 1) // 判断当前是否为第一个读者进程
P(rw_mutex);
signal(r_mutex);
signal(enter_mutex); // 释放许可，其余读者和写者进程将进行下一轮竞争
...
/* 读取数据 */
...
wait(r_mutex);
read_count--;
if(read_count == 0)
signal(rw_mutex);
signal(r_mutex);
}while(true);
上面的代码的 读者进程结构其实和第二个写者优先的 读者进程结构 是一样的，不一样的是写者进程结构。写者进程变成在每次写操作前都要等待 enter_mutex信号量。这里的P(enter_mutex) P操作并不会出现写者优先，而是按照先进先出的顺序让读者写者使用资源。