制作团体网站,博物馆网站做的最好的,织梦免费网站模块,如何开个公司网站目录
内核进程调度队列的过程
一个CPU拥有一个runqueue(运行队列在内存)
活动队列(active)
过期队列(expired)
active指针和expired指针
重绘runqueue
linux内核O(1)调度算法
总结
补充知识:
封装链式结构的目的是:
仅使用封装链式结构可以得到全部的task_struct的信…
目录
内核进程调度队列的过程
一个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 i0; i5 ;i)
{if(bitmap[i] 0) continue;//一次可检测32个位置else(bitmap[i]! 0){算法2查找bit位为1的精确位置}} 而算法2可以 利用 n (n - 1) 可以清除最低位的 1 的特性减少循环次数。找到哪个比特位为1, 就是哪个优先级中有pcb #include stdio.hint 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 的起始地址.
