操作系统

2020-04-29  本文已影响0人  KeHaoo

分成两个部分
第一部分：基本概念、处理器管理、存储管理
第二部分：设备管理、文件管理、并发程序设计

操作系统原理

基本概念

计算机硬件系统

组成

image-20200429093334026
中央处理器

中央处理器是计算机的运算核心（Core）和控制单元（ Control Unit） ，主要包括：

处理器与寄存器
image-20200429093613084
主存储器

DRAM

外围设备
设备类型
设备控制方式
总线
简介

总线（Bus） 是计算机各种功能部件之间传送信息的公共通信干线， 它是CPU、 内存、输入输出设备传递信息的公用通道

计算机的各个部件通过总线相连接， 外围设备通过相应的接口电路再与总线相连接， 从而形成了计算机硬件系统

按照所传输的信息种类， 总线包括一组控制线、 一组数据线和一组地址线

总线的类型

内部总线： 用于CPU芯片内部连接各元件

系统总线： 用于连接CPU、 存储器和各种I/O模块等主要部件

系统总线也有分级，如下面的图所示

通信总线： 用于计算机系统之间通信

系统总线

冯诺依曼结构

存储程序计算机

冯·诺伊曼等人在1946年总结并明确提出，被称为冯·诺伊曼计算机模型存储程序计算机在体系结构上主要特点

结构
image-20200429093531395

存储器的组织层次

存储器包括CPU中的高速缓存、主存储器、外围设备中的硬盘和网络中的远程存储器等

image-20200429093738493

计算机软件系统

软件开发的不同层次

计算机程序的执行过程

image-20200429094558283

操作系统

操作系统(Operating System)， 简称OS

OS是计算机系统最基础的系统软件， 管理软硬件资源、 控制程序执行， 改善人机界面， 合理组织计算机工作流程， 为用户使用计算机提供良好运行环境

简而言之， 操作系统是方便用户、 管理和控制计算机软硬件资源的系统程序集合

操作系统的组成

类型

操作控制方式

应用领域

资源管理

计算机资源包含

屏蔽资源使用的底层细节

驱动程序： 最底层的、 直接控制和监视各类硬件(或文件)资源的部分

职责是隐藏底层硬件的具体细节， 并向其他部分提供一个抽象的、 通用的接口
比如说： 打印一段文字或一个文件， 既不需知道文件信息存储在硬盘上的细节，也不必知道具体打印机类型和控制细节

资源共享方式
资源分配策略

系统控制

CPU速度与I/O速度不匹配的矛盾非常突出.只有让多道程序同时进入内存争抢CPU运行， 才可以够使得CPU和外围设备充分并行， 从而提高计算机系统的使用效率

image-20200429110425511 image-20200429110444095
多道程序系统的实现
控制方式
脱机作业控制方式

  1. OS： 提供作业说明语言

  2. 用户： 编写作业说明书， 确定作业加工控制步骤，并与程序数据一并提交

  3. 操作员： 通过控制台输入作业

  4. OS： 通过作业控制程序自动控制作业的执行

例： 批处理OS的作业控制方式， UNIX的shell程序，DOS的bat文件

联机作业控制方式

  1. 计算机： 提供终端（键盘/显示器）

  2. 用户： 登录系统

  3. OS： 提供命令解释程序

  4. 用户： 联机输入命令， 直接控制作业步的执行

例： 分时OS的交互控制方式

命令解释程序

不管是脱机控制方式还是联机控制方式都需要命令解释程序

命令解释程序： 接受和执行一条用户提出的对作业的加工处理命令
当一个新的批作业被启动， 或新的交互型用户登录进系统时， 系统就自动地执行命令解释程序， 负责读入控制卡或命令行， 作出相应解释， 并予以执行

会话语言： 可编程的命令解释程序

