处理机调度与死锁

这是一篇关于处理机调度与死锁的思维导图，处理机调度与死锁是操作系统资源管理中的两个核心问题，前者负责合理分配CPU资源，后者需避免进程因资源竞争陷入僵局。

处理机调度与死锁

• 处理机调度
  • 处理机调度概述
    • 基本概念
      • 调度本质是一种资源分配，处理机调度是对处理机资源进行分配
    • 层次
      • 高级调度
        • 调度对象是作业，又称为长程调度或者是作业调度
      • 中级调度
        • 又称为内存调度，，实际上就是存储器管理中的对换功能
      • 低级调度
        • 调度对象是进程，又称为进程调度或者是短程调度
      • 不同调度之间的比较：短程调度的运行频率最高；作业调度的运行时间最长；中程调度在这两方面则是位于两者中间
    • 调度算法的目标
      • 公平性，高效性，响应时间，吞吐量
      • 几个重要概念
        • CPU的资源利用率=忙碌时间/总时间
        • 周转时间=作业完成时间-作业提交时间
        • 等待时间=周转时间-运行时间
        • 平均周转时间=各个作业周转时间之和/作业数
        • 带权周转时间=作业周转时间/作业实际运行时间
        • 平均带权周转时间=各个作业平均带权周转时间之和/作业数
        • 系统吞吐量=总共完成作业数/总时间
  • 调度算法
    • 先来先服务调度算法（FCFS）
      • 基本思想：按照作业到达的先后顺序进行服务
      • 特点：非抢占式，实现简单但平均等待时间较长，不会引起饥饿
      • 优点与缺点：优点是公平且简单；缺点是对长作业有利，对短作业不利
      • 适用场景：批处理系统
    • 短作业优先调度算法（SJF）
      • 基本思想：优先调度估计运行时间最短的作业/进程
      • 特点：可证明是最优的平均等待时间算法，但难以准确估计作业长度，抢占式，会引起饥饿
      • 优点与缺点：优点是最短的平均等待时间和最短的平均周转时间，对短作业有利；缺点是对长作业不利，必须预支作业的运行时间，人机无法交互，完全不考虑作业紧急程度，不能保证紧迫性作业得到及时处理。
    • 优先级调度算法
      • 高响应比优先调度算法(HRRN)
        • 基本思想：为每个作业引入优先级（这里又称为优先相应比=（等待时间+要求服务时间）/要求服务时间），根据优先级决定作业的执行顺序
        • 特点：既考虑了作业等待时间，又考虑到作业运行时间，非抢占式，不会引起饥饿
        • 优点与缺点：优点是对上面两种算法进行了折中；缺点是每次进行调度前都要进行响应比的计算，会增加系统开销。
    • 轮转调度算法(RR)
      • 基本思想：根据先来先策略，让就绪队列上的每个进程每次仅运行一个时间片，即产生一次中断，如果就绪队列上有n个进程，则 每个进程大约都可获得1/n个处理机时间。（在分时系统中，最简单的且最常见的就是时间片轮转算法）
      • 时间片的设置和性能分析是关键
      • 优缺点：优点是公平，响应时间有保障，适合交互式系统；缺点是时间片设置不当会影响效率，切换开销大。
    • 多级队列调度算法
      • 基本思想是将进程按类型或特性划分到不同的队列，各队列有不同的调度算法。
      • 优缺点：优点是可针对不同类型进程优化调度；缺点是队列划分和算法选择需谨慎。
    • 多级反馈队列调度算法(FB)
      • 基本思想：在多级队列基础上，允许进程在队列间动态调整。首先设置多个就绪队列，其次每个队列都采用先来先算法，按队列优先级调度。
      • 优缺点：优点是兼顾各个进程需求，动态适应进程变化；缺点是实现过程复杂。
      • 特点：分为抢占和非抢占，可能会引起饥饿。
    • 基于公平原则的调度算法
      • 基本思想：保证各进程公平获取CPU资源。
      • 优缺点：优点是公平性好；缺点是可能牺牲一定的系统效率。
  • 实时调度
    • 定义：满足实时任务对时间的严格要求的调度方式。
    • 分类：硬实时调度和软实时调度。
  • 调度实例
    • 操作系统中实际应用案例分析，如Linux调度机制。
• 死锁
  • 死锁概述
    • 定义：多个进程因竞争资源而造成的一种相互等待的僵局。
    • 产生原因：资源竞争，进程推进顺序不当。
    • 必要条件：互斥条件，请求和保持条件，不剥夺条件，循环等待条件。
  • 预防死锁
    • 破坏互斥条件：使资源可同时被多个进程同时使用（不常用，部分资源特性不允许）
    • 破坏请求和保持条件：进程一次性请求全部资源，否则不分配。
    • 破坏不剥夺条件：允许系统剥夺进程已占资源。
    • 破坏循环等待条件：对资源排序，进程按序请求。
  • 避免死锁
    • 银行家算法
      • 基本思想：通过资源分配前的试探，判断分配后系统是否安全。
      • 优缺点：优点是可有效避免死锁，缺点是需预先知道进程最大资源需求。
  • 死锁的检测与预防
    • 死锁检测：定期检查系统是否存在死锁，常用资源分配图化简法。
    • 死锁解除：剥夺死锁进程资源，撤销死锁进程等。