CfsScheduler Class Reference

CFS (Completely Fair Scheduler) 调度器 More...

#include <cfs_scheduler.hpp>

Inheritance diagram for CfsScheduler:

Collaboration diagram for CfsScheduler:

Classes
struct	VruntimeCompare
	vruntime 比较器 (用于 multiset 红黑树) More...

Public Member Functions
auto	Enqueue (TaskControlBlock *task) -> void override
	将任务加入就绪队列
auto	Dequeue (TaskControlBlock *task) -> void override
	从就绪队列中移除指定任务
auto	PickNext () -> TaskControlBlock *override
	选择下一个要运行的任务
auto	GetQueueSize () const -> size_t override
	获取就绪队列大小
auto	IsEmpty () const -> bool override
	判断队列是否为空
auto	OnTick (TaskControlBlock *current) -> bool override
	每个 tick 更新任务的 vruntime
auto	OnPreempted (TaskControlBlock *task) -> void override
	任务被抢占时调用
auto	GetMinVruntime () const -> uint64_t
	获取当前 min_vruntime
构造/析构函数
	CfsScheduler ()=default
	CfsScheduler (const CfsScheduler &)=delete
	CfsScheduler (CfsScheduler &&)=delete
auto	operator= (const CfsScheduler &) -> CfsScheduler &=delete
auto	operator= (CfsScheduler &&) -> CfsScheduler &=delete
	~CfsScheduler () override=default
Public Member Functions inherited from SchedulerBase
virtual auto	OnTimeSliceExpired (TaskControlBlock *task) -> bool
	时间片耗尽处理：当任务时间片用完时调用
virtual auto	BoostPriority (TaskControlBlock *task, int new_priority) -> void
	优先级提升：当任务持有资源时被更高优先级任务等待，提升其优先级
virtual auto	RestorePriority (TaskControlBlock *task) -> void
	优先级恢复：当任务释放资源后，恢复其原始优先级
virtual auto	OnScheduled (TaskControlBlock *task) -> void
	任务开始运行时调用 (从 Ready 变为 Running)
virtual auto	GetStats () const -> const Stats &
	获取调度器统计信息
virtual auto	ResetStats () -> void
	重置统计信息
	SchedulerBase ()=default
	SchedulerBase (const SchedulerBase &)=default
	SchedulerBase (SchedulerBase &&)=default
auto	operator= (const SchedulerBase &) -> SchedulerBase &=default
auto	operator= (SchedulerBase &&) -> SchedulerBase &=default
virtual	~SchedulerBase ()=default

Static Public Attributes
static constexpr uint32_t	kDefaultWeight = 1024
	默认权重 (对应 nice 值为 0)
static constexpr uint64_t	kMinGranularity = 10
	vruntime 粒度 (用于计算抢占阈值)

Private Attributes
etl::multiset< TaskControlBlock *, kernel::config::kMaxReadyTasks, VruntimeCompare >	ready_queue_
	就绪队列 (红黑树，按 vruntime 升序排序，begin() = 最小 vruntime)
uint64_t	min_vruntime_ {0}
	当前最小 vruntime (用于新任务初始化)

Additional Inherited Members
Public Attributes inherited from SchedulerBase
const char *	name {"Unnamed Scheduler"}
	调度器名称
Protected Attributes inherited from SchedulerBase
Stats	stats_ {}

Detailed Description

CFS (Completely Fair Scheduler) 调度器

Copyright

Copyright The SimpleKernel Contributors

基于虚拟运行时间 (vruntime) 的完全公平调度器。 每个任务根据其权重累积 vruntime，调度器总是选择 vruntime 最小的任务。

特点：

• 完全公平：每个任务获得与其权重成正比的 CPU 时间
• 支持优先级：通过权重影响 vruntime 增长速度
• 防止饥饿：新任务的 vruntime 设置为 min_vruntime
• 动态抢占：在 OnTick 中检查是否需要抢占当前任务

Definition at line 29 of file cfs_scheduler.hpp.

Constructor & Destructor Documentation

CfsScheduler() [1/3]

CfsScheduler::CfsScheduler ( )

default

CfsScheduler() [2/3]

CfsScheduler::CfsScheduler ( const CfsScheduler &  )

delete

CfsScheduler() [3/3]

CfsScheduler::CfsScheduler ( CfsScheduler &&  )

delete

~CfsScheduler()

CfsScheduler::~CfsScheduler ( )

overridedefault

Member Function Documentation

Dequeue()

auto CfsScheduler::Dequeue ( TaskControlBlock *  task ) -> void

inlineoverridevirtual

从就绪队列中移除指定任务

Parameters

task	要移除的任务控制块指针

Implements SchedulerBase.

Definition at line 85 of file cfs_scheduler.hpp.

                                                        {
    if (!task) {
      return;
    }
 
    auto it = ready_queue_.find(task);
    if (it != ready_queue_.end()) {
      ready_queue_.erase(it);
      stats_.total_dequeues++;
    }
  }

Here is the caller graph for this function:

Enqueue()

auto CfsScheduler::Enqueue ( TaskControlBlock *  task ) -> void

inlineoverridevirtual

将任务加入就绪队列

Parameters

task

任务控制块指针

新加入的任务的 vruntime 设置为当前 min_vruntime，防止饥饿。

Implements SchedulerBase.

