第九章 存储管理 9.1 概述 一、存储器的层次：三级存储器结构 本章主要讨论几种常用的内存管理技术。 Cache 内存 外存 由硬件寄存器

Presentation on theme: "第九章 存储管理 9.1 概述 一、存储器的层次：三级存储器结构 本章主要讨论几种常用的内存管理技术。 Cache 内存 外存 由硬件寄存器"— Presentation transcript:

1 第九章 存储管理 9.1 概述 一、存储器的层次：三级存储器结构 本章主要讨论几种常用的内存管理技术。 Cache 内存 外存 由硬件寄存器
第九章 存储管理 9.1 概述 一、存储器的层次：三级存储器结构 本章主要讨论几种常用的内存管理技术。 Cache 内存 外存 由硬件寄存器 构成，速度等 同于电子线路 的开关速度 由顺序编制的 单元组成的一 维数组 内存的后备支 持，如：磁盘 、磁带 Cpu可以 直接访问 只有通过 内存，cpu 才能访问 存取速度增加 成本增加 容量减少 计算机软件技术基础 存储管理

2 9.1 概述 二、用户程序的处理过程 静态链接：进行事先链接，以后不再拆开的链接方式
装入时动态链接：便于实现目标模块的共享：实现多个模块共享一个模块、而不要每个程序都含有该模块的拷贝。 运行时动态链接：在运行期间需要一个模块才装载一个模块 绝对装入方式：按模块中的地址，将程序和数据装入到内存对应位置。 可重定位方式：在装入程序时，根据当时内存的实际使用情况，重新调整装入的内存位置，把程序装入到内存的适当地方。 9.1 概述 二、用户程序的处理过程 执行 代码 数学 模型 源 程序 目标 模块 装配 编辑 用PL 编译 连接 符号、名字 浮动地址 （以0为基地址） 相对地址 （同一的外部 访问地址） 内存的 物理地址 汇编 计算机软件技术基础 存储管理

3 9.1 概述 三、地址重定位（映射）---Relacation 定义：把程序中的逻辑地址变成内存中的物理地址的过程。
名字空间：编程人员采用相对地址来编程，其源程序存放的空间 地址空间：经汇编或编译后其目标程序占有的地址范围称为地址空间；这些地址编号是相对于起始地址而定的，称为逻辑地址或相对地址。 存储空间：存储空间是目标程序装入内存后占用的一系列物理单元的集合，这些单元编号称为物理地址或绝对地址。 2. 三大地址空间的关系 绝对目标程序 (绝对地址.物理地址) 名字空间 地址空间 存储空间 源程序 (名字/符号) 相对目标程序 (相对地址.逻辑地址) 编译 连接 地址重定位 计算机软件技术基础 存储管理

4 三、地址重定位（映射） x’ = x + D 物理地址 逻辑地址 下界地址—内存中的起始地址 3. 重定位的两种方式
重定位：当用户程序调入内存时，需把相对地址转换为绝对地址，同时要对程序中与地址相关的指令进行修改，这一过程称为重定位。 静态重定位 在程序装入时进行，通过处理机中的一对界地址寄存器来实现；界地址寄存器分为下界和上界地址寄存器，分别存放该作业在内存中的起始和终止地址，程序中的逻辑地址与下界地址相加得到物理地址，见图示。 x’ = x D 物理地址 逻辑地址 下界地址—内存中的起始地址 计算机软件技术基础 存储管理

5 三、地址重定位（映射） 逻辑地址空间 x L D 上界 下界 界地址寄存器 物理地址空间 x’ 时机：在程序执行之前进行；
实现：由装配程序根据将要装入的内存起始位置直接修改装配模块中的有关使用地址的指令。 特点：一次性全部完成，一旦装入内存，不能再移动。 性能分析： 优点---实现简单，不需要硬件机构； 缺点---程序重定位之后就不能在在内存中移动；要求程序的存储空间是连续的，不能放在若干个不连续的区域内。 计算机软件技术基础 存储管理

6 三、地址重定位（映射） (2)动态重定位 在程序执行过程中进行，当CPU访问内存指令时由动态变换机构自动进行地址转换。
实现：装配模块不加任何修改而转入内存，由定位寄存器和加法器硬件完成。 特点：部分、动态地完成。 性能分析： 优点---程序装入内存之后再搬迁也不会影响其正确执行；每个目标模块装入的存储区不必顺序相邻，只需要各自对应的定位寄存器即可。 缺点---需要硬件支持。 计算机软件技术基础 存储管理

