读者写者优先问题

发表于

参阅博客: 輝夜の永遠亭

读者优先：

1
2
3
semaphore read_cnt_mutex = 1;   //对临界区int readcount进行互斥
semaphore fmutex = 1;           //对读者--写者，写者--写者进行互斥。（双重作用）
int read_cnt = 0;

READER:

1
2
3
4
5
6
7
8
9
10
11
P(read_cnt_mutex);              //获取对read_cnt的互斥锁
if(read_cnt == 0)	P(fmutex);  //注意这条语句必须放在P(read_cnt_mutex)中，因为if语句和P语句之间不是原子的！！必须要防止其他的读者进程对read_cnt进行修改！！
read_cnt ++;
V(read_cnt_mutex);
read();
P(read_cnt_mutex);
read_cnt --;
if(read_cnt == 0)	V(fmutex);  //同上。因为if和V之间不是原子的，必须防止其他读者进行修改。  且，注意每次到0的时候释放fmutex，让写者可以进入。
V(read_cnt_mutex);

WRITER:

1
2
3
4
5
P(fmutex);    //只要拿到fmutex互斥锁，就可以进行“写”操作了。
write();
V(fmutex);

从上边我们可以看出：如果在writer正在等待fmutex的时候，这时一定是已经有多个读者在读取。倘若读者不断地到来，那么writer必然一直处于饥饿的状态。

因此，这种情况下，我们必须想一个措施，让写者的优先级提高。也就是，让写者在“到来”的时候，就要让不断到来的读者停止，让正在读的读者们全部读完之后，写者就开始写。

换句话说，就是要“当写者到的时候，屏蔽源源不断新来的读者，等待已有的读者读完，然后自己进去写”。

因此，輝夜の永遠亭提供了一个思路，就是使用一个queue变量，来限制源源不断的后来读者。

在计算机网络中，我们都知道各种“层”。大体思想无非是，如果有问题解决不了，就加一层；如果还解决不了，就加两层。

这里用了同样的思想。不过用“门”来比喻更好。就是写者在fmutex这个互斥的“门”外边又套了一层门进行把关，一旦写者到来，他就把外边这层门(semaphore queue)封死，因此源源不断的后来读者就全部封死在外边了。接下来就是写者在门里等着，等屋子(fmutex)里的已有的所有读者都读完，然后自己进去写。

思想很简单吧！我们来实现一下。

公平竞争

1
2
3
4
semaphore read_cnt_mutex = 1;
semaphore fmutex = 1;
semaphore queue = 1;
int read_cnt = 0;

READER:

1
2
3
4
5
6
7
8
9
10
11
12
13
P(queue);      //套上了一个“门”，READER必须得经过这个”门“，才能进”屋”读取。
P(read_cnt_mutex);
if(read_cnt == 0)	P(fmutex);
read_cnt ++;
V(read_cnt_mutex);
V(queue);      //过门了，就释放～
read();
P(read_cnt_mutex);
read_cnt --;
if(read_cnt == 0)	V(fmutex);
V(read_cnt_mutex);

WRITER:

1
2
3
4
5
6
7
P(queue);      //套上了一个“门”。
P(fmutex);
V(queue);      //注意放到这里才是符合语义的！	进门之后如果进了屋，就把门开放了。如果没进屋，就在门前守着，不让其他人进来。
write();
V(fmutex);

哈哈哈。其实我想写成“写者优先”的。结果写完了之后发现时公平竞争TAT。遂把标题从“写者优先”变成了“公平竞争”。

这里我们看到，每个读者和写者都要过门，没过门就不能进。这显然是非常公平的呀！一次只有一个可以进门，这不是公平的是什么？

想要对写者偏心的话，就要改成：只对第一个写者需要过门，然后只要有这第一个写者在这里把关，那么后来源源不断的写者也可以涌入。只不过给后边的写者开小灶，直接免费过门，不需要等了。

回想第一个读者优先也是这样，只要第一个读者进了屋，那么接下来到来的读者不用参与竞争就可以免费进屋了。这里的写者也一样，只要第一个写者进了门，那么接下来到来的写者就可以不用竞争也可以免费过门了。

看下实现：

写者优先

1
2
3
4
5
6
semaphore read_cnt_mutex = 1;
semaphore write_cnt_mutex = 1;
semaphore fmutex = 1;
semaphore queue = 1;
int read_cnt = 0;
int write_cnt = 0;

READER:

1
2
3
4
5
6
7
8
9
10
11
12
13
P(queue);
P(read_cnt_mutex);
if(read_cnt == 0)	P(fmutex);
read_cnt ++;
V(read_cnt_mutex);
V(queue);
read();
P(read_cnt_mutex);
read_cnt --;
if(read_cnt == 0)	V(fmutex);
V(read_cnt_mutex);

WRITER:

1
2
3
4
5
6
7
8
9
10
11
12
13
P(write_cnt_mutex);
if(write_cnt == 0)	P(queue);     //你懂的。因为if不是原子，因此前边必须有互斥量～ 这个互斥量还对write_cnt进行了写互斥～ 双重作用。
write_cnt ++;
P(fmutex);      //等着屋里的原有读者读完
V(write_cnt_mutex);
write();
P(write_cnt_mutex);
write_cnt --;
if(write_cnt == 0)	V(queue);
V(fmutex);      //释放锁，如果write_cnt!=0还有写者，因为queue没释放，因此源源不断的读者过不了门，因而fmutex肯定花落别的writer家。如果是0，那么之前一句queue就被释放了。这样的话，就是读者和写者竞争咯，这里会公平地争夺过门的机会。但是如果writer抢到了门，那么之后的过程就对reader不公平了。
V(write_cnt_mutex);

就完成啦～～