复习题答案

第1章 计算机系统概述

1.1 列出并简要地定义计算机的四个主要组成部分。

主存储器，存储数据和程序；算术逻辑单元，能处理二进制数据；控制单元，解读存储器中的指令并且使他们得到执行；输入/输出设备，由控制单元管理。 1.2 定义处理器寄存器的两种主要类别。

用户可见寄存器：优先使用这些寄存器，可以使机器语言或者汇编语言的程序员减少对主存储器的访问次数。对高级语言而言，由优化编译器负责决定把哪些变量应该分配给主存储器。一些高级语言，如C语言，允许程序言建议编译器把哪些变量保存在寄存器中。

控制和状态寄存器：用以控制处理器的操作，且主要被具有特权的操作系统例程使用，以控制程序的执行。

1.3 一般而言，一条机器指令能指定的四种不同操作是什么？

处理器－寄存器：数据可以从处理器传送到存储器，或者从存储器传送到处理器。

处理器－I/O：通过处理器和I/O模块间的数据传送，数据可以输出到外部设备，或者从外部设备输入数据。

数据处理：处理器可以执行很多关于数据的算术操作或逻辑操作。 控制：某些指令可以改变执行顺序。 1.4 什么是中断？

中断：其他模块（I/O，存储器）中断处理器正常处理过程的机制。 1.5 多中断的处理方式是什么？

处理多中断有两种方法。第一种方法是当正在处理一个中断时，禁止再发生中断。第二种方法是定义中断优先级，允许高优先级的中断打断低优先级的中断处理器的运行。 1.6 内存层次的各个元素间的特征是什么？

存储器的三个重要特性是：价格，容量和访问时间。 1.7 什么是高速缓冲存储器？

高速缓冲存储器是比主存小而快的存储器，用以协调主存跟处理器，作为最近储存地址的缓冲区。 1.8 列出并简要地定义I/O操作的三种技术。

可编程I/O：当处理器正在执行程序并遇到与I/O相关的指令时，它给相应的I/O模块发布命令（用以执行这个指令）；在进一步的动作之前，处理器处于繁忙的等待中，直到该操作已经完成。

中断驱动I/O：当处理器正在执行程序并遇到与I/O相关的指令时，它给相应的I/O模块发布命令，并继续执行后续指令，直到后者完成，它将被I/O模块中断。如果它对于进程等待I/O的完成来说是不必要的，可能是由于后续指令处于相同的进程中。否则，此进程在中断之前将被挂起，其他工作将被执行。

直接存储访问：DMA模块控制主存与I/O模块间的数据交换。处理器向DMA模块发送一个传送数据块的请求，（处理器）只有当整个数据块传送完毕后才会被中断。 1.9 空间局部性和临时局部性间的区别是什么？

空间局部性是指最近被访问的元素的周围的元素在不久的将来可能会被访问。临时局部性（即时间局部性）是指最近被访问的元素在不久的将来可能会被再次访问。 1.10 开发空间局部性和时间局部性的策略是什么？

空间局部性的开发是利用更大的缓冲块并且在存储器控制逻辑中加入预处理机制。时间局部性的开发是利用在高速缓冲存储器中保留最近使用的指令及数据，并且定义缓冲存储的优先级。

第2章 操作系统概述

1

2.1 操作系统设计的三个目标是什么？

方便：操作系统使计算机更易于使用。

有效：操作系统允许以更有效的方式使用计算机系统资源。

扩展的能力：在构造操作系统时，应该允许在不妨碍服务的前提下有效地开发、测试和引进新的系统功能。

2.2 什么是操作系统的内核？

内核是操作系统最常使用的部分，它存在于主存中并在特权模式下运行，响应进程调度和设备中断。 2.3 什么是多道程序设计？

多道程序设计是一种处理操作，它在两个或多个程序间交错处理每个进程。 2.4 什么是进程？

进程是一个正在执行的程序，它被操作系统控制和选择。 2.5 操作系统是怎么使用进程上下文的？

执行上下文又称为进程状态，是操作系统用来管理和控制所需的内部数据。这种内部信息和进程是分开的，因为操作系统信息不允许被进程直接访问。上下文包括操作系统管理进程以及处理器正确执行进程所需要的所有信息，包括各种处理器寄存器的内容，如程序计数器和数据寄存器。它还包括操作系统使用的信息，如进程优先级以及进程是否在等待特定I/O事件的完成。 2.6 列出并简要介绍操作系统的五种典型存储管理职责。

进程隔离：操作系统必须保护独立的进程，防止互相干涉数据和存储空间。

自动分配和管理：程序应该根据需要在存储层次间动态的分配，分配对程序员是透明的。因此，程序员无需关心与存储限制有关的问题，操作系统有效的实现分配问题，可以仅在需要时才给作业分配存储空间。

2.7 解释实地址和虚地址的区别。

虚地址指的是存在于虚拟内存中的地址，它有时候在磁盘中有时候在主存中。 实地址指的是主存中的地址。 2.8 描述轮循调度技术。

轮循调度是一种调度算法，所有的进程存放在一个环形队列中并按固定循序依次激活。因为等待一些事件（例如：等待一个子进程或一个I/O操作）的发生而不能被处理的进程将控制权交给调度器。 2.9 解释单体内核和微内核的区别。

单体内核是一个提供操作系统应该提供的功能的大内核，包括调度、文件系统、网络、设备驱动程序、存储管理等。内核的所有功能成分都能够访问它的内部数据结构和程序。典型情况下，这个大内核是作为一个进程实现的，所有元素都共享相同的地址空间。

微内核是一个小的有特权的操作系统内核，只提供包括进程调度、内存管理、和进程间通信等基本功能，要依靠其他进程担当起和操作系统内核联系作用。 2.10 什么是多线程？

多线程技术是指把执行一个应用程序的进程划分成可以同时运行的多个线程。

第3章 进程描述和控制

3.1 什么是指令跟踪？

指令跟踪是指为该进程而执行的指令序列。 3.2 通常那些事件会导致创建一个进程？

新的批处理作业；交互登录；操作系统因为提供一项服务而创建；由现有的进程派生。（表3.1） 3.3 对于图3.6中的进程模型，请简单定义每个状态。

运行态：该进程正在执行。就绪态：进程做好了准备，只要有机会就开始执行。 阻塞态：进程在某些事件发生前不能执行，如I/O操作完成。

新建态：刚刚创建的进程，操作系统还没有把它加入到可执行进程组中。

2

退出态：操作系统从可执行进程组中释放出的进程，或者是因为它自身停止了，或者是因为某种原因被取消。

3.4 抢占一个进程是什么意思？

处理器为了执行另外的进程而终止当前正在执行的进程，这就叫进程抢占。 3.5 什么是交换，其目的是什么？

交换是指把主存中某个进程的一部分或者全部内容转移到磁盘。当主存中没有处于就绪态的进程时，操作系统就把一个阻塞的进程换出到磁盘中的挂起队列，从而使另一个进程可以进入主存执行。 3.6 为什么图3.9（b）中有两个阻塞态？

有两个独立的概念：进程是否在等待一个事件（阻塞与否）以及进程是否已经被换出主存（挂起与否）。为适应这种2*2的组合，需要两个阻塞态和两个挂起态。 3.7 列出挂起态进程的4个特点。

1.进程不能立即执行。

2.进程可能是或不是正在等待一个事件。如果是，阻塞条件不依赖于挂起条件，阻塞事件的发生不会使进程立即被执行。

3.为了阻止进程执行，可以通过代理把这个进程置于挂起态，代理可以是进程自己，也可以是父进程或操作系统。

4.除非代理显式地命令系统进行状态转换，否则进程无法从这个状态中转移。 3.8 对于哪类实体，操作系统为了管理它而维护其信息表？

内存、I/O、文件和进程。

3.9 列出进程控制块中的三类信息。

进程标识，处理器状态信息，进程控制信息。 3.10 为什么需要两种模式（用户模式和内核模式）？

用户模式下可以执行的指令和访问的内存区域都受到限制。这是为了防止操作系统受到破坏或者修改。而在内核模式下则没有这些限制，从而使它能够完成其功能。 3.11 操作系统创建一个新进程所执行的步骤是什么？

1.给新进程分配一个唯一的进程标识号。2.给进程分配空间。3.初始化进程控制块。4.设置正确的连接。5.创建或扩充其他的数据结构。 3.12 中断和陷阱有什么区别？

中断与当前正在运行的进程无关的某些类型的外部事件相关，如完成一次I/O操作。陷阱与当前正在运行的进程所产生的错误或异常条件相关，如非法的文件访问。 3.13 举出中断的三个例子。

时钟终端，I/O终端，内存失效。 3.14 模式切换和进程切换有什么区别？

发生模式切换可以不改变当前正处于运行态的进程的状态。发生进程切换时，一个正在执行的进程被中断，操作系统指定另一个进程为运行态。进程切换需要保存更多的状态信息。

第4章 线程、对称多处理和微内核

4.1 表3.5列出了在一个没有线程的操作系统中进程控制块的基本元素。对于多线程系统，这些元素中那

些可能属于线程控制块，那些可能属于进程控制块？

这对于不同的系统来说通常是不同的，但一般来说，进程是资源的所有者，而每个线程都有它自己的执行状态。关于表3.5中的每一项的一些结论如下：进程标识：进程必须被标识，而进程中的每一个线程也必须有自己的ID。处理器状态信息：这些信息通常只与进程有关。进程控制信息：调度和状态信息主要处于线程级；数据结构在两级都可出现；进程间通信和线程间通信都可以得到支持；特权在两级都可以存在；存储管理通常在进程级；资源信息通常也在进程级。 4.2 请列出线程间的模式切换比进程间的模式切换开销更低的原因。

3

包含的状态信息更少。

4.3 在进程概念中体现出的两个独立且无关的特点是什么？

资源所有权和调度/执行。

4.4 给出在单用户多处理系统中使用线程的四个例子。

前台和后台操作，异步处理，加速执行和模块化程序结构。 4.5 哪些资源通常被一个进程中的所有线程共享？

例如地址空间，文件资源，执行特权等。 4.6 列出用户级线程优于内核级线程的三个优点。

1.由于所有线程管理数据结构都在一个进程的用户地址空间中，线程切换不需要内核模式的特权，因此，进程不需要为了线程管理而切换到内核模式，这节省了在两种模式间进行切换（从用户模式到内核模式；从内核模式返回用户模式）的开销。

2.调用可以是应用程序专用的。一个应用程序可能倾向于简单的轮询调度算法，而另一个应用程序可能倾向于基于优先级的调度算法。调度算法可以去适应应用程序，而不会扰乱底层的操作系统调度器。 3.用户级线程可以在任何操作系统中运行，不需要对底层内核进行修改以支持用户级线程。线程库是一组供所有应用程序共享的应用级软件包。 4.7 列出用户级线程相对于内核级线程的两个缺点。

1.在典型的操作系统中，许多系统调用都会引起阻塞。因此，当用户级线程执行一个系统调用时，不仅这个线程会被阻塞，进程中的所有线程都会被阻塞。

2.在纯粹的用户级进程策略中，一个多线程应用程序不能利用多处理技术。内核一次只把一个进程分配给一个处理器，因此一次进程中只能有一个线程可以执行。 4.8 定义jacketing。

Jacketing通过调用一个应用级的I/O例程来检查I/O设备的状态，从而将一个产生阻塞的系统调用转化为一个不产生阻塞的系统调用。 4.9 简单定义图4.8中列出的各种结构。

SIMD：一个机器指令控制许多处理部件步伐一致地同时执行。每个处理部件都有一个相关的数据存储空间，因此，每条指令由不同的处理器在不同的数据集合上执行。

MIMD：一组处理器同时在不同的数据集上执行不同的指令序列。主/从：操作系统内核总是在某个特定的处理器上运行，其他处理器只用于执行用户程序，还可能执行一些操作系统实用程序。

SMP：内核可以在任何处理器上执行，并且通常是每个处理器从可用的进程或线程池中进行各自的调度工作。集群：每个处理器都有一个专用存储器，而且每个处理部件都是一个独立的计算机。 4.10 列出SMP操作系统的主要设计问题。

同时的并发进程或线程，调度，同步，存储器管理，可靠性和容错。

4.11 给出在典型的单体结构操作系统中可以找到且可能是微内核操作系统外部子系统中的服务和功能。

设备驱动程序，文件系统，虚存管理程序，窗口系统和安全服务。 4.12 列出并简单解释微内核设计相对于整体式设计的七个优点。

一致接口：进程不需要区分是内核级服务还是用户级服务，因为所有服务都是通过消息传递提供的。 可扩展性：允许增加新的服务以及在同一个功能区域中提供多个服务。

灵活性：不仅可以在操作系统中增加新功能，还可以删减现有的功能，以产生一个更小、更有效的实现。

可移植性：所有或者至少大部分处理器专用代码都在微内核中。因此，当把系统移植到一个处理器上时只需要很少的变化，而且易于进行逻辑上的归类。

可靠性：小的微内核可以被严格地测试，它使用少量的应用程序编程接口（API），这就为内核外部的操作系统服务产生高质量的代码提供了机会。

分布式系统支持：微内核通信中消息的方向性决定了它对分布式系统的支持。

面向对象操作系统环境：在微内核设计和操作系统模块化扩展的开发中都可以借助面向对象方法的原理。

4

4.13 解释微内核操作系统可能存在的性能缺点。

通过微内核构造和发送信息、接受应答并解码所花费的时间比一次系统调用的时间要多。 4.14 列出即使在最小的微内核操作系统中也可以找到的三个功能。

低级存储器管理，进程间通信（IPC）以及I/O和中断管理。 4.15 在微内核操作系统中，进程或线程间通信的基本形式是什么？

消息。

第5章 并发性：互斥和同步

5.1 列出与并发相关的四种设计问题

进程间的交互，共享资源之间的竞争，多个进程的同步问题，对进程的处理器时间分配问题 5.2 列出并发的三种上下文

多个应用程序，结构化应用程序，操作系统结构 5.3 执行并发进程的最基本要求是什么？

加强互斥的能力

5.4 列出进程间的三种互相知道的程度，并简单地给出各自的定义。

进程间互相不知道对方：这是一些独立的进程，他们不会一起工作。

进程间间接知道对方：这些进程并不需要知道对方的进程ID号，但他们共享访问某些对象，如一个I/O缓冲区。

进程间直接知道对方：这些进程可以通过进程ID号互相通信，用于合作完成某些活动。 5.5 竞争进程和合作进程进程间有什么区别。

竞争进程需要同时访问相同的资源，像磁盘，文件或打印机。合作进程要么共享访问一个共有的资源，像一个内存访问区，要么就与其他进程相互通信，在一些应用程序或活动上进行合作。 5.6 列出与竞争进程相关的三种控制问题，并简单地给出各自的定义。

互斥：竞争进程仅可以访问一个临界资源（一次仅有一个进程可以访问临界资源），并发机制必须满足一次只有一个进程可以访问临界资源这个规则。

死锁：如果竞争进程需要唯一的访问多于一个资源，并且当一个进程控制着一个进程，且在等待另一个进程，死锁可能发生。

饥饿：一组进程的一个可能会无限期地拒绝进入到一个需要资源，因为其他 成员组成垄断这个资源。 5.7 列出对互斥的要求。

1.必须强制实施互斥：在具有关于相同资源或共享对象的临界区的所有进程中，一次只允许一个进程进入临界区。

2.一个在临界区停止的进程必须不干涉其他进程。

3.绝不允许出现一个需要访问临界区的进程被无限延迟的情况，即不会饿死或饥饿。 4.当没有进程在临界区中时，任何需要进入临界区的进程必须能够立即进入。 5.对相关进程的速度和处理器的数目没有任何要求和限制。 6.一个进程驻留在临界区中的时间是有限的。 5.8 在信号量上可以执行什么操作。

1.一个信号量可以初始化成非负数。

2.wait操作使信号量减1，如果值为负数，那么进程执行wait就会受阻。3signal操作使信号量增加1，如果小于或等于0，则被wait操作阻塞的进程被解除阻塞。 5.9 二元信号量与一般信号量有什么区别。

二元信号量只能取0或1，而一般信号量可以取任何整数。 5.10 强信号量与弱信号量有什么区别。

强信号量要求在信号量上等待的进程按照先进先出的规则从队列中移出。弱信号量没有此规则。

5

5.11 .什么是管程。

管程是由一个或多个过程，一个初始化序列和局部数据组成的软件模块。 5.12 对于消息，有阻塞和无阻塞有什么区别？

发送者和接收者任一方阻塞则消息传递需要等待，都无阻塞则不需等待。 5.13 通常与读者-写者问题相关联的有哪些条件？

1.任意多的读进程可以同时读这个文件 2.一次只有一个写进程可以往文件中写

3.如果一个写进程正在往文件中写时，则禁止任何读进程读文件。

第6章 并发性：死锁和饥饿

6.1 给出可重用资源和可消费资源的例子。

可重用资源：处理器，Ｉ/Ｏ通道，主存和辅存，设备以及诸如文件，数据库和信号量之类的数据结构。

可消费资源：中断，信号，消息和Ｉ/Ｏ缓冲区中的信息。 6.2 可能发生死锁所必须的三个条件是什么？

互斥，占有且等待，非抢占。 6.3 产生死锁的第４个条件是什么？

循环等待。

6.4 如何防止占有且等待的条件？

