[ linux-系统 ] 进程优先级 | Linux内核O(1)算法

进程优先级

进程优先级是操作系统用于决定哪个进程应优先获得 CPU 时间的一种机制

优先级属性是由什么决定的？

每个进程的task_struct有几个特定的int类型变量决定优先级

PRI(priority)进程的优先级   NI(nice)  优先级的修正数据 

查看优先级

可以使用ps -la命令查看系统进程的相关信息，包括UID、PID、PPID、PRI和NI等

PRI值越小，进程的优先级越高 

 最终优先级 = pri + nice 

UID补充：(user identification用户身份)

文件会记录拥有者所属组和对应的权限，所有操作都是进程操作，打开或查看文件时，进程自己会记录谁启动的文件，进程通过UID比较是否拥有权限

 修改进程优先级

修改进程优先级主要是通过修改nice值实现的，可以使用nice和renice命令或通过top命令进行修改。

$ sudo top
# 在top命令界面按“r”键，输入进程PID和新的nice值

nice值范围为-20至19，数值越小，优先级越高。 

进程切换 

Linux是基于时间片，进行调度轮转的，时间片到了，进程就要被切换

一个进程在时间片到了的时候，并不一定跑完了，可以在任何时候重新调度切换

切换过程和理解

进程在运行的时候，会有很多临时数据，在CPU的寄存器中保存，CPU内有很多个寄存器

CPU内部的寄存器的数据，是进程执行时的瞬时状态信息数据(上下文数据)

寄存器！=寄存器里面的数据

 进程切换的核心：进程上下文数据的保存与恢复

两个寄存器pc,ir

pc:存储着下一条要执行指令的内存地址

ir:用于暂存从内存中取出、正在解码和执行的指令

每个进程都要有自己的上下文数据，寄存器只有一套，多个进程共用一套寄存器

进程上下文数据的保存：将寄存器内的数据切走，保存到进程中的PCB中

恢复：将PCB保存的寄存器中的数据，恢复到寄存器中

看初代Linux源代码，可以看到task_struct里面有一个struct tss_struct(任务状态段)保存的是寄存器的信息

Linux的真实调度算法(Linux内核O(1)算法)

下图是Linux2.6内核中进程队列的数据结构

对于这个运行队列struct runqueue，内部成员主要为三个，两个结构体指针，两个结构体类型的数组，数组内部包含一个变量nr_active ，整形数组bitmap，和一个指向task_struct的指针数组

queue[140] 类型是struct task_struct* ,数组中有140个元素，就是有140个结构体指针，前100个指针[0,99]是给实时进程(实时优先级0-99数值高优先级高)使用的，我们不考虑。我们只考虑[100,139],普通优先级通过 nice 值调整，40个数组刚好对应nice值的范围，nice值范围是[-20,19]。  

真实进程优先级[60,99] , 数组下标和进程优先级对应关系为 下标 = pri - startpri(60) + 100

task_struct * queue 是一个指向进程控制块的指针，数组每一个元素表示进程优先级的大小

相同的进程优先级会用链表链接在一起，这就相当于数据结构中的开散列哈希表

哈希表中每个哈希桶存储一个进程队列，每个桶指向一个进程队列的头节点

CPU调度进程首先要先找到runqueue ,遍历内部数据结构，找到内部哈希表，根据优先级找它对应的进程

runqueue中两个指针最开始active = & array[0],expired = & array[1]

CPU调度只会从active队列中选择进程来进行调度

调度有三种情况：1.运行退出 2.不推出，时间片到了 3.新的进程产生了

情况1：运行完退出了，进程不放回调度队列即可

情况3：当我们正在调度队列时，新建进程，进程有优先级，根据优先级，拿active指针找到对应的哈希表，找位置插进去，需要OS帮助插入，OS还要调度，新进程越来越多，会影响OS调度

调度器要非常均衡的进程调度，如果新插入的进程很多且优先级较高，那么就影响后面进程的调度(进程饥饿问题)  解决方法：有新进程产生就放在过期队列expired中

情况2：时间片到了，不能直接放回active中，应该放在expired过期队列中。保证active队列永远都是一个存量进程竞争的情况，active队列进程只会越来越少，不会增多

 当active队列里的进程全部被调度完成后，只需swap(&active,&expired),改变指针指向的内容 

 

nr_active表示队列中有多少活跃进程数，也决定了什么时候swap

CPU调度时，用哈希表调度进程为O(1),140个位置哪个位置有进程只能遍历，时间复杂度太高，这里借助bitmap[5]优化调度效率，通过 位运算 快速找到第一个非空队列的位置。

bitmap[5] 充当一张位图，一共160个比特位覆盖140个进程优先级，比特位为0时表示对应位置为空，为1时表示对应位置有进程

真实调度时不会从头开始遍历每一个比特位，for循环一次就可以检测32个位置，如果等于0就检测下一批，如果不为0就检测当前32个比特位确定哪一个队列

for(int i = 0;i < 5;i++)
{if(bitmap[i] == 0) continue;else{//}
}

补充知识： 

Linux中链式结构，只有链接子段没有属性字段

一个进程，既可以在全局链表中，又可以在任何一个其他数据结构中，只要加节点字段即可

原理是什么？如果我要访问节点所属数据结构的其他成员该如何实现？

例如上图结构体，我们直到c的地址，如何求其他成员的地址？

先求成员 c 相对于结构体起始地址的字节偏移量 ,&( (struct A*)0 -> c) 

再根据c的真实地址减去偏移量，得到结构体的起始地址 (&c - &( (struct A*)0 -> c) );

拿到结构体起始地址就可以访问结构体内任意成员  (&c - &( (struct A*)0 -> c) ) -> b;