第13章複雑度O(1)を実現するスケジューリングアルゴリズム

linux 2.6カーネルのO(1)スケジューリングアルゴリズムを参照して,このスケジューリングアルゴリズムを1 KOSで実現した.
このアルゴリズムを実装する主な目的は、次のとおりです.
1、タスクの双方向チェーンテーブル(タイムスライス回転アルゴリズム、しかも双方向チェーンテーブルは削除を増加するのに適しており、アルゴリズムの複雑度はO(1))
2、優先順位ビットマップ(優先順位キューに合わせてアルゴリズムの複雑度はO(1)))
3、優先順位キュー(実は配列であり、配列要素はタスクチェーンヘッダであり、優先順位アルゴリズムに用いられる)
4、2つの実行キュー(active優先キューとexpired優先キュー)(activeキューにあるタスクタイムスライスが切れた場合、タイムスライスが再割り当てされ、expiredキューに挿入されます.activeキューにタスクがない場合、activeとexpiredキューを切り替えます)
5、ffs関数
ffs関数
このアルゴリズムを実現するにはffs(unsigned long word)関数を実現しなければならない.この関数の機能はfind first set bitである.0位から31位までスキャンbitで、1番目のbitが1のビット番号が見つかります.
この関数を実装するには、次の2つの方法があります.
1、アセンブリ命令の使用
2、C言語を使う
Intelアセンブリ
bsf oprd1, oprd2
ワードまたはダブルワードを右から左(0~31ビット)に走査し、オペランドoprd 2のうち1番目のbitが1のビット番号をオペランドoprd 1に送る.参考《IBM-PCアセンブリ言語プログラム設計第2版》p 436
AT&Tアセンブリ
bsfl %eax, %ebx
0~31ビットからeaxをスキャンし、スキャンした最初のbitが1のビット番号をebxに送る.
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;
}