为思维导图导出的md版本，可能存在部分出入
第一章 计算机系统概述
操作系统基本概念
基本概念
- 操作系统是指控制和管理整个计算机系统的硬件与软件资源，合理地组织，调度计算机的工作与资源的分配，进而为用户和其他软件提供方便的接口与环境的程序集合。
- 操作系统是计算机系统最基本的软件
特征（最基本的两个特征是并发和共享）
- 并发
- 共享
- 虚拟
- 异步
功能和目的
功能
- 处理及管理
- 存储器管理
- 设备管理
- 文件管理（文件系统）
接口
命令接口
- 联机控制方式 脱机控制方式
- 联机命令接口 脱机命令接口
联机命令接口（交互式命令接口）适用于分时或实时系统
脱机命令接口（批处理命令接口）适用于批处理系统
操作系统发展历程
- 手工操作阶段（无操作系统）
- 批处理阶段（操作系统开始出现）
- 分时操作系统
- 实时操作系统
操作系统运行环境
操作系统的运行模式
- 操作系统内核程序（在核心态）
- 用户自编程序（应用程序）（在用户态）
- 特权指令：I/O指令，置中断指令，存取用于内存保护的寄存器，送程序状态字到程序状态寄存器的指令
- 非特权指令，不能直接访问系统中的软硬件资源
时钟管理
中断机制
原语
中断和异常
内部异常（内中断/异常）【来自cpu内部产生的异常事件】
软件中断（程序性异常）
- 故障 例如：整除0，缺页，非法操作法等运算溢出
- 自陷：事先安排好的，用于在用户态调用操作系统内核程序
硬件中断
- 终止 例如：控制器出错，存储器校验错
外部中断（中断）【来自cpu外部的设备向cpu发出的中断请求】
可屏蔽中断 INTR （I/O中断，时钟中断）
不可屏蔽中断 NMI （异常，电源掉电）
中断响应优先级
- 不可屏蔽中断 > 内部异常 > 可屏蔽中断
- 硬件故障 > 软件中断（内部异常中）
- DMA中断请求优先于I/O中断请求
- 在I/O传送类中断请求中，高速设备优于低速
中断处理过程
- 关中断
- 保存断点
- 中断服务程序寻址
- 保护现场和屏蔽字
- 开中断
- 执行中断服务程序
- 关中断
- 恢复现场和屏蔽字
- 开中断
- 中断返回
- 注释：前三个（粉色）为中断隐指令，由硬件完成；后面的由中断服务程序完成
系统调用
凡是与资源有关的操作（存储分配，进行I/O传输以及管理文件）都必须通过系统调用的方式发出服务请求
- 设备管理
- 文件管理
- 进程管理
- 进程通信
- 内存管理
操作系统结构
- 分层法
- 模块化
- 宏内核
- 微内核
- 外核
操作系统引导
虚拟机
第二章 进程与调度
进程与线程
进程概念定义
- 进程是程序的一个执行过程
- 进程是一个程序及其数据在处理及上顺序执行时发生的活动
- 进程是一个具有独立功能的程序在一个数据集合上的运行过程，他是系统进行资源分配和调度（线程出现后调度的基本单位是 线程）的一个独立单位
进程的组成
进程控制块 PCB
PCB是进程存在的唯一标志
概念
- 为了使参与并发执行的每个程序（含数据）都能独立的运行，为其配置了一个专门的数据结构，成为进程控制块（PCB）
- 系统利用PCB来描述进程的基本情况和运行状态，进而控制和管理进程
- 操作系统对各个并发运行的进程进行管理，但凡所需要管理的信息，都会被放在PCB中
PCB包含的内容
进程描述信息
进程控制和管理信息
资源分配清单
处理机相关信息 主要指处理机中的各个寄存器的值
- 当进程处于执行过程中时，处理机很多信息都在寄存器中
- 当进程被切换时，处理机状态信息都必须保存在相应的PCB中，以便在该进程重新执行时，能够从断点继续执行
程序段
- 程序的代码
数据段
- 运行过程中产生的各种数据
进程实体
- 相应地，由程序段，相关数据段和PCB三部分构成给了 进程实体（又称为进程映像）
进程映像是静态的，进程是动态的
所谓创建进程就是创建进程实体中的PCB，撤销进程就是撤销进程的PCB
进程的特征
- 动态性 动态性是进程最基本的特征
- 并发性 并发行是进程的重要特征，也是操作系统的重要特征（操作系统最基本的两个特性：并发性和共享性）
- 独立性
- 异步性
进程的状态与转换
状态
- 运行态
- 就绪态
- 阻塞态 又称为等待态
- 创建态
- 终止态
状态之间的转换
- 需要注意的是：一个进程从运行态变为阻塞态是主动的行为，而从阻塞态变为就绪态是被动的行为，需要其他进程的协助
进程控制
具有创建新进程，撤销已有进程，实现进程状态转换的功能
一般把进程控制用的程序成为 原语（执行期间不允许中断，他是一个不可分割的基本单位）
进程的创建
进程的终止
引起进程终止的事件
- 正常结束
- 异常结束：发生异常事件，如存储区越界，非法指令，I/O故障
- 外界干预
进程的阻塞与唤醒
- Block原语和Wakeup原语必须成对使用
进程通信
进程通信是指进程之间的数据交换
- PV操作是低级通信
- 高级通信方式是指以较高的效率传输大量数据的通信方式
高级通信方法
共享存储
- 低级：数据结构的共享
- 高级：基于存储区的共享
消息传递
- 直接通信方式
- 间接通信方式（信箱通信方式）
管道通信
- 从本质上说，管道也是一种问价你
- 管道是半双工，只允许单向通信
线程和多线程模型
引入进程和线程的目的
- 进程：更好地使多道程序并发的执行，提高资源利用率和系统吞吐量
- 线程：减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能
线程是进程中的一个实体，是系统独立调度和分派的基本单位（进程是资源分配的基本单位），线程不自己拥有系统资源
线程也有 就绪 阻塞 和 运行 三种状态
进程和线程的比较
调度
- 线程是系统独立调度和分派的基本单位
- 进程是资源分配的基本单位
并发性
- 不仅进程之间可以并发执行，同一进程之间的多个线程也可以并发执行
拥有资源
- 进程是系统中拥有资源的基本单位，线程不拥有资源（除了很少的能保证独立运行的资源）
- 线程可以访问其隶属进程的系统资源
独立性
- 每个进程都拥有独立的地址空间和资源
系统开销
支持多线程处理
- 对于多线程，可以将进程中的多个线程分配到多个处理机上执行
线程的属性
- 线程是一个轻型实体
- 不同线程可以执行相同的程序
- 同一进程的各个线程共享进程所拥有的资源
- 线程是处理机独立调度单位，多个线程可以并发执行
- 线程也拥有生命周期 三种状态的转换同进程一致
线程的组织与控制
- 线程控制块 TCB
- 线程的创建
- 线程的终止
线程的实现方式
用户级线程（ULT）
有关线程的管理都在用户区，内核意识不到线程的存在
优点
- 线程切换不需要到内核空间
- 调度算法可以是进程专用的
- 用户级线程的实现与操作系统无关
缺点
- 系统调用的阻塞问题（同时只能调用一个线程，其他线程被阻塞）
- 不能发挥多处理机的优势（同时只能调用一个线程）
内核级线程（KLT）
优点
- 能发挥多处理机的优势
- 如果一个线程被阻塞，其他线程可以被调用运行
- 内核支持线程具有很小的数据结构和堆栈，线程切换比较快，开销小
- 内核本身也可以采用多线程技术，提高执行效率
缺点
- 通过以进程的线程切换，需要从用户态转到核心态进行，开销大
组合方式
通过线程库来创建和管理线程
- 在用户空间提供一个没有内核支持的库
- 实现由操作系统直接支持的内核级的一个库
多线程模型
多对一
- 优点： 进程管理是在用户空格键进行的，效率较高
一对一
- 优点：并发性高
多对多
- 既克服了多读一模型并发度不高的缺点
- 又克服了一对一模型一个用户进程占用太多内核级线程而开销太大的缺点
- 拥有上述两种模型的各自优点
处理机调度
处理机的概念
调度的基本概念
- 处理机调度是对处理机进行分配，从就绪队列按照一定算法，选择一个进程并将处理机分配给他运行，以实现进程的并发执行
调度的层次
- 高级调度（作业调度）
- 中级调度（内存调度）
- 低级调度（进程调度）
三级调度的关系
- 作业调度为进程活动做准备，进程调度使进程活动起来
- 中级调度将不能运行的进程挂机，处于作业调度和进程调度之间
- 作业调度次数最少，中级调度其次，进程调度频率最高
- 进程调度是最基本的，不可或缺的
调度的评价标准
CPU利用率
- CPU的利用率 = CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间）
系统吞吐量
周转时间
- 周转时间 = 作业完成时间 - 作业提交时间
- 平均周转时间 = （作业1的周转时间 + ····+作业n的周转时间）/n
- 带权周转时间 = 作业周转时间 / 作业实际运行时间
- 平均周转时间 = （作业1的带权周转时间 + ·····+作业n的带权周转时间）/n
等待时间（需要加上在外存的等待时间）
调度的时机、切换与过程
不能进行调度与切换的情况
- 在处理中断的过程中
- 进程在操作系统内核临界区中
- 其他需要完全屏蔽中断的原子操作过程中
进程调度的方式
- 非抢占式
- 抢占式
两种线程的调度
- 用户级线程调度
- 内核级线程调度
调度算法
先来先服务（FCFS）算法
短作业优先（SJF）算法
高响应比优先调度算法
- 响应比 = （等待时间+要求服务时间）/要求服务时间
时间片轮转算法
多级队列调度算法
多级反馈队列调度算法
优先级调度算法
非抢占式优先级调度算法
抢占式优先级调度算法
静态优先级
动态优先级
优先级设置参考原则
- 系统进程 > 用户进程
- 交互型进程 > 非交互型进程
- I/O型进程 > 计算型进程
同步与互斥
基本概念
临界资源
- 进入区：
- 临界区：进程中访问访问临界资源的那段代码。又称为 临界段
- 退出区：将正在访问临界区的标志清除
- 剩余区 ：代码中剩余部分
同步
互斥
同步机制遵循的准则
- 空闲让进
- 忙则等待
- 有限等待
- 让权等待
实现临界区互斥的方法
软件实现方法
- 单标志法：违背 空闲让进
- 双标志先检查：违背 忙则等待
- 双标志后检查：会造成 饥饿
- Peterson‘s Algorithm ：没有遵循 让权等待
硬件实现方法
中断屏蔽方法
硬件指令方法
- TestAndSet（TSL/TS）
- Swap（Exchange/HCHG）
互斥锁
信号量
管程
经典同步问题
- 生产者-消费者问题（多对多/一对一）
- 读者-写者问题
- 哲学家进餐问题
- 吸烟者问题
死锁
所谓死锁，是指多个进程因为竞争资源而造成的僵局（相互等待）
产生的原因
- 系统资源的竞争（不可剥夺资源）
- 进程推进非法
产生的必要条件（同时满足一下四个条件）
- 互斥条件
- 不剥夺条件
- 请求并保持条件
- 循环等待条件
死锁策略
- 死锁预防
- 避免死锁
- 死锁的检测与解除
死锁预防
破坏互斥条件：方法不太可行，需要保持互斥性
破坏不剥夺条件
- 已保持了某些不可剥夺资源的进程请求新的资源得不到满足时候，它必须释放他所有的资源
破坏请求并保持条件
- 采用预先静态分配方法，在运行前一次性申请完他所需要的所有资源
破坏循环等待条件
- 使用顺序资源分配法
死锁避免（防止系统进入不安全状态）
- 银行家算法
死锁的检测与解除
资源分配图
- 圆圈代表进程，框代表资源
- 进程到资源的有向边为 请求边
- 资源到进程的有向边为 分配边
死锁定理
简化资源分配图
- 在资源分配图中，找出既不阻塞又不孤点的进程pi
- 释放pi
S死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件成为 死锁定理
死锁解除
- 资源剥夺法
- 撤销进程法
- 进程回退法
第三章 内存管理
内存管理概念
基本原理和要求
主要功能
- 内存空间的分配与回收
- 地址转换
- 内存空间的扩充
- 内存共享
- 存储保护
程序的链接与装入
将程序变成内存可执行程序
编译
链接
- 静态链接
- 装入时动态链接
- 运行时动态链接
装入
绝对装入
- 只适用于弹道程序环境
可重定位装入（静态重定位）
- 要求连续的全部内存空间，
动态运行时装入（动态重定位）
- 可以将程序分配到不连续的存储区，动态申请分配内存
内存保护
- 使用上，下限寄存器
- 使用重定位寄存器（又称为基地址寄存器）和界地址寄存器（界长寄存器） 必须使用特权指令
内存共享
- 可重入代码又称为纯代码，不可被修改
连续分配管理方式
单一连续分配
- 整个内存的用户空间由该程序独占
- 只能适用于单用户，单任务操作系统，有内部碎片，存储器利用率低
固定分区分配
- 分区大小相等
- 分区大小不等
动态分区分配（可变分区分配）
- 首次适应算法 通常是最好的也是最快的
- 临近适应算法
- 最佳适应算法
- 最坏适应算法
基本分页存储管理（看书）
基本分段存储管理（看书）
段页式管理（看书）
虚拟内存管理
基本概念
传统存储管理方式特征
- 一次性
- 留驻性
局部性原理
- 时间局部性
- 空间局部性
虚拟存储器的特征
- 多次性
- 对换性
- 虚拟性
虚拟存储器的最大容量 ，与主存和内存容量没有必然的联系
虚拟存储器的实际容量
请求分页管理方式
内存分配策略
- 固定分配局部置换
- 可变分配全局置换
- 可变分配局部置换
页面置换算法、
最佳（OPT）置换算法
先进先出（FIFO）置换算法
最近最久未使用（LRU）置换算法
时钟（CLOCK）置换算法
- 简单时钟（CLOCK）置换算法
- 改进时钟（CLOCK）置换算法
抖动和工作集
- 抖动：频繁的换入换出页面
- 工作集：一段时间内要访问的页面集合
虚拟存储器性能影响因素
地址翻译 （课本上，很重要）
第四章 文件管理
文件系统基础
文件的逻辑结构
无结构文件
有结构文件
- 顺序文件
- 索引文件
- 索引顺序文件
文件的物理结构
连续分配
链接分配
- 隐式链接（默认）
- 显示链接
索引链接
混合索引分配
目录
FCB的有序集合成为文件目录，一个FCB就是一个目录项
目录结构
单级目录结构
- 实现了按名查找，但是查找速度慢，文件不允许重名，不方便文件共享
两级目录结构
- 缺乏灵活性，不能对文件分类
树形目录结构
- 绝对路径，相对路径
无环图目录结构
- 方便文件共享，但是系统管理变得复杂
目录实现
- 线性列表（通常使用）
- 哈希表
文件共享
- 基于索引结点的共享方式（硬链接）
- 利用符号链实现文件共享（软链接）
文件系统
外存空闲空间管理
- 空闲表法
- 空闲链表法
- 位示图法
- 成组链接法
第五章 输入/输出（I/O）管理
I/O管理概述
分类
按使用特性
- 人机交互类
- 存储设备
- 网络通信设备
按信息交换
- 块设备
- 字符设备
传输速率
- 低速设备
- 中速设备
- 高速设备
I/O接口（设备控制器）
组成部分
- 设备控制器与CPU的接口
- 设备控制器与设备的接口
- I/O逻辑
功能
- 接受和识别CPU发来的命令
- 数据交换
- 标识和报告设备的状态
- 地址识别
- 数据缓冲
- 差错控制