南京邮电大学 操作系统 课后习题答案

《操作系统教程》南邮正式版

习题解答

第三章 进程管理与调度习题

1、什么是多道程序设计？多道程序设计利用了系统与外围设备的并行工作能力，从而提高工作效率，具体表现在哪些方面？ 答：

让多个计算问题同时装入一个计算机系统的主存储器并行执行，这种设计技术称“ 多道程序设计 ”，这种计算机系统称“多道程序设计系统” 或简称“多道系统”。在多道程序设计的系统中，主存储器中同时存放了多个作业的程序。为避免相互干扰，必须提供必要的手段使得在主存储器中的各道程序只能访问自己的区域。 提高工作效率，具体表现在：

? ?

提高了处理器的利用率；

充分利用外围设备资源：计算机系统配置多种外围设备，采用多道程序设计并行工作时，可以将使用不同设备的程序搭配在一起同时装入主存储器，使得系统中各外围设备经常处于忙碌状态，系统资源被充分利用；

? 发挥了处理器与外围设备以及外围设备之间的并行工作能力；

从总体上说，采用多道程序设计技术后，可以有效地提高系统中资源的利用率，增加单位时间内的算题量，从而提高了吞吐率。 2、请描述进程的定义和属性。 答：

进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配、调度和保护的独立单位。

进程的属性有：结构性?共享性?动态性?独立性?制约性?并发性 3、请描述进程与程序的区别及关系。 答：

1

程序是静止的，进程是动态的。进程包括程序和程序处理的对象（数据集），进程能得到程序处理的结果。进程和程序并非一一对应的，一个程序运行在不同的数据集上就构成了不同的进程。通常把进程分为“系统进程”和“用户进程”两大类，把完成操作系统功能的进程称为系统进程，而完成用户功能的进程则称为用户进程。 4、进程有哪三种基本状态？三种进程状态如何变化？ 答：

通常，根据进程执行过程中不同时刻的状态，可归纳为三种基本状态：

· 等待态 ：等待某个事件的完成； · 就绪态 ：等待系统分配处理器以便运行； · 运行态 ：占有处理器正在运行。

进程在执行中状态会不断地改变，每个进程在任何时刻总是处于上述三种基本状态的某一种基本状态，进程状态之间转换关系：

运行态→等待态 往往是由于等待外设，等待主存等资源分配或等待人工干预而引起的。 等待态→就绪态 则是等待的条件已满足，只需分配到处理器后就能运行。

运行态→就绪态 不是由于自身原因，而是由外界原因使运行状态的进程让出处理器，这时候就变成就绪态。例如时间片用完，或有更高优先级的进程来抢占处理器等。

就绪态→运行态 系统按某种策略选中就绪队列中的一个进程占用处理器，此时就变成了运行态。

5、进程控制块是什么，有何作用？通常进程控制块包含哪些信息？ 答：

进程控制块(Process Control Block,简称PCB)，是操作系统为进程分配的用于标志进程，记录各进程执行情况的。进程控制块是进程存在的标志，它记录了进程从创建到消亡动态变化的状况，进程队列实际也是进程控制块的链接。操作系统利用进程控制块对进程进行控制和管理。

·标志信息 含唯一的进程名

·说明信息 有进程状态、等待原因、进程程序存放位置和进程数据存放位置 ·现场信息 包括通用、控制和程序状态字寄存器的内容 ·管理信息 存放程序优先数和队列指针 进程控制块的作用有：

2

? (1)记录进程的有关信息，以便操作系统的进程调度程序对进程进行调度。这些信息包括标志信息、说明信息、现场信息和管理信息等；

? (2)标志进程的存在，进程控制块是进程存在的唯一标志

6、什么是可再入程序？ 答：

（1） 什么是 可再入程序 。 一个能被 多个用户同时调用 的程序称做\可再入 \的程序。 （2） 可再入程序的性质。

? ?

可再入程序必须是纯代码，在执行时自身不改变；

一个可再入程序要求调用者提供工作区，以保证程序以同样方式为各用户服务。

