博客

第2章 进程与线程

2.1 进程

2.1.1 进程模型

在进程模型中， 计算机上所有可运行的软件， 通常也包括操作系统， 被组织成若干顺序进程

（sequential process） ， 简称进程（process） 。 一个进程就是一个正在执行程序的实例， 包括程序计数器、

寄存器和变量的当前值。

这里的关键思想是： 一个进程是某种类型的一个活动， 它有程序、 输入、 输出以及状态。 单个处理器可

以被若干进程共享， 它使用某种调度算法决定何时停止一个进程的工作， 并转而为另一个进程提供服务。

2.1.2 创建进程

有4种主要事件导致进程的创建：

1)系统初始化。

2)执行了正在运行的进程所调用的进程创建系统调用。

3)用户请求创建一个新进程。

4)一个批处理作业的初始化。

2.1.3 进程的终止

通常由下列条件引起：

1)正常退出（自愿的） 。

2)出错退出（自愿的） 。

3)严重错误（非自愿） 。

4)被其他进程杀死（非自愿） 。

2.1.4 进程的层次结构

某些系统中， 当进程创建了另一个进程后， 父进程和子进程就以某种形式继续保持关联。 子进程自身可以创建更多的进程， 组成一个进程的层次结构。 请注意， 这与植物和动物的有性繁殖不同， 进程只有一个父进程（但是可以有零个、 一个、 两个或多个子进程）

2.1.5 进程的状态

这三种状态是：

1)运行态（该时刻进程实际占用CPU） 。

2)就绪态（可运行， 但因为其他进程正在运行而暂时停止） 。

3)阻塞态（除非某种外部事件发生， 否则进程不能运行） 。

2.1.6 进程的实现

为了实现进程模型， 操作系统维护着一张表格（一个结构数组） ， 即进程表（process table） 。 每个进程占用一个进程表项。 （有些作者称这些表项为进程控制块。 ） 该表项包含了进程状态的重要信息， 包括程

序计数器、 堆栈指针、 内存分配状况、 所打开文件的状态、 账号和调度信息， 以及其他在进程由运行态转换到就绪态或阻塞态时必须保存的信息， 从而保证该进程随后能再次启动， 就像从未被中断过一样。

2.1.7 多道程序设计模型

采用多道程序设计可以提高CPU的利用率。 严格地说， 如果进程用于计算的平均时间是进程在内存中停留时间的20%， 且内存中同时有5个进程， 则CPU将一直满负载运行。 然而， 这个模型在现实中过于乐观，因为它假设这5个进程不会同时等待I/O。

更好的模型是从概率的角度来看CPU的利用率。 假设一个进程等待I/O操作的时间与其停留在内存中时间的比为p。 当内存中同时有n个进程时， 则所有n个进程都在等待I/O（此时CPU空转） 的概率是pn 。 CPU的利用率由下面的公式给出：

CPU利用率=1-pn

2.2 线程

在传统操作系统中， 每个进程有一个地址空间和一个控制线程。

2.2.1 线程的使用

1.并行实体共享同一个地址空间和所有可用数据的能力。

2.第二个关于需要多线程的理由是， 由于线程比进程更轻量级， 所以它们比进程更容易（即更快） 创建，也更容易撤销。

3.性能方面。如果存在着大量的计算和大量的I/O处理， 拥有多个线程允许这些活动彼此重叠进行， 从而会加快应用程序执行的速度。

4.在多CPU系统中， 多线程是有益的， 在这样的系统中， 真正的并行有了实现的可能。

2.2.2 经典的线程模型

在多线程的情况下， 进程通常会从当前的单个线程开始。 这个线程有能力通过调用一个库函数（如thread_create） 创建新的线程。

当一个线程完成工作后， 可以通过调用一个库过程（如thread_exit） 退出。 该线程接着消失， 不再可调度。 在某些线程系统中， 通过调用一个过程， 例如thread_join， 一个线程可以等待一个（特定） 线程退出。

一个常见的线程调用是thread_yield， 它允许线程自动放弃CPU从而让另一个线程运行。

2.2.3 POSIX线程

为实现可移植的线程程序， IEEE在IEEE标准1003.1c中定义了线程的标准。 它定义的线程包叫做Pthread。 大部分UNIX系统都支持该标准。

2.2.4 在用户空间中实现线程

有两种主要的方法实现线程包： 在用户空间中和在内核中。 这两种方法互有利弊， 不过混合实现方式也是可能的。 我们现在介绍这些方法， 并分析它们的优点和缺点。

优势：

1.保存该线程状态的过程和调度程序都只是本地过程， 所以启动它们比进行内核调用效率更高。 另一方面， 不需要陷入， 不需要上下文切换， 也不需要对内存高速缓存进行刷新， 这就使得线程调度非常快捷。

2.它允许每个进程有自己定制的调度算法。

缺点：

1.如何实现阻塞系统调用。 使用线程的一个主要目标是， 首先要允许每个线程使用阻塞调用， 但是还要避免被阻塞的线程影响其他的线程。

2.如果一个线程开始运行， 那么在该进程中的其他线程就不能运行， 除非

第一个线程自动放弃CPU。

2.2.5 在内核中实现线程

在内核中实现线程此时不再需要运行时系统了。 另外， 每个进程中也没有线程表。 相反， 在内核中有用来记录系统中所有线程的线程表。 当某个线程希望创建一个新线程或撤销一个已有线程时， 它进行一个系统调用， 这个系统调用通过对线程表的更新完成线程创建或撤销工作。

优势：

1.所有能够阻塞线程的调用都以系统调用的形式实现， 这与运行时系统过程相比， 代价是相当可观的。 当一个线程阻塞时， 内核根据其选择， 可以运行同一个进程中的另一个线程（若有一个就绪线程） 或者运行另一个进程中的线程。 而在用户级线程中， 运行时系统始终运行自己进程中的线程， 直到内核剥夺它的CPU（或者没有可运行的线程存在了） 为止。

2.内核线程不需要任何新的、 非阻塞系统调用。 另外， 如果某个进程中的线程引起了页面故障， 内核可以很方便地检查该进程是否有任何其他可运行的线程， 如果有， 在等待所需要的页面从磁盘读入时， 就选择一个可运行的线程运行。 这样做的主要缺点是系统调用的代价比较大， 所以如果线程的操作（创建、 终止等）比较多， 就会带来很大的开销

缺点：

1.当一个多线程进程创建新的进程时， 会发生什么？

新进程是拥有与原进程相同数量的线程， 还是只有一个线程？ 在很多情况下， 最好的选择取决于进程计划下一步做什么。 如果它要调用exec来启动一个新的程序， 或许一个线程是正确的选择； 但是如果它继续执行， 则应该复制所有的线程。

2.另一个话题是信号。 回忆一下， 信号是发给进程而不是线程的， 至少在经典模型中是这样的。 当一个信号到达时， 应该由哪一个线程处理它？ 线程可以“注册”它们感兴趣的某些信号， 因此当一个信号到达的时候， 可把它交给需要它的线程。

2.2.6 混合实现

人们已经研究了各种试图将用户级线程的优点和内核级线程的优点结合起来的方法。 一种方法是使用内核级线程， 然后将用户级线程与某些或者全部内核线程多路复用起来， 如图所示。 如果采用这种方法，编程人员可以决定有多少个内核级线程和多少个用户级线程彼此多路复用。 这一模型带来最大的灵活度。

2.2.7 调度程序激活机制

该机制工作的基本思路是， 当内核了解到一个线程被阻塞之后（例如， 由于执行了一个阻塞系统调用或者产生了一个页面故障） ， 内核通知该进程的运行时系统， 并且在堆栈中以参数形式传递有问题的线程编号和所发生事件的一个描述。 内核通过在一个已知的起始地址启动运行时系统， 从而发出了通知， 这是对UNIX中信号的一种粗略模拟。 这个机制称为上行调用（upcall） 。

2.2.8 弹出式线程

弹出式线程的关键好处是， 由于这种线程相当新， 没有历史——没有必须存储的寄存器、 堆栈诸如此类的内容， 每个线程从全新开始， 每一个线程彼此之间都完全一样。 这样， 就有可能快速创建这类线程。 对该新线程指定所要处理的消息。 使用弹出式线程的结果是， 消息到达与处理开始之间的时间非常短。

2.2.9 使单线程代码多线程化

一个线程的代码就像进程一样， 通常包含多个过程， 会有局部变量、 全局变量和过程参数。 局部变量和参数不会引起任何问题， 但是有一个问题是， 对线程而言是全局变量， 并不是对整个程序也是全局的。 有许多变量之所以是全局的， 是因为线程中的许多过程都使用它们（如同它们也可能使用任何全局变量一样） ， 但是其他线程在逻辑上和这些变量无关。

1.一种解决方案是为每个线程赋予其私有的全局变量。 在这个方案中， 每个线程有自己的errno以及其他全局变量的私有副本， 这样就避免了冲突。

2.还有另一种方案， 可以引入新的库过程， 以便创建、 设置和读取这些线程范围的全局变量。

3.另一种解决方案是， 为每个过程提供一个包装器， 该包装器设置一个二进制位从而标志某个库处于使用中。 在先前的调用还没有完成之前， 任何试图使用该库的其他线程都会被阻塞。 尽管这个方式可以工作， 但是它会极大地降低系统潜在的并行性。

2.3 进程间通信

进程经常需要与其他进程通信。 例如， 在一个shell管道中， 第一个进程的输出必须传送给第二个进程，这样沿着管道传递下去。 因此在进程之间需要通信， 而且最好使用一种结构良好的方式， 不要使用中断。 在下面几节中， 我们就来讨论一些有关进程间通信（Inter Process Communication， IPC） 的问题。

简要地说， 有三个问题。

1.第一个问题与上面的叙述有关， 即一个进程如何把信息传递给另一个。

2. 第二个要处理的问题是， 确保两个或更多的进程在关键活动中不会出现交叉， 例如， 在飞机订票系统中的两个进程为不同的客户试图争夺飞机上的最后一个座位。

3. 第三个问题与正确的顺序有关（如果该顺序是有关联的话） ， 比如， 如果进程A产生数据而进程B打印数据， 那么B在打印之前必须等待， 直到A已经产生一些数据。

2.3.1 竞争条件

在一些操作系统中， 协作的进程可能共享一些彼此都能读写的公用存储区。 这个公用存储区可能在内存中（可能是在内核数据结构中） ， 也可能是一个共享文件。

两个或多个进程读写某些共享数据， 而最后的结果取决于进程运行的

精确时序， 称为竞争条件（race condition） 。 调试包含有竞争条件的程序是一件很头痛的事。 大多数的测试运行结果都很好， 但在极少数情况下会发生一些无法解释的奇怪现象。

2.3.2 临界区

怎样避免竞争条件？ 实际上凡涉及共享内存、 共享文件以及共享任何资源的情况都会引发与前面类似的错误， 要避免这种错误， 关键是要找出某种途径来阻止多个进程同时读写共享的数据。 换言之， 我们需要的是互斥（mutual exclusion） ， 即以某种手段确保当一个进程在使用一个共享变量或文件时， 其他进程不能做同样的操作。

