cfs_scheduler_test.cpp File Reference

#include "cfs_scheduler.hpp"
#include <gtest/gtest.h>
#include "kstd_vector"
#include "task_control_block.hpp"

Include dependency graph for cfs_scheduler_test.cpp:

Go to the source code of this file.

Functions
	TEST (CfsSchedulerTest, BasicEnqueueDequeue)
	TEST (CfsSchedulerTest, VruntimeOrdering)
	TEST (CfsSchedulerTest, NewTaskVruntimeInitialization)
	TEST (CfsSchedulerTest, WeightImpactOnVruntime)
	TEST (CfsSchedulerTest, OnTickPreemption)
	TEST (CfsSchedulerTest, OnTickNoPreemption)
	TEST (CfsSchedulerTest, DequeueSpecificTask)
	TEST (CfsSchedulerTest, NullPointerHandling)
	TEST (CfsSchedulerTest, DefaultWeightAssignment)
	TEST (CfsSchedulerTest, Statistics)
	TEST (CfsSchedulerTest, MinVruntimeUpdate)
	TEST (CfsSchedulerTest, MultipleTicksVruntimeAccumulation)
	TEST (CfsSchedulerTest, FairnessWithDifferentWeights)
	TEST (CfsSchedulerTest, ExtremeWeightValues)
	TEST (CfsSchedulerTest, QueueSizeConsistency)
	TEST (CfsSchedulerTest, PreemptionStatistics)

Function Documentation

TEST() [1/16]

TEST	(	CfsSchedulerTest	,
		BasicEnqueueDequeue
	)

Copyright

Copyright The SimpleKernel Contributors

Definition at line 13 of file cfs_scheduler_test.cpp.

                                            {
  CfsScheduler scheduler;
 
  // 创建测试任务
  TaskControlBlock task1("Task1", 1, nullptr, nullptr);
  task1.status = TaskStatus::kReady;
  task1.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task1.sched_data.cfs.vruntime = 0;
 
  TaskControlBlock task2("Task2", 2, nullptr, nullptr);
  task2.status = TaskStatus::kReady;
  task2.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task2.sched_data.cfs.vruntime = 0;
 
  // 测试空队列
  EXPECT_TRUE(scheduler.IsEmpty());
  EXPECT_EQ(scheduler.GetQueueSize(), 0);
  EXPECT_EQ(scheduler.PickNext(), nullptr);
 
  // 加入任务
  scheduler.Enqueue(&task1);
  EXPECT_FALSE(scheduler.IsEmpty());
  EXPECT_EQ(scheduler.GetQueueSize(), 1);
 
  scheduler.Enqueue(&task2);
  EXPECT_EQ(scheduler.GetQueueSize(), 2);
 
  // 选择任务（vruntime 相同时，按入队顺序）
  auto* next1 = scheduler.PickNext();
  EXPECT_NE(next1, nullptr);
  EXPECT_EQ(scheduler.GetQueueSize(), 1);
 
  auto* next2 = scheduler.PickNext();
  EXPECT_NE(next2, nullptr);
  EXPECT_EQ(scheduler.GetQueueSize(), 0);
 
  EXPECT_EQ(scheduler.PickNext(), nullptr);
  EXPECT_TRUE(scheduler.IsEmpty());
}

Here is the call graph for this function:

TEST() [2/16]

TEST	(	CfsSchedulerTest	,
		DefaultWeightAssignment
	)

Definition at line 236 of file cfs_scheduler_test.cpp.

                                                {
  CfsScheduler scheduler;
 
  TaskControlBlock task("Task", 1, nullptr, nullptr);
  task.sched_data.cfs.weight = 0;  // 权重未设置
  task.sched_data.cfs.vruntime = 0;
 
  scheduler.Enqueue(&task);
 
  // 权重应该被设置为默认值
  EXPECT_EQ(task.sched_data.cfs.weight, CfsScheduler::kDefaultWeight);
}

Here is the call graph for this function:

TEST() [3/16]

TEST	(	CfsSchedulerTest	,
		DequeueSpecificTask
	)

