记录一些开发过程中对Linux kernel的阅读&研究，一些认知性的东西真的很容易忘……

注意，全都是个人猜想，很多我还自己不大明白，所以都是阶段性结论，也欢迎指正

Scheduling

ghOSt

这几天一直在阅读ghOSt的论文及其源码实现，站在目前的知识水平上来看相比于以前有了不少收获，在这里简单记录一下。

24.4.11

per-CPU和Centralized思考

Linux的原生实现逻辑就是典型的per-CPU model：
有一个专门的schedule的idle上下文（或者说idle调度类），当有线程时执行调度逻辑pick target thread，然后switch to；当线程被抢占or完成时再次切回idle上下文进行下一轮pick。调度了则执行对应线程，否则执行调度逻辑，以此类推，这就是典型的per-CPU。

也因此，虽然centralized model被证明很多时候更高效（比如说Shinjuku os），但确实是很难实现，估计得修改个大架构。好在，有了ghOSt，我们就把繁琐的逻辑从内核实现移到了用户实现，这就能同时简单地支持per-CPU和centralized了，不得不说确实真的是很伟大的发明。

24.4.12

Linux内核抢占调度机制

在Linux内核上实现抢占式调度具体是个什么样的运作方法呢？我们可以分情况讨论：

  1. 在单CPU情况下

    一开始，CPU位于idle线程，os启动时切换上下文到Bash中。创建线程时，将线程加入该CPU调度队列中。多进程情况下，线程运行时会发生时钟中断，在时钟中断中检测计算时间片，发生上下文切换回idle进程继续reschedule。

  2. 在多处理器情况下

    也是差不多的，一个CPU上运行的线程A创建了另一个线程B，这时候有两种情况：

    1. 线程B优先级更高

      kernel会直接把B抢占了A

    2. 线程B优先级比A低

      kernel会把B推开去抢占别的CPU，除非B只能在当前CPU运行

其中，第二种情况稍显复杂，我们可以详细来说说。【下以deadline为例，因为别的比如说RR是非抢占式调度】

首先，全局只有一个调度类对象（不考虑什么多个调度策略，或者说一个线程组只有一个调度类对象，差不多这个意思）。也就是说，创建线程会进入该调度类对象中，然后挑选线程也是从该调度类对象中pick。

当一个CPU上运行的线程A创建了另一个线程B，并且假设目前其他CPU跑满了任务，线程B的优先级很高。创建线程的相关syscall最终会调用activate_task【这点暂时存疑】，然后activate_task会调用调度类中的enqueue_task事件，将线程B压入到deadline调度类的红黑树中。activate_task结束返回之后，紧随其后一般会接一个resched_curr，也即将当前CPU reschedule。

这里，就需要分情况讨论了。

  1. 当线程B优先级>线程A优先级

    当前CPU进入到__schedule函数中，就会调用调度类的pick_next_task进而调用set_next_task，从而使得线程B抢占线程A，线程A重新入队，over。

  2. 当线程B优先级<=线程A优先级

    每个CPU进入到__schedule函数中，都会调用调度类的pick_next_task进而调用set_next_task，从而调用该函数：

    1
    2
    3
    4
    5
    6
    7
    static inline void deadline_queue_push_tasks(struct rq *rq)
    {
    	if (!has_pushable_dl_tasks(rq))
    		return;

    	queue_balance_callback(rq, &per_cpu(dl_push_head, rq->cpu), push_dl_tasks);
    }

    该函数以回调形式实现。之后，由于线程B优先级<=线程A优先级，最终会在__schedule中进入该分支：

    1
    2
    3
    4
    5
    if (likely(prev != next)) {
        ...
    } else {
        __balance_callbacks(rq);
    }

    从而调用__balance_callbacks来执行当前CPU上的所有balance callback，从而执行push_dl_tasks。该函数会将自身队列中未运行的线程，发送到那些合适的CPU上进行适当抢占：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /*
     * See if the non running -deadline tasks on this rq
     * can be sent to some other CPU where they can preempt
     * and start executing.
     */
    static int push_dl_task(struct rq *rq)
    {
    	next_task = pick_next_pushable_dl_task(rq);
    	// 找到一个合适的CPU（包括pick算法，以及查看next_task是否能抢占它的curr）
    	later_rq = find_lock_later_rq(next_task, rq);
    	// 将next_task迁移到target CPU上
    	deactivate_task(rq, next_task, 0);
    	set_task_cpu(next_task, later_rq->cpu);
    	activate_task(later_rq, next_task, 0);
    	// 通过发生IPI使其reschedule
    	resched_curr(later_rq);
    	return ret;
    }

    故而，此时线程B就可以抢占别的CPU了。

