マルチプロセッサとスケジューラ(その2)

前回に続いて、マルチプロセッサとHyperthreading(HT)のスケジューリングに関する話題を取り上げる。最近のIntel等の動向を見ると、チップ上に複数CPUコアを載せる手法(CMPまたはマルチコア)は、今後のプロセッサ市場では一般的になるらしい。

したがって今後のカーネルには、単なるマルチプロセッサ対応というだけでなく、個々のマルチプロセッサ・アーキテクチャを最大限に有効活用できるような機能が望まれる。カーネル2.6では、Ingo MolnarのO(1)スケジューラの導入によって、それまで1つのリストで管理していたプロセス・スケジューリングが、プロセッサ毎にプライオリティを考慮して振り分けられるようになった。O(1)スケジューラのメリットは各所で紹介されているが、Documentation/sched-*.txtには、デザインとコーディングのためのメモが残されている。

IOスケジューリング

またカーネル2.6では、デバイスIOのスケジューリングに関しても改善された。Nick Pigginによる予測(anticipatory) I/Oスケジューラが標準で採用され、ファイル入出力性能が大きく向上したとされている。デバイスIOのスケジューラは、カーネル・ブート時のパラメータで、elevator=as(anticipatory) のほかに、deadlineやcfq、noopを選択する事もできる。Documentation/as-iosched.txtに、Nickによる予測 I/O スケジューラが解説されている。さて前回から登場しているこのNick Pigginは2.6.0のリリース前に、Nick's schedulerと題して、プロセス・スケジューリングのO(1)スケジューラのパッチを盛んにLKMLに投稿していた。

本題に入る前に、まず前回の用語解説を補足する。

一般的なCPUアーキテクチャの呼び名

- CMP (Chip Multi Processor)

1個のプロセッサ・ダイ(チップ)に複数のCPUコアを搭載する技術。ボードには、1個のプロセッサ・ダイを搭載することで容易にSMPが実現できるほか、キャッシュメモリも統合することで、性能面でもメリットがあるとされる。前回紹介したIBM Power4やPower5が相当する。

- SMP (Symmetric Multi Processor)

対称型マルチプロセッサ。基本的に複数のプロセッサを同等に接続する回路を持つ。現在の多くのマルチプロセッサで採用している手法。以前はMP(Multi Processor)というと、非対称型マルチプロセッサ(ASMP=Asymmetric Multiple Processor)も含めて指したため、SMPという名称で区別していた。

- UP (Uni Proocessor)

マルチプロセッサに対して単一プロセッサのことを指す。Hyperthreading(HT)のように、物理的には1個のプロセッサであっても、論理的にSMPとして振舞う技術が出てきたので事態は複雑になってきている。Linuxでは伝統的に、SMPとUPでカーネルのコードを使い分けるようになっている。

ロードバランスとプライオリティ・ハンドリング

カーネル2.6.0のリリースの前後、LKMLでは2003年の年末から2004年にかけてプロセスのロードバランスとプライオリティ・ハンドリングに関する議論がさかんに行なわれていた。

Con Kolivasは次のように言った。彼はオーストラリアの開業医であるが、カーネルの性能比較に有効なConTestの作者である。彼もまた性能向上を目的として、2.5/2.6のO(1)スケジューラのパッチを何回かポストしている。

私はHyperthreadにも対応している、バッチ・スケジューリングの更新を完了した。
バッチ・スケジューリングとは何だろうか?タスクをバッチとして定義することは、多くのNICE値の比率に基いたCPUタイムを持つのではなく、アイドルになったときのCPUタイムを使用することを可能にする。
ではなぜ私は、Hyperthreadにも対応したバッチ・スケジューリングを必要とするのだろうか?
ハイパースレッド(P4HT)プロセッサで、2個の論理的なCPUとして実行させる場合、実行している一つのタスクがいかにプライオリティが高くとも、プライオリティが非常に低いタスクを、物理的なCPU性能の50%を消費して、走らせることができる。例えば、分散コンピューティング・クライアントのsetiathomeを使うときに、ナイス値20でsetiathomeを実行しても、実際にはCPUの半分の速度を消費して動作する。
これはメインラインのカーネルに採用して欲しいと主張しているわけではない。しかし、メインラインにHTスケジューラが採用される場合には、プライオリティが低いタスクが、HT CPUを遅くするのを防ぐ方法を考慮する必要がある。このパッチは、HTプロセッサのための一時的な評価基準と、メインラインで扱うための実証的な方法を提供する。パッチは次の場所にある。
http://ck.kolivas.org/patches/2.6/2.6.0/

Nick Piggin が答えた。

