【Linux】Linux2.6内核进程调度队列与调度原理

一、进程管理中的部分概念

• 竞争性: 系统进程数目众多，而CPU资源只有少量，甚至1个，所以进程之间是具有竞争属性的。为了高效完成任务，更合理竞争相关资源，便具有了优先级
• 独立性: 多进程运行，需要独享各种资源，多进程运行期间互不干扰
• 并行: 多个进程在多个CPU下分别，同时进行运行，这称之为并行
• 并发: 多个进程在一个CPU下采用进程切换的方式，在一段时间之内，让多个进程都得以推进，称之为并发

上面四个概念中竞争性、独立性和并行都非常好理解，下面对并发进行着重讲解。

在操作系统中，所有的进程都不是占有了CPU就一直运行，而是每隔一段时间，自动就会被CPU剥离下来，这里的一段时间指的是时间片，在后面的文章中会着重讲解，一个时间片通常为几毫秒，假设为1毫秒，如果操作系统中有10个进程要运行，那么在一秒这个期间中，每个进程都能被运行100次，例如这种在一段时间内，让多个进程同时得以推进的情况，我们称之为并发。

Linux内核是基于时间片轮转式抢占式内核，所以Linux内核支持进程之间进行CPU资源的抢占，例如一个优先级为80的进程正在运行，而此时有一个优先级为60的进程要运行，那么CPU会将优先级为80的进程剥离下来，运行优先级为60的进程。

二、寄存器

在CPU中有很多寄存器，例如大家熟知的eax、ebx、ecx、edx、ss、ds、cs、gs、fs、ebp、esp、eip、status_reg、cr0~cr4等寄存器。

我们在学习C语言后知道，临时变量具有临时性，那么在函数内定义的临时变量，函数结束后，临时变量就会被销毁，是如何返回给外部的呢？以下面的代码为例，我们需要将func函数中ret的值返回给外部，实际上是通过了eax寄存器来实现的，函数在返回时，会将变量的内容存放到eax寄存器中，外部的赋值语句，会将eax寄存器中的内容赋值给外部的变量中，那么这里的寄存器就充当了代码的临时空间。

int func()
{
	int ret = 0;
	// ...
	return ret;
}

int main()
{
	int num = func();
	// ...
	return 0;
}

在我们写代码的时候，通常使用的是顺序结构，也就是代码从上往下运行，但是代码中通常会有循环、函数的存在，当程序/进程进入循环或是跳转到函数时，我们的进程/程序，都能知道进程/程序运行到了哪里，其实就是因为CPU中的寄存器也就是eip寄存器/pc指针，也被称之为程序计数器，程序计数器能够记录下当前正在运行中程序的指令的下一条指令的地址，所以在我们运行的进程/程序能够知道代码运行到了哪里。

我们的程序在运行的时候，会使用这些寄存器的，进程会产生各种各样的数据，需要在寄存器中临时保持。
这里讲到的是单进程的情况，那如果是多进程的情况下会怎么样呢？当有多个进程的时候，各个进程都会在CPU中的寄存器形成临时数据，我们称之为进程的硬件上下文，每个进程的临时数据都是不一样的，但是在CPU中寄存器硬件只有一套，而进程的硬件上下文则是有几个进程就有几套，所以这里有一个很重要的结论：寄存器 != 寄存器的内容，这个结论非常的重要！！！

这里讲到了一个CPU只有一套寄存器硬件，但是进程的硬件上下文却不止一个，那么如何处理CPU的寄存器与进程的上下文的关系，将会在下面的进程切换中讲到。

三、进程切换

在Linux中，进程切换（Process Switching）是操作系统核心功能之一，它允许操作系统同时运行多个程序，虽然实际上CPU在任何给定时刻都只能执行一个程序的指令。进程切换是操作系统管理CPU时间的一种机制，它确保了每个程序都能获得一定的执行时间，从而实现了多任务处理（Multitasking）的能力。

进程切换的基本步骤：

