操作系统原理-第3章 存储器管理

第3章存储器管理3.1内存管理概述（次重点）3.2分区存储管理（次重点）3.3页式存储管理（重点）3.4段式存储管理（非重点）3.5段页式存储管理（自学）内存管理的核心任务Cache、内存、外存三级存储结构程序和数据的长期保存程序和数据进入内存才能被处理缓存一些关键数据如何让容量有限的内存被多任务安全高效地共享是现代操作系统内存管理的核心任务，也是本章介绍的主要内容。本章需掌握的知识要点内存管理任务三种内存管理方式两类算法（内存分配、页面置换）三组区别可重定位动态分区基本分页请求分页实存与虚存分页与分段连续与离散3.1存储管理的概念1、存储管理策略的分类OS本身的程序和数据与其他程序一起共享主存，为安全起见，多道程序系统常由OS把内存初始化为系统区和用户区两大部分：内存系统区（存放OS程序和数据）用户区（存放用户程序、数据）对用户区内存的管理可采取不同的策略，这些策略可以按照不同的方法进行分类。存储管理策略的分类1）静态划分及动态划分静态划分：固定分区、分页、段页式动态划分：可变分区、分段、伙伴系统2）实存管理与虚存管理实存管理连续分配（包括固定分区、可变分区和伙伴系统）实分页（Paging）实分段（Segmentation）虚存管理请求分页(Demandpaging)--主流技术请求分段(Demandsegmentation)段页式（segmentationwithpaging）离散分配2、物理地址和逻辑地址物理地址：存储单元的地址编号，又称绝对地址或实地址--物理地址的集合称为物理地址空间逻辑地址：用户程序中使用的地址，又称相对地址或虚地址--逻辑地址的集合称为逻辑地址空间--逻辑地址空间起始地址一般是0程序装入内存时（后），必须将逻辑地址转换成物理地址才能运行，一般采用可重定位方式：静态重定位：运行之前，由装入程序完成重定位动态重定位：运行时，由硬件地址变换机构完成重定位装入Load1,120034561200物理地址空间Load1,data1data13456源程序Load1,20034560100200编译连接逻辑地址空间BA=10001100系统采用静态重定位，程序装入内存时的示例（内外存副本不一致）：装入Load1,20034561200物理地址空间Load1,data1data13456源程序Load1,20034560100200编译连接逻辑地址空间BA=10001100系统采用动态重定位，程序装入内存时的示例（内外存副本一致）：10003456LOAD1,2000100200300LOAD1,2003456逻辑地址空间110012001300物理地址空间200VR+1000BR••••••••••••••••••运行时动态计算物理地址显然，采用动态重定位时，程序可在内存中浮动。3、程序的链接程序经编译后，形成一组目标模块，再利用链接程序将这组目标模块链接成装入模块（可执行文件）。三种链接方式：静态链接装入时动态链接运行时动态链接4、存储管理的功能（1）内存空间的分配与回收记录内存的使用情况——设置相应的内存分块表（内存分配回收的依据）内存空间划分问题？——静态或动态，等长或不等长确定分配算法——考虑连续性与离散性，驻留性与交换性，一次性与多次性，静态方式与动态方式内存碎片问题及解决办法确定回收策略（2）地址转换（又称地址重定位、地址映射）指为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址（相对地址，虚地址）转换为运行时由机器直接寻址的物理地址（绝对地址，实地址）的过程（3）内存的共享与保护进程共用相同内存区可节省空间，便于通信，所共享的代码应为纯代码（或者叫可重入的代码）内存保护限定程序只能访问自己所在的内存区，保护了OS和其他程序——常用界限寄存器对法和存取控制字来实现（4）内存的扩充常用覆盖、交换和虚拟存储技术等实现对内存的逻辑扩充，以使小内存能够运行大程序4、存储管理的功能（续）1）覆盖技术把内存的同一区域分配给一道程序的的若干个子程序或数据段需要的时候将其调入内存2）交换技术将内存中暂时不用的信息交换到外存上将需要的数据从外存调入内存3）虚拟存储—主流技术通过软件和硬件技术把内存和外存构成一个二级存储体系在用户眼里是一个大容量存储器（速度是内存的，容量是外存的）也利用了覆盖和交换技术5、内存扩充技术--以时间换空间覆盖示意图主程序(30k)子程序A(8k)子程序B(10k)子程序M(20k)子程序N(25k)子程序X(15k)主程序（30k)覆盖区1(25k)覆盖区0(10k)内存区用户的结构化程序区6、存储管理分类—按内存划分策略分区式存储管理：操作系统对内存进行分区，规定每个分区只能装入一个作业或进程。--包括单一连续区、固定分区和可变分区。分页式存储管理：内存空间和虚存空间都分成大小相等的页（如4k），虚存空间每一页可以按照某种策略装入内存空间的某一页。--目前最常用的的内存管理方式。分段式存储管理：内存以段为单位进行动态分区，进程的段可以装入存储空间的一个分区。--便于编程及程序共享段页式存储管理：结合段式和页式优点，先对进程空间分段，再对每个段进行分页。开销比较大，适用于大型系统。3.2分区式存储管理——早期的一类实存管理技术系统给每个作业或进程分配一个连续的内存分区。单一连续区分配（静态分区技术）固定分区分配（静态分区技术）可变分区分配（动态分区技术）可重定位分区分配（动态分区技术）伙伴系统（动态分区技术）1.单一连续区存储管理系统静态地将内存划分为两个区域：一个供操作系统使用一个供用户使用，且每次只能装入一个作业或进程适用于单用户单任务操作系统。操作系统用户程序0xFFF...0系统预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区，每个分区的大小可以相同也可以不同，分区的个数与大小固定不变，每个分区每次只能装一个作业。2.固定分区存储管理——单一连续区在多道程序系统中的直接应用OS0abcdjob2空内存当前运行作业所在分区下限寄存器上限寄存器2bcCPUjob3设置“主存分配表”，来管理主存空间的使用1）主存空间分配与释放区号起始地址长度(KB)占用标志1aS102bS2Job23cS3Job3三个分区的主存分配表主存分配：寻找没被占用且长度满足进程要求的分区。典型如顺序分配法。主存释放：更改主存分配表相应栏目。2）地址转换与存储保护地址转换常采用“静态重定位”方法作业在装入时：物理地址=逻辑地址+分区下限地址存储保护采用“界限寄存器对”法程序执行时判断：下限地址=物理地址=上限地址参看P81页，图3-13）主存空间的利用率“内碎片”问题严重，严重影响主存空间利用率分区大小固定作业往往比分区小很多，导致分区内部一部分空间闲置不用几种解决方法（了解）方法一：划分从小到大的多个分区，按顺序分配法分配，作业分配到的空间总是满足其要求的最小分区（常用方法）方法二：根据经常出现的作业的大小和频率进行静态分区方法三：作业按对主存空间的需求排成多个队列，规定每个队列中的作业只能进入到一个指定分区3.可变分区存储管理根据进程的需要，动态划分内存空间。事先不分配Job1Job2,Job3Job2完成克服了固定分区管理的“内碎片”问题，但产生了“外碎片”。设置“已分配分区表”及“空闲分区表”，来管理主存1）主存空间分配与释放序号起始地址长度(KB)标志11000K200空闲21400K1160空闲“空闲分区表”示例主存释放：合并相邻的空闲分区。主存分配：寻找没被占用且长度满足进程要求的空闲分区，并对其进行“分割”。可按多种算法。（1）最先适应分配算法空闲分区表按分区地址大小以递增顺序排列顺序查找空闲分区表，找到第一个满足作业要求的空闲分区优点：易于合并相邻的空闲分区，尽可能保留高地址端的空闲分区缺点：搜索次数多，影响工作效率三种主存分配算法（2）最佳适应分配算法空闲分区表按分区的大小以递增顺序排列找到第一个满足作业要求的空闲分区，一定是最小、且长度接近或合适作业要求的空闲分区优点：尽可能保留较大的空闲分区缺点：产生非常小的空闲分区（外碎片）三种主存分配算法（续）（3）最坏适应分配算法空闲分区表按分区的大小以递减顺序排列找到第一个满足作业要求的空闲分区，一定是最大、且长度与作业要求差别最大的空闲分区优点：分割后产生的空闲分区一般仍可供以后分配使用缺点：工作一段时间后，不能满足大作业对空闲分区的请求主存空间的释放增加了合并相邻空闲区的操作，主要是为了尽量及时简单地减少“外碎片”。2）地址转换与存储保护地址转换一般采用“动态重定位”方法存储保护采用“基址+限长寄存器对”法基址寄存器：存放作业所占分区的起始地址限长寄存器：存放作业所占分区的长度4.可重定位可变分区存储管理相当于引入了动态重定位和内存紧凑（紧缩、移动）技术的可变分区存储管理。紧缩消除了“外碎片”需要较大开销，以“时间”换“空间”一般在连续空闲区不满足某个作业需求，而空闲区之和能满足要求时进行。例3.1分区存储管理算法题采用可变分区方式管理内存时，若内存中按地址顺序依次有五个大小依次为15k、28k、10k、226k和110k的空闲区。现有五个作业Ja、Jb、Jc、Jd和Je，它们各需要内存10k、15k、102k、26k和180k。问：⑴如果采用最先适应分配算法，能将这五个作业按Ja~Je的次序全部装入内存吗？⑵用什么分配算法装入这5个作业可使内存的利用率最高？15k28k10k226k110k解答：⑴按最先适应分配算法，不能将这五个作业按Ja~Je的次序全部装入内存。因为内存中前两个原先的空闲分区能依次装入Ja(10k)和Jb(15k)，第3个10KB的空闲区和刚刚划分出来的两个大小分别为5KB和13KB的空闲区均无法分配，第4个空闲区可以分2次装入作业Jc(102k)和Jd(26k)，则作业Je(180k)无法装入内存。⑵用最佳适应分配算法装入这5个作业，可使内存的利用率最高。此时，原先的5个空闲区依次装入了5个作业，它们是：Jb(15k)，Jd(26k)，Ja(10k)，Je(180k)和Jc(102k)。15k28k10k226k110k5.伙伴系统（buddysystem）——介于固定分区与可变分区之间的动态分区技术以2的幂次个字节大小的空闲块为内存分配单位系统初启时，只有1个最大的2的幂次的空闲块，即整个可用的内存空间。当1个进程申请内存时，系统就分给它1个大于或等于进程所申请尺寸的最小的2的幂次的空闲块。例如，某进程提出的50KB的内存请求，将首先被系统向上取整，转化为对1个64KB的空闲块的请求。伙伴系统的内存分配过程如不能找到合适的空闲块，则把一个最小的比该空闲块大的空闲块对分成2个“伙伴”单位该对分过程可能会继续，直到获得合适的空闲块为止。伙伴系统的内存释放过程首先将被释放块与其伙伴单位合并成1个大的空闲块然后继续合并下去，直到不能合并为止。伙伴系统示例ActionMemoryStart1MA请求150kbA256k512kB请求100kbAB128k512kC请求50kbABC64k512k释放BAC64k512kD请求200kbAC64kD256kE请求60kbACED256k释放CA64kED256k释放A256k64kED256k释放E512kD256k释放D1M伙伴系统伙伴系统数据结构系统要为每一种可能的空闲块维护1个空闲块链表。设系统管理的可用内存空间共为2N个字节，则1个伙伴系统最多需要维护N个空闲块链表。Linux维护6个链表，对应长为1、2、4、8、16、32个页帧的内存块。每个页帧的大小为4K。伙伴系统的主要问题最大缺陷是不能有效地利用内存，特别是“内碎片”严重。例如，1个257KB的进程需要占用1个512KB的分配单位，其中将产生255KB的内碎片。另外，每次