操作系统第三章PPT.ppt

实例 Allocation A B C Need A B C Available A B C p0 0 3 0 7 2 3 2 1 0 p1 3 0 2 0 2 0 p2 3 0 2 6 0 0 p3 2 1 1 0 1 1 p4 0 0 2 4 3 1 为P0分配（0，2，0）后的情况（不安全） 死锁的检测和解除 检测 资源分配图 p1 p2 死锁检测 简化资源分配图 (1)在图中,找出既非阻塞又非独立的进程节点Pi (2)削去Pi的请求边和分配边 (3)Goto (1) 直至所有节点被处理 若能消去所有的边,使所有进程为孤立节点,则图为可完全简化的。 死锁定理： 死锁状态的充分条件，资源分配图不可完全简化 work= available L:={Li| alloci=0 reqi=0} (孤立进程点) For all Li L do Begin For all reqi =work do Begin work=work+alloci L=Li∪L end End Deadlock= ~(L={p1 … pn}) 死锁检测算法 死锁解除 检测到死锁后，两种解除死锁策略 回退到上一状态,进行资源剥夺 需保存以前状态的分配信息 重新分配资源，若不行，继续回退……， 撤消进程,直到死锁解除 * 基于时间片的轮转调度算法 多运用于分时系统中 两种策略 时间片轮转 多级反馈队列调度 时间片轮转 系统根据按时间片轮流调度进程 时间片大小的确定 太大：退化为FCFS 太小：系统开销过大 系统对进程的响应时间 T=nq； q为时间片,n为就绪队列中进程的数目； 系统的处理能力 应保证一个时间片处理完常用命令 多级反馈队列调度 设置多个就绪队列，为每个队列设定不同的优先级 第一个队列优先级最高，其他依次递减 优先级越高的队列、每个时间片越短 第 i+1个队列的时间片长是第i个队列的2倍 新进程进入内存后，首先加入第一队列队尾，按FCFS等待调度 第一轮结束后，若进程未结束，则加入第二队列，依此类推 仅当第一队列空闲时，才会调度第二队列进程运行，依此类推 就绪队列1 至CPU S1 就绪队列2 S2 至CPU 就绪队列3 S3 至CPU 就绪队列n Sn 至CPU 时间片：S1S2S3 多级队列反馈调度算法 多级队列反馈调度算法特点 长、短作业兼顾，有较好的响应时间 短作业一次完成； 中型作业周转时间不长； 大型作业不会长期不处理 实时调度 实现实时调度的基本条件 提供必要的调度信息 就绪时间、开始/完成截止时间、处理时间、资源要求、优先级； 系统处理能力强 满足限制条件 m:周期性实时任务 Ci:处理时间 Pi:周期时间 N:处理器数目 实现实时调度的基本条件 采用抢占调度方式 剥夺方式 非剥夺方式 实现简单 一般实时任务较小，以及时放弃CPU 具有快速切换机制 具有快速响应外部中断能力。 快速任务分派 实时调度算法的分类 非抢占式调度算法 时间片轮转 秒级 非抢占优先权（协同） 秒~毫秒级 抢占式调度算法 时钟中断抢占优先权 毫秒级 基于抢占点抢占 立即抢占 毫秒~微秒级 只要不在临界区即抢占（中断引发） 进程1 进程2 进程n 实时进程 调度时间 实时进程要求调度 调度实时进程运行 a 非抢占轮转调度 当前进程 实时进程 实时进程要求调度 当前进程运行完成 b 非抢占优先权调度 调度时间 c 基于时钟中断抢占的优先权抢占调度 当前进程 实时进程 实时进程要求调度 抢占时刻（其它中断） b 立即抢占优先权调度 当前进程 实时进程 实时进程要求调度 时钟中断到达时 调度时间 调度时间 常用的几种实时调度算法 最早截止时间优先EDF（earliest deadline first)算法 根据任务的截止时间来确定任务的优先级 截止时间越早，优先级越高 可以是抢占式或非抢占式 最早截止时间优先EDF例 1 3 4 2 1 3 4 2 1 2 3 4 t 开始截止时间 任务到达 任务执行 EDF算法用于非抢占调度方式 最低松弛度优先LLF算法 松弛度 若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90 主要用于可抢占的调度方式中 例：A的执行周期为20ms,执行时间10ms B的执行周期为50ms,执行时间25m