/* 调度类的层次结构 */
/* include/linux/sched.h */

/*
 * 调度类优先级（从高到低）：
 *
 * 1. stop_sched_class   - 停止类（最高优先级，用于迁移进程等）
 * 2. dl_sched_class     - Deadline 调度类（SCHED_DEADLINE）
 * 3. rt_sched_class     - 实时调度类（SCHED_FIFO, SCHED_RR）
 * 4. fair_sched_class   - 公平调度类（CFS，SCHED_NORMAL, SCHED_BATCH）
 * 5. idle_sched_class   - 空闲调度类（最低优先级）
 */

/* 调度类接口 */
struct sched_class {
    const struct sched_class *next;  /* 下一个调度类 */

    void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags);
    void (*dequeue_task)(struct rq *rq, struct task_struct *p, int flags);
    void (*yield_task)(struct rq *rq);
    bool (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);

    struct task_struct *(*pick_next_task)(struct rq *rq);
    void (*put_prev_task)(struct rq *rq, struct task_struct *p);

    void (*set_curr_task)(struct rq *rq);
    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    void (*task_fork)(struct task_struct *p);

    unsigned int (*get_rr_interval)(struct rq *rq, struct task_struct *p);

    int (*load_balance)(struct rq *rq, int this_cpu,
                        struct lb_env *env);

    /* ... */
};

/* 调度入口函数（简化） */
/* kernel/sched/core.c */
static inline struct task_struct *pick_next_task(struct rq *rq) {
    const struct sched_class *class;

    /* 按优先级遍历调度类 */
    for_each_class(class) {
        struct task_struct *p = class->pick_next_task(rq);
        if (p)
            return p;
    }

    /* 不应该到这里 */
    BUG();
}

vruntime 的计算：
vruntime += (实际运行时间 × NICE_0_LOAD) / 进程权重

权重由 nice 值决定：
nice = -20 → 权重 = 88761（最高优先级）
nice = 0   → 权重 = 1024（默认）
nice = 19  → 权重 = 15（最低优先级）

效果：
- nice值越小（优先级越高），vruntime增长越慢
- nice值越大（优先级越低），vruntime增长越快
- CFS总是选择vruntime最小的进程运行

/* CFS 调度实体 */
/* include/linux/sched.h */
struct sched_entity {
    struct load_weight load;        /* 负载权重 */
    struct rb_node run_node;        /* 红黑树节点 */
    struct list_head group_node;    /* 组链表节点 */
    unsigned int on_rq;             /* 是否在运行队列上 */

    u64 exec_start;                 /* 开始执行的时间 */
    u64 sum_exec_runtime;           /* 总执行时间 */
    u64 vruntime;                   /* 虚拟运行时间 */
    u64 prev_sum_exec_runtime;      /* 上次统计的总执行时间 */

    u64 nr_migrations;              /* 迁移次数 */

    struct sched_statistics statistics; /* 调度统计 */

    /* 组调度相关 */
    struct cfs_rq *cfs_rq;          /* 所属的CFS运行队列 */
    struct cfs_rq *my_q;            /* 自己的CFS运行队列（组调度） */
};

/* 更新 vruntime */
/* kernel/sched/fair.c */
static void update_curr(struct cfs_rq *cfs_rq) {
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_of(cfs_rq)->clock;
    u64 delta_exec = now - curr->exec_start;

    if (delta_exec <= 0)
        return;

    curr->exec_start = now;
    curr->sum_exec_runtime += delta_exec;

    /* 计算 vruntime 增量 */
    /* vruntime += delta_exec * NICE_0_LOAD / weight */
    u64 vruntime_delta = calc_delta_fair(delta_exec, curr);
    curr->vruntime += vruntime_delta;
}

/* 权重表（nice值到权重的映射） */
/* kernel/sched/score.c */
static const int sched_prio_to_weight[40] = {
    /* -20 */ 88761, 71755, 56483, 46273, 36291,
    /* -15 */ 29154, 23254, 18705, 14949, 11916,
    /* -10 */  9548,  7620,  6100,  4904,  3906,
    /*  -5 */  3121,  2501,  1991,  1586,  1277,
    /*   0 */  1024,   820,   655,   526,   423,
    /*   5 */   335,   272,   215,   172,   137,
    /*  10 */   110,    87,    70,    56,    45,
    /*  15 */    36,    29,    23,    18,    15,
};

CFS 红黑树示意：

              [vruntime=100]
             /              \
     [vruntime=80]    [vruntime=120]
        /      \          /      \
  [60]    [90]  [110]  [130]  [150]

最左节点（vruntime最小）= 下一个要运行的进程

/* CFS 运行队列 */
/* kernel/sched/fair.c */
struct cfs_rq {
    struct load_weight load;          /* 总负载权重 */
    unsigned int nr_running;          /* 运行进程数 */
    unsigned int h_nr_running;        /* 层次化运行进程数 */

    u64 exec_clock;                   /* 执行时钟 */
    u64 min_vruntime;                 /* 最小 vruntime */

