Linuxカーネルのタイマ管理の実装方法を調べています。


webで調べてタイマのに動作概要、関数名などは分かったのですが、もっと突っ込んだ実装レベルのタイマ処理について調査したいと思っています。

タイマ処理は処理が行われる順に並んでlist構造になっているようですが、例えばある処理をある時間に実行しなければならい状態が発生したときにlistに追加する時にlistの最初から全てなめてその処理が追加されるべき場所に追加されるのか、それとも最初から全てなめるのは時間がかかるので、どこに追加すべきかというのは別の方法で(検索ツリー等)やっているのかといった所を知りたいと思ってます。

Linuxカーネルのバーション2.4か2.6で知りたいです。

本来は関数名も分かっているのだからソースを見て解析できればいいのですが、プログラム言語はほとんど理解出来ない上、この調査結果を報告する期限が決まっていて、今からプログラム言語を勉強している時間がありません。

よろしくお願いいたします。

回答の条件
  • 1人5回まで
  • 登録:2006/09/19 11:12:37
  • 終了:2006/09/20 12:27:27

ベストアンサー

id:furutanian No.1

furutanian回答回数112ベストアンサー獲得回数142006/09/19 12:47:51

ポイント80pt

基本的なポイントですが、Linuxのスケジューラはプロセスを「処理が行われる順に並んだlist構造」で扱っていません。プロセスはlist構造で管理されていますが、それは処理順に並べられているわけではないです。

また「ある処理をある時間に実行しなければならない状態が発生」しても、特別な処理が行われることはありません。処理順はプロセスのスケジューリングポリシーと優先度でしか制御できません。LinuxはリアルタイムOSではないため、上記のような事態を確実に処理するようにはできていません。LinuxベースのリアルタイムOSであるRedHawkLinuxはスケジューラがそれ用に改造されており、一般的なLinuxとは別物になっています。

http://www.ccur.co.jp/realtime/redhawk.html

ちょっと脱線しましたが、スケジューリングポリシーと優先度によるスケジューリングは、乱暴に言えばポイント制みたいなもので、OSがプロセススイッチをするたびに、ポイントを足したり引いたりしながらlistをなめ、ポイントの高いものを優先的に実行すると考えれば間違いないと思います。なお、2.6ではCPUごとにlistを独立に持ったり、単にlistをなめることがないように工夫されていますが、基本的には2.4と大きくは変わりません。

id:labtest

参考にしたのは、カーネル2.4のタイマー処理概要

http://opentechpress.jp/kernel/internal24/node37.shtml#SECTION02...

と関数の説明

http://opentechpress.jp/kernel/internal24/node38.shtml#SECTION02...

を読んで、処理順にならんでいて、また同じ時間に処理すべきものはlist構造で並べていると読めたのですが、全然違うのですね。上記説明は古いのか間違っているのでしょうか?私の言っているタイマー処理というのは「TCP/IPのタイムアウト処理や再送処理などで利用」するようなものです。

2006/09/19 13:07:20

その他の回答(5件)

id:furutanian No.1

furutanian回答回数112ベストアンサー獲得回数142006/09/19 12:47:51ここでベストアンサー

ポイント80pt

基本的なポイントですが、Linuxのスケジューラはプロセスを「処理が行われる順に並んだlist構造」で扱っていません。プロセスはlist構造で管理されていますが、それは処理順に並べられているわけではないです。

また「ある処理をある時間に実行しなければならない状態が発生」しても、特別な処理が行われることはありません。処理順はプロセスのスケジューリングポリシーと優先度でしか制御できません。LinuxはリアルタイムOSではないため、上記のような事態を確実に処理するようにはできていません。LinuxベースのリアルタイムOSであるRedHawkLinuxはスケジューラがそれ用に改造されており、一般的なLinuxとは別物になっています。

http://www.ccur.co.jp/realtime/redhawk.html

ちょっと脱線しましたが、スケジューリングポリシーと優先度によるスケジューリングは、乱暴に言えばポイント制みたいなもので、OSがプロセススイッチをするたびに、ポイントを足したり引いたりしながらlistをなめ、ポイントの高いものを優先的に実行すると考えれば間違いないと思います。なお、2.6ではCPUごとにlistを独立に持ったり、単にlistをなめることがないように工夫されていますが、基本的には2.4と大きくは変わりません。

id:labtest

参考にしたのは、カーネル2.4のタイマー処理概要

http://opentechpress.jp/kernel/internal24/node37.shtml#SECTION02...

と関数の説明