7 三、地址重定位（映射） 100 300 400 LOAD 1，300 5678 1000 1100 1300 1400 LOAD 1，1300 内存 + 例： 计算机软件技术基础 存储管理

8 9.1 概述 四、存储管理的功能 多道并发环境中内存管理面临的问题： 防冲突； 保护OS； 合理分配； 扩充；虚---实。 2. 主要功能：
内存的分配与回收； 地址重定位； 内存信息的共享与保护:为了保护存储区内各类程序和信息不受某些错误程序的破坏和干扰，须采取保护措施。 内存的扩充（满足用户对内存超容量要求）:当作业的地址空间大于分配到的存储空间时需采取内存扩充技术，将内外存联合起来扩大存储空间，常采用的内存扩充技术有覆盖、交换和虚拟存储技术。 内、外存数据传输的控制。 目标：安全、高效、方便、最大限度地提高内存的利用率。 计算机软件技术基础 存储管理

9 9.2 早期的存储管理技术 ---分区式分配方式 一、固定式分区（静态分区） 目的：为了满足多道程序设计思想。
方法：将内存划分为若干个分区，每个分区分配给一个作业，用静态重定位方式进行地址转换，提供必要的保护手段，保证各作业互不干扰。在分区的划分方式上有固定分区和可变分区两种。 一、固定式分区（静态分区） 思想：存储器事先被划分为若干个大小不等的分区，系统为每个分区设置一个目录，说明该分区的大小、起始位置、分配状况等信息，所有分区目录构成一个分区说明表；用户为每个作业规定所需的最大存储量，存储管理程序负责找出一个足够大的分区分配给此作业。一旦划分好，在系统运行期间不再重新划分。 实施：通过分区说明表实行内存管理。 计算机软件技术基础 存储管理

10 一、固定式分区 Job A(6k) Job B(25k) 20k 28k 60k 124k OS ………… Job C(40k) 256K
20k 28k 60k 124k OS Job A(6k) ………… Job B(25k) Job C(40k) 256K 第一分区 第二分区 第三分区 第四分区 132K (b)内存分配图 区号 大小 起址 标志 1 8K 20K 已分 2 32K 28K 3 64K 60K 4 132K 124K 未分 (a)分区说明表 A(6k) B(25k) C(40k) D(150k) (c)后备队列作业 性能：分区大小固定，状态表的结构可以是顺序表也可以是链表；实现了多个作业共享内存；分区的分配和回收算法简单；缺点是内存利用不充足，有“碎片”，即作业所需空间和分区大小不一定恰好相等。 计算机软件技术基础 存储管理

11 9.2 分区式分配方式 二、可变式分区（动态分区） 图 2 控制信息区
L link tag size R link Up link 9.2 分区式分配方式 图 2 控制信息区 二、可变式分区（动态分区） 思想：又称动态存储管理，只有当作业调入内存时，才按作业大小建立分区，当作业执行完后又释放此空间。采用链结构来构造分区目录。下面从空间的分配和回收来进行讨论。 空间分配：由于多作业调入内存运行，有些作业运行结束后释放所占空间，内存区呈现占用块与空闲块交叉存在的状态，如图1所示。在每块开始与结束的几个字节中存放有关本块状态的信息，称为控制信息区，并把所有的空闲块链成一个双向链表，如图2所示。其中,Llink和 Rlink为链表左右指针，tag=0表示空闲块，tag=1表示占用块，size是本块的大小，Uplink为本块的起始地址。 图 1 占用块 空闲块 P1 P3 P4 P6 P8 计算机软件技术基础 存储管理

12 二、可变式分区 空间分配例题 设某系统用户区大小为5000字节，地址为1 ～ 5000，初始状态如下图a所示，依次分配给5个作业P1 ～ P5, 作业占用区大小分别为1000，300，600，900，700。 P0 为余下的空闲块，各占用块和空闲块情况如下页图b和c所示。 P1 P2 P3 P4 P5 P0 1000 300 600 900 700 1500 图 a 计算机软件技术基础 存储管理