综上所述，如此串联一下，我们可以归纳总结一下当CPU上运行的线程A创建了一个新的线程B时的执行链路：

  1. B优先级更大：

    原CPU：创建线程syscall→fork()→wake_up_new_task→sched_class->task_woken→执行check_preempt_curr→执行__schedule→pick出B，抢占A，over

  2. B优先级更小：

    原CPU：创建线程syscall→fork()→wake_up_new_task→sched_class->task_woken

    此时：

    1. 如果该CPU无需reschedule：→执行push_dl_task，迁移该线程，发送IPI→返回用户态

    2. 如果该CPU需要reschedule：task_woken无事发生，返回→执行__schedule→无事发生，B依然在原CPU的数据结构中→执行__balance_callbacks→执行push_dl_task，迁移该线程，发送IPI→返回用户态

其实这整个过程的链路是很好追踪的，为什么我花了很久呢：

ecad9f39d64acccafd9bca9958dfafce

因为我想找push_dl_task结果一直在看pull_dl_task（如图所示……这位置实在很星际啊hhh）也即最终push和pull逻辑是反的，故而我匪夷所思想了半天都没懂hhh……

不过这也让我些许看懂了balance的架构。每个CPU都有一个balance callback的队列，互相之间可以通过这种适时的、异步的调用pull或者push的callback来实现任务窃取，从而实现运行队列的负载均衡。

per-CPU和Centralized思考

  1. 在单CPU情况下，一开始，CPU位于idle线程，os启动时切换上下文到Bash中。创建线程时，将线程加入该CPU调度队列中。多进程情况下，线程运行时会发生时钟中断，在时钟中断中检测计算时间片，发生上下文切换回idle进程继续reschedule。
  2. 在多处理器情况下也是差不多的，一个CPU上运行的线程A创建了另一个线程B，并且线程B优先级更高，那么此时kernel就会可能综合考虑什么负载均衡之类的算法挑选出target CPU，将线程B入其队列，然后通过IPI让target CPU进行重新调度。

可以很震惊地发现，其实在Linux原生环境中，对于多处理器情况，单纯的per-CPU model为了做到负载均衡，其实已经逐步向centralized model靠拢了，相当于所有CPU都是一个暂时的c位。只不过，这种情况的劣势也很显然，也即我们不得不让工作线程暂停去工作，转而进行这一系列的send IPI（虽然这是异步的），这过程中的各种执行开销，然后估计还要什么获得锁之类的保证同步，感觉开销很大。

比如说，如果使用ghost，其调用链路会从最坏情况：

创建线程syscall→fork()→wake_up_new_task→sched_class->task_woken，task_woken无事发生，返回→执行__schedule→无事发生，B依然在原CPU的数据结构中→执行__balance_callbacks→执行push_dl_task，迁移该线程，发送IPI→返回用户态

变成

创建线程syscall→fork()→over

故而，直接将这些c位工作集中在某个CPU上体现，相当于从原来的均摊开销变为集中开销，可以使得worker CPU更专注于手头的工作，创建线程只需加入agent调度类的调度队列然后返回即可，无需进行更多操作，也是精简了许多开销。

也因此，我们可以很清楚了解到per-CPU在data center场景下的劣势。DC的CPU那么多，你每个CPU都需要一点额外开销，虽然也是均摊了，单估计加起来的开销会大于集中调度，因为后者省去了多线程访问调度数据结构（比如CFS红黑树）之类的并发控制开销。故而，在这种data canter的场景下运行ghost的优势，是显而易见的。