目录
1 进程状态
1.1 进程状态概念
1.2 运行&&阻塞&&挂起
1.2.1 知识点
1.3 理解内核链表的话题
1.4 僵尸状态 僵尸进程
1.5 两个问题
1.6 孤儿进程
2 进程优先级
2.1 进程优先级概念
2.2 查看系统进程
2.3 PRI和NI
2.4 四个概念：竞争，独立，并行，并发
3 进程切换
3.1 死循环进程如何运行
3.2 聊聊CPU寄存器
3.3 进程如何切换
4 Linux真实调度算法：O(1)调度算法
上一篇说明完进程的概念后，本文继续深入理解进程。
1 进程状态
1.1 进程状态概念
进程状态，本质是task_struct结构体内的一个整型变量，在操作系统内可用#define来表示R S T。进程什么状态，整型变量就改什么数字。进程状态就是task_struct内的一个整数。
源码定义：
/*
*The task state array is a strange "bitmap" of
*reasons to sleep. Thus "running" is zero, and
*you can test for combinations of others with
*simple bit tests.
*/
static const char *const task_state_array[] = {
"R (running)", /*0 */
"S (sleeping)", /*1 */
"D (disk sleep)", /*2 */
"T (stopped)", /*4 */
"t (tracing stop)", /*8 */
"X (dead)", /*16 */
"Z (zombie)", /*32 */
};
Linux进程状态
- R运行状态(running)：并不意味着进程一定在运行中，它表明进程要么是在运行中，要么在运行队列里。
- S睡眠状态(sleeping)：意味着进程在等待时间完成
- D磁盘休眠状态(Disk sleep)：有时候也叫不可中断睡眠状态，在这个状态的进程通常会等待IO的结束。
- T停止状态(stopped)：可以通过发送SIGSTOP信号给进程来停止进程。这个被暂停的进程可以通过发送SIGCONT信号让进程继续运行。
- X死亡状态(dead)：这个状态只是一个返回状态，你不会在任务列表里看到这个状态。
1.2 运行&&阻塞&&挂起
让CPU选一个进程去运行，本质是选择一个进程的PCB来运行，一个PCB要有指针指到它代码和数据。
一个CPU，一个调度队列： 
在Linux内核中，名字叫runqueue，类型是task_struct*。
Linux内核对于PCB的维护，采用的做法是一个task_struct节点，既可以属于一个全局双向链表，又可以把相关进程放相关队列里。也就是说一个进程的PCB节点既可以属于A数据结构，又可以属于B数据结构。所以在操作系统内部，专门为CPU设计了一个队列。
1.2.1 知识点
CPU调度就是在这个队列中按照顺序依次选择一个task_struct来进行调度执行。
什么叫运行状态：只要一个进程在调度队列中，就称该进程叫做运行状态。
什么叫阻塞状态：等待某种设备或资源就绪，不就绪就不调度。比如键盘，显示器等设备就不一定是就绪的，你用了一个scanf函数，不按键盘去输入内容，就是阻塞。
操作系统怎么对软硬件资源进行管理呢？以硬件为例，先描述，再组织。操作系统管理硬件，为每个设备构建struct device的节点(实际更复杂)，用指针将所有设备连接，转化成对链表的增删查改。操作系统内除了有运行队列，还有设备队列。然后每个设备都有一个自己的等待队列：
假设CPU正在运行这个进程，发现这个进程要进行scanf读取，然后操作系统就去检查键盘的状态(status)，发现键盘没有任何按键按下，此时操作系统发现这个进程无法再执行了，所以操作系统将这个进程从CPU上拿下来，将这个进程从运行队列中移除，将PCB链入到特定设备（这里是键盘，每个设备都有自己独立的等待队列）的等待队列中。一旦把这个进程链入到其他队列(不在运行队列中)，该进程就不会被调度，就处于阻塞状态。
所以从运行状态到阻塞状态的本质是将PCB链入到不同结构中。当键盘被用户按下时，这个进程不知道，操作系统作为硬件管理者，第一时间知道，转而查看就绪设备对应节点，将状态设为active，检查等待队列，发现指针不为空，将该等待队列中PCB设为运行状态，将该进程链回运行队列，CPU调度这个进程就会执行。
所以结论：进程状态的变化，表现之一就是要在不同的队列中进行流动。本质就是数据结构的增删查改。
假设内存资源严重不足，操作系统要做一件事，在磁盘中存在一个特定分区，称为swap交换分区，这时将等待队列中，操作系统让PCB在内存代码和数据换出到磁盘swap分区，此时这些进程的状态叫阻塞挂起，键盘一旦好了，操作系统就会将对应进程曾经换入磁盘中的代码和数据重新加载到内存，重新构建指针的映射，形成完整进程，再到运行队列。这个过程叫swap交换分区的唤出唤入过程，挂起是将进程的代码和数据挂到磁盘上。
如果内存资源相当吃紧，将等待队列中所有进程代码和数据全挂起，内存空间还是不够，操作系统就将运行队列中末端进程代码和数据唤到swap分区，这叫运行挂起。
1.3 理解内核链表的话题
内核中有一个结构体list_head，成员有且只包含next，prev。
有了它之后定义任何一个结构体，比如task_struct，将这个list_head节点类型作为新的目标数据结构成员。
那么运行队列中task_struct连接起来，就是通过list_head:
只指向目标结构体内部的成员list_head。
小知识：一个结构体a，取地址a和取地址a的第一个成员变量，地址是一样的。&a==&a.x
那么遍历链表，访问任何一个结构体的任何成员，怎么做呢？
答案:
(struct task_struct*)（list-&((struct task_struct*)0->links)）
将0号地址强转后直接访问links，再取地址得到links相较于结构体开始位置的偏移量。因为我只知道当前对象对应links地址，有了偏移量，直接list的地址值减去偏移量，就得到链表中头部地址，未来这个结构体内部的所有成员就都能访问了。
总结：已知结构体中某个成员的地址，通过计算该成员在结构体中的偏移量，就能得到结构体的首地址，进而访问所有成员。
所以task_struct有了list_head成员，就是双向链表将进程们连接起来，那么可不可以task_struct内部有非常多的list_head，答案是可以的。所以可以在每个字段将list_head连接起来，任何对应的struct task_struct，一个对象，一套属性。让task_struct既属于运行队列，又属于全局链表，还可以把它放在二叉树中。所以一个PCB可以随便链接，这些个PCB既在运行队列里，同时又在全局链表中，把它从运行队列里断键放到阻塞队列里，同时它又在全局链表中！这样就能理解了。
一个PCB可以同时隶属于多种数据结构，Linux内核中很多数据结构其实是网状的。
1.4 僵尸状态 僵尸进程
Z是僵尸状态，目的是为了获取退出信息。
在Linux中，我们创建子进程的目的，是为了让子进程完成某种事情的，然后结果相关的信息父进程需要知道，一个子进程退出时，操作系统可以将其代码和数据释放掉(PCB信息不能释放)。我们需要子进程退出时，父进程要从子进程中获取子进程退出的结果，所以一个子进程退出，要把退出信息暂时维持住，让父进程获取，在子进程退出之后，父进程获取子进程的退出信息之前，状态就是Z状态(僵尸状态)。
模拟验证Z状态：
编译然后查看进程：
运行可执行程序查看进程：
前面时候父子进程正常运行，后来子进程退出，肉眼看到子进程的状态是Z状态。
如果父进程一直不管，不回收，僵尸状态是不是一直要维护呢？答案是是的，如果父进程一直不管，不回收，不获取子进程的退出信息，那么僵尸状态一直存在，PCB一直存在，因为PID在，那么内存一直被占用，这叫内存泄漏问题！这是不通过new，malloc的内存泄露。僵尸进程就是内存泄漏。
1.5 两个问题
如果进程结束了，曾经因内存泄漏没有被释放的空间会恢复吗？或者说进程退出了，内存泄漏还在不在？
答案是不存在的，进程退了，内存泄漏问题就没有了。
什么样的进程具有内存泄漏问题是比较麻烦的？
真实世界很多软件启动之后不退出的，比如windows中自带的杀毒软件，这种是常驻内存的进程，这样的进程最怕内存泄漏。
知识点：unuse列表：存放进程结束后的task_struct，相当于数据结构的缓存，进程启动后，不用重新建立task_struct，而从unuse中获取，直接填属性，用来加快创建进程和释放进程的速度。
1.6 孤儿进程
写一个验证孤儿进程的代码
父子进程关系中，如果父进程先退出，子进程要被1号进程领养，这个被领养的进程（子进程），叫做孤儿进程。
在Linux系统中，1号进程创建的bash。
为什么要领养？如果不领养，子进程就会进入僵尸状态，就没人回收它了，就会造成内存泄漏，无法解决。领养之后新的父进程未来对这种子进程进行统一回收。
一个子进程变成孤儿进程后一般就自动变后台内容，ctrl c杀不掉，只能kill -9 加pid杀掉进程。
2 进程优先级
2.1 进程优先级概念
什么是优先级？优先级本质是一种衡量得到某种资源的先后顺序，同理：对进程，是进程得到CPU资源的先后顺序。
为什么要有进程优先级？因为目标资源稀缺，导致要通过优先级确定谁先谁后的问题！
优先级也是一种数字，是task_struct中的一个属性，值越低，优先级越高，反之，优先级越低。
2.2 查看系统进程
当代Linux或大部分操作系统，这些操作系统叫做基于时间片的分时操作系统。要考虑公平性，优先级先后差别不能太大，优先级可能变化，但是变化幅度不能太大。
使用ps -la可以看到以下内容：
几个重要信息：
- UID：代表执行者的身份
- PID：代表这个进程的代号
- PPID：代表这个进程是由哪个进程发展衍生而来的，亦即父进程的代号
- PRI：代表这个进程可被执行的优先级，其值越小越早被执行
- NI：代表这个进程的nice值
小知识：系统怎么会知道我访问文件时是拥有者，所属组还是other？
因为进程启动时，会记录UID，Linux系统中，访问任何资源都是进程访问，进程就代表用户，用户和系统打交道，只能通过进程来交互，所有需求都会变成进程，由OS帮你去调度去执行。所以识别权限不是识别用户，是识别进程和文件之间的权限。
2.3 PRI和NI
PRI：进程的优先级，默认是80。
NI：进程优先级的修改数据，也称nice值，调整优先级，在Linux下，就是调整进程的nice值。
所以一个进程的真实优先级=PRI(默认)+NI。默认这里是80。
使用top命令更改已经存在进程的nice：进入top后按“r”，然后输入进程的PID，然后输入nice值即可。
nice的取值范围是[-20，19]，默认的PRI是80，所以Linux进程优先级范围是[60,99]。
为什么优先级调整范围不能太宽泛？答：如果优先级跨度太大，用户能自己恶意修改自己进程的优先级，来尽可能的让自己进程总是优先获得资源，此时可能导致进程优先级低的进程长时间得不到CPU资源，进而导致进程饥饿。
2.4 四个概念：竞争，独立，并行，并发
多个进程之间存在竞争性：系统进程数目众多，而CPU资源只有少量，甚至只有一个CPU，所以进程之间是具有竞争属性的。为了高效完成任务，更合理竞争竞争相关资源，便具有优先级，独立性。多进程运行，需要独享各种资源，多进程之间互不干扰。
并行：多个进程在多个CPU下分别同时进行运行，称之为并行
并发：多个进程在一个CPU下采用进程切换的方式在一段时间内，让多个进程都得以推进，称之为并发。
3 进程切换
3.1 死循环进程如何运行
一旦一个进程占有CPU，会把自己的代码跑完吗？答案是不会！每个进程，操作系统都会给它分配一个时间片的东西，一个进程不会一直占用CPU，时间片到了，操作系统就会切换它。
死循环进程不会打死操作系统，因为有时间片，死循环进程不会一直占有CPU。
3.2 CPU寄存器
CPU调度进程时，访问其代码和数据，为了处理代码和数据，CPU内有很多寄存器，这些寄存器在32，64位下都有很多。例如ebp/esp，eax/ebx/acx/adx，cs/ds/es/gs等。寄存器内保存的是一个正在运行的进程，执行过程中此时刻的临时数据。
结论：
（1）寄存器就是CPU内部的临时空间
（2）寄存器！=寄存器里面的数据，寄存器是空间，只有一份，内容数据可以是多份的。
3.3 进程如何切换
进程切换，最核心的的就是保存和恢复当前进程硬件上下文的数据，即CPU内寄存器的内容。
切换中把寄存器的临时数据叫当前进程的硬件上下文数据，保存起来，保存到哪里了呢？结论是保存到task_struct里面。当代操作系统给每个进程TSS字段。TSS：任务状态段也是结构体，放上下文，能通过task_struct找到TSS。
总结：一个进程要切换，将其硬件上下文保存起来，在运行期间，CPU寄存器内包含很多临时数据，临时数据是进程运行上下文，每次运行，如果时间片到了，操作系统就会把进程切换下去，将上下文数据保存起来，下个进程再进来运行，重复这种流程。
4 Linux真实调度算法：O(1)调度算法
下面的所有内容可以参照上面的图片。
调度和切换共同构成调度器。每个CPU，有一个运行队列。在Linux内核中，运行队列叫做runquenue。里面有一个queue[140]，queue的类型是struct task_struct* queue[140]，其实是个指针数组，有140项。为什么是140呢？其实Linux的优先级其实是140个。那么为什么优先级范围是[60，99]？
queue[140]内[0,99]这100个称之为实时优先级(这里我们不考虑)。解释：操作系统分为两大类别：分时操作系统(按时间片为单位公平调度)。还有一种是实时操作系统，一旦我们来了一个进程，必须立即响应，处理完才能处理下一个进程。为什么很少谈这个呢？一般在工业领域，制造业领域用的比较多。比如汽车上车载系统控制、刹车控制，这种不敢上分时操作系统，用实时操作系统。在互联网领域，分时操作系统最广泛。
那么Linux只做分时操作系统不就行了吗？为啥还要加实时操作系统。因为为了让更多人用Liinux操作系统，满足更多人需求。所以大部分操作系统既支持实时，又支持分时。所以一般不考虑[0,99]，一旦不考虑，一共140，所以还剩40个优先级，这就和进程优先级范围[60，99]对应起来了。
所以优先级 x-60+(140-40),将优先级映射下标，这40个中保存的都是task_struct*，优先级是60就链入到对应100下标，就完成了对应按照不同优先级调度，局部上采用先进先出。
这个表本质就是哈希表，哈希函数是：x-60+(140-40).操作系统层面调度器选一个进程调度在一个确定优先级下找一个进程,时间复杂度是O(1)。如果所有进程优先级都比较低,不还是要遍历这个数组吗?遍历复杂度是O(n)，效率还是不高，所以调度器如何快速挑选一个进程呢？
这里在运行队列中有一个bitmap[5]，这是位图。这里的类型是unsigned int bitmap[5]，一共是32*5=160个比特位。为什么是5？因为这个位图的比特位和整个queue[140]一一对应，覆盖140个，所以是5，有160个比特位能覆盖这140个。比特位内容1/0表示是否存在内容。假设如果一个比特位是000…00100，代表2号下标有进程。
所以调度器，快速挑选一个进程。1 挑队列 2 挑进程
挑队列，只要查看位图整体把32个比特位整体查看有不为0的位置，再去对应32个比特位具体在哪个下标，缓解遍历140个位置的时间复杂度。
所以做到了以O(1)时间复杂度挑选一个进程，我们把它叫做Linux内核进程调度算法之O(1)调度算法。
还有一个是nr_active，表示整个队列中一共有多少个进程。所以调度中先查nr_active，大于0，再查bitmap[5]，确认下标，直接索引找到目标队列，从队列中查找进程，找到后将当前进程PCB放入struct task_struct* current指针里，然后执行切换算法，然后current选择不同进程放CPU上，继续运行。
这还没完，如果这样调度的话，假设现在有一个60号进程，也有一个99号进程。60号进程是一个死循环，60号进程时间片到了，此时被切换下去。因为下次还要调度放回队列里。60号进程放到60号下标对应队列的结尾处，会发现永远都是将下标100对应队列中的所有进程全跑完才能执行101，这就造成了进程饥饿问题。所以runqueue又干了一件事：在整个runqueue又弄一个哈希数组，和上面的大哈希表一模一样。
内核中设计了一个struct rqueue_elem结构体，内部有int nr_sctive，bitmap[5]，queue[140]。然后在rqueue内部定义struct rqueue_elsm prio_array[2]，在rqueue包含数组两个元素，0号下标是蓝色，1号下标是红色(对应图片)，从此以后在runqueue内部定义两个active，类型是struct rqueue_elem*，一个是活跃进程，一个是过期进程。struct rqueue_elem* active=&prio_array[0]。struct rqueue_elem* expired=&prio_arry[1]。
CPU在调度进程，挑进程首先永远只从active指针找到runqueue，60号进程被剥离下来，不能放回到原队列，必须把这个进程重新链入到rqueue_elem(过期队列中)，凡是时间片到了的进程，全部放进过期队列中，慢慢地，active queue中进程越来越少，expired queue进程越来越多。规定必须把active队列中进程全部调度完成才能有后续动作，然后神之一手：swap(&active,&expired);直接进行指针内容交换。active指向原来的expired，expired指向的就是原来active的空队列。然后重复调度，完成了O(1)调度算法。
所以为啥要有NI(nice值)而不是直接改PRI？
直接改PRI，如果这个进程在活跃队列里，改优先级，进程要不要重新改链入位置，在活跃队列中修改和在过期队列中修改都不好。所以有nice值，这个进程在活跃队列中时间片到了，进入过期队列时根据新的优先级去对应位置就好了。所以这是为了配合O(1)调度算法。
以上就是这篇文章的所有内容了，如果这篇文章对你有用，可以点点赞哦，你的支持就是我写下去的动力，后续会继续更新其他知识。
