091125

加速度モジュールをH8/3664とつないでみました。まずはH8/3664のI2Cモジュー ルでテスト。これでH8/TinyのI2Cまわりを整備がてら、うまくいったら、 LPC2388にもっていく目論み。このKXP84モジュールのVddは2.7V-5.25Vなので 5VのH8でも3.3VのLPC2388でもどっちでもいける。

並行性の細粒度、粗粒度というのは、細粒度はまめにスレッドの操作がいる、 粗粒度はあまりスレッドの操作がいらないということ。この粒度はアプリケー ションによって決まる。そのアプリケーションが取り扱うものに対して、並行 性を抽出した結果、粗粒度であれば、それは並行実行で十分に性能を出せると いうこと。逆に、細粒度にしかならなければ、本質的にその問題は並行実行に 向かないということだ。これはOSの如何を問わずアプリケーションに本質的な こと。
現実問題として、どうしても並行実行に向かない問題では、がんばって並行性 をひっぱり出したところで、同期にかかる時間の方が長くてまったく性能がで ないということになってしまう。
そういう意味では、細粒度のパフォーマンスを上げていくというのは、本来あ まり並列向けではない問題を、それでもなんとか並列で性能を上げようという ことになる。
無駄っぽいけれど、これはトレードオフの問題で、システムのサポートで 性能を上げれる余地がある。
しかし、本当にマルチプロセッサを活用できるのは、粗粒度に分解できる問題 だけだ。そして、そういう問題というのはかなり限られている。もう既にどう いう類いのものしか並列化が効かないというのはわかりきっている。
これとは別に、スレッドにするとプログラムが明瞭に書けるという、プログラ マ視点の楽さがある。僕はこの類いで、すぐに機能ごとにスレッド立ててしま う。これはこれで性能の低下、うっかりしたロックの忘れが嫌な問題だ。ロッ クについては、本質的に横取りが必要でなければ、コルーチンにすることでロッ クの必要性をなくして、性能も向上できる。というのがマイOSにファイバを 導入している理由なのだけど、あまり活用できていない。
本当にベスト尽くすなら、割込みハンドラの終了でそれを処理するスレッドコ ンテキストに切り替えてやるのがいいのかとは思っている。今なら割込みスレッ ドは継続をつかってスタックなしにできている。ならば、割込みハンドラの終 了でその継続を呼べば(その時に割り込まれたスレッドのスタックを使って)、 処理ができる。その処理の後は継続をともなってブロックになるので、またス レッドの切り替えに入る。...いいかも。いずれ実装してみたい。

Adding Scheduler Activations to Mach 3.0

Paul Barton-Davis, Dylan McNamee, Raj Vaswani, and Edward D.Lazowska
University of Washington

Technical Report 92-08-03 Reversed March 1993

の続き。

1. 導入

ユーザ層スレッドを伝統的なカーネルスレドの上に作ると、作成、終了、同期
のような一般の操作の性能に非常に効果がある。しかし残念ながら、、I/Oや、
ページフォルト、プロッセッサの横取りによるカーネル操作によって低性能で
あったり、正しくない動きをする。これはアプリケーションプログラマの板狭
みとして提起された。システムのサービスとしてよく統合されてはいるが普通
の場合の操作が重いカーネルスレッドを使うか、あるいは普通の場合の操作に
は良い性能だが、システムに十分に対応していないユーザスレッドを使うかだ。

この板狭みを解決するために、Andersonら[ABLL92]はスケジューラアクティベー
ションという新しいカーネルの要素を設計した。スケジューラアクティベーショ
ンはユーザ層のスレッドの管理に適切なサポートを提供する。スケジューラア
クティベーションの上に構築されたユーザ層のスレッドはカーネルスレッドの
機能と、ユーザ層のスレッドの柔軟さと性能を組み合わせる。ここ数年で、ス
ケジューラアクティベーションは、ユーザ層の並行性を管理する正しいカーネ
ルの機構だという大方の意見になった。

この論文で述べる、試みの目標はスケジューラアクティベーションをMach3.0に
実装することだった。[RBF+89] この論文はその概念よりもその実装に重点を置
く。 設計上の判断、必要とされるカーネルの変更、CThreadsライブラリにこの
新しいカーネルの構造を使うために追加した事、について述べる。

1.1 ユーザ層スレッド

並行実行を表現する時、並行度の単位が小さければ、細粒度の並行実行はまあ
まあのオーバーヘッドでサポートすることができる。カーネルプロセス(Unixの
ような)は最も粗粒度の並行プログラム以外にはそのコストがあまりにも高いと
認められてきた。MachやTopazのようなマルチプロセッサOSはこの問題にカーネ
ルスレッドを提供することで取り組もうとした。しかしカーネルスレッドもま
たあまりにもコストがかかることがわかり、MachとTopazは現在、そのカーネル
スレッドの上に構築されたユーザスレッドを提供している。Andersonら
[ABLL92] はカーネルスレッドがユーザスレッドに較べたコストは、実装上の問
題ではなく、2つの原因による、それ本来の問題であることを論じた。

