第三章--进程

        在Linux源代码中，常把进程称为任务(task)或线程(thread)。
一、进程、轻量级进程和线程
        进程是程序执行时的一个实例。你可以把它看作充分描述程序已经执行到何种程度的数据结构的汇集。
        进程类似于人类：它们被产生，有或多或少有效的生命，可以产生一个或多个子进程，最终都要死亡。但是进程之间没有性别差异--每个进程都只有一个父亲。
        从内核观点看，进程的目的就是担当分配系统资源(CPU时间、内存等)的实体。
        一个进程由几个用户线程(或简单地说，线程)组成，每个线程都代表进程的一个执行流。现在，大部分多线程应用程序都是用pthread库的标准库函数集编写的。

二、进程描述符
        进程描述符(process descriptor)的作用：描述进程的优先级，进程是正在CPU上运行还是因某些事件而被阻塞，给它分配了什么样的地址空间，允许它访问哪个文件等等。进程描述符都是task_struct类型结构，它的字段包含了与一个进程相关的所有信息。
        本章集中讨论进程的两种字段：进程的状态和进程的父/子间关系。
2.1、进程状态
        进程描述符中的state字段描述了进程当前所处的状态。它由一组标志组成，其中每个标志描述一种可能的进程状态。在当前的Linux版本中，这些状态是互斥的，因此，严格意义上说，只能设置一种状态：其余的标志将被清除。可能的状态包括：
        1、可运行状态(TASK_RUNNING)
        进程要么在CPU上执行，要么准备执行。
        2、可中断的等待状态(TASK_INTERRUPTIBLE)
        进程被挂起(睡眠)，直到某个条件变为真。产生一个硬件中断，释放进程正等待的系统资源，或传递一个信号都是可以唤醒进程的条件(把进程的状态放回到TASK_RUNNING)。
        3、不可中断的等待状态(TASK_UNINTERRUPTIBLE)
          与可中断的等待状态类似，但有一个例外，把信号传递到睡眠进程不能改变它的状态。
        4、暂停状态(TASK_STOPPED)
        进程的执行被暂停。当进程接收到SIGSTOP、SIGTSTP、或SIGTTOU信号后，进入暂停状态。
        5、跟踪状态(TASK_TRACED)
        进程的执行已由debugger程序暂停。当一个进程被另一个进程监控时(例如debugger执行ptrace()系统调用监控一个测试程序)，任何信号都可以把这个进程置于TASK_TRACED状态。
        还有两个进程状态是既可以存放在进程描述符的state字段中，也可以存放在exit_state字段中。从这两个字段的名称可以看出，只有当进程的执行被终止时，进程的状态才会变为这两种状态中的一种：
        僵死状态(EXIT_ZOMBIE)：
        进程的执行被终止，但是，父进程还没有发布wait4()或waitpid()系统调用来返回有关死亡进程的消息。发布wait()类系统调用前，内核不能丢弃包含在死进程描述符中的数据，因为父进程可能还需要它。
        僵死撤销状态(EXIT_DEAD)：
        最终状态：由于父进程刚发出wait4()或waitpid()系统调用，因而进程由系统删除。为了防止其他执行线程在同一个进程上也执行wait()类系统调用(这是一种竞争条件)，而把进程的状态由僵死(EXIT_ZOMBIE)状态改为僵死撤销状态(EXIT_DEAD)。
        内核也使用set_task_state和set_current_state宏：它们分别设置指定进程的状态和当前执行进程的状态。此外，这些宏确保编译程序或CPU控制单元不把赋值操作与其他指令混合。混合指令的顺序有时会导致灾难性的后果。
2.2、标识一个进程
        能被独立调度的每个执行上下文都必须拥有它自己的进程描述符。
        一个多线程应用程序中的所有线程都必须有相同的PID。
        遵照上面标准，Linux引入线程组的表示。一个线程组中的所有线程使用和该线程组的领头线程(thread group leader)相同的PID，也就是该组中第一个轻量级进程的PID，它被存入进程描述符的tgid字段中。getpid()系统调用返回当前进程的tgid值而不是pid的值，因此，一个多线程应用的所有线程共享相同的PID。绝大多数进程都属于一个线程组，包含单一的成员；线程组的领头线程其tgid的值与pid的值相同，因而getpid()系统调用对这类进程所起的作用和一般进程是一样的。
