操作系统章存储器管理

2024/1/61操作系统第四章存储器管理院(系):计算机科学与技术学院研究室:软件支持技术教师:王红滨2024/1/62内存(MainMemory或PrimaryMemory或RealMemory)也称主存,是指CPU能直接存取指令和数据的存储器。图内存在计算机系统中的地位2024/1/63内容概述4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式

存储器是计算机系统重要的组成部分,虽然存储器的容量不断扩大,但仍不能满足要求,因此存储器管理是操作系统的重要工作,存储器管理的主要内容是内存。存储器是用来存放系统和用户的程序和数据,其特点是存取速度快,存储方式是以新换旧,断电信息丢失。2024/1/644.1程序的装入和链接4.1.1程序的装入4.1.2程序的链接2024/1/654.1程序的装入和链接图4-2对用户程序的处理步骤多道程序环境下,程序要运行必须为之创建进程,而创建进程的第一件事就是分配内存源程序要运行通常经过编译(compile)

链接(link)

装入(load)等几个步骤2024/1/66(1)编译。 由编译程序将用户源代码编译成若干个目标模块。(2)链接。由链接程序将编译后形成的目标模块以及它们所需要的库函数,链接在一起,形成一个装入模块。(3)装入。由装入程序将装入模块装入主存的过程。2024/1/674.1.1程序的装入1.绝对装入方式2.可重定位装入方式3.动态运行时装入方式2024/1/681.绝对装入方式(AbsoluteLoadingMode)(适合“单道”)在编译时,如果知道程序将驻留在内存的什么位置,则编译程序产生绝对地址的目标代码装入模块被装入内存后,由于程序中的逻辑地址与实际内存地址完全相同,故不需对程序和数据的地址进行修改程序中所使用的绝对地址,既可在编译或汇编时给出,也可由程序员直接赋予。但在由程序员直接给出绝对地址时,不仅要求程序员熟悉内存的使用情况,而且一旦程序或数据被修改后,可能要改变程序中的所有地址。因此,通常是宁可在程序中采用符号地址,然后在编译或汇编时,再将这些符号地址转换为绝对地址。2024/1/692024/1/6102.可重定位装入方式(RelocationLoadingMode)(可用于“多道”)绝对装入方式只能将目标模块装入到内存中事先指定的位置在多道程序环境下,不可能预知目标模块放在内存中的地址,因此绝对装入方式不适合在多道环境下使用程序中目标模块的地址通常从0开始,其他地址都是相对于0计算把在装入时对目标程序中指令和数据的修改过程称为重定位,又因为地址变换通常是在装入时一次完成的,以后不再改变,故称为静态重定位。静态重定位特点:简单、不能在内存中移动、要求连续。2024/1/611图4-3作业装入内存时的情况125002024/1/612如何将程序在内存中从10000移动到20000？225002024/1/6133.动态运行时装入方式(DenamicRun-timeLoading)(可用于“多道”)可重定位方式不允许程序运行时在内存中移动位置装入程序,在把装入模块装入内存后,并不立即把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正要执行时才进行。因此,装入内存后的所有地址都仍是相对地址,依靠硬件支持进行地址转换。动态重定位特点:在内存中可移动。2024/1/6144.1程序的装入和链接4.1.1程序的装入4.1.2程序的链接2024/1/6154.1.2程序的链接1.静态链接方式(StaticLinking)在程序运行前,先将各目标模块及所需的库函数链接成一个完整的装入模块,以后不再拆开在将这几个目标模块装配成一个装入模块时,须解决以下两个问题

(1)对相对地址进行修改

(2)变换外部调用符号2024/1/616图4-4程序链接示意图相对地址外部调用符号2024/1/6172.装入时动态链接(LoadtimeDynamicLinking)

将用户的源程序编译后所得的一组目标模块在装入内存时采用边装入边链接的方式优点:(1)便于目标模块的修改和更新

(2)便于实现对目标模块的共享2024/1/6182024/1/6193.运行时动态链接(Run-timeDynamicLinking)

应用程序在每次运行的模块可能不相同,出错模块不一定什么时候运行。运行时动态链接方式将对某些模块的链接推迟到执行时才去做,即在执行过程中,当发现一个被调用模块尚未装入内存时,立即由OS去找到该模块并将之装入内存,把它链接到调用者模块上凡在执行过程中未被用到的目标模块,都不会被调入内存和被链接到装入模块上,这样不仅可加快程序的装入过程,而且可节省大量的内存空间2024/1/6202024/1/621内容概述4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式2024/1/6224.2连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4伙伴系统4.2.5哈希算法4.2.6可重定位分区分配4.2.7对换(Swapping)2024/1/6234.2.1单一连续分配连续分配方式为一个用户程序分配一个连续的内存空间单一连续分配是最简单的一种存储管理方式,但只能用于单用户、单任务的操作系统中采用这种存储管理方式时,可把内存分为系统区和用户区两部分,系统区仅提供给OS使用,通常是放在内存的低址部分;用户区是指除系统区以外的全部内存空间,提供给用户使用一般情况下无存储器保护机构(早期有)特点:(1)简单易行,系统开销小