在某些时候进程可能需要访问共享内存或共享文件， 或执行另外一些会导致竞争的操作。 我们把对共享内存进行访问的程序片段称作临界区域（critical region） 或临界区（critical section） 。 如果我们能够适当地安排， 使得两个进程不可能同时处于临界区中， 就能够避免竞争条件。

尽管这样的要求避免了竞争条件， 但它还不能保证使用共享数据的并发进程能够正确和高效地进行协作。 对于一个好的解决方案， 需要满足以下4个条件：

1)任何两个进程不能同时处于其临界区。

2)不应对CPU的速度和数量做任何假设。

3)临界区外运行的进程不得阻塞其他进程。

4)不得使进程无限期等待进入临界区。

2.3.3 忙等待的互斥

本节将讨论几种实现互斥的方案。 在这些方案中， 当一个进程在临界区中更新共享内存时， 其他进程将

不会进入其临界区， 也不会带来任何麻烦。

1.屏蔽中断

在单处理器系统中， 最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断， 并在就要离开之前再打开中断。 屏蔽中断后， 时钟中断也被屏蔽。 CPU只有发生时钟中断或其他中断时才会进行进程切换， 这样， 在屏蔽中断之后CPU将不会被切换到其他进程。 于是， 一旦某个进程屏蔽中断之后， 它就可以检查和修改共享内存， 而不必担心其他进程介入。

缺点：

因为把屏蔽中断的权力交给用户进程是不明智的。 设想一下， 若一个进程屏蔽中断后不再打开中断， 其结果将会如何？ 整个系统可能会因此终止。 而且， 如果系统是多处理器（有两个或可能更多的处理器） ， 则屏蔽中断仅仅对执行disable指令的那个CPU有效。 其他CPU仍将继续运行， 并可以访问共享内存。

2.锁变量

作为第二种尝试， 可以寻找一种软件解决方案。 设想有一个共享（锁） 变量， 其初始值为0。 当一个进程想进入其临界区时， 它首先测试这把锁。 如果该锁的值为0， 则该进程将其设置为1并进入临界区。 若这把锁的值已经为1， 则该进程将等待直到其值变为0。 于是， 0就表示临界区内没有进程， 1表示已经有某个进程进入临界区。

缺点：

但是， 这种想法也包含了与假脱机目录一样的疏漏。 假设一个进程读出锁变量的值并发现它为0， 而恰好在它将其值设置为1之前， 另一个进程被调度运行， 将该锁变量设置为1。 当第一个进程再次能运行时， 它同样也将该锁设置为1， 则此时同时有两个进程进入临界区中。

3.严格轮换法

在图2-23中， 整型变量turn， 初始值为0， 用于记录轮到哪个进程进入临界区， 并检查或更新共享内存。开始时， 进程0检查turn， 发现其值为0， 于是进入临界区。 进程1也发现其值为0， 所以在一个等待循环中不停地测试turn， 看其值何时变为1。 连续测试一个变量直到某个值出现为止， 称为忙等待（busy waiting） 。

由于这种方式浪费CPU时间， 所以通常应该避免。

只有在有理由认为等待时间是非常短的情形下， 才使用忙等待。 用于忙等待的锁， 称为自旋锁（spin lock） 。

4.Peterson解法



在使用共享变量（即进入其临界区） 之前， 各个进程使用其进程号0或1作为参数来调用enter_region。该调用在需要时将使进程等待， 直到能安全地进入临界区。 在完成对共享变量的操作之后， 进程将调用leave_region， 表示操作已完成， 若其他的进程希望进入临界区， 则现在就可以进入。

5.TSL指令

现在来看需要硬件支持的一种方案。 某些计算机中， 特别是那些设计为多处理器的计算机， 都有下面一条指令：


TSL RX,LOCK

称为测试并加锁（Test and Set Lock） ， 它将一个内存字lock读到寄存器RX中， 然后在该内存地址上存一个非零值。 读字和写字操作保证是不可分割的， 即该指令结束之前其他处理器均不允许访问该内存字。 执行TSL指令的CPU将锁住内存总线， 以禁止其他CPU在本指令结束之前访问内存。

2.3.4 睡眠与唤醒

Peterson解法和TSL或XCHG解法都是正确的， 但它们都有忙等待的缺点。 这些解法在本质上是这样的：

当一个进程想进入临界区时， 先检查是否允许进入， 若不允许， 则该进程将原地等待， 直到允许为止。

这种方法不仅浪费了CPU时间， 而且还可能引起预想不到的结果。 考虑一台计算机有两个进程， H优先级较高， L优先级较低。 调度规则规定， 只要H处于就绪态它就可以运行。 在某一时刻， L处于临界区中， 此时H变到就绪态， 准备运行（例如， 一条I/O操作结束） 。 现在H开始忙等待， 但由于当H就绪时L不会被调度， 也就无法离开临界区， 所以H将永远忙等待下去。 这种情况有时被称作优先级反转问题（priority inversion problem） 。

生产者-消费者问题

2.3.5 信号量

信号量是E.W.Dijkstra在1965年提出的一种方法， 它使用一个整型变量来累计唤醒次数， 供以后使用。

在他的建议中引入了一个新的变量类型， 称作信号量（semaphore） 。 一个信号量的取值可以为0（表示没有保存下来的唤醒操作） 或者为正值（表示有一个或多个唤醒操作） 。

Dijkstra建议设立两种操作： down和up（分别为一般化后的sleep和wakeup） 。 对一信号量执行down操作， 则是检查其值是否大于0。 若该值大于0， 则将其值减1（即用掉一个保存的唤醒信号） 并继续； 若该值为0， 则进程将睡眠， 而且此时down操作并未结束。 检查数值、 修改变量值以及可能发生的睡眠操作均作为一个单一的、 不可分割的原子操作完成。 保证一旦一个信号量操作开始， 则在该操作完成或阻塞之前， 其他进程均不允许访问该信号量。 这种原子性对于解决同步问题和避免竞争条件是绝对必要的。

2.3.6 互斥量

如果不需要信号量的计数能力， 有时可以使用信号量的一个简化版本， 称为互斥量（mutex） 。 互斥量仅仅适用于管理共享资源或一小段代码。 由于互斥量在实现时既容易又有效， 这使得互斥量在实现用户空间线程包时非常有用。

互斥量是一个可以处于两态之一的变量： 解锁和加锁。 这样， 只需要一个二进制位表示它， 不过实际上， 常常使用一个整型量， 0表示解锁， 而其他所有的值则表示加锁。 互斥量使用两个过程。 当一个线程（或进程） 需要访问临界区时， 它调用mutex_lock。 如果该互斥量当前是解锁的（即临界区可用） ， 此调用成功， 调用线程可以自由进入该临界区。

2.3.7 管程

为了更易于编写正确的程序， Brinch Hansen（1973） 和Hoare（1974） 提出了一种高级同步原语， 称为管程（monitor） 。

一个管程是一个由过程、

变量及数据结构等组成的一个集合， 它们组成一个特殊的模块或软件包。 进程可在任何需要的时候调用管程中的过程， 但它们不能在管程之外声明的过程中直接访问管程内的数据结构。

与管程和信号量有关的另一个问题是， 这些机制都是设计用来解决访问公共内存的一个或多个CPU上的互斥问题的。 通过将信号量放在共享内存中并用TSL或XCHG指令来保护它们， 可以避免竞争。 如果一个分布式系统具有多个CPU， 并且每个CPU拥有自己的私有内存， 它们通过一个局域网相连， 那么这些原语将失效。

2.3.8 消息传递

上面提到的其他的方法就是消息传递（message passing） 。 这种进程间通信的方法使用两条原语send和receive， 它们像信号量而不像管程， 是系统调用而不是语言成分。 因此， 可以很容易地将它们加入到库例程中去。

2.3.9 屏障

最后一个同步机制是准备用于进程组而不是用于双进程的生产者-消费者类情形的。 在有些应用中划分了若干阶段， 并且规定， 除非所有的进程都就绪准备着手下一个阶段， 否则任何进程都不能进入下一个阶段。 可以通过在每个阶段的结尾安置屏障（barrier） 来实现这种行为。 当一个进程到达屏障时， 它就被屏障阻拦， 直到所有进程都到达该屏障为止。

2.4 调度

当计算机系统是多道程序设计系统时， 通常就会有多个进程或线程同时竞争CPU。 只要有两个或更多的进程处于就绪状态， 这种情形就会发生。 如果只有一个CPU可用， 那么就必须选择下一个要运行的进程。 在操作系统中， 完成选择工作的这一部分称为调度程序（scheduler）， 该程序使用的算法称为调度算法（scheduling algorithm） 。

2.4.1 调度介绍

1.进程行为

几乎所有进程的（磁盘） I/O请求或计算都是交替突发的， 如图2-38所示。



某些进程（图2-38a的进程） 花费了绝大多数时间在计算上， 而其他

进程（图2-38b的进程） 则在等待I/O上花费了绝大多数时间。 前者称为计算密集型（compute-bound） ， 后者称为I/O密集型（I/O-bound） 。

2.何时调度

第一， 在创建一个新进程之后， 需要决定是运行父进程还是运行子进程。

第二， 在一个进程退出时必须做出调度决策。 一个进程不再运行（因为它不再存在） ， 所以必须从就绪进程集中选择另外某个进程。 如果没有就绪的进程， 通常会运行一个系统提供的空闲进程。

第三， 当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时， 必须选择另一个进程运行。

第四， 在一个I/O中断发生时， 必须做出调度决策。

3.调度算法分类

1)批处理。

在批处理系统中， 不会有用户不耐烦地在终端旁等待一个短请求的快捷响应。 因此， 非抢占式算法， 或对每个进程都有长时间周期的抢占式算法， 通常都是可接受的。

2)交互式。

在交互式用户环境中， 为了避免一个进程霸占CPU拒绝为其他进程服务， 抢占是必需的。 即便没有进程想永远运行， 但是， 某个进程由于一个程序错误也可能无限期地排斥所有其他进程。 为了避免这种现象发生， 抢占也是必要的。 服务器也归于此类， 因为通常它们要服务多个突发的（远程） 用户。

3)实时。

然而在有实时限制的系统中， 抢占有时是不需要的， 因为进程了解它们可能会长时间得不到运行， 所以通常很快地完成各自的工作并阻塞。实时系统与交互式系统的差别是， 实时系统只运行那些用来推进现有应用的程序， 而交互式系统是通用的， 它可以运行任意的非协作甚至是有恶意的程序。

4.调度算法的目标

2.4.2 批处理系统中的调度

1.先来先服务

所有调度算法中， 最简单的是非抢占式的先来先服务（first-come first-severd） 算法。 使用该算法， 进程按照它们请求CPU的顺序使用CPU。

这个算法的主要优点是易于理解并且便于在程序中运用。

2.最短作业优先

3.最短剩余时间优先

最短作业优先的抢占式版本是最短剩余时间优先（shortest remaining time next） 算法。 使用这个算法，调度程序总是选择剩余运行时间最短的那个进程运行。

2.4.3 交互式系统中的调度

