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

操作系统原理

基本概念

计算机硬件系统

组成

image-20200429093334026

中央处理器

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

• 运算逻辑部件： 一个或多个运算器
• 寄存器部件： 包括通用寄存器、 控制与状态寄存器， 以及高速缓冲存储器（Cache）
• 控制部件： 实现各部件间联系的数据、 控制及状态的内部总线； 负责对指令译码、发出为完成每条指令所要执行操作的控制信号、 实现数据传输等功能的部件

处理器与寄存器

image-20200429093613084

主存储器

DRAM

外围设备

设备类型

• 输入设备

  键盘 鼠标

• 输出设备

  显示器

• 存储设备

  1. 硬盘 如固态硬盘 机械硬盘 U盘等

  2. 光驱

     ····

• 网络通信设备

  网卡等

设备控制方式

• 轮询方式： CPU忙式控制+数据交换
• 中断方式： CPU启动/中断+数据交换
• DMA方式： CPU启动/中断， DMA数据交换

总线

简介

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

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

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

总线的类型

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

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

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

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

系统总线

冯诺依曼结构

存储程序计算机

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

• 以运算单元为中心， 控制流由指令流产生
• 采用存储程序原理， 面向主存组织数据流
• 主存是按地址访问、 线性编址的空间
• 指令由操作码和地址码组成
• 数据以二进制编码

结构

image-20200429093531395

存储器的组织层次

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

image-20200429093738493

计算机软件系统

软件开发的不同层次

• 计算机硬件系统： 机器语言
• 操作系统之资源管理： 机器语言+广义指令（扩充了硬件资源管理）
• 操作系统之文件系统： 机器语言+系统调用（扩充了信息资源管理）
• 数据库管理系统： +数据库语言（扩充了功能更强的信息资源管理）
• 语言处理程序： 面向问题的语言

计算机程序的执行过程

image-20200429094558283

操作系统

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

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

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

• 从用户角度看， OS管理计算机系统的各种资源， 扩充硬件的功能， 控制程序的执行
• 从人机交互看， OS是用户与机器的接口，提供良好的人机界面， 方便用户使用计算机，在整个计算机系统中具有承上启下的地位
• 从系统结构看， OS是一个大型软件系统，其功能复杂， 体系庞大， 采用层次式、 模块化的程序结构

操作系统的组成

• 进程调度子系统
• 进程通信子系统
• 内存管理子系统
• 设备管理子系统
• 文件管理子系统
• 网络通信子系统
• 作业控制子系统

类型

操作控制方式

• 多道批处理操作系统， 脱机控制方式
• 分时操作系统， 交互式控制方式
• 实时操作系统

应用领域

• 服务器操作系统、 并行操作系统
• 网络操作系统、 分布式操作系统
• 个人机操作系统、 手机操作系统
• 嵌入式操作系统、 传感器操作系统

资源管理

计算机资源包含

• 硬件资源
  处理器、 内存、 外设
• 信息资源
  数据、 程序

屏蔽资源使用的底层细节

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

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

资源共享方式

• 独占使用方式
• 并发使用方式

资源分配策略

• 静态分配方式
• 动态分配方式
• 资源抢占方式

系统控制

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

image-20200429110425511

image-20200429110444095

多道程序系统的实现

• 为进入内存执行的程序建立管理实体： 进程

• OS应能管理与控制进程程序的执行

• OS协调管理各类资源在进程间的使用

  • 处理器的管理和调度
  • 主存储器的管理和调度
  • 其他资源的管理和调度

• 如何使用资源： 调用操作系统提供的服务例程(如何陷入操作系统)

• 如何复用CPU： 调度程序(在CPU空闲时让其他程序运行)

• 如何使CPU与I/O设备充分并行： 设备控制器与通道(专用的I/O处理器)

• 如何让正在运行的程序让出CPU： 中断(中断正在执行的程序， 引入OS处理)

控制方式

脱机作业控制方式

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：用于访问内存数据

用户程序可见寄存器

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

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

• 数据寄存器： 又称通用寄存器
• 地址寄存器： 索引、 栈指针、 段地址等寄存器

控制与状态寄存器

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

• 程序计数器PC： 存储将取指令的地址
• 指令寄存器IR： 存储最近使用的指令
• 条件码CC： CPU为指令操作结果设置的位， 标志正/负/零/溢出等结果
• 标志位： 中断位、 中断允许位、 中断屏蔽位、 处理器模式位、 内存保护位、 …， 等

程序状态字PSW

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上现行程序的运行，转去执行相应的事件处理程序， 待处理完成后再返回原程序被中断处或调度其他程序执行的过程

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

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

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

中断、 异常与系统异常

