操作系统习题及复习资料四.docx

资源描述

操作系统习题及复习资料四.docx

《操作系统习题及复习资料四.docx》由会员分享，可在线阅读，更多相关《操作系统习题及复习资料四.docx（17页珍藏版）》请在冰点文库上搜索。

操作系统习题及复习资料四.docx

操作系统习题及复习资料四

四、计算题

1、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。

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

页号

物理块号

则逻辑地址0A5C（H）所对应的物理地址是什么？

要求：

写出主要计算过程。

1．解：

页式存储管理的逻辑地址分为两部分：

页号和页内地址。

由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。

由“内存为16KB”，可知有16块，块号为4位。

逻辑地址0A5C（H）所对应的二进制表示形式是：

000101001011100，根据上面的分析，下划线部分为页内地址，编码“00010”为页号，表示该逻辑地址对应的页号为2。

查页表，得到物理块号是11（十进制），即物理块地址为：

1011，拼接块内地址1001011100，得10111001011100，即2E5C（H）。

2、对于如下的页面访问序列：

1，2，3，4，1，2，5，1，2，3，4，5

当内存块数量为3时，试问：

使用FIFO、LRU置换算法产生的缺页中断是多少？

写出依次产生缺页中断后应淘汰的页。

（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。

要求写出计算步骤。

）

2．解：

采用先进先出（FIFO）调度算法，页面调度过程如下：

页面次序

主存

页面

情况

共产生缺页中断9次。

依次淘汰的页是1、2、3、4、1、2。

采用最近最少使用（LRU）调度算法，页面调度过程如下：

页面次序

主存

页面

情况

共产生缺页中断10次。

依次淘汰的页是1、2、3、4、5、1、2。

3、下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。

现有以下作业序列：

96K、20K、200K。

若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么?

空闲分区表

3．解：

若采用最佳适应算法，在申请96K存储区时，选中的是5号分区，5号分区大小

与申请空间大d,-致，应从空闲分区表中删去该表项；接着申请20K时，选中1号分区，分配后1号分区还剩下12K；最后申请200K，选中4号分区，分配后剩下18K。

显然采用最佳适应算法进行内存分配，可以满足该作业序列的需求。

为作业序列分配了内存空间后，空闲分区表如表5-3（a）所示。

若采用首次适应算法，在申请96K存储区时，选中的是4号分区，进行分配后4号分

区还剩下122K；接着申请20K，选中1号分区，分配后剩下12K；最后申请200K，现有

的五个分区都无法满足要求，该作业等待。

显然采用首次适应算法进行内存分配，无法满

足该作业序列的需求。

这时的空闲分区表如表5．3（b）所示。

分配后的空闲分区表

（a）

（b）

4、某采用段式存储管理的系统为装入主存的一个作业建立下表所示的段表．

段表

段号

段长

主存起始地址

660

2219

140

3300

100

580

1237

960

1959

回答下列问题：

（1）计算该作业访问[0,432],[l,10],[2,500]时（方括号中第一元素为段号，第二元素为段内地址）的绝对地址．

（2）总结段式存储管理的地址转换过程．

4．答：

（1）[0,432]→（432<660）2219+432=2651

[1，10]→（10<140）3300+10=3310

[2，500]→（因500>100所以地址越界，产生中断）

（2）总结段式存储管理的地址转换过程如下：

①从逻辑地址中取出段号和段内地址。

②根据段号，从段表中取出该段在主存中的始址和段长。

③比较段内地址和段长，如段内地址≤段长，则继续下一步，否则产生越界中段，程序中断（非法操作）。

④计算本段始址+段内地址，得到绝对地址。

1.假设一个系统中有5个进程,它们的到达时间和服务时间如表1所示,忽略I/0以及其他开销时间,若分别按先来先服务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRF）、时间片轮转（RR,时间片=1）调度算法进行CPU调度,请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。

表1进程到达和需服务时间

进程

到达时间

服务时间

分析：

进程调度的关键是理解和掌握调度所采用的算法。

FCFS算法选择最早进入就绪队列的进程投入执行;SPF算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新就绪的进程运行时间比正在执行的进程的剩余运行时间短,则新进程将抢占CPU;HRRF算法选择响应比最高的进程投入执行;RR算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间片。

答：

各进程的完成时间、周转时间和带权周转时间（如表2所示）

表2进程的完成时间和周转时间

进程

平均

FCFS

完成时间

周转时间

带权周转时间

1.00

1.17

2.25

2.40

6.00

8.6

2.56

SPF（非抢占）

完成时间

周转时间

带权周转时间

1.00

1.17

2.75

2.80

1.5

7.6

1.84

SPF（抢占）

完成时间

周转时间

带权周转时间

1.00

2.16

1.00

2.80

1.00

7.2

1.59

HRRF

完成时间

周转时间

带权周转时间

1.00

1.17

2.25

2.80

3.5

2.14

RR（q=1）

