操作系统第三章幻灯片

《操作系统第三章幻灯片》由会员分享，可在线阅读，更多相关《操作系统第三章幻灯片（77页珍藏版）》请在金锄头文库上搜索。

1、第3章 存储器管理,3.1 内存管理概述（次重点） 3.2 分区存储管理（次重点） 3.3 页式存储管理（重点） 3.4 段式存储管理（非重点） 3.5 段页式存储管理（自学）,本章需掌握的知识要点,内存管理任务 三种内存管理方式 两类算法（内存分配、页面置换） 三组区别,3.1 内存管理概述,1. 存储体系,OS负责协调各存储器的使用，OS本身的程序和数据与其他程序一起共享主存，为安全起见，多道程序系统常由OS把内存初始化为系统区和用户区两大部分：,内存,系统区（存放OS程序和数据）,用户区（存放用户程序、数据）,2. 存储管理的目的,充分利用内存，为多道程序并发执行提供存储基础 尽可能方便

2、用户使用 自动装入用户程序 用户程序中不必考虑硬件细节 能够解决小内存运行大程序的问题 支持程序在执行时可以动态伸缩 保证内存存取速度快 实现存储保护与安全 实现共享与通信 了解有关资源的使用状况 权衡实现的性能和代价,3. 存储管理的任务或功能,（1）内存空间的管理、分配与回收 记录内存的使用情况 设置相应的内存分块表（内存分配回收的依据） 内存空间划分问题？静态或动态，等长或不等长 确定分配算法考虑连续性与离散性，驻留性与交换性，一次性与多次性，静态方式与动态方式 内存碎片问题及解决办法 确定回收策略 （2）地址转换（又称地址重定位、地址映射） 指为了保证CPU执行指令时可正确访问存储单元

3、，需将用户程序中的逻辑地址（相对地址，虚地址）转换为运行时由机器直接寻址的物理地址（绝对地址，实地址）的过程,3. 存储管理的任务（续）,根据实施转换的主体和转换时机的不同，重定位具体分为两种：静态重定位和动态重定位。后者更常用 系统采用动态重定位后，程序在内存可浮动 （3）内存的共享与保护 进程共用相同内存区可节省空间，便于通信，所共享的代码应为纯代码（或者叫可重入的代码） 内存保护限定程序只能访问自己所在的内存区，保护了OS和其他程序常用界限寄存器对法和存取控制字来实现 （4）内存的扩充 常用覆盖、交换和虚拟存储技术等实现对内存的逻辑扩充，以使小内存能够运行大程序,装入,Load 1, 2

4、00 3456,1200,物理地址空间,Load 1, data1 data1 3456,源程序,Load 1, 200 3456,0,100,200,编译 连接,逻辑地址空间,BA=1000,1100,系统采用动态重定位， 程序装入内存时的示例（内外存副本一致）：,1000,3456,LOAD 1, 200,0,100,200,300,LOAD 1, 200,3456,逻辑地址空间,1100,1200,1300,物理地址空间,200,VR,+,1000,BR,动态重定位示例：,覆盖示意图,程序的装入和链接,源程序从编辑到运行要经历以下阶段： 编辑 编译 链接 装入 运行 静态链接、动态链接

5、绝对地址装入、静态重定位装入、动态重定位装入,存储管理策略分类,存储管理策略： 实存管理 连续区分配（包括固定分区、可变分区和伙伴系统） 分页（Paging ） 分段（Segmentation ） 虚存管理 请求分页(Demand paging)- 主流技术 请求分段(Demand segmentation) 段页式（ segmentation with paging ）,3.2 分区式存储管理 早期的一类实存管理技术,系统给每个作业或进程分配一个连续的内存分区。 单一连续区分配（静态分区技术） 固定分区分配（静态分区技术） 可变分区分配（动态分区技术） 可重定位可变分区分配（动态分区技术）

