深入理解Linux内核(3)---进程

1.进程、轻量级进程和线程

进程：是程序执行时的一个实例，可以看作充分描述程序已经执行到何种程度的数据结构的汇集。从内核观点看，进程的目的就是担当分配系统资源(CPU时间、内存等)的实体。

当一个进程创建时，它获得一个父进程地址空间的副本。共享正文段(代码段)，但并不执行一个父进程数据段、栈和堆的完全拷贝，而是采用写时复制技术。

Linux使用轻量级进程对多线程应用程序提供更好的支持，两个轻量级进程基本上可以共享一些资源，诸如地址空间、打开的文件等

2.进程描述符(process descriptor)

为了管理进程，内核必须对每个进程所做的事已经处于的状态进行清楚的描述。进程描述符是task_struct类型结构，它的字段包含了与一个进程相关的所有信息。它不仅包含了很多进程属性的字段，还包含了指向其他数据结构的指针。

(1)进程状态

Task_struct的state字段描述了进程当前所处的状态，Linux中这些标志是互斥的。

①运行状态(TASK_RUNNING)

进程要么正在执行，要么准备执行

②可中断的等待状态(TASK_INTERRUPTIBLE)

进程被挂起(睡眠)，知道某个条件为真，产生一个硬件中断，释放进程正等待的系统资源，或传递一个信号都是可以唤醒进程的条件(把进程状态改为TASK_RUNNING)

③不可中断的等待状态(TASK_UNINTERRUPTIBLE)

与TASK_INTERRUPTIBLE类似，但有一个例外，把信号传递到睡眠进程不能改变它的状态。

④暂停状态 (TASK_STOPPED)

进程的执行被暂停，当进程接收到SIGSTOP,SIGTSTP,SIGTTIN或SIGTTOU信号后，进入暂停状态

⑤跟踪状态(TASK_TRACED)

进程的执行被debugger程序暂停，当一个程序被另一个进程监控时(例如debugger执行ptrace()系统调用监控一个测试程序)，任何信号都可以把这个进程至于TASK_TRACED状态

⑥僵死状态(EXIT_ZOMBIE)            

进程的执行被终止，但是，父进程还没有发布wait4()或waitped()系统调用来返回有关死亡进程的信息。

在发布wait()类系统调用前，内核不能丢弃包含死亡进程描述符的数据，因为父进程可能还需要用它

⑦僵死撤销状态( EXIT_DEAD) 

最终状态：由于父进程发出wait4()或waitped(),进程由系统删除。

内核常用一个简单的赋值语句设置state字段

p->state = TASK_RUNNING;

内核也使用set_task_state和set_current_state宏来设置指定进程状态和当前进程状态。此外，这些宏确保编译程序或CPU控制单元不把赋值操作与其他指令混合。

 

(2)标识一个进程

一般来讲，能被独立调度的每个执行上下文都必须拥有自己的进程描述符。

由于进程和进程描述符有严格的一一对应关系，那么使用32位的进程描述符的地址来标识进程成为一种方便的方式，事实上Linux内核中，进程描述符指针指向这些地址，对进程的大部分引用是通过进程描述符指针进行的。

另一方面，类Unix系统允许用户用进程标志符(precess ID,PID)来标志进程，PID存放在进程描述符的pid字段中.PID顺序编号，新建进程的PID通常是前一个进程的PID加1。不过当内核使用的PID达到上限值时就必须开始循环使用已闲置的小PID号。

缺省情况下，最大PID号是32767(PID_MAX_DEFAULT-1),系统管理员可以对/proc/sys/kernel/pid_max写值来减小PID上限值。64位系统中PID上限可以扩大到4194303

内核管理一个pidmap-array位图来表示当前已分配的PID号和闲置的PID号。32位体系结构中pidmap-array位图存放在一个单独的页中。Linux把不同的PID与系统中每个进程或轻量级进程相关联。

另一方面，POSIX标准规定了一个多线程应用程序中的所有线程都必须有相同的PID.遵循这个标志，Linux引入线程组。一个线程组中的所有线程使用和该线程组的领头线程(thread group leader)相同的PID，也就是该组中第一个轻量级进程的PID，它被存在进程描述符的tgid字段中，getpid()返回当前进程的tgid值而不是pid值。因此一个多线程应用的所有线程共享相同的PID，线程组老大的tgid值与pid值相同。

