-操作系统练习题2016

复习题

一、假定在单CPU条件下有下列要执行的作业：

作业 1 2 3 到达时间 0 1 2 运行时间 10 4 3 优先级 2 3 5（高） （1）用一个执行时间图描述在采用非抢占优先级算法时执行这些作业的情况； （2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？

（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少 二、有两个程序，A程序按顺序使用CPU 10S，使用设备甲5S，使用CPU 5S，使用设备

乙10S，最后使用CPU 10S。B程序按顺序使用设备甲10S，使用CPU 10S，使用设备乙5S，使用CPU 5S，使用设备乙10S。在顺序环境下先执行A程序再执行B程序，CPU的利用率是多少？提示：CPU利用率=CPU运行时间/程序运行时间。 三、在单机系统中，系统中各个进程到达就绪队列的时刻、执行时间和优先级如下表所示。

假设进程的调度时间忽略不计。请分别给出采用下面不同的进程调度算法时各个进程的调度次序，画出执行时间图，并计算平均周转时间、平均带权周转时间。

进程 P1 P2 P3 P4 P5 到达就绪队列的时刻 0 2 4 6 8 执行时间（ms） 3 6 4 5 2 优先级 3 5 1（低） 2 4 （1）先来先服务调度算法；

（2）时间片轮换调度算法（时间片为1ms）； （3）抢占式短进程优先调度算法； （4）抢占式优先级调度算法；

（5）非抢占式优先级调度算法。

四、假设在单CPU条件下有下列要执行的作业： 作业 A B C D E 到达时间 0 1 2 3 4 运行时间 10 1 2 1 5 优先级 3 1 3 4（高） 2 （1）用一个执行时间图描述在非抢占优先级算法时，执行这些作业的情况。

（2）用一个执行时间图描述在RR算法时（不考虑优先级），执行这些作业的情

况（时间片为1单位）。

五、设系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算

结果。设每个用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用P、V操作写出这些进程使用打印机的算法。

六、有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源

S1和S2；进程P3需用资源S2和S3。回答：

(1)若对资源分配不加限制，会发生什么情况?为什么? (2)为保证进程正确工作，应采用怎样的资源分配策略?为什么? 七、用信号灯及P、V操作来描述右图 1、说明进程的同步关系：

2、设置信号灯，说明含义、初值。

3、写出程序描述（ 用P、V操作描述 P1、P2、P3）。 主函数如下：

main()

{int s13=0,s23=0; cobegin p1; p2; p3; coend}

八、假定系统中有4个进程P1、P2、P3、P4和3种类型的资源R1、R2、R3，数量分别

为9、3、6，在t0时刻的资源分配情况如表所示。

表 t0时刻的资源分配表

资 进 程 P1 P2 P3 P4 源 Max 况 R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 3 6 3 4 2 1 1 2 2 3 4 2 1 5 2 0 0 1 1 0 0 1 1 2 2 1 1 4 2 0 0 2 2 2 3 0 1 1 2 Allocation Need Available 情 试问：（1）t0时刻是否安全？

（2）P2发出请求向量Request2（1，0，1），系统能否将资源分配给它？ （3）在P2申请资源后，若P1发出请求向量Request1（1，0，1），系统能否

将资源分配给它？

（4）在P2申请资源后，若P3发出请求向量Request3（0，0，1），系统能否

将资源分配给它？

九、试化简图1中的进程——资源图，并利用死锁定理给出相应的理论。

十、试化简图2中的进程——资源图，并利用死锁定理给出相应的理论。

十一、 在银行家算法中，若出现下述资源分配情况：（5个进程，4类资源）

Process A B C D E Allocation 0032 1000 1354 0032 0114 Need 0012 1750 2356 0652 0656 Available 1622 试问： ⑴ 该状态是否安全，说明理由？

⑵ 若进程P2提出请求Request(1，2，2，2)后，系统能否将资源分配给它，

为什么？

十二、 考虑某一系统，它有四类资源R1，R2，R3，R4，有五个并发进程P0，P1，P2，