+ カーネルサービスのコスト。トラップされてカーネルに入るのは単純な手続
   き呼び出しに較べて、よりコストがかかる。アーキテクチャの潮流は、カー
   ネルトラップは相対的にコストがかかる方向になっている[ALBL91]。さらに、
   間違った振舞いのユーザプログラムから、カーネルを保護するために、シス
   テムを壊すような引数でないかどうか検査しないといけない。ユーザ層のス
   レッドパッケージは、スレッド管理の操作にカーネルトラップのオーバヘッ
   ドを避け、手続き呼出しを使うことができる。さらに、スレッドパッケージ
   は(カーネルスレッドのような)自分自身を守ることをする必要がない。間違っ
   た振舞いのプログラムが壊れるだけだからだ。

+ 一般化のコスト。 カーネルスレッドは全てに対して、全てを提供しないとい
   けない。あるプログラムがいくつかの特別な機能(例えば、ラウンドロビン
   割当て)が必要なくても、その機能が存在しているためのコストを払わない
   といけない。ユーザ層のスレッドパッケージは、それぞれのアプリケーショ
   ンの必要に応じて特別に最適化することができる[BLL88]。

ユーザ層のスレッドは比較的細粒度の並行性を表現するのに有効だということ
がわかった。残念ながら、ユーザ層のスレッドをカーネルスレッドのような、
今あるOSの機構の上に実装するのには難しい点がある。最初の問題は、カーネ
ルスレッドは、ユーザ層の状態にかかわらずスケジュールされること。カーネ
ルのスケジューラと、ユーザのスケジューラは、お互いに衝突してしまう可能
性がある。二番目の問題はI/O、ページフォルト、プロセッサ横取りのようなカー
ネルのイベントによって、ブロックする状態が、ユーザ層にはわからないこと
だ。様々な機構が、これらの問題のそれぞれについて取り組まれた。
[MSLM91][TG89] [Her91]、しかし、全ての困難さを扱った研究はなかった。ス
ケジューラアクティベーションは統合された解決法を提示する。

1.2 スケジューラアクティベーション

スケジューラアクティベーションはカーネルスレッドに代わって、ユーザ層の
並行性の管理をサポートをする。[ABLL92]に紹介されたように、スケジューラ
アクティベーションの環境は、以下の重要な特徴がある。

 + プロセッサはカーネルによってジョブに割合てられる。 プロセッサの割当
   てはカーネルによってユーザ層と通信した情報を元にしてなされる。カーネ
   ルはジョブにスケジューラアクティベーションを与えることで、プロセッサ
   を割当てる。その実体は伝統的なカーネルスレッドと同じようなものだが、
   以下に示す、追加的な特性がある。


 + ユーザ層のスレッドスケジューラはジョブに割当てられたプロセッサで走る
   スレッドの管理をする。カーネルによって与えられたスケジューラアクティ
   ベーションは、ユーザ層のスケジューラがスレッドを多重化する単純な容器
   である。スレッドのスケジューリングや、同期のような一般的な操作はカー
   ネルの介入なしに、ユーザ層において効果的に実行される。

 + ユーザ層が、カーネルにプロセッサ要求の変化を通知する。 ジョブの並行
   性が、その現在のプロセッサ割当てから上下する時にカーネルは通知される。

 + カーネルは、ユーザ層のスケジューラに、そのジョブに影響を及ぼすシステ
   ムイベントを通知する。これらのイベントはカーネルの中で起こる、プロセッ
   サの割当て、横取りや、ブロック、起床を含む。カーネルの役割りは、「イ
   ベントを処理する」から、適切なジョブのユーザ層のスレッド管理システム
   に「イベントを通信する」ことに変わる。これによって、ジョブに対して適
   切な方法でイベントを処理することができるようになる。

 + カーネルはスケジューラアクティベーションを時分割しない。スケジューラ
   アクティベーションはカーネルがジョブにプロセッサを割当てる手段である。
   ジョブは常に正確に、できるだけ多くのスケジューラアクティベーションを
   物理的なプロセッサがあるだけ持つ。カーネルは(与えられた数の)スケジュー
   ラアクティベーションを(より少ない数の)物理的なプロセッサの上に多重化
   することはない。

 + アプリケーションはこの新環境を使うとしても、変更の必要はない。これは
   イベントの管理はユーザ層のスレッド管理システムにカプセル化されている
   からで、そのインターフェースに変更はない。

このシステムに馴染みのない読者は、この先に進む前に[ABLL92]を読むことを
強くお勧めする。