【操作系统】第五章 存储器与虚拟存储器

目录

存储器的层次结构

程序的装入和链接

对换与覆盖

连续分配存储管理方式

分页和分段存储管理方式

虚拟存储器概述

请求分页存储管理方式

页面置换算法

抖动Thrashing与工作集

请求分段存储管理方式

---

存储器的层次结构

存储层次：CPU寄存器；
主存：高速缓存、主存储器、磁盘缓存；
辅存：固定磁盘，可移动磁盘
层次越高，访问速度越快，价格也越高，存储容量也最小
寄存器和主存掉电后存储的信息不再存在
辅存的信息长期保存

关于各级存储器：
可执行存储器：寄存器和主存储器
主存储器：内存或主存。
寄存器：访问速度最快，与CPU协调工作，价格贵。
高速缓存：介于寄存器和存储器之间。
> 备份主存主常用数据，减少对主存储器的访问次数；
>?缓和内存与处理机之间的矛盾。
磁盘缓存：
> 暂时存放频繁使用的一部分磁盘数据和信息；
>?缓和主存和I/O设备在速度上的不匹配；
> 利用主存的部分空间，主存可看成辅存的高速缓存。

程序的装入和链接

程序运行步骤：
1）编译：由编译程序(Compiler)对源程序进行编译，形成若干个目标模块
2）链接：由链接程序(Linker)将目标模块和它们所需要的库函数链接在一起，形成一个完整的装入模块
3）装入：由装入程序(Loader)将装入模块装入内存

物理地址和逻辑地址
物理地址（绝对地址）
> 物理内存的地址，内存以字节为单位编址
> 物理地址空间：所有物理地址的集合
逻辑地址（虚拟地址、相对地址）
> 由CPU产生的地址，即程序编译后使用的相对于0字节的地址
>?逻辑地址空间：由程序所生成的所有逻辑地址的集合

内存保护
目的：保护OS不被用户访问；保护用户进程不会相互影响
内存保护的实现：硬件
1）基地址寄存器：保存最小的合法物理内存地址（基地址）
2）界限寄存器：保存合法的地址范围大小（界限地址）
3）内存空间保护的实现： 判断“?基地址≤物理地址＜（基地址+界限地址）”是否成立。

程序的装入
1）绝对装入方式：编译时产生的地址使用绝对地址 程序或数据被修改时，需要重新编译程序
2）可重定位装入方式：
? ?编译后的目标模块使用相对地址
? ?在装入时，完成重定位（静态重定位）[逻辑地址转换为物理地址的过程，称为重定位，也称为地址变换]
? ? 需硬件支持
3）动态运行时装入方式
编译后的目标模块使用相对地址
在运行时，完成重定位（动态重定位）

程序的链接
1）静态链接
在程序运行前，将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开；
对相对地址进行修改；变换外部调用符号
2）装入时动态链接
在装入内存时，采用边装入边链接的链接方式；
便于修改和更新；
便于实现对目标模块的共享；
3）运行时动态链接
将某些目标模块的链接推迟到执行时才执行。即在执行过程中，若发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将它装入内存，并把它链接到调用者模块上；
加快装入过程，节省大量的内存空间

对换与覆盖

对换Swapping：把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需的程序或数据，调入内存。
对换是提高内存利用率的有效措施，广泛应用于OS中

对换的类型
1）整体对换：对换以整个进程为单位，也称为进程对换（被广泛应用于多道程序系统，并作为处理机中级调度）
2）页面(分段)对换：对换是以“页”或“段”为单位进行的，又统称为“部分对换”
目的是为了支持虚拟存储系统
3）为了实现进程对换，系统必须能实现三方面的功能
对换空间的管理；进程的换出；进程的换入

