1. 图2-2中给出了三个进程状态。理论上，三个状态之间可以有六种转换，每个状态两个。但图中只给出了四中转换。其余两种转换是否可能发生？

缺少的两种转换分别是：

• 就绪 → 阻塞
• 阻塞 → 运行

先说就绪 → 阻塞。因为就绪状态下的进程尚未获得CPU，所以无法发起读盘等可引发阻塞的操作。

再说阻塞 → 运行。阻塞进程转换为运行需要两种资源同时就位：

• 发生了等待的某种外部事件。
• 获得了CPU 资源。

我认为理论上这是可实现的，比如外部事件发生时CPU也是空闲的。

2. 假设要设计一种先进的计算机体系结构，它使用硬件代替中断来完成进程切换。进程切换时CPU需要哪些信息？请描述用硬件完成进程切换的工作过程。

在借助中断进行进程切换的实现中，两个进程的所有信息都借助进程表进行周转。在这种新的计算机体系中，不妨仍然使用进程表。

当一个进程从运行态转为就绪态或阻塞态时，将对应表项的指针传递给硬件，由硬件将当前的进程信息写入进程表表项。

当一个进程从就绪态转换为运行态时，也是通过该指针，从对应的表项恢复进程运行的所有信息。

3. 当代计算机中，为什么中断程序至少有一部分是由汇编语言编写的？

因为 C语言等高级语言未提供操纵寄存器的函数，而处理中断时又需要保存寄存器的值，设置程序计数器，设置新的堆栈等操作。因此这一部分需要由汇编语言编写。

4. 中断或系统调用把控制权转交给操作系统时，为什么通常会用到与被中断进程的栈分离的内存栈？

这样中断处理程序或系统调用的堆栈可完全由内核控制和保护。可以规避如下情形的发生：

• 因用户程序的堆栈过深导致stack overflow。
• 栈帧释放后，其数据可能不会在内存中抹去。这为在用户态获取内核信息提供了可能。

5. 一个计算系统的内存有足够的空间容纳 5 个程序。这些程序有一半的时间处于等待 I/O 的阻塞状态。请问 CPU 时间浪费的比例是多少？

假设这些进程进入阻塞状态的时间点是随机的，那么浪费比例为：
$${\frac{1}{2}}^5=\frac{1}{32}$$

6. 一个计算机的RAM有4GB，其中操作系统占 512MB。所有进程都占 256 MB(为了简化计算)并且特征相同。要是CPU利用率达到 99%，最大的I/O等待是多少？

假设进程的 I/O 等待时间与停留在内存中时间比例为 $P$，则有
$$\begin{array}{rl}1-P^{\frac{4GB-512MB}{256MB}}& =0.99\\ 1-P^{14}& =0.99\\ P^{14}& =0.01\\ P& \approx 0.72\end{array}$$

7. 如果多个作业能够并行运行，会比它们顺序执行完成的快。假设有两个作业同时运行，每个需要20分钟CPU时间。如果顺序执行，那么完成最后一个作业需要多长时间？如果并行执行又需要多长时间？假设I/O等待占50%。

易得，串行执行时间为 $40+40=80min$。

假设并行执行的期望时间为 $n$ 分钟，那在这 $n$ 分钟内，两个进程 A 和 B 分别会有以下状态：

• 处于运行状态 $ru{n}_A=ru{n}_B=20$ 分钟
• 处于阻塞状态 $20$ 分钟
• 处于就绪状态 $\frac{n-40}{2}$ 分钟

又有，CPU 利用率
$$use=1-{\frac{1}{2}}^2=0.75$$

因此有
$$\begin{array}{rl}\frac{ru{n}_A+ru{n}_B}{n}& =0.75\\ \frac{40}{n}& =0.75\\ n& \approx 53.33min\end{array}$$

8. 考虑一个六级多道程序（内存中可同时容纳6个程序）。假设每个进程的I/O等待占40%，那么CPU利用率是多少？

$$use=1-0.4^6\approx 0.996$$

9. 假设要从互联网上下载一个 2GB 大小的文件，文件内容可从一组镜像服务器获得，每个服务器可以传输的一部分。假设每个传输请求给定起始字节和结束字节。如何使用多线程优化下载时间？

可以编写一个这样的的下载工具：

• 主线程：向服务器发送 $n$ 个请求，每个请求下载文件的一部分，保证既不重复也不冗余。
• 读线程：创建 $m$ 个读线程用于处理响应，$m\le n$，第 $i$ 个响应交由第 $i\%m$ 个读线程处理，读线程解析响应后，将数据，数据长度以及起始字节交由写线程。
• 写线程：只有一个写线程。使用 seek，write 等函数将数据写入磁盘。

10. 为什么图 2-11a 不适用于在内存中使用高速缓存的文件服务器？每个进程可以有自己的缓存吗？

