操作系统复习七、八章

文章目录

操作系统复习七、八章
- 第七章内存管理
- - 内存管理的基本要求和原理
  - 覆盖与交换
  - 连续分配管理方式
  - 非连续分配管理方式
  - 基本分段存储管理方式
  - 段页式管理方式
  - 补充
- 第八章虚拟内存
- - 虚拟内存的基本概念
  - 请求分页管理方式
  - 易混知识点
  - 页面置换算法
  - 页面分配策略
  - 抖动
  - 工作集

第七章内存管理

基本概念
- 重定位机制、内存的保护和共享、逻辑地址、物理地址等
内存管理技术(表7.1)放置算法，地址计算方法
- 固定分区
- 动态分区
- 简单分页
- 简单分段

内存管理的基本要求和原理

程序执行前需要先放到内存中才能被 CPU 处理——缓和CPU与硬盘之间的速度矛盾
内存管理的功能
- 内存空间的分配与回收：操作系统完成主存储器空间的分配和管理
- 地址转换：逻辑地址转换为物理地址
- 内存空间的扩充：利用虚拟存储技术或者自动覆盖技术，从逻辑上扩充内存
- 存储保护：保护各道作业在各自存储空间运行，互不干扰
程序的装入和链接
- 创建步骤
  - 编译：编译程序将用户源代码编译成若干目标模块
  - 链接：由链接程序将编译后的形成的一组目标模块及所需要的库函数链接在一起，形成一个完整的装入模块
  - 装入：由装入程序将装入模块装入内存运行
- 链接的类型
  - 静态链接：程序运行之前，将库函数连接成一个完整的可执行程序
  - 装入时动态链接：将用户源程序编译后得到目标模块，装入内存时，采用边装入边链接的方式
  - 运行时动态链接：对于某些目标横块的链接，程序需要时才会对其链接
    便于修改和更新，便于实现对目标横块的共享
- 装入模式
  - 绝对装入
  - 可重定位装入（静态重定位）
    - 装入时按照实际的内存地址，将程序和数据装入内存
    - 优点：不需要对程序和数据的地址进行修改
    - 缺点：只适用于单道程序环境
  - 动态运行时装入（动态重定位）
    - 装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，当程序真正执行时才进行转换
    - 特点：需要重定位寄存器可以将程序分配到不连续的存储区中便于程序段的共享可以向用户提供更大的地址空间（地址空间大于存储空间）
逻辑地址空间与物理地址空间
- 逻辑地址空间：即相对地址，链接程序依次按照各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间
- 物理地址空间：
  - 内存中物理单元的集合，是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取。
  - 地址重定位：逻组地址转换成物理地址的过程。
内存保护
- CPU中设置上、下限寄存器，存放用户作业在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器的数据比较，判断是否越界
- 重定位寄存器（基址寄存器）和界地址寄存器（限长寄存图）：重定位寄存器中包含最小物理地址值，界地址寄存器包含逻辑地址的最大值地址转换过程：逻铜地址->界地址寄存暑->重定位寄存器->物理地址

覆盖与交换

覆盖
- 思想：将程序分为多个段（多个模块），常用的段常驻内存，不常用的段在需要时调入内存
- 将用户空间分为一个固定区和若干覆盖区，活跃部分放在固定区，即将访问的段放在覆盖区
- 特点：打破了必须将一个进程的全部信息装入主存后才能运行的限制，内存中能够更新的地方只有覆盖区的段，不在覆盖区的段会常驻内存
交换
- 思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）
- 换出：将处于等待状态的程序从内存中转移到铺存
- 换入：把准备好竞争CPU运行的程序从辅存转移到内存
- 结构：把磁盘空间分为文件去和对换区两个部分
  - 文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式
  - 对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区，主要追求换入换出速度，因此通常对换区采用连续分配方式
交换存在的问题
- 备份存储，使用快速硬盘，要求存储空间足够大，并且能够对内存映像进行直接访问
  转移时间和所交换的内存空间成正比
