存储器管理

存储器的层次结构

速度从高到低、容量从小到大

存储器管理的目的和功能

主存储器的分配和管理
提高主存储器的利用率
“扩充”主存容量
存储保护

存储分配的三种方式

直接指定方式（汇编地址写入）
静态分配方式（程序装入时确定位置）
动态分配方式

程序的装入和链接

将用户源程序变为可在内存中执行的程序：

编译翻译成机器级代码
链接使目标模块链接（引用的其它模块）成装入模块的过程
装入由装入程序将装入模块装入内存并执行

程序的装入

绝对装入方式
可重定位装入方式（静态、动态）
动态运行时装入方式

程序的链接

静态链接
装入时动态链接
运行时动态链接

连续分配存储管理方式

程序空间本来就是连续的用连续的内存装入连续的程序，减少管理工作的难度

单一连续分配方式（一个进程在内存）
- 优点：易于管理
- 缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。
分区式分配方式（一个进程占据一个分区）
- 固定分区分配
  - 易于实现，开销小
  - 内碎片造成浪费；分区总数固定，限制了并发执行的程序数目；存储空间的利用率太低
- 动态分区分配——分区分配算法

可重定位分区分配定时把存储空间中的空白区合并为一个大的连续区之前的可变式分区分配根据其要求量为其划定相应的区域。消除了 “内零头”，但造成“外零头”

分区分配算法

内零头(Internal Fragment)：分配给用户但用户没有使用的空间 “多分配的空间”
外零头(External Fragment )：没有分配但无法分配的空间，太小而无法分配，“分不出去的空间”

最佳适应算法BF

选择分区时总是寻找其大小最接近作业所要求的存储区域

优点：遇到大作业到来时，比较容易得到满足
缺点：留下许多无法使用的空白区；回收时，把它插入空白区链也颇为费时

最坏适应算法WF

寻找最大的空白区

缺点：将大空间分给了小作业后大作业来到无法满足申请

首次适应算法FF

空白区链的始端开始查找，选择第一个足以满足请求的空白块
分配后空白区被分成两部分一部分分配给作业；剩下的部分留在原空白区链中

优点：简单，查找速度快
缺点：存储空间利用率不高；找到合适空白区的速度降低。

循环首次适应算法NF

（下次适应算法）从上次查找结束的地方开始，找到一个足够大的空白区，就分配

优点：存储空间的利用更加均衡
缺点：需要获得相当大的空白区时，很难满足

快速适应算法QF

每一类具有相同容量的空闲分区，单独设立一个空闲分区链表
在内存中设立一张索引表，每一个表项记录空闲分区链表表头的指针
分配过程：根据进程的长度，寻找到能容纳它的最小空闲分区链表，并取下第一块进行分配即可

优点：查找效率高；满足对大空间的需求，也不会产生内存碎片
缺点：分区归还算法复杂，系统开销较大；以进程为单位，存在一定的浪费

伙伴系统

固定分区分配：并发执行的进程数量受到限制；内部碎片影响内存利用率
动态分区分配：算法复杂，回收分区时系统开销大

在伙伴系统中，可用内存块的大小为 2^k (1≤k≤m)

2^1表示分配的最小块的尺寸；
2^m表示分配的最大块的尺寸，通常是可供分配的整个内存空间的大小。

对空闲区按照大小分类，相同大小的分区链接为一个双向空闲链表；最多可形成 k（0 ≤k≤m ）个链表。

分页存储管理方式

引入分页

离散分配方式的引入：
连续分配方式会产生内/外零头
为解决零头问题又要进行紧凑等高开销活动
什么是离散分配：程序在内存中不一定连续存放
根据离散时的基本单位不同，可分为三种：
分页存储管理
分段存储管理
段页式存储管理

分页存储管理基本思想

离散的基础

分页(Pages)：将程序地址空间分页
分块(Frames)：将内存空间分块

离散分配的体现
- 内存一块可以装入程序一页
- 连续的多个页不一定装入连续的多个块中
- 注：系统中页块的大小是不变的。

离散分配没有外零头，且内零头肯定少于一个页面

分页存储管理的基本方法

如何建立程序空间与主存空间的映射——页表
如何进行地址变换——从程序逻辑地址到内存物理地址

页面和物理块

页面或页(Page)：把每个进程的逻辑地址空间分成一些大小相等的片。
物理块或页框(Page Frame)：内存空间也分成与页相同大小的若干存储块。在为进程分配存储空间时，总是以页框为单位。

页面大小由机器的地址结构决定通常在1KB~8KB之间。

实现分页存储管理的数据结构

页表：进程，描述该进程的各页面在内存中对应的物理块号。页表中包括页号、物理块号。
作业表：系统，记录作业的页表情况。
空闲块表：系统，记录主存当前空闲块。

