进程调度

一、 概述 
在多任务环境中，调度是至关重要的。在Linux核心中，调度能在一个非常短的时间内将一个进程切换到另一个进程。调度的设计是非常巧妙的，下面我们来学习调度的过程。 
二、 涉及的数据结构。 
2．1在task_stuct 中的表述： 
289 struct exec_domain *exec_domain; 
290 volatile long need_resched; 需要重新调度标志。 
291 unsigned long ptrace; 被追踪标志。 
292 
293 int lock_depth; /* Lock depth */ 
294 
295 /* 
296 * offset 32 begins here on 32-bit platforms. We keep 
297 * all fields in a single cacheline that are needed for 
298 * the goodness() loop in schedule(). 
299 */ 
300 long counter; 记录该进程到时间片用完还剩余的时间。 
301 long nice; 进程优先权 
302 unsigned long policy; 调度策略 
303 struct mm_struct *mm; 进程所在的页 
304 int has_cpu, processor; has_cpu表示已分配cpu ，processor指向所分配的cpu 
305 unsigned long cpus_allowed; 
306 /* 
307 * (only the 'next' pointer fits into the cacheline, but 
308 * that's just fine.) 
309 */ 
310 struct list_head run_list; 
311 unsigned long sleep_time; 
312 
313 struct task_struct *next_task, *prev_task; 前一进程，后一进程 
314 struct mm_struct *active_mm; 激活的页 

三、 调度函数的工作过程。 
schedule() 
1，首先测试task_struct中的active_mm位，查看该进程的页是否处理活动状态，不在则替换。 
2，在此处放置一标号，在必要时用于重新调度（不需再测试active_mm位，因该页已被调入）。 
3， 把当前进程称之为前进程，准备对该进程的cpu 进行调度。 
4， 如果有硬中断（或处理机例外），结束此次调度，换入相应的页，进入中断处理。 
5， 解除前进程与cpu的锁。 
6， 如果有软中断，进入软中断处理（do_softirq）,处理完后继续调度。 
7， 读取调度数据， 锁运行队列（runqueue） 
8， 如果前进程的调度策略为SCHED_RR（时间片轮转），则检查前进程的剩余时间，如时间已用完， 则将其重新赋值，挂到队列runqueue的最后，等待调度。继续调度新进程 
9， 假如前进程为TASK_RUNNING或TASK_INTERRUPTTIBLE状态置为TASK_RUNNING状态。如是其它状态，则将该进程转为睡眠状态，从运行队列中删除。（已不具备运行的条件）. 
10， 将前进程的重调度标志置为0。 
11， 为该 cpu找一个等待任务，称之为后进程。将其优先权置为负值。 
12， 若前进程的状态为RUNNING，重新计算前进程的优先权，并将next指针指向前进程（即后进程亦是前进程），其优先权为前进程的优先权。 
13， 循环测试任务队列（run_list）获取其入口及数据，计算优先权，选取最高者。（next指针不一定再指向前进程） 
14， 若最高优先权不是正值，则将任务队列解锁，对原有任务的优先权进行一番调整（增量）。重新为cpu 分配任务。转向第11步 
15， 将调度数据的curr指向后进程，置后进程的有cpu标志（has_cpu）为1,cpu值存于processor中。 
16， 解运行队列锁。 
17， 如果后进程与前进程相同，若无重新调度标志。则已调度完毕，退出调度（无需切换）。若有重新调度标志，转向2，重新开始调度。 
18， 将context_swith增一（记录上下文切换次数，可否无限增加？）进行上下文切换。 
19， 如果后进程的mm为0 （未分配页），则检查是否被在被激活的页里（active_mm）,否则换页。令后进程记录前进程激活页的信息，将前进程的active_mm中的mm_count（？）值加一。将cpu_tlbstate[cpu].state改为 TLBSTATE_LAZY（????）(采用lazy模式) 
20， 如果后进程的mm不为0（已分配页），但尚未激活，换页。切换mm（switch_mm）。 
21， 如果前进程的mm 为0（已失效） ，将其激活记录置空，将mm结构引用数减一,删除该页。 
22， 切换到后进程 
23， 进入调度结束阶段 
将前进程的调度策略置为非SCHED_YIELD，置其为未分配cpu状态 
如果前进程依然为RUNNING，进入下一步。否则，准备退出调度。 
若前进程为空闲任务或调度策略是（自动放弃cpu）SCHED_YIELD， 
则退出调度。否则将该进程分配一个cpu ，让其的优先权尽可能高。 
24，如果有需要重新调度，则转回2，否则，结束调度。 
四，调度用到的函数。 
goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)计算优先权。 
idle_task(cpu) (&init_task) 获取空闲进程 
can_schedule(p,cpu) 判断进程是否可以分配给该cpu 
preemption_goodness(struct task_struct * prev, struct task_struct * p, int cpu)计算不可抢占的进程优先权。 
reschedule_idle(struct task_struct * p) 为被唤醒的进程分配能尽快运行的cpu 
add_to_runqueue(struct task_struct * p) 将进程加到运行队列中去。 
move_last_runqueue(struct task_struct * p) 将进程加到队列最后。 
move_first_runqueue(struct task_struct * p) 将进程加到队列最前。 
inline void wake_up_process(struct task_struct * p) 唤醒进程 
wake_up_process_synchronous(struct task_struct * p) 同步唤醒进程。 
process_timeout(unsigned long __data) 进程运行时间超时。 
schedule_timeout(signed long timeout) 调度时间超时。 
__schedule_tail(struct task_struct *prev) 调度后处理。 
__wake_up(wait_queue_head_t *q, unsigned int mode, int nr) 唤醒后备队列。 
sleep_on(wait_queue_head_t *q) 让后备任务睡眠。 
sleep_on_timeout(wait_queue_head_t *q, long timeout) 睡眠超时。 
setscheduler(pid_t pid, int policy, struct sched_param *param) 设置调度。 
sys_nice(int increment) 改变优先权。 
sys_sched_getscheduler(pid_t pid) 获取进程的调度策略 
sys_sched_setscheduler(pid_t pid, int policy, struct sched_param *param) 设置进程的调度策略及优先权。 
sys_sched_setparam(pid_t pid, struct sched_param *param) 为进程设置优先权 
sys_sched_getparam(pid_t pid, struct sched_param *param) 获取进程的优先权。 
sys_sched_yield(void) 自愿放弃cpu 
sys_sched_get_priority_max(int policy) 获取最大优先权。 
sys_sched_get_priority_min(int policy) 获取最小优先权。 
sys_sched_rr_get_interval(pid_t pid, struct timespec *interval) 轮转时间间隔 

====