第2章：进程管理与任务调度

Linux 0.11 task_struct (约100行)
    |
    v
Linux 2.4 task_struct (约300行) - 引入SMP支持
    |
    v  
Linux 2.6 task_struct (约500行) - 添加线程支持、调度域
    |
    v
Linux 6.x task_struct (约700行) - 容器、cgroup、安全增强

     高地址
    ┌─────────────┐
    │   内核栈    │ 8KB(32位)/16KB(64位)
    ├─────────────┤
    │   红区保护   │ 防止栈溢出
    ├─────────────┤
    │ thread_info │ x86已移至per-CPU变量
    ├─────────────┤
    │  pt_regs    │ 系统调用/中断时保存
    └─────────────┘
     低地址

现代task_struct访问机制:
#define current get_current()

// x86_64实现 - 使用per-CPU变量
static inline struct task_struct *get_current(void) {
    return this_cpu_read_stable(current_task);
}

// ARM64实现 - 使用专用寄存器
static inline struct task_struct *get_current(void) {
    return (struct task_struct *)read_sysreg(sp_el0);
}

struct pid {
    refcount_t count;        // 引用计数，防止过早释放
    unsigned int level;       // 命名空间嵌套深度（0为根）
    spinlock_t lock;         // 保护tasks链表的自旋锁
    /* 按类型组织的任务链表：

     * PIDTYPE_PID - 单个任务
     * PIDTYPE_TGID - 线程组领导
     * PIDTYPE_PGID - 进程组
     * PIDTYPE_SID - 会话
     */
    struct hlist_head tasks[PIDTYPE_MAX];
    struct upid numbers[1];   // 灵活数组，每层一个upid
};

struct upid {
    int nr;                   // 该层命名空间中的PID值
    struct pid_namespace *ns; // 指向所属命名空间
};

全局PID哈希表组织:
pid_hash[hash(pid)] → struct pid → task_struct

命名空间内查找:
pid_namespace::idr → struct pid → 特定层级的upid

进程组/会话查找:
通过PIDTYPE_PGID/PIDTYPE_SID链表遍历

fork()系统调用的完整流程:

1. sys_fork() → kernel_clone(SIGCHLD, 0, 0, NULL, NULL, 0)
2. 分配新的task_struct:
   - dup_task_struct(): 复制当前进程的task_struct
   - 分配新的内核栈（通过alloc_thread_stack_node）
   - 复制thread_info和寄存器状态

3. 初始化子进程特有字段:
   - 分配新的PID（alloc_pid）
   - 设置进程关系（父子、兄弟链表）
   - 清零统计信息（CPU时间、缺页次数等）

4. 复制进程资源（按需共享或复制）:
   - copy_mm(): 复制内存管理结构，设置COW
   - copy_files(): 复制或共享文件描述符表
   - copy_sighand(): 复制信号处理器
   - copy_thread(): 设置子进程返回值为0
   - copy_namespaces(): 复制或共享命名空间

5. 调度器处理:
   - 设置子进程状态为TASK_RUNNING
   - 将子进程加入就绪队列（wake_up_new_task）
   - 可能触发负载均衡

COW的页表操作细节:

初始状态（fork前）:
父进程PTE: [PRESENT | RW | USER] → 物理页A

fork后（共享阶段）:
父进程PTE: [PRESENT | RO | USER | COW] → 物理页A
子进程PTE: [PRESENT | RO | USER | COW] → 物理页A
物理页A引用计数: 2

写操作触发（缺页异常处理）:

1. CPU尝试写入，发现页面只读，触发缺页异常
2. do_wp_page()处理写保护异常:
   if (页面引用计数 == 1) {
       // 最后一个引用，直接恢复写权限
       设置PTE为RW
   } else {
       // 多个引用，需要复制
       分配新物理页B
       复制A的内容到B
       更新PTE指向B，设置RW
       减少A的引用计数
   }

3. 刷新TLB项
4. 返回用户空间，重试写操作

// vfork的三个关键语义:

1. 父子进程共享完整的地址空间(包括栈、堆、数据段)
2. 父进程阻塞直到子进程调用exec或_exit
3. 子进程在共享期间的行为受到严格限制

内核实现的关键点:
kernel_clone(CLONE_VFORK | CLONE_VM | SIGCHLD, 0, 0, NULL, NULL, 0)