编译程序 和 操作系统程序 通常都是\可再入\程序，能同时被不同用户调用而构成不同的进程。

7、阐述进程调度的常用算法：先来先服务、优先数法、轮转法。 答：

?

先来先服务调度算法 该算法按进程进入就绪队列的先后次序选择可以占用处理器的进程。

? 优先数调度算法 对每个进程确定一个优先数，该算法总是让优先数最高的进程先使用处理器。对具有相同优先数的进程，再采用先来先服务的次序分配处理器。系统常以任务的紧迫性和系统效率等因素确定进程的优先数。进程的优先数可以固定的，也可随进程执行过程动态变化。 一个高优先数的进程占用处理器后，系统处理该进程时有两种方法，一是\非抢占式\，另一种是\可抢占式\。前者是此进程占用处理器后一直运行到结束，除非本身主动让出处理器，后者则是严格保证任何时刻总是让优先数最高的进程在处理器上运行。

? 时间片轮转调度法 把规定进程一次使用处理器的最长时间称为\时间片\。时间片轮转调度算法让就绪进程按就绪的先后次序排成队列，每次总选择该队列中第一个进程占用处理器，但规定只能使用一个时间片，如该进程尚未完成，则排入队尾，等待下一个供它使用的时间片。各个进程就这样轮转运行。时间片轮转算法经常用于分时操作系统中。

8、程序状态字包含哪些主要内容? 答：

(1)程序基本状态

3

(2)中断码 (3)中断屏蔽位

9、比较进程调度与作业调度的不同点。 答：

1）作业调度是宏观调度，它决定了哪一个作业能进入主存。进程调度是微观调度，它决定各作业中的哪一个进程占有中央处理机。（或）作业调度是高级调度，它位于操作系统的作业管理层次。进程调度是低级调度，它位于操作系统分层结构的最内层。

（2）作业调度是选符合条件的收容态作业装入内存。进程调度是从就绪态进程中选一个占用处理机。

10、C程序说明系统调用fork()的应用。请在①②③④处填入有关父、子进程的正确语句： ／* Example to demonstrate the function of System Call fork *／ main() {

int i； ① if(i)＞0 {

printf(“②”) ； } else{

printf(“③”) ； }

printf(“④”) ； }

执行本程序时，子进程在标准输出上打印以下结果： It is child process． Exit．

父进程在标准输出上打印以下结果： It is Parent process． Exit．

11、单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：

4

作业 1 2 3 4 5

进入系统时间 8:00 8:20 8:30 9:00 9:10 估计运行时间/分钟 40 30 12 18 5 (1) 如果应用先来先服务的作业调度算法，试将下面表格填写完整。 作业 1 2 3 4 5 进入系统时间 8:00 8:20 8:30 9:00 9:10 估计运行时间/分钟 40 30 12 18 5 作业平均周转时间T= （2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。 作业 1 2 3 4 5 进入系统时间 8:00 8:20 8:30 9:00 9:10 估计运行时间/分钟 40 30 12 18 5 作业平均周转时间T= 答： 1． (1) 作业 1 2

开始时间 结束时间 周转时间/分钟 开始时间 结束时间 周转时间/分钟 进入系统时间 8:00 8:20 估计运行时间/分钟 40 30 5

开始时间 8：00 8：40 结束时间 8：40 9：10 周转时间/分钟 40 50

3 4 5 8:30 9:00 9:10 12 18 5 9：10 9：22 9：40 9：22 9：40 9：45 52 40 35 217 作业平均周转时间T= 43.4 （2） 作业 1 2 3 4 5 进入系统时间 8:00 8:20 8:30 9:00 9:10 估计运行时间/分钟 40 30 12 18 5 开始时间 8：00 8：52 8：40 9：27 9：22 结束时间 8：40 9：22 8：52 9：45 9：27 周转时间/分钟 40 62 22 45 17 186 作业平均周转时间T= 37.2 12、有一个具有两道作业的批处理系统，作业调度采用短作业优先的非抢式调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列中，作业优先数即为进程优先数，优先数越小优先级越高。

作业名 到达时间 估计运行时间 优先数

A 10：00 40分 5 B 10：20 30分 3 C 10：30 50分 4 D 10：50 20分 6 （1）列出所有作业进入内存时间及结束时间。 （2）计算平均周转时间。 答：

每个作业运行将经过两个阶段：作业调度(SJF算法)和进程调度(优先数抢占式)。另外，批处理最多容纳2道作业，更多的作业将在后备队列等待。

时间(分钟) 10:00 10:20 10:30 10:50 11:10 12:00 12:20 A B A C D CPU A D D 进程就绪队列 C 作业后备队列

6

(1) 10:00，作业A到达并投入运行。

(2) 10:20，作业B到达且优先权高于作业A，故作业B投入运行而作业A在就绪队

列等待。

(3) 10:30，作业C到达，因内存中已有两道作业，故作业C进入作业后备队列等待。 (4) 10:50，作业B运行结束，作业D到达，按SJF短作业优先算法，作业D被装入

内存进入就绪队列。而由于作业A的优先级高于作业D，故作业A投入运行。 (5) 11:10，作业A运行结束，作业C被调入内存，且作业C的优先级高于作业D，

故作业C投入运行。

(6) 12:00，作业C运行结束，作业D投入运行。 (7) 12:20，作业D运行结束。

作业 进入内存时间 运行结束时间

A 10:00 11:10

B 10:20 10;50

C 11:10 12:00 D 10:50 12:20

各作业周转时间为：作业A 70，作业B 30，作业C 90，作业D 转时间为70分钟。

7

90。平均作业周 第四章 并发进程的同步与互斥

1、进程间同步和互斥的含义是什么? 答：

同步：并发进程之间存在的相互制约和相互依赖的关系。 互斥：若干进程共享一资源时，任何时刻只允许一个进程使用。 2、用文字描述银行家算法的基本思想？ 答：

银行家算法的基本思想是：将系统中的所有资源比做银行家的资金，每进行 一次资源的分配，银行家都要从当前的资源分配情况出发，计算这种分配方案的 安全性，如果是安全的，则进行分配，否则选择其它可能的分配方案。这样，每 次分配都计算安全性，从而可以避免死锁的发生。 3、简述死锁的防止与死锁的避免的区别。 答：

死锁的防止是系统预先确定一些资源分配策略，进程按规定申请资源，系统按预先规定的策略进行分配，从而防止死锁的发生。

而死锁的避免是当进程提出资源申请时系统测试资源分配，仅当能确保系统安全时才把资源分配给进程，使系统一直处于安全状态之中，从而避免死锁。

4、试说明资源的静态分配策略能防止死锁的原因。 答：

资源静态分配策略要求每个进程在开始执行前申请所需的全部资源，仅在系统为之分配了所需的全部资源后，该进程才开始执行。这样，进程在执行过程中不再申请资源，从而破坏了死锁的四个必要条件之一“占有并等待条件”，从而防止死锁的发生。

5、有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3。回答：

(1)若对资源分配不加限制，会发生什么情况?为什么? (2)为保证进程正确工作，应采用怎样的资源分配策略?为什么? 答：

.(1)可能会发生死锁

8

例如：进程P1，P2和P3分别获得资源S3，S1和S2后再继续申请资源时都要等待(2分)，这是循环等待。

(或进程在等待新源时均不释放已占资源) (2)可有几种答案：

A.采用静态分配 由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。

或B.采用按序分配 不会出现循环等待资源现象。

或C.采用银行家算法 因为在分配时，保证了系统处于安全状态。

６、某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。

(2)根据所定义的信号量，把应执行的PV操作填入适当，以保证进程能够正确地并发执行。

COBEGIN PROCESS PI(I=1，2，……) begin ； 进入售票厅； 购票； 退出； end； COEND