2.2.1、进程描述符处理
        进程是动态实体，其生命周期范围从几毫秒到几个月。因此，内核必须能够同时处理很多进程，并把进程描述符存放在动态内存中，而不是放在永久分配给内核的内存区。对每个进程来说，Linux都把两个不同的数据结构紧凑地存放在一个单独为进程分配的存储区域内：一个是内核态的进程堆栈，另一个是紧挨进程描述符的小数据结构thread_info，叫做线程描述符，这块存储区域的大小通常为8192个字节(两个页框)。考虑到效率的因素，内核让这8K空间占据连续的两个页框并让第一个页框的起始地址是2¹³的倍数。当几乎没有可用的动态内存空间时，就会很难找到这样的两个连续页框，因为空闲空间可能存在大量碎片。因此，在80x86体系结构中，在编译时可以进行设置，以使内核栈和线程描述符跨越一个单独的页框(4096个字节)。
        当使用一个页框存放内核态堆栈和thread_info结构时，内核要采用一些额外的栈以防止中断和异常的深度嵌套而引起的溢出。
        内核使用alloc_thread_info和free_thread_info宏分配和释放存储thread_info结构和内核栈的内存区。
2.2.2、标识当前进程
        thread_info结构与内核态堆栈之间的紧密结合提供的主要好处是：内核很容易从esp寄存器的值获得当前在CPU上正在运行进程的thread_info结构的地址。事实上，如果thread_union结构长度是8K(2¹³字节)，则内核屏蔽掉esp的低13位有效位就可以获得thred_info结构的基地址；而如果thread_union结构长度是4K，内核需要屏蔽掉esp的低12位有效位。这项工作由current_thread_info()函数来完成。
          用栈存放进程描述符的另一个优点体现在多处理器系统上：如前所述，对于每个硬件处理器，仅通过检查栈就可以获得当前正确的进程。
2.2.3、双向链表

2.2.4、进程链表
        进程链表把所有进程的描述符链接起来。每个task_struct结构都包含一个list_head类型的tasks字段，这个类型的prev和next字段分别指向前面和后面的task_struct元素。
        进程链表的头是init_task描述符，它是所谓的0进程(process 0)或swapper进程的进程描述符。init_task的tasks.prev字段指向链表中最后插入的进程描述符的tasks字段。
2.2.5、TASK_RUNNING状态的进程链表
        当内核寻找一个新进程在CPU上运行时，必须只考虑可运行进程(即处在TASK_RUNNING状态的进程)。
        提高调度程序运行速度的诀窍是建立多个可运行进程链表，每种进程优先权对应一个不同的链表。每个task_struct描述符包含一个list_head类型的字段run_list。如果进程的优先权等于k(其取值范围是0到139)，run_list字段把该进程链入优先权为k的可运行进程的链表中。此外，在多处理器系统中，每个CPU都有它自己的运行队列，即它自己的进程链表集。这是一个通过使数据结构更复杂来改善性能的典型例子：调度程序的操作效率的确更高了，但运行队列的链表却为此而被拆分成140个不同的队列！
2.3、进程间的关系
        程序创建的进程具有父/子关系。如果一个进程创建多个子进程时，则子进程之间具有兄弟关系。在进程描述符中引入几个字段来表示这些关系。进程0和进程1是由内核创建的，进程1(init)是所有进程的祖先。
2.3.1、pidhash表及链表

2.4、如何组织进程
        运行队列链表把处于TASK_RUNNING状态的所有进程组织在一起。当要把其他状态的进程分组时，不同的状态要求不同的处理。Linux选择了下列方式之一：
        * 没有为处于TASK_STOPPED、EXIT_ZOMBIE或EXIT_DEAD状态的进程建立专门的链表。由于对处于暂停、僵死、死亡状态进程的访问比较简单，或者通过PID，或者通过特定父进程的子进程链表，所以不必对这三种状态进程分组。
2.4.1、等待队列
        等待队列实现了在事件上的条件等待：希望等待特定事件的进程把自己放进合适的等待队列，并放弃控制权。因此，等待队列表示一组睡眠的进程，当某一条件变为真时，由内核唤醒它们。
        等待队列链表中的每个元素代表一个睡眠进程，该进程等待某一事件的发生；它的描述符地址存放在task字段中。task_list字段中包含的是指针，由这个指针把一个元素链接到等待相同事件的进程链表中。
        有两种睡眠进程：互斥进程(等待队列元素的flags字段为1)由内核有选择地唤醒，而非互斥进程(falgs值为0)总是由内核在事件发生时唤醒。等待访问临界资源的进程就是互斥进程的典型例子。等待相关事件的进程是非互斥的。例如，我们考虑等待磁盘传输数据的一组进程：一旦磁盘传输完成，所有等待的进程都会被唤醒。正如我们将在下面所看到的那样，等待队列元素的func字段用来表示等待队列中睡眠进程应该用什么方式唤醒。
