第四章存储器管理PPT课件

1、第四章第四章 存储器管理存储器管理存储器管理存储器管理OS外存内存存储器管理存储器管理v动态分区分配方式动态分区分配方式v分页和分段存储管理方式分页和分段存储管理方式v虚拟存储管理技术虚拟存储管理技术v请求分页系统的基本原理：页面置换算法请求分页系统的基本原理：页面置换算法存储器管理存储器管理存储器管理存储器管理可执可执行存行存储器储器存储器管理存储器管理存储器管理存储器管理v 编辑编辑编译编译链接链接装入装入运行运行v 图图4.14.1存储器管理存储器管理地址映射地址映射Load A 1200 3456 。 。1200物理地址空间物理地址空间Load A data1data1 3456源程序

2、源程序Load A 200 34560100200编译编译链链接接逻辑地址空间逻辑地址空间BA=10001100存储器管理存储器管理v物理地址：物理地址： 把内存分成若干个大小相等的存储单元，每个把内存分成若干个大小相等的存储单元，每个单元给一个单元给一个编号编号，这个编号被称为内存地址，这个编号被称为内存地址，又叫物理地址、绝对地址、实地址，可直接寻又叫物理地址、绝对地址、实地址，可直接寻址。址。v逻辑地址逻辑地址（相对地址，虚地址）（相对地址，虚地址） 用户的程序经过汇编或编译后形成目标代码，用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址目标代码通常采用相

3、对地址的形式，其首地址为为0 0，其余指令中的地址都相对于首地址而编址。，其余指令中的地址都相对于首地址而编址。 不能用逻辑地址在内存中读取信息。不能用逻辑地址在内存中读取信息。存储器管理存储器管理v（1 1）绝对装入方式）绝对装入方式 程序中所使用的绝对地址，装入时不再作地址程序中所使用的绝对地址，装入时不再作地址重定位。重定位。 绝对地址可在编译或汇编时给出，绝对地址可在编译或汇编时给出， 也可由程序也可由程序员直接赋予。员直接赋予。 逻辑地址与实际内存地址完全相同。逻辑地址与实际内存地址完全相同。 适用场合：单道程序环境。适用场合：单道程序环境。v？如何装入待执行的程序及其所需的数据？如

4、何装入待执行的程序及其所需的数据v？何时将程序的逻辑地址转换为物理地址？何时将程序的逻辑地址转换为物理地址存储器管理存储器管理v（2 2）可重定位装入方式（静态重定位）可重定位装入方式（静态重定位）: :允许将允许将程序装入与逻辑地址不同的物理内存空间。程序装入与逻辑地址不同的物理内存空间。v 地址映射在程序装入时进行，以后不再更改程序地址地址映射在程序装入时进行，以后不再更改程序地址缺点：缺点：不允许程序在内存中移动不允许程序在内存中移动存储器管理存储器管理v（3 3）动态运行时装入方式）动态运行时装入方式 把装入模块装入内存后，并不立即把装入模把装入模块装入内存后，并不立即把装入模块中的相

5、对地址转换为绝对地址，而是把这块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。种地址转换推迟到程序真正要执行时才进行。 装入内存后的所有地址都仍是装入内存后的所有地址都仍是相对地址相对地址。 动态运行时装入方式需要硬件支持，即动态运行时装入方式需要硬件支持，即重定重定位寄存器位寄存器，用于保存程序在内存中的起始地，用于保存程序在内存中的起始地址。址。存储器管理存储器管理v ？目标模块如何链接成装入模块呢？目标模块如何链接成装入模块呢？v （1 1）静态链接：）静态链接：指程序被装入内存之前，必须完全链接成一个装入指程序被装入内存之前，必须完全链接成一个装入模块，将

6、其中的存储引用全部转换为相对地址跳转语句。并将多个目标模块，将其中的存储引用全部转换为相对地址跳转语句。并将多个目标模块链接成为一个模块，使装入模块中的每一条指令具有相对于整个模模块链接成为一个模块，使装入模块中的每一条指令具有相对于整个模的第一条语句的逻辑地址。的第一条语句的逻辑地址。 相对地址的修改相对地址的修改 变换外部调用符号变换外部调用符号缺点：缺点：浪费存储空间浪费存储空间和处理机时间和处理机时间存储器管理存储器管理v（2 2）装入时动态链接）装入时动态链接 装入一个目标模块时，若发生一个外部模块装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外调用事件，

7、将引起装入程序去找出相应的外部目标模块，并将它装入内存。部目标模块，并将它装入内存。 优点优点：便于修改与更新：便于修改与更新 便于实现对目标模块的共享便于实现对目标模块的共享但是，可能链接一些不会执行的模块，浪费存但是，可能链接一些不会执行的模块，浪费存储空间和处理机时间。储空间和处理机时间。存储器管理存储器管理v（3 3）运行时动态链接）运行时动态链接 外部模块引用直至程序执行时才装入内存，并外部模块引用直至程序执行时才装入内存，并链接到装入模块中，进行地址转换。链接到装入模块中，进行地址转换。 可以解决静态链接和装入时动态链接都面临的可以解决静态链接和装入时动态链接都面临的存储空间和处理