- 只有进程空闲状态才能将进程换出
- 交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用起来会很快
- 交换通常在有许多进程运行且内存吃紧时开始启动，系统负荷降低就暂停
- 普通的交换使用不多，但交换策略的某些变体在许多系统中仍发挥作用
注意： PCB 会常驻内存，不会被换出外存

连续分配管理方式

单一连续分配
- 内存分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分，用户区为用户提供
- 无须进行内存保护，不会出现越界异常
- 优点：实现简单，无外部碎片，采用覆盖技术，不需要额外技术支持，只适用于单用户，单任务的操作系统
- 缺点：存在内部碎片，存储器利用率低
固定分区分配
- 种类
  - 分区大小相等：用一台计算机去控制多个相同对象的场合，缺乏灵活性
  - 分区大小不等：划分为多个较小的分区，适量的中等分区和少量大分区
- 优点：适用于多道程序的存储，无外部碎片
- 缺点：
  - 主存利用率低，存在内部碎片
  - 不能实现多进程共享一个主存区
  - 程序太大，无法放入任何一个分区
动态分区分配
- 在进程装入内存的时候，根据内存的大小动态的建立分区
- 优点：分区大小可以根据进程的实际情况进行分配
- 缺点：存在外部碎片，最后导致主存利用率下降，采用紧凑技术可以缓解这种缺陷
- 动态分配算法
  - 首次适应算法
    - 空闲分区按照地址递增的顶序进行查找，找到第一个满足要求的分区进行分配
    - 优点：综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序
  - 最佳适应算法
    - 按照容量递增的顶序进行查找分区，将第一个满足条件的进行分配
    - 优点：可以尽可能多地留下大片的空闲区
    - 缺点：性能较差，产生最多的外部碎片，回收分区后可能需要对空闲分区队列重新排序
  - 最坏适应（最大适应算法）
    - 空闲分区按照容量递减的次序进行查找，第一个满足条件的进行分配
    - 优点：可以减少难以利用的小碎片
    - 缺点：导致很快没有较大的内存块，性能很差，不利于大进程，算法开销大
  - 邻近适应算法（首次适应算法）
    - 分配内存时从上次查找结束的位置开始继续查找
    - 优点：算法开销小
    - 缺点：会使高地址的大分区也被用完

非连续分配管理方式

允许一个程序分散的装入不相邻的内存分区
基本分页存储管理方式
- 设计思想
  - 将主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位，进程以块为单位尽行空间申请
  - 分页存储与固定分区技术很像，但是其分页相对于分区又很小，分页管理不会产生外部碎片，产生的内部碎片也非常的小
- 分页存储的基本概念
  - 页面和页面大小
    - 进程中的块 = 页
    - 内存中的块 = 页帧
    - 进程申请主存空间，为每个页面分配主存中可用的页框，即页与页框一一对应
    - 页面大小要适中
      - 页面太小：进程页面数过多，页表过程，增加内存占用，降低硬件地址转换效率
      - 页面太大：页内碎片过多，降低内存利用率
  - 地址结构
    - 页号（有多少页的编号） + 页内偏移（页内存了多少东西）
  - 页表
    - 为了便于在内存中找到进程的每个页面对应的物理块，系统为每个进程建立一张页表，记录页面在内存中对应的物理块号，页表一般放在内存中
    - 页表项：页号+物理内存中的块号（不要与地址结构搞混），页表项的物理内存块号+地址结构中的页内偏移=物理地址