地址变换机构

使用寄存器：速度快，成本高
一般将页表存在内存进程的PCB中，运行时再装入页表寄存器PTR

分页系统中的地址变换过程如下：

根据逻辑地址,计算出页号和页内偏移量；
从PTR中得到页表首址，然后检索页表，查找指定页面对应的页框号；
用页框号乘以页面大小获得其对应的起始地址，并将其送入物理地址的高端。
将页内偏移量送入物理地址低端，形成完整的物理地址。

快表

快表TLB为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器其中专门保存当前进程最近访问过的一组页表项。
根据逻辑地址中的页号，会先查找快表中是否存在对应的页表项。
若快表中存在该表项，称为命中，取出其中的页框号加上页内偏移量计算出物理地址。
若快表中不存在该页表项，称为命中失败，则再查找页表，找到逻辑地址中指定页号对应的页框号。
同时，更新快表，将该表项插入快表中。

访问内存的有效时间 EAT

命中率a、查找快表时间b、访问内存时间c
有效访问时间EAT=a ✖ （b+c）+ (1- a) ✖ (b+2c)

两级和多级页表

引入两级页表采用离散分配方式，来解决难以找到一块连续的大内存空间的问题

利用离散分配方法实现的两级页表只是解决了大页表无需大片连续存储空间问题，但并未减少用较少内存去存放大页表问题，有关此类问题的成功解决方案在虚拟存储器管理中。

反置页表IPT

为了解决大页表问题占内存多现象，减少内存开销，避免一个进程一个页表。

IPT采用为主存中的每一个物理块建立一个页表项并按照块号排序，该表每个表项包含正在访问该物理块的进程标识、页号及特征位，用来完成主存物理块到访问进程的页号的转换。

即反过来查，原来是进程查物理现在是物理地址记录进程

对换

对换就是把内存中暂时不用的程序和数据换到外存，或把需要的程序和数据换入内存。
分为：

整体对换以进程为单位
页面/分段对换：以页或段为单位

分段存储管理方式

根据程序模块化设计时会将程序分段（如主程序段、子程序段、数据段等）而分段管理便是按程序模块化设计思想分段存储。

作业地址空间按逻辑信息的完整性被划分为若干个段；
段内的地址空间是连续的；
许多编译程序支持分段方式，自动根据源程序的情况产生若干个段。

分段较分页易于实现段的共享和段的保护。

段页式存储管理

分页管理内存管理效率高
- 没有外零头
- 内零头小
分段管理符合模块化思想
- 每个分段都具备完整的功能
- 方便代码共享、保护
- 没有内零头，存在外零头

段页式管理结合：先将用户程序分段，每段内再划分成若干页，每段有段号，每段内部的页有一连续的页号。

但在段页式存储管理方式中，每访问一次数据，需访问三次内存。访问段表、访问页表、访问相应数据，大大降低了访问速度。
可以设置快表，表项应包括段号、页号、物理块号。

总结：

综合了分段和分页技术的优点，既能有效地利用存储空间，又能方便用户进行程序设计
但是，实现段页式存储管理系统需要增加硬件成本，系统的复杂度和管理开销也大大增加
因此，段页式存储管理技术适合于大、中型计算机系统，不太适合小型、微型计算机系统

虚拟存储器

虚拟存储器概述

传统内存管理的一次性和驻留性严重降低内存利用率，减少系统吞吐量
当一个程序要求的存储容量超过内存，或大量作业需要内存空间时
从物理上增加内存容量，增加系统成本，并且增加是有限的。
所以从逻辑上增加内存容量，是虚拟存储技术所要解决的主要问题。

当进程运行时，先将当前要运行的部分程序装入内存，其他部分暂留外存；
当要执行的指令不在内存时，处理器发生中断，通知操作系统将所缺部分从外存调入内存，保证程序继续执行；
当内存不足时，允许程序部分换入、换出。

局部性原理

程序的执行总是呈现局部性。即在一个较短的时间段内，程序的执行仅限于某个部分。因此只要保证进程执行所需的部分程序和数据驻留在内存，一段时间内进程都能顺利执行。

具体表现为

时间局限性被访问过的数据可能再次被访问
空间局限性被访问过的存储单元其附近也可能被访问

虚拟存储器的定义

虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。

虚拟存储器的特征

多次性 多次性是指一个作业被分成多次调入内存运行。相对传统储存管理的一次性
对换性 对换性是指作业的运行过程中进行换进、换出。换进和换出能有效地提高内存利用率。相对传统储存管理的常驻性
虚拟性 虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

请求分页存储管理方式

工作原理：作业运行时，只将当前的一部分装入内存其余的放在辅存，一旦发现访问的页不在主存中，则发出缺页中断，由OS将其从辅存调入主存，如果内存无空块，则根据某种算法选择一个页淘汰以便装入新的页面。

利用这种方法，可使更多的作业处于就绪状态，且能支持比主存容量大的作业在系统中运行。从而提高存储空间利用率。

为了实现请求调页、页面置换两大功能，请求分页系统必须提供如下的硬件支持：

请求分页的页表机制。
缺页中断机构。
地址变换机构。

内存分配策略

固定分配局部置换但是难以确定进程合适的分配大小
可变分配全局置换（常用方式）预先分配用完再加
可变分配局部置换发现缺页后要换出再自行换入，不干涉其它区域

物理块分配算法

平均分配算法
按比例分配算法根据进程的大小
考虑优先权的分配算法

页面置换算法

最佳(优)置换算法OPT

理论上最理想的页面置换策略是：从主存中移出永远不再需要的页面；如无这样的页面存在，则应选择最长时间不需要访问的页面。

先进先出（FIFO）页面置换算法

实质是：总是选择作业中驻留时间最长(即最老)的一页淘汰。即：先进入主存的页面先退出主存。

最近最久未使用（LRU）置换算法

实质是：当需要置换一页面时，选择在最近一段时间内最久不用的页面予以淘汰。
特别的LRU需要硬件支持记录每个页面的最近使用情况

另有最少使用置换算法LFU：选择到当前时间为止被访问次数最少的页面被置换

简单Clock置换算法

此算法为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。
具体操作：

当某页被访问时，其访问位被置1。
置换程序从上次停止位置开始检查页面的访问位。
- 如果是0，就选择该页换出；
- 若为1，则重新将它置0，给该页驻留内存的机会暂不换出。

例：

改进Clock置换算法

如果该页面驻留内存期间没有被修改过，那么不必把它写回辅存，否则系统必须把它写回辅存。
即相对简单CLOCK添加修改位

由访问位A和修改位M组合四种类型页面：

类（A=0，M=0）：既未彼访问，又未被修改，是最佳淘汰页。
类（A=0，M=1）：最近未被访问，但已被修改，并不是很好的淘汰页。
类（A=1，M=0）：最近已被访问，但未被修改：该页有可能再被访问。
类（A=1，M=1）：最近已被访问且被修改，该页可能再被访问。

缺页率对有效访问时间的影响

设内存读写周期为t，查找快表时间为λ，缺页中断处理时间为ɛ

页面在内存且页表项在快表中,只需一次访问内存
EAT= λ + t
页面在内存但页表项不在快表中,需两次访问内存，一次读取页表，一次读取数据，另外还需更新快表。
EAT= λ + t + t + λ=2(λ + t)
页面不在内存：考虑查找快表时间、查找页表时间、缺页中断处理时间、更新快表时间、访问实际物理地址时间
EAT= λ + t +ɛ + λ + t = ɛ + 2(λ + t)
综上：
则引入快表命中率为α，缺页中断率为f，则有效访问内存时间为
EAT= λ + α t + (1- α)[t + f(t +ɛ +λ) + (1-f)(t +λ)]

抖动和工作集

抖动：如果运行进程的大部分时间都用于页面的换入/换出，而几乎不能完成任何有效的工作，则称此进程处于抖动状态。
抖动产生的原因有：

进程分配的物理块太少
置换算法选择不当
全局置换使抖动传播

可利用抖动发生前出现的征兆发现抖动并加以防范。
这些技术有：

采取局部置换策略
引入工作集的算法
L=S准则 - L缺页之间的平均时间，S平均缺页服务时间
选择暂停的进程

请求分段存储管理方式

工作原理：
请求分段系统中，程序运行之前，只需先调入若部分分段，便可启动运行。
当所访问的段不在内存中时，可请求OS将所缺的段调入内存。
硬件支持：

请求分段的段表机制。
缺段中断机构。
地址变换机构。

段表机制

环保护

环保护的基本原则是：
一个程序可以访问驻留在相同环或较低特权环中的数据
一个程序可以调用驻留在相同环或较高特权环中的服务。

习题4

P162

可采用哪几种方式将程序装入内存？它们分别适合何种场合

绝对装入方式，适于单道程序环境
可重定位装入方式，适于多道程序环境，静态存储分配
动态运行时装入方式，适于多道程序环境，动态存储分配

何谓静态链接？静态链接需要解决两个什么问题

静态链接：在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块（又称执行模块），以后不再拆开
需要解决：将相对地址进行修改；变换外部调用符号

何谓运行时动态链接？运行时动态链接有何优点

运行时动态链接：将某些目标模块的链接推迟到执行时才进行。
优点：节省内存空间

