在本章中，我们将讨论并发编程中饥饿的概念及其潜在原因。我们将讨论一些读者-作者问题，它们是饥饿的主要例子，我们将在示例 Python 代码中模拟它们。本章还将介绍死锁和饥饿之间的关系，以及饥饿的一些潜在解决方案。
本章将介绍以下主题：
- 饥饿背后的基本理念，其根源，以及一些更相关的概念
- 对读写器问题的详细分析，用于说明并发系统中饥饿的复杂性
以下是本章的先决条件列表：
- 确保计算机上安装了 Python 3
- 在下载 GitHub 存储库 https://github.com/PacktPublishing/Mastering-Concurrency-in-Python
- 在本章中，我们将使用名为
Chapter13的子文件夹 - 查看以下视频以查看代码的运行：http://bit.ly/2r3caw8
饥饿是并发系统中的一个问题，在并发系统中，进程（或线程）无法访问必要的资源以继续执行，因此无法取得任何进展。在这一节中，我们将研究饥饿状况的特征，分析饥饿的最常见原因，最后，考虑一个例证饥饿的例子。
并发程序在其执行过程中在不同进程之间实现某种排序是很常见的。例如，考虑一个具有三个独立过程的程序，如下：
- 其中一个负责处理非常紧迫的指令，这些指令需要在必要的资源可用时立即运行
- 另一个进程负责其他重要的执行，这些执行不像第一个进程中的任务那样重要
- 最后一个处理繁杂的、非常不频繁的任务
此外，这三个进程需要利用相同的资源来执行各自的指令。
直观地说，我们完全有理由实现一个规范，该规范允许第一个进程具有最高的执行优先级和对资源的访问权限，然后是第二个进程，最后一个进程具有最低的优先级。但是，想象一下这样的情况：前两个进程（优先级更高）经常运行，以至于第三个进程无法执行其指令；每当第三个进程需要运行时，它都会检查资源是否可用，并发现另一个优先级较高的进程正在使用它们。
这是一种饥饿的情况：第三个过程没有机会执行，因此，该过程无法取得进展。在一个典型的并发程序中，有三个以上具有不同优先级的进程是很常见的，但情况基本上是相似的：一些进程被赋予了更多的运行机会，因此，它们不断地执行。其他人的优先级较低，无法获得执行所需的资源。
在接下来的几个小节中，我们将讨论导致饥饿状况的潜在候选因素。大多数情况下，调度指令的协调性差是导致饥饿的主要原因。例如，处理三个独立任务的相当简单的算法可能会在前两个任务之间实现持续的通信和交互。
这种设置导致算法的执行流仅在第一个和第二个任务之间切换，而第三个任务发现自己处于空闲状态，无法在执行过程中取得任何进展；在这种情况下，因为它缺少 CPU 执行流。直观地说，我们可以确定问题的根源是算法允许前两个任务始终控制 CPU，因此，有效地防止任何其他任务也使用 CPU。一个好的调度算法的一个特点是能够分配执行流，并平等适当地分配资源。
如前所述，许多并发系统和程序在进程和线程执行方面实现特定的优先级顺序。这种有序调度的实现很可能导致优先级较低的进程和线程不足，并可能导致称为优先级反转的情况。
假设在并发程序中，进程 A 具有最高优先级，进程 B 具有中等优先级，最后是进程 C 具有最低优先级；过程 C 很可能处于饥饿状态。此外，如果进程 A（优先级化进程）的执行依赖于进程 C 的完成，而进程 C 已经处于饥饿状态，那么进程 A 也可能永远无法完成其执行，即使它在并发程序中被赋予了最高优先级。
下图进一步说明了优先级反转的概念：从t2到t3运行的高优先级任务需要访问一些资源，这些资源正被低优先级任务使用：
Diagram of priority inversion
重申一下，饥饿和优先级反转相结合可能导致即使是高优先级任务也无法执行其指令的情况。
考虑到设计调度算法的复杂性，让我们讨论饥饿的具体原因。我们在上一节中描述的情况表明了饥饿状况的一些潜在原因。然而，饥饿可能来自以下几个方面：
-
具有高优先级的进程（或线程）控制着 CPU 中的执行流，因此，低优先级的进程（或线程）没有机会执行它们自己的指令。
-
高优先级的进程（或线程）支配着不可共享资源的使用，因此，低优先级的进程（或线程）没有机会执行它们自己的指令。这种情况与第一种情况类似，但它涉及访问资源的优先级，而不是执行本身的优先级。
-
具有低优先级的进程（或线程）正在等待资源执行其指令，但是，一旦资源可用，具有较高优先级的其他进程（或线程）将立即被授予访问它们的权限，因此低优先级的进程（或线程）将无限期地等待。
饥饿还有其他原因，但以上是最常见的根本原因。
有趣的是，死锁情况也可能导致饥饿，因为饥饿的定义指出，如果某个进程（或线程）由于无法访问必要的进程而无法取得任何进展，则该进程（或线程）正在经历饥饿。
回想一下我们的死锁示例，即哲学家进餐问题，如下所示：
An illustration of the Dining Philosophers problem
在这种情况下出现死锁时，任何哲学家都无法获得执行其指令所需的资源（每个哲学家必须有两个叉子才能开始进食）。因此，每个陷入死锁的哲学家也都处于饥饿状态。
读者-作者问题是计算机科学领域中最经典、最复杂的例子之一，它说明了并发程序中可能出现的问题。通过对读者和作者问题的不同变体的分析，我们将揭示更多关于饥饿的信息，以及饥饿的常见原因。我们还将用 Python 模拟这个问题，以便对这个问题有更深入的理解。
在读者-作者问题中，首先，我们有一个共享资源，在大多数情况下，它是一个文本文件。不同的线程与该文本文件交互；每个人要么是读者，要么是作者。读取器是一个线程，它只访问共享资源（文本文件）并读取该文件中包含的数据，而写入器是一个线程，它访问并可能变异文本文件的内容。
我们知道，写入程序和读取器不能同时访问共享资源，因为如果一个线程正在向文件写入数据，那么不应该有其他线程访问该文件以从中读取任何数据。因此，读写器问题的目标是找到一种正确有效的方法来设计和协调这些读写器线程的调度。这一目标的成功实现不仅在于程序作为一个整体以最优化的方式执行，而且还在于所有线程都有足够的机会执行它们的指令，并且不会发生饥饿。此外，需要适当地处理共享资源（文本文件），以便不会损坏任何数据。
下图进一步说明了读写器问题的设置：
Diagram of readers-writers problem
正如我们所提到的，这个问题要求我们提出一个调度算法，以便读者和作者能够适当而有效地访问文本文件，而不会错误处理/破坏所包含的数据。解决这个问题的一个简单方法是对文本文件加锁，使其成为不可共享的资源；这意味着在任何给定时间只有一个线程（读写器）可以访问（并可能操纵）文本文件。
然而，这种方法仅仅等同于顺序程序：如果共享资源在给定时间只能由一个线程使用，则不同线程之间的处理时间不能重叠，并且有效地，执行变得顺序。因此，这不是最佳解决方案，因为它利用了并发编程。
关于读卡器线程的一个见解可以为这个问题提供一个更优化的解决方案：因为读卡器只是读取文本文件而不改变其中的数据，所以可以允许多个读卡器同时访问文本文件。事实上，即使多个读卡器同时从文本文件获取数据，数据也不会以任何方式发生更改，因此数据的一致性和准确性得以保持。
按照这种方法，我们将实现一个规范，在该规范中，如果共享资源正在被另一个读卡器打开以供读取，则没有读卡器会一直等待。具体来说，除了锁定共享资源外，我们还将有一个计数器，用于计算当前访问资源的读卡器数量。如果在程序中的任何一点，计数器从零变为一（换句话说，至少有一个读卡器开始访问资源），我们将从写卡器锁定资源；类似地，每当计数器减少到零（换句话说，没有读卡器请求访问资源），我们将释放资源上的锁，以便写卡器可以访问它。
该规范对于读卡器来说是有效的，因为一旦第一个读卡器访问了资源并对其进行了锁定，就没有编写器可以访问它，后续的读卡器将不必重新锁定它，直到最后一个读卡器读取完资源。
让我们尝试用 Python 实现这个解决方案。如果您已经从 GitHub 页面下载了本书的代码，请继续并导航到Chapter13文件夹。让我们看看Chapter13/example1.py文件；具体而言，writer()和reader()功能如下：
# Chapter13/example1.py
def writer():
global text
while True:
with resource:
print(f'Writing being done by
{threading.current_thread().name}.')
text += f'Writing was done by
{threading.current_thread().name}. '
def reader():
global rcount
while True:
with rcounter:
rcount += 1
if rcount == 1:
resource.acquire()
print(f'Reading being done by
{threading.current_thread().name}:')
print(text)
with rcounter:
rcount -= 1
if rcount == 0:
resource.release()在前面的脚本中，writer()函数将由threading.Thread实例（换句话说，一个单独的线程）调用，它指定了我们前面讨论过的编写器线程的逻辑：访问共享资源（在本例中，全局变量text，它只是一个 Python 字符串）并将一些数据写入资源。请注意，我们将其所有指令放在一个while循环中，以模拟应用的恒定性质（编写器和读取器不断尝试访问共享资源）。
我们还可以在reader()函数中看到读卡器逻辑。在请求访问共享资源之前，每个读卡器将为当前活动并试图访问资源的读卡器数量增加一个计数器。类似地，从文件中读取数据后，每个读卡器都需要减少读卡器的数量。在此过程中，如果读卡器是第一个访问该文件的读卡器（换句话说，当计数器为 1 时），它将锁定该文件，这样就没有写入者可以访问该文件；相反，当读卡器是最后一个读取文件的读卡器时，它必须释放该锁。
关于读卡器计数器的处理，请注意：您可能已经注意到，在递增/递减计数器变量（rcount时，我们使用了一个名为rcounter的锁对象。这是一种用于避免竞争条件的方法，竞争条件是计数器变量的另一个常见并发相关问题；具体来说，如果没有锁，多个线程可以同时访问和更改计数器变量，但确保数据完整性的唯一方法是按顺序处理此计数器变量。我们将在下一章更详细地讨论种族条件（以及避免种族条件的做法）。
回到我们当前的脚本，在主程序中，我们将设置text变量、读卡器计数器和两个锁对象（分别用于读卡器计数器和共享资源）。我们还将初始化并启动三个读线程和两个写线程，如下所示：
# Chapter13/example1.py
text = 'This is some text. '
rcount = 0
rcounter = threading.Lock()
resource = threading.Lock()
threads = [threading.Thread(target=reader) for i in range(3)] + [threading.Thread(target=writer) for i in range(2)]
for thread in threads:
thread.start()需要注意的是，由于读写器线程的指令都封装在while循环中，因此脚本在启动时将无限运行。您应该在大约 3-4 秒后取消 Python 执行，此时已产生足够的输出，以便可以观察程序的一般行为。
以下代码显示了我在运行脚本后获得的前几行输出：
> python3 example1.py
Reading being done by Thread-1:
This is some text.
Reading being done by Thread-2:
Reading being done by Thread-1:
This is some text.
This is some text.
Reading being done by Thread-2:
Reading being done by Thread-1:
This is some text.
This is some text.
Reading being done by Thread-3:
Reading being done by Thread-1:
This is some text.
This is some text.
...如您所见，前面的输出中有一个特定的模式：访问共享资源的所有线程都是读卡器。事实上，在我的整个输出过程中，没有写入程序能够访问该文件，因此，text变量只包含初始字符串This is some text.，并且没有以任何方式进行更改。您获得的输出也应该具有相同的模式（共享资源没有被改变）。
在这种情况下，编写者正经历饥饿，因为他们都无法访问和使用资源。这是我们调度算法的直接结果；由于允许多个读卡器同时访问文本文件，因此如果有多个读卡器访问文本文件的频率足够高，则将创建一个连续的读卡器流来遍历文本文件，使编写器没有空间尝试访问该文件。
这种调度算法无意中将读卡器优先于写卡器，因此被称为读卡器优先。因此，这种设计是不可取的。
第一种方法的问题是，当一个读卡器正在访问文本文件，而一个写卡器正在等待解锁该文件时，如果另一个读卡器开始执行该文件并希望访问该文件，则该读卡器的优先级将高于已在等待的写卡器。此外，如果越来越多的读者不断请求访问该文件，那么编写者将无限期地等待，这就是我们在第一个代码示例中观察到的。
为了解决这个问题，我们将实现一个规范，即一旦写入程序请求访问该文件，就不应该有读卡器能够在该写入程序之前插队访问该文件。为此，我们将在程序中增加一个 lock 对象，用于指定写入程序是否正在等待该文件，以及读取器线程是否可以尝试读取该文件；我们将此锁称为read_try。
类似于第一个访问文本文件的读卡器总是从写入器处锁定文本文件的方式，我们现在将拥有多个等待访问文件锁的写入器中的第一个写入器read_try，因此，没有读卡器可以再次在请求访问文本文件的写入器之前插队。正如我们在《读者参考》中所讨论的，由于我们跟踪等待文本文件的写入程序的数量，因此我们需要在程序中实现一个写入程序数量计数器及其相应的锁。
Chapter13/example2.py文件包含此实现的代码，如下所示：
# Chapter13/example2.py
import threading
def writer():
global text
global wcount
while True:
with wcounter:
wcount += 1
if wcount == 1:
read_try.acquire()
with resource:
print(f'Writing being done by
{threading.current_thread().name}.')
text += f'Writing was done by
{threading.current_thread().name}. '
with wcounter:
wcount -= 1
if wcount == 0:
read_try.release()
def reader():
global rcount
while True:
with read_try:
with rcounter:
rcount += 1
if rcount == 1:
resource.acquire()
print(f'Reading being done by
{threading.current_thread().name}:')
print(text)
with rcounter:
rcount -= 1
if rcount == 0:
resource.release()
text = 'This is some text. '
wcount = 0
rcount = 0
wcounter = threading.Lock()
rcounter = threading.Lock()
resource = threading.Lock()
read_try = threading.Lock()
threads = [threading.Thread(target=reader) for i in range(3)] +
[threading.Thread(target=writer) for i in range(2)]
for thread in threads:
thread.start()与我们对该问题的第一个解决方案相比，主程序保持相对不变（除了初始化read_try锁、wcount计数器及其锁wcounter，但在我们的writer()函数中，只要有至少一个写入程序等待访问该文件，我们就锁定read_try；当最后一个写入程序完成其执行时，它将释放锁，以便等待该文件的任何读取器现在都可以访问该文件。
同样，为了查看程序生成的输出，我们将让它运行 3-4 秒，然后取消执行，否则程序将永远运行。以下是我通过此脚本获得的输出：
> python3 example2.py
Reading being done by Thread-1:
This is some text.
Reading being done by Thread-1:
This is some text.
Writing being done by Thread-4.
Writing being done by Thread-5.
Writing being done by Thread-4.
Writing being done by Thread-4.
Writing being done by Thread-4.
Writing being done by Thread-5.
Writing being done by Thread-4.
...可以观察到，虽然一些读者能够访问文本文件（由我的输出的前四行指示），但一旦作者获得了对共享资源的访问权，就再也没有读者能够访问它了。我的其他输出包括关于编写说明的消息：Writing being done by等等。与我们在读者-作者问题的第一个解决方案中看到的相反，这个解决方案优先考虑作者，因此，读者挨饿。因此，这被称为作者偏好。
写入程序优先于读程序的原因是，虽然只有第一个和最后一个写入程序必须分别获取和释放read_try锁，但每个想要访问文本文件的读程序都必须单独与该锁对象交互。一旦read_try被写入程序锁定，任何阅读器都无法尝试执行其指令，更不用说尝试访问文本文件了。
在某些情况下，如果读卡器在写卡器之前初始化并执行（例如，在我们的程序中，读卡器是线程列表中的前三个元素，写卡器是最后两个元素），则某些读卡器能够访问文本文件。但是，一旦写入程序能够访问该文件并在执行过程中获取read_try锁，读卡器很可能会出现饥饿。
这种解决方案也是不可取的，因为它在我们的程序中为 writer 线程提供了更高的优先级。
您已经看到，我们尝试实现的两种解决方案都可能导致饥饿，因为它们没有为单独的线程提供同等的优先级；一个可以让作家挨饿，另一个可以让读者挨饿。这两种方法之间的平衡可能会使我们的实现在读者和作者之间具有同等的优先级，从而解决饥饿问题。
回想一下：在我们的第二种方法中，我们锁定了读卡器访问文本文件的尝试，要求一旦它开始等待文件，就不会有写卡器被饿死。在这个解决方案中，我们将实现一个锁，该锁也利用这个逻辑，但随后应用于读写器。然后，所有线程都将受到锁的约束，因此在单独的线程之间将实现相同的优先级。
具体来说，这是一个锁，用于指定线程在给定时刻是否有权访问文本文件；我们称之为服务锁。每个编写器或读取器在执行其任何指令之前都必须尝试获取此服务锁。已获得此服务锁的写入程序也将尝试获取资源锁，并在其后立即释放服务锁。然后，编写器将执行其写入逻辑，并最终在执行结束时释放资源锁。
让我们看看Chapter13/example3.py文件中用于 Python 实现的writer()函数，如下所示：
# Chapter13/example3.py
def writer():
global text
while True:
with service:
resource.acquire()
print(f'Writing being done by
{threading.current_thread().name}.')
text += f'Writing was done by
{threading.current_thread().name}. '
resource.release()另一方面，读卡器也需要首先获取服务锁。因为我们仍然允许多个读卡器同时访问资源，所以我们正在实现读卡器计数器及其相应的锁。
读卡器将获取服务锁和计数器锁，增加读卡器计数器（并可能锁定资源），然后依次释放服务锁和计数器锁。现在，它实际上将从文本文件中读取数据，最后，它将减少读卡器计数器，并可能释放资源锁（如果它是当时最后一个访问该文件的读卡器）。
reader()功能包含此规范，如下所示：
# Chapter13/example3.py
def reader():
global rcount
while True:
with service:
rcounter.acquire()
rcount += 1
if rcount == 1:
resource.acquire()
rcounter.release()
print(f'Reading being done by
{threading.current_thread().name}:')
#print(text)
with rcounter:
rcount -= 1
if rcount == 0:
resource.release()最后，在主程序中，我们初始化文本字符串、读取器计数器、所有必要的锁以及读取器和写入器线程，如下所示：
# Chapter13/example3.py
text = 'This is some text. '
rcount = 0
rcounter = threading.Lock()
resource = threading.Lock()
service = threading.Lock()
threads = [threading.Thread(target=reader) for i in range(3)] + [threading.Thread(target=writer) for i in range(2)]
for thread in threads:
thread.start()请注意，我们正在注释在reader()函数中打印文本文件当前内容的代码，以便于稍后输出的可读性。运行程序 3-4 秒，然后取消。以下是我在个人电脑上获得的输出：
> python3 example3.py
Reading being done by Thread-3:
Writing being done by Thread-4.
Reading being done by Thread-1:
Writing being done by Thread-5.
Reading being done by Thread-2:
Reading being done by Thread-3:
Writing being done by Thread-4.
...当前输出的模式是，读者和作者能够协作高效地访问共享资源；所有的读写器都在执行它们的指令，并且没有线程被这种调度算法耗尽。
请注意，当您在并发程序中处理读写器问题时，您不必重新设计我们刚才讨论的方法。PyPI 实际上有一个名为readerwriterlock的外部库，其中包含 Python 中三种方法的实现，以及对超时的支持。导航到https://pypi.org/project/readerwriterlock/ 了解更多关于图书馆及其文档的信息。
通过对读写器问题的不同解决方法的分析，您已经看到了解决饥饿问题的关键：因为如果在访问共享资源时没有给予某些线程高优先级，则它们将饥饿，因此在所有线程的执行中实现公平性将防止饥饿的发生。在这种情况下，公平性并不要求程序放弃它强加给不同线程的任何顺序或优先级；但为了实现公平性，程序需要确保所有线程都有足够的机会执行它们的指令。
记住这一点，我们可以通过实施以下一种（或组合）方法来解决饥饿问题：
- 提高低优先级线程的优先级：正如第二种方法中的写入线程和第三种方法中的读线程一样，对那些本来没有机会访问共享资源的线程进行优先级排序可以成功地消除饥饿。
- 先进先出线程队列：为了确保在另一个线程之前开始等待共享资源的线程能够在另一个线程之前获取资源，我们可以在先进先出队列中跟踪请求访问的线程。
- 其他方法：也可以实现几种方法来平衡不同线程的选择频率。例如，优先级队列也会逐渐增加在队列中等待了很长时间的线程的优先级，或者如果某个线程已经能够多次访问共享资源，则该线程的优先级将降低，依此类推。
在并发程序中解决饥饿问题可能是一个相当复杂和复杂的过程，在这个过程中，需要深入理解其调度算法，并了解进程和线程如何与共享资源交互。正如您在 readers-Writer 问题的示例中所看到的，它还需要对不同的方法进行多次实现和修改，才能找到解决饥饿问题的好方法。
饥饿是并发系统中的一个问题，在并发系统中，进程（或线程）无法访问继续执行所需的资源，因此无法取得任何进展；死锁情况也可能导致饥饿。
读者-作者问题是计算机科学领域中最经典、最复杂的例子之一，它说明了并发程序中可能出现的问题。通过分析解决读者-作者问题的不同方法，您已经了解了如何使用不同的调度算法解决饥饿问题。公平性是良好调度算法的基本要素，通过确保优先级在不同进程和线程之间适当分配，可以消除饥饿。
在下一章中，我们将讨论并发编程的三个常见问题中的最后一个：竞争条件。我们将包括竞争条件、相关概念以及竞赛条件与其他并发相关问题的基本基础和原因。
- 什么是饥饿，为什么它在并发程序中是不受欢迎的？
- 饥饿的根本原因是什么？从根本原因看，饥饿的常见高层次原因是什么？
- 死锁和饥饿之间有什么联系？
- 读者和作者的问题是什么？
- 解决读者-作者问题的第一种方法是什么？为什么在这种情况下会出现饥饿？
- 第二种解决读者-作者问题的方法是什么？为什么在这种情况下会出现饥饿？
- 第三种解决读者-作者问题的方法是什么？为什么它成功地解决了饥饿问题？
- 解决饥饿的一些常见方法是什么？
- Python 并行编程，作者：Jan Palach，Packt Publishing Ltd.2014
- Python 并行编程食谱，作者：Giancarlo Zaccone，Packt 出版有限公司，2015 年
- 饥饿与公平（tutorials.jenkov.com/java-concurrency/饥饿与公平），作者：Jakob jenkov
- 更快、公平地解决读者-作者问题，V.波波夫和 O.马佐卡