1.轮转调度

一种最古老、 最简单、 最公平且使用最广的算法是轮转调度（round robin） 。 每个进程被分配一个时间段， 称为时间片（quantum） ， 即允许该进程在该时间段中运行。 如果在时间片结束时该进程还在运行，则将剥夺CPU并分配给另一个进程。

2.优先级调度

每个进程被赋予一个优先级， 允许优先级最高的可运行进程先运行。

3.多级队列

4.最短进程优先

可以通过首先运行最短的作业来使响应时间最短。

5.保证调度

一种完全不同的调度算法是向用户作出明确的性能保证， 然后去实现它。

6.彩票调度

有一个既可给出类似预测结果而又有非常简单的实现方法的算法， 这个算法称为彩票调度（lottery scheduling）

7.公平分享调度

到现在为止， 我们假设被调度的都是各个进程自身， 并不关注其所有者是谁。 这样做的结果是， 如果用户1启动9个进程而用户2启动1个进程， 使用轮转或相同优先级调度算法， 那么用户1将得到90%的CPU时间， 而用户2只得到10%的CPU时间。

2.4.4 实时系统中的调度

实时系统是一种时间起着主导作用的系统。

实时系统通常可以分为硬实时（hard real time） 和软实时（soft real time） ， 前者的含义是必须满足绝对的截止时间， 后者的含义是虽然不希望偶尔错失截止时间， 但是可以容忍。

2.4.5 策略和机制

一个进程有许多子进程并在其控制下运行。 主进程完全可能掌握哪一个子进程最重要（或最紧迫） 而哪一个最不重要。 但是， 以上讨论的调度算法中没有一个算法从用户进程接收有关的调度决策信息， 这就导致了调度程序很少能够做出最优的选择。

2.4.6 线程调度

当若干进程都有多个线程时， 就存在两个层次的并行： 进程和线程。 在这样的系统中调度处理有本质差别， 这取决于所支持的是用户级线程还是内核级线程（或两者都支持） 。

用户级线程和内核级线程之间的差别在于性能。 用户级线程的线程切换需要少量的机器指令， 而内核级线程需要完整的上下文切换， 修改内存映像， 使高速缓存失效， 这导致了若干数量级的延迟。 另一方面， 在使用内核级线程时， 一旦线程阻塞在I/O上就不需要像在用户级线程中那样将整个进程挂起。

另一个重要因素是用户级线程可以使用专为应用程序定制的线程调度程序。

2.5 经典的IPC问题

2.5.1 哲学家就餐问题

五个哲学家围坐在一张圆桌周围， 每个哲学家面前都有一盘通心粉。 由于通心粉很滑， 所以需要两把叉子才能夹住。 相邻两个盘子之间放有一把叉子， 餐桌如图2-44所示。



原理：仅当哲学家的左右两支筷子都可用时，才允许他拿起筷子进餐。可以利用AND 型信号量机制实现，也可以利用信号量的保护机制实现。利用信号量的保护机制实现的思想是通过记录型信号量mutex对取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。

2.5.2 读者-写者问题

例如， 设想一个飞机订票系统， 其中有许多竞争的进程试图读写其中的数据。 多个进程同时读数据库是可以接受的， 但如果一个进程正在更新（写） 数据库， 则所有的其他进程都不能访问该数据库， 即使读操作也不行。 这里的问题是如何对读者和写者进行编程？

在一个读者到达， 且一个写者在等待时， 读者在写者之后被挂起， 而不是立即允许进入。

第3章 存储管理

3.1 无存储器抽象

最简单的存储器抽象就是根本没有抽象。 早期大型计算机（20世纪60年代之前） 、 小型计算机（20世纪70年代之前） 和个人计算机（20世纪80年代之前） 都没有存储器抽象。 每一个程序都直接访问物理内存。 当

一个程序执行如下指令：

MOV REGISTER1,1000

计算机会将位置为1000的物理内存中的内容移到REGISTER1中。 因此， 那时呈现给编程人员的存储器模型就是简单的物理内存： 从0到某个上限的地址集合， 每一个地址对应一个可容纳一定数目二进制位的存储单元， 通常是8个。

3.2 一种存储器抽象： 地址空间

总之， 把物理地址暴露给进程会带来下面几个严重问题。

第一， 如果用户程序可以寻址内存的每个字节， 它们就可以很容易地（故意地或偶然地） 破坏操作系统， 从而使系统慢慢地停止运行（除非有特殊的硬件进行保护， 如IBM 360的锁键模式） 。

第二， 使用这种模型， 想要同时（如果只有一个CPU就轮流执行） 运行多个程序是很困难的。

在系统中没有对物理内存的抽象的情况下， 很难做到上述情景， 因此， 我们需要其他办法。

3.2.1 地址空间的概念

地址空间是一个进程可用于寻址内存的一套地址集合。 每个进程都有一个自己的地址空间， 并且这个地址空间独立于其他进程的地址空间（除了在一些特殊情况下进程需要共享它们的地址空间外） 。

基址寄存器与界限寄存器

当一个进程运行时， 程序的起始物理地址装载到基址寄存器中， 程序的长度装载到界限寄存器中。 使用基址寄存器和界限寄存器是给每个进程提供私有地址空间的非常容易的方法， 因为每个内存地址在送到内存之前， 都会自动先加上基址寄存器的内容。

3.2.2 交换技术

有两种处理内存超载的通用方法。 最简单的策略是交换（swapping） 技术， 即把一个进程完整调入内存， 使该进程运行一段时间， 然后把它存回磁盘。 空闲进程主要存储在磁盘上， 所以当它们不运行时就不会占用内存（尽管它们的一些进程会周期性地被唤醒以完成相关工作， 然后就又进入睡眠状态） 。

另一种策略是虚拟内存（virtual memory） ， 该策略甚至能使程序在只有一部分被调入内存的情况下运行。

3.2.3 空闲内存管理

在动态分配内存时， 操作系统必须对其进行管理。 一般而言， 有两种方式跟踪内存使用情况： 位图和空闲链表。

1.使用位图的存储管理

使用位图方法时， 内存可能被划分成小到几个字或大到几千字节的分配单元。 每个分配单元对应于位图中的一位， 0表示空闲， 1表示占用（或者相反） 。

2.使用链表的存储管理

另一种记录内存使用情况的方法是， 维护一个记录已分配内存段和空闲内存段的链表。 其中链表中的一个结点或者包含一个进程， 或者是两个进程间的一个空的空闲区。

3.3 虚拟内存

虚拟内存的基本思想是： 每个程序拥有自己的地址空间， 这个空间被分割成多个块， 每一块称作一页或页面（page） 。 每一页有连续的

地址范围。 这些页被映射到物理内存， 但并不是所有的页都必须在内存中才能运行程序。 当程序引用到一部分在物理内存中的地址空间时， 由硬件立刻执行必要的映射。 当程序引用到一部分不在物理内存中的地址空间时， 由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

3.4 页面置换算法

3.4.10 页面置换算法小结

3.5 分页系统中的设计问题

3.5.1 局部分配策略与全局分配策略

第4章 文件系统

文件是进程创建的信息逻辑单元。 一个磁盘一般含有几千甚至几百万个文件， 每个文件是独立于其他文件的。 文件不仅仅被用来对磁盘建模， 以替代对随机存储器（ RAM） 的建模， 事实上， 如果能把每个文件看成一种地址空间， 那么读者就离理解文件的本质不远了。

4.1 文件

4.1.1 文件命名

文件的具体命名规则在各个系统中是不同的， 不过所有的现代操作系统都允许用1至8个字母组成的字符串作为合法的文件名。

有的文件系统区分大小写字母， 有的则不区分。 UNIX是前一类， MS-DOS是后一类。

4.1.2 文件结构

文件可以有多种构造方式， 在图4-2中列出了常用的三种方式。 图4-2a中的文件是一种无结构的字节序列， 操作系统事实上不知道也不关心文件内容是什么， 操作系统所见到的就是字节， 其任何含义只在用户程序中解释。 在UNIX和Windows中都采用这种方法。

4.1.3 文件类型

很多操作系统支持多种文件类型。 如UNIX和Windows中都有普通文件和目录， UNIX还有字符特殊文件（character special file） 和块特殊文件（block special file） 。

4.1.4 文件存取

早期操作系统只有一种文件存取方式： 顺序存取（sequential access） 。 进程在这些系统中可从头顺序读取文件的全部字节或记录， 但不能跳过某一些内容， 也不能不按顺序读取。 顺序存取文件是可以返回到起点的， 需要时可多次读取该文件。 在存储介质是磁带而不是磁盘时， 顺序存取文件是很方便的。

当用磁盘来存储文件时， 我们可以不按顺序地读取文件中的字节或记录， 或者按照关键字而不是位置来存取记录。 这种能够以任何次序读取其中字节或记录的文件称作随机存取文件（random access file） 。 许多应用程序需要这种类型的文件。

4.1.5 文件属性

文件都有文件名和数据。 另外， 所有的操作系统还会保存其他与文件相关的信息， 如文件创建的日期和时间、 文件大小等。 这些附加信息称为文件属性（attribute） ， 有些人称之为元数据（metadata） 。

4.1.6 文件操作

4.2 目录

文件系统通常提供目录或文件夹用于记录文件， 在很多系统中目录本身也是文件。 本节讨论目录、 目录的组成、 目录的特性和可以对目录进行的操作。

4.2.1 一级目录系统

目录系统的最简单形式是在一个目录中包含所有的文件。 这有时称为根目录， 但是由于只有一个目录，所以其名称并不重要。

4.2.2 层次目录系统

所需要的是层次结构（即， 一个目录树） 。 通过这种方式， 可以用很多目录把文件以自然的方式分组。

4.2.3 路径名

用目录树组织文件系统时， 需要有某种方法指明文件名。 常用的方法有两种。 第一种是， 每个文件都赋予一个绝对路径名（absolute path name） ，它由从根目录到文件的路径组成。

另一种指定文件名的方法是使用相对路径名（relative path name） 。 它常和工作目录（working directory） （也称作当前目录（current directory） ） 一起使用。

这时， 所有的不从根目录开始的路径名都是相对于工作目录的。

4.2.4 目录操作

4.3 文件系统的实现

4.3.1 文件系统布局

4.3.2 文件的实现

1.连续分配

最简单的分配方案是把每个文件作为一连串连续数据块存储在磁盘上。

连续磁盘空间分配方案有两大优势。

首先， 实现简单， 记录每个文件用到的磁盘块简化为只需记住两个数字即可： 第一块的磁盘地址和文件的块数。 给定了第一块的编号， 一个简单的加法就可以找到任何其他块的编号.

其次， 读操作性能较好， 因为在单个操作中就可以从磁盘上读出整个文件。 只需要一次寻找（对第一个块）。

连续分配方案也同样有相当明显的不足之处： 随着时间的推移， 磁盘会变得零碎。

2.链表分配

存储文件的第二种方法是为每个文件构造磁盘块链表， 如图4-11所示。 每个块的第一个字作为指向下一块的指针， 块的其他部分存放数据。

