Linux进程管理-随笔记录
进程的描述PCB
描述一个进程的结构。
组织方式
进程链表：用于遍历
进程树：体现父子关系
进程哈希表：用于pid检索
进程生命周期
僵尸
僵尸进程：PCB还没消失，等到父进程wait()，父进程可以得知子进程退出原因。
内存泄漏：随时间增加内存消耗震荡发散。
停止
用STOP信号暂停，保存中间结果，用CONTINUE信号继续。
1 | |
睡眠
深睡眠：只有当资源都满足才唤醒。kill -9也无法杀掉。
浅睡眠：可以被信号唤醒。
fork()
写时拷贝
相同的虚拟地址，但页表对应的物理地址不同。
vfork()
pthread_create()
clone
可以自由选择拷贝task_struct中的任意部分。
PID与TGID
用户空间中getpid()实际上得到的是TGID
进程脱孤
睡眠
依赖于等待队列
进程0和1
Linux调度算法
CFS调度策略
CFS策略
CFS 调度程序并不采用严格规则来为一个优先级分配某个长度的时间片，而是为每个任务分配一定比例的 CPU 处理时间。每个任务分配的具体比例是根据友好值来计算的。友好值的范围从 -20 到 +19，数值较低的友好值表示较高的相对优先级。具有较低友好值的任务，与具有较高友好值的任务相比，会得到更高比例的处理器处理时间。默认友好值为 0。
CFS 调度程序没有直接分配优先级。相反，它通过每个任务的变量 vruntime 以便维护虚拟运行时间，进而记录每个任务运行多久。虚拟运行时间与基于任务优先级的衰减因子有关，更低优先级的任务比更高优先级的任务具有更高衰减速率。对于正常优先级的任务（友好值为 0），虚拟运行时间与实际物理运行时间是相同的。
因此，如果一个默认优先级的任务运行 200ms，则它的虚拟运行时间也为 200ms。然而，如果一个较低优先级的任务运行 200ms，则它的虚拟运行时间将大于 200ms。同样，如果一个更高优先级的任务运行 200ms，则它的虚拟运行时间将小于 200ms。当决定下步运行哪个任务时，调度程序只需选择具有最小虚拟运行时间的任务。此外，一个更高优先级的任务如成为可运行，就会抢占低优先级任务。
下面分析一下 CFS 调度程序是如何工作的。假设有两个任务，它们具有相同的友好值。一个任务是 I/O 密集型而另一个为 CPU 密集型。通常，I/O 密集型任务在运行很短时间后就会阻塞以便等待更多的 I/O；而 CPU 密集型任务只要有在处理器上运行的机会，就会用完它的时间片。
因此，I/O 密集型任务的虚拟运行时间最终将会小于 CPU 密集型任务的，从而使得 I/O 密集型任务具有更高的优先级。这时，如果 CPU 密集型任务在运行，而 I/O 密集型任务变得有资格可以运行（如该任务所等待的 I/O 已成为可用)，那么 I/O 密集型任务就会抢占 CPU 密集型任务。
Linux 也实现了实时调度。采用 SCHED_FIFO 或 SCHED_RR 实时策略来调度的任何任务，与普通（非实时的）任务相比，具有更高的优先级。
Linux 采用两个单独的优先级范围，一个用于实时任务，另一个用于正常任务。实时任务分配的静态优先级为 0〜99，而正常任务分配的优先级为 100〜139。
这两个值域合并成为一个全局的优先级方案，其中较低数值表明较高的优先级。正常任务，根据它们的友好值，分配一个优先级；这里 -20 的友好值映射到优先级 100，而 +19 的友好值映射到 139。下图显示了这个方案。
CFS 性能
Linux CFS 调度程序釆用高效算法，以便选择运行下个任务。每个可运行的任务放置在红黑树上（这是一种平衡的、二分搜索树，它的键是基于虚拟运行时间的）。这种树如下图所示：
当一个任务变成可运行时，它被添加到树上。当一个任务变成不可运行时（例如，当阻塞等待 I/O 时），它从树上被删除。一般来说，得到较少处理时间的任务（虚拟运行时间较小）会偏向树的左侧；得到较多处理时间的任务会偏向树的右侧。
根据二分搜索树的性质，最左侧的结点有最小的键值；从 CFS 调度程序角度而言，这也是具有最高优先级的任务。由于红黑树是平衡的，找到最左侧结点会需要 O(lgN) 操作（这里 N 为树内结点总数）。不过，为高效起见，Linux 调度程序将这个值缓存在变量rb_leftmost中，从而确定哪个任务运行只需检索缓存的值。
红黑树
红黑树是对概念模型2-3-4树的一种实现，由于直接进行不同节点间的转化会造成较大的开销，所以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示2-3-4树中不同的节点。
2-3-4树中的2节点对应着红黑树中的黑色节点，而2-3-4树中的非2节点是以红节点+黑节点的方式存在，红节点的意义是与黑色父节点结合，表达着2-3-4树中的3，4节点。
（此处理解成红节点也好，红色链接也好，看个人喜好。很多书中会说是由黑色节点指出的红色链接，链接指向的节点颜色为红。）
1.节点颜色有红色和黑色
【2-3树到红黑树的转化见下文】
2.根节点必为黑色
【2-3树中如果根节点为2节点，那么它本来就对应红黑树中黑节点；如果根节点为3节点，也可以用黑色节点表示较大的那个元素，然后较小的元素作为左倾红节点存在于红黑树中】
3.所有叶子节点都是黑色
【此处提到的叶子其实是空链接，因篇幅问题不便全部画出】
4.任意节点到叶子节点经过的黑色节点数目相同
【红黑树中的红节点是和黑色父节点绑定的，在2-3树中本来就是同一层的，只有黑色节点才会在2-3树中真正贡献高度，由于2-3树的任一节点到空链接距离相同，因此反应在红黑树中就是黑色完美平衡】
5.不会有连续的红色节点
【2-3树中本来就规定没有4节点，2-3-4树中虽然有4节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点】
2-3-4树到红黑树的节点转换
我们先看2-3-4树到红黑树的节点转换。2节点直接转化为黑色节点；3节点这里可以有两种表现形式，左倾红节点或者右倾红节点。而4节点被 强制要求转化为一个黑父带着左右两个红色儿子。