Definition at line 183 of file cfs_scheduler_test.cpp.

                                            {
  CfsScheduler scheduler;
 
  TaskControlBlock task1("Task1", 1, nullptr, nullptr);
  task1.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task1.sched_data.cfs.vruntime = 100;
 
  TaskControlBlock task2("Task2", 2, nullptr, nullptr);
  task2.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task2.sched_data.cfs.vruntime = 200;
 
  TaskControlBlock task3("Task3", 3, nullptr, nullptr);
  task3.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task3.sched_data.cfs.vruntime = 300;
 
  scheduler.Enqueue(&task1);
  scheduler.Enqueue(&task2);
  scheduler.Enqueue(&task3);
 
  EXPECT_EQ(scheduler.GetQueueSize(), 3);
 
  // 移除中间的任务
  scheduler.Dequeue(&task2);
  EXPECT_EQ(scheduler.GetQueueSize(), 2);
 
  // 验证只剩下 task1 和 task3
  EXPECT_EQ(scheduler.PickNext(), &task1);
  EXPECT_EQ(scheduler.PickNext(), &task3);
  EXPECT_EQ(scheduler.PickNext(), nullptr);
}

Here is the call graph for this function:

TEST() [4/16]

TEST	(	CfsSchedulerTest	,
		ExtremeWeightValues
	)

Definition at line 385 of file cfs_scheduler_test.cpp.

                                            {
  CfsScheduler scheduler;
 
  TaskControlBlock task("Task", 1, nullptr, nullptr);
  task.sched_data.cfs.vruntime = 0;
 
  // 测试极小权重 (避免除零)
  task.sched_data.cfs.weight = 1;
  scheduler.OnTick(&task);
  EXPECT_GT(task.sched_data.cfs.vruntime, 0);
 
  // 测试极大权重
  task.sched_data.cfs.vruntime = 0;
  task.sched_data.cfs.weight = CfsScheduler::kDefaultWeight * 1000;
  scheduler.OnTick(&task);
  EXPECT_GT(task.sched_data.cfs.vruntime, 0);
  EXPECT_LT(task.sched_data.cfs.vruntime, 10);  // 应该很小
}

Here is the call graph for this function:

TEST() [5/16]

TEST	(	CfsSchedulerTest	,
		FairnessWithDifferentWeights
	)

Definition at line 355 of file cfs_scheduler_test.cpp.

                                                     {
  CfsScheduler scheduler;
 
  TaskControlBlock high_priority("HighPriority", 1, nullptr, nullptr);
  high_priority.sched_data.cfs.weight =
      CfsScheduler::kDefaultWeight * 2;  // 2倍权重
  high_priority.sched_data.cfs.vruntime = 0;
 
  TaskControlBlock low_priority("LowPriority", 2, nullptr, nullptr);
  low_priority.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;  // 1倍权重
  low_priority.sched_data.cfs.vruntime = 0;
 
  // 模拟相同次数的 tick
  constexpr int kTickCount = 10;
 
  for (int i = 0; i < kTickCount; ++i) {
    scheduler.OnTick(&high_priority);
    scheduler.OnTick(&low_priority);
  }
 
  // 高优先级任务的 vruntime 增长应该是低优先级的一半
  // high: delta = 1024 * 1000 / 2048 = 500 per tick
  // low:  delta = 1024 * 1000 / 1024 = 1000 per tick
  EXPECT_EQ(high_priority.sched_data.cfs.vruntime, 500 * kTickCount);
  EXPECT_EQ(low_priority.sched_data.cfs.vruntime, 1000 * kTickCount);
  EXPECT_EQ(low_priority.sched_data.cfs.vruntime,
            high_priority.sched_data.cfs.vruntime * 2);
}

Here is the call graph for this function:

TEST() [6/16]

TEST	(	CfsSchedulerTest	,
		MinVruntimeUpdate
	)

