|
(转载)linux内核进程调度以及定时器实现机制
一、2.6版以前内核进程调度机制简介 Linux的进程管理由进程控制块、进程调度、中断处理、任务队列、定时器、bottom half队列、系统调用、进程通信等等部分组成。 进程调用分为实时进程调度和非实时进程调度两种。前者调度时，可以采用基于动态优先级的轮转法（RR），也可以采用先进现出算法（FIFO）。后者 调度时，一律采用基于动态优先级的轮转法。某个进程采用何种调度算法由改进程的进程控制块中的某些属性决定，没有专门的系统用来处理关于进程调度的相关事 宜。Linux的进程调度由schedule（）函数负责，任何进程，当它从系统调用返回时，都会转入schedule（），而中断处理函数完成它们的响 应任务以后，也会进入schedule（）。
1. 进程控制块数据结构 Linux系统的进程控制块用数据结构task_struct表示，这个数据结构占用1680个字节，具体的内容不在这里介绍，详细内容见《Linux内核2.4版源代码分析大全》第二页。 进程的状态主要包括如下几个： TASK_RUNNING 正在运行或在就绪队列run-queue中准备运行的进程，实际参与进程调度。 TASK_INTERRUPTIBLE 处于等待队列中的进程，待资源有效时唤醒，也可由其它进程通过信号或定时中断唤醒后进入就绪队列run-queue。 TASK_UNINTERRUPTIBLE 处于等待队列的进程，待资源有效时唤醒，不也可由其它进程通过信号或者定时中断唤醒。 TASK_ZOMBIE 表示进程结束但尚未消亡的一种状态（僵死），此时，进程已经结束运行并且已经释放了大部分资源，但是尚未释放进程控制块。 TASK_STOPPED 进程暂停，通过其它进程的信号才能唤醒。
所有进程（以PCB形式）组成一个双向列表。next_task和prev_task就是链表的前后向指针。链表的头尾都是init_task（init进程）。不过进程还要根据其进程ID号插入到一个hash表当中，目的是加快进程搜索速度。
2. 进程调度 Linux进程调度由schedule（）执行，其任务是在run-queue队列中选出一个就绪进程。 每个进程都有一个调度策略，在它的task_struct中规定（policy属性），或为SCHED_RR,SCHED_FIFO，或为SCHED_OTHER。前两种为实时进程调度策略，后一种为普通进程调度策略。 用户进程由do_fork（）函数创建，它也是fork系统调用的执行者。do_fork（）创建一个新的进程，继承父进程的现有资源，初始化进程时钟、信号、时间等数据。完成子进程的初始化后，父进程将它挂到就绪队列，返回子进程的pid。 进程创建时的状态为TASK_UNINTERRUPTIBLE，在do_fork（）结束前被父进程唤醒后，变为TASK_RUNNING。处于TASK_RUNNING状态的进程被移到就绪队列中，当适当的时候由schedule（）按CPU调度算法选中，获得CPU。 如果进程采用轮转法，当时间片到时（10ms的整数倍），由时钟中断触发timer_interrupt（）函数引起新一轮的调度，把当前进程挂到 就绪队列的尾部。获得CPU而正在运行的进程若申请不到某个资源，则调用sleep_on（）或interruptible_sleep_on（）睡眠， 并进入就绪队列尾。状态尾TASK_INTERRUPTIBLE的睡眠进程当它申请的资源有效时被唤醒，也可以由信号或者定时中断唤醒，唤醒以后进程状态 变为TASK_RUNNING，并进入就绪队列。 首先介绍一下2.6版以前的的调度算法的主要思想，下面的schedule（）函数是内核2.4.23中摘录的： asmlinkage void schedule(void) { struct schedule_data * sched_data; struct task_struct *prev, *next, *p; struct list_head *tmp; int this_cpu, c;
spin_lock_prefetch(&runqueue_lock);
BUG_ON(!current->active_mm); need_resched_back: /*记录当前进程和处理此进程的CPU号*/ prev = current; this_cpu = prev->processor; /*判断是否处在中断当中，这里不允许在中断处理当中调用sechedule（）*/ if (unlikely(in_interrupt())) { printk("Scheduling in interrupt/n"); BUG(); }
release_kernel_lock(prev, this_cpu);
/*'sched_data' 是收到保护的，每个CPU只能运行一个进程。*/ sched_data = & aligned_data[this_cpu].schedule_data;
spin_lock_irq(&runqueue_lock);
/*如果当前进程的调度策略是轮转RR，那么需要判断当前进程的时间片是否已经用完，如果已经用完，则重新计算时间片值，然后将该进程挂接到就绪队列run-queue的最后*/ if (unlikely(prev->policy == SCHED_RR)) if (!prev->counter) { prev->counter = NICE_TO_TICKS(prev->nice); move_last_runqueue(prev); } /*假如前进程为TASK_INTERRUPTTIBLE状态，则将其状态置为TASK_RUNNING。如是其它状态，则将该进程转为睡眠状态，从运行队列中删除。（已不具备运行的条件） */ switch (prev->state) { case TASK_INTERRUPTIBLE: if (signal_pending(prev)) { prev->state = TASK_RUNNING; break; } default: del_from_runqueue(prev); case TASK_RUNNING:; } /*当前进程不需要重新调度*/ prev->need_resched = 0;
/*下面是一般的进程调度过程*/
repeat_schedule: next = idle_task(this_cpu); c = -1000; /*遍历进程就绪队列，如果该进程能够进行调度（对于SMP来说就是判断当前CPU未被占用能够执行这个进程，对于非SMP系统则为1），则计算该进程的优先级，如果优先级大于当前进程，则next指针指向新的进程，循环直到找到优先级最大的那个进程*/ list_for_each(tmp, &runqueue_head) { p = list_entry(tmp, struct task_struct, run_list); if (can_schedule(p, this_cpu)) { int weight = goodness(p, this_cpu, prev->active_mm); if (weight > c) c = weight, next = p; } }
/* 判断是否需要重新计算每个进程的时间片，判断的依据是所有正准备进行调度的进程时间片耗尽，这时，就需要对就绪队列中的每一个进程都重新计算时间片，然后返回前面的调度过程，重新在就绪队列当中查找优先级最高的进程执行调度。 */ if (unlikely(!c)) { struct task_struct *p;
spin_unlock_irq(&runqueue_lock); read_lock(&tasklist_lock); for_each_task(p) p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice); read_unlock(&tasklist_lock); spin_lock_irq(&runqueue_lock); goto repeat_schedule; }
/*CPU私有调度数据中记录当前进程的指针，并且将当前进程与CPU绑定，如果待调度进程与前面一个进程属于同一个进程，则不需要调度，直接返回。*/ sched_data->curr = next; task_set_cpu(next, this_cpu); spin_unlock_irq(&runqueue_lock);
if (unlikely(prev == next)) { /* We won't go through the normal tail, so do this by hand */ prev->policy &= ~SCHED_YIELD; goto same_process; } /*全局统计进程上下文切换次数*/ kstat.context_swtch++; /*如果后进程的mm为0 （未分配页），则检查是否被在被激活的页里（active_mm）,否则换页。令后进程记录前进程激活页的信息，将前进程的active_mm中的 mm_count值加一。将cpu_tlbstate[cpu].state改为 TLBSTATE_LAZY(采用lazy模式) 如果后进程的mm不为0（已分配页），但尚未激活，换页。切换mm（switch_mm）。 如果前进程的mm 为0（已失效） ，将其激活记录置空，将mm结构引用数减一,删除该页。 */ prepare_to_switch(); { struct mm_struct *mm = next->mm; struct mm_struct *oldmm = prev->active_mm; if (!mm) { BUG_ON(next->active_mm); next->active_mm = oldmm; atomic_inc(&oldmm->mm_count); enter_lazy_tlb(oldmm, next, this_cpu); } else { BUG_ON(next->active_mm != mm); switch_mm(oldmm, mm, next, this_cpu); }
if (!prev->mm) { prev->active_mm = NULL; mmdrop(oldmm); } }
/*切换到后进程，调度过程结束*/ switch_to(prev, next, prev); __schedule_tail(prev);
same_process: reacquire_kernel_lock(current); if (current->need_resched) goto need_resched_back; return; }
3. 进程上下文切换（摘自中国Linux论坛一片文章） 首先进程切换需要做什么？它做的事只是保留正在运行进程的"环境"，并把将要运行的进程的"环境"加载上来，这个环境也叫上下文。它包括各个进程"公用"的东西，比如寄存器。 struct task_struct { 。。。 /* tss for this task */ struct thread_struct tss; 。。。 }; 它是专用来存放进程环境的，这个结构体因CPU而异，你看它就能知道有那些寄存器是需要保存的了。 最后的问题就是切换了，虽然在i386上CPU可以自动根据tss去进行上下文的切换，但是Linux的程序员们更愿意自己做它，原因是这样能得到更有效的控制，而且作者说这和硬件切换的速度差不多，这可是真的够伟大的。 好了，现在来看源码，进程切换是使用switch_to这个宏来做的,当进入时prev即是现在运行的进程，next是接下来要切换到的进程， #define switch_to(prev,next,last) do { / asm volatile( "pushl %%esi/n/t" / "pushl %%edi/n/t" / "pushl %%ebp/n/t" /
// 首先它切换堆栈指针，prev->tss.esp = %esp；%esp = next->tss.esp，这以后的堆栈已经是next的堆栈了。 "movl %%esp,%0/n/t" /* save ESP */ / "movl %3,%%esp/n/t" /* restore ESP */ /
// 然后使进程prev的指针保存为标号为1的那一个指针，这样下次进程prev可以运行时，它第一个执行的就是pop指令。 "movl $1f,%1/n/t" /* save EIP */ /
// 把进程next保存的指针推进堆栈中，这句作用是，从__switch_to返回时，下一个要执行的指令将会是这个指针所指向的指令了。 "pushl %4/n/t" /* restore EIP */ /
// 使用jump跳到__switch_to函数的结果是：调用switch_to函数但不象call那样要压栈，但是ret返回时，仍是要弹出堆栈的，也就是上条指令中推进去的指令指针。这样，堆栈和指令都换了，进程也就被"切换"了。 "jmp __switch_to/n" /
// 由于上面所说的原因，__switch_to返回后并不会执行下面的语句，要执行到这，只有等进程prev重新被调度了。 "1:/t" / "popl %%ebp/n/t" / "popl %%edi/n/t" / "popl %%esi/n/t" / :"=m" (prev->tss.esp),"=m" (prev->tss.eip), / "=b" (last) / :"m" (next->tss.esp),"m" (next->tss.eip), / "a" (prev), "d" (next), / "b" (prev)); / } while (0)
最后是__switch_to函数，它虽然是c形式，但内容还都是嵌入汇编。
// 这句跟fpu有关，我并不感兴趣，就略过了。 unlazy_fpu(prev);
// 这句可能需要你去记起前面第二章中所描述的gdt表的结构了，它的作用是把进程next的tss描述符的type中的第二位清0，这位表示这个描述符是不是当前正在用的描述符，作者说如果不清0就把它load进tss段寄存器的话，系统会报异常（我可没试过）。 gdt_table[next->tss.tr >> 3].b &= 0xfffffdff;
// 把进程next的tss段load到tss段存器中。 asm volatile("ltr %0": :"g" (*(unsigned short *)&next->tss.tr));
// 保存进程prev的fs和gs段寄存器 asm volatile("movl %%fs,%0":"=m" (*(int *)&prev->tss.fs)); asm volatile("movl %%gs,%0":"=m" (*(int *)&prev->tss.gs));
然后下面就是load进程next的ldt，页表，fs，gs，debug寄存器。 因为Linux一般并不使用ldt，所以它们一般会指向一个共同的空的ldt段描述符，这样就可能不需要切换ldt了，如果进程next和prev是共享内存的话，那么页表的转换也就不必要了（这一般发生在clone时）。
二、2.6版内核对进程调度的优化 1. 新调度算法简介 2.6版本的Linux内核使用了新的调度器算法，称为O（1）算法，它在高负载的情况下执行得非常出色，并在有多个处理器时能够很好地扩展。 2.4版本的调度器中，时间片重算算法要求在所有的进程都用尽它们的时间片后，新时间片才会被重新计算。在一个多处理器系统中，当进程用完它们的时 间片后不得不等待重算，以得到新的时间片，从而导致大部分处理器处于空闲状态，影响SMP的效率。此外，当空闲处理器开始执行那些时间片尚未用尽的、处于 等待状态的进程时，会导致进程开始在处理器之间“跳跃”。当一个高优先级进程或交互式进程发生跳跃时，整个系统的性能就会受到影响。 新调度器解决上述问题的方法是，基于每个CPU来分布时间片，并取消全局同步和重算循环。调度器使用了两个优先级数组，即活动数组和过期数组，可以 通过指针来访问它们。活动数组中包含所有映射到某个CPU且时间片尚未用尽的任务。过期数组中包含时间片已经用尽的所有任务的有序列表。如果所有活动任务 的时间片都已用尽，那么指向这两个数组的指针互换，包含准备运行任务的过期数组成为活动数组，而空的活动数组成为包含过期任务的新数组。数组的索引存储在 一个64位的位图中，所以很容易找到最高优先级的任务。
新调度器的主要优点包括： ◆ SMP效率 如果有工作需要完成，所有处理器都会工作。 ◆ 等待进程 没有进程需要长时间地等待处理器，也没有进程会无端地占用大量的CPU时间。 ◆ SMP进程映射 进程只映射到一个CPU，而且不会在CPU之间跳跃。 ◆ 优先级 非重要任务的优先级低，反之亦然。 ◆ 负载平衡 调度器会降低那些超出处理器负载能力的进程的优先级。 ◆ 交互性能 即使在高负载的情况下，系统花费很长时间来响应鼠标点击或键盘输入的情况也不会再发生。
2.6版内核中，进程调度经过重新编写，调度程序不需每次都扫描所有的任务，而是在一个任务变成就绪状态时将其放到一个名为“当前”的队列中。当进 程调度程序运行时，只选择队列中最有利的任务来执行。这样，调度可以在一个恒定的时间里完成。当任务执行时，它会得到一个时间段，或者在其转到另一线程之 前得到一段时间的处理器使用权。当时间段用完后，任务会被转移到另一个名为“过期”的队列中。在该队列中，任务会根据其优先级进行排序。 从某种意义上说，所有位于“当前”队列的任务都将被执行，并被转移到“过期”队列中。当这种事情发生时，队列就会进行切换，原来的“过期”队列成为 “当前”队列，而空的“当前”队列则变成“过期”队列。由于在新的“当前”队列中，任务已经被排列好，调度程序现在使用简单的队列算法，即总是取当前队列 的第一个任务进行执行。这个新过程要比老过程快得多。
2. 2.6版新调度算法分析 下面的schedule（）函数摘录自2.6.6版内核源码： asmlinkage void __sched schedule(void) { long *switch_count; task_t *prev, *next; runqueue_t *rq; prio_array_t *array; struct list_head *queue; unsigned long long now; unsigned long run_time; int idx;
if (likely(!(current->state & (TASK_DEAD | TASK_ZOMBIE)))) { if (unlikely(in_atomic())) { printk(KERN_ERR "bad: scheduling while atomic!/n"); dump_stack(); } } need_resched: preempt_disable(); prev = current; /*获取相应CPU的进程就绪队列，每一个CPU都会有一个进程就绪等待队列，每个等待队列包括两个优先级数组，活动数组和过期数组，两个数组可以进行轮换。CPU相关等待队列run-queue的数据结构定义如下： struct runqueue { spinlock_t lock; /*队列自旋锁*/ unsigned long long nr_switches;/*进程上下文切换次数计数器*/ unsigned long nr_running, expired_timestamp, nr_uninterruptible, timestamp_last_tick; task_t *curr, *idle; /*标记当前CPU正在执行的任务及空闲任务的PCB指针*/ struct mm_struct *prev_mm; /*内存数据结构*/ prio_array_t *active, *expired, arrays[2]; /*优先级活动和过期数组，活动数组用来标记当前时间片未用完并且处于等待调度状态的进程列表，而过期数组用来标记当前时间片消耗完毕，无法继续运行的进 程列表*/ int best_expired_prio, prev_cpu_load[NR_CPUS]; #ifdef CONFIG_NUMA atomic_t *node_nr_running; int prev_node_load[MAX_NUMNODES]; #endif task_t *migration_thread; struct list_head migration_queue;
atomic_t nr_iowait; }*/ rq = this_rq();
release_kernel_lock(prev); now = sched_clock(); if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG)) run_time = now - prev->timestamp; else run_time = NS_MAX_SLEEP_AVG;
/* * Tasks with interactive credits get charged less run_time * at high sleep_avg to delay them losing their interactive * status */ if (HIGH_CREDIT(prev)) run_time /= (CURRENT_BONUS(prev) ? : 1); * if entering off of a kernel preemption go straight * to picking the next task. */ switch_count = &prev->nivcsw; if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { switch_count = &prev->nvcsw; if (unlikely((prev->state & TASK_INTERRUPTIBLE) && unlikely(signal_pending(prev)))) prev->state = TASK_RUNNING; else deactivate_task(prev, rq); } /*如果当前就绪队列中没有正在运行的任务，则进行进程上下文切换，到空闲进程*/ if (unlikely(!rq->nr_running)) { #ifdef CONFIG_SMP load_balance(rq, 1, cpu_to_node_mask(smp_processor_id())); #endif if (!rq->nr_running) { next = rq->idle; rq->expired_timestamp = 0; goto switch_tasks; } } /*获取当前活动数组指针，判断处于活动状态的进程数目，如果活动数组当中已经没有任何活动的进程，则需要将活动数组与过期数组进行对换，这样就可以很快的开始新一轮的调度，这里array指针总是指向活动数组。*/ array = rq->active; if (unlikely(!array->nr_active)) { /* * Switch the active and expired arrays. */ rq->active = rq->expired; rq->expired = array; array = rq->active; rq->expired_timestamp = 0; rq->best_expired_prio = MAX_PRIO; } /*由于调度器事先将活动数组的索引存放在了一个64位的bitmap位图结构当中，排序的依据是根据每个进程的优先级排列的，所以当我们需要查找当前活 动数组中优先级最高的进程的索引时，仅仅需要从位图中找到最前面的一个索引值就可以了，而不需要想2.4内核那样每次遍历就绪队列，计算每个进程的优先级 然后才能确定应该选择哪个进程作为下一个调度的对象。 查找到当前队列中优先级最高的进程索引，然后在列表中找到相应的进程。*/ idx = sched_find_first_bit(array->bitmap); queue = array->queue + idx; next = list_entry(queue->next, task_t, run_list); /*一个进程的优先级是从0到MAX_PRIO-1（MAX_PRIO为140），实时进程优先级是从0到MAX_RT_PRIO- 1（MAX_RT_PRIO为100），SCHED_NORMAL任务的优先级在MAX_RT_PRIO到MAX_PRIO-1之间，优先级值越小表明优 先级越大。 在这里首先判断当前需要调度的进程是否为实时进程，如果不是看是不是处于活动状态，如果是，根据其消耗的时间片，重新计算优先级。*/ if (!rt_task(next) && next->activated > 0) { unsigned long long delta = now - next->timestamp;
if (next->activated == 1) delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
array = next->array; dequeue_task(next, array); recalc_task_prio(next, next->timestamp + delta); enqueue_task(next, array); } next->activated = 0; /*开始进行进程切换，关于内核如何进行上下文切换这里就不看了*/ switch_tasks: reacquire_kernel_lock(current); preempt_enable_no_resched(); if (test_thread_flag(TIF_NEED_RESCHED)) goto need_resched; } 3. 2.6版新调度算法流程图
三、内核中断及定时器实现分析 void do_timer(struct pt_regs *regs) 而在内核2.6版本以后，定时器中断处理采用了软中断机制而不是底半机制。时钟中断处理函数仍然为timer_interrup（）-> do_timer_interrupt（）－> do_timer_interrupt_hook（）－> do_timer（）。不过do_timer（）函数的实现有所不同： void do_timer(struct pt_regs *regs) 两者所调用的函数基本相同，但是2.4.23版内核与2.6.6内核中，对于update_process_times（）函数的实现不同： void update_process_times(int user_tick) update_one_process(p, user_tick, system, cpu); update_process_times（）调用run_local_timers（）引起TIMER_SOFTIRQ定时器软中断，处理器在随 后的合适的时机运行软中断处理函数run_timer_softirq，这个函数是在init_timers（）函数中注册的： void __init init_timers(void) (void *)(long)smp_processor_id()); typedef struct tvec_root_s { struct tvec_t_base_s { spinlock_t lock; unsigned long timer_jiffies; struct timer_list *running_timer; tvec_root_t tv1; tvec_t tv2; tvec_t tv3; tvec_t tv4; tvec_t tv5; } ____cacheline_aligned_in_smp; (!cascade(base, &base->tv2, INDEX(0))) && (!cascade(base, &base->tv3, INDEX(1))) && !cascade(base, &base->tv4, INDEX(2))) cascade(base, &base->tv5, INDEX(3)); ++base->timer_jiffies; list_splice_init(base->tv1.vec + index, &work_list); timer = list_entry(head->next,struct timer_list,entry); list_del(&timer->entry); }
Linux系统调用的形式与POSIX兼容，也是一套C语言函数名的集合，入fock（），read（）等等共221个。系统调用是通过INT 0x80软中断调用进入内核，然后根据系统调用号分门别类的进行服务。 系统调用号：文件include/asm-i386/unistd.h为每一个系统调用规定了唯一的编号，这个编号与真正的响应函数之间的关系是利 用系统调用号为数组的下标，可以在sys_call_table（系统调用表数组）中查找对应的响应函数的sys_name的入口地址。 系统调用表：系统调用表sys_call_table是一组宏定义，将系统调用的编号和相应的内核系统调用处理函数的入口地址绑定。 内核宏定义syscallN（）用于系统调用的格式转换和参数的传递。其中N取0～6之间的任意整数。参数个数为N的系统调用由syscallN负 责格式转换和参数传递。对系统调用的初始化，即是对INT 0x80的初始化。系统启动时，汇编子程序setup_idt准备了256项的idt表。设置0x80号软中断服务程序system_call，这个就是 所有系统调用的总入口。 当进程需要进行系统调用时，必须以C语言函数的形式写一句系统调用命令。该命令如果已经在某个头文件中由相应的syscallN（）展开，则用户程 序必须包含该头文件。当进程执行到系统调用命令时，实际上执行的是syscallN（）展开的函数。系统调用的参数由个寄存器传递，然后执行INT 0x80中断，以内核态进入入口地址system_call。 从system_call入口的汇编程序的主要功能是： l 保存寄存器当前值； l 检验是否为合法的系统调用； l 根据系统调用表sys_call_table和EAX持有的系统调用号找出并转入系统调用响应函数； l 从该响应函数返回后，让EAX寄存器保存函数返回值，跳转至ret_from_sys_call（arch/i386/kernel/entry.S）。 以ret_from_sys_call入口的汇编程序段在Linux进程管理中起着十分重要的作用。所有系统调用结束前，以及大部分中断服务程序返 回前，都会跳转至此入口地址。反过来，该段程序也不仅仅为系统调用服务，它还要处理中断嵌套、bottom half队列、CPU调度、信号等事务。 |
|
|
