操作系统作业（五一）

• 首次适应：

• 最佳适应算法

（1） 64K=2^{16} 4=2^2 页码有两位, 64K/4=2^{12} , 逻辑地址12位

1023=0011 1111 1111 , 高两位为 00 , 在第0页，主存号为2，物理地址为 2\times1024+1023\mod1024=3071

2500=1001 1100 0100 , 高两位为 10 ,在第2页，主存号为6，物理地址为 6\times1024+2500\mod1024=6596

3500=1101 1010 1100 , 高两位为 11 , 在第3页，主存号为7， 物理地址为 7\times1024+3500\mod1024=7596

4500=1 0001 1001 0100 , 超出范围

(2)

（1） 32=2^5, 2K=2^{11}, 所以逻辑地址的格式为

（2）1M=2^{20}, 页内偏移为 2^{11}, 2^{20}/2^{11}=2^9, 要求表项有9位, 页表有 2^{11}项

（3)　2^{19}/2^{11}=2^8, 表项为8位即可。

​ 0A5C=0000 1010 0101 1100, 页码为2，页码合法，其对应物理块号为4，故原地址转换为0001　0010　0101　1100=125C, 即物理地址为125C。

​ 103C=0001　0000　0011　1100, 页码为4， 页码合法，但该页为装入内存，产生缺页中断。

​ 1A5C=0001　1010　0101　1100, 页码为6， 页码非法，产生越界中断。

• 当模块数 M=3 时

​ FIFO算法： 缺页数：9 缺页率：9/12=75%

​ LRU算法： 缺页数：10 缺页率：10/12=83.3%

• 当模块数 M=4 时

​ FIFO算法： 缺页数：10 缺页率： 10/12=83.3%

​ LRU算法： 缺页数：8 缺页率：8/12=66.7%

​ （1）FIFO算法换出的是物理块3中的第3页

​ （2）LRU算法换出的是物理块0中的第2页

​ （3）改进的Clock算法换出的是物理块2中的第0页

​ 当缺页时，若页面没有被修改过，则时间为8 ms+1μs

​ 当缺页时，若页面被修改过，则时间为20ms+1μs

​ 当不缺页时，直接访问内存，则时间为1μs

​ 设最大缺页率为p

​ 则有 (1-p)\times 1μs+p\times 30\%\times(8ms+1μs)+p\times70\%\times(20ms+1μs)=2μs

​ 解得 p=0.0061\%

​ 即最大缺页率为 0.0061\%

​ 4KB=2^{12}B , 故页内位移占虚地址的低12位，页号占剩余高位。

​ 2362H=0010　0011　0110　0010 ，页号为２，有效位为１。在内存中，先访问快表，时间为10ns , 初始 状态为空，故访问内存得到页框号，时间为100ns ,再合成物理地址访问主存，时间为100ns 。时间为： 10ns+100ns+100ns=210ns 。

​ 1565H=0001　0101　0110　0101 , 页号为1，有效位为0，不在内存中。先访问快表，时间为10ns , 快表中无相应信息，进行缺页中断处理，时间为108ms , 合成物理地址访问主存，时间为100ns 。时间为：10ns+108ms+100ns=108.11ms 。

​ 25A5H=0010　0101　1010　0101，页号为2，有效位为1，在内存中，先访问快表，时间为10ns ,快表中有相应信息，合成物理地址100ns 。时间为：10ns+100ns=110ns 。

​(0,137) = 50000+137 = 50137, (1,4000) 段内地址越界

​(2,3600) = 70000+3600 = 73600 , (5,230) 段号越界

​ （1） 第0段存在位为0，该段未装入内存，产生缺页中断。

​ （2） 第1段存在位为1，该段已装入内存，存取控制为R，但指令要求写，产生保护性中断

​ （3） 第3段存在位为1，该段已装入内存，存取控制为R，指令中段内位移小于段长 ，将该单元的内容读到寄存器R1中 。

​ （4）第3段存在位为1，该段已装入内存，存取控制为R，指令中段内位移大于段长，产生越界中断。

​ （5）第2段存在位为1，该段已装入内存，存取控制为E，指令中段内位移小于段长，跳到内存地址为3100处执行。