Definition at line 293 of file cfs_scheduler_test.cpp.

                                          {
  CfsScheduler scheduler;
 
  TaskControlBlock task1("Task1", 1, nullptr, nullptr);
  task1.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task1.sched_data.cfs.vruntime = 1000;
 
  TaskControlBlock task2("Task2", 2, nullptr, nullptr);
  task2.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task2.sched_data.cfs.vruntime = 500;
 
  TaskControlBlock task3("Task3", 3, nullptr, nullptr);
  task3.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task3.sched_data.cfs.vruntime = 750;
 
  scheduler.Enqueue(&task1);
  scheduler.Enqueue(&task2);
  scheduler.Enqueue(&task3);
 
  // 初始 min_vruntime 应该是 0
  EXPECT_EQ(scheduler.GetMinVruntime(), 0);
 
  // 选择 task2 (vruntime = 500)
  scheduler.PickNext();
 
  // min_vruntime 应该更新为队列中最小的 (750)
  EXPECT_EQ(scheduler.GetMinVruntime(), 750);
 
  // 选择 task3 (vruntime = 750)
  scheduler.PickNext();
 
  // min_vruntime 应该更新为 1000
  EXPECT_EQ(scheduler.GetMinVruntime(), 1000);
 
  // 选择 task1 (vruntime = 1000)
  scheduler.PickNext();
 
  // 队列为空，min_vruntime 保持为 1000
  EXPECT_EQ(scheduler.GetMinVruntime(), 1000);
}

Here is the call graph for this function:

TEST() [7/16]

TEST	(	CfsSchedulerTest	,
		MultipleTicksVruntimeAccumulation
	)

Definition at line 335 of file cfs_scheduler_test.cpp.

                                                          {
  CfsScheduler scheduler;
 
  TaskControlBlock task("Task", 1, nullptr, nullptr);
  task.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task.sched_data.cfs.vruntime = 0;
 
  // 模拟多次 tick
  constexpr int kTickCount = 10;
  uint64_t expected_delta = (CfsScheduler::kDefaultWeight * 1000) /
                            task.sched_data.cfs.weight;  // = 1000
 
  for (int i = 0; i < kTickCount; ++i) {
    scheduler.OnTick(&task);
  }
 
  EXPECT_EQ(task.sched_data.cfs.vruntime, expected_delta * kTickCount);
}

Here is the call graph for this function:

TEST() [8/16]

TEST	(	CfsSchedulerTest	,
		NewTaskVruntimeInitialization
	)

Definition at line 84 of file cfs_scheduler_test.cpp.

                                                      {
  CfsScheduler scheduler;
 
  TaskControlBlock task1("Task1", 1, nullptr, nullptr);
  task1.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task1.sched_data.cfs.vruntime = 1000;
 
  // 加入第一个任务
  scheduler.Enqueue(&task1);
  auto* picked1 = scheduler.PickNext();
  EXPECT_EQ(picked1, &task1);
 
  // 第二个任务 vruntime = 0 (新任务)
  TaskControlBlock task2("Task2", 2, nullptr, nullptr);
  task2.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task2.sched_data.cfs.vruntime = 0;
 
  scheduler.Enqueue(&task2);
  // 新任务的 vruntime 应该被设置为 min_vruntime (1000)
  EXPECT_EQ(task2.sched_data.cfs.vruntime, 1000);
}

Here is the call graph for this function:

TEST() [9/16]

TEST	(	CfsSchedulerTest	,
		NullPointerHandling
	)

Definition at line 215 of file cfs_scheduler_test.cpp.

                                            {
  CfsScheduler scheduler;
 
  // Enqueue 空指针应该不崩溃
  scheduler.Enqueue(nullptr);
  EXPECT_EQ(scheduler.PickNext(), nullptr);
 
  // Dequeue 空指针应该不崩溃
  scheduler.Dequeue(nullptr);
 
  // OnTick 空指针应该不崩溃
  EXPECT_FALSE(scheduler.OnTick(nullptr));
 
  // OnPreempted 空指针应该不崩溃
  scheduler.OnPreempted(nullptr);
 
  // OnScheduled 空指针应该不崩溃
  scheduler.OnScheduled(nullptr);
}

Here is the call graph for this function:

TEST() [10/16]

TEST	(	CfsSchedulerTest	,
		OnTickNoPreemption
	)

Definition at line 161 of file cfs_scheduler_test.cpp.

                                           {
  CfsScheduler scheduler;
 
  TaskControlBlock task1("Task1", 1, nullptr, nullptr);
  task1.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task1.sched_data.cfs.vruntime = 1000;
 
  TaskControlBlock task2("Task2", 2, nullptr, nullptr);
  task2.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  // OnTick 会让 task1 增加 1000，所以 task2 应该设置为 1000 + 1000 - 5 = 1995
  // 这样 OnTick 后：task1 = 2000, task2 = 1995，差距 5 < 10
  task2.sched_data.cfs.vruntime = 1995;
 
  scheduler.Enqueue(&task2);
 
  bool should_preempt = scheduler.OnTick(&task1);
 
  // OnTick 后差距为 5，小于 kMinGranularity (10)，不应该抢占
  EXPECT_FALSE(should_preempt);
}

