COS: A User-space Scheduling Framework

Reference:

项目总仓库

项目文档

ghOSt论文

COS-Kernel

COS-Userspace

在准备面试的过程中，以目前的水平重新审视半年前的这个项目，温故而知新，感觉又有了许多新的感悟。加之以前仅记录了参赛的感受和个人贡献，而没有记录对这整个项目的一个全面介绍，故而，今天我就稍微趁热打铁一下，结合项目文档、ghOSt论文、COS框架代码，来进行一个综合的介绍。

注：本文章的写作目的主要还是为了我自己整合一下知识，所以可能存在部分词不达意（？）、省略跳过的地方，并且全文组织逻辑也不是一篇完整的文章。如果有人对某部分有疑惑，欢迎联系我进行讨论。

基本介绍

COS是对ghOSt的一个从零开始的小型复现，支持了其基本功能，并且可以基于它实现多种多样较为复杂的调度算法。同时针对ghOSt在部分情景下的不足做了一些小优化，使得具有一定抗干扰性，同时能够支持简单的cgroup功能。

我们修改了Linux内核，增加了大约1500LoC。并且，我们还搭建了COS用户态，提供了比较全面实用的接口，还有许多调度算法实现实例（FIFO（开源）、Shinjuku（开源，一个多级队列时间片抢占的简要实现形式）、SJF、MFQ和DDL等）。

Background

在本部分中，我将结合ghOSt论文中的表述，以及实际开发过程中的感悟，对背景部分进行介绍。下面的内容这页PPT足以概括：

具体来说:

业界情况

1. Linux调度类机制

   面向对象设计：调度类接口+多个具体实现类（CFS，FIFO，RR，DDL……）

2. 优化对象：data center

3. 面临挑战：

   1. 逐渐牛掰的硬件（如CPU增多），还有新特性（如SMT、NUMA）；

   2. 安全性要求（需要隔离部分线程到部分CPU运行）；

   3. Linux调度类具有通用性不具专用性；

   4. Linux原生per-CPU模型不足以支持。

      注意，此处其实门道还是蛮多，详情可见本人这边写的和这边写的。

此处具体来说，可以以Shinjuku OS一文中的说法为例。对于现实中那些短请求较多的workload，比如说搜索引擎、FaaS、In-memory DB（支持简单的get/put和长请求range query）等，从理论上来说，使用Processor Sharing(PS)的调度策略会防止高尾延迟，而这PS就可以类似为一种跟RR比较相似的时间片策略。这也很符合直觉，因为RR一类的策略具有公平性和均等性的特点，使得短请求不至于被运行到完成的长请求饿死。

那么，为什么不能用Linux原生的real-time策略？我认为主要有两点原因：

1. 稳定性 用real-time策略可能导致内核不稳定，因为实时调度类在内核中调度优先级最高
2. 性能问题 Linux的real-time策略需要进行频繁的中断、上下文切换，开销较大较笨重，不够轻量级；Per-CPU策略只能让worker自己中断监测时间【主要原因】

故而，Shinjuku OS的解决方法是直接设置一个轻量级的专用OS，ghOSt则是将这个RR策略委托在了用户态实现，并且设立一个centrallized的线程集中控制，就避免了频繁的中断开销。

传统方法

1. 新增Linux调度类，从而新增新的调度算法

   编码困难，部署开销大，而且很难随着linux内核维护

2. 研发针对特定场景优化的专用OS（Shinjuku、Shenango）

   很难随着linux内核维护，需要对内核和应用程序都做修改

3. 仅适用用户态线程是不够的

   用户级线程的基本思路是，将M个用户级线程多路复用到N个内核线程上。

   缺点：不可预测

   ​ 首先你不知道它会被调度到哪个CPU上，也不知道它会什么时候停止，万一停的时候拿着锁就g了……

用户态调度框架

用户态编写自定义调度策略，调度Linux线程

1. Decouple：解耦了 内核调度类机制 (不变) 和 用户态调度策略 (变)（这点说得很本质）
2. Convenient：无需改变现有应用程序；提供很多供开发使用的接口；支持热更新
3. Flexible：可自定义实现多种调度策略 (如SJF、MFQ……)；支持快速调度；可以与别的调度策略共存

用户态调度框架分为内核实现和用户实现：内核通过为用户态提供接口（系统调用，eBPF钩子），将策略决策委托给用户空间；用户则通过内核提供的接口在用户态搭建部署自己的调度策略。

Motivation

线程调度

1. 线程本质上是一种状态机

   