- CLONE_VFORK: 设置完成等待机制(vfork_done)
- CLONE_VM: 共享mm_struct，不复制页表
- 父进程通过wait_for_vfork_done()睡眠

// 危险示例1 - 破坏父进程栈帧
int main() {
    int parent_var = 100;
    if (vfork() == 0) {
        parent_var = 200;  // 直接修改父进程的变量！
        return 0;          // 错误：破坏父进程的栈帧
        // 正确做法：_exit(0) 或 exec*()
    }
    printf("%d\n", parent_var);  // 输出200，栈已被破坏
}

// 危险示例2 - 栈指针混乱
void dangerous() {
    char buffer[1024];
    if (vfork() == 0) {
        // 子进程的栈帧覆盖了父进程的栈空间
        recursive_function();  // 可能破坏父进程的返回地址
        _exit(0);
    }
}

// 危险示例3 - 信号处理竞争
if (vfork() == 0) {
    signal(SIGTERM, handler);  // 修改了父进程的信号处理器！
    exec*(...);
}

int clone(int (*fn)(void *), void *stack, int flags, void *arg, ...);

关键标志位:
CLONE_VM       共享地址空间(线程)
CLONE_FILES    共享文件描述符表
CLONE_SIGHAND  共享信号处理器
CLONE_THREAD   同一线程组
CLONE_NEWNS    新mount命名空间
CLONE_NEWPID   新PID命名空间
CLONE_NEWNET   新网络命名空间

clone(thread_func, stack_top, 
      CLONE_VM | CLONE_FILES | CLONE_SIGHAND | 
      CLONE_THREAD | CLONE_SETTLS | CLONE_PARENT_SETTID |
      CLONE_CHILD_CLEARTID, arg);

运行队列结构:
struct runqueue {
    spinlock_t lock;
    unsigned long nr_running;

    struct prio_array *active;   // 活动优先级数组
    struct prio_array *expired;  // 过期优先级数组
    struct prio_array arrays[2]; // 实际数组存储
};

struct prio_array {
    unsigned int nr_active;
    unsigned long bitmap[BITMAP_SIZE];  // 140个优先级的位图
    struct list_head queue[MAX_PRIO];   // 每个优先级的任务队列
};

选择下一个任务:

1. idx = find_first_bit(array->bitmap)  // 硬件指令，O(1)
2. next = list_first_entry(&array->queue[idx])
3. 时间片用完后移到expired数组
4. active数组空时，交换active和expired指针

核心思想: 虚拟运行时间(vruntime)
vruntime = 实际运行时间 * (NICE_0_LOAD / 进程权重)

struct sched_entity {
    u64 vruntime;           // 虚拟运行时间
    u64 sum_exec_runtime;   // 实际运行时间累计
    struct rb_node run_node; // 红黑树节点
    unsigned int on_rq;     // 是否在运行队列

    // 负载权重
    struct load_weight load;
    struct load_weight avg_load;
};

struct cfs_rq {
    struct rb_root_cached tasks_timeline;  // 红黑树根
    struct sched_entity *curr;             // 当前运行
    struct sched_entity *next;             // 下一个运行
    u64 min_vruntime;                      // 最小vruntime基准

    unsigned int nr_running;
    unsigned long load;
};

1. 入队: 按vruntime插入红黑树 O(log n)
2. 选择: 最左节点(最小vruntime) O(1) [缓存]
3. 时间片: 
   slice = sched_period * se.load / cfs_rq.load
   默认sched_period = 6ms * nr_running (最大48ms)

4. 抢占检查:
   if (curr.vruntime - leftmost.vruntime > sched_granularity)
       触发抢占

EEVDF核心概念:

1. 虚拟截止时间: vdeadline = vruntime + slice
2. 延迟nice: 每个任务可设置延迟敏感度
3. 资格时间: eligible_time = vruntime - lag

选择算法:
在所有eligible的任务中，选择vdeadline最早的

调度类优先级(高→低):

1. stop_sched_class     停机调度类
2. dl_sched_class       DEADLINE调度类  
3. rt_sched_class       实时调度类(FIFO/RR)
4. fair_sched_class     CFS公平调度类
5. idle_sched_class     空闲调度类

struct sched_class {
    void (*enqueue_task)();   // 入队
    void (*dequeue_task)();   // 出队
    void (*yield_task)();     // 让出CPU
    void (*check_preempt)();  // 抢占检查
    struct task_struct *(*pick_next_task)(); // 选择下一个
    void (*put_prev_task)();  // 放回前一个
    void (*set_next_task)();  // 设置下一个
    void (*task_tick)();      // 时钟中断
    void (*switched_to)();    // 切换到此类
    void (*prio_changed)();   // 优先级改变
};