(2)资源利用率低(一次只能装入一个作业)2024/1/624图单一连续分配系统区用户区2024/1/6254.2连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4伙伴系统4.2.5哈希算法4.2.6可重定位分区分配4.2.7对换(Swapping)2024/1/6264.2.2固定分区分配最简单的可运行多道程序的存储管理方式将内存用户空间划分为若干个固定大小的区域,每个分区中只装入一道作业1.划分分区的方法(1)分区大小相等即使所有的内存分区大小相等分区太大浪费分区太小不够用(2)分区大小不等划分为多个大、中、小搭配的分区根据程序大小决定所使用的分区大班在大教室、小班在小教室2024/1/627图4-5固定分区使用表2.内存分配按分区使用表进行分配,依分区大小排序。20未分区使用表2K作业2024/1/628图固定分区分配2024/1/629管理特点(1)一个作业只能装入一个分区,不能装入两个或多个相邻的分区。一个分区只能装入一个作业,当分区大小不能满足作业的要求时,该作业暂时不能装入。(2)通过对“分区使用表”的改写,来实现主存的分配与回收。作业在执行时,不会改变存储区域,所以采用静态地址重定位方式。此方法易于实现,系统开销小。(3)当分区较大作业较小时,仍然浪费许多主存空间,很难避免内部碎片。并且分区总数固定,限制了并发执行的作业数目。2024/1/6304.2连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4伙伴系统4.2.5哈希算法4.2.6可重定位分区分配4.2.7对换(Swapping)2024/1/631图动态分区分配内存使用情况示意图4.2.3动态分区分配可变分区分配2024/1/632根据进程的实际需要,动态地为之分配内存空间1.分区分配中的数据结构空闲分区表:记录每个空闲分区的情况…2024/1/633图4-6空闲链结构1.分区分配中的数据结构…空闲分区链实现对空闲分区的分配和链接状态0为空闲可用1为已分配分区大小2024/1/634为什么作业4分配到352KB地址空间上？2024/1/6352.分区分配算法(1)首次适应算法FF空闲分区链以地址递增顺序链接分配时从链首开始查找,找到一个大小可满足的空闲分区,划出一块给请求者可能会造成在低地址部分很多难以利用的小空闲分区优点:(1)分配算法简单(2)优先利用低址部分,保留了高址的大空闲区,为大作业装入提供条件。缺点:每次从链首开始,增加了查找开销,并且留下许多难以利用的”碎片”(外碎片)2024/1/6362.分区分配算法(1)首次适应算法FF(2)循环首次适应算法该算法是由首次适应算法演变而成的空闲分区链以地址递增顺序链接,链表为循环链表每次分配时从上一次找到空闲分区的下一个空闲区开始优点:使空闲分区分布均匀,减少查找空闲分区开销缺点:会缺乏大的空闲分区2024/1/6372.分区分配算法(1)首次适应算法FF(2)循环首次适应算法(3)最佳适应算法每次分配时,把能满足要求、又是最小的分区分配给作业空闲分区链以大小递增顺序链接从头开始,第一次找到满足要求的空闲分区,必然是最优的,避免了“大材小用”宏观上看,会在存储器中留直许多难以利用的小分分区特点:解决了大作业的分配问题;每次总是最小的,容易产生不可利用的空闲区(“小碎片”);收回主存时,要按分区大小递增顺序插入到空闲区表中。2024/1/6382.分区分配算法(1)首次适应算法FF(2)循环首次适应算法(3)最佳适应算法(4)最差(坏)适应算法每次分配时,把能满足要求、又是最大的分区分配给作业空闲分区链以大小递减顺序链接可以保证不出现太小的“碎片”特点:不会产生过多的碎片;影响大作业的分配;收回主存时,要按大小递减的顺序插入到空闲区表中。2024/1/6392.分区分配算法(1)首次适应算法FF(2)循环首次适应算法(3)最佳适应算法(4)最差(坏)适应算法(5)快速适应算法(分类搜索法)按照分区大小设置多个空闲分区链，增加一个索引表，可以快速对应到一个空闲分区链上。空闲分区链分类：常用的大小分类，如2KB,4KB,8KB特点:分配速度快,不进行分区分割;存在一定的主存浪费;典型的以空间换时间的作法。2024/1/6403.分区分配操作1)分配内存图4-7内存分配流程需求大小空闲大小2024/1/641图4-8内存回收时的情况2)回收内存进程运行完释放内存时,系统根据回收区的首地址,从空闲链表区找到相应的插入点,有以下几种情况回收区与插入点的前一个空闲分区相邻接回收区与插入点的后一个空闲分区相邻接

回收区同时与插入点的前、后两个分区相邻接回收区不与任何空闲区邻接2024/1/642图动态分区分配方式中释放一个分区的流程不标准的流程图2024/1/643管理特点分区的长度不是预先固定的,而是按作业的实际需求来划分的。分区的个数也不是预先确定的,而是由装入的作业数决定的。分区的大小由作业的大小来定,提高了主存的使用效率。在主存分配过程中,会产生许多“外碎片”。“外碎片”是指小的无法使用的主存空间。使主存空间仍有一定的浪费。2024/1/6444.2连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4伙伴系统4.2.5哈希算法4.2.6可重定位分区分配4.2.7对换(Swapping)2024/1/6454.2.4伙伴系统1.伙伴算法原理2.伙伴算法实例3.伙伴算法结论2024/1/6461.伙伴算法原理Linux采用伙伴(buddy)算法对物理内存进行管理通过不断地平分较大的空闲内存块来获得较小的空闲内存块，直到获得所需的内存块；当内存释放时，尽可能的合并空闲内存块。其中内存块分配与合并都采用以2的幂次方为单位。所谓“伙伴”，就是指在空闲块被分裂时，由一个大块内存分裂出来的两个小块内存,互称“伙伴”算法采用位图和空闲链表作为辅助工具，其中位图用来跟踪内存块的使用情况，空闲链表用来维护内存中没有使用的内存块2024/1/6472.伙伴算法实例