2.4.2、等待队列的操作
        可以用DECLARE_WAIT_QUEUE_HEAD(name)宏定义一个新等待队列的头，它静态地声明一个叫name的等待队列的头变量并对该变量的lock和task_list字段进行初始化。函数init_waitqueue_head()可以用来初始化动态分配的等待队列的头变量。
        一旦定义了一个元素，必须把它插入等待队列。add_wait_queue()函数把一个非互斥进程插入等待队列链表的第一个位置。add_wait_queue_exclusive()函数把一个互斥进程插入等待队列链表的最后一个位置。remove_wait_queue()函数从等待队列链表中删除一个进程。waitqueue_active()函数检查一个给定的等待队列是否为空。
        sleep_on()类函数在以下条件下不能使用，那就是必须测试条件并且当条件还没有得到验证时又紧接着让进程去睡眠；由于那些条件是众所周知的竞争条件的根源，所以不鼓励这样使用。此外，为了把一个互斥进程插入等待队列，内核必须使用prepare_to_wait_exclusive()函数[或者只是直接调用add_wait_queue_exclusive()]。所有其他的相关函数把进程当作非互斥进程来插入。最后，除非使用DEFINE_WAIT或finish_wait()，否则内核必须在唤醒等待进程后从等待队列中删除对应的等待队列元素。
        内核通过下面的任何一个宏唤醒等待队列中的进程并把它们的状态置为TASK_RUNNING：wake_up，wake_up_nr，wake_up_all，wake_up_interruptible，wake_up_interruptible_nr，wake_up_interruptible_all，wake_up_interruptible_sync和wake_up_locked。从每个宏的名字我们可以明白其功能：
        * 所有宏都考虑到处于TASK_INTERRUPTIBLE状态的睡眠进程；如果宏的名字中不含字符串“interruptible”，那么处于TASK_UNINTERRUPTIBLE状态的睡眠进程也被考虑到。
        * 所有宏都唤醒具有请求状态的所有非互斥进程。
        * 名字中含有“nr”字符串的宏唤醒给定数的具有请求状态的互斥进程；这个数字是宏的一个参数。名字中含有“all”字符串的宏唤醒具有请求状态的所有互斥进程。最后，名字中不含“nr”或“all”字符串的宏只唤醒具有请求状态的一个互斥进程。
        * 名字中不含有“sync”字符串的宏检查被唤醒进程的优先级是否高于系统中正在运行进程的优先级，并在必要时调用schedule()。这些检查并不是由名字中含有“sync”字符串的宏进行的，造成的结果是高优先级进程的执行稍有延迟。
        * wake_up_locked宏和wake_up宏相类似，仅有的不同是当wait_queue_head_t中的自旋锁已经被持有时要调用wake_up_locked。
        因为所有的非互斥进程总是在双向链表的开始位置，而所有的互斥进程在双向链表的尾部，所以函数总是先唤醒非互斥进程然后再唤醒互斥进程。
2.5、进程资源限制
        
三、进程切换
        为了控制进程的执行，内核必须有能力挂起正在CPU上运行的进程，并恢复以前挂起的某个进程的执行。这种行为被称为进程切换(process switch)、任务切换(task switch)或上下文切换(context switch)。
3.1、硬件上下文
        进程恢复执行前必须装入寄存器的一组数据称为硬件上下文(hardware context)。硬件上下文是进程可执行上下文的一个子集，因为可执行上下文包含进程执行时需要的所有信息。在Linux中，进程硬件上下文的一部分存放在TSS段，而剩余部分存放在内核态的堆栈中。
        进程切换只发生在内核态。在执行进程切换之前，用户态进程使用的所有寄存器内容都已保存在内核态堆栈上，这也包括ss和esp这对寄存器的内容(存储用户态堆栈指针的地址)。
3.2、任务状态段

3.2.1、thread字段
        在每次进程切换时，被替换进程的硬件上下文必须保存在别处。不能像Intel原始设计那样把它保存在TSS中，因为Linux为每个处理器而不是为每个进程使用TSS。
        因此，每个进程描述符包含一个类型为thread_struct的thread字段，只要进程被切换出去，内核就把其硬件上下文保存在这个结构中。这个数据结构包含的字段涉及大部分CPU寄存器，但不包括诸如eax、ebx等等这些通用寄存器，它们的值保留在内核堆栈中。