对换区管理
主要目标：
????????提高进程换入和换出的速度；
????????提高文件存储空间的利用率次之；
????????应采用连续分配方式，很少考虑碎片问题
盘块管理中的数据结构
????????用于记录外存对换区中的空闲盘块的使用情况；
????????与动态分区分配方式相似；
????????空闲分区表/空闲分区链：包含对换区首址及大小
对换区的分配与回收：与动态分区方式的内存分配与回收方法相似

覆盖Overlaying
1.解决问题：程序大小超过物理内存总和
2.程序运行时：
只在内存中保留那些在任何时间都需要的指令和数据；
程序的不同部分在内存中相互替换。
3.由程序员声明覆盖结构，不需要操作系统的特别支持
4.覆盖结构的程序设计很复杂
5.应用于早期的操作系统

连续分配存储管理方式

连续分配方式：为一个用户程序分配一个连续的内存空间。
分类：
1）单一连续分配；2）固定分区分配；3）动态分区分配；4）动态可重定位分区分配

一、单一连续分配：
内存：
????????系统区：供OS使用、低址部分；
????????用户区：供用户使用
分配方式：单道程序环境下，仅装有一道用户程序，即整个内存的用户空间由该程序独占。
????????内存分配管理十分简单，内存利用率低
????????用于单用户、单任务OS
????????CP/M、MS-DOS、RT11
未采取存储器保护措施：节省硬件；方案可行

二、固定分区分配：
最早的、也是最简单的一种可运行多道程序的存储管理方式。
预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。
每个分区的大小可以相同也可以不同。但分区大小固定不变，每个分区装一个且只能装一个作业。
内存分配：如果有一个空闲区，则分配给进程。
划分分区的方法：
? ? ? ? 分区大小一样：程序太小（浪费内存）；程序太大（装不下）【有些场合适用eg：利用一台计算机同时控制多个相同对象】
? ? ? ? 分区大小不一样：多个小分区；适量中分区；少量大分区

三、动态分区分配：
定义: 又称为可变分区分配，根据进程的实际需要，动态地为之分配内存空间。
数据结构：空闲分区表；空闲分区链
1）空闲分区表：一个空闲分区占一个表目（?分区序号、分区始址、分区大小、状态等）
2）空闲分区链：为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区的尾部设置后向指针，通过前、后向指针，可将所有的空闲分区链接成一个双向链。

分配算法：顺序式分配算法；索引式分配算法
1）顺序式分配算法：
? > 依次搜索空闲分区链上的空闲分区，寻找一个其大小能够满足要求的分区
? >? 首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法
首次适应算法：空闲分区链以地址递增的次序链接
从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止
缺点：低址部分留下许多小碎片
循环首次适应算法：从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区
空闲分区分布更均匀，减少了查找的开销
缺点：缺乏大的空闲分区
最佳适应算法：?搜索整个序列，找到适合条件的最小的分区进行分配
空闲分区按其容量从小到大的顺序链接
用最小空间满足要求；但留下许多难以利用的小碎片
最坏适应算法：搜索整个序列，寻找最大的分区进行分配
空闲分区按其容量从大到小的顺序链接
分割后空闲块仍为较大空块；缺乏大的空闲分区
2）基于索引搜索的动态分区分配算法
>?提高搜索空闲分区的速度，在大、中型系统中采用
> 快速适应算法、伙伴系统和哈希算法
快速适应算法：将空闲分区按其容量大小进行分类，具有相同容量的所有空闲分区设有一个空闲分区链表；系统设有一张管理索引表，每一项对应一个空闲分区类型；分配时，根据进程长度，从索引表中寻找到能容纳它的最小空闲分区链表；从链表中取下第一块进行分配
优点：不分割分区，不产生碎片，查找效率高
缺点：分区归还主存时算法复杂，系统开销较大，存在浪费
伙伴系统：分区大小均为2的k次幂；内存按2的幂的大小来分配，即4KB、8KB等；主要用于多处理机系统中（Linux早期版本）
哈希算法：建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项对应于一个空闲分区链表的头指针。进行分配时，根据空闲区大小，通过计算哈希函数，得到在哈希表中的位置，找到对应的空闲分区链表。
优点：查找快速！
分配操作：分配内存；回收内存