6、伙伴系统（动态分区技术）,1. 单一连续区存储管理,系统静态地将内存划分为两个区域，一个供操作系统使用，一个供用户使用，且每次只能装入一个作业或进程，主要用于早期单道程序系统和后来的PC操作系统。特点是实现简单，但内存利用率低，作业大小受限。,操作系统 用户程序,0xFFF.,0,系统预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区，每个分区的大小可以相同也可以不同，分区的个数与大小固定不变，每个分区每次只能装一个作业。,内存分块表(MBT),内存,特点：实现简单，可用于多道程序系统，但内存利用率低，作业大小受限。,2. 固定分区存储管理 单一连续区在多道程序系统中的直接应用,3.

7、 可变分区存储管理,基本思想 内存划分是在作业或进程进入时动态进行的，分区的个数与大小都不是固定的 作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配 若有足够的空间，则把分配算法选中的那个分区直接分配给该作业，或者从那个选中的分区中割下与该作业申请量等大小的一部分连续空间分给该作业；否则令其等待。 特点 克服了固定分区管理的“内碎片”问题，但产生了“外碎片”。,怎样解决 碎片问题呢？,改进内存释放算法 在内存中移动程序 变连续分配为离散分配,4. 可重定位可变分区存储管理,基本思想 相当于引入了动态重定位和内存紧凑（紧缩、拼接、紧致、浮动、搬家）（compaction）技术的可变分

8、区存储管理 问题 实现紧凑所花的代价与换来的提高了内存空间利用率的好处相比是否值？ 内存紧凑的开销、频率、条件、时机？一经紧凑，外碎片是否彻底消失？ 特点 消除了内碎片，提高了内存利用率，便于动态申请内存， 便于共享内存，便于动态链接，但会产生外碎片，而紧凑内存需要花费处理机大量时间，另外，还需要硬件重定位机构支持，作业大小也受内存可用空间的限制。,可重定位可变分区存储管理（续1）,内存管理用主要数据结构 空闲分区链（或空闲分区表） 内存分配算法（顺序查找分配，可能触发紧凑程序） 最先适应（First Fit） 下次适应（Next Fit） 最佳适应（Best Fit） 最坏适应（Worst

9、Fit） 内存释放/回收算法（考虑及时合并相邻空闲区） 先在空闲分区链中找到插入点，再考虑能否合并相邻空闲区,数据结构怎样组织更有效？,例3.1 分区存储管理算法题,采用可变分区方式管理内存时，若内存中按地址顺序依次有五个大小依次为15k、28k、10k、226k和110k的空闲区。现有五个作业Ja、Jb、Jc、Jd和Je，它们各需要内存10k、15k、102k、26k和180k。问：如果采用最先适应分配算法，能将这五个作业按Ja Je的次序全部装入内存吗？用什么分配算法装入这5个作业可使内存的利用率最高？,解答： 按最先适应分配算法，不能将这五个作业按Ja Je的次序全部装入内存。因为内存中

10、前两个原先的空闲分区能依次装入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)。,5. 伙伴系统（buddy system） 介于固定分区与可变分区之间的动态分区技术,伙伴系统可看作固定分区分配和可变分区分配的一种折中方案。采用伙伴系统时

11、，内存是以2的幂次个字节大小的空闲块为分配单位的。系统初启时，只有1个最大的2的幂次的空闲块，它就是整个可用的内存空间。当1个进程申请内存时，系统就分给它1个大于或等于进程所申请尺寸的最小的2的幂次的空闲块。例如，某进程提出的50KB的内存请求，将首先被系统向上取整，转化为对1个64KB的空闲块的请求。 伙伴系统的内存分配过程在一开始不能找到合适的空闲块时将把一个最小的比该空闲块大的空闲块对分成2个“伙伴”单位，该对分过程可能会继续，直到获得合适的空闲块为止。 伙伴系统的内存释放过程首先考虑将被释放块与其伙伴单位合并成1个大的空闲块，然后继续合并下去，直到不能合并为止。,伙伴系统（续1）,为了

