lkd2 note
chapter 2
从内核出发
从何处获取源码，如何编译，如何安装新内核。
内核的一些状态，内核程序与用户空间的差异，内核所用一般函数的特点�

3.4 进程终结

进程终结时内核必须释放它所占有的资源，并通告其父。
进程的析构发生在它调用 exit() 之后。
do_exit():
. task_struct.state = PF_EXITING
. 调用 del_timer_sync() 删除内核定时器。
. 如果 BSD 的进程计账功能开启，do_exit() 调用 acct_process() 来输出计账信息。
. 然后调用 _exit_mm() 来放弃进程占用的 mm_struct ，如果没有别的进程使用它们（也就是说它们没有被共享），就彻底释放它们。
.调用 exit__sem()。如果进程排队等候 IPC 信号，则离队。
.调用 _exit_files()、_exit_fs()、exit_namespace() 和 exit_sighand()，以分别递减文件描述符、文件系统数据，进程名字空间和信号处理函数的引用计数。如果其中某些引用计数的值降为 0，则释放资源。
.把存放在 task_struct 中的 exit_code 成员中的任务退出代码置为 exit() 提供的代码。或者去完成任何其它由内核机制规定的退出动作。退出代码存放在这里供父进程有时检索。
. 调用 exit_notify() 向父进程发送信号，将子进程的父进程重新设置为线程组中的其它线程或 init 进程，并把进程状态设成 TASK_ZOMBIE.
. 最后 do_exit() 调用 schedule() 切换到其他进程。此进程不再被调度。
do_exit() kernel/exit.c

到此，进程只保留着内核栈、thread_info 和 task_struct ，此时进程存在的唯一目的就是向它的父进程提供信息。父进程检索到信息或通知内核这些信息无关后，进程所持有的剩余内存被释放，归还给系统。

3.4.1 删除进程描述符

退出清理工作完成后，在父进程获得已终结的子进程的信息后，或者通知内核它并不关注那些信息后，子进程的 task_struct 才被释放。

wait() 这一族函数通过 wait4() 实现。它先挂起调用它的进程，再到其中的一个子进程退出后返回该子进程的 PID 。此外调用该函数时提供的指针会指向子函数退出时的退出代码（此处不解原文。？？）

最终释放进程描述符时，release_task() 被调用：
. 调用 free_uid() 来减少该进程拥有者的进程使用计数。Linux 用一个单用户 Cache 统计和记录每个用户占用的进程数目、文件数目。如果这些数目都为 0 ，这块 Cache 就可以被销毁了。
. 调用 unhash_process 从 pidhash 上（？）删除该进程，同时也从 task_list 中删除该进程。
. 接下来，如果这个进程正在被 ptrace 跟踪，release_task（） 将跟踪进程的父进程重设为其最初的父进程并将它从 ptract_list 上删除。??
. 最后调用 put_task_struct() 释放进程内核栈和 thread_info 所占的页，并释放 task_struct 所占的 slab cache.

3.4.2 孤儿进程所赞成的进退维谷

如果孤儿已经产生，则内核会给孤儿在当前线程组（何谓“当前线程组”？）内找一个线程作为父亲；如果找不到，就让 init 做它们的父进程。在 do_exit() 中调用 notify_parent(), 该函数会通过 forget_original_parent() 来执行寻父过程。

struct task_struct *p, *reaper = father;
struct list_head * list;

if (father->exit_signal != -1)
reaper = prev_thread(reaper);
else
reaper = child_reaper;

if (reaper == father)
reaper = child_reaper;

4.2 Linux 调度算法

kernel/sched.c
2.5 版时重写了大部分代码。重新设计的原因有：
. 充分实现 O(1) 调度。不管有多少进程，新调度程序彩的每个算法都能在恒定时间内完成。
. 全面实现 SMP 的可扩展性，每个处理哭拥有自己的销和自己的可执行队列。
. 强化 SMP 的亲和力。昼将相关的一组任务分配给一个 CPU 进行连续的执行。只有在需要平衡任务队列的大小时才在 CPU 之间移动进程。
. 加强交互性能。即使在系统处于相当负载的情况下，也能保证系统的响应，并立即调度交互式进程。
. 保证公平。在合理设定的时间范围内，没有进程会处于饥饿状态。同样也没有进程能显失公平地得到大量的时间片。
. 虽然最常见的优化情况是系统中只有 1 ~ 2 个可运行进程，但是优化也完全有能力扩展到具有多处理器且每个处理器上运行了多个进程的系统中。

4.2.1 可执行队列

调度程序中最基本的数据结构是运行队列（runqueue），定义见 kernel/sched.c ，由结构 runqueue 表示。它是给定处理器上的可执行进程的链表，每个处理器一个，每个可投入运行的进程都惟一地归属于一个可执行队列。runqueue 中还包含每个处理器的调度信息。