13 占用块、空闲块表示图 1 1301 1001 1 1000 P1 1 600 P3 1 300 P2 2801 1901 1 700 P5 1 900 P4 图b—占用块 av 3501 1500 P0 图c—空闲块

14 二、可变式分区 空间回收：当作业执行完毕后，系统将空间收回，插入到空闲块链表中，但插入时还要判断左右相邻块是否空闲，若是则合并成一个较大的空间,它可通过每一块中头尾的控制信息区的tag标志来判断。设当前回收块起始地址为p,大小为n,则应判断它左邻居p-1和右邻居p+n的tag是否为0，若不为0则将当前回收块插入到空闲块链表中。若出现有tag为0的相邻块，则应修改原空闲块的大小，将本回收块和相邻块合并。如下图。 n 左邻居 右邻居 P-1 P P+n 计算机软件技术基础 存储管理

15 二、可变式分区 空间回收例题 在空间分配例题中，当作业P4完成后，应回收P4分区到空闲块链表中，见图a；当P5作业完成后，回收使由于其左右邻居均为空闲块，因此应进行合并，见图b所示。 计算机软件技术基础 存储管理

16 空间回收过程图 av 图a P1 P2 P3 P4 P5 P0 P4 释放 1901 3501 1500 P0 900 P4 P1 P2
1500 P0 900 P4 图a P1 P2 P3 P4 P5 P0 P5释放 av 1901 3100 P0+ P4 + P5 图b

17 二、可变式分区 分配算法： 最新适应算法(First-Fit)：空闲表按空闲块的物理起始地址递增次序排列，分配时，从第一块依次查找，找到第一块能容纳作业的空闲块就停止。 最佳适应算法(Best-Fit)：空闲表按空闲块的大小递增次序排列，分配时，从第一块依次查找，找到第一块能容纳作业的空闲块就停止。 最差适应算法：将空闲块链表中不小于n且是链表中最大空闲块的一部分分配给用户。 计算机软件技术基础 存储管理

18 二、可变式分区 5. 性能分析 最新适应法通常适用于实现不能掌握运行时可能出现的分配情况。 最佳适应法适用于请求分配内存大小范围较广的系统；
最差适应法每次都从内存中取最大的结点进行分配，从而使链表中结点大小趋于均匀，适用于请求分配内存较均匀的系统； 从时间上比较， 最新适应法分配时需查询空闲块链表，但回收时只要插入到表头即可； 最差适应法分配时不需查询链表，而回收时要将剩余部分插入链表适当位置； 最佳适应法无论分配和回收，均需查找链表，最费时间。 计算机软件技术基础 存储管理

19 9.2 分区式分配方式 三、多重式分区 一个作业装入内存中多个不一定相邻的分区。 优点：灵活利用内存； 缺点：碎片小了，但可能数量更多。
计算机软件技术基础 存储管理

20 9.2 分区式分配方式 四、可重定位式分区（紧缩分区） 1. 思想：为了是分散的小的空闲区得到合理使用，把所有的碎片拼接成一连续的空闲区。
2. 实现：向一个方向移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。 3. 问题： 地址项的修改---能够对作业重新定位； b. 紧缩时机: 回收时进行---每当作业结束,释放所占分区时; 分配时进行---当新作业到来又没有能容纳的空闲区分配时; 4. 性能：消除了碎片，提高了内存利用率；但花费了大量的cpu时间。 计算机软件技术基础 存储管理

21 9.2 分区式分配方式 五、分区管理的存储保护 界地址法：系统设置一对上、下界寄存器，每当选中某个作业运行时，先将它的界地址装入这对寄存器中，作业运行时形成的每一个访问存储器的地址都要同这两个寄存器的内容进行比较，若超出这个指定范围，便产生越界保护性中断，转去执行错误处理程序； 采用一对基地址、限长寄存器，原理同前，但此时基址寄存器还起着定位寄存器的作用。 计算机软件技术基础 存储管理

22 9.3 多道程序对换技术 引入：最早用于分时系统中提高内存利用率的一种内存扩充技术。
思想（roll-in roll-out）：把内存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存(磁盘)，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存。 实现：由换入和换出两个过程构成的交换进程完成。 核心问题：保证对换信息量要最少---只要保证当前正在执行的用户进程在内存中完整保存。 技术支持 一般都有动态重定位机构---因而一个作业换入内存时不一定要装入它被换出前所占据的区域中. 需要较多软件的支持. 计算机软件技术基础 存储管理