3.3、执行进程切换
        进程切换可能只发生在精心定义的点：schedule()函数。
        从本质上说，每个进程切换由两步组成：
        1、切换页全局目录以安装一个新的地址空间；
        2、切换内核态堆栈和硬件上下文，因为硬件上下文提供了内核执行新进程所需要的所有信息，包含CPU寄存器。
        我们又一次假定prev指向被替换进程的描述符，而next指向被激活进程的描述符。prev和next是schedule()函数的局部变量。
3.3.1、switch_to宏
        进程切换的第二步由switch_to宏执行。它是内核中与硬件关系最密切的例程之一。
        首先，该宏有三个参数，它们是prev，next和last。prev和next仅是局部变量prev和next的占位符，即它们是输入参数，分别表示被替换进程和新进程描述符的地址在内存中的位置。
        那第三个参数last呢？在任何进程切换中，涉及到三个进程而不是两个。假设内核决定暂停进程A而激活进程B。在schedule()函数中，prev指向A的描述符而next指向B的描述符。switch_to宏一旦使A暂停，A的执行流就冻结。
        随后，当内核想再次激活A，就必须暂停另一个进程C(这通常不同于B)，于是就要用prev指向C而next指向A来执行另一个switch_to宏。当A恢复它的执行流时，就会找到它原来的内核栈，于是prev局部变量还是指向A的描述符而next指向B的描述符。此时，代表进程A执行的内核就失去了对C的任何作用。但是，事实表明这个引用对于完成进程切换是很有用的。
        switch_to宏的最后一个参数是输出参数，它表示宏把进程C的描述符地址写在内存的什么位置了(当然，这是在A恢复执行之后完成的)。在进程切换之前，宏把第一个输入参数prev(即在A的内核堆栈中分配的prev局部变量)表示的变量的内容存入CPU的eax寄存器。在完成进程切换，A已经恢复执行时，宏把CPU的eax寄存器的内容写入由第三个输出参数----last所指示的A在内存中的位置。因为CPU寄存器不会在切换点发生变化，所以C的描述符地址也存在内存的这个位置。在schdeule()执行过程中，参数last指向A的局部变量prev，所以prev被C的地址覆盖。
3.3.2、__switch_to()函数
        
3.4、保存和加载FPU、MMX及XMM寄存器

3.4.1、保存FPU寄存器

3.4.2、装载FPU寄存器

3.4.3、在内核态使用FPU、MMX和SSE/SSE2单元

四、创建进程
        传统的Unix操作系统以统一的方式对待所有的进程：子进程复制父进程所拥有的资源。这种方法使进程的创建非常慢且效率低，因为子进程需要拷贝父进程的整个地址空间。实际上，子进程几乎不必读或修改父进程拥有的所有资源，在很多情况下，子进程立即调用execve()，并清除父进程仔细拷贝过来的地址空间。
        现代Unix内核通过引入三种不同的机制解决了这个问题：
        * 写时复制技术允许父子进程读相同的物理页。只要两者中有一个试图写一个物理页，内核就把这个页的内容拷贝到一个新的物理页，并把这个新的物理页分配给正在写的进程。
        * 轻量级进程允许父子进程共享每进程在内核的很多数据结构，如页表(也就是整个用户态地址空间)、打开文件及信号处理。
        * vfork()系统调用创建的进程能共享其父进程的内存地址空间。为了防止父进程重写子进程需要的数据，阻塞父进程的执行，一直到子进程退出或执行一个新的程序为止。
4.1、clone()、fork()及vfork()系统调用       
        在Linux中，轻量级进程是由名为clone()的函数创建的。这个函数使用下列参数：
        fn：
        指定一个由新进程执行的函数。当这个函数返回时，子进程终止。函数返回一个整数，表示子进程的退出代码。
        arg：
        指向传递给fn()函数的数据。
        flags：
        各种各样的信息。低字节指定子进程结束时发送到父进程的信号代码，通常选择SIGCHLD信号。剩余的3个字节给一clone标志组用于编码。
        child_stack：
        表示把用户态堆栈指针赋给子进程的esp寄存器。调用进程(指调用clone()的父进程)应该总是为子进程分配新的堆栈。
        tls：
        表示线性局部存储段(TLS)数据结构的地址，该结构是为新轻量级进程定义的。只有在CLONE_SETTLS标志被设置时才有意义。
        ptid：
        表示父进程的用户态变量地址，该父进程具有与新轻量级进程相同的PID。只有在CLONE_PARENT_SETTID标志被设置时才有意义。
        ctid：
        表示新轻量级进程的用户态变量地址，该进程具有这一类进程的PID。只有在CLONE_CHILD_SETTID标志被设置时才有意义。
