分析:首次适应算法将空闲区按起始地址递增的次序拉链,而最佳适应算法则将空闲区按 分区大小递增的次序拉链。在分配时飞它们都是从链首开始顺序查找,直至找到一个足够大的 空闲分区为止,然后按作业大小从该分区中划出一块内存空间分配给请求者,余下的分区(如 果有的话)仍按上述原则留在空闲分区链中;而在释放时,则需分别按地址递增或大小递增的 次序将空闲分区插入空闲分区链,并都需要进行空闲分区的合并。 答:使用首次适应算法和最佳适应算法进行上述内存的分配和回收后,内存的实际使用情 况如下图所示 5.在请求分页存储管理系统中,试问 (1)局部与全局页面淘汰算法有何区别?为什么在多道系统中常用局部页面淘汰算法? (2)试设计一个LRU淘汰算法的近似算法(指出所需的硬件支持、数据结构及软件处理流 答:(1)局部页面置换只在当前进程分配的页面中选择一个被置换的页面:全局页面置换 从整个存储器用户区的所有页面中选择一个被置换的页面 在多道程序系统中,采用局部页面置换策略进行页面置换,即使某个进程出现了抖动现象, 不致引起其他进程也产生抖动,-可以将抖动局限在较小的范围内。 (2)可以在MBT表中增设一个"引用位”,当MBT表中的页被访问时”引用位"置1,在MBT 表中再增设一个指针域,用于记录进入内存的页面顺序,另设一个替换指针指向最近刚刚进入 内存的页面。可以根据引用位的状态来判别各页面最近的使用情况,当需要置换一页时,选择 其引用位为0的页淘汰。该算法的程序流程图如图2.6所示: 入口 替换指针前进一步 指向下一存储块 引用位置0 其引用位=0 选择该也淘汰 出口 6.某系统采用页式存储管理策略,拥有逻辑空间32页,每页2K,拥有物理空间1M (1)写出逻辑地址的格式。 (2)若不考虑访问权限等,进程的页表有多少项?每项至少有多少位? (3)如果物理空间减少一半,页表结构应相应作怎样的改变? 答:(1)该系统拥有逻辑空间32页,故逻辑地址中页号必须用5位来描述;而每页为2K,因 此,页内地址必须用11位来描述,这样可得到它的逻辑地址格式如下 1110 页号「页内地址 (2)每个进程最多有32个页面,因此,进程的页表项最多为32项:若不考虑访问权限等
分析：首次适应算法将空闲区按起始地址递增的次序拉链,而最佳适应算法则将空闲区按 分区大小递增的次序拉链。在分配时飞它们都是从链首开始顺序查找,直至找到一个足够大的 空闲分区为止,然后按作业大小从该分区中划出一块内存空间分配给请求者,余下的分区(如 果有的话)仍按上述原则留在空闲分区链中;而在释放时,则需分别按地址递增或大小递增的 次序将空闲分区插入空闲分区链,并都需要进行空闲分区的合并。 答：使用首次适应算法和最佳适应算法进行上述内存的分配和回收后，内存的实际使用情 况如下图所示。 5.在请求分页存储管理系统中,试问: （1）局部与全局页面淘汰算法有何区别? 为什么在多道系统中常用局部页面淘汰算法? （2）试设计一个 LRU 淘汰算法的近似算法(指出所需的硬件支持、数据结构及软件处理流 程)。 答：（1）局部页面置换只在当前进程分配的页面中选择一个被置换的页面:全局页面置换 从整个存储器用户区的所有页面中选择一个被置换的页面。 在多道程序系统中,采用局部页面置换策略进行页面置换,即使某个进程出现了抖动现象, 不致引起其他进程也产生抖动,-可以将抖动局限在较小的范围内。 （2）可以在 MBT 表中增设一个"引用位",当 MBT 表中的页被访问时"引用位"置 1,在 MBT 表中再增设一个指针域,用于记录进入内存的页面顺序,另设一个替换指针指向最近刚刚进入 内存的页面。可以根据引用位的状态来判别各页面最近的使用情况,当需要置换一页时,选择 其引用位为 0 的页淘汰。该算法的程序流程图如图 2.6 所示: N Y 6.某系统采用页式存储管理策略,拥有逻辑空间 32 页,每页 2K,拥有物理空间 1M。 (1)写出逻辑地址的格式。 (2)若不考虑访问权限等,进程的页表有多少项?每项至少有多少位? (3)如果物理空间减少一半,页表结构应相应作怎样的改变? 答:(1)该系统拥有逻辑空间 32 页,故逻辑地址中页号必须用 5 位来描述;而每页为 2K,因 此,页内地址必须用 11 位来描述,这样可得到它的逻辑地址格式如下: 15 11 10 0 页 号 页 内 地 址 (2)每个进程最多有 32 个页面,因此,进程的页表项最多为 32 项；若不考虑访问权限等, 入口 替换指针前进一步 指向下一存储块 其引用位=0 选择该也淘汰 出口 引用位置 0
则页表项中只需给出页所对应的物理块块号,1M的物理空间可分成29个内存块,故每个页表 项至少有9位。 (3)如果物理空间减少一半,则页表中页表项数仍不变,但每项的长度可减少1位。 7.假定某页式管理系统,主存为64KB,分成16块,块号为0,1,2,3,4,…,15。设某作业有 4页,其页号为0,1,2,3,被分别装入主存的2,4,1,6块。试问 (1)该作业的总长度是多少字节?(按十进制) (2)写出该作业每一页在主存中的起始地址。 (3)若给出逻辑地址[0,100]、[1,50]、[2,0]、[3,60],请计算出相应的内存地址 答:(1)每块的长度=64KB/16=4KB 因为块的大小与页面的大小相等,所以每页为4KB。因此,作业的总长度为4KB×4=16KB。 (2)因为页号为0,1,2,3的页分别被装入主存2,4,1,6块中,即PMT为 页号块号 所以该作业的 第0页在主存中的起始地址为4K×2=8K 第1页在主存中的起始地址为4K×4=16K 第2页在主存中的起始地址为4K×1=4K 第3页在主存中的起始地址为4K×6=24K题 (3)逻辑地址[0,100]的内存地址为4K×2+100=8192+100=8292 逻辑地址[1,50]的内存地址为4K×4+50=16384+50=164 逻辑地址[2,0]的内存地址为4K×1+0=4096 逻辑地址[3,60]的内存地址为4K×6+60=24K+60=24576+60=24636 8.对于下表所示的段表,请将逻辑地址(0,137),(1,4000),(2,3600),(5,230)转换成物理 地址。 段号内存地址段长 0 50K 10K 60K 70K 120K 4150 分析:在分段系统中进行地址转换时,地址变换机构首先将逻辑地址中的段号与段表长度 作比较,如果段号超长,则产生越界中断;否则使以段号为索引去检索段表,从中得到段在内存 的始址和段长;然后再将逻辑地址中的段内地址与段长作比较,若不越界,则由段的始址与段 内地址相加,形成物理地址 答:(1)段号0小于段表长5,故段号合法:由段表的第0项可获得段的内存始址为50K,段 长为10K由于段内地址137,小于段长10K,故段内地址也是合法的,因此可得出对应的物理地 址为50K+137=51337。 (2)段号1小于段表长,故段号合法:由段表的第1项可获得段的内存始址为60K,段长为 3K;经检查,段内地址4000超过段长3K,因此产生越界中断 (3)段号2小于段表长,故段号合法:由段表的第2项可获得段的内存始址为70K,段长为
则页表项中只需给出页所对应的物理块块号,1M 的物理空间可分成 29 个内存块,故每个页表 项至少有 9 位。 （3）如果物理空间减少一半,则页表中页表项数仍不变,但每项的长度可减少 1 位。 7.假定某页式管理系统,主存为 64KB,分成 16 块,块号为 0,1,2,3,4,…,15。设某作业有 4 页,其页号为 0,1,2,3,被分别装入主存的 2,4,1,6 块。试问: (1)该作业的总长度是多少字节?(按十进制) (2)写出该作业每一页在主存中的起始地址。 (3)若给出逻辑地址[0,100]、[1,50]、[2,0]、[3,60],请计算出相应的内存地址。 答:(1)每块的长度=64KB/16=4KB 因为块的大小与页面的大小相等,所以每页为 4KB。因此,作业的总长度为 4KB×4=16KB。 (2)因为页号为 0,1,2,3 的页分别被装入主存 2,4,1,6 块中,即 PMT 为: 页号 块号 0 2 1 4 2 1 3 6 所以该作业的： 第 0 页在主存中的起始地址为 4K×2=8K 第 1 页在主存中的起始地址为 4K×4=16K 第 2 页在主存中的起始地址为 4K×1=4K 第 3 页在主存中的起始地址为 4K×6=24K 题 （3）逻辑地址[0,100]的内存地址为 4K×2+100=8192+100=8292 逻辑地址[1,50]的内存地址为 4K×4+50=16384+50=16434 逻辑地址[2,0]的内存地址为 4K×1+0=4096 逻辑地址[3,60]的内存地址为 4K×6+60=24K+60=24576+60=24636 8.对于下表所示的段表,请将逻辑地址(0,137),(1,4000),(2,3600),(5,230)转换成物理 地址。 段号 内存地址 段 长 0 50K 10K 1 60K 3K 2 70K 5K 3 120K 8K 4 150K 4K 分析：在分段系统中进行地址转换时,地址变换机构首先将逻辑地址中的段号与段表长度 作比较,如果段号超长,则产生越界中断;否则使以段号为索引去检索段表,从中得到段在内存 的始址和段长;然后再将逻辑地址中的段内地址与段长作比较,若不越界,则由段的始址与段 内地址相加,形成物理地址。 答:(1)段号 0 小于段表长 5,故段号合法:由段表的第 0 项可获得段的内存始址为 5OK,段 长为 1OK 由于段内地址 137,小于段长 1OK,故段内地址也是合法的,因此可得出对应的物理地 址为 5OK+137=51337。 (2)段号 1 小于段表长,故段号合法:由段表的第 1 项可获得段的内存始址为 60K,段长为 3K;经检查,段内地址 4000 超过段长 3K,因此产生越界中断。 (3)段号 2 小于段表长,故段号合法:由段表的第 2 项可获得段的内存始址为 7OK,段长为