トップ «前の日記(2004年08月10日) 最新 次の日記(2004年08月12日)» 編集
2003|01|02|03|04|05|06|07|08|09|10|11|12|
2004|01|02|03|04|05|06|07|08|09|10|11|12|
2005|01|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|10|12|
2009|02|03|06|07|10|11|12|
2010|01|02|03|04|07|09|10|11|12|
2011|01|03|04|05|06|07|08|10|
2012|01|06|08|09|10|12|
2013|01|02|03|04|07|09|11|12|
2014|01|03|04|05|06|09|
2015|04|
2016|01|08|
ここは旧えびめもです。えびめも2に移行します(2016/12/1)

2004年08月11日

Linux

先日linuxのドライバを書くときの注意点を書きました。これについてご質問のメールを頂戴いたしましたので自分の理解の助けも含めて、まとめを書いてみることにします。たまには頭を整理するために最新のカーネルを見てみるのも大切です。昔見たコードと今のコードはずいぶんと違っていますし。さて、今回のデータモデルは前回と同じですが
割り込みルーチンが受信データを受信バッファに格納し、
ユーザープロセスが受信バッファからデータを取り出す。
という流れとします。まず先日の話を読んでください。

割り込みルーチンの記述は略しますがユーザープロセスの流れは以下のようになります。ドライバのread()メソッドの中で

if( input_point == output_point){                // もしバッファにデータが無ければ
        // here is クリティカルセッション
        interruptible_sleep_on(&Q);              // データ到着まで待ち列Qでsleep
}
read_from_buffer(&buf);                          // データをバッファから取り出す。
プロセスはデータが無ければデータの到着までsleepに入るのが普通です。割り込みルーチンはデータをバッファに格納してwakeupします。ちなみにuITRON4のwup_tskと違ってLinuxのwakeupは、sleepしていなかった場合は空振りするだけです。ですからなにも考えずに常にwakeupを記述して問題ありません。