• 狭义的中断指来源于处理器之外的中断事件，即与当前运行指令无关的中断事件， 如I/O中
  断、 时钟中断、 外部信号中断等

• 异常指当前运行指令引起的中断事件， 如地址异常、 算术异常、 处理器硬件故障等

• 系统异常指执行陷入指令而触发系统调用引起的中断事件， 如请求设备、 请求I/O、 创建进程等

  系统异常与硬件无关

中断源

处理器硬件故障中断事件

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

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

程序性中断事件

处理器执行机器指令引起

• 除数为零、 操作数溢出等算术异常： 简单处理， 报告用户； 也可以由用户编写中断续元程序处理
• 非法指令、 用户态使用特权指令、 地址越界、 非法存取等指令异常： 终止进程
• 终止进程指令： 终止进程
• 虚拟地址异常： 调整内存后重新执行指令

自愿性中断事件

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

• 请求分配外设、 请求I/O、 等等
• 处理流程是： 陷入OS， 保护现场， 根据功能号查入口地址， 跳转具体处理程序

I/O中断事件

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

• I/O完成： 调整进程状态， 释放等待进程
• I/O出错： 等待人工干预
• I/O异常： 等待人工干预

外部中断事件

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

• 时钟中断、 间隔时钟中断： 记时与时间片处理
• 设备报到与结束中断： 调整设备表
• 键盘/鼠标信号中断： 根据信号作出相应反应
• 关机/重启动中断： 写回文件， 停止设备与CPU

中断系统

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

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

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

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

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

image-20200429142728623

中断装置

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

• 处理器外的中断： 由中断控制器发现和响应
• 处理器内的异常： 由指令的控制逻辑和实现线路发现和响应， 相应机制称为陷阱
• 请求OS服务的系统异常： 处理器执行陷入指令时直接触发， 相应机制称为系统陷阱

中断控制器

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

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

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

陷阱与系统陷阱

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

• 执行指令出现异常后， 会根据异常情况转向操作系统的异常处理程序
• 出现虚拟地址异常后， 需要重新执行指令，往往越过陷阱独立设置页面异常处理程序
• 执行陷入指令后， 越过陷阱处理， 触发系统陷阱， 激活系统调用处理程序

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

中断响应过程

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

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

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

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

2. 中断当前程序的执行

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

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

中断处理程序

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

中断处理过程

• 保护未被硬件保护的处理器状态

• 通过分析被中断进程的PSW中断码字段，识别中断源

• 分别处理发生的中断事件

• 恢复正常操作

  情况一： 对于某些中断， 在处理完毕后， 直接返回刚刚被中断的进程
  情况二： 对于其他一些中断， 需要中断当前进程的运行， 调整进程队列， 启动进程调度， 选择下一个执行的进程并恢复其执行

中断系统处理流程

多中断的响应与处理

中断屏蔽

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

中断优先级

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

一种可能的处理次序：

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

标识信息

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

• 系统分配的标识号
• 系统分配的进程组标识号
• 用户定义的进程名
• 用户定义的进程组名

现场信息

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

• 用户可见寄存器内容： 数据寄存器、 地址寄存器
• 控制与状态寄存器内容： PC、 IR、 PSW
• 栈指针内容： 核心栈与用户栈指针

控制信息

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

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

进程映像

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

• 进程控制块: 保存进程的标识信息、 状态信息和控制信息
• 进程程序块: 进程执行的程序空间
• 进程数据块: 进程处理的数据空间， 包括数据、 处理函数的用户栈和可修改的程序
• 核心栈: 进程在内核模式下运行时使用的堆栈， 中断或系统过程使用

image-20200429154610977

进程上下文

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

• 用户级上下文： 用户程序块/用户数据区/用户栈/用户共享内存
• 寄存器上下文： PSW/栈指针/通用寄存器
• 系统级上下文： PCB/内存区表/核心栈

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

进程的管理

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

• 系统调用/中断/异常处理程序
• 队列管理模块
• 进程控制程序
• 进程调度程序（独立进程居多）
• 进程通信程序（多个程序包）
• 终端登录与作业控制程序、 性能监控程序、 审计程序等外围程序

队列管理模块

进程实现的队列模型

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

控制与管理

• 进程创建： 进程表加一项， 申请PCB并初始化，生成标识， 建立映像， 分配资源， 移入就绪队列
• 进程撤销： 从队列中移除， 归还资源， 撤销标识，回收PCB， 移除进程表项
• 进程阻塞： 保存现场信息， 修改PCB， 移入等待队列， 调度其他进程执行
• 进程唤醒： 等待队列中移出， 修改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

进程切换的发生时机

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

