第四章 存储管理.docx

1、第四章 存储管理第四章 存储管理4.1 概述4.2 段式存储管理4.3 页式存储管理4.4 段页式存储管理4.5 虚拟存储4.6 交换技术与覆盖技术重要资源“瓶颈”：关键、紧张帕金森定律4.1 概述 4.1.1 存储体系 存储器的层次结构： 高速缓存Cache： 少量的、非常快速、昂贵、易变的内存RAM： 若干兆字节、中等速度、中等价格、易变的 磁盘： 数百兆或数千兆字节、低速、价廉、不易变的 由操作系统协调这些存储器的使用 重要性：直接存取要求内存速度尽量快到与CPU取指速度相匹配，大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥。 内存： 是由

2、存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器。 内存可以分为： 系统区：用于存放操作系统 用户区：用于装入并存放用户程序和数据。 4.1.2 存储管理目的 用户对内存的使用要求1 充分利用内存，为多道程序并发执行提供存储基础。2 尽可能方便用户使用 自动装入用户程序 用户程序中不必考虑硬件细节3 系统能够解决程序空间比实际内存空间大的问题4 程序在执行时可以动态伸缩5 内存存取速度快6 存储保护与安全7 共享与通信8 了解有关资源的使用状况9 实现的性能和代价 4.1.3 存储管理的任务

3、 前提: 引入多道程序设计技术 满足用户要求1 内存空间的管理、分配与回收 记录内存的使用情况 设置相应的内存分配表 （内存分配回收的依据） 内存空间划分问题？ 静态或动态，等长或不等长内存空间的管理、分配与回收 内存分配表 位示图表示法：用一位（bit）表示一个空闲页面（0：空闲，1：占用）。内存空间的管理、分配与回收 空闲页面表：包括首页面号和页面个数，连续若干的页面作为一组登记在表中 空闲块表：空闲块首址和空闲块长度，没有记录的区域即为进程所占用 空闲块链表：将所有的空闲块链成一个链表内存空间的管理、分配与回收 确定分配算法 实施内存分配 回收内存 分配回收方式: 静态分配与动态分配内存

4、空间的管理、分配与回收 连续性 ； 离散性驻留性 ； 交换性一次性； 多次性2 存储共享 内存共享：两个或多个进程共用内存中相同区域 目的： 节省内存空间，提高内存利用率 实现进程通信（数据共享） 共享内容： 代码共享，要求代码为纯代码 数据共享3 存储保护与安全 保护目的： 为多个程序共享内存提供保障,使在内存中的各道程序, 只能访问他自己的区域，避免各道程序间相互干扰，特别是当一道程序发生错误时, 不致于影响其它程序的运行。通常由硬件完成保护功能，由软件辅助实现。（特权指令不能完成存储保护。）存储保护 保护系统程序区不被用户侵犯 （有意或无意的） 不允许用户程序读写不属于自己地址空间的数据

5、 （系统区地址空间，其它用户程序的地址空间）保护过程-防止地址越界 每个进程都有自己独立的进程空间，如果哪个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。保护过程-防止地址越界一般由硬件提供一对寄存器： 基址寄存器：存放起始地址 限长寄存器：存放长度 （上界寄存器/下界寄存器）保护过程-防止操作越权 对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权。 即读写保护。4 内存“扩充” 通过虚拟存储技术实现

6、用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来扩充内存的容量，使用户得到比实际内存容量大的多的内存空间。内存“扩充” 具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制。5 地址映射（地址重定位，地址变换）(1) 逻辑地址（相对地址，虚地址）(2) 物理地址（绝对地址，实地址）(3) 地址映射(1)逻辑地址（相对地址，虚地址） 用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。 不能用逻辑地址在内存中读取信息。(2)物理地址（绝对地址

7、，实地址） 内存中存储单元的地址，可直接寻址。(3)地址映射 为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址映射。 原因: 当程序装入内存时, 操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。静态重定位 当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在连接装配时由软件完成）。动态重定位 在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由

8、硬件地址映射机制来完成。硬件支持，软硬件结合完成）。 硬件上需要一对寄存器的支持。4.1.4 各种存储管理方案单一用户（连续区）存储管理： 单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用。分区存储管理方案固定分区 预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，如图所示。但分区大小固定不变，每个分区装一个且只能装一个作业。 存储分配：如果有一个空闲区, 则分配给进程。固定分区内存管理：设置内存分配表内存分配：内存回收：简单缺点：内存利用率不高可变分区 内存的分