(3)进程描述符处理

对每个进程来说，Linux都把两个不同的数据结构紧凑地存放在一个单独为进程分配的存储区域内，一个是内核态的进程堆栈，另一个是线程描述符(thread_info),这块通常是8K

Esp寄存器是CPU栈指针，用来存放栈顶单元的地址。一旦数据写入堆栈，esp值就递减，因为thread_info结构体是52个字节，所以啮合栈能扩展到8140字节。

内核用这个联合结构方便的表示一个进程的线程描述符和内核栈。

union thread_union {

       struct thread_info thread_info;

       unsigned long stack[THREAD_SIZE/sizeof(long)];

};

内核用alloc_thread_info和free_thread_info宏分配和释放存储thread_info结构和内核栈的内存区。

 

(4)标志当前进程

Thread_info结构与内核态堆栈之间的紧密结合提供的好处是：内核很容易从esp寄存器的值获得当前在CPU上运行的进程的thread_info结构地址，如thread_union长8K，则屏蔽掉esp的低13位有效位，就得到thread_info的机地址，这个工作由current_thread_info()来完成。

进程最常用的是进程描述符地址，而不是thread_info结构的地址，为了获得当前运行进程的描述符指针，内核调用current宏，该宏本质上等价于current_thread_info()->task；current->pid返回在CPU上正执行的进程的PID。

用栈存放进程描述符的另一个优点是在多处理器系统上，对于每个硬件处理器，仅通过检查栈就可以获得当前正确的进程。有必要定义一个current数组，每个元素对应一个可用CPU.

(5)双向链表

Linux定义了list_head数据结构，LIST_HEAD(list_name)宏创建一个名字为list_name的双向链表，还初始化list_head数据机构的prev和next字段，让它们指向变量本身。需注意的是，list_head字段的指针中存放的是list_head字段的地址，而不是包含有list_head结构的整个结构地址。

双向链表详细分析见http://blog.chinaunix.net/uid-24708340-id-3235017.html

Linux2.6支持另一种双向链表，不是循环链表，主要用于散列表，对散列表而言重要的是空间而不是在固定时间内好到表中的最后一个元素。表头存放在hlist_head结构中。第一个元素的pprev字段和最后一个元素的next均为NULL.

①进程链表

进程链表把所有进程的描述符链接起来，每个task_struct都包含一个list_head类型的tasks字段。

表头是init_task描述符，即0进程的进程描述符。Init_task的tasks.prev字段指向链表中最后插入的进程描述符的tasks字段。SET_LINKS和REMOVE_LINKS宏分别用来从进程链表插入删除一个进程描述符。

#define for_each_process(p) \

       for (p = &init_task ; (p = next_task(p)) != &init_task ; )

这个宏用来遍历进程链表。每一次循环p存放的是被扫描进程描述符的地址，与list_entry宏返回值一样。

②TASK_RUNNING状态的进程链表

Linux2.6实现的运行队列与早期不同，其目的是让调度程序能在固定的时间内选出“最佳”可运行进程，与队列中可运行的进程数无关，是一个典型的用数据结构更复杂来改善性能的例子。

提高调度程序运行速度诀窍是，建立多个可运行进程链表，每种进程优先权对应一个不同的链表，每个task_struct描述符包含一个list_head类型的字段run_list.如果进程的优先权等于K(0~139)，run_list字段吧该进程连入优先权为K的可运行进程链表中。在多处理器系统中，每个CPU都有它自己的运行队列，即自己的进程链表集。这样调度程序运行效率高了，但运行队列的链表被拆分成了140个不同的队列。所有这些链表都有一个单独的prio_array_t数据结构来实现。

struct prio_array {

       DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */

       struct list_head queue[MAX_RT_PRIO];

};

enqueue_task(struct rq *rq, struct task_struct *p, int wakeup, u64 now)函数把进程描述符插入某个运行队列的链表, dequeue_task(struct rq *rq, struct task_struct *p, int sleep, u64 now)从运行的队列中删除一个进程描述符。