23 9.4 虚拟存储器的概念 一、引入目的： 为了解决分区存储管理中，当某作业需求空间大于内存物理空闲空间时，该作业无法运行的问题。 二、思想：
在程序执行过程中，把不经常被进程访问的程序段和数据放在外存中，待需要访问它们时再将它们调入内存。（部分装入内存） 三、意义： 简化设计、利于多道并发、运行更快 计算机软件技术基础 存储管理

24 9.4 虚拟存储器的概念 四、虚拟存储器： ① 虚拟地址：程序访问的逻辑地址。 ② 实在地址：处理器可直接访问的主存地址。
是指仅把作业的一部分装入内存便可运行该作业的存储器系统，具有请求调入和置换功能。 ① 虚拟地址：程序访问的逻辑地址。 ② 实在地址：处理器可直接访问的主存地址。 ③ 虚拟地址空间：虚拟地址的集合。 ④ 实在地址空间：计算机主存。 五、物质基础 二级存储器(内/外存)---实现内/外存有机联系; 动态地址转换机构(DAT)---实现动态定位. 计算机软件技术基础 存储管理

25 9.4 虚拟存储器的概念 实际上用户的虚拟地址空间并不可能是无限大，它受到以下两个条件制约： 1. 指令中地址场长度的限制。
1. 指令中地址场长度的限制。 2. 外存储器容量的限制。 虚拟存储管理技术需要解决的问题： （1）什么时候把哪部分程序装入内存。 （2）放在内存什么位置。 （3）当内存空间不足时，把哪部分程序淘汰出内存。 常用的虚拟存储技术有： 分页存储管理、分段存储管理、段页存储管理。 计算机软件技术基础 存储管理

26 9.5 请求分页式存储管理 一、分页式存储管理（静态分页） 1. 分页管理的基本概念 (1)页面、页架（块）
把每个作业的地址空间分成一些大小相等的片，称为“页”。 把内存的存储空间也分成大小与页相同的片，称为“页架”或者“块”。系统以页架为单位把内存分配给各作业，每个作业占有的内存无须连续，而且作业的所有页面也不一定同时装入内存。 计算机软件技术基础 存储管理

27 一、分页式存储管理（静态分页） 例题 假设系统选择页的大小为1k字节，则一个3k字节的作业将被划分为3页。此时主存有5个空白块（块2、3、8、9、11）。因此，当作业2的三块装入内存时可以选择任意3个空白块。图中假定第0页装入主存的块2中，第一页装入块3中，第2 页装入块8中（主存中块9和块11空闲）。 计算机软件技术基础 存储管理

28 分页映射存储图 主存空间 页架号 地址空间 0-1块 2k 100 2块 页号 页架号 3k 1k 4k 2k 5k 作业1 6k 2500
操作系统 Load 1,2500 第0页 第1页 第2页 12345 0-1块 Load 1,2500 12345 2k 作业2第0页 100 2块 页号 页架号 3k 作业2第1页 2 1 3 8 1k 4k 2k 5k 作业1 6k 2500 作业2的页表 7k 作业3 3k 8k 8块 作业2第2页 作业2的地址空间 9k 10k 作业3 11k 12k 计算机软件技术基础 存储管理

29 一、分页式存储管理（静态分页） (2)分页系统中的地址结构
在分页系统中，每个虚拟地址用一个数对（p,d）来表示，其中p为页号，d是该虚拟地址在页面号为p中的相对地址，称为页内地址。为计算方便，规定页的大小为2的幂。 (3)页表与页表地址寄存器 页表：系统为每个作业建立一个页面映像表（PMT），简称“页表”。页表中应包括：页号、页架号、状态。 页号：作业各页的页号，每个作业页号从零开始。 页架号：该页面在内存中的页架号。 状态：表示该页是否在内存中，用“0”表示该页不在内存，用“1”表示在内存中。 计算机软件技术基础 存储管理

