プロフィール

kosaki

Author:kosaki
連絡先はコチラ

ブログ検索
最近の記事
最近のコメント
最近のトラックバック
リンク
カテゴリー
月別アーカイブ
RSSフィード
FC2ブログランキング

スポンサーサイト このエントリーをはてなブックマークに追加

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


スポンサー広告 | 【--------(--) --:--:--】 | Trackback(-) | Comments(-)

シーケンスロック その2 このエントリーをはてなブックマークに追加

シーケンスロックの続きです。

前回の記事はこちら

今回はシーケンスロックとは赤レンジャーである(ちげー)という話をしたいと思います。
詳しくは続きを



赤いヤツら
戦隊が! 1列に! シーケンス!




前回の復習。

ロック関数を作りたいと思いました。
でも読み手もバスライトが走るので、いやーんな感じです。どうしましょ?

はい、いいですね?ここで発想の転換をしましょう。

鍵を掛けるのが遅いなら鍵を掛けなきゃいいじゃない(マリー・アントワネット)


ごほん。
トイレを引きずったまま、サイバーノーガード戦法ならぬサイバーノーロック戦法の話を続けてしまうとなにやら剣呑な雰囲気になってしまうので、ちょっと例えを変えましょう。


あるところに、ゴレンジャー大好きな少年がおとうさんと野球観戦に行きました。
しかし、ベンチを良く見ると・・・・・




くわっ


5レンジャー




なぜかこんなところに5レンジャーがいます。
当然試合後は大人の目をかいくぐって黄レンジャーの後をつけます。控え室に潜入です。


無論、選手控え室ごときに鍵が掛かっているはずもありません


少年は、期待に胸を震わせながら扉をゆっくりとあけます



・・・・・




・・・・・・・・・・






・・・・・・・・・・・・・・



なぜ、黄レンジャーの代わりに黒人ひげオヤジがいるとですか!!


はい、鍵を掛けなかったおかげで黄レンジャーの着替え中にドアを開けるというハプニング(これを専門用語でダーティーリードといいます)が発生してしまいました。
まさに黒ひゲイ危機一発。少年の心はズタズタです。


ところが、この状況においても事態を丸く治める方法が1つだけあります。


少年が、そっと扉を閉め、はっはっは疲れてるなかな僕、などと独り言をつぶやき
10秒ほど間をおいてからそっと扉をもう一度開ければ


うわーい、黄レンジャーだ。うわーい、うわーい


とはしゃぎながら部屋の中に入っていくことが可能な状況になっていること、請け合い。

そうです。
鍵がなければダーティーリードが発生してしまうのは避けれませんが、それで事態が破綻してしまうかどうかはあくまで読み手の心意気しだいなのです。


この理屈を実装したのがシーケンスロックです。
ソースファイルは linux-src/incoude/linux/seqlock.h にコンパクトにまとまっています。
順に見ていきましょう

/*
* Expected reader usage:
* do {
* seq = read_seqbegin(&foo);
* ...
* } while (read_seqretry(&foo, seq));
*/


まず、コメントで、読み手のお作法について解説しています。
読み始めで、read_segbegin(), 読み終わりで read_seqretry() を呼ぶと
ダーティーリードが発生したときには read_seqretry() が !0 を返すので
やり直してねって事です。


typedef struct {
unsigned sequence;
spinlock_t lock;
} seqlock_t;/


シーケンスロック構造体の定義。
書き手複数の状況でしか lock変数は使わないので実質sequence変数1つ!


static inline void write_seqlock(seqlock_t *sl)
{
spin_lock(&sl->lock);
++sl->sequence;
smp_wmb();
}

static inline void write_sequnlock(seqlock_t *sl)
{
smp_wmb();
sl->sequence++;
spin_unlock(&sl->lock);
}


write_seqlock()とwrite_sequnlock()はspin_lock(),spin_unlock()のように危険区域の
最初と最後に呼ぶことが想定されています。

ここで、lock, unlockともにsequenceを+1しているのに注目。
これによって、更新途中はsequenceが奇数になります。
そして、spin_lockによって2人の書き手が同時に危険区域に入ってこれないように保護しています。
そうしないと、危険区域なのにsequenceが偶数になる瞬間が出来てしまいますからね。

書き手用のロック、設計上書き手が1人なのが保障されているときは
spin_lock()を呼ぶのは時間の無駄なのでspin_lock()を呼ばない爆速バージョンも用意されています。
でも、シーケンスロックを使う以上、更新はまれなはずなのであんまり気にしても仕方がないっしょ。

(ところで、sequenceのインクリメントが前置形と後置形が混在してるのはなんでなんでしょ?だれかおせーて。)


static inline unsigned read_seqbegin(const seqlock_t *sl)
{
unsigned ret = sl->sequence;
smp_rmb();
return ret;
}

static inline int read_seqretry(const seqlock_t *sl, unsigned iv)
{
smp_rmb();
return (iv & 1) | (sl->sequence ^ iv);
}


こっちは読み手側の実装。
read_reqretry()のiv引数は initial valueの略、read_seqbegin()の戻り値が渡されることが
期待されてるぜー、って意味ね。

リトライの条件に注目。読み手が読むシーケンス値は


seqbegin() seqretry() あるべき動作
------------------------
奇数 奇数 retry
奇数 偶数 retry
偶数 奇数 retry
偶数 偶数(値変化あり) retry
偶数 偶数(値変化なし) 読み出し成功



の5パターンが考えられ、(iv & 1) が1番目の条件を、(sl->sequence ^ iv) がそれ以外の条件を尽くしていることを
確認して欲しい。


これで、シーケンスロックの仕組みは解説完了です。
ここで、「あれ? smp_wmb()とsmp_rmb()の解説終わってないよ」と気づいたあなたは鋭い。
実は理論的にはこれで終わりなのだが、実際にはこれだけではうまくいかないのである。
それがなぜかは次回説明したいと思う


関連記事
linux | 【2006-03-12(Sun) 17:53:22】 | Trackback:(1) | Comments:(5)
コメント

>> ところで、sequenceのインクリメントが前置形と後置形が混在してるのはなんでなんでしょ?だれかおせーて。

対称性の美学からかなぁ?コナンでそんなこといってたよ,昨日.
2006-03-13 月 22:54:16 | URL | 坩堝 #- [ 編集]

なるほどー、対象性か!

って、いやいや。
実は本文でちょっとだけかいたスピンロックとらないバージョンの
write_seqcount_begin(),
write_seqcount_end()
だと両方とも後置形なんですよ。

だから余計に謎でね
2006-03-14 火 02:00:02 | URL | 管理人 #- [ 編集]
このコメントは管理人のみ閲覧できます
2007-09-01 土 11:23:38 | | # [ 編集]
このコメントは管理人のみ閲覧できます
2007-10-09 火 17:01:08 | | # [ 編集]

おもしろかったです。分かりやすい例示をありがとうございます。
2008-03-27 木 13:18:16 | URL | Java3年目プログラマ #- [ 編集]
このBlogで屈指の人気のなさを誇るLinux のカーネルの話題のつづきです。前回の記事はこちら今回から数回にわたって smp_rmb(), smp_wmb() について解説していきます。ロック本体よりも長
【2006-03-18 Sat 05:01:23】 | 革命の日々!
  1. 無料アクセス解析
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。