Linux笔记---进程：进程切换与O(1)调度算法

1. 补充概念

1.1 并行与并发

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

由于在一个操作系统中进程的数量通常是很多的，所以并发的调度方式必不可少，在这篇文章中，我们要详细探讨进程是如何切换的。

1.2 实时操作系统与分时操作系统

实时操作系统：是指系统能够及时响应外部事件的请求，在规定的时间范围完成对该事件的处理，并控制实时任务协调一致地运行。实时操作系统分为硬实时系统（如火箭和导弹控制）和软实时系统（如银行），需要具备实时时钟管理、过载防护和高可靠性等能力。
分时操作系统：是一种允许多个用户同时共享一台计算机资源的操作系统。它通过将计算机的处理能力划分为多个时间片，轮流分配给不同的用户进程，使得每个用户都能在短时间内得到系统的响应，就好像独占使用整个系统一样。
时间片：当代计算机都是分时操作系统，每个进程都有它合适的时间片(其实就是一个计数器)。时间片到达，进程就被操作系统从CPU中剥离下来，接着其他进程将占据CPU资源，该进程回到运行队列重新排队。

进程的时间片用完就被CPU换下，让其他进程抢占CPU资源，这一点很好理解，但有两个问题：

当一个程序再次获得CPU资源时，如何接着上次运行的进度来继续运行？
CPU是如何由优先级来决定谁该抢占CPU资源的？或者说优先级是如何实现的？

2. CPU上下文切换

在Linux操作系统中，CPU上下文切换是指在多任务处理时，CPU从一个任务切换到另一个任务的过程。这个过程包括保存当前任务的CPU寄存器和程序计数器的值，加载新任务的上下文到这些寄存器和程序计数器，然后跳转到程序计数器所指的新位置，开始运行新任务。

上下文切换的目的是为了让多个任务看起来像是同时运行，而实际上CPU在短时间内轮流执行这些任务。

简单来说，每个进程在被换下时，会将当前CPU中寄存器的内容(上下文数据)保存到自己的PCB中维护起来，再将即将执行的进程的上下文数据加载到CPU中。

在task_struct中存在字段struct tss_struct tss，该结构体就用来保存进程的上下文数据。

struct tss_struct {
    struct x86_hw_tss x86_tss;
    unsigned long io_bitmap[IO_BITMAP_LONGS + 1];
    unsigned long stack[64];
} ____cacheline_aligned;

struct x86_hw_tss {
    unsigned short back_link, __blh;
    unsigned long sp0;
    unsigned short ss0, __ss0h;
    unsigned long sp1;
    unsigned short ss1, __ss1h;
    unsigned long sp2;
    unsigned short ss2, __ss2h;
    unsigned long __cr3;
    unsigned long ip;
    unsigned long flags;
    unsigned long ax;
    unsigned long cx;
    unsigned long dx;
    unsigned long bx;
    unsigned long sp;
    unsigned long bp;
    unsigned long si;
    unsigned long di;
    unsigned short es, __esh;
    unsigned short cs, __csh;
    unsigned short ss, __ssh;
    unsigned short ds, __dsh;
    unsigned short fs, __fsh;
    unsigned short gs, __gsh;
    unsigned short ldt, __ldth;
    unsigned short trace;
    unsigned short io_bitmap_base;
} __attribute__((packed));

x86_tss: 这是一个x86_hw_tss类型的结构体，它定义了硬件状态信息，包括寄存器的值、堆栈指针等。
io_bitmap: 这是一个unsigned long类型的数组，用于存储I/O权限位图。
stack: 这是一个unsigned long类型的数组，用于存储紧急内核堆栈。

上下文切换的性能影响

上下文切换是有一定开销的，每次上下文切换都需要几十纳秒到数微秒的CPU时间。特别是在进程上下文切换次数较多的情况下，很容易导致CPU将大量时间耗费在寄存器、内核栈以及虚拟内存等资源的保存和恢复上，进而大大缩短了真正运行进程的时间

3. O(1)调度算法

接下来的问题就是，操作系统如何根据优先级决定下一个接手CPU资源的进程是哪一个。

加入依次检查调度队列中的进程的优先级并从中选择的话，时间复杂度会达到O(n)。

O(1)调度算法是Linux内核中的一种进程调度算法，其名称中的“O(1)”表示该算法的时间复杂度是常数级别的，与系统中的进程数量无关。这种算法的设计目的是为了解决O(n)调度算法在处理大量进程时效率低下的问题。

下图是Linux中运行队列的结构示意图：

我们要讨论的核心在于：

3.1 prio_array结构体

在runqueue中有一个只含两个元素的结构体数组字段，即图中的array[0]和array[1]：

struct prio_array {
    unsigned int nr_active; /* 本组中待处理进程的总数 */
    unsigned long bitmap[BITMAP_SIZE]; /* 用位图的方式表示某个优先级上有没有待处理的进程队列 */
    struct list_head queue[MAX_PRIO]; /* 与bitmap对应，存储所有待运行的进程 */
};

// #define 5 BITMAP_SIZE
// #define 140 MAX_PRIO

nr_active：表示本组中待处理进程的总数。
bitmap：这是一个位图，用于表示某个优先级上是否有待处理的进程队列。位图中的每一位对应一个优先级，1表示该优先级上有待处理的进程队列，0表示没有。
queue：这是一个队列数组，用于存储所有待运行的进程。数组的下标对应进程的优先级，每个元素都是一个队列，队列中的节点是具有相同优先级的进程。例如，优先级为124的进程会被放到下标为124的队列中排队。

根据上面的信息可以知道，整个操作系统中的优先级范围为[0，140），共140种：