P3，P4。请按照银行家算法解答下列问题：

（1） 各进程的最大资源请求和已分配的资源矩阵如表所示，计算各进程仍需要请

求的资源向量组成的矩阵。

（2） 系统当前是处于安全状态吗？

（3） 当进程P2申请的资源分别为（0，1，0，0）时，系统能立即满足吗？ Max Allocation Need Available 进程 R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 P0 0 P1 2 P2 6 P3 4 P4 0 0 7 6 3 6 1 5 5 5 5 2 0 6 6 2 0 2 0 2 0 0 0 0 3 3 1 0 3 5 3 1 0 4 4 2 2 1 0 1

十三、 某虚拟存储器的用户编程空间有若干个页面，每页为1KB，内存为16MB。假定某

时刻已将一页面调入内存，该页逻辑地址为4062B,已知页表寄存器中页表始址为2004B，页表长度为8，此时刻内存部分数据如下表，求该页的物理地址，并指出该物理地址中的数据。

内存地址 2000B 2001B 2003B 2004B 2005B 2006B 2007B 2008B 数据 1535 652 71 211 45 3 1 57

内存地址 数据 2011B 2012B 2013B 2014B 2015B 2016B 2017B 2018B 78 599 111 3478 24 78 962 7758 2009B 2010B 5 486

2019B 2020B 75 85 十四、 若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设

每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。

（1）先来先服务（FCFS） （2）最短寻找时间优先调度（SSTF） （3）电梯调度法（SCAN） （4）单向扫描（循环扫描C－SCAN） 十五、 考虑下述页面走向：

1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为3时，试问FIFO、LRU这两种置换算法的缺页次数各是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）

十六、 某移动臂磁盘的柱面由外向里顺序编号，假定当前磁头停在100号柱面且移动臂

方向是向里的，现有如下表所示的请求序列在等待访问磁盘： 表 访问磁盘请求序列 请求次序 柱面号 1 190 2 10 3 160 4 80 5 90 6 125 7 30 8 20 9 140 10 25 回答下面的问题：

① 写出分别采用“最短查找时间优先算法”和“电梯调度算法”时，实际处理上述请求的次序。

② 针对本题比较上述两种算法，就移动臂所花的时间（忽略移动臂改向时间）而言，哪种算法更合适？简要说明之。

十七、 有一个系统其内存容量为1024KB，有8个作业同时到达，各作业需要的内存量

和运行时间如表所示。 作业编号 需要内存量（KB） 运行时间（S） A 140 3 B 80 1 C 100 3 D 60 2 E 50 1 F 30 3 G 15 2 H 20 3 假定系统初启时，将内存1024KB按作业的编号顺序分给各道作业，并假定是多CPU下，分配到内存的作业都可以立即运行。试问： （1） 1S后，内存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？ （2） 2S后，其内存空白区按上述两种算法如何链接？

（3） 在（2）后，此时有一个作业I要求进入内存，它需要内存量为12KB，按上述

两种算法，将把哪一块空白区分给它？

十八、 某计算机系统的内存容量为128KB，对存储器采用可变分区的存储管理办法，现

有3个作业(J1，J2，J3)在内存，其存储器的分配如图所示。 操作系统 J1 空闲区 J2 空闲区 J3 空闲区 0K 5K 20K 40K 50K 90K 100K 128K

(1)现有一个需要25KB存储空间的作业J4请求装入内存，若采用最先适应分配算法

来给J4分配空间。请给出装入J4后的内存分配表。

(2)若采用最优适应算法来给J4分配空间，给出装入J4后的内存分配表。

(3)在只有J1，J2，J3三个作业的情况下，J2运行结束撤离后，请给出J2撤离后的内

存分配表。

十九、 某程序在逻辑地址100处有一条取数指令LOAD l，500，而500单元内存放数据

51888。假设程序被分配到内存起始地址5000单元时，试用图示意，采用下述各种方式下的该指令及数据地址的物理地址及相应地址的变换过程。 (1)静态重定位。

