第5章:存储管理

吕鸣松(讲师)东北大学信息科学与工程学院lvmingsong@ise.
neu.
edu.
cn《操作系统原理》2013年春季课程主要内容存储管理的功能与目标分区存储管理覆盖与交换技术页式与段式存储管理机制虚拟存储器(重中之重)《操作系统原理》——东北大学第5章存储管理主要内容存储管理的功能与目标分区存储管理覆盖与交换技术页式与段式存储管理机制虚拟存储器(重中之重)《操作系统原理》——东北大学第5章存储管理存储管理存储器功能是保存数据,发展方向是高速、大容量和小体积存储组织在存储技术和CPU寻址许可的范围内组织合理的存储结构依据是访问速度、容量、价格等因素当前典型的存储体系结构寄存器-缓存-内存-外存《操作系统原理》——东北大学第5章存储管理存储体系结构《操作系统原理》——东北大学第5章存储管理容量更大单位容量更便宜速度更快存储体系结构寄存器位于CPU内部,有几个到几十个寄存器缓存Intel3770k4-core8MB:2285.
00Intel3930k6-core12MB:4399.
00速度为几个到几十个时钟周期《操作系统原理》——东北大学第5章存储管理存储体系结构内存4GB内存价格200.
00传输带宽在10GB级别《操作系统原理》——东北大学第5章存储管理存储体系结构外存希捷2TB硬盘:579.
00速度:每秒传输数据100MB左右《操作系统原理》——东北大学第5章存储管理存储管理的功能存储的分配和回收将外存中的数据调入内存,在内存中为它们安排合适的位置目的是可使多个程序同时驻留在内存中,以提高CPU利用率进程执行结束时,回收该进程所占内存资源涉及的设计问题分配结构放置策略交换策略调入策略回收策略《操作系统原理》——东北大学第5章存储管理存储管理的功能地址变换可执行文件生成中的链接技术程序加载(装入)时的重定位技术进程运行时硬件和软件的地址变换技术和机构《操作系统原理》——东北大学第5章存储管理存储管理的功能逻辑地址(相对地址,虚地址)用户的程序经过汇编或编译后形成目标代码,目标代码通常采用相对地址的形式其首地址为0,其余指令中的地址都相对于首地址来编址不能用逻辑地址在内存中读取信息物理地址(绝对地址,实地址)内存中存储单元的地址,物理地址可直接寻址《操作系统原理》——东北大学第5章存储管理…存储管理的功能地址映射将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址当程序装入内存时,操作系统要为该程序分配一个合适的内存空间,由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时,是按物理地址进行的,所以要进行地址转换《操作系统原理》——东北大学第5章存储管理存储管理的功能静态地址重定位在虚拟空间程序执行之前由装配程序完成地址映射《操作系统原理》——东北大学第5章存储管理.
MovAX,[k].
.
进程:20k+50k=70k存储管理的功能静态地址重定位优点无需硬件支持缺点只能装入有限数量的程序一个程序占用连续的空间,不易实现共享程序一旦装入内存,无法再移动无法实现虚拟存储器《操作系统原理》——东北大学第5章存储管理存储管理的功能动态地址重定位在程序运行过程中要访问数据时再进行地址变换(即在逐条指令执行时完成地址映射.
一般为了提高效率,此工作由硬件地址映射机制来完成)硬件上需要一对寄存器的支持,装入和执行时通过硬件地址变换机构,完成虚拟地址到实际内存地址的变换《操作系统原理》——东北大学第5章存储管理存储管理的功能动态地址重定位《操作系统原理》——东北大学第5章存储管理/185物理地址空间地址映射LoadA200BRVR10002001200存储管理的功能动态地址重定位优点可以移动程序,有利于实现共享(只要改变BR中地内容,便可将程序定位在新地内存空间中)可部分地、动态地分配内存,是虚拟存储器实现的基础缺点需要硬件支持,操作系统实现复杂《操作系统原理》——东北大学第5章存储管理存储管理的功能程序的链接——静态链接在程序执行之前,必须由链接装配程序把它们链接成一个可运行的目标程序,并在程序运行前都装入内存《操作系统原理》——东北大学第5章存储管理装入存储管理的功能程序的链接——装入时动态链接边装入边链接.
装入一个模块时,若发生外部模块调用,装入程序将去找出相应的外部模块并装入《操作系统原理》——东北大学第5章存储管理装入存储管理的功能程序的链接——运行时动态链接边执行边链接.
在执行过程中,若发现一个被调用模块尚未装入内存时,由OS去找该模块并将其装入内存,链接到调用者模块上优点能够加快程序的装入过程节省内存《操作系统原理》——东北大学第5章存储管理存储管理的功能内外存数据的传输控制将执行的程序和数据段调入内存,把处于等待状态的程序和数据段调出内存方法用户程序控制:例如,覆盖(Overlay)操作系统控制交换(Swapping)请求调入(ondemand)和预调入(onprefetch)《操作系统原理》——东北大学第5章存储管理存储管理的功能存储共享和保护各道作业只在自己所属区域中运行,不破坏其他作业以及不被其他作业破坏保护系统程序区不被用户侵犯(有意或无意的)不允许用户程序读写不属于自己地址空间的数据(系统区地址空间,其他用户程序的地址空间)代码和数据共享地址空间访问权限(读、写、执行)保护方法界限保护访问方式保护其它《操作系统原理》——东北大学第5章存储管理内存信息的共享与保护界限保护所有访问地址必须在上下界之间;每个进程都有自己独立的进程空间,如果一个进程在运行时所产生的地址在其地址空间之外,则发生地址越界当程序要访问某个内存单元时,由硬件检查是否允许,如果允许则执行,否则产生地址越界中断,由操作系统进行相应处理《操作系统原理》——东北大学第5章存储管理内存信息的共享与保护访问方式保护(保护键)《操作系统原理》——东北大学第5章存储管理内存信息的共享与保护界限寄存器与CPU状态(用户态、核心态)相结合用户态进程只能访问界限寄存器所规定范围内的内存;核心态进程可以访问整个内存地址空间存储器扩充使用虚存或自动复盖技术提供比实际内存更大的空间存储器的逻辑组织和物理组织由应用程序控制:覆盖由OS控制:交换(整个进程空间),虚拟存储的请求调入和预调入(部分进程空间)《操作系统原理》——东北大学第5章存储管理主要内容存储管理的功能与目标分区存储管理分区管理的基本原理固定分区动态分区动态分区分配算法覆盖与交换技术页式与段式存储管理机制虚拟存储器(重中之重)《操作系统原理》——东北大学第5章存储管理分区管理的基本原理原理把内存分为一些大小相等或不等的分区(partition),每个应用进程占用一个或几个分区.
操作系统占用其中一个分区特点适用于多道程序系统和分时系统支持多个程序并发执行难以进行内存分区的共享问题可能存在内存片和外碎片内碎片:占用分区之内未被利用的空间外碎片:占用分区之间难以利用的空闲分区《操作系统原理》——东北大学第5章存储管理分区管理的基本原理分区管理使用的数据结构分区说明表,分区链表可以值记录空闲分区,也可以同时记录空闲和占用分区分区表中,表项数目随着内存的分配和释放而动态改变,可以规定最大表项数目分区表可以划分为两个表格:空闲分区表,占用分区表.
从而减小每个表格的长度空闲分区表中按不同分配算法相应对表项排序《操作系统原理》——东北大学第5章存储管理固定分区原理把内存区固定地划分为若干个大小相等(和不等)的连续分区.
每个分区装一个且只能装一个作业原则分区一旦划分,整个执行过程中每个分区的长度和内存中总的分区数不变将每个进程指定到适应它的最小分区数据结构:分区说明表——记录分区的大小和使用情况《操作系统原理》——东北大学第5章存储管理固定分区《操作系统原理》——东北大学第5章存储管理固定分区进程的放置算法固定分区的进程队列:多队列适用大小不等的固定分区;单队列适用于大小相同的固定分区,也可用于大小不等的情况《操作系统原理》——东北大学第5章存储管理固定分区固定分区的评价优点易于实现,开销小缺点内碎片造成浪费(小作业不能有效利用分区空间)分区总数在系统生成时确定(固定),限制了系统的并发度可以和覆盖、交换技术配合使用《操作系统原理》——东北大学第5章存储管理动态分区基本思想内存不是预先划分好的,而是当作业装入时,根据作业的需求和内存空间的使用情况来决定是否分配若有足够的空间,则按需要分割一部分给进程否则令其等待主存空间评价优点:没有内碎片缺点:有外碎片《操作系统原理》——东北大学第5章存储管理动态分区分配算法分区分配算法寻找某个空闲分区,其大小需大于或等于程序的要求.
若是大于要求,则将该分区分割成两个分区,其中一个分区为要求的大小并标记为"占用",而另一个分区为余下部分并标记为"空闲"分区释放算法需要将相邻的空闲分区合并成一个空闲分区.
(这时要解决的问题是:合并条件的判断和合并时机的选择)《操作系统原理》——东北大学第5章存储管理动态分区分配算法最先匹配法(First-Fit)按分区的先后次序(分区按起始地址递增的顺序排列),从头查找,找到符合要求的第一个分区特点简单、快速分配.
该算法的分配和释放的时间性能较好,较大的空闲分区可以被保留在内存高地址但随着低地址分区不断划分而产生较多小分区,每次分配时查找时间开销会增大《操作系统原理》——东北大学第5章存储管理动态分区分配算法下次匹配法(Next-Fit)按分区的先后次序,从上次分配的分区起查找(到最后分区时再回到开头),找到符合要求的第一个分区该算法的分配和释放的时间性能较好,使空闲分区分布得更均匀,但较大的空闲分区不易保留《操作系统原理》——东北大学第5章存储管理动态分区分配算法最佳匹配法(Best-Fit)找到大小与要求相差最小的空闲分区(按空闲区大小从小到大的顺序排列)会形成较多外碎片,但是较大的空闲分区可以被保留最坏匹配法(Worst-Fit)找到最大的空闲分区(空闲分区按从大到小顺序排列)基本不留下小空闲分区,较大的空闲分区无法被保留《操作系统原理》——东北大学第5章存储管理动态分区分配算法《操作系统原理》——东北大学第5章存储管理采用最先适应法的内存分配变化过程动态分区分配算法《操作系统原理》——东北大学第5章存储管理动态分区分配算法《操作系统原理》——东北大学第5章存储管理动态分区分配算法不同分配算法分配16KB空间的过程《操作系统原理》——东北大学第5章存储管理动态分区分配算法动态分区时的回收与拼接《操作系统原理》——东北大学第5章存储管理上空闲区下空闲区上空闲区下空闲区上下相邻区都是空闲区上相邻区是空闲区下相邻区是空闲区上下相邻区都不是空闲区动态分区的问题碎片问题经过一段时间的分配回收后,内存中存在很多很小的空闲块.
它们每一个都很小,不足以满足分配要求;但其总和满足分配要求.
这些空闲块被称为碎片紧凑技术:通过在内存移动程序,将所有小的空闲区域合并为大的空闲区域《操作系统原理》——东北大学第5章存储管理动态分区的问题紧凑技术《操作系统原理》——东北大学第5章存储管理OSprocess1process3process6process910KB30KB14KB26KB80KB分区管理的基本原理解决碎片的主要思路——内存紧缩将各个占用分区向内存一端移动.
使各个空闲分区聚集在另一端,然后将各个空闲分区合并成为一个空闲分区对占用分区进行内存数据搬移占用CPU时间需要支持动态重定位的硬件支持紧缩时机:每个分区释放后,如果没有邻接空闲区但内存中有其他空闲区时,则马上进行拼接;或内存分配找不到满足条件的空闲分区时,而所有空闲区总容量却能满足需求量时,再进行拼接《操作系统原理》——东北大学第5章存储管理分区管理的优缺点优点简单缺点碎片问题内存利用率不高受分区大小或实际内存容量限制不利于程序段和数据段的共享《操作系统原理》——东北大学第5章存储管理Linux中的BuddySystem回顾固定分区和动态分区的问题固定分区:内碎片问题,分区数量限制并发度动态分区:管理复杂,外碎片问题《操作系统原理》——东北大学第5章存储管理Linux中的BuddySystem《操作系统原理》——东北大学第5章存储管理主要内容存储管理的功能与目标分区存储管理覆盖与交换技术页式与段式存储管理机制虚拟存储器(重中之重)《操作系统原理》——东北大学第5章存储管理覆盖技术(Overlay)当前的问题一个程序都已经太大,无法装入内存覆盖技术的原理把程序划分为若干个功能上相对独立的程序段不会同时执行的程序段共享同一块内存区域程序段先保存在磁盘上,当有关程序段的前一部分执行结束,把后续程序段调入内存,覆盖前面的程序段《操作系统原理》——东北大学第5章存储管理覆盖技术(Overlay)举例《操作系统原理》——东北大学第5章存储管理注:另一种覆盖方法:(100K)A(20K)占一个分区:20K;B(50K)、D(20K)和E(40K)共用一个分区:50K;F(30K)和C(30K)共用一个分区:30K;覆盖技术(Overlay)对覆盖技术的评价缺点对用户不透明,增加了用户负担.
编程时必须划分程序模块和确定程序模块之间的覆盖关系,增加编程复杂度从外存装入覆盖文件,以时间延长来换取空间节省优点覆盖不需要任何来自操作系统的特殊支持,所以覆盖通常限于用在微机和其他内存容量有限的或缺乏对更先进技术的硬件支持的系统中《操作系统原理》——东北大学第5章存储管理交换技术(Swapping)面临的问题如何增加系统的并发度交换技术的原理将暂时不能执行的程序送到外存中,从而获得空闲内存空间来装入新程序,或读入保存在外存中而满足条件的进程.
交换单位为整个进程的地址空间常用于多道程序系统或小型分时系统中,与分区存储管理配合使用《操作系统原理》——东北大学第5章存储管理交换技术(Swapping)对交换技术的评价优点增加并发运行的程序数目编写程序时不影响程序结构缺点换入和换出增加处理机开销程序整个地址空间都进行传送,没有考虑执行过程中地址访问的统计特性《操作系统原理》——东北大学第5章存储管理主要内容存储管理的功能与目标分区存储管理覆盖与交换技术页式与段式存储管理机制简单页式管理简单段式管理虚拟存储器(重中之重)《操作系统原理》——东北大学第5章存储管理简单页式管理无论是固定分区还是静态分区,无论是覆盖技术还是交换技术,都无法有效的解决内碎片和外碎片的问题是否存在一种办法,可以综合解决内碎片与外碎片问题《操作系统原理》——东北大学第5章存储管理简单页式管理基本原理将物理内存空间划分为固定大小的页面(Page)将程序的逻辑地址空间也划分为同样大小的页面程序加载时,分配其所需的所有页,这些页在物理内存中不必连续需要硬件支持实现地址映射《操作系统原理》——东北大学第5章存储管理简单页式管理举例《操作系统原理》——东北大学第5章存储管理简单页式管理举例《操作系统原理》——东北大学第5章存储管理简单页式管理需要记录哪些信息进程页表描述一个进程占用了哪些页,进程虚拟页面和物理页面映射《操作系统原理》——东北大学第5章存储管理简单页式管理整个系统维护一个物理页面表描述页面占用和空闲信息可用位示图或链表来实现整个系统维护一个请求表记录哪些进程请求了哪些页面《操作系统原理》——东北大学第5章存储管理进程号请求页面数页表始址页表长度状态简单页式管理中的地址转换给定一个进程虚拟地址空间的地址,如何找到该地址在物理内存中的实际位置LOAD0035H地址结构《操作系统原理》——东北大学第5章存储管理简单页式管理中的地址转换《操作系统原理》——东北大学第5章存储管理81C4简单页式管理中的地址转换硬件支持页表起始地址寄存器页表长度寄存器(越界控制)映射机制的硬件实现《操作系统原理》——东北大学第5章存储管理多级页表如果在使用时,进程页表需要载入内存,怎么办页表本身也需要占用物理内存页面页表太大怎么办多级页表页表的页表《操作系统原理》——东北大学第5章存储管理多级页表《操作系统原理》——东北大学第5章存储管理第0个页表页第1023个页表页多级页表二级页表地址映射对逻辑地址的解析方法不同映射过程不同为访问一个数据,需要几次内存访问一级页表也需要放入内存,怎么找到《操作系统原理》——东北大学第5章存储管理页目录表控制寄存器多级页表如果不够,还可建立更多级别的页表《操作系统原理》——东北大学第5章存储管理简单页式管理的优缺点优点改善了空间使用效率(每个进程的内碎片不超过页面大小,无外碎片)程序可以不必连续存放程序所需空间可以动态改变缺点程序需要一次性全部放入内存(仅对于简单页式管理)不易于共享(进程间不能共享页表)不易于动态链接(两个模块的内容可能位于同一页面)《操作系统原理》——东北大学第5章存储管理主要内容存储管理的功能与目标分区存储管理覆盖与交换技术页式与段式存储管理机制简单页式管理简单段式管理虚拟存储器(重中之重)《操作系统原理》——东北大学第5章存储管理简单段式管理引入目的便于共享数据、程序;便于动态链接原理将程序的地址空间按内容或函数关系划分为若干个段,每个段是一组逻辑上完整的程序或数据特点段与段之间可以不连续段长不固定物理内存需要采用动态分区管理(问题也一并引入)在简单段式管理中,所有段必须在程序执行时都载入《操作系统原理》——东北大学第5章存储管理简单段式管理《操作系统原理》——东北大学第5章存储管理简单段式管理需要的数据结构进程段表:记录所有段的段基址和段长度系统段表:系统内所有的段空闲段表:所有空闲段《操作系统原理》——东北大学第5章存储管理简单段式管理《操作系统原理》——东北大学第5章存储管理段表起始地址段表地址寄存器虚拟地址11C4段号段内地址段表段号始址0150013400内存段式管理举例《操作系统原理》——东北大学第5章存储管理在一个段式存储管理系统中,其段表为:段号内存起始地址段长02105001235020210090313505904193895求下述逻辑地址对应的物理地址是什么段号段内位移0430110250034004112(210+430=640)(2350+10=2360)非法1350+400=1750非法页式管理与段式管理的比较《操作系统原理》——东北大学第5章存储管理项目页式管理段式管理设计目的解决碎片问题解决数据共享问题出发点物理空间的划分与管理依据程序逻辑划分尺寸大小固定大小不固定地址映射通过"页号+页内偏移"拼接而来的通过"段基址+段内偏移"相加得到的尽管很少有系统直接使用简单页式和简单段式管理,但是这两种机制是实现虚拟存储器的基础主要内容存储管理的功能与目标分区存储管理覆盖与交换技术页式与段式存储管理机制简单页式管理简单段式管理虚拟存储器(重中之重)虚拟存储器的基本原理虚拟页式、虚拟段式、段页式管理页面置换算法《操作系统原理》——东北大学第5章存储管理虚拟存储器基本原理目前已经讲过的方法存在的问题程序执行时,所需指令和数据必须一次性全部调入内存系统的并发性受到物理内存大小的影响进程之间共享数据困难《操作系统原理》——东北大学第5章存储管理虚拟存储器基本原理为解决上述问题,需要一种机制在程序装入时,不必将其全部读入到内存,而只需将当前需要执行的部分页或段读入到内存,就可让程序开始执行在程序执行过程中,如果需执行的指令或访问的数据尚未在内存(称为缺页或缺段),则由处理器通知操作系统将相应的页或段调入到内存,然后继续执行程序另一方面,操作系统将内存中暂时不使用的页或段调出保存在外存上,从而腾出空间存放将要装入的程序以及将要调入的页或段《操作系统原理》——东北大学第5章存储管理虚拟存储器基本原理引入虚拟存储器的好处程序的大小将不受物理内存大小的限制因为每个进程占用的内存减少了,系统的并发度得到了提高部分调入可能使得需要载入内存的数据减少(用不到的数据不调入),从而进一步提高系统性能无需编程人员介入(对比覆盖技术)《操作系统原理》——东北大学第5章存储管理虚拟页式机制以简单页式管理为基础,增加请求调页的功能工作原理在进程开始运行之前,不是装入全部页面,而是装入部分页面,之后根据进程运行的需要,动态装入其它页面;当内存空间已满,而又需要装入新的页面时,则根据某种算法淘汰某个页面,以便装入新的页面三个主要问题缺页是如何产生并让系统知道的如果内存页面不足,应该怎么处理调入所需页面的时机《操作系统原理》——东北大学第5章存储管理虚拟页式机制对进程页表的修改标志位:(驻留位)页面在内存还是外存修改位(modifiedbit):数据是否被修改过访问统计:在近期内被访问的次数,或最近一次访问到现在的时间间隔外存地址:如果在外存,地址多少《操作系统原理》——东北大学第5章存储管理页号页面号驻留位外存地址访问位修改位虚拟页式机制缺页中断在地址映射过程中,在页表中发现所要访问的页不在内存,则产生缺页中断操作系统接到此中断信号后,就调出缺页中断处理程序,根据页表中给出的外存地址,将该页调入内存,使作业继续运行下去如果内存中有空闲块,则分配一页,将新调入页装入内存,并修改页表中相应页表项目的驻留位及相应的内存块号若此时内存中没有空闲块,则要淘汰某页,若该页在内存期间被修改过,则要将其写回外存《操作系统原理》——东北大学第5章存储管理虚拟页式机制调入所需页面的时机请求调入:当需要执行某条指令而又发现它不在内存时,或当执行某条指令需要访问其他的数据或指令时,这些指令和数据不在内存中,从而发生缺页中断(主要讨论)预调入:系统对那些在外存中的页进行调入顺序计算,估计出这些页中指令和数据的执行和被访问的顺序,并按此顺序将它们顺次调入和调出内存《操作系统原理》——东北大学第5章存储管理虚拟页式机制虚拟页式管理的优缺点优点支持一个进程的数据在内存中非连续存放实现了虚存缺点增加了系统开销,如缺页中断的处理请求调页算法如果不当,可能产生抖动现象《操作系统原理》——东北大学第5章存储管理抖动现象进程运行中,刚刚被淘汰的页很快被重新调入,调入不久又被再次淘汰,如此反复,以致大部分机器时间都用于页面调度,只有小部分时间用于进程的实际运行工作集模型一个进程在某一小段时间内访问页面的集合.
用WS(ti,)表示ti-到ti之间所访问的不同页面,则WS(ti,)即为进程在时间ti的工作集《操作系统原理》——东北大学第5章存储管理抖动每个进程的工作集大小为WSSi,则系统中全部进程对内存块的总请求量可表示为如果D大于可用内存块的总量m(Dm),可能出现抖动防止抖动操作系统监督每个进程的工作集,并给它分配工作集所需的内存块.
若有足够多的额外块,即可装入另外的进程;若工作集增大,超出可用块的总数,操作系统要选择一个进程挂起,将其页面换出,把内存分配给其它进程《操作系统原理》——东北大学第5章存储管理虚拟段式机制在简单段式管理基础上,增加请求调段和段置换功能对段表的扩充标志位:段在内存还是外存修改位:段的内容是否被修改增长位(该段是否增长过,在虚拟页式中没有该位)访问统计信息存取权限:R,W,X外存地址《操作系统原理》——东北大学第5章存储管理虚拟段式机制地址映射《操作系统原理》——东北大学第5章存储管理段表始址3400内存虚拟段式机制虚拟段式管理的优缺点优点可以实现虚存段长可动态改变便于信息共享和动态链接缺点每个段的长度仍旧受到物理内存大小的限制《操作系统原理》——东北大学第5章存储管理段页式机制能否有一种办法,把虚拟页式和虚拟段式的优点结合起来段页式的原理程序的虚拟地址空间分两个层次首先,根据程序语义划分成若干个段对于每个段内部,采用页式管理逻辑地址的组成:段号、页号、页内偏移地址变换:先查段表,后查页表《操作系统原理》——东北大学第5章存储管理段页式机制《操作系统原理》——东北大学第5章存储管理第2段页表段页式机制《操作系统原理》——东北大学第5章存储管理MainMemoryPageFrameOffsetPagingPageTable+Frame#OffsetSegTablePtr+SegmentationProgramSegmentTableSeg#Page#Offset高速联想寄存器(TLB)本质上是地址转换硬件中的一个小型存储器,用于缓存段表和页表,从而减少对内存的访问次数《操作系统原理》——东北大学第5章存储管理存储管理技术的发展《操作系统原理》——东北大学第5章存储管理程序处理系统处理连续存放不连续存放整体调入部分调入(段)页式管理中的分配与置换固定分配,局部置换为每个进程分配固定数量的页面,运行期间不变若进程缺页,只能替换该进程在内存中的某个页面为每个进程分配的内存块数量难以确定可变分配,全局置换首先为每个进程分配一定数量的物理内存页面,系统维护空闲页面进程缺页时,系统从全局的空闲队列中取一个页面分配给进程仅当空闲队列为空时,操作系统选择一个内存中的页面被替换掉《操作系统原理》——东北大学第5章存储管理(段)页式管理中的分配与置换可变分配,局部置换先为进程分配一定数量页面,缺页时,首先从进程自身替换若频繁发生缺页中断,则为进程附加分配一些物理页面,直至缺页减少若进程缺页很少,在不引起其缺页率明显增加的情况下,适当减少分配给该进程的页面数量《操作系统原理》——东北大学第5章存储管理页面置换算法功能如需要替换某个页面到外存,应该选择谁目标:把未来不使用或短期内不使用的页替换出去常见置换算法最佳算法最近最久未使用算法先进先出算法轮转法最不常用算法《操作系统原理》——东北大学第5章存储管理最佳置换算法基本原理选择"未来不再使用的"或"在离当前最远位置上"的页面被置换这只是一种理想情况,现实世界中,无法预知未来,因为这个算法是无法实现的可作为性能评价的依据在已知(后知后觉)一种执行路径的情况下《操作系统原理》——东北大学第5章存储管理最佳置换算法《操作系统原理》——东北大学第5章存储管理主存4321435432154一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率主存43214354321543最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率主存432143543215432最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率432143543215主存4321最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率432143543215主存431最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率432143543215主存431最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率432143543215主存4315最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率432143543215主存435最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率432143543215主存435最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率432143543215主存4352最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率432143543215主存3521最佳置换算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算采用最佳算法时的缺页率432143543215主存521缺页率=7/12最近最久未使用算法原理选择内存中最久未使用的页面进行置换问题是,为记录页面使用情况,硬件开销大硬件支持(寄存器法)为每个内存中的页面配置R=Rn-1Rn-2…R1R0进程访问某页时,将该页的Rn-1置1定时信号每隔一定时间右移一位寄存器R被视为一个整数,置换时,具有最小数值的寄存器对应的页面被淘汰《操作系统原理》——东北大学第5章存储管理最近最久未使用算法硬件支持(堆栈法)利用一个堆栈保存当前使用的各页面的页面号进程访问某页面时,将该页面的页面号从栈中移出,压入栈顶置换时,栈底页面被淘汰堆栈的深度=内存页面数量(无法真正实现)《操作系统原理》——东北大学第5章存储管理最近最久未使用算法《操作系统原理》——东北大学第5章存储管理一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,分配给该作业的物理块数为3,计算LRU算法时的缺页率432143543215栈状态先进先出算法(FIFO)基本原理与特点模拟LRU算法选择建立最早、在内存驻留时间最长的页面被置换会出现Belady异常现象较早调入的页往往是经常被访问的页,这些页在FIFO算法下被反复调入和调出Belady现象(异常)采用FIFO算法时,如果对一个进程未分配它所要求的全部页面,如果分配的页面数增多,有可能缺页率反而提高《操作系统原理》——东北大学第5章存储管理先进先出算法(FIFO)《操作系统原理》——东北大学第5章存储管理进程P有5页程序,访问页的顺序为:1,2,3,4,1,2,5,1,2,3,4,5;如果在内存中分配3个页面,则缺页情况如下:12次访问中有缺页9次;FIFO123412512345先进先出算法(FIFO)《操作系统原理》——东北大学第5章存储管理如果在内存中分配4个页面(增加一个),则缺页情况如下:12次访问中有缺页10次;FIFO123412512345时钟置换算法基本原理是LRU的一种近似算法为每页设置一个访问位,将内存中所有页面链接成一个循环队列(亦可隐式表达)某页被访问时,其访问位被置1置换时,检查各页的访问位,0可被置换,1则将其置0按照固定顺序检查各页面《操作系统原理》——东北大学第5章存储管理时钟置换算法43214354321541《操作系统原理》——东北大学第5章存储管理119时钟置换算法43214354321541《操作系统原理》——东北大学第5章存储管理120时钟置换算法43214354321541《操作系统原理》——东北大学第5章存储管理121时钟置换算法43214354321541000《操作系统原理》——东北大学第5章存储管理122时钟置换算法43214354321541000《操作系统原理》——东北大学第5章存储管理123时钟置换算法43214354321541000《操作系统原理》——东北大学第5章存储管理124时钟置换算法43214354321541000《操作系统原理》——东北大学第5章存储管理125时钟置换算法43214354321541000000《操作系统原理》——东北大学第5章存储管理126时钟置换算法4321435432154100000011《操作系统原理》——东北大学第5章存储管理127时钟置换算法4321435432154100000011000《操作系统原理》——东北大学第5章存储管理128时钟置换算法4321435432154100000011000《操作系统原理》——东北大学第5章存储管理129时钟置换算法43214354321541000000110001《操作系统原理》——东北大学第5章存储管理130时钟置换算法与LRU代价对比共同点为每个内存块开辟空间,记录访问信息额外开销LRU为严格记录对内存块的访问次序,需要将所有内存块排序如果内存块数量很大,用来记录信息的空间就大访问一次内存,理论上所有内存块的信息都改变时钟置换算法实现中可以不对所有内存块排序所以每个内存块固定耗费1bit的空间记录信息访问一次内存,大多数时候仅改变一个内存块的信息《操作系统原理》——东北大学第5章存储管理改进型时钟置换算法设置访问位A和修改位M根据访问位和修改位的取值,把内存页面分成几类第1类(A=0,M=0):未被访问,未被修改,最佳淘汰页第2类(A=0,M=1):未被访问,被修改,淘汰页第3类(A=1,M=0):被访问,未被修改,可能再访问第4类(A=1,M=1):被访问,被修改,可能再访问置换算法STEP1:查找第1类的,如果找到,淘汰一页;STEP2:如果找不到第1类的,淘汰第2类的;查找过程中,将所有查找过的页面的A置为0STEP3:如果找不到第2类的,将所有页面的A复位为0,重复第1步《操作系统原理》——东北大学第5章存储管理最不常用算法基本思想选择到目前为止被访问次数最少的页面进行置换每页设置访问计数器,当每页被访问时,计数器加1发生缺页中断时,淘汰计数器值最小的页面,并将所有计数器清零《操作系统原理》——东北大学第5章存储管理存储管理习题(1)《操作系统原理》——东北大学第5章存储管理请求分页管理系统中,假设某进程的页表内容如下表所示:页号页框(pageframe)号有效位(存在位)0101H11-02254H1页面大小为4KB,一次内存的访问时间是100ns,一次快表(TLB)的访问时间是10ns,处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间),进程的驻留集大小固定为2,采用最近最少使用置换算法(LRU)和局部淘汰策略.
假设,①TLB初始为空;②地址转换时先访问TLB,若TLB未命中,再访问页表(忽略访问页表之后的TLB更新时间);③有效位为0表示页表不在内存,产生缺页中断,缺页中断处理后,返回到产生缺页中断的指令处重新执行.
设有虚地址访问序列2362H、1565H、25A5H,请问:(1)依次访问上述三个虚地址,各需要多少时间,给出计算过程;(2)基于上述访问序列,虚地址1565H的物理地址是多少请说明理由.
存储管理习题(1)《操作系统原理》——东北大学第5章存储管理解答页面大小为4KB,所以2362H、1565H、25A5H对应的页号分别为2、1、2,根据页表内容,2362H、25A5H在内存,1565H不在内存.
初始快表为空,故2362H需装入快表,25A5H直接访问快表,1565H需装入内存,再装入快表.
据此:2362H:10(访TLB)+100(访页表)+100(访主存单元)=210ns1565H:10(访TLB)+100(访页表)+108(调页)+10(访TLB)+100(访主存单元)=100000220ns25A5H:10(访TLB)+100(访主存单元)=110ns根据页表,第0、2页在内存中,由于第2页刚刚被访问(访问2362H),根据LRU算法,将第0页替换,因此对应页框号为101H,故1565H的物理地址为101565H.