8、机时间浪费问题存储空间和处理机时间浪费问题 广泛用于事务处理系统广泛用于事务处理系统 操作系统自身的一些特殊处理例程，如错误处操作系统自身的一些特殊处理例程，如错误处理例程，也无需事先全部装入内存。理例程，也无需事先全部装入内存。存储器管理存储器管理v？程序在内存中如何组织？程序在内存中如何组织v连续存储：需要内存中的一块连续的、足够大的分连续存储：需要内存中的一块连续的、足够大的分区区v非连续存储：允许进程的程序和数据分别装在内存非连续存储：允许进程的程序和数据分别装在内存的不同分区中。的不同分区中。 常用的非连续存储技术：分页存储技术、分段存常用的非连续存储技术：分页存储技术、分段存储技术

9、及其组合。储技术及其组合。存储器管理存储器管理OSOS进程进程P POSOS进程进程P P（2 2）进程进程P P（1 1）进程进程P P（n n）进程的组成进程的组成基地址基地址长度长度P(1)P(1)26042604200200P(2)P(2)12401240300300P(n)P(n)65006500300300基地址基地址(a)连续存储连续存储(b)非连续存储非连续存储存储器管理存储器管理存储器管理存储器管理v定义：定义： 为一个用户程序分配一个连续的内存空间。为一个用户程序分配一个连续的内存空间。v种类种类 单一连续分配单一连续分配 固定分区分配固定分区分配 动态分区分配动态分区分配

10、 动态重定位分配动态重定位分配存储器管理存储器管理v 思想：把内存分为系统区和用户区，内存中仅驻留一道思想：把内存分为系统区和用户区，内存中仅驻留一道程序程序v 适用于单用户，单任务的系统中，如适用于单用户，单任务的系统中，如DOS。用户程序用户程序操作系统操作系统0 xFFF.0存储器管理存储器管理v等长分区等长分区 优点：分配简单优点：分配简单 缺点：可能存在内零头缺点：可能存在内零头 （internal fragmentationinternal fragmentation） 无法运行超过分区大小的程序。无法运行超过分区大小的程序。 v异长分区异长分区n优点：提高空间利用率，减少内零头浪

11、费。优点：提高空间利用率，减少内零头浪费。n缺点：分区的大小难以确定，仍存在内零头。缺点：分区的大小难以确定，仍存在内零头。OS8M8M8MOS10M2M6M存储器管理存储器管理v分区说明表：分区说明表： 定长分区，只需标明分区状态：定长分区，只需标明分区状态： 已分配、空闲。已分配、空闲。 对于异长分区对于异长分区C存储器管理存储器管理v优点：优点： 简单，易于实现简单，易于实现v缺点：缺点： 存在内零头存在内零头 无法装入超过分区大小的长进程。无法装入超过分区大小的长进程。存储器管理存储器管理v 动态分区分配：动态分区分配：根据进程的实际需要，动态的划分内根据进程的实际需要，动态的划分内存

12、空间，并分配给进程，彻底解决了内零头问题。存空间，并分配给进程，彻底解决了内零头问题。动态分区分配的过程动态分区分配的过程OS 8M120MOS 8MOS 8MP1 40MP2 10MP3 20MP4 10MP5 10MP6 20M10MP2 10MP4 10MP6 20M10M10M20M40M（a）分配之前）分配之前（b）分配之后）分配之后（c）P1、P3、P5结束结束存储器管理存储器管理v数据结构：数据结构：描述空闲分区和已分配分区的情况描述空闲分区和已分配分区的情况 空闲分区表（可用表）空闲分区表（可用表）举例举例 空闲分区链（自由链表）空闲分区链（自由链表）0K15K38K48K68

13、K80K110K120K空闲区表空闲区表已分配区表已分配区表始址始址长度长度标志标志15K15K23K23K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空空空空始址始址长度长度标志标志0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4空空空空分区分配表分区分配表：存储器管理存储器管理存储器管理存储器管理v顺序搜索法顺序搜索法首次适应算法首次适应算法循环首次适应算法循环首次适应算法最佳适应算法最佳适应算法最坏适应算法最坏适应算法v分类搜索法分类搜索法快速适应算法快速适应算法存储器

14、管理存储器管理v思想：思想： 空闲分区表或空闲分区链按空闲分区表或空闲分区链按地址递增地址递增的次序的次序排列，每次分配从表头开始搜索。排列，每次分配从表头开始搜索。 当空闲分区当空闲分区= =申请空间大小，或仅剩下非常申请空间大小，或仅剩下非常小的空间（小于系统设置的阈值），则将全小的空间（小于系统设置的阈值），则将全部分区分配给申请进程。部分区分配给申请进程。 否则将划分为两部分，一部分长度等于进程否则将划分为两部分，一部分长度等于进程申请空间的大小，另一部分链接到空闲分区申请空间的大小，另一部分链接到空闲分区表或空闲分区链中。表或空闲分区链中。存储器管理存储器管理v优点：优点： 尽量使用

15、低地址空间，高地址空间可能保留尽量使用低地址空间，高地址空间可能保留有较大的空闲分区。有较大的空闲分区。v缺点：缺点： 在低地址部分可能导致将较大分区不断分割在低地址部分可能导致将较大分区不断分割为较小的空闲分区（即为较小的空闲分区（即外零头外零头external external fragmentationfragmentation) )v解决外零头的策略：解决外零头的策略： 紧凑技术紧凑技术（compaction)compaction)，但需系统具有动，但需系统具有动态重定位的能力，开销大，不理想。态重定位的能力，开销大，不理想。存储器管理存储器管理利用紧凑技术消除外零头利用紧凑技术消除外

