第4章 处理机调度与死锁

CPU调度的基本准则有哪些？

• CPU 利用率：尽量保持 CPU 忙碌
• 吞吐量：单位时间完成进程数
• 周转时间：进程从提交到完成时间
• 等待时间：进程在就绪队列等待时间
• 响应时间：从提交到首次响应时间

操作系统调度算法有哪些？

操作系统调度算法是选择下一个执行任务的策略，主要分为以下几类：

1. 非抢占式调度

• 先来先服务（FCFS）

  • 按到达顺序执行，简单公平
  • 缺点：可能导致短作业长时间等待

• 短作业优先（SJF/SPF）

  • 优先执行预计运行时间最短的任务
  • 优点：平均等待时间最短
  • 缺点：难以准确预测运行时间，长作业可能"饥饿"

2. 抢占式调度

• 时间片轮转（RR）

  • 为每个任务分配固定时间片，轮流执行
  • 适合分时系统，响应性好
  • 时间片大小影响性能：太小增加切换开销，太大导致响应变慢

• 优先级调度

  • 高优先级任务先执行，可设置动态优先级
  • 防止"饥饿"：老化机制（提高长期等待任务的优先级）

• 多级反馈队列

  • 结合时间片轮转和优先级调度的优点
  • 多个优先级队列，高优先级队列时间片短
  • 任务运行时间越长，优先级越低

3. 实时调度

• 最早截止时间优先（EDF）

  • 截止时间早的任务先执行，适用于硬实时系统

• 速率单调调度（RMS）

  • 周期短的任务优先级高，适用于周期性实时任务

什么是死锁？

死锁是指多个进程在运行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

死锁产生的四个必要条件

• 互斥条件：资源一次只能被一个进程使用
• 占有和等待条件：已获得资源的进程可以再次申请新资源
• 非抢占条件：进程已获得的资源在未使用完之前不能被抢占
• 循环等待条件：若干进程之间形成头尾相接的循环等待资源关系

死锁的预防措施

• 破坏互斥条件：资源共享化
• 破坏占有和等待：进程启动前申请所需所有资源
• 破坏非抢占条件：允许系统抢占资源
• 破坏循环等待：按序分配资源

死锁的处理策略

• 死锁预防：破坏产生条件
• 死锁避免：动态检查避免进入不安全状态（如银行家算法）
• 死锁检测与恢复：定时检测，发现后处理
• 鸵鸟策略：忽略死锁问题

什么是自旋锁？什么时候使用？

• 拿不到锁时 循环等待，不挂起线程
• 适合锁持有时间 非常短 的场景
• 不适合长等待，会浪费 CPU

锁机制相关概念

什么是死锁？四个必要条件是什么？

• 死锁：线程互相等待资源，无法继续执行
• 互斥
• 占有并等待
• 不可剥夺
• 循环等待

如何避免死锁？

• 统一加锁顺序（最常用）
• tryLock + 超时
• 减少锁粒度
• 资源预分配
• 破坏循环等待条件

上下文切换

什么是上下文切换？

• CPU 保存当前任务状态、恢复另一个任务状态
• 包括寄存器、PC、堆栈等内容
• 切换过多会降低系统吞吐性能