76、什么是处理机调度？调度算法主要有哪几种？

1. 处理机调度（Processor Scheduling）

处理机调度是操作系统的重要功能之一，它决定了哪个进程或线程可以占用CPU进行执行。当有多个进程或线程在同一时间处于就绪态时，操作系统必须通过调度算法选择其中一个进程或线程来执行。

处理机调度的目标是提高系统的效率、响应时间和资源利用率，同时保持公平性和合理性。它可以根据不同的需求调整优先级、时间片等参数，以适应不同的系统场景，如实时系统、批处理系统、交互系统等。

2. 处理机调度的分类

根据调度的时机和范围，处理机调度可以分为以下几类：

• 长程调度（Long-Term Scheduling）：决定哪个作业或进程可以进入系统。通常用于批处理系统，选择进入内存准备执行的作业。
• 中程调度（Medium-Term Scheduling）：决定哪些进程要被交换进内存或交换出到外存。用于系统负载过大时，将部分进程挂起，释放内存。
• 短程调度（Short-Term Scheduling，或称CPU调度）：决定哪个处于就绪态的进程或线程可以获得CPU执行。这是处理机调度的核心部分，也是最常见的调度类型。

3. 常见的调度算法

（1）先来先服务（First-Come, First-Served, FCFS）

• 特点：按照进程到达的顺序进行调度，先到的先执行，不考虑优先级或时间片。
• 优点：实现简单，公平性较好。
• 缺点：可能导致较长的平均等待时间，特别是遇到长作业时容易导致“不可抢占”的问题（即短作业需要等待长作业执行完）。
• 应用场景：适用于批处理系统，但不适用于交互系统。

（2）短作业优先（Shortest Job First, SJF）

• 特点：每次调度选择执行时间最短的进程，以最小化平均等待时间。SJF可以是抢占式或非抢占式。
• 优点：可以显著降低平均等待时间，提高系统的效率。
• 缺点：需要准确预测每个进程的执行时间，这在实际操作中很难实现。同时，可能导致“长作业饥饿”的问题，即长作业可能一直得不到调度。
• 应用场景：适用于批处理系统。

（3）优先级调度（Priority Scheduling）

• 特点：为每个进程分配优先级，优先级高的进程优先获得CPU。优先级调度可以是抢占式或非抢占式的。
• 优点：可以确保重要任务或实时任务优先执行。
• 缺点：可能导致“低优先级饥饿”问题，即低优先级进程可能一直得不到调度。可以通过**老化技术（Aging）**提高进程优先级来解决饥饿问题。
• 应用场景：适用于对任务重要性有区分的系统，如实时系统或操作系统中的关键任务调度。

（4）轮转调度（Round-Robin, RR）

• 特点：每个进程按照先来先服务的顺序，轮流获得CPU执行，且每次只能执行一个时间片。时间片用完后，进程被放回就绪队列的末尾，等待下次轮到它时继续执行。
• 优点：公平性好，适用于交互系统，响应速度快。
• 缺点：时间片的选择很关键，时间片过长会退化为FCFS，时间片过短会导致频繁的上下文切换，降低系统效率。
• 应用场景：适用于交互式系统，如操作系统中的多任务调度。

（5）多级反馈队列调度（Multilevel Feedback Queue Scheduling）

• 特点：将进程根据优先级和执行行为分配到多个就绪队列中，每个队列采用不同的调度算法。进程可以在不同队列之间移动，例如高优先级进程可以快速执行，低优先级进程可以逐渐得到提升。
• 优点：兼顾了短作业优先和长作业的公平性，灵活性高，适应不同类型的进程。
• 缺点：实现复杂，需要设置合适的参数和队列策略。
• 应用场景：常用于通用操作系统的调度策略，如Linux的调度器。

（6）最短剩余时间优先（Shortest Remaining Time First, SRTF）

• 特点：SRTF是SJF的抢占式版本，每次选择剩余执行时间最短的进程执行。如果新来的进程的预期执行时间比当前进程剩余时间短，则抢占当前进程。
• 优点：可以进一步减少平均等待时间。
• 缺点：仍然需要准确预测执行时间，并可能导致长作业饥饿。
• 应用场景：适用于需要最小化等待时间的场景。

（7）实时调度算法（Real-Time Scheduling Algorithms）

• 特点：实时系统中的调度算法需要满足严格的时间约束。常见的实时调度算法包括固定优先级调度（如Rate Monotonic）和动态优先级调度（如Earliest Deadline First, EDF）。
• 应用场景：适用于实时系统，如嵌入式系统、工业控制系统。

4. 调度算法的选择

调度算法的选择取决于系统的具体需求和场景：

• 批处理系统：通常需要最小化等待时间和吞吐量，因此短作业优先（SJF）或多级反馈队列较为合适。
• 交互式系统：需要快速响应用户请求，因此轮转调度（RR）和优先级调度常用。
• 实时系统：需要满足严格的时间要求，因此实时调度算法（如EDF、Rate Monotonic）更为合适。

5. 调度算法的比较

调度算法	优点	缺点	适用场景
先来先服务 (FCFS)	实现简单，公平性好	平均等待时间长，可能导致长作业阻塞短作业	批处理系统
短作业优先 (SJF)	平均等待时间短	需要知道作业时间，长作业可能饥饿	批处理系统
优先级调度	重要任务优先	低优先级进程可能饥饿	实时系统、交互系统
轮转调度 (RR)	响应速度快，公平	时间片选择困难，频繁上下文切换	交互式系统
多级反馈队列	灵活，兼顾短作业优先和公平性	实现复杂	通用操作系统调度策略
SRTF	最小化等待时间	需要作业时间，可能导致长作业饥饿	批处理和实时场景
实时调度算法	满足实时要求，保证任务在规定时间内完成	调度复杂性高	实时系统、嵌入式系统

总结

处理机调度是操作系统管理CPU资源的重要功能，不同的调度算法适用于不同的场景和需求。常见的调度算法包括先来先服务（FCFS）、短作业优先（SJF）、优先级调度、轮转调度（RR）、多级反馈队列调度等，它们分别适应不同类型的系统，如批处理系统、交互式系统、实时系统等。

---

---

77、调度的层次和三级调度的联系

1、高级调度（作业调度）
2、中级调度（内存调度）
3、低级调度（进程调度）

操作系统中的调度机制分为三个主要层次：高级调度（作业调度）、中级调度（内存调度） 和低级调度（进程调度）。它们负责不同阶段的调度任务，从作业进入系统开始，到进程在CPU上执行，再到进程与内存之间的调度。

1. 高级调度（作业调度）

• 定义：高级调度，也称为作业调度（Job Scheduling），主要负责管理系统中进入作业的调度。它决定哪些作业可以进入内存，并且在合适的时机创建相应的进程进行执行。

• 作用：作业调度通常在批处理系统中使用，操作系统通过作业调度将外部的作业（如批处理任务）从外存加载到内存，并为它们分配资源。作业调度决定了系统的作业进入速率，平衡了系统的负载。

• 关键点：

  • 决定何时将作业提交到系统。
  • 负责作业的进入、排队和处理。
  • 需要考虑系统负载，避免过多作业同时进入内存造成内存不足。

• 触发条件