16、零头OS 8MOS 8MP7 16MP2 10MP4 10MP6 10M64MP7 16MP2 10MP4 10MP6 10M10M10M20M24M(a)紧凑之前紧凑之前(a)紧凑之后紧凑之后存储器管理存储器管理v思想：思想： 记忆上次分配分区的位置，下次实施分配，记忆上次分配分区的位置，下次实施分配，从记忆位置开始搜索。从记忆位置开始搜索。v优点：优点： 均衡使用整个内存空间。均衡使用整个内存空间。v缺点：缺点： 导致内存中缺少大分区。导致内存中缺少大分区。存储器管理存储器管理v思想：思想： 将空闲分区表或空闲分区链中空闲分区按从将空闲分区表或空闲分区链中空闲分区按从小到大递增顺序排列。为

17、进程分配存储空间小到大递增顺序排列。为进程分配存储空间时，从表头开始查找，第一个满足进程申请时，从表头开始查找，第一个满足进程申请存储空间大小的分区就是最适合的分区。存储空间大小的分区就是最适合的分区。v优点：优点： 尽量不分割大分区。尽量不分割大分区。v缺点：缺点： 导致大量较小的外零头导致大量较小的外零头存储器管理存储器管理v思想：思想： 空闲区按大小递减的顺序组成空闲分区表或空闲区按大小递减的顺序组成空闲分区表或空闲分区链。为进程分配存储空间时，从表空闲分区链。为进程分配存储空间时，从表头开始查找，选择第一个满足进程需要的分头开始查找，选择第一个满足进程需要的分区。区。v优点：优点： 避

18、免形成大量较小的外零头。避免形成大量较小的外零头。v缺点：缺点： 导致系统中缺乏大空闲分区。导致系统中缺乏大空闲分区。存储器管理存储器管理四种分配算法（四种分配算法（p7申请空间）申请空间）OS 8MP7 16MP2 10MP4 10MP6 10MP6 10MP4 10MP2 10MP2 10MP4 10MP6 10MP7 16MP7 16MOS 8MOS 8M10M10M20M24M24M20M10M10M10M10M4M40M(b)NFA(c)BFA(a)FFA或或WFA此次此次分配分配位置位置上次上次分配分配位置位置存储器管理存储器管理v思想：思想： 将空闲分区根据其容量大小进行分类，对

19、于将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立设立一个空闲分区链表，同时在内存中设立一张管理索引表。一张管理索引表。v优点：优点： 查找效率高。查找效率高。v缺点：缺点： 分区回收复杂。分区回收复杂。存储器管理存储器管理m.size:每个空每个空闲分区的大小闲分区的大小u.size：请求的：请求的分区大小；分区大小；存储器管理存储器管理v修改自由链或可用表中修改自由链或可用表中 起始地址、空闲区大小起始地址、空闲区大小 插入相应位置。插入相应位置。F1F1回收区回收区F1F1回收区回收区

20、F2F2F1F1回收区回收区F2F2F1F1存储器管理存储器管理v思想：思想： 分区大小为分区大小为2 2的的k k次幂，次幂，l lk mk m。 每一类相同大小的所有空闲分区，用一个双向每一类相同大小的所有空闲分区，用一个双向链表管理。链表管理。v分配算法分配算法 假设进程请长度为假设进程请长度为n n的存储空间。的存储空间。 当当2 2i-1 i-1 n 2=u.size?无无法法分分配配，返返回回紧紧凑凑形形成成连连续续空空闲闲区区修修改改有有关关的的数数据据结结构构否否否否是是存储器管理存储器管理v对换的引入对换的引入 将阻塞进程，暂时不用的程序，数据换出。将阻塞进程，暂时不用的程序

21、，数据换出。 将具备运行条件的进程换入。将具备运行条件的进程换入。 类型：类型： 整体对换：进程对换，解决内存紧张整体对换：进程对换，解决内存紧张 部分对换：页面对换部分对换：页面对换/ /分段对换：提供虚存支持分段对换：提供虚存支持存储器管理存储器管理v对换空间的管理（对换空间的管理（外存外存） 文件区文件区：离散分配方式离散分配方式 对换区对换区：连续分配方式连续分配方式v进程的换出与换入进程的换出与换入 进程的换出：选择处于阻塞态且优先级最低的进程作为进程的换出：选择处于阻塞态且优先级最低的进程作为换出进程换出进程 进程的换入：将换出时间最久的进程作为换入进程进程的换入：将换出时间最久的

22、进程作为换入进程存储器管理存储器管理存储器管理存储器管理v 基本原理基本原理 是一种特殊的固定分区方法是一种特殊的固定分区方法 将各进程的逻辑地址空间划分成若干个长度相等的页或将各进程的逻辑地址空间划分成若干个长度相等的页或页面页面 把内存空间按页的大小划分成物理块或页框。把内存空间按页的大小划分成物理块或页框。 分页：进程被分割成许多页面，每个页面内的指令和数分页：进程被分割成许多页面，每个页面内的指令和数据是连续的，它们的地址相对于其所属页的第一条语句据是连续的，它们的地址相对于其所属页的第一条语句的地址，称为的地址，称为页内偏移量页内偏移量。 逻辑地址被分为两部分：页号和页内偏移量逻辑地

23、址被分为两部分：页号和页内偏移量v 特性：特性： 同一物理块内地址连续，块之间可以不连续。同一物理块内地址连续，块之间可以不连续。 减小零头，一个进程平均浪费减小零头，一个进程平均浪费1/21/2个页面。个页面。 逻辑上相邻的页，物理上不一定相邻。逻辑上相邻的页，物理上不一定相邻。 页面大小应是页面大小应是2 2的幂，通常为的幂，通常为512 B-8 KB512 B-8 KB存储器管理存储器管理n地址结构 分页地址中的地址结构如下：分页地址中的地址结构如下： 页号页号P P位移量位移量W W3112110 对某特定机器，其地址结构是一定的。若给定一个逻对某特定机器，其地址结构是一定的。若给定一

