函数切入点

4888行：context_switch

context_switch ——切换到新的内存和新线程的寄存器状态。

static __always_inline struct rq * context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next, struct rq_flags *rf)

查找引用，发现被同文件中的 __schedule 函数引用过。

6165行：__schedule⁴

__schedule() 是一个主要的调度器函数。

驱动调度器即进入这个函数的主要途径有：

1. 显式阻塞：互斥锁、信号量、等待队列等。

2. 在中断和用户空间返回路径上检查TIF_NEED_RESCHED标志，实例可以参见arch/x86/entry_64.S。
   为驱动进程间的抢占，调度器在定时器中断处理程序scheduler_tick()中设置该标志。

3. 唤醒进程并不会导致进入调度函数，而是会在运行队列中添加一个任务。
   现在，如果添加到就绪队列的新进程抢占了当前进程，那么wakeup函数会设置TIF_NEED_RESCHED，并在最近的可能场合调用schedule():

   • 如果内核是可抢占的(CONFIG_PREEMPTION=y)：

     • 在系统调用或异常上下文中，在最外层的下一个preempt_enable()。（这可能就和wake_up()的spin_unlock()一样快！）
     • 在IRQ上下文中，从中断处理程序返回到可抢占上下文

   • 如果内核是不可抢占的(CONFIG_PREEMPTION没有被设定)，那么：

     • cond_resched() 调用
     • 显式的 schedule() 调用
     • 从系统调用或者异常返回用户空间
     • 从中断处理程序返回到用户空间

警告：必须在禁用抢占的情况下调用

static void __sched notrace __schedule(unsigned int sched_mode)

4952行：nr_running

外部可见的统计信息：当前可运行线程的数量。

unsigned int nr_running(void)

5658行：pick_next_task⁵

挑选合适的进程

static struct task_struct *pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)

知识点

进程控制符——task_struct

声明在 linux/sched.h 中：

unsigned long nvcsw, nivcsw;

进程描述符中有 nvcsw, nivcsw两个字段，它们的注释只有一个“context switch counts”
nvcsw: 自愿的上下文切换
nivcsw: 非自愿的上下文切换
当线程因为需要不可用的资源而阻塞时，就会发生自愿的上下文切换。当线程在其时间片期间执行或当系统识别出要运行的高优先级线程时，就会发生非自愿的上下文切换。

unsigned int __state;

其值是由对应状态的宏值通过相与运算得到的

#define TASK_RUNNING        0//进程要么正在执行，要么准备执行
#define TASK_INTERRUPTIBLE  1 //可中断的睡眠，可以通过一个信号唤醒
#define TASK_UNINTERRUPTIBLE    2 //不可中断睡眠，不可以通过信号进行唤醒，等待资源有效时唤醒（比如等待键盘输入、socket连接、信号等等），但不可以被中断唤醒. 
#define __TASK_STOPPED      4 //进程停止执行
#define __TASK_TRACED       8 //进程被追踪
/* in tsk->exit_state */ 
#define EXIT_ZOMBIE     16 //僵尸状态的进程，表示进程被终止，但是父进程还没有获取它的终止信息，比如进程有没有执行完等信息。                   
#define EXIT_DEAD       32 //进程的最终状态，进程死亡
/* in tsk->state again */ 
#define TASK_DEAD       64 //死亡
#define TASK_WAKEKILL       128 //唤醒并杀死的进程
#define TASK_WAKING     256 //唤醒进程

调度延迟

所谓「调度延迟」，是指一个任务具备运行的条件（进入 CPU 的 runqueue），到真正执行（获得 CPU 的执行权）的这段时间。那为什么会有调度延迟呢？因为 CPU 还被其他任务占据，还没有空出来，而且可能还有其他在 runqueue 中排队的任务。

排队的任务越多，调度延迟就可能越长，所以这也是间接衡量 CPU 负载的一个指标（CPU 负载通过计算各个时刻 runqueue 上的任务数量获得）。

