OS07-存储管理

1、信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室第章第章 存储管理存储管理4.1 引言引言4.2 单连续区管理单连续区管理4.3 分区式管理分区式管理4.4 覆盖与交换覆盖与交换4.5 页式存储管理页式存储管理4.6 段式存储管理段式存储管理4.7 段页式存储管理段页式存储管理4.8 虚拟存储器虚拟存储器4.9 请求页式存储管理请求页式存储管理4.10 请求段式存储管理请求段式存储管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室 4.1 引言引言1、存储管理的目的与功能、存储管理的目的与功能 存储分配存储分配 存储保护存储保护 提高内存使用率

2、提高内存使用率 内存扩充内存扩充 实现上述功能的几种技术实现上述功能的几种技术信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.1 引言引言 分配方式：分配方式：v 直接指定直接指定v 静态分配静态分配v 动态分配动态分配2、内存统一分配、内存统一分配信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.1 引言引言3、重定位、重定位v内存的每个存储单元都有一个编号，这种编号称内存的每个存储单元都有一个编号，这种编号称为为内存地址（或称为物理地址，绝对地址）。）。 内存地址的集合称为内存地址的集合称为内存空间（或存储空间）。v要求用户用内存地址编

3、程是非常困难的，尤其是要求用户用内存地址编程是非常困难的，尤其是在多道程序设计的环境中。在多道程序设计的环境中。 用户编程所用的地址称为用户编程所用的地址称为逻辑地址（或程序地址，或虚地址），由逻辑地址组成的空间称为，由逻辑地址组成的空间称为逻辑地址空间（或地址空间）。信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.1 引言引言地址映射地址映射Load A 200 3456 。 。1200物理地址空间物理地址空间Load A data1data1 3456源程序源程序Load A 200 34560100200编译编译连接连接逻辑地址空间逻辑地址空间BA=1000信

4、息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.1 引言引言重定位：逻辑地址转换为物理地址的过程重定位：逻辑地址转换为物理地址的过程重定位类型：重定位类型： 静态重定位：由重定位装入程序在作业静态重定位：由重定位装入程序在作业装入时完成。装入时完成。信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.1 引言引言v 方式：假定程序装入内存的首地址为BR，程序地址为VR，内存地址为MR，则地址映射按下式进行：MR=BR+VR 。 例如，程序装入内存的首地址为1000，则装配程序就按MR=1000+VR对程序中所有地址部分进行修改，修改后指令Loa

5、d A，200就变为Load A，1200v 优点：不需要硬件的支持。优点：不需要硬件的支持。 v 缺点：程序必须占用连续的内存空间；一旦缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动。程序装入后不能移动。信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.1 引言引言动态重定位：动态重定位：是在程序执行的过程中，每次访是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内问内存之前，将要访问的程序地址转换为内存地址。一般来说这种转换是由专门的硬件存地址。一般来说这种转换是由专门的硬件机构来完成的。机构来完成的。 v 方式：最简单的硬件机构是重定位

6、寄存器。方式：最简单的硬件机构是重定位寄存器。 在地址重定位机构中，有一个基地址寄存在地址重定位机构中，有一个基地址寄存器器BR和一个程序地址寄存器和一个程序地址寄存器VR，一个内存，一个内存地址寄存器地址寄存器MR。信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.1 引言引言v 过程：程序装入内存后，它所占用的内存区的首地址由系统送入基地址寄存器BR中。 在程序执行的过程中，若要访问内存，将访问的逻辑地址送入VR中。 地址转换机构把VR和BR中的内容相加，并将结果送入MR中，作为实际访问的地址。信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研

7、室 4.1 引言引言优点：优点：v程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。v一个程序不一定要求占用一个连续的内存空间。v可以部分地装入程序运行。v便于多个进程共享同一个程序的代码。动态地址重定位的代价：v需要硬件的支持。v实现存储管理的软件算法较为复杂。信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.1 引言引言4、程序的链接、程序的链接v 静态链接静态链接v 装入时动态链接装入时动态链接v 运行时动态链接运行时动态链接信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.2 单

8、一连续区管理单一连续区管理基本思想：内存分为系统工作区与用户工基本思想：内存分为系统工作区与用户工作区，用户空间为一个用户独占，用户作区，用户空间为一个用户独占，用户作业连续的存放在用户空间。作业连续的存放在用户空间。存储保护只要求对系统空间进行保护。存储保护只要求对系统空间进行保护。特点：单道系统特点：单道系统 系统简单系统简单 资源利用率低资源利用率低信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.3 分区式管理分区式管理 把整个内存划分为若干区域，操作系统占用一个区域，其它区域供系统中的多个作业共享，这种方法称为分区存储管理。 这是最简单的一种多道存储管理,按