处理过程
  1. OS启动命令解释程序， 输出命令提示符， 等待（键盘中断/鼠标点击/多通道识别）
  2. 每当用户输入一条命令(暂存在命令缓冲区)并按回车换行时， 申请中断
  3. CPU响应后， 将控制权交给命令解释程序，接着读入命令缓冲区内容， 分析命令、 接受参数， 执行处理代码
  4. 前台命令执行结束后， 再次输出命令提示符，等待下一条命令
  5. 后台命令处理启动后， 即可接收下条命令

前台命令：必须执行完毕后，才能继续输入命令

后台命令：命令启动后，可以继续启动下一个命令，而命令在后台的执行不影响

系统接口

操作系统的程序接口——系统调用

操作系统实现的完成某种特定功能的过程； 为所有运行程序提供访问操作系统的接口

就是操作系统为一些操作提供了接口，应用程序需要执行这些操作的时候就会去调用这些接口

实现
image-20200429114141408

系统结构

结构设计

OS构件
内核、 进程、 线程、 管程等

内核设计是OS设计中最为复杂的部分

设计概念
模块化、 层次式、 虚拟化

内核

单内核：内核中各部件杂然混居的形态， 始于1960年代， 广泛使用； 如Unix/Linux， 及Windows(自称采用混合内核的CS结构)

微内核：1980年代始， 强调结构性部件与功能性部件的分离， 大部分OS研究都集中在此

混合内核：微内核和单内核的折中， 较多组件在核心态中运行， 以获得更快的执行速度

外内核：尽可能减少内核的软件抽象化和传统微内核的消息传递机制，使得开发者专注于硬件的抽象化，部分嵌入式系统使用

层次结构

处理器管理

处理器与寄存器

处理器部件

image-20200429115552592

指令译码器ID：负责具体的解释指令的执行

指令暂存器IR：负责对指令的存储

程序计数器PC：指向下一跳要执行指令的地址

算术逻辑单元在完成计算之后会将内容汇总到标志寄存器Flag中

内存地址寄存器MAR、内存数据寄存器MDR：用于访问内存数据

用户程序可见寄存器

可以使程序员减少访问主存储器的次数， 提高指令执行的效率

所有程序可使用， 包括应用程序和系统程序

控制与状态寄存器

用于控制处理器的操作； 主要被具有特权的操作系统程序使用， 以控制程序的执行

程序状态字PSW

PSW既是操作系统的概念， 指记录当前程序运行的动态信息， 通常包含：

PSW也是计算机系统的寄存器

指令与处理机

机器指令

机器指令是计算机系统执行的基本命令， 是中央处理器执行的基本单位

指令由一个或多个字节组成， 包括操作码字段、 一个或多个操作数地址字段、 以及一些表征机器状态的状态字以及特征码

指令完成各种算术逻辑运算、 数据传输、 控制流跳转

指令执行过程

CPU根据PC（程序计数器）取出指令， 放入IR， 并对指令译码，然后发出各种控制命令， 执行微操作系列，从而完成一条指令的执行

一种指令执行步骤如下

  1. 取指： 根据PC从存储器或高速缓冲存储器中取指令到IR
  2. 解码： 解译IR中的指令来决定其执行行为
  3. 执行： 连接到CPU部件， 执行运算， 产生结果并写回， 同时在CC里设置运算结论标志； 跳转指令操作PC， 其他指令递增PC值
指令执行周期与指令流水线
image-20200429122203865
特权指令与非特权指令

用户程序并非能够使用全部机器指令， 那些与计算机核心资源相关的特殊指令会被保护，核心资源相关的指令只能被操作系统程序使用

如： 启动I/O指令、 置PC指令、 等等

假设A程序要输出123，同时B程序要输出456，如果将I/O控制交给计算机很有可能输出成142536，不符合要求

所以指令被分为特权指令和非特权指令

处理器模式

计算机通过设置处理器模式实现特权指令管理

计算机一般设置0、 1、 2、 3等四种运行模式，建议分别对应： 0操作系统内核、 1系统调用、2共享库程序、 3用户程序等保护级别

一般来说， 现代操作系统只使用0和3两种模式，对应于内核模式和用户模式

处理器模式的切换

包括“用户模式→内核模式”和“内核模式→用户模式” 的转换

