操作系统 CFS调度算法

### 完全公平调度器(CFS)原理

#### CFS概述
Completely Fair Scheduler（简称CFS），即完全公平调度器，是Linux系统中负责普通进程调度的核心组件之一[^2]。该调度器旨在提供一种更加公正的方式分配处理器资源给各个线程或进程。

#### 数据结构与时间复杂度
为了高效地管理和查找具有最低`vruntime`(虚拟运行时间)的任务,CFS选择了红黑树作为内部数据结构的一部分。这种选择使得每次插入、删除操作都能保持在O(log n)，从而保证了良好的性能表现[^1]。

#### vruntime机制
CFS引入了一个名为`vruntime`的概念来衡量每个任务已经获得的服务量。当新创建一个任务时会赋予其初始值；随着程序执行进度增加而累加此参数。对于等待更长时间未被执行过的轻载任务来说，则会被给予较低的`vruntime`值并放置于红黑树左侧位置，以便尽快得到CPU服务机会。

#### 关键函数解析
- **enqueue_entity()**: 将指定的任务加入到当前活动列表(Active List)以及对应的RB Tree节点之中；
- **dequeue_entity()**: 移除某个特定任务实例及其关联记录项；
- **place_entity()**: 对即将进入系统的进程进行初始化设置，并调整其`vruntime`以确保公平性[^3]。

void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initialPlacement);

这段代码展示了如何定义`place_entity()`方法签名，其中包含了两个主要输入参数：一个是代表控制组级别的请求队列对象(`cfs_rq`)，另一个是指向待处理实体(se)的指针变量。

#### 执行流程示例
通过构建内核模块并加载至目标机器上来观察实际效果是一种常见做法。例如，在完成编译之后可以利用命令行工具如make和insmod配合使用，进而触发相应事件的发生和发展变化情况：

make && sudo insmod km_param.ko pid1=<PID> pid2=<PID>
dmesg | tail -n 50

上述脚本片段说明了怎样安装自定义驱动文件km_param.ko并将选定进程ID传递进去测试CFS行为模式，最后借助日志查看最近发生的动态信息[^5]。