(2)采用重定位寄存器实现动态重定位。

(3)采用页表映像(映射)方式，假定页面大小为100单元，其负表各页映射到50，51、

52，53，54，55，?，59物理页上。

二十、 对于如下的页面访问序列： 1，2，3，4，1，2，5，1，2，3，4，5。当内存块

数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少（画出详细过程）？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断） 二十一、 给定下面的段表，已知下面的逻辑地址(其中方括号中的第一个元素为段号，

第二个元素为段内地址)求其对应的物理地址：

(1)[0,430]；(2)[3,400]；(3) [l,10]； (4) [2,500]； (5) [4,42]；(6) [1,11]。

段号 0 1 2 3 4 段长 600 14 100 580 96 段首地址 219 2300 90 1327 1954 二十二、 某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假

定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

页号 0 1 物理块号 3 7 页号 2 3 物理块号 11 8 则逻辑地址0A5C（H）所对应的物理地址是什么？要求：写出主要计算过程。 二十三、 某磁盘组有6片盘片，每片有两个记录面，存储区域内径为22cm，外径为

33cm，道存储密度为40道/cm，内层位存储密度为400b/cm，转速为3000r/min（转/分），问共有多少柱面？盘组总存储量为多少？平均等待时间为多少？

二十四、 假设有一个磁盘组共有100个柱面，每个柱面上有8个磁道，每个盘面被分

成8个扇区。现有一个含有6400逻辑记录的文件，逻辑记录的大小与扇区一致，该文件以顺序结构的形式被存储到磁盘上。柱面、磁道、扇区的编号从“0”开始，逻辑记录的编号也从“0”开始。文件信息从0柱面、0磁道、0扇区开始存放，试问： （1） 该文件的第3680个逻辑记录应该存放在什么位置？

（2） 第78柱面的第6磁道的第6扇区中存放了该文件的第几个逻辑记录？

二十五、 假设一个可移动磁头的磁盘具有200个磁道，其编号为0～199，当它刚刚结

束了125道的存取后，现正在处理143道的服务请求，假设系统当前I/O请求序列以FIFO顺序排列如下：86，147，91，177，94，150，102，175，130。试问对以下几

种磁盘I/O请求调度算法而言，满足以上请求序列，磁头将分别如何移动，请列出磁道访问次序，并计算出移动距离？ （1）先来先服务（FCFS） （2）最短寻找时间优先调度（SSTF） （3）电梯调度法（SCAN） （4）单向扫描（循环扫描C－SCAN）

二十六、 有一移动臂磁盘，共100个磁道，每个磁道分8个扇区，磁盘转速为500r/s

（转/秒），磁头每移动一个磁道需要10ms，有一个用户请求访问第25磁道第3扇区，并立即被系统响应，假设磁头当时处于15道上，磁头到达第25道时正处于1扇区的开始位置，试计算该用户至少需要等待多长时间？ 二十七、 假定磁盘转速为6000r/min（转/分），磁盘格式化时每个盘面被分为9个扇区，

现有一个文件共有 A，B，C，D，E，F，G，H，I九个逻辑记录要存放在同一磁道上供处理程序使用，假设每个记录的大小与扇区的大小相同，处理程序每次从磁盘读出一个记录后要花2.5ms处理时间。若忽略其他辅助时间，请回答下列问题： （3） 现在假设已经顺序存放好这9个记录，那么读出该文件需要多少时间？

（4） 为了使读出文件需要的时间最短，请重新调整各个记录的存放位置，画出各

个记录的存放位置，计算该文件的读出时间，并与（1）进行比较说明。

二十八、 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20

名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

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

（2 ）在下列横线中填入所定义的信号量，并把应执行的PV操作填入横线中，以保证进程能够正确地并发执行。 main()