中断、 异常或系统异常等事件导致用户程序向OS内核切换， 触发： 用户模式→内核模式

OS内核处理完成后， 调用中断返回指令（如Intel的iret） 触发： 内核模式→用户模式

中断

概念

中断是指程序执行过程中， 遇到急需处理的事件时， 暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序， 待处理完成后再返回原程序被中断处或调度其他程序执行的过程

操作系统是“中断驱动” 的； 换言之， 中断是激活操作系统的唯一方式

比如用户程序在运行的时候只有通过中断才能够切换

中断有广义和狭义之分， 上述中断是指广义的中断

中断、 异常与系统异常

中断源

处理器硬件故障中断事件

由处理器、 内存储器、 总线等硬件故障引起

处理原则为： 保护现场， 停止设备， 停止CPU， 向操作员报告， 等待人工干预

程序性中断事件

处理器执行机器指令引起

自愿性中断事件

处理器执行陷入指令请求OS服务引起； 在操作系统中， 它一般又被称作系统调用

I/O中断事件

来源于外围设备报告I/O状态的中断事件

外部中断事件

由外围设备发出的信号引起的中断事件

中断系统

中断系统是计算机系统中响应和处理中断的系统， 包括硬件子系统和软件子系统两部分

中断响应由硬件子系统完成

中断处理由软件子系统完成

中断响应处理与指令执行周期

在指令执行周期最后增加一个微操作， 以响应中断

image-20200429142728623
中断装置

计算机系统中发现并响应中断/异常的硬件装置称为中断装置。由于中断源的多样性， 硬件实现的中断装置有多种， 分别处理不同类型的中断这些中断装置因计算机而异， 通常有：

中断控制器

CPU中的一个控制部件， 包括中断控制逻辑线路和中断寄存器

  1. 外部设备向其发出中断请求IRQ， 在中断寄存器中设置已发生的中断
  2. 指令处理结束前， 会检查中断寄存器， 若有不被屏蔽的中断产生， 则改变处理器内操作的顺序， 引出操作系统中的中断处理程序

这个过程是异步的，先设置寄存器，在这条指令结束之后查看寄存器，才能进行中断

陷阱与系统陷阱

陷阱与系统陷阱： 指令的逻辑和实现线路的一部分

这个过程是同步的，是在执行指令的过程中发生的中断

中断响应过程

  1. 发现中断源， 提出中断请求

    1. 发现中断寄存器中记录的中断

    2. 决定这些中断是否应该屏蔽

    3. 当有多个要响应的中断源时， 根据规定的优先级选择一个

  2. 中断当前程序的执行

    保存当前程序的PSW/PC到核心栈

  3. 转向操作系统的中断处理程序

中断处理程序

操作系统处理中断事件的控制程序, 主要任务是处理中断事 件和恢复正常操作

中断处理过程
中断系统处理流程
多中断的响应与处理
中断屏蔽

当计算机检测到中断时, 中断装置通过中断屏蔽位决定是否响应已发生的中断，有选择的响应中断

中断优先级

当计算机同时检测到多个中断时, 中断装置响应中断的顺序，有优先度的响应中断

一种可能的处理次序：

  1. 处理机硬件故障中断事件
  2. 自愿性中断事件
  3. 程序性中断事件
  4. 时钟中断等外部中断事件
  5. 输入输出中断事件
  6. 重启动和关机中断事件

不同类型的操作系统有不同的中断优先级

中断的嵌套处理

当计算机响应中断后， 在中断处理过程中，可以再响应其他中断

操作系统是性能攸关程序系统， 且中断响应处理有硬件要求， 考虑系统效率和实现代价问题， 中断的嵌套处理应限制在一定层数内，如3层

中断的嵌套处理了改变中断处理次序， 导致先响应的有可能后处理

image-20200429150256898 image-20200429150317597

进程

进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，也是操作系统进行资源分配和调度的一个独立单位

一个进程包括五个实体部分

  1. (OS管理运行程序的)数据结构P
  2. (运行程序的)内存代码C
  3. (运行程序的)内存数据D
  4. (运行程序的)通用寄存器信息R
  5. (OS控制程序执行的)程序状态字信息PSW