完成时间

周转时间

带权周转时间

1.33

2.67

3.25

2.8

3.5

10.8

2.71

3.在银行家算法中，若出现下述资源分配情况：

进程

Allocation

Need

Available

A B C D

0 0 3 2

1 0 0 0

1 3 5 4

0 3 3 2

0 0 1 4

0 0 1 2

1 7 5 0

2 3 5 6

0 6 5 2

0 6 5 6

1 6 2 2

试问:

（1）该状态是否安全?

（2）如果进程P2提出请求Request（0,2,2,2〉后,系统能否将资源分配给它?

解:

（1）利用银行家算法对此时刻的资源分配情况进行分析,可得此时刻的安全性分析情况。

进程

Work

Need

Allocation

Work+Allocation

Finish

A B C D

1 6 2 2

1 6 5 4

1 9 8 6

1 9 9 10

2 9 9 10

0 0 1 2

0 6 5 2

0 6 5 6

1 7 5 0

2 3 5 6

0 0 3 2

0 3 3 2

0 0 1 4

1 0 0 0

1 3 5 4

1 6 5 4

1 9 8 6

1 9 9 10

2 9 9 10

3 12 14 14

true

从上述分析中可以看出，此时存在一个安全序列{P0,P3,P4,P1,P2},故该状态是安全的。

（2）P2提出请求Request2（1,2,2,2）,按银行家算法进行检查：

Request2（1,2,2,2）≤Need2（2,3,5,6）

Request2（1,2,2,2）≤Available（1,6,2,2）

试分配并修改相应数据结构，资源分配情况如下：

进程

Allocation

Need

Available

A B C D

0 0 3 2

1 0 0 0

2 5 7 6

0 3 3 2

0 0 1 4

0 0 1 2

1 7 5 0

1 1 3 4

0 6 5 2

0 6 5 6

0 4 0 0

再利用安全性算法检查系统是否安全,可用资源Available（0,4,0,0）已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能将资源分配给P2。

3某请求分页系统，用户空间为32KB，每个页面1KB，主存16KB。

某用户程序有7页长，某时刻该用户进程的页表如下：

页号

物理块号

是否在TLB

是

否

是

（1）计算两个逻辑地址：

0AC5H、1AC5H对应的物理地址。

（2）已知主存的一次存取为1.5us，对于TLB表（快表）的查询时间可以忽略，则访问上述两个逻辑地址共耗费多少时间？

答

（1）每页1kb代表页内偏移量为低地址10位，剩余的为页号，所以0AC5H对应的页号为2，物理块为4，说以物理地址为12C5H,同理可得1AC5H对应的物理地址为0AC5H.

（2）耗时为1×1.5us+2×1.5us=4.5us

4什么叫重定位？

它有哪两种方式？

这两种方式有什么区别？

由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改（变换），则程序必将无法执行。

为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。

5在具有快表的段页式存储管理方式中，如何实现地址变换？

答：

物理地址=该段在主存的起始地址+页框号*大小+页内地址。

第二次作业：

1、在某请求分页管理系统中，一个作业共5页，作业执行时一次访问如下页面：

1，4，3，1，2，5，1，4，2，1，4，5，若分配给该作业的主存块数为3，分别采用FIFO，LRU，Clock页面置换算法，试求出缺页中断的次数及缺页率。

答FIFO缺页次数为9，缺页率为3/4

LRU缺页数为9，缺页率为3/4

Clock缺页数为9，缺页率为3/4

2、某请求分页管理系统，假设进程的页表如下：

页号

页框号

有效位

装入时间

101H

—

254H

页面大小为4KB，一次内存的访问时间为100纳秒（ns），一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为100毫秒（已含更新TLB和页表的时间），进程的驻留集大小固定为2个页框，采用FIFO法置换页面。

假设1）TLB初始为空；2）地址转换时，先访问TLB，若TLB未命中时再访问页表（忽略TLB更新时间）；3）有效位为0表示页面不在内存中。

请问：

（1）该系统中，一次访存的时间下限和上限各是多少？

（给出计算过程）

（2）若已经先后访问过0、2号页面，则虚地址1565H的物理地址是多少？

（给出计算过程）

答

（1）一次访存时间下限10ns+100ns+100ns，上限10ns+100ns+100ms+100ns

（2）基于上述访问序列，当访问虚地址1565H时产生缺页中断，合法驻留集为2，必须从表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。

由此可得1565H的物理地址为101565H

3、设某计算机的逻辑地址空间和物理地址空间均为128KB，按字节编址。

若某进程最多需要6页数据存储空间，页面大小为1KB，操作系统采用固定分配局部置换策略为该进程分配4个页框（物理块）。

在时刻300前该进程各页面的访问情况如下表所示：

页号

页框号（块号）

装入时间

访问位

130

230

200

180

当进程执行到时刻300时，要访问逻辑地址为17CAH的数据，请回答下列问题：

（1）该逻辑地址对应的页号是多少？

（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？

要求给出计算过程。

（3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？

要求给出计算过程。

设搜索下一页的指针顺时针方向移动，且当前指向2号页框，示意图如下：

17CAH=（0001 0111 1100 1010）2

（1）页大小为1K，则页内偏移地址为10位，前6位是页号，所以逻辑地址对应的页号为：

（2）FIFO：

被置换的页面所在页框为7，所以对应的物理地址为（0001 1111 1100 1010）2=1FCAH

（3）CLOCK：

被置换的页面所在页框为2，所以对应的物理地址为（0000 1011 1100 1010）2=0BCAH

并有一下请求序列等待访问磁盘：

请求序列：

1，2，3，4，5，6，7，8，9

预访问柱面号：

150，50，178，167，87，43，23，160，85

试用最短寻找时间优先算法和电梯调度算法，分别排出实际处理上述请求的次序

第一题：

序列（柱面号）

最短寻找时间优先算法

9（85）、5（87）、2（50）、6（43）、7（23）、1（150）、8（160）、4（167）、3（178）

电梯调度算法

9（85）、5（87）、1（150）、8（160）、4（167）、3（178）、2（50）、6（43）、7（23）

第二题：

磁盘有199个磁道，当前磁头在54#磁道上，并向磁道号减小的方向上移动，现有一下请求序列等待访问磁盘：

请求序列12345678

带访问的柱面号9918438123151256668

试用最短寻找时间优先算法和电梯调度算法，分别排出实际处理上述请求的次序，并计算出他们的平均寻道长度

第二题：

序列（柱面号）

最短寻找时间优先算法

7（66）8（68）3（38）5（15）1（99）4（123）6（125）2（184）

12+2+30+23+84+24+2+59=236

平均寻道长度236/8=29.5

电梯调度算法

3（38）5（15）7（66）8（68）1（99）4（123）6（125）2（184）

16+23+51+2+31+24+2+59=208

平均寻道长度208/8=26

四、计算题

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

作业

运行时间

优先级

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

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

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

平均周转时间是多少？

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

平均带权周转时间是多少？

1．解：

（1）非抢占式优先级算法（3分）

作业1作业3作业2

||||t

0101317

（2）和（3）

作业

到达时间

运行时间

完成时间

周转时间

带权周转时间

1.0

4.0

3.7

平均周转时间

12.3

平均带权周转时间

2.9

2、若后备作业队列中等待运行的同时有三个作业J1、J2、J3，已知它们各自的运行

时间为a、b、c，且满足a

作业周转时间。

2．证明：

采用短作业优先算法调度时，三个作业的总周转时间为：

T1=a+（a+b）+（a+b+c）=3a+2b+c①

若不按短作业优先算法调度，不失一般性，设调度次序为：

J2、J1、J3。

则三个作业的

总周转时间为：

T2=b+（b+a）+（b+a+c）=3b+2a+c②

令②一①式得到：

T2-Tl=b-a>0

可见，采用短作业优先算法调度才能获得最小平均作业周转时间。

3、若有如表所示四个作业进入系统，分别计算在FCFS、SJF和HRRF算法下的平均

周转时间与带权平均周转时间。

作业

提交时间（时）

估计运行时间（分）

120

3．答：

作业

FCFS

SJF

HRRF

开始完成周转

时间时间时间

开始完成周转

时间时间时间

开始完成周转

时间时间时间

0010:

00120

10:

0010:

50120

10:

5011:

00120

11:

0011:

2090

0010:

00120

10:

3011:

20150

10:

0010:

1070

10:

1010:

3040

0010:

00120

10:

1011:

00130

10:

0010:

1070

11:

0011:

2090

平均周

转时间

T=112.5

T=95

T=102.5

带权平均周转时间

W=4.975

W=3.25

W=3.775

4、有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提交和估计运

行时间由下表给出：

作业

提交时间

估计运行时间（分钟）

系统采用剩余SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被剩余时间更短作业抢占。

（1）分别给出6个作业的执行时间序列、即开始执行时间、作业完成时间、作业周转时间。

（2）计算平均作业周转时间。

4．答：

作业号

提交时间

需运行

时间

开始运行时间

被抢占还需运行时间

完成时间

周转时间

10:

155

说明：

（1）J2到达时抢占J1；J3到达时抢占J2。

（2）但J4到达时，因不满足SJF，故J4不能被运行，J3继续执行5分钟。

（3）由于是4道的作业系统，故后面作业不能进入主存而在后备队列等待，直到有作业结束

（4）根据进程调度可抢占原则，J3第一个做完。

而这时J5、J6均己进入后备队列，而J5可进入主存。

（5）因J5最短，故它第二个完成。

这时J6方可进入主存。

因J6最短，故它第三个完成。

（6）然后是：

J4、J2和J1

（7）T=（155+95+20+55+15+20）/6=60

展开阅读全文