1. 保存当前进程状态
   当一个进程的时间片用完或者因为其他原因（如等待I/O操作完成）而需要被挂起时，操作系统会保存该进程的当前状态，包括程序计数器（PC指针，指向下一条要执行的指令的地址）、CPU寄存器的内容（如通用寄存器、状态寄存器、指令寄存器等）、堆栈信息等。在老版本的Linux的内核中，这些状态信息被保存在该进程的进程控制块（PCB）中，而在新版本的Linux内核中，这些状态并不是直接保存到PCB中，但还是与PCB相关，因为直接保存这些信息会导致PCB变大，而现在内核也对PCB的大小做出了限制，所以这些信息不是在PCB中直接保存，这就涉及到了PCB中的tss任务数据段，理解起来比较复杂，会在后面的文章中讲到，目前大家可以认为这些信息是保存在PCB中的。
   

2. 选择下一个进程
   操作系统会基于某种调度算法（如轮转调度、优先级调度、最短作业优先等）来选择一个进程来执行。调度算法的选择和设计直接影响到系统的性能和公平性。

3. 恢复新进程的状态
   一旦选定了下一个要执行的进程，操作系统就会从该进程的PCB中恢复其之前保存的状态信息，包括程序计数器、CPU寄存器的内容等。这样，CPU就可以从该进程上次停止的地方继续执行了。

4. 更新PCB和系统状态
   进程切换后，操作系统会更新相关PCB和系统状态，如修改进程状态、更新调度队列等，以便下次调度时使用。

值得注意的是将进程的上下文保存在PCB后，寄存器中的信息并不是被清除，而是被下一个进程的上下文中的信息直接覆盖，若进程没有上下文是一个新进程，那么会将进程跑起来，慢慢的将寄存器中原来的信息覆盖掉。

四、Linux2.6内核进程调度队列与调度原理

每一个CPU会维护一个自己的运行队列，下图是Linux2.6内核中进程队列的数据结构。

在图中我们可以看到，运行队列中有数组queue[140]，全称为task_struct* queue[140]，它是一个指针数组，用来管理进程的优先级，在操作系统中，优先级被分为了两种：

1. 实时优先级：对应数组的0 ~ 99，共100个优先级。（目前来说不是很重要，不过多做讲解）
2. 普通优先级：对应数组的100 ~ 139，共40个优先级。（细心一点能够看出，其实这里的普通优先级，就是上一篇文章讲到的进程优先级，使用映射的方法，将优先级60 ~ 99映射到了数组的100 ~ 139中）

在图中还可以发现，运行队列中维护两个queue[140]，两个queue[140]分别用来维护活跃进程和过期进程，维护两个queue[140]的原因是因为运行队列中如果只维护一个queue[140]的话，一直启动优先级较高的进程会导致优先级较低的进程无法被CPU被调度，不符合Linux内核的较为公平的调度。

运行队列中还维护了两个指针 void* active 和 void* expired 分别用来指向两个数组queue[140]，指针active指向的活跃队列，指针expired指向的是过期队列，CPU调度进程的时候会在活跃队列中优先级高的进程，当进程在一个时间片的时间内运行完后会出现两种情况，一是进程运行完毕，进程退出，二是进程未运行完毕，将该进程交给过期队列进行维护。若正常启动新的进程，是交给过期队列维护而不是活跃队列，以防出现上述不公平的调度，若启动的新进程需要进程抢占，则将新进程交给活跃队列进行维护。活跃队列中的进程会逐渐减少，过期队列中的进程会逐渐增多，当活跃队列中已经没有进程时，将指针active与指针expired指向的内容进行交换，那么活跃队列变为过期队列，过期队列变为活跃队列，重复这样的操作，可以保证Linux内核较为公平的调度每一个进程。

那么如何知道活跃队列中是否有进程呢？CPU应该调度哪个进程？如果每次调度进程都需要遍历一次数组，那么会导致效率低下，我们仔细再看看上图，对应的还有数组int bitmap[5]，也就是位图，一个int类型的变量是32位，那么这个数组就160位，一个位能对应一个优先级，那么160位比特位完全能够对应140个优先级。在这个bitmap中，每个bit位代表一个优先级队列，如果该位为1，则表示对应的优先级队列中有进程存在；如果为0，则表示队列为空。通过读取几个或几十个比特位即可判断队列中是否含有进程。运行队列中还维护了一个变量br_active，用来存储队列有有多少个进程。

总结

在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增加，我们称之为进程调度O(1)算法！这种算法通过优先级队列和位图等数据结构，实现了高效的进程调度。

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