不同程序

相同程序

进程状态

image-20200429152605988

  1. 运行态→ 等待态：等待资源、 I/O、 信号

  2. 等待态→ 就绪态：资源满足、 I/O结束、信号完成

  3. 运行态→ 就绪态：运行时间片到、有更高优先权进程

  4. 就绪态→ 运行态：处理器空闲时选择更高优先权进程抢占

进程挂起

OS无法预期进程的数目与资源需求， 计算机系统在运行过程中可能出现资源不足的情况

运行资源不足表现为性能低和死锁两种情况

解决办法： 剥夺某些进程的内存及其他资源，调入OS管理的对换区， 不参加进程调度， 待适当时候再调入内存、恢复资源、参与运行，这就是进程挂起

挂起态与等待态有着本质区别， 后者占有已申请到的资源处于等待， 前者没有任何资源

进程挂起的选择与恢复
image-20200429153137896

数据描述

进程控制块

进程控制块PCB是OS用于记录和刻画进程状态及环境信息的数据结构

分为标识信息、现场信息、控制信息

image-20200429153548426
标识信息

用于存放唯一标识该进程的信息

现场信息

用于存放该进程运行时的处理器现场信息

控制信息

用于存放与管理、 调度进程相关的信息

  1. 调度相关信息： 状态、 等待事件/原因、 优先级
  2. 进程组成信息： 代码/数据地址、 外存映像地址
  3. 队列指引元： 进程队列指针、 父子兄弟进程指针
  4. 通信相关信息： 消息队列、 信号量、 锁
  5. 进程特权信息： 如内存访问权限、 处理器特权
  6. 处理器使用信息： 占用的处理器、 时间片、 处理器使用时间/已执行总时间、 记账信息
  7. 资源清单信息： 如正占有的资源、 已使用的资源
进程映像

某一时刻进程的内容及其执行状态集合，是内存级的物理实体， 又称为进程的内存映像，包含：

image-20200429154610977
进程上下文

进程的执行需要环境支持， 包括CPU现场和Cache中的执行信息，OS中的进程物理实体和支持进程运行的环境合成进程上下文， 包括以下：

进程上下文刻画了进程的执行情况

进程的管理

关键的进程管理软件包括：

队列管理模块
进程实现的队列模型

操作系统建立多个进程队列， 包括就绪队列和等待队列，按需组织为先进先出队列与优先队列。队列中的进程可以通过PCB中的队列指引元采用单/双指引元或索引连接。进程与资源调度围绕进程队列展开。

控制与管理
原语与进程控制原语

进程控制过程中涉及对OS核心数据结构(进程表/PCB池/队列/资源表)的修改，为防止与时间有关的错误， 应使用原语

原语是由若干条指令构成的完成某种特定功能的程序，执行上具有不可分割性。原语的执行可以通过关中断实现

进程控制使用的原语称为进程控制原语，另一类常用原语是进程通信原语

进程切换

进程切换指从正在运行的进程中收回处理器，让待运行进程来占有处理器运行 ，进程切换实质上就是被中断运行进程与待运行进程的上下文切换， 处理过程是：

  1. 保存被中断进程的上下文
  2. 转向进程调度
  3. 恢复待运行进程的上下文

进程的切换必须在操作系统内核模式下完成，也就必须需要模式切换

模式切换

模式切换又称处理器状态切换， 包括：

  1. 用户模式到内核模式
    由中断/异常/系统调用中断用户进程执行而触发

    1. 处理器模式转为内核模式
    2. 保存当前进程的PC/PSW值到核心栈
    3. 转向中断/异常/系统调用处理程序

  2. 内核模式到用户模式
    OS执行中断返回指令将控制权交还用户进程而触发

    1. 从待运行进程核心栈中弹出PSW/PC值
    2. 处理器模式转为用户模式