涉及读写一致的场景，在进程之间同步没有线程来的方便，而且也不能有自己的缓存。

11.当一个多线程进程创建子进程时，如果子进程复制父进程的所有线程，就会出现问题：加入父进程中有一个线程正在等待键盘输入，现在就有两个线程在等待键盘输入，父进程和子进程各有一个。这种问题在单线程进程中也会发生吗？

不会。单线程进程无法同时做两件事：当它 fork 时一定没有因等待键盘而阻塞，当它因等待键盘而阻塞时也一定没有在 fork。

12. 图 2-8 给出了一个多线程的 Web 服务器。如果读取文件只能使用阻塞的 read 系统调用，那么 Web 服务器应该使用用户级线程还是内核级线程？为什么？

内核级线程。使用内核级线程时，内核可以感知到有那些线程处于阻塞态以及那些线程处于就绪态，因此可以进行调度。反之，使用用户级线程，内核只能感知到一个线程存在，无法进行调度。

13. 在本章中，我们介绍了多线程 Web 服务器，说明它比单线程服务器和有限状态机服务器更好的原因。存在单线程服务器更好的场景吗？请列举。

本章中，给出的三种实现如下：

• 多线程服务器：多线程 + 阻塞系统调用。代码易维护，性能好。
• 单线程服务器：单线程 + 阻塞系统调用。代码易维护，性能差。
• 有限状态机服务器：单线程 + 非阻塞系统调用。代码难维护，性能好。

在单核机器上执行纯计算任务，显然单线程模式更好。多线程不会执行的更快，只会增加编码的难度。

14. 既然计算机中只有一套寄存器，为什么图 2-12 中的寄存器集合是按每个线程列出的而不是按每个进程列出的？

寄存器总是和堆栈一起工作的。因此当线程在运行态和非运行态之间切换时，寄存器应该和栈等其他数据一起恢复或保存。

15. 在没有时钟中断的系统中，一个线程放弃 CPU 后可能再也不会获得 CPU 资源，那么为什么线程还要通过 thread_yield 资源放弃 CPU 呢？

在一个进程中的线程应该是互相协作的关系，一个线程可以通过该方式将时间片让渡给其他线程。

尤其是在用户级线程中，线程不会因时间中断等将CPU让渡给其他线程，此时 thread_yield 就显得很有必要了。

16. 线程可能被时钟中断抢占吗？如果可以，在什么情形下可以？如果不可以，为什么不可以？

用户级线程：当进程的时间片用完时会发生抢占，但内核无法随意调度进程中的线程，因此在下一个时间片，仍然是前一个线程继续运行，除非它自己将 CPU 让渡给其他线程。
内核级线程：当进程的时间片用完时会发生抢占，内核也可以随意调度进程中的任意线程使用CPU。

17. 请对使用单线程文件服务器和多线程文件服务器读取文件进行比较。当所需数据都在块高速缓存中时 ，获得工作请求，分派工作并完成其他必要工作需要花费 12ms。现假设有 $\frac{1}{3}$ 的请求，需要一个磁盘操作，额外花费 75ms，此时间段内该线程进入睡眠。那么单线程服务器每秒钟可以处理多少个请求？多线程服务器呢？

有 $\frac{1}{3}$ 的请求，需耗时 $75+12=87ms$。
有 $\frac{2}{3}$ 的请求，需耗时 $12ms$。
请求的平均耗时为 $87\ast \frac{1}{3}+12\ast \frac{2}{3}=27ms$。

因此，对于单线程服务器：$QPS=\frac{1000}{27}\approx 37.03请求/秒$。

多线程服务的QPS取决于线程数量和CPU核数，题目中并未给出，我们不妨假设线程数远高于请求的并发数，且只有一个核的CPU。

在此基础上，CPU一直在处理请求，因此 $QPS=\frac{1000}{12}\approx 83.33请求/秒$。

18. 在用户态实现线程的最大优点是什么？最大缺点是什么？

优点：线程切换不涉及系统调用，效率更高。

缺点：一个线程被阻塞，所有线程均被阻塞。

19. 图 2-15 中，创建线程和线程打印消息的顺序是随机交错的。有没有一种方法可以严格按照以下次序运行：创建线程1，线程1打印消息，线程1结束；创建线程2，线程2打印消息，线程2结束；依次类推。如果有，请说明方法；如果没有，请解释原因。

可以借助 pthread_join 函数等待线程退出。完整代码如下：

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

#define NUMBER_OF_THREADS 10

void *print_hello_world(void *tid) {
  printf("Hello World. Greeting from thread %d\n", tid);
  pthread_exit(NULL);
}

