linux任务调度学习

daly88

调度单位
    进程描述，位于运行栈底部，可通过偏移定位
thread_info {      
         task_struct *task;   //基本调度单位(下面展开)
         flags //TIF_NEED_RESCHED表明需要调度
         cpu   //CPU号
        。。。
     }
任务调度的基本单位
    task_struct {     
         state   //状态, TASK_RUNNING, ZOMBIE或其他
         *thread_info
         prio      动态优先级
         static_prio   静态优先级
         sleep_avg    平均睡眠时间
         policy       调度算法,NORMAL, RR, FIFO
         time_slice     剩余的时间片
         rt_priority     实时优先级
         ... ...
    }
    运行队列(调度控制结构)
    runqueue {
         task_struct *curr   正在运行的任务
         prio_array   *active   活动的优先队列
         prio_array   *expired 过期的优先队列
         prio_array   arrays[2] 实际优先队列
         ...
     }
    优先队列（O(1)调度算法的结构）
    prio_array {
         nr_active   队列中的任务数
         bitmap[BITMAP_SIZE]   
// 优先位图, 用1表示对应优先级有进程需要调度，0表示没有。通过位查找，快速找到优先级最高的任务。
         list_head queue[MAX_PRIO] 优先队列
    }
优先级
    linux把进程分为实时调度与一般调度。实时调度优先级为0~99, 只用FCFS或RR来调度。非实时的一般进程优先级为100~139，即其计算公式为100（最高实时优先级）+20+nice。其中nice值为-20~19, 由进程创建时指定。动态优先级根据进程的交互性来动态计算优先级，一般以nice为基数，加上-5~+5的交互性奖罚。通过计算sleep_avg来评估进程的交互性，如果sleep_avg比较多，即该进程为IO消耗型，可把其优先级降低(不需占用太多CPU)，反之亦然。
时间片
    进程的可用时间片是按照计算出来的优先级按比例分配。数值为5~800ms, 默认值为100ms.
可调度标志
内核提供了一个need_resched标志来表明是否需要重新执行一个调度。当某个进程耗尽它的时间片时，scheduler_tick()就会设置这个标志；当一个优先级高的进程进入可执行状态的时候，try_to_wake_up()也会设置这个标志。在返回用户空间以及从中断返回的时候，内核也会检查need_resched标志。如果已被设置，内核会在继续执行之前调用调度程序
调度算法
    核心由schedule()函数和scheduler_tick()函数实现。schedule函数从优先级数组prio_array中选取优先级最高的进程 --> 获取进程的thread_info --> 实施context switch切换到新的进程运行。而scheduler_tick()主要是更新时间片，时钟中断程序会自动调用scheduler_tick。scheduler_tick判断当前进程
若为实时进程，且时间片耗尽，重新计算时间片，并重新插入活跃队列的尾部。
若为普通进程，且时间片耗尽，重新计算时间片，移入过期队列。
    当活跃优先级队列中已没有剩余的被调度进程，活跃优先级队列与过期优先级队列的指针进行交换，进入新一轮的调度。2.6版本内核每次时间片用完就重新计算时间片，大大提升了调度效率。

何时调度？（何时被调用schedule()）
    1. 直接主动调用
2. 活动进程进入睡眠
3. 设置need_resched.当从内核态返回用户态时检测这个位，如果为1，则调度schedule().
   以下三种情况会设置need_schedule
a. 时钟中断服务程序中，用完自己的时间片
b. 当唤醒一个睡眠进程时，该进程有更高优先级
c. 一个进程改变了调度策略，优先级等。
何时抢占？
    用户抢占
     1. 当从系统调用返回到用户态
     2. 从中断程序返回到用户态。
内核抢占
2.6版本的内核是可以抢占的。
1. 从中断返回内核时，若内核不拥有锁，则可被抢占。若拥有锁，则不可抢占。这是内核通过preempt_count变量来判断的。
2. 内核阻塞，导致调用schedule()

参考
linux kernel 2.6进程调度分析
http://blog.163.com/steven_zyz/blog/static/1178243820071144412485/
Robert Love

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/73519/showart_1080925.html