专升本操作系统第四章存储管理.ppt

1、第四章 存 储 管 理,操作系统 Operating System,教学目的,存储器是作业驻留和活动的地方，和cpu一样对系统性能影响很大的瓶颈资源之一。如何让容量有限的内存被多任务安全高效共享是现代操作系统内存管理的核心任务 因此，本章着重介绍多种存储管理的方式，如分区管理，分页管理等,教学难点,页式存储管理 段式存储管理,存储管理,4.1 存储管理的概念 4.2 分区管理 4.3 分页管理 4.4 分段管理 4.5 段页式管理,存储管理的基本概念,物理内存：由系统实际提供的存储单元（通常为字节）所组成 物理内存是系统硬件（存储单元）支持的实实在在的内存，地址是一维的，存储容量受到实际存储单

2、元的限制 虚拟内存只考虑互相关联的信息之间的相对位置，其容量只受到计算机的地址位数的限制，如处理器有32位地址，则它的虚拟地址空间为2（32），约4G,虚拟地址到物理地址的映射,源程序经过编译链接后，形成一个以地址0位始地址的虚拟内存，每条指令或每个数据单元都在虚拟内存中拥有确定的地址，该地址称为虚拟地址。 当内存分配区确定后，就要将虚拟地址变换为内存中的物理地址，该变换过程就称为地址映射或重定位,静态映射,假设目标程序分配的内存起始地址为BA，每条指令或数据的虚拟地址为VA，则该指令或数据映射的内存地址就为MA=BA+VA 目标程序中的所有地址部分都以BA为基地址进行修改,动态映射,动态映射

3、是在目标程序执行过程中，在CPU访问内存之前，由硬件地址映射机构来完成将要访问的指令或数据的虚拟地址映射为内存的物理地址 地址映射机构通常由一个或多个公用的基地址寄存器BR和一个或多个虚拟地址寄存器VR组成,动态映射,BR存放当前程序分配的内存空间的起始地址，VR存放当前被映射的虚拟地址，映射得到的物理地址MA=BR+VR 只要改变BR的内容，就可以改变程序的内存空间，实现程序在内存中的搬家，所以BR又称为重定位寄存器,0 0 100 + 1100 200 1200,LOAD A 200,3456,VR 200,BR 1000,Load A 200,3456,存储管理,分区管理 分页管理 分段

4、管理 段页式管理,存储器的分区管理,基本思想：把内存划分为若干个大小不等的区域，每个区域称为一个分区 有可变分区和固定分区两种方案,固定分区,固定分区就是把内存划分为若干个大小不等的分区，分区的大小和分区总数可由操作员或操作系统在系统初启时建立好，一旦建好，每个分区的大小和分区的总数都是固定不变的 固定分区管理通过数据结构分区说明表来实现,固定分区示例,1分区,2分区,3分区,4分区,0 32k 40k 56k 88k,可变分区管理,与固定分区的3点不同： 1、可变分区的分区建立不是在系统初启时，而是在系统运行中，在作业装入时动态建立 2、分区的大小，不是事先设定的，而是根据作业对内存的需求量

5、而分配的 3、分区的个数也是变换不定的,0 32 256,可变分区的数据结构,位图 链表,可变分区的管理分配策略,最先适应法FF 最佳适应法BF 最坏适应法WF,三种策略比较,WF最快能找到要分配的空闲区，它总是查找空闲链表的第一个空闲区，若能满足则分配 在内存分配上，FF最快，因为BF和WF均要把分配剩余的空闲区按其大小插入到空闲表的合适位置，而FF不改变分配剩余部分在空闲链表的位置 在内存回收上，FF最佳。FF很容易实现邻接空闲区的合并，并且不需要改变合并后的空闲区在空闲链表中的位置 FF尽可能的分配低地址空间，保留高地址的空闲区，用于大作业分配,三种策略比较,分配前 WF BF FF,存

6、储管理,分区管理 分页管理 分段管理 段页式管理,分页与分区的比较,分区的缺点 1、当不存在能满足作业需求量的连续区时，即使空闲空间总量大于作业需求量，也不能分配 2、导致了内存碎片问题，使得内存利用率不高 3、合并内存碎片也要耗费大量的CPU时间 4、各个作业对用于不同的分区，不利用程序段的共享 分页管理取消了存储分配连续性要求，使得一个作业的地址空间在内存中是若干个不一定连续的区域,静态分页存储管理,先来看一个饭店安排客房的例子 假设一个大型饭店，所有的客房都是标准的双人间，部分客房已经住进客人，现又有一个旅游团要求入住。接待员统计了一下，说：“贵团全体都能住下，但是不能住同一楼层，更没有