9、分区划分的时机可分为不同的分区式管理。信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.3 分区式管理分区式管理一、固定式分区一、固定式分区v 基本思想：系统事先将内存划分为若干基本思想：系统事先将内存划分为若干大小固定的区域，每个区域可放一道用大小固定的区域，每个区域可放一道用户作业，运行中区域长度不变。这些内户作业，运行中区域长度不变。这些内存区域称为分区。存区域称为分区。信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.3 分区式管理分区式管理v 某系统的内存容量为某系统的内存容量为256K256K，操作系统占，操作系统占用低地址的用低

10、地址的20K20K，其余空间划分成，其余空间划分成4 4个固个固定大小的分区。如下图定大小的分区。如下图信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室作业队列v某系统的内存容量为某系统的内存容量为256K，操作系统占用低地址的，操作系统占用低地址的20K，其余空间划分成，其余空间划分成4个固定大小的分区。如下图个固定大小的分区。如下图20K28k60K124K256K-1OS作业A(6K)作业B(50K)作业C(20K)信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室管理：系统通过分区说明表进行管理：系统通过分区说明表进行 分区说明表内容：分区

11、号、分区分区说明表内容：分区号、分区大小、分区首址、分区状态大小、分区首址、分区状态信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.3 分区式管理分区式管理分区说明表分区说明表分区号分区号大小大小(KB)始址始址状态状态1820已分配已分配23228已分配已分配36460已分配已分配4132124未分配未分配优点：实现多道，实现方法简单缺点：空间浪费多，资源利用率很低信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.3 分区式管理分区式管理二、可变式分区二、可变式分区1.基本思想：系统在作业提出内存申请时再基本思想：系统在作业提出内存申请时

12、再根据用户请求划分内存分区大小和位置。根据用户请求划分内存分区大小和位置。并使分区的大小刚好与作业的大小相等。并使分区的大小刚好与作业的大小相等。2.管理：（管理：（1）空白分区说明表）空白分区说明表 已分配分区说明表已分配分区说明表 （2）分区链表）分区链表 空白分区链表空白分区链表 已分配分区链表已分配分区链表信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.3 分区式管理分区式管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.3 分区式管理分区式管理3.分区分配方法分区分配方法:其一是系统中无满足要求的空闲区，则分配其一是系统中无满

13、足要求的空闲区，则分配失败。失败。其二是空闲区大小与其二是空闲区大小与SIZE相等，则修改空闲相等，则修改空闲区表相应表目，向用户返回该空闲区首址，区表相应表目，向用户返回该空闲区首址，表示此空闲区已分给了要求的用户。表示此空闲区已分给了要求的用户。空白分区大小不合适的处理方法是系统确定空白分区大小不合适的处理方法是系统确定一常数，来确定每次分配时是否划分成两一常数，来确定每次分配时是否划分成两个分区。个分区。 信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.分区回收方法分区回收方法:回收时注意合并邻接空白分区回收时注意合并邻接空白分区4.3 分区式管理分区式管理信

14、息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室v释放区与前空闲区相邻：将释放区与前空闲区合并为释放区与前空闲区相邻：将释放区与前空闲区合并为一个空闲区。其首址仍为前空闲区首址，大小为释放一个空闲区。其首址仍为前空闲区首址，大小为释放区大小与空闲区大小之和。区大小与空闲区大小之和。v释放区与前后两个空闲区相邻：将这三个区合为一个释放区与前后两个空闲区相邻：将这三个区合为一个空闲区，其首址为前空闲区首址，大小为这三个区大空闲区，其首址为前空闲区首址，大小为这三个区大小之和，并取消原后空闲区表目。小之和，并取消原后空闲区表目。v释放区与后空闲区相邻：则把释放区合并到后空闲，释

15、放区与后空闲区相邻：则把释放区合并到后空闲，首地址为释放区首地址，大小为二者大小之和。首地址为释放区首地址，大小为二者大小之和。v释放区不与任何空闲区相邻：将释放区作为一个空闲释放区不与任何空闲区相邻：将释放区作为一个空闲区，将其大小和首址插入到空闲区表的适当位置区，将其大小和首址插入到空闲区表的适当位置。4.3 分区式管理分区式管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室 （1）首次适应算法）首次适应算法 空白分区按地址由小到大的顺序连接在一起，空白分区按地址由小到大的顺序连接在一起，形成空白区链，分配时找到的第一个满足要求的形成空白区链，分配时找到的第一个满

