导图社区 操作系统大纲笔记
- 55
- 10
- 1
- 举报
操作系统大纲笔记
超全！最细节的操作系统大纲笔记，归纳了操作系统的发展、进程管理、内容管理、文件管理、I/O管理的详细知识点，一张图带你了解操作系统知识！
编辑于2021-06-26 16:19:36- 操作系统发展
- 相似推荐
- 大纲
操作系统
概述
特征
并发
一段时间间隔发生
共享
互斥资源共享
同时访问共享
基本要求，互为存在
虚拟
时间划分复用技术
虚拟处理器
空间划分复用技术
虚拟存储器
异步
目标
资源管理
进程管理
内存管理
文件管理
设备管理
用户接口
命令接口
联机命令接口
立即处理，立即反馈
脱机命令接口
批处理
程序接口
系统调用
扩充机器
发展
1. 手工操作阶段
2. 批处理阶段
单道批处理系统
自动性
顺序性
单道性
多道批处理系统
多道
宏观上并行
微观上串行
并非多用户，没有交互性
3. 分时操作系统
同时性
交互性
独立性
及时性
特点：时间片
4. 实时操作系统
硬实时系统
软实时系统
紧急任务
5. 网络操作系统和分布式计算机系统
6. 个人计算机操作系统
运行环境
运行机制
时钟管理
中断机制
初衷用于多道程序运行
原语
最底层，最接近硬件
原子性，不可再划分
运行时间短，频率高
系统数据结构管理
中断与异常
内中断（异常）
自愿中断
指令中断，在计划当中
强迫中断
硬件故障，如缺页
软件中断，如除0
不可屏蔽
外中断
外设备请求
人为干预
内外的区分看是否在CPU上
核心态与用户态
核心态
时钟管理
中断管理
中断含有可以调用的，如指令中断也含有不可调用的，如强迫中断
设备管理
文件管理
进程控制
进程通信
内存管理
陷入指令，又称为访管指令，可调用的系统程序，仅在用户态下调用
用户态
非广义指令
体系结构
大内核
优点
高效
稳定
缺点
层次复杂
扩展性低
微内核
优点
层次清晰
模块独立，易于优化，系统可靠
缺点
性能下降
内核不稳定
进程管理
进程
概念
程序的一次执行过程
程序和其数据在处理机上执行时所发生的活动
系统进行资源分配和调度的独立单位
PCB是进程存在的唯一标志
特征
动态性
与程序区别的重要标识
并发性
间断性
资源可能被多个进程访问
不可再现性
独立性
异步性
结构性
状态
运行态
就绪态
阻塞态
创建态
结束态
控制
创建原语
1. 分配进程标识号，申请PCB
2. 分配资源
分配必要的内存空间等资源，若资源不足，则处于阻塞态，等待系统资源
3. 初始化PCB
4. 申请进入就绪队列
终止原语
1. 根据进程标识号，检索PCB
2. 终止该进程以及其子进程的执行
3. 所有占用资源归还父进程或操作系统
4. 将PCB从所在队列删除
阻塞原语
1. 进程调用系统服务，系统执行阻塞原语
2. 系统根据将要被阻塞进程标识号找到对应的PCB
3. 保护现场，状态转为阻塞态，停止运行
4. PCB插入等待队列
唤醒原语
1. 资源获取后，系统服务主动调用唤醒原语
2. 在等待队列找到相应进程的PCB
3. 从等待队列中移出，状态改为就绪态
4. 申请进入就绪队列
切换原语
1. 保存处理机上下文，包括程序计数器和其他寄存器
2. 更新PCB信息
3. 把进程PCB移入相应队列，如就绪或阻塞队列
4. 从就绪队列中选择另外一个进程执行，更新其PCB
5. 更新内存管理的数据结构
6. 恢复处理机上下文
组织
进程控制块
进程描述信息
进程标识符
用户标识符
进程控制和管理信息
进程当前状态
进程优先级
代码运行入口地址
程序的外存地址
进入内存的时间
处理机占用时间
信号量使用
资源分配清单
代码段指针
数据段指针
堆栈段指针
文件描述符
I/O
处理机相关信息
通用寄存器值
地址寄存器值
控制寄存器值
标识寄存器值
状态
程序段
进程所执行的代码段，由于用户可以运行多个相同的进程，该代码段可以被共享
数据段
堆栈
非重要组成
通信
共享存储
基于数据结构共享
低级方式
基于存储区的共享
高级方式
消息传递
直接通信
例如socket套接字
间接通信
利用中间实体，信箱方式，非数据库！没能找到应用实例！
管道通信
可以视为共享存储的优化，在内存或者文件实现均可，是半双工通信
线程
概念
轻量级进程，共享进程所有的资源
与进程比较
调度
线程是处理机调度和分派的基本单位
进程是资源调度的基本单位
处理机调度称独立调度，资源调度称拥有资源
拥有资源
理念上不拥有额外资源，否则切换开销很大失去线程意义
并发性
系统开销
地址空间和其他资源
共享进程资源
通信
分类
用户级线程
有用户栈，对于系统透明
核心级线程
切换核心态时候需要关联用户栈，保存线程上下文，然后启动中断处理，最后调用调度线程。
多线程模型
多用户对一核心
一用户对一核心
多用户对多核心
处理机调度
概念
作业调度
任务型调度，按照任务需求调入调出作业
内存调度
内存型调度，服务于内存提高效率和吞吐量
进程调度
就绪队列调度，服务于就绪队列
这里指进程级的调度，调度针对资源，是一种决策。而切换是实际的分配行为，在调度之后才有。
调度方式
非剥夺调度方式
剥夺调度方式
调度准则
CPU利用率
系统吞吐量
单位时间处理机完成作业的数量
周转时间
作业完成时间-作业提交时间
可能包括阻塞以及就绪的时间
等待时间
等待处理机时间之和
响应时间
提交请求到首次响应时间间隔
算法
FCFS
优点
简单，开销低
不会出现饥饿
缺点
对长作业有利，对短作业不利
对CPU繁忙作业有利，对IO作业不利
响应速度较一般
SJF
平均周转时间最短
优点
对短作业有利，响应时间高
系统吞吐量高
响应速度较快
缺点
对长作业不利
可能造成饥饿
SRT
优点
对短作业有利，响应时间高
系统吞吐量更高
响应速度较快
缺点
对长作业不利
更可能造成饥饿
HRRN
优点
系统吞吐量更高
平衡了FCFS和SJF
克服了饥饿
响应速度快
缺点
开销高
对长进程不过好
响应比=（等待时间+要求服务时间）/要求服务时间
RR
优点
简单，开销小
不存在饥饿
响应速度快
缺点
时间片短，则切换开销高
时间片长，则退化为FCFS
MFQ
优点
平衡兼顾
周转时间短
短作业优先
响应速度快
缺点
复杂，开销高
可能存在饥饿
AI
自己定义
进程同步
概念
临界
临界资源
一次仅允许一个进程使用的共享互斥资源
临界区
访问临界资源的代码
临界访问
1. 进入区
安全标识检查区
2. 临界区
3. 退出区
安全标识撤去区
4. 剩余区
可重入代码
不允许任何修改的代码
同步
多个进程完成任务需要按次序，属于直接制约
互斥
多进程资源使用制约，属于间接制约
准则
空闲让进
忙则等待
有限等待
让权等待
若果长时间等待无果，应该放弃等待
实现
算法实现
单标记算法
违背空闲让进
双标记算法
违背忙则等待
双标记后检查法
违背有限等待
Peterson算法
硬件实现
中断屏蔽方法
优点：简单方便
缺点：中断权力移交给用户，效率降低，并且危险
硬件指令方法
优点：适用于任意数目的进程
缺点：不能实现让权等待，有可能导致饥饿
信号量
信号量
PV操作
当s<0时，表示存在等待进程，等待进程数量=|s|
管程
程序中一般称为monitor
封装同步操作软件模块
目的
1. 集中管理分散在各个进程的临界区
2. 防止进程有意无意的错误同步操作
3. 便于用高级语言书写
记：集中管理，防止错误，便于书写
组成
局部于管程的共享数据结构说明
对该数据结构进行操作的一组过程
对局部于管程的共享数据结构设置初始值
记：说明、初始、过程
属性
共享性
安全性
变量访问受限于管程内
互斥性
每次只允许一个进程进入管程
封装性
被进程调用，属于语法范围，无法创建和撤销，类比抽象类
应用
可能出现多个进程进入到管程
唤醒者等待
HOARE管程，唤醒者回紧急等待队列，x.wait()为条件阻塞，x.signal()条件唤醒
被唤醒者等待
MESA管程，x.signal改为x.notify(),不需要唤醒者等待造成进程的切换，但被唤醒者由于不能立马进入运行态，所以运行之前需要再检查条件
唤醒仅在最后允许
应用
生产者-消费者问题
读者-写者问题
哲学家进餐问题
吸烟者问题
死锁
定义
多进程竞争资源造成互相等待
原因
系统资源有限
进程推进顺序不当
条件
互斥条件
记：互斥
不剥夺条件
记：独占
请求并且保持条件
记：贪心
循环等待条件
记：循环
互斥独占贪心循环
策略
死锁预防
破坏互斥：改共享
破坏剥夺：强释放
破坏请求保持：预分配
破坏循环等待：资源编号法
运行前安排好，破坏条件仅发生在预防阶段
死锁避免
系统安全状态
安全状态：存在满足进程需求序列
不安全状态：不存在满足进程需求序列
银行家算法
银行家算法不会限制资源申请，只会判断是否处于安全状态，若不安全，则试探作废，继续阻塞
运行时动态计算
死锁检测
资源分配图检测法
死锁定理
资源分配图不可简化
死锁解除
仅对死锁进程动手
资源剥夺法
强剥法
撤销进程法
杀人法
进程回退法
回滚法
定期检查且有解除策略
死锁忽略
I/O管理
概述
I/O设备分类
使用特性
人机交互外部设备
存储设备
网络通信设备
传输速率
低速
鼠标键盘
中速
打印机
高速
磁盘，显示器
信息交换单位
块设备
磁盘
传输速率较高、可寻址
字符设备
传输速率低、不可寻址、大都采用中断驱动方式
I/O控制方式
程序查询
中断驱动
DMA
通道
参考计算机组成最后章
I/O层次结构
用户层I/O软件
与用户交互的接口
设备独立软件
实现用户程序与设备驱动器统一的接口
执行所有设备的公有操作
向用户层提供统一接口
逻辑设备与和物理设备
优点
增加设备分配灵活性
易于实现I/O重定向
设备驱动程序
面向设备
中断处理程序
应该是不同设备自己的中断服务程序
I/O核心子系统
硬件
设备控制器
例如DMA
通讯
通过寄存器与CPU通讯
功能
接收CPU的命令
数据交互
提供设备状态信息
设备地址识别
组成
与CPU接口
控制线
地址线
数据线
与设备接口
I/O逻辑
实现对设备的控制，又称为设备控制器
I/O核心子系统
概述
I/O设备种类、速率和功能差异巨大，需要控制
I/O调度
确定一个好的顺序来执行多个I/O请求
例如磁盘调度
高速缓存与缓冲区
磁盘高速缓存
概述
利用内存的一块空间来暂存磁盘一组盘块的信息
存储高频访问数据
缓冲区
概述
利用内存作为缓冲区
是因为高速设备和低速设备通信而设
单缓冲
耗时MAX(C,T)+M
M独立
双缓冲
耗时MAX(T,C+M)
T独立
循环缓冲
多个缓冲区队列，in指针和out指针
缓冲池
复杂的缓冲队列组
设备分配与回收
考虑因素
固有属性
独占设备
分时共享设备
虚拟设备(SPOOLing)
分配算法
FCFS/SJF/优先级
安全性
安全分配方式
进入I/O进程阻塞，完成I/O进程唤醒
不安全分配方式
进入I/O后进程继续运行，并且可以多个I/O
静态分配与动态分配
静态分配
进程运行前为其分配全部资源，运行结束后归还资源
动态分配
进程运行过程中动态申请设备资源
数据结构
设备控制表DCT
每个设备对应一张DCT
类型
标志符
状态
COCT的指针
等待队列指针
控制器控制表COCT
每个控制器对应一张COCT
控制器标识符
控制器状态
CHCT指针
等待队列指针
通道控制表CHCT
每个控制器对应一张CHCT
标志符
状态
控制器表首地址
通道队列首指针
通道队列尾指针
系统设备表SDT
记录整个系统中所有设备情况
设备类
设备标识符
DCT
驱动程序入口
设备分配步骤
1. 根据进程请求的物理设备名查找SDT
2. 根据SDT找到DCT并分配设备
3. 根据DCT找到COCT分配控制器
4. 根据COCT找到CHCT分配通道
改进
用户编程时候使用逻辑设备名申请设备，操作系统负责逻辑设备到物理设备的映射
SPOOLing技术
概述
利用磁盘解决高速设备和低速设备之间的矛盾
作用
缓解设备与CPU的速度矛盾，实现预输入、后输出
组成
输入进程和输出进程
输入缓冲区和输出缓冲区
输入井和输出井
过程
输入进程
1. 输入进程申请一块磁盘空间作为输入井
2. 输入进程控制直接通过输入缓冲区把外设数据录入到输入井
输出进程
1. 输出进程申请一块磁盘空间作为输出井
2. 输出进程控制直接通过输出缓冲区把打印数据录入到输出井
3. 输出进程为用户进程申请一张空白的用户打印表，挂在请求队列上
文件管理
文件系统基础
概念
文件定义
以计算机外存为载体存储在计算机上的信息集合
记录
检索的基本单位
文件属性
名称
唯一对用户标识
标识符
唯一对文件系统标签
通常为数字ID
类型
文件类型
位置
指向设备和设备上文件的指针
大小
文件当前大小
保护
访问控制信息
log
创建、上次修改和上次访问相关信息
文件操作
创建文件
写文件
读文件
文件重定位（文件寻址）
删除文件
截断文件
打开与关闭
逻辑结构
无结构文件
字节流文件
有结构文件
顺序文件
串结构
记录之间的顺序与关键字无关
顺序结构
记录之间的顺序与关键字有关
索引文件
为变长文件建立索引表
索引顺序文件
顺序文件与索引文件的结合
散列文件
目录结构
文件控制块FCB=文件目录项
基本信息
访问控制信息
log
索引结点
仅有文件名和文件指针的数据结构
目录结构
单级目录结构
查找速度慢
不允许重名
不适用多用户
两级目录结构
多级目录结构
不利于文件共享
无环图目录结构
文件共享
硬连接
直接指针连接
删除一个硬链接文件并不影响其他有相同 inode 号的文件
文件有相同的 inode 及 data block
linux上的格式
只能对已存在的文件进行创建
不能交叉文件系统进行硬链接的创建
不能对目录进行创建，只可对文件创建
软连接
间接指针连接
指针（地址）指向文件的指针
软链接有自己的文件属性及权限等
可对不存在的文件或目录创建软链接
软链接可交叉文件系统
软链接可对文件或目录创建
删除软链接并不影响被指向的文件
文件保护
访问类型
读
写
执行
添加
删除
ls
访问控制
用户访问控制
文件系统实现
文件系统层次结构
用户调用接口
新建打开读写等操作
文件目录接口
FCB、索引结点管理
存储控制验证
软件实现访问权限控制
逻辑文件系统与文件信息缓冲区
记录与块号的计算
物理文件系统
逻辑块号转换为物理地址
辅助分配模块
设备管理程序模块
目录查找
线性列表
哈希表
折半
索引
文件实现
文件分配方式
连续分配
链接分配
隐式链接分配
显式链接分配
FAT
索引分配
链接方案
多层索引
混合索引
外存非空闲块的管理
文件存储空间管理
文件存储器空间划分与初始化
文件存储器空间管理
空闲表法
空闲链表法
位示图法
成组链接法
类似森林
外存空闲块的管理
磁盘组织管理
参数计算
一次读写操作时间
先找磁道，再找扇区，最后数据
寻道时间
跨磁道时间*磁道数量+启动时间
延迟时间
1/旋转速度
例如：xxx转/分
传输时间
数据字节数/（转速 * 磁道字节数）
例如：xxx转/秒
平均查找长度
移动磁道数/请求个数
平均每个请求需要移动磁道数
调度算法
FCFS
SSTF
SCAN
内容
已知当前位置和方向，一直扫到尾部，再反转扫到头部，如此往复
C-SCAN
内容
已知当前位置和方向，一直扫到尾部，再返回到头部，往尾部扫如此往复（返回速度和扫描速度一致）
如果没有说明，默认为取用改进SCAN和C-SCAN方式，即LOOK和C-LOOK方式
LOOK
SCAN改进版本，不需要到尽头，仅需要到最后一个请求磁道即可返回
C-LOOK
C-SCAN改进版本，不需要到尽头，仅需要到最后一个请求磁道即可返回
初始化
低级初始化
物理分区
逻辑初始化
创建文件系统
磁盘阵列
RAID
同时使用多个磁盘，提高传输率
多个磁盘并行存取大幅度提高数据吞吐率
通过镜像功能，提高安全可靠性
通过数据校验，提供容错能力
内存管理
程序与内存
程序装入与链接
编译
源代码到机器代码
链接
静态链接
编译后
装入时动态链接
装入内存时
运行时动态链接
动态链接库就是这种。
程序执行时
装入
绝对装入
可重定位装入
1.每次装入就计算好全部空间2.装入后不再改变，直到被换出
静态重定位
地址变换在装入时候完成，执行不再改变，程序必须连续
动态运行时装入
执行时可以改变存储空间，而且空间可以不连续，方便程序共享，提供用户更大的地址空间
动态重定位
执行时候才定位，而且程序空间可以不连续
逻辑与物理地址
内存保护
上下限寄存器
重定位寄存器与界地址寄存器
重定位：逻辑地址翻译物理地址界地址：判断是否越界
扩充内存
覆盖
同一进程中，要求用户给出覆盖结构，而虚拟内存技术则对于用户透明
程序在内存上分为固定区与可覆盖区
交换
不同进程中，每次换出换入整一个进程。
虚拟存储技术
并非物理扩充
连续分配方式
单一连续分配
内存仅有一个程序优点：简单，无外部碎片缺点：仅用于单用户，单任务操作系统，有内部碎片，效率很低
固定分区分配
仅有内部碎片
等分区方式
不等分区方式
动态分区分配
仅有外部碎片分配算法有：首次，最佳，最坏，邻近适应（循环首次）
非连续分配方式
页式存储管理
概念
页
进程中的块
页面
页的大小
页框
内存中的块
块
页在外存中的名称
页表
页号映射物理块号表
页表项
页表的一项
基本地址变换机构
快表地址变换机构
多级页表
段式存储管理
段表
地址变换机构
段的共享与保护
段页式存储管理
段表
页表
虚拟内存
概念
传统存储特征
一次性
作业必须一次性全部装入
驻留性
作业不会被换出
局部性原理
时间局部性
空间局部性
虚拟存储器特征
多次性
运行程序分多次调入
对换性
允许程序换入还出
虚拟性
仅逻辑上扩充容量
容量
理论最大容量
计算机地址位数
实际最大容量
min(计算机地址位数，内存+外存)
实现
方式
分页存储管理
分段存储管理
段页式存储管理
硬件
内存
外存
页表/段表机制
中断机制
地址变换机构
请求分页系统
基础
基本分页系统
增加调页功能
增加页面置换功能
作业不必完全装入内存
系统组成
页表机构
缺页中断机构
地址变换机构
置换算法
最佳置换(OPT)
最优但无法实现
先进先出(FIFO)
最简单但是效果差存在belady异常
最近最久没使用(LRU)
时钟算法
简单时钟算法
被命中过则访问位为1
被扫描访问位置0
双位时钟算法
访问位，修改位
第一轮
找（0，0），不作修改
第二轮
找（0，1）修改访问位
第三轮
找（0，0），不作修改
第四轮
找（0，1），不作修改
分配策略
驻留集大小策略
固定分配局部置换
难点是确定分配数目
可变分配全局置换
有可能由于贪婪导致占用其他程序的空间
可变分配局部置换
智能控制空间供需
调入页面时机
预调页策略
运行前调入
请求调页策略
运行中调入
调入页面位置
对换区充足
运行前进程所需要的文件全部放入对换区
对换区不足
最近修改的放入对换区
UNIX方式
相对于进程来设计
系统抖动
原因
页面置换算法不合理
频繁的页面调动行为
工作集算法
系统工作集平衡管理器控制
工作窗口
系统设定记录该进程工作页面历史
工作集
工作窗口里面不重复页面集合
调度情况
不适应进行调度
中断处理过程（非阻塞之时）
中断现场保护
中断现场恢复
重要的原子操作
应该进行调度
当前进程无法进行
中断结束