进程切换工作过程
  1. (中断/异常等触发)正向模式切换并压入PSW/PC
  2. 保存被中断进程的现场信息
  3. 处理具体中断/异常
  4. 把被中断进程的系统堆栈指针SP值保存到PCB
  5. 调整被中断进程的PCB信息， 如进程状态
  6. 把被中断进程的PCB加入相关队列
  7. 选择下一个占用CPU运行的进程
  8. 修改被选中进程的PCB信息， 如进程状态
  9. 设置被选中进程的地址空间， 恢复存储管理信息
  10. 恢复被选中进程的SP值到处理器寄存器SP
  11. 恢复被选中进程的现场信息进入处理器
  12. (中断返回指令触发)逆向模式转换并弹出PSW/PC
进程切换的发生时机

进程切换一定发生在中断/异常/系统调用，处理过程中， 常见的情况是：

一些中断/异常不会引起进程状态转换， 不会引起进程切换， 只是在处理完成后把控制权交回给被中断进程， 处理流程是：

  1. (中断/异常触发)正向模式切换压入PSW/PC
  2. 保存被中断进程的现场信息
  3. 处理中断/异常
  4. 恢复被中断进程的现场信息
  5. (中断返回指令触发)逆向模式转换弹出PSW/PC

多线程技术

传统进程是单线程结构进程
image-20200429163314902

单线程结构进程在并发程序设计上存在的问题 ：

操作系统会根据安全角度对进程之间的通信做一些限制，且进程之间的调度需要耗费的成本更高

多线程结构进程
image-20200429163707535

线程是进程的一条执行路径， 是调度的基本单位， 同一个进程中的所有线程共享进程获得的主存空间和资源

线程状态有运行、 就绪和睡眠， 无挂起

挂起与是否占有资源有关，而线程使用的是进程的资源

OS感知线程环境下：

OS不感知线程环境：

优点
多线程的实现
内核级线程KLT, Kernel-Level Threads

线程管理的所有工作由OS内核来做

image-20200429165321052

特点

用户级线程ULT, User-Level Threads

用户空间运行的线程库，提供多线程应用程序的开发和运行支撑环境。

线程管理的所有工作都由应用程序完成，内核没有意识到线程的存在。

image-20200429165534020

特点

  1. 所有线程管理数据结构均在进程的用户空间中， 线程切换不需要内核模式， 能节省模式切换开销和内核的宝贵资源
  2. 允许进程按应用特定需要选择调度算法， 甚至根据应用需求裁剪调度算法
  3. 能运行在任何OS上， 内核在支持ULT方面不需要做任何工作
  4. 不能利用多处理器的优点， OS调度进程，仅有一个ULT能执行
  5. 一个ULT的阻塞， 将引起整个进程的阻塞

Jacketing技术

把阻塞式系统调用改造成非阻塞式的,当线程陷入系统调用时，执行jacketing程序。由jacketing 程序来检查资源使用情况，以决定是否执行进程切换或传递控制权给另一个线程。

image-20200429165819309
混合式多线程

单应用的多个ULT可以映射成一些KLT， 通过调整KLT数目，可以达到较好的并行效果

image-20200429170733555

线程混合式策略下的线程状态

image-20200429170933586 image-20200429171000147

处理器调度

调度的层次

高级调度

又称长程调度， 作业调度决定能否加入到执行的进程池中

分时OS中， 高级调度决定：

中级调度

又称平衡负载调度，决定主存中的可用进程集合

低级调度

又称短程调度， 进程调度决定哪个可用进程占用处理器执行

主要功能

image-20200429171403339 image-20200429171456555

调度算法

选择处理器调度算法的原则
优先数调度算法

根据分配给进程的优先数决定运行进程

分类
与进入系统时间相关的优先数
时间片轮转调度算法
分级调度算法

又称多队列策略， 反馈循环队列

基本思想

例子：

image-20200429174252057
彩票调度算法
基本思想

为进程发放针对系统各种资源（如CPU时间） 的彩票； 当调度程序需要做出决策时， 随机选择一张彩票，持有该彩票的进程将获得系统资源

合作进程之间可以进行彩票交换