2. 所以线程调度算法最关键需要做到这两点：

   ①当线程状态发生变化，do something；（e.g. FIFO入队当线程变为runnable）

   ②通过某些规则从runqueue挑选线程调度。（e.g. FIFO pick next依据FCFS rule）

3. 故而实现用户态调度框架最本质的两个关键（下以序号来指代）：

   ①感知线程状态变化；（信息流向：Kernel→Userspace）

   ②告知调度决策；（信息流向：Userspace→Kernel）

Linux调度类机制

1. 面向对象设计：调度类接口+多个具体实现类（CFS，FIFO，RR，DDL……）。

2. 每次调度（__schedule）时，依照调度类优先级从高到低，一次调用对应调度类的钩子函数pick_next_task。

3. 每个CPU对应一个rq结构体，代表其任务队列。

4. 线程调度分为两种：

   1. 本地调度（Per-CPU Model）

      target线程的target CPU和发出调度指令的线程所在CPU是同一个，此时，会暂时让出自己的CPU给此target线程运行；

   2. 远程调度（Centrallized Model）

      target线程的target CPU和发出调度指令的线程所在CPU不是同一个，此时则需要硬件的支持，通过IPI（Inter-Processor Interrupt）来发送中断给对应的CPU，让其进行reschedule。

现有方法

1. eBPF效率不高（EXT）

   ①②两点通过eBPF实现

   1. 编码不便捷，受可表达性限制

   2. bpf程序一般都是同步的

      也即，当线程状态发生变化，cpu必须block，直到bpf那边把事件处理完了（比如进行调度决策等），cpu才能继续润。

      不像ghOSt是异步，cpu只需要发个消息，然后继续润，等待ghost打断就行。不得不说，这也是一个非常完美的中断思想的体现！！！

   3. 被动调度

      bpf的用户态调度框架思路是无任务可跑了才触发，并且受CFS线程优先级限制，不像ghost和cos一样主动打上去就行

   EXT的整体实现也是很有意思的，内核中许多地方的修改处理都很牛逼，我也是跟着它学习了不少eBPF的写法。EXT的内核实现不是这里的重点，具体可以看项目文档中关于EXT内核介绍的部分。

2. ghOSt

   ①共享内存；②系统调用。复现目标。

   1. 不抗干扰
   2. 不支持CGroup

故而，基于上述全部，我们决定开发COS：对ghOSt的简化复现，并给出了对它现存问题的解决思路。

Design

Overview

总体框架

1. 内核态：COS调度类

2. 用户态：Lord线程

3. 用户态至内核态通信：系统调用

4. 内核态至用户态通信：消息队列

5. Cgroup简单支持

用户态示范

FIFO Scheduler

Kernel: COS调度类

COS在内核中新增一个调度类，类似常用的CFS调度类。这个调度类向用户态提供一组系统调用来供用户态定义任意调度策略，同时负责执行用户态传入的调度策略。

DEFINE_SCHED_CLASS(cos) = {
	.enqueue_task		= enqueue_task_cos,
	.dequeue_task		= dequeue_task_cos,
	.check_preempt_curr	= check_preempt_curr_cos,
	.pick_next_task		= pick_next_task_cos,
	.task_dead = task_dead_cos,

#ifdef CONFIG_SMP
	.select_task_rq		= select_task_rq_cos,
	.task_woken     = task_woken_cos,
#endif
#ifdef CONFIG_UCLAMP_TASK
	.uclamp_enabled		= 0,
#endif
};

COS调度类优先级位于CFS之下，目的是不影响CFS的稳定运行，若在CFS之上，可能会造成CFS线程饿死，值得注意的是负责维持着内核的稳定性内核线程都是CFS调度类，如果这些线程得不到及时运行，会导致内核崩溃。

Lord线程调度类优先级则高于CFS等调度类，仅次于STOP调度类，这确保它能够一直运行在它绑定的CPU上，实时做出调度决策，避免因为被其他线程抢占而导致暂时得不到运行而导致调度时延。

DEFINE_SCHED_CLASS(cos_lord) = {
	.pick_next_task		= pick_next_task_cos_lord,
};

User: Lord线程

基本实现

Lord线程位于用户态，负责部署调度算法传入内核。用户程序可以通过set_lord()系统调用将自己绑定在指定CPU上，开启内核COS调度，成为Lord线程。只有Lord线程才有调度其他COS调度类线程（下称COS线程）的特权。同一个主机上只能有一个Lord线程，若已经有其他线程设置自己为Lord线程，则该系统调用会返回错误。

