第五章 内存管理1本章要点 1、地址映射 2、内存管理的4种方式v分区内存管理（3种放置策略）v分页内存管理（请求分页的页面置换算法 ） v分段内存管理 v段页式内存管理 3、虚拟存储 4、Unix的内存管理交换区、交换技术、交换进程、0#进程 、偷页进程等2计算机系统存储结构三级存储结构：高速缓存、内存和外存 3操作系统内存管理的任务内存管理任务 (1)地址映射 将程序地址空间中使用的逻辑地址变换成内存中的物理地址 的过程 (2) 内存的分配和回收 按照一定的算法把某一空闲的内存分配给进程，并在进程结 束时回收该进程占用的内存。 (3)虚拟存储技术 使用户程序的大小和结构不受主存容量和结构的限制，即使 在用户程序比实际主存容量还要大的情况下，程序也能 正确运行 (4)内存信息的共享与保护 保证用户程序(或进程映象)在各自的存储区域内操作，互不 干扰，同时又可以共享系统的资源 4地址映射w 物理地址：把内存分成若干个大 小相等的存储单元，每 个单元给一个编号，这 个编号称为内存地址（ 物理地址、绝对地址 、实地址），存储单 元占8位，称作字节（ byte）。 w 物理地址空间：物理地址的集合称为 物理地址空间（主存地 址空间），它是一个一 维的线性空间。 5地址映射w 程序地址：用户编程序时所用的地址（逻辑地 址、相对地址、虚地址 ），基本单位可与内存的 基本单位相同，也可以不相同。 w 程序地址空间（逻辑地址空间、虚地址空间）: 用户的程序地址的集合称为逻辑地址空间，它的 编址总是从0开始的，可以是一维线性空间，也可 以是多维空间。6地址映射地址映射（地址重 定位、地址转换） 使一个作业程序装 入到与基地址空 间不一致的存贮 空间所引起的必 须对程序内有关 地址部分的调整 过程称为地址重 定向。7地址映射地址映射方式地址映射的功能就是要建立虚实地址的对 应关系，实现地址映射有三种方式： 1.编程或编译时确定地址映射关系 2.静态地址映射：作业装入时进行重定位（软件实现） 3.动态地址映射：程序动态执行时进行重定位 （硬件完成）8地址映射1. 编程或编译时确定地址映射关系编程时确定虚实地址的关系是指在用机 器指令编程时，程序员直接按物理内存地 址编程，这种程序在系统中是不能做任何 移动的，否则就会出错。9静态地址映射2.静态地址映射静态地址映射是在程序执行之前由专门的 重定位装配程序完成地址映射 早期的多道系统中多半有一个装入程序（加载程序 ），它负责将用户程序装入系统，并将用户程序中 使用的访问内存的逻辑地址转换成物理地址。 评价: 优点：实现简单，不要硬件的支持。 缺点：程序分配的内存空间必须为连续空间， 程序在执行过程中不能移动；用户必须事先 确定所需要的存储量；程序和数据难以共享 ，造成内存空间的浪费。 10地址映射11动态地址映射3.动态地址映射动态地址映射是在程序执行时由系统硬件 逐条指令地完成从逻辑地址到物理地址的 转换的。动态地址重定位机构由基地址寄存器BR和 逻辑地址（虚地址）寄存器VR组成。内存 物理地址MA与逻辑地址的转换关系为：MA（BR）（VR） 12动态地址映射13地址映射优点动态地址映射技术的优点：（1）基地址寄存的内容由操作系统用特权指 令来设置，比较灵活，可以实现对内存的 非连续分配（2）动态地址映射在硬件执行时完成的，程 序中不执行的程序就不做地址映射的工作 ，这样既节省了CPU的时间 。又提供了实 现虚拟存储器的可能性（3）有利于程序和数据的共享 14内存的分配与回收操作系统在内存分配与回收时需要确定的策略有： 内存分配策略。确定对内存的管理方式和实现该管 理方式所需要使用的数据结构。 放置策略。确定待调入内存的程序和数据在内存中 的位置，即选择将哪个内存空闲区域实施分配。 交换策略。在内存空间不够时，操作系统需要将一 些进程的映像由内存调到外存交换区，以便使内存中 有足够的周转空间。交换策略决定了需要将哪些进程 的映像调出。 调入策略。当内存空间足够或内存就绪队列为空时 ，需要将外存交换区的就绪进程映像调入内存。调入 策略决定外存交换区的进程映像何时调入内存以及如 何调入内存。 回收策略。决定回收的时机以及回收时对于有邻接 空闲区的合并。15虚拟存储器1、问题的提出 物理存储器的结构是个一维的线性空间，容量是有限 的。 用户程序结构： 一维空间：一个用户程序就是一个程序，并且程序和 数据是不分离的； 二维空间：程序由主程序和若干个子程序（或函数） 组成，并且程序与数据是分离的； n维空间：即一个大型程序，由一个主模块和多个子 模块组成，其中各子模块又由主程序和子程序（或 函数）组成。 用户程序的大小，可能比内存容量小，也可能比内存 容量大，有时候要大得多。16虚拟存储器虚拟内存 是操作系统采用虚拟技术，在不改变物理 内存实际大小的情况下提供的逻辑上被扩 充了的内存。这种物理上不具备而逻辑上 具备的内存就是虚拟内存。局部性理论： 1、时间局限性：一条指令执行后不可能再次执行； 2、空间局限性：访问了某个存储单元则附近的单元 也会访问。 指令执行时，总是只涉及程序的一个局部。17虚拟存储器实现虚拟存储的方法：采用请求调入策略 基于局部性理论，程序运行时只将需要执行的那部分程序调 入内存，而不是调入程序的全部，比如请求分页、请求分 段。 采用交换技术在系统盘上开辟一个专门的空间作为内存的扩充，这部分磁 盘空间称为“交换区”或“对换区”，由内存管理模块进行管 理。交换区的作用是当内存空间不够时，将暂时不用的进 程映像调到磁盘交换区，以腾出内存空间，当再度用到被 调出的这部分进程映像时再将其调回内存。 采用覆盖技术在为程序分配内存空间时，操作系统根据程序结构将第0层设 置为常驻内存区。从第一层起，为该层中的多个模块设置 一个共享覆盖区，其容量与该层中最大模块的容量相当。 程序执行到哪个模块就将该模块送到它所共享的覆盖区中 。18虚拟存储器19内存信息的共享与保护在多道程序设计的环境下，系统中有系统程序 和多个用户程序同时存在，如何保证用户程 序不破坏系统程序，以及用户程序之间既共 享又不相互破坏？这就是存储保护所要解决 的问题。 常用的存储保护方法有3种： 1、上下界寄存器或基址加限长寄存器； 2、存储保护键法； 3、界限寄存器+核心态/用户态。20内存信息的共享与保护1、上下界寄存器保护法 下界寄存器：存放程序装入内存后的开始地址 上界寄存器：存放程序装入内存后的末地址 判别式： 下界寄存器 物理地址 上界寄存器21内存信息的共享与保护1、基址限长寄存器保护法 基址寄存器=下界寄存器（首地址）限长寄存器：存放程序长度 基址+限长=上界寄存器（末地址） 判别式： 基址寄存器物理地址基址+限长寄存器22内存信息的共享与保护例：有一程序装入内存的首地址是500，末地址是1500， 访问内存的逻辑地址是500、345、1000，判断是否 合法。解：下界寄存器：500上界寄存器：1500逻辑地址装入内存的首地 物理地址1、500500 1000 500 1000 1500（）2、345500 845 500 845 1500（）3、1000500 1500 500 1500 1500（）23内存信息的共享与保护2、存储保护键法 w 为每个被保护的存储块设置一个保护 键，在程序状态字中提供相应的key值 ，OS检查key是否与保护键的key吻合 ，是则不执行保护，否则要执行保护 。 w 常用保护方式： R读保护（不可读） W写保护（不可写） E执行保护（不可执行）24内存信息的共享与保护25内存信息的共享与保护3、界限寄存器+核心态/用户态 Unix采用的方法用户态下只能访问界限寄存器限定的地址范围 ； 核心态可以访问全部内存。26分区管理概述指导思想：主存适应作业，作业有多大就分多少，且物理空间连续。 优点：算法简单、直观； 缺点：内存利用率极低。 类型： 1、固定分区：把内存空间分成若干个大小不等的区域 ，称为分区。根据用户程序大小调入其中一个分区 ，区的大小大于作业大小。问题：内存空间浪费太大。 2、动态分区：作业有多大分配多大。问题：各作业释放后的空间不连续，导致总的空闲 空间很大却不能分配的情况发生。27分区管理概述操作系统进程A进程B进程C固定分区和动态分区比较28分区管理概述分区存储管理技术的实现： 1、地址映射 2、动态存储管理的机构（数据结构） 3、分区的分配和回收 4、三种基本的放置策略29分区管理概述1、地址映射：系统设置一个专用寄存器，称为基地址 寄存器，当一个进程被调度运行时，系 统首先从PCB中取出该进程的首地址装 入基地址寄存器中，在该进程运行的过 程中实现动态地址映射。物理地址=基址寄存器+逻辑地址30动态分区的数据结构2、数据结构描述内存资源：内存信息块 描述分区：分区描述器 管理空闲区：空闲区表、空 闲区队列31动态分区的分配与回收一、分配内存函数getmb（size）算法：OS在空闲队列中顺序查找第一个满足请求主 存大小的空闲区实施分配（修改相应的指针和flag） 。注意： 1、分配算法中切割空闲区是从低地址开始的，例如， 一个空闲区大小是100KB，首址是230KB，一申请 者要求80KB，分配时将从230KB开始的80KB分配 给申请者，剩下的部分仍作为一个空闲区，其首址 310KB，大小是20KB。也可以从高地址开始。 2、门限值是切割空闲区后剩下的区域若小于门限值， 不切割该空闲区，统统分给申请者（作用是避免碎 片的产生）。32动态分区的分配与回收二、释放内存函数relmb（baddr）为了使得相邻的空白区不至于被切分为多个 分区，所以回收时应尽可能地让相邻空白区 合并成一个空白区。当一个进程（或程序）释放某内存区时，要 调用存储区释放算法release,它将首先检查释 放区是否与空闲区表（队列）中的其它空闲 区相邻，若相邻则合并成一个空闲区，否则 ，将释放为一个空闲区插入空闲区表（或队 列）中的适当位置。 释放的空闲区与空闲区相邻有四种情况：33动态分区的分配与回收A、有上邻：将r合并到f1，f1.addr;f1.size+r.size=f.size B、有下邻：将r合并到f2, r.addr;r.size+r.size=f2.size C、有上、下邻：f1、r、f2 合并到f1, f1.addr; f1.size+r.size+f2.size=f1.size 撤消f2空闲区 D、无上、下邻：将r作为一个空闲区，并插入到空闲区 表的适当位置。34几种基本的放置策略分区分配和回收是对空闲区表（或空闲区队 列）数据结构进行操作，空闲区表的组织有 两种方法： 1、按空闲区大小的升序（降序）组织； 2、按空闲区首址升序（降序）组织。根据空闲区表组织的方法的不同，有不同 的放置策略，它们是： 首次适应算法：空闲区按物理地址递增排列。 最佳适应算法：空闲区按空间大小递增排列。 最坏适应算法：空闲区按空间大小递减排列。35几种基本的放置策略一、首次适应算法首次适应算法的空闲区表是按空闲区首址升序（ 即空闲区表是按空闲区首址从小到大）组织的。 36几种基本的放置策略切割空闲区有两种方法： 从空闲区头开始 从空闲区尾开始 空闲区大小50KB，首址156KB，申请34KB。37几种基本的放置策略一、首次适应算法思路：分配时从表首开始，以请求内存区的大小逐个 与空闲区进行比较，找到第一个满足要求的空闲后， 若空闲区大小与请求区的大小相等，则将该空闲区分 配给请求者，并撤消该空闲区所在表目；若大于请求 区，就将该空闲区的一部分分配给请求者，然后，修 改空闲区的大小和首址。这种算法的实质是尽可能地利用低地址部分的空闲区 ，而尽量地保证高地址部分的大