用伙伴算法管理一个64KB内存，要求最小的分配请求单元是2KB

内存的每个分配单元是2KB，设置位图中的每一位对应其中的每一个分配单元，“1”表示占用，“0”表示未占用，空闲链表对应于64KB的容量，共６项2024/1/648图伙伴算法2KB4KB8KB16KB32KB64KB00000000000000000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表初始状态2KB2024/1/6492.伙伴算法实例 续假设请求需要分配8KB的内存算法先将64KB分为内存32KB的A和A’，再将A分为内存为16KB的B和B’，然后再将B分为内存8KB的C和C’且在此过程中将A’，B’，C’分别加入到相应大小的空闲链表中，最后将起始为０的地址块C返回给用户,将位图相应的位置置1完成分配任务2024/1/650图伙伴算法2KB4KB8KB16KB32KB64KB00000000000000000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表初始状态2KB2024/1/651图伙伴算法2KB4KB8KB16KB32KB64KB00000000000000000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表整个内存分成A和A’A’A申请8KB2024/1/652图伙伴算法2KB4KB8KB16KB32KB64KB00000000000000000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表A分成B和B’A’BB’申请8KB2024/1/653图伙伴算法2KB4KB8KB16KB32KB64KB00000000000000000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表B分成C和C’A’CB’申请8KBC’分配C给用户2024/1/654图伙伴算法2KB4KB8KB16KB32KB64KB00000000000011110000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表B分成C和C’A’CB’申请8KBC’分配C给用户2024/1/6552.伙伴算法实例 续假设接下来又要申请一个2KB的空间，算法执行过程如下：首先检查空闲链表，若发现2KB的空闲链表为空，那么算法将上面的块C’分成大小为4KB的D和D’，D分为2KB的E和E’，其中D’和E’分别加入到4KB和2KB的空闲链表中，最后将E返回给用户，将位图中的相应位置置为12024/1/656图伙伴算法2KB4KB8KB16KB32KB64KB00000000000011110000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表B分成C和C’A’CB’申请2KBC’2024/1/657图伙伴算法2KB4KB8KB16KB32KB64KB00000000000011110000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表C’分成D和D’A’CB’申请2KBD’D2024/1/658图伙伴算法2KB4KB8KB16KB32KB64KB00000000000011110000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’CB’申请2KBD’EE’分配E给用户2024/1/659图伙伴算法2KB4KB8KB16KB32KB64KB00000000000111110000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’CB’申请2KBD’EE’分配E给用户2024/1/660

如果用户又要申请一个大小为16KB的内存空间，算法的执行过程同上，但这时搜索空闲链表时，发现正好有一个16KB的空闲块，该算法首先从16KB的空闲链表中删除B’，并将B’的地址返回给用户，同时将位图相应位置“1”2.伙伴算法实例 续2024/1/661图伙伴算法2KB4KB8KB16KB32KB64KB00000000000111110000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’CB’申请16KBD’EE’2024/1/662图伙伴算法2KB4KB8KB16KB32KB64KB11111111000111110000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’CB’申请16KBD’EE’分配B’给用户2024/1/6632.伙伴算法实例 续伙伴算法如何释放内存的呢？假设首先被释放的是大小为8KB的C块，算法首先检查C’，C’正处于使用状态，不会合并，因此算法将C块加入到8KB的空闲链表中。算法释放内存时，其相应的位图会被清零。2024/1/664图伙伴算法2KB4KB8KB16KB32KB64KB11111111000111110000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’CB’释放8KB的C块D’EE’C’正处于使用状态无法合并C’2024/1/665图伙伴算法2KB4KB8KB16KB32KB64KB11111111000100000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’CB’释放8KB的C块D’EE’2024/1/6662.伙伴算法实例 续伙伴算法如何释放内存的呢？如果接下来又释放了大小为2KB的E块，发现伙伴E’空闲，将E和E‘合并，得到大小为4KB的D块，又发现D的伙伴D’空闲，合并得到大小为8KB的C‘块，又发现C’的伙伴C处于空闲状态，将C和C‘合并，并添加到16KB的空闲链表中。算法释放内存时，其相应的位图会被清零。2024/1/667图伙伴算法2KB4KB8KB16KB32KB64KB11111111000100000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’CB’释放2KB的E块D’EE’2024/1/668图伙伴算法2KB4KB8KB16KB32KB64KB11111111000000000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’CB’释放2KB的E块D’EE’E’正处于空闲状态E和E’合并2024/1/669图伙伴算法2KB4KB8KB16KB32KB64KB11111111000000000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’CB’释放2KB的E块D’DD’正处于空闲状态D和D’合并2024/1/670图伙伴算法2KB4KB8KB16KB32KB64KB11111111000000000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’CB’释放2KB的E块C’C正处于空闲状态C和C’合并2024/1/671图伙伴算法2KB4KB8KB16KB32KB64KB11111111000000000000000000000000位图0KB8KB16KB32KB64KB内存块0KB8KB16KB32KB64KB空闲链表D’分成E和E’A’BB’释放2KB的E块2024/1/6723.伙伴算法结论当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i-1<n≤2i，在空闲分区大小为2i的空闲分区链表中查找，否则在2i+1找，等分后分配，依次类推。2024/1/6734.2连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4伙伴系统4.2.5哈希算法4.2.6可重定位分区分配4.2.7对换(Swapping)2024/1/6744.2.5哈希算法引入原因：上述的分类搜索法和伙伴系统中，都是把空闲分区进行分类，再查找这些分类的分区上会使时间性能下降。原理：哈希算法就是利用哈希快速查找的优点，对索引表进行快速查找。2024/1/6754.2连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4伙伴系统4.2.5哈希算法4.2.6可重定位分区分配4.2.7对换(Swapping)2024/1/6764.2.6可重定位分区分配图4-9紧凑的示意1.可重定位的引入连续分配存在的问题