16、足要求的分区分配。分区分配。 从该区中划出要求大小的分区分配给进程，从该区中划出要求大小的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区表中，余下的部分仍作为一个空闲区留在空闲区表中，但要修改其首址和大小。但要修改其首址和大小。 回收时按地址大小递增的顺序插入到空闲区回收时按地址大小递增的顺序插入到空闲区表的适当位置。表的适当位置。5.空闲区管理算法空闲区管理算法4.3 分区式管理分区式管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室（2）最佳适应算法）最佳适应算法 空白分区按长度由小到大的顺序连接在空白分区按长度由小到大的顺序连接在一起，形成空白区链，分配时

17、找到的第一个一起，形成空白区链，分配时找到的第一个满足要求的分区分配。满足要求的分区分配。 从该区中划出要求大小的分区分配给进程，从该区中划出要求大小的分区分配给进程，余下部分仍作为一个空闲区留在空闲区表中，余下部分仍作为一个空闲区留在空闲区表中，但要改变其在表中的位置。但要改变其在表中的位置。 回收时，合并相邻空闲分区，并重新调整回收时，合并相邻空闲分区，并重新调整其在空闲区表中位置。其在空闲区表中位置。4.3 分区式管理分区式管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室（3）最差适应算法）最差适应算法 空白分区按长度由大到小的顺序连接在空白分区按长度由大到小

18、的顺序连接在一起，形成空白区链，分配时找到的第一个一起，形成空白区链，分配时找到的第一个满足要求的分区分配。满足要求的分区分配。 分配和回收后要对空闲区表（队列）重新分配和回收后要对空闲区表（队列）重新排序。排序。 每次仅作一次查询工作。每次仅作一次查询工作。（4）循环首次适应算法）循环首次适应算法 空白分区按长度由小到大的顺序连接在空白分区按长度由小到大的顺序连接在一起，形成一个循环链表一起，形成一个循环链表。4.3 分区式管理分区式管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室 由于空闲区的大小与申请内存的大小相等的情况是很少的，绝大多数情况是从一个空闲区中切

19、去一块，剩下的部分作为一个空闲区仍留在空闲区表中，随着时间的推移，空闲区的发展趋势是越来越小，直至不能满足任何用户要求。 这种不能被任何用户使用的极小的空闲区称为碎片。碎片的出现造成了存储空间的浪费。4.3 分区式管理分区式管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室三、可重定位分区分配三、可重定位分区分配1.基本思想基本思想 在可变式分区分配的基础上，定期或周期性在可变式分区分配的基础上，定期或周期性的的“紧缩紧缩”内存空间。内存空间。 紧缩非常浪费处理机时间紧缩非常浪费处理机时间.4.3 分区式管理分区式管理信息工程大学电子技术学院信息工程大学电子技术学院4

20、01401教研室教研室2.紧缩时机：紧缩时机： 周期性；设置周期周期性；设置周期T,到时进行；到时进行； 作业申请内存时；作业申请内存时； 作业申请内存，且无空白分区可满足要求，但空白作业申请内存，且无空白分区可满足要求，但空白分区总长度满足要求时。分区总长度满足要求时。3.主要优点：内存利用率极高。主要优点：内存利用率极高。4.主要缺点：浪费时间主要缺点：浪费时间4.3 分区式管理分区式管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室五、分区保护五、分区保护目的：防止用户作业破坏操作系统或其它用户作业。目的：防止用户作业破坏操作系统或其它用户作业。方法：方法：1.

21、界限寄存器界限寄存器 上下界寄存器上下界寄存器 基址基址-限长寄存器限长寄存器 保证经过重定位形成的内存访问地址在界限寄保证经过重定位形成的内存访问地址在界限寄存器的范围之内。存器的范围之内。 2.存储保护键存储保护键 为每个作业设置一个保护键，为内存每块也为每个作业设置一个保护键，为内存每块也设置一个保护键，匹配才可访问。设置一个保护键，匹配才可访问。 4.3 分区式管理分区式管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.4 覆盖与交换覆盖与交换内存扩充技术内存扩充技术一、覆盖一、覆盖 把程序划分为若干个功能上相对把程序划分为若干个功能上相对独立的程序段，按

22、照其自身的逻辑结构独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一将那些不会同时执行的程序段共享同一块内存区域块内存区域 用户提出覆盖依据，每次调入内存用户提出覆盖依据，每次调入内存放在相同位置。放在相同位置。 系统开销大。系统开销大。信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.4 覆盖与交换覆盖与交换二、交换二、交换 把暂时不用的信息放到外存，调入把暂时不用的信息放到外存，调入马上需要的哪部分信息。马上需要的哪部分信息。 不需用户提出覆盖依据，每次调入不需用户提出覆盖依据，每次调入内存时可放在不同位置。内存时可放在不同位置。 系统开销小系统