存储管理

主要模式

逻辑地址

又称相对地址， 即用户编程所使用的地址空间

逻辑地址从0开始编号， 有两种形式：

段式程序设计

物理地址

又称绝对地址， 即程序执行所使用的地址空间，处理器执行指令时按照物理地址进行

主存储器的复用
按照分区复用
按照页架复用

存储管理的基本模式

将逻辑地址和物理地址相对于，就会有2*2=4个存储管理的基本模式

image-20200429180525340

功能

地址转换

又称重定位， 即把逻辑地址转换成绝对地址

静态重定位

在程序装入内存时进行地址转换

由装入程序执行， 早期小型OS使用

动态重地位

在CPU执行程序时进行地址转换

从效率出发， 依赖硬件地址转换机构

分配与去配
分配

进程装入主存时， 存储管理软件进行具体的主存分配操作， 并设置一个表格记录主存空间的分配情况

去配

当某个进程撤离或主动归还主存资源时， 存储管理软件要收回它所占用的全部或者部分存储空间， 调整主存分配表信息

空间共享

多个进程共享主存储器资源： 多道程序设计技术使若干个程序同时进入主存储器， 各自占用一定数量的存储空间， 共同使用一个主存储器

多个进程共享主存储器的某些区域： 若干个协作进程有共同的主存程序块或者主存数据块

存储保护

为避免主存中的多个进程相互干扰， 必须对主存中的程序和数据进行保护

这一功能需要软硬件协同完成，CPU检查是否允许访问， 不允许则产生地址保护异常， 由OS进行相应处理。

空间的扩充

存储扩充： 把磁盘作为主存扩充， 只把部分进程或进程的部分内容装入内存

  1. 对换技术： 把部分不运行的进程调出
  2. 虚拟技术： 只调入进程的部分内容

这一工作需要软硬件协作完成

  1. 对换进程决定对换， 硬件机构调入

  2. CPU处理到不在主存的地址， 发出虚拟地址异常， OS将其调入， 重执指令

虚拟存储器

提出

因此可以考虑部分调入进程内容

基本思想

实现思路

需要建立与自动管理两个地址空间

对于用户， 计算机系统具有一个容量大得多的主存空间， 即虚拟存储器。虚拟存储器是一种地址空间扩展技术，通常意义上对用户编程是透明的

虚拟存储器示意

存储管理的硬件支撑

存储管理涉及的存储对象

高速缓存存储器（Cache）
高速缓存存储器的构成
高速缓存存储器的组织
image-20200429183335305

L1 Cache： 分为数据缓存和指令缓存；内置； 其成本最高， 对CPU的性能影响最大； 通常在32KB-256KB之间

L2 Cache： 分内置和外置两种， 后者性能低一些； 通常在512KB-8MB之间

L3 Cache： 多为外置， 在游戏和服务器领域有效； 但对很多应用来说， 总线改善比设置L3更加有利于提升系统性能

image-20200429183705217

单连续分区存储管理

每个进程占用一个物理上完全连续的存储空间(区域)

单用户连续存储管理

固定分区存储管理

image-20200429201511135
主存分配

主存分配表

image-20200429201601892
地址转换
image-20200429202007910

可变分区存储管理

按进程的内存需求来动态划分分区

创建一个进程时， 根据进程所需主存量查看主存中是否有足够的空闲空间

由于分区大小按照进程实际需要量来确定， 因此分区个数是随机变化的

image-20200429202927852

已分配区表与未分配区表， 采用链表

image-20200429203018157
内存分配
动态重定位
image-20200429203805356
内存零头
移动技术（程序浮动技术）

移动分区以解决内存外零头，需要动态重定位支撑

image-20200429203515555 image-20200429203641069

页式存储管理

页表

页式存储管理中的地址

逻辑地址

页式存储管理的逻辑地址由两部分组成，页号和单元号， 逻辑地址形式：

image-20200429205234424
物理地址

页式存储管理的物理地址也有两部分组成，页架号和单元号， 物理地址形式：

