操作系统思维脑图思维导图
U351717208
2023-12-04
操作系统
软硬件
计算机
系统与硬件的相关内容讲解
树图思维导图提供《操作系统思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《操作系统思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：566aeb3d7d4fc3a1106ada3bc6640771
思维导图大纲
相关思维导图模版
操作系统思维导图模板大纲
操作系统引论
概述
OS的功能
基本功能
提供接口
OS处于用户与计算机硬件系统之间
扩展资源管理
处理机
存储管理
I/O
文件管理
扩展功能
虚拟机
其他功能
OS的设计动力
方便性
有效性
可扩展性
32bit--6 4bit（总线宽度）
可移植性
OS的发展动力
元器件升级代换
新的体系结构
更高的方便性需求
更高的有效性需求
OS的类型发展
无OS阶段
纯手动操作
用户角度
周转时间长
系统角度
吞吐量小
脱机输入输出
减少CPU空闲时间
提高I/O速度
单道批处理阶段
特点
单道性
独占性
同步性
结果可再现
缺点
用户运行时间短
系统资源少
多道批处理阶段
特点
多道性
共享性
异步性
结果不可再现
缺点
用户运行周期时间长
系统吞吐量大（优点）
分时系统
及时性
及时接收
及时反馈
实时系统
类型
单用户单任务
DOS
单用户多任务
WinXP
多用户多任务
win server,unix-linux
OS结构发展
无结构OS（单道批处理）
模块化结构：循环调用
层次化结构
c/s结构：缩短调用路径
b/s结构
微内核结构
足够
c/s结构
OS总结
共享
并发、并行、同时、微观
虚拟：数据结构分装
异步
多道批处理
分时系统
实时系统
处理机器管理
作业管理
作业的概念
在操作系统中，把用户要求计算机系统处理的一个计算任务或事务处理称为一个"作业"。
作业之间的区分：命名、标识符
资源需求清单
CPU现象保护--多道批处理
地址空间
输入输出
时间指标
作业实体
JDB+程序
JDB作用：作业存在的唯一标准
作业意义
作业是一个程序
作业是作业实体在计算机中的运行过程
是运行调度资源分配的基本单元
作业控制
收容：插入就绪队列
调度
请求I/O
I/O完成
完成
作业调度
依据一定的策略，决定作业执行顺序的过程
调度算法：作业调度的依据策略
评价指标
周转时间
T=退出时间-登录时间
平均周转时间
T=TA*1/n=1/吞吐量
带权周转时间
T=周转时间/执行时间=（执行时间+等待时间）/执行时间=1+等待时间/执行时间
调度算法
先来先服务（FCFS）
优先级=|先到时刻-到达时刻|
短作业优先（SF）
优先级=|执行时间|
响应比高优先（HRN）
优先级调度算法
作业管理特点
调度对象是作业，精度大，调度次数少，需要资源少，开销大，管理粗放，部件效率的低，并行度低
算法：简单，公平
进程管理
进程
进程的实体
PCB
标识符
CPU现场保护区
调度信息
进程间通信同步机制
作用
进程存在唯一标志
保障进程的断续
有利于进程管理
有利于进程问题通行
有利于进程同步
进程的定义
进程实体
PCB+实体+数据
进程定义
作业的一部分
进程实体的运行过程
运行和资源分配的基本实体
进程的状态模型
两状态模型
三状态模型
执行态
就绪态
阻塞态
第一种五状态模型
新建态
终止态
第二种五状态模型
新建态
执行态
七状态模型
挂起就绪态
挂起阻塞态
进程控制
创建
who
父进程、用户、交互、作业
how
创建进程定律
申请空间pcb
初始化pcb
分配标识符
分配资源
组装进程实体
修改状态
上传
how
找pcb
修改状态
插入队列
计算效率
阻塞
唤醒
挂起
who
父、用户、用户挂起其他程序
how
找pcb
修改状态
拆分进程实体
释放资源：把程序数据调出内存
插入静态队列
插入队列
激活
how
找pcb
重组实体
申请
调用
修改状态
插入队列
调度
who
系统
how
找pcb：运行调度算法，决定进程的运行程序
修改状态
插入队列
CPU切换
保留CPU现场
恢复CPU现场
CPU分配
调度算法
时间片轮转
高优先级优先
优先级确定
静态
不变
动态
改变：随等段时间等待而改变
抢占式
在进程到达时优先级跟CPU上执行的进程比较，如果高就抢占
非抢占式：在就绪队列排队
考虑进程的等近程度
在抢占调度中，低优先级进程周期可能出现饥饿、饿死
可考虑动态优先
多队列调度
采用多级调度可实现
可以避免饥饿
多级进程调度队列
自动切换
可能出现饥饿
公平调度算法
子主题 3
子主题 4
子主题 5
优先级
优先级倒置
P2阻塞P1，低优先级进程阻塞高优先级
区分阻塞两种状态
高优先级进程速率
实时调度：截止时间要求
开始截止时间
不晚于某某开始
不早于某某开始
完成截止时间
服务时间：开始时间不晚于=完成-服务
优先级=|当前时刻-最晚开始时间|
多调度的实现
进程调度的队列模型
进程问题
IPC分类
共享内存
共享简单变量
共享结构
共享外存
不同计算机的进程通信
邮箱
远程调用RPC
信息通信
特点
粒度数小
并行调度提高
并行度随CPU上升而下降
线程管理
线程
定义
线程进程的积分
线程共享内存空间
共享进程资源
线程职责
进程职责
线程运行基本单位
线程里线程实例的运行过程
实现
内核支持线程
用户级线程
混合级线程
超线程技术
信号量
前趋图
有向无环图，向前驱关系组成
有向无环图，向前驱关系组成前qu
前趋图的信号量表示
semaphore a=b=c=...g=0
信号量的作用
信号量的类型
整型信号量
记录型信号量
and型信息量
信号量集set
信号量集
经典同步问题
生产者和消费者问题
题目
系统中一组生产者进程和消费者进程，生产者每次生产一个产品放入缓冲区，消费者每次从缓冲区中取走一个产品
缓冲区
生产者、消费者共享一个初始为空、大小为n缓冲区
缓冲区是临界资源，必须互斥访问
只有缓冲区没满时，生产者才能把产品放入缓冲区
只有缓冲区没空时，消费者才能把产品从缓冲区取走
关系
同步关系
缓冲区满，生产者要等待消费者取走产品
缓冲区空，消费者要等待生产者生产产品
互斥关系
生产者与消费者必须互斥的访问临界区
实现
设置初始值为1的互斥信号量
设置同步信号量
表示空闲缓冲区的数量semaphoreempty=n
表示产品数量，非空缓冲区的数量semaphore full=0
设置一个信号量表示资源数量
哲学家就餐问题
问题
5个哲学家，5根筷子，思考和吃饭
关系分析
5个进程，他们与左右邻居中间的筷子访问是互斥关系
每位哲学家进程需要持有2个临界资源才能吃饭
要避免死锁现象
读者写者问题
高级的同步机制
定义
一种特殊的软件模块
组成
局部于管程的共享数据结构
对该数据结构进程操作的一组过程(函数)
对局部于管程的共享数据设置初始值语句
特征
局部于管程的数据只能被局部于管程的过程所访问
一个进程只有通过调用管程内的过程(“入口”)才能进入管程访问的共享数据
每次仅允许一个进程在管程内执行某个内部过程
处理机调度与死锁
死锁
死锁
僵持状态
原因：进程的推进次序不同
死锁发生必要条件
去除互斥条件
保持请求状态
循环等待
死锁处理
死锁表示
元素
进程
资源区
分配边：资源指向进程的有向边
申请边：进程指向资源的有向边
资源分配图
死锁定义里无环无死锁，有环可能有死锁
死锁检测
资源分配固化
找申请边的进程，去掉分配边，找不到转下一个字
找申请边能满足的进程把申请边变成分配边，转a，如果找不到转下一条
用死锁定理判断是否有进程
没有死锁状态：安全状态
死锁恢复
回退
杀死进程
关机重启
死锁动态避免
死锁的原因
多个线程或进程互相等待资源
线程或进程无法继续执行
等待无限期进行下去
死锁预防的原理
通过特定的算法和机制
使得线程或进程无法选择需要的资源
避免互相等待资源的情况发生
死锁避免方法
通过使用系统调用、信号量等机制
监控线程或进程的状态
在检测到死锁风险时采取措施避免死锁
死锁避免动态调整
通过动态监测和调整线程或进程的执行状态
在死锁发生前或发生后采取相应的措施
避免死锁对系统的影响
使用锁粒度控制死锁
使用细粒度锁可以提高并发性能
但也增加了发生死锁的风险
使用粗粒度锁可以减少死锁的发生但会影响并发性能
死锁避免的注意事项
尽量避免过度使用锁
避免死锁需要系统地分析和设计系统架构
在设计系统时需要考虑到死锁的预防和避免方法
存储器管理
内存
内存的物理存储结构
用于存放数据的硬件，程序执行前需要先放到内存中才能被CPU处理
内存的读写操作
从0开始，每个地址对应一个存储单元
字节编址
存储单元大小1个字8个二进制
字编址
存储单元大小1个字16个二进制位
内存的缓存
内存中一个个的“小房间”
外存
外存的物理存储结构
外存的访问速度
外存的数据保护
存储器的管理
物理地址
逻辑地址
虚拟地址空间
逻辑地址空间
静态链接
程序运行前，各目标模块及所需库函数连接成一个完整的可执行文件(装入模块)
载入时动态链接
将各目标模块装入内存时，边装入边链接的链接方式
运行时动态链接
程序执行中需要将该目标模块时，对其进行链接
优点
便于修改和更新
实现对目标模块的共享
逻辑地址转换为物理地址
绝对装入
单道程序环境
静态重定位
特点
地址变换是在装入时一次完成的
在一个作业装入时，必须分配其要求的全部内存空间
作业一旦进入内存后，在运行期间就不能再移动，也不能在申请内存空间
动态重定位
特点
动态运行时装入
逻辑地址一>物理地址
指令运行进行
重定位寄存器支持
存放装入模块存放的起始位置
允许程序在内存中发送移动
优点
程序运行前只需装入部分代码即可运行
根据需要动态申请分配内存
程序段的共享
页式和段式内存管理
页式内存管理
页框(物理块/页/内存块)
定义
将内存空间分成多个大小相等的分区，每个分区就是一个“页框
页框太大，会有内部碎片
页的访问方式：按页号访问
定义
将用户进程的地址空间分为与页框大小相等的一个个区域
页号
每个页面的编从0开始
逻辑地址一>物理地址
算出逻辑地址对应的页号
页号=逻辑地址/页面长度(取整)
页号对应页面在内存中的起始地址
页内偏移量=逻辑地址%页面长度(取余)
求逻辑地址载页面内的“偏移量
物理地址=页面起始地址+页内偏移量
技巧
如果每个页面大小为2^kB,用二进制数表示逻辑地址，则末尾K为为页内偏移量，其余部分就是页号
逻辑地址结构
页号P
如果有M位表示“页号”，则说明该系统中一个进程最多允许有2^K个页面
如果有K位表示“页内偏移量”，则说明该系统中有一个页面大小是2^k个内存单元
页内偏移量(页内地址)W
如果有K位表示“页内偏移量”，则说明该系统中有一个页面大小是2^k个内存单元
页表
概念
OS为每个进程建立一张页表，了解每个页面在内存中的存放的位置
一个进程对应一张页表
进程的每一页对应一个页表项
每个页表项由“页号”和“块号”组成
页表记录进程页面和实际存放内存块之间的对应关系
每个页表项的长度是相同的，页号是“隐含”的
两级页表
单机页表存在问题
所有页表项必须连续存放，页表过大时需要很大连续空间
在一段时间内并非所有的页面都用的到，因此没有必要让整个页表常驻内存
页目录表
两级页表
长长的页表再分页
逻辑地址结构(一级页号，二级页号，页内偏移量)
页目录表
多级页表
各级页表的大小不能超过一个页面
页目录表
页表相关
页目录表
外层页表
顶级页表
地址变换
按原地址结构将逻辑地址拆分成三部分
从PCB中都出页目录表地址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置
根据二级页号查表，找到最终要访问的内存块号
多闪页表
场景、位置、每场大小
分量页表
该表中内存、大小、用户空间
基本分段存储管理
段
段号
其位数决定每个进程最多可以分多少个段
段内地址
决定每个段的最大长度
2^n(n:位数)
段表
进程建立段映射表
特点
一次性
驻留性
局部性
文件管理
文件系统基础
用户接口
用户需通过OS提供的接口发出上述请求
文件目录系统
由于用户提供的是文件存放路径，因此需要OS一层一层查找目录，找到对应目录项
存取控制模块
不同用户对文件有不同的操作权限，为保证安全，需检查用户是否有访问权限
逻辑文件系统与文件信息缓冲区
验证用户的访问权后，需把用户提供的“记录号”转变为对应的逻辑地址
文件系统实现
文件块、磁盘块
文件的逻辑地址(逻块号、块内地址)
连续分配
每个文件在磁盘上占有一组连续的块
物理块号=起始块号+逻辑块号
优点
支持
顺序访问
随机访问(直接访问 )
连续分配的文件在顺序读/写时速度最快
顺序访问
缺点
物理上采用连续分配不方便连续文件拓展
产生磁盘碎片
紧凑法
链接分配
隐式链接
优点
方便文件拓展
不会产生外部碎片
外存利用率高
缺点
只支持顺序访问，不支持随机访问
指向下一个盘块的指针需耗费少量存储空间
效率低
显示链接
优点
文件分配表FAT
用于链接文件各物理块的指针显示的存放在一张表中
支持
顺序访问
随机访问
相比隐式链接
访问速度快很多
缺点
文件分配表占用存储空间
索引分配
定义
允许文件离散的分配在各个磁盘块
系统为每个文件建立一张索引表
索引表记录各个逻辑块对应低的物理块
索引块
存放的磁盘块称为索引块
数据块
文件数据存放的磁盘块称为数据块
优点
只支持随机访问
文件拓展容易实现
需给文件分配一个空闲块
增加一个索引表项
缺点
占用一定的存储空间
磁盘组织管理
存储空间划分与初始化
划分
将物理磁盘划分为一个个文件卷(逻辑卷)
文件卷(逻辑卷
初始化
将各文件卷划分为目录区、文件区
目录区
存放文件目录FCB
文件目录
空闲表
位示图
超级块
文件区
存放文件目录
管理方法
空闲表发
分配磁盘块
分配时可采用首次适应、最佳适应等策略
回收时注意表项合并问题
空闲链表发
空闲盘块链
以盘块为单位组成一条空闲链
分配时从链头依次取出空闲块
回收时将空闲块查到链尾
空闲盘区链
以盘区为单位组成一条空闲链
分配时可采用首次适应、最佳适应等策略
位示图
一个二进制位对应一个盘块 (字号、位号)或(行号、列号)与盘块一一对应
推出盘块号一>(字号、位号)或(行号、列号)之间的相互转换公式
成组链接法
UNIX采用的策略
适合大型文件系统
单道、多道之间批处理没有交互能力思维导图模板大纲
查看更多
相似思维导图模版
首页
我的文件
我的团队
个人中心