24、个逻辑地址空间中的地址为辑地址空间中的地址为A A，页面的大小为，页面的大小为L L，则页号，则页号P P和页内和页内地址地址d d可按下式求得：可按下式求得： MODLAdLAINTP存储器管理存储器管理v 假设内存能提供假设内存能提供1616个空闲块，进程个空闲块，进程P1P1被分割成被分割成4 4个页面，个页面，装入内存中的装入内存中的0 0号至号至3 3号块。进程号块。进程p2p2被分割成被分割成3 3个页面，个页面，装入装入4 4号至号至6 6号块。进程号块。进程P3P3被装入被装入7 7号至号至1212号块。号块。v 此时，进程此时，进程P4P4请求分配请求分配5 5个块大小的存储

25、空间，但内存个块大小的存储空间，但内存只有只有3 3个空闲块。于是，将暂时不运行的个空闲块。于是，将暂时不运行的P2P2交换出内存。交换出内存。v 然后，再将然后，再将P4P4装入装入4 4、5 5、6 6、1313、1414号块。号块。存储器管理存储器管理v (1)(1)页表：页表：用于记录进程的各页面到物理内存中页框的映射信息用于记录进程的各页面到物理内存中页框的映射信息v 页表还包括一个存取控制字段，又称页描述子。页表还包括一个存取控制字段，又称页描述子。v 每个进程至少拥有一个页表。每个进程至少拥有一个页表。页号页号块号块号0 00 01 11 12 22 23 33 3页号页号块号块

26、号0 0- -1 1- -2 2- -页号页号块号块号0 07 71 18 82 29 93 310104 411115 51212页号页号块号块号0 04 41 15 52 26 63 313134 41414进程进程P1、P2、P3、P4的页表的页表存储器管理存储器管理v (2)(2)请求表：请求表：描述系统内各个进程页表的位置和大小，用于实现描述系统内各个进程页表的位置和大小，用于实现地址转换，请求表也可以结合到个进程的地址转换，请求表也可以结合到个进程的PCBPCB里。里。v 整个系统一张请求表。整个系统一张请求表。请求请求 块数块数存储器管理存储器管理v (3)(3)存储页面表：存储

27、页面表：描述了物理内存空间的分配使用状况描述了物理内存空间的分配使用状况 位示图位示图: :由由0 0、1 1构成的向量，其中每一位表示一个物理构成的向量，其中每一位表示一个物理块块的使用状态：块块的使用状态：0 0空闲，空闲，1 1已被分配已被分配 空闲块链表：将内存中所有的空闲块通过其内的链接空闲块链表：将内存中所有的空闲块通过其内的链接指针连成一个链表，系统只需要记录链表头的位置。指针连成一个链表，系统只需要记录链表头的位置。v 整个系统一张存储页面表。整个系统一张存储页面表。00000111011111111111000111100111存储器管理存储器管理v变换过程变换过程 逻辑地址

28、逻辑地址页号及页内偏移量页号及页内偏移量 页号页号块号块号 块号，页内偏移量块号，页内偏移量物理地址物理地址0块号块号存储器管理存储器管理v页表寄存器页表寄存器 实现快速地址映射，存储执行进程的页表起始地址。实现快速地址映射，存储执行进程的页表起始地址。 当进程被创建时，其页表起始地址记载于进程当进程被创建时，其页表起始地址记载于进程PCBPCB中。中。 当进程被调度执行时，页表的起始地址将从该进程当进程被调度执行时，页表的起始地址将从该进程的的PCBPCB中取出，并填入页表寄存器中。中取出，并填入页表寄存器中。 进行地址变换时，处理机从页表寄存器中查找页表进行地址变换时，处理机从页表寄存器中

29、查找页表的地址。的地址。存储器管理存储器管理分页系统的地址变换过程分页系统的地址变换过程存储器管理存储器管理块号块号逻辑地址逻辑地址页表寄存器页表寄存器存储器管理存储器管理v设块长度为设块长度为1K1K，v指令指令LOAD 1,2500LOAD 1,2500的虚地址为的虚地址为100100。v总结：总结： 两次访问内存，即页表两次访问内存，即页表数据或指令数据或指令块块0存储器管理存储器管理v高速联想存储器高速联想存储器 存放最近访问的页表的高速缓存，也叫转换存放最近访问的页表的高速缓存，也叫转换检测缓冲器检测缓冲器TLB TLB （Translation Lookaside Translat

30、ion Lookaside BufferBuffer）。）。 根据局部性原理，保存当前进程最近访问过根据局部性原理，保存当前进程最近访问过的一组页表项的一组页表项 大小：只能存放大小：只能存放16-51216-512个页表项个页表项存储器管理存储器管理存储器管理存储器管理v设置多级页表的原因设置多级页表的原因 对于逻辑地址空间对于逻辑地址空间2 23232 页面大小为页面大小为4KB4KB 每个进程的页表项为每个进程的页表项为1MB1MB，且要求连续。，且要求连续。离散存储离散存储部分调入部分调入存储器管理存储器管理u首先将其分割，并离散的存储在内存的多个物理块中；首先将其分割，并离散的存储在