首先来看调度周期，调度周期的含义就是所有可运行的 task 都在CPU上执行一遍的时间周期，而 Linux CFS 中这个值是不固定的，当进程数量小于8的时候，sched period 就是一个固定值6ms，如果 runqueue 数量超过了8个，那么就保证每个 task 都必须运行一定的时间，这个一定的时间还叫最小粒度时间，CFS的默认最小粒度时间是0.75ms，使用 sysctl_sched_min_granularity 保存， sched period 是通过下面这个内核函数来决定的：

/*
* The idea is to set a period in which each task runs once.
*
* When there are too many tasks (sched_nr_latency) we have to stretch
* this period because otherwise the slices get too small.
*
* p = (nr <= nl) ? l : l*nr/nl
*/
static u64 __sched_period(unsigned long nr_running)
{
    if (unlikely(nr_running > sched_nr_latency))
        return nr_running * sysctl_sched_min_granularity;
    else
        return sysctl_sched_latency;
}

• nr_running 就是可执行 task 数量

调度周期是调度延迟吗，并且每一次计算都会给出一个确定的调度周期的值是多少，但是这个调度周期仅仅是用于调度算法里面，因为这里的调度周期是为了确保 runqueue 上的 task 的最小调度周期，也就是在这段时间内，所有的 task 至少被调度一次，但是这仅仅是目标，而实际是达不到的。因为系统的状态、task 的状态、task 的slice等等都是不断变化的，周期性调度器会在每一次 tick 来临的时候检查当前 task 的slice是否到期，如果到期了就会发生 preempt 抢，而周期性调度器本身的精度就很有限。 ↩︎

代码

输出队列长度

主要是参考了上次作业的 map.c 代码，摘取了其中获得队列长度的字段并进行了略微的修改。

重要的点是跟踪update_rq_clock函数可以获得struct rq结构，里面队列长度的记录。

主要修改了用户空间的代码，将 计算显示运行队列长度和 改为了 逐个显示各有任务cpu的队列长度。

from bcc import BPF
import time
code = """
#include <linux/sched.h>
struct rq {
	raw_spinlock_t lock;
	unsigned int nr_running;
	unsigned int nr_numa_running;
	unsigned int nr_preferred_running;
	unsigned int numa_migrate_on;
	long unsigned int last_blocked_load_update_tick;
	unsigned int has_blocked_load;
};
BPF_ARRAY(rq_map, struct rq, 1);
BPF_PERCPU_ARRAY(runqlen, u64, 1);
int update_rq_clock(struct pt_regs *ctx) {
	u32 key = 0;
	u32 rqKey = 0;
	struct rq *p_rq = 0;
	p_rq = (struct rq *)rq_map.lookup(&rqKey);
	if (!p_rq) { // 针对map表项未创建的时候，map表项之后会自动创建并初始化
		return 0;
	}
	bpf_probe_read_kernel(p_rq, sizeof(struct rq), (void *)PT_REGS_PARM1(ctx));
	u64 val = p_rq->nr_running;
	runqlen.update(&key, &val);
	return 0;
}
""" 
bpf = BPF(text=code)
bpf.attach_kprobe(event="update_rq_clock", fn_name="update_rq_clock")
while True:
    # 运行队列长度
    runqlen_list = bpf['runqlen'][0]
    for index, i in enumerate(runqlen_list):
        if i:
            print("cpu", index, ": ", i, end=", ", sep='')
    print()
    time.sleep(1)

运行结果：

具体核占用率

参考了lmp项目的 cpuutilize.py 代码

通过此代码我了解到可以使用bpf_get_smp_processor_id()函数来获取当前cpu。

此代码的追踪点为动态追踪点task_switch_finish，此追踪点可以获得切出进程的task_struct，因为容易变动，我将其改为了通配符形式。

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from bcc import BPF
from time import sleep