9、配：内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间。内存的管理： 设置内存空闲块表记录了空闲区起始地址和长度。内存分配：动态分配内存的回收：当某一块归还后，前后空间合并，修改内存空闲块表。内存分配：三种分配算法首先适配算法： 当接到内存申请时，查空闲块表，找到第一个不小于请求的空块，将其分割并分配。（特点：简单、快速分配）最佳适配算法： 接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配。（特点：用最小空间满足要求）最坏适配算法： 接到内存申请时，在空闲块表中找到一个不

10、小于请求的最大空块进行分配。（特点：当分割后空闲块仍为较大空块）碎片问题： 经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片。 造成存储资源的浪费碎片问题的解决： 紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域。 （紧缩技术，紧致技术，浮动技术，搬家技术） 问题：开销大；移动时机 讨论： 优点： A 便于动态申请内存 B 便于共享内存 C 便于动态链接 缺点：碎片问题(外碎片)4.2 段式存储管理4.2.1 基本思想（工作原理）用户程序划分 按程序自身的逻辑关系划分为若干个程序段，每个程序

11、段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。逻辑地址内存划分 内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定。内存分配 以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。4.2.2 管理段表： 它记录了段号，段的首（地）址和长度之间的关系。 每一个程序设一个段表空闲块管理： 记录了空闲区起始地址和长度。内存的分配算法： 首先适配；最佳适配；最坏适配4.2.3 硬件支持一对寄存器段表始址寄存器： 用于保存正在运行进程的段表的始址。段表长度寄存器：

12、 用于保存正在运行进程的段表的长度（例如上图的段表长度为3）。相联（联想）存储器 介于内存与寄存器之间的存储机制，它又叫快表。用途：保存正在运行进程的段表的子集（部分表项）。特点：按内容并行查找。引入快表的作用： 为了提高地址映射速度。快表项目：段号；段始址；段长度；标识（状态）位；访问位，淘汰位。快表淘汰问题？4.2.4 段的共享4.2.5 段的保护优点： 便于动态申请内存 管理和使用统一化 便于共享 便于动态链接缺点：产生碎片与可变分区存储管理方案区别4.3 页式存储管理4.3.1 基本思想（工作原理）用户程序划分 把用户程序按逻辑页划分成大小相等的部分，称为页。从0开始编制页号，页内地址

13、是相对于0编址。逻辑地址 用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址。内存空间： 按页的大小划分为大小相等的区域，称为内存块（又叫物理页面）。内存分配： 以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻。4.3.2 管理1.页表：系统为每个进程都建立了一个页表，页表给出逻辑地址号和具体内存块号相应的关系2.空块管理总页表3.内存的分配与回收计算一个作业所需要的总块数。查总页表，看看是否还有N个空闲块。如果有相应空闲块，则页表长度为该为N，可填入PCB中。（申请页表区，把页表始址填

14、入PCB）。分配N个空闲块，将块号和页号填入页表（页表号实际不用填）。修改总页表。4.3.3 硬件支持1一对寄存器： a 页表始址寄存器 b 页表长度寄存器2相联寄存器快表 1）页号 2）页在内存的块号 3）标识位 4）淘汰位4.3.4 优缺点优点：a 解决了碎片问题 b 便于管理缺点：a 不易实现共享 b 不便于动态连接4.4 段页式存储管理4.4.1 产生背景及基本思想 背景：结合了二者优点 克服了二者的缺点基本思想： 用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段） 逻辑地址：内存划分：按页式存储管理方案内存分配：以页为单位进行分配4.4.2 管理

15、1 段表：记录了每一段的页表始址和页表长度2 页表：记录了逻辑页号与内存块号的对应关系。（每一段有一个，一个程序可能有多个页表）3 空块管理：4 分配：同页式管理4.4.3 硬件支持段表始址寄存器 段表长度寄存器 相联存储器（快表）4.5 虚拟存储连续性 ； 离散性驻留性 ； 交换性一次性； 多次性 以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术4.5.1 概述 1 问题的提出： a 程序大于内存 b 程序暂时不执行或运行完是否还要占用内存。 虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上

