文章目录一、本文知识覆盖范围1、知识意义2、知识体系概览二、前趋图进程依赖关系的图形化表示1、前趋图基本概念2、前趋图结构分析3、PV操作实现前趋图三、死锁理论系统资源竞争的核心问题1、死锁的四大必要条件2、死锁预防策略3、死锁避免银行家算法4、 死锁最小资源数计算四、银行家算法动态资源分配的核心技术1、银行家算法基本原理2、安全状态检查机制3、资源分配决策过程4、 习题五、总结一、本文知识覆盖范围1、知识意义前趋图与银行家算法是操作系统中的核心同步与死锁处理技术它们解决了多进程并发执行中的关键问题前趋图解决进程间执行顺序控制问题确保依赖关系的进程按正确顺序执行避免数据竞争和逻辑错误银行家算法解决资源分配中的死锁预防问题通过动态资源分配策略避免系统陷入死锁状态具体应用场景数据库事务处理中的依赖关系管理分布式系统中的任务调度云计算平台的资源分配实时系统中的任务优先级控制2、知识体系概览知识模块具体内容学习重点前趋图基础前趋关系定义、前趋图结构、DAG特性理解进程依赖关系掌握图形化表示方法PV操作机制信号量设置、P操作检查、V操作通知掌握进程同步的底层实现原理死锁理论四大必要条件、死锁预防、死锁避免理解死锁产生机制掌握预防策略银行家算法安全状态检查、资源分配原则、算法实现掌握动态资源分配和死锁避免技术二、前趋图进程依赖关系的图形化表示本章节将详细讲解前趋图的基本概念、结构特征和实际应用帮助读者掌握进程间依赖关系的表示和管理方法。1、前趋图基本概念概念定义前趋图Precedence Graph是一种有向无环图DAG用于表示进程、程序段或语句之间的执行先后顺序关系。核心特征特征定义与特点具体实例无环性图中不存在闭环路径保证进程可按顺序完成如编译过程中的词法分析→语法分析→语义分析部分排序提供进程的部分排序无直接依赖的可并行执行如Web服务器中用户认证和日志记录可并行有向边箭头表示前趋关系从a指向b表示a必须在b之前完成如数据库事务中先写日志再提交事务实际例子编译系统词法分析→语法分析→语义分析→代码生成→优化Web应用用户登录→权限验证→业务处理→结果返回数据处理数据采集→数据清洗→数据转换→数据分析→结果输出适用场景多进程系统的任务调度工作流引擎的设计并行计算中的任务依赖管理数据库事务的依赖控制2、前趋图结构分析概念定义前趋图由节点和有向边组成节点代表进程或任务有向边代表前趋关系。核心特征结构元素定义与特点具体实例起始进程没有前趋的进程可以立即开始执行如系统启动时的初始化进程终结进程没有后继的进程执行完成后整个流程结束如批处理作业的最终输出进程前趋关系箭头数量表示依赖关系的数量如一个复杂任务可能有多个前置条件实际例子电商订单处理流程 订单创建(A) → 库存检查(B) → 支付处理(C) → 订单确认(D) → 发货通知(E)适用场景业务流程建模系统架构设计任务调度算法设计并行计算优化3、PV操作实现前趋图概念定义PV操作是操作系统提供的进程同步原语P操作用于检查资源V操作用于释放资源并通知等待进程。pvp代表资源等待方检查资源使用方是否使用完v代表资源使用方释放资源。信号量初值实现并发时信号量初值常为0 前趋图中有几个前趋关系箭头一般就设置几个信号量。核心特征P 操作也叫 “等待操作”wait作用是申请资源。执行 P 操作时信号量的值减 1若结果 ≥ 0说明能获取资源进程可继续执行若结果 0说明资源不足进程会被阻塞进入等待队列。V 操作也叫 “释放操作”signal作用是释放资源。执行 V 操作时信号量的值加 1若结果 ≤ 0说明有进程在等待该资源会唤醒等待队列中的一个进程若结果 0说明无进程等待仅更新信号量值。S代表信号量Semaphore是操作系统中的一种同步原语用于进程间的同步和互斥控制。初值为0表示初始状态下没有资源可用需要等待前趋进程完成适用场景进程间同步控制资源访问控制临界区保护条件等待机制### 1、依赖关系识别 从前趋图可以看出存在以下**4个直接依赖关系** | 依赖关系 | 含义 | 信号量 | |:-------|:-------|:-------| | P1 → P2 | P1完成后P2才能开始 | S1 | | P1 → P3 | P1完成后P3才能开始 | S2 | | P2 → P4 | P2完成后P4才能开始 | S4 | | P3 → P4 | P3完成后P4才能开始 | S5 | ### 2、进程特征分析 - **起始进程**P1没有前趋 - **终结进程**P4没有后继 - **并行进程**P2和P3都依赖P1可以并行执行 ## 三、信号量设计原理 ### 1、为什么需要5个信号量 **标准情况**4个依赖关系需要4个信号量 **实际情况**题目要求5个信号量原因如下 | 信号量 | 管理依赖 | 使用位置 | 作用 | |:-------|:-------|:-------|:-------| | S1 | P1→P2 | P1完成P2开始 | 确保P1完成后P2才能开始 | | S2 | P1→P3 | P1完成P3开始 | 确保P1完成后P3才能开始 | | S3 | P3→P2 | P3完成P2开始 | 确保P2等待P3完成隐式依赖 | | S4 | P2→P4 | P2完成P4开始 | 确保P2完成后P4才能开始 | | S5 | P3→P4 | P3完成P4开始 | 确保P3完成后P4才能开始 | ### 2、S3的特殊作用 **关键理解**S3实现了P3→P2的隐式依赖这意味着 - P2必须等待P3完成后才能继续执行 - 实际执行顺序变为P1 → P3 → P2 → P4 - 这超出了前趋图显示的显式依赖关系 ## 四、PV操作实现 ### 1、正确答案分析 **点a, b, c的操作** - **点a**V(S1)V(S2) - P1完成后通知P2和P3 - **点b**P(S1)P(S3) - P2等待P1和P3完成 - **点c**V(S4) - P2完成后通知P4 **点d, e, f的操作** - **点d**P(S2) - P3等待P1完成 - **点e**V(S3)V(S5) - P3完成后通知P2和P4 - **点f**P(S4)P(S5) - P4等待P2和P3完成 ### 2、执行流程 1. P1执行 → V(S1)V(S2)通知P2和P3 2. P3执行 → V(S3)V(S5)通知P2和P4 3. P2执行 → V(S4)通知P4 4. P4执行 → 完成所有任务三、死锁理论系统资源竞争的核心问题本章节将深入讲解死锁的产生机制、必要条件以及预防和避免策略帮助读者理解并解决系统资源竞争问题。1、死锁的四大必要条件概念定义死锁是指多个进程因竞争资源而造成的一种僵局当进程都在等待对方释放资源时系统无法继续执行。核心特征必要条件定义与特点具体实例互斥条件资源不能被多个进程同时使用如打印机、数据库连接、文件锁等独占资源保持和等待进程持有资源的同时请求其他资源如进程A持有打印机同时请求扫描仪不剥夺条件系统不能强行剥夺进程已持有的资源如操作系统不能强制释放进程的内存环路等待多个进程形成资源请求的循环等待如A等BB等CC等A的循环依赖实际例子死锁场景两个进程竞争两个资源 进程A请求资源1 → 获得资源1 → 请求资源2 → 等待 进程B请求资源2 → 获得资源2 → 请求资源1 → 等待 结果A等待B释放资源2B等待A释放资源1形成死锁适用场景多线程程序调试数据库事务管理分布式系统设计资源池管理2、死锁预防策略概念定义死锁预防是通过打破死锁的四大必要条件来防止死锁发生的方法。核心特征预防策略定义与特点具体实例打破互斥允许资源同时被多个进程访问如只读文件可以被多个进程同时访问打破保持等待要求进程一次性申请所有资源如数据库事务的原子性要求打破不剥夺允许系统剥夺进程资源如操作系统的内存回收机制打破环路等待按固定顺序申请资源如给资源编号按编号顺序申请3、死锁避免银行家算法概念定义死锁避免是在资源分配时动态检查系统是否处于安全状态避免进入可能导致死锁的状态。核心特征算法要素定义与特点具体实例安全状态存在安全序列能使所有进程顺利完成如系统能找到一种资源分配顺序让所有进程完成资源请求检查分配前检查是否会导致不安全状态如检查分配后是否还能找到安全序列动态分配根据当前系统状态决定是否分配资源如根据可用资源和进程需求动态决策实际例子银行家算法示例 系统资源总共有10个资源 进程A最大需求7个已分配2个还需5个 进程B最大需求5个已分配3个还需2个 进程C最大需求8个已分配2个还需6个 当前可用资源10-2-3-23个 安全序列检查B(需2个) → A(需5个) → C(需6个) 分配给B两个运行完35分配给A后满足a的需求 A完成后(释放给c)可用628个满足C的6个需求4、 死锁最小资源数计算题目核心要点死锁条件公式系统资源数 进程数 × (进程所需资源数 - 1) 1计算结果3个进程每个需要5个资源系统至少需要13个资源才能避免死锁系统状态分类[0,4]必定死锁[5,12]可能死锁[13,∞)不可能死锁银行家算法作用通过动态检查确保系统处于安全状态避免死锁发生四、银行家算法动态资源分配的核心技术本章节将详细讲解银行家算法的原理、实现方法和实际应用帮助读者掌握动态资源分配和死锁避免技术。1、银行家算法基本原理概念定义银行家算法是一种经典的死锁避免算法通过模拟资源分配过程确保系统始终处于安全状态。资源分配原则算法原则定义与特点具体实例进程接纳原则进程最大需求量不超过系统资源数如系统有100个资源进程最大需求不能超过100个资源请求原则进程请求总数不能超过最大需求量如进程最大需求10个累计请求不能超过10个延迟分配原则资源不足时可推迟分配但保证有限时间内获得如等待其他进程释放资源后再分配2、安全状态检查机制概念定义安全状态是指系统存在一个安全序列能够使所有进程按此序列执行并最终完成。核心特征检查要素定义与特点具体实例安全序列进程执行的顺序每个进程都能获得所需资源如P1→P3→P0→P2→P4的执行顺序资源可用性当前可用资源能否满足某个进程的需求如可用资源[3,3,2]能否满足进程需求[1,2,2]资源回收进程完成后释放的资源能否满足后续进程如进程完成后释放的资源加入可用资源池3、资源分配决策过程概念定义资源分配决策是在进程请求资源时通过银行家算法检查分配后系统是否仍处于安全状态。核心特征决策步骤定义与特点具体实例请求检查检查请求是否超过进程最大需求如进程最大需求5个请求6个则拒绝资源可用性检查系统是否有足够资源满足请求如请求3个资源系统只有2个则等待安全状态模拟模拟分配后的系统状态是否安全如分配后能否找到安全序列让所有进程完成4、 习题五、总结核心知识点回顾前趋图通过DAG表示进程依赖关系使用PV操作实现进程同步确保任务按正确顺序执行死锁理论理解死锁的四大必要条件掌握预防和避免策略保证系统稳定运行银行家算法通过安全状态检查实现动态资源分配有效避免死锁发生不同场景的技术选择建议应用场景推荐技术选择理由实施要点Web应用并发控制前趋图信号量控制请求处理顺序避免数据竞争使用Redis实现分布式信号量数据库连接池管理银行家算法动态分配连接避免连接耗尽实现连接池的安全状态检查分布式任务调度前趋图DAG调度管理任务依赖支持并行执行使用Apache Airflow等工具实时系统资源管理银行家算法优先级保证关键任务资源避免死锁实现基于优先级的资源分配