1. 进程与线程

2. 调度的基本概念和目标

2.1. 基本概念

• 进程：一个程序在其数据集上的一次执行。
• 就绪队列：包含所有准备运行但尚未被分配到CPU的线程的列表。

  在古老的单处理器操作系统中，通常将进程作为调度的基本单位。随着多处理器和多核系统的发展，现代操作系统更倾向于使用线程作为调度的基本单位，因此就绪队列中包含的是线程列表。

  在Linux中，每个CPU都有一个就绪队列，为了减少锁竞争，提高并行性。

  除了就绪队列，一般还有一个阻塞队列，线程被锁等原因阻塞后，会被放入阻塞队列，当阻塞的原因消除后，会重新进入就绪队列等待调度。

• 调度：从就绪队列中选择下一个要执行的进程，并将处理器分配给它的过程。

2.2. 调度的目标

• 公平性：确保每个进程都能获得合理的资源使用机会。
• 高效性：最大限度地利用系统资源，尤其是处理器。
• 响应时间：减少用户从发出请求到系统做出响应的时间。
• 吞吐量：单位时间内处理的任务数量。
• 周转时间：从提交作业到完成作业所需的时间。
• 等待时间：从进程进入就绪状态到首次分配处理器的时间。
• 截止时间：对于实时系统，必须保证任务能够在特定的时间内完成。

3. 调度算法的分类及常见的调度算法

3.1. 实时调度

分为硬实时和软实时，常见的实时调度算法：

1. 抢占式优先级调度：每个任务都有一个优先级，高优先级的任务可以抢占正在执行的低优先级任务。
   • 优先级可静态设置，一般通过任务的状态、任务截止时间等信息动态设置。
   • 存在优先级反转问题，可通过优先级继承等方式解决。
2. 最早截止期优先（EDF）：总是选择截止期最早的未完成任务进行执行。
   • 如果处理器资源足够，可以保证满足所有任务的截止时间。
3. 最低松弛度优先（LLF）：松弛度是指任务的剩余时间与截止期之间的差值，该算法选择松弛度最小的任务进行执行。

用于提高实时调度的效率的技术，如：

• 任务分段
• 资源预留
• 确定性调度

4. 实时调度和抢占式调度

5. Linux调度策略

---