四、动态可重定位分区分配
连续分配存在问题：碎片
动态重定位：在指令运行时，实现地址转换(相对地址转换为绝对地址)
分配算法：类似于动态分区分配算法，增加了紧凑的功能

分页和分段存储管理方式

分页存储管理方式
进程的逻辑地址空间可能是不连续的，如果有可用的物理内存，它将分给进程。
把物理内存分成大小固定的块，称为物理块(frame)。（大小为2的幂，通常为1KB~8KB）
把逻辑内存也分成固定大小的块，称为页(page)。
保留所有空闲块的记录。
运行一个有N页大小的程序，需要找到N个空的页框来装入程序
存在页内碎片：进程最后一页经常装不满，而形成不可利用的碎片
地址中的结构（32位）
页号P ????????????????????12-31位：20位；地址空间最多允许有1M（2^20）页
位移量W（页内地址） 0-11：12位；每页大小为4KB （2^12）

若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得

其中，INT：整除函数，MOD：取余函数 例如：系统页面大小为1KB，设A=5168B，则P=5，d=48

页表
系统为每个进程建立了一张页表。（保存在主存中）
逻辑地址空间内的所有页，依次在页表中有一表项，记录相应页在内存中对应的物理块号。
页表的作用：实现从页号到块号的地址映射。
实现：
页表寄存器(PTR)指向页表的起始地址和长度
在这个机制中，每一次的数据/指令存取需要两次内存访问，一次是访问页表，一次是访问数据/指令
解决两次访问的问题，是采用小但专用且快速的硬件缓冲，这种缓冲称为转换表缓冲器(TLB)或联想寄存器。
引入快表后的有效访问时间：
> 查找快表需要的时间为 λ
> 假设访问内存一次需要的时间为t EAT = t + t = 2t (基本分页存储系统中)
> 命中率—在联想寄存器中找到页号的百分比，比率与联想寄存器的大小有关，假设为a
> 引入快表的有效访问时间 (EAT) EAT = λ * a + (t + λ)(1 – a) + ?t
快表大小：16-512个页表项，局部性：90%
对页表所需要的内存空间，采用离散分配方式；部分页表调入内存
页表结构：两级页表；多级页表；反置页表
1）页面大小为4KB时（12位），若采用一级页表结构，应具有20位的页号，即页表项应有1M个；
2）在采用两级页表结构时，再对页表进行分页，使每页中包含210个页表项，最多允许有210个页表分页。
3）对于64位的机器，采用多级表结构（如果页面大小为4KB，那么还剩下52位，假定物理块大小为4K来划分页表，则余下的42位用于外层页号。此时在外层页表中可能有4096G个页表项，要占用16384GB的连续内存空间）
4）为减少页表占用的内存空间，引入反置页表，一个系统一张页表 ；对每个内存物理块设置一个条目。 每个条目保存在真正内存位置的页的虚拟地址，以及包括拥有这个页的进程的信息。 减少了需要储存每个页表的内存，但是当访问一个页时，增加了寻找页表需要的时间。 可使用哈希表来将查找限制在一个或少数几个页表条目。?

分段存储管理方式：
? 引入目的：为了满足用户（程序员）在编程和使用上多方面的要求 ?
一个程序是一些段的集合，一个段是一个逻辑单位
优点：方便编程；信息共享；信息保护；动态链接；动态增长
基本原理：在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。每个段都有自己的名字，通常用一个段号来代替段名，每个段都从0开始编址，并存储在一段连续的地址空间内。段的长度由相应的逻辑信息组的长度决定，因此各段长度不等。