7、几个挨着的。”,对于饭店这样的安排，客人不会感到奇怪，因为旅游团的大多数团员都是两人一组；而饭店每天都有入住的和退房的客人，想在同一楼层找几间挨着的客房实在不容易。,分页的基本原理,内存分配与饭店安排房间有所类似。 把作业的虚拟空间划分为若干个大小相等的块，成为页（Page），对所有的页从0依次编号，于是作业的虚拟地址可以用页号P和页内地址d来表示。 于此对应，内存空间也划分为与页大小相等的若干块，成为页帧（Page frame），系统以页为单位给作业分配帧，帧之间可以是不连续的，这样可以减少内存碎片，最多存在小于帧大小的内碎片，不会产生外碎片,分页的基本原理,一个作业只要它的总页数不大于内存

8、中的可用块数，系统就可以对它实施分配。同时为这个作业建立一个页号与块号的对照表，称为页表。这好像饭店的客户登记表一样 每个块的大小是固定的，一般是0.5KB4KB之间的数值，而且必须是2的幂次,分页的基本原理,一个作业只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。同时为这个作业建立一个页号与块号的对照表，称为页表。这好像饭店的客户登记表一样 每个块的大小是固定的，一般是0.5KB4KB之间的数值，而且必须是2的幂次 思考：为什么大小要在这个范围内？,分页存储管理示例,地址转换,页式存储管理对作业的地址转换采用动态重定位技术。 设每页大小为aKB 物理地址=物理块首址+块内地址

9、=物理块号*a+页内地址 逻辑地址=逻辑页首址+页内地址 =逻辑页号*a+页内地址,从上述过程中可以看出，分页管理每取一个数据时，都要访问两次内存，一次是访问内存中的页表，得到数据的物理地址，另一次是根据得到的物理地址，从内存中取得数据 为了提高地址变换的速度，在地址变换机构中，增加一个高速可并行查找的联想存储器，构成一张快表,分页系统地址转换过程,由指令产生逻辑地址 若逻辑页号不小于页表长度寄存器的值，则产生越界中断，否则，转（3） 由逻辑页号查快表，若成功，则读出物理块号，转（5） ，否则，转（4） 由逻辑页号查页表，从相应页表目取出该页相应的物理块号，把逻辑页号与物理块号至于快表表目中，

10、若此时快表已满，则先按淘汰算法淘汰一个快表表目 把物理块号与页内地址写入物理地址寄存器的相应位置得物理地址,地址变换示例,1、系统从作业申请表中，取出作业A的页表起址14000放入页表起址寄存器PAR中，把申请帧数放入PLR 2、由PAR得到A的页表地址为14000 3、将虚地址5000转换为页号P和页内地址D，即P=4，d=904 4、将页号与PLR比较，进行地址越界检查 5、若为有效地址，则从相应的页号4中，取出帧号21 6、由块号*块长度+块内地址，即21*1024+904=22408，即为虚地址5000对应的物理地址,设页的长度为1kb，作业A中有一条load 1，5000取数指令,页

11、的分配与回收,最简单的管理内存的方法是：位示图 位示图中的每一位与一个主存块对应，其值为0时，表示对应的主存块空闲；其值为1时，表示对应的主存块已分配 位示图的优点是占用主存空间少，可常驻内存，加快分配进程； 不足之处：不太直观，要进行图中每个位元素的下标值到其所对应的主存块的块号的转换,示例,设主存储器的可分配区域被分为256块，则只需要33B的位示图来作为主存分配表。其中8个字长32位的字可以描述全部256个块的分配使用情况，另有一个字节记录剩余的空闲块数。,页的分配与回收,还有可以采用顺序分配算法 先查看空闲块数是否能满足作业要求。若不能满足，则不进行分配，作业不能装入主存：若能满足，则

12、根据需求从位示图中找出一些为0的位，把这些位置成1，从空闲块中减去本次占用的块数，按公式“块号=字号*字长+位号”计算出这些位所对应的主存块号，把作业装入到这些块，并为作业建一张页表,动态分配存储管理,静态分页管理要求每个作业在分配到所申请的全部帧后才能装入运行。 静态缺点：当前可用帧数小于作业的需求量时，作业不能运行；作业的大小也受到了帧总数的限制 而动态分页的思想是：每次只装入一部分，其他部分在执行过程中动态装入,动态分页管理的任务,调入策略：当作业需要的信息不在内存中时，系统才把所需的页调入内存 替换策略：解决当前内存中没有空闲帧时，如何淘汰内存中已占据的帧 地址变换：完成将虚地址变换为

