Linux 真实调度算法

下图是Linux2.6内核中进程队列的数据结构，也有Linux2.6内核进程O(1)调度算法，可单单看一副图片，也不知所以然

1. queue[140]

首先就是这个queue[140]，queue它就是个哈希表，优先级就是哈希槽（slot），x-60 + (140 - 40)就是哈希转换算法

Linux操作系统的优先级其实总共是140个，那之前不是实验出优先级的范围是[60, 99]，总共40个吗？这里为啥是140个呢

因为Linux的优先级有实时优先级和分时优先级，它既是一个实时操作系统，又是一个分时操作系统，而[0, 99]是实时优先级（并不考虑），[100, 139]是分时优先级的范围，是咱们所要去关注的

x的取值范围是[60, 99]，将其代入到哈希转换算法中，得出的取值范围不就是[100, 139]。那此时就会存在疑问，既然这个实时优先级不考虑，为啥还要将它设计出来呢？

实时优先级适用于实时操作系统，Linux最初确实是作为分时操作系统设计的，主要应用于服务器领域。但它的调度算法之所以要加入实时操作系统特性，最根本的原因在于：任何操作系统开发者都希望扩大用户群体

虽然Linux在后端服务器领域应用最为广泛，但这并不意味着它只能用于服务器场景。实际上，Linux同样适用于工业控制和制造等实时性要求较高的领域。因此，现代操作系统通常都会同时支持分时和实时两种调度模式

2. bitmap[5] 位图

bitmap它首先是个位图，unsigned int bitmap[5]总共有160个比特位（32*5），比特位前140个的位置就逐一对应着queue[140]的slot，比特位中的内容：1/0，1表示该slot指向的进程不为空，0则为空

这里运行队列咱们只考虑从100开始，上面只是做个形象的展示。进程调度，宏观上先看优先级，优先级相同的先进先出（FIFO算法），比如图中2号优先级的第一个进程先调度

比如0000100，优先级为3的进程不为空。为啥位图的元素个数是5，因为4是128，6是192，只有5是最接近140的

调度器快速地挑选一个进程要分成两步，第一步就是挑队列，而挑队列再也不用去遍历queue这个指针数组了，直接查看对应的位图bitmap

第二步：再到队列中去挑特定的进程→这样挑选一个进程基本上做到了几乎为O(1)的时间复杂度，将这个调度算法称为Linux内核进程调度算法之大O(1)调度算法

3. nr_active

nr_active就表示整个队列中一共有多少个进程。所以进程调度时先查nr_active→bitmap（确认下标）→queue，找到目标队列，从目标队列头部提取内容，头部移除（Pop_from），将当前结点的PCB放入到struct task_struct* current指针里，执行切换算法，将current指针指向的进程放到CPU上就能运行了

如果这样调度的话，假如今天有一个60号进程，它是一个死循环，也有一个99号进程。60进程时间片到了，运行完毕后，切换下去，它未来还要被调度的，所以就将它重新放到了这个队列（60优先级指向的队列）的最后面进行排队

此时你就会发现存在什么样的问题，CPU在调度时，只有将60优先级队列中的所有进程全部跑完，才会跑后面优先级队列的进程，跑完前面所有进程，才会跑99号进程，可是60号进程是个死循环，那99号进程就永远无法被调度，就会造成进程饥饿问题

4. 活跃进程与过期进程

那为了解决上面进程饥饿问题，就存在着活跃进程与过期进程之分，活跃进程指向蓝色框，过期进程指向红色框，框中内容是相同的

挑选活跃进程中60号进程，它要被CPU调度，等时间片到了之后，它要从CPU上剖离下来，那此时这个进程它不能再放回到active指针所指向的活跃进程中的60号队列当中，得链入到expired指针所指向的过期进程中的60号队列当中，CPU它调度完成的进程都是要放入到过期进程的对应位置