12、实现伙伴系统，系统要为每一种可能的空闲块维护1个空闲块链表。设系统管理的可用内存空间共为2N个字节，则1个伙伴系统最多需要维护N个空闲块链表。由于每种尺寸的空闲块都有一个空闲块队列，因此内存的分配与释放可以有效地进行。 Linux维护6个链表。 伙伴系统的最大缺陷是不能有效地利用内存，特别是内碎片严重。例如，1个257KB的进程需要占用1个512KB的分配单位，其中将产生255KB的内碎片。另外，每次释放内存时都尽可能地合并伙伴单位的做法也会降低系统性能，因为刚合并好的块可能马上又要对分。一种改进的做法是延迟合并的时机。,伙伴系统（续2）,伙伴系统示意图,3.3 页式存储管理 不用“紧凑”也能

13、消除碎片的一种离散分配技术,实分页式存储管理（基本分页） 虚拟页式存储管理（请求分页）,3.3.1 实分页存储管理 似当今磁盘空间的管理，我认为在PC上很有发展前途！,基本思想（特殊的固定分区+离散分配） 系统自动地等分进程地址空间和内存空间，每一等分单位分别叫页（page）和块（frame，也叫页帧、页框、页架），页与块等大小，且都从0开始连续编号。进程运行时，全部页面必须装入内存，但逻辑上连续的各个页所对应的内存块可以不连续。,2. 相关概念,逻辑地址、页面、页内碎片 分页对用户是透明的。页面是内存的划分使用单位，似磁盘的扇区或簇，也似CPU的时间片。一般，一页的大小为2的整数次幂（k/2

14、4K16KB），也是个实验统计值，不能太大，也不能太小，为什么？进程的地址空间是一维连续的，用一个记号即可表示一个逻辑地址，但为重定位方便，系统常视逻辑地址为两部分组成的，即把地址的高位部分视为页号，低位部分视为页内偏移。进程最后一页中空闲的部分称为页内碎片。,该地址结构限定的最大地址空间是多少？最大页表呢？,3. 管理,页表（page map table）： 系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系(虚分页系统中页表表目的内容更多)。页表放在内存，属于进程的现场信息。 页表源于一组动态重定位寄存器，今天的用途主要有两处：记录进程的内存分配情况实现进程运行时的动态重

15、定位。 为了解决要求连续内存空间存放页表的问题，可用对页表分页并将其各页面离散存放的办法来实现。这就形成了多级页表，目前最常用的是2级页表，如Windows 2000和Linux中。这时，原来的页号部分，又被看成是两部分：页目录偏移、页表偏移。 另外，在IBM AS/400和Mac OS中，使用更省内存的反置页表,页表表目为：Pid、page、valid、point。下面是一个页表示意图。,页表示意图：,空块管理位示图(用于外存分配时常叫盘图),使用时需进行字位号到块号的转换：(i,j)b，b=i*w+j。另外，找n个连续的块较慢。,3. 管理（续1）,3. 管理（续2）,内存的分配与回收 计

16、算一个作业所需要的总块数N 查位示图，看看是否还有N个空闲块 如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB 依次分配N个空闲块，将块号和页号填入页表 修改位示图,4. 硬件支持,系统设置一对寄存器： 页表始址寄存器（用于重定位时查页表） 页表长度寄存器（用于重定位时内存保护校验，页表目还常有控制位） 联想存储器（associative memory）快表（cache结构，为提高地址变换速度而引入，在IBM系统中称TLB（Translation lookaside buffers） 用途：保存正在运行进程的部分页表项，以快速重定位 快表表目内容：页号、内存块号、标识位、淘汰位 快表的特点：可按内容并行查找 快表命中率：已经证明，16个表目可达90%以上。 Intel 80x86/Pentium有32