image-20200429205245188
地址转换
image-20200429205348154
代价

可变分区存储的基准地址是存储在寄存器中的，速度很快，而页表放在主存，每次地址转换必须访问两次主存

  1. 按页号读出页表中的相应页架号
  2. 按计算出来的绝对地址进行读写

存在问题： 降低了存取速度

解决办法： 利用Cache存放部分页表

快表

为提高地址转换速度， 设置一个专用的高速存储器， 用来存放页表的一部分，存放在高速存储器中的页表部分就是快表

快表表项： 页号， 页架号

这种高速存储器是联想存储器， 即按照内容寻址， 而非按照地址访问

因为要找的是页号对应的页架号，知道页号，不知道地址，所以是内容寻址

eg:假定主存访问时间为200毫微秒， 快表访问时间为40毫微秒， 查快表的命中率是90%

平均地址转换代价为 (200+40)*90\%+(200+200)*10\% =256毫微秒

比两次访问主存的时间（400毫微秒）下降了36%

地址转换流程

按逻辑地址中的页号查快表

多道程序环境下的进程表

进程表中登记了每个进程的页表。进程占有处理器运行时， 其页表起始地址和长度送入页表控制寄存器

用户作业名 页表始址 页表长度
AB 0010 4
CD 0014 3
EF 0017 7
… … …
多道程序环境下的地址转换
image-20200429213739251

内存分配/去配

可用一张位示图来记录主存分配情况，建立进程页表维护主存逻辑完整性

对于每个页使用1位去记录该页是否被占用

image-20200429205652984

页的共享

页式存储管理能够实现多个进程共享程序和数据

页式虚拟存储管理

把进程全部页面装入虚拟存储器， 执行时先把部分页面装入实际内存， 然后， 根据执行行为， 动态调入不在主存的页， 同时进行必要的页面调出

首次只把进程第一页信息装入主存， 称为请求页式存储管理

页式虚拟存储管理的页表

需要扩充页表项：

image-20200429214322339
页式虚拟存储管理的实现

CPU处理地址

OS处理缺页中断

image-20200429214740079 image-20200429214814276
页面调度

当主存空间已满而又需要装入新页时，页式虚拟存储管理必须按照一定的算法把已在主存的一些页调出去。选择淘汰页的工作称为页面调度。选择淘汰页的算法称为页面调度算法。

页面调度算法设计不当， 会出现（刚被淘汰的页面立即又要调入， 并如此反复），这种现象称为抖动或颠簸。

缺页中断率

假定进程P共n页， 系统分配页架数m个。P运行中成功访问次数为S， 不成功访问次数为F， 总访问次数A=S+F。缺页中断率定义为： f=F/A

影响缺页中断率的因素

eg：程序将数组置为“0”， 假定仅分得一个主存页架， 页面尺寸为128个字， 数组元素按行存放， 开始时第一页在主存

程序1：

int A[128][128];
for(int j=0;j<128;j++)
  for(int i=0;i<128;i++)
      A[i][j]=0;

内循环按照行进行遍历，导致每执行一次赋值就要产生一次缺页中断， 共产生(128×128－ 1)次缺页中断

程序2：

int A[128][128];
for(int i=0;i<128;i++)
  for(int j=0;j<128;j++)
      A[i][j]=0;

内循环按照列进行遍历，共产生(128－ 1)次缺页中断

OPT页面调度算法

理想的调度算法是： 当要调入新页面时， 首先淘汰以后不再访问的页， 然后选择距现在最长时间后再访问的页。该算法由Belady提出， 称Belady算法， 又称最佳算法（OPT）

OPT只可模拟， 不可实现

先进先出FIFO页面调度算法

总是淘汰最先调入主存的那一页， 或者说主存驻留时间最长的那一页(常驻的除外)

模拟的是程序执行的顺序性， 有一定合理性

最久未使用LRU页面调度算法

淘汰最近一段时间较久未被访问的那一页， 即那些刚被使用过的页面， 可能马上还要被使用到

模拟了程序执行的局部属性， 既考虑了循环性又兼顾了顺序性