30 一、分页式存储管理（静态分页） 2. 分页管理的原理 各进程的地址空间(虚拟空间)被划分成若干个长度相等的页(Page),此时
进程的逻辑地址(虚地址)=页号(P)+页内地址(位移d) 同样地把内存空间按与页相等的长度划分成相等大小的块(存储块); 由页表PT(存放每页的首地址)把页式虚地址与内存物理地址进行一一对应映射; 由硬件地址变换机构实现动态地址转换。 计算机软件技术基础 存储管理

31 一、分页式存储管理（静态分页） 算法思想：
当某作业被调度到处理器上运行时，操作系统自动将该作业的页表的起始地址和长度装入页表地址寄存器中，当CPU执行一条访问内存指令时，地址变换机构把逻辑地址分解成p和d两部分， p为页号，d为页内地址。按照p在页表中找到相应的页架号和状态，若状态为“1”，将页架号与页内地址合并为内存实在地址。若状态为“0”，表明此页不在内存中，系统将产生中断，停止执行用户程序，由存储管理模块将该页调入内存。 计算机软件技术基础 存储管理

32 一、分页式存储管理（静态分页） 例题: 假如某系统页面大小为（512)10字节，即相当于（1000)8字节，若逻辑地址为（1320)8，就可以方便的分解得到p=1,d=320. 由p及页表起始地址b，找到相应的页，将该页对应的页架号10送入地址变换机构p’,与页内地址d合并成内存实在地址号10320。 计算机软件技术基础 存储管理

33 分页系统中的地址转换 页架号 分页管理的地址转换图 8进制地址表示 地址空间 地址变换机构 p’ 1000 1320 2000 3000 p
1000 1320 2000 3000 p d Load 1,1320 23285 d 主存空间 页架号 10 320 1 320 … 23285 页号 页架号 状态 1 3 1 10 2 页表 10320 10 页表长 页表起始地址 L b 页表地址器存器 分页管理的地址转换图

34 一、分页式存储管理（静态分页） 3. 说明 页长的划分和内存大小以及内外存之间的传输速度有关；
有效地址---页号（P）和页内位移（d）的计算： a. 软件实现： 若虚地址为A，页面大小为S，则： P=A div S A整除S，商为P，余数为d d=A mod S b. 硬件实现：若页面大小为2的n次方，则A(m位) 中低n位是页内位移d, 其余高(m-n)位是页号的值。 计算机软件技术基础 存储管理

35 9.5 请求分页式存储管理 二、请求分页存储管理系统（动态分页）
依据：局部性原理---程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅限于某个部分；相应地，它访问的内存空间也局限于某个区域。 设计思想：允许只装入若干页（而非全部）的用户程序和数据，便可启动运行，以后根据请求陆续把即将要运行的页面调入内存。初启时，只装入第一页。 实现：在分页系统的基础上，增加请求调页功能和页面置换功能。 技术措施： 请求分页的页表机制--对纯分页页表进行扩展 页号 块号 改变位 引用位 状态位 外存地址 每个作业都有存入其JCB中私有页表； 当访问页不在内存时，产生缺页中断； OS管理一张总的存储分块表。 计算机软件技术基础 存储管理

36 二、请求分页存储管理系统 5. 硬件支持 动态地址映射机构---将虚地址转换物理地址； 页表实现形式：
用专用内存区实现：设置一个页表始址寄存器存放首地址，一次读(写)操作要两次访问内存，第一次访问是读页表以获得物理地址，第二次内存访问才是存取数据。---速度慢 用一组专用寄存器实现，采用特权指令对寄存器装配和修改---速度快，成本高，页表大时不可行； c. 用一个高速联想寄存器保存页表---快表实现：用一个小容量的高速寄存器来存放当前访问最频繁的少数活动页的页号及对应块号。---速度非常快，但需要动态更换表的内容。 中断响应机构---请求缺页时，产生中断信号，转入“缺页中断处理”，由硬件与软件共同完成，处理过程如下图： 计算机软件技术基础 存储管理

37 否 工作区入内存 填写页表各项 保护当前进程现场 进程调度该进程 是 有空闲块吗？ 否 引用位 选择一 页淘汰 启动待执行指令 执行下一
条指令 调入所需虚页 否 该页修改 过吗？ 计算页号与页内 相对地址 访内存执行 完成该指令 调整页表及 空闲块表 改变位 是 该页在 内存吗？ 是 把该页写 回外存 地址变换 恢复被中断 进程现场 状态位 否 硬件完成 计算机软件技术基础 存储管理

