操作系统基础16-读者写者问题

操作系统基础16-读者写者问题

2020-11-12 00:56·重学IT的老猫

进程同步问题是一个非常重要且相当有趣的问题,本篇我们对其中比较有名的读者-写者问题来进行学习。

操作系统基础16-读者写者问题

读者-写者

问题描述

假设一个数据库为多个并发进程所共享。有的进程可能只需要读数据库,而另一些进程可能更新(即)数据库。为了区分这两种类型的进程,我们称前者为读者(Reader),称后者为写者(Writer)。显然,如果多个读者同时访问共享数据,而不会产生副作用。但如果某个写者和其他进程(或读者或写者)同时访问数据库时可能导致数据不一致的错误。

为了确保不会出现数据不一致的问题,要求写者在写入数据库时具有共享数据库独占的访问权限。这一同步问题称为读者-写者问题(reader-writer problem)。

所以读者-写者问题要求:

  1. 允许多个读者同时执行读操作;
  2. 不允许多个写者同时操作;
  3. 不允许读者、写者同时操作。

解决策略

读者-写者问题要解决: 读、读共享;写、写互斥;写、读互斥。

写者是比较简单的,它与任何线程互斥,用互斥信号量P操作、V 操作即可解决。

读者的问题比较复杂,它必须实现与写者的互斥,多个读者还可以同时读。仅仅简单的一对P操作、V操作是无法解决的。

可以有三种策略:读者优先写者优先读写公平

读者优先

读进程只要看到有其他读进程正在访问文件,就可以继续作读访问;写进程必须等待所有读进程都不访问时才能写文件,即使写进程可能比一些读进程更早提出申请。可以使用一个计数器read_count记录读者总数目(包含等待和正在读的数目),如果read_count > 0 则写者等待,而读者直接读。当read_count = 0 写者与写者、写者与第一个读者抢占读写操作,这可以用一个二元信号量rw_mutex进行互斥访问。因为多个读者线程都要访问计数器,则使用一个二元信号量mutex进行互斥访问。

需要用到的共享变量:

1
2
3
int read_count = 0; // 系统当前读者进程数量
semaphore rw_mutex = 1; // 读者与写者互斥访问共享数据的互斥信号量
semaphore mutex = 1; // 多个读者进程互斥修改当前读者进程数量的信号量

写者进程结构

1
2
3
4
5
6
7
do {
P(rw_mutex);
...
/* 修改共享数据 */
...
V(rw_mutex);
}while(true);

读者进程结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);

读者优先有可能导致写者进程产生饥饿现象,当系统中不断出现读者进程时,写者进程始终无法进入临界区。

写者优先

需要用到的共享变量:

1
2
3
4
5
6
int read_count = 0;         // 系统当前读者进程数量
int write_count = 0; // 系统当前写者进程数量
semaphore rw_mutex = 1; // 读者与写者互斥访问共享数据的互斥信号量
semaphore r_mutex = 1; // 互斥修改当前读取文件的进程数
semaphore w_mutex = 1; // 互斥修改当前修改文件的进程数
semaphore enter_mutex = 1; // 获取申请访问文件的权限

写者进程结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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);

读者进程结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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);

写者优先有可能导致读者进程产生饥饿现象,当系统中不断出现写者进程时,读者进程始终无法进入临界区。

读写公平

需要用到的共享变量:

1
2
3
4
int read_count = 0;         // 系统当前读者进程数量
semaphore rw_mutex = 1; // 读者与写者互斥访问共享数据的互斥信号量
semaphore r_mutex = 1; // 互斥修改当前读取文件的进程数
semaphore enter_mutex = 1; // 获取申请访问文件的权限

写者进程结构

1
2
3
4
5
6
7
8
9
do { 
P(enter_mutex); // 阻断后续到达的读者进程
P(rw_mutex);
...
/* 修改数据 */
...
V(rw_mutex);
V(enter_mutex);
}while(true);

读者进程结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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操作并不会出现写者优先,而是按照先进先出的顺序让读者写者使用资源。

-------------本文结束 感谢阅读-------------