操作系统习题 下载本文

1 1 1 2 2 3 × × × (2’) FIFO

1 2 3 1 1 1 2 2 3 × × × (2’) OPT

1 2 3 1 1 1 2 2 3 × × × (2’)

内存块数 3

4 2 3 × 4 2 3 4 1 3 × 5 1 3 × 5 1 6 × 5 2 6 × 1 2 6 × 1 2 6 1 2 3 × 7 2 3 × 7 6 3 × 7 6 3 2 6 3 × 2 1 3 × 2 1 3 2 1 3 2 6 3 ×

4 4 2 3 × 2 4 2 3 1 4 1 3 × 5 4 1 5 × 6 6 1 5 × 2 6 2 5 × 1 6 2 1 × 2 6 2 1 3 3 2 1 × 7 3 7 1 × 6 3 7 6 × 3 3 7 6 2 2 7 6 × 1 2 1 6 × 2 2 1 6 3 2 1 3 × 6 6 1 3 ×

4 1 2 4 × 2 1 2 4 1 1 2 4 5 1 2 5 × 6 1 2 6 × 2 1 2 6 1 1 2 6 2 1 2 6 3 3 2 6 × 7 3 7 6 × 6 3 7 6 3 3 7 6 2 3 2 6 × 1 3 2 1 × 2 3 2 1 3 3 2 1 6 3 2 6 ×

置换算法 FIFO 16

LRU 15 OPT

11 (3’)

2考虑下面存储访问序列,该程序大小为460字:10,11,104,170,73,309,185,245,

246,434,458,364 设页面大小是100字,请给出该访问序列的页面走向。又设该程序基本可用内存是200字,采用FIFO置换算法,求出缺页率。如果采用LRU算法,缺页率是多少?如果采用最优淘汰算法,其缺页率又是多少? 解:

该序列的页面走向为:0、1、0、3、1、2、4、3。 (1’) FIFO 0 1 0 3 1 2 4 3 0 0 0 3 3 3 4 2 1 1 1 1 2 2 3 × × × × × × (2’)

LRU 0 1 0 3 1 2 4 3 0 0 0 0 1 1 4 4 1 1 3 3 2 2 3 × × × × × × × (2’)

OPT 0 1 0 3 1 2 4 3

0 × 0 1 × 0 1 FIFO 6

6/12=0.5

3 1 × 3 1

LRU 7

7/12=0.583

3 2 × 3 4 ×

3 4

(2’)

算法 缺页次数 缺页率 OPT 5

5/12=0.417 (3’)

3设某页系统中,页帧大小为100字。一个程序大小为1200字,可能的访问序列如下: 10,205,110,735,603,50,815,314,432,320,225,80,130,270

系统采用LRU算法。当为其分配4个主存块时,给出该作业驻留的各个页的变化情况及页故障数。 答:

首先将逻辑地址变换成页号。这样10,205,110,735,603,50,815,314,432,320,225,80,130,720,通过除以页的大小100,页号分别为0,2,1,7,6,0,8,3,4,2,0,1,2。(3’)

系统为运行进程分配4个主存块,采用LRU算法,因此可以列表给出进程的缺页情况: 0 2 1 7 6 0 8 3 4 3 2 0 1 2 0 2 1 7 6 0 8 3 4 3 2 0 1 2 0 2 1 7 6 0 8 3 4 3 2 0 1 0 2 1 7 6 0 8 8 4 3 2 0 0 2 1 7 6 0 0 8 4 3 3 F F F F F F F F F S F F F S (5’)

由上表可见,被淘汰的页依次为0,2,1,7,6,0,8,4。缺页次数为12次 (2’)

4某请求页式管理系统,用户编程空间有40个页面,每个页面为200H字节。假定某时刻用户页表中虚页号和物理块号对照表如下: 虚页号 0 2 5 17 20 物理块号 5 20 8 14 36

求虚地址0A3CH、223CH分别对应的物理地址。 答:

虚地址0A3CH转换成十进制数为2620,每个页为200H,即512B,由2620/512可得,页号为5,页内地址为60。查页表可知,其主存块号为8。(3’) 因此地址为2620的物理地址为:8*512+60=4156。(2’)

虚地址223CH转换成十进制数为8762,由8762/512可得,其页号为17,页内地址为58。查页表可知,其主存块号为14。(3’)

因此地址为8762的物理地址为14*512+58=7226。(2’)

5某系统采用页式存储管理策略,拥有逻辑空间32页,每页2KB;拥有物理空间1MB。 1) 写出逻辑地址的格式

2) 若不考虑访问权限位,进程的页表有多少项?每项至少多少位? 3) 如果物理空间减少一半,页表结构应作怎样的改? 答:

1)逻辑空间32页,占5个二进制位。每页2KB,占11位。故描述逻辑空间需要16位(2’)。

15 … 11 10 … 0

逻辑地址的格式:[ | ] (1’)

2)进程的页表有32项,每项的位数由主存的分块数决定(2’)。1MB的空间可划分为512个2KB的块,每个块用9个二进制位表示(2’)。

3)如果物理空间减少一半时,主存地址需要19位表示,仍大于逻辑空间的大小,故页表结构可以不变。(3’)

6有一虚拟存储系统,采用先进先出(FIFO)的页面淘汰算法。在主存忠为每一个作业进程开辟3页。某作业运行中使用的操作数所在的页号依次为:4,3,2,1,4,3,5,4,3,2,1,5。

1) 该作业运行中总共出现多少次缺页?

2) 若每个作业进程在主存拥有4页,又将产生多少次缺页? 3) 如何解释所出现的现象? 解:

先进先出算法的实质是:总是选择作业中在主存驻留时间最长的一页进行淘汰。 若在主存中为每一作业进程开辟3页,对于题中的页面访问过程,其页面调度过程如下所示

4 3 2 1 4 3 5 4 3 2 1 5 页面1 4 4 4 1 1 1 5 5 5 5 5 5 页面2 3 3 3 4 4 4 4 4 2 2 2 页面3 2 2 2 3 3 3 3 3 1 1 缺页中断 F F F F F F F F F (3’) 1) 该作业运行中总共出现9次缺页(1’)

2) 在主存拥有4页,又将产生10次缺页(1’)。其页面调度过程见下图:

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

页面1 4 4 4 4 4 4 5 5 5 5 1 1 页面2 3 3 3 3 3 3 4 4 4 4 5 页面3 2 2 2 2 2 2 3 3 3 3 页面4 1 1 1 1 1 1 2 2 2 缺页中断 F F F F F F F F F F (3’)

3)从这个例子可以看出,当主存中为每一作业进程开辟4页时,出现了缺页次数反而增加的现象。这种现象称为Belady现象。(2’)

7关于存储管理,试问: (1) 在分页、分段和段页式存储管理中,当访问一条指令或数据时,需要访问内存几次?

各做什么处理?

(2) 假设一个分页存储系统具有快表,多数活动页表都可以存在其中,页表放在内存中,

内存访问时间是1us。若快表的命中率是85%,快表的访问时间为0.1us,则有效存取时间为多少?若快表命中率为50%,那么有效存取时间为多少?

解答:(1)分页需要访问2次,第一次访问页表,第二次执行访内操作(2’);分段需要访问2次,第一次访问段表,第二次执行访内操作;段页式需要访问3次,第一次访问段表,第二次访问页表,第三次执行访内操作(2’)。

(2)当快表的命中率为85%时,执行一次访内操作需要的时间: T=1*0.85+2*(1-0.85)=1.15(us) (3’)

当快表的命中率为50%时,执行一次访内操作需要的时间:

T=1*0.5+2*(1-0.5)=1.5(us) (3’)

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

(1)按FIFO调度算法将产生多少次缺页中断,依次淘汰的页号为多少,缺页中断率为多少。 (2)按LRU调度算法将产生多少次缺页中断,依次淘汰的页号为多少,缺页中断率为多少。 答:

页面走向为:1,2,1,0,4,1,3,4,2,1

(1)按FIFO调度算法将产生5次缺页中断;依次淘汰的页号为:0,1,2; 缺页中断率为:5/10=50% (3’) 1 2 1 0 4 1 3 4 2 1 0 0 0 0 0 4 4 4 4 4 4 1 1 1 1 1 1 3 3 3 3 2 2 2 2 2 2 2 2 1 × × × × × (2’)

(2)按LRU调度算法将产生6次缺页中断;依次淘汰的页号为:2,0,1,3; 缺页中断率为:6/10=60% (3’) 1 2 1 0 4 1 3 4 2 1 0 0 0 0 0 0 0 3 3 3 3 1 1 1 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 1 × × × × × × (2’)

9一台计算机含有65536字节的存储空间,这一空间被分成许多长度为4096字节的页。有一个程序,其代码段为32768字节,数据段为16386字节,栈段为15870字节。试问该机器的主存空间适合这个进程吗?如果将每页改成512字节,合适吗? 答:

当存储空间每块为4096B时,共可分成16块。其中: 程序代码段占:32768/4096=8块; (1’) 数据段占:16386/4096=5块; (1’) 栈段占:15870/4096=4块; (1’) 合计为:8+5+4=17块; (1’)

故该机器的主存空间不适合这个作业。 (1’)

当存储空间每块为512B时,共可分成128块。其中: 程序代码段占:32768/512=64块; (1’) 数据段占:16386/512=32块; (1’) 栈段占:15870/512=31块; (1’) 故合计为:64+32+31=127块。 (1’)

故该机器的主存空间是适合这个作业的。 (1’)

10一个请求分页系统中,内存的读/写周期为8纳秒,当配置有快表时,查快表需要1纳秒,内外存之间传送一个页面的平均时间为5000纳秒。假定快表的命中率为75%,页面失效率