进程状态定义:
#define TASK_RUNNING         0x00
#define TASK_INTERRUPTIBLE   0x01  
#define TASK_UNINTERRUPTIBLE 0x02
#define __TASK_STOPPED       0x04
#define __TASK_TRACED        0x08
#define TASK_IDLE            0x80
#define TASK_NEW             0x800

状态转换图:
           fork()
    [NEW] -------> [RUNNABLE] <----
      |               ^  |         |
      |            调度|  |阻塞     |唤醒
      v               |  v         |
   [RUNNING] -------> [SLEEP] -----
             时间片用完   ^
                         |
                     I/O等待/锁等待

// 设置状态并检查条件的原子操作
set_current_state(TASK_INTERRUPTIBLE);
if (!condition) {
    schedule();  // 原子地检查并睡眠
}
set_current_state(TASK_RUNNING);

context_switch(prev, next):

1. 切换地址空间(如果需要)
   if (prev->mm != next->mm)
       switch_mm(prev->mm, next->mm)

2. 切换处理器状态
   switch_to(prev, next, last)

__switch_to:
    // 保存prev的寄存器到栈
    pushq %rbp
    pushq %rbx  
    pushq %r12-r15

    // 切换栈指针
    movq %rsp, TASK_threadsp(%rdi)  // 保存prev的rsp
    movq TASK_threadsp(%rsi), %rsp  // 加载next的rsp

    // 恢复next的寄存器
    popq %r15-r12
    popq %rbx
    popq %rbp

    // 更新per-CPU的current指针
    movq %rsi, PER_CPU_current

    retq  // 返回到next的执行点

TLB刷新策略:

1. 完全刷新: invlpg/flush_tlb_all() - 开销大
2. ASID/PCID: 进程地址空间标识符 - 避免刷新
3. 惰性TLB: 内核线程借用地址空间 - 延迟刷新

惰性TLB模式:
if (!next->mm) {  // 内核线程
    next->active_mm = prev->active_mm;
    原子增加引用计数
    进入lazy TLB模式
}

每个CPU维护独立的运行队列，减少锁竞争:
DEFINE_PER_CPU(struct rq, runqueues);

负载均衡:

- 定期均衡(tick时)
- 空闲均衡(CPU空闲时)  
- 新任务均衡(fork时)
- exec均衡(exec时)

调度域层级:
    [NUMA NODE 0]     [NUMA NODE 1]
         |                 |
    [PACKAGE 0]       [PACKAGE 1]  
       /    \           /    \
   [CORE0][CORE1]  [CORE2][CORE3]
     / \    / \      / \    / \
   SMT SMT SMT SMT  SMT SMT SMT SMT

// 快速选择下一个任务
if (likely(prev->sched_class == &fair_sched_class &&
           rq->nr_running == rq->cfs.h_nr_running)) {
    // 只有CFS任务，直接从红黑树选择
    next = pick_next_task_fair(rq, prev);
}

// 错误 - 破坏父进程栈帧
if (vfork() == 0) {
    return 0;  // 危险！
}

// 正确
if (vfork() == 0) {
    _exit(0);  // 直接退出，不执行清理
}

// 父子进程共享文件偏移量
int fd = open("file", O_RDWR);
if (fork() == 0) {
    write(fd, "child", 5);  // 可能与父进程写入交错
}
write(fd, "parent", 6);

// 忙等待 - CPU密集
while (!ready) {
    sched_yield();  // 如果没有其他就绪任务，立即返回
}

// 正确方式 - 使用条件变量或信号量
pthread_cond_wait(&cond, &mutex);

// RT任务等待普通任务持有的锁
// 解决方案：优先级继承协议或优先级天花板

// 将所有线程绑定到一个CPU - 性能灾难
CPU_ZERO(&cpuset);
CPU_SET(0, &cpuset);
pthread_setaffinity_np(thread, sizeof(cpuset), &cpuset);

echo 1 > /sys/kernel/debug/tracing/events/sched/enable
cat /sys/kernel/debug/tracing/trace

perf sched record -- ./workload
perf sched latency

watch -n 1 'cat /proc/sched_debug'

cat /proc/[pid]/sched
cat /proc/[pid]/schedstat