int main() {
  for (int i = 0; i < NUMBER_OF_THREADS; i++) {
    printf("Main here. Creating thread %d\n", i);
    pthread_t thread;
    // 创建线程
    int status = pthread_create(&thread, NULL, print_hello_world, (void*)i);
    if (status != 0) {
      printf("Oops. pthread_create returned error code %d\n", status);
      exit(-1);
    }
    // 等待线程退出，可能会阻塞调用线程。
    pthread_join(thread, NULL);
  }
  return 0;
}

可使用如下命令进行编译：

gcc -o main main.cc -pthread

20. 在讨论线程中的全局变量时，曾使用过程 create_global 分配内存存储指向变量的指针，而不是变量自身。这是必需的吗？还是直接存储变量自身也可行？

create_global 出现在 2.2.9 小节，用于创建线程级别的全局变量，通常和 set_global 以及 get_global 一起使用。

我认为存储变量自身也可行。

可将 create_global 的接口改造为：

int create_global(const char *name, int size);

create_global 会创建可存储 size 个字节的内存片段，并与 name 绑定。

get_global 改造为：

int get_global(const char *name, void **ptr);

使用 get_global 获取与 name 绑定的内存地址，将该地址写入 ptr 指向的指针。

废弃 set_global 接口。

原书答案认为是不可行的，该答案认为变量的 size 和 type 难以处理，答案原文如下：

The pointers are really necessary because the size of the global variable is unknown. It could be anything from a character to an array of floating-point numbers. If the value were stored, one would have to give the size to create_global, which is all right, but what type should the second parameter of
set_global be, and what type should the value of read_global be?

21. 考虑一个线程全部在用户态实现的系统，该运行时系统每秒钟获得一个时钟中断。当某个线程正在该运行时系统中执行时发生了一个时钟中断，此时会出现什么问题？你有什么解决问题的建议吗？

啥是运行时系统？一个管理线程的函数的集合，比如pthread_create，phtread_join 等等。

运行时系统在收到时钟中断信号后，可能执行的一种操作是进行线程状态切换：

• 将当前正在执行的线程修改为就绪状态
• 从就绪队列中挑选一个线程，并将其修改为运行状态。

假设这样一种场景，当前线程正在执行 thread_yield，正在将自己的状态修改为就绪状态。此时收到了时钟中断信号，中断处理程序也会修改当前线程的状态。这可能会导致数据不一致。如果这段代码有互斥量保护，还可能导致死锁。

可以通过缓存信号的方式解决上述冲突。

比如，新增一个标记位，和一个中断缓存队列。

当线程调用运行时系统中的某个函数时，先设置标记位，执行完成后，复位标记位，并处理中断缓存队列。

当中断到达时，先检查标记位是否被设置，若被设置则放入缓存队列，反之则立即被处理。

从而保证，中断不会丢失，运行时系统中的函数也不会被并发执行。

22. 假设一个操作系统中不存在类似于 select 的系统调用来提前判断从文件，管道或设备中读取数据时是否安全，但该操作系统允许设置定时来中断阻塞的系统调用。在上述条件下，是否有可能在用户态实现一个线程包？请讨论。

要实现一个用户级的线程包，就需要保证线程在被阻塞时，可以将CPU交给其他线程使用。

为了实现上述目标，在执行可能阻塞的系统调用前，先设置一个定时器。

如果在定时器触发前，阻塞仍未解决，则通过定时器的中断机制将CPU的控制权交由线程包重新分配。

如果在定时器出发前，系统调用完成了，那就取消定时器。

定时器的设置与取消，中断机制的执行，线程的阻塞状态的转换。三者应该保证原子性，这虽然比较麻烦，但我觉得可以实现。

23. 两个进程在一个共享内存的多处理器(两个CPU)上运行，当它们要共享一块内存时，图 2-23 中使用 turn 变量的忙等待解决方案还有效吗？

仍然有效。turn 的修改仍然是原子的，因此对 turn 的赋值和检测与单处理器没有区别，所以仍然有效。

24. 在抢占式进程调度的条件下，图 2-24 中互斥问题的 Peterson 解法可行吗？如果是非抢占式调度呢？

非抢占式：挑选一个进程，并让其开始运行直到被阻塞，或者自动放弃CPU。

不可行。

假设有两个进程 A 和 B，A 先进入了临界区，在临界区内进入了阻塞状态。此时 B 进入了运行状态，并一直忙等待，由于 B 不会被抢占，因此 A 也无法离开临界区，从而导致 A 和 B 互相等待，都无法正常执行下去。

抢占式：挑选一个进程，并让其开始运行，但为其运行时间设置上限。如果在运行时间达到上限时仍在运行，则将其挂起。

可行。

25. 2.3.4节中所讨论的优先级反转问题在用户级线程中是否可能发生？为什么?

优先级反转问题是指，进入临界区的低优线程因无法获得CPU使用权导致自身无法退出临界区，进而导致高优线程一直忙等待的现象。

