题目1
1、某个OS采用可变分区分配方法管理，用户主存512KB，自由区由可用空区表管理。若分配时采用分配自由区的低地址部分的方案，假设初始时全为空。对于下列申请顺序： 申请(300KB), 申请(100KB), 释放(300KB), 申请(150KB),申请(30KB),申请(40KB),申请(60KB),释放(30KB)。回答下列问题：
（1）采用首次适应（FF），自由空区中有哪些空块（给出地址和大小）？
（2）若采用最佳适应（BF），回答（1）中的问题。
（3）如果再申请100KB，针对（1）和（2）各有什么结果？
解答：
（1）如下图所示：
（2）如下图所示：
（3）针对（1） 可分配在400K位置；针对（2） 无法分配。
题目2
2、考虑下面的页访问串：1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6 假定有4,5,6个页块，应用下面的页面替换算法，计算各会出现多少次缺页中断。注意，所给定的页块初始均为空，因此，首次访问一页时就会发生缺页中断。
（1）LRU （2）FIFO （3）Optimal
解答：
（1）LRU
对于4个页块：
可得共出现缺页中断10次；
步骤同上图可得5个页块共出现缺页中断8次，6个页块共出现缺页中断7次。
（2）FIFO
对于4个页块：
可得共出现缺页中断14次；
步骤同上图可得5个页块共出现缺页中断10次，6个页块共出现缺页中断10次。
（3）Optimal
对于4个页块：
可得共出现缺页中断8次；
步骤同上图可得5个页块共出现缺页中断8次，6个页块共出现缺页中断7次。
题目3
3、一台计算机有4个页块，装入时间、上次引用时间、它们的R（读）与M（修改）位如下表所示（时间：滴答），请问NRU、FIFO、LRU和第二次机会算法将替换那一页？
解答：
NRU算法将替换0类编号页页0；
FIFO算法将替换最早装入页页2
LRU算法将替换最近未被使用页页1
第二次机会算法将替换载入时间早且R位为零的页页0。
题目4
4、有一页式系统，其页表存放在主存中。
（1）如果对主存的一次存取需要1.5微秒，试问实现一次页面访问时的存取时间是多少？
（2）如果系统加有快表且平均命中率为85%，而页表项在快表中的查找时间忽略为0，试问此时的存取时间为多少？
解答：
（1）需要两次访问内存：第一次是访问页表，从而找到线性地址对应的物理地址；第二次是利用找到的物理地址来访问实际的内存页面。所以共需要3微秒。
（2）在快表中得到物理地址到主存找的概率是85%，需要1.5微秒；页表不在快表中在主存的概率是15%，需要3微秒，所以存取时间为1.50.85+30.15=1.725微秒。
题目5
5、已知某系统页面长4KB，页表项4B，采用多层分页策略映射64位虚拟地址空间。若限定最高层页表占1页，问它可以采用几层分页策略。
解答：
页面大小为4KB，总共有2^12位信息，其中只有2^10位信息是所需要的信息，而另外4字节的内容是管理这张页表的信息。64位地址空间，事实上每页只能存放10位的容量，去掉作为页内地址的12位空间，将有2^52页表，将这些页表按每页存放10位容量计算，则需要[52/10]=6层，故必须采取6层分页策略。
题目6
6、在一个段式存储管理系统中，其段表如表1所示。试求表2所示中的逻辑地址所对应的物理地址。
解答：
（1）由于第0段的内存始址为210，段长为500，故逻辑地址[0,430]是合法地址。逻辑地址[0,430] 对应的物理地址为210＋430＝640。
（2）由于第1段的内存始址为2350，段长为20，故逻辑地址[1,10]是合法地址。逻辑地址[1,10]对应 的物理地址为2350+10=2360。
（3）由于第段起始地址为100，段长为90，所给逻辑地址[2,500]非法。
（4）由于第3段的内存始址为1350，段长为590，故逻辑地址[3,400]是合法地址。逻辑地址[3,400] 对应的物理地址为1350＋400＝1750 。
（5）由于第4段的内存始址为1938，段长为95，所给逻辑地址[4,112]非法。
（6）由于系统中不存在第5段，所给逻辑地址[5,32]非法。
题目7
7、请求分页管理系统中,假设某进程的页表内容如下表所示:
页面大小为 4KB,一次内存的访问时间是 100ns,一次快表(TLB)的访问时间是10ns,处理一次缺页的平均时间 10^8 ns(已含更新 TLB 和页表的时间),进程的驻留集大小固定为 2,采用最近最少使用置换算法(LRU)和局部淘汰策略。假设（1）TLB 初始为空;（2）地址转换时先访问 TLB,若 TLB 未命中,再访问页表(忽略访问页表之后的 TLB 更新时间);（3）有效位为 0 表示页面不在内存,产生缺页中断,缺页中断处理后,返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H,请问:
(1)依次访问上述三个虚地址,各需多少时间?给出计算过程。
(2)基于上述访问序列,虚地址 1565H 的物理地址是多少?请说明理由。
解答：
（1）根据页式管理工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即212，则得到页内位移占虚地址12位，页号占剩余高位。可得三个虚地址的页号P如下：
2362H: P=2,访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。
1565H：P=1，访问快表10ns，落空，访问页表100ns，落空，进行缺页中断处理108ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+100ns≈108ns。
25A5H：P=2，访问快表，因第一次访问已将该页号放入块表，因此花费10ns便可合成物理地址，访主存100ns，共计10ns+100ns=110ns。
（2）当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H物理地址为101565H。
题目8
8、设某计算机的逻辑地址空间和物理地址空间均为 64KB,按字节编址。若某进程最多需要 6 页(Page)数据存储空间,页的大小为 1KB,操作系统采用固定分配局部置换策略为此进程分配 4 个页框(Page Frame)。在时刻 260 前的该进程访问情况如下表所示(访问位即使用位)。
当该进程执行到时刻 260 时,要访问逻辑地址为 17CAH 的数据。请回答下列问题:
(1) 该逻辑地址对应的页号是多少?
(2) 若采用先进先出(FIFO)置换算法,该逻辑地址对应的物理地址是多少?要求给出计算过程。
(3) 若采用时钟(CLOCK)置换算法,该逻辑地址对应的物理地址是多少?要求给出计算过程 (设搜索下一页的指针沿顺时针方向移动,且当前指向 2 号页框,示意图如下) 。
解答：
（1）17CAH=(0001 0111 1100 1010)2。页大小为1K，所以页内偏移地址为10位，于是前6位是页号，所以得到页号为：5。
（2）若采用FIFO算法，则被置换的页面所在页框为7，所以对应的物理地址为(0001 1111 1100 1010)2=1FCAH。
（3）若采用时钟算法，第一次循环时访问位都置为0，又当前指针指向2号页框，故第二次循环将置换2号页框对应的页，所以对应的物理地址为(0000 1011 1100 1010)2=0BCAH。