{ int ； ； 进入售票厅； 购票； 退出； ；

｝

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

二十九、 设有三个人，M，Q，R，其中M负责采购原材料并放到房间A中，Q从房

间A中取出原材料并加工成产品后，放到房间B中，R从房间B中取出产品并销售（房间A和B都恰好能放一件原材料）。试用P、V操作描述 M，Q，R三人实现上述工作的控制流程。

(1)在下列横线中写出该定义的信号量及其初值。

(2)根据所定义的信号量，把应执行的PV操作填入下列横线中，以保证进程能够正确地并发执行。 main（ ） {

int ， ， ， ； cobegin /*下列进程将并发执行*/ M（ ）； Q（ ）； R（ ）；

coend } M（ ） Q（ ） { { 采购原材料； ； ； 从房间A中取原材料； 将原材料放到房间A中； ； ； 加工成产品； } ； R（ ）

{ 将产品放到房间B中； ； ； 从房间B中取原材料； }

； 销售；

}

三十、 四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F，

但限制是进程A和进程C不能同时读文件F，进程B和进程D也不能同时读文件F，为了使这四个进程并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题：

（1）在下列程序中填入应定义的信号量及初值。

（2）在下列程序中填上适当的P、V操作，以保证它们能正确并发工作：

main（ ） { int ； cobegin /*下列进程将并发执行*/ A（ ）； B（ ）； C（ ）； D（ ）； coend } A（ ） { ； read F； ；} C（ ） { ； read F； ；} B（ ） { ； read F； ；} D（ ） { ； read F； ；}

三十一、 桌上有一只盘子，每次只能放一只水果，爸爸专向盘子中放苹果，妈妈专向

盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用P—V操作实现他们这间的同步机制。

三十二、 有5批处理作业（A,B,C,D,E）几乎同时到达，估计运行的时间分别为2，4，

6，8，10分钟，它们的优先级数分别为1，2，3，4，5（1为最低优先数）。对下面的每种调度算法，分别计算作业的平均周转时间：

1、优先级算法；2、时间片轮转法（时间片为2分钟）；3、FCFS（作业到达顺序为C,D,B,E,A）;4、短作业优先

三十三、 假定某计算机系统配置的主存容量为1GB，当采用页式虚拟存储管理时提供

给用户使用的逻辑地址空间为4GB，页面大小为4KB。访问主存的时间为200ns，访问高速缓存的时间为40ns，查快表的命中率为90％，试问： (1)画出该系统的逻辑地址空间结构示意图； (2)用户作业最多可以有多少页? (3)主存空间一共被划分成多少块?

(4)计算按相对地址转换成绝对地址进行存取的平均时间是多少?

三十四、 假设一个磁盘组有100个柱面(编号为0～99)，每个柱面有32个磁道(又称盘

面，编号为0～31)，每个盘面有16个扇区(编号为0～15)。每个盘面使用一个读写磁头。现采用位示图方法管理磁盘空间，其字号位号均从0开始递增编号。令磁盘块号按柱面顺序和盘面顺序编排。请回答下述问题： (1)若采用32位的字组成位示图，共需要多少个字？

(2)计算第40字的第18位对应的柱面号、磁头号和扇区。 (3) 若从位示图中查找到第50个字的第16位对应的位是“0”，那么其对应的空闲块应在哪个柱面上？应对应哪个扇区？应当那个磁头来完成信息的传送？

三十五、

三十六、

三十七、

进程A和进程B共享某个资源。它们并发执行的程序如下： begin

busy ∶ Boolean； busy ∶= true; cobegin process A

begin

L∶if busy then begin

使用资源； busy∶=false； end；

goto L； end： process B

begin

K∶ if not busy then begin

使用资源； busy ∶ =true； end；

goto K; end； coend；

end：

回答下面问题：

(1)进程A和进程B按什么规律在使用资源？

(2)若程序中不使用布尔变量busy，而改用PV操作来管理，则应采用同步方式还是互斥方式？

(3)在保持原来的资源使用规律情况下，把上述程序改用PV操作来管理。

三十八、 某文件以顺序结构形式存放在磁盘上。该文件有9个等长逻辑记录，每个逻

辑记录的长度为250个字节。文件在磁盘上的起始块号为99，而一个磁盘块长度为512个字节，系统缓冲区数据长度也为512个字节。要求： (1)采用记录成组方式存放该文件信息时，块因子为多少最合适？ (2)该文件至少要占用磁盘块的数目；

(3)若把文件的第6个逻辑记录读入用户区20000单元开始的区域，写出主要过程。

三十九、 在一个多道批处理系统中，供用户使用的主存空间有100K，主存采用可变

分区管理，并且已装入主存的作业不被移动。今有如下表所示仅作计算的作业序列，

假设作业调度和进程调度均采用计算时间短的作业优先调度算法，当第一个作业进入输入井后就开始调度，并忽略系统开销的时间。 要求：

(1)写出作业调度的次序； (2)计算各作业的周转时间； (3)计算平均作业周转时间。 入输井需计算主存 作业 时间 时间 要求 1 2 3 4 5

四十、 假定某计算机系统配置的主存容量为1GB，当采用页式虚拟存储管理时提供给用

户使用的逻辑地址空间为4GB，页面大小为4KB。访问主存的时间为200ns，访问高速缓存的时间为40ns，查快表的命中率为90％，试问： (1)画出该系统的逻辑地址空间结构示意图； (2)用户作业最多可以有多少页? (3)主存空间一共被划分成多少块?

(4)计算按相对地址转换成绝对地址进行存取的平均时间是多少?

四十一、 假定某文件现有10个逻辑记录，每个逻辑记录的大小为150个字节。一个

磁盘块长度为512个字节，逻辑记录不跨块存放。系统缓冲区的长度也为512个字节，系统空间足够使用。在打开该文件时，要分别实现两种操作，在文件的末端增加一条记录(变成11个记录)以及删除文件末端记录(变成9个记录)，请回答： (1)该文件占有几个磁盘块?

(2)分别计算对顺序、链接和索引三种存储结构各需启动I／O操作的最少次数并填写下表。 存储结构 顺序结构 链接结构 索引结构 文件末端增加一条记录 删除文件末端记录 进入主 存时间 开始 时间 完成 时间 周转 时间 9.0时 9.2时 9.3时 9.5时 9.6时 0.5小时 0.4小时 0.3小时 0.2小时 0.1小时 15K 60K 40K 10K 15K

四十二、 有一个程序要将100×100的整型数组的初值置为对角线元素为“1”，其它

元素为“0”。采用页式虚拟存储管理方法，其页面大小为200个整型数组元素，数组中的元素按行编址存放。假定只有两个主存块可用来存放数组信息，初始状态为空。将数组初始化的程序分别如下： （A程序）int a[100][100]；

int i，j；

for(j=0；j<=99；j++) for(i=0；i<=99；i++) { if i==j a[i][j]=1 else a[i][j]=0；} ??

(B程序) int a[100][100];

int i,j;

for(i=0；i<=99；i++) for(j=0；j<=99；j++) { if i==j a[i][j]=1

else a[i][j]=0；} ??

试问：(1)整个数组占用多少页面？

(2)采用FIFO算法进行页面调度，上述两个程序执行时，各产生多少次缺页中断？

四十三、 假定某文件FILEI以链接结构形式存放在磁盘上，共有7个逻辑记录，每个

逻辑记录的大小为150个字节。而一个磁盘块长度为512个字节，系统缓冲区的长度也为512个字节。 试问：

(1)为了提高磁盘空间利用率，应采用何种技术存放文件FILE1(约定一个逻辑记录不能跨越存储在多个磁盘块中)?

(2)画出文件FILE1在盘上的结构示意图，包括文件目录的最基本信息(文件在磁盘上的起始盘块号为50，文件占用的其它磁盘块号可自定)。

(3)若文件FILE1已打开，根据画出的文件结构示意图，将文件FILE1的第6号逻辑记录(逻辑记录从l开始编号)读到主存90000开始的区域，请写出主要工作步骤。

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