1、第第3 3章章 存储器管理存储器管理n3.1 内存管理概述内存管理概述（次重点）（次重点）n3.2 分区存储管理分区存储管理（次重点）（次重点）n3.3 页式存储管理页式存储管理（重点）（重点）n3.4 段式存储管理段式存储管理（非重点）（非重点）n3.5 段页式存储管理段页式存储管理（自学）（自学）本章需掌握的知识要点本章需掌握的知识要点n内存管理任务内存管理任务n三种内存管理方式三种内存管理方式n两类算法（内存分配、页面置换）两类算法（内存分配、页面置换）n三组区别三组区别可可重定位动态分区重定位动态分区基本分页基本分页请求分页请求分页实存实存 与与 虚存虚存分页分页 与与 分段分段连续连
2、续 与与 离散离散3.13.1 内存管理概述内存管理概述1. 存储体系存储体系三级存储器三级存储器内存内存( (主存主存) )：RAM、ROM外存外存( (辅存辅存) )：磁盘磁盘、磁带、光盘等、磁带、光盘等高速缓冲存储器高速缓冲存储器(cache) 另有寄存器级另有寄存器级 OS负责协调各存储器的使用，负责协调各存储器的使用，OS本身的程序和数据与其他本身的程序和数据与其他程序一起共享主存，为安全起见，多道程序系统常由程序一起共享主存，为安全起见，多道程序系统常由OS把内存把内存初始化为系统区和用户区两大部分：初始化为系统区和用户区两大部分： 内存内存 系统区（存放系统区（存放OSOS程序和
3、数据）程序和数据） 用户区（存放用户程序、数据）用户区（存放用户程序、数据）2. 存储管理的目的存储管理的目的n充分利用内存，为多道程序并发执行提供存储基础充分利用内存，为多道程序并发执行提供存储基础n尽可能方便用户使用尽可能方便用户使用 自动装入用户程序自动装入用户程序 用户程序中不必考虑硬件细节用户程序中不必考虑硬件细节n能够解决小内存运行大程序的问题能够解决小内存运行大程序的问题n支持程序在执行时可以动态伸缩支持程序在执行时可以动态伸缩n保证内存存取速度快保证内存存取速度快n实现存储保护与安全实现存储保护与安全n实现共享与通信实现共享与通信n了解有关资源的使用状况了解有关资源的使用状况n
4、权衡实现的性能和代价权衡实现的性能和代价3. 存储管理的任务存储管理的任务或功能或功能（1）内存空间的管理、分配与回收）内存空间的管理、分配与回收n记录内存的使用情况记录内存的使用情况 设置相应的内存分块表（内存分配回收的依据）设置相应的内存分块表（内存分配回收的依据）n内存空间划分问题？内存空间划分问题？静态或动态，等长或不等长静态或动态，等长或不等长n确定分配算法确定分配算法考虑连续性与离散性，驻留性与交换性，一次考虑连续性与离散性，驻留性与交换性，一次性与多次性，静态方式与动态方式性与多次性，静态方式与动态方式n内存碎片问题及解决办法内存碎片问题及解决办法n确定回收策略确定回收策略 （2
5、）地址转换）地址转换（又称地址重定位、地址映射）（又称地址重定位、地址映射）n指为了保证指为了保证CPU执行指令时可正确访问存储单元，需将执行指令时可正确访问存储单元，需将用户程序中的用户程序中的逻辑地址逻辑地址（相对地址，虚地址）（相对地址，虚地址）转换为运行时转换为运行时由机器直接寻址的由机器直接寻址的物理地址物理地址（绝对地址，实地址）的（绝对地址，实地址）的过程过程3. 存储管理的任务（续）存储管理的任务（续）n根据实施转换的主体和转换时机的不同，重定位具体分根据实施转换的主体和转换时机的不同，重定位具体分为两种：为两种：静态重定位静态重定位和和动态重定位动态重定位。后者更常用。后者更
6、常用n系统采用动态重定位后，程序在内存系统采用动态重定位后，程序在内存可浮动可浮动（3）内存的共享与保护）内存的共享与保护n进程共用相同内存区可节省空间，便于通信，所共享的进程共用相同内存区可节省空间，便于通信，所共享的代码应为代码应为纯代码纯代码（或者叫（或者叫可重入的代码可重入的代码）n内存保护限定程序只能访问自己所在的内存区，保护了内存保护限定程序只能访问自己所在的内存区，保护了OS和其他程序和其他程序常用界限寄存器对法和存取控制字来实现常用界限寄存器对法和存取控制字来实现（4）内存的扩充）内存的扩充n常用常用覆盖覆盖、交换交换和和虚拟存储虚拟存储技术等实现对内存的逻辑扩技术等实现对内存
7、的逻辑扩充，以使小内存能够运行大程序充，以使小内存能够运行大程序装入装入Load 1, 200 3456 1200物理地址空间物理地址空间Load 1, data1data1 3456源程序源程序Load 1, 200 34560100200编译编译连接连接逻辑地址空间逻辑地址空间BA=10001100系统采用动态重定位，系统采用动态重定位，程序装入内存时的示例程序装入内存时的示例（内外存副本一致）（内外存副本一致）：10003456LOAD 1, 2000100200300LOAD 1, 2003456逻辑地址空间逻辑地址空间110012001300物理地址空间物理地址空间200VR+100
8、0BR动态重定位示例：动态重定位示例：覆盖示意图覆盖示意图主程序主程序(30k)子程序子程序 A(8k)子程序子程序 B(10k)子程序子程序M(20k)子程序子程序N(25k)子程序子程序X(15k) 主程序（主程序（30k)覆盖区覆盖区1(25k)覆盖覆盖 区区0(10k)内内存存区区用户的结构化程序区 程序的装入和链接程序的装入和链接n源程序从编辑到运行要经历以下阶段：源程序从编辑到运行要经历以下阶段： 编辑编辑 编译编译 链接链接 装入装入 运行运行n静态链接、动态链接静态链接、动态链接n绝对地址装入、静态重定位装入、动态绝对地址装入、静态重定位装入、动态重定位装入重定位装入存储管理策
9、略分类存储管理策略分类n存储管理策略存储管理策略：n实存管理实存管理n连续连续区区分配分配（包括（包括固定分区固定分区、可变分区可变分区和和伙伴系统伙伴系统）n分页分页（Paging ）n分段分段（Segmentation ）n虚存管理虚存管理n请求分页请求分页(Demand paging)- 主流技术主流技术n请求分段请求分段(Demand segmentation)n段页式段页式（ segmentation with paging ）离散分配离散分配3.2 3.2 分区式存储管理分区式存储管理 早期的一类早期的一类实存实存管理技术管理技术 系统给每个作业或进程分配一个系统给每个作业或进程分
10、配一个连续连续的内存分的内存分区区。n单一连续区分配（静态分区技术）单一连续区分配（静态分区技术）n固定分区分配固定分区分配（静态分区静态分区技术）技术）n可变分区分配（动态分区技术）可变分区分配（动态分区技术）n可重定位可变分区分配可重定位可变分区分配（动态分区动态分区技术）技术）n伙伴系统伙伴系统（动态分区动态分区技术）技术）1. 单一连续区存储管理单一连续区存储管理 系统静态地将内存划分为两个区域，一个供操作系统使用，系统静态地将内存划分为两个区域，一个供操作系统使用，一个供用户使用，且每次只能装入一个作业或进程，主要一个供用户使用，且每次只能装入一个作业或进程，主要用于早期单道程序系统
11、和后来的用于早期单道程序系统和后来的PC操作系统。操作系统。特点特点是实现是实现简单，但内存利用率低，作业大小受限。简单，但内存利用率低，作业大小受限。操作系统操作系统用户程序用户程序0 xFFF.0区号区号起始地址起始地址长度长度(KB)状态状态1aS102bS213cS30系统预先把可分配的内存空间分割成若干个连续区域，每一区系统预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区，每个分区的大小可以相同也可以不同，分区的个域称为分区，每个分区的大小可以相同也可以不同，分区的个数与大小固定不变，每个分区每次只能装一个作业。数与大小固定不变，每个分区每次只能装一个作业。OS0abcd
12、空空 job2空空 内存分块表内存分块表(MBT)内存内存特点特点：实现简单，可用于多道程序系：实现简单，可用于多道程序系统，但内存利用率低，作业大小受限。统，但内存利用率低，作业大小受限。2. 2. 固定分区存储管理固定分区存储管理 单一连续区在多道程序系统中的直接应用单一连续区在多道程序系统中的直接应用3. 可变分区存储管理可变分区存储管理n基本思想基本思想内存划分是在作业或进程进入时动态进行的，分区内存划分是在作业或进程进入时动态进行的，分区的个数与大小都不是固定的的个数与大小都不是固定的作业装入时，根据作业的需求和内存空间的使用情作业装入时，根据作业的需求和内存空间的使用情况来决定是否
13、分配况来决定是否分配若有足够的空间，则把分配算法选中的那个分区直若有足够的空间，则把分配算法选中的那个分区直接分配给该作业，或者从那个选中的分区中割下与接分配给该作业，或者从那个选中的分区中割下与该作业申请量等大小的一部分连续空间分给该作业；该作业申请量等大小的一部分连续空间分给该作业；否则令其等待。否则令其等待。n特点特点克服了固定分区管理的克服了固定分区管理的“内碎片内碎片”问题，但产生了问题，但产生了“外碎片外碎片”。怎样解决怎样解决碎片问题碎片问题呢？呢？改进内存释放算法改进内存释放算法在内存中移动程序在内存中移动程序变连续分配为离散分配变连续分配为离散分配4. 4. 可重定位可变分区
14、存储管理可重定位可变分区存储管理n基本思想基本思想相当于引入了动态重定位和相当于引入了动态重定位和内存紧凑内存紧凑（紧缩、拼接、紧致、浮（紧缩、拼接、紧致、浮动、搬家）动、搬家）（compaction）技术的可变分区存储管理）技术的可变分区存储管理n问题问题实现紧凑所花的代价与换来的提高了内存空间利用率的实现紧凑所花的代价与换来的提高了内存空间利用率的好处相比是否值？好处相比是否值？内存紧凑的开销、频率、条件、时机？内存紧凑的开销、频率、条件、时机？一经紧凑，外碎片是否彻一经紧凑，外碎片是否彻底消失？底消失？n特点特点消除了消除了内碎片，提高了内存利用率，便于动态申请内存，内碎片，提高了内存利
15、用率，便于动态申请内存， 便于共享内存，便于动态链接，但会产生外碎片，而紧便于共享内存，便于动态链接，但会产生外碎片，而紧凑内存需要花费处理机大量时间，另外，还需要硬件重凑内存需要花费处理机大量时间，另外，还需要硬件重定位机构支持，作业大小也受内存可用空间的限制。定位机构支持，作业大小也受内存可用空间的限制。可重定位可变分区存储管理（续可重定位可变分区存储管理（续1）n内存管理用主要数据结构内存管理用主要数据结构空闲分区链空闲分区链（或空闲分区表）（或空闲分区表）n内存分配算法内存分配算法（顺序查找分配，可能触发（顺序查找分配，可能触发紧凑紧凑程序）程序）最先适应最先适应（First Fit）
16、下次适应下次适应（Next Fit）最佳适应（最佳适应（Best Fit）最坏适应最坏适应（Worst Fit）n内存释放内存释放/回收回收算法算法（考虑及时（考虑及时合并相邻空闲区合并相邻空闲区）先在空闲分区链中找到插入点，再考虑能否合并相邻先在空闲分区链中找到插入点，再考虑能否合并相邻空闲空闲区区数据结构怎样组织更有效？例例3.1 分区存储管理算法分区存储管理算法题题n采用可变分区方式管理内存时，若内存中按地址顺采用可变分区方式管理内存时，若内存中按地址顺序依次有五个大小依次为序依次有五个大小依次为15k、28k、10k、226k和和110k的的空闲区。现有五个作业空闲区。现有五个作业Ja
17、、Jb、Jc、Jd和和Je，它们各需要内存它们各需要内存10k、15k、102k、26k和和180k。问：问：如果采用最先适应分配算法，能将这五个作如果采用最先适应分配算法，能将这五个作业业按按Ja Je的次序全部装入内存吗？的次序全部装入内存吗？用什么分配用什么分配算法装入这算法装入这5个作业可使内存的利用率最高？个作业可使内存的利用率最高？解答：解答： 按最先适应分配算法，不能将这五个作业按最先适应分配算法，不能将这五个作业按按Ja Je的次序全部装入内存。因为内存中前两个原先的空闲分区能的次序全部装入内存。因为内存中前两个原先的空闲分区能依次装依次装入入Ja(10k)和和Jb(15k)，
18、第，第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)。1
19、5k28k10k226k110k5. 伙伴系统伙伴系统（buddy system）介于固定分区与可变分区之间的动态分区技术介于固定分区与可变分区之间的动态分区技术n伙伴系统可看作固定分区分配和可变分区分配的一种折中方案。伙伴系统可看作固定分区分配和可变分区分配的一种折中方案。采用伙伴系统时，内存是以采用伙伴系统时，内存是以2的幂次个字节大小的空闲块为分的幂次个字节大小的空闲块为分配单位的。配单位的。系统初启时，只有系统初启时，只有1个最大的个最大的2的幂次的空闲块，它的幂次的空闲块，它就是整个可用的内存空间。当就是整个可用的内存空间。当1个进程申请内存时，系统就分个进程申请内存时，系统就分给它
20、给它1个大于或等于进程所申请尺寸的最小的个大于或等于进程所申请尺寸的最小的2的幂次的空闲块。的幂次的空闲块。例如，某进程提出的例如，某进程提出的5050KBKB的内存请求，将首先被系统向上取整，转化为对的内存请求，将首先被系统向上取整，转化为对1 1个个6464KBKB的空闲块的请求。的空闲块的请求。n伙伴系统的内存分配过程伙伴系统的内存分配过程在一开始不能找到合适的空闲块时将在一开始不能找到合适的空闲块时将把一个最小的比该空闲块大的空闲块把一个最小的比该空闲块大的空闲块对分成对分成2 2个个“伙伴伙伴”单位，单位，该对分过程可能会继续，直到获得合适的空闲块为止。该对分过程可能会继续，直到获得
21、合适的空闲块为止。n伙伴系统的内存释放过程伙伴系统的内存释放过程首先考虑将被释放块与其伙伴单位首先考虑将被释放块与其伙伴单位合合并并成成1 1个大的空闲块，然后继续合并下去，直到不能合并为止。个大的空闲块，然后继续合并下去，直到不能合并为止。伙伴系统伙伴系统（续（续1） 为了实现伙伴系统为了实现伙伴系统，系统要为每一种可能的空闲块维护，系统要为每一种可能的空闲块维护1 1个空闲块链表。设系统管理的可用内存空间共为个空闲块链表。设系统管理的可用内存空间共为2 2N N个字个字节，则节，则1 1个伙伴系统最多需要维护个伙伴系统最多需要维护N N个空闲块链表。由于个空闲块链表。由于每种尺寸的空闲块都
22、有一个空闲块队列，因此内存的分每种尺寸的空闲块都有一个空闲块队列，因此内存的分配与释放可以有效地进行。配与释放可以有效地进行。 LinuxLinux维护维护6 6个链表个链表。 伙伴系统的最大缺陷伙伴系统的最大缺陷是不能有效地利用内存，特别是内是不能有效地利用内存，特别是内碎片严重。碎片严重。例如，例如，1 1个个257257KBKB的进程需要占用的进程需要占用1 1个个512512KBKB的分配单位，的分配单位，其中将产生其中将产生255255KBKB的内碎片。的内碎片。另外，另外，每次释放内存时都尽可能每次释放内存时都尽可能地合并伙伴单位的做法也会降低系统性能，因为刚合并地合并伙伴单位的做
23、法也会降低系统性能，因为刚合并好的块可能马上又要对分。一种改进的做法是延迟合并好的块可能马上又要对分。一种改进的做法是延迟合并的时机。的时机。伙伴系统伙伴系统（续（续2） 伙伴系统示意图伙伴系统示意图ActionMemoryStart1MA请求请求150kbA256k512kB请求请求100kbAB128k512kC请求请求50kbABC64k512k释放释放BAC64k512kD请求请求200kbAC64kD256kE请求请求60kbACED256k释放释放CA64kED256k释放释放A256k64kED256k释放释放E512kD256k释放释放D1M3.3 3.3 页式存储管理页式存储
24、管理 不用不用“紧凑紧凑”也能消除碎片的一种也能消除碎片的一种离散分配离散分配技术技术n实分页式存储管理（基本分页）实分页式存储管理（基本分页）n虚拟页式存储管理（请求分页）虚拟页式存储管理（请求分页）3.3.1 3.3.1 实分页存储管理实分页存储管理 似当今磁盘空间的管理，我认为在似当今磁盘空间的管理，我认为在PCPC上很有发展前途！上很有发展前途！1. 基本思想（基本思想（特殊的固定分区特殊的固定分区+离散分配离散分配）n系统自动地等分进程地址空间和内存空系统自动地等分进程地址空间和内存空间，每一等分单位分别叫页间，每一等分单位分别叫页（page）和块和块（frame，也叫页帧、页框、页
25、架），也叫页帧、页框、页架），页与块等大小，页与块等大小，且都从且都从0开始连续编号。进程运行时，开始连续编号。进程运行时，全部页面必须装入内存，但逻辑上连续全部页面必须装入内存，但逻辑上连续的各个页所对应的内存块可以不连续。的各个页所对应的内存块可以不连续。2. 相关概念相关概念n逻辑地址、页面、页内碎片逻辑地址、页面、页内碎片 分页对用户是透明的。页面是内存的划分使用单位，似磁盘分页对用户是透明的。页面是内存的划分使用单位，似磁盘的扇区或簇，也似的扇区或簇，也似CPU的时间片。一般，一的时间片。一般，一页的大小页的大小为为2的的整数次幂（整数次幂（k/24K16KB），也是个实验统计值，不
26、能太），也是个实验统计值，不能太大，也不能太小，大，也不能太小，为什么为什么？进程的？进程的地址空间是一维连续的地址空间是一维连续的，用一个记号即可表示一个逻辑地址，但为重定位方便，系用一个记号即可表示一个逻辑地址，但为重定位方便，系统常统常视视逻辑地址逻辑地址为为两部分组成的，即把地址的高位部分视两部分组成的，即把地址的高位部分视为页号，低位部分视为页内偏移。进程最后一页中空闲的为页号，低位部分视为页内偏移。进程最后一页中空闲的部分称为部分称为页内碎片页内碎片。0111231页号页号P页内位移量页内位移量W编号编号01048575相对地址相对地址04095该地址结构限定的最大地址空间是多少？
27、最大页表呢？3. 管理管理n页表（页表（page map table）：）： 系统为每个进程建立一个页表，页表给出逻辑页号和系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系具体内存块号相应的关系(虚分页系统中页表表目的内容更多虚分页系统中页表表目的内容更多)。页。页表放在内存，属于进程的现场信息。表放在内存，属于进程的现场信息。 页表源于一组动态重定位寄存器，今天的用途主要有页表源于一组动态重定位寄存器，今天的用途主要有两处：两处：记录进程的内存分配情况记录进程的内存分配情况实现进程运行时的动实现进程运行时的动态重定位。态重定位。 为了解决要求连续内存空间存放页表的问题为了
28、解决要求连续内存空间存放页表的问题，可用对，可用对页表分页并将其各页面离散存放的办法来实现。这就形成页表分页并将其各页面离散存放的办法来实现。这就形成了了多级页表多级页表，目前最常用的是，目前最常用的是2级页表，如级页表，如Windows 2000和和Linux中。这时，原来的页号部分，又被看成是两部分：中。这时，原来的页号部分，又被看成是两部分：页目录偏移、页表偏移。页目录偏移、页表偏移。 另外，在另外，在IBM AS/400和和Mac OS中，使用更省内存的中，使用更省内存的反置页表反置页表,页表表目为：页表表目为：Pid、page、valid、point。下面是一个页表示意图。下面是一个
29、页表示意图。.01234560123456进程的进程的地址空间地址空间页框页框（物理块）（物理块）页页号号页表页表主存中页框主存中页框（物理块）（物理块）.页表示意图：页表示意图：0310/10/10/10/10/1017空闲块数空闲块数n空块管理空块管理位示图位示图(用于外存分配时常叫盘图用于外存分配时常叫盘图)使用时需进行字位号到块号的转换：使用时需进行字位号到块号的转换：(i,j)b，b=i*w+j。另外，找。另外，找n个连续的块较慢。个连续的块较慢。3. 管理（续管理（续1）3. 管理管理（续（续2）n内存的分配内存的分配与回收与回收计算一个作业所需要的总块计算一个作业所需要的总块数数
30、N查位示图，看看是否还有查位示图，看看是否还有N个空闲块个空闲块如果有足够的空闲块，则页表长度设为如果有足够的空闲块，则页表长度设为N，可填入可填入PCB中；申请页表区，把页中；申请页表区，把页表始表始址填入址填入PCB依次分配依次分配N个空闲块，将块号和页号填入个空闲块，将块号和页号填入页表页表修改位示图修改位示图4. 硬件支持硬件支持n系统设置一对寄存器：系统设置一对寄存器： 页表始址寄存器页表始址寄存器（用于重定位时查页表）（用于重定位时查页表） 页表长度寄存器页表长度寄存器（用于重定位时内存保护校验，页表目还常有控制位）（用于重定位时内存保护校验，页表目还常有控制位）n联想存储器联想存
31、储器（associative memory）快表快表（cache结构，结构，为提高地址变为提高地址变换速度而引入换速度而引入，在，在IBM系统系统中称中称TLB（Translation lookaside buffers） 用途：保存正在运行进程的部分页表项，以快速重定位用途：保存正在运行进程的部分页表项，以快速重定位快表表目内容：页号、内存块号、标识位、淘汰位快表表目内容：页号、内存块号、标识位、淘汰位快表的特点：可按内容并行查找快表的特点：可按内容并行查找快表命中率：已经证明，快表命中率：已经证明，16个表目可达个表目可达90%以上。以上。 Intel 80 x86/Pentium有有32
32、项，项，SGI MIPS R4000有有48项。项。下面是快表在地址转换过程中应用的示意图。下面是快表在地址转换过程中应用的示意图。分页地址映射过程示意图分页地址映射过程示意图地址越界地址越界p 页表页表 l比较比较P=1pp .快表快表 b+页号页号p p 页内地址页内地址dP d页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址.物理地址物理地址页目录地址页目录地址目录位移目录位移页表位移页表位移页位移页位移虚拟地址虚拟地址页表地址页表地址.页目录（每进程一个）页目录（每进程一个）块号块号. 页页 表表代码或数据代码或数据.物理页物理页+二级页表结构及地址映射过程二级
33、页表结构及地址映射过程（未画出快表）（未画出快表）5. 实分页存储管理方式小结实分页存储管理方式小结n优点：优点：内存利用率高内存利用率高，解决了碎片问题；，解决了碎片问题； 便于管理。便于管理。n缺点：缺点：不易不易实现实现共享共享（见（见P93）；）； 不便于不便于页面页面动态增长动态增长； 进程仍受内存可用空间大小的限制；进程仍受内存可用空间大小的限制； 所需硬件支持较多。所需硬件支持较多。3.3.2 虚拟虚拟页式存储管理页式存储管理1. 基本思想基本思想实分页实分页+对换和请求装入功能对换和请求装入功能系统等分进程地址空间和内存空间，每一等分单位系统等分进程地址空间和内存空间，每一等分
34、单位分别叫页和块，页与块等大小，且都从分别叫页和块，页与块等大小，且都从0开始连开始连续编号。续编号。进程运行时，进程运行时，只需部分页面在内存只需部分页面在内存，且，且逻辑上连续的页所对应的内存块可以不连续。当逻辑上连续的页所对应的内存块可以不连续。当进程访问的页不在内存时将产生进程访问的页不在内存时将产生缺页中断缺页中断，由服，由服务程序把所缺页装入内存，此时若内存空间已满，务程序把所缺页装入内存，此时若内存空间已满，则又需要则又需要对换对换进程根据进程根据页面调度算法页面调度算法淘汰某个内淘汰某个内存页面，再装入所缺页面。存页面，再装入所缺页面。2. 虚拟存储器的概念虚拟存储器的概念n实
35、存管理方式的特征实存管理方式的特征： 一次性；驻留性一次性；驻留性；连续性。；连续性。n虚拟存储器是虚拟存储器是为了为了逻辑扩充内存，以解决小内存无法运行大逻辑扩充内存，以解决小内存无法运行大程序的问题而程序的问题而引入引入的，是一种以的，是一种以CPU时间和外存空间换取内时间和外存空间换取内存空间的技术（是存空间的技术（是OS中的资源转换技术），也是迄今为止逻中的资源转换技术），也是迄今为止逻辑扩充内存程度最彻底的技术（远强于覆盖和交换技术）。辑扩充内存程度最彻底的技术（远强于覆盖和交换技术）。n虚拟存储器是在虚拟存储器是在1961年由英国曼彻斯特大学的年由英国曼彻斯特大学的Fotherin
36、gham提出，并在该校的提出，并在该校的atlas机器上实现的一种存储技术。从机器上实现的一种存储技术。从1970年后被广泛应用，今天的年后被广泛应用，今天的OS普遍采用这一技术管理内存普遍采用这一技术管理内存，但，但我们仍应辨证地看待它我们仍应辨证地看待它。n虚拟存储器的基本思想虚拟存储器的基本思想是：是：程序、数据、堆栈的大小可以超过内存程序、数据、堆栈的大小可以超过内存的大小，的大小，OS把程序当前使用的部分保留在内存，而把其它部分保存在磁把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。盘上，并在需要时在内存和磁盘之间动态交换。n虚拟存储器支
37、持多道程序设计技术。虚拟存储器支持多道程序设计技术。虚存管理方式的特征虚存管理方式的特征：多次性；对换性；虚拟性多次性；对换性；虚拟性；离散性；离散性2. 虚拟存储器的概念（续虚拟存储器的概念（续1） 1968年美国年美国MIT的的Denning提出程序局部性原理提出程序局部性原理是对虚拟存储器有力的理论支持。是对虚拟存储器有力的理论支持。n程序局部性原理程序局部性原理 程序在执行时呈现出高度的局部性特征，即在一较短程序在执行时呈现出高度的局部性特征，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。程序执
38、行的它所访问的存储空间也局限于某个区域。程序执行的局部性表现在时间与空间两个方面：局部性表现在时间与空间两个方面：时间局部性时间局部性 一条指令被执行了，则在不久的将来它可能再被执行一条指令被执行了，则在不久的将来它可能再被执行空间局部性空间局部性 若某一存储单元被访问，则在不久之后，与该存储单若某一存储单元被访问，则在不久之后，与该存储单元相邻的单元也可能被访问元相邻的单元也可能被访问2. 虚拟存储器的概念（续虚拟存储器的概念（续2）n虚拟存储器定义虚拟存储器定义（至今没有统一定义，我认为以下前（至今没有统一定义，我认为以下前3种比较重要）种比较重要）n虚假的存储器；虚假的存储器；n进程能够
39、访问的虚拟地址空间；进程能够访问的虚拟地址空间；n具有请求调入功能和置换功能，能从逻辑上对内存容量具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。加以扩充的一种存储器系统。n把内存与外存有机的结合起来使用，从而得到一个容量把内存与外存有机的结合起来使用，从而得到一个容量很大的很大的“内存内存”，这就是虚存，这就是虚存n虚拟存储器是把内存与外存这两级存储器并用做一级存储器虚拟存储器是把内存与外存这两级存储器并用做一级存储器的结果，是逻辑扩充内存的最佳手段的结果，是逻辑扩充内存的最佳手段n虚拟存储器的容量虚拟存储器的容量取决于内存与外存的容量之和，但实际最取决于内存与外存
40、的容量之和，但实际最大尺寸取决于系统的地址结构大尺寸取决于系统的地址结构2. 虚拟存储器的概念（续虚拟存储器的概念（续3） 虚拟存储器虚拟存储器是建立在离散分配的内存管理技术基础上是建立在离散分配的内存管理技术基础上的，它主要有以下的，它主要有以下3种实现方法种实现方法：n请求分页系统请求分页系统虚拟分页系统虚拟分页系统n基本分页系统基本分页系统 + 请求分页功能请求分页功能 + 页面置换功能页面置换功能n硬硬/软件支持软件支持：请求分页的页表机制、缺页中断机构、动态地址变换：请求分页的页表机制、缺页中断机构、动态地址变换机构、对换机制、大容量外存。机构、对换机制、大容量外存。n请求分段系统请
41、求分段系统虚拟分段系统虚拟分段系统n基本分段系统基本分段系统 + 请求分段功能请求分段功能 + 分段置换功能；分段置换功能；n硬硬/软件支持：请求分段的段表机制、缺段中断机构、动态地址变换软件支持：请求分段的段表机制、缺段中断机构、动态地址变换机构、对换机制、大容量外存。机构、对换机制、大容量外存。n请求段页式系统请求段页式系统虚拟段页式系统虚拟段页式系统n请求分页系统请求分页系统 + 请求分段系统请求分段系统n硬硬/软件支持：页表机制、缺页中断机构、段表机制、缺段中断机构、软件支持：页表机制、缺页中断机构、段表机制、缺段中断机构、动态地址变换机构、对换机制、大容量外存动态地址变换机构、对换机
42、制、大容量外存。2. 虚拟存储器的概念（续虚拟存储器的概念（续4） 要辨证地看待虚拟存储器管理要辨证地看待虚拟存储器管理n问题问题1：windows98为何常提示为何常提示“内存不足内存不足”？n问题问题2：当今：当今OS几乎都用虚拟内存技术，有几乎都用虚拟内存技术，有必要吗？必要吗？n虚拟存储器管理的主要优点虚拟存储器管理的主要优点 扩充了内存，解决了小内存无法运行大程序的问扩充了内存，解决了小内存无法运行大程序的问题，提高了内存的利用率和多道程度题，提高了内存的利用率和多道程度n虚拟存储器管理的主要缺点虚拟存储器管理的主要缺点 实现开销大，程序运行比实模式下慢实现开销大，程序运行比实模式下
43、慢3. 虚分页所需的硬件支持虚分页所需的硬件支持n页表机制页表机制（似实分页的，只是扩充了页表目内容）（似实分页的，只是扩充了页表目内容）n用于地址转换；用于地址转换；n扩充页表项：页号、页架号、状态位、访问字段扩充页表项：页号、页架号、状态位、访问字段/位、位、修改位、外存地址修改位、外存地址n缺页中断（缺页中断（Page Fault）机构）机构n在地址映射过程中，所访问的页不在内存时，便产在地址映射过程中，所访问的页不在内存时，便产生一缺页中断；生一缺页中断；OS接到此中断信号后，就调出缺页接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该中断处理程序，根据页表中给出
44、的外存地址，将该页调入内存，更新页表，完成重定位，使进程继续页调入内存，更新页表，完成重定位，使进程继续运行下去。这期间可能调用置换程序。运行下去。这期间可能调用置换程序。n与常规中断的不同之处：与常规中断的不同之处：n在指令执行期间产生和处理中断信号；在指令执行期间产生和处理中断信号；n一条指令在执行期间，可能产生多次缺页中断。一条指令在执行期间，可能产生多次缺页中断。3. 虚分页所需的硬件支持（续虚分页所需的硬件支持（续1）n地址变换机构地址变换机构（似实分页的，但重定位过程中可（似实分页的，但重定位过程中可能触发缺页中断）能触发缺页中断）n首先检索快表，若找到，修改页表项中的访首先检索快
45、表，若找到，修改页表项中的访问位，然后利用页表项中给出的页架号和页问位，然后利用页表项中给出的页架号和页内地址，形成物理地址。内地址，形成物理地址。n如果在快表中未找到相应的页表项，则检索如果在快表中未找到相应的页表项，则检索内存中的页表，察看页表项中的状态位，若内存中的页表，察看页表项中的状态位，若该页已经调入内存，则形成物理地址，并更该页已经调入内存，则形成物理地址，并更新快表，当快表满时，应淘汰一个页表项；新快表，当快表满时，应淘汰一个页表项；若该页尚未调入内存，则若该页尚未调入内存，则产生缺页中断产生缺页中断，请，请求求OS把该页调入内存，然后再完成重定位。把该页调入内存，然后再完成重
46、定位。4. 内存分配策略和分配算法内存分配策略和分配算法n最小物理块（页架）数的确定最小物理块（页架）数的确定n保证进程正常运行所需的最少页架数；保证进程正常运行所需的最少页架数；n与指令的格式、功能和寻址方式有关。与指令的格式、功能和寻址方式有关。n页架的分配策略页架的分配策略n固定分配局部置换固定分配局部置换：进程占据的内存页架数不变；：进程占据的内存页架数不变；置换时在该进程所占页架中选则换出对象。系统给置换时在该进程所占页架中选则换出对象。系统给各进程分配固定数目的页架时，可考虑各进程分配固定数目的页架时，可考虑按比例分按比例分、平均分、结合工作集、结合优先权分配等策略。平均分、结合工
47、作集、结合优先权分配等策略。n可变分配全局置换：可变分配全局置换：初始时先给进程分配一定数目的页架，初始时先给进程分配一定数目的页架，当进程缺页率较高或较低时，能由当进程缺页率较高或较低时，能由OS对其占据的页架数加以对其占据的页架数加以调整，置换时在整个内存用户区的页架中选则换出对象。调整，置换时在整个内存用户区的页架中选则换出对象。n可变分配局部置换：可变分配局部置换：可变分配同上，置换时在运行进程所可变分配同上，置换时在运行进程所占页架中选则换出对象。占页架中选则换出对象。4. 内存分配策略和分配算法（续内存分配策略和分配算法（续1）n工作集（工作集（Working Set）模型）模型D
48、enning在在1968年研究缺页率与页架数的关系时提出年研究缺页率与页架数的关系时提出工作集的概念，旨在降低进程的缺页率。工作集的概念，旨在降低进程的缺页率。n一个进程当前使用的页的集合叫它的一个进程当前使用的页的集合叫它的工作集工作集。更形。更形式化的定义是：对于给定的页面访问序列选取定长式化的定义是：对于给定的页面访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页的区间，称为工作集窗口，落在工作集窗口中的页面集合称为面集合称为工作集。工作集。例如，某访问序列为：例如，某访问序列为： 26157775162341234443434441327 | |t1 | |t2 则则ws(t
49、1)=1,2,5,6,7，ws(t2)=3,4n尽量保持进程的工作集在内存可以降低进程的尽量保持进程的工作集在内存可以降低进程的缺页率，这种方法叫缺页率，这种方法叫工作集模型工作集模型。依据是。依据是局部局部性原理性原理。借助该模型，可实现可变分配、改进。借助该模型，可实现可变分配、改进时钟置换算法等。时钟置换算法等。n Windows 2000Windows 2000在系统初始化时，计算进程的在系统初始化时，计算进程的最小和最大工作集值，当物理内存大于最小和最大工作集值，当物理内存大于32MB32MB（serverserver大于大于64MB64MB）时，进程缺省最小工作）时，进程缺省最小工
50、作集为集为5050页，最大工作集为页，最大工作集为345345页。页。4. 内存分配策略和分配算法（续内存分配策略和分配算法（续2）n内存分配算法内存分配算法n同基本分页，管理物理页帧同基本分页，管理物理页帧/空闲内存块的数据结空闲内存块的数据结构也是位示图构也是位示图 5. 调页策略调页策略n请求调页策略请求调页策略（demand paging）n进程运行过程中靠缺页中断程序装入所需访问的进程运行过程中靠缺页中断程序装入所需访问的不在内存的页面。实现简单，用得广，但费时。不在内存的页面。实现简单，用得广，但费时。n预调页策略预调页策略（prepaging）n进程运行之前预先装入一些页面。主要