必须有足够大的连续空间才能分配“拼接”或“紧凑”的引入来了31K程序2024/1/677缺点:(1)紧凑增加主机的开销

(2)紧凑修改空闲分区表移动条件:无内外存信息交换2024/1/678图4-10可重定位示意图2.可重定位的实现作业装入内存后的所有地址仍是相对地址,将相对地址转换成物理地址的工作在指令执行时进行地址变换过程是在程序执行期间,随着每条指令和数据的访问而自动进行的。真正访问地址=相对地址+重定位寄存器中地址需要有硬件地址变换机构的支持2024/1/6793.可重定位分区分配算法图4-11可分区分配算法流程图2024/1/680可重定位分区分配法的优缺点优点:可以消除碎片,能够分配更多的分区,有助于多道程序设计,提高内存的利用率。缺点:紧凑花费了大量CPU时间;2024/1/6814.2连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4伙伴系统4.2.5哈希算法4.2.6可重定位分区分配4.2.7对换(Swapping)2024/1/682图对换两个进程2024/1/6834.2.7对换(Swapping)1.对换的引入所谓“对换”,是指把内存中暂时不能运行的进程或者暂时不用的程序和数据,调出到外存上,以便腾出足够的内存空间,再把已具备运行条件的进程或进程所需要的程序和数据,调入内存。对换是提高内存利用率的有效措施如果对换是以整个进程为单位,称为“整体对换”或“进程对换”如果对换是以“页”或“段”为单位进行的,则称为“页面对换”或“分段对换”,又统称为“部分对换”,这种对换方法是实现请求分页及请求分段式存储器的基础,其目的是为了支持虚拟存储系统。2024/1/6842.对换空间的管理在具有对换功能的OS中,通常把外存分为文件区和对换区文件区管理的主要目标是提高文件存储空间的利用率,采取离散分配方式。外存中对换区主要存放从内存中换出的进程,对换空间管理的主要目标是提高进程换入和换出的速度。为了能对对换区中的空闲盘块进行管理,在系统中应配置相应的数据结构,以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似,即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项,即对换区的首址及其大小,它们的单位是盘块号和盘块数对换区的分配采用连续分配方式,分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法2024/1/6853.进程的换出与换入(1)进程的换出 ①选出被换出的进程选择原则:ⅰ先“阻塞”或“睡眠”的进程,后“就绪”

ⅱ优先级低的进程

ⅲ在内存最长的进程的进程换出

ⅳ最近最久未使用进程②进程换出过程系统首先选择处于“阻塞”状态且优先级最低的进程作为换出进程,然后启动盘块,将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误,便可回收该进程所占用的内存空间,并对该进程的进程控制块做相应的修改。2024/1/6863.进程的换出与换入(1)进程的换出(2)进程的换入系统应定时地查看所有进程的状态,从中找出(PCB集合中)“就绪”状态且已换出的进程,将其中换出时间(换出到磁盘上)最久的进程作为换入进程,申请内存,若成功将之换入,否则在换出某些进程,腾出足够内存,在换入。2024/1/687内容概述4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式

4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式2024/1/688离散分配方式连续分配方式要求为一个进程分配连续的内存空间(整体装入),分形成许多“碎片”而浪费,“紧凑”操作会付出相当大的代价如果允许一个进程直接分散地装入到许多不相邻接的分区中,称为离散分配方式离散分配方式有分页存储管理方式、分段存储管理方式和段页存储管理方式2024/1/689将用户作业的地址空间分成若干个大小相同的区域,称为页面或页,并为每个页从“0”开始编号;相应地,主存空间也分成与页大小相同的若干个存储块,或称为物理块或页框(frame),并且采用同样的方式为它们进行编号,从0开始:0块,1块,…,n-1块。以便将碎片限制在较小的范围内。不再需要进行空闲区域的合并拼接。程序的逻辑地址由页号和页内地址组成,页号的长度决定了分页的多少,页内地址的长度决定了页面的大小。在为作业分配主存时,以块为单位将作业中的若干页分别装入多个可以不相邻接的块中。作业执行时根据逻辑地址中的页号找到它所在的块号,再确定当前指令要访问的主存的物理地址。分页存储管理方式2024/1/690分页的概念程序地址空间分成大小相等的页面,同时把内存也分成与页面大小相等的块,当一个用户程序装入内存时,以页面为单位进行分配。页面的大小是为2n,通常为1KB,2KB,nKB等。2024/1/6914.3.1页面与页表4.3.2地址变换机构4.3.3两级和多级页表4.3基本分页存储管理方式2024/1/6924.3.1页面与页表1.页面1)页面和物理块分页存储管理,是将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或页,并为各页加以编号,从0开始,如第0页、第1页等也把内存空间分成与页面相同大小的若干个存储块,称为物理块或页框(frame),也同样为它们加以编号,如0＃块、1＃块等等在为进程分配内存时,以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片,称之为“页内碎片”由编译系统或用户2024/1/693图4-12页表的作用3.页表分页系统中,将进程的每一页离散地存储在内存的任一物理块中,为每个进程建立一张页面映像表,简称页表作用:是实现从页号到物理块号的地址映射。通常没有存页号,要连续分配2024/1/6942024/1/695

