操作系统练习题解析 下载本文

程的控制下,将用户要求的数据从输入机通过输入缓冲区送到输入井,CPU需要数据时,直接从输入井读入内存;在输出进程的控制下,把用户要求输出的数据,先从内存送入输出井,待输出设备空闲时,再将输出井的数据经输出缓冲区送到输出设备上。

五、综合题

1.假设一个系统中有五个进程{P1,P2,P3,P4,P5}和三类资源{A,B,C},当前资源分配和请求情况如表:试用银行家算法进行分析:1

①当前状态安全吗?

②当进程P4提出资源请求{1,1,2}后,系统能否满足?

1.解:①存在一个安全序列P3,P2,P1,P4,P5,所以当前状态安全。 P1 P2 P3 P4 P5 P3 P2 P1 P4 P5 work A B C Allocation A B C 2 1 1 3 2 0 1 1 2 0 2 0 0 1 1 2 2 4 3 3 6 6 5 6 8 6 7 8 8 7 Allocation A B C Need A B C 3 0 1 1 3 2 1 1 2 1 4 7 2 5 0 1 1 2 3 2 0 2 1 1 0 2 0 0 1 1 Need A B C Available A B C 2 2 5 1 1 2 1 3 2 3 0 1 1 4 7 2 5 0 3 3 6 6 5 6 8 6 7 8 8 7 8 9 8 true true true true true Work+ Allocation A B C finish A B C ②当进程P4提出资源请求{1,1,2}后 因为(1,1,2)<(1,4,7),请求合理

因为(1,1,2)<(2,2,4),假设满足P4的请求,修改数据结构如下

P1 P2 P3 P4 P5 Allocation A B C 2 1 1 3 2 0 1 1 2 1 3 2 0 1 1 Need A B C 3 0 1 1 3 2 1 1 2 0 3 5 2 5 0 Available A B C 1 1 2 找不出安全序列,所以不能满足P4的请求。

2.有四个作业,它们的提交、运行时间如下表所示,说明采用先来先服务、短作业优先和响应比高者优先调度算法,作业调度顺序各是什么?并计算各种调度算法的平均周转时间和平均带权周转时间。1

作业号 A B C D

提交时间 8.0 8.3 8.5 9.0 运行时间 2.0 0.5 0.1 0.4

2. . 解:先来先服务的作业调度顺序是A、B、C、D, 作业A的周转时间是2,带权周转时间是1; 作业B周转时间是2.2, 带权周转时间是4.4; 作业C周转时间是2.1, 带权周转时间是21; 作业D周转时间是2, 带权周转时间是5;

平均周转时间是2.075,平均带权周转时间是7.85 。

短作业优先的作业调度顺序是A、C、D、B,

作业A的周转时间是2,带权周转时间是1; 作业C周转时间是1.6, 带权周转时间是16; 作业D周转时间是1.5, 带权周转时间是3.75; 作业B周转时间是2.7, 带权周转时间是5.4;

平均周转时间是1.95,平均带权周转时间是6.54 。

高响应比优先的作业调度顺序是A、C、B、D,

作业A的周转时间是2,带权周转时间是1; 作业C周转时间是1.6, 带权周转时间是16; 作业B周转时间是2.3, 带权周转时间是4.6; 作业D周转时间是2, 带权周转时间是5;

平均周转时间是1.975,平均带权周转时间是6.65 。

3. 若在一分页存储管理系统中,某作业共4页,已知页面大小为1024字节,假定某时刻系统为用户

的第0、1、2、3页分配的物理块号为5、6、3、7,试将逻辑地址2365(十进制),3402(十进制),09BA(十六进制),19B9(十六进制)转化为相应的物理地址。1

3.若在一分页存储管理系统中,某作业的页表如下所示。已知页面大小为1024字节,假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、3、7、6试将逻辑地址2148(十进制),3000(十进制),08A7(十六进制),18C6(十六进制)转化为相应的物理地址。

解:2148 的逻辑页号为2,页内偏移为100,故物理地址为7*1024+100=7268 3000的逻辑页号为2,页内偏移为952,故物理地址为7*1024+952=8120

08A7转换为二进制位000010 0010100111,页号为2,对应块号为7,故物理地址为000111 0010100111 即1CA7,同理,18C6页号为6,越界,发生越界中断。

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

(1)先来先服务(按A,B,C,D,E)算法。 (2)优先级调度算法。

(3)时间片轮转算法(每个时间片为2min)。

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

执行次序 A 运行时间 10 优先数 3 等待时间 0 周转时间 10