(6)进程间的关系

①程序创建的进程具有父子关系，如果一个进程创建多个进程，则子进程之间有兄弟关系。

②有的情况下，内核必须能从进程PID导出对应的进程描述符，比如当进程P1希望向进程P2发生一个信号时，P1调用kill()，其参数是P2的PID，内核从这个PID到处其对应的进程描述符，然后从P2的进程描述符中取出记录挂起信号的数据结构指针。

顺序扫描进程描述符表并检查进程描述符的id字段是可行但相对低效的，为了加速查找，引入了4个散列表

内核初始化期间动态地为4个散列表分配空间，并把它们的地址存入pid_hash数组。

散列表的详细分析见：http://blog.chinaunix.net/uid-24708340-id-3307281.html

Linux利用链表来处理冲突的PID：每个表项石油冲突的进程描述符组成的双向链表，如下图，进程号为2892和29384的两个进程散列好这个表的第200个元素，进程29385的进程散列到这个表的第1466个元素。

具有链表的散列法比从PID到表索引的线性转换更优越，因为实际应用中系统的进程数远小于32768，如果任何表项定义为32768项都是一个存储浪费。

PID散列表的数据机构还为每组线程组(pid相同)保留一个进程链表。

并且内核为每个PID定义一个进程链表，最主要的数据结构是四个pid结构的数组，它在进程描述符pid字段中

struct pid
{
      int nr; //pid的数值
       struct hlist_node pid_chain;//链接散列链表的下一个和前一个元素

       struct list_head pid_list;//每个pid的进程链表头
};

下面是处理PID散列表的函数和宏：

do_each_task_pid(nr,type,task)

while_each_task_pid(nr,type,task)

循环作用在PID值等于nr的类型为type的链表中，task指向当前被扫描的元素的进程描述符表。

find_task_by_pid_type(type,nr)

find_task_by_pid(nr)==find_task_by_pid_type(PIDTYPE_PID,nr)

attach_pid(task,type,nr)

detach_pid(task,type)

next_thread(task)

(7)如何组织进程

①运行队列链表吧处于TASK_RUNNING状态的所有进程组织在一起，其他状态进程分组时，Linux选择下列方式之一：

没有为处于TASK_STOPPED,EXIT_ZOMBIE或EXIT_EAD状态的进程建立专门链表，韵味这几种状态进程的访问比较简单，或者通过PID,或者通过特定父进程的子进程链表，所以不必要对这三种状态分组。

处于TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE状态的进程细分为很多类，每一类都响应一个特殊事件，这个过程中进程没有迅速取回足够的信息。所以有必要介绍另外的进程链表。

②等待队列：

等待队列在内核中主要用在中断处理、进程同步及定时，表示进程等待某些事件的发生。等待队列表示一组睡眠的进程，当某一条件为真时，由内核唤醒它们。

等待队列由双向链表实现，其元素包含指向进程描述符的指针，每个等待队列都有一个等待队列头。

struct __wait_queue_head {

       spinlock_t lock;

       struct list_head task_list;

};

typedef struct __wait_queue_head wait_queue_head_t;同步是通过等待队列头中的lock自旋锁达到的，task_list字段是等待进程链表的头。

等待队列链表中的元素是

struct __wait_queue {

       unsigned int flags;

#define WQ_FLAG_EXCLUSIVE       0x01

       void *private;

       wait_queue_func_t func;

       struct list_head task_list;

};

typedef struct __wait_queue wait_queue_t;

等待队列链表中的每个元素代表一个睡眠进程。有两种睡眠进程：互斥进程由内核有选择地唤醒，非互斥进程总是有内核在事件发生时唤醒。

③等待队列操作

DECLARE_WAIT_QUEUE_HEAD(name)静态初始化，

init_waitqueue_head()动态初始化。一旦定义了一个元素，必须把它插入等待队列，add_wait_queue()函数把一个非互斥进程插入等待队列链表的第一个位置。add_wait_queue_exclusive()把一个互斥进程插入等待队列的最后一个位置。

remove_wait_queue()从等待队列链表中删除一个进程

