一、优先级的理解

首先我们来思考这个问题：进程优先级和权限的问题。

权限：是决定我们能不能干这个事情，能不能使用这个资源。

优先级：是我们有使用这个资源的前提下，我们使用这个资源的先后顺序。

所以进程优先级就是：进程已经得到某种资源的前提下，使用这个资源的先后顺序。

那么为啥要有优先级呢？

其实导致这个问题的原因就是我们的资源和要使用我们这个资源之间比例不协调，资源少，使用的人多。

就比如我们在学校饭堂，我们需要进行排队打饭，这是因为我们的窗口少，人多。

在Linux下，对于进程优先级的设计，其也是在我们的task_struct中的，其在我们的task_struct中，其也是两个整型变量。

我们可以使用ps -l指令查看到其。

可以看到，上面有两个属性：PRT和NI

一个是优先级号PRT，一个是NI值，NI就是我们的进程优先级的修正数据。

我们对于进程的优先级的修改都是通过修改NI值来进行修改的。

UID就是进程的执行者。

二、进程优先级的修改

1、PRT&&NI

PRT即进程的优先级，或者通俗点来说的话就是程序被CPU执行的先后顺序，这个值越小，那么其优先级越高

NI就是我们说的nice值，其是表示的进程的优先级的修正数。

PRT(new)=PRT(old)+NI

所以在Linux下，对进程的优先级进行修改就是对NI值进行修改，当NI值为负数的时候，那么其的优先级就变高。

那么我们要如何进行修改呢？

我们先输入top指令然后输入我们要修改的进程的pid，然后输入要修改的NI值。

注意的是，我们的NI的值，在root用户下 ，其可以修改的范围是-20~19，然后我们普通用户可以修改的范围是0~19；

然后我们要注意的是，old的PRT是有一个基准值的，其不是我们上一次的PRT这样，在教材上，规定是80 ，然后我们有的系统中的是20。

这个不影响，反之我们知道优先级的修改是有个范围的，然后优先级PRT越小，那么其优先级越高即可。

为啥我们的优先级要有一个范围呢?
目前我们使用的大部分计算机的操作系统都是分时操作系统，其是给我们的进程分配时间片，当时间片使用完，那么就要将资源释放出来，这个调度方式是为了使得计算机的资源分配更加公平合理，可以较为均衡的让不同的进程都可以得到资源。

操作系统也不允许我们经常对进程优先级进行修改。

对于进程优先级，我们更多是理论上的知识，对于操作不是太重要，有个了解即可。

补充：

竞争性：

首先我们先明确，为啥会有竞争性，因为我们的资源不足，我们的计算机中CPU资源只有少量，但是我们想使用CPU资源的进程是非常多的，所以我们的进程之间是有竞争属性的。其目的也是为了更高效的运行我们的计算机，使进程之间对于资源的分配更加合理，所以也就有了我们上面的进程优先级

独立性：

我们的进程之间是互相独立的，其有独立的pid和代码和数据，需要独立的各种资源，多进程运行期间是互不干扰的。

并行：

多个进程在CPU下分别同时运行，这个是同一个时刻在CPU中进行运行。

并发：

多个进程在一个CPU下采用切换的方式，在一段时间内，让多个进程都可以获得CPU的资源，得到运行，这种叫做并发。

并发和并行的区别：

就是并行是，CPU同时处理好几个进程，并发是在一个时间中，有多个进程在CPU中被处理，但是细看某个时刻，实际上也是一个进程在CPU中运行。

三、进程切换和调度

1、基础知识补充

首先我们补充一个知识，在我们的C语言结构体中，我们如何精确的获取到结构体成员的地址呢？

就比如我们有如下结构体：

struct A{

int a ;

int b;

int c;

double d;

}

那么我们对结构体变量取地址，我们知道取到的是其中一个字节的地址。因为在我们的内存中对于地址，也是一个字节一个字节的。

那么其取到的地址，其实是整个结构体变量中的最低的字节的地址，那么如果我们只知道其中一个结构体成员的地址，那么可以得到其他成员变量的地址么？

是可以的，我们前面学习数组的时候，知道对数组取地址，还有对首元素取地址，都是一样的，也是整个数组的最低地址，然后我们对地址进程++操作就可以找到后续的变量了。当然这个方法还有个要求，就是我们的这个数据存储的物理结构上要是连续的。就可以通过偏移量进行查找。

如上面的结构体，我们知道c成员的地址，然后我们使用这个代码：&((struct *) 0->c )，就可以得到c成员变量相对于结构体变量的最低地址的偏移量。

上面这个代码，就是将0强转为我们的结构体变量指针，然后以0为基准就得到c的地址了。

2、进程调度

前面我们知道了进程的组织方式，实际上是一个链表结构，那么我们可以将其设计成单链表的形式。这个设计方式很简单易懂，但是还有其他的方式，下面我们来重新设计一下。

首先，对于进程的调度，我们得先将要被调度的进程链接起来，我们可以设计一个struct link结构体。其成员变量就两个：struct link*next和struct link*prev。

