读者 - 作者的第二种算法解决方案

Question

我很难理解读者 - 写作者问题的第二种算法.我理解一般的概念,作家将优先于读者(读者可能会饿死).我甚至理解这个算法的读/写器锁在C++中的条件变量实现.但是,信号量和互斥量的实现对我来说毫无意义.这是维基百科的一个例子:

int readcount, writecount; (initial value = 0)
semaphore mutex 1, mutex 2, mutex 3, w, r ; (initial value = 1)

READER
  P(mutex 3);
    P(r);
      P(mutex 1);
        readcount := readcount + 1;
        if readcount = 1 then P(w);
      V(mutex 1);
    V(r);
  V(mutex 3);

  reading is done

  P(mutex 1);
    readcount := readcount - 1;
    if readcount = 0 then V(w);
  V(mutex 1);


WRITER
    P(mutex 2);
      writecount := writecount + 1;
      if writecount = 1 then P(r);
    V(mutex 2);

  P(w);
    writing is performed
  V(w);

  P(mutex 2);
    writecount := writecount - 1;
    if writecount = 0 then V(r);
  V(mutex 2);

[http://en.wikipedia.org/wiki/Readers-writers_problem][2]

我不明白读卡器锁中的三个信号量(互斥锁3,r和互斥锁1)是什么.对于readcount,不是一个信号量足够吗？

Answer 1

mutex 1保护readcount变量; mutext 2保护writecount变量; mutex r保护读取操作,而mutext w保护写入操作.

1)让我们假设一位作家进来:

信号mutex 2和增量writercount来解释额外的编写器(本身)由于它是唯一可以改变的过程writercount(因为它正在保持mutex 2),它可以安全地测试它是否是唯一的writer(writercount==1),如果是真的,它会发出互斥信号r来保护读者从进来 - 其他作家(writercount > 1)可以享受r已经发出信号的互斥锁.

然后,编写者发出互斥信号,w以保护其更改免受其他(并发)编写者的影响.

最后一个writer(writecount==1)发布了互斥r,让读者执行他们的任务.

2)让我们假设读者进来:

信号mutex 3保护读者的设置逻辑免受其他读者的影响; 然后发信号通知互斥锁r以保护其他编写者(记住,r当编写器正在运行时发出信号); 然后发出信号mutex 1以保护读取数据(来自其他可能正在退出的读取器),如果它是第一个读取器(readercount == 1),则发出互斥信号w以防止编写者(现在不允许编写者执行其操作).

阅读可以并行完成,因此在阅读时不需要其他读者的保护(记住,此时w正在进行互斥,所以没有来自作者的干扰)

然后最后一个读取器重置write mutex(w)以允许编写器.

阻止作家饥饿的伎俩是作者构成读者(当发信号通知互斥p)时,即使有很多读者,也很有可能获得安排.此外,mutex 3防止太多读者等待互斥r,因此编写者很有可能r在他们来时发出信号.

Answer 2

查看PJ Courtois、F. Heymans 和 DL Parnas 编写的Concurrent Control with "Readers" and "Writers"，这是 Wikipedia 上的代码参考。它解释了为什么需要所有互斥体。