可以要求进程一次性地请求所有需要的资源，并且阻塞这个资源直到所有请求都同时满足。 6.5 给出防止无抢占条件的两种方法。

第一种，如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占用的资源，如果有必要，可再次请求这些资源和另外的资源。

第二种，如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。

6.6 如何防止循环等待条件？

可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了Ｒ类型的资源，那么它接下来请求的资源只能是那些排在Ｒ类型之后的资源类型。 6.7 死锁避免，检测和预防之间的区别是什么？

死锁预防是通过间接地限制三种死锁必要条件的至少一个或是直接地限制循环等待的发生来避免死锁的出现。死锁避免允许可能出现的必要条件发生，但是采取措施确保不会出现死锁的情况。而死锁检测允许资源的自由分配，采取周期性的措施来发现并处理可能存在的死锁情况。

第7章 内存管理

7.1 内存管理需要满足哪些需求？

重定位、保护、共享、逻辑组织和物理组织。 7.2 为什么需要重定位进程的能力？

通常情况下，并不能事先知道在某个程序执行期间会有哪个程序驻留在主存中。此外还希望通过提供一个巨大的就绪进程池，能够把活动进程换入和换出主存，以便使处理器的利用率最大化。在这两种情况下，进程在主存中的确切位置是不可预知的。 7.3 为什么不可能在编译时实施内存保护？

由于程序在主存中的位置是不可预测的，因而在编译时不可能检查绝对地址来确保保护。并且，大多数程序设计语言允许在运行时进行地址的动态计算（例如，通过计算数组下标或数据结构中的指针）。因此，必须在运行时检查进程产生的所有存储器访问，以便确保它们只访问了分配给该进程的存储空

6

间。

7.4 允许两个或多个进程访问进程的某一特定区域的原因是什么？

如果许多进程正在执行同一程序，则允许每个进程访问该程序的同一个副本要比让每个进程有自己单独的副本更有优势。同样，合作完成同一任务的进程可能需要共享访问同一个数据结构。 7.5 在固定分区方案中，使用大小不等的分区有什么好处？

通过使用大小不等的固定分区：1.可以在提供很多分区的同时提供一到两个非常大的分区。大的分区允许将很大的进程全部载入主存中。2.由于小的进程可以被放入小的分区中，从而减少了内部碎片。 7.6 内部碎片和外部碎片有什么区别？

内部碎片是指由于被装入的数据块小于分区大小而导致的分区内部所浪费的空间。外部碎片是与动态分区相关的一种现象，它是指在所有分区外的存储空间会变成越来越多的碎片的。 7.7 逻辑地址、相对地址和物理地址间有什么区别？

逻辑地址是指与当前数据在内存中的物理分配地址无关的访问地址，在执行对内存的访问之前必须把它转化成物理地址。相对地址是逻辑地址的一个特例，是相对于某些已知点（通常是程序的开始处）的存储单元。物理地址或绝对地址是数据在主存中的实际位置。 7.8 页和帧之间有什么区别？

在分页系统中，进程和磁盘上存储的数据被分成大小固定相等的小块，叫做页。而主存被分成了同样大小的小块，叫做帧。一页恰好可以被装入一帧中。 7.9 页和段之间有什么区别？

分段是细分用户程序的另一种可选方案。采用分段技术，程序和相关的数据被划分成一组段。尽管有一个最大段长度，但并不需要所有的程序的所有段的长度都相等。

第8章 虚拟内存

8.1 简单分页与虚拟分页有什么区别？

简单分页：一个程序中的所有的页都必须在主存储器中程序才能正常运行，除非使用覆盖技术。 拟内存分页：不是程序的每一页都必须在主存储器的帧中来使程序运行，页在需要的时候进行读取。 8.2 解释什么是抖动。

虚拟内存结构的震动现象，在这个过程中处理器大部分的时间都用于交换块，而不是执行指令。 8.3 为什么在使用虚拟内存时，局部性原理是至关重要的？

可以根据局部性原理设计算法来避免抖动。总的来说，局部性原理允许算法预测哪一个当前页在最近的未来是最少可能被使用的，并由此就决定候选的替换出的页。 8.4 哪些元素是页表项中可以找到的元素？简单定义每个元素。

帧号：用来表示主存中的页来按顺序排列的号码。 存在位（P）：表示这一页是否当前在主存中。 修改位（M）：表示这一页在放进主存后是否被修改过。 8.5 转移后备缓冲器的目的是什么？

转移后备缓冲器（TLB）是一个包含最近经常被使用过的页表项的高速缓冲存储器。它的目的是为了减少从磁盘中恢复一个页表项所需的时间。 8.6 简单定义两种可供选择的页读取策略。

在请求式分页中，只有当访问到某页中的一个单元时才将该页取入主存。 在预约式分页中，读取的并不是页错误请求的页。 8.7 驻留集管理和页替换策略有什么区别？

驻留集管理主要关注以下两个问题：（1）给每个活动进程分配多少个页帧。（2）被考虑替换的页集是仅限在引起页错误的进程的驻留集中选择还是在主存中所有的页帧中选择。

页替换策略关注的是以下问题：在考虑的页集中，哪一个特殊的页应该被选择替换。 8.8 FIFO和Clock页替换算法有什么区别？

7

时钟算法与FIFO算法很接近，除了在时钟算法中，任何一个使用位为一的页被忽略。 8.9 页缓冲实现的是什么？

（1）被替换出驻留集的页不久又被访问到时，仍在主存中，减少了一次磁盘读写。

（2）被修改的页以簇的方式被写回，而不是一次只写一个，这就大大减少了I/O操作的数目，从而减少了磁盘访问的时间。

8.10 为什么不可能把全局替换策略和固定分配策略组合起来？

固定分配策略要求分配给一个进程的帧的数目是确定的，当一个进程中取入一个新的页时，这个进程驻留页集中的一页必须被替换出来（保持分配的帧的数目不变），这是一种局部替换策略。 8.11 驻留集和工作集有什么区别？

一个进程的驻留集是指当前在主存中的这个进程的页的个数。一个进程的工作集是指这个进程最近被使用过的页的个数。

8.12 请求式清除和预约式清除有什么区别？

在请求式清除中，只有当一页被选择用于替换时才被写回辅存；

在预约式清除中，将这些被修改的多个页在需要用到它们所占据的页帧之前成批的写回辅存。

第9章 单处理器调度

9.1 简要描述三种类型的处理器调度。

长程调度：决定加入到待执行的进程池中；

中程调度：决定加入到部分或全部在主存中的进程集合中； 短程调度：决定哪一个可用进程将被处理器执行。 9.2 在交互式操作系统中，通常最重要的性能要求是什么？

反应时间

9.3 周转时间和响应时间有什么区别？

周转时间是一个要求花费在系统上的包括等待时间和服务时间的总的时间。响应时间对一个交互进程，这是指从提交一个请求到开始接受响应之间的时间间隔。通常进程在处理该请求的同时，就开始给用户产生一些输出。

9.4 对进程调度，较小的优先级值表示较低的优先级还是较高的优先级？

在UNIX和许多其他系统中，大的优先级值表示低优先级进程。许多系统，比如WINDOWS，刚好相反，大数值表示高优先级。

9.5 抢占式和非抢占式调度有什么区别？

非抢占：在这种情况下，一旦进程处于运行态，他就不断执行直到终止，或者为等待I/O或请求某些操作系统服务而阻塞自己。

抢占：当前正在运行的进程可能被操作系统中断，并转移到就绪态。关于抢占的决策可能是在一个新进程到达时，或者在一个中断发生后把一个被阻塞的进程置为就绪态时，或者基于周期性的时间中断。 9.6 简单定义FCFS调度。

当每个进程就绪后，它加入就绪队列。当当前正在运行的进程停止执行时，选择在就绪队列中存在时间最长的进程运行。 9.7 简单定义轮转调度

以一个周期性间隔产生时钟中断，当中断产生时，当前正在运行的的进程被置于就绪队列中，然后基于FCFS策略选择下一个就绪作业运行。 9.8 简单定义最短进程优先调度。

这是一个非抢占的策略，其原则是下一次选择所需处理时间最短的进程。 9.9 简单定义最短剩余时间调度。

最短剩余时间是针对SPN增加了抢占机制的版本。在这种情况下，调度器总是选择预期剩余时间最短的进程。当一个新进程加入到就绪队列时，他可能比当前运行的进程具有更短的剩余时间，因此，只

8

有新进程就绪，调度器就可能抢占当前正在运行的进程。 9.10 简单定义最高响应比优先调度。

在当前进程完成或被阻塞时，选择R值最大的就绪进程。R=(w+s)/s,w等待处理器的时间，s期待的服务时间。

9.1 1简单定义反馈调度。

调度基于抢占原则并且使用动态优先级机制。当一个进程第一次进入系统时，它被放置在RQ0。当它第一次被抢占后并返回就绪状态时，它被防止在RQ1。在随后的时间里，每当它被抢占时，它被降级到下一个低优先级队列中。一个短进程很快会执行完，不会在就绪队列中降很多级。一个长进程会逐级下降。因此，新到的进程和短进程优先于老进程和长进程。在每个队列中，除了在优先级最低的队列中，都使用简单的FCFS机制。一旦一个进程处于优先级最低的队列中，它就不可能再降低，但是会重复地返回该队列，直到运行结束。

第10章 多处理器和实时调度

10.1 列出并简单定义五种不同级别的同步粒度。

细粒度：单指令流中固有的并行；

中等粒度：在一个单独应用中的并行处理或多任务处理； 粗粒度：在多道程序环境中并发进程的多处理；

非常粗粒度：在网络节点上进行分布处理，以形成一个计算环境； 无约束粒度：多个无关进程。

10.2 列出并简单定义线程调度的四种技术。

加载共享：进程不是分配到一个特定的处理器，而是维护一个就绪进程的全局队列，每个处理器只要空闲就从队列中选择一个线程。这里使用术语加载共享来区分这种策略和加载平衡方案，加载平衡是基于一种比较永久的分配方案分配工作的。

组调度：一组相关的线程基于一对一的原则，同时调度到一组处理器上运行。

专用处理器分配：在程序执行过程中，每个程序被分配给一组处理器，处理器的数目与程序中的线程的数目相等。当程序终止是，处理器返回到总的处理器池中，可供分配给另一个程序。 动态调度：在执行期间，进程中线程的数目可以改变。 10.3 列出并简单定义三种版本的负载分配。

先来先服务（FCFS）：当一个作业到达时，它的所有线程都被连续地放置在共享队列末尾。当一个处理器变得空闲时，它选择下一个就绪线程执行，直到完成或阻塞。 最少线程数优先：共享就绪队列被组织成一个优先级队列，如果一个作业包含的未调度线程数目最少，则给它指定最高的优先级。具有同等优先级的队列按作业到达的顺序排队。和FCFS一样，被调度的线程一直运行到完成或阻塞。

可抢占的最少线程数优先：最高的的优先级给予包含的未被调度的线程数目最少的作业。刚到达的作业如果包含的线程数目少于正在执行的作业，它将抢占属于这个被调度作业的线程。 10. 硬实时任务和软实时任务有什么区别？

硬实时任务指必须满足最后期限的限制，否则会给系统带来不可接受的破坏或者致命的错误。

软实时任务也有一个与之相关联的最后期限，并希望能满足这个期限的要求，但是这并不是强制的，即使超过了最后期限，调度和完成这个任务仍然是有意义的。 10.5 周期性实时任务和非周期性实时任务有什么区别？

非周期任务有一个必须结束或开始的最后期限，或者有一个关于开始时间和结束时间的约束。而对于周期任务，这个要求描述成“每隔周期T一次”或“每隔T个单位”。 10.6 列出并简单定义对实时操作系统的五方面的要求。

可确定性：在某中程度上是指它可以按固定的、预先确定的时间或时间间隔执行操作。 可响应性：它关注的是在知道中断之后操作系统未中断提供服务的时间

9

用户控制：用户应该能够区分硬实时任务和软实时任务，并且在每一类中确定相对优先级。实时系统还允许用户指定一些特性，例如使用分页还是进程交换、哪一个进程必须常驻主存、使用何种磁盘算法、不同的优先级的进程各有哪些权限等。

可靠性 ：可靠性必须提供这样一种方式，以继续满足实时最后期限。

故障弱化操作：故障弱化操作指系统在故障时尽可能多的保存其性能和数据的能力。 10.7 列出并简单定义四类实时调度算法。

静态表驱动法：执行关于可行调度的静态分析。分析的结果是一个调度，它用于确定在运行时一个任务何时必须开始执行。

静态优先级驱动抢占法：同样，执行一个静态分析，但是没有制定调度，而且用于给任务指定优先级，使得可以使用传统的优先级驱动的抢占式调度器。

基于动态规划调度法：在运行是动态地确定可行性，而不是在开始运行前离线的确定（静态）。一个到达的任务，只有当能够满足它的时间约束时，才可以被接受执行。可行性分析的结果是一个调度或规划，可用于确定何时分派这个任务。

动态尽力调度法：不执行可行性分析。系统试图满足所有的最后期限，并终止任何已经开始运行但错过最后期限的进程。

10.8 关于一个任务的哪些信息在实时调度是非常有用？

就绪时间：任务开始准备执行的时间。对于重复或周期性的任务，这实际上是一个事先知道的时间序列。而对于非周期性的任务，或者也事先知道这个时间，或者操作系统仅仅知道什么时候任务真正就绪。

启动最后期限：任务必须开始的时间。

完成最后期限：任务必须完成的时间。典型的实时应用程序或者有启动最后期限，或者有完成最后期限，但不会两者都存在。

处理时间：从执行任务直到完成任务所需的时间。在某些情况下，可以提供这个时间，而在另外一些情况下，操作系统度量指数平均值。其他调度系统没有使用这个信息。 资源需求：任务在执行过程中所需的资源集合（处理器以外的资源）。

优先级：度量任务的相对重要性。硬实时任务可能具有绝对的优先级，因为如果错过最后期限则会导致系统失败。如果系统无论如何也要继续运行，则硬实时任务和软实时任务可以被指定相关的优先级，以指导调度器。

子任务结构：一个任务可以分解成一个必须执行的子任务和一个可选的子任务。只有必须执行的子任务拥有硬最后期限。

第11章 I/O管理和磁盘调度

11.1 列出并简单定义执行I/O的三种技术。

可编程I/O：处理器代表进程给I/O模块发送给一个I/O命令，该进程进入忙等待，等待操作的完成，然后才可以继续执行。

中断驱动I/O：处理器代表进程向I/O模块发送一个I/O命令，然后继续执行后续指令，当I/O模块完成工作后，处理器被该模块中断。如果该进程不需要等待I/O完成，则后续指令可以仍是该进程中的指令，否则，该进程在这个中断上被挂起，处理器执行其他工作。 直接存储器访问（DMA）：一个DMA模块控制主存和I/O模块之间的数据交换。为传送一块数据，处理器给DMA模块发送请求，只有当整个数据块传送完成后，处理器才被中断。 11.2 逻辑I/O和设备I/O有什么区别？

逻辑I/O：逻辑I/O模块把设备当作一个逻辑资源来处理，它并不关心实际控制设备的细节。逻辑I/O模块代表用户进程管理的一般I/O功能，允许它们根据设备标识符以及诸如打开、关闭、读、写之类的简单命令与设备打交道。

设备I/O：请求的操作和数据（缓冲的数据、记录等）被转换成适当的I/O指令序列、通道命令和控

10

制器命令。可以使用缓冲技术，以提高使用率。

11.3 面向块的设备和面向流的设备有什么区别？请举例说明。

面向块的设备将信息保存在块中，块的大小通常是固定的，传输过程中一次传送一块。通常可以通过块号访问数据。磁盘和磁带都是面向块的设备。

面向流的设备以字节流的方式输入输出数据，其末使用块结构。终端、打印机通信端口、鼠标和其他指示设备以及大多数非辅存的其他设备，都属于面向流的设备。 11.4 为什么希望用双缓冲区而不是单缓冲区来提高I/O的性能？

双缓冲允许两个操作并行处理，而不是依次处理。典型的，在一个进程往一个缓冲区中传送数据（从这个缓冲区中取数据）的同时，操作系统正在清空（或者填充）另一个缓冲区。 11.5 在磁盘读或写时有哪些延迟因素？

寻道时间，旋转延迟，传送时间

11.6 简单定义图11.7中描述的磁盘调度策略。

FIFO:按照先来先服务的顺序处理队列中的项目。

SSTF:选择使磁头臂从当前位置开始移动最少的磁盘I/O请求。

SCAN:磁头臂仅仅沿一个方向移动，并在途中满足所有未完成的请求，直到它到达这个方向上最后一个磁道，或者在这个方向上没有其他请求为止。接着反转服务方向，沿相反方向扫描，同样按顺序完成所有请求。

C-SCAN:类似于SCAN， 11.7 简单定义图7层RAID。

0：非冗余

1：被镜像；每个磁盘都有一个包含相同数据的镜像磁盘。

2：通过汉明码实现冗余；对每个数据磁盘中的相应都计算一个错误校正码，并且这个码位保存在多个奇偶校验磁盘中相应的文件。

3：交错位奇偶校验；类似于第二层，不同之处在于RAID3为所有数据磁盘中同一位置的位的集合计算一个简单的奇偶校验位，而不是错误校正码。