38 9.5 请求分页式存储管理 三、请求分页系统的性能： 有效存取时间：t=（1-P）ma+P×缺页处理时间
有快表时，存取时间短。速度与命中率相关。 无快表时，执行速度降低。（二次访问） 计算机软件技术基础 存储管理

39 9.5 请求分页式存储管理 四、页面淘汰算法（置换）
由于分页管理中分配给每道程序的页架数有限，因此内存中的页面要随时进行更换，称为页面淘汰。页面更换不当会导致刚淘汰出内存的页面又要调入内存，这样使处理器大部分时间都用于页面调度上，称为“抖动”，从而降低了系统运行的速度。为了避免产生这种现象，需要选择一种较好的算法进行页面淘汰。 作用：处理缺页中断时，如内存中空闲块不够，则将内存中的某页置换到外存。 计算机软件技术基础 存储管理

40 四、页面淘汰算法 评价：在特定存储访问序列上运行页面淘汰算法，用其缺页率来衡量。 页面走向：评价时用于量化缺页率的存储访问序列。
（人工获得）随机产生；实际跟踪记录地址。 量化： 对于给定的页面(大小确定), 只关心页号, 不关心整个页地址; 如果对P页进行了访问,随后立即对P页的访问不会缺页; 内存可用空闲块W越多, 缺页数就会越少。 计算机软件技术基础 存储管理

41 四、页面淘汰算法 3. 几种常用页面调度算法 （1）先进先出法（FIFO—First Input First Output）：
算法思想：认为最先进入内存的页面，不再被使用的可能性最大，所以最先进入内存的页面，最先被调出内存。 例：设有一用户程序共分为5页，其执行时页面变化的规律称为页面走向P，分配给该程序的页架数M为3，其页面淘汰过程如下图，其中F为“+”号表示页面有交换。 FIFO页面淘汰过程 4 3 5 + 2 1 P= M=3 F= 页面走向 先进 后进 计算机软件技术基础 存储管理

42 （1）先进先出法 性能分析： 这一算法适用于按线性顺序访问地址的程序，否则效率不高。因为最先进入内存的页面可能是经常被使用的页面，这样会引起页面频繁的变换 算法简单, 但性能较差(实验证明),表现为: 内存利用率不高, 原因---基于“cpu按线性顺序访问存储空间”假设,而事实并非如此,如循环语句； 存在异常现象：内存块增加，反而缺页率会增加，原因---该算法根本没有考虑程序执行的动态特性。 计算机软件技术基础 存储管理

43 四、页面淘汰算法 (2)最优淘汰法(OPT Optimal Replacement) 思想：淘汰将在最长的时间后才要访问的页面。
实现：非常困难，因为需要跟踪各页面方可预测未来。“看将来” 性能分析： a. 最优算法,目的在于减少页面交换次数,节约处理机时间； b. 缺页率 f=7/12=58% OPT页面淘汰过程 4 3 5 + 2 1 P= M=3 F= 页面走向 计算机软件技术基础 存储管理

44 四、页面淘汰算法 (3)最久未使用法(LRU Least Recently Used)
思想：基于“过去一段时间里不曾被访问过的页，在最近的将来可能也不再会被访问”假设。淘汰一页时，选取在最近一段时间内最久未使用过的页面予以淘汰。 实现：“跟踪过去，推测未来” 较难实现。 软件实现，系统开销大； 硬件实现，增加机器成本。 计算机软件技术基础 存储管理

45 (3)最久未使用法 常采用近似算法： 最不频繁使用法(LRU)---把最不常用的页面先淘汰。
实现方法:每一页设立一个计数器,每访问一次后,将该页的计数器加1,然后淘汰计数值最小的页。 b. 最近没有使用法(NUR)---把最近没有使用过的页面淘汰。 实现方法：每一页设立一个标志位，每当访问某一页时,将该页的标志位置“1”，周期性地检查每一页的标志位,将标志位为“1”的页记入一表格中，淘汰时,检查表格内容,淘汰无记录的页. 计算机软件技术基础 存储管理

46 (3)最久未使用法 性能分析:： 近似算法是较为实用的算法，效果较好，实现不难。 缺页率
例：对下面的页面走向，使用：LFU算法，f=10/12=83% LRU页面淘汰过程 5 3 4 + 2 1 P= M=3 F= 页面走向 计算机软件技术基础 存储管理

47 四、页面淘汰算法 (4) 第二次机会算法(SCR)---FIFO的改进 思想：保护经常被访问的“老页”不被淘汰。
计算机软件技术基础 存储管理

48 9.5 请求分页式存储管理 五、物理块分配算法---内存空闲块分配 最少块数原则---不允许一条指令在执行过程中缺页
最少块数必须保证访问指令执行期间不缺页。 结论: 每个进程的最少块数由指令集结构决定; 每个进程的最多块数由可用内存的总量决定。 2. 全局分配与局部分配 允许缺页时在全体进程中选择淘汰者(可变分配) 缺页时只在自己驻内页中选择淘汰者(固定分配) 计算机软件技术基础 存储管理

49 五、物理块分配算法 3. 分配算法 等分法: 总块数m /总进程数n 性能---一视同仁，但有的剩余；有的不够。 按需比例法： si/s*m
其中:si---进程pi地址空间大小; s=∑si(i=1……n) m---内存总块数 4. 抖动问题: 刚被淘汰出去的页面,很快又要访问,有调回内存, 如此反复。由于淘汰算法不当产生. 计算机软件技术基础 存储管理

50 9.5 请求分页式存储管理 六、工作集： 程序局部性的近似表示---在任何一小段时间里，作业运行只集中于访问某几页
定义: 一个作业在某一小段时间△内访问页面的集合,记为--- W(t, △),最近被访问过的页的集合。 性质:既与某一时刻t有关;又与 工作集窗口(△)有关. 性能: 防止抖动,有OS监视每个W. 计算机软件技术基础 存储管理

51 9.5 请求分页式存储管理 七、请求时分页存储管理系统的性能 优点： 1. 提供大容量的多个虚拟存储器 2. 提高了内存利用率;
3. 作业地址空间不受内存限制，有利于组织多道程序执行; 4. 不要求作业在内存中连续存放，有效解决碎片问题; 缺点： 1. 要求相应的硬件支持; 2. 增加系统开销; 3. 算法选择不当,会产生抖动. 计算机软件技术基础 存储管理

52 9.6 段式存储管理 由于分区、分页式管理时进程的地址空间结构都是线性的，要求将程序、数据、子程序等进行编译、连接时也按线性空间的一维地址顺序排列。使得共享非常困难，因为：分页系统中的每一页都只是存放信息的物理单位，其本身并无完整的意义，而在实现程序和数据的共享时都是以信息的逻辑单位为基础的。 一、分段的基本思想 引入：为了满足用户（程序员）在编程和使用上多方面的要求。 2. 分段：(用户编程时决定)把程序按内容或过程（函数）关系划分 成若干个段，每段定义一组逻辑上完整的程序和数据，且每段有自己的名字和长度。 计算机软件技术基础 存储管理

53 9.6 段式存储管理 3. 分段管理的基本概念 （1）段 一个程序由若干个程序模块组成，可以按模块来分配存储空间。分段管理把每个模块的地址空间称为“段”。每个段规定一个段号，每个段的地址空间都从“0”地址开始。 （2）分段管理中的地址结构 在分段情况下，每一个虚拟地址需要用两部分来描述，如下图。 段号s 段内地址w ！在分页存储管理中，一个虚拟地址可以分解为页号和页内地址。 计算机软件技术基础 存储管理

54 9.6 段式存储管理 (3) 段表、段地址寄存器 系统为每个作业建立一个段映象表（SMT），简称段表，段表中包括：段号、段的长度、段在主存中的起始地址、段的状态以及存取权限等。同时系统设立一个段表地址寄存器，指出当前运行作业的段表在主存中的起始地址b以及段表长度L。 计算机软件技术基础 存储管理

55 9.6 段式存储管理 二、段式存储管理 与页式存储管理相似，只把那些经常访问的段驻留内存，其余段放入外存，待需要时自动调入。
三、段式管理的实现 段式虚地址空间---二维 程序地址=段名(s)+段内位移(w相对于每段起始) 注意:与页式虚地址(一维)的区别: 段名(号)之间无顺序关系; 段的长度是不固定的.(与完整的逻辑信息有关) 计算机软件技术基础 存储管理