存储管理习题(2)《操作系统原理》——东北大学第5章存储管理在一采取局部置换策略的请求分页系统中,分配给某个作业的内存块数为4,其中存放的4个页面的情况如表所示:上面所有时间均是从进程开始运行时从0开始计时的时钟数,如果系统采用:(1)FIFO算法;(2)LRU算法;(3)改进的Clock算法,将选择哪一页换出存储管理习题(3)《操作系统原理》——东北大学第5章存储管理设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址.
若进程最多需要6页存储空间,页的大小为1KB,操作系统若采用固定分配局部置换策略为该进程分配4个页面.
在时刻260前的该进程访问情况如表所示(访问位即使用位)页号页面号装入时间访问位071301142301222001391601在260时刻,要访问逻辑地址为17CAH的数据,请回答:1、逻辑地址对应的页号是多少2、若采用先进先出置换算法,该逻辑地址对应的物理地址是多少给出计算过程.

3、若采用时钟置换算法,该逻辑地址对应的物理地址是多少给出计算过程.
设顺时针搜索下一页,且当前指向2号页面,示意图如下.

存储管理习题(4)《操作系统原理》——东北大学第5章存储管理在一个请求分页管理存储系统中,一个程序的页面走向为4,3,2,1,4,3,5,4,3,2,1,5,并采用LRU页面置换算法.
设分配给该程序的存储块数为M,当M分别为3和4时,试求出在访问过程中缺页中断的次数和缺页率,并比较两种结果,从中可以得到什么启示存储管理习题(4)《操作系统原理》——东北大学第5章存储管理432143543215432143543215存储管理习题(5)某系统采用动态分区管理内存,内存空间为640K,高端40K存放操作系统.
内存分配时,系统优先使用空闲区低端的空间.
对下列请求序列:作业1申请130K,作业2申请60K,作业3申请100K,作业2释放60K,作业4申请200K,作业3释放100K,作业1释放130K,作业5申请140K,作业6申请60K,作业7申请50K,作业6释放60K,请分别画出使用首次适应算法和最佳适应算法进行内存分配和回收后内存的实际使用情况.