操作系统复习题2014年

操作系统

第一章

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.2什么是操作系统的内核？

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

2.3什么是多道程序设计？

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

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

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

2.6列出并简要介绍操作系统的五种典型存储管理职责。

进程隔离：操作系统必须保护独立的进程，防止互相干涉数据和存储空间。 自动分配和管理：程序应该根据需要在存储层次间动态的分配，分配对程序员是透明的。因此，程序员无需关心与存储限制有关的问题，操作系统有效的实现分配问题，可以仅在需要时才给作业分配存储空间。 P51

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

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

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

2.9解释单体内核和微内核的区别。

单体内核是一个提供操作系统应该提供的功能的大内核，包括调度、文件系统、网络、设备驱动程序、存储管理等。内核的所有功能成分都能够访问它的内部数据结构和程序。典型情况下，这个大内核是作为一个进程实现的，所有元素都共享相同的地址空间。微内核是一个小的有特权的操作系统内核，只提供包括进程调度、内存管理、和进程间通信等基本功能，要依靠其他进程担当起和操作系统内核联系作用。 2.10什么是多线程？

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

第三章

3.1 什么是指令跟踪？

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

答：新的批处理作业；交互登录；操作系统因为提供一项服务而创建；由现有的进程

派生。（详情请参考表3.1）

3.3 对于图3.6中的进程模型，请简单定义每个状态。

答：运行态：该进程正在执行。就绪态：进程做好了准备，只要有机会就开始执行。阻塞态：进程在某些事件发生前不能执行，如I/O操作完成。新建态：刚刚创建的进程，操作系统还没有把它加入到可执行进程组中。退出态：操作系统从可执行进程组中释放出的进程，或者是因为它自身停止了，或者是因为某种原因被取消。 3.4 抢占一个进程是什么意思？

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

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

3.6 为什么图3.9（b）中有两个阻塞态？

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

答：1.进程不能立即执行。2.进程可能是或不是正在等待一个事件。如果是，阻塞条件不依赖于挂起条件，阻塞事件的发生不会使进程立即被执行。3.为了阻止进程执行，可以通过代理把这个进程置于挂起态，代理可以是进程自己，也可以是父进程或操作系统。4.除非代理显式地命令系统进行状态转换，否则进程无法从这个状态中转移。 3.8 对于哪类实体，操作系统为了管理它而维护其信息表？

答：内存、I/O、文件和进程。（p92） 3.9 列出进程控制块中的三类信息。

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

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

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

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

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

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

第四章

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

这些元素中那些可能属于线程控制块，那些可能属于进程控制块？

答：这对于不同的系统来说通常是不同的，但一般来说，进程是资源的所有者，而每个线程都有它自己的执行状态。关于表3.5中的每一项的一些结论如下：进程标识：进程

必须被标识，而进程中的每一个线程也必须有自己的ID。处理器状态信息：这些信息通常只与进程有关。进程控制信息：调度和状态信息主要处于线程级；数据结构在两级都可出现；进程间通信和线程间通信都可以得到支持；特权在两级都可以存在；存储管理通常在进程级；资源信息通常也在进程级。

4.2 请列出线程间的模式切换比进程间的模式切换开销更低的原因。

答：包含的状态信息更少。(正因为上述很多信息是进程有而线程没有的) 4.3 在进程概念中体现出的两个独立且无关的特点是什么？

答：资源所有权和调度/执行。（p112）

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

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

答：例如地址空间，文件资源等。

4.6 列出用户级线程优于内核级线程的三个优点。

答：1.由于所有线程管理数据结构都在一个进程的用户地址空间中，线程切换不需要内核模式的特权，因此，进程不需要为了线程管理而切换到内核模式，这节省了在两种模式间进行切换（从用户模式到内核模式；从内核模式返回用户模式）的开销。2.调用可以是应用程序专用的。一个应用程序可能倾向于简单的轮询调度算法，而另一个应用程序可能倾向于基于优先级的调度算法。调度算法可以去适应应用程序，而不会扰乱底层的操作系统调度器。3.用户级线程可以在任何操作系统中运行，不需要对底层内核进行修改以支持用户级线程。线程库是一组供所有应用程序共享的应用级软件包。 4.7 列出用户级线程相对于内核级线程的两个缺点。

