人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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

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

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

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

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

●質問者: labtest
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:Linux Web なめる ほと カーネル
○ 状態 :終了
└ 回答数 : 6/6件

▽最新の回答へ

1 ● furutanian
●80ポイント ベストアンサー

基本的なポイントですが、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と大きくは変わりません。

◎質問者からの返答

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

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

と関数の説明

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

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


2 ● くまっぷす
●10ポイント

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以降は)プロセス優先度順にキューが複数並べてあり優先度が高い方から先に検索するようになりました。


3 ● kurukuru-neko
●20ポイント

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

>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


4 ● furutanian
●0ポイント

失礼しました。先の回答はカーネルのプロセススケジューリングについての内容で的外れでした(なぜか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もまったく同じのようです。

◎質問者からの返答

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

>計算できる

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


5 ● furutanian
●0ポイント

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

#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が決定されます。

◎質問者からの返答

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

int i = expires & TVR_MASK;

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


1-5件表示/6件
4.前の5件|次5件6.
関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