阅读量:0
而我们在调用进程时并不是对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)算法