23、开销小信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.5 页式存储管理页式存储管理一、基本思想：一、基本思想：1.把作业地址空间分成一些大小相等的片，把作业地址空间分成一些大小相等的片，称为页；同样把存储空间也分成大小相称为页；同样把存储空间也分成大小相同的片，称为块。同的片，称为块。2.页面保持逻辑上的连续性（从页面保持逻辑上的连续性（从0开始编开始编制页号），但是所对应的块则不一定连制页号），但是所对应的块则不一定连续。续。3.系统为每个作业设置一张页表以建立作系统为每个作业设置一张页表以建立作业块业块-页之间的映射关系页之间的映射关系信息工程大学电子技术学院信

24、息工程大学电子技术学院401401教研室教研室.01234560123456作业的作业的地址空间地址空间页框页框（物理块）（物理块）页页号号页页表表主存中页框主存中页框（物理块）（物理块）.4.5 页式存储管理页式存储管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室二、地址结构二、地址结构地址结构：页式存储管理采用一维地址结地址结构：页式存储管理采用一维地址结构，既地址空间为一连续的线性空间构，既地址空间为一连续的线性空间系统在进行地址转换时将逻辑地址划分为系统在进行地址转换时将逻辑地址划分为页号和页内位移两部分。页号和页内位移两部分。页号P 页内位移4.5 页式存

25、储管理页式存储管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室页面大小页面大小 太小则空间开销增大，太大则页内碎片增大。太小则空间开销增大，太大则页内碎片增大。通常都为通常都为0.5K、 1K、 2K、 4K、16K、64K。为什么取为什么取2的幂？的幂？ 可不用计算，直接得出地址的两部分。可不用计算，直接得出地址的两部分。0111231页号页号P页内位移量页内位移量W编号编号01048575相对地址相对地址040954.5 页式存储管理页式存储管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室三、地址变换三、地址变换1.页表作用：建立起连

26、续的地址空间与进程所占不连页表作用：建立起连续的地址空间与进程所占不连续的存储空间的映射。续的存储空间的映射。 系统为每个进程建立一个页表，页表的长度和系统为每个进程建立一个页表，页表的长度和首地址存放在首地址存放在PCB或作业表中。或作业表中。 页号 0 1 ： ：块号3317：4.5 页式存储管理页式存储管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室例，如图，作业例，如图，作业1有有2页分别装入内存的第页分别装入内存的第5、6块；作业块；作业2有有3页装入内存的第页装入内存的第2、4、7块；作业块；作业3有有1 页装入内存的第页装入内存的第8块块。4.5 页式

27、存储管理页式存储管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室2.地址转换过程：地址转换过程：地址转换需两次访问内存。4.5 页式存储管理页式存储管理页表始址页号 页内位移块号 页内位移PT越界越界中断寄存器信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室例，设页长为例，设页长为1K1K，程序地址字长为，程序地址字长为1616位，用户程序位，用户程序空间和页表如图。空间和页表如图。4.5 页式存储管理页式存储管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室 3.快表方式快表方式 另设置一高速缓冲存储器，将页表全部

28、或部分另设置一高速缓冲存储器，将页表全部或部分放入，以提高地址转换速度。我们把这种快速放入，以提高地址转换速度。我们把这种快速存储器组成的页表称为快表，把存放在内存中存储器组成的页表称为快表，把存放在内存中的页表称为慢表。的页表称为慢表。(快表又叫联想存储器快表又叫联想存储器) 问题：问题：v 可能快速存储器多大都是不够的，因为程序可可能快速存储器多大都是不够的，因为程序可能会更大。能会更大。v 快速存储器是非常非常昂贵的。快速存储器是非常非常昂贵的。4.5 页式存储管理页式存储管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室 实际上我们并不需要一个很大的快速实际上

29、我们并不需要一个很大的快速存储器，有一个能存放存储器，有一个能存放16个页表表目个页表表目的快速存储器就够了。的快速存储器就够了。 硬件根据需要将页表中当前需要的少硬件根据需要将页表中当前需要的少量表目读入快表，其它表目仍留在内存量表目读入快表，其它表目仍留在内存的页表中，当需要时读入新的表目，并的页表中，当需要时读入新的表目，并淘汰适当的表目。淘汰适当的表目。4.5 页式存储管理页式存储管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室p页表页表地址越界地址越界 L比较比较P=Lpp. . .快表快表 b+页号页号p 页内地址页内地址dPd物理地址物理地址页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址具有快表系统的地具有快表系统的地址映射机制址映射机制4.5 页式存储管理页式存储管理信息工程大学电子技术学院信息工程大学电子技术学院401401教研室教研室4.两级或多级页表两级或多级页表 现代操作系统都支持很大的地址空间，现代操作系统都支持很大的地址空间，页表很大（仅采用一级页