bpf_text = """
#include <linux/sched.h>
struct key_t {u32 cpu,pid,tgid;};
struct time_t {u64 total,idle;};
BPF_HASH(start, struct key_t);
BPF_HASH(dist, u32, struct time_t);
void pick_start(struct pt_regs *ctx, struct task_struct *prev) {
    u64 ts = bpf_ktime_get_ns();
    u64 pid_tgid = bpf_get_current_pid_tgid();
    struct key_t key;
    struct time_t cpu_time, *time_prev;
    u32 cpu, pid;
    u64 *value, delta;
    cpu = key.cpu = bpf_get_smp_processor_id();
    key.pid = pid_tgid;
    key.tgid = pid_tgid >> 32;
    start.update(&key, &ts);
    pid = key.pid = prev->pid;
    key.tgid = prev->tgid;
    value = start.lookup(&key);
    if (value == 0)
        return;
    delta = ts - *value;
    start.delete(&key);
    time_prev = dist.lookup(&cpu);
    if (time_prev == 0) {
        cpu_time.total = 0;
        cpu_time.idle = 0;
    } else
        cpu_time = *time_prev;
    cpu_time.total += delta;
    if (pid == 0)
        cpu_time.idle += delta;
    dist.update(&cpu, &cpu_time);
    return;
}
"""
b = BPF(text=bpf_text)
b.attach_kprobe(event_re="^finish_task_switch$|^finish_task_switch\.isra\.\d$", fn_name="pick_start")
dist = b.get_table("dist")
while True:
    try:
        sleep(1)
        print("%-6s%-16s%-16s%-6s%%" % ("cpu", "total", "idle", "percent"))
        for k, v in dist.items():
            print("%-6d%-16d%-16d%-6.4f%%" % (k.value, v.total, v.idle, (v.total - v.idle)/v.total))
        dist.clear()
    except KeyboardInterrupt:
        print("\b\bquit")
        exit()

运行结果：

调度延迟

「调度延迟」的计算得分两种情况：

1. 任务因等待 event 进入休眠态（Voluntary Switch），那么就是从被唤醒（“wakeup/wakeup_new” 的时间点），到获得 CPU （任务切换时的 “next_pid” ）的间隔。
2. 任务因 Involuntary Switch 让出 CPU（任务切换时作为 * “prev_pid”* ），到再次获得 CPU （之后的某次任务切换时作为 “next_pid” ）所经历的时间。在这期间，任务始终在 runqueue 上，始终是 runnable 的状态，所以有 “prev_state” 是否为 TASK_RUNNING 的判断。

from bcc import BPF
from time import sleep
code = """
#include <linux/sched.h>
struct taskData {
    u32 pid;
    char comm[TASK_COMM_LEN];
};
BPF_HASH(qtime, u32);
BPF_HASH(dist, struct taskData);
TRACEPOINT_PROBE(sched, sched_wakeup) {
    u64 ts = bpf_ktime_get_ns();
    u32 pid = args->pid;
    qtime.update(&pid, &ts);
    return 0;
}
TRACEPOINT_PROBE(sched, sched_wakeup_new) {
    u64 ts = bpf_ktime_get_ns();
    u32 pid = args->pid;
    qtime.update(&pid, &ts);
    return 0;
}
TRACEPOINT_PROBE(sched, sched_switch) {
    u64 *val, delta, ts = bpf_ktime_get_ns(); // 获取当期内核时间
    u32 pid = args->prev_pid;
    struct taskData data = {0}; // 将对齐所用的整个内存初始化为0，避免其作为键时查找失败
    if(args->prev_state == TASK_RUNNING)
        qtime.update(&pid, &ts); // 在qtime中记录
    pid = args->next_pid;
    val = qtime.lookup(&pid); // 查找切入进程的切出时间
    if(val) {// 找到，则更新时间片
        delta = ts - *val;
        data.pid = pid;
        bpf_probe_read_kernel_str(&data.comm, TASK_COMM_LEN, &args->next_comm);
        dist.update(&data, &delta);
        qtime.delete(&pid); // 删除切入进程的切出时间
    }
    return 0;
}
"""
aBPF = BPF(text=code)
dist = aBPF["dist"]
while True:
    try:
        print("%-16s %-10s %-10s" % ("comm", 'pid', 'delay/ms'))
        sleep(1)
        for k, v in dist.items():
            print("%-16s %-10d %-6f" % (k.comm.decode('utf-8'), k.pid, v.value/1000))
        print()
        dist.clear()
    except KeyboardInterrupt:
        print("\b\bquit")
        exit()

运行结果：

TOP5占用

CPU 前五大占用：ps axu|sort -r -k3 | head -n 6

内存前五大占用：ps axu|sort -r -k4 | head -n 6

