> For the complete documentation index, see [llms.txt](https://hansimov.gitbook.io/csapp/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hansimov.gitbook.io/csapp/part3/ch12-concurrent-programming/homework.md).

# 家庭作业

## 练习题 12.16

{% tabs %}
{% tab title="练习题 12.16" %}
编写 hello.c（图 12-13）的一个版本，它创建和回收 n 个可结合的对等线程，其中 n 是一个命令行参数。
{% endtab %}
{% endtabs %}

## 练习题 12.17

{% tabs %}
{% tab title="练习题 12.17" %}
A. 图 12-46 中的程序有一个 bug。要求线程睡眠一秒钟，然后输出一个字符串。然而，当在我们的系统上运行它时，却没有任何输出。为什么？

```c
/* WARNING: This code is buggy! */
#include "csapp.h"
void *thread(void *vargp);

int main()
{
    pthread_t tid;

    Pthread_create(&tid, NULL, thread, NULL);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp)
{
    Sleep(1);
    printf("Hello, world!\n");
    return NULL;
}
```

> 图 12-46 练习题 12.17 的有 bug 的程序

B. 你可以通过用两个不同的 Pthreads 函数调用中的一个替代第 10 行中的 exit 函数来改正这个错误。选哪一个呢？
{% endtab %}
{% endtabs %}

## 练习题 12.18

{% tabs %}
{% tab title="练习题 12.18" %}
用图 12-21 中的进度图，将下面的轨迹线分类为安全或者不安全的。

A. $$H\_2,L\_2,U\_2,H\_1,L\_1,S\_2,U\_1,S\_1,T\_1,T\_2$$ 

B. $$H\_2,H\_1,L\_1,U\_1,S\_1,L\_2,T\_1,U\_2,S\_2,T\_2$$ 

C. $$H\_1,L\_1,H\_2,L\_2,U\_2,S\_2,U\_1,S\_1,T\_1,T\_2$$ 
{% endtab %}
{% endtabs %}

## 练习题 12.19

{% tabs %}
{% tab title="练习题 12.19" %}
图 12-26 中第一类读者—写者问题的解答给予读者的是有些弱的优先级，因为读者在离开它的临界区时，可能会重启一个正在等待的写者，而不是一个正在等待的读者。推导出一个解答，它给予读者更强的优先级，当写者离开它的临界区的时候，如果有读者正在等待的话，就总是重启一个正在等待的读者。
{% endtab %}
{% endtabs %}

## 练习题 12.20

{% tabs %}
{% tab title="练习题 12.20" %}
考虑读者—写者问题的一个更简单的变种，即最多只有 N 个读者。推导出一个解答，给予读者和写者同等的优先级，即等待中的读者和写者被赋予对资源访问的同等的机会。提示：你可以用一个计数信号量和一个互斥锁来解决这个问题。
{% endtab %}
{% endtabs %}

## 练习题 12.21

{% tabs %}
{% tab title="练习题 12.21" %}
推导出第二类读者—写者问题的一个解答，在此写者的优先级高于读者。
{% endtab %}
{% endtabs %}

## 练习题 12.22

{% tabs %}
{% tab title="练习题 12.22" %}
检查一下你对 select 函数的理解，请修改图 12-6 中的服务器，使得它在主服务器的每次迭代中最多只回送一个文本行。
{% endtab %}
{% endtabs %}

## 练习题 12.23

{% tabs %}
{% tab title="练习题 12.23" %}
图 12-8 中的事件驱动并发 echo 服务器是有缺陷的，因为一个恶意的客户端能够通过发送部分的文本行，使服务器拒绝为其他客户端服务。编写一个改进的服务器版本，使之能够非阻塞地处理这些部分文本行。
{% endtab %}
{% endtabs %}

## 练习题 12.24

{% tabs %}
{% tab title="练习题 12.24" %}
RIO I/O 包中的函数（10.5 节）都是线程安全的。它们也都是可重入函数吗？
{% endtab %}
{% endtabs %}

## 练习题 12.25

{% tabs %}
{% tab title="练习题 12.25" %}
在图 12-28 中的预线程化的并发 echo 服务器中，每个线程都调用 echo\_cnt 函数（图 12-29）。echo\_cnt 是线程安全的吗？它是可重入的吗？为什么是或为什么不是呢？
{% endtab %}
{% endtabs %}

## 练习题 12.26

{% tabs %}
{% tab title="练习题 12.26" %}
用加锁—复制技术来实现 gethostbyname 的一个线程安全而又不可重入的版本，称为 gethost-byname\_ts。一个正确的解答是使用由互斥锁保护的 hostent 结构的深层副本。
{% endtab %}
{% endtabs %}

## 练习题 12.27

{% tabs %}
{% tab title="练习题 12.27" %}
一些网络编程的教科书建议用以下的方法来读和写套接字：和客户端交互之前，在同一个打开的已连接套接字描述符上，打开两个标准 I/O 流，一个用来读，一个用来写：

```c
FILE *fpin, *fpout;
fpin  = fdopen(sockfd, "r");
fpout = fdopen(sockfd, "w");
```

当服务器完成和客户端的交互之后，像下面这样关闭两个流：

```c
fclose(fpin);
fclose(fpout);
```

然而，如果你试图在基于线程的并发服务器上尝试这种方式，将制造一个致命的竞争条件。请解释。
{% endtab %}
{% endtabs %}

## 练习题 12.28

{% tabs %}
{% tab title="练习题 12.28" %}
在图 12-45 中，将两个 V 操作的顺序交换，对程序死锁是否有影响？通过画出四种可能情况的进度图来证明你的答案：

|      情况1      |      |  情况2 |      |  情况3 |      |  情况4 |      |
| :-----------: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
|      线程 1     | 线程 2 | 线程 1 | 线程 2 | 线程 1 | 线程 2 | 线程 1 | 线程 2 |
|      P(s)     | P(s) | P(s) | P(s) | P(s) | P(s) | P(s) | P(s) |
|      P(t)     | P(t) | P(t) | P(t) | P(t) | P(t) | P(t) | P(t) |
|      V(s)     | V(s) | V(s) | V(t) | V(t) | V(s) | V(t) | V(t) |
|      V(t)     | V(t) | V(t) | V(s) | V(s) | V(t) | V(s) | V(s) |
|  {% endtab %} |      |      |      |      |      |      |      |
| {% endtabs %} |      |      |      |      |      |      |      |

## 练习题 12.29

{% tabs %}
{% tab title="练习题 12.29" %}
下面的程序会死锁吗？为什么会或者为什么不会？

```c
初始时： a = 1, b = 1, c = 1

线程 1    |    线程 2
---------|----------
P(a);    |    P(c);
P(b);    |    P(b);
V(b);    |    V(b);
P(c);    |    V(c);
V(c);    |    
V(a);    |    
```

{% endtab %}
{% endtabs %}

## 练习题 12.30

{% tabs %}
{% tab title="练习题 12.30" %}
考虑下面这个会死锁的程序。

```c
初始时： a = 1, b = 1, c = 1

线程 1   |   线程 2   |  线程 3
--------|-----------|--------
P(a);   |   P(c);   |   P(c);
P(b);   |   P(b);   |   V(c);
V(b);   |   V(b);   |   P(b);
P(c);   |   V(c);   |   P(a);
V(c);   |   P(a);   |   V(a);
V(a);   |   V(a);   |   V(b);
```

A. 列出每个线程同时占用的一对互斥锁。

B. 如果$$a \lt b \lt c$$，那么哪个线程违背了互斥锁加锁顺序规则？

C. 对于这些线程，指出一个新的保证不会发生死锁的加锁顺序。
{% endtab %}
{% endtabs %}

## 练习题 12.31

{% tabs %}
{% tab title="练习题 12.31" %}
实现标准 I/O 函数 fgets 的一个版本，叫做 tfgets，假如它在 5 秒之内没有从标准输入上接收到一个输入行，那么就超时，并返回一个 NULL 指针。你的函数应该实现在一个叫做 tfgets-proc.c 的包中，使用进程、信号和非本地跳转。它不应该使用 Linux 的 alarm 函数。使用图 12-47 中的驱动程序测试你的结果。

{% code title="code/conc/tfgets-main.c" %}

```c
#include "csapp.h"

char *tfgets(char *s, int size, FILE *stream);

int main()
{
    char buf[MAXLINE];

    if (tfgets(buf, MAXLINE, stdin) == NULL)
        printf("BOOM!\n");
    else
        printf("%s", buf);

    exit(0);
}
```

{% endcode %}

> 图 12-47 家庭作业题 12.31 \~ 12.33 的驱动程序
> {% endtab %}
> {% endtabs %}

## 练习题 12.32

{% tabs %}
{% tab title="练习题 12.32" %}
使用 select 函数来实现练习题 12.31 中 tfgets 函数的一个版本。你的函数应该在一个叫做 tfgets-select.c 的包中实现。用练习题 12.31 中的驱动程序测试你的结果。你可以假定标准输入被赋值为描述符 0。
{% endtab %}
{% endtabs %}

## 练习题 12.33

{% tabs %}
{% tab title="练习题 12.33" %}
实现练习题 12.31 中 tfgets 函数的一个线程化的版本。你的函数应该在一个叫做 tfgets-thread.c 的包中实现。用练习题 12.31 中的驱动程序测试你的结果。
{% endtab %}
{% endtabs %}

## 练习题 12.34

{% tabs %}
{% tab title="练习题 12.34" %}
编写一个$$N \times M$$矩阵乘法核心函数的并行线程化版本。比较它的性能与顺序的版本的性能。
{% endtab %}
{% endtabs %}

## 练习题 12.35

{% tabs %}
{% tab title="练习题 12.35" %}
实现一个基于进程的 TINY Web 服务器的并发版本。你的解答应该为每一个新的连接请求创建一个新的子进程。使用一个实际的 Web 浏览器来测试你的解答。
{% endtab %}
{% endtabs %}

## 练习题 12.36

{% tabs %}
{% tab title="练习题 12.36" %}
实现一个基于 I/O 多路复用的 TINY Web 服务器的并发版本。使用一个实际的 Web 浏览器来测试你的解答。
{% endtab %}
{% endtabs %}

## 练习题 12.37

{% tabs %}
{% tab title="练习题 12.37" %}
实现一个基于线程的 TINY Web 服务器的并发版本。你的解答应该为每一个新的连接请求创建一个新的线程。使用一个实际的 Web 浏览器来测试你的解答。
{% endtab %}
{% endtabs %}

## 练习题 12.38

{% tabs %}
{% tab title="练习题 12.38" %}
实现一个 TINY Web 服务器的并发预线程化的版本。你的解答应该根据当前的负载，动态地增加或减少线程的数目。一个策略是当缓冲区变满时，将线程数量翻倍，而当缓冲区变为空时，将线程数目减半。使用一个实际的 Web 浏览器来测试你的解答。
{% endtab %}
{% endtabs %}

## 练习题 12.39

{% tabs %}
{% tab title="练习题 12.39" %}
Web 代理是一个在 Web 服务器和浏览器之间扮演中间角色的程序。浏览器不是直接连接服务器以获取网页，而是与代理连接，代理再将请求转发给服务器。当服务器响应代理时，代理将响应发送给浏览器。为了这个试验，请你编写一个简单的可以过滤和记录请求的 Web 代理：

A. 试验的第一部分中，你要建立以接收请求的代理，分析 HTTP，转发请求给服务器，并且返回结果给浏览器。你的代理将所有请求的 URL 记录在磁盘上一个日志文件中，同时它还要阻塞所有对包含在磁盘上一个过滤文件中的 URL 的请求。

B. 试验的第二部分中，你要升级代理，它通过派生一个独立的线程来处理每一个请求，使得代理能够一次处理多个打开的连接。当你的代理在等待远程服务器响应一个请求使它能服务于一个浏览器时，它应该可以处理来自另一个浏览器未完成的请求。

使用一个实际的 Web 浏览器来检验你的解答。
{% endtab %}
{% endtabs %}