アカウント名:
パスワード:
たとえセキュリティなどが充実しても、実働OSとしてのWindowsには致命的な欠点があります。それは、user-level threadのサポートが全く存在しないことです。
Win32 APIを眺めた方はご存知でしょうが、user-level threadの間で同期をとる手法としてWin32ではprocess間同期のため(これはkernelの中にある)のAPIをそのまま流用しています。したがって、同期をとるためにuser modeとsupervisor modeの間で遷移を行わなければなりません。これはtrapに伴うcontext保存などのoverheadを伴うため、性能を著しく落とします(Unix上のbenchmarkでは同期に要する
Ureah Vahaliaの本を読んだ限りでは、user-level threadは「kernelにthreadの状態を全く保存しないthreadの実装」であると理解しています。したがってUnixの世界では、libraryだけで十分実装できるものです。Solaris threadの場合、LWPを全く使わないようにすればuser-levelになります(新しいLWPを生成することもできる)。
Solaris/POSIX mutexにおけるstarvationの問題ですが、本質は「Bがmutexを手放した時、Aが次にmutexをとれることを保証する」ことにありそうです。よくあるmutexの実装は、(priorityを考えないとして、この問題にはこれで十分)
lock(m) { while (!try_lock(m, curth)) { enqueue(m, curth); context_switch(); } } unlock(m) { unlock(m, curth); th = dequeue(m); add_dispatchqueue(th); }
while (!try_lock(m, curth)) { enqueue(m, curth); context_switch(); }
enqueue(m, curth); context_switch();
unlock(m, curth); th = dequeue(m); add_dispatchqueue(th);
という感じでしょう。try_lock()にtest-and-setなどを用います。これでは確かにunlock()とlock()が同時に動いた場合、raceしてしまいますね。
素人のあっしが思いつく方法としては(多分誰かやってるだろう)、
lock(m) { if (!try_lock(m, curth)) { enqueue(m, curth); context_switch(); /* curth should have the lock now. */ } } unlock(m) { unlock(m, curth); th = dequeue(m); try_lock(m, th); /* This should succeed. */ add_dispatchqueue(th); }
if (!try_lock(m, curth)) { enqueue(m, curth); context_switch(); /* curth should have the lock now. */ }
enqueue(m, curth); context_switch(); /* curth should have the lock now. */
unlock(m, curth); th = dequeue(m); try_lock(m, th); /* This should succeed. */ add_dispatchqueue(th);
てなものがあります。unlock()するthreadが直ちに次のthreadにlockをとらせるので、両者がraceしないのがミソです。
こんなideaがうまくうごくのか...なんて考えたんで、user-level threadではないのですが実験をしてみました。FreeBSD-currentのin-kernel mutexにこのideaを実装し、freefallから引っ張り出したsrc/sysでGENERIC kernelを作るのに要する時間を比べてみました。
実験機はPII-266 x 2、RAMが256MB。sourceなどがbuffer cacheに入らないよう、boot直後にkernelを作りました。makeには-j 16を与え、Giantなどで衝突しやすいようにしておきました。
time(1)で時間を測った結果なんですが...
と、実時間で1分強、kernel timeで28秒ほど負けました。原因なんですが、以下に示すようにcontext switchの回数が増えたためのようです。
voluntaryとinvoluntaryを合わせると、約3.9倍です。よくよく考えたら、mutexを待っていたthreadを必ず実行させるのだから、unlockにともなってcontext switchも起きる可能性が高くなるわけですよね。mutexはcostが安いことが売りなので、そこに重たいcontext switchを強要するのは本末転倒というオチでした。
th が lock の所有権を持っていても wakeup して active なスレッドになるために幾ばくかの時間がかかると思われます。その間に、m を lock しようとしたスレッドがことごとく block されるのが context switch が増える原因だと思われます。
これで1つ思いあたることが出てきました。実際の実装ではunlock時にthをdispatch queueに放り込んだ後、それが実行中のthreadよりも優先度が高ければcontext switchをしています。ですが、ここが甘いのです。smpの場合、もっとほかに優先度の低いthreadを実行しているcpuがあるかも知れません。その場合、優先度の最も低いthreadを実行しているcpuを探しだし、threadを横取りする必要があります(Solarisはそうしているはず)。
fair mutex vs supervisor-mode lockの問題は... この2つだと、どっちもどっちというぐらいしかいえないです。ただ、user-levelの場合はkernelと違って、scheduler activationの併用により見かけ上のcpuを増やすことができます。これをうまく使えばuser-levelならではの方法がなにかできるかも知れません。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
ナニゲにアレゲなのは、ナニゲなアレゲ -- アレゲ研究家
思うんですが (スコア:1, 興味深い)
よしんば堅くなっても速度が... (スコア:1, 興味深い)
たとえセキュリティなどが充実しても、実働OSとしてのWindowsには致命的な欠点があります。それは、user-level threadのサポートが全く存在しないことです。
Win32 APIを眺めた方はご存知でしょうが、user-level threadの間で同期をとる手法としてWin32ではprocess間同期のため(これはkernelの中にある)のAPIをそのまま流用しています。したがって、同期をとるためにuser modeとsupervisor modeの間で遷移を行わなければなりません。これはtrapに伴うcontext保存などのoverheadを伴うため、性能を著しく落とします(Unix上のbenchmarkでは同期に要する
誤読だった。 (スコア:1)
「Windows には user-level threadのサポートが全く存在しないことです」と書かれていたので、「Windows が "thread" と名づけているものは全部 kernel-level thread (*1)じゃん。user-level thread (*2) は fiber。」と脊髄反射してしまいました。
# 忙しい時にコメントを付けるものをではない(自戒)
OS が標準で用意している同期オブジェクトがタコいという話だったのですね。それに関しては同意します。
Windows の場合、OS が API レベルで用意している同期機構が kernel-level のも
コンタミは発見の母
Re:誤読だった。 (スコア:1)
Ureah Vahaliaの本を読んだ限りでは、user-level threadは「kernelにthreadの状態を全く保存しないthreadの実装」であると理解しています。したがってUnixの世界では、libraryだけで十分実装できるものです。Solaris threadの場合、LWPを全く使わないようにすればuser-levelになります(新しいLWPを生成することもできる)。
Solaris/POSIX mutexにおけるstarvationの問題ですが、本質は「Bがmutexを手放した時、Aが次にmutexをとれることを保証する」ことにありそうです。よくあるmutexの実装は、(priorityを考えないとして、この問題にはこれで十分)
という感じでしょう。try_lock()にtest-and-setなどを用います。これでは確かにunlock()とlock()が同時に動いた場合、raceしてしまいますね。
素人のあっしが思いつく方法としては(多分誰かやってるだろう)、
てなものがあります。unlock()するthreadが直ちに次のthreadにlockをとらせるので、両者がraceしないのがミソです。
落とし穴: context switchの爆発 (スコア:1)
こんなideaがうまくうごくのか...なんて考えたんで、user-level threadではないのですが実験をしてみました。FreeBSD-currentのin-kernel mutexにこのideaを実装し、freefallから引っ張り出したsrc/sysでGENERIC kernelを作るのに要する時間を比べてみました。
実験機はPII-266 x 2、RAMが256MB。sourceなどがbuffer cacheに入らないよう、boot直後にkernelを作りました。makeには-j 16を与え、Giantなどで衝突しやすいようにしておきました。
time(1)で時間を測った結果なんですが...
と、実時間で1分強、kernel timeで28秒ほど負けました。原因なんですが、以下に示すようにcontext switchの回数が増えたためのようです。
169805 involuntary context switches
672156 involuntary context switches
voluntaryとinvoluntaryを合わせると、約3.9倍です。よくよく考えたら、mutexを待っていたthreadを必ず実行させるのだから、unlockにともなってcontext switchも起きる可能性が高くなるわけですよね。mutexはcostが安いことが売りなので、そこに重たいcontext switchを強要するのは本末転倒というオチでした。
Re:落とし穴: context switchの爆発 (スコア:1)
> voluntaryとinvoluntaryを合わせると、約3.9倍です。よくよく考えたら、mutexを待って
> いた threadを必ず実行させるのだから、unlockにともなってcontext switchも起きる可能性
> が高くなるわけですよね。mutexはcostが安いことが売りなので、そこに重たいcontext
> switchを強要するのは本末転倒というオチでした。
実装が分らないのでいい加減なことしか言えませんが、try_lock(m, th) の内容が、m の中にあるオーナースレッドをあらすフィールドに(atomic 命令で) th 書き込むだけの処理だけを行うのでしょうか?
そうだとすると、この処理を加えることで context switch が増える真の原因は、「sleep しているスレッドが mutex lock の所有権を得てしまう」こと、言い換えれば「mutex が遊んでしまう」ことにあると思います。
th が lock の所有権を持っていても wakeup して active なスレッドになるために幾ばくかの時間がかかると思われます。その間に、m を lock しようとしたスレッドがことごとく block されるのが context switch が増える原因だと思われます。
逆に、unlock 時に wait しているスレッドを起こすのは 特に問題ないと思います。
実際、Solaris 2.7 以降は mutex の unlock 時には待っているスレッドを全部叩き起こす competitive hand-off の戦略をとっています。全員が起きても lock を取れるのは 1スレッドだけで、他のスレッドはまた block されるように思えますが、実際にはタイムラグがあるし mutex lock は競合さえおこさなければ短時間で抜けていくので全員がうまくやれるという寸法です。
色々いいましたが、OS カーネルの同期プリミティブに unfair な mutex を使うことはパフォーマンスの面から見ると正しいと思います。そして性能を求めるプログラムを書くためには、同期プリミティブを直に使いながら、ユーザースレッドの優先度を上げ下げして疑似デッドロックを回避するしかないと思われます。
ただ、パフォーマンスよりは互換性・移植性を求めるユーザーも多いわけで、その人たちのためにあまり考えずに使える fair なロックのライブラリを提供してしかるべきだと思います。
その提供がないのは WindowsNT/2000 が 特権モードを介さないでは使えない同期処理 API しか提供しないのと比べて、どちらがより罪が重いのでしょうか?
コンタミは発見の母
Re:落とし穴: context switchの爆発 (スコア:1)
これで1つ思いあたることが出てきました。実際の実装ではunlock時にthをdispatch queueに放り込んだ後、それが実行中のthreadよりも優先度が高ければcontext switchをしています。ですが、ここが甘いのです。smpの場合、もっとほかに優先度の低いthreadを実行しているcpuがあるかも知れません。その場合、優先度の最も低いthreadを実行しているcpuを探しだし、threadを横取りする必要があります(Solarisはそうしているはず)。
fair mutex vs supervisor-mode lockの問題は... この2つだと、どっちもどっちというぐらいしかいえないです。ただ、user-levelの場合はkernelと違って、scheduler activationの併用により見かけ上のcpuを増やすことができます。これをうまく使えばuser-levelならではの方法がなにかできるかも知れません。