FreeBSD 版 dynamic ticks の実装ですが、デバイスドライバと callout queue 走査のコードが密結合した prototype 版が動き始めました. これを、VMware Fusion 上で動作させて CPU 使用率の差を見てみます. タイマ割り込み間隔が狭くなると、VMM は細かい間隔でゲストOSに対して割り込みを注入することになり、結果的にホストOSのCPU時間をガシガシ利用しにいきます. 今回のようにタイマ割り込みの間隔を dynamic にすることで、ホストOS の CPU 使用率は interval tick mode に比べて抑えられるはずです. これを検証するため、今回のような実験を行いました. なお、測定には top コマンドの Accumulative mode を用いました.　以下が結果です.

タイマ割り込み間隔を 1000 HZ にしたときは、なかなか良い感じにdynamic ticksが効いてます！HZを1000に設定した場合、VMM(=VMware Fusion)は1秒間に1000回のタイマ割り込みをゲストOSに注入する必要があります. 今回の変更では、この間隔を必要になるまで遅延しているので、CPU使用率がかなり抑えられています. 一方、100HZのときはあまり効いていません. 微妙に CPU 使用率が抑えられていますが、誤差の範囲でしょう. これは、元々のtick間隔が長くなるためにするためだと考えられます. ちなみに、FreeBSD 上の top コマンドやネットワークはちゃんと動作しているので、カーネルが要求したタイマはちゃんと発火している模様です.

残りの懸念事項は以下の通りです :

グローバル変数がたくさん！
callout queue を走査するため、若干割り込みハンドラが長くなってしまうのがどういった影響を与えるのか
dynamic tick mode と interval tick mode の switch を行っていない. date コマンド打って日時を確認している感じだと特に問題なさそうだが、真面目に検証する必要がある.
デバイスドライバと callout queue が密結合している.
性能劣化は生じないか.
Theo さんに教えてもらった論文の話(プロファイリング)をまだ考慮していない.
polling しているドライバへの影響( koie さんに教えて頂きました. ありがとうございます！)

いい加減だとは言え、一応動いているし効果も出ているので、とりあえず Freebsd-hackers 辺りに投げてみようかな.

2010/03/30 追記 : Freebsd-hackers に投げてみました. hacker の皆様の返信待ちです. ドキドキ.

2010-03-15

AsiaBSDcon の Work-in-progress talk にて "First step for dynticks in FreeBSD" というタイトルで発表してきました

FreeBSD BSD

AsiaBSDcon の WIP( Work-in-progress ) talk のセッションで発表してきました. スライドは
First step for dynticks in FreeBSD
にあります.

内容としては、"Linux などに導入されている tickless 機構を FreeBSD に入れてみたらどうか"という内容で、実際に callout queue を走査して次のタイマイベントをゲットするところまではできたよ、という発表をしました.

実は、最初(少なくとも AsiaBSDcon 初日、DevSummit の時)は WIP で発表するつもりなんて全くありませんでした. DevSummit あたりで、 FreeBSD の tickless 化についてちょっとだけお話できれば良いかなぁくらい. しかし、初日の DevSummit の中で Alexander Mortin さんが CPU の Power State の話をし始めたときがあったので、私がウザいくらい喰いついて(笑)、色々教えてもらいました. 具体的には、彼の使っている laptop PC では、Processor が C4 State に入る前に起きてしまうらしく、それ以上深く sleep できないとのこと. 需要はあるんだなぁということで、とりあえず tickless 化に不可欠な Callout queue の scan ルーチンを実装しました.

土曜日の時点で実装状況を id:syuu1228 さんに Skype で伝えたところ、WIP で発表したらどうかと提案が. せっかくなんで、当日WIPの申し込みをして、参戦しました！

WIP 自体は、いざ始まってみるとかなりガチな内容でビックリ！

