操作系统应用题

1.一个由3个页面(页号为0、1、2)，每页有2048个字节组成的程序，假定在某时刻调入8个物理块的内存，其页面的页号和物理块号的对照表如下：

逻辑页号 0 1 2 主存块号 4 7 1 请根据页表，计算下列给出的逻辑地址对应的绝对地址。 (1)100 (2)2617 (3)5196 2. 假定在单CPU条件下有下列要执行的作业：

作业 1 2 3

作业到来的时间是按作业编号顺序进行的（即后面的作业依次比前一个作业迟到一个时间单位）

（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。

（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是

运行时间 10 4 3 优先级 2 3 5 多少？

（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？

答：（1）作业1，作业3，作业2

1 3 2

1 11 14 18 （2）作业1：10 作业2：16 作业3：11 平均周转时间：（10＋16＋11）/3＝37/3 （3）作业1：1 作业2：4 作业3：11/3 平均带权周转时间：26/9

3. 某操作系统为可抢占的系统，该系统的进程调度状态如图所示，请说明：

（1）什么事件引起每次显著的状态变迁？

答：1（运行—就绪）：中断 2（就绪—运行）：进程调度 3（运行—阻塞）：等待I/O完成或某事件的发生 4（阻塞—就绪）： I/O已经完成或某事件已经发生

（2）下述状态变迁因果关系能否发生？为什么？ A、2->1 B、3->2 C、4->2

答：A:能。因为是可抢占的系统，当发生了可抢占的因素，会剥夺当前进程的运行，转为就绪。 B:能。 C:不能。 4. 根据如下段表： 段号 0 1 2 3

（1）求出逻辑地址0,200的物理地址并将其合法性填入段表的适当位置

答：段号0对应的基址是300，因此所访问的物理地址是500。合法 （2）求出逻辑地址2,1000的物理地址并将其合法性填入段表的适当位置

答：段号2对应的基址是3000，因此所访问的物理地址是4000。合法

5. 有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。

基地址 300 7500 3000 2000 长度 合法（0）/非法（1） 200 0 0 1010 100 (1)试说明A、B两进程之间存在什么样的制约关系？

(2)为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。

6. 设 input进程不断向缓冲区Q写入信息，output进程不断地将刚由input进程写入的信息读出。试问：

（1）这两个进程有何相互制约关系？

（2）试用P、V操作写出这两个进程完成这项任务的代码段和信号量的含义及初值。 7. 根据如下段表： 段号 基地址 长度 合法（0）/非法（1） 0 300 200 1 7500 0 2 3000 1010 3 2000 100 （1） 求出逻辑地址为0，100的物理地址并将其的合法性填入上表适

当位置； 400;合法

(2)求出逻辑地址为3，100的物理地址并将其的合法性填入上表适当位置； 2100；合法

8. 在请求分页系统中，某用户的编程空间为16个页面，每页1K，分配的内存空间为8K。假定某时刻该用户的页表如下图所示，试问： （1）逻辑地址084B（H）对应的物理地址是多少？（用十六进制表示） 084B(H)=

（2）逻辑地址5000（十进制）对应的物理地址是多少？（用十进制表示）

（3）当该用户进程欲访问24A0H单元时，会出现什么现象？ 页号 块号

0 3 1 7 2 4 3 1 4 12 5 9 6 61 7 20 9. 有一个虚拟存储系统。分配给某进程3页内存，开始时内存为空，页面访问序列如下：

6、5、4、3、2、1、5、1、5、2、1、2、1、2、1、6、5 （1） 若采用先进先出的页面置换算法（FIFO），缺页次数为多少？

（2） 若采用最近最少使用的页面置换算法（LRU），缺页次数为多少？

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

作进入系统时估计运行时间/业 间 分钟 1 8:00 40 2 8:20 30 3 8:30 12 4 9:00 18 5 9:10 5

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

（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。

作进入系统时估计运行时间/开始时结束时周转时间/分业 间 分钟 间 间 钟 1 8:00 40 2 8:20 30 3 8:30 12 4 9:00 18 5 9:10 5 作业平均周转时间T= 11. 设有三个批作业JOB1、JOB2、JOB3，其到达时间、处理时间及完成时间如下：

作业 作业到达时间（时） 开始处理时间（时） 处理完成时间（时）

JOB1 15 18 22

JOB2 18 21 23

JOB3 17 19 21

试计算：

（1）各个作业的周转时间； （2）所有作业的平均周转时间；

12. 某移动臂磁盘的柱面由外向里顺序编号，假定当前磁头停在100号柱面且移动臂方向是向里的，现有如下表1所示的请求序列在等待访问磁盘：