http://opentechpress.jp/kernel/internal24/node38.shtml#SECTION02...

を読んで、処理順にならんでいて、また同じ時間に処理すべきものはlist構造で並べていると読めたのですが、全然違うのですね。上記説明は古いのか間違っているのでしょうか?私の言っているタイマー処理というのは「TCP/IPのタイムアウト処理や再送処理などで利用」するようなものです。

2006/09/19 13:07:20
id:Kumappus No.2

くまっぷす回答回数3784ベストアンサー獲得回数1852006/09/19 12:55:25

ポイント10pt

http://www.atmarkit.co.jp/flinux/special/kernel25/kernel25b.html

http://itpro.nikkeibp.co.jp/article/COLUMN/20060630/242253/

2.4までは線形検索、つまり頭から全部なめていたのですが、2.5(つまり2.6以降は)プロセス優先度順にキューが複数並べてあり優先度が高い方から先に検索するようになりました。

id:kurukuru-neko No.3

kurukuru-neko回答回数1844ベストアンサー獲得回数1552006/09/19 16:14:39

ポイント20pt

>例えばある処理をある時間に実行しなければならい

>TCP/IPのタイムアウト処理や再送処理などで利用

 2.4でそのような時間にこだわる場合、RTLinux,ARTLinux

のように独自実装が必要。 Linux 2.4では条件に該当する

タイマーを順番に呼び出すだけ。

http://www.da-cha.org/lki/lki.ja-2.html

http://homepage3.nifty.com/rio_i/lab/driver24/001module.html

http://osdn.jp/event/pdf/LW2001Fall_takahashi.pdf

Linux 2.6では、タイマー、優先度が増えたが基本的には

 該当するタイマー処理を順に呼び出す。

http://www.atmarkit.co.jp/flinux/special/kernel26/kernel26_01a.h...

http://www.atmarkit.co.jp/flinux/special/kernel26/kernel26_04a.h...

http://dontaku.csce.kyushu-u.ac.jp/~aono/linux-kernel_hirour/sem...

詳解 Linuxカーネル 第2版

http://www.oreilly.co.jp/books/4873111331/

http://www.oreilly.co.jp/BOOK/lidriver2/contents.htm

id:furutanian No.4

furutanian回答回数112ベストアンサー獲得回数142006/09/19 16:42:39

失礼しました。先の回答はカーネルのプロセススケジューリングについての内容で的外れでした(なぜかKumappusさんも同様の質問の受け取り方をされているようですが(^^;))。

タイマ処理の追加(add_timer関数)は、ズバリ以下のように処理になります。

・指定されたタイマ実行時間までの相対時間をtick単位で求める

・今から0tick後に期限が来るもの、tv1[0]から辿ることのできるlistの最後に要素を追加

・今から1tick後に期限が来るもの、tv1[1]のlistの最後に追加

・<略>

・今から255(=2^8)tick後に期限が来るもの、tv1[255]のlistの最後に追加

・今から255(=2^8)~512(=(2^8)*2)tick未満に期限が来るもの、tv2[1]のlistの最後に追加

・今から(2^8)*2~(2^8)*3tick未満に期限が来るもの、tv2[2]のlistの最後に追加

・<略>

・今から(2^8)*63~(2^8)*64(=2^14)tick未満に期限が来るもの、tv2[63]のlistの最後に追加

・今から2^14~2^20tick未満に期限が来るもの、tv3[x]のlistの最後に追加

・今から2^20~2^26tick未満に期限が来るもの、tv4[x]のlistの最後に追加

・それ以降に期限が来るもの、tv5[x]のlistの最後に追加

……という感じで、タイマ実行までの時間に応じて5つのプール(tv:timer_vec)があり、そのプールの仕切りの中に追加をする仕組みのようです。言い方を変えると、タイマの追加は256+64x4個のlistのどれかにぶら下げるだけで、ぶら下げるべきlistはビットシフトで計算できるので「listをなめる処理は一切ない」が答えですね。