4：交错块分布奇偶校验；对每个数据磁盘中相应的条带计算一个逐位奇偶。 5：交错块分布奇偶校验；类似于第四层，但把奇偶校验条带分布在所有磁盘中。 6：交错块双重分布奇偶校验；两种不同的奇偶校验计算保存在不同磁盘的不同块中。 11.8 典型的磁盘扇区大小是多少？

512比特

第12章 文件管理

12.1 域和记录有什么不同？

域（field）是基本数据单位。一个域包含一个值。

记录（record）是一组相关的域的集合 ，它可以看做是应用程序的一个单元。 12.2 文件和数据库有什么不同？

文件（file）是一组相似记录的集合，它被用户和应用程序看做是一个实体，并可以通过名字访问。 数据库（database）是一组相关的数据集合，它的本质特征是数据元素间存在着明确的关系，并且可供不同的应用程序使用。 12.3 什么是文件管理系统？

文件管理系统是一组系统软件，为使用文件的用户和应用程序提供服务。 12.4 选择文件组织时的重要原则是什么？

访问快速，易于修改，节约存储空间，维护简单，可靠性。 12.5 列出并简单定义五种文件组织。

堆是最简单的文件组织形式。数据按它们到达的顺序被采集，每个记录由一串数据组成。

11

顺序文件是最常用的文件组织形式。在这类文件中，每个记录都使用一种固定的格式。所有记录都具有相同的长度，并且由相同数目、长度固定的域按特定的顺序组成。由于每个域的长度和位置已知，因此只需要保存各个域的值，每个域的域名和长度是该文件结构的属性。 索引顺序文件保留了顺序文件的关键特征：记录按照关键域的顺序组织起来。但它还增加了两个特征：用于支持随机访问的文件索引和溢出文件。索引提供了快速接近目标记录的查找能力。溢出文件类似于顺序文件中使用的日志文件，但是溢出文件中的记录可以根据它前面记录的指针进行定位。

索引文件：只能通过索引来访问记录。其结果是对记录的放置位置不再有限制，只要至少有一个索引的指针指向这条记录即可。此外，还可以使用长度可变的记录。 直接文件或散列文件：直接文件使用基于关键字的散列。

12.6 为什么在索引顺序文件中查找一个记录的平均搜索时间小于在顺序文件中的平均搜索时间？

在顺序文件中，查找一个记录是按顺序检测每一个记录直到有一个包含符合条件的关键域值的记录被找到。索引顺序文件提供一个执行最小穷举搜索的索引结构。 12.7 对目录执行的典型操作有哪些？

搜索，创建文件，删除文件，显示目录，修改目录。 12.8 路径名和工作目录有什么关系？

路径名是由一系列从根目录或主目录向下到各个分支，最后直到该文件的路径中的目录名和最后到达的文件名组成。工作目录是一个这样的目录，它是含有用户正在使用的当前目录的树形结构。 12.9 可以授予或拒绝的某个特定用户对某个特定文件的访问权限通常有哪些？

无（none），知道（knowledge），执行（execution），读(reading)，追加（appending），更新（updating），改变保护（changing protection），删除（deletion）。 12.10 列出并简单定义三种组块方式。

固定组块（fixed blocking）：使用固定长度的记录，并且若干条完整的记录被保存在一个块中。在每个块的末尾可能会有一些未使用的空间，称为内部碎片。 可变长度跨越式组块（variable-length spanned blocking）：使用长度可变的记录，并且紧缩到块中，使得块中没有未使用空间。因此，某些记录可能会跨越两个块，通过一个指向后继块的指针连接。 可变长度非跨越式组块（variable-length unspanned blocking）：使用可变长度的记录，但并不采用跨越的方式。如果下一条记录比块中剩余的未使用空间大，则无法使用这一部分，因此在大多数块中都会有未使用的空间。

12.11 列出并简单定义三种文件分配方法。

连续分配是指在创建文件时，给文件分配一组连续的块。链式分配基于单个的块，链中的每一块都包含指向下一块的指针。索引分配：每个文件在文件分配表中有一个一级索引，分配给该文件的每个分区在索引中都有一个表项。

第13章 网 络

13.1 网络访问层的主要功能是什么？

网络层主要关注在两个端系统（服务器、工作站）之间的数据交换，以及端系统间的物理网络。 13.2 传输层的任务是什么？

传输层关注的是数据的可靠性和保证数据能正确到达接收端应用程序。 13.3 什么是协议？

协议是定义了用来管理两个单元间进行数据交换的一系列规则的集合。 13.4 什么是协议体系结构？

这是一种实现通信功能的软件结构。典型地，协议结构包含了一个分层化的协议集，并且每个层中有一个或多个协议。 13.5 什么是TCP/IP？

传输控制协议/互联网协议（TCP/IP）是两个最初为网际互连提供低层支持而设计的协议。TCP/IP协

12

也被广泛应用于涉及由美国防卫部门和因特尔团体发展的比较广泛的协议集。 13.6 使用套接字接口的目的是什么？

套接字接口是一个能够编写程序的API，从而利用TCP/IP 协议程序建立一个用户端和服务器之间的通信。

第14章 分布式处理、客户/服务器和集群

14.1 什么是客户/服务器计算？

客户/服务器计算是一个网络环境，在这个网络环境中包含着客户机和服务器，并由服务器来响应客户机的请求。

14.2 客户/服务器计算与任何其他形式的分布式数据处理的区别是什么？

1、在用户的本地系统上为该用户提供界面友好的应用程序，这样做可使系统具有更高的可靠性。这使得用户可以在很大程度上控制对计算机的使用方式和时间，并使得部门级管理者具有响应本地需求的能力。

2、尽管应用是分散开的，但仍然强调公司数据库的集中以及很多网络管理和使用功能的集中。这使公司的管理者能够对计算信息系统的投资总额进行总体控制，并提供互操作，以使多系统能够配合起来。同时，减少了各部门和单位在维护这些复杂的计算机设施时的开销，使他们能够选择他们需要的各种类型的机器和接口来访问那些数据和信息。

3、对于用户组织和厂商来说，他们有一个共同的承诺事项，即使系统开放和模块化。这意味着用户在选择产品和混和使用来自众多厂商的设备时具有很多选择。

4、网络互联是操作的基础，网络管理和网络安全在组织和操作信息系统中具有很高的优先权。 14.3 像TCP/IP这样的通信结构在客户/服务器计算环境中的作用是什么？

它是使客户端和服务器能够协同工作的通信软件。

14.4 讨论将应用程序定位在客户上、服务器上或分开定位在客户和服务器上的基本原理。

基于服务器的处理：这种配置的基本原理是用户工作站最适宜于提供良好的用户界面，并且数据库和应用程序很容易在中心系统上维护。尽管用户获得了良好界面的好处，但是，这种配置类型并不总能有效提高处理效率或系统支持的实际商业功能上有本质的改变。基于客户的处理：它使用户能够使用适应本地需要的应用。合作处理：这种配置类型可以比其他客户/服务器方式为用户提供更高的生产效率和更高的网络效率。

14.5 什么是胖客户和瘦客户，两种方法在基本原理上的差别是什么？

胖客户：这是基于客户的处理，而大部分的软件都集中在客户端。胖客户模型的主要优点是它充分利用了桌面功能，分担了服务器上的应用处理并使它们更加有效，不容易产生瓶颈。

瘦客户：这是基于服务器的处理，而大部分的软件都集中在服务器。这种方式更近似地模拟了传统的以主机为中心的方式，常常是使将公司范围的应用程序从大型机环境迁移到分布式环境的途径。 14.6 给出将pros和cons用于胖客户和瘦客户策略的建议。

胖客户：胖客户模型的主要优点是它充分利用了桌面功能，分担了服务器上的应用处理并使它们更加有效，不容易产生瓶颈。新增加的功能很快就超出了桌面机器的处理能力，迫使公司进行升级。如果模型扩充超出了部门的界限，合并了很多用户，则公司必须安装高容量局域网来支持在瘦服务器和胖客户之间进行大量的传输。最后，维护、升级或替换分布于数十台或数百台桌面机的应用程序将变得非常困难。瘦客户：这种方式更近似地模拟了传统的以主机为中心的方式，常常是使将公司范围的应用程序从大型机环境迁移到分布式环境的途径。但是它不能提供和胖客户策略一样的灵活性。 14.7 解释三层客户/服务器体系结构的基本原理。

中间层机器基本上是位于用户客户和很多后端数据库服务器之间的网关。中间层机器能够转换协议，将对一种类型的数据库查询映像为另一种类型数据库的查询。另外，中间层机器能够融合来自不同数据源的结果。最后，中间层机器因介于两个层次之间而可以充当桌面应用程序和后端应用程序之间的网关。

13

14.8 什么是中间件？

中间件是在上层应用程序和下层通信软件和操作系统之间使用标准的编程接口和协议。它提供统一的方式和方法来跨越各种平台访问系统资源。

14.9 既然具有像TCP/IP这样的标准，为什么还需要中间件？

TCP/IP不提供API和中间层协定来支持应用于不同的硬件和操作系统的多种应用程序平台。 14.10 列出消息传递的阻塞原语和无阻塞原语的优缺点。

无阻塞原语为进程提供了对消息传递机制高效而灵活的使用，这种方法的缺点是难于测试和调试使用这些原语的程序。问题的不可再现性与时间顺序相关性往往导致产生很多奇怪而麻烦的问题。阻塞原语有与无阻塞原语相反的优缺点。

14.11 列出远程过程调用的非永久性和永久性绑定的优缺点。

非永久绑定：因为连接需要维持两端的状态信息，因此需要消耗资源，非永久绑定类型用于保存这些资源。另一方面，建立连接所带来的开销使非永久绑定对同一个调用者频繁调用远程过程的情况不太适用。

永久绑定：对于对远程过程进行多次重复调用的应用程序，永久绑定保持着逻辑连接，并支持使用同一连接进行一系列的调用和返回。

14.12 列出同步远程过程调用和异步远程过程调用的优缺点。

同步远程过程调用易于理解和编程，因为它的行为是可以预期的。然而，它未能发挥分布式应用中固有的全部并行性。这就限制了分布式应用所能具有的交互性，降低了性能。为了提供更大的灵活性，各种异步远程过程调用机制已经得到实现，以获得更大程度的并行性而同时又保留了远程过程调用的通俗性和简易性。异步远程过程调用并不阻塞调用者，应答也可以在需要它们时接收到，这使客户在本地的执行可以与对服务器的调用并行进行。 14.13 列出并简短定义四种不同的构建集群的方法。

被动等待：当主服务器出现故障时，由从服务器来接管。

分离服务器：各服务器具有独自的磁盘，数据可连续地从主服务器复制至从服务器。

各服务器连接到磁盘：所有服务器都连接到同一磁盘，但每台服务器仍拥有自己的磁盘，一旦某台服务器发生故障，则其磁盘被其他服务器接管。 共享磁盘：多台服务器同时共享对磁盘的访问。

第15章 分布式进程管理

15.1 讨论实现进程迁移的原因。

负载共享：通过将进程从负载较重的系统迁移到负载较轻的系统，负载就会得到平衡，从而提高整体性能。通信性能：可以将交互密集的多个进程移动到同一节点上，以减少因为它们之间的交互而带来的通信开销。同样，当一个进程在某些文件或某组文件上执行数据分析，且文件的大小比进程要大很多时，将该进程移动到数据端也许是更有利的。可用性：需要长时间运行的进程，在得到错误的预先通知时，或者在预定的关机时间之前，为了能够存活下来，可能需要迁移到其他机器中。如果操作系统提供了这样的通知，则那些需要继续运行的进程可以迁移到另一个系统上，或者保证在稍后的某个时间在当前系统上能重新启动。特殊功能的使用：进程的迁移可以充分利用特定节点上独特的硬件或软件功能。

15.2 在进程迁移过程中，进程地址空间是如何处理的？

下列策略可能被采用：Eager（all）：在迁移时转移整个地址空间。 预先复制（precopy）：进程继续在源节点上执行，而地址空间已经复制到了目标节点上。在预先复制的过程中，源节点上的某些页有可能又被修改，这些页必须被复制第二次。 Eager（dirty）：仅仅转移那些位于主存中且已被修改了的地址空间的页。虚地址空间的所有其他块将在需要时才转移。

基于引用的复制（copy-on-reference）：这是Eager（dirty）的变体，只有在引用某页时，该页才被

14

取入。

刷新（flushing）：通过把脏页写回磁盘，该进程的页可以从源机器的主存中清除。这样，在需要时可以从磁盘访问到页，而不是从源节点的存储器中访问。 15.3 抢占式和非抢占式进程迁移的动机是什么？

非抢占式进程迁移对于负载平衡是很有用的，它的优点是能够避免全面性进程迁移的开销，缺点是该方法对于负载分布的突然变化反应不佳。 15.4 为什么不可能确定真正的全局状态？

因为系统之间的通信延迟，不可能在系统范围内维护一个所有系统都随时可用的时钟。而且，维护一个中央时钟并让所有本地时钟与之保持精确同步，这在技术上也是不现实的，因为经过一段时间后，在各个本地时钟之间就会产生一些偏差，这将导致同步的丢失。 15.5 集中式算法和分布式算法所实行的分布式互斥有何区别？

在完全集中式算法中，一个节点被指定为控制节点，它控制对所有共享对象的访问。当任何进程请求对一个临界资源进行访问时，就向本地资源控制进程发送一个请求，这个进程接着向控制节点发送一条请求消息，当共享对象可用时，将返回一条许可消息。当进程结束使用资源后，向控制节点发送一条释放消息。

在分布式算法中，互斥算法涉及到每个离散的实体之间的同步合作。 15.6 定义两种类型的分布式死锁。

在资源分配中产生的死锁以及由于消息通信而产生的死锁。

第16章 安全

16.1 计算机安全的基础要求是什么？

机密性，完整性，可用性，可靠性。

16.2 主动安全攻击和被动安全攻击有什么不同？

被动攻击在本质上是对传输进行窃听或监视。对方的目标是获取正在传输的信息。主动攻击包括对数据或数据流的更改或者生成错误的数据或数据流。

16.3 列出并简单定义主动安全攻击和被动安全攻击的分类。

被动攻击：①释放消息内容：未被授权的人或程序了解了文件或消息的内容；②通信分析：通过分析数据传输模式来获取信息。

主动攻击：①伪装：一个实体假装成另一个不同的实体；②重放：被动地捕获一个数据单元，然后再把它重发以产生未经授权的结果；③更改消息：改变合法消息的某些部分，或者消息被延迟或记录下来，产生未授权的结果；④拒绝服务：阻止或禁止对通信设施的正确使用或管理。 16.4 大多数通用的用户访问控制技术都要求有哪些元素？

在共享系统或服务器上，用户访问控制的最普遍的技术是用户登录，这需要一个用户标识符（ID）和一个口令。

16.5 在访问控制中，主体和对象有什么区别？

主体（subject）：能够访问对象的实体。一般地，主体概念等同于进程。任何用户或应用程序获取对一个对象的访问，实际上是通过一个代表该用户或应用程序的进程。 对象（object）：访问控制所针对的一切。例如文件、文件的某些部分、程序、内存段以及软件对象。 16.6 解释图16.6中salt的目的。

salt有三方面的作用：⑴防止在口令文件中出现相同的口令。即使有两个用户选择了相同的口令，那些口令也将被指定不同的时间，因此，两个用户的“扩展”口令是不同的。⑵有效地增加口令的长度，而不要求用户记住那两个额外的字符。因此，可能的口令个数增加了4096，从而增加了猜测口令的难度。⑶防止使用DES的硬件实现，硬件实现会使蛮力猜测攻击变得容易。 16.7 解释统计异常入侵检测和基于规则的入侵检测有什么不同？

统计异常检测：包括收集在一段时间上与合法用户的行为有关的数据。然后对观察到的行为进行统计

15

试验，以高度的信心来确定该行为是否是合法用户的行为。基于规则的检测：包括定义一组规则的工作，该组规则用于决定一个已知的行为是否是入侵者的行为。

16.8 1999年和2000年开发的电子邮件附件和电子邮件VBS恶意软件（如Melissa、love letter）称为电子邮件病毒。请问用术语电子邮件蠕虫是否更正确一些？

这两种术语都合适。术语电子邮件蠕虫通常是一个独立的程序而不是嵌入其他程序的一个程序块，因此电子邮件病毒更正确一些。

16.9 加密在病毒设计中扮演着什么角色？

加密技术将以如下方式被使用：有一部分病毒，一般称为变种引擎，它生成一个随机的密钥来加密病毒剩余的部分。该密钥与病毒一起存储，变种引擎自身却改变了。当受到感染的程序唤起执行时，病毒使用这个存储的随机密钥来解密病毒。当病毒复制时，选择另一个不同的随机密钥。 16.10 攻击常规加密方案的两种通用方法什么？

密码分析：依靠算法的本质和关于明文一般特点的知识，甚至一些“明文-密文对”来进行攻击。这类攻击利用算法的特性，试图推导出具体的明文，或者推导出使用的密钥。

强力攻击：它在一块密文上尝试每种可能的密钥，直到转换得到一个可理解的明文。 16.11 什么是DES和三重DEA？

DES是被NIST标准化的一个广泛应用的传统编码标准。最初的DES指定了一个数据编码运算法则(DEA)。最近的标准的版本也包括使用三重DEA的选择项,用二或三个独立的密钥重复基本的DEA三次。 16.12 AES是如何改进三重DEA的？

AES被期望在软件中运行得比TDEA更快。同时, AES使用更大的块尺寸,这可以提高安全性。 16.13 在评估AES候选者时，将使用什么评估原则？