与连续分配方案不同， 这一方法可以充分利用每个磁盘块。 不会因为磁盘碎片（除了最后一块中的内部碎片） 而浪费存储空间。

3.在内存中采用表的链表分配

如果取出每个磁盘块的指针字， 把它放在内存的一个表中， 就可以解决上述链表的两个不足。

4.i节点

最后一个记录各个文件分别包含哪些磁盘块的方法是给每个文件赋予一个称为i节点（index-node） 的数据结构， 其中列出了文件属性和文件块的磁盘地址。

4.3.3 目录的实现

在读文件前， 必须先打开文件。 打开文件时， 操作系统利用用户给出的路径名找到相应目录项。 目录项

中提供了查找文件磁盘块所需要的信息。

4.3.4 共享文件

当几个用户同在一个项目里工作时， 他们常常需要共享文件。 其结果是， 如果一个共享文件同时出现在

属于不同用户的不同目录下， 工作起来就很方便。

共享文件是方便的， 但也带来一些问题。 如果目录中包含磁盘地址， 则当连接文件时， 必须把C目录中的磁盘地址复制到B目录中。 如果B或C随后又往该文件中添加内容， 则新的数据块将只列入进行添加工作的用户的目录中。 其他的用户对此改变是不知道的。 所以违背了共享的目的。

有两种方法可以解决这一问题。 在第一种解决方案中， 磁盘块不列入目录， 而是列入一个与文件本身关联的小型数据结构中。 目录将指向这个小型数据结构。 这是UNIX系统中所采用的方法（小型数据结构即是i节点） 。

在第二种解决方案中， 通过让系统建立一个类型为LINK的新文件， 并把该文件放在B的目录下， 使得B与C的一个文件存在连接。 新的文件中只包含了它所连接的文件的路径名。 当B读该连接文件时， 操作系统查看到要读的文件是LINK类型， 则找到该文件所连接的文件的名字， 并且去读那个文件。 与传统（硬） 连接相对比起来， 这一方法称为符号连接（symbolic linking） 。

4.3.5 日志结构文件系统

LFS的设计者决定重新实现一种UNIX文件系统， 该系统即使对于一个大部分由零碎的

随机写操作组成的任务， 同样能够充分利用磁盘的带宽。 其基本思想是将整个磁盘结构化为一个日志。 每隔一段时间， 或是有特殊需要时， 被缓冲在内存中的所有未决的写操作都被放到一个单独的段中， 作为在日志末尾的一个邻接段写入磁盘。

4.3.6 日志文件系统

虽然基于日志结构的文件系统是一个很吸引人的想法， 但是由于它们和现有的文件系统不相匹配， 所以还没有被广泛应用。 尽管如此， 它们内在的一个思想， 即面对出错的鲁棒性， 却可以被其他文件系统所借鉴。 这里的基本想法是保存一个用于记录系统下一步将要做什么的日志。 这样当系统在完成们即将完成的任务前崩溃时， 重新启动后， 可以通过查看日志， 获取崩溃前计划完成的任务， 并完成它们。 这样的文件系统被称为日志文件系统， 并已经被实际应用。

4.3.7 虚拟文件系统

所有和文件相关的系统调用在最初的处理上都指向虚拟文件系统。 这些来自用户进程的调用， 都是标准的POSIX系统调用， 比如open、 read write和lseek等。 因此， 虚拟文件系统对用户进程有一个“更高层”接口，它就是著名的POSIX接口。

4.4 文件系统管理和优化

4.4.1 磁盘空间管理

文件通常存放在磁盘上， 所以对磁盘空间的管理是系统设计者要考虑的一个主要问题。 存储n个字节的文件可以有两种策略： 分配n个字节的连续磁盘空间， 或者把文件分成很多个连续（或并不一定连续） 的块。 在存储管理系统中， 分段处理和分页处理之间也要进行同样的权衡。

正如我们已经见到的， 按连续字节序列存储文件有一个明显问题， 当文件扩大时， 有可能需要在磁盘上移动文件。 内存中分段也有同样的问题。 不同的是， 相对于把文件从磁盘的一个位置移动到另一个位置， 内存中段的移动操作要快得多。 因此， 几乎所有的文件系统都把文件分割成固定大小的块来存储， 各块之间不一定相邻。

1. 块大小
   
   分配单位很小意味着每个文件由很多块组成， 每读一块都有寻道和旋转延迟时间， 所以， 读
   
   取由很多小块组成的文件会非常慢。
2. 记录空闲块
   
   第一种
   
   方法是采用磁盘块链表， 每个块中包含尽可能多的空闲磁盘块号。
   
   第二种
   
   另一种空闲磁盘空间管理的方法是采用位图。n个块的磁盘需要n位位图。
3. 磁盘配额
   
   为了防止人们贪心而占有太多的磁盘空间， 多用户操作系统常常提供一种强制性磁盘配额机制。 其思想是系统管理员分给每个用户拥有文件和块的最大数量， 操作系统确保每个用户不超过分给他们的配额。

4.4.2 文件系统备份

• 物理转储
  
  物理转储的主要优点是简单、 极为快速（基本上是以磁盘的速度运行） 。 主要缺点是， 既不能跳过选定的目录， 也无法增量转储， 还不能满足恢复个人文件的请求。 正因如此， 绝大多数配置都使用逻辑转储。
• 逻辑转储
  
  逻辑转储从一个或几个指定的目录开始， 递归地转储其自给定基准日期（例如， 最近一次增量转储或全面系统转储的日期） 后有所更改的全部文件和目录。

4.4.3 文件系统的一致性

影响文件系统可靠性的另一个问题是文件系统的一致性。 很多文件系统读取磁盘块， 进行修改后， 再写回磁盘。 如果在修改过的磁盘块全部写回之前系统崩溃， 则文件系统有可能处于不一致状态。

4.4.4 文件系统性能

1. 高速缓存
   
   常用的减少磁盘访问次数技术是块高速缓存（block cache） 或者缓冲区高速缓存（buffer cache） 。
   
   常用的算法是： 检查全部的读请求， 查看在高速缓存中是否有所需要的块。 如果存在， 可执行读操作而无须访问磁盘。 如果该块不在高速缓存中， 首先要把它读到高速缓存， 再复制到所需地方。
2. 块提前读
   
   第二个明显提高文件系统性能的技术是： 在需要用到块之前， 试图提前将其写入高速缓存， 从而提高命中率。
3. 减少磁盘臂运动
   
   另一种重要技术是把有可能顺序存取的块放在一起， 当然最好是在同一个柱面上， 从而减少磁盘臂的移动次数。

4.4.5 磁盘碎片整理

所有的空闲磁盘空间放在一个单独的、 与被安装的文件邻近的单元里。 但随着时间的流逝， 文件被不断地创建与删除， 于是磁盘会产生很多碎片， 文件与空穴到处都是。 结果是， 当创建一个新文件时， 它使用的块会散布在整个磁盘上， 造成性能的降低。

4.5 文件系统实例

4.5.1 CD-ROM文件系统

1. ISO 9660文件系统
   
   最普遍的一种CD-ROM文件系统的标准是1988年被采纳的名为ISO 9660的国际标准。 实际上现在市场上的所有CD-ROM都支持这个标准， 有的则带有一些扩展（下面会对此进行讨论） 。 这个标准的一个目标就是使CD-ROM独立于机器所采用的字节顺序和使用的操作系统， 即在所有的机器上都是可读的。
2. Rock Ridge扩展
3. Joliet扩展

4.5.2 MS-DOS文件系统

MS-DOS按32位的数字存储文件的大小， 所以理论上文件大小能够大至4GB。

第5章 输入/输出

5.1 I/O硬件原理

5.1.1 I／O设备

I/O设备大致可以分为两类： 块设备（block device） 和字符设备（character device） 。


块设备


块设备把信息存储在固定大小的块中， 每个块有自己的地址。 通常块的大小在512字节至32 768字节之间。 所有传输以一个或多个完整的（连续的） 块为单位。 块设备的基本特征是每个块都能独立于其他块而读写。

硬盘、 CD-ROM和USB盘是最常见的块设备。

字符设备


字符设备以字符为单位发送或接收一个字符流， 而不考虑任何块结构。 字符设备是不可寻址的， 也没有任何寻道操作。 打印机、 网络接口、 鼠标（用作指点设备） 、 老鼠（用作心理学实验室实验） ， 以及大多数与磁盘不同的设备都可看作是字符设备。

5.1.2 设备控制器

5.1.3 内存映射I／O

每个控制器有几个寄存器用来与CPU进行通信。 通过写入这些寄存器， 操作系统可以命令设备发送数

据、 接收数据、 开启或关闭， 或者执行某些其他操作。 通过读取这些寄存器， 操作系统可以了解设备的状

态， 是否准备好接收一个新的命令等。

5.1.4 直接存储器存取

无论一个CPU是否具有内存映射I/O，它都需要寻址设备控制器以便与它们交换数据。CPU可以从I/O控制器每次请求一个字节的数据，但是这样做浪费CPU的时间，所以经常用到一种称为直接存储器存取（Direct Memory Access，DMA）

5.1.5 重温中断

当一个I/O设备完成交给它的工作时，它就产生一个中断（假设操作系统已经开放中断），它是通过在分配给它的一条总线信号线上置起信号而产生中断的。该信号被主板上的中断控制器芯片检测到，由中断控制器芯片决定做什么。

5.2 I／O软件原理

5.2.1 I／O软件的目标

1. 设备独立性
   
   在设计I/O软件时一个关键的概念是设备独立性（device independence）。它的意思是应该能够编写出这样的程序：它可以访问任意I/O设备而无需事先指定设备。
2. 错误处理
   
   一般来说，错误应该尽可能地在接近硬件的层面得到处理。
3. 同步（synchronous）（即阻塞）和异步（asynchronous）（即中断驱动）传输
   
   大多数物理I/O是异步的——CPU启动传输后便转去做其他工作，直到中断发生。如果I/O操作是阻塞的，那么用户程序就更加容易编写——在read系统调用之后，程序将自动被挂起，直到缓冲区中的数据准备好。正是操作系统使实际上是中断驱动的操作变为在用户程序看来是阻塞式的操作。
4. 缓冲（buffering）
   
   数据离开一个设备之后通常并不能直接存放到其最终的目的地。例如，从网络上进来一个数据包时，直到将该数据包存放在某个地方并对其进行检查，操作系统才知道要将其置于何处。

5.2.2 程序控制I／O

I/O的最简单形式是让CPU做全部工作，这一方法称为程序控制I/O（programmed I/O）。

借助于例子来说明程序控制I/O是最简单的。考虑一个用户进程，该进程想在打印机上打印8个字符的字符串“ABCDEFGH”。它首先要在用户空间的一个缓冲区中组装字符串，如图5-7a所示。

操作系统相继采取的操作总结在图5-8中。首先，数据被复制到内核空间。然后，操作系统进入一个密闭的循环，一次输出一个字符。在该图中，清楚地说明了程序控制I/O的最根本的方面，这就是输出一个字符之后，CPU要不断地查询设备以了解它是否就绪准备接收另一个字符。这一行为经常称为轮询（polling）或忙等待（busy waiting）。

