100128

FF13続き。ミッションのD,Cクラスを全部五つ星にしました。これらは今迄あま り使うことのなかったサッズをメインでやってみた。ライト、サッズ、ホープ の三人は武器でATB加速をかけれるので、サッズの武器はフォーマルハウト Lv40にまでしてみた。これで最高のATB加速30%に。

ファルシ=タイタンのミッションの途中にCクラスで五つ星をとってないのがあっ たので、それをとったついでにM47のラクタビージャの五つ星に挑戦。成功!

ファング/スノウ/ヴァニラで魔法耐性を52%/47%/39%まであげて、武器は目標タイムを伸ばすために攻撃力がない物に。





JAM/BLA/JAMで、とにかくスロウを入れる。後はBLA/BLA/BLAでチェーンを稼ぐ。 「れんぞくま」もここまで耐性あげればどってことないので放置。ブレイクし たらATK/ATK/BLA。あともう一削りのところでハイウィンドを入れるつもりがブ レイクが切れてしまってもう一回ブレイクすることになってしまったけれど、 五つ星!
TPあればヒーラーいらないので、ブレイク後にATK/ATK/ATKできるPTにすればもっ とよかったかも。

スケジューラアクティベーション続き。ここでのターゲットになっているOSは TopazというMachのようなマイクロカーネルだ。この手のマイクロカーネルの場 合、UXサーバを実行するだけでかなりの量のスレッドを立ちあげることになる ため(それはユーザ/カーネルの境界の設定を間違えたことに起因する)、スレッ ドの実行性能を上げないといけないという背景がある。スレッドの数が多いた め、1:1スレッドではトラップのオーバーヘッドがきついということ、それぞれ のスレッドについてカーネルスタックをもたないといけないため、その領域が メモリを圧迫する。モノリシックカーネルの場合、カーネルの実行自体にはほ とんどスレッドは必要ないのでスケジューラアクティベーションの切実な必要 性はない。

Scheduler Activations: Effective Kernel Support for the User-Level
Management of Parallelism

Thomas E.Anderson, Brian N.Bershad, Edward D.Lazowska and Henry M.Levy
University of Washington

ACM Transactions on Computersystems, Vol.10, No.1, February 1992,p53-79.


Mach[21]、Topaz[22]、V[7]のようなマルチプロセッサOSはアドレス空間毎のス
レッドをカーネルで直接提供している。カーネルスレッドを使ってプログラム
することで、ユーザ層スレッドによって問題となったシステムの整合性の問題
を回避できる。カーネルはそれぞれのアプリケーションのスレッドを物理プロ
セッサに直接スケジュールするからである。あいにくカーネルスレッドは伝統
的なUNIXプロセスと同じように多くの並行プログラムにとって、あまりにも重
い。カーネルスレッドの性能は一般に一桁程度伝統的なプロセスよりも良いが、
ユーザスレッドの良い事例(つまり、並行処理とI/Oがない)の性能に較べて一桁
悪い。結果として、Mach(CThreads[8])とTopaz(WorkCrews[24])のユーザ層のス
レッドはついにカーネルスレッドの上に実装されることになった。ユーザ層の
スレッドは伝統的なプロセスの上に構築されるのとまったく同じようにカーネ
ルスレッドの上に構築される; それらはちょうど同じような性能であり、同じ
問題を抱える。

並行プログラマはそして難しい板狭みに直面することになった: 単一プログラ
ムでI/Oがないアプリケーションには良い性能と正しい振舞いをするユーザ層を
使うか、性能は悪いがそのような制限のないカーネルスレッドを使うかだ。

1.2 この研究の目標

この論文ではこの板挟みに取り組む。カーネルスレッドの機能とユーザ層スレッ
ドの柔軟性と性能を組み合わせたカーネルインターフェースとユーザ層のスレッ
ドパッケージを述べる

具体的には、

 - スレッドの操作にカーネルの仲介が必要ない一般的な事例では、一番良い出
   来のユー ザ層スレッド管理システム(これはシステムによく統合されていな
   いという問題があるが)との性能と本質的に同じである。

 - プロセッサの再割当てや、I/Oのようなカーネルの介入が必要となる、まれ
   な場合では、カーネルスレッド管理システムの振舞いをまねることができる:

   - 準備完了なスレッドがある場合にはプロセッサが待機することがない。
   - 高優先度のスレッドが低優先度のスレッドの走行の間、待つことはない。
   - スレッドがカーネルにトラップされてブロックする時(例えばページフォ
     ルトにより)、そのスレッドに使われていたプロセッサは他のスレッド(ア
     ドレス空間を問わない)に使うことができる。

 - 我々のシステムのユーザ層の部分はアプリケーション固有な注文を簡単にす
   るように構成されている。スケジューリング方針を変更するのも簡単である
   し、workers[16],Actors[1],Futures[10]のような、異る並行モデルさえも
   用意できる。

これらの目標をマルチプロセッサ上の並行プログラムで達成する難しさは、必
要な制御やスケジューリングの情報をカーネルとそれぞれのアプリケーション
のアドレス空間に分配されるということである。アプリケーションの間にプロ
セッサを割当てることを可能にするために、カーネルはユーザ層のスケジュー
リングの情報が必要である(つまりそれぞれのアドレス空間は、どの程度の並行
度があるか)。アプリケーションの並行性を管理するために、ユーザ層のスレッ
ドシステムは、プロセッサ再割当てや、I/O要求、終了のような、普通アプリケー
ションには隠されているカーネルの事象について知っている必要がある。