评估原则包括安全性、计算效率、需要的存储量、硬件和软件的适用性和灵活性。 16.14 解释常规加密和公钥加密有什么不同。

在传统编码中，编码和解码使用相同的密钥。公钥编码中有一对密钥,一个用于编码而另一个用于解码。 这二个密钥中只有一个需要被保留私用。 16.15 术语公钥、私钥和密钥的区别是什么？

对称加密中的密钥通常称为密钥。公钥加密中使用的两个密钥称为公钥和私钥。私钥总是保密的，之所以将它称为私钥，是为了避免与对称加密中的密钥混淆。

练习题答案

第1章 计算机系统概述

1.1、图1.3中的理想机器还有两条I/O指令： 0011 = 从I/O中载入AC 0111 = 把AC保存到I/O中

在这种情况下，12位地址标识一个特殊的外部设备。请给出以下程序的执行过程（按照图1.4的格式）：

1. 从设备5中载入AC。

2. 加上存储器单元940的内容。 3. 把AC保存到设备6中。

假设从设备5中取到的下一个值为3940单元中的值为2。 答案：存储器（16进制内容）：300：3005；301：5940；302：7006 步骤1：3005－>IR；步骤2：3－>AC

步骤3：5940－>IR；步骤4：3＋2＝5－>AC 步骤5：7006－>IR：步骤6：AC－>设备 6

16

1.2、本章中用6步来描述图1.4中的程序执行情况，请使用MAR和MBR扩充这个描述。 答案：1. a. PC中包含第一条指令的地址300，该指令的内容被送入MAR中。

b. 地址为300的指令的内容（值为十六进制数1940）被送入MBR，并且PC增1。这两个步骤

是并行完成的。

c. MBR中的值被送入指令寄存器IR中。

2. a. 指令寄存器IR中的地址部分（940）被送入MAR中。 b. 地址940中的值被送入MBR中。 c. MBR中的值被送入AC中。

3. a. PC中的值（301）被送入MAR中。

b. 地址为301的指令的内容（值为十六进制数5941）被送入MBR，并且PC增1。 c. MBR中的值被送入指令寄存器IR中。

4. a. 指令寄存器IR中的地址部分（941）被送入MAR中。 b. 地址941中的值被送入MBR中。

c. AC中以前的内容和地址为941的存储单元中的内容相加，结果保存到AC中。 5. a. PC中的值（302）被送入MAR中。

b. 地址为302的指令的内容（值为十六进制数2941）被送入MBR，并且PC增1。 c. MBR中的值被送入指令寄存器IR中。

6. a. 指令寄存器IR中的地址部分（941）被送入MAR中。 b. AC中的值被送入MBR中。

c. MBR中的值被存储到地址为941的存储单元之中。

1.4、假设有一个微处理器产生一个16位的地址（例如，假设程序计数器和地址寄存器都是16位）并且具有一个16位的数据总线。

a.如果连接到一个16位存储器上，处理器能够直接访问的最大存储器地址空间为多少？ b.如果连接到一个8位存储器上，处理器能够直接访问的最大存储器地址空间为多少？ c.处理访问一个独立的I/O空间需要哪些结构特征？

d.如果输入指令和输出指令可以表示8位I/O端口号，这个微处理器可以支持多少8位I/O端口？

答案：对于(a)和(b)两种情况，微处理器可以直接访问的最大存储器地址空间为216 = 64K bytes；唯一的区

别是8位存储器每次访问传输1个字节，而16位存储器每次访问可以传输一个字节或者一个16位的字。对于(c)情况，特殊的输入和输出指令是必要的，这些指令的执行体会产生特殊的“I/O信号”（有别于“存储器信号”，这些信号由存储器类型指令的执行体产生）；在最小状态下，一个附加的输出针脚将用来传输新的信号。对于(d)情况，它支持28 = 256个输入和28 = 256个输出字节端口和相同数目的16位I/O端口；在任一情况, 一个输入和一个输出端口之间的区别是通过被执行的输入输出指令所产生的不同信号来定义的。

1.5、考虑一个32位微处理器，它有一个16位外部数据总线，并由一个8MHz的输入时钟驱动。假设这个微处理器有一个总线周期，其最大持续时间等于4个输入时钟周期。请问该微处理器可以支持的最大数据传送速度为多少？外部数据总线增加到21位，或者外部时钟频率加倍，哪种措施可以更好地提高处理器性能？请叙述你的设想并解释原因。 答案：时钟周期＝1/（8MHZ）＝125ns

总线周期＝4×125ns＝500ns

每500ns传输2比特；因此传输速度＝4MB/s

加倍频率可能意味着采用了新的芯片制造技术（假设每个指令都有相同的时钟周期数）；加倍外部数据总线，在芯片数据总线驱动/锁存、总线控制逻辑的修改等方面手段广泛（或许更新）。在第一种方案中，内存芯片的速度要提高一倍（大约），而不能降低微处理器的速度；第二种方案中，内存的字长必须加倍，以便能发送/接受32位数量。

1.6、考虑一个计算机系统，它包含一个I/O模块，用以控制一台简单的键盘/打印机电传打字设备。CPU中包含下列寄存器，这些寄存器直接连接到系统总线上：

17

INPR：输入寄存器，8位 OUTR：输出寄存器，8位 FGI：输入标记，1位 FGO：输出标记，1位 IEN：中断允许，1位

I/O模块控制从打字机中输入击键，并输出到打印机中去。打字机可以把一个字母数字符号编码成一个8位字，也可以把一个8位字解码成一个字母数字符号。当8位字从打字机进入输入寄存器时，输入标记被置位；当打印一个字时，输出标记被置位。

a. 描述CPU如何使用这4个寄存器实现与打字机间的输入/输出。 b. 描述通过使用IEN，如何提高执行效率？

答案：a.来源于打字机的输入储存在INPR中。只有当FGI＝0时，INPR才会接收来自打字机的数据。当

数据接收后，被储存在INPR里面，同时FGI置为1。CPU定期检查FGI。如果FGI＝1，CPU将把INPR里面的内容传送至AC，并把FGI置为0。

当CPU需要传送数据到打字机时，它会检查FGO。如果FGO＝0，CPU处于等待。如果FGO

＝1，CPU将把AC的内容传送至OUTER并把FGO置为0。当数字符号打印后，打字机将把FGI置为1。

b.（A）描述的过程非常浪费。速度远高于打字机的CPU必须反复不断的检查FGI和FGO。如果中

断被使用，当打字机准备接收或者发送数据时，可以向CPU发出一个中断请求。IEN计数器可以由CPU设置（在程序员的控制下）。

1.7、实际上在所有包括DMA模块的系统中，DMA访问主存储器的优先级总是高于处理器访问主存储器的优先级。这是为什么?

答案：如果一个处理器在尝试着读或者写存储器时被挂起, 通常除了一点轻微的时间损耗之外没有任何危

害。但是，DMA可能从或者向设备(例如磁盘或磁带)以数据流的方式接收或者传输数据并且这是不能被打断的。否则，如果DMA设备被挂起（拒绝继续访问主存），数据可能会丢失。

1.9、一台计算机包括一个CPU和一台I/O设备D，通过一条共享总线连接到主存储器M，数据总线的宽度为1个字。CPU每秒最多可执行106条指令，平均每条指令需要5个机器周期，其中3个周期需要使用存储器总线。存储器读/写操作使用1个机器周期。假设CPU正在连续不断地执行后台程序，并且需要保证95%的指令执行速度，但没有任何I/O指令。假设1个处理器周期等于1个总线周期，现在要在M和D之间传送大块数据。 a.若使用程序控制I/O，I/O每传送1个字需要CPU执行两条指令。请估计通过D的I/O数据传送的最大可能速度。

b.如果使用DMA传送，请估计传送速度。

答案：a.处理器只能分配5％的时间给I/O.所以最大的I/O指令传送速度是10e6×0.05＝50000条指令/秒。

因此I/O的传送速率是25000字/秒。

b.使用DMA控制时，可用的机器周期下的数量是

10e6（0.05×5＋0.95×2）＝2.15×10e6

如果我们假设DMA模块可以使用所有这些周期，并且忽略任何设置和状态检查时间，那么这个值就是最大的I/O传输速率。 1.10、考虑以下代码：

for ( i = 0；i < 20；i++) for (j = 0；j < 10；j++) a[i] = a[i]*j

a. 请举例说明代码中的空间局部性。 b. 请举例说明代码中的时间局部性。

答案：a.读取第二条指令是紧跟着读取第一条指令的。

b.在很短的间歇时间内， a[i]在循环内部被访问了十次。

18

1.11、请将附录1A中的式（1.1）和式（1.2）推广到n级存储器层次中。 答案：定义：

Ci = 存储器层次i上每一位的存储单元平均花销 Si = 存储器层次i的规模大小

Ti = 存储器层次i上访问一个字所需时间

Hi = 一个字在不高于层次i的存储器上的概率

Bi = 把一个数据块从层次i+1的存储器上传输到层次i的存储器上所需时间

高速缓冲存储器作为是存储器层次1；主存为存储器层次2；针对所有的N层存储器层以此类推。有：

CS??CSii?1nni

i?Si?1 Ts的引用更复杂，我们从概率论入手：所期望的值x?n?iPr[x?1]，由此我们可以写出：

i?1nTs??TiHi

i?1我们需要清楚如果一个字在M1（缓存）中，那么对它的读取非常快。如果这个字在M2而不在M1中，那么数据块需要从M2传输到M1中，然后才能读取。因此，T2 = B1+T1 进一步，T3 = B2+T2 = B1+B2+T1 以此类推：Ti?n?Bj?1i?1i?1j?T1

n所以，Ts?n??(BH)?T?Hji1i?2j?1i?1ii

但是，

?Hi?1?1

ni?1最后，Ts???(BH)?T

ii1i?2j?11.12、考虑一个存储器系统，它具有以下参数： Tc = 100 ns Cc = 0.01 分/位 Tm = 1200 ns Cm = 0.001 分/位 a.1MB的主存储器价格为多少？

b.使用高速缓冲存储器技术，1MB的主存储器价格为多少？

c.如果有效存取时间比高速缓冲存储器存取时间多10% ，命中率H为多少？ 答案：a.价格 = Cm×8×106 = 8×103 ￠ = ＄80 b.价格 = Cc×8×106 = 8×104 ￠ = ＄800 c.由等式1.1知：1.1×T1 = T1+(1-H)T2 (0.1)(100) = (1-H)(1200) H=1190/1200

1.13、一台计算机包括包括高速缓冲存储器、主存储器和一个用做虚拟存储器的磁盘。如果要存取的字在

19

高速缓冲存储器中，存取它需要20ns；如果该字在主存储器中而不在高速缓冲存储器中，把它载入高速缓冲存储器需要60ns（包括最初检查高速缓冲存储器的时间），然后再重新开始存取；如果该字不在主存储器中，从磁盘中取到内存需要12ms，接着复制到高速缓冲存储器中还需要60ns，再重新开始存取。高速缓冲存储器的命中率为0.9，主存储器的命中率为0.6，则该系统中存取一个字的平均存取时间是多少（单位为ns）？

答案：有三种情况需要考虑：

字所在的位置 在缓存中 不在缓存，在主存中 不在缓存也不在主存中 概率 0.9 （0.1）（0.6）= 0.06 （0.1）（0.4）= 0.04 访问所需时间（ns） 20 60+20 = 80 12ms+60+20 = 12,000,080 所以平均访问时间是：Avg = (0.9)(20) + (0.06)(80) + (0.04)(12000080) = 480026 ns 1.14、假设处理器使用一个栈来管理过程调用和返回。请问可以取消程序计数器而用栈指针代替吗？ 答案：如果栈只用于保存返回地址。或者如果栈也用于传递参数，这种方案只有当栈作为传递参数的控制

单元而非机器指令时才成立。这两种情况下可以取消程序计数器而用栈指针代替。在后者情况中，处理器同时需要一个参数和指向栈顶部的程序计数器。

第2章 操作系统概述

2.1假设我们有一台多道程序的计算机，每个作业有相同的特征。在一个计算周期T中，一个作业有一半时间花费在I/O上，另一半用于处理器的活动。每个作业一共运行N个周期。假设使用简单的循环法调度，并且I/O操作可以与处理器操作重叠。定义以下量： ?时间周期=完成任务的实际时间

?吞吐量=每个时间周期T内平均完成的作业数目

?处理器使用率=处理器活跃（不是处于等待）的时间的百分比

当周期T分别按下列方式分布时，对1个、2个和4个同时发生的作业，请计算这些量： a. 前一般用于I/O，后一半用于处理器。

b. 前四分之一和后四分之一用于I/O，中间部分用于处理器。 答：（a）和（b）的答案相同。尽管处理器活动不能重叠，但I/O操作能。 一个作业 时间周期=NT 处理器利用率=50﹪ 两个作业 时间周期=NT 处理器利用率=100﹪ 四个作业 时间周期=（2N-1）NT 处理器利用率=100﹪

2.2 I/O限制的程序是指如果单独运行，则花费在等待I/O上的时间比使用处理器的时间要多的程序。处理器限制的程序则相反。假设短期调度算法偏爱那些在近期石油处理器时间较少的算法，请解释为什么这个算法偏爱I/O限制的程序，但是并不是永远不受理处理器限制程序所需的处理器时间？

受I/O限制的程序使用相对较少的处理器时间，因此更受算法的青睐。然而，受处理器限制的进程如果在足够长的时间内得不到处理器时间，同一算法将允许处理器去处理此进程，因为它最近没有使用过处理器。这样，一个处理器限制的进程不会永远得不到处理器。

2.3请对优化分时系统的调度策略和用于优化多道程序批处理系统的调度策略进行比较。

分时系统关注的是轮转时间，时间限制策略更有效是因为它给所有进程一个较短的处理时间。批处理系统关心的是吞吐量，更少的上下文转换和更多的进程处理时间。因此，最小的上下文转换最高效。 2.4系统调用的目的是什么?如何实现与操作系统相关的的系统调用以及与双重模式（内核模式和用户模式）操作相关的系统调用？

系统调用被应用程序用来调用一个由操作系统提供的函数。通常情况下，系统调用最终转换成在内核模式下的系统程序。

2.5在IBM的主机操作系统OS/390中，内核中的一个重要模块是系统资源管理程序（System Resource Manager,SRM），他负责地址空间（进程）之间的资源分配。SRM是的OS/390在操作系统中具有特殊性，

20

没有任何其他的主机操作系统，当然没有任何其他类型的操作系统可以比得上SRM所实现的功能。资源的概念包括处理器、实存和I/O通道，SRM累计处理器、I/O通道和各种重要数据结构的利用率，它的目标是基于性能监视和分析提供最优的性能，其安装设置了以后的各种性能目标作为SRM的指南，这会基于系统的利用率动态的修改安装和作业性能特点。SRM依次提供报告，允许受过训练的操作员改进配置和参数设置，以改善用户服务。

现在关注SRM活动的一个实例。实存被划分为成千上万个大小相等的块，称为帧。每个帧可以保留一块称为页的虚存。SRM每秒大约接受20次控制，并在互相之间以及每个页面之间进行检查。如果页未被引用或被改变，计数器增1。一段时间后，SRM求这些数据的平均值，以确定系统中一个页面未曾被触及的平均秒数。这样做的目的是什么？SRM将采取什么动作？

操作系统可以查看这些数据已确定系统的负荷，通过减少加在系统上的活跃作业来保持较高的平均利用率。典型的平均时间应该是两分钟以上，这个平均时间看起来很长，其实并不长。

第3章 进程描述和控制

3.1. 给出操作系统进行进程管理时的五种主要活动，并简单描述为什么需要它们。

答：用户进程和系统进程创建及删除。系统中的进程可以为信息共享、运算加速、模块化和方便并发地执行。而并发执行需要进程的创建和删除机制。当进程创建或者运行时分配给它需要的资源。当进程终止时，操作系统需要收回任何可以重新利用的资源。

进程的暂停和继续执行。在进程调度中，当进程在等待某些资源时，操作系统需要将它的状态改变为等待或就绪状态。当所需要的资源可用时，操作系统需要将它的状态变为运行态以使其继续执行。 提供进程的同步机制。合作的进程可能需要共享数据。对共享数据的并行访问可能会导致数据冲突。操作系统必须提供进程的同步机制以使合作进程有序地执行，从而保证数据的一致性。

提供进程的通信机制。操作系统下执行的进程既可以是独立进程也可以是合作进程。合作进程之间必须具有一定的方式进行通信。

提供进程的死锁解决机制。在多道程序环境中，多个进程可能会竞争有限的资源。如果发生死锁，所有的等待进程都将永远不能由等待状态再变为运行态，资源将被浪费，工作永远不能完成。 3.2. 在[PINK89] 中为进程定义了以下状态：执行（运行）态、活跃（就绪）态、阻塞态和挂起态。当进

程正在等待允许使用某一资源时，它处于阻塞态；当进程正在等待它已经获得的某种资源上的操作完成时，它处于挂起态。在许多操作系统中，这两种状态常常放在一起作为阻塞态，挂起态使用本章中给出的定义。请比较这两组定义的优点。

答：[PINK89]中引用了以下例子来阐述其中阻塞和挂起的定义：