表1 访问磁盘请求序列 请求次序 1 2 3 4 5 6 7 8 9 10 柱面号 190 10 160 80 90 125 30 20 140 25 回答下面的问题：

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

② 针对本题比较上述两种算法，就移动臂所花的时间（忽略移动臂改向时间）而言，哪种算法更合适？简要说明之。（考研） 13.假定 系统中有4个进程P1、P2、P3、P4和3类资源R1、R2、R3（资源数量分别为9、3、6），在t0时刻的资源分配情况如下表所示。

资 源 Max Allocation need available 进程 R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 2 2 2 1 1 2 P2 6 1 3 5 1 1 1 0 2 P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 4 2 0 试问： （1）t0时刻是否安全？ （2）P2发出请求向量request2（1,0,1），系统能否将资源分配给它？（3）在P2申请资源后，若P1发出请求向量request1（1,0,1），系统能否将资源分配给它？（4）在P1申请资源后，若P3发出请求向量request3（0,0,1），系统能否将资源分配给它？ 答案：（1）在t0时刻存在一个安全序列{P2，P1，P3，P4}，故系统是安全的。 （2） 可以找到一个安全序列{ P2，P1，P3，P4}，故系统是安全的，

可以将P2所申请的资源分配给它。 （3） P1阻塞。 （4） 分配将被撤销，进程P3阻塞

14.有4个进程P1、P2、P3、P4，它们进入系统的时刻和要求的运行

时间如下表所示： 进程 进入时刻 要求运行时间 P1 0.000 3 P2 1.001 6 P3 4.001 4 P4 6.001 2 （1） 画图分别说明，系统采用先来先服务和时间片轮转（（时间片=2）

调度算法时，它们的执行情况。 （2） 分别计算上述两种情况下进程的平均周转时间。

答案：（1）FCFS：按它们进入系统的先后次序执行； 时间片轮转：ABABCDBC （2）FCFS：平均周转时间：（（3-0）+（9-1.001）+（13-4.001）+（15-6.001））/4=7.25

时间片轮转：（（5-0）+（13-1.001）+（15-4.001）+（11-6.001））/4=8.25 15.采用可变分区方式管理主存空间时，若主存中按地址顺序依次有5个大小分别为15KB、28KB、10KB、226KB和110KB的空闲区。现在有5个作业Ja、Jb、Jc、Jd和Je，它们所需的主存依次为10KB、15KB、102KB、26KB和180KB。请问：

（1）如果采用首次适应算法能把这5个作业按Ja~Je的次序全部装入主存吗？P87

（2）用什么分配算法装入这5个作业可使主存的利用率最高？ 答案：

（1）不能。

（2）用最佳适应算法。

16.某采用请求分页存储管理的系统为装入主存的一个进程建立了如下所示的页表（采用十进制） 页号 20 22 200 150 30 50 状态位 1 0 1 1 0 0 如果页面大小是2000B，那么，下面那个虚地址的访问会引起缺页中断？不会引起缺页中断的虚地址将转换成什么物理地址？ （1）10451 （2） 21 答案： （1） 会引起缺页中断；（2）不会。物理地址为：401421 17.在采用请求分页存储管理的系统中，一作业的页面走向为1、2、3、

4、3、1、5、4、6、2、1、2、5、7、3、2、4，假定分配给该作业的物理块数为4，开始时4个物理块全部为空。试计算用LRU调度算法时，访问过程中发生的缺页次数和页面置换次数，写出依次应淘汰的页面号。 答案： 序1 2 3 4 3 1 5 4 6 2 1 2 5 7 3 2 4 列 栈 1 2 3 4 3 1 5 4 6 2 1 2 5 7 3 2 4 1 2 3 4 3 1 5 4 6 2 1 2 5 7 3 2 1 2 2 4 3 1 5 4 6 6 1 2 5 7 3 1 1 2 4 3 1 5 4 4 6 1 2 5 7 缺√ √ √ √ √ √ √ √ √ √ √ √ 页 置 √ √ √ √ √ √ √ √ 换 依次应淘汰的页面号为：2、3、1、5、4、6、1、5 18.某计算机系统进行依次内存访问的时间是1us，它采用分页存储系统管理内存，使用块表和页表进行地址转换。若页表常驻内存，快表的命中率为85%，则有效存取时间是多少？

