操作系统导论 ：Operating Systems: Three Easy Pieces

课后习题：Homework

该章节课后习题README部分翻译（便于以后查看）：

1. 习题介绍

        这个作业让你探索一些使用锁和条件变量来实现本章讨论的生产者/消费者队列的各种形式的真实代码。您将查看实际的代码，在各种配置中运行它，并使用它来了解哪些工作，哪些不工作，以及其他的复杂情况。

代码的不同版本对应着“解决”生产者/消费者问题的不同方法。

第一步是下载代码并键入make以构建所有变体。解压后应该看到四个文件：

• main-one-cv-while.c：用一个条件变量解决了 生产者/消费者问题。
• main-two-cvs-if.c：同上，但有两个条件变量，并使用if检查是否休眠。
• main-two-cvs-while.c：同上，但有两个条件变量和while，用于检查是否睡眠。（正确的版本。
• main-two-cvs-while-extra-unlock.c：同上，但释放锁，然后在填充和获取程序周围重新获取它。

查看pc-header.h也是有用的，它包含所有这些不同的主程序的公共代码，以及Makefile，以便正确地构建代码。

每个程序都有以下标志：

  -l <number of items each producer produces>
  -m <size of the shared producer/consumer buffer>
  -p <number of producers>
  -c <number of consumers>
  -P <sleep string: how producer should sleep at various points>
  -C <sleep string: how consumer should sleep at various points>
  -v [verbose flag: trace what is happening and print it]
  -t [timing flag: time entire execution and print total time]

这里，前四个参数关系是明确的：-l 指定每个生产者应该循环多少次（以及每个生产者产生多少数据项），-m 控制共享缓冲区的大小（大于等于1），-p 和 -c 分别设置有多少生产者和消费者。

        更有趣的是两个睡眠字符串（sleep string），一个用于生产者，一个用于消费者。这些标志允许你让每个线程在执行的某些点休眠，从而切换到其他线程；这样你就可以尝试各种解决方案，也许还能找出具体问题，或者研究生产者/消费者问题的其他方面。

        该字符串如下所示。例如，如果有三个生产者，字符串应该用冒号分隔符分别指定每个生产者的睡眠时间。这三个生产者的睡眠字符串看起来像这样。

sleep_string_for_p0:sleep_string_for_p1:sleep_string_for_p2 

        每个睡眠字符串依次是一个逗号分隔的列表，用于决定在代码中的每个sleep点睡眠多少时间。为了更好地理解每个生产者或每个消费者的睡眠字符串，让我们看看main-two-cvs-while.c中的代码，特别是生产者代码。在这个代码片段中，生产者线程会循环一段时间，通过调用\_fill()将元素放入共享缓冲区。在这个填充例程周围有一些等待和发送信号的代码，以确保当生产者试图填充缓冲区时缓冲区没有被填满。详情见本章。

void *producer(void *arg) {
    int id = (int) arg;
    int i;
    for (i = 0; i < loops; i++) {   p0;
        Mutex_lock(&m);             p1;
        while (num_full == max) {   p2;
            Cond_wait(&empty, &m);  p3;
        }
        do_fill(i);                 p4;
        Cond_signal(&fill);         p5;
        Mutex_unlock(&m);           p6;
    }
    return NULL;
}

从代码中可以看到，有许多标记为p0、p1等的点。这些点是代码可以休眠的地方。消费者代码(这里没有显示)有类似的等待点(c0等)。

为生产者指定睡眠字符串很简单：只要确定生产者在p0, p1，…, p6。例如，字符串1,0,0,0,0,0,0,0,0 指定生产者应该在标记p0处休眠1秒(在获取锁之前)，然后在每次循环中都不休眠。

2. 操作示例

        现在让我们展示运行其中一个程序的输出。首先，让我们假设用户运行时只有一个生产者和一个消费者。让我们不添加任何睡眠(这是默认行为)。在本例中，缓冲区大小被设置为2 (-m 2)。

首先，让我们构建如下代码：

homework/HW-Threads-RealCV$ make
gcc -o main-two-cvs-while main-two-cvs-while.c -Wall -pthread
gcc -o main-two-cvs-if main-two-cvs-if.c -Wall -pthread
gcc -o main-one-cv-while main-one-cv-while.c -Wall -pthread
gcc -o main-two-cvs-while-extra-unlock main-two-cvs-while-extra-unlock.c 
  -Wall -pthread

现在，我们能够运行如下程序：

homework/HW-Threads-RealCV$ ./main-two-cvs-while -l 3 -m 2 -p 1 -c 1 -v