假设一个进程已经执行了一段时间，它需要一个额外的磁带设备来写出一个临时文件。在它开始写磁带之前，进程必须得到使用某一设备的许可。当它做出请求时，磁带设备可能并不可用，这种情况下，该进程就处于阻塞态。假设操作系统在某一时刻将磁带设备分配给了该进程，这时进程就重新变为活跃态。当进程重新变为执行态时要对新获得的磁带设备进行写操作。这时进程变为挂起态，等待该磁带上当前所进行的写操作完成。

这种对等待某一设备的两种不同原因的区别，在操作系统组织其工作时是非常有用的。然而这并不能表明那些进程是换入的，那些进程是换出的。后一种区别是必需的，而且应该在进程状态中以某种形式表现出来。

3.3. 对于图3.9（b）中给出的7状态进程模型，请仿照图3.8（b）画出它的排队图。

答：图9.3给出了单个阻塞队列的结果。该图可以很容易的推广到多个阻塞队列的情形。

3.4. 考虑图3.9（b）中的状态转换图。假设操作系统正在分派进程，有进程处于就绪态和就绪/挂起态，并

且至少有一个处于就绪/挂起态的进程比处于就绪态的所有进程的优先级都高。有两种极端的策略：（1）总是分派一个处于就绪态的进程，以减少交换；（2）总是把机会给具有最高优先级的进程，即使会导致在不需要交换时进行交换。请给出一种能均衡考虑优先级和性能的中间策略。

答：对于一个就绪/挂起态的进程，降低一定数量（如一或两个）优先级，从而保证只有当一个就绪/挂起态的进程比就绪态的进程的最高优先级还高出几个优先级时，它才会被选做下一个执行。

21

3.5. 表3.13给出了VAX/VMS操作系统的进程状态。

a. 请给出这么多种等待状态的理由。

b. 为什么以下状态没有驻留和换出方案：页错误等待、也冲突等待、公共事件等待、自由页等待和

资源等待。

c. 请画出状态转换图，并指出引发状态装换的原因。 答：

a. 每一种等待状态都有一个单独的队列与其相关联。当影响某一等待进程的事件发生时，把等待进

程分成不同的队列就减少了定位这一等待进程所需的工作量。例如，当一个页错误完成时，调度程序就可以在页错误等待队列中找到等待的进程。

b. 在这些状态下，允许进程被换出只会使效率更低。例如，当发生页错误等待时，进程正在等待换

入一个页从而使其可以执行，这是将进程换出是毫无意义的。 c. 可以由下面的进程状态转换表得到状态转换图。

当前状态 下一状态

当前正在执行 可计算（驻留） 可计算（换出） 各种等待状态（驻留） 各种等待状态（换出） 当前正在执行 调度 可计算（驻留） 重调度 换入 事件发生 可计算（换出） 换出 事件发生 各种等待状态（驻留） 等待 各种等待状态（换出） 换出 3.6. VAM/VMS操作系统采用了四种处理器访问模式，以促进系统资源在进程间的保护和共享。访问模式确定：

? 指令执行特权：处理器将执行什么指令。

? 内存访问特权：当前指令可能访问虚拟内存中的哪个单元。 四种模式如下：

? 内核模式：执行VMS操作系统的内核，包括内存管理、中断处理和I/O操作。

? 执行模式：执行许多操作系统服务调用，包括文件（磁盘和磁带）和记录管理例程。 ? 管理模式：执行其他操作系统服务，如响应用户命令。

? 用户模式：执行用户程序和诸如编译器、编辑器、链接程序、调试器之类的实用程序。

在较少特权模式执行的进程通常需要调用在较多特权模式下执行的过程，例如，一个用户程序需要一个操作系统服务。这个调用通过使用一个改变模式（简称CHM）指令来实现，该指令将引发一个中断，把控制转交给处于新的访问模式下的例程，并通过执行REI（Return from Exception or Interrupt，从异常或中断返回）指令返回。

a. 很多操作系统有两种模式，内核和用户，那么提供四种模式有什么优点和缺点？ b. 你可以举出一种有四种以上模式的情况吗？ 答：

a. 四种模式的优点是对主存的访问控制更加灵活，能够为主存提供更好的保护。缺点是复杂和处理

的开销过大。例如，程序在每一种执行模式下都要有一个独立的堆栈。 b. 原则上，模式越多越灵活，但是四种以上的模式似乎很难实现。

3.7. 在前面习题中讨论的VMS方案常常称为环状保护结构，如图3.18所示。3.3节所描述的简单的内核/

22

用户方案是一种两环结构，[SILB04]指出了这种方法的问题：环状（层次）结构的主要缺点是它不允许我们实施须知原理，特别地，如果一个对象必须在域Dj中可访问，但在域Di中不可访问，则必须有就j

b. 请给出环状结构操作系统解决这个问题的一种方法。 答：

a. 当j

具有特权或者要求的安全性更高，那么这种限制就是合理的。然而，通过以下方法却可以绕过这种安全策略。一个运行在Dj中的进程可以读取Dj中的数据，然后把数据复制到Di中。随后，Di中的进程就可以访问这些信息了。

b. 有一种解决这一问题的方法叫做可信系统，我们将在16章中进行讨论。 3.8. 图3.7（b）表明一个进程每次只能在一个事件队列中。

a. 是否能够允许进程同时等待一个或多个事件？请举例说明。 b. 在这种情况下，如何修改图中的排队结构以支持这个新特点？ 答：

a. 一个进程可能正在处理从另一个进程收到的数据并将结果保存到磁盘上。如果当前在另一个进程

中正有数据在等待被取走，进程就可以继续获得数据并处理它。如果前一个写磁盘操作已经完成，并且有处理好的数据在等待写出，那么进程就可以继续写磁盘。这样就可能存在某一时刻，进程即在等待从输入进程获得数据，又在等待磁盘可用。

b. 有很多种方法解决这一问题。可以使用一种特殊的队列，或者将进程放入两个独立的队列中。不

论采用哪种方法，操作系统都必须处理好细节工作，使进程相继地关注两个事件的发生。

3.9. 在很多早期计算机中，中断导致寄存器值被保存在与给定的中断信息相关联的固定单元。在什么情况

下这是一种实用的技术？请解释为什么它通常是不方便的。

答：这种技术是基于被中断的进程A在中断响应之后继续执行的假设的。但是，在通常情况下，中断可能会导致另一个进程B抢占了进程A。这是就必须将进程A的执行状态从与中断相关的位置复制到与A相关的进程描述中。然而机器却有可能仍将它们保存到前一位置。参考：[BRIN73]。 3.10. 3.4节曾经讲述过，由于在内核模式下执行的进程是不能被抢占的，因此UNIX不适用于实时应用。

请阐述原因。

答：由于存在进程不能被抢占的情况（如在内核模式下执行的进程），操作系统不可能对实时需求给予迅速的反应。

第4章 线程、对称多处理和微内核

4.1. 一个进程中的多个线程有以下两个优点：（1）在一个已有进程中创建一个新线程比创建一个新进程所

需的工作量少；（2）在同一个进程中的线程间的通信比较简单。请问同一个进程中的两个线程间的模式切换与不同进程中的两个线程间的模式切换相比，所需的工作量是否要少？ 答：是的，因为两个进程间的模式切换要储存更多的状态信息。

4.2. 在比较用户级线程和内核级线程时曾指出用户级线程的一个缺点，即当一个用户级线程执行系统调用

时，不仅这个线程被阻塞，而且进程中的所有线程都被阻塞。请问这是为什么？

答：因为对于用户级线程来说，一个进程的线程结构对操作系统是不可见的，而操作系统的调度是以进程为单位的。

4.3. 在OS/2中，其他操作系统中通用的进程概念被分成了三个独立类型的实体：会话、进程和线程。一

个会话是一组与用户接口（键盘、显示器、鼠标）相关联的一个或多个进程。会话代表了一个交互式的用户应用程序，如字处理程序或电子表格，这个概念使得PC用户可以打开一个以上的应用程序，在屏幕上显示一个或更多个窗口。操作系统必须知道哪个窗口，即哪个会话是活跃的，从而把键盘和鼠标的输入传递个相应的会话。在任何时刻，只有一个会话在前台模式，其他的会话都在后

23

台模式，键盘和鼠标的所有输入都发送给前台会话的一个进程。当一个会话在前台模式时，执行视频输出的进程直接把它发送到硬件视频缓冲区。当一个会话在后台时，如果该会话的任何一个进程的任何一个线程正在执行并产生屏幕输出，则这个输出被送到逻辑视频缓冲区；当这个会话返回前台时，屏幕被更新，为新的前台会话反映出逻辑视频缓冲区中的当前内容。

有一种方法可以把OS/2中与进程相关的概念的数目从3个减少到2个。删去会话，把用户接口（键盘、显示器、鼠标）和进程关联起来。这样，在某一时刻，只有一个进程处于前台模式。为了进一步地进行构造，进程可以被划分成线程。 a. 使用这种方法会丧失什么优点？

b. 如果继续使用这种修改方法，应该在哪里分配资源（存储器、文件等）：在进程级还是线程级？ 答：

a. 会话的使用非常适合个人计算机和工作站对交互式图形接口的需求。它为明确图形输出和键盘/

鼠标输入应该被关联到什么位置提供了一个统一的机制，减轻了操作系统的工作负担。 b. 应该和其他的进程/线程系统一样，在进程级分配地址空间和文件。

4.4. 考虑这样一个环境，用户级线程和内核级线程呈一对一的映射关系，并且允许进程中的一个或多个线

程产生会引发阻塞的系统调用，而其他线程可以继续运行。解释为什么这个模型可以使多线程程序比在单处理器机器上的相应的单线程程序运行速度更快？

答：问题在于机器会花费相当多的时间等待I/O操作的完成。在一个多线程程序中，可能一个内核级线程会产生引发阻塞的系统调用，而其他内核级线程可以继续执行。而在单处理器机器上，进程则必须阻塞知道所有的系统调用都可以继续运行。参考：[LEWI96]

4.5. 如果一个进程退出时，该进程的某些线程仍在运行，请问他们会继续运行吗？

答：不会。当一个进程退出时，会带走它的所有东西——内核级线程，进程结构，存储空间——包括线程。参考：[LEWI96]

4.6. OS/390主机操作系统围绕着地址空间和任务的概念构造。粗略说来，一个地址空间对应于一个应用程

序，并且或多或少地对应于其他操作系统中的一个进程；在一个地址空间中，可以产生一组任务，并且它们可以并发执行，这大致对应于多线程的概念。管理任务结构有两个主要的数据结构。地址空间控制块（ASCB）含有OS/390所需要的关于一个地址空间的信息，而不论该地址空间是否在执行。ASCB中的信息包括分派优先级、分配给该地址空间的实存和虚存、该地址空间中就绪的任务数以及是否每个都被换出。一个任务控制块（TCB）标识一个正在执行的用户程序，它含有在一个地址空间中管理该任务所需要的信息，包括处理器状态信息、指向该任务所涉及到的程序的指针和任务执行结构。ASCB是在系统存储器中保存的全局结构，而TCB是保存在各自的地址空间中的局部结构。请问把控制信息划分成全局和局部两部分有什么好处？

答：关于一个地址空间的尽可能多的信息可以随地址空间被换出，从而节约了主存。

4.7. 一个多处理系统有8个处理器和20个附加磁带设备。现在有大量的作业提交给该系统，完成每个作

业最多需要4个磁带设备。假设每个作业开始运行时只需要3个磁带设备，并且在很长时间内都只需要这3个设备，而只是在最后很短的一段时间内需要第4个设备以完成操作。同时还假设这类作业源源不断。

a. 假设操作系统中的调度器只有当4个磁带设备都可用时才开始一个作业。当作业开始时，4个设

备立即被分配给它，并且直到作业完成时才被释放。请问一次最多可以同时执行几个作业？采用这种策略，最多有几个磁带设备可能是空闲的？最少有几个？

b. 给出另外一种策略，要求其可以提高磁带设备的利用率，并且同时可以避免系统死锁。分析最多

可以有几个作业同时执行，可能出现的空闲设备的范围是多少。 答：

a. 采用一个保守的策略，一次最多同时执行20/4=5个作业。由于分配各一个任务的磁带设备最多同

时只有一个空闲，所以在同一时刻最多有5个磁带设备可能是空闲的。在最好的情况下没有磁带设备空闲。

b. 为了更好的利用磁设备，每个作业在最初只分配三个磁带设备。第四个只有的需要的时候才分配。

24

在这种策略中，最多可以有20/3=6个作业同时执行。最少的空闲设备数量为0，最多有2个。参考：Advanced Computer Architectrue,K.Hwang,1993.

4.8. 在描述Solaris用户级线程状态时，曾表明一个用户级线程可能让位于具有相同优先级的另一个线程。

请问，如果有一个可运行的、具有更高优先级的线程，让位函数是否还会导致让位于具有相同优先级或更高优先级的线程？

答：任何一个可能改变线程优先级或者使更高优先级的线程可运行的调用都会引起调度，它会依次抢占低优先级的活跃线程。所以，永远都不会存在一个可运行的、具有更高优先级的线程。参考：[LEVI96]

第5章 并发性：互斥和同步

5.1

答：b.协同程序read读卡片，将字符赋给一个只有一个字大小的缓冲区rs然后在赋给squash协同程。协同程序Read在每副卡片图像的后面插入一个额外的空白。协同程序squash不需要知道任何关于输入的八十个字符的结构，它简单的查找成对出现的星号，然后将更改够的字符串经由只有一个字符大小的缓冲sp，传递给协同程序print。最后协同程序print简单的接受到来的字符串，并将他们打印在包含125个字符的行中。

5.2．考虑一个并发程序，它有两个进程p和q，定义如下。A.B.C.D和E是任意的原子语句。假设住程序执行两个进程的parbegin

Void p() void q() { A; { D; B; E; C; } }

答：ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DABCE; 5.3考虑下面的程序

const int n=50; int tally;

void total() { int count;

for(count =1;count <=n;count ++) {tally++; } }