这样active queue进程会越来越少，expired queue进程会越来越多。直至active queue中的进程全部为0，即nr_active = 0，最后直接swap(&active, &expired)，交换它两指向的内容，重新进行调度

上面才算是真正的Linux内核进程调度算法之大O(1)调度算法。这里还要提到的一点就是：当新进程到来时，如果将新进程放到过期进程当中，目前这个进程就处于就绪状态

很多分时操作系统是支持内核优先级抢占的，比如当前正在运行的是80号进程，新来了一个65号进程，新进程就要给特权，让它尽快运行，那就只能让它插队，那总不能让它插到过期进程的队列当中吧，就直接让它链入到活跃进程的65号队列当中，就开始了优先级的抢占

环境变量

1. 基本概念

• 环境变量（environmentvariables）一般是指在操作系统中用来指定操作系统运行环境的一些参数
• 比如：我们在编写C/C++代码的时候，在链接的时候，从来不知道我们所链接的动态静态库在哪里，但是照样可以链接成功，生成可执行程序，原因就是有相关环境变量帮助编译器进行查找
• 环境变量通常具有某些特殊用途，还有在系统当中通常具有全局特性
• 常见环境变量
  • PATH：指定命令的搜索路径
  • HOME：指定用户的主工作目录(即用户登陆到Linux系统中时，默认的目录）
  • SHELL：它的值通常是/bin/bash

2. 命令行参数

main函数有参数吗？有，argv相当于一张命令行参数表，而argc表示argv指针数组元素的个数

#include<stdio.h>int main(int argc, char* argv[])
{for (int i = 0; i < argc; i++){printf("argv[%d]: %s\n", i, argv[i]);}return 0;
}

再写一段代码，来帮助理解程序如何利用argv命令行参数表实现选项功能

int main(int argc, char* argv[])
{if (argc != 2){printf("Usage: %s [-a|-b|-c]\n", argv[0]);return 0;}const char* arg = argv[1];if (strcmp(arg, "-a") == 0)printf("这是功能1\n");else if (strcmp(arg, "-b") == 0)printf("这是功能2\n");else if (strcmp(arg, "-c") == 0)printf("这是功能3\n");else printf("Usage: %s [-a|-b|-c]\n", argv[0]);return 0;
}

3. PATH 环境变量

可是执行我们自己的命令需要带./，执行系统的命令却不需要，这是为什么呢？

首先你写的二进制指令与系统的指令并没有本质区别，咱们所用的指令本质上在系统里提前预装的二进制程序，你写的二进制程序同样如此，它们两个并没有本质区别。 那为啥一个带路径，一个不带路径呢?

你要知道，要去执行一个程序，那必须先找到它。./code在当前路径下执行可执行程序， 系统指令却不需要带路径的原因是因为系统中存在环境变量

特别不建议将你自己写的二进制程序拷贝到/usr/bin目录下，因为你的二进制文件并没有经过测试，可能会存在bug，可能会污染系统原本的指令池

那系统凭啥就知道执行命令时就去/usr/bin目录下去找呢？因为系统中存在环境变量PATH，这个环境变量在系统中默认是存在的，用来标识一串路径，告诉系统，要去哪些路径下去找二进制可执行文件（系统中搜索指令的默认搜索路径）

4. 环境变量具体操作

介绍两个指令，env：查看系统中所有的环境变量，echo $环境变量名称：具体查看一个环境变量的内容

对于PATH这个环境变量，执行ls指令时，以冒号作为分隔符，从第一个路径去找可执行文件，没找到再依次去后面的路径找

如果想要去修改一个环境变量的内容，直接环境变量名称=具体修改内容，比如PATH=/home/xiao，就直接进行路径覆盖

如果想要在PATH这个环境变量中去新增一个路径，可以PATH=$PATH:绝对路径。那我修改了咋改回来呢？关掉xshell，再重新登录即可（恢复默认的环境变量）