B C D E 6 2 4 8 5 2 1 4 10 16 18 22 16 18 22 30 根据表中的计算结果,5个进程的平均周转时间T为: T=(10+16+18+22+30)/5=19.2min

(2)采用最高优先级调度(HPF)算法时,5个任务在系统中的执行顺序、完成时间及周转时间如下表所示: 执行次序 B E A C D 运行时间 6 8 10 2 1 优先数 5 4 3 2 1 等待时间 0 6 14 24 26 周转时间 6 14 24 26 27 它们的平均周转时间为: T=(6+14+24+26+27)/5= 19.4min

(3)如果系统采用时间片轮转(RR)算法,令时间片为2分钟,5个任务轮流执行的情况为: 第1轮:(A,B,C,D,E) 第2轮:(A,B,D,E) 第3轮:(A,B,E) 第4轮:(A,E) 第5轮:(A)

显然,5个进程的周转时间为:T1=30min、 T2=22min、 T3=6min、T4=16min、T5=28min。它们的平均周转时间T为:

T=(30+22+6+16+28)/5=20.4min

6.某车站售票厅,任何时刻最多可容纳40名购票者进入,当售票厅中少于40购票者时,则厅外的购票者可立即进入,否则需在外面等待。若把一个购票者看作一个进程,请用wait、signal操作管理这些并发进程时,应怎样定义信号量?写出信号量的初值以及信号量取值的含义。

3.解:设置一个信号量S,表示售票厅里还可以容纳的人数,初值为20。每个购票者的描述如下:

Semaphore S=20; Buyer() {

wait(S); 进入售票厅; 购票;

退出售票厅; signal(S); }

7.假定某页式管理系统,主存为64KB,分成16块,块号为0,1,2,3,4,…,15。设某作业有4页,其页号为0,1,2,3,被分别装入主存的2,4,1,6块。试问:

(1)该作业的总长度是多少字节?

(2)写出该作业每一页在主存中的起始地址。 (3)若有多个逻辑地址[1,120]、[0,40]、[2,5]、[3,70],试计算出相应的内存地址。(方括号内的第一个元素为页号,第二个元素为页内位移)。

解答:

(1)每块的长度为64KB/16=4KB

在页式存储管理系统中,页与块大小相等,因此作业总长度为4KB*4=16KB=16384B。

(2)因为页号为0、1、2、3的页分别装入主存入2、4、1、6块中,所以该作业每一页在主存中的起始地址如下:

第0页在主存中的起始地址:4KB*2=8KB=8192B 第1页在主存中的起始地址:4KB*4=16KB=16384B 第2页在主存中的起始地址:4KB*1=4KB=4096B 第3页在主存中的起始地址:4KB*6=24KB=24576B (3)内存地址=块地址+页内地址,地址变换如下: 逻辑地址[0,100]的内存地址为:4KB*2+100=8292B 逻辑地址[1,50]的内存地址为:4KB*4+50=16434B 逻辑地址[2,0]的内存地址为:4KB*1+0=4096B 逻辑地址[3,60]的内存地址为:4KB*6+60=24636B

8.假定一个盘组共有200个盘面,每个盘面上有16个磁道,每个盘面分成4 个扇区,问: (1)若一个扇区为一个盘块,整个磁盘空间共有多少个盘块? (2)如果用字长为32位的单元来构造位示图,共需要多少个字?

(3)位示图中第19个字的第18位对应的盘块号是多少?(位示图的行列下标、盘块号都从0开始编号)

9.在一个请求分页存储管理系统中,一个作业的页面走向为2、1、3、5、2、4、2、5、3、2、5、2,分配给该作业的物理块为3,初始时为空,计算采用先进先出置换算法、最近最久未使用置换算法的缺页次数。

10.有一个长度为n的有界缓冲区,一组生产者进程生产产品,每生产一件产品,就放到缓冲区的一个空单元格中,一组消费者消费产品,每次在缓冲区中取出一件产品消费。生产者和消费者共享缓冲区,要求:如果缓冲区的产品已经满了,则生产者不能再放,如果缓冲区已经空了,则消费者不能再取。用信号量写出生产者和消费者并发执行的过程

11.某系统有R1、R2和R3共三种资源,在T0时刻P1、P2、P3和P4这4个进程对资源的占有和需求情况见下表,此时系统的可用资源向量为(2,1,2)。

P1 P2 P3 P4

最大资源需求量 R1 R2 R3 3 2 2 6 1 3 3 1 4 4 2 2 已分配资源数量 R1 R2 R3 1 0 0 4 1 1 2 1 1 0 0 2