第3章 存储管理 3.1 存储管理概述 3.2 基于连续分配的内存管理方法 3.3 基于离散分配的内存管理方法 3.4 虚拟存储管理

Presentation on theme: "第3章 存储管理 3.1 存储管理概述 3.2 基于连续分配的内存管理方法 3.3 基于离散分配的内存管理方法 3.4 虚拟存储管理"— Presentation transcript:

1 第3章 存储管理 3.1 存储管理概述 3.2 基于连续分配的内存管理方法 3.3 基于离散分配的内存管理方法 3.4 虚拟存储管理
第3章 存储管理 3.1 存储管理概述 3.1.1 计算机的存储器组织 3.1.2 存储管理的主要功能与目标 3.1.3 映射程序地址空间到主存 3.2 基于连续分配的内存管理方法 3.3 基于离散分配的内存管理方法 3.4 虚拟存储管理 补充部分必要的微机原理知识

2 3.1 存储管理概述 3.1.1 计算机的存储器组织 A Primary Memory(PM )
当今计算机都是基于冯诺依曼存储程序式，程序和数据在使用时都必须位于主存中。 3.1.1 计算机的存储器组织 A Primary Memory(PM ) 主存，hold data and programs the Executable Memeory(EM) 可执行内存---hold program images, 存储代码段的PM Secondary Memory(SM) --辅存 Visual Memory(VM) --PM+部分SM CPU Memory Manage Units—CPU的MMU registers Mov load PM/EM image SM:program saved

3 外存（secondary storage)
3.1.1 计算机的存储器组织 存储器组织，需要依据存储技术发展及CPU可寻址范围，在访问速度、容量和价格之间寻求平衡。 常见的微机存储器组织，是如图所示的“寄存器-高速缓存-内存-外存”结构 从上到下速度越来越慢，容量越来越大，单元价格越来越便宜。 虽然存储器容量在不断扩大、速度不断提高，但仍不能满足现代软件发展的需求。 存储器始终是计算机体系中的宝贵资源。 如何对它们进行有效管理，不仅直接影响到存储器的利用率，而且对计算机系统的性能有重大影响。 存储管理是OS一项非常重要的任务。 寄存器（registers) 高速缓存（caches) 主存（primary memory) 外存（secondary storage)

4 3.1.2 存储管理的主要功能与目标 ①内存分配与回收 ②实现有效的存储保护与共享 ③主存扩充（扩充主存的大小） ④提高主存的利用率
为每个进程创建执行空间，分配初始所需基本内存，并允许进程在执行中动态申请/释放内存。 ②实现有效的存储保护与共享 ③主存扩充（扩充主存的大小） 引入虚拟存储技术，用外存扩充主存数量，弥补物理内存数量的不足。 ④提高主存的利用率 采用合理得当的算法、策略和数据结构。 ☆提高计算机资源利用率的根本途径是采用多道程序设计技术，实现并发共享。

5 目标模块 (*.obj) (relocatable module) 可执行的装入模块the absolute module
3.1.3 映射程序地址空间到主存 源程序 (.c,.bas,.pas,for,…) 目标模块 (*.obj) (relocatable module) 编译 compile 连接或链接的三种方式 静态链接、装入时动态链接、运行时动态链接 加载装入的三种方式 绝对装入、可重定位的装入、运行时动态装入 可执行的装入模块the absolute module the program image 【多个目标模块】 +【库(.lib, .dll)】 连接 link 四个阶段 编译时Compile Time 连接时Link Time 加载时Load Time 运行时Run Time 加载/运行时需重定位部分 静态数据（全局变量） 地址变量、过程入口点 局部变量被安排在堆栈中

6 A UNIX-style memory Layout

7 第3章 存储管理 3.1 存储管理概述 3.2 基于连续分配的内存管理方法 3.3 基于离散分配的内存管理方法 3.4 虚拟存储管理
第3章 存储管理 3.1 存储管理概述 3.2 基于连续分配的内存管理方法 3.2.1 单一连续分配 3.2.2 固定分区分配(Fixed-partition) 3.2.3 动态分区分配(Variable-partition) 3.3 基于离散分配的内存管理方法 3.3.1 页式分配与管理 3.3.2 段式分配与管理 3.3.3 段页式分配与管理 3.4 虚拟存储管理 补充部分必要的微机原理知识 进程使用物理地址 一次性 完全分配 进程使用逻辑地址 部分分配 存储扩充