4.1.1、do_fork()函数
        do_fork()函数负责处理clone()、fork()和vfork()系统调用。
4.1.2、copy_process()函数
        copy_process()创建进程描述符以及子进程执行所需要的所有其他数据结构。它的参数与do_fork()的参数相同，外加子进程的PID。

4.2、内核线程
        在Linux中，内核线程在以下几方面不同于普通进程：
        1、内核线程只运行在内核态，而普通进程即可以运行在内核态，也可以运行在用户态。
        2、因为内核线程只运行在内核态，它们只使用大于PAGE_OFFSET的线性地址空间。另一方面，不管在用户态还是内核态，普通进程可以用4GB的线性地址空间。
4.2.1、创建一个内核线程
        kernel_thread()函数创建一个新的内核线程。它接受的参数有：所要执行的内核函数得地址(fn)、要传递给函数的参数(arg)、一组clone标志(flags)。
4.2.2、进程0
        所有进程的祖先叫做进程0，idle进程或因为历史原因叫做swapper进程，它是在Linux的初始化阶段从无到有创建的一个内核线程。
4.2.3、进程1
        由进程0创建的内核线程执行init()函数，init()依次完成内核初始化。init()调用execve()系统调用装入可执行程序init。结果，init内核线程变为一个普通进程，且拥有自己的每进程(per-process)内核数据结构。在系统关闭之前，init进程一直存活，因为它创建和监控在操作系统外层执行的所有进程的活动。
4.2.4、其他内核线程
        Linux使用很多其他内核线程。其中一些在初始化阶段创建，一直运行到系统关闭；而其他一些在内存必须执行一个任务时“按需”创建，这种任务在内核的执行上下文中得到很好的执行。
        一些内核线程的例子(除了进程0和进程1)是：
        keventd(也被称为事件)：执行keventd_wq工作队列中的函数。
        kapmd：处理与高级电源管理(APM)相关的事件。
        kswapd：执行内存回收。
        pdflush：刷新“脏”缓冲区中的内容到磁盘以回收内存。
        kblockd：执行kblockd_workqueue工作队列中的函数。实质上，它周期性地激活块设备驱动程序。
        ksoftirqd：运行tasklet；系统中每个CPU都有这样一个内核线程。
五、撤销进程
        很多进程终止了它们本该执行的代码，从这种意义上说，这些进程“死”了。当这种情况发生时，必须通知内核以便内核释放进程所拥有的资源，包括内存、打开文件及其他我们在本书中讲到的零碎东西，如信号量。
        进程终止的一般方式是调用exit()库函数，该函数释放C函数库所分配的资源，执行编程者所注册的每个函数，并结束从系统回收金车概念的那个系统调用。exit()函数可能由编程者显示地插入。另外，C编译程序总是把exit()函数插入到main()函数的最后一条语句之后。
        内核可以有选择地强迫整个线程组死掉。这发生在以下两种典型情况下：当进程接收到一个不能处理或忽视的信号时，或者当内核正在代表进程运行时在内核态产生一个不可恢复的CPU异常时。
5.1、进程终止
        在Linux2.6中有两个终止用户态应用的系统调用：
        * exit_group()系统调用，它终止整个线程组，即整个基于多线程的应用。do_group_exit()是实现这个系统调用的主要内核函数。这是C库函数exit()应该调用的系统调用。
        * exit()系统调用，它终止某一个线程，而不管该线程所属线程组中的所有其他进程。do_exit()是实现这个系统调用的主要内核函数。这是被诸如pthread_exit()的Linux线程库的函数所调用的系统调用。
5.1.1、do_group_exit()函数
        do_group_exit()函数杀死属于current线程组的所有进程。它接受进程终止代号作为参数，进程终止代号可能是系统调用exit_group()(正常结束)指定的一个值，也可能是内核提供的一个错误代号(异常结束)。
5.1.2、do_exit()函数
        所有进程的终止都是由do_exit()函数来处理的，这个函数从内核数据结构中删除对终止进程的大部分引用。
5.2、进程删除
        release_task()函数从僵死进程的描述符中分离出最后的数据结构；对僵死进程的处理有两种可能的方式：如果父进程不需要接收来自子进程的信号，就调用do_exit()；如果已经给父进程发送了一个信号，就调用wait4()或waitpid()系统调用。在后一种情况下，函数还将回收进程描述符所占用的内存空间，而在前一种情况下，内存的回收将由进程调度程序来完成。