操作系统第四章复习.ppt

第四章 存储器管理,一、 程序的装入和链接及其重要概念 (1) 编译(Compiling ) (2) 链接(Linking) 静态链接 动态链接 装入时动态链接 运行时动态链接 (3) 装入(Loading) 绝对装入 可重定位装入 动态重定位装入,符号地址 相对地址(逻辑地址) 绝对地址（物理地址） 重定位 静态重定位 动态重定位,二、存储管理策略,实存管理 连续区分配（包括固定分区、可变分区和伙伴系统） 分页（Paging ） 分段（Segmentation ） 段页式（ segmentation with paging ） 虚存管理 请求分页(Demand paging)- 主流技术 请求分段(Demand segmentation) 段页式（ segmentation with paging ）,三、连续分配方式,1、动态分区分配算法 FF,CFF,BF,WF 各种算法是如何来进行内存的分配和回收的？ 2、 造成动态分区分配方式浪费内存空间的主要原因是什么？它可以通过什么办法加以解决。 紧凑或拼接 3、什么是“内零头”和“外零头”？它们分别在哪些内存分配方式下存在？ “多分配的空间” “分不出去的空间” 4、 什么是对换？外存对文件区和对换区是如何管理的？对换的分类？,1、 分页系统是如何将地址空间中的作业划分成若干个页，如何进行内存分配？ 2、分页系统的地址转换。 掌握分页系统逻辑地址的结构，为了进行逻辑地址到物理地址的转换，分页系统必须为每个作业配置什么样的数据结构并提供哪些硬件支持？如何实现地址转换？为什么引进快表可以加快分页系统存取指令和数据的速度。 3、分段存储管理方式。 了解由分页发展为分段，并近一步发展为段页式存储管理方式的主要推动力是什么？分段和段页式系统是如何管理作业的地址空间和内存空间的？它们的地址变换是如何完成的？并应注意对分段系统和分页系统的比较。为什么分段比分页更容易保护和共享。,四、离散分配方式,1、为什么要引入虚拟存储器？ 常规存储管理方式的特征（一次性和驻留性） 局部性原理 2、虚拟存储器的特征 离散性、多次性、对换性和虚拟性。 了解每种特征的具体含义，以及它们相互之间存在的关系？ 3、实现虚拟存储器的关键技术是什么？ 请求调页（段）技术和页（段）置换技术，这些技术的实现需要得到哪些硬件和软件支持。 （一定容量的内存和较大容量的外存、页（段）表、缺页（段）中断机构和地址变换机构）,五、离散分配方式之虚拟存储器,4、请求分页系统的基本原理 （1）页表机制 （2）地址变换机构和过程 （3）页面分配和置换策略 固定分配局部置换 可变分配全局置换 可变分配局部置换 （4）页面置换算法（ “抖动”，计算缺页率） OPT置换算法 FIFO置换算法 LRU置换算法及其近似算法Clock算法 5、请求分段系统的基本原理。,六、几个重要知识点,1、内存扩充技术：交换和覆盖技术 2、缺页率。 和缺页率有关的因素有哪些？ 3、抖动。发生抖动的现象是什么？产生抖动的原因有哪些？消除抖动的方法？ 4、工作集和驻留集。,各种存储方法比较,各种存储方法比较,各种存储方法比较,典型问题分析,1. 什么情况下需要进行重定位？为什么要引入动态重定位？ 2. 考虑一个由256个页面、每页由4096字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问： （1）逻辑地址需要多少位二进制来表示？ （2）物理地址需要多少位二进制来表示？ 3. 对一个将页表存放在内存中的分页系统： 1）如果内存需要0.2us，有效访问时间为多少？ 2）如果加一快表，且假定在快表中找到页表项的几率高达90，则有效访问时间又是多少（假定查快表需花的时间为0）？,4. 在虚拟内存管理中，地址变换机构将逻辑地址转换为物理地址，形成该逻辑地址的阶段是（ ）。 编辑 编译 链接 装载 5. 采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是_ A）224 B）28 C） 216 D） 232 6. 作业在执行中发生了缺页中断，经操作系统处理后，应让其执行_指令。 A）被中断的前一条 B）被中断的后一条 C）被中断的 D） 启动时的第一条,7、某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空），采用最佳适配（Best fit）算法，分配和释放的顺序为：分配15MB，分配30MB，释放15MB，分配6MB，此时主存中最大空闲分区的大小是（ ） A：7MB B：9MB C：10MB D：15MB,逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（ ） A：64 B：128 C：256 D：512,D,B,8、某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为210字节，页表项大小为2字节，逻辑地址结构为,9、当系统发生抖动时，可以采取的有效措施是 （ ） 、撤销部分进程 、增加磁盘交换区的容量 、提高用户进程优先级 A：仅 B：仅 C：仅 D： 仅、 ,A,11、某虚拟存储器的用户编程空间共32个页面，每页1KB，主存16KB。某户作业为6页，假定某时刻该作业页表如图。试将虚拟地址0A5CH、103CH、1A5CH转换为物理地址。相应的物理地址是否合法？是否产生缺页？,10、 在缺页处理过程中，操作系统执行的操作可能是（ ） 、修改页表 、磁盘I/O 、分配页框 A：仅、 B：仅 C：仅 D： 、 和 ,D,12、某系统的空闲分区表如下，系统采用可变分区存储管理模式，现有一个程序序列：96K、20K、200K。若用首次适应算法和最佳适应算法来为这些程序分配内存，试问哪一种算法可以满足所有程序的请求，为什么？,13、解决大作业和小内存的矛盾有哪些途径？简述其实现思想。,14、某段式存储管理采用如下段表。试计算（0，430）、（3，200）、（1，34）、（2，2500）的主存地址。当无法进行地址变换时，应说明产生何种中断。,15、一个32位地址的计算机使用两级页表，虚地址被分成9位顶级页表域；11位的二级页表域，其余位为页内偏移，请问： 1) 页面长度是多少？ 2) 在逻辑地址空间中，共存在多少页？,页面长度为2124K 页数220,16.请求分页管理系统中，某页表如图 ： 页面大小为4KB， 一次内存的访问时间是100ns， 一次快表（TLB）的访问时间是10ns， 处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间）， 进程的驻留集大小固定为2， 采用LRU算法和局部淘汰策略。 假设: TLB初始为空； 忽略访问页表之后的TLB更新时间； 有效位为0表示页面不在内存，缺页中断处理后，返回到产生缺页中断的指令处重新执行。 设有虚地址访问序列2362H、1565H、25A5H，请问： （1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。 （2） 基于上述访问序列，虚地址1565H的 物理地址是多少？,解答：,页面4KB，12位，即16进制的3位，则2362H的最高位就是页号。 （1）2362H：P=2，访问快表10ns，因初始为空，因此需访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计： 10ns+100ns+100ns=210ns。 1565H：P=1，访问快表10ns，落空，访问页表100ns，没在主存，缺页中断处理108ns（已含更新TLB和页表的时间），合成物理地址后访问主存100ns。 10ns+100ns+108ns+100ns318ns。 25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计： 10ns+100ns=110ns。 （2）当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。,17、设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页（Page）存储空间，页的大小为1KB。操作系统采用固定分配局部置换策略为此进程分配4个页框。,当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题： （1）该逻辑地址对应的页号是多少？ （2）若采用先进先出置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。 （3）若采用时钟置换算法，该逻辑地址对应的物理地址是多少？（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框）,解答： 17CAH=(0001 0111 1100 1010)2 （1）页大小为1K，所以页内偏移地址为10位，于是前6位是页号，所以第一问的解为：5 （2）FIFO，则被置换的页面所在页框为7，所以对应的物理地址为（0001 1111 1100 1010）2 1FCAH （3）CLOCK，则被置换的页面所在页框为2，所以对应的物理地址为（0000 1011 1100 1010）2 0BCAH,18. 关于请求分页系统的页面置换策略如下： 系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没被访问过的页框将被系统收回，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。 当发生缺页时，如果该页曾被使用过且还在空闲页链表中，则将其重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。 忽略其他进程的影响和系统开销。初始时进程驻留集为空。 目前系统空闲页的页框号依次为：32、15、21、41，进程P依次访问的为、。 请回答下列问题：当虚拟页为、 、 时，对应的页框号分别是什么？说明理由。,解答：,1、页框号为21。 因为起始驻留集为空， 而0页对应的页框为空闲链表中的第三个空闲页框，其对应的页框号为21。 2、页框号为32。 因为11 10故发生第三轮扫描，页号为1的页框在第二轮已经处于空