导图社区 算法
这是一篇关于算法的思维导图,主要内容包括:云计算,内存管理算法,分布式同步算法,避免死锁算法,进程调度算法,磁盘调度算法。
编辑于2025-06-27 11:51:46这是一篇关于程序和库信息的思维导图,主要内容包括:(查看基础信息),获取ELF节的长度信息,显示可执行文件或库需要静态加载的动态库完整列表--显示加载时的依赖项,列出二进制文件的节信息,查看动态节,列出并查看段,查看重定位节,反汇编,列出库中未定义的符号,列出动态符号,列出二进制文件或库的符号表,查看节中的数据,符号的类型。
这是一篇关于设备驱动的思维导图,主要内容包括:主要功能,设备驱动模型。阐述了设备驱动的主要功能、信号定义、设备驱动模型等内容。
这是一篇关于算法的思维导图,主要内容包括:云计算,内存管理算法,分布式同步算法,避免死锁算法,进程调度算法,磁盘调度算法。
社区模板帮助中心,点此进入>>
这是一篇关于程序和库信息的思维导图,主要内容包括:(查看基础信息),获取ELF节的长度信息,显示可执行文件或库需要静态加载的动态库完整列表--显示加载时的依赖项,列出二进制文件的节信息,查看动态节,列出并查看段,查看重定位节,反汇编,列出库中未定义的符号,列出动态符号,列出二进制文件或库的符号表,查看节中的数据,符号的类型。
这是一篇关于设备驱动的思维导图,主要内容包括:主要功能,设备驱动模型。阐述了设备驱动的主要功能、信号定义、设备驱动模型等内容。
这是一篇关于算法的思维导图,主要内容包括:云计算,内存管理算法,分布式同步算法,避免死锁算法,进程调度算法,磁盘调度算法。
算法
云计算
动态迁移
预拷贝Pre-copy
首次同步:将源虚拟机内存全量复制到目标主机; 循环同步:监控内存变化,每次仅复制修改过的页面(脏页),直到脏页生成速度 < 复制速度
停机拷贝Stop-and-Copy
暂停源虚拟机,复制最后一批脏页,同步 CPU 状态(寄存器、进程调度信息) 目标主机启动虚拟机,恢复网络连接(通过 MAC 地址漂移技术保持 IP 不变)
内存管理算法
分区管理算法
固定分区分配算法
将内存划分成若干个固定大小的分区,每个分区大小可以不同 但在系统运行期间保持不变 当有进程需要内存时,系统为其分配一个大小合适的空闲分区 如果没有合适大小的空闲分区,则进程等待
实现简单,管理开销小
容易产生内部碎片(每个分区内未被利用的空间) 内存利用率低
可变分区分配算法
首次适应算法
从内存的低地址开始查找,找到第一个能满足进程大小的空闲分区,将其分配给进程 分配后,若该空闲分区还有剩余空间,则将剩余部分作为新的空闲分区
简单且速度较快,倾向于使用低地址部分的空闲分区 保留高地址部分的大空闲分区,有利于后续大进程的分配
低地址部分会逐渐产生许多小的空闲分区,导致后续查找合适空闲分区的时间增加 且容易使高地址部分的大空闲分区长期闲置
最佳适应算法
遍历所有空闲分区,选择大小最接近且能满足进程需求的空闲分区进行分配 同样,分配后若有剩余空间,将其作为新的空闲分区
能尽量避免大材小用,减少内存碎片的产生,使内存资源得到更充分的利用
每次分配都需要遍历所有空闲分区,查找开销大 而且会产生大量难以利用的小碎片,因为每次都尽量选择最小的满足条件的分区 随着时间推移,这些小碎片可能无法满足任何新进程的需求
最坏适应算法
与最佳适应算法相反,它选择最大的空闲分区来分配给进程 这样做的目的是使分配后剩余的空闲分区也尽可能大,以便能满足后续较大进程的需求
对于大进程的分配较为有利,不容易因为没有足够大的连续空闲空间而导致分配失败
会迅速耗尽大的空闲分区,使内存空间很快碎片化,导致后续小进程也难以找到合适的空闲分区,而且每次查找最大空闲分区也有一定开销
分页管理算法
基本分页存储管理
将进程的逻辑地址空间划分为大小相等的页(Page) 把内存的物理地址空间划分为与页大小相同的块(Frame,也称为页框) 进程的页离散地存储在内存的页框中 通过页表(Page Table)来记录页与页框之间的映射关系 当进程访问某个逻辑地址时,系统通过页表将其转换为物理地址
有效地解决了碎片问题,提高了内存利用率。因为页的大小固定 进程可以按照页为单位离散地存储在内存中,减少了内部碎片
增加了系统开销,因为需要维护页表 并且每次内存访问都需要查询页表进行地址转换,这会降低内存访问速度
请求分页存储管理
在基本分页的基础上,引入了虚拟内存的概念 进程在运行时,只有部分页面装入内存 当访问到不在内存中的页面时,产生缺页中断 操作系统根据一定的置换算法,将内存中的某一页换出到外存 再将需要的页面从外存调入内存
进一步提高了内存利用率 使得系统能够运行比实际内存大得多的进程,实现了虚拟内存功能
缺页中断处理开销较大,需要进行页面置换操作 涉及 I/O 操作,会影响系统性能 同时,置换算法的选择对系统性能有较大影响
分段管理算法
基本分段存储管理
将进程的逻辑地址空间按照程序的逻辑结构划分为若干个段(Segment) 每个段大小可以不同,例如代码段、数据段、栈段等 每个段都有自己的段号和段内偏移地址 系统为每个进程维护一个段表(Segment Table) 用于记录段的起始地址和段长度等信息 当进程访问某个逻辑地址时,通过段表将逻辑地址转换为物理地址
符合程序的逻辑结构,便于程序的模块化设计和共享 例如可以将共享代码放在一个单独的段中,多个进程可以共享该段
容易产生外部碎片(内存空间中不连续的空闲块) 因为段的大小不固定,随着进程的创建和撤销 内存空间会变得碎片化 导致难以找到足够大的连续空闲空间来分配给新的段
段页式存储管理
结合了分页和分段的优点,先将进程的逻辑地址空间按逻辑结构划分为若干个段 然后再将每个段划分为若干个页,内存空间同样划分为页框 系统为每个进程维护一个段表和多个页表 段表记录段与页表的对应关系 页表记录页与页框的映射关系 地址转换时,先通过段表找到对应的页表,再通过页表将逻辑地址转换为物理地址
既具有分段系统的逻辑清晰、便于共享和保护的优点 又具有分页系统能有效解决碎片问题、提高内存利用率的优点
地址转换过程复杂 需要多次访问内存 先访问段表,再访问页表,最后访问内存中的数据 增加了系统开销
页面置换算法
OPT最佳置换算法
选择在未来最长时间内不会被访问的页面进行置换
FIFO先进先出置换算法
择最先进入内存的页面进行置换 维护一个先进先出的页面队列,当需要置换页面时,置换队首的页面
LRU最近最久未使用置换算法
选择最近一段时间内最久未被访问的页面进行置换 它基于一个假设,即过去一段时间内未被访问的页面,在未来一段时间内也不太可能被访问
LFU最少使用页面置换算法
为内存中的每个页面设置一个移位寄存器 用于记录该页被访问的频率 该算法会将在最近时期使用最少的页面作为淘汰页
NRU时钟置换算法
将所有页面组织成一个环形链表,类似于时钟的指针 每个页面设置一个访问位(R 位),当页面被访问时,R 位设置为 1 当需要置换页面时,从当前指针位置开始扫描环形链表, 找到第一个 R 位为 0 的页面进行置换, 并将经过的 R 位为 1 的页面的 R 位清 0 如果一轮扫描下来所有页面的 R 位都为 1, 则重新开始扫描,直到找到 R 位为 0 的页面 A=0,M=0:{该页最近既未被访问 又未被修改 是最佳淘汰页} A=0,M=1:{该页最近未被访问 但已被修改 并不是很好的淘汰页} A=1,M=0:{该页最近已被访问 但未被修改 该页有可能再被访问} A=1,M=1:{该页最近已经被访问且被修改 该页有可能再被访问}
改进型时钟算法
简单的时钟置换算法仅考虑到一个页面最近是否被访问过 事实上,如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存 只有被淘汰的页面被修改过时,才需要写回外存 除了考虑一个页面最近有没有被访问过之外,操作系统还应考虑页面有没有被修改过 在其他条件都相同时,应优先淘汰没有修改过的页面,避免I/O操作
其他暂定
资源图分配算法(allocator)
2的幂次方空闲链表算法
McKusick-Karels分配算法
伙伴系统(Buddy)
Mach的区域Zone分配算法
Dynix分配算法
Solaris的Slab分配算法
分布式同步算法
面包房算法
利用事件排序的方法对要求访问临界资源的全部事件进行排序 按照FCFS原则对事件进行处理
基本假设
系统由N个节点组成 每个节点只有一个进程 仅负责控制一种临界资源 并处理那些同时到达的请求
每个进程保持一个队列 用来记录本节点最近收到的消息 以及本节点自己产生的消息
消息分为请求消息 应答消息和撤销消息 系统会根据事件时序对每个进程队列中的请求消息进行排序 进程队列初始为空
进程Pi发送的消息形式为request(Ti,i) Ti=Ci代表进程Pi发送此消息时对应的逻辑时钟值 i代表消息内容
算法描述
当进程Pi请求资源时 他把请求消息request(Ti,i)排在自己的请求队列中 同时也把该消息发给系统中的其他进程
当进程Pj接收到外来消息request(Ti,i)后 发送应答消息reply(Tj,j)并把request(Ti,i)放入自己的请求队列
若满足条件: 1.Pi自身请求访问该资源的消息已处于请求队列的最前面 2.Pi已收到从所有其他进程发来的应答消息 这些消息的时间戳都晚于(Ti,i) 则允许进程Pi访问该资源
为了释放该资源 Pi从自己的队列撤销请求消息 并发送一个打上时间戳的释放消息release给其他进程
当进程Pj收到Pi的释放消息release后 撤销自己队列中的原Pi的request(Ti,i)消息
令牌环算法
首先会将所有进程组成一个逻辑环(logical ring) 然后在系统中会设置一个象征存取权力的令牌 该令牌(token)是一种特定格式的报文 其在进程所组成的逻辑环中不断循环传递 只有获得该令牌的进程才有权力进入临界区 访问共享资源 令牌在初始化后 会被随机赋予逻辑环中的一个进程 令牌在逻辑环循环传递时 会以点对点的方式按照固定的方向和顺序 从一个进程依次逐个传递到另一个进程 当一个进程获得令牌时 如果不需要访问共享资源 则会将令牌继续传递下去 否则 保持令牌并对共享资源进行检查 如果共享资源空闲 则进入临界区进行访问 访问结束并退出临界区后再将令牌继续传递下去 进程利用令牌 每次只能访问一次共享资源
避免死锁算法
银行家算法
每个新进程在进入系统时 其都必须申明其在运行过程中可能需要每种资源类型的最大单元数 该数目不应该超过系统所拥有的最大资源总量 当进程请求一组资源时 系统必须首先确定是否有足够的资源可分配给该进程 若有 则进一步计算在将这些资源分配给该进程后 系统是否会处于不安全状态 如果不会 则将资源分配给该进程 否则让该进程等待
数据结构 Need[i,j]=Max[i,j]-Allocation[i,j]
可利用资源向量Available
每个元素代表一类可利用的资源数目 其初值是系统中所配置的该类全部可用资源的数目 该数目会随对应资源的分配和回收动态改变 Available[j]=k 表示系统中现有R[j]类资源k个
最大需求矩阵Max
n*m的矩阵 定义了系统中n个进程中每个进程对m类资源的最大需求 Max[i,j]=k 表示进程i需要R[j]类资源的最大数目为k
分配矩阵Allocation
n*m矩阵 定义了系统中每类资源当前已经分配给每一个进程的资源数 Allocation[i,j]=k 表示进程i当前已分得R[j]类资源的数目为k
需求矩阵Need
n*m矩阵 用于表示每个进程尚需的各类资源数 Need[i,j]=k表示进程i还需要R[j]类资源k个方能完成其任务
算法流程
Request[i]是进程P[i]的请求向量 Request[i][j]=k 表示进程P[i]需要K个R[j]类型的资源 当前P[i]发出请求时 会进行如下检查 (1)如果Request[i][j]>Need[i][j] 则出错 因为它所需要的资源数已经超过了它所宣布的最大值 (2)如果Request[i][j]>Available[j] 表示尚无足够资源 P[i]需等待 (3)系统试图把资源分配给进程P[i] Available[j]=Available[j] - Request[i][j]; Allocation[i][j]=Allocation[i][j]+Request[i][j]; Need[i,j]=Need[i,j] - Request[i][j]; (4)系统执行安全性算法 检查此次资源分配后系统是否处于安全状态(就是得有安全序列) 若是 则正式将资源分配给进程P[i] 完成本次分配 若否 则将本次试探分配作废 恢复原来的资源分配状态 让进程P[i]等待
资源预分配算法
资源预分配算法要求进程在运行前一次性申请所需的全部资源 系统只有在能够满足进程所有资源需求时,才会为其分配资源并允许进程运行 如果资源不足,进程就只能等待
死锁检测与解除算法
死锁检测与解除算法并不预防死锁的发生,而是定期检查系统是否发生死锁 当检测到死锁时,通过剥夺某些进程的资源来解除死锁
进程调度算法
目标: 1.资源利用率 2.公平性 3.平衡性
先来先服务调度算法FCFS
短作业优先调度算法SJF
SJF调度算法时以作业长短来计算优先级的 作业越短 优先级越高 当把SJF调度算法用于作业调度时: 它将从外存的作业后备队列中选择估计运行时间最短的作业并优先把它调入内存运行 当把SJF调度算法用于进程调度时: 它将从就绪队列中选择估计运行时间最短的进程 并为之分配CPU运行
优先级调度算法
基于进程的紧迫程度 由外部赋予进程响应的优先级 会根据该优先级进行调度 可以保证紧迫性高的进程优先运行 当把该算法用于作业调度时: 系统从后备队列中选择优先级最高的作业装入内存 当把该算法用于进程调度时: 系统将从就绪队列中选择具有最高优先级的进程在CPU上运行
子类
非抢占式优先级调度算法
一旦把处理机分配给就绪队列中优先级最高的进程 该进程便会一直执行下去直到完成或因发生某事件而放弃处理机 系统才可以将处理机重新分配
抢占式优先级调度算法
在把处理机分配给优先级最高的进程并使之执行时 只要出现另一个优先级更高的进程 调度程序就会将处理机分配给信道的优先级更高的进程
高响应比优先级调度算法HRRN
优先级=(等待时间+要求服务时间)/要求服务时间 1.如果作业的等待时间相同 则要求服务时间越短 优先级越高(有利于短作业) 2.当作业的要求服务时间相同时 优先级取决于等待时间 3.对长作业的优先级 其可随等待时间的增加而提高(作业的等待时间足够长时 也可获得处理机)
优先级
静态优先级
在创建进程时确定的 在进程的整个运行期间保持不变
动态优先级
在创建进程之初 先赋予进程一个优先级 然后优先级会随进程的推进或等待时间增加而改变 以获得更好的调度性能
批处理系统
轮转调度算法RR
基于时间片轮转的调度算法
基本原理
系统会将所有的就绪进程按FCFS策略排成一个就绪队列 系统可以设置每隔一定时间便产生一次中断 去激活调度程序进行调度 把处理机分配给队首进程 并令其执行一个时间片 当它运行完后 在把处理机分配给就绪队列中新的队首进程 同样让它也执行一个时间片 这样 就可以保证就绪队列中的所有进程在确定的时间段内 都能获得一个时间片的处理机时间
进程切换的时机
1.若一个时间片尚未用完而进程便已完成 则立即激活调度程序 将已经运行完成的进程从就绪队列中删除 在调度就绪队列中新的队首进程运行 2.当一个时间片用完 计时器中断程序就会激活 此时如果进程尚未运行完毕 调度程序就把它送往就绪队列的末尾
多级队列调度算法
多级队列调度算法将系统中的进程就绪队列从一个拆分成若干个 将不同类型或性质的进程固定分配在不同的就绪队列 不同的就绪队列采用不同的调度算法 一个就绪队列中的进程可以设置不同的优先级 不同的就绪队列本身也可设置不同的优先级
多级反馈队列调度算法
调度机制
1.设置多个不同优先级的就绪队列 按优先级排序
2.每个队列都采用FCFS调度算法
当新进程进入内存后 首先将它放入第一个队列的末尾 按FCFS策略等待调度 当轮到该进程执行时 如果它能在该时间片内完成 则可撤离系统 否则 调度程序将其转入第二个队列的末尾等待调度 如果在它在第二个队列中运行一个时间片后仍未完成 则放入第三个队列 一次类推 当进程最后被降到第n队列后 在第n队列便采取RR方式运行
3.按队列优先级调度
调度程序首先调度最高优先级队列中的各进程运行 仅当第一队列空闲时 才调度第二队列中的进程运行 依次类推 如果处理器在第i队列中未某进程服务时 又有新进程进入任一优先级较高的队列 则须立即把正在运行的进程放回到第i队列的末尾 并把处理机分配给新到的高优先级进程
基于公平原则的调度算法
保证调度算法(针对每个进程的公平性)
1.跟踪计算每个进程自创以来已经执行的处理时间 2.计算每个进程应获得的处理机时间(自创建以来的时间/n个进程) 3.计算进程获得处理机的时间比率(时机执行时机/应获得处理机时机) 4.比较个进程获得处理机时机的比率 5.调度程序应选择比率最小的进程 将处理机分配给它 并让它一直运行 直到比率超过次小的进程为止
公平分享调度算法(针对用户的公平性)
完全公平调度器CFS调度算法
CFS 的核心思想是公平地分配 CPU 时间给各个进程,避免进程饥饿 它基于 “完全公平” 的原则,即每个进程应该按照其权重(weight)比例获得 CPU 时间 权重反映了进程的相对优先级,权重越高的进程应获得更多的 CPU 时间 为了实现公平调度,CFS 引入了虚拟时间(virtual time)的概念 每个进程都有自己的虚拟时间,虚拟时间的推进速度与进程的权重成反比 权重高的进程,其虚拟时间推进速度慢;权重低的进程,虚拟时间推进速度快 通过比较进程的虚拟时间,CFS 总是选择虚拟时间最小的进程运行, 确保每个进程按照权重比例公平地获得 CPU 时间
最早截止时间优先算法EDF
根据任务的截止时间确定任务的优先级 任务的截止时间越早 其优先级越高 具有最早截止时间的任务排在队列的前面 调度程序在选择任务时 总是选择就绪队列的第一个任务 并为之分配处理机
最低松弛度优先算法LLF
根据任务的紧急程度确定任务的优先级 任务的紧急程度越高 赋予该任务的优先级就越高 以使其可以被优先执行 松弛度=必须完成时间点-本身运行时长-当前时间点 松弛度最低的任务排在就绪队列的最前面 调度程序会选择队首任务执行 松弛度为0时会开始抢占
分时系统
非抢占式优先级调度算法
一旦把处理机分配给就绪队列中优先级最高的进程 该进程便会一直执行下去直到完成或因发生某事件而放弃处理机 系统才可以将处理机重新分配
抢占式优先级调度算法
在把处理机分配给优先级最高的进程并使之执行时 只要出现另一个优先级更高的进程 调度程序就会将处理机分配给信道的优先级更高的进程
抢占原则
优先级
短进程优先
时间片
资源需求原则
实时任务原则
实时系统
调度性能评估
任务流时间
把完成任务所需的时间定义为任务流时间
调度流时间
一个调度流时间等于系统中所有处理机上的任务流时间总合
平均流时间
平均流时间等于调度流时间除以任务数
处理机利用率
处理机利用率等于该处理机上任务流时间之和除以最大有效时间单位
加速比
加速比等于各处理机的忙时间之和除以并行工作时间
吞吐率
单位时间内系统完成的任务数
磁盘调度算法
FCFS调度算法
SSTF调度算法
SCAN调度算法
CSCAN调度算法
NStepSCAN调度算法
FSCAN调度算法