Definition at line 58 of file cfs_scheduler.hpp.

                                                        {
    if (!task) {
      return;
    }
 
    // 如果是新任务 (vruntime == 0)，设置为当前 min_vruntime
    if (task->sched_data.cfs.vruntime == 0) {
      task->sched_data.cfs.vruntime = min_vruntime_;
    }
 
    // 确保任务有合理的权重
    if (task->sched_data.cfs.weight == 0) {
      task->sched_data.cfs.weight = kDefaultWeight;
    }
 
    if (ready_queue_.size() >= ready_queue_.max_size()) {
      klog::Err("CfsScheduler::Enqueue: ready_queue_ full, dropping task");
      return;
    }
    ready_queue_.insert(task);
    stats_.total_enqueues++;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

GetMinVruntime()

auto CfsScheduler::GetMinVruntime ( ) const -> uint64_t

inline

获取当前 min_vruntime

Returns

uint64_t 最小虚拟运行时间

Definition at line 187 of file cfs_scheduler.hpp.

                                                        {
    return min_vruntime_;
  }

Here is the caller graph for this function:

GetQueueSize()

auto CfsScheduler::GetQueueSize ( ) const -> size_t

inlineoverridevirtual

获取就绪队列大小

Returns

size_t 队列中的任务数量

Implements SchedulerBase.

Definition at line 126 of file cfs_scheduler.hpp.

                                                             {
    return ready_queue_.size();
  }

Here is the caller graph for this function:

IsEmpty()

auto CfsScheduler::IsEmpty ( ) const -> bool

inlineoverridevirtual

判断队列是否为空

Returns

bool 队列为空返回 true

Implements SchedulerBase.

Definition at line 134 of file cfs_scheduler.hpp.

                                                      {
    return ready_queue_.empty();
  }

Here is the caller graph for this function:

OnPreempted()

auto CfsScheduler::OnPreempted ( TaskControlBlock *  task ) -> void

inlineoverridevirtual

任务被抢占时调用

Parameters

task

被抢占的任务

被抢占的任务需要重新入队，保持其 vruntime。

Reimplemented from SchedulerBase.

Definition at line 176 of file cfs_scheduler.hpp.

                                                            {
    if (task) {
      stats_.total_preemptions++;
      // CFS 不需要额外处理，Schedule() 会将任务重新入队
    }
  }

Here is the caller graph for this function:

OnTick()

auto CfsScheduler::OnTick ( TaskControlBlock *  current ) -> bool

inlineoverridevirtual

每个 tick 更新任务的 vruntime

Parameters

current

当前运行的任务

Returns

bool 返回 true 表示需要抢占当前任务

CFS 核心逻辑：

1. 更新当前任务的 vruntime（考虑权重）
2. 检查是否有 vruntime 更小的任务需要抢占

Reimplemented from SchedulerBase.

Definition at line 147 of file cfs_scheduler.hpp.

                                                                        {
    assert(current != nullptr &&
           "CfsScheduler::OnTick: current task must not be null");
 
    // 更新 vruntime：delta = tick * (kDefaultWeight / weight)
    // 权重越大，vruntime 增长越慢，获得更多 CPU 时间
    uint64_t delta = (kDefaultWeight * 1000) / current->sched_data.cfs.weight;
    current->sched_data.cfs.vruntime += delta;
 
    // 检查是否需要抢占：队列中有 vruntime 更小的任务
    if (!ready_queue_.empty()) {
      auto* next = *ready_queue_.begin();
      // 如果队列顶部任务的 vruntime 比当前任务小超过阈值，则需要抢占
      if (next->sched_data.cfs.vruntime + kMinGranularity <
          current->sched_data.cfs.vruntime) {
        stats_.total_preemptions++;
        return true;  // 需要抢占
      }
    }
 
    return false;  // 不需要抢占
  }

Here is the caller graph for this function:

operator=() [1/2]

auto CfsScheduler::operator= ( CfsScheduler &&  ) -> CfsScheduler &=delete

delete

operator=() [2/2]

auto CfsScheduler::operator= ( const CfsScheduler &  ) -> CfsScheduler &=delete

delete

PickNext()

auto CfsScheduler::PickNext ( ) -> TaskControlBlock*

inlineoverridevirtual

选择下一个要运行的任务

Returns

TaskControlBlock* 下一个任务，如果队列为空则返回 nullptr

选择 vruntime 最小的任务，实现完全公平调度。

Implements SchedulerBase.

Definition at line 103 of file cfs_scheduler.hpp.

                                                              {
    if (ready_queue_.empty()) {
      return nullptr;
    }
 
    auto it = ready_queue_.begin();
    auto* next = *it;
    ready_queue_.erase(it);
    stats_.total_picks++;
 
    if (!ready_queue_.empty()) {
      min_vruntime_ = (*ready_queue_.begin())->sched_data.cfs.vruntime;
    } else {
      min_vruntime_ = next->sched_data.cfs.vruntime;
    }
 
    return next;
  }

Here is the caller graph for this function:

Member Data Documentation

kDefaultWeight

constexpr uint32_t CfsScheduler::kDefaultWeight = 1024

staticconstexpr

默认权重 (对应 nice 值为 0)

Definition at line 32 of file cfs_scheduler.hpp.

kMinGranularity

constexpr uint64_t CfsScheduler::kMinGranularity = 10

staticconstexpr

vruntime 粒度 (用于计算抢占阈值)

Definition at line 35 of file cfs_scheduler.hpp.

min_vruntime_

uint64_t CfsScheduler::min_vruntime_ {0}

private

当前最小 vruntime (用于新任务初始化)

Definition at line 208 of file cfs_scheduler.hpp.

{0};

ready_queue_

etl::multiset<TaskControlBlock*, kernel::config::kMaxReadyTasks, VruntimeCompare> CfsScheduler::ready_queue_

private

就绪队列 (红黑树，按 vruntime 升序排序，begin() = 最小 vruntime)

Definition at line 205 of file cfs_scheduler.hpp.

---

The documentation for this class was generated from the following file:

• /workspaces/SimpleKernel/src/task/include/cfs_scheduler.hpp