Here is the call graph for this function:

TEST() [11/16]

TEST	(	CfsSchedulerTest	,
		OnTickPreemption
	)

Definition at line 139 of file cfs_scheduler_test.cpp.

                                         {
  CfsScheduler scheduler;
 
  TaskControlBlock task1("Task1", 1, nullptr, nullptr);
  task1.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task1.sched_data.cfs.vruntime = 100;
 
  TaskControlBlock task2("Task2", 2, nullptr, nullptr);
  task2.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task2.sched_data.cfs.vruntime = 0;  // 更小的 vruntime
 
  scheduler.Enqueue(&task2);
 
  // task1 运行，vruntime 不断增长
  task1.sched_data.cfs.vruntime = 100;
  bool should_preempt = scheduler.OnTick(&task1);
 
  // task2 的 vruntime (0) 比 task1 小很多，应该抢占
  EXPECT_TRUE(should_preempt);
}

Here is the call graph for this function:

TEST() [12/16]

TEST	(	CfsSchedulerTest	,
		PreemptionStatistics
	)

Definition at line 447 of file cfs_scheduler_test.cpp.

                                             {
  CfsScheduler scheduler;
 
  TaskControlBlock task1("Task1", 1, nullptr, nullptr);
  task1.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task1.sched_data.cfs.vruntime = 1000;
 
  TaskControlBlock task2("Task2", 2, nullptr, nullptr);
  task2.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task2.sched_data.cfs.vruntime = 0;
 
  scheduler.Enqueue(&task2);
 
  // 触发抢占
  scheduler.OnTick(&task1);
  auto stats = scheduler.GetStats();
  EXPECT_EQ(stats.total_preemptions, 1);
 
  // OnPreempted 也会增加抢占计数
  scheduler.OnPreempted(&task1);
  stats = scheduler.GetStats();
  EXPECT_EQ(stats.total_preemptions, 2);
}

Here is the call graph for this function:

TEST() [13/16]

TEST	(	CfsSchedulerTest	,
		QueueSizeConsistency
	)

Definition at line 405 of file cfs_scheduler_test.cpp.

                                             {
  CfsScheduler scheduler;
 
  kstd::vector<TaskControlBlock*> tasks;
  for (int i = 0; i < 5; ++i) {
    auto* task = new TaskControlBlock("Task", 10, nullptr, nullptr);
    task->sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
    task->sched_data.cfs.vruntime = i * 100;
    tasks.push_back(task);
  }
 
  // 加入 5 个任务
  for (auto* task : tasks) {
    scheduler.Enqueue(task);
  }
  EXPECT_EQ(scheduler.GetQueueSize(), 5);
 
  // 移除 3 个任务
  scheduler.PickNext();
  scheduler.PickNext();
  scheduler.PickNext();
  EXPECT_EQ(scheduler.GetQueueSize(), 2);
 
  // 加入 2 个任务
  scheduler.Enqueue(tasks[0]);
  scheduler.Enqueue(tasks[1]);
  EXPECT_EQ(scheduler.GetQueueSize(), 4);
 
  // 清空队列
  while (!scheduler.IsEmpty()) {
    scheduler.PickNext();
  }
  EXPECT_EQ(scheduler.GetQueueSize(), 0);
  EXPECT_TRUE(scheduler.IsEmpty());
 
  // 清理内存
  for (auto* task : tasks) {
    delete task;
  }
}

Here is the call graph for this function:

TEST() [14/16]

TEST	(	CfsSchedulerTest	,
		Statistics
	)