31、内存的多个物理块中；u为之建立二级页表，记录被分割的各个页面存储在哪些块为之建立二级页表，记录被分割的各个页面存储在哪些块中，也称为外层页表。中，也称为外层页表。以逻辑地址空间为32位为例。页面大小为4KB.存储器管理存储器管理外层页号某页表分页的首址外层页内地址存储器管理存储器管理存储器管理存储器管理v 如何解决页表占用大量内存的问题？如何解决页表占用大量内存的问题？ 部分页表分页在外存部分页表分页在外存 在外层页表项中设置状态位。在外层页表项中设置状态位。存储器管理存储器管理对于某些机器，二级页表也可能非常大，可以采对于某些机器，二级页表也可能非常大，可以采用多级页表，对外层页表再进行分页

32、，将各个页用多级页表，对外层页表再进行分页，将各个页面离散的存储到不相邻接的物理页框中。面离散的存储到不相邻接的物理页框中。存储器管理存储器管理v某虚拟存储器的用户编程空间共某虚拟存储器的用户编程空间共3232个页，每页为个页，每页为2KB2KB。假定某时刻一用户页表中已调入内存的页面对应的物假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：理块号如下表：页号页号物理块号物理块号0 05 51 110102 24 43 37 7则逻辑地址则逻辑地址0A5C0A5C（H H）所对应的物理地址为）所对应的物理地址为 ：525C525C存储器管理存储器管理v0A5C0A5C0000,100

33、00,1010,0101,1100010,0101,1100v页号为页号为1 1，对应块号为，对应块号为1010，有：，有：v物理地址：物理地址：01010101，0 0010,0101,1100010,0101,1100v即：即：525C525C存储器管理存储器管理v彻底消除了外零头，仅存在很少的内零头，提彻底消除了外零头，仅存在很少的内零头，提高了高了内存利用率内存利用率v分页操作由系统自动进行，一个页面不能实现分页操作由系统自动进行，一个页面不能实现某种逻辑功能。用户看到的逻辑地址是一维的，某种逻辑功能。用户看到的逻辑地址是一维的，无法调试执行其中的某个子程序或子函数无法调试执行其中的某

34、个子程序或子函数v采用分页技术不易于实现存储共享，也不便于采用分页技术不易于实现存储共享，也不便于程序的动态链接程序的动态链接存储器管理存储器管理存储器管理存储器管理v分段存储管理方式的引入分段存储管理方式的引入 在分页存储系统中，进程的地址空间是一维在分页存储系统中，进程的地址空间是一维线性的，这破坏了程序内部天然的逻辑结构。线性的，这破坏了程序内部天然的逻辑结构。 基于模块化程序设计时，常常需要将一个大基于模块化程序设计时，常常需要将一个大任务划分成若干相对独立的子任务，对应于任务划分成若干相对独立的子任务，对应于子任务编写子程序。子任务编写子程序。存储器管理存储器管理v分段存储管理方式的

35、引入分段存储管理方式的引入 方便编程方便编程 LOAD 1, A | LOAD 1, A | 将分段将分段A A中中D D单元内容单元内容读入寄存器读入寄存器1 1中中STORE 1, B | STORE 1, B | 将寄存器将寄存器1 1中内容存中内容存入入B B分段分段C C单元。单元。 信息共享信息共享 信息保护信息保护 动态增长动态增长 动态链接动态链接 存储器管理存储器管理v分段分段 把程序按模块（独立的主程序，子程序，数把程序按模块（独立的主程序，子程序，数据段，工作区段）划分成段，每段有自己的据段，工作区段）划分成段，每段有自己的名字和长度，一个进程所包含的段是一个二名字和长度

36、，一个进程所包含的段是一个二维的虚拟空间。维的虚拟空间。 以段为单位分配内存，各段长度不等。以段为单位分配内存，各段长度不等。 采用采用动态划分技术动态划分技术，将物理内存动态的划分，将物理内存动态的划分成许多尺寸不相等的分区成许多尺寸不相等的分区存储器管理存储器管理v段表段表 记载进程的各个段到物理内存中分区的映射记载进程的各个段到物理内存中分区的映射 每个段将占据一个每个段将占据一个连续连续的存储区域，但各段之的存储区域，但各段之间不必连续间不必连续。段号段号012段首址段首址段长度段长度58K20K100K110K260K140K利用段表实现地址映射利用段表实现地址映射存储器管理存储器管

37、理v地址变换地址变换v段表寄存器段表寄存器 实现快速地址变换，用来存放实现快速地址变换，用来存放当前执行进程当前执行进程的段表在物理内存中的起始地址。的段表在物理内存中的起始地址。 当创建进程，将进程的程序和数据装入内存当创建进程，将进程的程序和数据装入内存时，系统为之建立段表，并将段表的起始地时，系统为之建立段表，并将段表的起始地址填入进程的址填入进程的PCBPCB中。中。 当进程被调度执行时，取出其当进程被调度执行时，取出其PCBPCB中的段表首中的段表首址，填入段表寄存器中。址，填入段表寄存器中。存储器管理存储器管理长度长度Cl始址始址Cb+段号段号S S 段内地址段内地址d比较比较比较

38、比较b + d段段表表S= Cl快表快表物理地址物理地址段表寄存器段表寄存器逻辑地址逻辑地址lb.Slb地址越界地址越界d=1d=1地址越界地址越界地址越界地址越界比较比较存储器管理存储器管理v有效消除了有效消除了内零头内零头，提高了存储利用率，提高了存储利用率v允许子程序独立编译和修改，而不需要重新编允许子程序独立编译和修改，而不需要重新编译或链接其它相关子程序译或链接其它相关子程序v容易实现存储共享容易实现存储共享v具有较高的安全保障具有较高的安全保障v很容易满足程序段的很容易满足程序段的动态增长动态增长需要需要存储器管理存储器管理分页系统分页系统分段系统分段系统页是物理单位页是物理单位段