答案：有效存取时间为：0.85×1+（1-0.85）×（1+1）=1.15（us） 19.假定某系统采用可变分区管理技术，某时刻在内存中有3个大小分别为35KB、25KB、50KB的空闲块，它们的起始地址依次递增。请构造一个内存请求序列，使得首次适应分配算法能满足该请求序列，而最佳适应分配算法则不能。要求对构造出的序列满足分配算法的情况进行简单的文字说明或图示。 答案：

内存请求序列为：5KB、35KB、30KB|、25KB。设这是4个作业J1、J2、J3、J4的内存请求，则系统采用两种分配法的分配过程如下： （1） P267

20.一个进程已分配到4个内存块，如下表所示。 页号 内存块号 装入时间 最近访问访问位 修改位 时间 2 0 60 161 0 1 1 1 130 160 0 0 0 2 26 162 1 0 3 3 20 163 1 1 当进程访问自己地址空间中的4号页面时产生缺页中断。请分别用FIFO、LRU、NRU算法，决定缺页中断服务程序选择换出的页面。 答案：

（1）FIFO：页面3最早被装入3号内存块，所以先换出。 （2）LRU： P267

21.假定一个磁盘有200个柱面，编号为0~199，在完成了对125柱面的请求后，当前正在143号柱面处为一个请求服务。请求队列中还有若干个请求者在等待服务，假设他们依次要访问的柱面号为：86,147,91,177,94,150,102,175,130。请分别计算SSTF、SCAN和CSCAN算法时实际服务的次序和磁臂移动的距离，并求平均寻道长度。 答案：

SSTF：143 147 150 130 102 94 91 86 175 177 磁头移动总量：162

SCAN：143 147 150 175 177 130 102 94 91 86 磁头移动总量：125 CSCAN：

22.假定磁盘的磁臂现位于6号柱面上，下表列出6个请求者等待访问磁盘，试列出最省时间的响应次序。 序号 1 2 3 4 5 6 柱面号 7 5 15 7 20 5 磁道号 6 5 20 4 9 15 块号 2 6 6 4 5 2 答案：现进行移臂调度，要求移臂时间短；再进行旋转调度，要求旋转周数最少。

最省时间的响应次序为：6-2-1-4-3-5

23.设某文件为链接文件，由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为512B，并依次存放在50、121、75、80、63号磁盘块上。若要存取文件的第1569逻辑字节处地信息，问要访问哪一个磁盘块？ 答案：

因为1569=512×3+33，所以要访问字节的逻辑记录号为3，对应的物理磁盘块号为80.故应访问第80号磁盘块。

24.某磁盘共有500000个块，当前有200000个空闲块，每个地址占16位，若用位示图实现该磁盘的空闲块表，则共需要多少个二进制位？ 答案：

500000个。

25. （6分）在一个请求分页系统中，假如系统分配给一个作业的物理块数为3，

此作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5。试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页次数。

26.（6分）假设对磁盘的请求串为95，180，35，120，10，122，75，68。并且磁头的位置刚刚由70移动到80。试给出用SCAN算法调度时磁头的移动轨迹并计算平均寻道长度。

27、（6分）在公共汽车上，司机和售票员的活动如下：

司机： 售票员： 启动车辆 上乘客 正常行驶 关车门 到站停车 售票 开车门 下乘客 （1）、说明这两个活动的同步关系？ （2）、用信号量和P、V操作实现他们的同步关系。 28、（8分）设系统中有三类资源（A，B，C）和5个进程（P1，P2，P3，P4，P5），A资源的数量为17，B资源的数量为5，C资源的数量为20，T0时刻的系统状态见下表

进程 最大资源需求量 已分配资源数量 A B C A B C P1 5 5 9 2 1 2 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4

（1） T0时刻是否为安全状态？若是，请给出安全序列？ （2） 在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分

配，为什么

（3） 在（2）的基础上，若进程P4请求资源（2，0，1），是否能实

施资源分配，为什么？

在（3）的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配，为什么？

答案：

1．答：首先根据逻辑地址查页表，得到主存的块号，再根据公式绝对地址=块号×块长+页内地址进行计算。 （1）100的页号为0（100/2048=2），页内地址为100mod2048=100；查表得主存块号为4，于是绝对地址=4×2048+100=8292； （2）2617的页号为1（2617/2048=1），页内地址为2617mod2048=569；查表得主存块号为7，于是绝对地址=7×2048+569=14905； （3）5196的页号为2（5196/2048=2），页内地址为5196mod2048=1100；查表得主存块号为1，于是绝对地址=1×2048+1100=3148； （注：mod为取模运算，即求余数）

5.（1）A和B两个进程存在着因共享资源（共享打印机）而产生的间接制约关系。 （2）