wait_queue_active()函数检查一个给定的等待队列是否为空。

等待队列的详细应用参看：http://blog.chinaunix.net/uid-24708340-id-3070724.html

(8)进程资源限制

每个进程都有一组资源限制(resource limit),限制制定了进程能使用的系统资源数量。其中一些可以用getrlimit和setrlimit函数查询和更改。

进程的资源限制通常是在系统初始化时由进程0建立的，然后由每个后续进程继承。

对当前进程的资源限制存放在current->signal-rlim字段，即进程描述符的一个字段

struct rlimit {

       unsigned long rlim_cur; //soft limit:current limix

       unsigned long rlim_max;//hard limit:maximum value for rlimi_cur

};

更改资源时遵循三个原则

①任一个进程都可将一个软限制值更改为小于或等于其硬限制值

②任何一个进程可降低其硬限制值，但它必须大于或等于其软限制值，这种降低对于普通用户不可逆

③只有超级用户进程可以提高硬限制值

常量RLIM_INFINITY制定了一个无限量的限制

RLIMIT_AS:进程可用存储区的最大长度(byte)，这会影响sbrk,mmap。

RLIMIT_CORE：core文件的最大字节数，其值为0则阻止创建core

RLIMIT_CPU：CPU时间的最大量值(秒)，当超过该值时，向该进程发送SIGXCPU信号，如果进程还不终止，再发一个SIGKILL信号。

RLIMIT_DATA：对大小的最大值(字节)。

RLIMIT_FSIZE：文件大小的最大值(字节)，当超过该值时，内核给该进程发SIGXFSZ信号

RLIMIT_LOCKS：一个进程可以拥有的锁的最大数。

RLIMIT_MSGQUEUE：消息队列中的最大字节数。

RLIMIT_NOFILE：每个进程的最大文件数。

RLIMIT_SIGPENDING：进程挂起信号的最大数。

RLIMIT_STACK：栈大小的最大值。

 

3.进程切换

为了控制进程的执行，内核必须有能力挂起正在CPU上运行的进程，并恢复以前挂起的某个进程的执行，这种行为称为进程切换(process switch)、任务切换(task switch)或上下文切换(context switch).

(1) 硬件上下文

进程恢复执行前必须装入寄存器的一组数据，称为硬件上下文(hardware context),硬件上下文是进程可执行上下文的一个子集，因为可执行上下文包含进程执行时需要的所有信息，在Linux中，进程硬件上下文的一部分存放在TSS段，剩余部分存放在内核态堆栈中。

(2) 任务状态段(Task State Segment,TSS)

用来存放硬件上下文，尽管Linux并不适用硬件上下文切换，但是强制它为系统中每个不同的CPU创建一个TSS，这样做是因为

①当80x86的一个CPU从用户态切换到内核态时，它从TSS中获取内核态堆栈的地址。

②当用户态进程试图通过in或out指令访问一个I/O端口时，CPU需要访问存放在TSS中的I/O许可权位图(Permission Bitmap)以检查该进程是否有访问端口的权利。

 tss_struct结构描述TSS的格式，每个TSS有它自己8字节的任务状态段描述符(Task State Segment Descriptor,TSSD).在intel的原始设计中，系统中的每个进程都应当指向自己的TSS,但在Linux设计中，每个CPU只有一个TSS。

(3)thread字段

每次进程切换时，被替换进程的硬件上下文不能像Intel原始设计那样保存在TSS中，因此每个进程描述符包含一个类型为thread_struct的thread字段，只要进程被切换出去，内核就把硬件上下文保存在这个结构中。这个数据结构包含的字段涉及大部分CPU寄存器，但不包括诸如eax,ebx等等这些通用寄存器，它们的值保留在内核堆栈中。

(4)执行进程切换

进程切换可能只发生在精心定义的点:schedule()函数，从本质上说，每个进程切换由两部组成：

①切换页全局目录以安装一个新的地址空间

②切换内核态堆栈和硬件上下文，因为硬件上下文提供了内核执行新进程所需要的所有信息，包括CPU寄存器。

进程切换的第二步由switch_to宏执行，它是内核中与硬件关系最密切的历程之一。带三个参数，分别是prev,next和last。Prev,next是局部变量的占位符。last是输出参数,它表示宏把进程C的描述符地址写在内存的什么位置。