さて先日お話しましたように 『here is クリティカルセッション』の箇所がレースコンディションになります。
if文でデータが無い事を確認し { カッコの中に進んだところでデータが到着し、割り込み処理を行ったとします。そこでのwakeupは空振りに終わります。そして既にデータは到着しているにもかかわらず sleep に入ってしまい、起こされなくなります。下手をするとデッドロックが起きます。通常は次のデータの到着で割り込みが入り、sleepから起きますが、例えばキーボードデバイスだったとするなら、ユーザーがAと押したときに無反応で、あれ?と思ってBを押したときに連続してABと2文字入力されるといった不具合が発生します。よくないですね。

これの対応ですが、一番簡単に思いつくのは割り込みをとめてしまうことしょう。

cli();						 // 割り込み禁止
if( input_point == output_point){                // もしバッファにデータが無ければ
        sti();                                   // 割り込み許可
        // here is クリティカルセッション
        interruptible_sleep_on(&Q);              // データ到着まで待ち列Qでsleep
}else{
        sti();                                   // 割り込み許可
}
read_from_buffer(&buf);                          // データをバッファから取り出す。
しかしこれでは対策したことになりません。sti()によって割り込み許可されたときに、保留されていた割り込みが実行されるので最初の例と比べて何の対策にもなっていません。それにドライバでcli()割禁を使うのはお行儀がよくありません。

ではsti()をとったら何が起こるでしょうか?つまり割り込み禁止(cpuロック状態)で sleep に入ってみます。常識的に考えると、cpuロックの状態でsleepに入ったら起してくれる人が居ないのでデッドロックになりますよね。で、

論よりRUN
ということで実験してみると・・・
cli();                                           // 割り込み禁止
if( input_point == output_point){                // もしバッファにデータが無ければ
        interruptible_sleep_on(&Q);              // cpuロックのままsleepしてみる
}
read_from_buffer(&buf);                          // データをバッファから取り出す。
先ほどこれを実験してみましたが、意外なことに?今のバージョンのlinuxでは特に問題が起きませんでした。将来はどうなるかわかりませんし、cpuロック状態でsleepするなんて、OS的にお行儀がよくないに変わりありませんが、意外なことに大丈夫でした。じゃ、どーしてかなということで、linux-2.4.24のinterruptible_sleep_on()関数のソースを見てみます。実際には多数のマクロが組み合わさっていますが読みやすいように展開しました。
void interruptible_sleep_on(qwait_queue_head_t *q)
{
        unsigned long flags;
        wait_queue_t wait;
 
        init_waitqueue_entry(&wait, current);
        current->state = TASK_INTERRUPTIBLE;  //タスク状態をsleepということにする
                                              //寝に入るつもりだが実際にはまだ寝てない
        __add_wait_queue(q, &wait);           //自プロセスをウェイトキューにつなぐ
        schedule();                           //スケジューラを呼び出してsleepする
        __remove_wait_queue(q, &wait);        //自プロセスをウェイトキューから外す
}
説明はほとんどコメントに書きました。
current->state = TASK_INTERRUPTIBLE は自プロセスを休眠にする"つもり" を意味しています。マルチタスクOSにおいて、sleepの正体は何かというと、『他のプロセスにCPUを譲ること』ですから、実際にsleepに入るのはいつかというと、schedule() を呼び出し他のプロセスにCPUを譲って、結果として自プロセスはsleepになったということになります。

ではさらに奥の schedule() 関数を 割り込み禁止状態で呼び出したとして、見ていきます。

asmlinkage void schedule(void)
{
        struct schedule_data * sched_data;
        struct task_struct *prev, *next, *p;
        struct list_head *tmp;
        int this_cpu, c;
 
        prev = current;
        this_cpu = prev->processor;
 
        if (unlikely(in_interrupt())) {
                printk("Scheduling in interrupt\n");
                BUG();
        }
 
        release_kernel_lock(prev, this_cpu);
release_kernel_lock()関数は、以下のようなマクロです。
#define release_kernel_lock(task, cpu) \
do { \
        if (task->lock_depth >= 0) \
                spin_unlock(&kernel_flag); \
        release_irqlock(cpu); \
        __sti(); \
} while (0)
おや、ここで sti()が実行されました。すなわち、schedule() 関数はそこまでの割り込みモードがどうなっているかに関係なく、割り込み許可モードに移行するのだということが分かります。(そりゃーディスパッチャですしね)これでデッドロックが起こらない理由は分かりました。

さて、このsti()が実行されたタイミングで保留されていた割り込みが実行されたらどうなるか考えて見ます。思い出してください。自プロセスはまだ実行中ですが current->state = TASK_INTERRUPTIBLE すなわち sleep になっていますし、しかも自プロセスをウェイトキュー(待ち列)につなぐ処理までは完了しています。ここで割り込みルーチンが呼ばれて wakeup が実行されます。wakeupは待つ列ににつながっているプロセスを全て TASK_RUNNNINGの状態に戻します(待ち列からは外しません)。ということで割り込みルーチンが終わって戻ってきたときには TASK_RUNNINGの状態になっています。そして schedule()関数のさらに先へと進みます。schedule()関数内部では、他のプロセスへのディスパッチが起こるかもしれませんが、自プロセスはTASK_RUNNINGですから他のランニングプロセスを一周して自分のところにも帰ってきます。そして schedule()関数を抜けます。続いての処理は見てのとおりで待ち列から自分を外し、復帰します。問題となる点は見当たりませんでした。

以上のポイントを整理すると、

1. if文で寝るか寝ないかの条件判断
    ↓
2. TASK_INTERRUPTIBLEにする
    ↓
3. 待ち列につなぐ
    ↓
4. schedule()を呼び出す
この区間がクリティカルセッションということになり、割り込みルーチンに割り込まれたら困る区間ということになります。今回の例のようにcli()で割り込み禁止にしてしまうのも方法でしょう。しかしcli()つまりcpuロックはOSにとってお行儀がよくありません。cpuロックはプリエンプションを阻害し、タスクディスパッチのレイテンシが増してしまう結果になります。といっても実際には現状のlinux-2.4カーネルは、カーネル空間走行中は非プリエンプティブですけどね。これは逆説的ですが、ドライバでcli()〜sti()。正しくは save_and_cli()〜restore_flags()で割り込み制御をしているドライバがあまりに多くて、linuxをリアルタイム化するのにウンザリしてしまったりするのです。

cli()を使っていれば、最初の使っていない例よりはだいぶプロっぽい書き方です。『分かっている人』に見えますし、ガツンとcpuロックするなんて

男っぽくてワイルド
かもしれませんが、ちとワイルドすぎるので、もっと洗練されてるイケメン青年実業家のような
女が惚れるような
コードを考えてみましょう。
上のフローでの、if文での寝るか寝ないかの条件判断位置を逆にしてみると
1. TASK_INTERRUPTIBLEにする  (寝るつもり。という事ね)
    ↓
2. 待ち列につなぐ
    ↓
3. if文で寝るか寝ないかの条件判断
    ↓ 4. 寝るならschedule()を呼ぶ。他のプロセスに処理が回りsleepということになる
5. 待ち列から外す
    ↓
6. TASK_RUNNINGにする
としてみるとどうなるでしょう?実はこれで問題が解決します。任意の時点で割り込みルーチンに割り込まれても大丈夫です。よーくみてください。
3.寝るか寝ないかの条件判断以前に割り込みが入ったならば、if文での結果『寝ない』という事になりますから、1.2.の処理は 5.6. の処理で後片付けされますので何も起きません。3.の条件判断直後に割り込みが入ったときは、割り込みルーチンのwakupによって、自プロセスのstateが TASK_INTERRUPTIBLE -> TASK_RUNNING に戻されます。そして schedule()に入りますので寝ません。ほら、cli()なしでも良くなりました。残念ながらトリビアと違って合コンのネタには適しませんが覚えておいて損はありません。

実際にはlinuxには上記の動作を行うためのマクロが用意されています。以下のように使います。

wait_event_interruptible(待ち列Q, 条件);
「条件が真になるまで」寝て待ちます。言い換えれば「偽のあいだ」寝て待ちます。最初のプログラムを書き換えると次のようになります。
wait_event_interruptible(Q,(input_point != output_point)); // (input_point != output_point)になるまで寝る
read_from_buffer(&buf);                                    // データをバッファから取り出す。
この辺は結構高度な話題で上記の説明だけでは理解が難しいかもしれませんが、ドライバを書くことになりましたらプロセスの動きは頭のなかでイメージをもっていなければなりませんね。興味をもたれた方は 08/27(金)に東京CQ出版社でセミナーをやりますので、図付き・デモ付き・踊り付き?で解説しますので来てくださいね。お一人様\13,000です(宣伝)。と書こうしましたら満席でした。あらら。SH-Linuxのセミナーもやります。
http://it.cqpub.co.jp/eSeminar/Default.asp?NV=CCM&CI=E01-0029
こっちではここまで高度な話をする時間は無いかなと思います。(踊りは冗談ですけど)