然后这个双链表结构体节点是存在于我们的进程的task_struct中的，而且其位置就在其结构体成员中的中间位置左右。

大致结构如下：

下面我们解决几个问题：

1、对于一个进程，我们的CPU是如何通过这个双向链表获取到进程的其他信息的？

首先，我们知道、其是一个结构体、那么我们可以通过偏移量的方式获取到其他属性，就是求其他元素和我们的链表结构体之间的偏移量问题。

2、为啥这样子做？

这样可以增加链式管理的扩展性，就是我们对于整个调度，就只需要维护这个链表的代码了。

好处如下：

1、减少内存开销，避免额外内存分配

若使用独立链表节点：每个进程要额外申请一个链表结构体，进程数量多（成千上百）时，会产生大量碎片化内存，还要频繁调用 malloc/free，带来分配、释放开销

内嵌链表：链表节点是 task_struct 的成员变量，创建进程时一次性分配整块内存，销毁时整块释放，无额外动态内存操作，内存利用率更高。

2、地址连续，CPU 缓存命中率大幅提升（核心优势）

CPU 访问内存时优先读取高速缓存（Cache），连续地址数据缓存效率远高于离散数据：

task_struct 本身是一块连续内存，内嵌的链表节点和进程其他字段物理地址紧邻。

调度器遍历链表时，读取链表指针的同时，task_struct 里的进程状态、优先级、时间片等调度信息也会被一同载入缓存。

独立链表节点会分散在内存各处，遍历链表时频繁触发缓存失效（Cache Miss），速度慢很多。

3. 链表操作极简，无需指针二次跳转

独立链表节点逻辑（冗余）：

链表节点 → 指针 → task_struct 遍历 / 增删时，拿到链表节点还要二次解引用才能访问进程数据。

内嵌链表逻辑（直访）：

task_struct 自身包含 next/prev 指针，拿到链表节点 = 直接拿到进程结构体。 调度器增、删、遍历就绪队列、等待队列时，少一层指针跳转，指令更少、执行更快。

4. 增删节点逻辑统一、安全，不易野指针

Linux 内核调度队列（就绪队列、休眠队列、停止队列等）都基于内嵌双向链表：

入队 / 出队：只需要修改当前进程 task_struct 内的 next/prev 指针，以及队列头尾指针，逻辑通用、代码复用性强。

进程消亡时，task_struct 整体回收，不会出现 “链表节点还在、进程结构体已释放” 的悬空野指针，内核稳定性更高。

5. 支持一个进程同时挂入多个链表

一个进程可能同时属于多个调度队列（如：就绪队列 + 组调度队列、信号等待队列）。 task_struct 中可以内嵌多组独立双向链表节点（run_list、wait_list 等），让进程同时挂载到不同链表，实现多队列管理，这是内核调度、等待、阻塞模型的基础。

6. 适配内核通用链表框架

Linux 内核实现了一套通用双向链表 list_head，设计初衷就是内嵌式使用： 所有内核队列（进程、定时器、文件、信号量）统一用这套链表，task_struct 内嵌 list_head 可以直接复用内核标准链表接口（list_add/list_del/list_for_each），不用为进程调度单独实现一套链表逻辑，代码维护成本低。

四、进程运行队列

在我们的计算机中每个CPU都会有一个调度队列：struct runqueue{};

如下所示：

我们看图中标记的两个位置，可以看到其有两个queue，然后其大小是140的空间，其就是一个数组结构，然后我们对其0-99的位置的进程不关心，关心的是100-139位置的，其实可以看到其位置个数就刚刚好对应我们的优先级的范围大小，优先级和进程运行队列实际上是映射的关系。

0-99这个位置是给实时进程使用的。

CPU会从这个数组中，从优先级高的开始往优先级低的找，找到这个优先级中有进程，那么就会去执行。

那么有个疑问？

如果说我们的CPU此时正在执行优先级为80的进程，然后呢，此时隔一会就会有一个优先级为79的进程进入我们的运行队列，那么其是否就立马去执行我们的79进程呢？

实则不是，可以发现我们上面是有两换个一样的部分，其中一个是活跃进程，一个是过期进程，然后呢我们的CPU只会去活跃进程的数组中调用进程，然后后面来的会先插入到过期进程的数组中，当前面的活跃进程数组的进程被调用完，那么就会将其进行调换，然后我们再看，上面有两个指针active和*expired，active是指向的活跃进程部分，然后expired是指向的过去进程部分，然后调度完后，他们两个指针会进行交换。

所以这样就避免了进程饥饿问题。

然后呢对于进程调度的查找，实际上是使用的位运算，会有140个二进制数字，然后其中那个位置为1，那么就表示数组的这个位置有进程要被调度。

然后操作系统实际上不是一个bit位一个bit位进行查找的，其是一次找32位，可以看到我们上面有一个bitmap[5]其就是我们进行位运算的数组。其一次进行32位的bit位的运算。

所以总的来说，在Linux中的调度算法，其时间复杂度就是O(1)的。