2)页面大小在分页系统中的页面其大小应适中,由硬件决定,即由机器的地址结构所决定。页面若太小,一方面虽然可使内存碎片减小,从而减少了内存碎片的总空间,有利于提高内存利用率,但另一方面也会使每个进程占用较多的页面,从而导致进程的页表过长,占用大量内存;此外,还会降低页面换进换出的效率如果选择的页面较大,虽然可以减少页表的长度,提高页面换进换出的速度,但却又会使页内碎片增大。因此,页面的大小应选择得适中,且页面大小应是2的幂,通常为512B~8KB2024/1/6962.地址结构分页地址包括页号和页内地址(页内位移量),其地址结构如下:页号P页内相对地址(位移量W)3112110

对某特定机器,其地址结构是一定的。若给定一个逻辑地址空间中的地址为A,页面的大小为L,则页号P和页内地址d可按下式求得:220=1M212=4KB2024/1/697例:系统页面大小为1KB,逻辑地址为2170B,求页号与页内地址。页号P=INT[2170/1024]=2页内地址d=2170mod1024=122B第0页0~1023第1页1024~2047第2页2048~30712024/1/6984.3.1页面与页表4.3.2地址变换机构4.3.3两级和多级页表4.3基本分页存储管理方式2024/1/6994.3.2地址变换机构1.基本地址变换机构用于实现从逻辑地址到物理地址的转换,将逻辑地址中的页号转换为内存中的物理块号,通过页表来完成页表大多驻留在内存中,在系统中设置页表寄存器PTR(Page–TableRegister),在其中存放页表在内存中的始址和页表的长度进程未执行时,页表的始址和页表长度存放在本进程的PCB中,当调度程序调度到某进程时,才将这两个数据装入页表寄存器2024/1/6100图4-13分页系统的地址变换机构以页号查页表,得到对应页装入内存的块号内存地址＝物理块号×页大小＋页内地址bw访问两次内存2024/1/61012.具有快表的地址变换机构由于页表是存放在内存中,因此每次CPU存取一个数据要两次访问内存即,查页表时要作一次访问内存的工作,然后是访问程序要求访问的内存,这样,存取速度降低一倍,将会影响整个系统的使用效率。为提高地址变换速度,在地址变换机构中增设一个具有并行查寻能力的高速缓冲寄存器,又称为“联想寄存器”(AssociativeMemory)或“快表”,用以存放当前访问的那些页表项,价格贵。快表通常可存放16-512个表项,命中率可达90％以上2024/1/6102图4-14具有快表的地址变换机构2024/1/6103例题例1:有一系统采用分页存储管理,有一作业大小是8KB,页大小为2KB,依次装入内存的第7、9、A、5,试将逻辑地址0AFEH字节,1ADDH字节转换成内存地址。答:逻辑地址0AFEH字节0000101011111110P＝1W＝01011111110字节内存地址＝0100101011111110

＝4AFEH字节2024/1/6104例题逻辑地址1ADDH字节0001101011011101P＝3W＝01011011101字节内存地址＝0010101011011101＝2ADDH字节2024/1/6105例题例2:有一系统采用分页存储管理,有一作业大小是8KB,页大小为2KB,依次装入内存的第7、9、10、5块,试将逻辑地址7145字节,3412字节转换成内存地址。2024/1/6106例题逻辑地址7145字节P＝INT[7145/2048]＝3W＝7145mod2048

＝1001字节内存地址=5*2048=11241字节逻辑地址7145字节的内存地址是:11241字节2024/1/6107例题逻辑地址3412字节P＝INT[3412/2048]＝1W＝3412mod2048

＝1364字节内存地址=9*2048=19796字节逻辑地址3412字节的内存地址是:19796字节2024/1/61084.3.1页面与页表4.3.2地址变换机构4.3.3两级和多级页表4.3基本分页存储管理方式2024/1/61094.3.3两级和多级页表现代的大多数计算机系统,都支持非常大的逻辑地址空间(232~264)。在这样的环境下,页表就变得非常大,要占用相当大的内存空间例如,对于一个具有32位逻辑地址空间的分页系统,若规定页面大小为4KB即212B,则在每个进程页表中的页表项可达1M(220)个之多。每个页表项占用4个字节(32bit),故每个进程仅仅其页表就要占用4MB的内存空间,而且还要求是连续的。页号P偏移量W3112110220=1M2024/1/6110可以采用两个方法来解决这一问题①采用离散分配方式来解决难以找到一块连续的大内存空间的问题②只将当前需要的部分页表项调入内存,其余的页表项仍驻留在磁盘上,需要时再调入2024/1/61111.两级页表(Two-LevelPageTable)

可利用将页表分页,并离散地将各个页面分别存放在不同的物理块中,同样要为离散分配的页表再建立一张页表,称为外层页表(OuterPageTable),每个页表项中记录了页表页面的物理块号210=1024210=1024212=4KB2024/1/6112图4-15两级页表结构两级页表结构每个物理块为4KB,恰好放一个1页页表(1024个项,每项4B),共需1024个这样的块0表示没有装入内存1表示在内存2024/1/6113图4-16具有两级页表的地址变换机构外层页表始址页表始址物理块2024/1/61142.多级页表对于32位的机器,采用两级页表结构是合适的;但对于64位的机器,如果页面大小仍采用4KB即212B,那么还剩下52位,假定仍按物理块的大小(210位)来划分页表,则将余下的42位用于外层页号。此时在外层页表中可能有4096G个页表项,要占用16384GB的连续内存空间。必须采用多级页表,将外层页表再进行分页,也是将各分页离散地装入到不相邻接的物理块中,再利用第2级的外层页表来映射它们之间的关系对于64位的计算机,如果要求它能支持264(=1844744TB)规模的物理存储空间,则即使是采用三级页表结构也是难以办到的;而在当前的实际应用中也无此必要2024/1/6115具有64位地址的分页存储管理242=4096G210=1024212=4KB632024/1/6116分页存储管理方案的评价(1)采用动态地址变换会增加计算机成本和降低处理机的速度。