程序控制I/O十分简单但是有缺点，即直到全部I/O完成之前要占用CPU的全部时间。

5.2.3 中断驱动I／O

允许CPU在等待打印机变为就绪的同时做某些其他事情的方式就是使用中断。

5.2.4 使用DMA的I／O

中断驱动I/O的一个明显缺点是中断发生在每个字符上。中断要花费时间，所以这一方法将浪费一定数量的CPU时间。这一问题的一种解决方法是使用DMA。

本质上，DMA是程序控制I/O，只是由DMA控制器而不是主CPU做全部工作。这一策略需要特殊的硬件（DMA控制器），但是使CPU获得自由从而可以在I/O期间做其他工作。

5.3 I／O软件层次

I/O软件通常组织成四个层次，如图5-11所示。每一层具有一个要执行的定义明确的功能和一个的定义明确的与邻近层次的接口。

5.3.1 中断处理程序

当中断发生时，中断处理程序将做它必须要做的全部工作以便对中断进行处理。然后，它可以将启动中断的驱动程序解除阻塞。

中断处理远不是无足轻重的小事。它要花费相当多的CPU指令，特别是在存在虚拟内存并且必须设置页表或者必须保存MMU状态（例如R和M位）的机器上。在某些机器上，当在用户态与核心态之间切换时，可能还需要管理TLB和CPU高速缓存，这就要花费额外的机器周期。

5.3.2 设备驱动程序

每个连接到计算机上的I/O设备都需要某些设备特定的代码来对其进行控制。这样的代码称为设备驱动程序（device driver），它一般由设备的制造商编写并随同设备一起交付。

5.3.3 与设备无关的I／O软件

虽然I/O软件中有一些是设备特定的，但是其他部分I/O软件是与设备无关的。

5.3.4 用户空间的I／O软件

尽管大部分I/O软件都在操作系统内部，但是仍然有一小部分在用户空间，包括与用户程序连接在一起的库，甚至完全运行于内核之外的程序。系统调用（包括I/O系统调用）通常由库过程实现。

5.4 盘

5.4.1 盘的硬件

1. 磁盘
2. RAID
   
   廉价磁盘冗余阵列
3. .CD-ROM
4. 可刻录CD

5.4.2 磁盘格式化

硬盘由一叠铝的、合金的或玻璃的盘片组成，直径为5.25英寸或3.5英寸（在笔记本电脑上甚至更小）。

在每个盘片上沉积着薄薄的可磁化的金属氧化物。

5.4.3 磁盘臂调度算法

5.4.4 错误处理

5.4.5 稳定存储器

5.5 时钟

时钟（clock）又称为定时器（timer），由于各种各样的原因决定了它对于任何多道程序设计系统的操作都是至关重要的。

5.5.1 时钟硬件

比较简单的时钟被连接到110V或220V的电源线上，这样每个电压周期产生一个中断，频率是50Hz或60Hz。

另一种类型的时钟由三个部件构成：晶体振荡器、计数器和存储寄存器，如图5-32所示。当把一块石英晶体适当地切割并且安装在一定的压力之下时，它就可以产生非常精确的周期性信号，典型的频率范围是几百兆赫兹，具体的频率值与所选的晶体有关。

5.5.2 时钟软件

时钟硬件所做的全部工作是根据已知的时间间隔产生中断。涉及时间的其他所有工作都必须由软件——时钟驱动程序完成。时钟驱动程序的确切任务因操作系统而异，但通常包括下面的大多数任务：

1)维护日时间。

2)防止进程超时运行。

3)对CPU的使用情况记账。

4)处理用户进程提出的alarm系统调用。

5)为系统本身的各个部分提供监视定时器。

6)完成概要剖析、监视和统计信息收集。

5.5.3 软定时器

5.6 用户界面：键盘、鼠标和监视器

5.6.1 输入软件

1. 键盘软件
2. 鼠标软件

5.6.2 输出软件

1. 文本窗口
2. X窗口系统
3. 图形用户界面
4. 位图
5. 字体

5.7 瘦客户机

5.8 电源管理

5.8.1 硬件问题

5.8.2 操作系统问题

5.8.3 应用程序问题

5.9 有关输入／输出的研究

5.10 小结

习题

第6章 死锁

6.1 资源

资源就是随着时间的推移， 必须能获得、 使用以及释放的任何东西。

6.1.1 可抢占资源和不可抢占资源

资源分为两类： 可抢占的和不可抢占的。 可抢占资源（preemptable resource） 可以从拥有它的进程中抢占而不会产生任何副作用， 存储器就是一类可抢占的资源。

不可抢占资源（nonpreemptable resource） 是指在不引起相关的计算失败的情况下， 无法把它从占有它的进程处抢占过来。

总的来说， 死锁和不可抢占资源有关， 有关可抢占资源的潜在死锁通常可以通过在进程之间重新分配资源而化解。 所以， 我们的重点放在不可抢占资源上。

使用一个资源所需要的事件顺序可以用抽象的形式表示如下：

1)请求资源。

2)使用资源。

3)释放资源。

6.1.2 资源获取

6.2 死锁概述

如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件， 那么， 该进程集合就是死锁的。

6.2.1 资源死锁的条件

死锁的四个必要条件：

1)互斥条件。 每个资源要么已经分配给了一个进程， 要么就是可用的。

2)占有和等待条件。 已经得到了某个资源的进程可以再请求新的资源。

3)不可抢占条件。 已经分配给一个进程的资源不能强制性地被抢占， 它只能被占有它的进程显式地释放。

4)环路等待条件。 死锁发生时， 系统中一定有由两个或两个以上的进程组成的一条环路， 该环路中的每个进程都在等待着下一个进程所占有的资源。

6.2.2 死锁建模

有四种处理死锁的策略：

1)忽略该问题。 也许如果你忽略它， 它也会忽略你。

2)检测死锁并恢复。 让死锁发生， 检测它们是否发生， 一旦发生死锁， 采取行动解决问题。

3)仔细对资源进行分配， 动态地避免死锁。

4)通过破坏引起死锁的四个必要条件之一， 防止死锁的产生。

6.3 鸵鸟算法

最简单的解决方法是鸵鸟算法： 把头埋到沙子里， 假装根本没有问题发生 。

6.4 死锁检测和死锁恢复

第二种技术是死锁检测和恢复。 在使用这种技术时， 系统并不试图阻止死锁的产生， 而是允许死锁发生， 当检测到死锁发生后， 采取措施进行恢复。 本节我们将考察检测死锁的几种方法以及恢复死锁的几种方法。

6.4.1 每种类型一个资源的死锁检测

这一算法是依次将每一个节点作为一棵树的根节点， 并进行深度优先搜索。 如果再次碰到已经遇到过的节点， 那么就算找到了一个环。 如果从任何给定的节点出发的弧都被穷举了， 那么就回溯到前面的节点。 如果回溯到根并且不能再深入下去， 那么从当前节点出发的子图中就不包含任何环。 如果所有的节点都是如此， 那么整个图就不存在环， 也就是说系统不存在死锁。

6.4.2 每种类型多个资源的死锁检测

如果有多种相同的资源存在， 就需要采用另一种方法来检测死锁。 现在我们提供一种基于矩阵的算法来检测从P1 到Pn 这n个进程中的死锁。 假设资源的类型数为m， E1 代表资源类型1， E2 代表资源类型2， Ei 代表资源类型i(1≤i≤m)。 E是现有资源向量（existing resource vector） ， 代表每种已存在的资源总数。 比如， 如果资源类型1代表磁带机， 那么E1 =2就表示系统有两台磁带机。

在任意时刻， 某些资源已被分配所以不可用。 假设A是可用资源向量（available resource vector） ， 那么Ai 表示当前可供使用的资源数（即没有被分配的资源） 。 如果仅有的两台磁带机都已经分配出去了， 那么A1 的值为0。

现在我们需要两个数组： C代表当前分配矩阵（current allocation matrix） ， R代表请求矩阵（request matrix） 。 C的第i行代表Pi 当前所持有的每一种类型资源的资源数。 所以， Cij 代表进程i所持有的资源j的数量。 同理， Rij 代表Pi 所需要的资源j的数量。 这四种数据结构如图6-6所示。

这四种数据结构之间有一个重要的恒等式。 具体地说， 某种资源要么已分配要么可用。 这个结论意味着：

换言之， 如果我们将所有已分配的资源j的数量加起来再和所有可供使用的资源数相加， 结果就是该类资源的资源总数。

第1个不能被满足， 因为没有CDROM驱动器可供使用。

第2个也不能被满足， 由于没有打印机空闲。 幸运的是， 第3个可被满足， 所以进程3

运行并最终释放它所拥有的资源， 给出

A=(2 2 2 0)

接下来， 进程2也可运行并释放它所拥有的资源， 给出

A=(4 2 2 1)

现在剩下的进程都能够运行， 所以这个系统中不存在死锁。

6.4.3 从死锁中恢复

1. 利用抢占恢复
   
   在某些情况下， 可能会临时将某个资源从它的当前所有者那里转移到另一个进程。 许多情况下， 尤其是对运行在大型主机上的批处理操作系统来说， 需要人工进行干预。
2. 利用回滚恢复
   
   一旦检测到死锁， 就很容易发现需要哪些资源。 为了进行恢复， 要从一个较早的检查点上开始， 这样拥有所需要资源的进程会回滚到一个时间点， 在此时间点之前该进程获得了一些其他的资源。
3. 通过杀死进程恢复
   
   最直接也是最简单的解决死锁的方法是杀死一个或若干个进程。 一种方法是杀掉环中的一个进程。 如果走运的话， 其他进程将可以继续。 如果这样做行不通的话， 就需要继续杀死别的进程直到打破死锁环。

6.5 死锁避免

6.5.1 资源轨迹图

避免死锁的主要算法是基于一个安全状态的概念。

6.5.2 安全状态和不安全状态

如果没有死锁发生， 并且即使所有进程突然请求对资源的最大需求， 也仍然存在某种调度次序能够使得每一个进程运行完毕， 则称该状态是安全的。

安全状态和不安全状态的区别是： 从安全状态出发， 系统能够保证所有进程都能完成；

而从不安全状态出发， 就没有这样的保证。

6.5.3 单个资源的银行家算法

银行家算法就是对每一个请求进行检查， 检查如果满足这一请求是否会达到安全状态。 若是， 那么就满足该请求； 若否， 那么就推迟对这一请求的满足。 为了看状态是否安全， 银行家看他是否有足够的资源满足某一个客户。 如果可以， 那么这笔投资认为是能够收回的， 并且接着检查最接近最大限额的一个客户， 以此类推。 如果所有投资最终都被收回， 那么该状态是安全的， 最初的请求可以批准。

6.5.4 多个资源的银行家算法

可以把银行家算法进行推广以处理多个资源。

6.6 死锁预防

6.6.1 破坏互斥条件

先考虑破坏互斥使用条件。 如果资源不被一个进程所独占， 那么死锁肯定不会产生。

6.6.2 破坏占有和等待条件

只要禁止已持有资源的进程再等待其他资源便可以消除死

