並行分散ソフトウェア／並列分散ソフトウェア
電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/sie/pdsoft-2005/2005-12-02
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/sie/
http://www.cs.tsukuba.ac.jp/~yas/
次の３つを合算する。
用語の意義
- 並行 concurrent
- 並列 parallel
- 分散 distributed
歴史
- ＯＳと逐次プログラミング／マルチプログラミング
- 同期通信プリミティブ。ロック、セマフォ、モニタ、ランデブ
- プログラミング言語による支援
- SMP とスレッド
割込みと並行プログラミング
- 逐次
- １度に１つの手続きが実行される
- 並行
- １度に複数の手続きが実行される
複数の手続きを実行する主体は、「プロセス」や「スレッド」。
- 並列
- 速く解きたい
- 分散
- 離れていても心は１つ
逐次処理は非常に特殊。
- 歴史的な都合。ハードウェアが高かった。
- 逐次プログラムの書きやすさ。制限をつけた方がわかりやすい。
共通の話
- (プロセッサが複数)
- プロセスか複数
- プロセス間の協調(coordination)が必要。同期、通信。
- 資源割り当ての最適化、スケジューリングが重要
２つの言語が必要
- 計算言語
- 個々の活動を記述
- 協調言語
- 統一されたプログラムに組み立てるための「糊」
Java など、１つの言語で計算と協調が書けるものもある。
歴史的に重要な出来事と並行プログラミングを学ぶ意義。
講義の最後には、ここで現れるキーワードを理解できることを目標にする（今
日の段階では理解できないものがあってもよい）。
Per Brinch Hansen (Editor): "The Origins of Concurrent Programming:
From Semaphores to Remote Procedure Calls", Springer (2002). ISBN:
0387954015.
Fundamental Concepts
- Asynchronous processes
- Speed independence
- Fire scheduling
- Mutual exclusion
- Deadlock prevention
- Process communication
- Hierarchical structure
- Extensible system kernels
Programming Language Concepts
- Concurrent statements
- Critical regions
- Semaphores
- Message buffers
- Conditional critical regions
- Secure queuing variables
- Monitors
- Remote procedure calls
Java などの近代的なプログラミング言語は、だいたい持っている。
以前は、ＯＳ記述時に、アセンブリ言語やＣ言語で記述。
ハードウェアは、本質的には並列。全部の素子が同時に動く。
プログラムカウンタの発明。プログラム内蔵方式。
ノイマン型コンピュータ。
当初のコンピュータに、ＯＳはない。
１台のコンピュータのメモリに、同時に複数のプログラムをロードして切り替
えながら動作させる。
ハードウェアは、高い。
高いＣＰＵを有効に活用したい。
バッチ処理の誕生。入出力とＣＰＵ処理を「並列」動作させる。
入力-処理-出力
入力-処理-出力
入力-処理-出力
プロセスの概念の確立。プロセスとプログラムの分離。
一般のプログラミングは、逐次のまま。
ＯＳだけ並行プログラミング
- 難しい並行プログラミングをＯＳに閉じ込めて、残りは楽をする。
- ＯＳはがんばって作る
今でもＯＳの教科書には、セマフォやデッドロックの話が出ている。
Concurrent Pascal, Solo。
ＯＳの実装では、実際には、「割り込み禁止」という軽量の相互排除命令が多
用された。
ユーザレベルの命令の例
fork join model
Time sharing system。
１台の中央のコンピュータ（メインフレーム）に、複数の「（文字）端末」を接続。
端末を使っている人からすると専有しているように見える。
TSS で複数のアプリケーションを同時に走らせる。
CPU が貴重な時代。CPU を遊ばせない。
１台のメインフレームに、同時に複数のＯＳを走らせるのが始り。
近年、Virtual PC, VMware 等のパソコン用のＶＭも現れている。
プログラムとデータを分離。
データを中心に考える。
データに integrity を持たせる。
integrity を満たしたデータだけを、きちんと
永続的に保存する。
複数のデータベースへの問い合わせ（検索、更新）を、できるだけ「並行」に
実行する。
効率のため。
最終結果は、１つひとつ逐次的にやったものと同じ。
serializability。
integrity を満たす。
Sun。
資源を共有したい。プリンタ。ディスク。
ディスクレス・ワークステーション。
NFS, NIS, RPC 出現。
X Window。ウインドウのプログラミングは、本質的に並行。
X Windowの実装は、クライアント・サーバ・モデルに基づく。
ただし、後に、モデルを変更した。
サーバからクライアントへのイベントの送信を付けた。
リスナ・パタンへと発展。
- ペトリネット
- CSP, Communicating Sequential Processes
- Actors
- Concurrent Pascal, Distributed Processes(言語の名前)
- Ada
- PLITS, Synchronizing Resources, Cell
- Argus
Ada。アメリカ国防省で仕様を決めた組込み機器用のプログラミング言語。
- 仕様（インタフェース）と実現の分離
- プロセス生成
- ランデブによるプロセス間通信
並行実行。同期。非決定性。ガード付きコマンド。
哲学者の食事問題。生産者消費者問題／有限バッファ問題。デッドロック。
初期の実装は、全部コルーチン。
能動的なオブジェクト。自律性がある。
自律(autonomous, autonomic)の定義が人それぞれ。
人工知能分野の用語でもある。
移動エージェント mobile agent
Flynn の分類
- SISD, Single Instruction, Single Data
- SIMD, Single Instruction, Multiple Data
- MISD, Multiple Instruction, Single Data
- MIMD, Multiple Instruction, Multiple Data
MIMD の分類
Machシステムでの分類
- 共有メモリがある
- アクセスが均質: UMA (Uniform Memory Access), SMP (Symmetric Multiprocessor)
- アクセスが不均質(100倍くらい): NUMA (Non-uniform Memory Access)
- 共有メモリがない: NORMA (No-Remote Memory Access)。
データフローコンピュータ。関数型言語。論理型言語。
第五世代コンピュータ。
逐次に対して、どうやって並列性を抽出するかが主眼。
逐次プログラムでは、マルチプロセッサで走らせても１倍。
特定用途のマルチプロセッサ。
スパコン。ベクトルコンピュータ。
Occam/Transputer。
分散共有メモリ。
fork() は、重たい。
軽いプロセス、スレッドの研究。
OSは、ジャイアント・ロック。
メッセージ・パッシングは、本質的には並行プログラミング。
実際問題は単に手続き呼出し。
obj1.method1();
Smalltalk 80
Sony CSL 横手らによるオブジェクト指向OS。
Object Request Broker。複数の言語を繋ぎたい。
オブジェクト指向が入った RPC 。
- PVM, Parallel Virtual Machine
- MPI, Message Passing Interface
- OpenMP
Arts, RT-Mach, TRON。
ある時間内にある処理が完了することを保証する。
「速い」とか「現在」という意味はない。
The Realtime Operating system Nucleus。
Tron住宅。
Ubiquitousより前。
機器の内部にあり、表面的にはパソコンのようなキーボードやモニタは現れな
い。
小さいものに組込むのが流行り。
以前は工場の「制御用」。
家電製品。東芝 RD-X4EX, RD-Z1 のバグ。
RD-X2 のジャイアントロック。
比較的あたらし。
パソコン用の（フロッピ・）ディスクＯＳ（Disk Operating System）。
一度に１つだけプログラムが動く。
キーボード入出力、フロッピ・ディスクのＤＭＡ転送完了には割込みを使う。
「パソコンで」、一度に複数のプログラムを切り替えながら使える。
CP/M に、Unix 的な機能を入れた
- 階層化ディレクトリ。mkdir, chdir
- 子プロセスは作れる。（自分は止まる。）
「パソコンで」、複数のプログラムを同時に動かしても、うまく動くようになっ
た。
MS Windows 95 は、内部的には、COM/OLE と呼ばれる ORB の固まりで作られ
ている。
パソコンでは、保護の概念が希薄。
TCP/IPの４層モデル。ＯＳＩの７層モデルより古い。
Socket API。もともと Unix 4.2 BSD 用。
socket(), accept(), connect(), select()。
クライアント・サーバ・モデル。
inetd。
貧乏人の Internet。
今の用語だとモデムによるファイル転送によるＰ２Ｐ。
電子メールとネットニュースの記事を運ぶ。
ニュースシステムの仕組みは、分散システムの優れた例になっている。
夜中に走らせる。ソフトの配布と論文投稿。
文字たけでなく、絵が出る。ヘルパーで音も出る。
クライアント・サーバ・モデル。
バッチ処理。
Common Gateway Interface。
最近では、多くの人が、CGI ではじめて並行プログラミングに出会う。
ロックしないとダメ。デッドロックが起り得る。
Webブラウザで、アニメーションを行うために登場。
重たい fork() を避ける。
近代的な RPC。
HTML。XML。HTTP。SOAP。
プログラム・カウンタ回りだけ増やしたもの。
１つのチップに、複数の CPU を載せる。
今の段階では、単に、CPU 2 個あるものを 1 個にまとめたようなもの。
昔の SMP の再現。
Peer-to-peer 。
クライアント・サーバの意義が大事。
クライアント・サーバが現れる前の状況に戻ってはいけない。
Single Point of Failure を避けるという考え方はよい。
マルチプロセッサではない、単一CPUのシステムで、効率的に並行プログラム
を記述するための仕組み。
CPU と周辺装置の並列処理に使う。
ハードウェアの直接的なサポートがある。
割込みのプログラミングは、非常に難しい。デバッガが使えない。
printf() もつかえない。
ただし、並行性の記述については、スレッドのデッドロックよりは、場合によっ
ては簡単かもしれない。
もともとスレッドのプログラムを割込みのプログラムに書き換えるのは
難しい。
入出力装置(デバイス)、デバイス(device)
とは、コンピュータの箱の中に内蔵されているハードウェアの部品やケーブル
で外で接続する部品。
普通は、CPU とメモリ以外のことを指す。
周辺装置(peripheral device)、
入出力装置(IO device)とも呼ばれる。
- ハードディスク
- キーボード
- マウス
- グラフィクス・カード
- ネットワーク・インタフェース
メモリ、ＣＰＵ、デバイスは、バス(bus)(システム・バス(system bus))を通
じて接続されている。
図１ バスにより接続されたＣＰＵ、メモリ、デバイス
バス：何本かの配線の束
- アドレスバス
- メモリのアドレスを示すための線
- データバス
- データを送るための線
- コントロールバス
- その他、制御用の線
各デバイスとCPU で実行されるプログラムとデバイスとり橋渡しをする機器。
例：キーボード用のコントローラの働き
データが、電気信号などの形で送られてくる。コントローラの中のレジスタ
（小容量のメモリ）に保存され。
CPU から見える場所
- デバイス・コントローラが I/O 空間にあり、ポート番号と呼ばれる番地
が振られている。CPU が、ポート番号を指定して入出力命令を実行すると、
I/O 空間にあるレジスタの内容が読み書きできる(I/O 空間を示す信号線が1に
なる)。
- デバイス・コントローラが、普通のメモリと同じ空間にあり、番地が番
地が振られている。CPU が、その番地へ普通のロード命令やストア命令でアク
セスすると、コントローラのレジスタの内容が読み書きできる。
入出力の時に CPU が働くかどうか
- CPU が入出力命令、あるいは、ロード命令／ストア命令を実行する。
- DMA (Direct Memory Access)やバスマスタと呼ばれる機器があり、その
機器がCPU が普通に命令を実行している合間をぬって一時的にバスを乗っ取り、
データをメモリにコピーする。
CPU の速度に比べて、デバイスの速度は遅い。
- 入出力の完了を待っていると CPU の能力が無駄に捨てられる。
- 複数の独立したデバイスは、同時に動かしたい。
- あるプロセスがデバイスへの入出力を行ないたい時、CPU がその処理に
つきっきりになってしまうと、他のプロセスまで先に進めなくなる。
ポーリング(polling):
周期的にデバイス・コントローラの状態をチェックする。
- 周期が短いと、チェックのヘッドが多くなるが、デバイスとの応答はよ
くなる。
- 周期が長いと、その逆。
割込み(interrupt):入出力が可能になった時にデバイスがCPUに知らせる。
- 入力デバイス
- コントローラは、入力データが到着すると、制御バスの割込み要求(IRQ,
Interrupt Request)信号線を1にする。
(DMAやバスマスタを使っている時には、メモリへのコピーが完了した時)
- 出力デバイス
- コントローラは、出力用バッファが空になると、割込み要求信号線を1に
する。
CPU は、割込み要求を受け付けると、現在実行中の処理を中断して、
割込み処理ルーチン
あるいは
割込みハンドラ
と呼ばれるプログラムを実行する。
割込み処理ルーチンでは、実際に入力命令を実行したり、
次のデータを出力を開始する。
最後に、割込み処理から復帰する命令を実行する。すると、先ほど中断してい
た処理が再開される。
相互排除(mutual exclusion)：
ある資源をアクセスできるスレッドの数を
多くても１つにする。
プログラムの字面上、相互排除が必要な部分を
際どい部分(critical section)
(
クリティカルセクション
)
という。
CPUには、割込みを禁止する命令がある。
割込みを禁止は、相互排除に使える。
割り込み禁止の状態で、自分が動いていれば、他のモジュールが動くことはあり得ない。
CPUの命令で1命令から数命令で実装可能である。
int shared_resource ;
interrupt_hander_1()
{
int x;
x = shared_resource ;
x = x + 1 ;
shared_resource = x ;
}
interrupt_hander_2()
{
int x;
x = shared_resource ;
x = x + 1 ;
shared_resource = x ;
}
PDP-11 には、割込み禁止のレベルが 7 段階(3ビット)あった。
SPL (Set Priority Level) 命令。
splhigh(); /* 割り込み禁止 */
＜際どい部分。この間は、相互排除される＞
spl0(); /* 割り込み許可 */
上のプログラムを書き直す。
int shared_resource ;
interrupt_hander_1()
{
int x;
splhigh();
x = shared_resource ;
x = x + 1 ;
shared_resource = x ;
sp0();
}
interrupt_hander_2()
{
int x;
splhigh();
x = shared_resource ;
x = x + 1 ;
shared_resource = x ;
sp0();
}
多重の割込みを許す。
x = spltty(); /* 割り込みレベルを TTY レベルに上げる。 */
＜この間は、TTY レベル以下について相互排除される＞
spl(x); /* 割り込みレベルを元にもどす。 */
NetBSDのマニュアルより: spl(), spl0(), splbio(), splclock(),
splhigh(), splvm(), spllock(), spllowersoftclock(), splnet(),
splsched(), splserial(), splsoftclock(), splsoftnet(),
splsoftserial(), splstatclock(), spltty(), splvm(), splx()
単一プロセッサでは、割込みレベルを調整した方が効率がよいし、
並列性も高くなる。しかし、SMP では、この方法は使えない。
ジャイアント・ロック。splhigh() に頼ったプログラミング。
カーネルの割込み処理のプログラムは難しい。
割込みをプロセス間通信に変換してメッセージ・パッシングの世界でものを考
えたい。
割り込み禁止の時間が短くなり、応答性が上がる。
本当の割り込み禁止や、割込みレベルによる優先度付けができなくなる。
↑[もどる]
・[12月2日]
・[12月9日]
Last updated: 2005/12/09 21:00:02
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>