答：1.在典型的操作系统中，许多系统调用都会引起阻塞。因此，当用户级线程执行一个系统调用时，不仅这个线程会被阻塞，进程中的所有线程都会被阻塞。2.在纯粹的用户级进程策略中，一个多线程应用程序不能利用多处理技术。内核一次只把一个进程分配给一个处理器，因此一次进程中只能有一个线程可以执行。 4.8 定义jacketing。

答：Jacketing通过调用一个应用级的I/O例程来检查I/O设备的状态，从而将一个产生阻塞的系统调用转化为一个不产生阻塞的系统调用。

第五章

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

答：进程间的交互，共享资源之间的竞争，多个进程的同步问题，对进程的处理器时间分配问题(p144)

5.2列出并发的三种上下文

答：多个应用程序，结构化应用程序，操作系统结构 5.3执行并发进程的最基本要求是什么？ 答：加强互斥的能力(p144)

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

答：进程间互相不知道对方：这是一些独立的进程，他们不会一起工作。进程间间接知道对方：这些进程并不需要知道对方的进程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.11.什么是管程。

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

5.13.通常与读者-写者问题相关联的有哪些条件？

答：1.任意多的读进程可以同时读这个文件，2.一次只有一个写进程可以往文件中写，3.如果一个写进程正在往文件中写时，则禁止任何读进程读文件。

第六章

６.１给出可重用资源和可消费资源的例子。

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

可消费资源：中断，信号，消息和Ｉ/Ｏ缓冲区中的信息。 ６.２可能发生死锁所必须的三个条件是什么？ 答：互斥，占有且等待，非抢占。 ６.３产生死锁的第４个条件是什么？ 答：循环等待。

６.４如何防止占有且等待的条件？ 答：可以要求进程一次性地请求所有需要的资源，并且阻塞这个资源直到所有请求都同时满足。

６.５给出防止无抢占条件的两种方法。

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

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

另一个进程，要求它释放资源。 ６.６如何防止循环等待条件？

答：可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了Ｒ类型的资源，那么它接下来请求的资源只能是那些排在Ｒ类型之后的资源类型。 ６.７死锁避免，检测和预防之间的区别是什么？ 答：死锁预防是通过间接地限制三种死锁必要条件的至少一个或是直接地限制循环等待的发生来避免死锁的出现。死锁避免允许可能出现的必要条件发生，但是采取措施确保不会出现死锁的情况。而死锁检测允许资源的自由分配，采取周期性的措施来发现并处理可能存在的死锁情况。

６.４考虑下面的一个系统，当前不存在未满足的请求。

可用

r1 r2 r3 r4 2 1 0 0

当前分配 最大需求 仍然需求 r1 0 2 0 2 0 r2 0 0 0 3 3 r3 1 0 3 5 3 r4 2 0 4 4 2 r1 0 2 6 4 0 r2 0 7 6 3 6 r3 1 5 5 5 5 r4 2 0 6 6 2 r1 r2 r3 r4 a计算每个进程仍然可能需要的资源，并填入标为“仍然需要”的列中。 b系统当前是处于安全状态还是不安全状态，为什么。 c系统当前是否死锁？为什么？

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

e如果Ｐ３的请求（0，1，0，0）到达，是否可以立即安全地同意该请求？在什么状态（死锁，安全，不安全）下可以立即同意系统剩下的全部请求？如果立即同意全部请求，哪个进程（如果有）是死锁的或可能变成死锁的？ 解： 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 没有死锁

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

进程 最大 占用 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

６.１６评价下面给出的就餐问题的解决方案。一位饥饿的哲学家首先拿起他左边的叉子，如果他右边的叉子也是可用的，则拿起右边的叉子开始吃饭，否则他放下左边的叉子，并重复这个循环。

解：如果哲学家们步调完全一致地拿起左边叉子又放下的话，他们会重复这一过程，导致饥饿情况的出现。