假设这样一种场景，在临界区内进行系统调用导致低优线程阻塞，而后另一个线程开始执行并忙等待。这种场景也会造成两个线程都无法正常运行的问题。

原书的英文答案认为不会发生，原文如下：
The priority inversion problem occurs when a low-priority process is in its critical region and suddenly a high-priority process becomes ready and is scheduled. If it uses busy waiting, it will run forever. With user-level threads, it cannot happen that a low-priority thread is suddenly preempted to allow a high-priority thread run. There is no preemption. With kernel-level threads this problem can arise.

26. 2.3.4节中描述了一种有高优先级进程H和低优先级进程L的情况，导致了 H 陷入了死循环。若采用轮转调度算法地代替优先级算法，还会发生同样的问题吗？请讨论。

不会发生。L 总会获得CPU使用权，从而退出临界区。这解除了 H 和 L 对 「CPU使用权和临界区」的循环等待。

27. 在使用线程的系统中，若使用用户级线程，是每个线程一个栈还是每个进程一个栈？如果使用内核级线程呢？请解释。

无论是用户级还是内核级，每个线程都需要一段内存来存储那些被调用但还未返回的函数的数据。这段内存就是栈。

28. 在开发计算机时，通常首先用一个程序模拟执行，一次运行一条指令，多处理器也严格按此模拟。在这种没有同时事件发生的情形下，会出现竞争条件吗？

Yes. The simulated computer could be multiprogrammed. For example, while process A is running, it reads out some shared variable. Then a simulated clock tick happens and process B runs. It also reads out the same variable. Then it adds 1 to the variable. When process A runs, if it also adds 1 to the variable, we have a race condition.

29. 将生产者-消费者问题扩展成多生产者-多消费者的问题，生成(消费)者都写(读)一个共享的缓冲区，每个生产者和消费者都在自己的线程中执行。图 2-28 中使用信号量的解法在这个系统中还可行吗？

可行，因为 down 和 up 是原子的，这仍然保证了在任意时间点，只有一个线程在临界区内。

30. 考虑对于两个进程 P0 和 P1 的互斥问题的解决方案。假设变量初始值为 0。P0 点的代码如下：

/* other code */
while (turn != 0) {} /* Do nothing and wait */
Critical Section /* ... */
turn = 0;
/* Other Code */

P1 的代码是将上述代码中的 0 替换为 1。该方法是否能处理互斥问题中所有可能的情形？

---

感觉这题写错了。

turn 的初始值为 0，因此 P0 先执行，P0执行完 turn 还是 0，P1 根本不能进入临界区。

---

感觉把代码改成下面这样才是对的。

P0 的代码：

/* other code */
while (turn != 0) {} /* Do nothing and wait */
Critical Section /* ... */
turn = 1;
/* Other Code */