8 内存被划分为两个区域：系统区和用户区；应用程序装入用户区，可使用户区全部空间。
3.2.1 单一连续存储管理 内存被划分为两个区域：系统区和用户区；应用程序装入用户区，可使用户区全部空间。 特点 简单、易管理，适用于单用户/单任务的OS，如CM/P，DOS系统。 存在的问题 对内存空间要求少的程序，会造成内存浪费；对空间大以至装不下的大程序，要求用户自己基于覆盖/交换等技术进行解决； 程序全部装入，使得即使很少用到的程序部分也始终占用内存。

9 3.2.2 固定分区（fixed partitioning）
是把内存划分为若干个固定大小的连续分区，分区大小可相等也可不等； 一般是根据程序大小，选择分配当前空闲的、适当大小的分区。 优点： 易于实现，开销小。 缺点 内存片造成浪费（会有“内碎片”）； 分区总数固定，限制了并发执行的程序数量

10 固定分区的动态重定位机制

11 固定分区的保护实现机制 可保证在主存内运行时各进程的物理地址都不超越自己的上下界限。－－一旦超越将自动触发一个越界中断。

12 3.2.3 动态分区（可变分区） （1）基本分配、管理思想 （2）动态分区分配常采用的数据结构
OS初始化后，PM被配置为一个连续大整块(N0个单元) 随后依次启动pk个进程： 之后因不断经历进程释放和新进程创建，最终导致一个各进程空间区无序分配安排、且可能留下“小碎片(hole)”的内存布局分布图象。 若采用空间紧凑技术(compact)，代价非常昂贵。 （2）动态分区分配常采用的数据结构 空闲分区表(Free Block Table, FBT) 表项:大小|始址；存在问题：表目大小难以预先准确估计； 空闲分区链表(Free Block Chain, FBC) 双向链表，数据直接存储在各分区的头尾处 比较灵活，可双向搜索

13 可变分区分配常用的数据结构

14 几种常用的动态分区分配算法 首次适应算法(first-fit) 最佳适配法（best-fit） 最坏适配法（worst-fit）
该算法的分配和释放的时间性能很好，较大的空间分区可以被保留在内存高端。 但随着低端分区不断划分会产生较多小分区，每次分配时时间开销会增大。 最佳适配法（best-fit） 从个别看,外碎片较小；但整体上,会形成较多外碎片。 优点：较大的空闲分区可被保留。 最坏适配法（worst-fit） 不易导致小空闲区(碎片),但较大空闲分区不被保留。 循环首次分配算法(next-fit) 总是最后被分配分区的下一个空闲分区开始搜索。

