cfs_scheduler.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <etl/multiset.h>
 
#include <cassert>
#include <cstdint>
 
#include "kernel_config.hpp"
#include "kernel_log.hpp"
#include "scheduler_base.hpp"
#include "task_control_block.hpp"
 
class CfsScheduler : public SchedulerBase {
 public:
  static constexpr uint32_t kDefaultWeight = 1024;
 
  static constexpr uint64_t kMinGranularity = 10;  // 10 ticks
 
  struct VruntimeCompare {
    auto operator()(const TaskControlBlock* a, const TaskControlBlock* b) const
        -> bool {
      if (a->sched_data.cfs.vruntime != b->sched_data.cfs.vruntime) {
        return a->sched_data.cfs.vruntime < b->sched_data.cfs.vruntime;
      }
      return a < b;
    }
  };
 
  auto Enqueue(TaskControlBlock* task) -> void override {
    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++;
  }
 
  auto Dequeue(TaskControlBlock* task) -> void override {
    if (!task) {
      return;
    }
 
    auto it = ready_queue_.find(task);
    if (it != ready_queue_.end()) {
      ready_queue_.erase(it);
      stats_.total_dequeues++;
    }
  }
 
  [[nodiscard]] auto PickNext() -> TaskControlBlock* override {
    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;
  }
 
  [[nodiscard]] auto GetQueueSize() const -> size_t override {
    return ready_queue_.size();
  }
 
  [[nodiscard]] auto IsEmpty() const -> bool override {
    return ready_queue_.empty();
  }
 
  [[nodiscard]] auto OnTick(TaskControlBlock* current) -> bool override {
    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;  // 不需要抢占
  }
 
  auto OnPreempted(TaskControlBlock* task) -> void override {
    if (task) {
      stats_.total_preemptions++;
      // CFS 不需要额外处理，Schedule() 会将任务重新入队
    }
  }
 
  [[nodiscard]] auto GetMinVruntime() const -> uint64_t {
    return 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;
 
 private:
  etl::multiset<TaskControlBlock*, kernel::config::kMaxReadyTasks,
                VruntimeCompare>
      ready_queue_;
 
  uint64_t min_vruntime_{0};
};