56 三、段式管理的实现 2. 段式管理中的地址转换 当作业要进行存储访问时，由硬件地址转换机构与段表地址寄存器找到段表中相应段的记录，从而将段式地址空间的二维地址转换成实际内存地址。如下图，将逻辑地址s=2，w=292转换成实际地址8292。 段表地址器存器 s w 主存空间 8292 292 2 逻辑地址 b L 地址转换机构 200 300 500 1kb 1 4kb 920 3 8kb 6kb 段号 长度 起址 状态 SMT表 分段管理的地址转换图 计算机软件技术基础 存储管理

57 三、段式管理的实现 3. 段式管理的存储保护 (1)越界保护
当CPU访问某逻辑地址时，硬件自动将段号与段地址寄存器中段表长度进行比较，同时要将段内地址与段表中该段长度进行比较，如果合法则进行地址转换，否则产生越界。 (2)存取控制保护 由于分段情况下段是逻辑上完整的信息集合，因此要防止其中的信息被不允许共享者窃取或修改，往往用存取权限来控制各类用户对信息的共享程度。常用的控制类型有读、写、执行、修改等。 计算机软件技术基础 存储管理

58 9.6 段式存储管理 四、分段管理的优缺点 1. 优点 便于程序模块化处理。每个程序模块构成各自独立的分段，并采用段的保护措施不受其它模块的影响和干扰。 便于处理变化的数据。根据实际应用中数据长度随输入数据多少而变化的情况，要求动态扩大一个分段的地址空间，在分段系统中并不困难。 便于共享分段。在分段系统中分段的共享只要通过各作业段表的相应表目指向同一个共享段的物理副本来实现。 计算机软件技术基础 存储管理

59 9.6 段式存储管理 2. 缺点： 要求一定的硬件支持，增加了成本。要为地址变换花费CPU时间，为表格提供附加的存储空间。
分段尺寸的大小受到主存的限制。由于段的长度不固定，会出现“碎片”问题，处理机要为存储器的紧缩付出代价。 计算机软件技术基础 存储管理

60 9.7 段页式存储管理 一、段页式管理的基本概念 1、段页结构
段页式管理是分页和分段管理结合的结果。段页式管理中，作业的地址空间采用分段方式，而作业的每一段采用分页方式。整个主存分成大小相等的存储块，称为页架，主存以页架为单位分配给每个作业。 2、段页管理的地址结构 段页式管理中的逻辑地址用三个参数表示，如下图 段号s 页号p 页内地址d 段页式管理地址结构 计算机软件技术基础 存储管理

61 一、段页式管理的基本概念 3、段表、页表、段地址寄存器
系统为每个作业建立一个段表，并为每个段建立一个页表，并设置一个段地址寄存器来指出当前运行作业段的段表起始地址和段表长度。 计算机软件技术基础 存储管理

62 9.7 段页式存储管理 二、段页式管理的地址转换 1、地址转换硬件将逻辑地址中的段号s 与段地址寄存器中的段表起始地址b相加得到该访问段的表目。 2、从该段表目中得到该段页表的起始地址，并与逻辑地址中的页号p相加得到欲访问页在该段页表中的地址。 3、从该页表目中得到对应的页架号p’ 并与逻辑地址中的页内地址d相加得到绝对地址。 计算机软件技术基础 存储管理

63 主存空间 页架号 段页管理的地址转换图 段表地址器存器 页表起始地址 状态 页号 页架号 L b 1 2 3 4 5 6 7 页表长度 1
主存空间 页架号 页表起始地址 状态 页号 页架号 L b 1 2 3 4 5 6 7 页表长度 1 3 2 5 状态 1 PMT0 1 6 7 2 3 5 SMT PMT3 s p d p’ d 逻辑地址 物理地址 段页管理的地址转换图 计算机软件技术基础 存储管理

64 9.7 段页式存储管理 三、段页式管理的优缺点 优点: 段页式管理具有分页、分段管理的优点，是使用的最广泛、最灵活的一种存储管理技术。
缺点： 需要更多的硬件支持，增加了硬件的成本，同时也增加了软件的复杂性和管理开销。 许多大中型计算机，如IBM370/168、Multics等都采用这种段页式虚拟存储器。 计算机软件技术基础 存储管理