６.１７假设有两种类型的哲学家。一类总是先拿起左边的叉子（左撇子），另一类总是先拿起右边的叉子（右撇子）。左撇子的行为和图６.１２中定义的一致。右撇子的行为如下： 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 拿着他的左边叉子。向右推理可得所有哲学家都是饥饿的左撇子。这与条件矛盾，因此假设不成立，没有人饥饿。

第7章 内存管理

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

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

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

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

答：如果许多进程正在执行同一程序，则允许每个进程访问该程序的同一个副本要比让每个进程有自己单独的副本更有优势。同样，合作完成同一任务的进程可能需要共享访问同一个数据结构。

7.5. 在固定分区方案中，使用大小不等的分区有什么好处？

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

答：内部碎片是指由于被装入的数据块小于分区大小而导致的分区内部所浪费的空间。外部碎片是与动态分区相关的一种现象，它是指在所有分区外的存储空间会变成越来越多的碎片的。

7.7. 逻辑地址、相对地址和物理地址间有什么区别？

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

7.8. 页和帧之间有什么区别？

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

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

3210

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

16

空间为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.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.

第八章 虚拟内存

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

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

8.2 解释什么是抖动。 虚拟内存结构的震动现象，在这个过程中处理器大部分的时间都用于交换块，而不是执行指令。

8.3 为什么在使用虚拟内存时，局部性原理是至关重要的？ 可以根据局部性原理设计算法来避免抖动。总的来说，局部性原理允许算法预测哪一个当前页在最近的未来是最少可能被使用的，并由此就决定候选的替换出的页。 8.4 哪些元素是页表项中可以找到的元素？简单定义每个元素。 帧号：用来表示主存中的页来按顺序排列的号码。存在位（P）：表示这一页是否当前在主存中。修改位（M）：表示这一页在放进主存后是否被修改过。 8.5 转移后备缓冲器的目的是什么？

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

在请求式分页中，只有当访问到某页中的一个单元时才将该页取入主存。在预约式分页中，读取的并不是页错误请求的页。

8.7 驻留集管理和页替换策略有什么区别？ 驻留集管理主要关注以下两个问题：（1）给每个活动进程分配多少个页帧。（2）被考虑替换的页集是仅限在引起页错误的进程的驻留集中选择还是在主存中所有的页帧中选择。页替换策略关注的是以下问题：在考虑的页集中，哪一个特殊的页应该被选择替换。 8.8 FIFO和Clock页替换算法有什么区别？

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

（1）被替换出驻留集的页不久又被访问到时，仍在主存中，减少了一次磁盘读写。（2）被修改的页以簇的方式被写回，而不是一次只写一个，这就大大减少了I/O操作的数目，从而减少了磁盘访问的时间。

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

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

8.11 驻留集和工作集有什么区别？

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

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

在请求式清除中，只有当一页被选择用于替换时才被写回辅存；在预约式清除中，将这些被修改的多个页在需要用到它们所占据的页帧之前成批的写回辅存。

第九章单处理器调度

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增加了抢占机制的版本。在这种情况下，调度器总是选择预期剩余时间最短的进程。当一个新进程加入到就绪队列时，他可能比当前运行的进程具有更短的剩余时间，因此，只有新进程就绪，调度器就可能抢占当前正在运行的进程。 9.10简单定义最高响应比优先调度。

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

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

习题

9.1考虑下面的进程集合： 进程名 A B C D E 到达时间 0 1 3 9 12 处理时间 3 5 2 5 5 对这个集合，给出类似于表9.5和图9.5的分析。

每格代表一个时间单位，方框中的数表示当前运行的进程

A A A A A A A A ABAAAABBAAAAAAAABBBCCBCABCBCCBBCBABBBBCBBBBBBBABB C C B B B B C CBCBBCBBC D B B B C D B DBDDDDBDD D D D D D D D DEEDDDEDDDDDDDDDDEEDDDEDE D E E E E D E EEEEEEEEE D E E E E D D E E D E E E E E EEEEEEEE

第一到第八行依次是FCFS RR, q=1 RR, q=4 SPN SRT HRRN Feedback, q=1 Feedback, q=2(i)

A B C D E

