study kernel(1) -- process, schedule

一、 进程
1. 进程描述符
内核用进程描述符task_struct表示用户空间中进程的所有信息。
task_struct 定义如下：
struct task_struct {
volatile long state; //进程运行状态
struct thread_info; //线程描述符
struct mm_struct; //描述内存存储信息
struct tty_struct; //与进程相关的tty
struct fs_struct; //当前目录
struct signal_struct; //所接收的信号
......
};
其中，state用于表示进程当前的运行状态进程状态：
1． TASK_RUNNING：进程正在执行或是可执行的，调度器可将其加入运行队列(runqueue)。
2． TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE：进程由于某些原因（通常是状态不满足）而被阻塞，当条件满足后，则会重新变成TASK_RUNNING。不同的是， TASK_INTERRUPTIBLE，可以响应内核发出的信号；而TASK_UNITERRUPTIBLE不响应内核发出的信号。
3． EXIT_ZOMBIE：进程已经结束，但此时任占用内核栈、thread_info、task_struct，为了向父进程提供信息。当父进程调用了wait4()后，信息会被释放。
4． __TASK_STOPPED：进程停止运行。
2. 创建进程
fork()系统调用的功能是为当前进程创建一子进程。调用此函数时，系统将调用宏指令_syscall0，并做最终调用内核接口sys_fork()。
asmlinkage int sys_fork(struct pt_regs regs)
{
return do_fork(SIGCHLD, regs.esp, ®s, 0, NULL, NULL);
}
SIGCHLD是在定义的一个宏，它告诉do_fork()函数应创建一个子进程，即创建并初始化进程描述符task_struct以及他包含的其他结构。
3. 创建内核线程
Linux内核可以看作一个服务进程。内核需要多个执行流并行，为了防止可能的阻塞，多线程化是必要的。内核线程的调度由内核负责，一个内核线程处于阻塞状态时不影响其他的内核线程，因为其是调度的基本单位。
内核线程是由kernel_thread()函数在内核态下创建的:
int kernel_thread(int (*fn)(void *), void * arg, unsigned long flags)
{
struct pt_regs regs;
memset(®s, 0, sizeof(regs));
......
/* Ok, create the new process.. */
return do_fork(flags|CLONE_VM|CLONE_UNTRACED, 0, ®s, 0, NULL, NULL);
}
内核线程的创建本质上也是建立了一个task_struct。其中CLONE_VM标志表示，避免复制进程的页表。内核线程和调用的进程(current)具备相同的进程空间，因为调用者运行在进程的内核态，所以进程在内核态时共享内核空间。

二、 进程调度
4. 进程调度类型
Linux进程按照下面调度类型被调度：
SCHED_FIFO：先进先出的实时进程。如果没有其他可运行的更高优先级实时进程，该进程将一直占用CPU。
SCHED_RR：时间片轮转的实时进程。所有具有相同优先级的SCHED_RR实时进程公平分配CPU时间。
SCHED_NORMAL：普通的分时进程。
5. 普通进程调度
普通进程通过静态优先级nice值决定进程的基本时间片，nice值越小，静态优先级越高，进程获得的CPU时间更长。同时以nice值为基础并通过检查进程过去的情况设置优先级，既动态优先级。调度程序总是选择动态优先级高的进程投入运行。
Linux基于以动态优先级为基础的调度算法。内核为每个进程设置一个基本的优先级，但它允许调度程序根据需要来加减优先级，然后挑选优先级最高的进程投入运行。当进程时间片用完重新分配时间时，也会根据优先级值动态分配时间。
6. 实时进程调度
实时算法实现都是静态优先级，而不会设置动态优先级。这能保证优先级高的实时进程总能抢占优先级低的进程。
7. 更新时间片scheduler_tick()
void scheduler_tick(void)
{
struct task_struct *p = current;

if (p->array != rq->active) { //如果current->array没有指向runqueue，说
set_tsk_need_resched(p); 明进程已经过期但未被替换，则设置
goto out; need_resched字段以进行重新调度
}

/* current为SCHED_FIFO，进程不会被低优先级进程抢占，因此不更新时间片。
current为SCHED_RR，时间片将递减。若时间片用完，则重新计算时间片，设置need_resched字段，将进程加入runqueue尾部。
*/
if (rt_task(p)) {
if ((p->policy == SCHED_RR) && !--p->time_slice) {
p->time_slice = task_timeslice(p); //根据静态优先级计算时间片
set_tsk_need_resched(p);
requeue_task(p, rq->active);
}
goto out_unlock;
}
/* 更新普通进程时间片。若时间片用完，设置need_resched字段，根据动态优先级设置进程优先级，根据静态优先级设置时间片。若时间片未用完，则检查进程是否可继续占用CPU。
*/
if (!--p->time_slice) {
set_tsk_need_resched(p);
p->prio = effective_prio(p);
p->time_slice = task_timeslice(p);
} else {
......
}
}
8. 调度程序schedule()
调用schedule()函数分为直接调用和延迟调用。如果current进程因不能获得必要的资源要立即被阻塞，就直接调用schedule()；也可通过设置current的need_resched字段被设置，以延迟方式调用schedule()。由于总是在恢复用户态进程的执行前检查这个标志，所有schedule()将在不久之后的某个时间被调用。
asmlinkage void __sched schedule(void)
{
struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array *array;
int idx;
struct rq *rq;
……
……
prev = current;
array = rq->active; //获取活动优先级队列
idx = sched_find_first_bit(array->bitmap); //通过优先级位图快速查找进程
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list); //返回进程描述符
if(prev != next)
context_switch(); //如果选中的进程不是当前进程则进行上下文切换
}
9. 用户抢占
内核即将返回用户空间时，如果need_resched标志被设置，会导致schedule()被调用，发生用户抢占。
10. 内核抢占
thread_info引入了preempt_count计数器。该计数器初始值为0，每当使用锁的 时候数值加1，释放锁的时候数值减1。当数值为0的时候，内核就可执行抢占。从中断返回内核空间的时候，内核会检查need_resched和preempt_count的值。如果need_resched被设置，并且preempt_count为0的话，这说明有一个更为重要的任务需要执行并且可以安全地抢占，此时调度程序就会调度(抢占当前进程)。如果preempt_count不为0，说明当前 任务持有锁，所以抢占是不安全的。这时，就会像通常那样直接从中断返回当前执行进程。 如果当前进程所持有的所有的锁都被释放了。那么preempt_count就会重新为0。此时，释放锁的代码会检查need_resched是否被设置。如果是的话，就会调用调度程序。