(2)各种表格要占用一定容量的主存空间,而且还要花费一部分处理机时间用来建立和管理这些表格。

(3)虽然说外碎片消除了,但每个作业的最后一页一般都有不能充分利用的空闲区。

(4)存储扩充问题仍未得到解决。2024/1/6117内容概述4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式

4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式2024/1/61184.4基本分段存储管理方式在分段存储管理方式中,作业的地址空间被划分为若干个段,每个段定义了一组逻辑信息。它以段为单位分配主存,每段分配一个连续的主存空间,但各段之间不要求连续。由于各段的长度不一样,所以分配的内存空间大小也不一样。供用户使用的逻辑地址为段号(段名)+段内地址。在装入作业时,用一张段表记录每个分段在主存中的起始地址和长度。若装入作业的某段信息找不到足够大的空闲区,可采用移动技术,合并分散的空闲区。主存的分配与回收类似于动态分区分配,采用动态重定位。2024/1/61194.4基本分段存储管理方式4.4.1分段存储管理方式的引入4.4.2分段系统的基本原理4.4.3信息共享4.4.4段页式存储管理方式2024/1/61204.4.1分段存储管理方式的引入分页存储管理的主要目的是为了提高内存利用率,分段存储管理的主要目的是为了满足用户在编程和使用上的要求分段管理的主要目的方便编程(这是主要的因素)用户作业通常按逻辑关系分若干个段如LOAD1,[A]|<D>;STORE1,[B]|<C>;信息共享程序与数据的共享是以信息的逻辑单位为基础信息保护动态增长动态链接2024/1/61214.4基本分段存储管理方式4.4.1分段存储管理方式的引入4.4.2分段系统的基本原理4.4.3信息共享4.4.4段页式存储管理方式2024/1/61224.4.2分段系统的基本原理1.分段分段存储管理方式中,作业的地址空间被分成若干个段(segment),每个段定义了一组逻辑信息分段地址中的地址具有如下结构分段方式已得到许多编译程序的支持段号段内地址3116150216=64K216=64K2024/1/61232.段表在分段存储管理系统中,为每个分段分配一个连续的分区,而进程中的各个段可以离散地移入内存中的不同的分区中系统为每个进程建立一张段映射表,简称为“段表”每个段在段表中占一个表项,其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度实现从逻辑段到物理内存区的映射。2024/1/6124图4-17利用段表实现地址映射缺点:外碎片类似可重定位分区分配2024/1/6125图4-18分段系统的地址变换过程3.地址变换机构访问两次内存还要检查段内地址与段长是否越界,越界发中断2024/1/61264.分页和分段的主要区别页是信息的物理单位,分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位,它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要页的大小固定且由系统决定(由机器硬件决定),一个系统只有一种大小的页面;而段的长度却不固定,决定于用户所编写的程序分页的作业地址空间是一维的,即单一的线性地址空间,程序员只需利用一个记忆符,即可表示一个地址;而分段的作业地址空间则是二维的,程序员在标识一个地址时,既需给出段名,又需给出段内地址相同:都是采用离散分配方式,且都要通过地址映射机构实现地址变换。2024/1/61274.4基本分段存储管理方式4.4.1分段存储管理方式的引入4.4.2分段系统的基本原理4.4.3信息共享4.4.4段页式存储管理方式2024/1/61284.4.3信息共享分段存储的一个优点是易于实现段的共享,即允许若干个进程共享一个或多个分段分页系统中虽然也能实现程序和数据的共享,但远不如分段系统方便可重入代码(ReentrantCode)又称为“纯代码”(PureCode)是一种允许多个进程同时访问的代码。可重入代码是一种不允许任何进程对它进行修改的代码

(1)程序在执行时可能改变的部分,拷贝到该局部数据区。

(2)程序执行时,只对该数据区(属于该进程私有)中的内容进行修改,而不去改变共享的代码。2024/1/6129图4-19分页系统中共享editor的示意图2024/1/6130图4-20分段系统中共享editor的示意图2024/1/6131分段管理特点(1)段长可以根据需要动态增长。这样,便于对具有完整逻辑功能的信息段共享,便于实现程序的动态链接。(2)存在外碎片问题,若采用“紧凑”技术合并空闲区,会增加系统开销。(3)段的大小受主存可用空闲区大小的限制。2024/1/61324.4基本分段存储管理方式4.4.1分段存储管理方式的引入4.4.2分段系统的基本原理4.4.3信息共享4.4.4段页式存储管理方式2024/1/61334.4.4段页式存储管理方式1.基本原理是分段和分页原理的结合将用户程序分成若干个段,并为每一段赋予一个段名,再把每一段分成若干个页,把主存分成与页大小相同的块,每段分配与其页数相同的主存块,主存块可以连续,也可以不连续。段页式管理中,逻辑地址由段号、段内页号及页内地址三部分所组成2024/1/6134图4-21段页式地址结构2024/1/6135图4-22利用段表和页表实现地址映射2024/1/61362.地址变换过程图4-23段页式系统中的地址变换机构访问三次内存2024/1/6137段页式管理特点根据程序情况把程序分成若干段,再根据页面大小把每一段分成若干页,主存仍然分成与页大小相等的块。分配主存时,把程序的每一段的页分配到主存块中。这种分配方式既照顾到了用户共享和使用方便的需求,又考虑到了主存的利用率,提高了系统的性能。这种分配方式比分页管理的空间浪费要多。程序各段的最后一页都有可能浪费一部分空间。另外段表和页表占用空间,都比分页和分段多一些,这样就增加了硬件成本、系统的复杂性和开销。2024/1/6138内容概述4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念