- 基本地址变换机构
  - 计算方式
    - 也好P = A / L，以内偏移量 W = A % L
    - 比较页号 P 和页表长度 M，若 P >= M产生越界中断
    - 页表中页号P对应的页表项地址 = 页表始址 F + 页号 P * 页表项长度取出该页表项内容b
    - 计算 E = b * L+ w 使用 E去访问内存
  - 页表项大小的设计应当尽量一页正好能装下所有的页表项
  - 分页管理存在的问题
    - 地址变换过程必须足够快，否则访存速率会峰低
    - 页表不能太大。否则会降低内存利用率
  - 组成
    - 设置一个页表寄存器(PTR),存放页表在内存中的起始地址F和页表长度M
    - 页表的始址和页表长度放在进程控制块(PCB)中
- 具有快表的地址变换机构
  - 可优化方向：如果页表放在内存中，取地址访问一次内存，按照地址取出数据访问一次内存，共需要两次访问内存
  - 优化：地址变换机构中增加一个具有并性查找能力的高速缓冲寄存器（快表），又称为相联存储器(TLB)
    相联存储图既可以按照地址查找也可以按照内容查找
  - 访问一个逻辑地址的访问次数
    - 基本地址变换机构两次访存
    - 具有块表的地址变换机构
      - 块表命中，只需一次访存
      - 快表未命中，需要两次访存
  - 变换过程
    - CPU给出逻辑地址后，先查询快表中是香命中
    - 若快表命中，直接从快表中该页对应的页框好，与页内偏移量拼接成物理地址
    - 若快表不命中，再按照正常方式从页表中查询相应页表项，并将该页表项存入快表中（按照一定策路）
两级页表
- 如果页数过多，就会导致页表也过多，那么我们可以考虑设置一个用来储存页表的页表（套娃）
- 逻辑地址空间格式=一级页号+二级页号+页内偏移
- 设计多级页表的时候，最后一定要保证顶级页表一定只有一个
- 建立多级页表的目的在于建立索引，不必浪费主存空间去储存无用的顶表项，也不用盲目式的查询页表项

基本分段存储管理方式

出发点
- 分页是从计算机角度考虑设计的，目的是为了内存的利用率，提高计算机性能，分页通过硬件机制实现，对用户完全透明
- 分段是从用户和程序员的角度提出，满足方使编程，信息保护和共享，动态增长及动态链接等多方面的需要
分段
- 按照用户进程中的自然段划分逻辑空间
- 地址结构=段号S+段内偏移量W
- 页式系统中，页号和页内偏移对用户透明
- 段式系统中段号和段内偏移量必须由用户显示的提供
段表
- 每个进程都有一张逻相空间与内存空间映射的段表，这个段表项对应进程的一段，段表项记录该段在内存中的始址和长度
- 段表内容=段号+段长+本段在主存中的地址
地址变换机构
- 逻辑地址A中取出段号S和段内偏移量W
- 比较段号S和段表长度M,若S>=M,则产生越界中断，否则继续执行
- 段号S对应的段表项地址=段表始址F+段号S段表项长度，从该段表项中取出段长C,比较段内偏移量与C的大小判断是否出现越界
- 取出段表项中该段的始址b,计算E=b+W,用得到的物理地址E去访问内存
段的共享与保护
- 共享
  - 两个作业的段表中响应表项指向被共享段的同一个物理副本来实现的。纯代码或者可重入代码以及不可修改的数据可以被共享
- 保护机制
  - 存取控制裱糊
  - 地址越界保护

段页式管理方式

页式存储有效的提高内存利用率，分段存储能反映程序的逻辑结构并有利于段的分享，将这两种方式结合一下。这种二者结合的方法经常在计算机理论中遇到
思想
- 作业的地址空间首先被分成若干逻辑段，每段有自己的段号
- 每个段分成若干大小固定的页
- 对内存空间的管理仍然和分页存储管理一样
地址结构段号S+页号P+页内偏移量W
为了实现地址变换，系统为每个进程建立了一张段表，每个分段有一个页表。一个进程中，段表只能有一个，页表可以有多个
地址变换方式

补充

