操作系统学习笔记（十）操作系统知识点梳理
近期刚把操作系统整本书看了一遍，趁着有个总体印象，先梳理一下知识点
操作系统
计算机概述
操作系统特征
- 并发
- 共享
- 虚拟
- 异步
操作系统目标和功能
计算机系统资源管理者
- 处理机管理
- 存储器管理
- 文件管理
- 设备管理
用户和硬件之间的接口
对计算机资源的扩充
操作系统发展历史
手工操作阶段
批处理系统
- 单道批处理
- 多道批处理
分时操作系统
- 同时性
- 交互性
- 独立性
- 及时性
实时操作系统
网络操作系统
分布式计算机系统
操作系统运行环境
处理器运行模式
- 特权指令
- 非特权指令
操作系统内核
时钟管理
中断机制
原语
系统控制的数据结构及处理
- 进程管理
- 存储器管理
- 设备管理
中断和异常
内部异常（不可屏蔽）
- 故障（软件）
- 自陷（软件）
- 终止（硬件）
外部中断（硬件）
- 可屏蔽中断 INTR
- 不可屏蔽中断 NMI
系统调用
- 设备管理
- 文件管理
- 进程控制
- 进程通信
操作系统结构
分层法
模块化
宏内核
微内核
分为微内核和服务器
微内核基本功能
- 进程管理
- 低级存储器管理
- 中断和陷入处理
微内核特点
- 扩展性和灵活性
- 可靠性和安全性
- 可移植性
- 分布式计算
外核
操作系统引导过程
虚拟机
- 第一类虚拟机
- 第二类虚拟机
进程与线程
进程与线程
进程的概念和特征
进程的概念
- PCB是进程存在的唯一标志
- 进程是进程实体运行过程，是系统进行资源分配和调度的一个独立单位
进程的特征
- 动态性
- 并发性
- 独立性
- 异步性
进程的状态与转换
- 运行态
- 就绪态
- 阻塞态（等待态）
- 创建态
- 结束态
进程的组织
PCB
包含
- 进程描述信息
- 进程控制和管理信息
- 资源分配清单
- 处理机相关信息
组织方式
- 链接方式
- 索引方式
程序段
数据段
进程的控制
- 进程的创建
- 进程的终止
- 进程的阻塞和唤醒
进程的通信
共享存储（需要使用同步互斥工具，如PV）
- 低级方式：基于数据结构的共享
- 高级方式：基于存储区的共享
消息传递
- 直接通信方式
- 间接通信方式
管道通信
线程和多线程模型
线程的基本概念
- 引入线程的目的
线程与进程的比较
- 调度
- 并发性
- 拥有资源
- 独立性
- 系统开销
- 支持多处理机
线程的属性
线程的状态转换
- 执行状态
- 就绪状态
- 阻塞状态
线程的组织与控制
线程控制块TCB
- 线程标识符
- 一组寄存器
- 线程运行状态
- 优先级
- 线程专有存储区
- 堆栈指针
线程的创建
线程的终止
线程的实现
- 用户级线程ULT，也就是协程
- 内核级线程KLT
- 组合方式
多线程模型
- 多对一模型：多个用户级线程映射到一个内核级线程
- 一对一模型
- 多对多模型
处理机调度
调度的概念
基本概念：从就绪队列中按照一定算法选择一个进程并将处理机分配给它运行
调度的层次
- 高级调度（作业调度）
- 中级调度（内存调度）
- 低级调度（进程调度）
调度的目标
- CPU利用率
- 系统吞吐量
- 周转时间
- 等待时间
- 响应时间
调度的实现
调度程序
- 排队器
- 分派器
- 上下文切换器
调度的时机，切换与过程
不能调度
- 中断处理过程中
- 进程在操作系统内核临界区
- 需要完全屏蔽中断的原子操作
应该调度
- 发生调度条件且当前进程无法进行下去
- 中断处理结束或自陷处理结束
进程调度方式
- 非抢占式调度
- 抢占式调度
闲逛进程
两种线程的调度
- 用户级线程调度
- 内核级线程调度
调度算法
- FCFS
- 短作业优先SJF
- 优先级调度算法
- 高响应比优先
- 时间片轮转调度
- 多级队列调度
- 多级反馈队列调度
进程切换
- 上下文切换
- 上下文切换的消耗
- 上下文切换与模式切换
同步与互斥
基本概念
- 临界资源
- 同步
- 互斥
实现临界区互斥的基本方法
软件实现方法
- 单标志法
- 双标志法
- 双标志后检查法
- Peterson’s Algorithm
硬件实现方法（低级方法，元方法）
- 中断屏蔽法
- 硬件指令法（TestAndSet/Swap）
互斥锁
- 采用硬件机制实现
- 主要缺点是忙等待
信号量
- 整形信号量
- 记录型信号量
- 利用信号量实现同步
- 利用信号量实现进程互斥
- 利用信号量实现前驱关系
管程
定义
组成
- 管程的名称
- 局部于管程内部的共享数据结构说明
- 对该数据结构进行操作的一组过程
- 局部于管程内部的共享数据设置初始值的语句
条件变量
经典同步问题
- 生产者-消费者问题
- 读者-写者问题
- 哲学家进餐问题
- 吸烟者问题
死锁
概念
定义
原因
系统资源竞争
进程推进顺序非法
死锁产生的必要条件
- 互斥条件
- 不剥夺条件
- 请求并保持条件
- 循环等待条件
死锁处理策略
死锁预防
- 破坏互斥条件
- 破坏不剥夺条件
- 破坏请求并保持条件
- 破坏循环等待条件
避免死锁
- 系统安全状态
- 银行家算法
死锁的检测及解除
- 资源分配图
- 死锁定理
- 死锁解除
内存管理
内存管理概念
内存管理的主要功能
- 内存空间的分配和回收
- 地址转换
- 内存空间的扩充
- 内存共享
- 存储保护
进程运行的基本原理
程序的链接和装入
编译
链接
- 静态链接
- 装入时动态链接
- 运行时动态链接
装入
- 绝对装入
- 可重定位装入（静态重定位）
- 动态运行时装入
逻辑地址和物理地址
进程的内存映像
- 代码段：程序的二进制代码，只读，可被多个进程共享
- 数据段：程序运行时加工处理的对象，包括全局变量和静态变量
- 进程控制块（PCB）
- 堆：用来存放动态分配的变量，使用malloc函数动态向高地址分配空间
- 栈：用来实现函数调用，从用户空间的最大地址向低地址方向增长
内存保护
- 在CPU中设置一对上下限寄存器
- 采用重定位寄存器和界地址寄存器
内存共享
内存的分配与回收
连续分配
单一连续分配
固定分区分配
动态分区分配
- 首次适应算法
- 邻近适应算法
- 最佳适应算法
- 最坏适应算法
离散分配
分页存储
概念
- 页面和页面大小
- 地址结构
- 页表
基本地址变换机构
具有快表的地址变换机构
两级页表
分段存储
- 分段
- 段表
- 地址变换机构
- 段的共享和保护
段页式
虚拟内存管理
基本概念
传统存储管理方式的特征
- 一次性
- 驻留性
局部性原理
虚拟存储器的定义和特征
定义
特征
- 多次性
- 对换性
- 虚拟性
虚拟内存的实现
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
文件管理
文件
文件的概念
文件的组成
- 存储空间
- 分类和索引信息
- 访问权限的信息
文件的结构
- 数据项
- 记录
- 文件
文件控制块和索引节点
文件的属性
- 名称
- 类型
- 创建者
- 所有者
- 位置
- 大小
- 保护
- 创建时间
文件控制块（FCB）
索引节点（i节点）
- 磁盘索引节点
- 内存索引节点
文件的基本操作
- 创建文件
- 写文件
- 读文件
- 重新定位文件
- 删除文件
- 截断文件
文件的打开与关闭
打开文件表
- 进程打开文件表
- 系统打开文件表
打开文件表的索引（文件描述符/文件句柄）
- 文件指针
- 文件打开计数
- 文件磁盘位置
- 访问权限
文件保护
- 口令保护
- 加密保护
- 访问控制
文件的逻辑结构
无结构文件（流式文件）
有结构文件（记录式文件）
顺序文件
存储方式
- 顺序存储
- 链式存储
结构
- 串结构
- 顺序结构
索引文件
- 定长记录文件，记录的地址可以直接根据长度和索引号计算
- 变长记录文件：建立索引表，包含记录指针，长度，并按关键字排序。索引表本身也是一个定长记录文件
索引顺序文件
- 将顺序文件中的所有记录分为若干组，为顺序文件建立索引表
散列文件
文件的物理结构
文件的分配方式：非空闲块的管理
连续分配
链接分配
- 隐式链接：只适合顺序访问
- 显式链接：FAT
索引分配
- 链接方案
- 多层索引
- 混合索引
混合索引分配
文件存储空间管理：磁盘空闲块的管理
目录
目录结构
- 单级目录结构
- 两级目录结构
- 树形目录结构
- 无环图目录结构
目录操作
- 搜索
- 创建文件
- 删除文件
- 创建目录
- 删除目录
- 移动目录
- 显示目录
- 修改目录
目录实现
- 线性列表
- 哈希表
文件共享
- 硬链接：基于索引节点的共享方式
- 软链接：利用符号链实现文件共享
文件系统
文件系统结构层次
- I/O控制
- 基本文件系统
- 文件组织模块
- 逻辑文件系统
文件系统布局
文件系统在磁盘中的结构
- 主引导记录（MBR）
- 引导块（boot block）
- 超级块（super block）
- 文件系统中的空闲块
文件系统在内存中的结构
- 内存中的安装表
- 内存中的目录结构的缓存
- 整个系统的打开文件表
- 每个进程的打开文件表
外存空闲空间管理
空闲表法
- 首次适应算法
- 邻近适应算法
- 最佳适应算法
- 最坏适应算法
空闲链表法
- 空闲盘块链
- 空闲盘区链
位示图法
成组链接法
- 盘块的分配
- 盘块的回收
虚拟文件系统（VFS）
I/O管理
概述
I/O设备
分类
按信息交换的单位
- 块设备
- 字符设备
按传输速率
- 低速设备
- 中速设备
- 高速设备
I/O接口（设备控制器）
组成
- 设备控制器与CPU的接口
- 设备控制器与设备的接口
- I/O逻辑
主要功能
- 接受和识别CPU发来的命令
- 数据交换
- 标识和报告设备
- 地址识别
- 数据缓冲
- 差错控制
I/O端口（接口中可被CPU直接访问的寄存器）
分类
- 数据寄存器：实现CPU和外设之间的数据缓冲
- 状态寄存机：获取执行结果和设备的状态信息
- 控制寄存器：由CPU写入，以便启动命令或更改设备模式
通信方法
- 独立编址
- 统一编址（内存映射I/O）
控制方式
- 程序直接控制
- 中断驱动方式
- DMA
- 通道控制
I/O软件层次结构
- 用户层I/O软件
- 设备独立性软件
- 设备驱动程序
- 中断处理程序
- 硬件
应用程序I/O接口（I/O系统与高层之间的接口）
- 字符设备接口
- 块设备接口
- 网络设备接口
- 阻塞/非阻塞I/O
设备独立性软件
与设备无关的软件，包括执行所有设备公有操作的软件
高速缓存与缓冲区
磁盘高速缓存（逻辑上属于磁盘，物理上是驻留在内存的盘块）
形式
- 内存中开辟单独的空间作为高速缓存，大小固定
- 把未利用的空间作为缓存池，供分页请求和磁盘I/O共享
缓冲区
目的
- 缓和CPU和I/O设备间速度不匹配的问题
- 减少CPU的中断频率，放宽了CPU中断响应时间的限制
- 解决了基本数据单元大小不匹配的问题
- 提高了CPU和I/O设备之间的并行性
方法
- 硬件缓冲器
- 缓冲区（内存中）
缓冲技术
- 单缓冲，数据处理用时max(C,T) + M
- 双缓冲，数据处理用时max(C + M, T)
- 循环缓冲
- 缓冲池
设备的分配与回收
根据使用方式分类
- 独占式使用设备
- 分时式共享使用设备
- 虚拟设备（SPOOLing）
设备分配的数据结构
- 设备控制表DCT
- 控制其控制表COCT
- 通道控制表CHCT
- 系统设备表SDT
设备分配策略
原则：既要充分发挥设备使用效率，又要避免死锁
方式
- 静态分配：一旦分配，一直为该作业占有
- 动态分配
算法
静态分配
动态分配
- 先请求先分配
- 优先级高者优先
安全性（防治死锁）
- 安全分配方式：进程发出I/O请求就进入阻塞态
- 不安全分配方式：发出I/O请求后还可以继续运行，发出第二第三个I/O请求
逻辑设备名到物理设备名的映射
- 整个系统只有一个LUT表
- 每个用户登录，系统为之建立一个进程，并建立一个LUT放入进程的PCB中
SPOOLing技术（假脱机技术）缓和CPU的高速性和I/O设备低速性之间的矛盾，将独占设备改造成共享设备的技术
组成
- 输入井和输出井
- 输入缓冲区和输出缓冲区
- 输入进程和输出进程
特点
- 提高了I/O速度
- 将独占设备改造成共享设备
- 实现了虚拟设备功能
设备驱动程序接口
磁盘和固态硬盘
磁盘
- 磁道
- 柱面
- 盘面
- 扇区（盘块）
磁盘管理
- 磁盘初始化
- 分区
- 引导块
- 坏块
磁盘调度算法
读写时间
- 寻道时间
- 旋转延迟
- 传输时间
算法
- 先来先服务
- 最短寻找时间优先
- 扫描算法（电梯算法）
- 循环扫描
固态硬盘
特性
磨损均衡
- 动态磨损均衡
- 静态磨损均衡