写者优先的读者-写者问题

Question

问题

在书 "Little Book of Semaphores" 中，第 1 页。 71、存在以下问题:

Write a solution to the readers-writers problem that gives priority to writers. That is, once a writer arrives, no readers should be allowed to enter until all writers have left the system.

我找到了一个解决方案，但它与书中给出的有点不同。

我的解决方案

共享变量:

readSwitch = Lightswitch()
writeSwitch = Lightswitch()
noWriters = Semaphore(1)
noReaders = Semaphore(1)

Semaphore(1)表示初始化为1的信号量，Lightswitch在书上是这样定义的：

class Lightswitch:
  def __init__(self):
    self.counter = 0
    self.mutex = Semaphore(1)

  def lock(self, semaphore):
    self.mutex.wait()
    self.counter += 1
    if self.counter == 1:
      semaphore.wait()
    self.mutex.signal()

  def unlock(self, semaphore):
    self.mutex.wait()
    self.counter -= 1
    if self.counter == 0:
      semaphore.signal()
    self.mutex.signal()

Reader 逻辑:

noReaders.wait()
noReaders.signal()

readSwitch.lock(noWriters)

# critical section for readers

readSwitch.unlock(noWriters)

编写器逻辑:

writeSwitch.lock(noReaders)
noWriters.wait()

# critical section for writers

writeSwitch.unlock(noReaders)
noWriters.signal()

书中的解法

共享变量:

readSwitch = Lightswitch()
writeSwitch = Lightswitch()
noWriters = Semaphore(1)
noReaders = Semaphore(1)

Reader 逻辑:

noReaders.wait()
readSwitch.lock(noWriters)
noReaders.signal()

# critical section for readers

readSwitch.unlock(noWriters)

编写器逻辑:

writeSwitch.lock(noReaders)
noWriters.wait()

# critical section for writers

noWriters.signal()
writeSwitch.unlock(noReaders)

问题

1) 在 reader 逻辑中，在我的解决方案中，noReaders.signal() 紧跟在 noReaders.wait() 之后。这里的想法是 noReaders 就像一种旋转门，允许 reader 通过它，但一到达就被作者锁定。

然而，在本书的解决方案中，noReaders.signal()是在调用readSwitch.lock(noWriters)之后完成的。

为什么我的订单会产生不正确的行为？

2) 在编写器逻辑中，在我的解决方案中，writeSwitch.unlock(noReaders) 出现在 noWriters.signal() 之前。然而，本书将它们的顺序颠倒过来。我的订单会产生错误行为有什么原因吗？

编辑：附加问题

我还有一个问题。我可能对本书的解决方案有一些误解。假设发生以下情况：

Reader1获取noReaders（noReaders变为0）
Reader 在noReaders等待2次（noReaders变为-1）
Writer 1 在noReaders等待（noReaders变成-2）
Reader 在noReaders等待3次（noReaders变成-3）
Reader 在noReaders等待4次（noReaders变为-4）
Reader1获取noWriters（noWriters变为0）
Reader 1 个信号 noReaders（noReaders 变成 -3；Reader 2 个被解锁）
Reader 2通过noWriters电灯开关；发出信号 noReaders（noReaders 变为 -2， Reader 3 被解锁)

在上面的情况下，似乎额外的 reader 可以不断到达并进入临界区，尽管一个 writer 正在等待。

此外，考虑到 reader 和 writer 正在循环，完成临界区的 reader 可以循环并再次等待 noReaders，即使已经有 writer 在等待.

我误会了什么？

Answer 1

使用您的解决方案，可能会出现以下情况：

在 writeSwitch.unlock(noReaders) 之后 noWriters.signal()
新作者执行writeSwitch.lock(noReaders)
A reader 执行 readSwitch.lock(noWriters)，即使有写入器也会进入临界区。

本书的解决方案在唤醒 reader 之前先唤醒等待中的作者。您的解决方案首先唤醒 readers，并且还允许 readers 在 readSwitch.lock(noWriters) 排队，这样他们就可以运行即使有作家在等待。

写者优先的读者-写者问题

Readers-writers problem with writer priority

concurrency

semaphore

问题

我的解决方案

书中的解法

问题

编辑：附加问题