内核进程切换实现分析-白红宇

内核进程切换实现分析

阅读量：6253 次

发布时间：2019-06-22

本文共 16598 字，大约阅读时间需要 55 分钟。

当我们在linux编写用户态程序时并不需要考虑进程间是如何切换的, 即使当我们编写驱动程序时也只需调用一些阻塞接口来让渡cpu. 但是cpu究竟是如何切换进程的, 在进程切换过程中需要做什么, 今天我们通过分析内核schedule()的实现来看下内核是如何完成进程切换的.

先看下几个相关的数据结构:

1 struct thread_info {  2     unsigned long flags;  3     /**  4      * 抢占标记, 为0可抢占, 大于0不能抢占, 小于0出错  5      * preempt_disable()/preempt_enable()会修改该值  6      * 同时也是被抢占计数, preempt_count的结构可见include/linux/hardirq.h中描述  7      * 最低字节为抢占计数, 第二字节为软中断计数, 16-25位(10位)为硬中断计数  8      * 26位为不可屏蔽中断(NMI)标记, 27位为不可抢占标记  9      * 针对preempt_count的判断宏都在include/linux/hardirq.h中 10      * 11     **/ 12     int preempt_count; 13     //break地址限制 14     mm_segment_t addr_limit; 15     //task结构体 16     struct task_struct *task; 17     struct exec_domain *exec_domain; 18     //线程所在cpu号, 通过raw_smp_processor_id()获取 19     __u32 cpu; 20     //保存协处理器状态, __switch_to()中修改 21     __u32 cpu_domain; 22     //保存寄存器状态, __switch_to()假定cpu_context紧跟在cpu_domain之后 23     struct cpu_context_save cpu_context; 24     __u32 syscall; 25     __u8 used_cp[16]; 26     unsigned long tp_value; 27 #ifdef CONFIG_CRUNCH 28     struct crunch_state crunchstate; 29 #endif 30     union fp_state fpstate __attribute__((aligned(8))); 31     union vfp_state vfpstate; 32 #ifdef CONFIG_ARM_THUMBEE 33     unsigned long thumbee_state; 34 #endif 35     struct restart_block restart_block; 36 }; 37 struct task_struct { 38     //任务状态, 0为可运行, -1为不可运行, 大于0为停止 39     volatile long state; 40     void *stack; 41     //引用计数 42     atomic_t usage; 43     //进程标记状态位, 本文用到的是TIF_NEED_RESCHED 44     unsigned int flags; 45     unsigned int ptrace; 46 #ifdef CONFIG_SMP 47     struct llist_node wake_entry; 48     //该进程在被调度到时是否在另一cpu上运行, 仅SMP芯片判断 49     //prepare_lock_switch中置位, finish_lock_switch中清零 50     int on_cpu; 51 #endif 52     //是否在运行队列(runqueue)中 53     int on_rq; 54     int prio, static_prio, normal_prio; 55     unsigned int rt_priority; 56     const struct sched_class *sched_class; 57     struct sched_entity se; 58     struct sched_rt_entity rt; 59 #ifdef CONFIG_CGROUP_SCHED 60     struct task_group *sched_task_group; 61 #endif 62 #ifdef CONFIG_PREEMPT_NOTIFIERS 63     struct hlist_head preempt_notifiers; 64 #endif 65     unsigned int policy; 66     int nr_cpus_allowed; 67     //cpu位图, 表明task能在哪些cpu上运行, 系统调用sched_setaffinity会修改该值 68     cpumask_t cpus_allowed; 69 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT) 70     //该进程调度状态, 记录进程被调度到的时间信息, 在sched_info_arrive中修改 71     struct sched_info sched_info; 72 #endif 73     /** 74      * mm为进程内存管理结构体, active_mm为当前使用的内存管理结构体 75      * 内核线程没有自己的内存空间(内核空间共有), 所以它的mm为空 76      * 但内核线程仍需要一个内存管理结构体来管理内存(即active_mm的作用) 77      * 进程则同时存在mm与active_mm, 且两者相等(否则访问用户空间会出错) 78      * 79     **/ 80     struct mm_struct *mm, *active_mm; 81     //进程上下文切换次数 82     unsigned long nvcsw, nivcsw; 83     ...... 84 };

首先来分析调度管理的入口, 内核调度的通用接口是schedule()(defined in kernel/sched/core.c).

1 asmlinkage void __sched schedule(void) 2 { 3     struct task_struct *tsk = current; 4     sched_submit_work(tsk); 5     __schedule(); 6 }

current即get_current()(defined in include/asm-generic/current.h), 后者为current_thread_info()->task. current_thread_info()是内联函数(defined in arch/arm/include/asm/thread_info.h): THREAD_SIZE大小为8K, 即内核假定线程栈向下8K对齐处为thread_info, 通过它索引task_struct.

1 static inline struct thread_info *current_thread_info(void) 2 { 3     register unsigned long sp asm ("sp"); 4     return (struct thread_info *)(sp & ~(THREAD_SIZE - 1)); 5 }

获取task后判断当前task是否需要刷新IO队列, 然后执行实际的调度函数__schedule().

__schedule()的注释详细指出了调度发生的时机:

1. 发生阻塞时, 比如互斥锁, 信号量, 等待队列等.

2. 当中断或用户态返回时检查到TIF_NEED_RESCHED标记位. 为切换不同task, 调度器会在时间中断scheduler_tick()中设置标记位.

3. 唤醒不会真正进入schedule(), 它们仅仅在运行队列中增加一个task. 如果新增的task优先于当前的task那么唤醒函数将置位TIF_NEED_RESCHED, schedule()将最可能在以下情况执行:

如果内核是开启抢占的(CONFIG_PREEMPT), 在系统调用或异常上下文执行preempt_enable()之后(最快可能在wake_up()中spin_unlock()之后); 在中断上下文, 从中断处理程序返回开启抢占后.

如果内核未开启抢占, 那么在cond_resched()调用, 直接调用schedule(), 从系统调用或异常返回到用户空间时, 从异常处理程序返回到用户空间时.

1 static void __sched __schedule(void)  2 {  3     struct task_struct *prev, *next;  4     unsigned long *switch_count;  5     struct rq *rq;  6     int cpu;  7 need_resched:  8     //关闭抢占, current_thread_info->preempt_count--  9     preempt_disable(); 10     //获取线程所在cpu 11     cpu = smp_processor_id(); 12     rq = cpu_rq(cpu); 13     rcu_note_context_switch(cpu); 14     prev = rq->curr; 15     schedule_debug(prev); 16     if (sched_feat(HRTICK)) 17         hrtick_clear(rq); 18     raw_spin_lock_irq(&rq->lock); 19     switch_count = &prev->nivcsw; 20     //如果进程停止且支持抢占 21     if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { 22         //判断是否有信号挂起 23         if (unlikely(signal_pending_state(prev->state, prev))) { 24             prev->state = TASK_RUNNING; 25         } else { 26             //没有信号挂起则将当前进程踢出运行队列 27             deactivate_task(rq, prev, DEQUEUE_SLEEP); 28             prev->on_rq = 0; 29             //如果该进程属于一个工作队列, 判断是否需要唤醒另一个进程 30             if (prev->flags & PF_WQ_WORKER) { 31                 struct task_struct *to_wakeup; 32                 to_wakeup = wq_worker_sleeping(prev, cpu); 33                 if (to_wakeup) 34                     try_to_wake_up_local(to_wakeup); 35             } 36         } 37         switch_count = &prev->nvcsw; 38     } 39     //sched_class.pre_schedule 40     pre_schedule(rq, prev); 41     if (unlikely(!rq->nr_running)) 42         idle_balance(cpu, rq); 43     //sched_class.put_prev_task 44     put_prev_task(rq, prev); 45     //sched_class.pick_next_task 46     next = pick_next_task(rq); 47     //清除需要调度标记 48     clear_tsk_need_resched(prev); 49     rq->skip_clock_update = 0; 50     //如果next不等于prev即调度到其它进程 51     if (likely(prev != next)) { 52         rq->nr_switches++; 53         rq->curr = next; 54         ++*switch_count; 55         //进程上下文切换, 过程中会解锁rq->lock 56         context_switch(rq, prev, next); 57         /* 58          * The context switch have flipped the stack from under us 59          * and restored the local variables which were saved when 60          * this task called schedule() in the past. prev == current 61          * is still correct, but it can be moved to another cpu/rq. 62          */ 63         cpu = smp_processor_id(); 64         rq = cpu_rq(cpu); 65     } else 66         raw_spin_unlock_irq(&rq->lock); 67     post_schedule(rq); 68     //恢复抢占, current_thread_info->preempt_count++ 69     sched_preempt_enable_no_resched(); 70     //如线程标记位TIF_NEED_RESCHED仍存在继续调度 71     if (need_resched()) 72         goto need_resched; 73 }

__schedule()中首先关闭该线程的抢占(current_thread_info->preempt_count自减), 获取线程所在cpu(current_thread_info->cpu), 再获取对应cpu的rq. 此处先看下rq的结构(defined in kernel/sched/sched.h). cpu_rq()(defined in kernel/sched/sched.h)是一个复杂的宏, 用于获取对应cpu的rq结构. 来看下它的定义(以SMP芯片为例):

1 #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu))) 2 #define per_cpu(var, cpu) (*SHIFT_PERCPU_PTR(&(var), per_cpu_offset(cpu)))

SHIFT_PERCPU_PTR()是对特定平台的宏, 一般平台上即直接取地址加偏移. 偏移不一定是线性的, 所以用per_cpu_offset()宏获取(其实质是个数组, 在setup_per_cpu_areas()中初始化). 再看下runqueues(defined in kernel/sched/core.c)又是如何定义的.

1 DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues); 2 #define DEFINE_PER_CPU_SHARED_ALIGNED(type, name) \ 3     DEFINE_PER_CPU_SECTION(type, name, PER_CPU_SHARED_ALIGNED_SECTION) \ 4     ____cacheline_aligned_in_smp 5 #define DEFINE_PER_CPU_SECTION(type, name, sec) \ 6     __PCPU_ATTRS(sec) PER_CPU_DEF_ATTRIBUTES \ 7     __typeof__(type) name

这样就都串起来了, runqueues是struct rq的数组, 各个cpu通过偏移获取对应结构体地址.

开始调度前首先要获取运行队列rq的自旋锁. 调度器算法是由pre_schedule(), put_prev_task(), pick_next_task()与post_schedule()实现的. 这几个接口都是当前进程调度器类型结构体(sched_class)的回调. 关于调度器模型的分析以后有空分析, 此处先略过.

回到__schedule(), 再得到调度后的进程后先清除调度前的进程的调度标记, 判断调度前后进程是否不同, 不同则执行上下文切换的工作, context_switch()(defined in kernel/sched/core.c)是为了恢复到调度后进程的环境, 包括TLB(内核线程仅访问内核空间无需切换, 用户进程需切换), 恢复寄存器与堆栈等.

1 static inline void context_switch(struct rq *rq, \  2     struct task_struct *prev, struct task_struct *next)  3 {  4     struct mm_struct *mm, *oldmm;  5     //准备进程切换  6     //sched_info_switch记录调度前后两个进程在调度时刻的时间信息  7     //prepare_lock_switch将调度后进程next->on_cpu置位(对于SMP芯片)  8     prepare_task_switch(rq, prev, next);  9     mm = next->mm; 10     oldmm = prev->active_mm; 11     arch_start_context_switch(prev); 12     /** 13      * 切换内存空间, mm为调度后进程的内存空间, oldmm为调度前进程正在使用的内存空间 14      * 对于内核线程没有私有内存空间, mm为空, 此时无需切换内存空间 15      * 所以复用之前的mm, 同时tlb进入lazy mode, 如果为用户进程(mm非空)则需刷新mm 16      * 17     **/ 18     if (!mm) { 19         next->active_mm = oldmm; 20         atomic_inc(&oldmm->mm_count); 21         enter_lazy_tlb(oldmm, next); 22     } else 23         switch_mm(oldmm, mm, next); 24     /** 25      * 内核线程没有自己的内存空间, 需要引用其它进程的内存空间 26      * 但当该线程还在运行时不可能自己减少对该mm的引用 27      * 因此需要缓存该mm, 在调度到新进程后再减少引用 28      * 这就是rq->prev_mm作用, 其减少见finish_task_switch() 29      * 30     **/ 31     if (!prev->mm) { 32         prev->active_mm = NULL; 33         rq->prev_mm = oldmm; 34     } 35     /** 36      * 释放运行队列锁 37      * 通常释放锁操作在switch_to()之后, 但在部分平台上需要解锁执行上下文切换 38      * 此时就需要定义__ARCH_WANT_UNLOCKED_CTXSW, 具体参见scheduler/sched-arch.txt 39      * 40     **/ 41 #ifndef __ARCH_WANT_UNLOCKED_CTXSW 42     spin_release(&rq->lock.dep_map, 1, _THIS_IP_); 43 #endif 44     context_tracking_task_switch(prev, next); 45     //切换寄存器状态与栈, 实际调用__switch_to(defined in arch/arm/kernel/entry-armv.S) 46     switch_to(prev, next, prev); 47     barrier(); 48     //当前运行的cpu可能不是之前的cpu, 所以需要重新获取当前的runqueue 49     finish_task_switch(this_rq(), prev); 50 }

context_switch()中最主要的两个函数是switch_mm()与switch_to(), 前者切换mm与TLB后者切换寄存器与栈. switch_mm()以后有空详述, 先看下switch_to(), 其调用的__switch_to()(defined in arch/arm/kernel/entry-armv.S)是汇编函数:

1 #define switch_to(prev,next,last) \  2 do { \  3     last = __switch_to(prev,task_thread_info(prev), task_thread_info(next)); \  4 } while (0)  5 ENTRY(__switch_to)  6 UNWIND(.fnstart)  7 UNWIND(.cantunwind)  8     add ip, r1, #TI_CPU_SAVE  9     ldr r3, [r2, #TI_TP_VALUE] 10     ARM( stmia ip!, {r4 - sl, fp, sp, lr} ) 11     THUMB( stmia ip!, {r4 - sl, fp} ) 12     THUMB( str sp, [ip], #4 ) 13     THUMB( str lr, [ip], #4 ) 14 #ifdef CONFIG_CPU_USE_DOMAINS 15     ldr r6, [r2, #TI_CPU_DOMAIN] 16 #endif 17     set_tls r3, r4, r5 18 #if defined(CONFIG_CC_STACKPROTECTOR) && !defined(CONFIG_SMP) 19     ldr r7, [r2, #TI_TASK] 20     ldr r8, =__stack_chk_guard 21     ldr r7, [r7, #TSK_STACK_CANARY] 22 #endif 23 #ifdef CONFIG_CPU_USE_DOMAINS 24     mcr p15, 0, r6, c3, c0, 0 25 #endif 26     mov r5, r0 27     add r4, r2, #TI_CPU_SAVE 28     ldr r0, =thread_notify_head 29     mov r1, #THREAD_NOTIFY_SWITCH 30     bl atomic_notifier_call_chain 31 #if defined(CONFIG_CC_STACKPROTECTOR) && !defined(CONFIG_SMP) 32     str r7, [r8] 33 #endif 34     THUMB( mov ip, r4 ) 35     mov r0, r5 36     ARM( ldmia r4, {r4 - sl, fp, sp, pc} ) 37     THUMB( ldmia ip!, {r4 - sl, fp} ) 38     THUMB( ldr sp, [ip], #4 ) 39     THUMB( ldr pc, [ip] ) 40 UNWIND(.fnend) 41 ENDPROC(__switch_to)

进入函数调用时R0与R1分别为调度前进程的task_struct与thread_info, R2为调度后进程的thread_info. 函数首先将当前寄存器中R4-R15(除IP与LR外)全部保存到调度前进程的thread_info.cpu_context(IP指向的地址)中, 然后恢复TLS(thread local store). set_tls(defined in rch/arm/include/asm/tls.h)用于内核向glibc传递TLS地址.

1 .macro set_tls_software, tp, tmp1, tmp2 2     mov \tmp1, #0xffff0fff 3     str \tp, [\tmp1, #-15] @ set TLS value at 0xffff0ff0 4 .endm

在ARM_V7平台上使用set_tls_software宏, 即将调度后进程的thread_info.tp_value(R3的值)保存在0xFFFF0FF0, 这是内核为glibc获取TLS专门预留的地址.

恢复TLS后还需恢复协处理器, 同样是从thread_info.cpu_domain(R6的值)中获取. 然后调用回调通知链, 入参分别是thread_notify_head, THREAD_NOTIFY_SWITCH, 调度后进程的thread_info. 看了下这里注册回调的都是与架构强相关的代码: mm, fp, vfp和cp这几类寄存器的修改. 因为与架构强相关, 先不分析了, 以后有空再看.

最后从调度后进程的thread_info.cpu_context(R4指向的地址)恢复寄存器. 想想为什么不一起保存/恢复R0-R3, IP和LR?

注意此处! 当PC被出栈后, 就切换到调度后进程代码执行了, 即switch_to()是不返回的函数. 既然是不返回的函数, 后面的代码是干什么的呢? 自然是线程恢复运行时的恢复代码了. 当调度前的进程恢复(即通过__switch_to出栈PC恢复之前执行代码地址)后继续执行context_switch(). 此时进程身份已经互换了, 之前调度出去的进程作为被调度到的进程(但是代码中的prev与next还是没有改变, 因为寄存器与栈仍为之前的状态), 而当前被调度出去的进程可能是之前调度到的进程, 也可能是第三个进程. 且此时程序运行在哪个CPU上也是不确定的. 所以先做内存屏障, 然后调用finish_task_switch()完成上下文切换.

1 static void finish_task_switch(struct rq *rq, \  2     struct task_struct *prev) __releases(rq->lock)  3 {  4     struct mm_struct *mm = rq->prev_mm;  5     long prev_state;  6     //清空prev_mm  7     rq->prev_mm = NULL;  8     /**  9      * 源码注释已经指出进程在退出时会最后一次调度schedule(), 调度不会返回 10      * 测试进程状态是否为TASK_DEAD必须在获取运行队列锁时 11      * 否则退出的进程可能被调度到另一CPU上, 在那个CPU上退出导致两次减少引用计数 12      * 13     **/ 14     prev_state = prev->state; 15     vtime_task_switch(prev); 16     finish_arch_switch(prev); 17     perf_event_task_sched_in(prev, current); 18     //finish_lock_switch()中执行解锁 19     //注意此处解锁不一定与__schedule()中为同一把锁, 因为此时可能切换了CPU 20     finish_lock_switch(rq, prev); 21     //如果之前切换内存空间时处于禁止中断状态则推迟到此处切换内存空间 22     finish_arch_post_lock_switch(); 23     fire_sched_in_preempt_notifiers(current); 24     //注意此处drop的是rq->prev_mm, rq->prev_mm是在__schedule()中被赋值为prev->active_mm 25     //如此保证了尽管内核线程没有内存空间, 但仍能正常使用mm 26     if (mm) 27         mmdrop(mm); 28     //释放task_struct 29     if (unlikely(prev_state == TASK_DEAD)) { 30         kprobe_flush_task(prev); 31         put_task_struct(prev); 32     } 33     tick_nohz_task_switch(current); 34 }

至此完成进程上下文切换, 重新回到__schedule(), 执行post_schedule()完成清理工作, 恢复该进程可抢占状态, 判断当前线程是否需要调度, 如果需要再走一遍流程.

关于调度器的代码我们将在以后具体分析, 如果感兴趣也可以看下内核文档中对调度器的说明(在Documentation/scheduler目录下), 这里稍稍翻译下(主要是针对cgroup使用的补充比较有价值).

1. sched-arch.txt

讨论与架构相关的调度策略. 进程上下文切换中运行队列的自旋锁处理: 一般要求在握有rq->lock情况下调用switch_to. 在有些情况下(比如在进程上下文切换时有唤醒操作, 见arch/ia64/include/asm/system.h为例)switch_to需要获取锁, 此时调度器需要保证无锁时调用switch_to. 在这种情况下需要定义__ARCH_WANT_UNLOCKED_CTXSW(一般与switch_to定义在一起).

2. sched-bwc.txt

讨论SCHED_NORMAL策略的进程的带宽控制. CFS带宽控制需要配置CONFIG_FAIR_GROUP_SCHED. 带宽控制允许进程组指定使用一个周期与占比, 对于给定的周期(以毫秒计算), 进程组最多允许使用占比长度的CPU时间, 当进程组执行超过其限制的时间进程将不得再执行直到下一个周期到来.

周期与占比通过CPU子系统cgroupfs管理. cpu.cfs_quota_us为一个周期内总的可运行时间(以毫秒计算), cpu.cfs_period_us为一个周期的长度(以毫秒计算), cpu.stat为调节策略. 默认值cpu.cfs_period_us=1000ms, cpu.cfs_period_us=-1. -1表明进程组没有带宽限制, 向其写任何合法值将开启带宽限制, 最小的限制为1ms, 最大的限制为1s, 向其写任何负数将取消带宽限制并将进程组恢复到无约束状态.

可以通过/proc/sys/kernel/sched_cfs_bandwidth_slice_us(默认5ms)获取调度时间片长度.

进程组的带宽策略可通过cpu.stat的3个成员获取: nr_periods nr_throttled throttled_time.

存在两种情况导致进程被节制获取CPU: a. 它完全耗尽一个周期中的占比 b. 它的父进程完全耗尽一个周期中的占比. 出现情况b时, 尽管子进程存在运行时间但它仍不能获取CPU直到它的父亲的运行时间刷新.

3. sched-design-CFS.txt

CFS即completely fair scheduler, 自2.6.23后引入, 用于替换之前的SCHED_OTHER代码. CFS设计目的是基于真实的硬件建立理想的, 精确的多任务CPU模型. 理想的多任务CPU即可以精确的按相同速度执行每一个任务, 比如在两个任务的CPU上每个任务可以获取一半性能. 真实的硬件中我们同时仅能运行一个任务, 所以我们引入虚拟运行时间的概念. 任务的虚拟运行时间表明在理想的多任务CPU上任务下一次执行时间, 实际应用中任务的虚拟运行时间即其真实的运行时间.

CFS中的虚拟运行时间通过跟踪每个task的p->se.vruntime值, 借此它可以精确衡量每个task的期望CPU时间. CFS选择task的逻辑是基于p->se.vruntime值: 它总是尝试运行拥有最小值的task.

CFS设计上不使用传统的runqueue, 而是使用基于时间的红黑树建立一个未来任务执行的时间线. 同时它也维护rq->cfs.min_vruntime值, 该值是单调增长的值, 用来跟踪runqueue中最小的vruntime. runqueue中所有运行进程的总数通过rq->cgs.load值统计, 它是该runqueue上所有排队的task的权重的综合. CFS维护这一个时间排序的红黑树, 树上所有可运行进程都以p->se.vruntime为键值排序, CFS选择最左的task执行. 随着系统持续运行, 执行过的task被放到树的右侧, 这给所有task一个机会成为最左的task并获取CPU时间. 总结CFS工作流程: 当一个运行的进程执行调度或因时间片到达而被调度, 该任务的CPU使用值(p->se.vruntime)将加上它刚刚在CPU上消耗的时间. 当p->se.vruntime足够高到另一个任务成为最左子树的任务时(再加上一小段缓冲以保证不会发生频繁的来回调度), 那么新的最左子树的任务被选中.

CFS使用ns来计算, 它不依赖jiffies或HZ. 因此CFS没有其它调度中有的时间片的概念. CFS只有一个可调整参数: /proc/sys/kernel/sched_min_granularity_ns用于调整工作负载(从桌面模式到服务器模式).

调度策略:

1. SCHED_NORMAL(传统叫法SCHED_OTHER)用于普通task.

2. SCHED_BATCH不像通常task一样经常发生抢占, 因此允许task运行更久, 更好利用cache.

3. SCHED_IDLE比nice值19更弱, 但它不是一个真正的idle时间调度器, 可以避免优先级反转的问题.

SCHED_FIFO/SCHED_RR在sched/rt.c中实现并遵循POSIX规范.

调度器类型的实现通过sched_class结构, 它包含以下回调:

enqueue_task(): 当task进入可运行状态时调用, 将task放入红黑树中并增加nr_running值.

dequeue_task(): 当task不再可运行时调用, 将task从红黑树中移除并减少nr_running值.

yield_task(): 将task移除后再加入红黑树.

check_preempt_curr(): 检测进入可运行状态的task是否可抢占当前运行的task.

pick_next_task(): 选择最合适的task运行.