    struct rb_root_cached tasks_timeline; /* 红黑树 */
    struct rb_node *rb_leftmost;      /* 最左节点（vruntime最小） */

    struct sched_entity *curr;        /* 当前运行的实体 */
    struct sched_entity *next;        /* 下一个要运行的实体 */

    /* ... */
};

/* 选择下一个要运行的进程 */
static struct task_struct *pick_next_task_fair(struct rq *rq) {
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;

    if (!cfs_rq->nr_running)
        return NULL;

    /* 获取红黑树最左节点（vruntime最小的进程） */
    se = __pick_next_entity(cfs_rq);

    /* 设置为当前运行的实体 */
    put_prev_entity(cfs_rq, cfs_rq->curr);
    set_next_entity(cfs_rq, se);

    return task_of(se);
}

/* 获取最左节点 */
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq) {
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left)
        return NULL;
    return __rb_entity(left);
}

/* 将进程加入红黑树 */
static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
                            int flags) {
    /* 更新 vruntime */
    if (!(flags & ENQUEUE_WAKEUP))
        se->vruntime += cfs_rq->min_vruntime;

    /* 插入红黑树 */
    __enqueue_entity(cfs_rq, se);

    /* 更新运行队列统计 */
    update_load_add(&cfs_rq->load, se->load.weight);
    cfs_rq->nr_running++;
}

/* 实时调度策略 */
/* include/uapi/linux/sched.h */
#define SCHED_FIFO      1   /* 先进先出，不时间片轮转 */
#define SCHED_RR        2   /* 时间片轮转 */
#define SCHED_DEADLINE  6   /* 截止时间调度 */

/* 实时运行队列 */
struct rt_rq {
    struct rt_prio_array active;     /* 优先级数组 */
    unsigned int rt_nr_running;      /* 运行的实时进程数 */
    unsigned int rr_nr_running;      /* 使用RR策略的进程数 */
    /* ... */
};

/* 实时优先级数组 */
/* 100个优先级（0最高，99最低） */
struct rt_prio_array {
    DECLARE_BITMAP(bitmap, MAX_RT_PRIO + 1);
    struct list_head queue[MAX_RT_PRIO];
};

/*
 * SCHED_FIFO 行为：
 * - 一旦获得CPU，一直运行直到：
 *   1. 主动让出（yield/schedule）
 *   2. 被更高优先级的实时进程抢占
 *   3. 阻塞等待事件
 * - 不会因时间片用完而被抢占
 *
 * SCHED_RR 行为：
 * - 与 SCHED_FIFO 类似，但有时间片
 * - 时间片用完后，移到同优先级队列末尾
 * - 相同优先级的进程轮流执行
 */

# 查看和修改进程的调度策略
chrt -p $$
# pid 12345's current scheduling policy: SCHED_OTHER
# pid 12345's current scheduling priority: 0

# 设置实时调度策略
sudo chrt -f 50 $$    # SCHED_FIFO, 优先级50
sudo chrt -r 50 $$    # SCHED_RR, 优先级50

# 查看实时优先级范围
chrt -m
# SCHED_OTHER min/max priority : 0/0
# SCHED_FIFO min/max priority : 1/99
# SCHED_RR min/max priority : 1/99
# SCHED_BATCH min/max priority : 0/0
# SCHED_IDLE min/max priority : 0/0

调度时机：

1. 时钟中断（Timer Interrupt）
   - 每个tick（通常1-10ms）触发一次
   - 更新当前进程的运行时间
   - 检查是否需要抢占（need_resched标志）
   - 如果需要，调用schedule()

2. 系统调用返回用户态时
   - 检查 need_resched 标志
   - 如果设置了，调用 schedule() 而不是直接返回

3. 进程阻塞时
   - 进程调用 schedule() 主动让出CPU
   - 等待I/O、等待锁、等待信号等

4. 进程唤醒时
   - wake_up() 唤醒一个睡眠进程
   - 如果被唤醒的进程优先级更高，设置 need_resched
   - 在当前进程返回用户态前触发调度

5. 进程创建/退出时
   - 新进程可能需要立即调度
   - 进程退出时需要选择下一个进程

/* 调度的核心函数 */
/* kernel/sched/core.c */
asmlinkage __visible void __sched schedule(void) {
    struct task_struct *prev, *next;
    struct rq *rq;

    rq = this_rq();  /* 获取当前CPU的运行队列 */

    /* 关中断 */
    local_irq_disable();

    /* 选择下一个进程 */
    prev = rq->curr;
    next = pick_next_task(rq);

    if (likely(prev != next)) {
        /* 需要切换进程 */
        rq->nr_switches++;
        rq->curr = next;

        /* 上下文切换 */
        context_switch(rq, prev, next);
        /* 注意：context_switch 之后，
         * CPU上运行的是 next 进程
         * 当 prev 进程再次被调度时，
         * 从 context_switch 返回
         */
    }

    /* 开中断 */
    local_irq_enable();
}