(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。 答：

.(1)定义一信号量S，初始值为20。 意义：

S>0 S的值表示可继续进入售 票厅的人数 S=0 表示售票厅中已有20名顾 客(购票者) S<0 |S|的值为等待进入售票 厅的人数

(2)P(S)

9

进入售票厅；

购票； 退出；

V(S)

(3)S的最大值为20 S的最小值为20－n

注：信号量的符号可不同(如写成t)，但使用时应一致(即上述的s全应改成t)。 ７、假定系统有三个并发进程read, move和print共享缓冲器B1和B2。进程read负责从输入设备上读信息，每读出一个记录后把它存放到缓冲器B1中。进程move从缓冲器B1中取出一记录，加工后存入缓冲器B2。进程print将B2中的记录取出打印输出。缓冲器B1和B2每次只能存放一个记录。要求三个进程协调完成任务，使打印出来的与读入的记录的个数，次序完全一样。

请用PV操作，写出它们的并发程序。 答：

begin SR,SM1,SM2,SP:semaphore; B1,B2:record;

SR:=1;SM1:=0;SM2:=1;SP:=0 cobegin process read X:record;

begin R: (接收来自输入设备上一个记录) X:=接收的一个记录； P(SR)； B1:=X; V(SM1); goto R; end; Process move Y:record; begin

10

答：

当前系统处于安全状态，安全序列如下求解： work = Available = (3 , 3 , 2 )

寻找 Needj <= work = ( 3 , 3 , 2 ) ( j = 0 , 1 , 2 , 3 , 4) j = 1 Need1 = (1 ,2 ,3 ) < = (3 , 3 , 2 ) work : = (3 , 3 , 2 ) + (2 ,0 ,0 ) = (5 , 3 , 2 )

寻找 Needj <= work = ( 5 , 3 , 2 ) ( j = 0 , 2 , 3 , 4) j = 3 Need3 = (0 ,1 ,1 ) < = (5 , 3 , 2 ) work : = (5 , 3 , 2 ) + (2 ,1 ,1 ) = (7 , 4 , 3 ) 寻找 Needj <= work = (7 , 4 , 3 ) ( j = 0 , 2 , 4) j = 4 Need4 = (4 ,3 ,1 ) < = (7 , 4 , 3 ) work : = (7 , 4 , 3 ) + (0 ,0 ,2 ) = (7 , 4 , 5) 寻找 Needj <= work = (7 , 4 , 5) (j = 0 , 2 ) j = 2 Need2 = (6 ,0 ,0 ) < = (7 , 4 , 5 ) work : = (7 , 4 , 5 ) + (3 ,0 ,2 ) = (10 , 4 , 7) 寻找 Needj <= work = (10 , 4 , 7) ( j = 0 ) j = 0 work : = (10 , 4 , 7 ) + (0 ,1 ,0 ) = (10 , 5 , 7) 所以安全序列为＜P1，P3，P4，P2，P0＞。

１５、有一阅览室，读者进入时必须先在一张登记表上登记。该表中每个表项代表阅览室中的一个座位。读者离开时要消掉其登记信息。阅览室共有50个座位。登记表每次仅允许一位读者进行登记或注销。读者登记时，发现登记表满，他在阅览室外等待，直至有空位再登记进入。试用类Pascal语言和P、V操作，描述读者行为。 答：

Begin {initial value of S is 50}

Parbegin Begin {register } P (S) ;

Register and enter into the reading room ; End;

16

Begin {leave off} Register off and leave ; V (S) ; End ; End ;

１６、考虑一个共有150个存储单元的系统，如下分配给三个进程，P1最大需求70,己占有25；P2最大需求60,己占有40；P3最大需求60,己占有45。使用银行家算法，以确定下面的任何一个请求是否安全。(1)P4进程到达，P4最大需求60,最初请求25个。(2)P4进程到达，P4最大需求60,最初请求35。如果安全，找出所有的安全序列；如果不安全，给出结果分配情况。 答：

(1) 由于系统目前还有150-25-40-45=40个单元，P4进程到达，把25个单元分给它。这

时系统还余15个单元，可把15个单元分给P3，它执行完后会释放60个单元。于是可供P1(还要45个单元)，P2(还要20个单元)，P4(还要35个单元)任何一个执行。安全序列为：

P1，P2，P3，P4，P3，P1，P2，P4 P1，P2，P3，P4，P3，P1，P4，P2 P1，P2，P3，P4，P3，P2，P1，P4 P1，P2，P3，P4，P3，P2，P4，P1 P1，P2，P3，P4，P3，P4，P1，P2 P1，P2，P3，P4，P3，P4，P2，P1

(2) P4进程到达，P4最大需求60,最初请求35。如果把35个单元分给P4，系统还余5

个单元，不再能满足任何一个进程的需求，系统进入不安全状态。

１７、在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有二个进程P1和P2，其中P1拣白子；P2拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试写出两进程P1和P2能并发正确执行的程序。 答：

实质上是两个进程的同步问题，设信号量S1和S2分别表示可拣白子和黑子，不失一般性，若令先拣白子。

17

var S1,S2:semaphore;

S1:=1;S2:=0; cobegin {

process P1 begin repeat P(S1); 拣白子 V(S2); until false; end process P2 begin repeat P(S2); 拣黑子 V(S1); until false; end } coend.

１８、系统有A、B、C、D共4种资源，在某时刻进程P0、P1、P2、P3和P4对资源的占有和需求情况如表，试解答下列问题：

Allocation Process A B C D P0 0 0 3 2 A B C D A B C D 0 0 4 4 1 6 2 2 Claim Available 18

P1 P2 P3 P4

1 0 0 0 1 3 5 4 2 7 5 0 3 6 10 10 0 3 3 2 0 9 8 4 0 0 1 4 0 6 6 10 (1) 系统此时处于安全状态吗？为什么？

(2) 若此时P2发出request1(1、2、2、2)，系统能分配资源给它吗？为什么？ 答：

(1)系统处于安全状态，存在安全序列： P0，P3，P4，P1，P2 P0，P3，P1，P4，P2 P0，P3，P1，P2，P4

(2)不能分配，否则系统会处于不安全状态。

１９、假设有32 个存储区域，其编号为0，1，…，31，用一个32 位的标志字，位号也是0，1，…31，分别描述32 个存储区域使用状态：当某一位为1 时，表示对应存储区域已分配，若为0，表示对应存储区域空闲。

get进程： 负责存储区域分配，每次分配一个区域，找出标志字某为0 的位置成1。 put进程： 负责存储区域回收，把回收存储区域标志字对应位清成0。 要求：

(1)分析get 进程与put 进程的具体同步关系。 答：

get进程分配完32.个存储区域后，再执行分配时必须等待put进程回收区域，而put进程无须等待分配进程get;get与put共享32位的标志字，它们必须互斥访问

(2)采用PV 操作同步工具，写出get 进程与put 进程的同步算法(可用流程图描述，但信号量名称、作用、初值必须说明。)

答：mutex是互斥信号量，初值是1，对32位标志字进行保护;

S是标志字的同步信号量，初值为32，表示系统开始时32个区域均空闲，可供分配。

19

第五章

11.

当分配给改作业的物理页框数为3时

使用opt算法，缺页中断数为6，缺页中断率为50% 使用fifo算法，缺页中断数为9，缺页中断率为75%

使用LRO算法，缺页中断数为7，缺页中断率为7/12=58.3% 13.

(1)物理地址=400+430=830 (2)物理地址=1300+200=1500 (3)地址越界 (4)缺段中断 15.

0A5C=0000 1010 0101 1100 1KB=210B

虚拟地址的高六位为页号，低10位为页内地址

页号=000010B=2 ,对应的物理块号为4，页内地址=1001011100B=604 物理地址=4*1024+604=4700

093C=0000 1001 0011 1100 页号为2，对应的物理块为4，页内地址=100111100=316

物理地址=4*1024+316=4412

20

第六章

8

(1) 使用fcfs算法 从143磁道开始 86 57 147 61 91 56 177 86 94 83 150 56 102 48 175 73 130 45 总寻道长度 565

(2) 使用sstf算法 147 4 150 3 130 20 102 28 94 8 91 3 86 5 175 89 177 2

总寻道长度162 (3) 使用扫描算法 147 4 150 3 175 25 177 2 130 47 102 28 94 8 91 3

21

86 5

总寻道长度=125

22

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