深入理解Linux内核--进程（阅读笔记）（原创）
深入理解Linux内核--进程（阅读笔记）（原创）
由 王宇 原创并发布：
第三章进程
进程是任何多道程序设计的操作系统中的基本概念。通常把进程定义为程序执行的一个实例
1、进程、轻量级进程和线程
进程的目的就是担当分配系统资源
2、进程描述符（静态特性）
（1）进程描述符
为了管理进程，内核必须对每个进程所做的事情进行清楚的描述。例如，内核必须知道进程的优先级，它是正在CPU上运行还是某些事件而被阻塞，给它分配了什么样的地址空间，允许它访问那些文件等等。这就是进程描述符(processdescriptor)的作用，--进程描述符都是task_struct类型结构
（2）进程状态
可运行状态(TASK_RUNNING)
暂停状态(TASK_STOPPED)
可中断的等待状态(TASK_INTERRUPTTIBLE)
不可中断的等待状态(TASK_UNINTERRUPTTIBLE)
僵死状态(EXIT_ZOMBIE)
僵死撤销状态(EXIT_DEAD)
跟踪状态(TASK_TRACED)
（3）标识一个进程：进程标识符processID
（4）进程描述符处理
进程描述符存放在动态内存中，而不是放在永久分配给内核的内存区
把线程描述符(thread_info)和进程堆栈紧凑地存放在一个单独为进程分配的存储区域内。（？？？）
（5）标识当前进程
（6）双向链表
linux内核定义了list_head数据结构
数据结构的处理函数和宏
list_add(n,p);
list_add_tail(n,p);
list_del(p);
list_empty(p);
list_entry(p,t,m);
list_for_each(p,n);
list_for_each_entry(p,h,m);
（7）进程链表:每个task_struct结构都包含一个list_head类型的tasks字段
（8）TASK_RUNNING状态的进程链表
提高调度程序运行速度的诀窍是建立多个可运行进程链表，每种进程优先权对应一个不同的链表
prio_array_t数据结构
enqueue_task(p,array)函数把进程描述符插入某个运行队列的链表中
（9）进程间的关系
程序创建的进程具有父子关系，如果一个进程创建多个子进程时，则子进程之间具有兄弟关系。参考表3-3
（10）pidhash表及链表
PID导出对应的进程描述符指针，顺序扫描进程链表并检查进程描述符的pid字段是可行但相当低效，为了加速查找，引入了4个散列表：
PIDTYPE_PID进程ID
PIDTYPE_TGID线程组领头进程的PID
PIDTYPE_PGID进程组领头进程的PID
PIDTYPE_SID会话领头进程的PID
处理PID散列表的函数和宏：参考P100
（11）如何组织进程
运行对链表把处于TASK_RUNNING状态的所有进程组织在一起，没有为处于TASK_STOPPEDEXIT_ZOMBIEEXIT_DEAD状态的进程建立专门的链表
（12）等待队列
等待队列实现了在事件上的条件等待：希望等待特定事件的进程把自己放进合适的等待队列，并放弃控制权。因此等待队列表示一组睡眠的进程，当某一条件变为真时，由内核唤醒它们。
等待队列由双向链表实现，其元素包括指向进程描述符的指针。每个等待队列都有一个等待队列头，等待队列头是一个类型为wait_queue_head_t的数据结构
struct__wait_queue_head{
spinlock_tlock;//同步
structlist_headtask_list;//等待进程链表的头
};
等待队列链表中的元素类型为wait_queue_t
struct__wait_queue{
unsignedintflags;
structtask_struct*task;
wait_queue_funcfunc;
structlist_headtask_list;
};
（13）等待队列的操作
[1]、定义等待队列头：DECLARE_WAIT_QUEUE_HEAD(name)动态分配：init_waitqueue_head()
[2]、初始化wait_queue_t结构：init_waitqueue_entry(q,p);
[3]、将定义的元素，插入、删除、检查等待队列：add_wait_queue();add_wait_queue_exclusive();remove_wait_queue();waitqueue_active();
[4]、调用进程在等待队列上睡眠，一直到修改了给定条件为止。wait_eventwait_event_interruptible
[5]、唤醒：wake_up
（14）进程资源限制
每个进程都有一组相关的资源限制(resourcelimit),限制指定了进程能使用的系统资源数量。这些限制避免用户过分使用系统资源（CPU、磁盘空间等）3、进程切换
挂起、恢复进程的执行，称为进程切换、任务切换、或上下文切换
（1）硬件上下文
所有进程必须共享CPU寄存器，因此在恢复一个进程的执行之前，内核必须确保每个寄存器转入了挂起进程时的值。进程恢复执行前必须装入寄存器的一组数据称为硬件上下文。硬件上下文是进程可执行上下文的一个子集。
（2）任务状态段：linux没有使用80x86提供的段类型
（3）执行进程切换
[1]切换页全局目录以安装一个新的地址空间（第九章描述）
[2]切换内核态堆栈的硬件上下文，因为硬件上下文提供了内核执行新进程所需要的所有信息，包括CPU寄存器
（4）switch_to宏
（5）__switch_to函数
（6）保存和加载FPU、MMX及XMM寄存器
（7）在内核态使用FPU、MMX和SSE/SSE2单元
4、创建进程
写时复制技术：
（1）clone()、fork()、及vfork()系统调用
（2）do_fork()函数：负责处理clone()、fork()、vfork()系统调用
步骤：参见P122
（3）copy_process()函数
步骤：参见P123
（4）内核线程
内核线程不受不必要的用户态上下文的拖累
5、撤销进程
（1）进程终止
（2）do_group_exit()
（3）do_exit()
（4）进程删除第七章进程调度
Linux与任何分时系统一样，通过一个进程到另一个进程的快速切换，达到表面上看来多个进程同时执行的神奇效果
1、调度策略
调度算法必须实现几个互相冲突的目标：进程响应时间尽可能快，后台作业的吞吐量尽可能高，尽可能避免进程的饥饿现象，低优先级和高优先级进程的需要尽可能调和等等
决定什么时候以怎样的方式选择一个新进程运行的这组规则就是所谓的调度策略。
Linux的调度基于分时技术：多个进程以“时间多路复用”方式运行，因为CPU的时间被分成“片”，给每个可运行进程分配一片。当然单处理器在任何给定的时刻只能运行一个进程。如果当前运行进程的时间片或时限到期时，该进程还没有运行完毕，进程切换就可以发生。分时依赖于定时中断，因此对进程是透明的。不需要在程序中插入额外的代码来保证CPU分时
调度策略也是根据进程的优先级对它们进行分类：
传统上把进程分类为“I/O受限”或“CPU受限”
另一种分类：
交互式进程--命令shell文本编辑图形应用
批处理进程--编译程序数据库搜索引擎及科学计算
实时进程--视频、音频应用程序、机器人控制程序
linux没有办法区分交换式程序和批处理程序
（1）进程的抢占
当前进程thread_info结构中的TIF_NEED_RESCHED标志被设置，以便时钟中断处理程序终止时调度程序被调用
注意，被抢占的进程并没有被挂起，因为它还处于TASK_RUNNING状态，只不过不在使用CPU.此外，记住Linux2.6内核是抢占式的，这意味着进程无论是处于内核态还是用户态，都可能被抢占。
（2）一个时间片必须持续多长？
对时间片大小的选择始终是一种折衷。Linux采取单凭经验的方法，即选择尽可能长、同时能保持良好响应时间的一个时间片。
2、调度算法
早期版本：在每次进程切换时，内核扫描可运行进程的链表，计算进程的优先级，然后选择“最佳”进程来运行。缺点：算法的开销太大
调度类型：
SCHED_FIFO:
先进先出的实时进程。当调度程序把CPU分配给进程的时候，它把该进程描述符保留在运行队列链表的当前位置。如果没有其他可运行的更高级优先级实时进程，进程就继续使用CPU，想用多久就用多久，即使还有其他具有相同优先级的实时进程处于可运行状态
SCHED_RR:
时间片轮转的实时进程。当调度程序把CPU分配给进程的时候，它把该进程的描述符放在运行队列链表的未尾。这种策略保证对所有具有相同优先级的SCHED_RR实时进程公平地分配CPU时间
SCHED_NORMAL:
普通的分时进程
（1）普通进程的调度
每个普通进程都有它自己的静态优先级，调度程序使用静态优先级来估价系统中这个进程与其他普通进程之间调度的程度。内核用从100（最高优先级）到139（最低优先级）的数表示普通进程的静态优先级。注意值越大优先级越低
新进程总是继承其父进程的静态优先级，通过把某些“nice值”传递给系统调用，用户可以改变自己拥有的进程的静态优先级
[1]基本时间片
静态优先级本质上决定了进程的基本时间片，即进程用完了以前的时间片时，系统分配给进程的时间片长度。静态优先级和基本时间片的关系公式参考P263
[2]动态优先级和平均睡眠时间
普通进程除了静态优先级，还有动态优先级，其值的范围是100-139.公式参见：P263
[3]活动和过期进程
即使具有较高静态优先级的普通进程获得了较大的CPU时间片，也不应该使静态优先级较低的进程无法运行。为了避免进程饥饿，当一个进程用完它的时间片时，它应该被还没有用完时间片的低优先级的进程取代。为了实现这种机制，调度程序维持两个不相交的可运行进程的集合。
活动进程：这些进程还没有用完它们的时间片，因此允许它们运行。
过期进程：这些进程已经用完了它们的时间片，并因此被禁止运行，直到所有活动进程都过期
[4]实时进程的调度
每个实时进程都与一个实时优先级相关，实时优先级是一个范围从1-99的值
3、调度程序所使用的数据结构
（1）数据结构runqueue:Linux2.6调度程序最重要的数据结构
（2）进程描述符
4、调度程序所使用的函数
scheduler_tick()维持当前最新的time_slice计数器
try_to_wake_up()唤醒睡眠进程
recalc_task_prio()更新进程的动态优先级
schedule()选择要被执行的新进程
load_balance()维持多处理器系统中运行队列的平衡5、多处理器系统中运行队列的平衡
6、与调度相关的系统调用
nice()系统调用
getpriority()系统调用
setpriority()系统调用
与实时进程相关的系统调用：参见p291
第十九章进程通信
1、管道
最适合在进程之间实现生产者/消费者的交互。有些进程向管道中写入数据，而另外一些进程则从管道中读出数据。
管道(pipe)是所有Unix都愿意提供的一种进程间通信机制。管道是进程之间的一个单向数据流：一个进程写入管道的所有数据都由内核定向到另一个进程，另一个进程由此就可以从管道中读取数据。
(1)使用管道
管道被看作是打开的文件，但在已安装的文件系统中没有相应的映像。可以使用pipe()系统调用来创建一个新管道，这个系统调用返回一对文件描述符；然后进程通过fork()把这两个描述符传递给它的子进程，由此与子进程共享管道。进程可以在read()系统调用中使用第一个文件描述符从管道中读取数据，同样也可以在write()系统调用中使用第二个文件描述符向管道中写入数据。
Linux采用了另外一种解决方法：每个管道的文件描述符仍然都是单向的，但是在使用一个描述符之前不必把另外一个描述符关闭。
(2)管道数据结构
pipe_inode_info参考表：19-1
pipe_buffer参考表：19-2
(3)pipefs特殊文件系统
管道是作为一组VFS对象来实现的，因此没有对应的磁盘映像。因为这种文件系统在系统目录树中没有安装点，因此用户根本看不到它。但是，有了pipefs，管道完全被整合到VFS层，内核就可以以命名管道或FIFO的方式处理它们，FIFO是以终端用户认可的文件而存在的
(4)创建和撤销管道（操作：P772）
pipe()系统调用由sys_pipe()函数处理，后者又会调用do_pipe()函数
(5)从管道中读取数据（操作：P775）
希望从管道中读取数据的进程发出一个read()系统调用，为管道的读端指定一个文件描述符。
(6)向管道中写入数据（操作：P777）
希望向管道中写入数据的进程发出一个write()系统调用，为管道的写端指定一个文件描述符
2、FIFO
虽然管道是一种十分简单、灵活、有效的通信机制，但它们有一个主要的缺点，也就是无法打开已经存在的管道。这就是的任意的两个进程不可能共享同一个管道，除非管道由一个共同的祖先进程创建。
Unix系统引入了一种称为命名管道或者【FIFO代表“先进先出”：最先写入文件的字节总是被最先读出】的特殊文件类型。FIFO在这几个方面都非常类似于管道：在文件系统中不拥有磁盘块，，打开的FIFO总是与一个内核缓冲区相关联，这一缓冲区中临时存放两个或多个进程之间交换的数据
然而，有了磁盘索引节点，使的任何进程都可以访问FIFO，因为FIFO文件名包含在系统的目录树中
主要差别：
FIFO索引节点出现在系统目录树上而不是pipefs特殊文件系统中
FIFO是一种双向通信管道;也就是说，可能以读/写模式打开一个FIFO
(1)创建并打开FIFO
进程通过执行mknod()系统调用创建一个FIFO，POSIX引入了一个名为mkfifo()的系统调用专门用来创建FIFO
FIFO一旦被创建，就可以使用普通的open()、read()、write()和close()系统调用访问FIFO，但是VFS对FIFO的处理方法比较特殊，因为FIFO的索引节点及文件操作都是专用的，并且不依赖于FIFO所在的文件系统。
3、SystemVIPC
IPC是进程间通信(InterprocessCommunication)的缩写，通常指允许用户态进程执行下列操作的一组机制：
通过信号量与其他进程进行同步
向其他进程发送消息或者从其他进程接收消息
和其他进程共享一段内存区
IPC数据结构是在进程请求IPC资源（信号量，消息队列或者共享内存区）时动态创建的。每个IPC资源都是持久的：除非被进程显示地释放，否则永远驻留在内存中（直到系统关闭）。IPC资源可以由任一进程使用，包括哪些不共享祖先进程所创建的资源的进程
每个新资源都是使用一个32位的IPC关键字来标识的，这和系统的目录树中的文件路径名类似
(1)使用IPC资源
根据新资源是信号量、消息队列还是共享内存，分别调用semget()、msgget()或者shmget()函数创建IPC资源。
这三个函数的主要目的都是从IPC关键字（作为第一个参数传递）中导出相应的IPC标识符，进程以后就可以使用这个标识符对资源进行访问
数据结构：
ipc_ids
kern_ipc_perm
(2)ipc()系统调用
在8086体系结构中，只有一个名为ipc()的IPC系统调用。
(3)IPC信号量
计数器，用来为多个进程共享的数据结构提供受控访问。
如果受保护的资源是可用的，那么信号量得值就是正数：如果受保护的资源现不可用，那么信号量的值就是0.要访问资源的进程试图把信号量的值减1，但是，内核阻塞这个进程，直到在这个信号量上的操作产生一个正值。当进程释放受保护的资源时，就把信号量的值增加1；在这样处理的过程中，其他所有正在等待这个信号量的进程就都被唤醒。
[1]可取消的信号量操作
如果个进程突然放弃执行，那么它就不能取消已经开始执行的操作（例如，释放自己保留的信号量），因此通过把这些操作定义成可取消，进程就可以让内核把信号量返回到一致状态并允许其他进程继续执行，进程可以在semop()函数中指定SEM_UNDO标志请求可取消的操作
[2]挂起请求的队列
内核给每个IPC信号量都分配了一个挂起请求队列，用来标识正在等待数组中的一个（或多个）信号量的进程。这个队列是一个sem_queue数量结构的双向链表
数据结构：sem_queue
(5)IPC消息
进程产生的每条消息都被发送到一个IPC消息队列中，这个消息一直存放在队列中直到另一个进程将其读走为止。
消息是由固定大小的首部和可变长度的正文组成的，可以使用一个整数值（消息类型）标识消息，这就允许进程有选择地从消息队列中获取消息。只要进程从IPC消息队列中读出一条消息，内核就把这个消息删除；因此，只能有一个进程接收一条给定的消息。
数据结构：msg_queue
(6)IPC共享内存
最有用的IPC机制是共享内存，这种机制允许两个或多个进程通过把公共数据结构放入一个共享内存区来访问它们。如果进程要访问这种存放在共享内存区的数据结构，就必须在自己的地址空间中增加一个新内存区，它将映射与这个共享内存区相关的页框。这样的页框可以很容易地由内核通过请求调页进程处理
shmat函数把一个共享内存区"附加attach"到一个进程上
[7]换出IPC共享内存区的页
内核在把包含在共享内存区的页换出时一定要谨慎，并且交换高速缓存的作用是至关紧要的。
因为IPC共享内存区映射的是在磁盘上没有映像的特殊索引节点，因此其页是可交换的。因此为了回收IPC共享内存区的页，内核必须把它写入交换区。因为IPC共享内存区是持久
[8]IPC共享内存区的请求调页
4、POSIX消息队列
POSIX标准(IEEEStd1003.1-2001)基于消息队列定义了一个IPC机制，就是大家知道的POSIX消息队列。它很像本章前面“SystemVIPC消息队列”但优点如下：
更简单的基于文件的应用接口
完全支持消息优先级（优先级最终决定队列中消息的位置）
完全支持消息到达的异步通知，这通过信号或是线程创建实现
用于阻塞发送与接收操作的超时机制