Definition at line 250 of file cfs_scheduler_test.cpp.

                                   {
  CfsScheduler scheduler;
 
  TaskControlBlock task1("Task1", 1, nullptr, nullptr);
  task1.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task1.sched_data.cfs.vruntime = 0;
 
  TaskControlBlock task2("Task2", 2, nullptr, nullptr);
  task2.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task2.sched_data.cfs.vruntime = 0;
 
  // 测试 enqueue 计数
  scheduler.Enqueue(&task1);
  scheduler.Enqueue(&task2);
  auto stats = scheduler.GetStats();
  EXPECT_EQ(stats.total_enqueues, 2);
 
  // 测试 pick 计数
  scheduler.PickNext();
  stats = scheduler.GetStats();
  EXPECT_EQ(stats.total_picks, 1);
 
  scheduler.PickNext();
  stats = scheduler.GetStats();
  EXPECT_EQ(stats.total_picks, 2);
 
  // 测试 dequeue 计数
  scheduler.Enqueue(&task1);
  scheduler.Enqueue(&task2);
  scheduler.Dequeue(&task1);
  stats = scheduler.GetStats();
  EXPECT_EQ(stats.total_dequeues, 1);
 
  // 测试重置统计
  scheduler.ResetStats();
  stats = scheduler.GetStats();
  EXPECT_EQ(stats.total_enqueues, 0);
  EXPECT_EQ(stats.total_picks, 0);
  EXPECT_EQ(stats.total_dequeues, 0);
  EXPECT_EQ(stats.total_preemptions, 0);
}

Here is the call graph for this function:

TEST() [15/16]

TEST	(	CfsSchedulerTest	,
		VruntimeOrdering
	)

Definition at line 54 of file cfs_scheduler_test.cpp.

                                         {
  CfsScheduler scheduler;
 
  TaskControlBlock task1("Task1", 1, nullptr, nullptr);
  task1.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task1.sched_data.cfs.vruntime = 1000;
 
  TaskControlBlock task2("Task2", 2, nullptr, nullptr);
  task2.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task2.sched_data.cfs.vruntime = 500;  // 最小 vruntime
 
  TaskControlBlock task3("Task3", 3, nullptr, nullptr);
  task3.sched_data.cfs.weight = CfsScheduler::kDefaultWeight;
  task3.sched_data.cfs.vruntime = 750;
 
  // 按任意顺序加入任务
  scheduler.Enqueue(&task1);
  scheduler.Enqueue(&task2);
  scheduler.Enqueue(&task3);
 
  EXPECT_EQ(scheduler.GetQueueSize(), 3);
 
  // 应该按 vruntime 从小到大选择
  EXPECT_EQ(scheduler.PickNext(), &task2);  // vruntime = 500
  EXPECT_EQ(scheduler.PickNext(), &task3);  // vruntime = 750
  EXPECT_EQ(scheduler.PickNext(), &task1);  // vruntime = 1000
  EXPECT_EQ(scheduler.PickNext(), nullptr);
}

Here is the call graph for this function:

TEST() [16/16]

TEST	(	CfsSchedulerTest	,
		WeightImpactOnVruntime
	)

Definition at line 107 of file cfs_scheduler_test.cpp.

                                               {
  CfsScheduler scheduler;
 
  TaskControlBlock task1("HighPriorityTask", 1, nullptr, nullptr);
  task1.sched_data.cfs.weight = CfsScheduler::kDefaultWeight * 2;  // 高优先级
  task1.sched_data.cfs.vruntime = 0;
 
  TaskControlBlock task2("LowPriorityTask", 2, nullptr, nullptr);
  task2.sched_data.cfs.weight = CfsScheduler::kDefaultWeight / 2;  // 低优先级
  task2.sched_data.cfs.vruntime = 0;
 
  scheduler.Enqueue(&task1);
  scheduler.Enqueue(&task2);
 
  auto* first = scheduler.PickNext();
  EXPECT_NE(first, nullptr);
 
  // 模拟 OnTick 更新 vruntime
  uint64_t initial_vruntime = first->sched_data.cfs.vruntime;
  scheduler.OnTick(first);
 
  // 权重大的任务 vruntime 增长慢
  if (first == &task1) {
    // task1 权重是 2048，delta = 1024 * 1000 / 2048 = 500
    EXPECT_EQ(first->sched_data.cfs.vruntime, initial_vruntime + 500);
  } else {
    // task2 权重是 512，delta = 1024 * 1000 / 512 = 2000
    EXPECT_EQ(first->sched_data.cfs.vruntime, initial_vruntime + 2000);
  }
}

Here is the call graph for this function: