处理机的调度和死锁.ppt

3.4.3进程（线程）调度方式 1.自调度 各个处理机自行在就绪队列中取任务。 特点；简单，分布式调度，调度算法可采用前述方法，多个CPU利用率都不错（不会闲） 但： 瓶颈问题，（单队列） 低效性；（需拷贝现场） 线程切换频繁（当线程合作时,各线程并行的条件不容易满足） 2.成组调度 优点： （1）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。 （2）每次分配一组CPU，减少了调度频率。 分配时间 （1）面向程序 （2）面向线程：使处理机利用率更高。 2.成组调度 应用程序A 应用程序B Cpu1 线程1 线程1 Cpu2 线程2 空闲 Cpu3 线程3 空闲 Cpu4 线程4 空闲 时间 1/2 1/2 浪费37.5% 应用程序A 应用程序B Cpu1 线程1 线程1 Cpu2 线程2 空闲 Cpu3 线程3 空闲 Cpu4 线程4 空闲 时间 4/5 1/5 浪费15% 3.专用处理机分配 引入：多处理机系统，每个处理已不再属宝贵资源。 特点：每个进（线）程专用处理机，使其切换小，提高效率。 主要用于大型计算，实时系统 3.5产生死锁的原因和必要条件 3.5.1产生死锁的原因。 一、竞争资源引起死锁。 1．可剥夺（CPU、内存，）和非剥夺性（打印机，磁带机）资源 2．竞争非剥夺性资源——可造成死锁 p1 p2 R1 R2 3.5产生死锁的原因和必要条件 3．竞争临时性资源 临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。 二、进程推进顺序不当引起死锁。 2 1 3 D P2Req(R2) P2Req(R1) P1Req(R1) P1Req(R2) P2Rel(R2) P2Rel(R1) P1Rel(R1) P1Rel(R2) 4 3.5.2 产生死锁的必要条件 1．互斥条件（资源的临界性） 2．请求和保持条件 3．不剥夺条件 4．环路等待 3.5.3处理死锁的基本方法 1．预防；破坏4个条件之一：有效，使资源利用率低。 2．避免：防止进入不安全态。 3．检测：检测到死锁再清除。 4．解除：与“检”配套。 3.6 死锁预防和避免 3.6.1 死锁预防 一、互斥条件是资源固有属性，不能避免。 二、摒弃请求和保持条件 全分配，全释放（AND） 缺点：（1）延迟进程运行 （2）资源严重浪费 三、摒弃“不剥夺”条件 增加系统开销，且进程前段工作可能失效。 3.6 死锁预防和避免 3.6.1 死锁预防 四、摒弃“环路”条件 有序资源分配法：为资源编号，申请时需按编号进行。 缺点： （1）新增资源不便，（原序号已排定） （2）用户不自由 （3）资源与进程使用顺序不同造成浪费 3.6.2 系统的安全状态 在“避免死锁”方法中的判断条件 1. 安全状态 按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。 能找到安全序列的状态为安全状态。 3.6.2 系统的安全状态（2） 2.安全状态例 进程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 安全序列：p2?p1?p3 3.6.2 系统的安全状态（3） 3安全——不安全的转换 上例中，若P3再申请一台，则不安全 进程 最大需求 已分配 可用 P1 10 5 2 P2 4 2 P3 9 3 3.6.3利用银行家算法避免死锁 1．数据结构 available[j]=k: 系统现有Rj类资源k个； max[i,j]=k: 进程i需要Rj的最大数k个； alloc[i,j]=k: 进程i已得到Rj类资源k个； need[i,j]=k: 进程i需要Rj类资源k个 有：need[i,j]= max[i,j]－alloc[i,j] requesti 进程i请求资源数 worki：进程i执行完后系统应有资源数（也即可用数） finish[i]：布尔量，表进程i能否顺序完成。 3.6.3利用银行家算法避免死锁 2．银行家算法 reqi=needi error reqi=availi block 3.6.3利用银行家算法避免死锁 avail=avail-reqi alloci=alloci+reqi needi=needi-reqi finish[i]=.F. needi=work work=work+alloci finish[i]=.T. 4实例 Max A B C Allocation A B C Need A B C Available A B C p0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0)