本系列博文是《现代操作系统（英文第三版）》（Modern Operating Systems，简称MOS）的阅读笔记，定位是正文精要部分的摘录和课后习题精解，因此不会事无巨细的全面摘抄，仅仅根据个人情况进行记录和推荐。由于是英文版，部分内容会使用英文原文。
课后习题的选择标准：尽量避免单纯的概念考察（如：What is spooling?）或者简单的数值计算，而是能够引起思考加深理解的题目。为了保证解答的正确性，每道题都会附上原书解答，而中文部分会适当加入自己的见解。原书答案（需注册）
从本节开始，新增“概念名称回顾”，不会展开来写，仅供按图索骥、查漏补缺，方便回顾。上一节也会补上。
概念名称回顾
进程：相关API、状态、实现；
线程：和进程的区别与联系、内核级线程和用户级线程区别和实现及优劣；
进程通信：竞争条件、临界区、互斥与忙等、信号量、互斥锁、管程、消息传递、屏障
调度算法：不同系统的不同调度算法、机制与策略分离；
典型IPC问题：哲学家进餐问题、读者—写者问题
1.关于进程数目、进程平均I/O频率与CPU利用率的推导
原书P94假设进程用于等待I/O结束的时间为它运行的总时间中的p（比如，p=80%代表这个进程I/O花费的时间是总运行时间的80%），同一时间内内存中一共有n个进程在运行，那么这n个进程都在等待I/O的概率为pn——这意味着所有的进程都没用使用CPU，也即CPU处在空闲状态——那么，根据对立事件的概率，CPU利用率就可以表示为：
CPU 利用率 = 1 – pn
利用这个公式做图表，会得到很多有价值的结论。
可以看出，(1)在进程数相同时，I/O频率越高，CPU的利用率越低；(2)为了提高CPU的利用率，可以采取的方法是增加同时运行的进程数。
虽然这个公式是把I/O频率平均化所得的近似公式，并且假定这n个进程之间的运行互不干扰；更准确的模型需要用排队论的知识进行构建，但是，“增加进程数以使得CPU更不常处于空闲状态”的结论，依然正确，并与上图仅仅有着轻微的不同。
这个简单模型甚至还能得到另一个推断：如果计算机拥有512MB内存，操作系统占用了128MB，其余进程I/O频率都是80%，并且每个占用128MB，那么此时的CPU利用率是1-0.83，也即49%；而当增加512MB内存时，意味着可以运行更多的4个进程，这时CPU的利用率会提升到79%，也即这额外的512MB内存带来了30%的CPU利用率提升。
更神奇的是，这个简单模型还可以用来计算多个进程并行时所需使用的总时间，例子请参考习题5。
2.Peterson解法
原书P123，为了能够保证进程互斥地进入临界区（critical_region），并要求只使用软件编码实现（不提供额外的硬件机制），最初可以想到的解决方法如下，它被称为严格轮换法（Strict Alternation）：
(TURE) {while(turn != 0);critical_region();turn = 1;noncritical_region();}(TURE) {while(turn != 1);critical_region();turn = 0;noncritical_region();}
虽然可以保证互斥这一要求，但是这两个进程只能轮流进入临界区，这意味着较快的一个进程会被较慢的另一个所拖慢。也即，当process0刚退出临界区而使得turn=1、process1在非临界区时，process0不能马上再次进入临界区，这违反了（原文中的前文“一个好的临界区访问方式”的）条件3，这4个条件如下：
1.任何两个进程不能同时进入同一个临界区；
2.不应做出有关CPU速度或个数的任何假设；
3.任何不在它的临界区的进程不应阻塞其他进程；
4.不应有任何进程无限地等待进入临界区。
看来这个根据直觉写出的解法并不令人满意。为了从软件角度解决这个问题，不同人提出了不同的算法。Peterson于1981年发现了一个相当简单的解法：
#define FALSE 0#define TRUE 1turn; interested[N]; enter_region({other = interested[process] = TRUE; turn = process; (turn == process && interested[other] == TRUE); }{interested[[process] = FALSE; }
稍作分析可以看出，如果只有一个进程，可以无限运行下去；如果有两个进程，它们都标记了自己对临界区感兴趣（interested[process] = TRUE），但此时turn由后设置者决定。而先设置者p0正好可以退出while循环，执行临界区代码，并于退出临界区时声明自己对临界区无兴趣（interested[[process] = FALSE）。这时，如果另一个进程p1在忙等，则可以进入临界区；如果不在忙等，它的interseted要么非真（未执行到这个语句），要么为真但尚未开始进行忙等：对于前者，如果p0足够快，可以再次进入临界区；对于后者，p0就只能开始忙等，等待p1先进入临界区了。
读者可能对上面我的转述看的一头雾水，没关系，自行根据代码和情形假设推导下各个情况才能理解这个解法的妙处。我个人认为这段代码妙处在于，它用了两个变量（一个整型和一个2个元素的数组）而非单一变量来提供更好的解法，这个思路非常值得学习。
3.实时系统中周期任务可调度的条件的推导
原书P161，假设一个实时系统中所有任务都是周期性的，一共有m个任务，第i个任务周期为Pi，需要时间Ci的CPU才能处理完，那么这些任务可调度的条件是
\[\sum_{i=1}^{m}\frac{C_{i}}{P_{i}}\leq 1\]
旁观者的姓名永远爬不到比赛的计分板上。