我々がこの問題を扱うことについて、インテルがどれぐらい口をはさむか興味がある。私はいずれにしてもバッチ・スケジューリングについて、プライオリティの何らかのソートを行なうかを考えている。私はPOWER5では、そのための唯一の健全な方法である、ハードウェアによってプライオリティ設定をすることができると考えている。
それから私は、このパッチが醜すぎるので、そのようなエレガントなスケジューラに入ることはできないと思う。あなたには問題はない。なぜならこの問題自体が醜いのだから。
タスクが別の兄弟(sibling)上で走るタスクより下の「delta」プライオリティ・ポイントである場合は、その兄弟(sibling)に制御を移す事というのはどうだろうか。したがって、タイムスライスによるプライオリティ機構が動作し始めることになる。私はこれを、「active unbalance」と呼ぼう!ほかにアドバイスは?

Jun Nakajima が答えた。

現在一般に知られているいるように、論理プロセッサの実行リソースの利用効率は約60%である。それは、プロセッサの実装とその時の負荷に依存する。これは将来、より高くすることができるだろう。そしてそのとき、それらの相対的なプライオリティはさらに高くすることができる。従って私は、一般的なスケジューラ・コードに、そのような特定の実装に依存する要素を、ハード・コーディングすることはよい考えではないと思う。
H/Wベースのプライオリティに関しては、特に有用かどうかは確かではない。非常に多くのイベントがプロセッサの内部で起こり、実行時にリソース・セットの変更がとても急速に要求されるからである。例えばH/Wは実行時に、より速くするために何をすべきかを知っているだろうし、論理プロセッサにプライオリティを課すことは、場合によっては遅くなることがあるからである。

Nick Piggin は、「メカニズムは一般的にして、パラメータは特定のアーキテクチャに依存する。」という彼のアイデアは、共通のスケジューラコードの中に、実装に固有なハードコーディングを含めるものでは無いと答えた。彼もまたハードウェアのことは詳しくないのだが、実際に存在しているハードウェアベースのプライオリティ解決策を提供しないハードウェアが、同じことをするためのソフトウェアを必要とするならば、そういうソフトウェアがあってもいいのではないかと言った。

他のスレッドで、Con はNickの「active unbalance」のアイデアについて言った。

私はIngoとこれについて議論したが、それは我々が考えていたようなものである。恐らく、10の動的プライオリティの相対的なクロスオーバと、事前にある5の静的プライオリティの絶対的なクロスオーバはともに、キューにすることができる。これは実際のところ、UPのHTの場合にだけ必要な方法である。

Nickはそれに反対した。

ロードバランサが行なうべき仕事を含むので複雑ではあるが、SMPのHTでも有効なはずで、一般的なコードにできるはずである。従ってマルチCPUと「同じ問題」となる。ナイス値-20のプロセスは、ナイス値19のプロセスに対して、パフォーマンスの40-55%を失う場合がある。10%では、恐らくその数値は高すぎるのだが、我々が望んでいるところである。5%以下というのが、単一のHT論理プロセッサで起きていることである。

ConはNickのこの提案について、メールを出した後で考え直したとして賛成した。

締めくくりに、Bill Davidsenも言った。

ここには、2つのゴールがある。片方のsibling上でバッチ処理をしないことは、意味がある。私はNick's latestを試した後、Conのpatchを試すつもりである。実際にそれらがうまく動けば、両方とも使用するとしよう。バッチ処理は、サーバでの夜毎の報告書作成にとても役立つだろう。
しかし全体のHTスケジューリングについて、もしそれを決定する方法があった場合、最小のキャッシュ・スラッシングで、2つの(あるいはN個の)プロセスをスケジューリングしたいと思うだろう。私は、2-3kのコード+データのフットプリント(データ容量)を備えた小さな反復する内部のループを持っていたプロセスが、それ以外の他の何かとうまく共存できるのかについては疑問に思う。また、FPUの競合を最小限にすることは、文句なしでさらにパフォーマンスを改善するとは思う。私は、このような情報を得るためのツールが、今のところあるか知らないが、システムが利用可能な間は、どんなスケジューリングも暗闇の中である程度うまく働いているように見える。

Conは、複数のパッチはうまく動作しないと言った。しかし、それらはなんらかの方法でともに生かす方法がある。Billは情報を得るツールの存在に関して求めた。Conが次のように付け加えた。

現在のツールでは不可能である。ユーザスペースだけが、これを予測する機会を得るだろう。また、我々が少しずつ作業している単純なルールは、ユーザスペースを信頼することができないということである。したがって、これが近い将来すぐにできるようにはならないということである。

結局Billは、この問題の解決策なしで多くの前進をするのは難しいだろうと考えた。というわけで中途半端ではあるが、次回に続く。