39、是逻辑单位段是逻辑单位页的大小固定页的大小固定段的大小可变段的大小可变一维地址空间一维地址空间二维地址空间二维地址空间对用户透明对用户透明对用户可见对用户可见相同点：都采用非连续存储，由地址映射实现地相同点：都采用非连续存储，由地址映射实现地址变换址变换不同点：不同点：存储器管理存储器管理v可重入代码可重入代码 允许多个进程同时访问的代码，又称纯代码。允许多个进程同时访问的代码，又称纯代码。v假定物理块大小为假定物理块大小为4kB4kB，则代码占，则代码占4040个块，数据个块，数据去占去占1010个物理块。个物理块。n可容纳可容纳40个用户的多用户系统，用户共享一个个用户的多用户系统，用户共

40、享一个文本编辑程序，该程序有文本编辑程序，该程序有160KB的代码和的代码和40KB的数据区。则的数据区。则40个用户需要的空间数为：个用户需要的空间数为：若代码是可重入的，则可以共享。内存中只需一若代码是可重入的，则可以共享。内存中只需一份副本，需要内存空间为：份副本，需要内存空间为：存储器管理存储器管理存储器管理存储器管理分段系统中共享分段系统中共享editoreditor的示意图的示意图存储器管理存储器管理v产生背景：产生背景： 结合了段式与页式二者优点，克服了二者的缺点。结合了段式与页式二者优点，克服了二者的缺点。v基本思想：基本思想： 用户程序划分：按段式划分（即：按段的逻辑关用户程

41、序划分：按段式划分（即：按段的逻辑关系进行划分）；系进行划分）； 对系统讲：按页划分每一段。对系统讲：按页划分每一段。v逻辑地址逻辑地址v内存划分：按页式存储管理方案内存划分：按页式存储管理方案v内存分配：以页为单位进行分配内存分配：以页为单位进行分配段号段号段内地址段内地址页号页号页内地址页内地址段号段号页内偏移页内偏移段内页号段内页号存储器管理存储器管理v数据结构：段表与页表数据结构：段表与页表段号段号 页表长度页表长度 页表首址页表首址页号页号 块号块号页号页号 块号块号用户程序用户程序段表段表页表页表内存内存段0段段1段段2存储器管理存储器管理v地址变换过程地址变换过程存储器管理存储器

42、管理v动态地址变换过程动态地址变换过程 至少要访问三次以上的内存，即：至少要访问三次以上的内存，即： （1 1）访问段表）访问段表 （2 2）访问页表）访问页表 （3 3）访问物理单元）访问物理单元快表快表存储器管理存储器管理段号段号 段内页号段内页号 页内偏移量页内偏移量检索快表检索快表命中命中访问段表访问段表访问页表访问页表页在内存页在内存缺页中断处理缺页中断处理更新页表更新页表更新快表更新快表块号块号 偏移量偏移量是是否否是是否否逻辑地址逻辑地址物理地址物理地址存储器管理存储器管理v综合了分段和分页技术的优点，既能有效地利综合了分段和分页技术的优点，既能有效地利用存储空间，又能方便用户进

43、行程序设计。用存储空间，又能方便用户进行程序设计。v但是，实现段页式存储管理系统需要增加但是，实现段页式存储管理系统需要增加硬件硬件成本成本，系统的复杂度和管理开销也大大增加。，系统的复杂度和管理开销也大大增加。v因此，段页式存储管理技术适合于大、中型计因此，段页式存储管理技术适合于大、中型计算机系统，不太适合小型、微型计算机系统。算机系统，不太适合小型、微型计算机系统。存储器管理存储器管理存储器管理存储器管理v常规存储器管理方式的特点常规存储器管理方式的特点 一次性一次性（指全部装入）（指全部装入） 驻留性驻留性（指驻留在内存不换出）（指驻留在内存不换出）v在一较短的时间内，程序的执行仅局限

44、于某个部在一较短的时间内，程序的执行仅局限于某个部分；相应的，它所访问的存储空间也局限于某个分；相应的，它所访问的存储空间也局限于某个区域。区域。 时间局限性：循环操作时间局限性：循环操作 空间局限性：顺序执行空间局限性：顺序执行存储器管理存储器管理v基本思想：基本思想： 在进程运行前，先将当前要运行的少数页面在进程运行前，先将当前要运行的少数页面或段装入内存，另一部分暂时留在外存；进或段装入内存，另一部分暂时留在外存；进程运行时，当要执行的指令不在内存时，由程运行时，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作。系统自动完成将它们从外存调入内存工作。v目的：目的： 提高内

45、存利用率。提高内存利用率。存储器管理存储器管理进程执行进程执行页页/段在内存段在内存缺页缺页/段中断段中断内存已满内存已满页页/段置换段置换从外存装入页从外存装入页/段段更新页更新页/段表段表是是否否是是否否存储器管理存储器管理v虚拟存储器虚拟存储器 具有请求具有请求调入和置换调入和置换功能，能从逻辑上对内功能，能从逻辑上对内存容量加以扩充的一种存储器系统。存容量加以扩充的一种存储器系统。 逻辑容量由内存容量和外存容量之和所决定。逻辑容量由内存容量和外存容量之和所决定。 运行速度接近内存速度，每位成本接近于外运行速度接近内存速度，每位成本接近于外存。存。存储器管理存储器管理v 一、请求分页系统

