上图是 Linux2.6 内核中进程队列的数据结构，之间关系也已经给各人画出来，方便各人明白。 一个 CPU 拥有一个 runqueue。 Linux真正的调理方式是通过runqueue进行调理的，我们知道进程的优先级范围是根据nice值确定的，而nice值的范围为[-20，19]，以是进程的优先级分40个级别。 如上图，runqueue中有一个数组array，这其实是一个结构体数组，其结构体成员为nr_active,bitmap[5],queue[140]三个，我们先从成员queue[140]开始先容，其140个空间分别对应的是140个优先级，而0~99为实时优先级，这些一般是用在少数注意实时性操纵系统上才会频繁使用的优先级，一般我们所用的操纵系统都注意进程间调用的平衡，以是这里对于前0~99的优先级我们先暂且不淡，而100~139这40位优先级我们称为平常优先级，对应我们nice值的取值范围，以是在调用我们的进程可以根据其优先级60~99分别对应100~139进行分列调用，雷同优先级的进程链接在同一优先级进程的反面 而我们在调用进程时并不是对queue队列进行遍历，而是通过bitmap[5]位图，一个long类型的大小为32比特，5个为160比特，充足进行对queue[140]的标注，我们可以在有进程的位置将二进制对应设置为1，那么在遍历时直接通过bitmap[0~4]进行每次32位的查找，若为0则体现该32位置比特没有进程调用，若不为0则再对32个比特中查找，那么这样我们就可以对位图进行操纵，来确定队列中那个优先级存在进程，这样遍历调理队列时间复杂度基本为O(1)
从上图中我们可以看到结构体数组array其成员是开辟了两个的，其分别为运动队列和过期队列，运动队列保证进程只出不进（根据优先级调用排队等待实行的进程），而过期队列保证进程只进不出（调用过的进程或是新来的进程都进入过期队列进行排队等候），在CUP调用进程时始终调用的是运动队列，但CUP并不是直接去调用运动队列的，而是在runqueue队列中，通过两个指针*active，*expired，进行调理，*active指向运动队列，而*expired指向过期队列，当运动队列中的进程被调理完之后将指针*active和*expired进行交换，那么原先的过期队列就变成了运动队列，原先的运动队列就变成了过期队列，CUP通过指针*active再进行调理，通过指针active和expired的交换我们实现了时间复杂度为O(1)的进程调理。
运动队列 ● 时间片还没有结束的所有进程都按照优先级放在该队列 ● nr_active: 总共有多少个运行状态的进程 ● queue[140]: 一个元素就是一个进程队列，雷同优先级的进程按照 FIFO 规则进行排队调理 , 以是，数组下 标就是优先级 ● 从该结构中，选择一个最符合的进程，过程是怎么的呢？ 1. 从 0 下表开始遍历 queue[140] 2. 找到第一个非空队列，该队列肯定为优先级最高的队列 3. 拿到选中队列的第一个进程，开始运行，调理完成 4. 遍历 queue[140] 时间复杂度是常数！但照旧太低效了 ● bitmap[5]: 一共 140 个优先级，一共 140 个进程队列，为了提高查找非空队列的效率，就可以用 5*32 个 比特位体现队列是否为空，这样，便可以大大提高查找效率 过期队列 ● 过期队列和运动队列结构千篇一律 ● 过期队列上放置的进程，都是时间片耗尽的进程 ● 当运动队列上的进程都被处理惩罚完毕之后，对过期队列的进程进行时间片重新计算 active 指针和 expired 指针 ● active 指针永远指向运动队列 ● expired 指针永远指向过期队列 ● 可是运动队列上的进程会越来越少，过期队列上的进程会越来越多，因为进程时间片到期时不停都存在 的。 ● 不要紧，在符合的时候，只要可以或许交换 active 指针和 expired 指针的内容，就相当于有具有了一批新的活 动进程 在系统当中查找一个最符合调理的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增长，我们称之为进程调理 O(1) 算法
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
