第四章作业（存储器管理）
第一次作业：
1、对于首次适应算法，请回答下列问题：
（1）应如何将各空闲分区链接成空闲分区链？
为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。为了检索方便，在分区尾部重复设置状态位和分区大小表目。当分区被分配出以后，把状态位由0改为1，此时，前、后向指针已无意义。
（2）在回收内存时，可能出现哪几种情况？应怎样处理这些情况？
(1回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。
(2回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
(3回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。
(4 回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。
（3）请对该算法的内存管理性能进行分析。
该算法倾向于优先利用内存中低地址，从而保证了高地址部分的大空闲去。这给以后达的大作业分配大的内存空间创造的条件。起缺点是低址部分不断被划分，会留下许多难以利用的小空闲分区，每次查找都从低址开始，会增加查找空闲分区的开销。
2分页和分段存储管理有何区别？
答：主要表现在（1）页是信息的物理单位，分页是为实现离散分配方式，以消
减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要
而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。
分段的目的是为了能更好地满足用户的需要。
（2）页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，
是由机器硬件实现的，因而在系统中只能有一种大小的页面；根据信息的性质来划分。（3）分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，即需给出段名，又需给出段内地址。
3某请求分页系统，用户空间为32KB，每个页面1KB，主存16KB。某用户程序有7页
（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、
页面大小为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前该进程各页面的访问情况如下表所示：
当进程执行到时刻300时，要访问逻辑地址为17CAH 的数据，请回答下列问题： （1）该逻辑地址对应的页号是多少？
（2）若采用先进先出（FIFO ）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。
（3）若采用时钟（CLOCK ）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。设搜索下一页的指针顺时针方向移动，且当前指向2号页框，示意图如下：
9号号7
17CAH=(0001 0111 1100 1010)2
（1）页大小为1K ，则页内偏移地址为10位，前6位是页号，所以逻辑地址对应的页号为：5 （2）FIFO ：被置换的页面所在页框为7，所以对应的物理地址为（0001 1111 1100 1010）2=1FCAH
（3）CLOCK ：被置换的页面所在页框为2，所以对应的物理地址为