• 阻塞式系统调用、 虚拟地址异常导致被中断进程进入等待态
• 时间片中断、 I/O中断后发现更高优先级进程，导致被中断进程转入就绪态
• 终止用系统调用、 不能继续执行的异常，导致被中断进程进入终止态

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

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

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

• 活跃态ULT代表绑定KLT的三态
• 活跃态ULT运行时可激活用户调度
• 非阻塞系统调用可使用Jacketing启动用户调度， 调整活跃态ULT

image-20200429170933586

image-20200429171000147

处理器调度

调度的层次

高级调度

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

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

• 是否接受一个终端用户的连接
• 命令能否被系统接纳并构成进程
• 新建态进程是否加入就绪进程队列

中级调度

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

• 引进中级调度是为了提高内存利用率和作业吞吐量
• 中级调度决定那些进程被允许驻留在主存中参与竞争处理器及其他资源， 起到短期调整系统负荷的作用
• 中级调度把一些进程换出主存， 从而使之进入“挂起” 状态， 不参与进程调度，以平顺系统的负载

低级调度

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

• 进程调度程序： 又称分派程序， 操作系统中实现处理器调度的程序， 是操作系统的最核心部分
• 处理器调度策略的优劣直接影响到整个系统的性能

主要功能

• 记住进程或内核级线程的状态
• 决定某个进程或内核级线程什么时候获得处理器， 以及占用多长时间
• 把处理器分配给进程或内核级线程
• 收回处理器

image-20200429171403339

image-20200429171456555

调度算法

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

• 资源利用率： 使得CPU或其他资源的使用率尽可能高且能够并行工作
• 响应时间： 使交互式用户的响应时间尽可能小， 或尽快处理实时任务
• 周转时间： 提交给系统开始到执行完成获得结果为止的这段时间间隔称周转时间， 应该使周转时间或平均周转时间尽可能短
• 吞吐量： 单位时间处理的进程数尽可能多
• 公平性： 确保每个用户每个进程获得合理的CPU份额或其他资源份额

优先数调度算法

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

分类

• 抢占式优先数调度算法
• 非抢占式优先数调度算法

与进入系统时间相关的优先数

• 计算时间短(作业/进程)优先

• 剩余计算时间短进程优先

• 响应比高者(作业/进程)优先
  

• 先来先服务： 先进队先被选择

• 多用于高级调度； 低级调度中， 以计算为主的进程过于优越

时间片轮转调度算法

• 根据各个进程进入就绪队列的时间先后轮流占有CPU一个时间片
• 时间片中断
• 时间片的确定： 选择长短合适的时间片, 过长则退化为先来先服务算法, 过短则调度开销大
• 不同进程时间片长度可调

分级调度算法

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

基本思想

• 建立多个不同优先级的就绪进程队列
• 多个就绪进程队列间按照优先数调度
• 高优先级就绪进程， 分配的时间片短
• 单个就绪进程队列中进程的优先数和时间片相同

例子：

image-20200429174252057

彩票调度算法

基本思想

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

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

存储管理

主要模式

逻辑地址

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

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

• 一维逻辑地址（地址）
• 二维逻辑地址（段号:段内地址）

段式程序设计

• 把一个程序设计成多个段（代码段、数据段、堆栈段、等等）
• 用户可以自己应用段覆盖技术扩充内存空间使用量

物理地址

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

主存储器的复用

按照分区复用

• 主存划分为多个固定/可变尺寸的分区
• 一个程序/程序段占用一个分区

按照页架复用

• 主存划分成多个固定大小的页架

• 一个程序/程序段占用多个页架

存储管理的基本模式

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

• 单连续存储管理： 一维逻辑地址空间的程序占用一个主存固定分区或可变分区
• 段式存储管理： 段式二维逻辑地址空间的程序占用多个主存可变分区
• 页式存储管理： 一维逻辑地址空间的程序占用多个主存页架区
• 段页式存储管理： 段式二维逻辑地址空间的程序占用多个主存页架区

image-20200429180525340

功能

地址转换

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

静态重定位

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

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

动态重地位

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

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

分配与去配

分配

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

去配

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

空间共享

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

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

存储保护

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

• 私有主存区中的信息： 可读可写
• 公共区中的共享信息： 根据授权
• 非本进程信息： 不可读写

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

空间的扩充

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

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

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

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

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

虚拟存储器

提出

• 主存容量限制带来诸多不便
  • 用户编写程序必须考虑主存容量限制
  • 多道程序设计的道数受到限制
• 用户编程行为分析
  • 全面考虑各种情况， 执行时有互斥性
  • 顺序性和循环性等空间局部性行为
  • 某一阶段执行的时间局部性行为

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

基本思想