15 一种典型的动态分区分配算法 //采用首次适应算法和FBC结构
long get_block(int x, byte * p) { //请求大小为X int i; long y; i=1; while ( FBC[i].size!=0 && FBC[i].size<x) i++; if (FBC[i].size ==0) {p=null; return 0 ;} p=FBC[i].addr; y=FBC[i].size-x; if (y>=delt) { FBC[i].size= y; FBC[i].addr= FBC[i].addr+x; } return x;

16 第3章 存储管理 3.1 存储管理概述 3.2 基于连续分配的内存管理方法 3.3 基于离散分配的内存管理方法 3.4 虚拟存储管理
第3章 存储管理 为进程分配的空间是连续的，且使用的地址为物理地址 3.1 存储管理概述 3.2 基于连续分配的内存管理方法 3.3 基于离散分配的内存管理方法 3.3.1 页式分配与管理 3.3.2 段式分配与管理 3.3.3 段页式分配与管理 3.4 虚拟存储管理 3.4.1 虚存管理的基本原理 3.4.2 基于请求分页的虚存管理技术 3.4.3 基于请求分段的虚存管理技术 3.4.4 段页式虚存管理技术 进程使用逻辑地址，采用一次性完全、离散分配，便于共享 进程使用逻辑地址，实现部分且离散分配 便于存储扩充与共享

17 (一)页式分配管理的基本思想 3.3.1 页式分配与管理 进程使用线性逻辑地址LA(32位、一维、连续)
OS透明地将线性地址分页， 即将32位地址划分为两段: p=[LA/页大小];d=LA-P*页大小 OS透明地将物理内存也按页大小(4k)划分一系列的页框(frame)，并进行依次编号 OS通过页映射表（页表），将进程地址空间的所有逻辑页，分别映射加载到不同的、不必连续的物理页框中。 进程Pi 页表 第0页 第1页 第2页 第3页 … 第m页 Frame_2 Frame_8 Frame_1 Frame_9 Frame_4 进程Pi 地址空间 物理内存 1 2 3 4 8 9 n 页号p 页内地址d （这里，设页大小为：4K） 优点：内存分配适应性更强；没有外碎片； 每个进程浪费空间不超过1个页。 缺点：仍要求程序一次性地全部装入内存。

18 （二）页式分配管理的数据结构

19 Procedure cmalloc(x, p) Begin
（三）页式管理的进程主存分配算法 Procedure cmalloc(x, p) Begin k:=x/block_size; p:=0; //分配失败返回0 if N>=k then begin p := get a PT; //申请一个页表区 for i=1 to k do pt[i] := get a free block; end; End ;

20 （四）页式分配管理的地址变换过程

21 （五）引入目录页的两级页表体系结构 具有两级页表的页式地址变换过程

22 （六）页式系统的共享实现方法示意图

23 3.3.2 段式分配与管理 （一）段式分配与管理的基本思想 按程序中的自然分段特性来划分逻辑空间，形成二维地址空间。
例如，序中主程序、子程序、静态变量、堆栈等，都是基于段的。 逻辑地址形式: (段号s,段内位移d)； 低级语言程序中用户可直接给出该形式地址，高级语言程序在编译后也可得到这种形式地址。 程序加载时，OS为所有的段分配所需内存，每个段被分配在一个连续分区；但进程中的各个段可离散分配到主存的不同分区； 在为每个段分配物理内存时，采用动态分区管理方法。

24 进程段表 (Segment Table,ST)
（二）段式分配管理的相关数据结构 进程用户空间段描述表 段长 | 属性 | 起始逻辑地址|段表项索引号 进程段表 (Segment Table,ST) 每个进程一张（套），被放置在系统空间 段长|段属性(保护码)|段基址 ☆进程局部描述符表(Local Descriptor Table, LDT) 描述可变分区的空闲段表（FBT或FBC） 用户空间中的一个逻辑段 加载/映射 需借助：FBT或FBC 物理主存的某个分区

25 Procedure cmalloc(k; s1,s2,…,sk; p) Begin
（三）段式存储分配的描述算法 Procedure cmalloc(k; s1,s2,…,sk; p) Begin p:=get a ST ; //获得一个存放段表的空间 for i=1 to k do begin ST[i] = get a region; //获得一空闲的分区 if fail then begin p:=0; break; end; end; End ;

26 （四）段式地址变换机制 变换映射的 核心数据结构

27 （四）段式地址变换过程（简明示图）

28 相同点 不同点， ★段式和页式分配管理－－对比 均为离散分配方式； 都通过地址映射机构来实现地址变换。
两者在概念上有很大不同：页是信息的物理单位，是由OS透明实现的；段是信息的逻辑单位，可更好、更自然满足程序设计需要，更便于实现信息共享。 页长固定,由系统决定；段长则不固定。 页式系统中，用户使用的是一维线性地址(分页对用户透明)；在段式系统中，用户使用的二维地址(段号:段内地址) 页式系统存储分配的适应性更大，浪费的空间更少。

29 （一）段页式系统分配管理的基本思想 （二）动态地址变换所依赖的数据结构 3.3.3 段页式分配与管理 逻辑空间的管理，与段式系统相同；
先分段，对每个段再进行分页； 对用户而言，段页式系统与段式系统是一样的； 用户逻辑地址仍是“段号:段内位移”，系统按页式管理，透明地，将段内位移划分为页号:页内位移. 系统实际使用逻辑地址：段号(s)|页号(p)|页内位移 对物理空间的管理，与页式系统相同。 （二）动态地址变换所依赖的数据结构

30 3.3.3 段页式分配与管理 （一）段页式系统分配管理的基本思想 （二）动态地址变换所依赖的数据结构 （三）动态地址变换 每个进程:
一个段表；多个页表(每段一个页表)； 段表项中原‘段基址’栏，改为‘段页表基址’ 进程段表及相关各段页表，都放在系统空间；实际系统中，进程各段的页表通常被组织在一起，构成一套进程页表。 （三）动态地址变换 首先通过逻辑段号，查段表,获得所在段的页表基址; 通过逻辑地址页号，查前步所得页表，得到页框号； 由“页框号:页内地址”，即可计算出内存物理地址。 进行一次访问需三次访问内存；仍可采用联想存储器解决。快表关键字:段号/页号；快表值:页框号:属性值

31 3.3.3（三）段页式系统的地址转换过程

32 ☆一种更简单的段页式系统实现方法 每个进程一个段表, 一个页表 经段式系统的地址变换过程产生的地址，不作为是物理地址，而是作为线性地址。
对线性地址，再按页式系统方法，映射变换到主存物理地址。

33 第3章 存储管理 3.1 存储管理概述 3.2 基于连续分配的内存管理方法 3.3 基于离散分配的内存管理方法 3.4 虚拟存储管理
第3章 存储管理 3.1 存储管理概述 3.2 基于连续分配的内存管理方法 3.3 基于离散分配的内存管理方法 3.4 虚拟存储管理 3.4.1 虚存管理的基本原理 3.4.2 基于请求分页的虚存管理技术 3.4.3 基于请求分段的虚存管理技术 3.4.4 段页式虚存管理技术 3.4.5 用户空间虚存分配与管理方法

34 3.4.1 虚存管理的基本原理 （一）局部性原理 （二）虚拟存储器实现的基本原理
程序在执行过程中的一个较短时期，所执行的指令地址和操作数地址，将局限于一定区域内。 程序执行活动具有：时间局部性和空间局部性。 （二）虚拟存储器实现的基本原理

35 3.4.1 虚存管理的基本原理 （一）局部性原理 （二）虚拟存储器实现的基本原理
程序装入时,不必将其全部读入内存，只需将当前执行需要的部分页(或段)装入内存，就可让程序开始执行。 在程序执行过程中，如需访问尚未在内存的逻辑地址单元(缺页或缺段)，则OS通过相应机制将所缺页(段)装入内存----消除缺页(段)故障。 另一方面，OS还将暂时不用的页(段)调出内存，以腾出更多的可用内存空间。 从用户的角度看，系统好象提供了比实际内存更大的存储容量－－这种虚拟扩展的存储体系，常被称为“虚拟存储器”

36 3.4.1 虚存管理的基本原理 （一）局部性原理 （二）虚拟存储器实现的基本原理 （三）虚拟存储技术的优势 （四）虚拟存储的主要实现方式
能给用户提供大于实际物理内存的虚拟存储器，允许在较小内存中执行较大进程，并可在有限主存中容纳更多的并发进程。 与覆盖技术相比，虚拟存储实现对用户透明，不影响用户编程结构，用户可在高达232的虚空间编制程序。 （四）虚拟存储的主要实现方式 请求分页；请求分段；请求段页式 （五）虚拟存储的基本特征 离散性；多次性；对换性；虚拟性

37 3.4.2 基于请求分页的虚存管理技术 请求分页的虚存系统需对页式系统进行如下几方面的扩充：
对页表的页表项(PTE)进行扩展，增加一些必要的管理标志位（它们占用PTE原先恒为0的低位段，故并不需要扩大PTE的大小）。 (不需增加新的硬件或设施) 增加可有效处理缺页(故障) 的相关设施和机制(硬件) 增强页面调度管理能力（软件扩展） 选用合适的页面调入策略、页面置换策略和页面置换算法； 增强对系统及各进程驻留页面集，即“工作集”的有效管理，降低系统缺页率，提高系统性能。(软件扩展) 支持自动选取/设定工作集大小，及动态维护、修剪工作集。 增加对物理页框的管理，以支持更有效的页面调度和工作集管理 (软件扩展) 增加页框状态描述数据库，该库可直接存储在相关页框中。

38 3.4.2（一）请求分页系统的页表项(PTE) 本示图只是集中说明了请求分页系统PTE中可能会设置的一些重要标志位，与实际系统未必吻合
不同OS的PTE如何编排或如何组合通常会有差异，有些OS本身也会有多套编排组合。

39 要求CPU(硬件)能提供对缺页中断支持，能根据页表项中的相关标志位，判断当前页是否有效--是否要产生缺页中断。
3.4.2（二）请求分页系统的缺页中断处理 要求CPU(硬件)能提供对缺页中断支持，能根据页表项中的相关标志位，判断当前页是否有效--是否要产生缺页中断。 缺页中断是一种比较特殊的中断，体现在： 在指令执行期间产生和处理缺页中断 常规外部中断，是在每条指令执行完毕后，检查是否有中断请求到达。 一条指令可能产生多次中断。 当从中断处理程序返回时，能正确执行原先产生缺页故障的指令。 对无效页面的一次访问称为“缺页故障”，内核中断处理程序将这类错误处理调派给内存管理的故障程序。

40 当发生缺页故障时，OS会向外存(页文件或页映射文件)发出读操作调入相关页面；
☆页面调入I/O 当发生缺页故障时，OS会向外存(页文件或页映射文件)发出读操作调入相关页面； 页面调入I/O操作是同步的，即线程会进入睡眠等待直到I/O完成（‘等待事件’到来）被唤醒。 对同一进程的多个线程(并发)，若遇到同位置缺页故障，可串接到同一等待事件中. 页面调入I/O代码也必须能识别处理调入完成后，相关页表项的情况变换。

41 ☆缺页处理基本过程

42 3.4.2（三）请求分页系统的页面调度管理 1. 页面调入策略 2. 置换页面策略 3.置换页面算法
请求调页(demand paging)：发生缺页时，只调入目标页。实现简单，但易导致更多I/O次数。 预调页：在发生缺页需调入某页时，同时预调入该页的若干个相邻页。 待调入页面来源 进程装入时，将其全部复制到交换区(页文件)，以后总是从交换区调入，速度较快。 凡是未被修改页，都从映射文件区调入，被置换时不必调出；已修改页，被置换时调出到交换区，以后从交换区调入 2. 置换页面策略 固定分配局部置换；可变分配全局置换；可变分配局部置换。 3.置换页面算法 置换页面策略下，选择下一个被置换页的算法

43 置换页面算法 可利用“栈方法”实现对LRU算法的支持 利用一个特殊的栈来保存当前使用的各个页面的页面号。
每当进程访问该页时，便将该页面号从栈中移出，将它压入栈顶。 栈顶始终时最新被访问的页面的编号，而栈底是最近最久未被使用的页面号。 最佳算法(optimal, OPT) 选择未来最长时间不使用页进行置换(最理想算法) 先进先出算法(FIFO) 最不常用算法(Least Frequently Used, LFU) 选择到至今访问次数最少的页进行置换，要设置一个页面访问计数器。 最近最久未使用算法(Least Recently Used, LRU) 选择内存中至今最久未使用页面进行置换； 是局部性原理的合理近似，性能接近最佳，但硬件开销较大。 时钟算法(clock) 改进的时钟算法（结合访问位A和修改位M）

44 置换页面算法 最佳算法(optimal, OPT) 注意，新页面被调入某页框时，页框上的所有标志位或访问计数等，均要进行复位！
先进先出算法(FIFO) 最不常用算法(Least Frequently Used, LFU) 最近最久未使用算法(Least Recently Used, LRU) 时钟算法(clock) 也称最近未用算法(Not Recently Used,NRU)，是LRU和FIFO的折衷。每页框有个使用位(use bit,ub)，若该页被访问ub=1。 所有驻留页面组织为类似时钟的环形缓冲池，置换时采用一个类时钟指针，从当前指针位置开始顺时针搜索检查ub=0的页框，选择首个遇到的ub=0的页框进行置换。 改进的时钟算法（结合访问位A和修改位M） 第一轮候选对象：A=0∧M=0，失败进入下一轮 第二轮候选对象：A=0∧M≠0， ，失败进入下一轮 第三轮，先将所有目标驻留页面框的A复位，再从满足A=0∧M≠0的候选页面框中，进行一轮选择。 注意，新页面被调入某页框时，页框上的所有标志位或访问计数等，均要进行复位！

45 实例：比较OPTIMAL与FIFO算法性能

46 实例：比较OPTIMAL与LRU算法性能

47 计算机系统访问内存的速度远高于访问外存。若经常发生缺页中断，就需不断从外存调页到内存，就会大大降低系统性能。
3.4.2（四）工作集与驻留集（1） 计算机系统访问内存的速度远高于访问外存。若经常发生缺页中断，就需不断从外存调页到内存，就会大大降低系统性能。 通过对缺页率的长期研究，Denning于1968年，基于程序工作的局部性原理，提出了工作集理论。 Denning的工作集理论 将在某个时间间隔Δ内，进程实际要访问的页面集合，称为工作集。 将进程驻留物理内存的页面子集，称为“驻留集” 如果能预知进程程序代码在某段时间内要访问那些页面，并将它们提前预调入内存，使“驻留集”接近“工作集”就可降低缺页率，提高CPU利用率。 将进程在时间t的工作集记为w(t,Δ), Δ称为工作集的窗口尺寸，它与系统工作集大小、维护策略密切相关，正确选择Δ的大小，对物理内存利用率和系统吞吐率有重要影响。

48 进程创建时,OS为它分配一定数量的初始页框。
3.4.2（四）工作集与驻留集（2） 工作集分类 系统工作集；进程工作集（每个进程一套）。 相应地，“驻留集”也可进行类似的分类。 进程创建时,OS为它分配一定数量的初始页框。 若系统采用可变分配策略，则进程可在执行过程中根据需要，动态增加工作集/驻留集大小； 当进程工作集大小达到它的预定上界，或者由于其它进程对内存需求时，内存管理器就会启动进程工作集的修剪，以腾出页框。 如果缺页故障发生时，物理内存已满，“置换策略＋置换算法”被用来确定内存中那个页面被移出，以便为新页腾出空页框。 单CPU体系下，使用可变分配全局置换的LRU或改进时钟算法较普遍。 多CPU体系下，用局部FIFO置换策略/算法较普遍。

49 3.4.5 用户空间虚存分配与管理方法 以页为单位的虚拟地址分配方法 内存映射文件方法(类似：段页式) 堆分配方法
引入虚拟地址描述符(VAD)树进行描述，VAD的建立与PTE的建立基本同步；(Linux: mm_struct, va_area_struct) 分配空间具有：‘仅保留’和‘提交’两类。 采用“懒惰计算”的请求页面调度和映射策略； 内存映射文件方法(类似：段页式) 采用基于区域对象的虚存分配数据结构; 常用于以下三种目的： 加载或执行.exe和.dll，不需对文件进行缓存； 访问大型数据文件，减少文件I/O次数； 实现多进程间的数据共享（共享内存）（内存页） 堆分配方法 堆是保留的地址空间中一个或多个页组成的区域； 该区域可用堆管理器(一组函数)按小块划分和分配;

50 区域对象的创建、映射，以及其相关数据结构
有效 已打开的 文件对象 每个共享进程一套

51 建区域对象时，系统会同时创建该区域的虚拟段结构描述和各相关原型页表项，返回区域对象句柄号。
区域对象的应用方法 建区域对象时，系统会同时创建该区域的虚拟段结构描述和各相关原型页表项，返回区域对象句柄号。 Win32 API: CreateFileMapping() 其它进程可通过OpenFileMapping()获得同一映射文件的区域对象句柄号。 不同进程借助区域对象句柄号，可将同一区域对象“分别映射”到自己的地址空间中 。 Win32 API: MappingViewOfSecting() 内在：建立相关的页表项； 外在：返回区域相同用户进程空间的虚基址和长度。