1.3 やり方

我々のやり方では、それぞれのアプリケーションに仮想マルチプロセッサを提
供する。専用の物理マシンの抽象化である。それぞれのアプリケーションはい
くつの(どこの)プロセッサが割当てられたかを正確に知っていて、そのスレッ
ドのどれがこれらのプロセッサで走行するかについて完全に制御する。OSカー
ネルはアドレス空間の間でプロセッサの割当てを完全に制御し、それには
アプリケーションの実行中にプロセッサの割当ての数を変更することも含む。

これらを達成するために、カーネルは、そのアドレス空間のスレッドスケジュー
ラにそのアドレス空間に影響するあらゆるカーネルの事象を通知し、アプリケー
ションにそのスケージューリング状態について完全な情報を与える。それぞれ
のアドレス空間のスレッドシステムはカーネルに、プロセッサ割当ての決定に
影響を与えるユーザ層のスレッド操作を通知し、カーネルに反映する必要のな
い大部分のスレッド操作の性能は良いままである。

これらの考えを実現するに使ったカーネルの機構を「スケジューラアクティベー
ション」と呼んだ。スケジューラアクティベーションはカーネルイベントによ
る制御をカーネルからアドレス空間スレッドスケジューラに移行する。そのス
レッドスケジューラはそのアクティベーションをユーザ層のデータ構造を変更
したり、ユーザ層のスレッドを実行したり、カーネルへの要求を作成したりす
るのに使うことができる。

この設計の試作はDEC SRCのFireflyマルチプロセッサワークステーション[22]
によってなされた。スケジューラアクティベーションとカーネルスレッドの違
いは大きいものの、類似点も十分にあるので、カーネル側の実装はTopazのカー
ネルスレッドへの比較的卒直な改造で済んだ。TopazはFirefly由来のOSである。
同じように、ユーザ層への実装は、比較的卒直なFast threads(これはTopazの
カーネルスレッドの上に構築されるように設計されたユーザ層スレッドシステ
ムである)への改造で済んだ。

我々の目標は、カーネルスレッドの機能を正確にユーザ層で用意できることを
示すことであるため、この論文での発表は、ユーザ層のスレッドはプログラマ
あるいはコンパイラによって使われている並行性モデルであることと仮定する。

他の並行性モデルで、それがカーネルスレッドあるいはプロセスの上に構築さ
れたユーザ層であり、ユーザ層スレッドと同じような問題があるのであれば、
それらをスケジューラアクティベーションの上に構築することで問題は解決さ
れる。

2. ユーザ層スレッド: 性能的な優位さと、機能の制限

この章では、我々の研究の動機は、ユーザ層スレッドがカーネルスレッドに較
べて優位であること、ユーザ層スレッドをカーネルスレッドやプロセスの上に
構築することによる困難さである。ユーザ層スレッドの性能は、実装上の問題
ではなく、本質的にカーネルスレッドより良いことを示す。ユーザ層スレッド
は、さらにプログラミングモデルや実行環境に対して柔軟性ががある。その上、
ユーザ層スレッドによって明らかになったシステムの問題はユーザ層スレッドに
起因するものではなく、不適切なカーネル支援によるものであることを示す。

2.1 ユーザ層スレッド管理

ユーザ層スレッドにある最適化がカーネルにも適用でき、それが機能の妥協な
くユーザ層スレッドと同じように効果があると考えるのは自然である。あいに
くカーネル内のスレッドを管理するには本質的にとても高くつくものがある:

 - スレッド管理の操作の費用: カーネルスレッドではプログラムは全てのスレッ
   ド操作で、余分の保護境界をまたがないといけない。同じアドレス空間でス
   レッドをスイッチする時であってもだ。これは余計なカーネルトラップだけ
   でなく、引数をコピーして、それを検査しなくてはならない。カーネルはバ
   グっていたり、悪意のあるプログラムから守らないといけないからだ。対照
   的にユーザ層スレッドの操作はまったく楽に処理することができて、コンパ
   イラがコードをインライン展開し、洗練されたレジスタ割当てをすると、と
   りわけ良い。その上、安全性は妥協できる: アドレス空間の境界があるので
   ユーザ層スレッドシステムの間違った使用があったとしても、問題ない。

 - 一般化の費用: カーネルスレッド管理では、一つの実装を全てのアプリケー
   ションが使用する。一般的にするために、カーネルスレッドシステムは、妥
   当なアプリケーションで必要となる全ての機能を提供しないといけない; こ
   れは特定の機能を必要としないアプリケーションにとっては余計な費用とな
   る。対照的にユーザ層スレッドはアプリケーションによって別のスレッドラ
   イブラリをリンクすることができるので、そのアプリケーションの必要なだ
   けのシステムを提供することができる。例えば、多くの並行アプリケーショ
   ンが単純なFIFOのようなスケジューリング[24]を使うことができるのに、多
   くのカーネルスレッドシステムは優先度横取りスケジューリングを実装して
   いる

これらの要因はスレッド管理の操作が本質的に重いものであれば重要でなかっ
ただろう。カーネルへのトラップや優先度スケジューリングの費用は、例えば
UNIXのプロセスのような大きな費用のかかる場合では大きな問題ではなかった。
しかしながら、スレッド操作の費用は関数呼出しの費用になり得る。なのでカー
ネル実装によって追加されるいかなる費用も、例え少なくともそれは多大であ
り、良い実装のユーザ層スレッドシステムは、良い実装のカーネルスレッドシ
ステムよりずっとよい性能となる。