• 存储管理把进程全部信息放在辅存中， 执行时先将其中一部分装入主存， 以后根据执行行为随用随调入
• 如主存中没有足够的空闲空间， 存储管理需要根据执行行为把主存中暂时不用的信息调出到辅存上去

实现思路

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

• (辅存)虚拟地址空间： 容纳进程装入
• (主存)实际地址空间： 承载进程执行

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

虚拟存储器示意

存储管理的硬件支撑

存储管理涉及的存储对象

• 为获得更好的处理性能， 部分主存程序与数据（特别是关键性能数据） 被调入Cache， 存储管理需要对其进行管理， 甚至包括对联想存储器的管理
• 为获得更大的虚拟地址空间， 存储管理需要对存放在硬盘、 固态硬盘、 甚至网络硬盘上的虚拟存储器文件进行管理

高速缓存存储器（Cache）

• Cache是介于CPU和主存储器间的高速小容量存储器， 由静态存储芯片SRAM组成， 容量较小但比主存DRAM技术更加昂贵而快速， 接近于CPU的速度
• CPU往往需要重复读取同样的数据块，Cache的引入与缓存容量的增大， 可以大幅提升CPU内部读取数据的命中率，从而提高系统性能

高速缓存存储器的构成

• 高速缓冲存储器通常由高速存储器、 联想存储器、 地址转换部件、 替换逻辑等组成
• 联想存储器： 根据内容进行寻址的存储器
• 地址转换部件： 通过联想存储器建立目录表以实现快速地址转换。 命中时直接访问Cache； 未命中时从内存读取放入Cache
• 替换部件： 在缓存已满时按一定策略进行数据块替换， 并修改地址转换部件

高速缓存存储器的组织

• 由于CPU芯片面积和成本， Cache很小
• 根据成本控制， 划分为L1、 L2、 L3三级

image-20200429183335305

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

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

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

image-20200429183705217

单连续分区存储管理

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

单用户连续存储管理

• 主存区域划分为系统区与用户区，设置一个栅栏寄存器界分两个区域， 硬
  件用它在执行时进行存储保护

• 一般采用静态重定位进行地址转换，硬件实现代价低

  静态重定位： 在装入一个作业时， 把该作业中程序的指令地址和数据地址全部转换成绝对地址

  image-20200429201248032

• 适用于单用户单任务操作系统， 如DOS

固定分区存储管理

• 支持多个分区
• 分区数量固定、大小固定
• 可用静态重定位
• 硬件实现代价低
• 早期OS采用

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%

平均地址转换代价为

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

地址转换流程

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

• 若该页已在快表中， 则由页架号和单元号形成绝对地址
• 若该页不在快表中， 则再查主存页表形成绝对地址， 同时将该页登记到快表中
• 当快表填满后， 又要登记新页时， 则需在快表中按一定策略淘汰一个旧登记项

多道程序环境下的进程表

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

多道程序环境下的地址转换

image-20200429213739251

内存分配/去配

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

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

image-20200429205652984

页的共享

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

• 数据共享： 不同进程可以使用不同页号共享数据页

• 程序共享： 不同进程必须使用相同页号共享代码页

  同一个程序不同的进程代码的位置是确定的

页式虚拟存储管理

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

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

页式虚拟存储管理的页表

需要扩充页表项：

• 每页的虚拟地址、 实际地址
• 主存驻留标志、 写回标志、 保护标志、 引用标志、可移动标志

image-20200429214322339

页式虚拟存储管理的实现

CPU处理地址

• 若页驻留， 则获得块号形成绝对地址
• 若页不在内存， 则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页面调度算法

• 采用循环队列机制构造页面队列， 形成了一个类似于钟表面的环形表

• 队列指针则相当于钟表面上的表针， 指向可能要淘汰的页面

• 使用页引用标志位

工作流程

• 页面调入主存时， 其引用标志位置1
• 访问主存页面时， 其引用标志位置1
• 淘汰页面时， 从指针当前指向的页面开始扫描循环队列
  • 把所遇到的引用标志位是1的页面的引用标志位清0， 并跳过
  • 把所遇到的引用标志位是0的页面淘汰， 指针推进一步

反置页表

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

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

为什么需要反置页表

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

反置页表如何实现

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

image-20200430104624992

反置页表的页表项

进程号 页号 标志位 链指针

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

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

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

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

反置页表的哈希表

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

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

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

地址转换过程

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

image-20200430105811444

段式存储管理

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

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

段式程序设计

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

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

image-20200430110727777

段式存储管理的基本思想

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

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

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

image-20200430111438522

段的共享

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

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

image-20200430112527632

段页式存储管理

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

对于每一段进行页式管理

对于每一段进行页式管理

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

image-20200430113258327

image-20200430113318715