操作系统第四章复习.ppt

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