int cos_do_set_lord(int cpu_id) 
{
	struct task_struct *p = current;
	// 1. 设置cpu mask，并且将lord迁移到cpu_id对应CPU上
	// xiunian: 其原理是简单的调用set cpu allow相关内核函数，我猜测里面应该会有一个出队入队的情况
	cos_move2target_rq(cpu_id);
    
	// xiunian: COS作为简化实现，只允许一个主机同时只存在一个lord线程
	if (cos_on) 
		return -EINVAL;
	spin_lock_irqsave(&cos_global_lock, flags);

    // 2. 设置为COS调度类
	struct sched_param param = {
		.sched_priority = 0,
	};
	sched_setscheduler(p, SCHED_COS, &param);
	// 3. 修改状态信息
	rq = cpu_rq(cpu_id);
	open_cos(rq, p, cpu_id); // rq->cos.lord、lord_on_rq、lord_cpu、cos_on、lord、cg_init

	spin_unlock_irqrestore(&cos_global_lock, flags);
	return ;
}

而为了保证用户态调度算法调度决策的及时进行，我们需要将Lord线程绑定在它运行核上，并且设置它的优先级为最高，使得它无法被其他CFS线程抢占。

这个优先级最高以及绑核是怎么实现的呢？具体来说，我们在内核中增设了一个COS Lord调度类，其优先级差不多处于所有调度类的巅峰：

DEFINE_SCHED_CLASS(cos_lord) = {
	.pick_next_task		= pick_next_task_cos_lord,
};

我们在其pnt钩子函数中，如果它是lord所在CPU，则不断返回lord：

struct task_struct *pick_next_task_cos_lord(struct rq *rq) {
    // 仅有lord所在CPU设置了rq->cos.lord（在open_cos中），其余CPU皆为NULL
	if (rq->cos.lord != NULL && task_is_running(rq->cos.lord) && lord_on_rq) {
		return rq->cos.lord;
	}
	return NULL;
}

这样一来，就做到了Lord线程的高优先级以及绑核效果。

Discussion

ghOSt为了保证系统的稳定性，实现了Agent（类似于COS的Lord） thread的Migration，也即当有重要的内核CFS线程要运行在Agent所在CPU时，Agent会默默退让当前CPU，迁移到其他CPU上。为了简单起见，COS没有实现该功能，并且设定将Lord thread绑定在CPU id较大的CPU上（因为重要的内核线程一般都运行在0-2号CPU），从而缓解该矛盾。而后续的Evaluation部分也暂未因该问题产生较大影响，故而暂且不作考虑。

感知线程状态变化

消息队列的结构

内核会将线程状态的变化信息通过共享内存实现的消息队列传递到Lord线程。

由于COS实现假定全局只有一个Lord，故而仅需设置一个global的消息队列即可：

struct cos_message_queue *global_mq;

Lord线程在调用set_lord后，会紧接着调用create_msg_queue来创建消息队列：（此处共享内存的queue_fops未做了解（其实是了解过然后忘了hhh），写法感觉还是比较套路，不做赘述）

int cos_create_queue(void) 
{
    // 1. 申请共享内存
	global_mq = vmalloc_user(sizeof(struct cos_message_queue));
	// 2. 以fd形式（匿名inode）使用
	int fd = anon_inode_getfd("[cos_queue]", &queue_fops, global_mq,
			      O_RDWR | O_CLOEXEC);
	return fd;
}

该段内存以环形队列形式组织。然后，内核这端就会在不同事件发生的时候，向共享内存写入消息，等待User的Lord线程从共享内存中取出消息，做出对应的调度决策，即可。

int produce_task_runnable_msg(struct task_struct *p) {
	return produce_task_message(MSG_TASK_RUNNABLE, p);
}
int produce_task_blocked_msg(struct task_struct *p) {
	return produce_task_message(MSG_TASK_BLOCKED, p);
}
int produce_task_new_msg(struct task_struct *p) {
	return produce_task_message(MSG_TASK_NEW, p);
}
int produce_task_dead_msg(struct task_struct *p) {
	return produce_task_message(MSG_TASK_DEAD, p);
}
int produce_task_preempt_msg(struct task_struct *p) {
	return produce_task_message(MSG_TASK_PREEMPT, p);
}
int produce_task_new_blocked_msg(struct task_struct *p) {
	return produce_task_message(MSG_TASK_NEW_BLOCKED, p);
}
int produce_task_cos_preempt_msg(struct task_struct *p) {
	return produce_task_message(MSG_TASK_COS_PREEMPT, p);
}

消息发送的时机

这里其实还是稍显复杂的，建议去看看文档（3.2.3部分）吧，欣赏一下我这部分完美的图。印象中是task preempt卡了我们不久，我研究了很久才发现了它是需要一个排除法机制，还挺有意思的。

看完了文档之后，这里对具体涉及到的代码进行一个小注释。

首先是这里的cos_prepare_task_switch了。它负责发送task new、task preempt消息，可谓是重点之一了。顾名思义，它会在调度上下文切换之前被调用。

其中有一点需要注意，对于task new的情况，COS调度类不支持调度类遗传，即一个线程新建时候它的调度类不可能是COS。线程只能调用sched_setscheduler系统调用将自己调度类设置为COS，在这个过程中，线程需要先下CPU。而之所以在这里才发送task new消息，不是在sched_setscheduler时就发送消息，是为了防止这样一种竞态情况：sched_setscheduler发送消息→用户态接收消息并马上调度到某个CPU，但此时该线程还没有从原来的CPU上下来，这时就会导致一个线程同时在两个CPU上运行，从而g。

void cos_prepare_task_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next) 
{
	if (cos_policy(prev->policy) && prev->cos.is_new) {
		if (task_on_rq_queued(prev)) {
			produce_task_new_msg(prev);	// 此时新任务可运行
		} else {
			produce_task_new_blocked_msg(prev);	// 此时新任务不可运行
		}
		prev->cos.is_new = 0;
		return;	// 排除法1：不是task new
	}

	if (prev->cos.is_blocked) // 排除法2：不是task block
		return;

    // 排除结束，那就是task preempt了
	if (cos_policy(next->policy)) 
		produce_task_cos_preempt_msg(prev);
	else 
		produce_task_preempt_msg(prev);
		
}

除此之外，其它几个消息的发送时间不甚特殊，在此不做赘述。

用户与内核同步

内核必须保证用户态Lord线程消费消息的实时性。每条消息都有一个seqnum，来检测Lord每次做出调度策略的时候，是否已经消费完最新的消息。内核通过维护下一个要分配的seq num：a，与Lord每次做出调度决策时传入的已消费消息的最大seq num：b对比，若b不等于a + 1，意味着Lord还有消息没有消费，内核会拒绝本次调度决策。

告知调度决策

基本实现

shoot系统负责将用户态的调度策略传递到内核态。在COS的实现中，我们也是实现了组提交以增加效率。

我们使用共享内存shoot area负责存储一次部署中用户态调度策略传入内核的参数，例如target TID、target CPU、seq num等，并且可以反馈本次调度是否成功；我们使用shoot_task()系统调用将一组调度策略传入内核。

int cos_do_shoot_task(cpumask_var_t shoot_mask) 
{
	preempt_disable();
	for_each_cpu(cpu_id, shoot_mask) {	// 进行一个global的check
        // 获取对应shoot area上本次要调度的线程
		pid = task_shoot_area->area[cpu_id].pid;
		p = find_process_by_pid(pid);
		if (!p) continue;
		get_task_struct(p);

        // 几个调度失败场景，出现可能是因为用户态调度策略写错了
		if (unlikely(p->cos.is_dying)) {	// target thread已经寄了
			task_shoot_area->area[cpu_id].info = _SA_ERROR;
			continue;
		}
		if (unlikely(!task_is_running(p))) {	// target thread已经在跑了
			task_shoot_area->area[cpu_id].info = _SA_ERROR;
			continue;
		}

		// 准备开始shoot
		rq = cpu_rq(cpu_id);
		// xiunian: 多次对同一CPU的shoot视为抢占，所以只需一个变量记录next schedule即可
 		rq->cos.next_to_sched = p; 
		rq->cos.is_shoot_first = 1;
        
		if (cpu_id == lord_cpu) {
			need_local_shoot = true;
		} else {
			__cpumask_set_cpu(cpu_id, ipimask);
		}
	}

	// 发送远程IPI
	cos_remote_shoot(ipimask);

	if (need_local_shoot) {	// 本地调度
		lord_on_rq = 0;
		cos_local_shoot();
		lord_on_rq = 1;
	}

	preempt_enable_no_resched();
	return 0;
}

void cos_remote_shoot(struct cpumask *ipi_mask) {
	int cpu;
    struct rq_flags rf;
    
    rq_lock_irqsave(rq, &rf);
    !test_tsk_need_resched(rq->curr) && set_nr_and_not_polling(rq->curr);
    rq_unlock_irqrestore(rq, &rf);
    
	VM_BUG_ON(this_rq()->cos.lord != current);
	if (!cpumask_empty(ipi_mask)) {
		apic->send_IPI_mask(ipi_mask, RESCHEDULE_VECTOR);
	}
}

值得注意的一点是，COS对于per-CPU model和centrallized model的支持。对于centrallized model的支持还是显而易见的，值得注意的是对per-CPU model的支持。

当线程需要shoot到lord所在CPU，如果不做任何操作，它是会被优先级更高的Lord class拦截的。故而，引入lord_on_rq这个全局变量。在reschedule之前，将lord_on_rq（全局变量）置为false。这样一来，在pick_next_lord中就会返回NULL，也即跳过Lord class，去Cos class，调度target thread了，然后reschedule完再把lord_on_rq调为true。

if (rq->cos.lord != NULL && task_is_running(rq->cos.lord) && lord_on_rq) {
	return rq->cos.lord;
}
return NULL;

这样一来，相当于简单屏蔽了一会儿这个Lord class了，从而达到per-CPU的效果。如果要实现严格的per-CPU，我们可以在sendmsg的时候才把这个lord_on_rq置为true，从而有一种唤醒的效果。这样一来就需要对这个lord_on_rq进行并发保护了。

动态优先级提升

在一些场景（比如说使用于burst的情况，也即一开始没有很多请求，所以跑了多个负载，然后突然爆发很多请求，这种情况下需要快速抢占CFS线程），需要快速对COS线程进行调度，无视干扰线程。然而，为了确保系统稳定，COS调度类优先级低于CFS调度类。故而，我们采取了一种动态优先级提升的方法来解决这个问题。在一个COS线程被调度到目标CPU上时候，此时我们将其优先级短暂地提升到最高，之后当目标CPU调用schedule函数挑选其上CPU执行的时候，在将其优先级下降到CFS之下，这样就兼顾了性能与系统稳定性。

然而，优先级在Linux初始化时便确定下来，按存储的物理地址从高到低确定，是定死的。故而，我们借助Lord class的高优先级，来实现这一动态优先级提升。

具体来说，我们存储一个per-CPU的变量is_shoot_first。在目标线程刚刚被Lord部署到目标CPU上时，拉高电平is_shoot_first：

	rq->cos.next_to_sched = p; 
rq->cos.is_shoot_first = 1;

在Lord class之中，当is_shoot_first被拉高，就说明有COS线程刚刚需要被部署，我们返回即可：

struct task_struct *pick_next_task_cos_lord(struct rq *rq) {
	if (rq->cos.next_to_sched != NULL && task_is_running(rq->cos.next_to_sched) && rq->cos.is_shoot_first) {
		rq->cos.is_shoot_first = 0;
		return rq->cos.next_to_sched;
	}
}

这样就成功借助了Lord class的高优先级来实现优先调度。

Discussion

值得注意的是，ghOSt这边是将这个shoot采取了一个事务机制，感觉这个起名真是说到本质了。二者都同样是对某个执行过程的记录，负责统筹全局，并且也同样具有原子性，感觉真的非常合适。COS为了简单起见，没有实现这个。

简单的Cgroup实现

为了契合题意（赛题要求支持cgroup），COS支持cgroup对CPU使用率的限制。COS额外提供了四个系统调用。

COS负载线程可以随意将自己添加入一个cgroup，或者删除。同时也可以调整cgroup的CPU使用率，如80%，意味着当前cgroup中的所有线程对CPU的使用率最大值为80%，例如在1ms内最多只能获取0.8ms的运行时间。这意味着COS能够支持云原生场景中的容器。

这里可能稍微偷了个懒，没有去兼容Linux原生Cgroup，而是实现了一个限制CPU使用率的小功能（因为时间不够了2333）。

这部分还是比较简单的，其实可以去看这个开发思路文档，思路写得更详细更具体，在此就只说说基本思路了。实现cgroup的基本逻辑：

多个cgroup通过链表形式链接，都有一个cg id。然后，每个task可以通过cg_ctl来把自己加入某个cgroup或者从某个中删除，每次调用task_tick都会检查一下salary是否耗尽，耗尽则reschedule，并且设置pnt那边salary<=0就不return。同时，在context switch之前也会update on cpu和off cpu，纪录更精确的CPU时。

Evaluation

这部分确实没什么好说的（虽然也很挣扎……）具体看项目文档吧。

不过有一点目前还是比较存疑，也即那个RocksDB场景似乎不是I/O密集型而是计算密集型（）因为具体的RockDB数据库是In-memory的，并且每个请求也都是polling一段纯粹的CPU工作时来模拟请求的处理，所以我认为当初这方面我们的认知出了点问题，不过看起来影响不大。