/* 上下文切换 */
static void context_switch(struct rq *rq,
                            struct task_struct *prev,
                            struct task_struct *next) {
    struct mm_struct *mm = next->mm;
    struct mm_struct *oldmm = prev->active_mm;

    /* 切换内存地址空间 */
    if (!mm) {
        /* 内核线程没有自己的地址空间 */
        next->active_mm = oldmm;
    } else {
        switch_mm(oldmm, mm, next);  /* 切换页表 */
    }

    /* 切换寄存器上下文 */
    switch_to(prev, next, prev);
    /* 注意：switch_to 是汇编实现的
     * 它切换栈指针、程序计数器等寄存器
     * 切换后，CPU执行 next 进程的代码
     * 当 prev 再次被调度时，从 switch_to 返回
     */
}

/* 负载均衡的核心逻辑（简化） */
/* kernel/sched/fair.c */

/*
 * 负载均衡的触发时机：
 * 1. 新进程创建时（sched_balance_fork）
 * 2. 定时器触发（sched_balance_timer）
 * 3. CPU空闲时（idle_balance）
 *
 * 负载均衡的层次结构（调度域）：
 *
 * Level 4: NODE (跨NUMA节点)
 *   Level 3: MC (多核CPU)
 *     Level 2: DIE (同一芯片)
 *       Level 1: SMT (超线程)
 *         Level 0: CPU (单个逻辑CPU)
 *
 * 迁移成本：
 * SMT < MC < DIE < NODE
 * 超线程之间迁移成本最低
 * 跨NUMA节点迁移成本最高
 */

/* CPU空闲时的负载均衡 */
static int idle_balance(struct rq *this_rq) {
    struct rq *busiest = NULL;
    int pulled_task = 0;

    /* 遍历调度域，寻找负载最重的CPU */
    for_each_domain(this_cpu, sd) {
        if (sd->flags & SD_LOAD_BALANCE) {
            /* 找到最忙的CPU */
            busiest = find_busiest_queue(sd, this_cpu);
            if (busiest && busiest->nr_running > this_rq->nr_running) {
                /* 从最忙的CPU迁移进程 */
                pulled_task = move_tasks(this_rq, this_cpu,
                                         busiest, busiest->cpu,
                                         sd, CPU_NEWLY_IDLE);
                if (pulled_task)
                    break;
            }
        }
    }

    return pulled_task;
}

# 查看CPU亲和性
taskset -p $$
# pid 12345's current affinity mask: ff  (所有8个CPU)

# 绑定进程到特定CPU
taskset -c 0,1 $$
taskset -p $$
# pid 12345's current affinity mask: 3  (CPU 0和1)

# 查看调度信息
cat /proc/self/sched
# bash (12345, #threads: 1)
# ---------------------------------------------------------
# se.exec_start                                :     12345.678901
# se.vruntime                                  :       123.456789
# se.sum_exec_runtime                          :        12.345678
# se.nr_migrations                             :               42
# ...

# 创建一个CPU密集型进程
yes > /dev/null &
PID=$!

# 查看其调度信息
cat /proc/$PID/sched
# yes (PID, #threads: 1)
# se.exec_start    : ...
# se.vruntime      : ...

# 修改优先级
sudo renice -n -5 -p $PID
sudo renice -n 10 -p $PID

# 观察 vruntime 的变化
watch -n 1 "cat /proc/$PID/sched | grep vruntime"

# 清理
kill $PID

/* sched_bench.c - 测试优先级对CPU占用的影响 */
#include <stdio.h>
#include <unistd.h>
#include <sys/resource.h>
#include <time.h>

int main(int argc, char *argv[]) {
    int nice_val = 0;
    if (argc > 1)
        nice_val = atoi(argv[1]);

    setpriority(PRIO_PROCESS, 0, nice_val);

    clock_t start = clock();
    long count = 0;

    /* CPU密集型计算 */
    while (1) {
        count++;
        if (clock() - start > 5 * CLOCKS_PER_SEC)
            break;
    }

    printf("nice=%d, iterations=%ld\n", nice_val, count);
    return 0;
}

# 同时运行高优先级和低优先级进程
./sched_bench -20 &
./sched_bench 19 &
wait

# 高优先级进程完成更多迭代

/* sched_policy.c */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <sched.h>
#include <unistd.h>
#include <string.h>

int main() {
    struct sched_param param;

    /* 查看当前调度策略 */
    int policy = sched_getscheduler(0);
    switch (policy) {
        case SCHED_OTHER: printf("Policy: SCHED_OTHER\n"); break;
        case SCHED_FIFO:  printf("Policy: SCHED_FIFO\n"); break;
        case SCHED_RR:    printf("Policy: SCHED_RR\n"); break;
    }

    /* 设置 SCHED_RR 策略 */
    param.sched_priority = 50;
    if (sched_setscheduler(0, SCHED_RR, &param) < 0) {
        perror("sched_setscheduler (需要root权限)");
        return 1;
    }

    printf("New policy: SCHED_RR, priority: 50\n");

    /* 查看时间片大小 */
    struct timespec ts;
    if (sched_rr_get_interval(0, &ts) == 0) {
        printf("RR interval: %ld.%09ld seconds\n",
               ts.tv_sec, ts.tv_nsec);
    }

    return 0;
}