段表
在分段式存储管理系统中，为每个分段分配一个连续的分区。进程中的各个段可以离散地装入内存中不同的分区中。
每个段在表中占有一个表项，记录了该段在内存中的起始地址（基址）和段的长度。
段表保存在内存中，由控制寄存器保存其地址。

段页式存储管理方式
基本原理：分段和分页原理的结合，即先将用户程序分成若干段，再把每个段分成若干个页，并为每个段赋予一个段名。
优点：
既有分段系统的便于实现、可共享、易于保护、可动态链接；
又能像分页系统，很好地解决内存的外部碎片问题。

虚拟存储器概述

定义：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而成本接近于外存。

特征：
多次性：作业中的程序和数据允许被分成多次调入内存允许
对换性：作业运行时无须常驻内存
虚拟性：从逻辑上扩充了内存容量，使用户看到的内存容量远大于实际内存容量

实现方法：
请求分页系统：
????????硬件支持：页表、缺页中断、地址变换机构。
????????软件支持：请求调页软件、页面置换软件。
请求分段系统
????????硬件支持：段表、缺段中断、地址变换机构。
????????软件支持：请求调段软件、段置换软件。
段页式虚拟存储器：增加请求调页和页面置换。

请求分页存储管理方式

请求分页中的硬件支持
请求页表机制：
状态位P：指示该页是否在内存
访问字段A：记录该页在一段时间内被访问的次数
修改位M：也称脏位，标志该页是否被修改过
外存地址：指示该页在外存中的地址（物理块号）
缺页中断机构：
????????在指令执行期间产生和处理中断信号
????????一条指令在执行期间，可能产生多次缺页中断
地址变换机构：与分页内存管理方式类似

请求分页中的内存分配
最小物理块数的确定：保证进程正常运行所需的最小物理块数。
物理块的分配策略：
????????固定分配 局部置换； 可变分配 全局置换； 可变分配 局部置换。
物理块分配算法：
????????平均分配算法； 按比例分配算法； 考虑优先权的分配算法；

页面调入策略
> 何时调入：
预调页策略：预先调入一些页面到内存
请求调页策略：发现需要访问的页面不在内存时，调入内存
> 从何处调入页面
如系统拥有足够的对换区空间，全部从对换区调入所需页面
如系统缺少足够的对换区空间，凡是不会被修改的文件，都直接从文件区调入；当换出这些页面时，由于未被修改而不必再将它们重写磁盘，以后再调入时，仍从文件区直接调入
UNIX方式：未运行过的页面，从文件区调入；曾经运行过但又被换出的页面，从对换区调入
>?如何调入？
1）查找所需页在磁盘上的位置。
2）查找一内存空闲块：（如果有空闲块，就直接使用它； ?如果没有空闲块，使用页面置换算法选择一个“牺牲”内存块； 将“牺牲”块的内容写到磁盘上，更新页表和物理块表。）
3）将所需页读入(新)空闲块，更新页表
4）重启用户进程。
>?缺页率
访问页面成功(在内存)的次数为S； 访问页面失败(不在内存)的次数为F 总访问次数为A=S+F
缺页率为 f= F/A
影响因素：页面大小、分配内存块的数目、页面置换算法、程序固有属性
缺页中断处理的时间 t = β×ta + (1- β)×tb
存取内存的时间= 200 nanoseconds (ns)
平均缺页处理时间 = 8 milliseconds (ms)
t = (1 – p) × 200ns + p × 8ms ? = (1 – p) × 200ns + p ×8,000,000ns ? = 200ns + p × 7,999,800ns 如果每1,000次访问中有一个缺页中断，那么：? t = 8.2 ms ? ?
这是导致计算机速度放慢40倍的影响因子！

页面置换算法

页面置换：找到内存中没有使用的一些页，换出
算法：替换策略
性能 ：找出一个导致最小缺页数的算法
同一个页可能会被装入内存多次
优点：完善了逻辑内存和物理内存的划分——在一个较小的物理内存基础之上可以提供一个大的虚拟内存