不能被修改的代码称为纯代码或可重入代码，不属于临界资源
分段与分页的区别
- 分页对用户不可见，分段对用户可见
- 分页的地址空间是一维的，分段的地址空间是二维的
- 分页（单级页表）、分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构
- 分段更容易实现信息的共享和保护（纯代码问重入代码可以共享）
分段与分页的优缺点
- 分段
  - 优点：很方便按照逻辑模块实现信息的共享和保护
  - 缺点：
    - 如果段长过大，为其分配很大的连续空间会很不方便
    - 段式管理会产生外部碎片
- 分页
  - 优点：内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片
  - 缺点：不方便按照逻辑模块实现信息的共享和保护

第八章虚拟内存

虚拟内存的特性
虚拟内存的实现:软件和硬件结合 (页表分级、快表机制联想存储器TLB、存取时间计算、地址计算
- 硬件上: 请求分页、请求分段、段页式
- 软件上: 操作系统的各种策略(表8.3)
- 常用的替换策略
  - (OPT\LRU\FIFO\CLOCK)Belady现象，缺页中断次数，若没有说明的，包括初始的

虚拟内存的基本概念

传统管理方式的特征
- 一次性：作业必须一次性全部装入内存后，才能开始运行
  - 作业很大无法装入则无法运行
  - 大量作业要求运行时，由于内存不足，只能一部分作业先运行，导致多道程序度下降
- 驻留性
  - 作业装入内存后，一直驻留在内存中，任何部分不会被移出
局部性原理
- 时间局部性
  - 一条指令执行后，不就之后指令可能被再次执行，数据被访问后，不久后数据可能再次被访问
  - 原因：程序中存在着大量的循环操作
  - 时间局部性通过将最近使用的指令和数据存储在高速缓冲存储器中
- 空间局部性
  - 一旦程序访问了某个存储单元，不久之后附近的存储单元也将被访问
  - 原因：指令通常是顺序存放，顺序执行的，数据一般也是以向量、数组、表等形式簇聚存储的
  - 空间局部性使用较大的高速缓存，将预取机制继承到高速缓存控制逻辑中实现
虚拟存储器的定义和特征
- 基于局部性原理，程序的一部分装入内存，一部分留在外存，需要的时侯将外存内容调入内存，就好像产生了一个巨大的内存空间
- 特征：
  - 多次性：作业在运行时，分多次调入内存运行
  - 对换性：作业不必一直驻留内存，允许作业在运行过程中进行换进换出
  - 虚拟性：从逻辑上扩充内存容量，使用户看到的内存容量远大于实际的内存容量
虚拟内存技术的实现
- 建立在离散分配的内存管理方式上
- 实现方式
  - 请求分页存储管理
  - 请求分段存储管理
  - 请求段页式存储管理
- 硬件支持
  - 一定容量的内存和外存
  - 页表机制（或者段表机制）
  - 中断机构
  - 地址变换机构

请求分页管理方式

系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能
页表机制
- 组成：页号物理块号状态位P访问字段A
  修改位M外存地址
- 状态位：当前页是否已经调入内存
- 访问字段A:记录本页在一段时间内被访问的次数
- 修改位M:记录本页是否被修改过
- 外存地址：指出该页在外存上的位置（通常是物理块号）
缺页中断机制
- 当访问页面不在内存时就会发生缺页中断
- 特点
  - 指令执行期间产生中断，而不是指令执行之后产生中断和处理中断
  - 一条指令在执行期间，可能产生多次缺页中断
地址变换机构
- 检索快表，找到访问页，修改页表项中的访问位，利用页表项中给出的物理块号和页内地址形成物理地址
- 没有找到改页的页表项，去内存中寻找页表，看该页是否已经调入内存，没有调入则产生缺页中断，请求从外存把该页调入内存

易混知识点

虚拟内存的最大容量是由计算机的地址结构(CPU寻址范围)确定的
虚拟内存的实际容量=min(内存和外存容量之和，CPU寻址范固)

页面置换算法

最佳置换算法（OPT）
- 选择永不使用或者最长时间内不再访问的页面进行淘汰，但是现实中是无法预知的（无法实现）
- 优点：缺页率最小，性能最好
先进先出页面置换算法（FIFO）
- 优先淘汰最早进入的页面
- 优点：实现简单
- 缺点：与进程的实际运行规律不匹配
- Belady异常：增大分配的物理块数但是故障数不减反增。只有先进先出算法会出现
最近最久未使用（LRU）置换算法
- 选择最近最长时间设有被访问的页面进行淘汰，每个页面设置一个访问字段，用来标识上次被访问到现在经历的时间
- 优点：性能好
- 缺点：实现复杂需要寄存器和栈的硬件支持LRU是堆栈类算法
时钟CLOCK置换算法
- 像一个时钟一样转图，每个页面设置一个使用位（访问位），遇到设有被使用的就会将页面换出，然后将使用位置0，如果遇到使用的就会将使用位置零，然后扫描下一个
- 优点：性能接近于最佳置换算法
- 缺点：实现复杂开销大
- 改进型CLOCK算法
  - 使用位（访问位）的基础上增加修改位
  - 扫描过程
    - 扫描缓冲区，选择第一个使用位和修改位都为0的页面换出
    - 第一步失败后，查找使用位为0，修改位为1的进行替换，对于每个跳过的帧，将使用位置为0
    - 第二步失败后，指针回到初始地点且使用位（访问位）均为0，重复第一步
  - 优点：相对于未改进型，节省了时间

页面分配策略

驻留集：给一个进程的分配的物理页框的集合就是这个进程的驻留集
考虑因素
- 分配给一个进程的的存储量域小，任何时侯驻留在主存中的进程数就域多，可以提高处理机的时间利用率
- 一个进程在主存中的页数过少，页错误率就会相对较高
- 页数过多，对进程的错误率也不会产生过多的影响
分配策略
- 固定分配局部置换
  - 每个进程分配固定物理块数，缺页的时候就进行换页
  - 难以确定每个进程应该分配的物理块数
  - 太多导致资源利用率下降太少导致频繁缺页中断
- 可变分配全局替换
  - 进程分配一定物理块，系统自身保留一定空闲物理块，如果进程缺页，就对该进程分配新的物理块
  - 优点：最容易实现，动态调整物理块分配
  - 缺点：如果盲目分配物理块，就会导致多道程序并发能力下降
- 可变分配局部替换
  - 根据进程的缺页情况，对物理块进行动态分配，如果频繁缺页，就对其多分配物理块，如果缺页率特别低，就减少其物理块
  - 优点；保特了系统的多道程序并发能力
  - 缺点：增大了开销，实现复杂
调入页面的时机
- 预调页策略
  - 将预计不久被访问的页面调入，成功率位50%
- 请求调页策略
  - 当进程提出缺页的时候，，再按照一定策略进行调页
  - 特点：一次调入一夜，调入/调出页面数多时会花费过多的I/O开销
从何处调页
- 拥有足够的对换空间：可以全部从对换区调入所需页面，提高调页速度
- 缺少足够的对换区空间：不会被修改的文件从文件区调入，可能被修改的部分换入对换区，以后再从对换区调入。原理：读速度比写速度块
- UNX方式：进程相关文件访问文件区，没有运行的页面从文件区调入，曾经运行过但又被换出的页面放在对换区

抖动

刚换出的页面又要换入内存
原因
- 分配到物理页帧数不足（主要原因）
- 置换算法不当

工作集

某段时间内，进程要访问的页面集合
原理
- 操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块
- 落入工作集的页面需要调入驻留集中，落在工作集外面的页面可以从驻留集中换出
- 若还有空闲物理块，可以再调入一个进程到内存以增加多道程序数。
- 若所有进程的工作集之和超过了可用物理块的总数，操作系统就会暂停一个进程，并将其页面调出并将其物理块分配给其他进程