16、，并在需要时在内存和磁盘之间动态交换。 虚拟存储器支持多道程序设计技术。2 程序局部性原理： 在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面。时间局部性： 一条指令被执行了，则在不久的将来它可能再被执行。空间局部性： 若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用。3 虚拟存储技术虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就是虚存。实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作。4.5.2 虚拟页式存储管理1 基本工作原理 在进

17、程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。2 页表表项页号、驻留位、内存块号、外存地址、访问位、修改位 驻留位（中断位）：表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页（由不同的算法决定）修改位：查看此页是否在内存中被修改过3 缺页中断 在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去。如果内存中有空闲块，则分配

18、一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号。若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存。4 页面淘汰算法先进先出页面淘汰算法（FIFO） 选择在内存中驻留时间最长的页并淘汰之。理想淘汰算法最佳页面算法（OPT） 淘汰以后不再需要的或最远的将来才会用到的页面。最近未使用页面淘汰算法（NRU） 选择在最近一段时间内未使用过的一页并淘汰之。实现：设置访问位（R） 修改位（M）启动一个进程时，置0；R被定期清零。发生缺页中断时，操作系统检查R，M： 第0类：无访问，无修改 第1类：无访问，有修改 第2类：有访问，无修改 第3类：有访

19、问，有修改操作系统随机从编号最小的非空类中选择一页淘汰最近最少使用页面淘汰算法（LRU） 选择最后一次访问时间距离当前时间最长的一页并淘汰之。 即淘汰没有使用的时间最长的页。实现代价很高 硬件方法LRU的软件解决方案：最不经常使用（NFU） 选择访问次数最少的页面淘汰之。实现：软件计数器，一页一个，初值为0。每次时钟中断时，计数器加R。发生缺页中断时，选择计数器值最小的一页淘汰。改进：计数器在加R前先右移一位 R位加到计数器的最左端称为老化算法。第二次机会淘汰算法 (SCR) 按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0。例子1：计

20、算缺页次数 某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。FIFO 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 5 5 2 1 1页2 4 3 2 1 4 3 3 3 5 2 2页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共缺页中断9次 LRU 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 4 3 2 1 5页2 4 3 2 1 4 3 5 4 3 2 1页3 4 3 2 1 4 3 5 4 3 2 x x x x x x x x x x

21、共缺页中断10次 OPT 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 1 1 5 5 5 2 1 1页2 4 3 3 3 3 3 3 3 5 5 5页3 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共缺页中断7次例子2：计算缺页次数 某程序在内存中分配m页初始为空，页面走向为1，2，3，4，1，2，5，1，2，3，4，5。当m=3，m=4时缺页中断分别为多少？用FIFO算法。例子2：计算缺页次数m=3时，缺页中断9次m=4时，缺页中断10次注：FIFO页面淘汰算法会产生异常现象，当分配给进程的物理页面数增加时，缺页次数反而增加。5 影响缺页次数的

22、因素(1) 分配给进程的物理页面数(2) 页面本身的大小(3) 程序的编制方法(4) 页面淘汰算法例子3：内存分配一页，初始时第一页在内存，页面大小为128个整数。 矩阵A128X128按行存放。 程序编制方法1： For j:=1 to 128 For i:=1 to 128 Ai,j:=0; 程序编制方法2： For i:=1 to 128 For j:=1 to 128 Ai,j:=0;4.5.3 性能问题1 颠簸（抖动） 在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象为颠簸。原因： a 页面淘汰算

23、法不合理。 b 分配给进程的物理页面数太少。2 工作集模型 基本思想：根据程序的局部性原理，一般情况下进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中则不断发生中断。 如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数。工作集： 对于给定的访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合称为工作集。工作集：内容取决于页的三个因素 a 访页序列特性 b 时刻Ti c 窗口长度()例： 26157775162341234443434441327 | |t1