在本例中，如果您跟踪代码(使用verbose标志-v)，您将在屏幕上得到以下输出(或类似的内容)

 NF             P0 C0
  0 [*---  --- ] p0
  0 [*---  --- ]    c0
  0 [*---  --- ] p1
  1 [u  0 f--- ] p4
  1 [u  0 f--- ] p5
  1 [u  0 f--- ] p6
  1 [u  0 f--- ]    c1
  1 [u  0 f--- ] p0
  0 [ --- *--- ]    c4
  0 [ --- *--- ]    c5
  0 [ --- *--- ]    c6
  0 [ --- *--- ] p1
  0 [ --- *--- ]    c0
  1 [f--- u  1 ] p4
  1 [f--- u  1 ] p5
  1 [f--- u  1 ] p6
  1 [f--- u  1 ]    c1
  1 [f--- u  1 ] p0
  0 [*---  --- ]    c4
  0 [*---  --- ]    c5
  0 [*---  --- ]    c6
  0 [*---  --- ] p1
  0 [*---  --- ]    c0
  1 [u  2 f--- ] p4
  1 [u  2 f--- ] p5
  1 [u  2 f--- ] p6
  1 [u  2 f--- ]    c1
  0 [ --- *--- ]    c4
  0 [ --- *--- ]    c5
  0 [ --- *--- ]    c6
  1 [f--- uEOS ] [main: added end-of-stream marker]
  1 [f--- uEOS ]    c0
  1 [f--- uEOS ]    c1
  0 [*---  --- ]    c4
  0 [*---  --- ]    c5
  0 [*---  --- ]    c6

Consumer consumption:
  C0 -> 3

在描述这个简单示例中发生的事情之前，让我们先理解输出中对共享缓冲区的描述，如左边所示。一开始是空的(一个空槽用——表示，两个空槽用[*--- ---]表示)；输出还显示了缓冲区中的条目数(num\_full)，从0开始。

然后，在P0给它赋值后，它的状态变为[u 0 f——](num\_full变为1)。你可能还会注意到这里有一些额外的标记；u标记显示use\_ptr的位置(这是下一个消费值的消费者将从那里获得一些东西)；类似地，f标记显示了填充\_ptr的位置(这是下一个生产者将产生值的位置)。当你看到*标记时，它仅仅意味着use\_ptr和fill\_ptr指向同一个槽。

沿着右侧，您可以看到每个生产者和消费者将要执行的步骤的轨迹。例如，生产者获取锁(p1)，然后，因为缓冲区有一个空槽，所以在其中生成一个值(p4)。然后继续执行，直到它释放锁(p6)，然后尝试重新获取锁。在本例中，使用者获取锁并使用值(c1, c4)。进一步研究跟踪，以了解生产者/消费者解决方案如何与单一生产者和消费者一起工作。

现在，让我们添加一些暂停来更改跟踪的行为。在本例中，假设我们想让生产者休眠，以便消费者可以先运行。我们可以这样做

homework/HW-Threads-RealCV$ ./main-two-cvs-while -l 1 -m 2 -p 1 -c 1 -P 1,0,0,0,0,0,0 -C 0 -v
 NF             P0 C0
  0 [*---  --- ] p0
  0 [*---  --- ]    c0
  0 [*---  --- ]    c1
  0 [*---  --- ]    c2
  0 [*---  --- ] p1
  1 [u  0 f--- ] p4
  1 [u  0 f--- ] p5
  1 [u  0 f--- ] p6
  1 [u  0 f--- ]    c3
  0 [ --- *--- ]    c4
  0 [ --- *--- ]    c5
  0 [ --- *--- ]    c6
  1 [f--- uEOS ] [main: added end-of-stream marker]
  1 [f--- uEOS ]    c0
  1 [f--- uEOS ]    c1
  0 [*---  --- ]    c4
  0 [*---  --- ]    c5
  0 [*---  --- ]    c6

Consumer consumption:
  C0 -> 1

正如您所看到的，生成器点击代码中的p0标记，然后从它的sleep规范中获取第一个值，在本例中是1，所以每个对象在尝试获取锁之前都会休眠1秒。因此，消费者开始运行，获取锁，但发现队列为空，从而进入睡眠状态(释放锁)。然后生产者运行(最终)，所有的过程都如您所料。

注意：必须为每个生产者和消费者提供睡眠规格。因此，如果您创建两个生产者和三个消费者(使用-p 2 -c 3，您必须为每个指定休眠字符串(例如，-p 0:1或-c 0,1,2:0:3,3,3,1,1,1)。睡眠字符串可以比代码中睡眠点的数量短；其余的睡眠槽被初始化为零。