4.创建进程

现代Unix内核通过引入三种不同的机制来解决子进程复制父进程所拥有资源的效率问题。

①写时复制技术允许父子进程都相同的物理页。只要两这种有一个试图写一个物理页，内核就把这个页的内容拷贝到一个新的物理页，并把这个新的物理页分配给正在写的进程。

②轻量级进程允许父子进程共享每进程在内核的很多数据结构，如页表(整个用户态的地址空间)、打开文件表及信号处理。

③vfork()系统调用创建的进程能共享其父进程的内存地址空间，为了防止父进程重写子进程需要的数据，阻塞父进程的执行，一直到子进程退出或执行一个新的程序为止。

(1) clone()、fork()及vfork()系统调用

Linux中，轻量级进程是由名为clone()的函数创建，这个函数使用下列参数：

fn:指定一个由新进程执行的函数，当这个函数返回时，子进程终止，函数返回一个整数，表示子进程的退出代码。

arg:指向传递给fn()的参数

flags：各种各样信息，低字节指定子进程结束时发送到父进程的信号代码，一般是SIGCHLD信号，剩余三个字节给一clone标志组用于编码

child_stack:表示把用户态堆栈指针赋给子进程的esp寄存器，调用进程(调用clone()的父进程)应该总是为子进程分配新的堆栈

tls:线程局部存储段(TLS)数据结构的地址，该结构是为新轻量级进程定义的。只有CLONE_SETTLS被设置时才有意义。

ptid:父进程的用户态变量地址，该父进程具有与新轻量级进程相同的PID。

ctid:新轻量级进程的用户态变量地址，该进程具有这一类进程的PID。

clone标志

CLONE_VM:共享内存描述符和所有的页表

CLONE_FILES：共享打开文件表

…

实际上，clone()是C库中定义的一个封装函数，它负责建立新轻量级进程的堆栈并且调用对编程者隐藏的clone()系统调用，实现clone()系统调用的sys_clone()服务例程没有fn和arg.

asmlinkage int sys_clone(unsigned long clone_flags, unsigned long newsp,

                      int __user *parent_tidptr, int tls_val,

                      int __user *child_tidptr, struct pt_regs *regs)

{
       if (!newsp)

              newsp = regs->ARM_sp;

       return do_fork(clone_flags, newsp, regs, 0, parent_tidptr, child_tidptr);
}

实际上，封装函数把fn指针存放在该函数本身返回地址存放的位置，arg指针正好存放在子进程堆栈中fn的下面，当封装函数结束时，CPU从堆栈中取出返回地址，然后执行fn(arg)

传统的fork()系统调用在Linux中是用clone()实现的，其中clone()的flags参数指定为SIGCHLD信号已经所有请0的clone标志，而它的child_stack参数是父进程当前的堆栈指针，因此父子进程暂时共享一个用户态堆栈，但是写时复制，立即各自得到用户态堆栈的拷贝。

vfork()也是用clone()实现的，其中clone()参数flags指定为SIGCHLD信号和CLONE_VM及CLONE_VFORK标志，clone()的参数child_stack等于父进程当前的栈指针。

(2) do_fork()函数

clone(),fork()和vfork()系统调用都是通过do_fork()函数实现的。

do_fork()利用辅助函数copy_precess()来创建进程描述符以及子进程执行所需要的所有其他内核数据结构，do_fork()主要执行步骤：

①查找pidmap_array位图，为子进程分配新的PID

②检查父进程的ptrace字段(current->ptrace)，确定父进程是否想跟中子进程

③调用copy_precess()复制进程描述符，如果所有必须的资源都是可用的，该函数返回刚创建的task_struct描述符的地址，这好似创建过程的关键步骤。

④如果设置了CLONE_STOPPED标志，或者必须跟踪子进程，即在P->ptrace中设置PT_PTRACED标志。

⑤如果没有设置CLONE_STOPPED标志，则调用wake_up_new_task()函数

⑥如果CLONE_STOPPED被设置，则把子进程职位TASK_STOPPED状态。