void main() {

tally =0;

parbegin(total(),total(); write(tally);

}

答：a.随意一看,tally值的范围好像是落在[50,100]这个区间里,因为当没有互斥时可以从0直接增加到50.这一基本论点是当并发的运行这两进程时,我们不可能得到一个比连续执行单一某进程所得tally值还低的一个最终tally值.但是考虑下面由这两进程按交替顺序执行载入,增加,存储的情况,同时变更这个共享变量的取值:

1.进程A载入tally值,tally值加到1,在此时失去处理器(它已经增加寄存器的值到1,但是还没有存储这个值).

25

2.进程B载入tally值(仍然是0),然后运行完成49次增加操作,在它已经将49这个值存储给共享变量tally后,失去处理器控制权.

3.进程A重新获得处理器控制权去完成它的第一次存储操作(用1去代替先前的49这个tally值),此时被迫立即放弃处理器.

4.进程B重新开始,将1(当前的tally值)载入到它自己的寄存器中,但此时被迫放弃处理器(注意这是B的最后一次载入).

5.进程A被重新安排开始,但这次没有被中断,直到运行完成它剩余的49次载入,增加和存储操作,结果是此时tally值已经是50.

6.进程B在它终止前完成仅有的最后一次增加和存储操作.它的寄存器值增至2,同时存储这个值做为这个共享变量的最终结果.

一些认为会出现低于2这个值的结果,这种情况不会出现.这样tally值的正确范围是[2,100].

b.对一般有N个进程的情况下,tally值的最终范围是[2,N*50],因为对其他所有进程来说,从最初开始运行到在第五步完成.但最后都被进程B破坏掉它们的最终结果.

5.4.忙等待是否总是比阻塞等待效率低（根据处理器的使用时间）？请解释。

答：就一般情况来说是对的,因为忙等待消耗无用的指令周期.然而,有一种特殊情况,当进程执行到程序的某一点处,在此处要等待直到条件满足,而正好条件已满足,此时忙等待会立即有结果,然而阻塞等待会消耗操作系统资源在换出与换入进程上. 5.5考虑下面的程序

boolean blocked[2]; int rurn;

void P(int id) {

While (true) {

While(turn!=id); {

While(blocked[1-!id] /*do nothing*/; Turn =id; } }

Void main () {

Blocked[0]=false; Blocked[1]=false; Turn=0;

Parbegin(P(0),P(1)); }

这是【HYMA66】中提出的解决互斥问题的一种方法。请举出证明该方法不正确的一个反例。

答：考虑这种情况:此时turn=0,进程P(1)使布尔变量blocked[1]的值为true,在这时发现布尔变量blocked[0]的值为false,然后P(0)会将true值赋予blocked[0]

,此时turn=0,P(0)进入临界区,P(1)在将1赋值给turn后,也进入了临界区.

5.6解决互斥的另一种软件方法是lamport的面包店（bakery）算法，之所以起这个名字，是因为它的思想来自于面包店或其他商店中，每个顾客在到达时都得到一个有编号的票，并按票号依次得到服务，算法如下：

Boolean choosing[n];

26

Int number[n]; While (true) {

Choosing[i]=true;

Number[i]=1+getmax(number[],n)； Choosing[i]=false; For(int j=0;j

While (choosing[j]) {}

While ((number[j]!=0)&&(number[j],j)<(number[i],i) {} }

/*critical section*/ Number[i]=0; /*remainder*/; }

数组choosing和number分别被初始化成false和0，每个数组的第i个元素可以由进程i读或写，但其他进程只能读。符号（a，b）<（c，d）被定义成 （a，c）或（a=c且b

B． 说明这个算法避免了死锁。 C． 说明它实施了互斥。

答：a.当一个进程希望进入临界区时,它被分配一个票号.分配的票号是通过在目前那些等待进入临界区的进程所持票号和已经在临界区的进程所持票号比较,所得最大票号再加1得到的.有最小票号的进程有最高的优先级进入临界区.当有多个进程拥有同样的票号时,拥有最小数字号进入临界区.当一个进程退出临界区时,重新设置它的票号为0.

b.如果每个进程被分配唯一的一个进程号,那么总会有一个唯一的,严格的进程顺序.因此,死锁可以避免.

c.为了说明互斥,我们首先需要证明下面的定理:如果Pi在它的临界区,Pk已经计算出来它的number[k],并试图进入临界区,此时就有下面的关系式: ( number[i], i ) < ( number[k], k ).为证明定理,定义下面一些时间量:

Tw1:Pi最后一次读choosing[k], 当 j=k,在它的第一次等待时,因此我们在Tw1处有choosing[k] = false.

Tw2:Pi开始它的最后执行, 当j=k,在它的第二次while循环时,因此我们有Tw1 < Tw2. Tk1:Pk在开始repeat循环时;Tk2:Pk完成number[k]的计算; Tk3: Pk设置choosing[k]为false时.我们有Tk1

因为在Tw1处,choosing[k]=false,我们要么有Tw1

5.7当按图5.2的形式使用一个专门机器指令提供互斥时，对进程在允许访问临界区之前必须等待多久没有控制。设计一个使用testset指令的算法，且保证任何一个等待进入临界区的进程在n-1个turn内进入，n是要求访问临界区的进程数，turn是指一个进程离开临界区而另一个进程获准访问这个一个事件。

27

答：以下的程序由[SILB98]提供： var j: 0..n-1; key: boolean; repeat

waiting[i] := true; key := true;

while waiting[i] and key do key := testset(lock); waiting[i] := false; < critical section > j := i + 1 mod n;

while (j ≠ i) and (not waiting[j]) do j := j + 1 mod n; if j = i then lock := false else waiting := false; < remainder section > Until

这个算法用最普通的数据结构：var waiting: array [0..n – 1] of boolean Lock：boolean

这些数据结构被初始化成假的，当一个进程离开它的临界区，它就搜索waiting的循环队列 5.8考虑下面关于信号量的定义：

Void semWait(s) {

If (s.count>0) {

s.count--; } Else {

Place this process in s.queue; Block; } }

Void semSignal(s) {

If (there is at liast one process blocked on semaphore) {

Remove a process P from s.queue; Place process P on ready list; }

Else

s.count++; }

比较这个定义和图5.3中的定义，注意有这样的一个区别：在前面的定义中，信号量永远不会取负值。当在程序中分别使用这两种定义时，其效果有什么不同？也就是说，是否可以在不改变程序意义的前提下，用一个定义代替另一个？

答：这两个定义是等价的，在图5.3的定义中，当信号量的值为负值时，它的值代表了有多少个进程在等待；在此题中的定义中，虽然你没有关于这方面的信息，但是这两个版本的函数是一样的。

28

5.9可以用二元信号量实现一般信号量。我们使用semWaitB操作和semSignalB操作以及两个二元信号量delay和mutex。考虑下面的代码

Void semWait(semaphor s) {

semWaitB(mutex); s--; if (s<0) {

semSignalB(mutex); semWaitB(delay); } Else

Semsignalb(mutex) }

Void semSignal(semaphore s); {

semWaitB(mutex); s++; if(s<=0)

semSignalB(delay); semSignalB(mutex); }

最初。S被设置成期待的信号量值，每个semwait操作将信号量减1，每个semsignal操作将信号量加1.二元信号量mutex被初始化成1，确保在更新在更新s时保证互斥，二元信号量delay被初始化成0，用于挂起进程，

上面的程序有一个缺点，证明这个缺点，并提出解决方案。提示：假设两个进程，每个都在s初始化为0时调用semwait（s）,当第一个刚刚执行了semsignalb（mutex）但还没有执行semwaitb（delay），第二个调用semwait（s）并到达同一点。现在需要做的就是移动程序的一行.

答：假设两个进程，每个都在s被初始化成0时调用semWait（s），当第一个刚执行了semSignalB（mutex）但还没有执行semWaitB（delay）时，第二个调用semWait（s）并到达同一点。因为s=-2 mutex没有锁定，假如有另外两个进程同时成功的调用semSignal（s），他们接着就会调用semsignalb（delay），但是第二个semsignalb没有被定义。

解决方法就是移动semWait程序中end前的else一行到semSignal程序中最后一行之前。因此semWait中的最后一个semSignalB(mutex)变成无条件的，semSignal中的semSignalb(mutex)变成了有条件的。

5.10 1978年，dijkstra提出了一个推测，即使用有限数目的弱信号量，没有一种解决互斥的方案，使用于数目未知但有限的进程且可以避免饥饿。1979年，j.m.morris提出 了一个使用三个弱信号量的算法，反驳了这个推测。算法的行为可描述如下，如果一个或多个进程正在semwait（s）操作上等待，另一个进程正在执行semsignal（s），则信号量s的值未被修改，一个等待进程被解除阻塞，并且这并不取决于semwait（s）。除了这三个信号量外，算法使用两个非负整数变量，作为在算法特定区域的进程的计数器。因此，信号量A和B被初始化为1，而信号量M和计数器NA，NM被初始化成0.一个试图进入临界区的进程必须通过两个分别由信号量A和M表示路障，计数器NA和NM分别含有准备通过路障A以及通过路障A但还没有通过路障M的进程数。在协议的第二部分，在M上阻塞的NM个进程将使用类似于第一部分的串联技术，依次进入他们的临界区，定义一个算法实现上面的描述。 答：这个程序由[RAYN86]提供： var a, b, m: semaphore;

29

na, nm: 0 ? +∞;

a := 1; b := 1; m := 0; na := 0; nm := 0; semWait(b); na ← na + 1; semSignal(b); semWait(a); nm ← nm + 1; semwait(b); na ← na – 1;

if na = 0 then semSignal(b); semSignal(m) else semSignal(b); semSignal(a) endif;

semWait(m); nm ← nm – 1; ;

if nm = 0 then semSignal(a) else semSignal(m) endif;

5.11下面的问题曾被用于一个测试中：

侏罗纪公园有一个恐龙博物馆和一个公园，有m个旅客和n辆车，每辆车只能容纳一名旅客。旅客在博物馆逛了一会儿，然后派对乘坐旅客车。当一辆车可用时，它载入一名旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客进程和n个进程。下面的代码框架是在教室的地板上发现的。忽略语法错误和丢掉的变量声明，请判定它是否正确。注意，p和v分别对应于semwait和semsignal。 Resource Jurassic_Park()

Sem car_avail:=0,car_taken:=0,car_fillde:=0.passenger_released:=0 Process passenger(i:=1 to num_passengers)

Do true->nap(int(random(1000*wander_time))) P(car avail);V(car_taken);P(car_filled) P(passenger_released) Od

End passenger

Process car(j:=1 to num_cars)

Do true->V(car_avail);P(car_taken);V(car_filled) Nap(int(random(1000*ride_time))) V(passenger_released) Od End car

End Jurassic_Park 答：这段代码有一个重要问题.在process car中的代码 V(passenger_released)能够解除下面一种旅客的阻塞,被阻塞在P(passenger_released)的这种旅客不是坐在执行V()的车里的旅客.

5.12在图5.9和5.3的注释中，有一句话是“仅把消费者临界区（由s控制）中的控制语句移出还是不能解决问题，因为这将导致死锁”，请用类似于表5.3的表说明。

答： 1 2 3 4 5 Producer SemWaitB(S) n++ If(n==1) (semSignalB(delay)) semSignalB(s) Consumer s 1 0 0 0 1 n 0 0 1 1 1 delay 0 0 0 1 1 30

6 7 8 9 10 semWaitB(s) semWaitB(delay) semWaitB(s) n-- If(n==0) (semWaitB(delay)) 1 0 1 1 0 0 0 0 生产者和消费者都被阻塞。 5.13考虑图5.10中定义的无限缓冲区生产者/消费者问题的解决方案。假设生产者和消费者都以大致相同的速度运行，运行情况如下：

生产者：append;semSignal;produce;···append;semSignal 消费者：consume;take;semWait;consume;take;semWait;

生产者通常管理给换成区一个元素，并在消费者消费了前面的元素后发信号。生产者通常添加到一个空缓冲去中，而消费者通常取走缓冲区中的唯一元素。尽管消费者从不在信号量上阻塞，但必须进行大量的信号量调用，从而产生相当多的开销。

构造一个新程序使得能在这种情况下更加有效。

提示：允许n的值为-1，这表示不仅缓冲区为空，而且消费者也检测到这个事实并将被阻塞，直到生产者产生新数据。这个方案不需要使用图5.10中的局部变量m。

答：

这个程序来自于[BEN82] program producerconsumer; var n: integer;

s: (*binary*) semaphore (:= 1); delay: (*binary*) semaphore (:= 0); procedure producer; begin repeat produce;

semWaitB(s); append; n := n + 1;

if n=0 then semSignalB(delay); semSignalB(s) forever end;

procedure consumer; begin repeat

semWaitB(s); take;

n := n – 1; if n = -1 then begin

semSignalB(s); semWaitB(delay); semWaitB(s) end;

31

consume;

semSignalB(s) forever end;

begin (*main program*) n := 0; parbegin

producer; consumer parend end.

5.14考虑图5.13.如果发生下面的交换，程序的意义是否会发生改变？

a.semWait(e);semWait(s) b.semSignal(s);semSignal(n) c.semWait(n);semWait(s) d.semSignal(s);semSignal(e)

答：只要交换顺序都会导致程序错误。信号量s控制进入临界区，你只想让临界区区域包括附加或采取功能。

5.15在讨论有限缓冲区（见图5.12）生产者/消费者问题时，注意我们的定义允许缓冲区中最多有n-1个入口？

a.这是为什么？

b.请修改程序，以不久这种低调？

答：如果缓冲区可以容纳n个入口，问题在于如何从一个满的缓冲区中区分出一个空的缓冲区，考虑一个有六个位置的缓冲区，且仅有一个入口，如下： A Out in 然后，当一个元素被移出，out=in。现在假设缓冲区仅有一个位置为空： D E A B C In out 这样，out=in+1.但是，当一个元素被添加，in被加1后，out=in，当缓冲区为空时同理。 b．你可以使用一个可以随意增加和减少的辅助的变量，count。

5.16这个习题说明了使用信号量协调三类进程。圣诞老人在他北极的商店中睡眠，他只能被一下两种情况之一唤醒：（1）所有九头驯鹿都从南太平洋的假期回来了，或者（2）某些小孩在制作玩具时遇到了困难。为了让圣诞老人多睡会，这些孩子只有在是那个人都遇到困难时才唤醒他。当三个孩子的问题得到解决时，其他想访问圣诞老人的孩子必须等到那些孩子返回。如果圣诞老人醒来后发现在三个孩子在他的店门口等待，并且最后一头驯鹿已经从热带回来。则圣诞老人决定让孩子门等到圣诞节之后，因为准备最后一天哦iuxunlu必须与其他unlu在暖棚中等待并且还没有套上缰绳做成雪橇前回来。请用信号量解决这个问题。 答：santa:圣诞老人reindeer:驯鹿elf:小孩子sleigh:雪橇toys:玩具

32

5.17通过一下步骤说明消息传递和信号量具有同等的功能：

a.用信号量实现消息传递。提示：利用一个共享缓冲区保存信箱，每个信箱由一个消息槽数组成的。 b.用消息传递实现信号量。提示：引入一个独立的同步进程。

答：b.这个方法来自于[TANE97].同步进程维护了一个计数器和一个等待进程的清单。进程调用相关用于向同步进程发送消息的生产者，wait或signal，来实现WAITHUO SIGNAL.然后生产者执行RECEIVE来接受来自于同步进程的回复。

当消息到达时，同步进程检查计数器看需要的操作是否已经足够，SIGNALs总是可以完成，但是假如信号值为0时，WAITs将会被阻塞。假如操作被允许，同步进程就发回一个空消息，因此解除调用者的阻塞。假如操作是WAIT并且信号量的值为0时，同步进程进入调用队列，并且不发送回复。结果是执行WAIT的进程被阻塞。当SIGNAL被执行，同步进程选择一个进程在信号量上阻塞，要不就以先进先出顺序，要不以其他顺序，并且发送一个回复。跑步条件被允许因为同步进程一次只需要一个。

33

第6章 并发性：死锁和饥饿

６.１写出图６.１（a）中死锁的四个条件。

解：互斥：同一时刻只有一辆车可以占有一个十字路口象限。占有且等待：没有车可以倒退；在十字路口的每辆车都要等待直到它前面的象限是空的。非抢占: 没有汽车被允许挤开其他车辆。 循环等待: 每辆汽车都在等待一个此时已经被其他车占领的十字路口象限。

６.２按照６.１节中对图６.２中路径的描述，给出对图６.３中６种路径的简单描述。

解：１.Q 获得 B 和Ａ, 然后释放 B 和 A. 当 P 重新开始执行的时候, 它将会能够获得两个资源。 2. Q 获得 B和Ａ， P 执行而且阻塞在对 A的请求上. Q释放 B 和Ａ。当 P 重新开始执行的时候，它将会能够获得两个资源。

3. Q 获得 B ，然后 P 获得和释放 A. Q 获得Ａ然后释放 B 和 A. 当 P 重新开始行的时候，它将会能够获得 B。 4. P 获得Ａ然后 Q 获得 B. P 释放 A. Q 获得Ａ然后释放 B. P 获得 B 然后释放 B。

5. P 获得，然后释放 A. P 获得 B. Q 执行而且阻塞在对Ｂ的请求上。Ｐ释放Ｂ。当 Q 重新开始执行的时候，, 它将会能够获得两个资源。

6. P 获得Ａ而且释放Ａ然后获得并且释放 B. 当 Q 重新开始实行, 它将会能够获得两个资源。

６.３图６.３反映的情况不会发生死锁，请证明。

证明：如果 Q 获得 B 和Ａ（在 P之前请求Ａ）, 那么 Q 能使用这些两类资源然后释放他们, 允许Ａ进行。 如果 P在 Q之前请求Ａ获得Ａ, 然后Q 最多能执行到请求Ａ然后被阻塞。 然而,一旦 P 释放 A ， Q 能进行。 一旦 Q 释放 B, Ａ能进行。

r1 r2 r3 r4 r1 r2 r3 r4 r1 r2 r3 r4 ６.４考虑

0 0 1 2 0 0 1 2 下面的一

2 0 0 0 2 7 5 0 个系统，当

0 0 3 4 6 6 5 6 前不存在

2 3 5 4 4 3 5 6 未满足的

0 3 3 2 0 6 5 2 请求。 2 1 0 0

可用

r1 r2 r3 r4

当前分配 最大需求 仍然需求

a计算每个进程仍然可能需要的资源，并填入标为“仍然需要”的列中。 b系统当前是处于安全状态还是不安全状态，为什么。 c系统当前是否死锁？为什么？

d哪个进程（如果存在）是死锁的或可能变成死锁的？

e如果Ｐ３的请求（0，1，0，0）到达，是否可以立即安全地同意该请求？在什么状态（死锁，安全，不安全）下可以立即同意系统剩下的全部请求？如果立即同意全部请求，哪个进程（如果有）是死锁的或可

34

能变成死锁的？ 解： a. 0 0 0 0

0 7 5 0 6 6 2 2 2 0 0 2 0 3 2 0

b.系统当前处于安全状态，因为至少有一个进程执行序列，不会导致死锁，运行顺序是p1, p4, p5, p2,

p3.

c.系统当前并没有死锁，因为P1进程当前分配与最大需求正好相等，P1进程可以运行直至结束，接

下来运行其他进程

d.P2,P3,P4,P5可能死锁

e.不可以，当进程P1,P4,P5执行完可用资源为（4，6，9，8），P2,P3将死锁，所以不安全，完全不

可以立即同意系统剩下的全部请求。

６.５ 请把６.４中的死锁检测算法应用于下面的数据，并给出结果。

Available=(2 1 0 0)

2 0 0 1 0 0 1 0 Request= 1 0 1 0 Allocation= 2 0 0 1 2 1 0 0 0 1 2 0

解： 1. W = (2 1 0 0)

2. Mark P3; W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0) 3. Mark P2; W = (2 2 2 0) + (2 0 0 1) = (4 2 2 1) 4. Mark P1; no deadlock detected 没有死锁

６.６一个假脱机系统包含一个输入进程Ｉ，用户进程进程Ｐ和一个输出进程Ｏ，它们之间用两个缓冲区连接。进程以相等大小的块为单位交换数据，这些块利用输入缓冲区和输出缓冲区之间的移动边界缓存在磁盘上，并取决于进程的速度。所使用的通信原语确保满足下面的资源约束：i+o≤max 其中，max表示磁盘中的最大块数，i表示磁盘中的输入块数目， o表示磁盘中的输出块数目。 输入 输出 P 缓冲区 缓冲区

以下是关于进程的知识： １. 只要环境提供数据，进程Ｉ最终把它输入到磁盘上（只要磁盘空间可用）。 ２. 只要磁盘可以得到输入，进程Ｐ最终消耗掉它，并在磁盘上为每个输入块输出有限量的数据（只要磁

盘空间可用）。 ３. 只要磁盘可以得到输出，进程Ｏ最终消耗掉它。说明这个系统可能死锁。

I o 35

解：当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处理输入数据，即要将处理数据放入输出数据区。于是P进程等待磁盘空间输出，I进程等待磁盘空间输入，二者死锁。

６.７给出在习题６.６中预防死锁的附加资源约束，仍然通话输入和输出缓冲区之间的边界可以根据进程的要求变化。

解：为输出缓冲区保留一个最小数目(称为reso)块, 但是当磁盘空间足够大时允许输出块的数目超过这一个界限。 资源限制现在变成 Ｉ + Ｏ ≤max Ｉ≤max – reso 当0 < reso < max 如果程序 P 正在等候递送输出给磁盘, 程序 O 最后处理所有的早先输出而且产生至少reso页, 然后让 P 继续执行。 因此 P 不会因为 O 而延迟。

如果磁盘充满I/O，Ｉ能被延迟; 但是迟早, 所有的早先的 输入可以被Ｐ处理完，而且对应的输出将会被 O 处理, 因而可以让Ｉ继续执行。

６.８在ＴＨＥ多道程序设计系统中，一个磁鼓（磁盘的先驱，用做辅存）被划分为输入缓冲区，处理和输出缓冲区，它们的边界可以移动，这取决于所涉及的进程速度。磁鼓的当前状态可以用以下参数描述： max表示磁鼓中的最大页数，i示磁鼓中的输入页数，p示磁鼓中的处理页数，o示磁鼓中的输出页数，reso出保留的最小页数，resp理保留的最小页数。 解：

Ｉ + Ｏ + Ｐ≤max – Ｉ + Ｏ≤max – resp Ｉ + Ｐ ≤max – reso Ｉ ≤max – (reso + resp)

６．９在ＴＨＥ多道程序设计系统中，一页可以进行下列状态转换： １.空→输入缓冲区（输入生产）

２.输入缓冲区→处理区域（输入消耗） ３.处理区域→输出缓冲区（输出生产） ４.输出缓冲区→空（输出生产） ５.空→处理区域（输出消耗） ６.处理区域→空（过程调用）

a根据Ｉ，Ｏ和Ｐ的量定义这些转换的结果。

b如果维持习题６.６中关于输入进程，用户进程和输出进程的假设，它们中的任何一个转换是否会导致死锁。

解： 1. i ←i + 1

2. i←i – 1; p ←p + 1 3. p←p – 1; o←o + 1 4. o ←o – 1 5. p←p + 1 6. p ←p – 1

b. 结合在对问题 6.7 的解决办法被列出的资源限制, 我们 能总结下列各项:

6. 过程返回能立刻发生因为他们只释放

36

资源。

5. 程序调用可能用尽磁盘片 (p= max – reso) 导致死锁。 4. 当有输出时输出消耗能立刻发生。

3. 输出生产能暂时被延迟直到所有的早先输出被消耗而且为下一步的输出至少可以产生reso页。 2. 只要有输入，输入消耗能立刻发生。

1. 输入生产被延迟直到所有先前输入和对应的输出已经被消耗。 此时, 当 i= o=0,如果消费进程还没有占用完磁盘空间 ( p < max – reso)，可以产生输入。 结论: 分配给消费进程的不受控制的存储空间是 唯一可能引发死锁的因素。

６.１０考虑一个共有１５０个存储器单元的系统，其单元如下分配三个进程：

进程 最大 占用 1 70 45 2 60 40 3 60 15 使用银行家算法，以确定同意下面的任何一个请求是否安全。如果安全，说明能保证的终止序列；如果不安全，给出结果分配简表。

a．第４个进程到达，最多需要６０个存储单元，最初需要２５个单元。 b第４个进程到达，最多需要６０个存储单元，最初需要３５个单元。

解： a.若同意第4个进程请求，则储存器单元共用去25＋15＋40＋45=125个单元，还有25个存储单元，则可以安全执行全部进程。安全顺序是1－2－3－4

b.若同意第4个进程请求，则还有15个资源可以用，此时处于不安全状态，结果分配见表 进程 最大 占有 需要 空闲 1 70 45 25 15 2 60 40 20 3 60 15 45 4 60 35 25

６.１１评价独家算法在实际应用中是否有用。

解：不切实际的: 不能总是预先知道最大要求, 进程数目和资源数目可能随着时间改变 。大多数的操作系统忽视死锁。

６.１２有一个已经实现了的管道算法，使得进程Ｐ０产生的Ｔ类型的数据元素经进程序列Ｐ1Ｐ2?Ｐn-1,并且按该顺序在元素上操作。

a.定义一个一般的消息缓冲区，包含所有部分消耗的数据元素，并按下面的格式为进程Ｐi(0≤i≤n-1)写一个算法。 Repeat 从前驱接收 消耗

给后续发送 Forever

假设Ｐ0收到Ｐn-1发送的空元素。该算法能够使进程直接在缓冲区中保存的消息上操作，而无需复制。 b.说明关于普通的缓冲区进程不会死锁。

解：ar buffer: array 0..max-1 of shared T;

available: shared array 0..n-1 of 0..max;

\var K: 1..n-1;

region available do begin

37

available(0) := max;

for every k do available (k) := 0; end

\

var j: 0..max-1; succ: 0..n-1; begin

j := 0; succ := (i+1) mod n; repeat

region available do

await available (i) > 0;

region buffer(j) do consume element; region available do begin

available (i) := available(i) – 1;

available (succ) := available (succ) + 1; end

j := (j+1) mod max; forever end

b.死锁可以被解决通过 P0 waits for Pn-1 AND P1 waits for P0 AND . . . . .

Pn-1 waits for Pn-2 因为

(available (0) = 0) AND (available (1) = 0) AND . . . . .

(available (n-1) = 0)

但是如果max > 0,这个条件不成立，因为临界域满足 claim(1)+ claim(2)+ ?+claim(n)

< available(1)+available(2)+?+available(n) =max

６.１３ a.３个进程共享４个资源单元，一次只能保留或释放一个单元。每个进程最大需要２个单元。说明不会死锁。

b.Ｎ个进程共享Ｍ个资源单元，一次只能保留或释放一个单元。每个进程最大需要单元数不超过Ｍ，并且所有最大需求的总和小于Ｍ+Ｎ。说明不会发生死锁。

解：a.说明由于每个进程最多需要2个资源，最坏情况下，每个进程需要获得一个，系统还剩1个，这一个资源，无论分给谁都能完成。完成进程释放资源后，使剩余进程也完成，故系统不会死锁。

b.假定每个进程最多申请X个资源，最坏情况下，每个进程都得到X-1个资源都在申请最后一个资源，这时系统剩余资源数量为M-N(X－1)，只要系统还有一个剩余资源，就可以使其中的一个进程获得所需要的全部资源，该进程运行结束以后释放资源，就可以使其他进程得到全部资源的 满足，因此，当M-N(X-1)》1时系统不会发生死锁，解这个不等式X《（M+N-1）,系统不会发生死锁，因此，当所有进程的需求总和小于M+N时，系统是不会发生死锁的。

６.１４考虑一个由四个进程和一个单独资源组成的系统，当前的声明和分配矩阵是

38

3 1 2 1 C = 9 A= 3 7 2

对于安全状态，需要的最小资源数目是多少？

解：最小资源数是３个，总共有１０个资源。Ｐ２获得一个资源，完成后释放两个资源，Ｐ１获得三个资源，完成后释放三个资源，接下来Ｐ４获得五个资源，释放完资源后，Ｐ３获得所需的６个资源后完成。

６.１５考虑下列处理死锁的方法：1银行家算法，2死锁检测并杀死线程，释放所有资源，３事先保留所有资源，４如果线程需要等待，５资源排序，６重新执行检测死锁并退回线程的动作。

评价解释死锁的不同方法使用的一个标准是，哪种方法允许最大的并发。换言之，在没有死锁时，哪种方法允许最多数目的线程无需要等待继续前进？对下面列出的６种处理死锁的方法，给出从１到６的一个排序（１表示最大程序的并发），并解释你的排序。

另一个标准是效率；哪种方法需要最小的处理器开销？假设死锁很少发生，给出各种方法从１到６的一个排序（１表示最有效），并解释这样排序的原因。如果死锁发生很频繁，你的顺序需要改变吗？ 解：a从最多并发事件到最少, 有一个大概的次序如下： 1. 死锁检测并杀死线程，释放所有资源 发现死锁并退回线程的动作，如果线程需要等候那么重新开始线程而且释放所有的资源，在死锁发生之前，这些运算法则都不会限制并发, 因为他们仰赖运行时间检查而并非静态的限制。 他们的效果在死锁被发现比较难以描述：他们仍然允许许多并发(在一些情形，他们增加它), 但是很难有准确的估计。 第三个运算法则是最奇怪的, 因为如此后许多的它的并发将会是无用的重复; 因为线程竞争执行时间, 这一个运算法则也影响运行速度。 因此在两者的极端,它以这顺序被列出两次。 2. 银行家的运算法则 资源排序

这些运算法则因为限制多种的可允许的计算，而相对早先两种法则会引起更多的不必要的等候。 银行家的运算法则避免不安全的配置 和资源排序限制配置序列以便线程在他们是否一定等候的时候有较少的选择。

3. 事先保留所有的资源

这一个运算法则相比前两个要允许更少的并发, 但是比最坏的那一种有更少的缺点。因为要预先保留所有的资源,线程必须等候比较长的而且当他们工作的时候更有可能阻塞其他的线程,因此系统上来说具有更多的线性。

4. 如果线程需要等待，则重新启动线程并且释放所有的资源

如上所述, 这一个运算法则在区别最多和最少并发上有疑问,这具体要看并发的定义。 b从最高效率到最低，有如下大概的一个顺序： 1. 预先保留所有的资源 资源排序

因为他们没有包括运行时间经常开支，所以这些运算法则最有效率。 注意这是在相同的静态限制下的结果。 2. 银行家的运算法则

发现死锁而且杀死线程,释放它的资源

这些运算法则在概略的配置上包括运行时间检查

; 银行家的运算法则运行搜寻查证复杂度在线程和配置的数字和死锁检测中是 O(n m)，死锁检测的复杂度是 O(n)。资源-从属链被线程数目，资源数目和分配数目限制。 3. 发现死锁并退回线程的动作

39

这一个运算法则运行也需要运行上述的相同的时间检查。 在写内存上的复杂度为O(n) 。

4. 如果线程需要等待，则重新启动线程并释放所有的资源

这一个运算法则是非常无效率，有如下两个理由。 首先, 因为线程有重新开始的危险, 他们完成的可能性低。其次，他们与其他重新开始线程竞争有限的执行时间, 因此整个系统运行的速度很慢。

６.１６评价下面给出的就餐问题的解决方案。一位饥饿的哲学家首先拿起他左边的叉子，如果他右边的叉子也是可用的，则拿起右边的叉子开始吃饭，否则他放下左边的叉子，并重复这个循环。 解：如果哲学家们步调完全一致地拿起左边叉子又放下的话，他们会重复这一过程，导致饥饿情况的出现。 ６.１７假设有两种类型的哲学家。一类总是先拿起左边的叉子（左撇子），另一类总是先拿起右边的叉子（右撇子）。左撇子的行为和图６.１２中定义的一致。右撇子的行为如下： begin repeat

think;

wait(fork[(i+1)mod5]); wait(fork[i]); eat;

signal(fork[i]);

signal(fork[(i+1)mod5]);

forever; end;

证明：a如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以避免死锁。 b如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以防止饥饿。

解：a假设存在死锁情况，设有 D个哲学家，他们每人都有一支叉子而且另一支叉子被邻居占有。不失一般性，设Pj 是一个左撇子。 Pj 抓牢他的左边叉子而且没有他的右边叉子, 他的右边邻居 Pk 没有完成就餐因此也是一个左撇子。 因此依次推理下去所有这Ｄ个哲学家都是左撇子。这与既有左撇子又有右撇子的条件矛盾，假设不成立，不存在死锁。 b

假设左撇子 Pj 饥饿，也就是说，有一部分人在就餐而Pj从不吃。 假如 Pj 没有叉子。 这样 Pj 的左边邻居 Pi 一定持续地占有叉子而始终不吃完。 因此Pi 是 右撇子，

抓住他的右边叉子, 但是从不得到他的左边叉子来完成就餐,也就是说 Pi

也饥饿。 现在 Pi 左边邻居也一定是持续占有右边叉子的右撇子。 向左进行这样的推理，得出所有哲学家都是饥饿的右撇子，这同Pj是个左撇子矛盾。因此 Pj 一直拥有左边子而且在等待他的右边叉子,Pj 的右边邻居 Pk 一直举着他的左边叉子而且从不完成一餐,也就是, Pk 是也饥饿的左撇子。 如果 Pk 不是一直拿着他的左边叉子， Pj 就可以就餐;因此 Pk 拿着他的左边叉子。向右推理可得所有哲学家都是饥饿的左撇子。这与条件矛盾，因此假设不成立，没有人饥饿。

６.１８图１.１７显示了另外一个使用管程解决哲学家就餐问题的方法。和图６.１４比较并阐述你的结论。

解：图６.１４是等待可用的叉子，图６.１７是等待邻居吃完，在本质上逻辑是一样的，后者显得更加紧凑。

40

monitor dining_controller; enum states{thinking,hungry,eating} state[5]; cond needFork[5] /*condition variable*/ void get_forks(int pid) /*pid is the philosopher id number*/ { start[pid]=hungry; /*announce that I am hungry*/ if(state[(pid+1)%5]= =eating ||(state[(pid-1)%5]= =eating cwait(needFork[pid]); /*wait if either neighbor is eating*/ state[pid]=eating; /*proceed if neither neighbor is eating*/ } void release_fork(int pid) { state[pid]=thinking; /*give right(higher)neighbor a chance to eat*/ if(state[(pid+1)%5])= =hungry) &(state[(pid+2)%5])!=eating) csignal(needFork[pid+1]); /*give left(lower)neighbor a chance to eat*/ else if(state[(pid-1)%5]= =hungry) ||(state[(pid-2)%5!=eating]

void philosopher[k=0 to 4] /*the five philosopher clients*/ { while(true) { ; get_forks(k); /*client requests two forks via monitor*/ ; release_forks(k); /*client releases forks via the monitor*/ } }

６.１９在表６.１３中，Linux的一些原子操作不会涉及到对同一变量的两次访问。比如

atomic_read(atomic_t *v).简单的读操作在任何体系结构中都是原子的。为什么该操作增加到了原子操作的指令表？

解：原子操作是在原子数据类型上操作, 原子数据类型有他们自己的内在的 格式。 因此，不能用简单的阅读操作, 但是特别的阅读操作

41

对于原子数据类型来说是不可或缺的。 ６.２０考虑Linux系统中的如下代码片断： read_lock(&mr_rwlock); write_lock(&mr_rwlock);

mr_rwlock是读者写者锁。这段代码的作用是什么？

解：因为写者锁将会自旋，所以这段代码会导致死锁, 等待所有的 读者解锁, 包括唤醒这个线程。

６.２１两个变量a和b分别有初始值１和２，对于Linux系统有如下代码：

线程1 a = 3； mb( )； -- -- 线程2 -- -- c = b； rmb()； d = a；

使用内在屏障是为了避免什么错误？

解：没有使用内存屏障, 在一些处理器上可能 c接到b 的新值, 而d接到b 的旧值。 举例来说, c可以等于 4(我们期待的), 然而 d 可能等于 1.(不是我们期待的)。 使用mb() 确保a 和 b 按合适的次序被写, 使用 rmb()确保 c 和d 按合适的次序被读。

第7章 内存管理

7.1. 2.3节中列出了内存管理的5个目标，7.1节中列出了5中需求。请说明它们是一致的。

答: 重定位≈支持模块化程序设计; 保护≈保护和访问控制以及进程隔离; 共享≈保护和访问控制;

逻辑组织≈支持模块化程序设计;

物理组织≈长期存储及自动分配和管理.

7.2. 考虑使用大小相等分区的固定分区方案。分区大小为2e16字节，贮存的大小为2e24字节。使用一

个进程表来包含每一个进程对应的分区。这个指针需要多少位？

答:分区的数量等于主存的字节数除以每个分区的字节数：224/216 = 28. 需要8个比特来确定一个分区大小为28中的某一个位置。

7.3. 考虑动态分区方案，说明平均内存中空洞的数量是段数量的一半。

答: 设n和h为断数量和空洞数量的个数.在主存中,每划分一个断产生一个空洞的概率是0.5,因为删除一个断和添加一个断的概率是一样的.假设s是内存中断的个数那么空洞的平均个数一定等于s/2.而导致空洞的个数一定小余断的数量的直接原因是相邻的两个断在删除是一定会产生一个空洞.

7.4. 在实现动态分区中的各种放置算法（见7.2节），内存中必须保留一个空闲块列表。分别讨论最佳适

配、首次适配、临近适配三种方法的平均查找长度。

答:通过上题我们知道，假设s是驻留段的个数，那么空洞的平均个数是s/2。从平均意义上讲，平均查找长度是s/4。

7.5. 动态分区的另一种放置算法是最坏适配，在这种情况下，当调入一个进程时，使用最大的空闲存储

块。该方法与最佳适配、首次适配、邻近适配相比，优点和缺点各是什么？它的平均查找长度是多少？

答：一种对最佳适配算法的评价即是为固定分配一个组块后和剩余空间是如此小以至于实际上已经

42

没有什么用处。最坏适配算法最大化了在一次分配之后，剩余空间的大小仍足够满足另一需求的机率，同时最小化了压缩的概率。这种方法的缺点是最大存储块最早被分配，因此大空间的要求可能无法满足。

7.6. 如果使用动态分区方案，下图所示为在某个给定的时间点的内存配置：

阴影部分为已经被分配的块；空白部分为空闲块。接下来的三个内存需求分别为40MB，20MB和10MB。分别使用如下几种放置算法，指出给这三个需求分配的块的起始地址。 a. 首次适配 b. 最佳适配

c. 临近适配（假设最近添加的块位于内存的开始） d. 最坏适配 答：

a. 40M的块放入第2个洞中,起始地址是80M. 20M的块放入第一个洞中.起始地址是20M. 10M的块的起始地址是120M。

b. 40M,20N,10M的起始地址分别为230M,20M和160M.

c. 40M,20M,10M的起始地址是80M,120160M.

d. 40M,20M,10M,的起始地址是80M,230M,360M.

7.7. 使用伙伴系统分配一个1MB的存储块。

a. 利用类似于图7.6的图来说明按下列顺序请求和返回的结果：请求70；请求35；请求80；返回

A；请求60；返回B；返回D；返回C。 b. 给出返回B之后的二叉树表示。 答： a.

b.

43

7.8. 考虑一个伙伴系统，在当前分配下的一个特定块地址为011011110000.

a. 如果块大小为4，它的伙伴的二进制地址为多少？ b. 如果块大小为16，它的伙伴的二进制地址为多少？ 答：

a. 011011110100 b. 011011100000

k

7.9. 令buddyk(x)为大小为2、地址为x的块的伙伴的地址，写出buddyk(x)的通用表达式。

答：

7.10. Fabonacci序列定义如下：

F0=0,F1=1,Fn+2=Fn+1+Fn,n≧0

a. 这个序列可以用于建立伙伴系统吗？

b. 该伙伴系统与本章介绍的二叉伙伴系统相比，有什么优点？ 答：

a. 是。字区大小可以确定Fn = Fn-1 + Fn-2.。

b. 这种策略能够比二叉伙伴系统提供更多不同大小的块，因而具有减少内部碎片的可能性。但由于

创建了许多没用的小块，会造成更多的外部碎片。

7.11. 在程序执行期间，每次取指令后处理器把指令寄存器的内容（程序计数器）增加一个字，但如果遇

到会导致在程序中其他地址继续执行的转跳或调用指令，处理器将修改这个寄存器的内容。现在考虑图7.8。关于指令地址有两种选择：

? 在指令寄存器中保存相对地址，并把指令寄存器作为输入进行动态地址转换。当遇到一次成功的

转跳或调用时，由这个转跳或调用产生的相对地址被装入到指令寄存器中。

? 在指令寄存器中保存绝对地址。当遇到一次成功的转跳或调用时，采用动态地址转换，其结果保

存到指令寄存器中。 哪种方法更好？

44

答：使用绝对地址可以减少动态地址转换的次数。但是，我们希望程序能够被重定位。因此，在指令寄存器中保存相对地址似乎就更好一些。也可以选择在进程被换出主存时将指令寄存器中的地址转换为相对地址。

321016

7.12. 考虑一个简单分页系统，其物理存储器大小为2字节，页大小为2字节，逻辑地址空间为2个页。

a. 逻辑地址空间包含多少位？ b. 一个帧中包含多少字节？

c. 在物理地址中指定帧需要多少位？ d. 在页表中包含多少个页表项？

e. 在每个页表项中包含多少位？（假设每个页表项中包含一个有效/无效位） 答：

161026

a. 物理地址空间的比特数是2*2=2

10

b. 一个帧包含的字节跟一个页是一样的,2比特.

321022

c. 主存中帧的数量是2/2=2,所以每个帧的定位要22个比特

16

d. 在物理地址空间,每个页都有一个页表项,所以有2项

e. 加上有效/无效位，每个页表项包含23位。7.13. 分页系统中的虚地址a相当于一对（p，w），其中p是页号，w是页中的字节号。令z是一页中的字

节总数，请给出p和w关于z和a的函数。

答：关系是：a = pz + w，其中p = ∟a/z?, a/z的整数部分。w = Rz(a) ，a除以z的余数

7.14. 在一个简单分段系统中，包含如下段表：

起始地址 660 1752 222 996 长度（字节） 248 442 198 604 对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误是否会发生： a. 0，198 b. 2，256 c. 1，530 d. 3，444 e. 0，222 答：

a. 段0定位在660,所以我们有物理地址660+190=858. b. 222+156=378

c. 段1长度为422,所以会发生错误 d. 996+444=1440 e. 660+222=882.

7.15. 在内存中，存在连续的段S1,S2,?，Sn按其创建顺序一次从一端放置到另一端，如下图所示：

当段Sn+1被创建时，尽管S1,S2,?，Sn中的某些段可能已经被删除，段Sn+1仍被立即放置在段Sn之后。当段（正在使用或已被删除）和洞之间的边界到达内存的另一端时，压缩正在使用的段。 a. 说明花费在压缩上的时间F遵循以下的不等式：

F≧(1-f)/1+kf), k=t/2s-1

其中，s表示段的平均长度（以字为单位）；l标识段的平均生命周期，按存储器访问；f表示在平衡条件下，未使用的内存部分。提示：计算边界在内存中移动的平均速度，并假设复制一个字至少需要两次存储器访问。

b. 当f=0.2，t=1000，s=50时，计算F。 答：

45

a. 很明显,在一个周期t内一些段会产生而一些段会被删除.因为系统是公平的,一个新的段会在t内被插入,此外,边界会医s/t的速度移动.假设t0是边界到达空洞的时间,t0=fmr/s, m=内存的长度,在对段进行压缩时会有(1-f)m个数被移动,压缩时间至少是2(1-f)m.则花在压缩上的时间F为F=1-t0/(t0+tc)。

b. K=(t/2s)-1=9;F≧(1-0.2)/(1+1.8)=0.29

第8章 虚拟内存

8.1 假设在处理器上执行的进程的也表如下所示。所有数字均为十进制数，每一项都是从0开始记数的，并且所有的地址都是内存字节地址。页尺寸为1024个字节。 虚拟页号 有效位 访问位 修改位 页帧号 0 1 1 0 4 1 1 1 1 7 2 0 0 0 — 3 1 0 0 2 4 0 0 0 — 5 1 0 1 0 a． 描述CPU产生的虚拟地址通常是如何转化成一个物理主存地址的。 b．下列虚拟地址对应于哪个物理地址（不用考略页错误）？ （i）1052 （ii）2221 （iii）5499 解答

a：由虚拟地址求得页号和偏移量，用虚拟页号作为索引页表，得到页帧号，联系偏移量得到物理地址

b:(i)1052=1024+28 查表对应的页帧号是7，因此物理地址为7*1024+28=7196 (ii)2221=2*1024+173 此时出现页错误

(iii)5499=5*1024+379 对应的页帧号为0 因此物理地址是379

8.2 考虑一个使用32位的地址和1KB大小的页的分页虚拟内存系统。每个页表项需要32位。需要限制页表的大小为一个页。 a．页表一共需要使用几级？

b．每一级页表的大小是多少？提示：一个页表的大小比较小。

c．在第一级使用的页较小与在最底下一级使用的页较小相比，那种策略使用最小个数的页？ 解答

a：虚拟内存可以分为232/210= 222页，所以需要22个bit来区别虚拟内存中的一页，每一个页表可以包含210/4=28项，因此每个页表可以包含22bit中的8个bit，所以需要三级索引。 b：第二级页表有28个页表项，第一级页表有26个页表项。

c：如果顶层有26个页表项将会减少使用空间，在这种情况下，中间层页表有26个并且每个都有28个页表项，底层有214个页并且每个都有28个页表项，因此共有1+26+214页=16,449页。如果中间层有26个页表项，那么总的页数有1+28+214页=16,641页。如果底层有26个页表项，那么总的页表数是1+28+216页=65,973页。 8.3 a：图8.4中的用户表需要多少内存空间？

b：假设需要设计一个哈希反向页表来实现与图8.4中相同的寻址机制，使用一个哈希函数来将20位页号映射到6位哈希表。表项包含页号帧号和链指针。如果页表可以给每个哈希表项分配最多3个溢出项的空间，则哈希反向页表需要占用多大的内存空间？

46

解答

a：4Mbyte

b：行数：26+2=128项。每项包含：20（页号）+20（帧号）+8bits（链索引）=48bits=6bytes。总共：128*6=768bytes

8.4 一个进程分配给4个页帧（下面的所有数字均为十进制数，每一项都是从0开始计数的）。上一次把一页装入到一个页帧的时间，上一次访问页帧中的页的时间，每个页帧中的虚拟页号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之间的时钟时间，而不是从事件发生到当前的时钟值）。 虚拟页号 页帧 加载时间 访问时间 R位 M位 2 0 60 161 0 1 1 1 130 160 1 0 0 2 26 162 1 0 3 3 20 163 1 1 当虚拟页4发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。 a.FIFO（先进先出）算法 b.LRU（最近最少使用）算法 c.Clock算法

d.最佳（使用下面的访问串）算法

e.在页错误之前给定上述内存状态，考虑下面的虚拟页访问序列： 4,0,0,2,4,2,1,0,3,2

如果使用窗口大小为4的工作集策略来代替固定分配，会发生多少页错误？每个页错误何时发生？ 解答

a:页帧3，在时间20加载，时间最长。

b:页帧1，在时间160访问距现在时间最长。 c:清除页帧3的R位（最早加载），清除页帧2的R位，（次最早加载），换出的是页帧0因为它的R位为0。

d:换出的是页帧3中的虚拟页3，因为它将最晚被访问到。 e:一共有6个错误，如下

8.5 一个进程访问5页：A,B,C,D和E，访问顺序如下：

A;B;C;D;A;B;E;A;B;C;D;E

假设置换算法为先进后出，该进程在主存中有三个页帧，开始时为空，请查找在这个访问顺序中传送的页号。对于4个页帧的情况，请重复上面的过程。 解答

分别有9次和10次页错误，这被称之为“Belady′s现象”（\Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine,\by Belady et al, Communications of the ACM, June 1969.）

8.6 一个进程在磁盘上包含8个虚拟页，在主存中固定分配给4个页帧。发生如下顺序的页访问：

1,0,2,2,1,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,7,2,4,2,7,3,3,2,3

47

a.如果使用LRU替换策略，给出相继驻留在这4个页帧中的页。计算主存的命中率。假设这些帧最初是空的。

b.如果使用FIFO策略，重复问题（a）。

c.比较使用这两种策略的命中率。解释为什么这个特殊的访问顺序，使用FIFO的效率接近于LRU。 解答

a:LRU：命中率=16/33

b:FIFO：命中率=16/33

c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。

8.7 在VAX中，用户页表以系统空间的虚拟地址进行定位。让用户页表位于虚存而不是主存中有什么好处？有什么缺点？ 解答

最主要的优点是在物理内存空间上的节省。这主要是两方面的原因：（1）一个用户页表可以仅当使用时才取入内存。（2）操作系统可以动态的分配用户页表，产生一个页表仅当程序被创建时。

当然，也有一个缺点：地址转换需要多余的工作。 8.8 假设在主存中执行下列程序语句： for(i=1;i≤n;i++) a[i]=b[i]+c[i];

页尺寸为1000个字。令n=1000。使用一台具有所有寄存器指令并使用了索引寄存器的机器，写出实现上述语句的一个假想程序，然后给出在执行过程中的页访问顺序。 解答

由机器语言编写的程序，在主存中地址4000处开始运行。运行情况如下： 4000 （R1）←1 建立索引记录i 4001 （R1）←n 在R2中建立n 4002 比较R2，R1 检查i﹥n 4003 如果大于则跳转到4009

4004 （R3）←B（R1） 使用索引记录R1到达B[i]

4005 （R3）←（R3）+C（R1）使用索引记录R1加上C[i] 4006 A（R1）←（R3）使用索引记录R1将总和存入A[i]中 4007 （R1）←（R1）+1 i加一 4008 跳到4002 6000—6999 存储A 7000—7999 存储B 8000—8999 存储C 9000 存储1

48

9001 存储n

由这个循环产生的参考串为 494944（47484649444）1000

包括11.000个参考，但仅包括5个不寻常的页

8.9 IBM System/370体系结构使用两级存储器结构，并且分别把这两级称为段和页，这里的分段方法缺少本章所描述的关于段的许多特征。对于这个基本的370体系结构，页尺寸可以是2KB或4KB，段大小固定为64KB或1MB。这种方案缺少一般分段系统的那些优点？370的分段方法有什么好处？ 解答

S/370分段系统是固定的且对程序员是不可见的，因此没有一个分段系统的优点在S/370中实现（无保护情况下）每一个段表项的P位提供整个段表的保护。

8.10 假设页尺寸为4KB，页表项大小位4字节。如果要映射一个64位地址空间，并且最顶层的页表对应于一页，则需要几级页表？ 解答

因为每个页表项有4bytes，每个页表有4Kbytes，所以每个页表可以映射1024=210个页，标识出210×212=222bytes的地址空间。然而，地址空间是264bytes。增加一个二层页表，顶层页表指向210个页表，标识出232个页表，将这个过程继续下去就得到：

深度 地址空间 1 222bytes 2 232bytes 3 242bytes 4 252bytes 5 262bytes 6 272bytes（﹥264bytes） 我们可以看到5层是不够表示64位的地址空间，但是6层达到了要求。但是6层中只有2位被使用，而不是全部的10位。所以不是使用72位的虚拟地址空间，而是将除了最低两位外的其他位全部屏蔽忽略。这样将会得到一个64位地址空间，顶层页只有4个页表项。另外一种方法是修改规则将顶层页做成一个单独的物理页并且让它适合4个页。这样将会节省一个页。

8.11 考虑一个系统该系统采用基于页的内存映射，并使用一级页表。假设页表总是在主存中。 a.如果一次存储器访问需要200ns，那么一次需要调页的存储器访问要多长时间？

b.现在增加一个MMU，在命中或未命中时有20ns的开销。如果假设有85%的存储器访问命中都在MMU TLB中，那么哪些是有效的存储器访问时间？ c.解释TLB命中率如何影响有效的存储器访问时间。 解答

a.400ns。200ns用来得到页表项，200ns用来到达存储位置 b.这是一个常见的有效时间计算公式： （220×0.85）+（420×0.15）=250

两种情况：第一种，TLB中包含所需的页表项。在这种情况下在200ns外多了20ns的存储访问时间。第二种，TLB中不包含所需的页表项。这时我们会再多花200ns来把所需的页表项取入TLB。

c.TLB命中率越高有效存储器访问时间就越短，因为额外的200ns来得到页表项的时间被节省了。

8.12 考虑一个进程的页访问序列，工作集为M帧，最初都是空的。页访问串的长度为P，包含N个不同的页号。对任何一种页替换算法， a.页错误次数的下限是多少？

49

b.页错误次数的上限是多少？ 解答 a.N b.P

8.13 在论述一种页替换算法时，一位作者用一个在循环轨道上来回移动的雪犁机来模拟说明：雪均匀地落在轨道上，雪犁机一恒定的速度在轨道上不断的循环，轨道上被扫落的雪从系统中消失。

a.8.2节讨论的哪一种页替换算法可以用它来模拟？ b.这个模拟说明了页替换算法的那些行为？ 解答

a.这是一个很好的时钟算法的类似。雪落在轨道上类似于页到达循环页缓存中。时钟算法时钟算法指针的移动类似于雪犁机的移动。

b.注意到在时钟指针最近的前面可替换页的密度是最高的，就好像在雪犁机最近的前面的雪是最厚的一样。因此我们可以认为时钟算法在寻找替换页时是非常有效的。事实上可以看到雪犁机前雪的厚度是轨道上雪平均厚度的两倍。通过这种类似，在单循环中被时钟策略替换的页的号码是被随机替换的页的号码的两倍。这个近似不是最完美的，因为时钟指针并不是以一个确定的速率移动，但是直观意义还是有的。

8.14 在S/370体系结构中，存储关键字是与实存中每个页帧相关联的控制字段。这个关键字中与页替换有关的有两位：访问位和修改位。当在帧中的任何单元执行写操作时，修改位被置为1；当一个新页被装入到该帧中时，访问位被置为1。请给出一种方法，仅仅使用访问位来确定哪个页帧是最近最少使用的。 解答

处理器硬件置访问位为0当一个新页被加入到帧时，置为1当这个页帧的位置被访问到时。操作系统可以维护几个页帧表队列，一个页帧表项从一个队列移动到另一个队列取决于这个页帧的访问位被值为零的时间长短。当必须有页被替换时，被替换的页将从具有最长未被访问时间的页帧队列中选取。

8.15 考虑如下的页访问序列（序列中的每一个元素都是页号）： 12345213323454511325

定义经过k次访问后平均工作集大小为Sk（△）=1/k∑W（t，△）（t=1—k），并且定义经过k次访问后错过页的概率为Mk（△）=1/k∑F（t，△）（t=1—k），其中如果页错误发生在虚拟时间t，则F（t，△）=1，否则F（t，△）=0。

a.当△=1，2，3，4，5，6时，绘制与图8.19类似的图标来说明刚定义的页访问序列的工作集。

b.写出S20（△）关于△的表达式。 b.写出M20（△）关于△的表达式。 解答 a.

50