Linux进程管理-随笔记录

进程的描述PCB

image-20211002122957484

描述一个进程的结构。

组织方式

进程链表:用于遍历

进程树:体现父子关系

进程哈希表:用于pid检索

进程生命周期

image-20211002123858943

僵尸

僵尸进程:PCB还没消失,等到父进程wait(),父进程可以得知子进程退出原因。

内存泄漏:随时间增加内存消耗震荡发散。

停止

用STOP信号暂停,保存中间结果,用CONTINUE信号继续。

Ctrl+zbgfg

睡眠

深睡眠:只有当资源都满足才唤醒。kill -9也无法杀掉。

浅睡眠:可以被信号唤醒。

fork()

image-20211005105535624

写时拷贝

image-20211005105035326

相同的虚拟地址,但页表对应的物理地址不同。

vfork()

image-20211005105600004

pthread_create()

image-20211005105804929

clone

image-20211005110022717

image-20211005110030577

可以自由选择拷贝task_struct中的任意部分。

PID与TGID

image-20211005110908778

用户空间中getpid()实际上得到的是TGID

进程脱孤

image-20211005111807317

睡眠

image-20211005112255626

依赖于等待队列

进程0和1

image-20211005112807754

Linux调度算法

image-20211005114800208

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。下图显示了这个方案。

image-20211011160615690

CFS 性能

Linux CFS 调度程序釆用高效算法,以便选择运行下个任务。每个可运行的任务放置在红黑树上(这是一种平衡的、二分搜索树,它的键是基于虚拟运行时间的)。这种树如下图所示:

image-20211011160739213

当一个任务变成可运行时,它被添加到树上。当一个任务变成不可运行时(例如,当阻塞等待 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节点被 强制要求转化为一个黑父带着左右两个红色儿子。

image-20211011145729459

image-20211011150640330

发表评论

nv-author-image