严格实现的代价大(需要维持特殊队列)

LRU算法的模拟实现
每页建一个引用标志， 供硬件使用
设置一个时间间隔中断： 中断时页引用标志置0
地址转换时， 页引用标志置1
淘汰页面时， 从页引用标志为0的页中间随机选择
时间间隔多长是个难点

最不常用LFU页面调度算法

淘汰最近一段时间内访问次数较少的页面， 对OPT的模拟性比LRU更好

基于时间间隔中断， 并给每一页设置一个计数器，时间间隔中断发生后， 所有计数器清0每访问页1次就给计数器加1选择计数值最小的页面淘汰

时钟CLOCK页面调度算法

工作流程

反置页表

内存管理单元MMU：CPU管理虚拟/物理存储器的控制线路， 把虚拟地址映射为物理地址， 并提供存储保护， 必要时确定淘汰页面，是为页式存储管理设置的专门硬件机构。

反置页表IPT：MMU用的数据结构

为什么需要反置页表

在分页系统中，每个进程都有一个页表。现代系统中可能存在大量进程，每个进程都允许很大的逻辑地址空间，因而进程可能拥有一个很大的页表，这些页表会占用大量的内存空间。而通过物理页向逻辑页映射就可以节省很大的存储空间。

反置页表如何实现

内存中的每一个物理页设置一个表项，表项中存放进程号和页号，最后系统只维护一张反置页表。

image-20200430104624992
反置页表的页表项

进程号 页号 标志位 链指针

进程号：使用该物理页的进程号

页号： 该物理页对应的虚拟地址页号

标志位： 有效、 引用、 修改、 保护和锁定等标志信息

链指针： 哈希链（哈希冲突的时候，通过链表串在一起）

反置页表的哈希表

如果是使用页表就可以直接从该进程的页表查询到页架号，而现在采用的是反置页表，在页表到页架号的映射上需要采用哈希查询，所以要维系一个哈希表。

哈希函数输入：进程号和页号

哈希函数输出：反置页表项的指针

地址转换过程
  1. 通过哈希表查询到反置页表项的指针
  2. 比对指向的页表项的进程号和页号
    • 相同，则该页就是所需要的物理页
    • 不相同，沿着链指针继续
      • 如果有相同的，该页就是所需要的物理页
      • 没有相同的，说明页面不在内存中，而在虚拟内存中，需要页面置换
image-20200430105811444

段式存储管理

段式存储是面向开发人员的，开发人员根据自己的需要对程序进行划分，程序的不同的部分采用不同的段进行地址管理，而对内存的物理管理是基于可变分区存储管理的，只不过可变分区存储管理是一个进程一个段，而段式存储管理是一个进程多个段。

它与页式管理也不同，也是管理对于开发人员是透明的，系统自动对软件的内存按照也进行切割。而且页式管理每个页是大小相等，均匀分布的。而段式管理段的大小和位置是不确定的。

段式程序设计

每个程序可由若干段组成， 每一段都可以从“0”开始编址， 段内的地址是连续的

分段存储器的逻辑地址由两部分组成 段号单元号

image-20200430110727777

段式存储管理的基本思想

段式存储管理基于可变分区存储管理实现， 一个进程要占用多个分区

硬件需要增加一组用户可见的段地址寄存器（代码段、 数据段、 堆栈段， 附加段） ， 供地址转换使用

存储管理需要增加设置一个段表， 每个段占用一个段表项， 包括： 段始址、 段限长， 以及存储保护、 可移动、 可扩充等标志位

image-20200430111438522
段的共享

通过不同进程段表中的项指向同一个段基址来实现

对共享段的信息必须进行保护， 如规定只能读出不能写入， 不满足保护条件则产生保护中断

image-20200430112527632

段页式存储管理

段式存储管理可以基于页式存储管理实现

对于每一段进行页式管理

对于每一段进行页式管理

段页式存储管理的地址转换

image-20200430113258327 image-20200430113318715
上一篇 下一篇

猜你喜欢

热点阅读