Ta 0 1 3 9 12 Ts 3 5 2 5 5

FCFS Tf 3 8 10 15 20

Tr 3.00 7.00 7.00 6.00 8.00 6.20 Tr/Ts 1.00 1.40 3.50 1.20 1.60 1.74

RR q = 1 Tf 6.00 11.00 8.00 18.00 20.00

Tr 6.00 10.00 5.00 9.00 8.00 7.60

Tr/Ts 2.00 2.00 2.50 1.80 1.60 1.98

RR q = 4 Tf 3.00 10.00 9.00 19.00 20.00

Tr 3.00 9.00 6.00 10.00 8.00 7.20 Tr/Ts 1.00 1.80 3.00 2.00 1.60 1.88

SPN Tf 3.00 10.00 5.00 15.00 20.00

Tr 3.00 9.00 2.00 6.00 8.00 5.60 Tr/Ts 1.00 1.80 1.00 1.20 1.60 1.32

SRT Tf 3.00 10.00 5.00 15.00 20.00

Tr 3.00 9.00 2.00 6.00 8.00 5.60 Tr/Ts 1.00 1.80 1.00 1.20 1.60 1.32

HRRN Tf 3.00 8.00 10.00 15.00 20.00

Tr 3.00 7.00 7.00 6.00 8.00 6.20 Tr/Ts 1.00 1.40 3.50 1.20 1.60 1.74

FB q = 1 Tf 7.00 11.00 6.00 18.00 20.00

Tr 7.00 10.00 3.00 9.00 8.00 7.40 Tr/Ts 2.33 2.00 1.50 1.80 1.60 1.85

FB Tf 4.00 10.00 8.00 18.00 20.00

q = 2i Tr 4.00 9.00 5.00 9.00 8.00 7.00

Tr/Ts 1.33 1.80 2.50 1.80 1.60 1.81

9.2对下面的集合重复习题9.1的要求

进程 A B C D 到达时 0 1 2 3 处理时间 1 9 1 9

A A A A A A A A BBBBBBBBBCBBCBCCBBBBBBDDBDBBBBBBBBCBBBDBBDBBBBBDB B B B B B D D BDBBBBBBB B B B B B D B CDDCBCBBD B D D D D D B DDDDDDBDDBDDDDDDDDBDDDBDE D E E E E D E EEEEEEEEE D E E E E D D E E D E E E E E EEEEEEEE

A B C D Ta 0 1 2 3 Ts 1 9 1 9 FCFS Tf 1.00 10.00 11.00 20.00

Tr 1.00 9.00 9.00 17.00 9.00 Tr/Ts 1.00 1.00 9.00 1.89 3.22 RRq=1 Tf 1.00 18.00 3.00 20.00

Tr 1.00 17.00 1.00 17.00 9.00

Tr/Ts 1.00 1.89 1.00 1.89 1.44 RRq=4 Tf 1.00 15.00 6.00 20.00

Tr 1.00 14.00 4.00 17.00 9.00

Tr/Ts 1.00 1.56 4.00 1.89 2.11 SPN Tf 1.00 10.00 11.00 20.00

Tr 1.00 9.00 9.00 17.00 9.00 Tr/Ts 1.00 1.00 9.00 1.89 3.22 SRT Tf 1.00 11.00 3.00 20.00

Tr 1.00 10.00 1.00 17.00 9.00

Tr/Ts 1.00 1.11 1.00 1.89 1.25 HRRN Tf 1.00 10.00 11.00 20.00

Tr 1.00 9.00 9.00 17.00 9.00 Tr/Ts 1.00 1.00 9.00 1.89 3.22 FBq=1 Tf 1.00 19.00 3.00 20.00

Tr 1.00 18.00 1.00 17.00 9.25

Tr/Ts 1.00 2.00 1.00 1.89 1.47 FB Tf 1.00 18.00 3.00 20.00

q=2i Tr 1.00 17.00 1.00 17.00 9.00 Tr/Ts 1.00 1.89 1.00 1.89 1.44

第十一章 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指

令序列、通道命令和控制器命令。可以使用缓冲技术，以提高使用率。 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比特 习题

