操作系统复习四
# 存储器管理
# 程序的装入 (即重定位方法)
重定位：一个经过编译链接的程序存在于自己的虚拟地址空间中，当要运行时才把它装入主存空间。这时需要将程序中的虚拟地址转换为主存中的物理地址，这个转化过程就是重定位技术。
程序在成为进程前的准备工作如下：
- 编辑：形成源文件
- 编译：形成目标模块
- 链接：由多个目标模块或程序库生成可执行文件
- 装入：构造 PCB，形成进程 (使用物理地址)
重定位方法：
- 绝对装入
- 可重定位装入 (又称静态重定位)：
- 程序员编写程序时可以采用相对地址
- 作业（用户程序）在装入内存时才确定它的物理地址，并且将相对地址转换为物理地址
- 作业一旦装入就不能移动、改变空间或者被换出主存
- 在程序运行之前，由链接装入程序进行的一次重定位
- 在程序运行之前已经完成了逻辑地址到物理地址的转换 (只要完成链接装入)
- 动态装入
- 动态重定位是在程序执行的过程中，每当访问指令或数据时，才将要访问的指令或数据的逻辑地址转换成物理地址
- 在程序装入时不对地址做任何操作，也就是保留逻辑地址不变，装入内存后的所有地址都仍是相对地址
# 分区储存管理：
分配方式：
- 固定分区
- 分区大小相等：只适合于多个相同程序的并发执行
- 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区
- 固定分区可能存在内碎片
- 动态分区分配
- 在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小
- 优点：没有内碎片，缺点：有外碎片；如果大小不是任意的，也可能出现内碎片
分区分配所用数据结构：
空闲分区表 —— 核心数据结构
用于为内存中每个尚未分配出去的分区设置一个表项，每个分区的表项包含分区序号、分区始址及分区大小等表目
空闲分区链
通过前、后向指针将所有的分区链接成一个双向链
分区分配的算法：
首次适应算法 FF
内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲分区为止。然后按作业大小划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中
循环首次适应算法
内存分配时，不再每次从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，并从中划出一块与请求的大小相等的内存空间分配给作业
最佳适应算法
"最佳" 是指每次为作业分配内存时，总把既能满足要求、又是最小的空闲分区分配给作业，避免了 "大材小用"
分区的分配和回收操作：
分配内存
首先系统要利用某种分配算法，从空闲分区链 (表) 中找到所需的分区
- 设请求的分区大小为 u.size，表中每个空闲分区的大小可表示为 m.size
- 若 m.size-u.size<=size (size 是事先规定的不再切割的剩余分区的大小), 说明多余部分太小，可不再切割，将整个分区分配给请求者
- 否则 (即多余部分超过 size)，从该分区中划分出与请求的大小相等的内存空间分配出去，余下的部分仍留在空闲分区链或空闲分区表中。最后，将分配区的首址返回给调用者
回收内存
可重定位分区分配：
内存紧缩：将各个占用分区向内存一端移动。使各个空闲分区聚集在另一端，然后将各个空闲分区合并成为一个空闲分区
动态重定位实现：
- 地址变换过程（逻辑地址到物理地址）是在程序执行期间，随着对每条指令和数据的访问而自动进行的，故称为动态重定位
- 当系统对内存进行了 “紧凑”，而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可
- 地址转换是程序指令要真正执行时才进行
- 增加了一个重定位寄存器，来存放程序或数据在内存中的起始地址。（提高地址变换的速度，提高效率）
动态重定位分区分配算法：
对换：是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。
- 整体对换：整个进程对换
- 部分对换：以页或段为单位进行对换
对换空间的管理：
- 为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况
- 数据结构：可以用空闲分区表或空闲分区链
外存空间分类：
- 文件区：
- 用于存放文件，由于通常的文件都是较长久地驻留在外存上，故对文件区管理的主要目标，是提高文件存储空间的利用率
- 离散分配方式
- 对换区
- 于存放从内存换出的进程，由于这些进程在对换区中驻留的时间是短暂的，而对换操作又较频繁，故对对换空间管理的主要目标，则是提高进程的换入、换出速度
- 用连续分配方式，较少考虑外存中的碎片问题
进程的换入与换出：
进程换出：
系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改
进程换入：
系统应定时地查看所有进程的状态，从中找出 “就绪” 状态但已换出的进程，将其中换出时间 (换出到磁盘上) 最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止
离散分配方式：
分页存储管理
分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页；
相应地，也把内存空间分成与页面相同大小的若干个存储块，称为 (物理) 块或页框 (frame)
分配时主存块可以不连续，而页内逻辑地址是连续的
逻辑地址由两部分组成：页号和页内地址，逻辑地址是连续的
页面大小应是 2 的幂，通常为 512B~8KB
- 小例题：某系统页面大小为 1kB，设 A＝2170B，则 P＝2，d＝122
地址变换机构 —— 页表：
实现逻辑地址到物理地址的转换。实际上只是将逻辑地址中的页号，转换为内存中的物理块号
作用：实现从页号到物理块号的地址映射
由于页表是存放在内存中的，这使 CPU 每次要存取一个数据时，都要两次访问内存
虚实地址快速转换缓冲 (TLB) 是一组相联快速存储，是寄存器
- 程序地址访问存在局部性
- 空间局部性
两级页表与多级页表：解决了难以找到一块连续的大内存空间的问题，只需将当前需要的部分页表调入内存，其余的页表驻留在磁盘上，需要再调入
分段存储管理
- 引入分段存储管理方式， 主要是为了满足用户和程序员的需要：
- 方便编程、信息共享、信息保护、动态增长、动态链接
- 将程序的地址空间划分为若干个段 (segment)，程序加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。
- 优点：没有内碎片，外碎片可以通过内存紧缩消除
- 段表：和页表作用一样
- 引入分段存储管理方式， 主要是为了满足用户和程序员的需要：
页式管理和段式管理比较：
- 分页是出于系统管理的需要，分段是出于用户应用的需要
- 页大小是系统固定的，而段大小则通常不固定
- 分页是一维的，各个模块在链接时必须组织成同一个地址空间；分段是二维的 (因为分段还有一个段长)，各个模块在链接时可以每个段组织成一个地址空间
- 通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度
段页式存储管理
- 把用户程序分成若干段，再把每个段分成若干页
- 段页式既具有分段系统便于实现、分段可共享、易于保护、可动态链接等一系列优点，也具有分页系统那样很好地解决内存的外部碎片问题，以及为各个分段可离散地分配内存等问题
- 在段页式系统中，为了获取一条指令或数据，须 3 次访问内存
- 为了提高速度，增设了一个高速缓冲寄存器，每次访问它时，同时利用段号和页号去检索高速缓存
# 虚拟存储器
常规存储器管理方式的特征：一次性 (一次性装入)，驻留性 (驻留内存，直到运行结束)
局部性原理：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限与一定区域。
- 时间局部性：大量循环操作
- 空间局部性：程序的顺序执行
虚拟存储器：具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量受限于计算机的地址结构和可用磁盘容量，其运行速度接近于内存速度。
虚拟存储的好处：大程序，大的用户空间，并发，易于开发
虚拟存储器实现方法：
分页请求系统
在分页系统基础上，增加请求调页功能、页面置换功能
- 硬件：
- 请求分页的页表机制
- 缺页中断机构
- 地址变换机构
- 硬件：
分段请求系统
在分段系统基础上，增加请求调段功能、分段置换功能
- 硬件：
- 请求分段的段表机制
- 缺段中断机构
- 地址转换机构
- 硬件：
虚拟存储器特征：多次性、对换性、虚拟性
虚拟存储的调入策略、分配策略和清除策略
调入策略：
- 请求调页：只调入发生缺页时所需的页面，容易实现，对外存 I/O 次数多，开销较大
- 预调页：在发生缺页需要调入某页时，一次调入该页以及相邻的几个页，提高调页的 I/O 效率，基于预测，若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页
分配策略：
- 最佳适应、最先适应
清除策略：
- 请求清除：页被置换时才调出，把清除推迟到最后一刻
- 预清除：该页被置换之前就调出，因而可以成批调出多个页面
内存分配策略和分配算法：
最小物理块确定：
- 指能保证进程正常运行所需的最小物理块数
- 进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、 功能和寻址方式
- 简单机器最少 2 块，一块是用于存放指令的页面，另一块则是用于存放数据的页面
- 允许间接寻址，则至少 3 块或者更多块
物理块的分配策略
固定分配局部置换
为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。运行时缺页，则从分配给该进程的 n 个页面中选出一页换出，然后在调入一页，保证该进程的内存空间不变。
可变分配全局置换
可变分配局部置换
页面置换算法：
最佳置换算法
其所选择的被淘汰页面，将是永不使用的，或者是在将来最长时间内不再被访问的页面
先进先出置换算法
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰
最近最久未使用置换算法
选择最近最久未使用的页面予以淘汰
Clock 置换算法、改进型 Clock 置换算法
轮换算法：
每页有一个使用标志位 (use bit)，若该页被访问则置 user bit=1。置换时采用一个指针，从当前指针位置开始按地址先后检查各页，寻找 use bit=0 的页面作为被置换页。指针经过的 user bit=1 的页都修改 user bit=0，最后指针停留在被置换页的下一个页
最不常用算法：
选择到当前时间为止被访问次数最少的页面被置换；每页设置访问计数器，每当页面被访问时，该页面的访问计数器加 1；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零
例题：
1、多进程在主存中彼此互不干扰的环境下运行，操作系统是通过（B ）来实现的。
A、内存分配 b、内存保护 c、内存扩充 D、地址映射
2、假定占有 m 块（初始为空）的进程有一个页访问串，这个页访问串的长度是 p，其中涉及到 q 个不同的页号，对于任何页面替换算法，计算出：缺页中断次数的下界是（p），缺页中断的上界是（q）
3、多虚拟内存管理中，地址变换架构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（C），完成该变换过程的阶段是（D）。
A、编辑 B、编译 C、链接 D、装载
4、分区分配内存管理方式的主要保护措施是（A）。
A、界地址保护 B、程序代码保护 C、数据保护 D、栈保护
5、某基于动态分配存储管理的计算机，其主存容量为 55MB（初始为空），采用最佳适配算法，分配和释放的顺序为，分配 15MB，分配 30MB，释放 15MB，分配 8MB，分配 6MB，此时主存中最大空闲分区的大小是（B）。
A、7MB B、9MB C、10MB D、15MB
6、不会产生内碎片的存储管理是（B）。
A、分页式存储管理 B、分段式存储管理 C、固定分区式存储管理 D、段页式存储管理
7、分页系统中的页面是为（B ）。
A、用户所感知的 B、操作系统所感知的 C、编译系统所感知的 D、链接装配程序所感知
8、选项中，属于多级页表优点的是（ D）。
A、加快地址变换速度 B、减少缺页中断次数 C、减少页表项所占字节数 D、减少页表所占的连续内容空间