24、| |t2 ws(t1)=1,2,5,6,7 ws(t2)=3,44.5.4 虚拟段式存储管理1 段表内容 增加：特征位（在/不在内存，是否可共享），存取权限位（读，写，执行），标志位（是否修改过，能否移动），扩充位（固定长/可扩充 ）2 越界中断处理 进程在执行过程中，有时需要扩大分段，如数据段。由于要访问的地址超出原有的段长，所以发越界中断。操作系统处理中断时 ，首先判断该段的“扩充位”，如可扩充，则增加段的长度；否则按出错处理。3 缺段中断处理 检查内存中是否有足够的空闲空间 a 若有，则装入该段，修改有关数据结构，中断返回 b 若没有，检查内存中空闲区的总和是否满足要求，是则应采用紧缩

25、技术，转a；否则，淘汰一些段，转a4 段的动态链接 大型程序： 若干程序段，若干数据段 一些熟知的事实： * 进程的某些程序段在进程运行期间可能根本不用 * 互斥执行的程序段没有必要同时驻留内存 * 有些程序段执行一次后不再用到 静态链接：为了程序正确执行，必须由连接装配程序把它们连接成一个可运行的目标程序，并在程序运行前都装入内存。 问题：花费时间，浪费空间（1） 段的动态链接 在程序开始运行时，只将主程序段装配好并调入内存，其它各段的装配是在主程序段的运行过程中逐步完成。每当需要调用一个新段时，再将这个新段装配好，并与主程序段链接。 页式存储管理：难以完成动态链接，其逻辑地址是一维的。（2

26、） 链接间接字和链接中断 机器指令：直接寻址，间接寻址 采用间接寻址时，间接地址指示的单元的内容称为间接字，在间接字中，包含了直接地址，还包含了附加的状态位。格式为： 处理机在执行间接指令时，其硬件能自动对链接字中连接标志位进行判断。当L=1时，硬件自动发链接中断，并停止执行该间接指令，转去执行链接中断处理程序。处理完后（L已被中断处理程序改为0），再重新执行该间接指令；若L=0，则根据间接字中的直接地址去取数据。（3） 编译程序的准备工作 LOAD 1, A| 编译前3段 LOAD* 1,3|100 100 链接后678 7“A|4段120 ：12345678（4） 链接中断处理* 根据链接

27、间接字找出要访问段的符号名和段内地址* 分配段号，检查该段是否在内存，若不在，则从外存调入，并登记段表，修改内存分配表* 修改间接字：修改连接标志位为0，修改直接地址* 重新启动被中断的指令执行（5） 其他问题纯段和杂段纯段：被链接段是可再入的，或称“纯的”，即该段在执行过程中，不允许修改其中的数据。杂段：又称链接段，将程序所有可能变更的数据，包括链接间接字和某些临时变量、内部变量等，放在杂段中。4.6 交换技术与覆盖技术在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾。覆盖技术主要用在早期的操作系统中交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术

28、的出现 交换技术与覆盖技术共同点： 进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换不同点：如何控制交换？4.6.1 覆盖技术 覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间。 一般要求作业各模块之间有明确的调用结构，用户要向系统指明覆盖结构，然后可由操作系统完成自动覆盖。把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域。程序段先保存在磁盘上，当有关程序段的先头部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了）。一般要求作业各模块之间有明确的调用结构，程序员要向系统

29、指明覆盖结构，然后由由操作系统完成自动覆盖。 缺点：对用户不透明，增加了用户负担。 例子：目前这一技术用于小型系统中的系统程序的内存管理上，MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区TPA的高端部分与COMMAND.COM暂驻模块也是一种覆盖结构。4.6.2 交换技术 当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。多用于分时系统中。 交换技术实现中的几个问题： 1 选择原则：即将哪个进程换出/入内存？ 例子：分时系统，时间片轮转法或基于优先数的调度算法 在选择换出进程时，要确定换出的进程是要长时间等待的 需要特殊考虑的是：任何等待I/O的进程中存在的问题。解决： 从不换出处于等待I/O状态的进程 仅通过操作系统缓冲执行I/O操作 总之，有些I/O进程因DMA而不能换出内存或换出前需要操作系统的特殊帮助 2 交换时机的确定：何时需发生交换？ 例子： 只要不用就换出（很少再用） 只在内存空间不够或有不够的危险时换出3 交换时需要做哪些工作？ 需要一个盘交换区：必须足够大以存放所有用户程序的所有内存映像的拷贝；必须对这些内存映像的直接存取。 切换程序4 换入回内存时位置的确定 换出后再换入的内存位置一定要在换出前的原来位置上吗？ 受