⑦如果父进程被跟踪，则把子进程的PID存入current的ptrace_message字段并调用ptrace_notify().

⑧如果设置了CLONE_VFORK标志，则把父进程插入等待队列，并挂起父进程知道子进程释放自己的内存地址空间。

⑨结束并返回子进程的PID。

(3)copy_process()函数

copy_process()创建进程描述符以及子进程执行所需要的所有其他数据结构。

(4)内核线程(kernel thread)

内核线程不受不必要的用户态上下文拖累，只运行在内核态，只适用大于PAGE_OFFSET的线性空间。

kernel_thread()函数创建一个新的内核线程，接受的参数有：内核函数地址(fn),fn的参数(arg),一组clone标志(flags),该函数本质上是调用do_fork().

do_fork(flags|CLONE_VM|CLONE_UNTRACED, 0, pregs, 0, NULL, NULL);

CLONE_VM标志避免复制调用进程的页表(内核线程不会访问用户态地址空间)

CLONE_UNTRACED标志保证不会有任何进程跟踪新内核线程，即使调用进程被跟踪。

pregs表示内核栈的地址。

新的内核线程开始执行fn(arg)函数，如果该函数结束，内核线程执行系统调用_exit()，并把fn()的返回值传递给它。

(5)进程0

Idle进程是所有进程的祖先，也叫swapper进程，是在Linux初始化阶段创建的一个内核线程。

start_kernel()函数初始化内核需要的所有数据结构，激活中断，创建另一个进程1的内核线程，init进程

kernel_thread(init, NULL, CLONE_FS|CLONE_SIGHAND);

内核线程1进程与进程0共享每进程所有的内核数据结构。

创建init进程后，进程0执行cpu_idle()函数，该函数本质上是在开中断的情况下重复执行hlt汇编指令，只有当没有其他进程处于TASK_RUNNING状态时，调度程序才选择进程0.在多处理器系统中，每个CPU都有一个进程0

 (6)进程1

由idle进程创建的内核线程执行init()函数，init()依次完成内核初始化，并执行可执行程序init，结果init内核线程变为一个普通进程且拥有自己的每进程内核数据结构，在系统关闭前，init进程一直存活，因为它创建和监控在操作系统外层执行的所有进程的活动。

(7)其他的一些内核线程，一些是在初始化阶段创建，一些在内核必须执行一个任务时按需创建，这种任务在内核的执行上下文中得到很好的执行。

Keventd：执行keventd_wq工作队列

Kapmd:处理与高级电源管理(APM)相关的时间

Pdflush:刷新“脏”缓冲区的内容到磁盘以回收内存

Kblockd:执行kblockd_workqueue工作队列中的函数，实质上周期性地激活块设备驱动程序。

Ksoftirqd：运行tasklet，系统中每个CPU都有一个这样的线程。

 

5.撤销进程

进程终止了它们本该执行的代码，即进程“死”了时，必须通知内核释放进程所拥有的资源，包括内存、打开文件及信号量等。

(1) 进程终止

进程终止一般方式是调用exit()库函数，该函数释放C函数库所分配的资源，exit()可能由编程者显示的插入，C编译器总是把exit()函数插入到main()函数的最后一条语句之后。

exit_group()系统调用，终止整个线程组,由do_group_exit()实现。

exit()终止某一个进程，由内核函数do_exit()实现。Pthread_exit()线程库的系统调用

(2) do_group_exit()函数

杀死current线程组的所有进程，接受进程的终止代号作为参数exit_group()指定的一个值。也可能是内核提供的错误代号(异常结束)

(3)do_exit()函数

所有进程的终止都是由do_exit()函数来处理，这个函数从内核数据结构中删除对终止进程的大部分引用。

(4)进程删除

Unix内核不允许进程一终止就丢弃包含在进程描述符字段中的数据，只有父进程发出了与被终止进程相关的wait()类系统调用后，才允许这样。

若父进程在子进程结束前就挂了，或者子进程死掉时父进程没有等待(即没有wait()函数调用)，子进程就成为僵死进程，僵死进程将成为init的子进程，init进程用wait()类系统调用检查其合法的子进程终止时，就会撤销僵死的进程。