# 完全公平调度器相关的api

CFS（Completely Fair Scheduler），顾名思义，完全公平调度器。CFS 作为主线调度器之一，也是最典型的 O(1) 调度器之一。

## 结构体介绍

- `CompletelyFairScheduler`：实现了 `Scheduler` trait，是完全公平调度算法逻辑的主要实施者。
- `FairSchedEntity`
  - **重要字段**
    - `cfs_rq`：指向自己所在的完全公平调度队列。
    - `my_cfs_rq`：`Option` 变量。当该实体是一个单独进程时为 `None`；若该实体是一个组，则必须指向组内的私有调度队列。这个 `cfs_rq` 还可以继续往下深入，从而构成树型结构。
    - `pcb`：指向当前实体对应的 `PCB`。若当前实体是一个组，则这个 `Weak` 指针不指向任何值。

`FairSchedEntity` 是完全公平调度器中最重要的结构体，它代表一个调度实体。它不仅可以表示一个进程，还可以是一个组或一个用户，但在 CFS 队列中它只表示一个调度实体。这样的设计可以为上层提供更多思路，例如把不同进程归纳到一个调度实体，从而实现组调度，而不需要改变调度算法。

在 CFS 中，整体结构是**一棵树**：每一个调度实体作为 `cfs_rq` 中的一个节点；若该调度实体不是单个进程（例如进程组），则还需要在该实体中维护自己的 `cfs_rq`。嵌套展开后，每一个叶子节点就是一个单独的进程。需要理解这样一棵树，**后续文档会以这棵树为核心讲解**。

该结构体具体的字段意义请查阅源代码。这里提及几个重要的字段：

- `CfsRunQueue`：完全公平调度算法中管理 `FairSchedEntity` 的队列。它可以挂在总的 `CpuRunQueue` 下，也可以作为子节点挂在 `FairSchedEntity` 上，详见上文 `FairSchedEntity`。
  - **重要字段**
    - `entities`：存储调度实体的红黑树
    - `current`：当前正在运行的实体
