第13章 实现复杂度O(1)的调度算法

参考了linux 2.6内核的O(1)调度算法,在1KOS中实现了该调度算法。

实现该算法的主要是靠:

  1. 任务的双向链表(时间片轮转算法,而且双向链表适合增加删除,算法复杂度为O(1))
  2. 优先级位图(跟优先级队列配合,算法复杂度为O(1))
  3. 优先级队列(其实是数组,数组元素是任务链表头,用于优先级算法)
  4. 两个运行队列(active优先级队列和expired优先级队列)(在active队列上的某个任务时间片用完时,会重新分配时间片,然后插到expired队列上。当active队列上没有任务时,切换active和expired队列)
  5. ffs函数

ffs函数

实现该算法必须实现ffs(unsigned long word)函数,这个函数的功能是find first set bit。从第0位到第31位为扫描bit,找到第一个bit为1的位号。

实现该函数有两种方法:

  1. 使用汇编指令
  2. 使用C语言

intel 汇编中

bsf oprd1, oprd2

从右向左(0~31位)扫描字或双字,把操作数oprd2中第一个bit为1的位号送到操作数oprd1上。可参考《IBM-PC汇编语言程序设计 第2版》p436

AT &T 汇编

bsfl %eax, %ebx

从0~31位扫描eax,把扫描到的第一个bit为1的位号送到ebx上。

使用C语言实现(使用二分法)

<

pre name=”code” class=”c”> static inline unsigned long __ffs(unsigned long word) { unsigned long b = 0, s; s=16; if(word<<16 != 0)s=0; b+=s; word>=s; s=8; if(word<<24 != 0)s=0; b+=s; word>=s; s=4; if(word<<28 != 0)s=0; b+=s; word>=s; s=2; if(word<<30 != 0)s=0; b+=s; word>=s; s=1; if(word<<31 != 0)s=0; b+=s; return b; }

Leave a Reply

Your email address will not be published. Required fields are marked *