Linux：进程调度算法和进程地址空间

✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

文章目录

目录

文章目录

前言

一  进程调度算法

1.1  进程队列数据结构 

1.2  优先级

​编辑

1.3  活动队列

​编辑 1.4  过期队列

1.5  active指针和expired指针 

1.6  进程连接 

二  进程地址空间

2.1  程序地址空间回顾

2.2  进程地址空间

2.2.1 简单了解 

2.2.2  区域划分 

​编辑 2.2.3  理解地址空间上的地址

​编辑 2.2.4  总结

2.3  页表 

2.4  关于地址空间mm_struct

 2.5  为什么要有进程地址空间

​编辑 2.6  怎么维护进程地址空间

总结

---

前言

本篇详细介绍了进一步介绍进程调度算法和虚拟地址空间，让使用者有更加深刻的认知，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

---

一  进程调度算法

1.1  进程队列数据结构 

 

上图是Linux2.6内核中进程队列的数据结构，之间关系也已经给大家画出来，方便大家理解 

一个CPU拥有一个runqueue 

如果有多个CPU就要考虑进程个数的负载均衡问题 

1.2  优先级

●  普通优先级：100～139（我们都是普通的优先级，想想nice值的取值范围，可与之对应！）

●  实时优先级：0～99（不关心） ——实时操作系统使用

 设计一个结构体queue，设计存放队列的数组

1.3  活动队列

●  时间片还没有结束的所有进程都按照优先级放在该队列 

●  nr_active: 总共有多少个运行状态的进程

●  queue[140]: 一个元素就是一个进程队列，相同优先级的进程按照FIFO规则进行排队调度,所以，数组下 标就是优先级！

●  从该结构中，选择一个最合适的进程，过程是怎么的呢？

        1. 从0下表开始遍历queue[140]

        2. 找到第一个非空队列，该队列必定为优先级最高的队列

        3. 拿到选中队列的第一个进程，开始运行，调度完成！

        4. 遍历queue[140]时间复杂度是常数！但还是太低效了！

●  bitmap[5]:一共140个优先级，一共140个进程队列，为了提高查找非空队列的效率，就可以用5*32个 比特位表示队列是否为空，这样，便可以大大提高查找效率！

 1.4  过期队列

●  过期队列和活动队列结构一模一样

●  过期队列上放置的进程，都是时间片耗尽的进程（以及新进程的加入）

●  当活动队列上的进程都被处理完毕之后，对过期队列的进程进行时间片重新计算

1.5  active指针和expired指针 

●  active指针永远指向活动队列 

●  expired指针永远指向过期队列

●  可是活动队列上的进程会越来越少，过期队列上的进程会越来越多，因为进程时间片到期时一直都存在的。

●  没关系，在合适的时候，只要能够交换active指针和expired指针的内容，就相当于有具有了一批新的活动进程！

在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增 加，我们称之为进程调度O(1)算法！ 

1.6  进程连接 

 我们知道，所有的进程都被链表连接，进程可以在运行队列，在阻塞队列，还要在受操作系统管辖的全局队列里，它是怎么做到的呢？

 

二  进程地址空间

2.1  程序地址空间回顾

我们在讲C语言的时候，老师给大家画过这样的空间布局图

我们写一段代码

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
int g_val = 0;
int main()
{pid_t id = fork();if (id < 0) {perror("fork");return 0;}else if (id == 0) { //child,子进程肯定先跑完，也就是子进程先修改，完成之后，父进程再读取g_val = 100;printf("child[%d]: %d : %p\n", getpid(), g_val, &g_val);}else { //parentsleep(3);printf("parent[%d]: %d : %p\n", getpid(), g_val, &g_val);}sleep(1);return 0;
}

我们发现，父子进程，输出地址是一致的，但是变量内容不一样！能得出如下结论: 

●  变量内容不一样,所以父子进程输出的变量绝对不是同一个变量 

●  但地址值是一样的，说明，该地址绝对不是物理地址！

●  在Linux地址下，这种地址叫做 虚拟地址

●  我们在用C/C++语言所看到的地址，全部都是虚拟地址！物理地址，用户一概看不到，由OS统一管理

OS必须负责将 虚拟地址 转化成 物理地址 。 

2.2  进程地址空间

2.2.1 简单了解 

所以之前说‘程序的地址空间’是不准确的，准确的应该说成 进程地址空间 ，那该如何理解呢？ 

讲一个简单的故事 

 一个大富翁（操作系统）有10亿美金，而他有四个私生子，但是四个私生子（进程）都并不知道对方的存在，所以他们都认为大富翁只有他唯一一个儿子，而大富翁告诉他们一旦自己去世了，就把所有的家产留给他，所以每个儿子也都信了，所以大富翁其实给每个私生子都画了一个大饼（进程地址空间）。每个人都认为自己有十亿家产。 但实际上是这些私生子要多少才会给多少（进程需要多少空间操作系统就给多少空间） 

也就是说，对每一个进程，都有一份属于自己的虚拟地址空间（本质是一个内核数据结构对象） 

2.2.2  区域划分 

 2.2.3  理解地址空间上的地址

 内存的最小寻址单位是1字节

首先，我们要明白，指针就是地址，地址就是指针。 而地址是内存单元的编号。所以，一个指针占几个字节，等于是一个地址的内存单元编号有多长。

 2.2.4  总结

2.3  页表 

对于页表来说，不止有虚拟地址和物理地址进行映射，还有页表标记位和读写缺陷等

 

常量被放在区域，这段区域的权限只读

这段代码编译器是能编译过的，所以不是编译器的问题，是操作系统在运行时发现的问题

操作系统是进程的管理者，进程挂了，一定和操作系统有关系 

读写权限就可以帮助我们做检查，比方说当前是常量字符区但是你却想修改，就会被操作系统拦截，该非法请求就不会被发送到物理内存。

标志位就是帮助们判断进程的代码和数据是否被加载到内存中，因为我们知道我们的进程对应的代码和数据是有可能处于挂起状态的（还没加载到内存）。 

惰性加载：其实就是需要多少就加载多少。操作系统对大文件是可以实现分批加载，也就是说当前的进程可能只有PCB在内存中，但是代码和数据可能还没马上加载进来。  

2.4  关于地址空间mm_struct

我们可以用readelf -S 程序名 显示可执行程序的分段

 

 程序编译的时候不存在这种数据

动态开辟，函数栈帧等操作栈区不断进行扩大释放操作

 2.5  为什么要有进程地址空间

 2.6  怎么维护进程地址空间

---

总结

✨✨✨各位读友，本篇分享到内容是否更好的让你理解，如果对你有帮助给个👍赞鼓励一下吧！！
🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！