P4 P5 10.5 10.8 0.1 0.4 参考答案：
(1)先来先服务（FCFS） 调度顺序 1 2 3 4 5 进程 P1 P2 P3 P4 P5 到达时刻 10.1 10.3 10.4 10.5 10.8 运行时间 0.3 0.9 0.5 0.1 0.4 开始时间 10.1 10.4 11.3 11.8 11.9 完成时间 10.4 11.3 11.8 11.9 12.3 周转时间 0.3 1.0 1.4 1.4 1.5 平均周转时间：T＝（0.3 + 1.0 + 1.4 + 1.4 + 1.5）/ 5 = 1.12 (2) 短进程优先（SPF） 调度顺序 1 2 3 4 5 进程 P1 P3 P4 P5 P2 到达时刻 10.1 10.4 10.5 10.8 10.3 运行时间 0.3 0.5 0.1 0.4 0.9 开始时间 10.1 10.4 10.9 11.0 11.4 完成时间 10.4 10.9 11.0 11.4 12.3 周转时间 0.3 0.5 0.5 0.6 2.0 平均周转时间：T＝（0.3 + 0.5 + 0.5 + 0.6 + 2.0）/ 5 = 0.78
27． 设有四个进程，它们到达就绪队列的时刻、运行时间及优先级（此处优先级1为最低优先级，优先级4为最高优先级）如表2－6所示。若分别采用非抢占式优先级调度算法和可抢占式优先级调度算法，试给出各进程的调度顺序以及平均周转时间。
表2－6 各进程到达就绪队列的时刻、运行时间及优先级
进程 P1 P2 P3 P4 到达时刻 0 1 2 3 运行时间 8 3 7 12 优先级 1 3 2 4 参考答案：
(1) 非抢占式优先级调度算法 调度顺序 1 2 3 4 进程 P1 P4 P2 P3 优先级 1 4 3 2 到达时刻 0 3 1 2 运行时间 8 12 3 7 开始时间 0 8 20 23 完成时间 8 20 23 30 周转时间 8 17 22 28 平均周转时间：T＝（8 + 17 + 22 + 28）/ 4 = 18.75
(2) 抢占式优先级调度算法 调度 顺序 1 进程 P1 优先级 1 到达 时刻 0 剩余运行时间 8 开始 时间 0 停止 时间 1 共完成时间 1 状态 未完成 周转 时间 2 3 4 5 6 P2 P4 P2 P3 P1 3 4 3 2 1 1 3 1 2 0 3 12 1 7 7 1 3 15 16 23 3 15 16 23 30 2 12 3 7 8 未完成 完成 完成 完成 完成 12 15 21 30 平均周转时间：T＝（12 + 15 + 21 + 30）/ 4 = 19.5
28． 什么是死锁？产生死锁的原因和必要条件是什么？处理死锁的基本方法有哪些？
参考答案：若系统中存在一组进程（两个或两个以上），它们中的每一个都占用了某些资源而又都在等待其中另一个进程所占用的资源，这种等待如果没有外力作用，将永远不会结束，这就是“死锁”，或说这一组进程处于“死锁”状态。
产生死锁的原因主要有两个：一是多个进程竞争资源，二是进程请求和释放资源的时机不对。
产生死锁的必要条件有：互斥条件、占有且等待条件、不可剥夺条件、循环等待条件。处理死锁的基本方法有：预防死锁、避免死锁、检测和解除死锁。
29． 什么是线程？简述与进程的区别和联系。
参考答案：线程是进程中的一个实体，是CPU调度和分派的基本单位。
线程具有许多传统进程的特征，故又称为轻型进程。传统的进程称为重型进程，相当于只有一个线程的任务。在引入线程的操作系统中，通常一个进程拥有若干个线程，至少也有一个线程。下面从调度、并发性、拥有资源和系统开销几个方面对线程和进程进行比较。
（1）调度。在传统的操作系统中，进程既是资源分配和拥有的基本单位，又是独立调度和执行的基本单位。而在引入线程后，则把线程作为调度和执行的基本单位，把进程作为资源分配和拥有的基本单位，把传统进程的两个属性分开，使线程轻装运行，从而显著提高系统的并发程度。同一进程中两个线程的切换不会引起进程切换，但由一个进程中的线程切换到另一个进程中的线程时，将会引起进程切换。
（2）并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可以并发执行，因而使系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。
（3）拥有资源。不论是传统的操作系统，还是引入线程的操作系统，进程都是拥有资源的独立单位。线程基本上不拥有资源（只有一点运行时必不可少的资源），但它可以访问其所属进程的全部资源。亦即一个进程的代码段、数据段以及系统资源（如已打开的文件、I/O设备等），可供该进程的所有线程共享。
（4）系统开销。系统在创建或撤消进程时，都要为之分配或回收资源，如内存空间、I/O设备等，因此系统所付出的开销将显著地大于创建或撤消线程的开销。同样，在进行进程切换时，需要保存当前进程的执行环境，设置和恢复被调度进程的执行环境，而线程切换只需保存和设置少量寄存器的内容，不涉及存储管理方面的操作，因而进程切换的开销也远大于线程切换的开销。
第三章习题
1．什么叫重定位？它有哪两种方式？这两种方式有什么区别？
参考答案：当程序装入内存时，操作系统将为该程序分配一个合适的内存空间，由于程序的逻辑地址与所分配到内存的物理地址不一致，而CPU执行指令时是按物理地址进行的，为使程序能正确运行，必须将用户程序中的逻辑地址转换成内存中的物理地址，这个地址转换过程就称为“重定位”，又称为“地址映射”。它有静态重定位和动态重定位两种方式。
两者的区别是：静态重定位是当用户程序被装入内存时，由装入程序一次性地把逻辑地址转换成物理地址，以后不再转换，它不需要增加硬件地址转换机构，但程序在内存中需占据一片连续区域，并且在重定位之后就不能再移动位置。动态重定位是把程序装入内存后，并不立即将程序中的逻辑地址转换为物理地址，而是在CPU执行每一条指令时进行地址转换，程序装入内存后可移动位置，不必连续存放在一起，但是需要硬件地址变换机构的支持。
2．在动态分区分配方式中，若采用最先适应算法，应如何回收内存？
参考答案：在动态分区分配方式中，若采用最先适应算法，则在回收一块内存空间时，首先根据回收区的始址在空闲分区链中查找插入点，找到后，按照下面四种情况进行回收：
（1）回收分区（记为R）与其前面的空闲分区（记为F1）邻接：合并R与F1，修改
空闲分区表中F1的大小，即加上R的大小，始址不变。
（2）回收分区（记为R）与其后面的空闲分区（记为F2）邻接：合并R与F2，修改
空闲分区表中F2的大小，即加上R的大小，始址不变。
（3）回收分区（记为R）与其前后的空闲分区（分别记为F1和F2）均邻接：合并R
与F1、F2，修改空闲分区表中F1的大小，即加上R与F2的大小，始址不变。 （4）回收分区（记为R）与其前后的空闲分区（分别记为F1和F2）均不邻接：在空
闲分区表中增加一条记录，该空闲分区的始址和大小，即为R的始址和大小。
3．动态分区分配的常用算法有哪些？各有什么特点？ 参考答案：动态分区分配的常用的内存分配算法
（1）最先适应算法。该算法要求空闲分区表按各分区起始地址递增的顺序排列。每次分配时，总是从第一条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割该空闲区，一部分分配给作业，余下部分仍为空闲区。该算法可能将大的空闲分区分割成多个小分区，从而使系统产生很多小得无法再用的“碎片”。
（2）最优适应算法。从所有空闲分区中挑选一个大小能满足作业要求的最小分区，这样可以保证不去分割一个更大的分区，使装入大作业时比较容易得到满足。为提高查找效率，将空闲分区表按各分区大小递增的顺序排列，分配时，顺序查找空闲分区表，直到找到一个大小满足作业要求的分区为止。
（3）最坏适应算法。与最优适应算法相反，该算法要求将空闲分区表按各分区大小递减的顺序排列，每次分配时从所有空闲分区中挑选一个最大的分区，分割一部分给作业使用，使剩下的部分不至于太小，仍可供使用，但不容易保留下大的空闲分区，不利于大作业的内存分配。
4． 在可变分区存储管理中，设作业A（30KB），作业B（70KB），作业C（50KB）依次请求内存分配，内存现有两个空闲区：F1（100KB）和F2（50KB），如图3－18所示。若分别采用最先适应算法、最优适应算法和最坏适应算法，画出内存分配情况图。
已分配 F1（100KB） 已分配 F2（50KB） 图3－18 内存使用情况示意图
参考答案：
（1） 采用最先适应算法分配：
已分配 作业A（30KB） 作业B（70KB） 已分配 作业C（50KB）
（2） 采用最优适应算法分配： 已分配 作业B（70KB） F1（30KB） 已分配 作业A（30KB） F2（20KB） 作业C没有足够的空闲分区分配，只有等待系统回收到足够空闲内存后再装入内存。 （3） 采用最坏适应算法分配：
已分配 作业A（30KB） 作业B（70KB） 已分配 作业C（50KB）
5．什么是对换？为什么要引入对换？ 参考答案：对换就是把内存中暂时不能运行的进程或暂时不用的程序和数据，换出到外存上，把已具备运行条件的进程或进程所需要的程序和数据，换入内存。引入对换的目的是为了提高内存的利用率。
6．简述分页系统的地址变换过程。 参考答案：在系统中设置了一个页表寄存器，用于存放当前执行进程的页表在内存的始址和页表长度。进程未执行时，其页表始址和页表长度存放在它的PCB中；当进程被调度执行时，这两个数据就被装入页表寄存器中。每当CPU要访问内存时，地址变换机构会自动将逻辑地址分为页号和页内地址两部分，然后将页号与页表长度进行比较，若页号不小于页表长度，说明本次所访问的地址已超越进程的地址空间，产生“地址越界”中断，并停止执行该指令。若未出现越界错误，则用页号检索页表，找到对应的表项后，从中得到该页面在内存的块号，并将块号送入物理地址寄存器中。与此同时，将逻辑地址中的页内地址直接送入物理地址寄存器的块内地址字段中，便得到了物理地址。整个地址转换过程如图3－10所示（图中页面大小为1KB）。可根据下式由块号计算出物理地址：
物理地址＝块号×块长（即页面大小）＋ 页内地址
7．分页和分段存储管理有何区别？ 参考答案：（1）页是信息的物理单位，分页是为实现离散分配方式，以减少内存的外零头，提供内存的利用率。段则是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好地满足用户的需要。
（2）页的大小固定且由系统决定，是由机器硬件实现的；而段的长度却不固定，决定
于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
（3）分页的作业地址空间是一维的，即单一的线性地址空间；而分段的作业地址空间
是二维的，由段名（或段号）和段内地址构成。
8．简述分段系统的地址变换过程。 参考答案：分段系统的地址转换采用动态重定位方式。在系统中设置了一个段表寄存器，用于存放当前执行进程的段表在内存的始址和段表长度。每当CPU要访问内存时，地址变换机构就将逻辑地址中的段号与段表长度进行比较，若段号不小于段表长度，产生“地址越界”中断，停止执行该指令。若未越界，则用段号检索段表，找到对应的表项后，从中得到该段的基址和段长，然后检查段内地址是否超出该段的段长，若超出，则发出“地址越界”中断，停止执行该指令。若未越界，就用基址加上段内地址，得到访存的物理地址。
9． 在一分页系统中，页面大小为4KB，某个已装入内存的作业的页表如表3－3所示。请计算下列逻辑地址所对应的物理地址：378，15034，5700，30000。
表3－3 作业页表 表3－4 作业段表 表3－5 作业页表
页号 0 1 2 3 4 块号 3 9 10 6 15
段号 0 1 2 3 4 段始址 2100 3500 200 1200 5400 段长 630 180 150 300 1120
页号 0 1 2 3 4 块号 15 20 33 － － 状态 1 1 1 0 0 参考答案：（1）逻辑地址378： 页号＝378/4096＝0
页内地址＝378MOD4096＝378
用页号0查找页表，找到对应的块号为3，则物理地址为： 物理地址＝块号×页面大小＋页内地址＝3×4096＋378＝12666 （2）逻辑地址15034：
页号＝15034/4096＝3
页内地址＝5700MOD4096＝2746
用页号3查找页表，找到对应的块号为6，则物理地址为：
物理地址＝块号×页面大小＋页内地址＝6×4096＋2746＝27322 （3）逻辑地址5700：
页号＝5700/4096＝1
页内地址＝5700MOD4096＝1604
用页号1查找页表，找到对应的块号为9，则物理地址为：
物理地址＝块号×页面大小＋页内地址＝9×4096＋1604＝38468
