|
unsigned long nr_uninterruptible; 下面几个指针分别指向当前运行的进程、空闲进程、被停止运行的进程 struct task_struct *curr, *idle, *stop; unsigned long next_balance; struct mm_struct *prev_mm;进程切换时存放被替换进程内存描述符 字段clock用于实现就绪队列自身的时钟，每次调用周期性调度器时，都会更新clock的值。内核还提供了函数update_rq_clock，可在操作就绪队列的调度中多次调用。 u64 clock; ...... }; 调度类结构体在文件include/linux/sched.h中定义，如下： struct sched_class { next字段将各个调度类按重要性链接起来，最重要的是实时进程，其次是完全公平进程，再次是空闲进程 const struct sched_class *next; 向就绪队列添加一个新进程，在进程从睡眠状态变为可运行状态调用该操作 void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags); 将一个进程从就绪队列中去除。 void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags); 当进程志愿放弃对处理器的控制权时，可使用系统调用sched_yield，这将导致内核调用 函数yield_task void (*yield_task) (struct rq *rq); 进程放弃CPU控制权并将控制权交给p进程 bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt); 用一个新唤醒的进程来抢占当前进程， void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags); 选择下一个需要运行的进程 struct task_struct * (*pick_next_task) (struct rq *rq); 通知调度器类当前运行的进程将要被另一个进程代替。 void (*put_prev_task) (struct rq *rq, struct task_struct *p); ...... 用于设置调度队列的当前进程，例如cfs_rq->curr void (*set_curr_task) (struct rq *rq); 由周期性调度器调用，更新一些时间统计量 void (*task_tick) (struct rq *rq, struct task_struct *p, int queued); 当新进程创建时调用初始化一些特定调度器类的东西，并设置重调度标志TIF_NEED_RESCHED void (*task_fork) (struct task_struct *p); ...... }; 调度器操作比进程更一般的实体，每个进程描述结构中都嵌有一个调度实体结构，但并不是一个调度实体就等于一个进程，有时候将一组进程集合起来表示一个调度实体。调度实体结构在文件include/linux/sched.h中定义，如下： struct sched_entity { load记录一个调度实体负荷权重 struct load_weight load; /* for load-balancing */ 红黑树节点，使得实体可以在红黑树上排序 struct rb_node run_node; 用于链接到就绪队列的cfs_tasks字段上 struct list_head group_node; 表示实体是否在就绪队列上 unsigned int on_rq; 当新进程被加入就绪队列或者在周期性调度器中，会计算当前值和exec_start之间的差值，将差值加到sum_exec_runtime中，exec_start则更新为当前时间 u64 exec_start; 记录消耗的CPU时间 u64 sum_exec_runtime; 保存进程的虚拟时间，关于虚拟时间后面讲详细讲解 u64 vruntime; 当进程失去CPU控制权时将sum_exec_runtime保存到prev_sum_exec_runtime中 u64 prev_sum_exec_runtime; ...... 下面是跟组调度相关的字段 #ifdef CONFIG_FAIR_GROUP_SCHED struct sched_entity *parent; 建立组调度中调度实体的层次关系 struct cfs_rq *cfs_rq; 组所属的调度队列 /* rq "owned" by this entity/group: */ struct cfs_rq *my_q;组内部的调度队列 #endif }; 2 优先级与负荷权重2.1优先级的计算前面讲过优先级有3个，static_prio、normal_prio和prio。Static_prio在进程启动时静态设置可用nice系统调用修改；normal_prio与静态优先级和调度策略有关，调度策略可能被修改；prio是调度算法中用到的优先级，他可能被内核临时改变，比如一个高优先级的进程在使用的互斥量，被一个低优先级进程占据了，这是就要临时提高低优先级的优先级，这个优先级就保存在prio中。 在用户空间中，用nice系统调用设置进程的静态优先级，该nice值的范围是-20到19之间，值越低优先级越高。内核内部表示优先级的的范围是0到139，同样也是值越低优先级越高。从0到99专事实进程使用。Nice值-20到19映射的范围是100到139. 优先级prio的获取是通过函数effective_prio来实现的，如下： 程序首先计算进程的普通优先级然后判断进程的优先级是否小于MAX_RT_PRIO，这里并不考虑调度策略。如果进程优先级在实时进程优先级范围内就直接返回其优先级（prio）否则返回其普通优先级。 static int effective_prio(struct task_struct *p) { p->normal_prio = normal_prio(p); if (!rt_prio(p->prio)) return p->normal_prio; return p->prio; } 【effective_prio--->normal_prio】 由于实时进程中，进程描述符p->rt_priority字段表示的优先级是其数值越大优先级越高，与内核内部表示优先级的方法刚好相反，所以在内核内部优先级的计算方法是 MAX_RT_PRIO-1 - p->rt_priority;。函数__normal_prio仅仅是返回进程的静态优先级 return p->static_prio;。 static inline int normal_prio(struct task_struct *p) { int prio; if (task_has_rt_policy(p)) prio = MAX_RT_PRIO-1 - p->rt_priority; else prio = __normal_prio(p); return prio; } 2.2 负荷权重的计算进程每降低一个nice值，多获得10%的CPU时间，每升高一个nice值，则放弃10%的CPU时间。为执行该策略，内核将优先级转换为权重。优先级--权重转换表： kernel/sched/sched.h static const int prio_to_weight[40] = { /* -20 */ 88761, 71755, 56483, 46273, 36291, /* -15 */ 29154, 23254, 18705, 14949, 11916, /* -10 */ 9548, 7620, 6100, 4904, 3906, /* -5 */ 3121, 2501, 1991, 1586, 1277, /* 0 */ 1024, 820, 655, 526, 423, /* 5 */ 335, 272, 215, 172, 137, /* 10 */ 110, 87, 70, 56, 45, /* 15 */ 36, 29, 23, 18, 15, }; 计算权重的函数是set_load_weight，空闲进程的权重最小。负荷权重包含在数据结构load_weight中如下： struct load_weight { unsigned long weight, inv_weight; }; Weight表示优先级在表prio_to_weight中映射的权重，inv_weight表示被负荷权重除的结果，这些值也存在表prio_to_wmult中，这个表与表prio_to_weight中的值一一对应。这些值的计算方法是(2^32/x)，x表示在表prio_to_weight中对应位置中的值。 static void set_load_weight(struct task_struct *p) { int prio = p->static_prio - MAX_RT_PRIO; struct load_weight *load = &p->se.load; if (p->policy == SCHED_IDLE) { load->weight = scale_load(WEIGHT_IDLEPRIO); load->inv_weight = WMULT_IDLEPRIO; return; }
load->weight = scale_load(prio_to_weight[prio]); load->inv_weight = prio_to_wmult[prio]; } 3核心调度器调度器的实现基于两个函数：周期性调度器函数和主调度器函数。 周期性调度器函数scheduler_tick：在内核频率HZ中断处理函数中调用该函数。周期性调度函数的主要工作是更新各种时间统计量，在必要的时候进行进程 调度。在多CPU系统中它还进行负载均衡处理。 主调度器函数schedule：如果进程主动放弃执行而选择另一个活动进程运行就调用该函数。 周期性调度器函数和主调度器函数都不直接操作进程，而是调用进程所属的操作类来操作进程。每个进程都属于某个调度类（完全公平调度类、实时调度类）。 3.1 周期性调度器kernel/sched/core.c void scheduler_tick(void) { int cpu = smp_processor_id(); 获取当前CPU的cpu id struct rq *rq = cpu_rq(cpu);获取当前CPU对应的就绪队列结构 struct task_struct *curr = rq->curr;获取当前进程的进程描述符 在函数update_rq_clock中，更新就绪队列的两个成员rq->clock_task，rq->clock。 update_rq_clock(rq); 函数update_cpu_load_active负责更新就绪队列的cpu_load[]数组。将数组中先前存储的负荷值向后移动一个位置，将当前就绪队列的负荷计入数组的第一个位置。 update_cpu_load_active(rq); 调用当前进程所属的调度类的task_tick函数，在该函数中更新一些时间计数，必要时调度其他活动进程来执行。 curr->sched_class->task_tick(rq, curr, 0); ...... #ifdef CONFIG_SMP rq->idle_balance = idle_cpu(cpu); 在多处理器系统中进行负载均衡，保证不同CPU的运行队列包含数量基本相同的可运行进程 trigger_load_balance(rq, cpu); #endif } 3.2 主调度器kernel/sched/core.c asmlinkage void __sched schedule(void) { struct task_struct *tsk = current； 提交一些阻塞的IO请求避免死锁。 sched_submit_work(tsk); 主调度器的组要工作都在函数__schedule中实现。 __schedule(); } 【schedule--->__schedule】 static void __sched __schedule(void) { struct task_struct *prev, *next; unsigned long *switch_count; struct rq *rq; int cpu; need_resched: preempt_disable(); 禁止抢占 cpu = smp_processor_id(); 获取当前进程CPU id rq = cpu_rq(cpu);获取当前cpu对应的就绪队列结构 因为要切换到其他活动进程，所以当前进程就变成了“以前的”进程了。 prev = rq->curr; ...... 保存进程切换计数 switch_count = &prev->nivcsw; 标志 PREEMPT_ACTIVE可以保证进程被抢占但是不被移除就绪队列 if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { 如果进程有非阻塞挂起信号，而且状态为TASK_INTERRUPTIBLE，就不将进程移除就绪队列，并将其状态设为TASK_RUNNING。 if (unlikely(signal_pending_state(prev->state, prev))) { prev->state = TASK_RUNNING; } else { 调用函数 p->sched_class->dequeue_task将进程移除队列。 deactivate_task(rq, prev, DEQUEUE_SLEEP); prev->on_rq = 0; if (prev->flags & PF_WQ_WORKER) { struct task_struct *to_wakeup; 每一个工作队列都有一个工作者线程，如果当前进程是一个工作者线程，就查看是否有其他处于等待中的工作者线程，如果有在本地CPU上唤醒。 to_wakeup = wq_worker_sleeping(prev, cpu); if (to_wakeup) try_to_wake_up_local(to_wakeup); } } switch_count = &prev->nvcsw; } 如果CPU将变为空闲状态，即就绪队列上没有可运行的进程，就试图从其他CPU上可运行的进程移动到本地CPU的就绪队列上。 if (unlikely(!rq->nr_running)) idle_balance(cpu, rq); 通知调度器类当前运行的进程将要被另一个进程代替。 put_prev_task(rq, prev); 选择下一个应该执行的进程 next = pick_next_task(rq); 清除重调度标志TIF_NEED_RESCHED，重调度标志是由进程调度类设置的，表示调度请求，内核会在适当的时机完成该标志。 clear_tsk_need_resched(prev); rq->skip_clock_update = 0; if (likely(prev != next)) { rq->nr_switches++; rq->curr = next; ++*switch_count; 递增进程切换计数 完成进程上下文切换，下面详细分析。 context_switch(rq, prev, next); /* unlocks the rq */ 进程已经切换到其他进程去运行了，在后来的某个时候当前进程再次被调度时进程从这里开始运行，但是它在这中间可能已经被移动到其他CPU上了，所以此时栈上的cpu和rq变量的只可能就不一样了。 cpu = smp_processor_id(); rq = cpu_rq(cpu); } else raw_spin_unlock_irq(&rq->lock); post_schedule(rq); sched_preempt_enable_no_resched(); if (need_resched()) goto need_resched; } 【schedule--->__schedule--->context_switch】 static inline void context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next) { struct mm_struct *mm, *oldmm; mm = next->mm; oldmm = prev->active_mm; 如果将要运行的进程是一个内核线程，则它是没有进程虚拟地址空间的，就将上一个进程的虚拟地址空间报保存到 next->active_mm 中， if (!mm) { next->active_mm = oldmm; atomic_inc(&oldmm->mm_count); enter_lazy_tlb(oldmm, next); } else switch_mm(oldmm, mm, next); 更换虚拟内存上下文 如果前一个进程是内核线程就将前一个进程的prev->active_mm重置为NULL，rq->prev_mm指向上一个进程的虚拟地址空间 if (!prev->mm) { prev->active_mm = NULL; rq->prev_mm = oldmm; } ...... 进程寄存器和栈的切换，有特定体系架构的汇编实现。switch_to之后进程已经运行在了新进程之上，当前进程再次被调度运行时这中间可能已经经历过很多次切换了，但是要保证prev指向上一个进程。这上一个进程可能并不是当前进程，所以要传递三个参数，下面代码等效于prev=switch_to(next, prev); switch_to(prev, next, prev); barrier();
finish_task_switch(this_rq(), prev); |
|
|
