3. 进程调度与死锁

• ​调度动机与时机

  • 功能

    • ​按某种算法从就绪态进程为当前CPU选择其上运行的新进程

  • ​时机

    • ​进程结束

    • ​进程阻塞

    • ​中断返回

    • ​更高优先级的进程到来

    • ​当前运行进程的时间片用完

• ​进程切换 7步

  • ​1.保存pc,和其他寄存器的cpu上下文环境

  • ​2.更新被替换的进程的pcb

  • ​3.修改进程状态，把之形态改为就绪态

  • ​4.被替换进程的PCB移到就绪或阻塞队列

  • ​5.执行新进程，更新该进程的PCB

  • ​6.更新内存管理的数据结构

  • ​7.恢复被调度程序选中的进程的硬件上下文

• ​调度算法

  • ​选择依据

    • ​周转时间短

    • ​响应时间快

    • ​截止时间的保证

    • ​吞吐量高

    • ​处理机利用率好

  • ​算法类型

    • ​1.先来先服务

      • ​优点：

        • ​利于长进程

        • ​利于CPU繁忙型进程（科学计算）

      • ​缺点：

        • ​不利于短进程

        • ​系统平均周转时间比较长

    • ​2.短进程优先

      • ​优点：

        • ​降低进程的平均等待时间

        • ​提高系统的吞吐量

      • ​缺点：

        • ​不利于长进程

        • ​不能保证紧迫进程及时处理

        • ​进程长短根据用户的估计而定，不一定真正做到短进程优先

    • ​3.优先权调度

      • ​算法类型

        • ​非抢占式

        • ​抢占式

      • ​优先权类型

        • ​静态优先权

        • ​动态优先权

      • ​问题与方案

        • ​无穷阻塞（饥饿）

        • ​老化技术

    • ​4.时间片轮转

      • ​时间片大小确定

        • ​响应时间的要求

        • ​就绪队列中进程数量

        • ​系统的处理能力

    • ​5.多级队列调度

      • ​将就绪队列分为多个独立队列（永久不可变）

        • ​进程某些属性

        • ​占内存大小

        • ​进程优先权

        • ​进程类型

    • ​6.多级反馈队列调度

      • ​优先权越高，时间片越短

      • ​等待时间长的进程会被转移到优先级高的就绪队列

• ​实时系统的调度

  • ​基本条件

    • ​1、提供必要的调度信息

      • ​就绪时间

      • ​开始截止时间和完成截止时间

      • ​处理时间

      • ​资源要求

      • ​优先级

    • ​2. 系统处理能力强

    • ​3.采用抢占式调度机制

      • ​基于始终中断抢占

      • ​立即抢占

    • ​4.具有快速切换机制

      • ​对外部中断的快速响应能力

      • ​快速的进程切换能力

  • ​常用调度算法

    • ​最早截止时间有限EDF

    • ​最低松弛度优先 LLF

• ​死锁

  • ​产生原因

    • ​竞争共享资源

    • ​分配资源的顺序不当

  • ​必要条件

    • ​互斥条件

    • ​请求和保持

    • ​不剥夺

    • ​环路等待

  • ​处理死锁

    • ​预防死锁

      • ​摒弃三分之一个必要条件

    • ​避免死锁

      • ​安全状态

      • ​不安全状态

      • ​银行家算法

    • ​检测并解除死锁

      • ​何时调用

        • ​死锁可能发生的频率

        • ​死锁发生时受影响的进程数量

      • ​死锁定理

        • ​用于检测资源分配状态S是否为死锁状态

        • ​当前仅当S状态的资源分配图是不可完全简化的

      • ​死锁的解除

        • ​终止进程

          • ​1.终止所有死锁进程

          • ​2.一次只终止一个处于死锁的进程

        • ​资源抢占

          • ​1.抢占哪个进程和哪些资源？

            • ​死锁进程所拥有的资源数量

          • ​2.回滚

            • ​回滚到某个安全状态

          • ​3.饥饿

            • 进程因长时间不能获得所需要的资源而无线等待

    • ​忽略死锁

• ​多处理器调度

  • ​类型

    • ​耦合度

      • ​紧耦合

        • ​共享主存储器系统 I/O设备

      • ​松耦合

        • ​每台都有自己的存储器和I/O

        • ​通过通道或通信线路来实现多台计算机间互连

    • ​对称

      • ​对称

        • ​结构类似

      • ​非对称

        • ​一主多从

  • ​进程分配方式

    • ​对称

      • ​静态分配

        • ​为每个处理器建立一个专门的就绪队列

        • ​一个进程只在一个处理器上运行

        • ​优点

          • ​调度开销小

        • ​缺点

          • ​不能动态的平衡各处理器的负载，忙闲不均

      • ​动态分配

        • ​每次进程调度获取的不是一个处理器

        • ​设置公共就绪队列

      • ​优点

        • ​考虑了负载平衡

        • ​把进程分给当前空闲的处理器

    • ​非对称

      • ​主机上调度程序，从机上用户程序

      • ​优点

        • ​系统处理比较简单

      • ​缺点

        • ​单点问题

  • ​进程调度方式

    • ​自调度

      • ​优点

        • ​易移植

        • ​cpu利用率高

      • ​缺点

        • ​瓶颈问题

        • ​低效性

        • ​线程切换频繁

    • ​成组调度

      • ​讲一组相互合作的线程或进程分配到一组处理器上

      • ​优点

        • ​减少线程切换，提高性能

        • ​减少调度开销

      • ​时间分配

        • ​面向所有的应用程序平均分

        • ​面向所有的线程平均分

    • ​专用处理器分配

      • ​每个线程一个专用处理器

      • ​一个进程一组专用处理器

      • ​优点

        • ​加速了应用程序的运行速度

        • ​避免了进程切换

      • ​缺点

        • ​浪费资源