目录
内核进程调度队列的过程
一个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呢?
- runqueue只有一个array , 如果一直有优先级高的进程插入进来,会导致优先级低的进程一直无法运行,导致饥饿问题
- 而两个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; // 二进制表示为 11101 printf("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 的起始地址.