锁。 一种实现方法是规定所有进程在开始执行前请求所需的全部资源。 如果所需的全部资源可用， 那么就将它们分配给这个进程， 于是该进程肯定能够运行结束。 如果有一个或多个资源正被使用， 那么就不进行分配， 进程等待。

6.6.3 破坏不可抢占条件

破坏第三个条件（不可抢占） 也是可能的。

然而， 并不是所有的资源都可以进行类似的虚拟化。 例如， 数据库中的记录或者操作系统中的表都必须被锁定， 因此存在出现死锁的可能。

6.6.4 破坏环路等待条件

消除环路等待有几种方法。 一种是保证每一个进程在任何时刻只能占用一个资源， 如果要请求另外一个资源， 它必须先释放第一个资源。 但假若进程正在把一个大文件从磁带机上读入并送到打印机打印， 那么这种限制是不可接受的。

另一种避免出现环路等待的方法是将所有资源统一编号， 如图6-13a所示。 现在的规则是： 进程可以在任何时刻提出资源请求， 但是所有请求必须按照资源编号的顺序（升序） 提出。 进程可以先请求打印机后请求磁带机， 但不可以先请求绘图仪后请求打印机。

6.7 其他问题

6.7.1 两阶段加锁

常用的方法是两阶段加锁（two-phase locking） 。 在第一阶段， 进程试图对所有所需的记录进行加锁，一次锁一个记录。 如果第一阶段加锁成功， 就开始第二阶段， 完成更新然后释放锁。 在第一阶段并没有做实际的工作。

6.7.2 通信死锁

源死锁是最普遍的一种类型， 但不是惟一的一种。 另一种死锁发生在通信系统中（比如说网络） ， 即两个或两个以上进程利用发送信息来通信时。 一种普遍的情形是进程A向进程B发送请求信息， 然后阻塞直至B回复。 假设请求信息丢失， A将阻塞以等待回复， 而B会阻塞等待一个向其发送命令的请求， 因此发生死锁。

根据标准的定义， 在一系列进程中， 每个进程因为等待另外一个进程引发的事件而产生阻塞， 这就是一种死锁。 相比于更加常见的资源死锁， 我们把上面这种情况叫做通信死锁（communication deadlock） 。

另外一种技术通常可以用来中断通信死锁： 超时。

并非所有在通信系统或者网络发生的死锁都是通信死锁。 资源死锁也会发生， 如图6-15中的网络。

6.7.3 活锁

在某种情形下， 轮询（忙等待） 可用于进入临界区或存取资源。 采用这一策略的主要原因是， 相比所做的工作而言， 互斥的时间很短而挂起等待的时间开销很大。

6.7.4饥饿

在动态运行的系统中， 在任何时刻都可能请求资源。 这就需要一些策略来决定在什么时候谁获得什么资源。 虽然这个策略表面上很有道理， 但依然有可能使一些进程永远得不到服务， 虽然它们并不是死锁进程。

6.8.有关死锁的研究

死锁在操作系统发展的早期就作为一个课题被详细地研究过。 死锁的检测是一个经典的图论问题， 任何对数学有兴趣的研究生都可以在其上做3～4年的研究。

6.9 小结

死锁是任何操作系统的潜在问题。 在一组进程中， 每个进程都因等待由该组进程中的另一进程所占有的资源而导致阻塞， 死锁就发生了。 这种情况会使所有的进程都处于无限等待的状态。 一般来讲， 这是进程一直等待被其他进程占用的某些资源释放的事件。 死锁的另外一种可能的情况是一组通信进程都在等待一个消息， 而通信信道却是空的， 并且也没有采用超时机制。

通过跟踪哪一个状态是安全状态， 哪一个状态是不安全状态， 可以避免死锁。 安全状态就是这样一个状态： 存在一个事件序列， 保证所有的进程都能完成。 不安全状态就不存在这样的保证。 银行家算法可以通过拒绝可能引起不安全状态的请求来避免死锁。

也可以在设计系统时就不允许死锁发生， 从而在系统结构上预防死锁的发生。 例如， 只允许进程在任何时刻最多占有一个资源， 这就破坏了循环等待环路。 也可以将所有的资源编号， 规定进程按严格的升序请求资源， 这样也能预防死锁。

资源死锁并不是惟一的一种死锁。 尽管我们可以通过设置适当的超时机制来解决通信死锁， 但它依然是某些系统中潜在的问题。

活锁和死锁的问题有些相似， 那就是它也可以停止所有的转发进程， 但是二者在技术上不同， 由于活锁包含了一些实际上并没有锁住的进程， 因此可以通过先来先服务的分配策略来避免饥饿。

第7章 多媒体操作系统

略

第8章 多处理机系统

8.1 多处理机

共享存储器多处理机（或以后简称为多处理机， multiprocessor） 是这样一种计算机系统， 其两个或更多的CPU全部共享访问一个公用的RAM。 运行在任何一个CPU上的程序都看到一个普通（通常是分页） 的虚602拟地址空间。 这个系统惟一特别的性质是， CPU可对存储器字写入某个值， 然后读回该字， 并得到一个不同的值（因为另一个CPU改写了它） 。

在进行恰当组织时， 这种性质构成了处理器间通信的基础： 一个CPU向存储器写入某些数据而另一个读取这些数据。

8.1.1 多处理机硬件

所有的多处理机都具有每个CPU可访问全部存储器的性质， 而有些多处理机仍有一些其他的特性， 即读出每个存储器字的速度是一样快的。 这些机器称为UMA（Uniform Memory Access， 统一存储器访问） 多处理机。

1.基于总线的UMA多处理机体系结构

最简单的多处理机是基于单总线的， 参见图8-2a。 两个或更多的CPU以及一个或多个存储器模块都使用同一个总线进行通信。 当一个CPU需要读一个存储器字（memory word） 时， 它首先检查总线忙否。 如果总线空闲， 该CPU把所需字的地址放到总线上， 发出若干控制信号， 然后等待存储器把所需的字放到总线上。

当某个CPU需要读写存储器时， 如果总线忙， CPU只是等待， 直到总线空闲。 这种设计存在问题。 在只有两三个CPU时， 对总线的争夺还可以管理； 若有32个或64个CPU时， 就不可忍受了。 这种系统完全受到总线带宽的限制， 多数CPU在大部分时间里是空闲的。

这一问题的解决方案是为每个CPU添加一个高速缓存（cache） ， 如图8-2b所示。 这个高速缓存可以位于CPU芯片的内部、 CPU附近、 在处理器板上或所有这三种方式的组合。 由于许多读操作可以从本地高速缓存上得到满足， 总线流量就大大减少了， 这样系统就能够支持更多的CPU。 一般而言， 高速缓存不以单个字为基础， 而是以32字节或64字节块为基础。 当引用一个字时， 它所在的整个数据块（叫做一个cache行） 被取到使用它的CPU的高速缓存当中。

还有另一种可能性就是图8-2c中的设计， 在这种设计中每个CPU不止有一个高速缓存， 还有一个本地的私有存储器， 它通过一条专门的（私有） 总线访问。 为了优化使用这一配置， 编译器应该把所有程序的代码、 字符串、 常量以及其他只读数据、 栈和局部变量放进私有存储器中。 而共享存储器只用于可写的共享变量。 在多数情况下， 这种仔细的放置会极大地减少总线流量， 但是这样做需要编译器的积极配合。

2.使用交叉开关的UMA多处理机


即使有最好的高速缓存， 单个总线的使用还是把UMA多处理机的数量限制在16至32个CPU。 要超过这个数量， 需要不同类型的互连网络。 连接n个CPU到k个存储器的最简单的电路是交叉开关， 参见图8-3。

3.使用多级交换的UMA多处理机


Omega网络的接线模式常被称作全混洗（perfect shuffle） ， 因为每一级信号的混合就像把一副牌分成两半， 然后再把牌一张张混合起来。

接着看看Omega网络是如何工作的， 假设CPU 011打算从存储器模块110读取一个字。 CPU发送READ消息给开关1D， 它在Module域包含110。 1D开关取110的首位（最左位） 并用它进行路由处理。 0路由到上端输出， 而1的路由到下端， 由于该位为1， 所以消息通过低端输出被路由到2D。

所有的第二级开关， 包括2D， 取用第二个比特位进行路由。 这一位还是1， 所以消息通过低端输出转发到3D。 在这里对第三位进行测试， 结果发现是0。 于是， 消息送往上端输出， 并达到所期望的存储器110。

该消息的路径在图8-5中由字母a标出。

4.NUMA多处理机


单总线UMA多处理机通常不超过几十个CPU， 而交叉开关或交换网络多处理机需要许多（昂贵） 的硬件， 所以规模也不是那么大。 要想超过100个CPU还必须做些让步。

通常， 一种让步就是所有的存储器模块都具有相同的访问时间。 这种让步导致了前面所说的NUMA多处理机的出现。

所有NUMA机器都具有以下三种关键特性， 它们使得NUMA机器与其他多处理机相区别：

1)具有对所有CPU都可见的单个地址空间。

2)通过LOAD和STORE指令访问远程存储器。

3)访问远程存储器慢于访问本地存储器。

在对远程存储器的访问时间不被隐藏时（因为没有高速缓存） ， 系统被称为NC-NUMA（No Cache NUMA， 无高速缓存NUMA） 。 在有一致性高速缓存时， 系统被称为CC-NUMA（Cache-Coherent NUMA，高速缓存一致NUMA） 。


5.多核芯片


虽然CPU可能共享高速缓存或者不共享（如图1-8所示） ， 但是它们都共享内存。 考虑到每个内存字总是有惟一的值， 这些内存是一致的。 特殊的硬件电路可以确保在一个字同时出现在两个或者多个的高速缓存中的情况下， 当其中某个CPU修改了该字， 所有其他高速缓存中的该字都会被自动地并且原子性地删除来确保一致性。 这个过程称为窥探（snooping） 。

这样设计的结果是多核芯片就相当于小的多处理机。 实际上， 多核芯片时常被称为片级多处理机（Chip-level MultiProcessors， CMP） 。

8.1.2 多处理机操作系统类型

1.每个CPU有自己的操作系统


组织一个多处理机操作系统的可能的最简单的方法是， 静态地把存储器划分成和CPU一样多的各个部分， 为每个CPU提供其私有存储器以及操作系统的各自私有副本。 实际上n个CPU以n个独立计算机的形式运行。

由于这些原因， 上述模型已很少使用， 尽管在早期的多处理机中它一度被采用， 那时的目标是把已有的操作系统尽可能快地移植到新的多处理机上。

2.主从多处理机


图8-8中给出的是第二种模型。 在这种模型中， 操作系统的一个副本及其数据表都在CPU 1上， 而不是在其他所有CPU上。 为了在该CPU 1上进行处理， 所有的系统调用都重定向到CPU 1上。 如果有剩余的CPU时间， 还可以在CPU 1上运行用户进程。 这种模型称为主从模型（master-slave） ， 因为CPU 1是主CPU， 而其他的都是从属CPU。



这个模型的问题是， 如果有很多的CPU， 主CPU会变成一个瓶颈。 毕竟， 它要处理来自所有CPU的系统调用。