页面置换算法：
最佳置换算法（OPT）：被置换的页将是之后最长时间不被使用的页
先进先出置换算法（FIFO）：总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰
最近最久未使用置换算法（LRU）：选择最近最久未使用的页面予以淘汰
最少使用算法（LFU）：LFU 选择在最近时期使用最少的页面作为淘汰页
Clock置换算法：每个页都与一个访问位相关联，初始值位0；当页被访问时置访问位为1；置换时选择访问位为0的页 ；若为1，重新置为0
页面缓冲算法：设置两个链表： ①空闲页面链表：保存空闲物理块 ②修改页面链表：保存已修改且需要被换出的页面等被换出的页面数目达到一定值时，再一起换出外存，
目的：显著降低页面换进、换出的频率，减少了开销；可采用较简单的置换策略
需要一个最小的缺页率；通过运行一个内存访问的特殊序列（访问序列），计算这个序列的缺页次数
访问内存的有效时间EAT

抖动Thrashing与工作集

抖动：一个进程的页面经常换入换出
根本原因：同时在系统中运行的进程太多； 因此分配给每一个进程的物理块太少，不能满足进程运行的基本要求，致使进程在运行时，频繁缺页，必须请求系统将所缺页面调入内存。
抖动的发生与系统为进程分配物理块的多少有关。
据程序运行的局部性原理，如果能够预知某段时间内程序要访问的页面，并将它们预先调入内存，将会大大降低缺页率。

工作集
定义：指在某段时间间隔Δ里进程实际要访问页面的集合。
把某进程在时间t的工作集记为w(t，Δ),其中的变量Δ称为工作集的“窗口尺寸”。
工作集w(t，Δ)是二元函数，即在不同时间t的工作集大小不同，所含的 ? ?页面数也不同；工作集与窗口尺寸Δ有关，是Δ的非降函数，即：

预防方法：
1）采取局部置换策略：只能在分配给自己的内存空间内进行置换；
2）把工作集算法融入到处理机调度中；
3）利用“L=S”准则调节缺页率：

4）选择暂停进程

请求分段存储管理方式

硬件支持：
请求段表机制：

缺段中断机构：
1）在指令执行期间产生和处理中断信号
2）一条指令在执行期间，可能产生多次缺段中断
3）由于段不是定长的，对缺段中断的处理要比对缺页中断的处理复杂
地址变换机构：若段不在内存中，则必须先将所缺的段调入内存，并修改段表，然后利用段表进行地址变换。

分段的共享
> 共享段表：保存所有的共享段
1）共享进程计数count；? ? ? ?2）存取控制字段；? ? ? ? 3）段号
> 共享段的分配：
对首次请求使用共享段的用户，分配内存，调入共享段，修改该进程段表相应项，再为共享段表增加一项，count=1
对其他使用共享段的用户，修改该进程段表相应项，再为共享段表增加一项，count=count+1
>?共享段的回收
撤销在该进程段表中共享段所对应的表项，并执行count=count-1操作
若为0，回收该共享段的内存，并取消共享段表中对应的表项
若不为0，只取消调用者进程在共享段表中的有关记录

分段保护
1）越界检查：由地址变换机构来完成； 比较段号与段表长度；段内地址与段表长度。
2）存取控制检查：以段为基本单位进行。
通过“存取控制”字段决定段的访问方式；
基于硬件实现。
3）环保护机构：
低编号的环具有高优先权；
一个程序可以访问驻留在相同环或较低特权环（外环）中的数据；
一个程序可以调用驻留在相同环或较高特权环（内环）中的服务。

本篇介绍了存储器与虚拟存储器。存储器的层次结构，程序的装入与链接，对换与覆盖，连续分配方式等内容。虚拟存储器的概念，请求分页、分段存储等内容，虚拟存储器提高了多道程序度与处理机的利用率。