P1 的代码：
```c
/* other code */
while (turn != 1) {} /* Do nothing and wait */
Critical Section /* ... */
turn = 0;
/* Other Code */

这样 P0 和 P1 就会交替进入临界区，这样是比较可行的。

31. 一个可以屏蔽中断的操作系统如何实现信号量？

To do a semaphore operation, the operating system first disables interrupts. Then it reads the value of the semaphore. If it is doing a down and the semaphore is equal to zero, it puts the calling process on a list of blocked processes associated with the semaphore. If it is doing an up, it must check to see if any processes are blocked on the semaphore. If one or more processes are blocked, one of them is removed from the list of blocked processes and made runnable. When all these operations have been completed, interrupts can be enabled again.

32. 请说明仅通过二元信号量和普通机器指令如何实现计数信号量（即可以保持一个任意值的信号量）。

二元信号量的定义(74页)：

• 初值为 1。
• 保证任意时刻最多有一个线程进入临界区。但这一条需要调用线程配合，即进入前调用 Down，退出前调用 Up.

用 std::mutex 和 std::condition_variable 实现信号量 Semaphore：

#include <mutex>
#include <condition_variable>

class BinarySemaphore {
  // 互斥量，保护数据
  std::mutex mutex;

  // 条件变量，用于阻塞线程
  std::condition_variable cv;

  int64_t value = 1;

 public:
  void Up() {
    {
      std::unique_lock<std::mutex> lock(mutex);
      ++value;
    }
    if (value > 0) {
      cv.notify_one();
    }
  }
  void Down() {
    std::unique_lock<std::mutex> lock(mutex);
    while (value == 0) {
      cv.wait(lock, [this]() -> bool { return value != 0; });
    }
    --value;
  }
};

上述实现是符合信号量的标准的：

• down 操作：将 value 减一，当且仅当 value 为 0 时调用线程进入睡眠。
• up 操作：将 value 加一，而且绝对不会阻塞调用线程。
• mutex 保证了 down 和 up 的原子性。

接下来，使用两个二元信号量和两个整型变量实现题目要求的计数信号量。

• int64_t value，计数字段。
• int64_t blocking，有多少个线程阻塞在 block 上面。
• BinarySemaphore mutex ：保护 value 和 block，在每个时刻最多只有一个线程读写。
• BinarySemaphore block：当 value 为 0 时，阻塞调用线程。

class Semaphore {
  BinarySemaphore mutex;
  BinarySemaphore block;
  int64_t value = 0;
  int64_t blocking = 0;

 public:
  Semaphore() {
    // 因为 BinarySemaphore::value 的初始值是 0，
    // 所以先执行一次 mutex.Up，表示没有线程持有该锁。
    mutex.Up();
  }

  ~Semaphore() {
    std::cout << "value: " << value << ", blocking: " << blocking << std::endl;
  }

  void Down() {
    mutex.Down();
    if (value) {
      value--;
      mutex.Up();
    } else {
      blocking++;
      mutex.Up();
      block.Down();
    }
  }

  void Up() {
    mutex.Down();
    if (blocking) {
      blocking--;
      mutex.Up();
      block.Up();
    } else {
      value++;
      mutex.Up();
    }
  }
};

修改 value 的定义为 value-blocking，从而省略掉 blocking 字段。新的实现如下：

class Semaphore {
  BinarySemaphore mutex;
  BinarySemaphore block;
  int64_t value = 0;

 public:
  Semaphore() {
    // 先 Down 一次，把初始值消耗掉
    block.Down();
  }
  ~Semaphore() {
    std::cout << "value: " << value << std::endl;
  }

  int64_t Value() const {
    return value;
  }

  void Down() {
    mutex.Down();
    if (value > 0) {
      value--;
      mutex.Up();
    } else {
      value--;
      mutex.Up();
      block.Down();
    }
  }

  void Up() {
    mutex.Down();
    if (value < 0) {
      value++;
      block.Up();
      mutex.Up();
    } else {
      value++;
      mutex.Up();
    }
  }
};

33. 如果一个系统只有两个进程，可以使用一个屏障来同步这两个进程吗？为什么？

屏障通常用于同步一组进程的多阶段的动作。当这一组进程都完成特定阶段的动作后，才会一起进入下一阶段。

因此能否使用屏障和线程数量没有关系，只要进程的工作有明显的阶段性，就很适合使用屏障。

34. 如果线程在内核态实现，可以使用内核信号量对同一个进程中的两个线程进行同步吗？如果线程在用户态实现呢？假设其他进程中没有线程需要访问该信号量。请解释你的答案。

1. 内核态实现，可以。因为内核能明确知道线程的所有信息。
2. 用户态实现，不可以。因为内核只能感知到一个线程的存在，当这个线程被阻塞后，没有其他线程再使其进入就绪状态了。

35. 管程的同步机制使用条件变量和两个特殊操作 wait 和 signal。一种更通用的同步方式是只用一条原语 waituntil，它以任意的布尔谓词作为参数。例如 waitutil x < 0 or y+z < n，这样就不需要 signal 原语了。这种方法为何从未被采用过。为什么？

试想系统应以何种机制来检查布尔谓词是否为真呢？

• 轮询：每个一段时间检查一次。缺点很明显，间隔短则退化为忙等待，间隔长则效率低下。
• 回调：在每个变量被修改时进行判断。缺点是实现困难，比如在 C++ 中，如何为某个 int 类型的变量设置回调呢。
• 主动通知：修改了相关变量的线程，发送一个信号。这就是 signal 原语了。

还有其他方法吗？暂时没想到。

综合来看，signal 原语的方案是最可用的。其他两种都不太具备实操性。

36. 一个快餐店有四类雇员：领班，接受顾客点的菜单；厨师：准备饭菜；打包员：将饭菜装在袋子里；收银员：拿钱交饭。每个雇员可被看作一个可以进行通信的串行进程，那么进程间的通信方法是什么？

进程间的通信方式有哪些：信号量，互斥量，管程，消息传递，屏障。

基于消息传递可以很好的实现该场景。实现了一个简易 demo，放到了 github。

37. 假设有一个使用信箱的消息传递系统，当向满信箱发消息或从空信箱收消息时，进程不会阻塞，而是得到一个错误代码。进程响应错误代码的处理方式是不断地重试，知道成功为止。这种方式会导致竞态条件吗？

竞态条件的定义：两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，成为竞态条件。(67页)

显然这种忙等待的方式不会触发竞态条件。

38. CDC 6000计算机使用一种称作处理器共享的又去的轮转调度算法，可以同时处理多达 10 个 I/O 进程。每条指令结束后都进行进程切换，即进程1执行指令1，进程2执行指令2，以此类推。进程切换由特殊硬件完成，所以没有开销。如果在没有竞争的条件下一个进程需要 T 秒完成，那么当有 n 个进程共享处理器时完成该进程需要多长时间？

单个进程需要使用 T 秒的 CPU，且进程之间切换无额外耗时。因此总共需要 $nT$ 秒。

39. 考虑以下C代码，程序执行时创建了多个子进程？

void main() {
	fork();
	fork();
	exit();
}

设有进程号为 100 的主进程开始执行 main 函数。
执行完第一个 fork 后，会产出一个新的进程，设其进程号为 201。
接着，100 和 201 均执行到了第二个 fork，分别产生一个新进程，设进程号分别为 301 和 202。

因此总共产生了三个子进程，四个进程的关系如下所示：

100
|___ 201
|	|___202
|___ 301

40. Round-Robin 调度算法一般需要维护一个就绪进程列表，每个进程在列表中只出现一次。如果某个进程在列表中出现两次会发生什么情况？什么情况下可以允许出现多次？

相当于对该进程提权了，可以分到更多的时间片。

41. 是否可以通过分析源代码来确定进程是CPU密集型的还是I/O密集型的？运行时如何确定？

通过源代码分析可能不太准确吧，比较还有启动参数，输入输出的数据规模等影响因素。

通过进程的运行时长和使用的CPU时间作比较，可以判断其类型。

42. 请说明 Round-Robin 调度算法中时间片长度和上下文切换时间是怎样相互影响的？

为了保证CPU的利用率，时间片长度总是上下文切换时间的若干倍。

43. 对某系统进行检测后发现，在阻塞I/O之前，平均每个进程的运行时间为 T。一次进程切换需要的时间是 S，这里 S 实际上就是开销。对于采用时间片长度为 Q 的轮转调度，请给出一下各种情况的 CPU 利用率计算公式。

CPU 利用率就是进程使用CPU的时间除以CPU总时间，即
$$\frac{进程使用CPU的时间}{进程使用CPU的时间+进程切换使用的时间}$$
当 $Q=\infty$ 或者 $Q>T$ 时，显然每隔时间 T 则发生一次切换，因此有
$$utilization=\frac{T}{T+S}$$

当 $Q<T$ 时，则进程每运行时间 T，则会发生 $\frac{T}{Q}$ 次切换，因此有

$$utilization=\frac{T}{\frac{T}{Q}S+T}=\frac{Q}{Q+S}$$

同上，当 $Q=S$ 时有
$$utilization=\frac{T}{\frac{T}{Q}S+T}=\frac{1}{2}$$

当 $Q$ 趋近于 $0$，每运行时间 T，需要无穷多切换次数，显然利用率趋近于 0。

44. 有五个待运行的作业，估计它们的运行时间为 9，6，3，5，X。以何种次序调度能得到最短的响应时间？

响应时间：作业从提交到完成的时间间隔。

假设五个作业同时提交，则采用最短作业优先的策略可保证最短的平均响应时间。
$$\begin{array}{cc}0<X\le 3& ：X，3，5，6，9\\ 3<X\le 5& ：3，X，5，6，9\\ 5<X\le 6& ：3，5，X，6，9\\ 6<X\le 9& ：3，5，6，X，9\\ 9<X& ：3，5，6，9，X\end{array}.$$

45. 有五个批处理作业 A ~ E，它们几乎同时到达一个计算中心。估计它们的运行时间分别为 10、6、2、4、8分钟。其优先级分别为 3、5、2、1、4，其中 5 为最高优先级。对于下列每种调度算法，计算其平均进程周转时间，可忽略进程切换的开销。

a. 轮转法：$\frac{10+18+24+28+30}{5}=22.0minutes$

初始有五个任务使用轮转CPU，因此 C 完成于 $2/\frac{1}{5}=10$ 分钟。
然后有四个任务使用轮转CPU，因此 D 完成于 $(4-2)/\frac{1}{4}+10=18$ 分钟。
然后有三个任务使用轮转CPU，因此 B 完成于 $(6-4)/\frac{1}{3}+18=24$ 分钟。
然后有两个任务使用轮转CPU，因此 E 完成于 $(8-6)/\frac{1}{2}+24=28$ 分钟。
最后有一个任务使用轮转CPU，因此 A 完成于 $(8-6)/\frac{1}{1}+28=30$ 分钟。

b. 优先级调度：$\frac{6+14+24+26+30}{5}=20.0minutes$

• 首先执行 B，耗时 6 分钟。
• 然后执行 E，耗时 14 分钟。
• 然后执行 A，耗时 24 分钟。
• 然后执行 C，耗时 26 分钟。
• 最后执行 D，耗时 30 分钟。

c. FIFO (按照10、6、2、4、8次序运行)：$\frac{10+16+18+22+30}{5}=19.2minutes$

• 首先执行 A，耗时 10 分钟。
• 然后执行 B，耗时 16 分钟。
• 然后执行 C，耗时 18 分钟。
• 然后执行 D，耗时 22 分钟。
• 最后执行 E，耗时 30 分钟。

d. 最短优先作业：$\frac{2+6+12+20+30}{5}=14.0minutes$

46. 运行在 CTSS 上的某个进程需要30个时间片才能完成。该进程必须调入多少次？

第 1 次调度，运行 1 时间片，还需 29 个。
第 2 次调度，运行 2 时间片，还需 27 个。
第 3 次调度，运行 4 时间片，还需 23 个。
第 4 次调度，运行 8 时间片，还需 15 个。
第 5 次调度，运行 15 时间片，还需 0 个。

综上，总共调入 5 次。

47. 一个实时系统有 2 个周期为 5ms 的电话任务，每次任务使用的 CPU 时间是 1ms；还有一个周期为 33ms 的视频流，每次任务使用的CPU时间是 11ms。这个系统是可调度的吗？

92页给出的是否可调度的衡量标准是：若有 $m$ 个事件，事件 $i$ 以周期 $P_i$ 发生，并需要 $C_i$ 秒的 CPU 时间，若满足 ${\sum }_{i=1}^m\frac{C_i}{P_i}\le 1$ 则可调度，反之则不可。

这个式子可以理解为：对于任意一类事件，在一个周期内，总是能分配到足够的CPU时间。

根据上述式子，可得出：
$$\frac{1}{5}+\frac{1}{5}+\frac{11}{33}\approx 0.733\le 1$$

因此，该系统可以调度。

48. 在上一题中，再加入一个视频流，系统还是可调度的吗？

$$\frac{1}{5}+\frac{1}{5}+\frac{11}{33}+\frac{11}{33}\approx 1.067>1$$

因此，再加入一个视频流后，系统不可调度。

49. 用 $a=\frac{1}{2}$ 的老化算法来预测运行时间。先前的四次运行，从最老到最近的一个，依次为 40ms、20ms、40ms、15ms。那么下次的预测时间是多少？

$$T=15\ast \frac{1}{2}+40\ast \frac{1}{4}+20\ast \frac{1}{8}+40\ast \frac{1}{8}=25.0ms$$

50. 一个软实时系统有 4 个周期时间，其周期分别为 15ms、100ms、200ms、250ms。假设这 4 个事件分别需要 35ms、20ms、10ms、x ms 的 CPU 时间。保持系统可调度的最大 x 值是多少？

根据可调度性估算公式 ${\sum }_{i=1}^m\frac{C_i}{P_i}\le 1$ ，可得

$$\begin{array}{rl}\frac{35}{100}+\frac{20}{100}+\frac{10}{200}+\frac{x}{250}& =1\\ x& =(1-\frac{35}{100}-\frac{20}{100}-\frac{10}{200})\ast 500\\ x& =200ms\end{array}$$

因此，x 的上限为 200ms。

51. 在哲学家就餐问题中使用如下规则：编号为偶数的哲学家先拿他左边的叉子再拿他右边的叉子；编号为偶数的哲学家先拿他右边的叉子再拿他左边的叉子；这条规则能否避免死锁？

死锁的四个条件：互斥条件、占有和等待条件、不可抢占条件、环路等待条件。

不难发现，上述策略不存在环路等待条件。因此可以避免。

52. 一个实时系统需要处理两个语音通信，每个通信都是 6ms 运行一次，每次占用 1ms CPU 时间，加上 25帧/秒的一个视频，每一帧需要 20ms 的 CPU时间。这个系统是可调度的吗？

$$\frac{1}{6}+\frac{1}{6}+\frac{20}{\frac{1000}{25}}=\frac{5}{6}\le 1$$

因此是可调度的。

53. 考虑一个系统，希望以策略与机制分离的方式实现内核级线程调度。请提出一个解决方案。

内核提供 n 个就绪队列，编号从 1 到 n。编号为 i 的队列最多可以连续获得 i 个时间片，队列内的线程FIFO的获得时间片。

用户通过指定线程进入哪个队列来控制其优先级。

54. 在哲学家就餐问题的解法(图2-47)中，为什么在过程 take_fork 中将状态变量置为 HUNGRY？

首先，中文第四版省略了一段代码，在英文版原书中，philosopher 函数的实现如下：

void philosopher(int i) {	// i: philosopher number, from 0 to N-1
	where (TRUE) {		  	// repeat forever
		think();			// philosopher is thinking
		take_forks(i);		// acquire two forks or block
		eat();				// yum-yum, spaghetti
		put_forks(i);		// put both forks back on table
	}
}

置为 HUNGRY，是为了配合相邻的哲学家。当相邻哲学家放下叉子时，可根据该状态唤醒自己。

55. 考虑图 2-47 中的过程 put_forks，假设变量 state[i] 在对 test 的两次调用之后（而不是之前）才被置为 THINKING，这会对解法有什么影响吗？

导致 test 时无法唤醒被挂起的相邻的哲学家。

56. 按照哪一类进程何时开始执行，读者-写者问题可以有几种方式求解。请详细描述该问题的三种变体，每一种变体偏好（或不偏好）某一类进程。对每种变体，请指出当一个读者或写者访问数据库时会发生什么，以及当一个进程结束对数据库的访问后又会发生什么？

Variation 1: readers have priority. No writer may start when a reader is active. When a new reader appears, it may start immediately unless a writer is currently active. When a writer finishes, if readers are waiting, they are all started, regardless of the presence of waiting writers.

Variation 2: Writers have priority. No reader may start when a writer is waiting. When the last active process finishes, a writer is started, if there is one; otherwise, all the readers (if any) are started.

Variation 3: symmetric version. When a reader is active, new readers may start immediately. When a writer finishes, a new writer has priority, if one is waiting. In other words, once we have started reading, we keep reading until there are no readers left. Similarly, once we have started writing, all pending writers are allowed to run.

个人感觉第三种做法并不妥当。在该做自称是 symmetric ，但仍可能会导致一种操作一直饥饿。比如 Reader 先来了，且在 Reader 结束前一直有Reader 到来，则 Writer 永远不会被执行。

应该改成 FIFO 比较合适，先来的先被执行，如果和当前的操作互斥，则在当前操作结束后再执行。

57. 请编写一个 shell 脚本，读取文件的最后一个数字，加 1 后追加至文件末尾，从而生成顺序数文件。启动该脚本两次，并访问相同的文件。需要多长时间才会出现竞争条件？临界区是什么？请修改改脚本以避免竞争。

无锁版本

# 第一个参数是文件名
# 向文件末尾追加一百个数字
repeat=0
while True
do
  last=`tail -n 1 $1 2>&1`;
  if [[ -z `echo $last | grep "^[0-9][0-9]*$"` ]]; then
    last=0;
  fi
  if [ $repeat -ge 100 ]; then
    break;
  fi
  repeat=`expr ${repeat} + 1`;
  next=`expr ${last} + 1`;
  echo $next >> $1;
done

临界区包含三个步骤：

• 读取最后一行
• 加一
• 追加至末尾

有锁版本。一个并不鲁棒的锁——借助mkdir的结果判断是否获得锁：

# 第一个参数是文件名
# 向文件末尾追加一百个数字
repeat=0
while True
do
  last=`tail -n 1 $1 2>&1`;
  if [[ -z `echo $last | grep "^[0-9][0-9]*$"` ]]; then
    last=0;
  fi
  if [ $repeat -ge 100 ]; then
    break;
  fi
  repeat=`expr ${repeat} + 1`;
  next=`expr ${last} + 1`;
  echo $next >> $1;
done

58. 假设有一个提供信号量的操作系统。请实现一个消息系统，可以发送和接收消息。

可以参见
02-message-passing.h
02.problem.36.h

59. 使用管程代替信号量来解决哲学家就餐问题。

现基于 Semaphore 实现哲学家就餐问题。见 02-philosopher-semaphore.h

按照定义，它应该具有以下几个特点：

• 一个由过程，变量以及数据结构组成的集合。(这就是 C++ 中的类呀)
• 不能在管程之外访问管程内的数据结构。(类的私有成员变量)
• 任一时刻管程内只有一个活跃的线程。（或许也能实现，可能会很丑。。。）

管程代码见 02-monitor.h

再基于 Monitor 实现一遍。见 02.problem.59.h

60. 假设某大学准备把美国最高法院的信条"平等但隔离其本身就是不平等"（Separate but equal is inherently unequal）即运用在种族上也运用在性别上，从而结束校园内长期使用的浴室按性别隔离的做法。但是，为了迁就传统习惯，学校颁布法令：当有一个浴室有女生在浴室里时，其他女生也可以进入，但男生不行，反之亦然。在每个浴室的门上有一个滑动标记，表示当前处于以下三种可能状态之一：空；有女生；有男生；用你喜欢的编程语言编写下面的过程：woman_wants_to_enter，man_wants_to_enter，woman_leaves，man_leaves。可以随意使用计数器和同步技术。

代码见 02.problem.60.h

61. 重写图 2-23 中的程序，使它可以处理两个以上的进程。

C/C++ 中对 build-in 类型的变量赋值是原子的，利用这一点实现严格轮转。代码见 02.problem.61.h

62. 跳过。

63. 跳过。

64. 跳过。

65. 跳过。