11.3使用与表11.2类似的方式，分析下列磁道请求：27，129，110，186，147，41，10，

64，120。假设磁头最初定位在磁道100处，并且沿着磁道号减小的方向移动。假设磁头沿着磁道增大的方向移动，请给出同样的分析。

FIFO 下一个被访问的磁道 27 129 110 186 147 41 10 64 120 平均寻道长度 横跨的磁道数 73 102 19 76 39 106 31 54 56 61.8 SSTF 下一个被访问的磁道 110 120 129 147 186 64 41 27 10 平均寻道长度 横跨的磁道数 10 10 9 18 39 122 23 14 17 29.1 SCAN 下一个被访问的磁道 64 41 27 10 110 120 129 147 186 平均寻道长度 横跨的磁道数 36 23 14 17 100 10 9 18 39 29.6 C-SCAN 下一个被访问的磁道 64 41 27 10 186 147 129 120 110 平均寻道长度 横跨的磁道数 36 23 14 17 176 39 18 9 10 38 如果磁头沿着增大的方向，只有SCAN和C-SCAN的结果有变化

SCAN 下一个被访问的磁道 110 120 129 147 186 64 41 27 10 平均寻道长度 横跨的磁道数 10 10 9 18 39 122 23 14 17 29.1 C-SCAN 下一个被访问的磁道 110 120 129 147 186 10 27 41 64 平均寻道长度 文件管理

横跨的磁道数 10 10 9 18 39 176 17 14 23 35.1 第12章

12.1域和记录有什么不同？

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

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

答：文件管理系统是一组系统软件，为使用文件的用户和应用程序提供服务。

12.4选择文件组织时的重要原则是什么？

答：访问快速，易于修改，节约存储空间，维护简单，可靠性。 12.5列出并简单定义五种文件组织。 答：堆是最简单的文件组织形式。数据按它们到达的顺序被采集，每个记录由一串数据组成。顺序文件是最常用的文件组织形式。在这类文件中，每个记录都使用一种固定的格式。所有记录都具有相同的长度，并且由相同数目、长度固定的域按特定的顺序组成。由于每个域的长度和位置已知，因此只需要保存各个域的值，每个域的域名和长度是该文件结构的属性。索引顺序文件保留了顺序文件的关键特征：记录按照关键域的顺序组织起来。但它还增加了两个特征：用于支持随机访问的文件索引和溢出文件。索引提供了快速接近目标记录的查找能力。溢出文件类似于顺序文件中使用的日志文件，但是溢出文件中的记录可以根据它前面记录的指针进行定位。索引文件：只能通过索引来访问记录。其结果是对记录的放置位置不再有限制，只要至少有一个索引的指针指向这条记录即可。此外，还可以使用长度可变的记录。直接文件或散列文件：直接文件使用基于关键字的散列。

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列出并简单定义三种文件分配方法。

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

12.4选择文件组织时的重要原则是什么？

答：访问快速，易于修改，节约存储空间，维护简单，可靠性。 12.5列出并简单定义五种文件组织。 答：堆是最简单的文件组织形式。数据按它们到达的顺序被采集，每个记录由一串数据组成。顺序文件是最常用的文件组织形式。在这类文件中，每个记录都使用一种固定的格式。所有记录都具有相同的长度，并且由相同数目、长度固定的域按特定的顺序组成。由于每个域的长度和位置已知，因此只需要保存各个域的值，每个域的域名和长度是该文件结构的属性。索引顺序文件保留了顺序文件的关键特征：记录按照关键域的顺序组织起来。但它还增加了两个特征：用于支持随机访问的文件索引和溢出文件。索引提供了快速接近目标记录的查找能力。溢出文件类似于顺序文件中使用的日志文件，但是溢出文件中的记录可以根据它前面记录的指针进行定位。索引文件：只能通过索引来访问记录。其结果是对记录的放置位置不再有限制，只要至少有一个索引的指针指向这条记录即可。此外，还可以使用长度可变的记录。直接文件或散列文件：直接文件使用基于关键字的散列。

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列出并简单定义三种文件分配方法。

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

本文来源：https://www.bwwdw.com/article/tjyv.html