アカウント名:
パスワード:
変な話ですけど、priority inheritanceはちゃんと実装するんでしょうね? 現状の実装を見たら目が点になったので...
あと、C言語上で同じ文であってもarchitectureによってlockが必要だったりいらなかったりすることがありますよね(i386はsparcなどほかのarchitectureに比べてhardwareがmemory accessの同期をとってしまうことが多い、並列度を落とせっつーとるのか?)。ここできちんと全てのarchitectureをカバーするような配慮ができるかな?
最近の2.4は追ってないけど、初期のではlockの種類を問わずpriority inheritanceが全く行われていなかったような。それから、Linux kernelで特に問題になっていないように見えるのは、まだmainstream kernelに対してdispatch delayを意識するapplicationが存在しないという背景があります。Solarisの時にはこれが初期から大問題になり(主にinterrupt threadとrealtime process、特に前者はシステム全体に響く)、結局priority inheritanceがpreemptive kernelとならんで強烈に効いたわけです。
memory barrierについては、最大の敵は「人間」です。Cで書いた文が一体どのようにassemberに落ちるのかがわからないといけないので、発見には手間がかかります。実際、i386では平気だと思っていたものがsparc64ではうまく動かず、lockのかけなおしをする羽目になった経験があります。Linux kernelの基本方針はi386に似せた抽象化なので、よくよく注意しないと救えないarchitectureが出てくる恐れすらあります。
聞き伝えですが、sparc64の場合はi386と違ってmemory accessをout-of-orderにやってしまうことが多いそうです(並列度を上げるためにはしょうがないけど)。したがって、memory barrierを置いたとしても、それまでに完了して欲しいwriteがmemory barrierにぶち当たるまでに確実に実行することが保証できません。当時の議論を読み返して気が付いたのですが、これはhardwareの問題であり、softwareではmemory barrierよりも高級なlock(せいぜいmutexで済むのが救いだが)を使うしかありません。
それから、このような問題はある構造体のたった1つのmemberを読むだけでも起こり得ます。したがって、kernelのほぼ全てに渡って影響を及ぼします。そのような問題に対してmachine-dependentな対策をとった場合、特定のarchitectureでしか現れないbugをkernel全体にばらまいてしまう恐れがあります。
そういうわけで、FreeBSDではこの問題をmachine-independentなlock primitive(実際にはsleep mutex)で解決することにしました。これならsys/kern以下のlockに関わる問題をi386で解決すれば、sparc64でもその恩恵をそのまま受けることができます。
386では問題なかった -> 字面上の命令の順序は問題なかった -> それでsparcで問題がおきたということはストア命令が他のプロセッサから違う順番で見えた ->* membar #Syncを入れると良い
*の部分ですが、問題が起きるのはC言語上では1つの文(たいていは式文)でありながら、assemblerに落とすと複数回のstoreを必要としてしまう場合です(2重以上の間接参照をdereferする場合など)。この場合はC言語ではそれ以上式を分割できないため、C言語のレベルでは解決できません(マクロなどは一切使えない)。
ではdereferenceを全てバラしてcompilerが頑張ればいいかというと、そうもいきません。一般にあるdataがthread-localであるか否かを自動的に判断するのは(特にpointerの値を簡単にいじることができ、かつそれが必要になる場面では)技術的に困難な問題を抱えてしまいます。かといって全てにmemory barrierを張ると、並列度が落ちて無駄にperformanceを悪化させる結果になります。ならばassemble listに手を加えて...というのは、すでに4.3BSDで失敗しています。
memory barrierはあくまで1つのinstructionだけに対して同期をとるための手法です(その点ではi386のlock prefixと変わらない)。したがって、test-and-setやconditional storeなどの命令と併用するぐらいしか有効な使い道はありません。
なお、上述の問題はinstruction setについてmemory accessを何回認めるかに対する考え方の違いが原因です。したがって、この問題は10年、20年、50年経っても解決を見る見込みはありません。とならば、いたずらに問題を複雑化させるよりも、より問題を(machine-independentにすることにより)発見しやすくしておく(より多くの人が再現実験に加われる)努力をすべきです。最適化はその後でも遅くありません。
n重参照のdereference(n>2)は、例えば
p->p_pgrp->pg_jobc == 0
の左辺ですね。これはsignal処理の中で出てきた例(実際に問題になった)ですが、ほかにもprocess groupやsessionをprocessからたどる場合によく起こります。FreeBSDに関していえば、KSE(Kernel Scheduling Entity)のmergeにより、processももはや出発点ではなく、threadに貼りつくだけのものになってしまいました。ですから、
td->td_proc->p_pgrp->...
というdereferenceもぼちぼち出てきてます。まぁ、Cのレベルで複数の式文に分けることはできますが、実際にキーを打つ立場としてはそれをやると読みづらいし、あちこちいじらないといけないし、ローカル変数の初期化を忘れて...など、面倒なことの方が多いです(そんなことに時間を割く余裕はない)。
また、このような文を書いた場合、アドレス値のloadを複数回、しかも一般には不連続に(loadだけを連続実行することができない)繰り返すことになります。こうなるとmemory barrierだけではloadの間に入った別の命令を超えた保護ができません。
実際のところ、Linux/UNIXレベルのOSに汎用の実時間処理機能を持たせるには、他にも多くの課題があります。
sleep-wakeupによる同期というのは、本質的にはlock primitiveの1種であるcondition variableと等価です(他はmutexとshared-exclusive lock)。したがって、同期をとるべき資源の持ち主は一般的にはわからず、priority inheritanceは確かに困難です。condition variableについてはSolarisもpriority inheritaceは行ってしません。shared-exclusive lockではowner-of-recordに対してpriority inheritanceを行うことにより、疑似的に実現しています。
この感じだと世の中にはあまり知られていないようですが(少なくともLinux kernelは実装していない)、実は実行単位がspinではなくblockすることにより待機する、sleepable mutexがあります(Solarisのadaptive lockはその1種)。もちろん、必要ならばpriority inheritanceを行います。sleepable mutexが必要な理由は簡単で、全てのデータをspin lockで保護した場合、あるデータを多くのprocessorがlockしようとするとシステムに空きprocessorがなくなってしまうためです。したがって、kernelのうちschedulingに関わる部分などごく一部を除き、全てのデータはこのsleepable mutexで保護するのが普通です。Solarisの実装で理論的にpriority inheritanceがもっとも多く行われるのは、このsleepable mutexの場合です(実測しても間違いなくそうなるであろう)。
それから、このような話が出てくるとオウムがえしのようにrealtimeを考える人がいますが、それは決して本質ではありません。粒度の細かいlockが必要な最大の理由は、kernel内部の並列度を上げることにあります。これはTSS-likeに使うUnixでも十分役に立ちますし、従来の枠組みでは全く扱えなかったinterrupt handlingの並列化にはなくてはなりません。実際、Solarisを2 cpuの計算機(sun4u)で走らせていると、少しコンパイルするだけでもkernel timeが70-80%まで上がります。あるいは、まだGiant lockがとれていないFreeBSD-currentを4 cpuの計算機で走らせると、高々100程度のprocessでも30程度がGiant待ちを食らってしまいます。これらの現象を観察すると、mutexによるデータ保護はもちろん必要ですし、interrupt threadが不必要に遅延を食らわないようにするためにdispatch delayを減らす努力が必須であることも理解できます。realtimeはその技術を流用したために可能になる後付けであり、決して始めにrealtime有りきではありません。
おっしゃるとおり、応答性と並列性は別のものです。並列性を上げるための仕組みが、カーネル内プリエンプトを可能にする仕組みに流用できるという副次効果があるだけです。
ちなみに、sleep-wakeupによる同期が本質的にはcondition variableと等価ということも知っています。 ま、Linuxの場合、sleepable mutexの導入を考える以前に、ロックの粒度が大きいところを細かくするほうが先決です。今のままCPU数を増やすとファイルシステムの奥の方と、ブロックデバイス周りのロックの粒度が問題になるでしょう。 sleepable mutexを利用する場合も注意が必要だと思います。 sleepable mutexも万能ではなく、あらかじめ短いことがわかっている排他区間で利用するとコストが高くつきます。実際の実装では適当なところで妥協し、馬鹿spinlockと使い分けをするのが良いでしょう。（というかsleepable mutexが不必要なくらい全てのロック区間を短くするのが良い） sleepable mutexを採用するなら、まずLinuxの割り込み処理も、Solarisのようにスレッドとして動けるように書き直すことと、 ロックを握りっぱなしにされないようにプライオリティ継承かシーリングセマフォ的なものの導入することが必須となるでしょう。
ところで、一般にはプライオリティ継承は応答性を高める目的で実装されますが、「プライオリティ継承が必要だ！」と言われているのは、上記sleepable_mutexを前提とした話だったのでしょうか？
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
にわかな奴ほど語りたがる -- あるハッカー
新機能 (スコア:5, 参考になる)
2.5で入るかもしれない機能のなかではプロセスごとにファイルシステムの名前空間を分ける機能(CLONE_NAMESPACE?)と入出力のより一般的な扱い(マルチキーボード、マルチディスプレー、マウスによる複数端末としての利用)に期待しています。
あとは
- ファイルのマルチストリーム(ntfsとかmacのfsにあるやつ)
- posix acl(or 互換するもの)
- 非同期I/O
が実装されるっぽいです。カーネルの中では
- シリアルドライバの書き直し
- ネットワークドライバを高負荷に耐えられる方式に変更
- ページキャッシュの粒度の変更
のコードを見てみたいです。Linuxのスケーラビリティの問題の原因となってるI/Oのlockの粗さとスケジューラの粗さにも手がはいるんではないかと期待します。
Re:新機能 (スコア:5, 興味深い)
変な話ですけど、priority inheritanceはちゃんと実装するんでしょうね? 現状の実装を見たら目が点になったので...
あと、C言語上で同じ文であってもarchitectureによってlockが必要だったりいらなかったりすることがありますよね(i386はsparcなどほかのarchitectureに比べてhardwareがmemory accessの同期をとってしまうことが多い、並列度を落とせっつーとるのか?)。ここできちんと全てのarchitectureをカバーするような配慮ができるかな?
Re:新機能 (スコア:3, 興味深い)
現時点でLinuxのパフォーマンスの分析した記事や論文を見る限り、そのへんが実際に問題になっているというデータはない(僕の知る限り）ので、2.5ではやらない or 後回しじゃないでしょうか。
メモリバリアはバグとかはあるかもしれませんが、そこそこ多様なメモリモデルに対応できるプリミティブが用意されてて、一応書くべきところには書いてあるように読めます(実は大量に抜けがあったりするのかも)。
Re:新機能 (スコア:3, 参考になる)
最近の2.4は追ってないけど、初期のではlockの種類を問わずpriority inheritanceが全く行われていなかったような。それから、Linux kernelで特に問題になっていないように見えるのは、まだmainstream kernelに対してdispatch delayを意識するapplicationが存在しないという背景があります。Solarisの時にはこれが初期から大問題になり(主にinterrupt threadとrealtime process、特に前者はシステム全体に響く)、結局priority inheritanceがpreemptive kernelとならんで強烈に効いたわけです。
memory barrierについては、最大の敵は「人間」です。Cで書いた文が一体どのようにassemberに落ちるのかがわからないといけないので、発見には手間がかかります。実際、i386では平気だと思っていたものがsparc64ではうまく動かず、lockのかけなおしをする羽目になった経験があります。Linux kernelの基本方針はi386に似せた抽象化なので、よくよく注意しないと救えないarchitectureが出てくる恐れすらあります。
Re:新機能 (スコア:1)
これについては強く同意します。んで
>> 実際、i386では平気だと思っていたものがsparc64ではうまく動かず、lockのかけなおしをする羽目になった経験があります。
これですが(gccですが)sparcの方に__asm__("membar #Sync":::"memory")、86の方に__asm__("" ::: "memory")とか書いてはダメでしょうか？ 86では何もしなくてよくてsparcではlockが必要になるという状況が思いつかないのですが、支障がなければ教えてもらえないでしょうか？
Re:新機能 (スコア:3, 興味深い)
聞き伝えですが、sparc64の場合はi386と違ってmemory accessをout-of-orderにやってしまうことが多いそうです(並列度を上げるためにはしょうがないけど)。したがって、memory barrierを置いたとしても、それまでに完了して欲しいwriteがmemory barrierにぶち当たるまでに確実に実行することが保証できません。当時の議論を読み返して気が付いたのですが、これはhardwareの問題であり、softwareではmemory barrierよりも高級なlock(せいぜいmutexで済むのが救いだが)を使うしかありません。
それから、このような問題はある構造体のたった1つのmemberを読むだけでも起こり得ます。したがって、kernelのほぼ全てに渡って影響を及ぼします。そのような問題に対してmachine-dependentな対策をとった場合、特定のarchitectureでしか現れないbugをkernel全体にばらまいてしまう恐れがあります。
そういうわけで、FreeBSDではこの問題をmachine-independentなlock primitive(実際にはsleep mutex)で解決することにしました。これならsys/kern以下のlockに関わる問題をi386で解決すれば、sparc64でもその恩恵をそのまま受けることができます。
Re:新機能 (スコア:1)
i386では問題なかった -> 字面上の命令の順序は問題なかった -> それでsparcで問題がおきたということはストア命令が他のプロセッサから違う順番で見えた -> membar #Syncを入れると良い
というのでどこか間違ってるでしょうか？
まともなプロセッサなら強いordering(i386)かメモリバリア(こっちが多数派だし将来的に増えるハズ)のどっちかがあるはずなので特定のアーキテクチャに依存するということは無いと思います。
Re:新機能 (スコア:2)
*の部分ですが、問題が起きるのはC言語上では1つの文(たいていは式文)でありながら、assemblerに落とすと複数回のstoreを必要としてしまう場合です(2重以上の間接参照をdereferする場合など)。この場合はC言語ではそれ以上式を分割できないため、C言語のレベルでは解決できません(マクロなどは一切使えない)。
ではdereferenceを全てバラしてcompilerが頑張ればいいかというと、そうもいきません。一般にあるdataがthread-localであるか否かを自動的に判断するのは(特にpointerの値を簡単にいじることができ、かつそれが必要になる場面では)技術的に困難な問題を抱えてしまいます。かといって全てにmemory barrierを張ると、並列度が落ちて無駄にperformanceを悪化させる結果になります。ならばassemble listに手を加えて...というのは、すでに4.3BSDで失敗しています。
memory barrierはあくまで1つのinstructionだけに対して同期をとるための手法です(その点ではi386のlock prefixと変わらない)。したがって、test-and-setやconditional storeなどの命令と併用するぐらいしか有効な使い道はありません。
なお、上述の問題はinstruction setについてmemory accessを何回認めるかに対する考え方の違いが原因です。したがって、この問題は10年、20年、50年経っても解決を見る見込みはありません。とならば、いたずらに問題を複雑化させるよりも、より問題を(machine-independentにすることにより)発見しやすくしておく(より多くの人が再現実験に加われる)努力をすべきです。最適化はその後でも遅くありません。
Re:新機能 (スコア:1)
>>C言語上では1つの文(たいていは式文)でありながら、assemblerに落とすと複数回のstoreを必要としてしまう場合です(2重以上の間接参照をdereferする場合など)。この場合はC言語ではそれ以上式を分割できないため
の例を示していただけないでしょうか？
それと
>>memory barrierはあくまで1つのinstructionだけに対して同期をとるための手法
これはメモリバリアのどのような側面を指してそうおっしゃてるのでしょうか？
Re:新機能 (スコア:2)
n重参照のdereference(n>2)は、例えば
の左辺ですね。これはsignal処理の中で出てきた例(実際に問題になった)ですが、ほかにもprocess groupやsessionをprocessからたどる場合によく起こります。FreeBSDに関していえば、KSE(Kernel Scheduling Entity)のmergeにより、processももはや出発点ではなく、threadに貼りつくだけのものになってしまいました。ですから、
というdereferenceもぼちぼち出てきてます。まぁ、Cのレベルで複数の式文に分けることはできますが、実際にキーを打つ立場としてはそれをやると読みづらいし、あちこちいじらないといけないし、ローカル変数の初期化を忘れて...など、面倒なことの方が多いです(そんなことに時間を割く余裕はない)。
また、このような文を書いた場合、アドレス値のloadを複数回、しかも一般には不連続に(loadだけを連続実行することができない)繰り返すことになります。こうなるとmemory barrierだけではloadの間に入った別の命令を超えた保護ができません。
Re:新機能 (スコア:1)
>>C言語上では1つの文(たいていは式文)でありながら、assemblerに落とすと複数回のstoreを必要としてしまう場合です(2重以上の間接参照をdereferする場合など)。この場合はC言語ではそれ以上式を分割できないため
に対するもので、この場合storeはやってないように見えます。
それから
>>実際、i386では平気だと思っていたものがsparc64ではうまく動かず、lockのかけなおしをする羽目になった
と書かれていますが、このコードはi386ではロックなしで問題ないのでしょうか？
コンパイラの最適化 (スコア:1)
brake-handle さんのおしゃる通りなのですが 「問題が起きるのはC言語上では1つの文(たいていは式文)でありながら、assemblerに落とすと複数回のstoreを必要としてしまう場合」 以上に、 C コンパイラの最適化の掛かり方が 問題になることが多いと思います。
は2回の load に変換されるわけですが、 最適化によってこの2つの load 命令の距離が 引き離されて 間に他の load/store 命令が入ってくることが 考えられます。 こういう場合に、 メモリバリアを 関数なりインラインアセンブラの形で 挿入すると 最適化が切れて一見正しく実行されるコードが 出力さることがあります。
結局、 C 言語を使ってマルチスレッドプログラムをする場合、 「(machine-independentな)ワードの読み書きは アトミックに行われる」以上の同期は期待でき ないです。 アーキテクチャ/コンパイラの組み合わせによっては double 型や 64ビット整数の代入すら アトミックになりませんし。
コンタミは発見の母
Re:コンパイラの最適化 (スコア:1)
>>i386では平気だと思っていたものがsparc64ではうまく動かず、lockのかけなおしをする羽目になった経験があります。
なんてことがありうるのだろうかと興味があったのでダラダラと議論を長引かせてしまいました。上記の指摘された問題であればi386の方でもマズイですよね？doubleとか64bit整数だと逆にsparc64では大丈夫ってことになりそうですし。
Re:新機能 (スコア:1)
スピンロックはCPU間の排他を行う仕組みです。スピンロック区間は普通割り込み禁止・プリエンプト禁止で瞬間的に走り抜けます。つまりこれ以上の優先度はありません
まあ、複数のCPUが同時にスピンロックを試みた時にどのCPUが、権利を取得できるかは運任せという問題はありますが。
確かにおっしゃるとおりsleep/wakeupメカニズムの方のプライオリティ継承は実装されていません。しかきこの機能を完全に実装しようと思うと非常にコストがかかります(資源確保のネスト、複数プロセスが資源を持っているときなど状態が非常に複雑です）。どこで妥協するかがポイントでしょう。Linuxでどのような実時間処理に利用したいか考えたうえで、最小限の実装するのが、まあ妥当なところでしょうか。
実際のところ、Linux/UNIXレベルのOSに汎用の実時間処理機能を持たせるには、他にも多くの課題があります。
Re:新機能 (スコア:2)
sleep-wakeupによる同期というのは、本質的にはlock primitiveの1種であるcondition variableと等価です(他はmutexとshared-exclusive lock)。したがって、同期をとるべき資源の持ち主は一般的にはわからず、priority inheritanceは確かに困難です。condition variableについてはSolarisもpriority inheritaceは行ってしません。shared-exclusive lockではowner-of-recordに対してpriority inheritanceを行うことにより、疑似的に実現しています。
この感じだと世の中にはあまり知られていないようですが(少なくともLinux kernelは実装していない)、実は実行単位がspinではなくblockすることにより待機する、sleepable mutexがあります(Solarisのadaptive lockはその1種)。もちろん、必要ならばpriority inheritanceを行います。sleepable mutexが必要な理由は簡単で、全てのデータをspin lockで保護した場合、あるデータを多くのprocessorがlockしようとするとシステムに空きprocessorがなくなってしまうためです。したがって、kernelのうちschedulingに関わる部分などごく一部を除き、全てのデータはこのsleepable mutexで保護するのが普通です。Solarisの実装で理論的にpriority inheritanceがもっとも多く行われるのは、このsleepable mutexの場合です(実測しても間違いなくそうなるであろう)。
それから、このような話が出てくるとオウムがえしのようにrealtimeを考える人がいますが、それは決して本質ではありません。粒度の細かいlockが必要な最大の理由は、kernel内部の並列度を上げることにあります。これはTSS-likeに使うUnixでも十分役に立ちますし、従来の枠組みでは全く扱えなかったinterrupt handlingの並列化にはなくてはなりません。実際、Solarisを2 cpuの計算機(sun4u)で走らせていると、少しコンパイルするだけでもkernel timeが70-80%まで上がります。あるいは、まだGiant lockがとれていないFreeBSD-currentを4 cpuの計算機で走らせると、高々100程度のprocessでも30程度がGiant待ちを食らってしまいます。これらの現象を観察すると、mutexによるデータ保護はもちろん必要ですし、interrupt threadが不必要に遅延を食らわないようにするためにdispatch delayを減らす努力が必須であることも理解できます。realtimeはその技術を流用したために可能になる後付けであり、決して始めにrealtime有りきではありません。
Re:新機能 (スコア:1)
おっしゃるとおり、応答性と並列性は別のものです。並列性を上げるための仕組みが、カーネル内プリエンプトを可能にする仕組みに流用できるという副次効果があるだけです。
ちなみに、sleep-wakeupによる同期が本質的にはcondition variableと等価ということも知っています。 ま、Linuxの場合、sleepable mutexの導入を考える以前に、ロックの粒度が大きいところを細かくするほうが先決です。今のままCPU数を増やすとファイルシステムの奥の方と、ブロックデバイス周りのロックの粒度が問題になるでしょう。
sleepable mutexを利用する場合も注意が必要だと思います。 sleepable mutexも万能ではなく、あらかじめ短いことがわかっている排他区間で利用するとコストが高くつきます。実際の実装では適当なところで妥協し、馬鹿spinlockと使い分けをするのが良いでしょう。（というかsleepable mutexが不必要なくらい全てのロック区間を短くするのが良い） sleepable mutexを採用するなら、まずLinuxの割り込み処理も、Solarisのようにスレッドとして動けるように書き直すことと、 ロックを握りっぱなしにされないようにプライオリティ継承かシーリングセマフォ的なものの導入することが必須となるでしょう。
ところで、一般にはプライオリティ継承は応答性を高める目的で実装されますが、「プライオリティ継承が必要だ！」と言われているのは、上記sleepable_mutexを前提とした話だったのでしょうか？