algorithm - Reader-Writer 的第二种算法解决方案

Question

我很难理解读者-作者问题的第二种算法。我理解一般概念，即作者将优先于读者(读者可能会饿死)。我什至理解这个算法的条件变量实现Reader/Writer Locks in 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)有什么用。一个信号量不够读数吗？

Answer 1

mutex 1保护 readcount多变的; mutext 2保护 writecount多变的;互斥 r保护读取操作和互斥 w保护写操作。

1) 假设一位作家进来了:

信号 mutex 2并递增 writercount考虑额外的作者(本身)因为它是唯一可以改变 writercount 的进程(因为它持有 mutex 2 )，它可以安全地测试它是否是唯一的写入者( writercount==1 )，如果为真，它会发出互斥信号 r为了保护读者不进来——其他作者(writercount > 1)可以享受互斥锁r已经发出信号。

编写器然后发出互斥量信号 w以保护其更改不受其他(并发)作者的影响。

最后一个作者 ( writecount==1 ) 释放互斥体 r让读者执行他们的任务。

2) 假设一位读者进来了:

信号 mutex 3保护读者的设置逻辑不受其他读者的影响；然后信号互斥 r防止其他作者(记住，r 在作者操作时发出信号)；然后发出信号 mutex 1保护 readcount(来自可能正在退出的其他读者)，如果它是第一个读者( readercount == 1 )，信号互斥 w以防止写入者(现在排除写入者执行他们的操作)。

读取可以并行进行，因此在读取时不需要其他读取器的保护(记住，此时正在持有互斥锁 w，因此不会受到写入器的干扰)

然后最后一个读取器重置写互斥锁 ( w ) 以允许写入器。

---

防止写者饥饿的技巧是写者冒充读者(当发出互斥信号 p 时)，因此即使有很多读者也有很好的机会被安排。另外，mutex 3防止太多读者等待互斥体 r , 所以作家有很好的机会发出信号 r当他们来的时候。