导图社区 操作系统
王道操作系统所有知识点的思维导图，包括计算机系统概述、进程管理、内存管理、文件管理等内容，欢迎收藏和使用
提示: 本内容由社区用户上传并分享。平台不对内容的真实性、合法性、知识产权归属及是否侵害第三方权利进行事前审核或保证。本内容可能包含受版权保护的图片、字体或其他第三方素材，使用前请自行确认授权范围。
CAN（Controller Area Network）和CAN FD（CAN with Flexible Data Rate）是两种常用的汽车通信协议，它们具有各自的特点和适用场景。以下是对CAN和CAN FD总线协议的入门介绍。
王道计算机组成原理所有知识点的思维导图，包括计算机系统概述、数据的表示和运算、存储系统、指令系统、中央处理器、总线，欢迎收藏和使用。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
操作系统
计算机系统概述
概念
串行
并行
并发
并发是宏观上并行，微观上串行:两个或多个事件在同一时间间隔内发生
操作系统的分类及特点
批处理操作系统
单道批处理
自动性
顺序性
单道性
多道批处理
多道
宏观上并行
微观上串行
分时操作系统的特点
时间片🤔
特点
同时性
多个用户同时使用一台计算机
交互性
用户可以和系统进行人机对话
独立性
用户可以独立进行操作，互不干扰
及时性
用户能在很短的时间内获得响应
实时操作系统的特点
硬实时系统
飞机控制
软实时系统
买票
及时
可靠
用户态和内核态
怎么进去内核态？
中断(外中断)
硬件中断
外部设备带来的中断，如i/o设备发出的中断，外部信号中断(如按esc键)
时钟中断
定时器引起的中断
异常(内中断、异常、陷入)
软件中断
系统调用
程序的非法操作码
算术操作溢出
存取访问控制错
非法指令
校验错
除数为零
地址越界(非法)
数据格式非法
正常问题
虚拟系统的缺页
用户从用户态转到内核态(访管指令)
专门的陷入指令
用户执行特权指令
时间片中断
硬件故障
处理器或内存出问题
进程管理
进程与线程
进程的概念
组成
程序段
数据段
PCB(process control block)程序控制块
程序的一次执行过程
一个程序和其数据在处理机上运行时发生的活动
进程实体的一次运行过程
进程的五种状态
运行态
就绪态
阻塞态
创建态
怎么创建
分配标识
分配资源
初始化pcb
就绪序列接纳
结束态
状态变化
就绪到运行
进程获得处理机资源
运行到就绪
时间片用完或有更好优先级进去
运行到阻塞
进程中的某一资源还没准备好
阻塞到就绪
资源已经准备好
进程控制
创建
终止
阻塞
唤醒
就绪
运行
结束
切换
进程通信
低级通信方式
pv操作
高级通信方式
共享存储
存在一块可直接访问的共享空间
通过共享空间进行读写操作
低级共享
基于数据结构的共享
高级共享
基于存储区的共享
消息传递
直接通信
间接通信(邮箱、信箱通信方式)
管道(半双工)
共享存储的先进方式
因为不会出现访问共享区域等待的情况
线程
一个进程有多个线程
轻量级进程
进程和线程的区别
调度
在同一进程中，线程切换不会引起进程切换
资源
分开了，进程是对应拥有资源的独立单位，线程是独立调度
进程
单进程既是拥有资源的基本单位，也是独立调度的基本单位
并发并发
引入线程的操作系统具有更好的并发性既可以在线程之间并发，也可以在进程之间并发
系统开销
创建或撤销时开销大
小
地址空间和其他资源
进程的地址空间相互独立
共享
通信
需进程同步和互斥手段
可以共享全局变量
两类线程实现
ULT.用户级线程
线程由应用程序管理，内核不管
KLT内核级线程
内核管理线程，应用程序不管
组合使用
三种线程模型
多对一
多个用户级线程对一个内核级线程
一对一
多对多是什么价值的唯一源泉？
处理机调度
三级调度
作业调度(高级)
作业调度让进程为被调用做准备
中级调度(内存调度)
暂时不能运行的进程放到外存，叫挂起态有机会运行放到就绪态
调度算法
进程调度(低级)
分配处理机
FCFS(先来先服务)
不可剥夺算法
SJB(短作业优先算法)
平均等待时间、平均周转时间最少
优先级调度算法
根据是否能抢处理机，分为
非剥夺式
剥夺式
优先级
静态优先
动态优先
进程优先级
系统大于用户
交互大于非交互
钉钉大于微信
i/o大于计算
高响应比优先调度算法
响应比=(等待时间+要求服务时间)/要求服务时间
时间片轮转转
时间片过小
开销大
时间片过大
先来先服务
多级反馈队列
结合了时间片和优先级
每个队列有不同的时间片和优先级
前两个很垃圾第三个可以实时四五六可以用在分时上
进程同步
什么是临界区
进程中访问临界资源的一段代码
什么是临界资源
一次仅允许一个进程使用的资源(和独占式设备类似)
什么是同步？
直接制约关系(进程之间为了某种目的产生的制约关系)
为什幺要同步？
为了产生一定的约束
什么是互斥？
我用的时候你不能用
实现临界区互斥的方法
软件方法
单标志法
一个牌子，我进来了，牌子变成你可以进来我从后门出去了你却不想进来，我就不能再进去
违背空闲让进
双标志法先检查
有两个牌子，两个人换牌子都要一定时间，可能撞上了
违背忙则等待
双标志法后检查
先改自己的，后看别人的
违背有限等待，导致饥饿
皮特森peterson算法(三标志算法)
进门先客套
硬件方法
中断屏蔽方法
关中断
我在用，其他人爬
硬件指令
信号量
整型信号量
未遵循让权等待，遵循忙则等待
记录型信号量
因为实现了让权等待，进程不能进去临界区时，立即释放处理器，防止忙则等待
实现同步
实现互斥
步骤
分析同步和互斥关系
确定PV操作的大致顺序
设置信号量
PV操作要紧夹使用互斥资源的那个行为，中间不能有其他冗余代码
经典同步互斥问题(会写代码)
生产消费者问题
关系分析
缓冲区互斥，生产后才能消费(同步)
整理思路
确定互斥(一个)、同步(一个)的pv操作位置
三个信号量
互斥信号量mutex
满缓冲区缓冲数full
空缓冲区缓冲数empty
吃水果问题
盘子(互斥) 妈妈放橘子后儿子才能吃(同步)爸爸放苹果后女儿才能吃(同步)
两个生产消费者问题
信号量设置
互斥盘子plate
同步apple
同步orange
读写问题
读者霸占，写者共享
读进程优先
读者和写者
互斥
读者和读者
无互斥
写者和写者
思路
写者和所有的互斥读者与写者互斥，与读者并发因为可能有多个读者，因此要有个计数器
计数器要对读者互斥，不让可能出现混乱
计数器
count
互斥信号量(保证count的互斥)
mutex
读写互斥
readw
读写公平法(也称写进程优先)
哲学家进餐问题
五个进程(哲学家)和五个缓冲区(筷子)
对缓冲区互斥
一:同时拿两双筷子
二:限制动作
五个互斥信号量(哲学家编号与筷子编号有关系)
吸烟者问题
吸烟者和供应者
同步
吸烟者和吸烟者
类似吃水果问题，只不过人数有所变化
三个不同供应种类(类似不同水果)
三个互斥量
供应者和吸烟者
管程
定义
由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块
软件模块
数据
成员变量
操作
成员函数
赋初值语句
子主题
抽象类
死锁
死锁产生的四个必要条件
允许资源共享
不剥夺
设定资源可剥夺(释放)
请求并保持
预先静态分配，一次申请所有资源且运行时不再请求其他资源
循环等待
顺序资源分配法
死锁预防和避免
什么是死锁预防
破坏四个必要条件其中的一个或多个
什么是死锁避免(银行家算法)
防止系统进去不安全状态
死锁避免
系统安全状态
安全序列
银行家算法
数据结构
可利用资源
available
最大需求矩阵
Max
分配矩阵
allocation
需求矩阵
Need
检测后解除
允许发生死锁，发生后解除
资源剥夺
撤销进程
进程回退
死锁定理
资源分配图不可完全简化
完全简化是可消去所有边
内存管理
操作系统对内存空间进行合理的划分和有效的动态分配
内存管理的概念
功能
内存空间的分配与回收
地址转换
一般是逻辑地址变成物理地址
这个过程是地址重定位
内存空间的扩充
自动覆盖技术
自动覆盖虚拟内存
存储保护
基本原理
程序装入过程
第一步
编译
用户源程序变成目标模块
第二步
链接
将(目标模块+库函数)链接成完整的装入模块
静态链接
程序运行前
装入时动态链接
边链接边装入
运行时动态链接
我需要目标模块，这个模块才开始链接
第三步
装入
装入内存
绝对装入
逻辑地址和物理地址相同
只适用于单道程序环境
可重定位装入
静态重定位
有逻辑地址向物理地址的转化
作业装入时，空间必须足够大(一次性装入)
运行时不能再内存中移动，也不可以再要空间
动态运行时装入
动态重定位
需要寄存器支持
静态重定位不支持的，都支持
内存保护
上下限寄存器
看地址是否过大或过小
重定位寄存器和界地址寄存器
界地址寄存器(限长寄存器)
含有逻辑长度的最大值
重定位寄存器(基址寄存器)
有最小的物理地址值
连续分配管理方式
单一连续分配
内存空间中只有一道程序
有内部碎片，无外部碎片
内部碎片是？分区内的碎片外部碎片是？分区外的碎片假设内存是一个盒子，内部碎片是有固定隔板中未装满的那部分，外部碎片是有移动隔板的盒子中未装程序的部分
覆盖(解决空间不足)与交换(提高作业道数)
覆盖
同一进程内执行
将内存分为固定区和覆盖区，固定区放经常活跃的段覆盖区放第二活跃的，外存区放第三活跃的
交换
不同进程内执行
换出
内存到外存
换入
外存到内存
固定分区分配
分区大小已经固定
多道程序
动态分区分配
可变分区分配
按照程序需要的内存来分配空间
紧凑
移动进程来调整空闲分区大小
对应于外存中的磁盘整理
动态分区分配策略
分配空闲分区
首次适应
最佳适应
最坏适应
邻近适应(循环首次适应算法)
非连续分配管理方式
和连续分配最大的区别在于，可以把程序分段后放入内存
分页存储管理方式
基本分页
与固定分区类似，不产生外部碎片，只产生内部碎片
几个概念
页面和页面大小
页
进程中的块(要放入内存中的)
某固定大小的物体
页框(也称页帧)
内存中的块
物体大小的盒子
块
外存中同样大小的内容
地址结构(索引)
页内偏移量(0-11位)W
页号(12-31位)P
如果这是一本书，页号告诉你在哪一页，页内偏移量告诉你在哪一行
页表
每个进程都有一个页表，存放在内存中
哈利波特(进程)有七本书(用动态分配技术分为了七个内存空间)，哈利波特打败伏地魔是在哪本书里面？
这时你就可以查找页表找出这一情节在哈利波特与死亡圣器这本书里了
页表项
某个情节在哈利波特哪一部中哪一页
地址
某个情节在哈利波特某一页中，而这一页在一整行奇幻系列书本中哪个位置
地址变换
利用页表实现
通过页表实现
访问两次内存
页表项单位怎么确定？(下限如何确定)
关键在页数
具有快表的地址变换机构
快表，又称相联存储器
先访问快表
有就提取
没有就走页表查询这一条路
快表页表同时访问
两级页表
多级页表解决了什么问题？又出现了什么问题
将最低级页表放在外面，用的时候根据高级页表查找得到
顶级页表最多只有一个
解决了页表占用了太多内存的问题使得有时访存比较慢
请求分页(虚拟内存部分)
分段存储管理方式
分段
段内要求连续，断间不要求连续
段表项
段号+段长+基址
段的共享与保护
只共享其他人不能使用的纯代码(可重入代码)
不共享段在分别进程中的位置(即段号)
保护
存取控制保护
地址越界保护
为什么页式存取只判断页号是否越界页内偏移不可能越界？
因为页内偏移小于或等于页面大小
什么是显示给出？为什么段号和段内偏移要显示给出？
显示给出就是不包括在一个大数中，各个部分清清楚楚
因为每段大小不一，无法确定位置
要看段号是不是多了，也要看偏移是不是超过了这一段的大小
段页式管理方式
作业分段，内存空间分页
㊙一个进程最多一个段表，但是可以由多个页表
逻辑地址
段号+页号+页内偏移量
段号+页表长度+页表初始地址
页号和块号
虚拟内存管理
基本概念
传统内存的特点
一次性
作业全部装入后才能运行
驻留性
装入后就不会被换出，直到运行结束(阻塞了就等，不会被换出)
局部性原理
时间局部
刚刚运行过的软件可能会再次使用，因此提升优先级
空间局部
某个照片被访问后，后面的照片很可能被访问
类似于网页预加载
什么是虚拟存储器
以内存为主，外存为辅
程序可拆分
多次性
对应传统的一次性
对换性
对应传统的驻留性
虚拟性
只是逻辑上扩充了，实际上没有扩充
实现支持
内存加外存
传统的基本上只用到内存
页表(或者段表)
中断机制
传统的没有中断机制
实现方式(存储管理)
请求分页
增加了四个字段
状态位
放入内存没？
访问字段
用了多少次？
修改位
内容改过没？
外存地址
家是哪里的？
缺页中断过程
页面不在就产生缺页中断
先查快表
快表无则看是不是在内存中
不在就缺页中断然后调入内存
页面置换算法
opt(最佳置换算法)
放弃最长时间内不用的
1923412345999999假如只有三个格子，那么放入3的时候放弃9
FIFO先进先出
会出现belady异常
物理块越多，缺页次数反而变多
巧妙
LRU(最近最久未使用)
(时钟置换算法)NRU CLOCK
加个使用位
装入置1，访问到也置1
用完后替换出去的帧还是1，优先级比0小
改进型CLOCK
多了一个修改位
页面置换策略
基础概念
驻留集大小
什么是驻留集？
驻留集就是给一个进程分配的物理页框
三种
固定分配局部置换
给进程分配一定物理块后就不管了
可变分配全局置换
分配物理块后，还留有空闲区
可变分配局部置换
只有在进程缺页率极高的情况下，才会给进程再分配一些空闲物理块
为什么没有固定分配全局置换呢
因为这相当于把整块内存都分出去了(全局置换)
什么时候调用
预调页策略
基于空间局部性
请求调页
没有该页面才进行调页
从何处调页
知识储备
外存
存档文件的文件区
存放对换页面的对换区
对换区采用连续分配，所以更快一点
调页来源
对换区足够
从对换区调
对换区不够
从文件区和对换区里面调
UNIX方式
用过的放在对换区，没用过的放在文件区
抖动
什么是抖动
页面频繁换入换出
怎么预防
局部置换策略
工作集算法融入到处理机调度中
什么是工作集算法？
工作集:某段时间间隔内，进程要访问的页面集合
根据最近访问过的页面确定工作集
调整缺页率
选择暂停的进程
原因
内存太小
地址翻译
TLB(高速缓存)
Cache
主存
请求分段
请求段页式
文件管理
文件系统基础
文件的概念
文件定义
图片文本程序游戏等都是文件
存储空间内的数据+分类和索引中的信息+访问权限
图书管理员(操作系统)管理图书馆(存储空间)中的一本书(文件)
文件的属性(七个)
文件的基本操作(六个)
文件的打开和关闭
逻辑结构(有印象即可)
无结构文件(流式文件)
有结构文件(记录式文件)
顺序文件
串
记录按时间排序
顺序
记录按关键字排序
索引文件
定长索引类似分页存储
变长索引只能顺序查找
索引顺序文件
组与组之间必须有序，组内可以无序
联想:分段段内必须连续段间随便放(实际上联系不大)
散列文件或直接文件
目录结构
索引占空间更加小
文件控制块
FCB存放控制文件所需的各种信息的数据结构
包含了哪些信息
基本信息
存取控制信息
使用信息
索引节点
磁盘索引节点就是放在磁盘上的索引节点
怎么用索引节点的地址信息计算最大文件大小
目录结构分类
单级目录
只有一个目录表，每个文件占用一个目录项
两级目录
解决查找慢，文件不允许重名问题
多级目录结构
现在手机电脑用的
绝对路径
从根结点到目的文件上所有的目录+数据文件名
中间用“/”分割来
相对路径
从当前目录到目的文件所有目录+数据文件名
中间也用“/”分割开
无环图目录结构
为了共享
文件共享
硬链接
基于索引节点
每个用户都有指向其索引节点的指针
软链接
基于符号链接
联想office.里的超链接？
保存共享文件的路径名
文件保护
口令保护
加密保护
访问控制
文件系统实现
文件系统层次结构(牢记)
0.用户调用接口
文件目录系统
存取控制验证
逻辑文件系统和文件信息缓冲区
物理文件系统
辅助分配模块
设备管理模块
发出请求
查找目录
验证用户能不能用
能用就给出逻辑结构
通过逻辑结构找到物理地址
删除就用辅助空间分配模块
使用文件就用设备分配模块
目录实现
线性表
哈希表
文件实现
连续分配
联想:动态分区分配(内存管理)
也是动态分段，段内连续
链接分配
无外部碎片
离散
分类
隐式分配
只能根据指针顺序访问
显示分配
用内存放指针表，通过查表找下一个指针，再通过指针找到想找的内容
快在内存，优在稳定
索引分配
支持直接访问
m级目录要查找m+1次，访问m+1次磁盘。和访问第几条记录无关
连续分配要1次
链接分配要n次
磁盘组织与管理
磁盘的结构
磁头
磁道
扇区
磁道间隙
扇区间隙
读写操作时间(想象一下)
三部分
磁盘寻址方式
盘面号-柱面号-扇区号(或块号)
磁盘调度算法(会手动模拟)
FCFS先来先服务
SSTF最短寻找时间算法
SCAN循环算法(电梯)
LOOK调度(到达最远处的一个请求)
C-SCAN循环扫描算法(一轮又一轮)
C-LOOK算法
磁盘格式化
物理格式化
低级格式化
分区
逻辑格式化
高级格式化
创建文件系统
