✨个人主页： 熬夜学编程的小林
💗系列专栏： 【C语言详解】 【数据结构详解】【C++详解】【Linux系统编程】
目录
1、进程空间的地址
1.1、基本概念
1.2、代码分析
1.3、如何理解地址空间
1.4、进一步理解页表和写时拷贝
1.5、进一步理解虚拟地址
2、内核进程调度队列
2.1、一个CPU拥有一个runqueue
2.2、优先级
2.3、活动队列
2.4、过期队列
2.5、active指针和expired指针
2.6、总结
1、进程空间的地址
1.1、基本概念
- 程序段(Text):程序代码在内存中的映射，存放函数体的二进制代码。
- 初始化过的数据(Data):在程序运行初已经对变量进行初始化的数据。
- 未初始化过的数据(BSS):在程序运行初未对变量进行初始化的数据。
- 栈 (Stack):存储局部、临时变量，函数调用时，存储函数的返回指针，用于控制函数的调用和返回。在程序块开始时自动分配内存,结束时自动释放内存，其操作方式类似于数据结构中的栈。
- 堆 (Heap):存储动态内存分配,需要程序员手工分配,手工释放.注意它与数据结构中的堆是两回事，分配方式类似于链表。
1.2、代码分析
地址空间图
讲解进程地址空间之前，我们先编写一段C语言程序。
#include<stdio.h>
#include<unistd.h>
int g_val = 100;
int main()
{printf("father is running,pid:%d,ppid:%d\n",getpid(),getppid());pid_t id = fork();if(id == 0){// childint cnt = 0;while(1){printf("I am child process,pid:%d,ppid:%d,g_val:%d,&g_val:%p\n",getpid(),getppid(),g_val,&g_val);sleep(1);cnt++;if(cnt == 3){g_val = 300;printf("I am child process,change %d -> %d\n",100,300);}}}else{// fatherwhile(1){printf("I am father process,pid:%d,ppid:%d,g_val:%d,&g_val:%p\n",getpid(),getppid(),g_val,&g_val);sleep(1);}}return 0;
}测试结果
从上面的测试结果我们可以看到发现，父子进程，输出地址是一致的，但是变量内容不一样！能得出如下结论:
- 变量内容不一样,所以父子进程输出的变量绝对不是同一个变量。
- 但地址值是一样的，说明，该地址绝对不是物理地址！
- 在Linux地址下，这种地址叫做 虚拟地址。
- 我们在用C/C++语言所看到的地址，全部都是虚拟地址！物理地址，用户一概看不到，由OS统一管理。
OS必须负责将 虚拟地址 转化成 物理地址 。
具体如下图：
上图分析：使用系统调用接口创建新的进程时，fork后的数据代码，父子进程将会同时执行，同时增加新的进程控制块(tast_struct)，父子进程通过刚开始相同的页表指向相同的物理空间，其所使用的进程地址空间对应的位置也是相同的，父子进程指向同一个g_val，因此，父进程和子进程对应的g_val的地址是相同的，但是，当子进程尝试修改g_val变量时，为保证进程的独立性，操作系统识别到当前子进程通过页表找到g_val，想修改g_val，此时，操作系统会重新开辟一段空间，将上述值拷贝下来，修改映射关系，因此使用不同的物理内存地址，互不影响，互相独立。
为什么要写时拷贝呢?写时拷贝的效率会不会很低呢？
通过调整拷贝的时间顺序，达到有效节省空间的效果。
写时拷贝的效率并不会很低，因为如果不写时拷贝，需要将父进程的所以数据拷贝一份，而写时拷贝只需要将需要修改的数据拷贝一份，最坏情况也是跟不写时拷贝的效率一样。
可不可以直接将父进程的数据全部拷贝到新的空间呢？
可以，但是没有必要这么做。
因为子进程是能够访问父进程的数据的，大部分情况下，是不需要进行全部拷贝过来，那样太浪费空间了；我们通常是要进行写入的时候，OS才会要写入的变量复制一份，重新开一个大小一样的空间，在新开的空间内写入数据，再将新空间的地址交给页表。这是按需申请。通过调整拷贝的时间顺序，达到节省空间的目的。
1.3、如何理解地址空间
什么是划分区域？
举个例子，如果需要将桌子划分为两块该如何划分，假设桌子长度为100厘米。我们可以将桌子划分为左边区域和右边区域，左边区域为[1,50]，右边区域为[50,100]。用计算机语言描述则可以通过两个结构体来描述，一个描述区域宽度，一个描述哪个区域。
struct area
{int start;int end;
}
struct desktop
{struct area left;struct area right;
}struct desktop d;
//me
d.left.start=1;
d.left.end=70;
//同桌
d.right.start=70;
d.right.end=100;源代码
地址空间本质就是内核中的一个结构体对象。
为什么要有地址空间？
1.将无序变成有序，让进程以统一的视角看待物理内存以及自己运行的各个区域。
2.进程管理模块和内存管理模块进行解耦。
3.拦截非法请求---对物理内存的保护。
1.4、进一步理解页表和写时拷贝
页表还有一些其他的作用，1、判断该物理地址是否在内存中(进程挂起情况) 2、识别rwx权限(常量区不能修改值情况)
当操作系统判断出地址不在内存中时还会做进一步判断：
- 1、是不是数据不在物理内存
- 2、是不是数据需要写时拷贝
- 3、如果都不是才能异常处理
写时拷贝
父子进程创建时使用相同的虚拟地址，而进行修改时，经操作系统识别，重新复制一份，并开辟新的空间，经过页表映射的是不同的物理地址，此时修改的是不同的物理地址的数据，其虚拟地址不受影响。
写时拷贝（Copy-on-write，简称COW）是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的。此作法主要的优点是如果调用者没有修改该资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。
1.5、进一步理解虚拟地址
在最开始的时候，进程地址空间和页表里面的数据从哪里来的呢？
是从可执行程序内部来的。程序里面本身就有地址！！！这个地址就是虚拟地址(逻辑地址)。我们的可执行程序里面已经没有变量名和函数名，都变成了地址；
补充：
objdump -S 可执行程序 # 查看反汇编
objdump -S myprocess > test.s # 将反汇编内容重定向到test.s文件测试结果
结论：
创建一个进程，就会创建一个task_struct，地址空间，页表和物理内存。
2、内核进程调度队列
上图是Linux2.6内核中进程队列的数据结构，之间关系也已经给uu们画出来，方便大家理解 。
2.1、一个CPU拥有一个runqueue
- 如果有多个CPU就要考虑进程个数的负载均衡问题
2.2、优先级
- 普通优先级：100～139（我们都是普通的优先级，想想nice值的取值范围，可与之对应！）
- 实时优先级：0～99（不关心）
2.3、活动队列
- 时间片还没有结束的所有进程都按照优先级放在该队列
- nr_active: 总共有多少个运行状态的进程
- queue[140]: 一个元素就是一个进程队列，相同优先级的进程按照FIFO规则进行排队调度,所以，数组下标就是优先级！
- 从该结构中，选择一个最合适的进程，过程是怎么的呢？
- 1. 从0下表开始遍历queue[140]
- 2. 找到第一个非空队列，该队列必定为优先级最高的队列
- 3. 拿到选中队列的第一个进程，开始运行，调度完成！
- 4. 遍历queue[140]时间复杂度是常数！但还是太低效了！
- bitmap[5]:一共140个优先级，一共140个进程队列，为了提高查找非空队列的效率，就可以用5*32个比特位表示队列是否为空，这样，便可以大大提高查找效率！
2.4、过期队列
- 过期队列和活动队列结构一模一样
- 过期队列上放置的进程，都是时间片耗尽的进程
- 当活动队列上的进程都被处理完毕之后，对过期队列的进程进行时间片重新计算
2.5、active指针和expired指针
- active指针永远指向活动队列
- expired指针永远指向过期队列
- 可是活动队列上的进程会越来越少，过期队列上的进程会越来越多，因为进程时间片到期时一直都存在的。
- 没关系，在合适的时候，只要能够交换active指针和expired指针的内容，就相当于有具有了一批新的活动进程！
2.6、总结
在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增加，我们称之为进程调度O(1)算法！