13、对应的物理地址,主存页面分配策略,平均分配：将内存中所以物理块等分给进入系统中的进程的做法，简单易行，但会导致“内碎片”增加和缺页率提高 按进程长度比例分配 设Si 为进程Pi逻辑空间页面数，定义S=Si；m为内存空间物理块总数，则分配给进程Pi的内存物理块数Ai为： Ai=Si/S*m 按进程优先级分配 按长度和优先级分配,页面调度算法,调度算法的好坏，直接影响系统的效率 抖动：刚被调出的帧马上要访问，调入内存后不久又要被调出，如此反复的调入调出,页面调度算法,最佳淘汰算法OPT淘汰算法 Belady于1966提出的一种理论上的算法。每次都淘汰以后永不使用的，或者最长时间后才会被访问的页面

14、虽然可以保证最低的缺页率，但无法实现，因为它必须知道页面“将来”的访问情况,页面调度算法,先进先出淘汰算法FIFO 总是淘汰最先进入内存的页面。 实现简单，只需把进程已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存最老的页面 效率不高，而且会造成Belady现象,Belady现象,一般而言，内存帧数越多，一个作业发生缺页的次数越少 但Belady提出反例 一个作业有5个页，编号从0到4，页的引用顺序为012301401234，采用FIFO替换算法，当存储帧数为3的，缺页次数为9，内存帧数为4的缺页反而为10,页面调度算法,最近最久未用淘汰算法LRU 总是淘汰

15、内存中最长时间没有被访问的帧，即淘汰最后一次访问时间距当前时间间隔最长的页面 LRU的开销很大，必须要有硬件的支持，完全由软件实现其速度至少会减少10倍，所以用LRU的近似算法更实用,页面调度算法,二次机会淘汰算法SC 通过对FIFO进行简单的改造，结合页表中的访问位而得来一种淘汰算法。 该算法首先检查位于FIFO链链首的页，如果它的访问位为0，则选择该页淘汰；如果它的访问位为1，则清除其访问位，将它移至FIFO链链尾。如此重复。,页面调度算法,时钟淘汰算法 最近未用淘汰算法,例题,已知某作业执行时页面访问次序为：70120304230321201701，该作业得到3个空闲内存块，开始时，前三

16、页已装入内存。要求： （1）试计算采用FIFO淘汰算法和LRU算法进行页面调度时产生的缺页中断次数 （2）求出各自的缺页中断率,例题,解：（1）FIFO 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,例题,解：（1）FIFO 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,例题,解：（1）FIFO 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 p p p p p p p p p p p p 一共产生12次缺页,例题,LRU 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7

17、0 1,例题,LRU 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,例题,LRU 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 p p p p p p p p p 一共产生9次缺页,例题,（2） FIFO缺页率为：12/20*100%=60% LRU缺页率为：9/20*100%=45%,存储管理,分区管理 分页管理 分段管理 段页式管理,分段式存储管理基本思想,分页和分区存储管理对用户提供的是一个线性的地址空间，即作业的地址都是从0开始顺序编址 但是，一个作业的地址空间都有一定的逻辑关系，例如可以划分为主程序、子程序和各种数据

18、结构（数组、栈、文件等），因此，如果按照各个逻辑结构来申请作业的地址空间并进行管理，将非常有利于程序设计。 基本思想：将作业按逻辑上有完整意义的段划分，每段都有自己的名字，以段为单位分配内存并进行内外存交换,段式管理的基本原理,将程序的地址空间划分为若干个段(segment)，这样就使得每个进程都有一个二维的地址空间（段号+段内相对地址） 为每个段分配一个连续的分区，而进程中的各个段可以不连续的存放在内存的不同分区中。 程序加载时，操作系统为所有段分配其所需的内存，各段之间不必连续，物理内存的管理采用动态分区的管理方法。,段式物理地址分配回收,分配：在为某个段分配物理内存时，可以采用最先适应法、最坏适应法和最佳适应法等 回收：回收某个段占用的空间时，要注意将回收的空间与其相邻的空间合并,段式管理的数据结构,为了实现段式管理，操作系统需要如下的数据结构来实现进程的地址空间到物理内存空间的映射，并跟踪物理内存的使用情况，以便在装入新的段的时候，合理的分配内存空间,数据结构,进程段