自作OSに挑戦する日記 13日目

自作OS 日記

　「30日でできる！OS自作入門」を読んで分かったことや、とりあえず書いておきたいことなどを書いていきます。
　この本はChapterが1から30まであるので、各チャプター毎に1記事書いていきます。

Chapter 13 「タイマ - 2」

今回やった内容

  • タイマの処理を高速にする

環境

作業記録

　12日目に実装したタイマをもっと高速にします。具体的には以下のような作業をしました。

  • FIFO8 → FIFO32 (!!)
  • キーボードやマウスからの割り込みデータを受け取るFIFOバッファを統一する
  • 複数タイマの管理を連想配列で行うようにする
  • 番兵の設置

FIFO8 → FIFO32

　FIFO8バッファはデータをchar(8バイト)で保持しているため、キーボードやマウスからの割り込みデータをまとめて受け取ろうとするとオーバーフローしてしまいます。ということで、データをint(32バイト)で保持できるようなFIFO32バッファを作ります。

struct FIFO32{
    int *buf;
    int p, q, size, free, flags;
};

キーボードやマウスからの割り込みデータを受け取るFIFOバッファを統一する

　main関数を書き換えます。

// マウス・キーボードなど全ての情報を統べるFIFO32
struct FIFO32 osfifo;
int osfifobuf[128];
fifo32_init(&osfifo, 128, osfifobuf);

while(1){
    io_cti();

    if(fifo32_status(&osfifo) == 0){
        io_sti();
        volatile int wait = 3000;
        while(-- wait);
    }
    else{
        int data = fifo32_get(&osfifo);
        io_sti();

        /* キー表示などの処理 */
    }
}

複数タイマの管理を連想配列で行うようにする

　タイトル通りです！

struct TIMER{
    struct TIMER *next_timer;
    unsigned int timeout, flags;
    struct FIFO32 *fifo;
    unsigned char data;
};

// タイマーに時間をセットする
void timer_set(struct TIMER *timer, unsigned int timeout){
    // 割り込み禁止
    int eflags = io_load_eflags();
    io_cli();

    // 時間セット
    timer->timeout = timer_ctl.count + timeout;
    timer->flags = TIMER_FLAG_USING;

    // LinkedListの適切な位置にTimerを配置する処理
    // 1.先頭に配置する場合
    if(timer->timeout <= timer_ctl.timer_lead->timeout){
        timer->next_timer = timer_ctl.timer_lead;
        timer_ctl.timer_lead = timer;
        timer_ctl.next = timer->timeout;
        io_store_eflags(eflags);
        return;
    }

    // 2.配置する場所を全探索
    struct TIMER *bef_timer, *aft_timer = timer_ctl.timer_lead;
    while(1){
        bef_timer = aft_timer;
        aft_timer = aft_timer->next_timer;
        if(aft_timer == 0) break;

        if(timer->timeout <= aft_timer->timeout){
            bef_timer->next_timer = timer;
            timer->next_timer = aft_timer;
            io_store_eflags(eflags);
            return;
        }
    }
}

　常にソートされた状態でタイマを管理するので、タイムアウトしたタイマを探すという処理が少し早くなりました。

// タイマーチェック
struct TIMER *timer = timer_ctl.timer_lead;
int cnt = 0;
timer_ctl.next = 0xffffffff;
while(1){
    // まだ時間じゃない…
    if(timer->timeout > timer_ctl.count){
        break;
    }

    // タイムアウト
    timer->flags = TIMER_FLAG_ALLOC;
    fifo32_put(timer->fifo, timer->data);
    timer = timer->next_timer;
}

番兵の設置

　連想配列の一番最後にありえないような値を置いといて、連想配列へのタイマの挿入処理が楽になるようにしました。値を二部探索するときに先頭と最後に-INFとINFを入れるみたいなイメージです。

まとめ

　13日目はとことん効率化をしました〜！途中処理速度の計測を行ったのですが、12日目と比べてかなり処理速度が上がっていてたのを確認できたので満足です。