一些宏： cpu_rq(processor) 返回给定处理器可执行队列的指针；this_rq() 返回当前处理器的可执行队列；task_rq(task) 反回指定任务所在的队列指针。

在对可执行队列进行操作以前，应该先锁住它。不过一个处理器很少需要锁其它处理器的 runqueue。

struct runqueue *rq;
unsigned long flags;

rq = task_rq_lock(task, &flags);
/* 对任务队列 rq 进行操作 */
task_rq_unlock(rq, &flags);

或者可以用 this_rq_lock() 来锁住当前的可执行，用 rq_unlock(struct runqueue *rq) 释放给定队列上的锁。

struct runqueue * rq;

rq = this_rq_lock();
/* 操作此 rq */
rq_unlock(rq);

为了避免死锁，要锁住多个运行队列的代码时必须按照可执行队列地址从低向高的顺序：

/* 锁定 */
if (rq1 == rq2)
spin_lock(&rq1->lock);
else{
if (rq1 < rq2){
spin_lock(&rq1->lock);
spin_lock(&rq2->lock);
} else {
spin_lock(&rq2->lock);
spin_lock(&rq1->lock);
}
}
/* 操作 rq1 rq2 */

/* 释放锁 */
spin_unlock(&rq1->lock);
if (rq1 != rq2)
spin_unlock(&rq2->lock);

这些步骤可以简化为：

double_rq_lock(rq1, rq2);
/* 操作两个 rq ... */
double_rq_unlock(rq1, rq2);

这些代码的原理就是，嵌套的锁必须以相同的顺序操作。

4.2.2 优先级数组

每个任务队列都有两个优先组数组，一个活跃的和一个过期的。

/* kernel/sched.c */

#define MAX_PRIO  140
#define BITMAP_SIZE  5

struct prio_array{
int nr_active; /* 任务数目 */
unsigned long bitmap[BITMAP_SIZE]; /* 优先级位图 */
struct list_head queue[MAX_PRIO]; /* 优先级队列 */
}

sched_find_first_bit()
find-first-set

4.3 抢占和上下文切换

上下文切换就是从一个可执行进程切换到另一个可执行进程。由 kernel/sched.c 中的 context_switch() 函数处理。每当一个新的进程被先出来准备投入运行的时候，schedule() 就会调用该函数：
.调用定义在 <asm/mmu_context.h> 中的 switch_mm(),该函数负责把虚拟内存从上一个进程映射切换到新进程中
.调用定义在 <asm/system.h> 中的 switch_to() ，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息。

内核提供了一个 need_resched 标志来表明是否需要重新调度。当某个进程耗尽它的时间片时，scheduler_tick() 会设置这个标志；当一个优先级高的进程进入可执行状态时，try_to_wake_up() 也会设置这个标志。

set_tsk_need_resched()
clear_tsk_need_resched()
need_resched()

在返回用户空间以及从中断返回的时候，if (need_resched()) schedule();

每个进程都包含一个 need_resched 标志，它在 thread_info 中的一个特别的标志变量中的一位来表示。它比全局变量快。

4.3.1 用户抢占

（从中断或系统调用）返回用户空间时调度是安全而且合理的。

4.3.2 内核抢占

只要没有持有锁，内核就可以抢占。为了支持内核抢占在 thread_info 引入了 preempt_count 计数器，它初始值为 0，每当使用锁时加 1 ，释放锁时减 1。从中断返回内核空间的时候，如果 need_resched 被设置并且 preempt_count 为 0，调度程序会被调用。释放锁的代码也会检查 need_resched 是否被设置而选择是否执行 schedule()。有些内核代码需要允许或禁止内核抢占。

内核抢占发生在：
.？？？？
.当内核代码再一次具有可抢占性的时候
.显式地调用 schedule()
.任务阻塞

4.4 实时

两种实时高度策略：SCHED_FIFO 和 SCHED_RR。普通的调度策略是 SCHED_NORMAL。

SCHED_FIFO：一直执行抢占 SCHED_NORMAL 进程，直到它愿意让出处理器。
SCHED_RR：带时间片的 SCHED_FIFO，当时间片被耗尽时同一优先级的其它任务被调度。

实时优先级范围从 0 到 MAX_RT_PRIO - 1。

4.5 与调度相关的系统调用

与调度相关的系统调用
nice()
sched_setscheduler()
sched_getscheduler()
sched_setparam()
sched_getparam()
sched_get_priority_max()
sched_get_priority_min()
sched_rr_get_interval()
sched_setaffinity()
sched_getaffinity()
sched_yield()

4.5.1 与调度策略和优先级有相关的系统调用

4.5.2 与处理器绑定有关的系统调用

4.5.3 放弃处理器时间

你现在有时间研究这个？
工作需要吗�

生活需