お話をしていた方々も、 Alexander Mortin さんや OpenBSD の開発指揮をとっている Theo さんで、こんな中で発表していいのか...と結構ガクガクブルブルしていましたが、適当な英語で最後まで突っ走りました(笑

色々な方と懇親会でお声をかけて頂いて、割とやりたいことは伝わっていたみたいで、ホントよかった！あと、Theo さんと Dynticks について色々ご意見頂けました！後で教えて頂いたペーパー読まないとね.　次の目標は、15日以内に FreeBSD のコミュニティにプロトタイプのパッチを投げることです. 頑張るぞっ！

最後に、焚きつけてくれたid:syuu1228 さんと、貴重な機会を与えてくださった @Hiroki_Sato さん、そしてお話を聞いてくれた全ての方に感謝です. ありがとうございました:D

2010-01-13

Keynoteで吐き出した画像ファイルをepsに一括変換するスクリプト

Keynote LaTex

画像をKeynote で作ると、論文用に作った画像を発表にもそのまま利用できてお得. Keynote からはき出せるファイル形式は tiff, png, jpeg のみなので、これを LaTex で認識できるよう eps 形式に変換してやる必要がある. UNIX 系のOS では、ImageMagick という画像変換パッケージがあり、この中に入っている convert コマンドを利用すると画像ファイルを eps に変換できる*1. Mac OS X の場合、ImageMagick は MacPorts を通してインストールできる.

port install ImageMagick

使い方は

convert a.tiff a.eps # a.tiff が入力ファイル, a.eps が出力ファイル

が、Keynote から吐き出した画像ファイルを毎回コマンド打って変換するのはなんだか面倒.
Keynote から吐き出した tiff ファイルを eps に変換するには、以下のようなコマンドを実行すればよい.

for f in *.tiff; do convert $f `echo $f | sed s/tiff/eps/g`  ; done

tiff じゃない拡張子のファイルを扱う場合は、"tiff"の部分を変更して使うこと.

余白部が邪魔

という場合は、-trim オプションを利用する.

for f in *.tiff; do convert -trim $f `echo $f | sed s/tiff/eps/g`  ; done

Makefile 中で使う場合

このスクリプトを Makefile に書く場合は、シェル変数へのアクセスが $$に変わることに注意.

eps:
    for f in *.tiff; do convert $$f `echo $$f | sed s/tiff/eps/g`  ; done
clean:
    rm -f *eps

*1:UNIX 系の OS に convert というツールがバンドルされているかのように記述してあったので修正. random_oracle さん、ありとうございました.

2010-01-11

カーネルタイマは何故リストで管理されているのか

Linux

カーネルタイマは何故リストで管理されているのか、という理由がわかった気がするのでメモ. カーネルタイマは expires (点火する時間)で5段階に場合わけされて管理されているが、ロックはこの5段階ごとに保持されている. 何故タイマ毎にロックをしないのだろう? その方がロックの粒度が小さくなり、並列度が増すはずだ.
仮に timer_list 構造体が spinlock_t lock 持っていたとして、カーネル側の実装は以下のようにすればよさげに見える.

/* kernel side functions */
void __run_timers(void)
{
    while( timer_list_has_timers(lists) ){
        timer = get_next_timer();
        fn = timer->function;
        data = timer->data;
        ...
        spin_lock_irq( &timer->lock );
        detach_timer( timer );
        fn( data );
        spin_unlock_irq( &timer->lock );
    }
}

int add_timer( struct timer_list *timer )
{
    spin_lock_irqsave( &timer->lock, flags );
    ...
    add_timer_internal( timer );
    ...
    spin_unlock_irqsave( &timer->lock, flags );
}

int del_timer( struct timer_list *timer )
{
    spin_lock_irqsave( &timer->lock, flags );
    ...
    detach_timer( timer );
    ...
    spin_unlock_irqsave( &timer->lock, flags );
}

でもこれではダメで、Linux のタイマのコールバック関数の中には、呼び出しの契機となったタイマに対して破壊的な操作( free されても良いように！ ) 配慮されている:

/* kernel timer client side functions */
void timer_handler(unsigned long data)
{
    struct timer_list *timer = data;
    ...
    timer->expires = jiffies + 3*HZ;
    kfree( mytimer );
}

void timer_start(void)
{
    struct timer_list *timer;
    timer = kmalloc( GFP_KERNEL, sizeof(struct timer_list) );
    init_timer( timer );
    timer->function = timer_handler;
    timer->data = timer;
    timer->expires = jiffies + 3*HZ;

    add_timer( timer );
}

add_timer, del_timer などのカーネルタイマAPIは、EXPORT_SYMBOLされており、カーネルモジュールからも呼び出しを行うことができる. よって、(カーネルタイマの実装を知らない)プログラマがカーネルタイマを使ってプログラムを書くことを想定すると、「コールバック関数内ではタイマを触らないでください」という暗黙の制約はあまりよろしくない.
これをできるようにするためには、Linux カーネル側で、「一度タイマをコールバックしたらもう触らない」という風にすれば良い. すると、__run_timersを以下のように修正すればよさげである.

void __run_timers(void)
{
    while( timer_list_has_timers(lists) ){
        timer = get_next_timer();


        spin_lock_irq( &timer->lock );
        ...
        fn = timer->function;
        data = timer->data;
        detach_timer( timer );
        spin_unlock_irq( &timer->lock );
        ...
        fn ( data ) ;
        ...
    }
}

実際現在のLinux カーネル(2.6.27.23)では「一度タイマをコールバックしたらもう触らない」ようにしている. 上記のコードとの違いは、ロックを保持しているのがタイマ毎か、点火する時間で分けた5段階のリスト毎に保持しているか、という辺りのみである*1.
さて、これはうまく動くんだろうか? 結果からいうと、ダメだ. この場合、以下のようなクリティカルセクションがロックから露出してしまっている:

__run_timers の spin_unlock_irq の直後にdel_timerなどタイマへのポインタを参照する関数が呼ばれた場合.

このタイミングでタイマのステートを変更されると、意図しない挙動になる可能性がある. 例えば、 (カーネルが)コールバックしたハンドラの中で行われる処理が大変重く、その途中で別のスレッドから del_timer が発行されたとしよう. del_timer を処理中に、ハンドラ内で kfree されると、del_timer へのポインタが無効になり、危険である.
この問題を解決するには、コールバックを行っている最中にロックを保持しておけばよい. が、今度は最初に述べたような問題が生じてしまう.

この問題が生じている原因と解決策

上記例で述べた問題の原因は、

セマンティクス(後方互換)の維持
カーネルタイマ1つ1つのステートが変更される可能性がある区間にロックが必要

という2つを同時に満たそうとしたために発生している.
これを解決するにはタイマ毎ではなく、もう一段大きな粒度でロックする必要がある. Linux では、これが時間で区切られた5段階のリストであった、ということらしい.

*1:そういう風に、擬似コードを書いているつもりですが、何かまずい点があったら教えてください.^^;