导图社区 操作系统
- 137
- 14
- 0
- 举报
操作系统
操作系统的东西，文件，进程等。需要可以下载。
编辑于2021-03-13 16:15:14
- 相似推荐
- 大纲
操作系统
调度与死锁
调度类型
高级调度（作业调度）
低级调度（进程调度）
中级调度（对换）
调度的准则
CPU使用量
吞吐量
周转时间
等待时间
响应时间
截止时间保证
调度算法
先来先服务调度算法（FCFS）
最简单的CPU调度算法，可以通过FIFO就队列实现
平均等待时间很长
非抢占式，如果CPU分配到了一个进程，那么该进程就会使用CPU直到释放CPU或者是请求I/O
短作业优先调度算法（SJF）
SJF算法可以是抢占式也可以是非抢占式的
这个算法将每个进程与其下次CPU执行的长度关联起来
时间片轮转调度算法（RR）
为分时系统设计
增加了抢占以切换进程
时间量或者时间片是比较小的时间单元
RR算法性能很大程度取决于时间片的大小，极端情况下，如果时间片很大，那么RR算法就会退化成为FCFS算法，如果时间片很小，那么就会导致大量的上下文切换
优先级调度算法
静态优先级
动态优先级
非抢占式
抢占式
响应比高者优先
多级队列调度算法
将就绪队列分成单独的队列
根据进程的属性去设置优先级
采用固定优先级抢占调度
多级反馈队列算法
最通用的CPU调度算法
比较复杂
思想很简单，前几个调度的合成
死锁
基本概念
多个进程因为竞争资源而产生的一种僵死状态。若无外力推动，这些进程将无法继续执行
原因
资源不足
进程推进顺序非法
必要条件
互斥使用
请求并保持（不释放）
非剥脱条件（非抢占）
环路等待（循环等待）
处理方法
预防死锁
避免死锁
检测死锁
解除死锁
避免死锁的算法
银行家算法
概念
安全序列
是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和
安全状态
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态
安全状态一定是没有死锁发生
不安全状态
不存在一个安全序列
不安全状态不一定导致死锁
数据结构
可利用资源向量Available
是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目
最大需求矩阵Max
一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求
分配矩阵Allocation
一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数
需求矩阵Need
一个n×m的矩阵，用以表示每一个进程尚需的各类资源数
三者关系
Need[i,j]=Max[i,j]-Allocation[i,j]
银行家算法计算图例
计算图例
操作系统简介
定义
管理计算机资源并且控制程序执行的系统软件
目标
方便
有效
可扩充
开放
发展
发展史
无OS
单批道处理系统
多批道处理
分时系统
特点
多路性
独立性
及时性
交互性
实时系统
特点
实时响应并安全可靠
特点
每一次发展，都是把CPU释放出来，让其能更好地专注于CPU要做的事情
基本特征
并发性
最基本的特征
共享性
虚拟性
逻辑对应用户，物理对应真实
异步性
不确定，由并发引起的
主要功能
处理机管理
进程调度
进程控制
进程同步
进程通信
存储器管理
内存分配
内存保护
地址映射
内存扩充
接口
命令
图形
文件管理
文件共享
文件目录
文件操作
外存分配
设备管理
虚拟设备
缓冲区管理
设备控制
设备分配
进程的描述和控制
程序特点
顺序执行
封闭性
顺序性
可再现性
并发执行
失去封闭性
间断性
不可再现性
程序和进程的关系
进程
进程是动态的
进程是暂时的
有生命周期
进程=P+D+PCB
特征
动态性
独立性
并发
异步
结构特征PCB
三种状态
就绪态
执行态
阻塞态
图视
占用的两种形式
目态（用户）
管态（系统）
程序
程序是静态的
程序是永久的
进程的一部分
PCB 进程控制块
定义
操作系统核心中的一种数据结构
主要表示进程状态
作用
使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位或与其他进程并发执行的进程
唯一表示
两种组织形式
链接方式
索引方式
六个原语
创建原语
终止原语
阻塞原语
唤醒原语
挂起原语
激活原语
进程创建的过程
1、申请空白PCB
2、申请必要资源（P、D=>M）
3、初始化PCB
4、插入到就绪队列
进程终止的过程
1、进程执行态，调度下一个
2、进程其他状态，队列移除
3、终止子孙进程
4、归还资源
5、归还PCB(PCB插入到空白队列中)
线程
目的
提高并发度
缺点
加大开销
又称轻型进程（进程=P（Program）+D（Data）+PCB）
作业
定义
用户在一次解题或一个事物处理过程中要求计算机系统所做工作的集合
作业是由一系列有序的步骤组成的
图例
作业的图视
作业、进程、程序的关系
作业是宏观的
进程是微观的
程序是静态的
进程是动态的
存储器管理
别称
主存
内存
两大部分
系统区
用户区
主要目标
为用户提供方便、安全和充分大的存储器
划分形式
连续
非连续
虚拟
内存分配的主要目的
提高内存的利用率
地址映射
定义
逻辑地址到物理地址的转换
三种
固定的地方映射
可装不同的地方，装入后不可动
不仅仅能装入不同的地方，装入后可动
程序装入方式
绝对装入（固定的地方装入）
软件实现
可从定位装入（装入时完成）
软件实现
动态装入（动态运行时装入）
硬件实现
内存分配算法
首次适应算法
特点
倾向于内存中的低地址部分的空闲区，在高地址部分的空闲区很少被用到
优点
为以后达到的大作业分配大的内存控件创造了条件
缺点
低地址部分经常使用并且不断划分，留下了许多难以利用的小空间
每次都是从地址的最低位开始寻找，增加开销
循环首次适应算法
特点
全部的内存都可以利用到，不倾向于高低位地址
优点
比较快
比较均衡
缺点
不利于大作业
最佳适应算法
特点
每次分配给文件的都是最合适该文件大小的分区
优点
大小适中，片内碎片少
缺点
片外碎片多，而且难以利用
最坏适应算法
特点
尽可能地利用存储器中大的分区
优点
使剩下的空闲分区不至于太小
产生碎片的几率最小
对中小作业有利
查询效率很高
缺点
会使存储器中缺乏大的空闲分区
绝大多数的时候会造成资源浪费或者是完全无法实现分配
回收算法
占用区的四种情况
上占下占
解决
新增一个分区
上空下占
解决
改上空区的长度
上占下空
解决
改下空区的起始地址和长度
上空下空
解决
改上区的长度，“三合一”，删除下分区
解决内存分配问题以及外部碎片问题的方案
允许物理地址控件为非连续的
四种具体方案
分页式存储管理
思想
把用户的地址控件划分成若干个固定大小的区域，成为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等
优点
没有外碎片，每个内碎片不超过页的大小
缺点
程序全部装入内存，增加了机器的成本和系统开销
分页式管理机制图
分段式存储管理
思想
将用户程序地址空间分成若干个大小不等的端，每段可定义一组相对完整的逻辑信息。分配时以段为单位分配
优点
方便用户编程
分段保护，分段共享，动态增加
便于动态链接
缺点
会产生内碎片
分段式管理机制图
端页式存储管理
思想
利用分段的方法来分配和管理虚拟存储器，利用分页的方法来分配和管理实际内存
优点
分页式存储管理和分段式存储管理的优点总和
缺点
复杂性和开销增加，需要硬件
占用的内存增加，速度下降
端页式管理机制图
虚拟存储器
特征
多次性
对换性
作用
将用户地址空间中的逻辑地址映射为内存空间中的物理地址
访问字段
1、页号
2、物理块号
3、存取控制
4、状态位
程序访问时用到
5、访问字段
选择换出页面
6、修改位
换出页面是否重写
7、外存地址
换入页
实现的形式
请求分页系统
页面置换算法
FIFO（先进先出）
简述
和生活中的排队类似
算法步骤
把一个进程已调入内存的页面按先后次序链接成一个队列
设置一个指针，称为替换指针
使指针总是指向最老的页面
LRU（最近最久未使用）
简述
认为最近最长时间未访问过的页面不会再访问，在将来的一段时间内也不会访问，故淘汰页面
淘汰页面时，选择现有页面中的值最大从而淘汰
算法步骤
建立一个特殊的栈
如果栈为满的情况且最新元素不在栈中，选择最底部的弹出
如果栈中存在着相同的元素，那么把这个元素提到栈顶
LFU（最近最少未使用）
OPT(最佳置换页面算法) 不可实现
请求分段系统
地址转换机制
设备管理
结构
四级结构三级控制
设备控制图
解释
CPU，中央处理器
CH，通道
CO，控制器
K、M、T、P，设备
分类
根据速度分类
高速设备
中速设备
低速设备
根据输入输出划分
输入设备
输出设备
根据传输单位去划分
字符型传输设备
块传输设备
根据使用的属性划分
独占设备
共享设备
虚拟设备
设备控制器的主要功能
进行数据交换（DR）
接受识别命令（CR）
反馈状态（CR）
按址识别
缓冲功能
差错处理功能
通道
别称
外围处理机
I/O处理机
与CPU的关系
CPU有复杂的指令系统，有自己的存储器，CPU与CH并行工作
CH 指令系统单一，无存储器，CH受控CPU
DMA（直接存储器访问）
目的
为了解决批量数据的输入/输出问题
工作方式图
I/O分配算法
所需的数据结构
设备控制表（DCT）
记录本设备的情况
控制器控制表（COCT）
记录了控制器的忙碌状态
通道控制表（CHCT）
记录了通道的忙碌
记录了与通道相连的控制器表的部分信息
系统控制表（SDT）
记录了系统中全部设备的情况
流程图
申请设备流程图
删除设备流程图
释放设备流程图
缓冲区
种类
单缓冲
双缓冲
循环缓冲
缓冲池
缓冲区功能
缓解CPU与I/O速度上的差异
减少中断次数
提高CPU与I/O并发度
I/O软件结构
1、用户
2、应用程序
3、设备独立程序
4、设备驱动程序
5、中断处理程序
四层
6、设备
设备独立性
简述
应用程序独立于具体使用的物理设备。为了实现设备独立性而引入了逻辑设备和物理设备这两个概念。在应用程序中，使用逻辑设备名称来请求使用某类设备
而在系统实际执行时，还必须使用物理设备名称。因此，系统须具有将逻辑设备名称转换为某物理设备名称的功能
优点
易于实现设备的重定向
用户和物理的外围设备无关，系统增减或变更外围设备时不必修改
易于对付输入输出设备的故障
提高了系统的可靠性
增加了外围设备分配的灵活性，能更有效地利用外围设备资源，实现多道程序设计技术
虚拟设备
通过虚拟技术，将一台独占设备虚拟成多台逻辑设备，供多个用户进程同时使用
文件
描述
外存上的唯一的数据结构，并且具有文件名的一组相关信息的集合
名词解释
成组：把n个逻辑记录放在一个物理记录中
分解：把一个逻辑记录从屋里记录中拆分出来
分类
逻辑结构
流式文件（无结构）
记录式文件（有结构）
定长记录（顺序）
变长记录（索引）
按照用途分类
系统文件
用户文件
库文件
按照文件中数据的形式划分
源文件
目标文件
可执行文件
文件的组织形式
顺序文件
文件中的记录可以随意
按照串结构或者顺序结构进行排列组合
存取效率式所有的逻辑文件中最高的
顺序结构：通常是按照关键字进行排列的
索引文件
对于边长记录的文件，会建立一张索引表。索引表式定长记录的顺序文件
索引文件图
索引顺序文件
克服了边长记录不便于直接存储的缺点
是顺序文件和索引文件相组合的产物
索引顺序文件图
直接文件
给定关键字进行定位是，直接获得指定关键字的物理地址
关键字本身存有物理地址
哈希文件
倒排
利用哈希值，将记录转换为相应记录的地址
文件目录
定义
是由一组文件目录项组成的
每个目录项是记录某个文件的名字、存放地址以及其他有关文件说明信息和控制信息的数据结构
设计要求
1、按名存取
2、提高对目录检索的速度
3、文件共享
4、允许文件重名
文件控制块PCB
1、文件名
2、文件物理地址
3、文件逻辑结构
4、用户名
5、文件长度
6、文件类型
7、文件建立日期以及时间
8、文件最近修改时间
9、文件连接计数
文件管理中的组织形式
单极目录
两级目录
多级属性目录
磁盘管理
什么是磁盘
磁盘是利用磁记录技术存储数据的存储器
计算机主要的存储介质
可以存储大量的二进制数据
断电后能够保持数据不丢失
磁盘性能决定
寻道时间
旋转延迟
传输时间
磁盘调度算法
先来先服务（FCFS）
最基本的磁盘调度算法
根据进程请求访问磁盘的先后次序进行调度
公平、简单，且每个进程都能一次地得到处理，不会出现某一进程的请求长期得不到满足的情况
此算法由于未对寻道进行优化，导致平均寻道时间可能较长
最短寻道时间优先（SSTF）
在移动磁头到别处以便处理其他请求之前，处理靠近当前磁头位置的所有请求可能较为合理
大大提高了性能
是一种短作业优先调度
可能会导致饥饿请求
扫描算法
双向扫描（SCAN，电梯调度）
磁臂从磁头的一端开始，向另一端移动。到达另一端后，磁头反转，继续处理
如果请求刚好在磁头前进方向的前方，能够马上处理
如果请求在磁头的后方，必须等待，直到磁头反转
单向扫描（循环扫描 C-SCAN）
是双向扫描调度的一个变种
提供更加均匀的等待时间
从一段扫向另一端，到达另一端时，立即返回最初的位置，依次如此扫描
磁盘符合较大的系统比较适合的算法
不太会造成饥饿的问题
N步扫描
当N=1时，简化为FCFS算法
当N=∞时，转化为SCAN算法
FSCAN
外存
外存分配方式
连续分配
要求
每个文件在磁盘上占有一组连续的块
连续分配图例
链接分配
分类
隐式链接
显式链接
简述
链接分配解决了连续分配的所有问题
每个文件时磁盘块的链表
只能访问用于顺序访问文件
不能有效支持文件的直接访问
链接分配图视
索引分配（索引文件）
类别
单级索引
多级索引
多级混合索引（UNIX）
简述
解决了连续分配的外部碎片和大小
通过将所有指针放在一块，解决了链接分配高效的直接访问
索引分配图视
空闲空间管理
空闲区表法
空闲链表法
位视图法
分配
回收
成组链接法
分配
回收
同步与通信
简介
临界资源：一段时间内只允许一进程访问的资源
临界区：程序中涉及到临界资源的代码段
同步基本概念
同步也称为直接制约关系
同步指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而等待、传递信息所产生制约关系
进程间的直接制约关系就是源于他们之间的相互合作
准则
空闲让进
忙则等待
有限等待
让权等待
利用软件实现互斥
两个标志位
一个指针
利用硬件实现互斥
加锁
信号量
简介
又称为信号灯
多线程环境下使用的一种设施，可以用来保证两个或多个关键代码段不被并发调用
是一种卓有成效的进程互斥同步工具
分类
整型信号量
仅能通过两个标准的原子操作wait 和signal
记录型信号量
采取了“让权等待”策略
是一种不存在“忙等”现象的进程同步机制
经典的同步问题
生产者消费者问题
读者写者问题
哲学家就餐问题