4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式2024/1/6139问题的提出在程序的某次运行,执行了这部分程序就不会执行另一部分程序。当把作业全部装入主存后,作业执行时实际上只使用部分信息,甚至有些部分在作业执行的整个过程中都不会被使用到(局部性原理)。是否需要一次性地将作业全部装入？作业是否需要长期地驻留在主存？不少学者已进行了广泛的研究,这些研究结果为虚拟存储器的实现奠定了基础。2024/1/61404.5虚拟存储器的基本概念4.5.1虚拟存储器的引入4.5.2虚拟存储器的实现方法4.5.3虚拟存储器的特征2024/1/6141连续分配离散分配(基本)分页(基本)分段段页式方便程序装入提高内存利用率2024/1/61424.5.1虚拟存储器的引入作业装入内存时可能会出现如下问题(1)作业太大,因无足够内存而不能装入,无法运行。(2)无足够内存满足大量作业运行的要求。只能将少量作业装入内存让它们先运行,而将大量作业留在外存上等待。解决方法:(1)增加内存容量(从物理上增加内存容量),成本加大。(2)逻辑上扩充内存容量,即采用虚拟存储技术。2024/1/61431.常规存储器管理方式的特征(1)一次性要求作业全部装入内存才能运行(2)驻留性作业装入内存后便一直驻留内存,直至运行结束2024/1/61442.局部性原理

早在1968年,Denning.P就曾指出:程序在执行时将呈现出局部性规律,即在一较短的时间内,程序的执行仅局限于某个部分;相应地,它所访问的存储空间也局限于某个区域。提出论点如下: (1)程序执行时,除了少部分的转移和过程调用指令外,在大多数情况下仍是顺序执行的。

(2)过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域,但经研究看出,过程调用的深度在大多数情况下都不超过5。

(3)程序中存在许多循环结构,这些虽然只由少数指令构成,但是它们将多次执行。

(4)程序中还包括许多对数据结构的处理,如对数组进行操作,它们往往都局限于很小的范围内。2024/1/6145

局限性又表现在下述两个方面:(1)时间局限性。如果程序中的某条指令一旦执行,则不久以后该指令可能再次执行;如果某数据被访问过,则不久以后该数据可能再次被访问。产生时间局限性的典型原因,是由于在程序中存在着大量的循环操作。

(2)空间局限性。一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,其典型情况便是程序的顺序执行。2024/1/61463.虚拟存储器定义虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定(由地址结构决定的)其运行速度接近于内存速度,而每位的成本却又接近于外存。虚拟存储技术是一种性能非常优越的存储器管理技术,故被广泛地应用于大、中、小型机器和微型机中。书上2024/1/61474.5虚拟存储器的基本概念4.5.1虚拟存储器的引入4.5.2虚拟存储器的实现方法4.5.3虚拟存储器的特征2024/1/6148虚拟存储器的实现都是建立在离散分配的存储管理方式基础上的主要有请求分页系统和请求分段系统两种方式2024/1/61494.5.2虚拟存储器的实现方法1.请求分页系统在分页系统的基础上增加了请求调页功能和页面置换功能(1)硬件支持请求分页的页表机制,它是在纯分页的页表机制上增加若干项而形成的,作为请求分页的数据结构;缺页中断机构,即每当用户程序要访问的页面尚未调入内存时便产生一缺页中断,以请求OS将所缺的页调入内存;地址变换机构,它同样是在纯分页地址变换机构的基础上发展形成的(2)实现请求分页的软件用于实现请求调页的软件和实现页面置换的软件2024/1/61502.请求分段系统 在分段系统的基础上,增加了请求调段及分段置换功能(1)硬件支持请求分段的段表机制缺段中断机构地址变换机构(2)软件支持用于实现请求调段的软件和实现分段置换的软件2024/1/61514.5虚拟存储器的基本概念4.5.1虚拟存储器的引入4.5.2虚拟存储器的实现方法4.5.3虚拟存储器的特征2024/1/61524.5.3虚拟存储器的特征1.离散性离散性是指在主存分配时采用离散分配方式。2.多次性

一个作业被分成多次调入内存运行3.对换性允许在作业的运行过程中进行换进、换出4.虚拟性能够从逻辑上扩充内存容量,使用户所看到的内存容量远大于实际内存容量。2024/1/6153内容概述4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式

4.7页面置换算法4.8请求分段存储管理方式2024/1/61544.6请求分页存储管理方式4.6.1请求分页中的硬件支持4.6.2内存分配策略和分配算法4.6.3调页策略2024/1/61554.6.1请求分页中的硬件支持1.页表机制它是在分页存储管理系统上增加了请求调页功能、页面置换功能所形成的分页式虚拟存储管理系统。每个页表(增加了四个字段),如下:

状态位P

用于指示该页是否已调入内存访问字段A

用于记录本页在一段时间内被访问的次数,或记录本页在最近多长时间未被访问修改位M