listをなめなきゃならない処理は、タイマ実行処理の中で時々行えばいいようにできてます(この「時々行う処理」は、先のhttp://opentechpress.jp/kernel/internal24/node37.shtml#SECTION02...に説明がある「繰上げの処理」になります)。

なお、この処理はkernel/timer.cのinternal_add_timer関数に記述されていて、処理アルゴリズム自体は2.4も2.6もまったく同じのようです。

id:labtest

>ぶら下げるべきlistはビットシフトで

>計算できる

初心者の質問で申し訳ないのですが、具体的にどのようにすれば計算できるのでしょうか?

2006/09/19 20:25:54
id:furutanian No.5

furutanian回答回数112ベストアンサー獲得回数142006/09/19 23:55:46

さすがに、シフト演算(<<や>>)についての基本的な説明は不要だと思いますが、となるとココから先はソースを読む以外に説明の方法はありません。「※」でコメントを加えたのでご参考に。

#define TVN_BITS 6

#define TVR_BITS 8

#define TVN_SIZE (1 << TVN_BITS) ※ 0100_0000b = 64

#define TVR_SIZE (1 << TVR_BITS) ※ 1_0000_0000b = 256

#define TVN_MASK (TVN_SIZE - 1) ※ 0011_1111b = 63

#define TVR_MASK (TVR_SIZE - 1) ※ 1111_1111b = 255

static void internal_add_timer(tvec_base_t *base, struct timer_list *timer)

{

    unsigned long expires = timer->expires;         ※ タイマをかけたい時間(jiffies/tick単位)

    unsigned long idx = expires - base->timer_jiffies;   ※ タイマ発動までの相対時刻を求める(jiffies/tick単位)

    struct list_head *vec;                 ※ 5つのうち、どのプールを使うか

    if (idx < TVR_SIZE) {                  ※ 255tick以内にタイマ発動か?

        int i = expires & TVR_MASK;

        vec = base->tv1.vec + i;            ※ プール1の中のぶら下げるlistを決定

    } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {     ※ 1の8+6ビット左シフト(=256 * 64)未満か?

        int i = (expires >> TVR_BITS) & TVN_MASK;    ※ 8ビット右シフトする(=256で割る)

        vec = base->tv2.vec + i;            ※ プール2の中のぶら下げるlistを決定

    } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {   ※ 256 * 64 * 64 未満か?

        int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK; ※ 8+6ビット右シフトする(=256 * 64で割る)

        vec = base->tv3.vec + i;            ※ プール3の中のぶら下げるlistを決定

    } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {

        int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;

        vec = base->tv4.vec + i;            ※ プール4の中のぶら下げるlistを決定

    } else if ((signed long) idx < 0) {

        /*

         * Can happen if you add a timer with expires == jiffies,    ※もう、過ぎちゃってるよ

         * or you set a timer to go off in the past

         */

        vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);

    } else {

        int i;

        /* If the timeout is larger than 0xffffffff on 64-bit

         * architectures then we use the maximum timeout:

         */

        if (idx > 0xffffffffUL) {

            idx = 0xffffffffUL;

            expires = idx + base->timer_jiffies;

        }

        i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;

        vec = base->tv5.vec + i;            ※ プール5の中のぶら下げるlistを決定

    }

    /*

     * Timers are FIFO:

     */

    list_add_tail(&timer->entry, vec);           ※ 上で決定したlistの最後にぶら下げる

}

……と、上記のようなシフト演算によって、ぶら下げるべきlistが決定されます。

id:labtest

非常によく分かりました。ソースまで調べていただいて大変ありがとうございます。1点だけ分からない点があるので教えてください(何度もすみません)。プールの中のぶら下げるlistを決めるのに

int i = expires & TVR_MASK;

expire時間を255でビットマスクしていますが、なぜビットマスクすることでぶら下げるlistを決められるのでしょうか?

2006/09/20 10:37:33
id:furutanian No.6

furutanian回答回数112ベストアンサー獲得回数142006/09/20 12:15:44

> expire時間を255でビットマスクしていますが、なぜビットマスクすることで

> ぶら下げるlistを決められるのでしょうか?

この質問は様々な意味に受け取れますので、趣旨と違ったら再度聞いてください。

>   if (idx < TVR_SIZE) {       ※ 255tick以内にタイマ発動か?

>     int i = expires & TVR_MASK;

>     vec = base->tv1.vec + i;    ※ プール1の中のぶら下げるlistを決定

255でビットマスクする=256で割った余りを求める、という理解は大丈夫ですよね?

私は2度目の回答で「5つのプールがある」と書きましたが、ひとつめのプールは、

直近256tick以内にタイマが発動される、256個のlistヘッダ要素を持つ配列ですから、

256で割った余りを求めることで、ぶら下げるlistが決定できます。

なお、2つ目以降のプールは、64要素しかないので、63でビットマスクしています。

id:labtest

>255でビットマスクする=256で割った余りを

>求める、という理解は大丈夫ですよね?

すいません理解していませんでした。大変助かりました。

2006/09/20 12:24:48

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません