发布时间 : 星期五 文章操作系统-第5章练习题更新完毕开始阅读
0. 分页管理，访问虚拟页序列是7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1， 分配到3个物理页
面， 画出不同页面置换算法结果，得出缺页率。
(1) 先进先出FIFO (2) 最近最久未使用页面置换算法LRU (3) 理想型淘汰算法OPT （1）FIFO，缺页15次， 所以缺页率15/20 1 2 3 1 2 3 1 2 3 7 7 7 7 7 7 0 7 0 0 7 0 0 7 0 1 7 0 1 1 7 0 1 1 7 0 1 2 2 0 1 2 2 0 1 2 2 0 1 0 0 0 3 2 3 1 3 2 0 3 3 2 0 3 0 2 3 0 0 0 4 4 3 0 4 4 0 3 4 2 4 3 2 4 2 0 2 4 0 2 2 3 4 2 3 3 4 3 2 3 0 0 2 3 0 0 3 2 0 2 0 3 3 3 3 2 2 2 1 0 1 3 1 1 3 2 1 2 0 1 2 0 1 2 2 2 0 0 1 0 2 0 1 1 1 7 7 1 2 7 1 0 7 7 7 0 1 0 7 0 2 0 0 1 7 0 1 1 1 （2）LRU, 缺页12次， 所以缺页率12/20 （3）OPT，缺页9次， 所以缺页率9/20
1． 主存容量55MB，依次分配15MB，分配30MB，释放15MB，分配8MB，分配6MB， (1) 采用最佳适应算法，最终最大的空闲区大小是多少 (2) 采用最先适应算法，最终最大的空闲区大小是多少 (3) 采用最坏适应算法，最终最大的空闲区大小是多少
(1) 9MB (2)10MB (3)7MB
2． 逻辑地址18位， 11-17位表示页号，0-10位表示页内偏移（页内地址），一个作业依次
装入2、3、7号物理页中，问（1）虚拟内存多大，有多少个虚拟页，每页多大（2）逻辑地址2500对应的物理地址？
（1） 虚存2^18字节，有2^7个页，每页2^11字节 （2） 由题知，虚页号0,1,2分别对应物理页2,3,7
2500/2048=1余452， 对应物理页号为3，页内偏移为452
3． 采用2级页表，页面大小2^10字节，逻辑地址空间大小为2^16页，页目录表中每个表
项大小为2字节，则页目录表中至少包含多少个表项？
答：一共有2^16个页面，即 页目录表项数量*下一级页表项数量=2^16个， 页目录中项数最少的时候也就是下级页表项数最多的时候。 下级页表最多有2^10/2=2^9项， 所以页目录表至少有2^16/2^9=2^7项。
4． 读写一次物理内存需要1us，若快表命中率85%，问访问一次内存需要多少时间？
1*0.85+2*0.15=1.15us
5． 地址空间2^64字节，采用多级分页存储管理，页面大小4KB，每个页面项占8字节，
问至少采用多少级页表 答：每页最多可存4096/8=512(2^9)项，共有2^64/4096=2^52页， (2^9)^X>=2^52, 解得X=6
6．段表如下： 段号 0 1 2 3 4 段长 600 128 100 580 96 段起始地址 256 2300 113 1326 1952 问(0，430)，（2，88），（4，112）对应的物理地址？
答：分别是256+430=686，113+88=201，地址越界（112>96）
6． 分页管理系统，某作业有4个页面，分别装入3、4、6、8物理块，页面大小1024字节，
假设有一条指令mov 2100, 3100，指出源操作数和目标操作数的物理地址。假设虚拟地址是5000，求物理地址。
3100/1024=3余28，逻辑页3对应物理页8，因此物理地址是8*1024+28 2100/1024=2余52，逻辑页2对应物理页6，因此物理地址是6*1024+52 5000/1024=4余XXX，逻辑页只有0-3页，因此地址越界。
7． 设主存容量1MB，外存容量400MB，计算机的地址线是32位，问虚存地址空间最大为
多大？
答：虚存地址空间只与地址线位数有关，因此大小为2^32字节。但其中最多只有401MB能映射到外存及内存(虚存中可以有大片地址不实际映射)。
8． 某计算机系统，逻辑空间与地址空间均为64KB，按字节编址，页大小是1KB，某进程
需要6页存储空间，操作系统分配4个页框（指物理页），某时刻对应关系如下： 页号 0 1 2 3 页框号 7 4 2 9 装入时刻 130 230 200 160 此刻执行到260时刻，要访问逻辑地址为17CAH， 采用先进先出置换，问17CAH将对应的物理地址？
17CAH=0001 0111 1100 1010，页号占6位，页内地址占10位, 所以逻辑页号是5，页内地址是后10位 (也可以除以1024取商和余数)。5号逻辑页要对应最早使用的7号物理页(先进先出，5号逻辑页替换掉0号逻辑页), 因此物理地址为0001 1111 1100 1010 (即物理页号替换逻辑页号，得到物理地址)
9． 在请求分页系统中，访问内存时间为100ns，缺页中断时间是25ms，如果希望程序在缺
页情况下执行时间与不缺页情况下相比延长不超过10%，问缺页率f不得超过多少？ 答：没提快表，所以页表都在内存中获得，所以不缺页情况下访问一次内存需要2*100=200ns 缺页情况下要求平均不超过200*110%=220ns.
(1-f) 200+f(100+t1+100)<=220 其中缺页中断时间t1=25000000ns。解得f<=0.00008% 涉及到内存有效访问时间EAT的问题，要代入到求EAT的公式中
即EAT=a(&+t)+(1-a)[(1-f)(&+t+&+t)+f(&+t+t1+&+t)] 其中a为快表命中率，f为缺页率，&为一次读或更新快表时间，t为访问一次内存时间，t1为一次缺页中断时间
10．分页系统，快表命中率70%，一次内存存取时间为1ns，缺页时要发生置换，如果无页面修改标记，一个缺页中断要8000ns，有修改标记的，一个缺页中断要20000ns，两种情况各占40%，60%，为保证有效访问时间不超过2ns，求允许的最大缺页率f是多少
EAT=a(&+t)+(1-a)[(1-f)(&+t+&+t)+f(&+t+t1+&+t)]<=2ns
其中a=70%, t=1ns, &=0, t1=8000*40%+20000*60% 代入即可解得f 。
11．采用LRU算法，所分配的物理页面有3页，装入虚页的序列为7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，访问一次内存需要100ns，一次快表查询速度是20ns，缺页中断处理时间是25ms，若快表命中率20%，问这20页的平均访问时间是多少？
参看本章第0题，先由虚页序列，3页物理页和LRU算法得到缺页率f=0.6， 然后代入到EAT公式即可。
12．分页系统，访问内存一次需要250ns，缺页率2%，缺页中断在处理已修改页面时需要12ms，处理未修改页面时需要5ms，两种情况各占40%和60%，求有效访问时间EAT
EAT=a(&+t)+(1-a)[(1-f)(&+t+&+t)+f(&+t+t1+&+t)]
其中a=0, t=250ns, f=2%，&=0, t1=12000000*40%+5000000*60% 代入即可
13．分页系统，访问内存一次需要400ns，访问联想寄存器一次需要150ns，缺页中断在页面修改和未修改情况下各是8ms和3ms，两种情况各占50%，缺页率是2%，联想寄存器命中率是70%，求有效访问时间EAT
联想寄存器等价于快表，代入公式即可。
14．分页系统，每页32个字，一段代码长度为320个字，页表如下 页号 页架号 状态 0 6 1 1 4 1 2 3 1 3 2 1 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 0 0 把以下八进制逻辑地址翻译为物理地址，不能翻译的说明理由 101，204，576
答： 本题中页号指虚页号，页架号指物理页号，状态指是否存在于内存中。
八进制101翻译为二进制为001000001。每页32个字，则页内地址占低5位，其余高位表示页号，则该逻辑地址页号为2，页内地址为1，即对应物理页号为3，页内地址为1，二进制物理地址为001100001(写成八进制也可)
八进制204翻译为二进制为010000100。则虚页号为4，不在内存中，发生缺页中断。 八进制576翻译为二进制为101111110。虚页号为11，这段代码虚页号为0-9， 不在这个范围内，越界。
15．请求段式管理系统，虚拟地址空间24位，高8位作为段号，问（1）一个进程最多有多少个段？（2）每段最大长度？（3）段表如下，把以下地址翻译为物理地址 （0，430），（1，50），（2，30），（3，70） 段号 0 1 2 3 段长 600 40 100 80 主存起始地址 2100 2800 4000 是否在主存中 是 是 否 是 (1) 2^8 (2) 2^16
(3) 存在于主存且不越界的情况下，物理地址=段的起始地址+段内偏移 （0，430）物理地址为2100+430=2530 （1，50） 50>40， 越界 （2，30） 没在主存
（3，70） 物理地址为4000+70=4070 16．请求段页式管理系统，虚拟地址空间16位，每个进程有2个段，段内分页，页大小2^12字节，段页表如下图所示。