OS知识点
2020-01-06 11:08:48 0 举报AI智能生成
计算机操作系统思维导图
作者其他创作
大纲/内容
OS主要功能
处理机管理功能
进程创建
进程同步
进程通信
调度
层次
低级调度
中级调度
高级调度
目标
CPU利用率
CPU的用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
周转时间
（作业）周转时间=作业完成时间-作业提交时间
平均周转时间
平均周转时间=各作业周转时间之和/作业数
带权周转时间
T=作业周转时间/作业实际运行的时间=(作业完成时间−作业提交时间)/作业实际运行的时间
带权平均周转时间
平均带权周转时间=各作业带权周转时间之和/作业数
吞吐量
系统吞吐量=总共完成了少道作业/总共花了多少时间
响应时间
等待时间+要求服务时间
算法
先来先服务
规则
到达的先后顺序进行服务
用于作业/进程调度
作业后备队列
进程就绪队列
优点
公平简单
缺点
短进程不利
短作业优先
规则
最短的作业/进程优先得到服务
用于作业/进程调度
短作业优先
短进程优先
优点
平均等待时间短
平均周转时间短
缺点
短作业有利
实际使用时难以估计时间
高响应比优先
规则
计算响应比
Rp=(等待时间+要求服务时间)/要求服务时间= 响应时间/要求服务时间
用于作业/进程调度
均可
优点
等待服务时间相同，要求服务时间短的优先（SJF的优点）
服务时间相同，等待时间长的优先（FCFS的优点）
缺点
每次调度都需要计算响应比，系统开销大
轮转调度算法
规则
按照各进程到达就绪队列的顺序，轮流让各进程执行一个时间片
用于作业/进程调度
用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间）
优点
公平；响应快，适用于分时操作系统；
缺点
进程切换频率高，开销大
不区分任务的紧急程度
优先级调度算法
规则
每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
调度时机
抢占式
进程主动放弃处理机时进行调度
就绪队列发生变化 时，检查是否发生抢占，有就调度
非抢占式
进程主动放弃处理机时进行调度
用于作业/进程调度
均可
优点
区分紧急程度、重要程度
缺点
有可能导致饥饿（不断有高优先级进程到来）
多级反馈队列调度算法
规则
设置多级就绪队列
优先级从高到低
时间片从小到大
新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是最下级的队列，则重新放回该队列队尾
只有第k队列为空时，才会为k+1级队头的进程分配时间片
调度时机
FCFS
时间片轮转
抢占式
在k级队列的进程运行过程中，若更上级的队列（1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾
优点
各类进程相对公平（FCFS）
每个新到达的进程都可以很快得到响应（RR)
短进程只用较少的时间就可以完成（SPF)
不需要估计进程的运行时间
缺点
有可能会导致饥饿
基于公平原则的调度算法
保证调度算法
公平分享调度算法
实时调度算法
非抢占式调度算法
非抢占式轮转调度
非抢占式优先级调度
抢占式调度算法
基于时钟中断的抢占式优先级调度算法
立即抢占的优先级调度算法
最早截止时间优先EDF
最低松驰度优先算法（LLF)
松驰度 = 完成截止时间-本身（还需）运行的时间-当前时间
优先级倒置的解决算法
高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞
解决方法
方法一：（规定）假如进程P3在进入临界区后P3所占用的处理机就不允许被抢占。
方法二：（规定）当高优先级进程P1要进入临界区，去使用临界资源，如果已有一个低优先级进程P3正在使用该资源，此时一方面P1被阻塞，另一方面由P3继承P1的优先级，并一直保持到P3退出临界区。
死锁
死锁是什么
资源问题
竞争不可抢占资源引起死锁
竞争可消耗资源引起死锁
进程推进顺序不当引起的死锁
死锁发生条件
互斥条件
请求和保持条件
请求和保持：进程已经保持了至少一个资源，但又提出了新的资源请求，该 资源已被其它进程占有，此时请求进程被阻塞，但对自己已经获得的资源保持不放。
不可抢占条件
不可抢占：进程已获得的资源在未使用完不能被抢占，只能在进程使用完由自己释放。
循环等待条件
循环等待条件：存在一种进程资源的循环待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
处理死锁的方法
预防死锁
破坏“请求和保持”条件
第一种协议：开始运行之前，必须一次性地申请其在整个运行过程中所需要的全部资源。
第二种协议：允许一个进程只获得运行初期所需资源后，便开始运行。运行过程中逐步释放已分配给自己的、且已用完的全部资源，然后再请求新的资源。
破坏不可抢占条件
当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。
破坏循环等待条件
首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（编号相同的资源）一次申请完。
避免死锁
安全/不安全状态
如果系统按照这种序列分配资源，则每个进程都能顺利完成，只要能找出一个（多个）安全序列，系统就是安全状态。
利用银行家算法来避免死锁
数据结构
(1)可利用资源向量(Available)
(2)最大需求矩阵(Max)
(3)已分配矩阵(Allocation)
(4)需求矩阵(Need)
(5)进程请求向量(Request)
(6)工作向量(Work)
银行家算法
Request<=Need
Request<=Available
预分配
安全性算法
安全性算法
Work=Available
Need<=Work
Work = Work+Allocation
检测和解除死锁
死锁检测
（1）不阻塞、不孤立
（2）释放资源、继续运行
（3）消去所有边，使所有进程结点都成为孤立结点。
死锁解除
（1）抢占资源。
（2）终止（或撤消）进程
（3）进程回退
存储器管理功能
内存管理
内存分配和回收
程序的装入与链接
装入方式
静态装入
绝对地址
静态重定位装入
绝对地址
动态重定位
逻辑地址
运行时转换物理地址
链接
静态链接
对相对地址进行修改
变换外部调用 符号
装入时动态链接
优点
便于修改和更新
便于实现对目标模块的共享
运行时动态链接
优点
加快程序的装入过程
节省大量的内容空间
内存分配
碎片
内部碎片
分配给某进程的内存区域中没有用上的部分。
外部碎片
内存中的某些空闲分区由于太小而难以利用的部分。
连续分配管理
单一连续分配
方法
用户程序独占用户区
优点
实现简单
无外部碎片
不一定需要内存保护
缺点
利用率低
碎片
内部碎片
固定分区分配
方法
多道程序
程序间互不干扰
装入若干个固定大小的分区
分类
分区大小相等
优点
方便、实用
缺点
缺乏灵活性
分区大小不等
优点
增加了灵活性
缺点
浪费空间
碎片
无外部碎片
产生内部碎片
动态分区分配
数据结构记录内存
空闲分区表
空闲分区链
内存分区分配算法
分配操作
检索空闲分区链表
比较分区大小
有无事先规定的不再切割的剩余分区的大小
合适则修改数据结构
顺序式搜索算法
首次适应算法 （First fit，FF）
算法思想
从低地址寻找
流程
（1）空闲分区以地址递增的次序排列。
（2）每次分配内存的时候查找空闲分区链（表）
（3）找到后，划分内存空间并进行分配。
优点
优先利用内存中低址部分的空闲分区，保留了高址部分的大空间区。
缺点
低址部分不断被划分，留下很多碎片。
碎片
外部碎片
循环首次适应算法
算法思想
每次都从上次查找结束的位置开始检索。
流程
（1）空闲分区以地址递增的次序排列（可排成一个循环链表）。
（2）每次分配内存时从上次查找结束的位置开始查找空闲分区链区表）
（3）找到后，划分内存空间并进行分配。
优点
空闲分区分布更均匀，减少查找空闲分区的开销
缺点
缺乏大的空闲分区
碎片
外部碎片
最佳适应算法
算法思想
每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业。
流程
（1）空闲分区按容量递增次序链接。
（2）每次分配内存的时候查找空闲分区链（空闲分区表）
（3）找到后，划分内存空间并进行分配。
优点
缺点
每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。
碎片
外部碎片
最坏适应算法
算法思想
优先选择最大空闲区
流程
（1）空闲分区按容量递减次序链接。
（2）每次分配内存的时候查找空闲分区链（空闲分区表）
（3）找到大小能满足要求的第一个空闲分区。
优点
可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利。
查找效率高（排序：从大到小；查找：查第1分区即可）
缺点
导至较大的连续分区被迅速用完，有大进程进来的时候，就没有内存分区可用了。
碎片
外部碎片
索引式搜索算法
快速适应算法
又称为分类搜索法，将 空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表。同时，设立一张管理索引表，其中的每一个索引项对应一种空闲分区类型，并记录了该类型空闲分区链表表头的指针
优点
不会产生内存碎片、查换效率高。
缺点
系统开销大，存在空间浪费。
伙伴系统
无论已分配分区或空闲分区，其大小均为2的K次幂（k为整数，1≤k ≤m)。通常情况 下2m是整个可分配 内存的大小（最大分区的大小）。
哈希算法
利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。
动态可重定分区分配
紧凑
动态重定位
对换
类型
整体对换
页面（分段）对换
对换空间
文件区
特点
长时间驻留外存
访问频率低
目标
存储空间利用率
文件访问速度
分配方式
离散分配方式
对换区
特点
驻留外存时间短
操作频率高
目标
提高换入换出速度
提高存储空间利用率
分配方式
连续分配方式
非连续分配管理
基本分页存储管理方式
基本思想
建立进程与内存之间的对应关系
基本概念
页
块
地址结构
页面地址（位偏移量）
逻辑地址MOD 页面大小
页号
P=INT[逻辑地址/页面大小]
页表
页表项
页号
块号
基本地址变换机构
根据逻辑地址计算页号、偏移量
判断页号是否越界
页表项
页号
访问快表
查找页表项
页表始址+页号*页表项长度
计算物理地址
内存块号
偏移量
访问内存
计算
已知
页面大小
逻辑地址
物理地址
基本分段存储管理方式
基本思想
建立程序和内存之间的逻辑关系
基本概念
段内地址（段内偏移量）
段号（段名）
段表
段号
段长
基址
基本地址变换机构
根据逻辑地址得到段号、段内地址
判断段号是否越界
段号
段表长度
查询段表，找到对应的段表项
段表基址+段号*段表项长度
检查段内地址是否超过段长（越界中断）
计算得到物理地址
访问内存单元
分段和分页之间的区别
分支主题
段页式存储管理方式
基本思想
综合利用“页”和“段”的特点，即有页内存利用率高，又有的段的易于实现按逻辑模块实现共享和保护
基本概念
段号
段内页号
页内地址
地址变换机构
逻辑地址得到段号、页号、页内偏移量
判断段号是否会越界，如果段号S大于或等于段表长度M，则产生越界中断，否则继续执行。
查询段表，找到对应的段表项（段表地址=段表始址+段号*段表项长度
对给定页号和查找到的段表项中的页表长度进行比较，判断给定页号是否越界
根据页表存放的块号（页表始址）找到对应的页表项
根据页表项中存储的内存块号+页内地址形成物理地址
按物理地址访问内存
内存回收
回收区与插入点的前一个空闲分区相邻
回收区与插入点的后一个空闲分区相邻
回收区同时与插入点的前、后两个分区
回收区和前后空闲分区均不相邻
内存扩充
虚拟内存概念
常规存储器管理方式特征
一次性
驻留性
局部性原理
时间局限性
空间局限性
虚拟内存概念
最大容量
计算机的地址结构（CPU寻址范围）确定
实际容量
min（CPU寻址范围，内存+外存）确定
虚拟存储器的特征
多次性
对换性
虚拟性
虚拟存储器的实现方法
请求分页
请求页表机制
状态位
访问字段
修改位
外存地址
地址变换机构
1、检查页号是否越界
2、查找快表，如果命中的话，直接访问对应的物理地址。如果 没有命中，转入第3步。
3、根据页表寄存器的页表始址位置，找到请求页表在内存的位置。找到对应页表项后，若对应页面未调入内存，则产生缺页中断，之后由操作系统的缺页中断处理程序进行处理。
4、快表中的页面一定是在内存中的。若某个页面被换出外存，则快表中的相应表项也删除，否则可能访问错误的页面。
内存分配
内存分配策略
（1）固定分配局部置换
策略
数目不变，运行时不改变
现有物理块进行置换
（2）可变分配全局置换
策略
数目不定，运行时可增减
空闲物理块、其他进程（未锁定）
（3）可变分配局部置换
策略
数目不定，运行时可增减
现有物理块进行置换
调入策略
何时调入
（1）预调页策略
（2）请求调页策略
何处调入
（1）系统足够的对换区空间
（2）系统缺少足够的对换区空间
（3）UNIX调入过程
如何调入
内存满/没满
页面修改/没修改
页面置换算法
最佳置换算法
算法原则
以后永不使用的页面/最长（未来）时间内不再被访问的页面
先进先出置换算法
算法原则
淘汰最早进入内存的页面
belady现象
最近最久未使用置换算法
算法原则
选择最近最久未使用的页面予以淘汰。
寄存器
栈
时钟置换算法
（1）内存中所有页面通过链接指针接成一个循环队列。
（2）当某页被访问时，其访问位置1。
（3）选择淘汰页时，检查访问位。为0，则换出；为1，则重置为0。
（4）如果 循环一圈后未找到可换出页面，则再次循环。
改进型时钟置换算法
第一轮：从当前置换位置开始扫描到第一个（0，0）的页面用于替换。
本轮扫描不修改任何标志位。
第二轮：从当前置换位置开始扫描到第一个（0，1）的页面用于替换。
本轮将所有扫描过的页面访问位设为0。
第三轮：从当前置换位置开始扫描到第一个（0，0）的页面用于替换。
本轮扫描不修改任何标志位
第四轮：从当前置换位置开始扫描到第一个（0，1）的页面用于替换。
页面缓存算法
（1）空闲页面链表
（2）修改页面链表
请求分段
请求段表机制
存取方式
访问字段
修改位
外存地址
存在位
外存始址
磁盘管理
磁盘存储器的性能和调度
数据组织和格式
存储面
每个磁盘片分一个或两个存储面
磁道
每条磁道存储相同数目的二进制位
扇区（盘块/磁盘块）
每个扇区存放的数据量相同
内侧扇区密度大，外侧扇区密度小
磁盘类型
硬盘和软盘
单片盘和多片盘
固定头磁盘和活动头（移动头)磁盘
磁盘访问时间
寻道时间Ts
旋转延迟时间Tτ
1/2r
传输时间
b/rN
磁盘调度算法
FCFS
根据进程请求访问磁盘的先后次序进行调度
最短寻道时间优先（SSTF)
优先处理与当前磁头最近的磁道
扫描（SCAN)算法
循环扫描（CSCAN)算法
自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问磁道。
NStepSCAN
FSCAN
外存组织方式
连续组织方式
连续分配方式要求每个文件在磁盘上占有一组连续的块
优点
（1）顺序访问容易
（2）定长记录文件进行随机访问
物理块号=起始块号+逻辑块号
（3）顺序访问速度快
缺点
（1）要求为一个文件分配连续的存储空间
（2）必须事先知道文件的长度
（3）不能灵活地删除和插入记录
（4）难以满足文件动态增长的需求
链接组织方式
隐式链接
只支持顺序访问，不支持随机访问
指向下一个盘块的指针也占据存储空间
显式链接
把用于链接文件各物理块的指针显式地存放在内存的一张链接表中
FAT
FAT12
盘块为单位
位宽12位
盘块大小
FAT表项数
FAT占空间大小
最大磁盘容量
以簇为单位
FAT16
以簇为单位
位宽16位
簇大小
分区大小
最大分区大小
FAT32
以簇为单位
NTFS
以簇为单位
卷上簇的大小（卷因子）
逻辑簇号
卷因子*LCN=卷上物理字节偏移量
虚拟簇号
以文件为单位，将属于某个文件的簇按顺序进行编号
主控文件表
索引组织方式
单级索引组织方式
多级索引方式
增量式索引组织方式
直接寻址
一次间址
二次间址
三次间址
最大文件长度的计算
读写磁盘的次数
文件存储空间的管理
空闲表法
连续分配方式
序号
第一空闲块号
空闲盘块数
空闲链表法
离散分配方式
空闲盘块链
分配
释放
空闲盘区链
分配
释放
位示图法
成组链接法
组织
分配
回收
提高磁盘IO速度的途径
磁盘高速缓存
提高磁盘I/O速度的其它方法
廉价（独立）冗余阵列
提高磁盘可靠性的技术
第一级容错技术
第二级容错技术
基于集群的容错功能
后备系统
数据一致性控制
设备管理功能
文件管理功能
文件管理
文件系统
文件
元素
记录
数据项
基本数据项
组合数据项
文件名和扩展名
文件类型
按用途分
系统文件
用户文件
库文件
按源程序和数据的形式分
源文件
目标文件
可执行文件
按存取控制属生分
只执行文件
只读文件
读写文件
按组织形式和处理方式分
普通文件
目录文件
特殊文件
文件操作
创建
删除
读
写
设置文件的读写位置
文件系统的层次
对象及其属性
对对象操作和管理的软件集合
文件系统接口
文件的逻辑结构
是否有结构
有结构文件
定长记录
所有记录的长度都是相同的
所有记录上的各数据项都处在记录上相同的位置，具有相同的数据和长度
文件的长度用记录数目表示
变长记录
各记录的长度不相同
无结构文件
文件的长度以字节为单位
文件的组织方式
顺序文件
由一系列记录按某种顺序排列形成的文件
顺序文件的排列方式
串结构
按存入时间的先后进行排序
记录之间的顺序与关键字无关
顺序结构
由用户指定一个字段作为关键字，由关键字来标识一条记录
关键字
关键字可为任意类型
每个记录的关键字是唯一的
记录按关键字排序
可采用多种方式（折半查找、插值查找...)提高查找效率。
优点
存取效率高
适合批量存储
缺点
查找或修改单个记录的性能差
增删记录困难
记录寻址
隐式寻址
显式寻址
索引文件
为可变长记录文件建立一张索引表，每个记录对应一个表项
优点
提高了文件的查找速度
插入、删除记录非常方便
缺点
存储开销大
索引顺序文件
为每个文件建立一张索引表，每个索引表项对应一组记录中的第一个记录。
文件目录
要求
实现“按名存取”
提高对目录的检索速度
文件共享
允许文件重名
文件控制块
基本信息
存取控制信息类
使用信息类
索引结点
单级文件目录
只建立一张目录表
从要求来看
实现
按名存储
查找速度慢
不允许重名
不便于实现文件共享
两级文件目录
组成
主文件目录MFD
用户文件目录UFD
从要求来看
提高了检索目录的速度
在不同的用户目录中，可以使用相同的文件名
不同用户还可以不同的文件访问系统中的同一共享文件
树形目录（多级目录 ）
组成
根目录 （主目录 ）
树的结点（子目录）
对叶（数据文件）
路径名
当前目录
相对路径名
绝对路径名
目录操作
创建目录
删除目录
改变目录
移动目录
链接操作
查找
目录查询
线性检索
单级目录
树形目录
Hash方法
文件共享
其于有向无循环图实现文件共享
索引结点
符号链接
优点
避免了删除共享文件后遗留悬空指针的情况
可以通过网络链接到其他系统中的文件
缺点
文件访问开销大，增加了启动磁盘的频率
链接本身也是文件，需要配置索引结点，要耗费一定的磁盘空间
文件保护
人为因素
通过存取控制机制
保护域
域是进程对一组对象访问权的集合
进程与域 的连接关系
静态
动态
访问权
一个进程能对某对象执行操作的权力称为访问权
有序对（对象名，权集）
访问矩阵
行代表域
列代表对象
每一项是一组访问权组成
访问矩阵修改
拷贝权
改变同一列
所有权
改变同一列
控制权
改变同一行
访问矩阵实现
访问控制表
按对象划分
访问权限表
按域划分
系统因素
采取系统容错技术
自然因素
建立后备系统
操作系统与用户之间接口
基本概念
0 条评论
下一页