top5占用说的是占用cpu最久的5个进程，在操作系统运行卡顿的情况下，查找这5个进程，对其中暂时不紧急的任务加以控制，就可以提高计算机的性能。

这里使用静态跟踪点sched:sched_switch来对各进程的切换进行追踪，记录每个进程的运行时间；最后，根据时间进行降序排序，便可获得top5进程。

from bcc import BPF
from time import sleep
code = """
#include <linux/sched.h>
BPF_HASH(start, u32);
BPF_HASH(dist, u32);
TRACEPOINT_PROBE(sched, sched_switch) {
    u32 pid = args->next_pid; // 获取切入进程号
    u64 ts = bpf_ktime_get_ns(), *val, delta;
    start.update(&pid, &ts); // 更新切入进程开始时间
    pid = args->prev_pid; // 获取切出进程
    val = start.lookup(&pid); // 寻找切出进程开始时间
    if(!val) // 找不到就退出
        return 0;
    delta = ts - *val; // 找到了，计算切出进程时间片
    start.delete(&pid); // 删除切出进程开始时间
    val = dist.lookup(&pid); // 查找切出进程总运行时间
    if(val) // 找到了，则总运行时间增加时间片，找不到，则初始化为时间片
        delta += *val;
    dist.update(&pid, &delta);
    return 0;
}
"""
aBPF = BPF(text=code)
dist = aBPF["dist"]
while True:
    try:
        sleep(1)
        arr = [(k.value, v.value) for k, v in dist.items()]
        # print(arr)
        arr.sort(key=lambda elem: elem[1], reverse=True)
        print("%-6s %-6s"%("pid", "time/ms"))
        for elem in arr:
            print("%-6d %-6f"%(elem[0], elem[1]/1e6))
        print()
        dist.clear()
    except KeyboardInterrupt:
        print("\b\bquit")
        exit()

运行结果：

↩︎

__schedule

形参表示此次是主动调度(false)抑或是抢占(true)。__schedule()主要做了两件事情：挑选合适的进程 和 完成进程的切换。

static void __sched notrace __schedule(unsigned int sched_mode)
{
	struct task_struct *prev, *next;
	unsigned long *switch_count;
	unsigned long prev_state;
	struct rq_flags rf;
	struct rq *rq;
	int cpu;

	cpu = smp_processor_id(); 								// 获取当前执行cpu_id
	rq = cpu_rq(cpu); 									// 获取当前cpu对应的就绪队列
	prev = rq->curr;									// 当前正在此CPU上运行的进程

	schedule_debug(prev, !!sched_mode);							// 各种schedule()时间调试检查和统计:

	if (sched_feat(HRTICK) || sched_feat(HRTICK_DL))					// 采用sched_feat作为内核调试控制开关
		hrtick_clear(rq);								// 清除高精度任务

	local_irq_disable();									// 屏蔽当前CPU上的所有中断
	rcu_note_context_switch(!!sched_mode);							// 把当前的CPU状态设置为通过状态

	/*
确保下面的signal_pending_state()->signal_pending()不能与调用者完成的__set_current_state(TASK_INTERRUPTIBLE)重新排序，以避免与signal_wake_up()竞争:
另外，membarrier系统调用从用户空间发出后，在存储到rq->curr之前，需要一个完整的内存屏障。
	 */
	rq_lock(rq, &rf);									// 给就绪队列上锁？
	smp_mb__after_spinlock();								// 早期锁获取和后期内存访问之间设置了一个完全的内存屏障

	/* Promote REQ to ACT */
	rq->clock_update_flags <<= 1;								// 
	update_rq_clock(rq);									// 就绪队列时钟的更新
	switch_count = &prev->nivcsw;								// 切换次数 = 被动切换次数
	/*
		我们必须加载prev->state一次(task_struct::state是不稳定的)，例如:
		-我们在下面与deactivate_task()形成一个控制依赖。
		- ptrace_{，un} freeze_tracing()可以改变我们下面->state
	 */
	prev_state = READ_ONCE(prev->__state);
	if (!(sched_mode & SM_MASK_PREEMPT) && prev_state) {
		if (signal_pending_state(prev_state, prev)) {					// 检测进程是否可以休眠
			WRITE_ONCE(prev->__state, TASK_RUNNING);					// 可以休眠则：把当前进程状态改为就绪态
		} else {
			prev->sched_contributes_to_load =						// 不可以则：计算调度对负载的影响
				(prev_state & TASK_UNINTERRUPTIBLE) &&					// 是深度睡眠、非noload、非冻结则有影响
				!(prev_state & TASK_NOLOAD) &&
				!(prev->flags & PF_FROZEN);
			if (prev->sched_contributes_to_load)
				rq->nr_uninterruptible++;						// 曾经处于队列但现在处于深度睡眠状态的进程数量
			/*
				其中__schedule()和ttwu()具有匹配的控制依赖项。
				在此之后，schedule()必须不再关心p->状态。
			 */
			deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);			// 从运行队列中删除prev进程
			if (prev->in_iowait) {								// 当前进程在等待io操作
				atomic_inc(&rq->nr_iowait);						// 增加运行队列中等待io操作进程的数量
				delayacct_blkio_start();					
// 在主调度函数__schedule()中，如果任务prev因为IO阻塞，即prev->in_iowait不为0而调度出去，这时候就会调用delayacct_blkio_start()将当前时间戳记录下来：
			}
		}
		switch_count = &prev->nvcsw;							// 切换次数 = 主动切换次数
	}

	next = pick_next_task(rq, prev, &rf);							// 挑选合适的next任务来运行
	clear_tsk_need_resched(prev);								// 清除当前进程prev的重新调度标志TIF_NEED_RESCHED
	clear_preempt_need_resched();								// 来设置preempt.need_resched为1, 来清除重新调度
#ifdef CONFIG_SCHED_DEBUG
	rq->last_seen_need_resched_ns = 0;
#endif

	if (likely(prev != next)) {								// 如果不是相同进程间的切换
		rq->nr_switches++;									// rq的切换数加1
		/*
		 * 使用rcu_dereference(rq->curr)的RCU用户可能不会看到pick_next_task()对task_struct的修改。
		 */
		RCU_INIT_POINTER(rq->curr, next);							// 将任务next更新到rq->curr指针
		/*
			membarrier系统调用要求每个体系结构在更新rq->curr之后，在返回用户空间之前，都有一个完整的内存屏障。
			以下是在各种体系结构上提供该屏障的方案。
			- mm? switch_mm(): mmdrop()适用于x86, s390, sparc, PowerPC。switch_mm()依赖PowerPC上的membarrier_arch_switch_mm()。
			- finish_lock_switch()用于弱顺序体系结构，其中spin_unlock是一个完全屏障，
			- switch_to()用于arm64(弱顺序，spin_unlock是一个释放屏障)，
		 */
		++*switch_count;									// 切换次数增加

		migrate_disable_switch(rq, prev);							// 禁止迁移到其他cpu上
		psi_sched_switch(prev, next, !task_on_rq_queued(prev));		

		trace_sched_switch(sched_mode & SM_MASK_PREEMPT, prev, next);				// 重要tracepoint：sched_switch

		/* Also unlocks the rq: */
		rq = context_switch(rq, prev, next, &rf);						// 从当前的任务prev上切换到目标任务next
	} else {										// 如果是相同进程间的切换
		rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);				// 收尾处理：包括释放锁和开中断
		rq_unpin_lock(rq, &rf);
		__balance_callbacks(rq);
		raw_spin_rq_unlock_irq(rq);
	}
}

1. next = pick_next_task⁵

2. rq = context_switch(rq, prev, next, &rf);

pick_next_task

由于不同的调度类会对应pick_next_task不同的实现，这里以fair调度类举例，对应的实现为pick_next_task_fair()，因为当前linux的fair调度类对应的调度策略是CFS，所以读者应当对CFS原理有一个基本的认识。这里罗列几个细小但关键的点：

1. 挑选进程的过程会根据各个调度类的优先级依次遍历，以找到合适的调度类中的合适的进程作为接下来运行的任务，这里假设rt调度类中的没有进程，然后找到了fair调度类。
2. 在fair调度类(CFS策略)上挑选进程的基本原则是：挑选cfs_rq上vruntime最小的任务作为下一个运行的进程。
3. 若最终没有选到进程，则会挑选idle调度类运行idle进程。