在动态分区分配方式中，应如何将各空闲分区链接成空闲分区链

按照地址递增的顺序链接分区：首次适应、循环首次适应
按照分区大小顺序链接分区：最佳适应、最坏适应算法
按分区的大小和分类链接成多条分区链：快速适应、伙伴系统、哈希算法

什么是基于顺序搜索的动态分区分配算法？分为哪几种
它将空闲分区链接成空闲分区链，以此在分配时搜索链上分区，找到满足算法要求的分区
分为首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法
在采用首次适应算法回收内存时，可能出现哪几种情况？应怎么处理

回收区与上面的空闲分区邻接，合并，首地址仍是前一空闲分区的，不必为回收分区分配新表项，只需修改前一分区大小
回收区与下面的空白区邻接，合并，重新使用新空闲区首址，修改大小
回收区与上、下面的空白区邻接，合并，直接将后面空白区取消，修改大小，首地址仍是前一空闲分区的
回收区与上、下面的空白区均不邻接，建立新表项

为什么要引入对换？对换可分为哪几种类型
为了提高系统的吞吐量，提高内存的利用率和处理机的利用率；
全局对换、局部对换。
为实现对换，系统应具备哪几方面的功能
对对换空间的管理
进程的换入、换出
基于离散分配时所用的基本单位不同，可将离散分配分为哪几种？
分页存储管理方式、分段存储管理方式、段页式存储管理方式
什么是页表？页表的作用是什么？
每个进程对应 1 个页表，描述该进程的所需各页面在内存中对应的物理块号。
为实现分页存储管理。需要哪些硬件支持?
页表寄存器、物理地址寄存器和快表寄存器。
地址变换机构。
在分页系统中是如何实现地址变换的?
（1）根据逻辑地址,计算出页号和页内偏移量；
（2）从PTR中得到页表首址，然后检索页表，查找指定页面对应的页框号；
（3）用页框号乘以页面大小获得其对应的起始地址，并将其送入物理地址的高端。
（4）将页内偏移量送入物理地址低端，形成完整的物理地址。
在具有快表的段页式存储管理方式中，如何实现地址变换?
根据逻辑地址中的页号，查找快表中是否存在对应的页表项。
若快表中存在该表项，称为命中（hit），取出其中的页框号，加上页内偏移量，计算出物理地址。
若快表中不存在该页表项，称为命中失败，则再查找页表，找到逻辑地址中指定页号对应的页框号。同时，更新快表，将该表项插入快表中。并计算物理地址
分页和分段存储管理有何区别?
页是信息的物理单位，而段是信息的逻辑单位。
页的大小固定而且由系统决定，段的大小不固定，通常由编译程序划分。
分页用户程序地址空间是一维的，分段用户程序地址空间是二维的。
试全面比较连续分配和离散分配方式。
连续分配程序空间本来就是连续的，用连续的内存装入连续的程序，减少管理工作的难度
离散分配方式需要额外的硬件支持，且实现的算法相对比较复杂
没有外零头不受连续空间限制，每块都能分出去，仅有小于一个页面的内零头程序大小一般不是页大小的整数倍。

P189

什么是程序运行时的时间局限性和空间局限性?
- 时间局限性被访问过的数据可能再次被访问
- 空间局限性被访问过的存储单元其附近也可能被访问
实现虚拟存储器需要哪些硬件支持?
请求分页/段的页/段表机制
缺页/段中断机构
地址变换机构
实现虚拟存储器需要哪些关键技术？
请求调页/段功能、页面置换功能
请详细说明请求分页系统的地址变换过程。
1. 取逻辑地址分解为页号和页内偏移
2. 根据页号查找页表,获得该页的描述信总
3. 若该页中断位为1，产生缺页中断
4. 更新该页的描述信息
5. 根据页块号和页内偏移，计算物理地址。
试说明在请求分页系统中页面的调入过程。
当程序要访问的页面未在内存时，便向CPU发出缺页中断，中断处理程序通过查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘将所缺之页调入内存，然后修改页表。
如果内存已满，则须先按照置换算法从内存中选出一页准备换出，然后再把所缺的页调入内存，并修改页表中的相应表项，并将此页表项写入快表中。
在缺页调入内存后，修改后的页表形成所要访问数据的物理地址，再去访问内存数据。
整个页面的调入过程对用户是透明的。
在请求分页系统中，常采用哪几种页面置换算法?
最佳置换算法OPT
先进先出置换算法FIFO
最近最久未使用置换算法LRU
最少使用置换算法LFU
简单的Clock置换算法
改进型Clock置换算法

在请求分页系统中，产生“抖动”的原因是什么?
- 进程分配的物理块太少
- 置换算法选择不当
- 全局置换使抖动传播