操作系统复习习题

1.若一只盘子一次只能放一个水果，A只往盘中放苹果，B只往盘中放梨子，C只从盘中取苹果，D只从盘中取梨子。试用：(1) 信号量和P、V操作；(2) 管程，写出同步算法。 解：(1) 采用P、V操作的同步算法如下：

semaphore SAB=1; //A、B的资源信号量，同时又是它们的互斥信号量 semaphore SC=0; //C的资源信号量(用于与A同步) semaphore SD=0; //D的资源信号量(用于与B同步) begin

parbegin

process A: //进程A的算法描述 {

while(true) {

取一个苹果；

wait(SAB); //测试盘子是否为空 将一苹果放入盘中；

signal(SC) //通知C盘中已有苹果(可能唤醒C) }

}

process C: {

while(true) {

wait(SC); //测试盘子是否有苹果 从盘中取出苹果;

signal(SAB); //通知A(或B)盘子一空(可能唤醒A或B) 消费该苹果; } }

process B: //进程B的算法描述 {

while(true) {

取一个梨子；

wait(SAB); //测试盘子是否为空 将一梨子放入盘中；

signal(SD) //通知D盘中已有梨子(可能唤醒D) }

}

process D: {

while(true) {

wait(SD); //测试盘子是否有梨子 从盘中取出梨子;

signal(SAB); //通知A(或B)盘子一空(可能唤醒A或B) 消费该梨子; } }

.

.

parend end

(2) 采用管程的同步算法如下：

首先定义管程MPC，该管程可描述如下： type MPC=monitor

var flag: integer; //flag=0:盘中无水果；=1盘中有苹果；=2盘中有梨子 empty: condition; //用于A或B等待空盘子 W: array[1..2] of condition //W[1]用于等待苹果，W[2]用于等待梨子 procedure entry put(integer k) begin

if flag>0 then empty.wait; //生产者A或B进程阻塞 flag=k;

放一k号水果入盘中; //设1号水果为苹果，2号水果为梨子 if W[k].queue then full.signal; //若有等待k号水果者，则唤醒之

end

procedure entry get(integer k) begin

if flag<>k then W[k].wait; 从盘中取k号水果; flag := 0;

//消费者C或D进程阻塞

if empty.queue then empty.signal; //若等待队列非空，则唤醒队首的一个生产者进程 end begin

flag :=0; //初始化内部数据 end

A、B、C、D四个进程的同步算法可描述如下： parbegin Process A begin 任取一个苹果; MPC.put(1); end

Process B begin

任取一个梨子; MPC.put(2); end

Process C begin

MPC.get(1); 吃苹果; end

Process D

.

.

begin

MPC.get(2); 吃梨子; end parend

2.设自行车生产车间有两个货架，货架A可以存放8个车架，货架B可以存放20个车轮；又设有4个工人，他们的活动是重复劳动，分别为：工人1 加工一个车架放入货架A中；工人2、3分别加工车轮放入货架B中（每人每次放入1个车轮）；工人4从货架A中取一个车架，再从货架B中取两个车轮，组装成一辆自行车。试用PV操作实现四个工人的合作。

【分析】信号量Aempty表示货架A的空位数，其初值为8；信号量Afull表示货架A上存放

的车架数，其初值为0；信号量Bempty表示货架B的空位数，其初值为20；信号量Bfull表示货架B上存放的车轮数，其初值为0；信号量mutex用于互斥（初值为1）。

解：BEGIN

semaphore Aempty，Bempty，Afull，Bfull，mutex；

Aempty ：= 8；Bempty ：= 20；Afull ：= 0；Bfull ：= 0；mutex ：=1； PARBEGIN

Worker1：BEGIN

L1：生产1个车架；

P（Aempty）； //测试货架A是否有空位置 P（mutex）； //互斥使用货架A 车架放到货架A； V（Afull）； //货架A上的车架数增1，必要时唤醒等待的进程

V（mutex）； goto L1； END

Worker2、3：BEGIN

L2：生产1个车轮；

P（Bempty）； //测试货架B是否有空位置 P（mutex）； //互斥使用货架B 车轮放到货架B； V（Bfull）； //货架B上的车轮数增1，必要时唤醒等待的进程 V（mutex）； goto L2； END

Worker4：BEGIN

L3：P（Afull）； //测试货架A上是否有车架

P（Bfull）；P（Bfull）； //测试货架B上是否有2个车轮 P（mutex）；

取1个车架；取2个车轮； V（Aempty）； //货架A空位置增1 V（Bempty）；V（Bempty）；//货架B空位置增2 V（mutex）；

.

.

组装成一辆自行车； goto L3； END PAREND END

3.有两个作业A和B，分别在7:00和8:30到达系统，它们估计的计算时间分别为0.8小时和0.1小时，系统在9:00开始以响应比高者优先算法进行调度。在单道系统中该两个作业被选中时的响应比各为多少？

解：9:00时，作业A的响应比=1+2/0.8=3.5

作业B的响应比=1+0.5/0.1=6

所以9:00时作业调度程序选中作业B

9:06作业B结束，调度作业A，此时作业A的响应比=1+2.1/0.8=3.625

综上可知，在单道系统中A、B两个作业被选中时的响应比分别为3.625和6

4.有一个具有两道作业的批处理系统（最多可有两道作业同时装入内存执行），作业调度采用计算时间短的作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法，今有如下作业序列，作业优先数即为进程优先数，优先数越小优先级越高：

作业名 J1 J2 J3 J4 到达时间 10 : 10 10 : 20 10 : 30 10 : 50 估计运行时间 20分钟 30分钟 25分钟 20分钟 优先数 5 3 4 6 列出所有作业进入内存时间及结束时间。 （1） 计算平均周转时间。

解：先作必要的分析（可在草稿纸上完成，分析过程不计分）：

10：10 J1被调入，开始运行

10：20 J2进入内存，因优先级高，开始运行

J1运行了10分钟，还剩10分钟，因优先级低，运行态变就绪态 10：30 J1继续就绪

J2运行了10分钟，还剩20分钟 J3到达，但不能被调入 10：50 J2运行结束，J4到达

调入短作业J4，但因J4优先级比J1低，J1开始继续运行 11：00 J1运行结束

J3被调入，因优先级高，开始运行 J4因优先级低，仍就绪 11：25 J3运行结束，J4开始运行 11：45 J4运行结束

（1）各个作业进入主存时间、结束时间和周转时间如下表所示：（6分）

作业名 J1 J2 J3 提交时间 10：10 10：20 10：30 进入时间 10：10 10：20 11：00 结束时间 11：00 10：50 11：25 周转时间 50 30 55 .

.

J4 10：50 10：50 11：45 55 （2） 平均周转时间：（50+30+55+55）/4=47.5（min）

5.有一个多道程序设计系统，采用不可移动的可变分区方式管理主存空间，设主存空间为100K，采用最先适应分配算法分配主存，作业调度采用响应比高者优先算法，进程调度采用时间片轮转算法（即内存中的作业均分CPU时间），今有如下作业序列：

作业名 J1 J2 J3 J4 J5 提交时间 10 : 00 10 : 15 10 : 30 10 : 35 10 : 40 需要执行时间 40分钟 30分钟 20分钟 25分钟 15分钟 要求主存量 25K 60K 50K 18K 20K 假定所有作业都是计算型作业且忽略系统调度时间。回答下列问题： (1) 列表说明各个作业被装入主存的时间、完成时间和周转时间； (2) 写出各作业被调入主存的顺序； (3) 计算5个作业的平均周转时间。

解：先作必要的分析（可在草稿纸上完成，分析过程不计分）： 10：00 J1到达，被调入内存并开始运行，内存剩75KB 10：15 J2到达，被调入内存并开始与J1一起运行。J1运行了15分钟，还需执行25分

钟。内存剩15KB

10：30 J3到达，因内存不能满足，不被调入。J1、J2继续运行。 10：35 J4到达，因内存不能满足，不被调入。此时J1相当于已运行了15+10=25分钟，

还需执行15分钟；J2相当于已运行了10分钟，还需执行20分钟。

10：40 J5到达，因内存不能满足，不被调入。J1、J2继续运行。 11：05 J1运行结束，J2还需执行5分钟。内存中的2个空闲分区分别是25K和15K，能

满足J4或J5需求，但不能满足J3的需要。J4的响应比=1+30/25 =2.2；J5的响应比=1+25/15=2.67，J5被调入内存并与J2一起运行，内存中的空闲分区大小是5KB和15K。

11：15 J2运行结束，内存中的空闲分区是65KB和15K。J3 的响应比=1+45/20=3.25，J4

的响应比=1+40/25=2.6，J3被调入内存与J5一起运行。内存中的空闲分区大小是15KB和15K。J3需执行20分钟，J5还需执行10分钟。

11：35 J5运行结束，J4调入内存运行。J3还需执行10分钟，J4还需执行25分钟。 11：55 J3运行结束 12：10 J4运行结束 答：（1）各个作业被装入主存的时间、完成时间和周转时间如下表所示：

作业名 J1 J2 J3 J4 J5 装入主存时间 10：00 10：15 11：15 11：35 11：05 作业完成时间 11：05 11：15 11：55 12：10 11：35 周转时间 65 60 85 95 55 （2）作业被调入主存的顺序为J1，J2，J5，J3，J4。

.

.

（3）平均周转时间=（65+60+85+95+55）/5=72（分钟）。

（3） (北京大学1997年试题)某系统有A,B,C三类资源（数量分别为17，5，20）和P1~P5

五个进程，在T0时刻系统状态如下表所示：

进程 P1 P2 P3 P4 P5 最大资源需求量 A B C 5 5 4 4 4 5 3 0 2 2 9 6 11 5 4 已分配资源数量 A B C 2 4 4 2 3 1 0 0 0 1 2 2 5 4 4 系统采用银行家算法实施死锁避免策略,请回答下列问题： ①T0时刻是否为安全状态？若是，请给出安全序列。 ②在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？ ③在②的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？ 解：① 由已知条件可得尚需矩阵Need和可用资源向量Avalable如下：

Need Avalable A B C A B C P1 3 4 7 2 3 3 P2 1 3 4 P3 0 0 6 P4 2 2 1 P5 1 1 0

利用银行家算法对此时刻的资源分配情况进行分析如下表：

进程 P4 P2 P3 P5 P1 Work 2 3 3 4 3 7 8 3 9 12 3 14 15 4 18 Need 2 2 1 1 3 4 0 0 6 1 1 0 3 4 7 Allocation 2 0 4 4 0 2 4 0 5 3 1 4 2 1 2 Work+Allocation Finish 4 3 7 8 3 9 12 3 14 15 4 18 17 5 20 true true true true true 从上述分析可知，存在一个安全序列P4，P2，P3，P5，P1，故T0时刻系统是否安全的。 ② 在T0时刻若进程P2请求资源(0，3，4)，不能实施资源分配。因为当前C类资源剩余3个而P2请求4个，客观条件无法满足它的请求，因此不能实施资源分配，P2阻塞。

③ 在②的基础上，若进程P4请求资源（2，0，1），可以实施资源分配。因为由①可知，P4是安全序列中的第一个进程，只要P4的请求量没有超出它的尚需量，系统满足它的请求后仍处于安全状态，即仍然存在安全序列P4，P2，P3，P5，P1。

6.有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10，6，2，4，8min。其优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算器平均进程周转时间（进程切换开销不考虑）。

(1) 先来先服务(按A,B,C,D,E顺序)算法；

.

.

(2) 优先级调度算法；

(3) 时间片轮转算法(设时间片为1min——原题无此假设)。

解：(1) 采用先来先服务算法时，5个任务在系统中的执行顺序、完成时间及周转时间如下表所示。

执行顺序 预计运行时间 开始执行时间 完成时间 周转时间 A B C D E 10 6 2 4 8 0 10 16 18 22 10 16 18 22 30 10 16 18 22 30 5个进程的平均周转时间为：(10+16+18+22+30)/5=19.2 (min)

(2) 采用最高优先级调度算法时，5个任务在系统中的执行顺序、完成时间及周转时间如下表所示。

执行顺序 预计运行时间 优先数 开始执行时间 完成时间 周转时间 B E A C D 6 8 10 2 4 5 4 3 2 1 0 6 14 24 26 6 14 24 26 30 6 14 24 26 30 5个进程的平均周转时间为：(6+14+24+26+30)/5=20 (min)

(1) 采用时间片轮转调度算法时，可以认为5个进程均分CPU时间，它们在系统中的执行

情况如下：

第一轮：A，B，C，D，E （5min）

第二轮：A，B，C(C完成，即C的周转时间为8min)，D，E （5min） 第三轮：A，B，D，E （4min）

第四轮：A，B，D(D完成，即D的周转时间为17min)，E （4min） 第五轮：A，B，E （3min）

第六轮：A，B(B完成，即B的周转时间为23min)，E （3min） 第七轮：A，E （2min）

第八轮：A，E(E完成，即E的周转时间为28min) （2min） 第九轮：A （1min）

第十轮：A(A完成，即A的周转时间为30min) （1min）

所以，5个进程的平均周转时间为：(8+17+23+28+30)/5=21.2 (min)

7.页式存储管理中，主存空间按页分配，可用一张“位示图”构成主存分配表。假设主存容量为2M字节，页面长度为512字节，若用字长为32位的字作主存分配的“位示图”需要多少个字？如页号从1开始，字号和字内位号（从高位到低位）均从0开始，试问：第2999页对应于何字何位；99字19位又对应于第几页？ 解：(1) 内存总块数=2MB/512B=4096

位示图需要字数=4096/32=128 (2) 字号=(2999-1)/32=93

.

.

位号=(2999-1)%32=22

即第2999内存页对应于位示图中93字的22位。 (3) 99*32+19+1=3188

即位示图99字19位对应于内存的3188页

8.某操作系统采用可变分区分配存储管理方法，用户区为512K且始址为0，用空闲分区表管理空闲分区。若分配时采用分配空闲低地址部分的方案，其初始时用户区的512K空间空闲，对下述申请序列：申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K；回答下列问题：

（1）采用首次适应算法，空闲分区中有哪些空闲块（给出始址，大小）？ （2）采用最佳适应算法，空闲分区中有哪些空闲块（给出始址，大小）？ 答：(1) 序号 始址 大小 1 150K 30KB 2 280K 20KB 3 400K 112KB

(2) 序号 始址 大小

1 210K 90KB

2 400K 30KB

3 470K 42KB

9．一个32位地址的计算机系统使用二级页表，虚地址分为10位顶级页表，10位二级页表，

其余是页内偏移。试问：(1) 页面长度是多少？(2) 虚拟地址空间有多少个页面？

10.在采用页式存储管理的系统中，某作业的逻辑地址空间为4页（每页2048字节），且已知该作业的页表如下表。试借助地址转换图（即要求画出页式存储管理系统地址转换示意图）求出逻辑地址4688所对应的物理地址。

页 表 页 号 0 1 2 3 解：逻辑地址4688所在的页号和页内偏移分别为：

页号P=4688/2048=2

页内偏移W=4688%2048=592

内存块号 2 4 6 9 .

.

页表寄存器 页表始址 页表长度 > • 越界中断 逻辑地址 页号P=2 页内偏移W=592 + 页号 块号b 0 1 2 3 2 4 6 9 页表 物理地址

从上述地址转换图可知，进行地址转换的步骤如下： （1） 由虚地址计算出页号和页内偏移量； （2） 根据页号和进程的页表首址，查页表，找到对应的页表项，取出帧号(内存块号)； （3） 帧号*页面大小+页内偏移形成物理地址。即62048+592=12880

11.在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题： （此图类似地4题）

（1）按FIFO调度算法将产生的缺页中断次数、依次淘汰的页号和缺页中断率各为多少？

（2）按LRU调度算法将产生的缺页中断次数、依次淘汰的页号和缺页中断率各为多少？ 答：由题目的已知条件，可得页面走向为： 1, 2, 1, 0, 4, 1, 3, 4, 2, 1

(1) FIFO的页面置换图如下：

页面走向 1 2 1 0 4 1 3 4 2 1 0 页帧 是否缺页 被淘汰页号

1 √ 0 1 2 √ 0 1 2 0 1 2 4 1 2 √ 0 4 1 2 4 3 2 √ 1 4 3 2 4 3 2 4 3 1 √ 2 b W 物理地址=62048+592 =12880 按FIFO调度算法将产生5次缺页中断，依次淘汰的页号为0,1,2，缺页中断率为5/10=50%。 (2) LRU算法的页面置换图如下：

页面走向 1 2 1 0 4 1 3 4 2 1

1 页面队列 是否缺页 被淘汰页号

.

2 1 0 √ 1 2 0 0 1 2 4 0 1 √ 2 1 4 0 3 1 4 √ 0 4 3 1 2 4 3 √ 1 1 2 4 √ 3 0 √ .

按LRU调度算法将产生6次缺页中断，依次淘汰的页号为2,0,1,3，缺页中断率为6/10=60%。

12.某系统对主存采用页式管理，供用户使用的主存区域共0K字节，被分成160块，块号为0，1，…，159。现有一作业的地址空间共占4页，其页号为0, 1, 2, 3，被分配到主存的第2，4，1，5块中。请回答：

(1) 作业每一页的长度为多少字节？

(2) 写出该作业被装入主存时，其对应的页表。

(3) 把该作业的每一页在主存中的起始地址(用16进制表示)填在下表中：

页号 0 1 2 3 起始地址 解：(1) 作业每一页的长度为4K字节

(2) 该作业被装入主存时，其对应的页表为

逻辑页号 0 1 2 3 主存块号 2 4 1 5 (3) 该作业的每一页在主存中的起始地址(用16进制表示)如下表所示。

页号 0 1 2 3

起始地址 2000H 4000H 1000H 5000H .