3.4 重新计算时间片
- 当所有线程时间片用完时，老版本linux采用循环遍历计算的方式重新计算时间片
- 新版本调度程序通过维护两个优先级数组：活动数组和过期数组，过期时间耗尽的线程放入过期数组，异步计算过期数组的时间片 。最后只需要交换两个数组即可
- 静态优先级由用户指定后就不可更改，即前面介绍的nice值
- 动态优先级根据静态优先级和进程交互性函数关系计算而来
- effective_prio函数返回一个进程的动态优先级：该函数以nice值为基数，再根据交互程度加上奖惩值（-5～5）
- 交换程度判断：计算进程执行时间和休眠时间 。task_struct的sleep_avg变量，默认为10ms，休眠时增加该值（休眠时长），运行时减少该值
- 进程创建时，父子进程平分时间片 。防止创建多个进程以抢占更多cpu时间
- 任务时间片用完时，根据任务的动态优先级计算时间片 。函数为task_timeslice 。时间值根据优先级值按比例缩放 。最高200ms，最低10ms，默认为100ms
- 如果一个交互性很强的进程（TASK_INTER_ACTIVE宏），时间片用完后，会被再次放入活动数组而不是过期数组 。避免出现需要交互却因为没有等到两个数组交换而执行不了 。实现代码：scheduler_tick函数
- 处于休眠的线程进入等待队列，里面保存所有因等待某些事件发生的进程组成的简单链表
- 等待队列的数据结构为wake_queue_head_t
- 等待队列的创建：DECLEAR_WAITQUEUE或init_waitqueue_head
- 加入等待队列：add_wait_queue
- 与等待队列相关的事件发生时，队列的进程会被唤醒，使用wake_up函数
- 负载平衡程序针对多处理器系统中可执行程序负载不均衡的情况
- 函数为kernel/sched.c中的load_balance函数
- 调用时机：可执行队列为空时，定时调用（系统空闲时每隔1ms调用，其他情况每隔200ms调用） 。单处理器不需要此函数 。
- 负载平衡调用时需要锁定当前队列，并且屏蔽中断
- load_balance操作步骤： 调用find_busiest_queue，找到最繁忙的队列 。该队列进程数最多 。如果没有超过当前队列25%的队列，直接结束返回 从繁忙队列中选择一个优先级数组用来抽取进程，最好是过期数组 寻址含有优先级最高（值最小）的链表，把高优先级的进程分散开 找到链表中没有在执行，且可移动，且不在高速缓存中的进程，靠用pull_task将进程抽取到当前队列 只要队列不平衡就执行以上步骤 。最后释放锁 。
- 上下文切换是从一个进程切换到另一个进程 。
- 上下文切换定义在kernel/sched.c中的context_switch函数，该函数完成两项基本工作 调用定义在include/asm/menu_context.h中的switch_mm，负责把虚拟内存从上一个进程映射切换到新进程中 调用定义在include/asm/system.h中的switch_to，负责从上一个进程的处理器状态切换到新进程的处理器状态 。包括保存，恢复栈信息和寄存器信息
- 内核提供need_resched标志表明是否需要重新调度 。某个进程用尽时间片时，schedular_tick会设置该标志；当一个高优先级进程进入可执行状态时，try_to_wake_up也会设置该标志
- 每个进程都包含need_resched标志
- 用户抢占：内核返回用户空间时，如果need_reshed被设置，导致调用schedule，会选择一个更合适的进程执行的情况
- 用户抢占在以下情况时发生： 从系统调用返回用户空间 从中断处理程序返回用户空间
- 大部分Unix其他变体和大部分操作系统，不支持内核抢占，内核代码需要一直执行直到完成
- 2.6版本内核中，添加了内核抢占 。只要重新调度是安全的，就可以内核抢占
- 只要没有持有锁，重新调度就是安全的，可以内核抢占
- 持有锁使用thread_info中的preempt_count计数器表示，使用锁时数值加一，释放锁时数值减一
- 内核抢占在以下情况时发生： 从中断处理程序返回内核空间时 当内核代码再一次具有可抢占性时 内核中的任务显示调用schedule 内核中的任务阻塞
- sched_setscheduler：设置task_struct的policy和rt_priority值
- sched_setaffinity：设置task_struct的cpus_allowed这个位掩码标志
- sched_yield：将进程从活动队列移动到过期队列，以让出执行时间