表示该页在调入内存后是否被修改过外存地址该页在外存上的地址,通常是物理块号页号物理块号状态位P访问字段A修改位M外存地址2024/1/61562.缺页中断机构在请求分页系统中,每当所要访问的页面不在内存时,便产生一缺页中断缺页中断与一般中断的区别在指令执行期间产生和处理中断信号一条指令在执行期间可能产生多次缺页中断2024/1/6157图4-24涉及6次缺页中断的指令2024/1/61583.地址变换机构图4-25请求分页中的地址变换过程2024/1/61594.6请求分页存储管理方式4.6.1请求分页中的硬件支持4.6.2内存分配策略和分配算法4.6.3调页策略2024/1/61604.6.2内存分配策略和分配算法1.最小物理块数的确定是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时,进程将无法运行进程应获得的最少物理块数与计算机的硬件结构有关,取决于指令的格式、功能和寻址方式对于某些简单的机器,若是单地址指令且采用直接寻址方式,则所需的最少物理块数为2。其中,一块是用于存放指令的页面,另一块则是用于存放数据的页面如果该机器允许间接寻址时,则至少要求有三个物理块对于某些功能较强的机器,其指令长度可能是两个或多于两个字节,因而其指令本身有可能跨两个页面,且源地址和目标地址所涉及的区域也都可能跨两个页面,可能至少需要6个物理块2024/1/61612.物理块的分配策略

在请求分页系统中,可采取两种内存分配策略,即固定和可变分配策略。在进行置换时,也可采取两种策略,即全局置换和局部置换。于是可组合出以下三种适用的策略固定分配局部置换 为每个进程分配固定页数的内存空间,在整个运行期间不再改变。分配页数少,会频繁缺页中断;分配页数多,浪费资源,内存中运行作业少。可变分配局部置换 为每个进程分配一定量的内存空间。若运行中频繁缺页中断,则再增加若干物理块,直至缺页率减少到适当值为止。反之,若缺页率很低,则减少物理块可变分配全局置换 先为每个进程分配一定量物理块,OS有一个空闲物理块队列,某进程缺页时从空闲队列取块装页,当空闲队列为空后,OS再调出某一进程的页,置换2024/1/61623.物理块分配算法(1)平均分配算法这是将系统中所有可供分配的物理块,平均分配给各个进程例如,当系统中有100个物理块,有5个进程在运行时,每个进程可分得20个物理块。这种方式貌似公平,但实际上是不公平的,因为它未考虑到各进程本身的大小。如有一个进程其大小为200页,只分配给它20个块,这样,它必然会有很高的缺页率;而另一个进程只有10页,却有10个物理块闲置未用2024/1/6163(2)按比例分配算法

这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程,每个进程的页面数为Si,则系统中各进程页面数的总和为:

又假定系统中可用的物理块总数为m,则每个进程所能分到的物理块数为bi,将有:b应该取整,它必须大于最小物理块数。2024/1/6164(3)考虑优先权的分配算法

在实际应用中,为了照顾到重要的、紧迫的作业能尽快地完成,应为它分配较多的内存空间通常采取的方法是把内存中可供分配的所有物理块分成两部分:一部分按比例分配给各进程;另一部分则根据各进程的优先权,适当地增加其相应份额后,分配给各进程在有的系统中,如重要的实时控制系统,则可能是完全按优先权来为各进程分配其物理块的2024/1/61654.6请求分页存储管理方式4.6.1请求分页中的硬件支持4.6.2内存分配策略和分配算法4.6.3调页策略2024/1/61664.6.3调页策略1.何时调入页面(1)预调页策略采用一种以预测为基础的预调页策略,将那些预计在不久之后便会被访问的页面预先调入内存,在连续分配时,一次调入若干相邻的页。这样方法从表面上看起来很好,但系统无法预计系统中作业的运行情况,难以实现,成功率50%。(2)请求调页策略当进程在运行中需要访问某部分程序和数据时,若发现其所在的页面不在内存,便提出请求,由OS将其所需页面调入内存目前的虚拟存储中大多采用此种策略2024/1/61672.从何处调入页面在请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区。对换区的磁盘I/O速度比文件区的高每当发生缺页请求时,系统应从何处将缺页调入内存,可分成如下三种情况(1)系统拥有足够的对换区空间,这时可以全部从对换区调入所需页面,以提高调页速度。在进程运行前,文件由文件区->对换区。(2)系统缺少足够的对换区空间,这时凡是不会被修改的文件,都直接从文件区调入。凡是会被修改的文件,都直接从对换区调入。(3)UNIX方式。开始时,由于与进程有关的文件都放在文件区,故凡是未运行过的页面,都应从文件区调入。换出到对换区,以后再调入就从对换区调入。2024/1/61683.页面调入过程每当程序所要访问的页面未在内存时,便向CPU发出一缺页中断,中断处理程序首先保留CPU环境,分析中断原因后,转入缺页中断处理程序。该程序通过查找页表,得到该页在外存的物理块后,如果此时内存能容纳新页,则启动磁盘I/O将所缺之页调入内存,然后修改页表。如果内存已满,则须先按照某种置换算法从内存中选出一页准备换出。如果该页未被修改过,可不必将该页写回磁盘;但如果此页已被修改,则必须将它写回磁盘,然后再把所缺的页调入内存,并修改页表中的相应表项,置其存在位为“1”,并将此页表项写入快表中。在缺页调入内存后,利用修改后的页表,去形成所要访问数据的物理地址,再去访问内存数据。整个页面的调入过程对用户是透明的。2024/1/6169请求分页存储管理方式的特点优点:不需要程序段和数据在内存中连续存放,便于有效利用内存;提供了内外存统一管理的虚拟存储技术,扩大了内存空间。缺点