46、一、请求分页系统 以页为单位进行置换以页为单位进行置换 需硬件（需硬件（1 1）请求分页的页表机制）请求分页的页表机制（2 2）缺页中断）缺页中断（3 3）地址变换机构）地址变换机构 需实现请求分页机制的软件（置换软件等）需实现请求分页机制的软件（置换软件等）v 二、请求分段系统二、请求分段系统 以段为单位转换以段为单位转换: :（1 1）请求分段的段表结构）请求分段的段表结构（2 2）缺段中断）缺段中断（3 3）地址变换机构）地址变换机构 需实现请求分段机制的软件（置换软件等）需实现请求分段机制的软件（置换软件等）存储器管理存储器管理v多次性多次性v对换性对换性v虚拟性虚拟性说明：虚拟性是以

47、多次性和对换性为基础的，而多次说明：虚拟性是以多次性和对换性为基础的，而多次性和对换性又必须建立在离散分配的基础上。性和对换性又必须建立在离散分配的基础上。存储器管理存储器管理存储器管理存储器管理v请求式分页也称虚拟页式存储管理请求式分页也称虚拟页式存储管理与与纯分页存储管理不同，请求式分页管理系统在进纯分页存储管理不同，请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入一个或程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根面；当内存空间

48、已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。据某种算法淘汰某个页面，以便装入新的页面。存储器管理存储器管理v请求分页需要解决的问题请求分页需要解决的问题 系统如何获知进程当前所需页面不在主存。系统如何获知进程当前所需页面不在主存。 当发现缺页时，如何把所缺页面调入主存。当发现缺页时，如何把所缺页面调入主存。 当主存中没有空闲的物理块时，为了要接受当主存中没有空闲的物理块时，为了要接受一个新页，需要一个新页，需要把老的一页淘汰出去，根据把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。什么策略选择欲淘汰的页面。存储器管理存储器管理v请求分页中的硬件支持请求分页中的

49、硬件支持 页表机制页表机制 缺页中断机构缺页中断机构 可在指令执行期间产生和处理中断信号。可在指令执行期间产生和处理中断信号。 一条指令可能产生多次缺页中断。一条指令可能产生多次缺页中断。页号页号物理块号物理块号状态位状态位P P访问字段访问字段A A修改位修改位M M外存地址外存地址存储器管理存储器管理存储器管理存储器管理Memory Management Unit 存储器管理存储器管理存储器管理存储器管理v 当进程要求装入新的页面或程序段时，如果当前没有足当进程要求装入新的页面或程序段时，如果当前没有足够的空闲空间，需要交换一些页面或段到外存，如果被够的空闲空间，需要交换一些页面或段到外存

50、，如果被交换出去的页面或段很快将被进程使用，则又需要将其交换出去的页面或段很快将被进程使用，则又需要将其换入内存。如果系统花费大量的时间把程序和数据频繁换入内存。如果系统花费大量的时间把程序和数据频繁的装入和移出内存而不是执行用户指令，那么称系统出的装入和移出内存而不是执行用户指令，那么称系统出现了现了“抖动抖动”。v 根本原因：选择的页面或段不恰当。根本原因：选择的页面或段不恰当。存储器管理存储器管理v 最小物理块数的确定最小物理块数的确定 最小物理块数：保证进程正常运行所需的最小物理块最小物理块数：保证进程正常运行所需的最小物理块数。数。v 物理块的分配策略物理块的分配策略 两种内存分配策

51、略：两种内存分配策略：固定分配策略：为每个进程分配固定数量的物理块，在固定分配策略：为每个进程分配固定数量的物理块，在进程的运行期间，其物理块数固定不变。进程的运行期间，其物理块数固定不变。可变分配策略：为每个活跃进程分配的物理块数在进程可变分配策略：为每个活跃进程分配的物理块数在进程的生命周期内是可变的。即，系统可以首先给进程分的生命周期内是可变的。即，系统可以首先给进程分配一定数量的物理块，进程运行期间，可以增加或减配一定数量的物理块，进程运行期间，可以增加或减少。少。存储器管理存储器管理 两种置换策略两种置换策略当系统欲把一个页面装入内存时，应当在什么范围内判当系统欲把一个页面装入内存时

52、，应当在什么范围内判断已经没有空闲物理块供分配？断已经没有空闲物理块供分配？ 局部置换局部置换：系统在进程自身所分到的物理块中判断当前：系统在进程自身所分到的物理块中判断当前是否存在空闲物理块，并在其中进行置换；是否存在空闲物理块，并在其中进行置换； 全局置换全局置换：在整个内存空间内判断有无空闲物理块，并：在整个内存空间内判断有无空闲物理块，并允许从其它进程所分到的物理块中选择一个页面换出内允许从其它进程所分到的物理块中选择一个页面换出内存。存。当指定的范围内没有空闲物理块时，应当从指定的范围当指定的范围内没有空闲物理块时，应当从指定的范围内选择哪个页面移出内存？内选择哪个页面移出内存？存储