3.对称多处理机


我们的第三种模型， 即对称多处理机（Symmetric MultiProcessor， SMP） ， 消除了上述的不对称性。 在存储器中有操作系统的一个副本， 但任何CPU都可以运行它。 在有系统调用时， 进行系统调用的CPU陷入内核并处理系统调用。

8.1.3 多处理机同步

任何实用的互斥信号量协议的核心都是一条特殊指令， 该指令允许检测一个存储器字并以一种不可见的操作设置。 我们来看看在图2-22中使用的指令TSL（Test and Set Lock） 是如何实现临界区的。 正如我们先前讨论的， 这条指令做的是， 读出一个存储器字并把它存储在一个寄存器中。 同时， 它对该存储器字写入一个1（或某些非零值） 。 当然， 这需要两个总线周期来完成存储器的读写。 在单处理机中， 只要该指令不被中途中断， TSL指令就始终照常工作。

如果能消除在请求一侧的所有由TSL引起的写操作， 我们就可以明显地减少这种开销。 使提出请求的CPU首先进行一个纯读操作来观察锁是否空闲， 就可以实现这个目标。

另一个减少总线流量的方式是使用著名的以太网二进制指数补偿算法（binary exponential backoff algorithm） （Anderson， 1990） 。

一个更好的思想是， 让每个打算获得互斥信号量的CPU都拥有各自用于测试的私有锁变量， 如图8-11所示（Mellor-Crummey和Scott， 1991） 。

自旋与切换


自旋直接浪费了CPU周期。 重复地测试锁并不是高效的工作。 不过， 切换也浪费了CPU周期， 因为必须保存当前线程的状态， 必须获得保护就绪链表的锁， 还必须选择一个线程， 必须装入其状态， 并且使其开始运行。

8.1.4 多处理机调度

1.分时


处理独立线程的最简单算法是， 为就绪线程维护一个系统级的数据结构， 它可能只是一个链表， 但更多的情况下可能是对应不同优先级一个链表集合， 如图8-12a所示。

不过这一方法有两个缺点， 一个是随着CPU数量增加所引起的对调度数据结构的潜在竞争， 二是当线程由于I/O阻塞时所引起上下文切换的开销（overhead）

2.空间共享


最简单的空间共享算法是这样工作的。 假设一组相关的线程是一次性创建的。 在其创建的时刻， 调度程序检查是否有同线程数量一样多的空闲CPU存在。 如果有， 每个线程获得各自专用的CPU（非多道程序处理） 并且都开始运行。 如果没有足够的CPU， 就没有线程开始运行， 直到有足够的CPU时为止。 每个线程保持其CPU直到它终止， 并且该CPU被送回可用CPU池中。 如果一个线程在I/O上阻塞， 它继续保持其CPU，而该CPU就空闲直到该线程被唤醒。 在下一批线程出现时， 应用同样的算法。

3.群调度（Gang Scheduling）


空间共享的一个明显优点是消除了多道程序设计， 从而消除了上下文切换的开销。 但是， 一个同样明显的缺点是当CPU被阻塞或根本无事可做时时间被浪费了， 只有等到其再次就绪。 于是， 人们寻找既可以调度时间又可以调度空间的算法， 特别是对于要创建多个线程而这些线程通常需要彼此通信的线程。

群调度由三个部分组成：

1)把一组相关线程作为一个单位， 即一个群（gang） ， 一起调度。

2)一个群中的所有成员在不同的分时CPU上同时运行。

3)群中的所有成员共同开始和结束其时间片。

8.2 多计算机

8.2.1 多计算机硬件

1.互连技术


在每个节点上有一块网卡， 带有一根或两根从网卡上接出的电缆（或光纤） 。 这些电缆或者连到其他的节点上， 或者连到交换机上。

2.网络接口

8.2.2 低层通信软件

在多计算机系统中高性能通信的敌人是对包的过度复制。

8.2.3 用户层通信软件

在多计算机中， 不同CPU上的进程通过互相发送消息实现通信。 在最简单的情况下， 这种消息传送是暴露给用户进程的。


1.发送和接收


在最简化的的情形下， 所提供的通信服务可以减少到两个（库） 调用， 一个用于发送消息， 另一个用于

接收消息。 发送一条消息的调用可能是

send(dest,＆mptr);

而接收消息的调用可能是

receive(addr,＆mptr);

2.阻塞调用和非阻塞调用

8.2.4 远程过程调用

尽管消息传递模型提供了一种构造多计算机操作系统的便利方式， 但是它有不可救药的缺陷： 构造所有通信的范型（paradigm） 都是输入/输出。 过程send和receive基本上在做I/O工作， 而许多人认为I/O就是一种错误的编程模型。

8.2.5 分布式共享存储器

在图8-21a中， 是一台配有通过硬件实现的物理共享存储器的真正的多处理机。 在图8-21b中， 是由操作系统实现的DSM。 在图8-21c中， 我们看到另一种形式的共享存储器， 它通过更高层次的软件实现。 在本章的后面部分， 我们会讨论第三种方式， 不过现在还是专注于讨论DSM。

8.2.6 多计算机调度

在一台多处理机中， 所有的进程都在同一个存储器中。 当某个CPU完成其当前任务后， 它选择一个进程并运行。 而在一台多计算机中， 情形就大不相同了。 每个节点有其自己的存储器和进程集合。

8.2.7 负载平衡

8.3 虚拟化

除了强大的隔离性， 在虚拟机上运行软件还有其他的好处。 其中之一就是减少了物理机器的数量从而节省了硬件、 电源的开支以及占用更少的空间。

虚拟机的另一个好处在于检查点和虚拟机的迁移（例如， 在多个服务器间迁移以达到负载平衡） 比在一个普通的操作系统中进行进程迁移更加容易。

虚拟机的另一个用途是运行那些不再被支持或不能在当前硬件上工作的操作系统（或操作系统版本） 中的遗留应用程序（legacy application） 。

8.3.1 虚拟化的条件

简单地说， 每个有内核态和用户态的处理器都有一组只能在内核态执行的指令集合， 比如I/O指令、 改变MMU状态的指令等。 Popek和Goldberg（1974） 两人在他们的经典虚拟化工作中称这些指令为敏感指令（sensitive instruction） 。 还有一些指令如果在用户态下执行会引起陷入。 Popek和Goldberg称它们是特权指令（privileged instruction） 。 在他们的论文中首次论述指出， 当且仅当敏感指令是特权指令的子集时， 机器才是可虚拟化的。

8.3.2 Ⅰ型管理程序

像所有的I型管理程序一样， 它在裸机上运行。 虚拟机在用户态以用户进程的身份运行， 因此， 它不允许执行敏感指令。 虚拟机内运行着一个客户操作系统， 该客户操作系统认为自己是运行在内核态的， 但是实际上它是运行在用户态的。 我们把这种状态称为虚拟内核态（virtual kernel mode） 。 虚拟机内还运行着用户进程， 这些进程认为自己是运行在用户态的（事实上也正是如此） 。

8.3.3 Ⅱ型管理程序

II型管理程序也能正常工作的原因就已经很清楚了： 所有的敏感指令被仿真这些指令的过程调用所替代。 客户操作系统发射的敏感指令不会被真正的硬件执行。 它们转换成了对管理程序的调用， 而这些调用仿真了那些敏感指令。

8.3.4 准虚拟化

运行在I型和II型管理程序之上的都是没有修改过的客户操作系统， 但是这两类管理程序为了获得合理的性能都备受煎熬。

8.3.5 内存的虚拟化

现在我们已经知道了如何虚拟化处理器。 但是一个计算机系统不止是一个处理器。 它还有内存和I/O设备。 它们也需要虚拟化。 让我们来看看它们是如何实现的。

在这方面， 将来的VT技术可以通过硬件实现两级映射从而提供一些帮助。 硬件首先把虚拟页面映射成客户操作系统所认为的“物理页面”， 然后再把它（硬件仍然认为它是虚拟页面） 映射到物理地址空间， 这样做不会引起陷入。

8.3.6 I／0设备的虚拟化

当设备驱动程序试图进行I/O操作时， 它们会读写设备的硬件寄存器。 这些指令是敏感指令， 将会陷入到管理程序， 管理程序根据需要从硬件中读取或向硬件中写入所需的数据。

8.3.7 虚拟工具

使用虚拟机技术， 一个软件开发人员能够仔细地创建一个虚拟机， 装入所需的操作系统、 编译器、 函数库和应用程序代码， 组成一个整体来运行。 这个虚拟机映像可以被放到光盘（CD-ROM） 或网站上以供用户安装或下载。

这种方法意味着只有软件开发者需要了解所有的依赖关系。 客户得到的是可以正常工作的完整

的程序包， 独立于他们正在使用的操作系统、 各类软件、 已安装的程序包和函数库。 这些被包装好的虚拟机通常叫做虚拟工具（virtual appliance） 。

8.3.8 多核处理机上的虚拟机

8.3.9 授权问题

8.4 分布式系统

分布式系统（distributed system） 。 这些系统与多计算机类似， 每个节点都有自己的私有存储器， 整个系统中没有共享的物理存储器。 但是， 分布式系统与多计算机相比， 耦合更加松散。

8.4.1 网络硬件

1.以太网（Ethernet）

2.因特网

8.4.2 网络服务和协议

1.网络服务



2.网络协议

8.4.3 基于文档的中间件

作为一个例子， 假设提供的URL是http://www.minix3.org/doc/faq.html。 浏览器按照下面的步骤取得所需的页面。

1)浏览器向DNS询问www.minix3.org的IP地址。

2)DNS回答， 是130.37.20.20。

3)浏览器建立一个到130.37.20.20上端口80的TCP连接。

4)接着浏览器发送对文件doc/faq.html的请求。

5)www.acm.org服务器发送文件doc/faq.html。

6)释放TCP连接。

7)浏览器显示doc/faq.html文件中的所有文本。

8)浏览器获取并显示doc/faq.html中的所有图像。

8.4.4 基于文件系统的中间件

8.4.5 基于对象的中间件

8.4.6 基于协作的中间件

8.4.7 网格

8.5 有关多处理机系统的研究

第9章 安全

9.1 环境安全

安全包含许多方面的内容， 其中比较主要的三个方面是威胁的实质、 入侵者的本性和数据的意外遗失。我们将分别加以研究。

9.1.1 威胁

从安全性角度来讲， 计算机系统有四个主要目标， 同时也面临着三个主要威胁， 如图9-1所示。



第一个目标是数据保密（data confidentiality） ， 指将机密的数据置于保密状态。

第二个目标数据完整性（data integrity） 是指未经授权的用户没有得到许可就擅自改动数据。

第三个目标系统可用性（system availability） 是指没有人可以扰乱系统使之瘫痪。

9.1.2 入侵者

入侵者表现为两种形式： 被动入侵者仅仅想阅读他们无权阅读的文件； 主动入侵者则怀有恶意， 他们未经授权就想改动数据。 当我们设计操作系统抵御入侵者时， 必须牢记要抵御哪一种入侵者。 通常的入侵者种类包括：

