内核进程调度队列(linux的真实调度算法) ─── linux第13课

目录

内核进程调度队列的过程

一个CPU拥有一个runqueue(运行队列在内存)

活动队列(active)

过期队列(expired)

active指针和expired指针

重绘runqueue

linux内核O(1)调度算法

总结

补充知识:

封装链式结构的目的是:

仅使用封装链式结构可以得到全部的task_struct的信息的原理:

---

内核进程调度队列的过程

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

一个CPU拥有一个runqueue(运行队列在内存)

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

在上图我们可以看到,runqueue中含有两个struct queue数据结构  array[0]是活跃队列和array[1]是过期队列

struct queue队列数据结构包含了nr_activce  bitmap[5] queue[140]三个结构

        queue队列中的

•         nr_active是哈希桶中task_struct的数量      功能:控制是否swap(下面讲了)
•         bitmap[5]充当位图           功能:更快找到下一个要调度的进程在哈希桶的哪个位置
•         queue[140]是一个哈希桶, 在100到139下标中分别存储链式的进程PCB(task_struct) ,正好对应了40种进程优先级.

活动队列(active)

• 时间片还没有结束的所有进程都按照优先级放在该队列
• nr_active: 总共有多少个运行状态的进程
• queue[140]: 一个元素就是一个进程队列，相同优先级的进程按照FIFO规则进行排队调度,所以，数组下标就是优先级！

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

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

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

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

4. 遍历queue[140]时间复杂度是常数！但还是太低效了！因此设计了bitmap[5r]

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

过期队列(expired)

• 过期队列和活动队列结构一模一样
• 过期队列上放置的进程，都是时间片耗尽的进程
• 当活动队列上的进程都被处理完毕之后，对过期队列的进程进行时间片重新计算

active指针和expired指针

active指针永远指向活动队列

expired指针永远指向过期队列

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

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

重绘runqueue

 下图重新描绘了runqueue 

此时active是array[0]的首地址 ,expired 是array[1]的首地址

为什么runqueue需要两个array呢?

1.  runqueue只有一个array , 如果一直有优先级高的进程插入进来,会导致优先级低的进程一直无法运行,导致饥饿问题
2. 而两个array可以解决问题:  一个array结构叫做actice队列  ,另一个叫做expired队列,归定cpu只能从active队列中,选取task_struct运行其对应的程序 , 新进程和时间片到了的进程的task_struct 按照优先级加在expired队列中,等到active队列中pcb的数量为0时 ,交换两个队列指针(swap(&active,&expried)) 省去了将pcb重新插入的步骤.

linux内核O(1)调度算法

如何进行快速算法调度(快速找到下一个task_struct),linux设计了一种O(1)算法

4*8*5 =140 

而bitmap[5]正好是5个int值

可以利用类似这种算法

for(int i=0; i<5 ;i++)
{if(bitmap[i] == 0) continue;//一次可检测32个位置else(bitmap[i]!= 0){算法2查找bit位为1的精确位置}}

而算法2可以 利用 n & (n - 1) 可以清除最低位的 1 的特性，减少循环次数。找到哪个比特位为1, 就是哪个优先级中有pcb

#include <stdio.h>int countBits(int num) 
{int count = 0;while (num) {num &= (num - 1);count++;}return count;
}int main() {int num = 29; // 二进制表示为 11101printf("Number of 1 bits in %d is %d\n", num, countBits(num));return 0;
}

总结

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

补充知识:

进程的task_struct都用链表链接

task_struct可在运行队列 , 阻塞队列中

linux的链式结构是双链结构

task_struct中将双链结构进行了封装如下图struct node 

封装链式结构的目的是:

如果进程处于某个链式结构中, 只需将task_struct中的链式结构的next和prev填充就行, 而且使得task_struct还可以同时处于多个链表中.

仅使用封装链式结构可以得到全部的task_struct的信息的原理:

下图讲解了仅使用封装链式结构可以得到全部的task_struct的信息

先得到链式结构的偏移量,再找到task_struct的首地址即可

类似使用offset(type ,x)

假设structA从0地址存储, 其实大概率不可能存储到这 , 只是为了得到C的偏移量,再用真实C的地址来找structA 的起始地址.