53、器管理存储器管理存储器管理存储器管理 平均分配算法平均分配算法 将空闲物理块平均分配给各个进程。将空闲物理块平均分配给各个进程。 按比例分配算法按比例分配算法 根据进程大小按比例分配物理块。根据进程大小按比例分配物理块。 S S为页数总和，为页数总和，m m为物理块总数。为物理块总数。bibi是分到的物是分到的物理块数理块数 考虑优先权的分配算法考虑优先权的分配算法存储器管理存储器管理v调入页面的时机：系统应当在调入页面的时机：系统应当在何时何时把一个页面装把一个页面装入内存？入内存？ 预调页策略预调页策略 请求调页策略请求调页策略v确定从何处调入页面确定从何处调入页面 全部从对换区调入（前期

54、准备）全部从对换区调入（前期准备） 干净页从文件区调入，脏页从对换区调入干净页从文件区调入，脏页从对换区调入 UnixUnix方式方式 未运行过的页从文件区调入未运行过的页从文件区调入 运行过且被换出的页的从对换区调入运行过且被换出的页的从对换区调入v页面调入过程页面调入过程存储器管理存储器管理存储器管理存储器管理v不适当的置换算法可能导致系统出现不适当的置换算法可能导致系统出现“抖动抖动”现象。现象。v常用的页面置换算法：常用的页面置换算法： 最佳置换算法最佳置换算法 先进先出置换算法先进先出置换算法 最近最久未使用置换算法最近最久未使用置换算法 ClockClock置换算法置换算法 其它置

55、换算法其它置换算法存储器管理存储器管理v由由BeladyBelady于于19661966年提出的理论算法。年提出的理论算法。v基本思想：基本思想： 所选择的被淘汰页面，将是以后永不使用的，所选择的被淘汰页面，将是以后永不使用的， 或许是在最长或许是在最长( (未来未来) )时间内不再被访问的页时间内不再被访问的页面。面。无法实现u用于评价其他置换算法的性能用于评价其他置换算法的性能存储器管理存储器管理v基本思想：基本思想： 该算法总是淘汰最先调入主存的那一页，或该算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻者说在主存中驻留时间最长的那一页（常驻的除外）。的除外）。

56、n实现时实现时，只需把一个进程已调入内存的页，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个面按先后次序链接成一个队列，并设置一个指针，使它总是指向最老的页面。指针，使它总是指向最老的页面。存储器管理存储器管理vFIFOFIFO存在存在BeladyBelady现象现象 BeladyBelady现象产生的原因：现象产生的原因：FIFOFIFO算法的置换特算法的置换特征与进程访问内存的动态特征相矛盾，即被征与进程访问内存的动态特征相矛盾，即被置换的页面并不是进程不会访问的。置换的页面并不是进程不会访问的。 BeladyBelady现象现象：采用：采用FIFOFIFO算法时，如果

57、对一个算法时，如果对一个进程未分配它所要求的全部页面，有时就会进程未分配它所要求的全部页面，有时就会出现分配页面增多，缺页率反而提高的异常出现分配页面增多，缺页率反而提高的异常现象。现象。 BeladyBelady现象举例：现象举例：1 2 3 4 1 2 5 1 2 3 4 1 2 3 4 1 2 5 1 2 3 4 5 5抖动存储器管理存储器管理v 思想：思想： 依据局部性原理：如果一个页面最近被访问过，那依据局部性原理：如果一个页面最近被访问过，那么它将在不久的将来再次被访问。么它将在不久的将来再次被访问。 根据页面装入内存以后的使用情况，选择淘汰内存根据页面装入内存以后的使用情况，选择

58、淘汰内存中最近最久未使用的页面（根据历史判断）中最近最久未使用的页面（根据历史判断）v 实现方式：实现方式： 设置访问字段，用来标注该页最后一次被访问的时设置访问字段，用来标注该页最后一次被访问的时间。（系统开销大）间。（系统开销大）v LRULRU的缺点：的缺点：实现困难实现困难存储器管理存储器管理v寄存器寄存器 为了记录某进程在内存中各页的使用情况，为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存须为每个在内存中的页面配置一个移位寄存器，可表示为器，可表示为 : R=R: R=Rn-1n-1R Rn-2n-2R Rn-3n-3 R R2 2R R1 1R R0

59、0存储器管理存储器管理v 栈栈 将访问页面组织在一个堆栈中，最近访问的页面位于将访问页面组织在一个堆栈中，最近访问的页面位于栈顶，栈底的页面即是最久未被访问的。栈顶，栈底的页面即是最久未被访问的。存储器管理存储器管理v 简单的简单的ClockClock置换算法（置换算法（NRUNRU）最近未使用算法）最近未使用算法 为每页设置一位为每页设置一位访问位访问位，将内存中的所有页面通过，将内存中的所有页面通过链接指链接指针针链接成一个循环队列；链接指针指向上一次进行页面置链接成一个循环队列；链接指针指向上一次进行页面置换时被置换页面所在位置的下一个位置。换时被置换页面所在位置的下一个位置。 算法实现

60、要点如下：算法实现要点如下：（1 1）一个页面首次装入主存或被访问时，其）一个页面首次装入主存或被访问时，其“访问位访问位”置置1 1；（2 2）淘汰页面时，从指针当前指向的页面开始扫描循环队）淘汰页面时，从指针当前指向的页面开始扫描循环队列，把所遇到的列，把所遇到的“访问位访问位”是是1 1的页面的的页面的“访问位访问位”清清0 0，并跳过这个页面；把所遇到的并跳过这个页面；把所遇到的“访问位访问位”是是0 0的页面淘汰，的页面淘汰，指针推进一步；指针推进一步；（3 3）扫描循环队列时，如果遇到的所有页面的）扫描循环队列时，如果遇到的所有页面的“访问位访问位”均为均为1 1，指针就会环绕整个