1.非专业用户的随意浏览。

2.内部人员的窥视。

3.为获取利益而尝试。

4.商业或军事间谍。

9.1.3 数据意外遗失

除了恶意入侵造成的威胁外， 有价值的信息也会意外遗失。 造成数据意外遗失的原因通常包括：

1.天灾： 火灾、 洪水、 地震、 战争、 暴乱或老鼠对磁带和软盘的撕咬。

2.软硬件错误： CPU故障、 磁盘或磁带不可读、 通信故障或程序里的错误。

3.人为过失： 不正确的数据登录、 错误的磁带或磁盘安装、 运行了错误的程序、 磁带或磁盘的遗失， 以及其他的过失等。

9.2 密码学原理

在算法中使用的加密参数叫做密钥（key） 。 如果P代表明文， KE 代表加密密钥， C代表密文， E代表加密算法（即， 函数） ， 那么C=E(P,KE )。 这就是加密的定义。 其含义是把明文P和加密密钥KE 作为参数， 通过加密算法E就可以把明文变为密文。

同样地， 当D表示解密算法， KD 表示解密密钥时， P=D(C,KD )。 也就是说， 要想把密文还原成明文，可以用密文C和解密密钥KD 作为参数， 通过解密算法D进行运算。 这两种互逆运算间的关系如图9-2所示。

9.2.1 私钥加密技术

许多类似的密钥系统都有这样一个特点， 那就是给定了加密密钥就能够较为容易地找到解密密钥， 反之亦然。 这样的系统采用了私钥加密技术或对称密钥加密技术。

9.2.2 公钥加密技术

由于对信息进行加密和解密的运算量是可控制的， 所以私钥加密体系十分有用。 但是它也有一个缺陷：发送者与接受者必须同时拥有密钥。

公钥加密技术（1976年由Diffie和Hellman提出） 。 这一体系的特点是加密密钥和解密密钥是不同的， 并且当给出了一个筛选过的加密密钥后不可能推出对应的解密密钥。 在这种特性下， 加密密钥可被公开而只有解密密钥处于秘密状态。

当我们使用公钥密码体系时， 每个人都拥有一对密钥（公钥和私钥） 并把其中的公钥公开。 公钥是加密密钥， 私钥是解密密钥。 通常密钥的运算是自动进行的， 有时候用户可以自选密码作为算法的种子。 在发送机密信息时， 用接收方的公钥将明文加密。 由于只有接收方拥有私钥， 所以也只有接收方可以解密信息。

9.2.3 单向函数

在接下来的许多场合里， 我们将看到有些函数f， 其特性是给定f和参数x， 很容易计算出y=f(x)。 但是给定f(x)， 要找到相应的x却不可行。 这种函数采用了十分复杂的方法把数字打乱。 具体做法可以首先将y初始化为x。 然后可以有一个循环， 进行多次迭代， 只要在x中有1位就继续迭代， 随着每次迭代， y中的各位的排列以与迭代相关的方式进行， 每次迭代时添加不同的常数， 最终生成了彻底打乱位的数字排列。 这样的函数叫做加密散列函数。

9.2.4 数字签名

文件所有者利用他的私钥对散列值进行运算得到D(散列值)。 该值称为签名块（signature block） 。

接收方收到文档和散列值后， 首先使用事先取得一致的MD5或SHA算法计算文档的散列值， 然后接收方使用发送方的公钥对签名块进行运算以得到E(D(hash)） 。

如果计算后的散列值与签名块中的散列值不一致， 则表明： 要么文档、 要么签名块、 要么两者共同被篡改过（或无意中被改动） 。

要使用这种签名机制， 接收方必须知道发送方的公钥。

9.2.5 可信平台模块

有一种方法在工业上已经被采用， 该方法需要用到一种叫做可信平台模块（Trusted Platform Modules，TPM） 的芯片。 TPM是一种加密处理器（cryptoprocessor） ， 使用内部的非易失性存储介质来保存密钥。

该芯片用硬件实现数据的加密/解密操作， 其效果与在内存中对明文块进行加密或对密文块进行解密的效果相同， TPM同时还可以验证数字签名。

9.3 保护机制

9.3.1 保护域

域（domain） 是一对（对象， 权限） 组合。 每一对组合指定一个对象和一些可在其上运行的操作子集。

9.3.2 访问控制列表

第一种方法包括一个关联于每个对象的（有序） 列表里， 列表里包含了所有可访问对象的域以及这些域如何访问这些对象的方法。 这一列表叫做访问控制表（Access Control List， ACL） 。

9.3.3 权能

9.3.4 可信系统

9.3.5 可信计算基

每一个可信系统的核心是最小的可信计算基（Trusted Computing Base， TCB） ， 其中包含了实施的所有安全规则所必需的硬件和软件。

9.3.6 安全系统的形式化模型

第10章 实例研究1： Linux

10.2 Linux概述

10.2.1 Linux的设计目标

一直以来， UNIX都被设计成一种能够同时处理多进程和多用户的交互式系统。

10.2.2 到Linux的接口

10.2.3 shell

尽管Linux系统具有图形用户界面， 然而大多数程序员和高级用户都更愿意使用一个命令行界面， 称作shell。

10.2.4 Linux应用程序

10.2.5 内核结构

处在最顶层的是到内核的系统调用接口。 所有系统调用都来自这里， 其导致一个陷入， 并将系统从用户态转换到受保护的内核态， 继而将控制权交给上述的内核部件之一。

10.3 Linux中的进程

10.3.1 基本概念

在Linux系统中， 进程通过非常简单的方式创建。 系统调用fork将会创建一个与原始进程完全相同的进程副本。 调用fork函数的进程称为父进程， 新的进程称为子进程。 父进程和子进程都拥有自己的私有内存映像。 如果在调用fork函数之后， 父进程修改了属于它的一些变量， 这些变化对于子进程来说是不可见的， 反之亦然。

但是， 父进程和子进程可以共享已经打开的文件。

事实上， 父、 子进程的内存映像、 变量、 寄存器以及其他所有的东西都是相同的， 这就产生了一个问题： 该如何区别这两个进程？

秘密在于fork系统调用给子进程返回一个零值， 而给父进程返回一个非零值。 这个非零值是子进程的进程标识符（Process Identifier， PID） 。 两个进程检验fork函数的返回值， 并且根据返回值继续执行， 如图10-4所示。

Linux系统中的进程可以通过一种消息传递的方式进行通信。 在两个进程之间， 可以建立一个通道， 一个进程向这个通道里写入字节流， 另一个进程从这个通道中读取字节流。 这些通道称为管道（pipe)。

进程还可以通过另一种方式通信： 软件中断。 一个进程可以给另一个进程发送信号（signal） 。

10.3.2 Linux中进程管理相关的系统调用

10.3.3 Linux中进程与线程的实现

Linux中的线程


2000年的时候， Linux系统引入了一个新的、 强大的系统调用clone， 模糊了进程和线程的区别， 甚至使得两个概念的重要性被倒置。

pid=clone(function,stack_ptr,sharing_flags,arg);

10.3.4 Linux中的调度

在我们来关注Linux系统的调度算法。 首先要认识到， Linux系统的线程是内核线程， 所以Linux系统

的调度是基于线程的， 而不是基于进程的。

为了进行调度， Linux系统将线程区分为三类：

1)实时先入先出。

2)实时轮转。

3)分时。

Linux调度算法使用一个重要的数据结构——调度队列。 在系统中， 一个CPU有一个调度队列， 除了其他信息， 调度队列中有两个数组， 一个是正在活动的， 一个是过期失效的。 如图10-10所示， 这两个分量都是指向数组的指针， 每个数组都包含了140个链表头， 每个链表具有不同的优先级。 链表头指向给定优先级的双向进程链表。 调度的基本操作如下所述。

10.4 Linux中的内存管理

10.4.1 基本概念

每个Linux进程都有一个地址空间， 逻辑上有三段组成： 代码、 数据和堆栈段。

10.4.2 Linux中的内存管理系统调用

10.4.3 Linux中内存管理的实现

1.物理内存管理


在许多系统中由于异构硬件限制， 并不是所有的物理内存都能被相同地对待， 尤其是对于I/O和虚拟内存。 Linux区分三种内存区域（zone） ：

1)ZONE_DMA： 可以用来DMA操作的页。

2)ZONE_NORMAL： 正常规则映射的页。

3)ZONE_HIGHMEM： 高内存地址的页， 并不永久性映射。


2.内存分配机制


Linux支持多种内存分配机制。 分配物理内存页框的主要机制是页面分配器， 它使用了著名的伙伴算法。

3.虚拟地址空间表示


虚拟地址空间被分割成同构连续页面对齐的区域。 也就是说， 每个区域由一系列连续的具有相同保护和分页属性的页面组成。

10.4.4 Linux中的分页

Linux分页背后的基本思想是简单的： 为了运行， 一个进程并不需要完全在内存中。 实际上所需要的是用户结构和页表。 如果这些被换进内存， 那么进程被认为是“在内存中”， 可以被调度运行了。 代码、 数据和栈段的页面是动态载入的， 仅仅是在它们被引用的时候。 如果用户结构和页表不在内存中， 直到交换器把它们载入内存进程才能运行。

页面置换算法


页面替换是这样工作的。 Linux试图保留一些空闲页面， 这样可以在需要的时候分配它们。 当然， 这个页面池必须不断地加以补充。 PFRA（页框回收算法） 算法展示了它是如何发生的。

10.5 Linux中的I/O系统

Linux和其他的UNIX系统一样， I/O系统都相当的简单明了。 基本上， 所有的I/O设备都被当作文件来处理， 并且通过与访问所有文件同样的read和write系统调用来访问。

10.5.1 基本概念

Linux把设备当作一种特殊文件整合到文件系统中。 每个I/O设备都被分配了一条路径， 通常在/dev目录下。

例如： 一个磁盘的路径可能是“/dev/hd1”， 一个打印机的路径可能是“/dev/lp”， 网络的路径可能是“/dev/net”。

10.5.2 网络

I/O的另外一个例子是网络， 由Berkeley UNIX首创并在Linux中差不多原封不动引入。 在Berkeley的设计中， 关键概念是套接字（socket） 。



每个套接字支持一种特定的网络类型， 这在套接字创建时指定。 最常用的类型是：

1)可靠的面向连接的字节流。

2)可靠的面向连接的数据包流。

3)不可靠的数据包传输。

10.5.3 Linux的输入/输出系统调用

10.5.4 输入/输出在Linux中的实现

在Linux中I/O是通过一系列的设备驱动来实现的， 每个设备类型对应一个设备驱动。 设备驱动的功能是对系统的其他部分隔离硬件的细节。

10.5.5 Linux中的模块

10.6 Linux文件系统

10.6.1 基本概念

10.6.2 Linux的文件系统调用

要创建一个文件时， 可以使用creat系统调用。

creat系统调用不仅创建了一个新文件， 还以写的方式打开了这个文件。 为了使以后的系统调用能够访问这个文件， creat成功时返回一个非负整数， 这个非负整数叫做文件描述符， 也就是例子中的fd。