並行システム
システム情報系情報工学域,
システム情報工学研究科コンピュータサイエンス専攻
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2017/2017-10-06
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/
科目番号
- 01CH303: 一般コース
- 01CJ217: 高度IT専修コース
成績の付け方。次のものを合算する。
欠席した日についても、レポートを提出すること。
印刷物は、配布しない。必要なら自分で印刷しなさい。
用語の意義
- 並行 concurrent
- 並列 parallel
- 分散 distributed
ハードウェア
- UMA (Uniform Memory Access), SMP (Symmetric Multiprocessor)
- NUMA (Non-uniform Memory Access)
- NORMA (No-Remote Memory Access)
歴史 history
- ＯＳと単一プログラミング／マルチプログラミング OS and sequential programming/ multiprogramming
- 同期通信プリミティブ。ロック、セマフォ、モニタ、ランデブ。
Synchronization primitives. locks, semaphores, monitors, rendezvous.
- プログラミング言語による支援。
Programming language support.
- SMP とスレッド。
SMP and threads.
割り込みと並行プログラミング
Interrupts and concurrent programming
- 割り込み禁止による相互排除。
mutual exclusion by disabusing interrupts
- 逐次 sequential
- １度に１つの手続きが実行される
- 並行 concurrent
- １度に複数の手続きが実行される
main()
{
printf("hello, world!\n");
}
逐次プログラムでは、1度に1つの手続き(関数)(procedure(function))しか実行
されない。printf() が動くと main() は止まる。
複数の手続きを実行する主体は、「プロセス(process)」や「スレッド
(thread)」。
図? 逐次プログラムと並行プログラムの動作(時間と空間の観点から)
並列処理と分散処理の目的
- 並列 parallel
- １つの問題を（逐次処理より）速く(faster)解きたい
- 分散 distributed
-
- 離れていても心は１つ sharing one heart between two separate lovers
- 1台のコンピュータに乗らないデータを扱いたい(並列の一種)
逐次処理は非常に特殊。
- 歴史的な都合。ハードウェアが高価だった。
- 逐次プログラムの書きやすさ。制限をつけた方がわかりやすい。
並行プログラミング（並列、分散、その他）の共通の話
- (プロセッサが複数) (multiple processors)
- プロセスが複数 multiple processes
- プロセス間の協調(coordination)が必要。同期(synchronization)、通信(communication)。
- 資源割り当て(resource allocation)、スケジューリング(scheduling )が重要。
単一プロセッサでの並行プログラミングもある。後述。
concurrent programming in a single processor.
２つの言語が必要
- 計算言語 computational languages
- 個々の活動を記述
- 協調言語 coordination languages
- 統一されたプログラムに組み立てるための「糊(glue)」
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 などの近代的なプログラミング言語は、だいたい持っている。
以前は、ＯＳ記述時に、アセンブリ言語やＣ言語で記述。
ハードウェアは、本質的には並列。全部の素子が同時に動く。
プログラムカウンタの発明。プログラム内蔵方式。
ノイマン型コンピュータ。
当初のコンピュータに、ＯＳはない。
１台のコンピュータのメモリに、同時に複数のプログラムをロードして切り替
えながら動作させる。
ハードウェアは、高い。
高いＣＰＵを有効に活用したい。
バッチ処理の誕生。入出力とＣＰＵ処理を「並列」動作させる。
図? バッチ処理における CPU と入出力装置の並列動作 (parallel processing of CPU and I/O in batch processeing)
プロセスの概念の確立。プロセスとプログラムの分離。
一般のプログラミングは、逐次のまま。
ＯＳだけ並行プログラミング
- 難しい並行プログラミングをＯＳに閉じ込めて、残りは楽をする。
- ＯＳはがんばって作る
今でもＯＳの教科書には、セマフォやデッドロックの話が出ている。
Concurrent Pascal, Solo。
ＯＳの実装では、実際には、「割り込み禁止」という軽量の相互排除命令が多
用された。
OSがある集中型システム。
技術的に確立している。
図? 集中型システムのハードウェア (hardware of a centralized system)
ユーザレベルの命令の例
fork join model
Time sharing system。
１台の中央の大型コンピュータ(mainframe)に、複数の「（文字）端末
(terminal)」を接続。
端末を使っている人からすると専有しているように見える。
TSS で複数のアプリケーションを同時に走らせる。
CPU が貴重な時代。CPU を遊ばせない。
図? メインフレームと端末(a mainframe and terminals)
１台のメインフレームに、同時に複数のＯＳを走らせるのが始り。
TSS の実装方法の１つでもあった。
最近は、
コンピュータの高速化で、性能が余ってきた。もともとハードウェアｎ台でやっ
ていた仕事を、ハードウェアとしては１台に集約する。並列処理の逆。
図? 仮想計算機によるサーバの集約(集約前) (before server consolidation by virtual machines)
図? 仮想計算機によるサーバの集約(集約後) (after server consolidation by virtual machines)
1999年VMware Workstation 以降、パソコン用の VM も広く使われる。
プログラムとデータを分離。データを複数のプログラムで共有(share)。
データを中心に考える。
データに integrity を持たせる。
integrity を満たしたデータだけを、きちんと
永続的(persistent)に保存する。
複数のデータベースへの問い合わせ（検索、更新）を、できるだけ「並行
(concurrent)」に実行する。
効率のため。
最終結果は、１つひとつ逐次的(sequential)にやったものと同じ。
serializability。
integrity を満たす。
Sun。
資源を共有したい。プリンタ。ディスク。
ディスクレス・ワークステーション。
Socket API。
NFS, NIS, RPC 出現。
もともと Unix 4.2 BSD 用。
socket(), listen(), accept(), connect(), send(), recv(), select()。
複数の通信プロトコル(TCP/IP以外も)を扱える。
遠隔手続呼出し。プロセス間通信(interprocess communication)だが、一見、
手続き呼び出し(procedure calls)に見える。
X Window。ウインドウのプログラミングは、本質的に並行(inherently concurrent)。
X Windowの実装は、クライアント・サーバ・モデル(client server model)に基づく。
ただし、後に、モデルを変更した。
サーバからクライアントへのイベント(events)の送信を付けた。
リスナ・パタン(listener pattern)へと発展。
- ペトリネット Petri Net
- CSP (Communicating Sequential Processes)
- Actors
- Concurrent Pascal, Distributed Processes(言語の名前)
- Ada
- PLITS, Synchronizing Resources, Cell
- Argus
Ada。アメリカ国防省(US DoD, Department of Defence)
で仕様を決めた組み込みシステム(embedded systems)用の
プログラミング言語。
- 仕様(specification)（インタフェース(interface)）と実現(implementation)の分離
- プロセス生成
- ランデブ(rendezvous)によるプロセス間通信
並行実行(concurrent execution)。同期(synchronization)。非決定性
(non-determinism)。ガード付きコマンド(guarded commands)。
哲学者の食事問題(dining philosophers problem)。生産者消費者問題
(producer-consumer problem)／有限バッファ問題(bounded buffers)。デッド
ロック(deadlock)。
初期の実装は、全部コルーチン(coroutine)。
能動的なオブジェクト(active objects)。自律性(autonomous, autonomic)がある。
自律(autonomous, autonomic)の定義が人それぞれ。
人工知能(artificial intelligence)分野の用語でもある。
移動エージェント mobile agent
プログラムをオブジェクト(objects)の集合で書く。
オブジェクトは、人間のように、自律(autonomous, autonomic)している。
オブジェクトの内部のデータは外から触れない。データベースの逆。
オブジェクトの内部をアクセスするには、メッセージ(message)を送るしかない。
オブジェクト指向プログラミングは、本質的には並行プログラミング。
実際問題は単に手続き呼出しの実装が多い。
obj1.method1();
Smalltalk 80
オブジェクト指向データベース(object-oriented databases)の矛盾。
Sony CSL (Computer Science Laboratory) 横手らによるオブジェクト指向OS。
Object Request Broker。複数の言語を繋ぎたい。
オブジェクト指向が入った RPC 。
- PVM, Parallel Virtual Machine
- MPI, Message Passing Interface
- OpenMP
Arts, RT-Mach, TRON。
ある時間内にある処理が完了することを保証する(guarantee)。
「速い」とか「現在」という意味はない。
The Realtime Operating system Nucleus。
Tron住宅。
Ubiquitousより前。
機器の内部にあり、表面的にはパソコンのようなキーボードやモニタは現れな
い。
小さいものに組込むのが流行り。
以前は工場の「制御用(control)」。
家電製品。炊飯器など。
The Internet of Things.
Cyber-Physical Systems (CPS).
比較的あたらし。
パソコン用の（フロッピ・）ディスクＯＳ（(floppy)Disk Operating System）。
一度に１つだけプログラムが動く。
キーボード入出力、フロッピ・ディスクのＤＭＡ転送完了には割り込みを使う。
「パソコンで」、一度に複数のプログラムを切り替えながら使える。
CP/M に、Unix 的な機能を入れた。
- 階層化ディレクトリ(hierarchical directories)。mkdir, chdir
- 子プロセスは作れる(child processes)。（自分は止まる。）
「パソコンで」、複数のプログラムを同時に動かしても、うまく動くようになっ
た。
MS Windows 95 は、内部的には、COM/OLE と呼ばれる ORB の固まりで作られ
ている。
パソコンでは、保護の概念が希薄。
TCP/IPの４層モデル。
OSI の７層モデル(seven layer model)より古い。
クライアント・サーバ・モデル(client server model)。
inetd (Internet daemon)。
貧乏人の Internet。poor man's Internet
今の用語だとモデム(modem)によるダイヤルアップ(dial up)接続を用いた
peer-to-peer (P2P) 型のファイル転送(file transfer)。
電子メール(email)とネットニュース(netnews, Usenet)の記事を運ぶ。
ニュースシステム(news system)の仕組みは、分散システムの優れた例になっている。
ソフトの配布と論文投稿。
anonymous ftp。archie.
夜中に走らせるのが礼儀。
文字たけでなく、絵が出る。ヘルパーで音も出る。
クライアント・サーバ・モデル(client server model)。
バッチ処理風(batch processing like)。
Common Gateway Interface。
最近では、多くの人が、CGI ではじめて並行プログラミングに出会う。
ロックしないとダメ。デッドロックが起り得る。
Webブラウザで、アニメーションを行うために登場。
重たい fork() を避ける。
近代的な RPC。
HTML。XML。HTTP。SOAP。
プログラム・カウンタ回りだけ増やしたもの。
１つのチップに、複数の CPU を載せる。
今の段階では、単に、CPU 2 個あるものを 1 個にまとめたようなもの。
昔の SMP −＞ UMA の再現。コア数、チップ数が増えるに従い、
不均質になる。
Peer-to-peer 。
クライアント・サーバの意義が大事。
クライアント・サーバが現れる前の状況に戻ってはいけない。
Single Point of Failure を避けるという考え方はよい。
- データセンター(data centers)に資源を集中させる
- 複数企業で資源を共有する。
メインフレームによるTSSの再来か。
シングルプロセッサは、１台のコンピュータにプロセッサが CPU が 1 つ、メ
モリも 1つ。
ネットワークで接続された複数のコンピュータ(multiple computers that are
connected with a network)から構成される分散システム(distributed
systems)と対比する時には、集中型システム(centralized systems))と呼ばれ
る。
技術的に確立している。
図? 集中型システムのハードウェア (hardware of a centralized system)
Flynn の分類 (Flynn's taxonomy)
- SISD, Single Instruction, Single Data
- SIMD, Single Instruction, Multiple Data
- MISD, Multiple Instruction, Single Data
- MIMD, Multiple Instruction, Multiple Data
MIMD の分類
- 共有メモリがある(with shared memory)
- 共有メモリがない(without shared memory)
Machシステムでの分類 ( Mach operating system kernel, Mach microkernel )
- 共有メモリがある(with shared memory)
- アクセスが均質: UMA (Uniform Memory Access), SMP (Symmetric Multiprocessor)
- アクセスが不均質(100倍くらい): NUMA (Non-uniform Memory Access)
- 共有メモリがない: NORMA (No-Remote Memory Access)。
データフローコンピュータ(data flow computer)。関数型プログラミング
(functional programming)。論理型プログラミング(logic programming)。第五
世代コンピュータ(the fifth generation computer)。
逐次に対して、どうやって並列性(parallelism)を抽出するかが主眼。
逐次プログラムでは、マルチプロセッサで走らせても１倍。
特定用途のマルチプロセッサ(special purpose parallel computer)。
スパコン(super computers)。ベクトルコンピュータ(vector computers)。
Occam/Transputer。CSPの実装。
MMU (memory management unit)の活用。分散共有メモリ(distributed shared
memory, distributed virtual memory)。
図? 共有メモリ型マルチプロセッサ(バス共有) (Shared memory multiprocessor (with a shared bus))
- Symmetric multiprocessor (SMP)とも言う。メモリへのアクセス時間がどの場所も対称的で均質(symmetric)。
- 分散システムには分類しないのが普通。
集中システムのプログラムがそのまま動作するので。
- キャッシュの親和性(cache affinity)まで考えると分散的な技術がいる。
メモリの整合性(memory consistency)まで考えると、本当はかなり難しい。
- マルチコアCPU (multi-core CPU)は、単体でSMP分類される。歴史的には古い。
図? 共有メモリ型マルチプロセッサ(クロスバースイッチ) (shared memory multiprocessor with a crossbar switch)
複数のCPUが別のメモリに同時にアクセスできる。
同じメモリならバスと同様に衝突する。
共有メモリ型マルチプロセッサをうまく使いたいが、fork() は、重たい。
軽いプロセス(lightweight processes)、スレッド(threads)の研究。
OSは、ジャイアント・ロック(giant lock)。
図? 非均質共有メモリ型マルチプロセッサ (shared memory multiprocessor with non-uniform memory access)
相互結合ネットワークで、遠隔のメモリを CPU から直接アドレスでアクセス
できる。ただし、速度は 100 倍くらい遅い。
図? LANに接続されたPC
遠隔のメモリは、アクセスできない(no remote memory access)。
機種が違う(heterogeneous)こともある。
図? 2次元トーラス
格子状だが、端が反対側とつながっている。
世の中、3次元なので、2次元トーラスの配線は簡単。
3次元以上のトーラスも可能だが、配線が大変になる。
マルチプロセッサではない、単一CPUのシステムで、効率的に並行プログラム
を記述するための仕組み。
CPU と周辺装置の並列処理に使う。
ハードウェアの直接的なサポートがある。
割り込みのプログラミングは、非常に難しい。デバッガが使えない。
printf() もつかえない。
ただし、並行性の記述については、スレッドのデッドロックよりは、場合によっ
ては簡単かもしれない。
もともとスレッドのプログラムを割り込みのプログラムに書き換えるのは
難しい。
入出力装置(デバイス)、デバイス(device)
とは、コンピュータの箱の中に内蔵されているハードウェアの部品やケーブル
で外で接続する部品。
普通は、CPU とメモリ以外のことを指す。
周辺装置(peripheral device)、
入出力装置(IO device)とも呼ばれる。
- ハードディスク(hard disks)
- キーボード(keyboard)
- マウス(mouse)
- グラフィクス・カード(graphics card)
- ネットワーク・インタフェース・カード(network interface card)
メモリ、ＣＰＵ、デバイスは、バス(bus)(システム・バス(system bus))を通
じて接続されている。
図? バスにより接続されたＣＰＵ、メモリ、デバイス(CPU, memory, and I/O devices connected with a bus)
バス(bus)：何本かの配線の束
- アドレスバス (address bus)
- メモリのアドレスを示すための線
- データバス (data bus)
- データを送るための線
- コントロールバス (control bus)
- その他、制御用の線
各デバイスとCPU で実行されるプログラムとデバイスとり橋渡しをする機器。
例：キーボード用のコントローラの働き
データが、電気信号などの形で送られてくる。コントローラの中のレジスタ(register)
（小容量のメモリ）に保存され。
CPU から見える場所
- デバイス・コントローラが I/O 空間にあり、ポート番号(port number)と
呼ばれる番地が振られている。CPU が、ポート番号を指定して入出力命令(I/O
instruction)を実行すると、I/O 空間にあるレジスタの内容が読み書きできる
(I/O 空間を示す信号線が1になる)。
- デバイス・コントローラが、普通のメモリと同じ空間にあり、メモリ番地
(memory address)が振られている。CPU が、その番地へ普通のロード命令
(load instruction)やストア命令(store instruction)でアクセスすると、コン
トローラのレジスタの内容が読み書きできる。MMIO (Memory mapped I/O).
入出力の時に CPU が働くかどうか
- CPU が入出力命令(I/O instruction)、あるいは、ロード命令(load
instruction)や／ストア命令(store instruction)を実行する。
- DMA (Direct Memory Access)やバスマスタと呼ばれる機器があり、その
機器がCPU が普通に命令を実行している合間をぬって一時的にバスを乗っ取り、
データをメモリにコピーする。
CPU の速度に比べて、デバイスの速度は遅い。
- 入出力の完了を待っていると CPU の能力が無駄に捨てられる。
- 複数の独立したデバイスは、同時に動かしたい。
- あるプロセスがデバイスへの入出力を行ないたい時、CPU がその処理に
つきっきりになってしまうと、他のプロセスまで先に進めなくなる。
解決策
- ポーリング(polling)
-
周期的(periodic)にデバイス・コントローラの状態をチェックする。
- 周期が短いと、チェックのヘッドが多くなるが、デバイスとの応答はよ
くなる。
- 周期が長いと、その逆。
- 割り込み(interrupt)
- 入出力が可能になった／DMA転送が完了した時にデバイスがCPUに知らせる。
- 単位が荒い時には、ポーリングよりよい。
- 割り込みが細かすぎる（毎秒数100以上）、割り込み処理の
オーバヘッドが大きくなる。
- プログラミングが難しい。
割り込みのタイミング
- 入力デバイス(input device)
- コントローラは、入力データが到着すると、制御バスの割り込み要求(IRQ,
Interrupt Request)信号線を1にする。
DMAを使っている時には、メモリへのコピーが完了した時に
信号線を1にする。
- 出力デバイス(output device)
- コントローラは、出力用バッファ(output buffer)が空(empty)になると、
割り込み要求信号線を1にする。
CPU は、割り込み要求を受け付けると、現在実行中の処理を中断して、
割り込みサービスルーチン(Interrupt Service Routine)
あるいは
割り込みハンドラ(interrupt handler)
と呼ばれるプログラムを実行する。
割り込み処理ルーチンでは、実際に入力命令を実行したり、
次のデータを出力を開始する。
最後に、割り込み処理から復帰する命令を実行する。すると、先ほど中断してい
た処理が再開される。
図? OSの上半分と下半分
カーネル・モードのユーザ・プロセスと割り込みハンドラが共有データをアクセ
スする。
注意: Linux では、top half と bottom half を別の意味で使っている。
情報科学類「オペレーティングシステムII」の資料
参照。
相互排除(mutual exclusion)：
ある資源をアクセスできるスレッドの数を多くても１つにする。
プログラムの字面上、相互排除が必要な部分を
際どい部分(critical section)
(
クリティカルセクション
)
という。
CPUには、割り込みを禁止/許可する命令がある。
例: x86
di # disable interrupts
....
ei # disable interrupts
単一プロセッサでは、割り込み禁止を使って相互排除を実現できる。
割り込み禁止の状態で、自分が動いていれば、他のモジュールが動くことはあり得ない。
割り込み禁止は、軽い(lightweight)。CPUの命令で1命令から数命令で実装可能である。
マルチプロセッサでは、割り込み禁止を使って相互排除を実現できない。
In a multiprocessor system, it is impossible to realize mutual exclusion by disabling interrupts.
int shared_resource ;
user_process()
{
int x;
x = shared_resource ;
x = x + 1 ;
shared_resource = x ;
}
interrupt_handler()
{
int x;
x = shared_resource ;
x = x + 1 ;
shared_resource = x ;
}
PDP-11 には、割り込み禁止のレベルが 7 段階(3ビット)あった。
SPL (Set Priority Level) 命令。
splhigh(); /* 割り込み禁止 disable interrupt */
＜際どい部分。critical section.＞
spl0(); /* 割り込み許可 enable interrupt */
上のプログラムを書き直す。
int shared_resource ;
user_process()
{
int x;
splhigh();
x = shared_resource ;
x = x + 1 ;
shared_resource = x ;
spl0();
}
interrupt_handler()
{
int x;
splhigh();
x = shared_resource ;
x = x + 1 ;
shared_resource = x ;
spl0();
}
多重の割り込みを許す。
x = spltty(); /* 割り込みレベルを TTY レベルに上げる。
Block interrupts from TTY devices (IPL_TTY). */
＜この間は、IPL_TTY レベル以下について相互排除される。
Mutual exclusion for IPL_TTY and lower. ＞
spl(x); /* 割り込みレベルを元にもどす。
Restore the system priority level to the previous one. */
NetBSD man page: spl(), spl0(), splbio(), splclock(), splhigh(),
splvm(), spllock(), spllowersoftclock(), splnet(), splsched(),
splserial(), splsoftclock(), splsoftnet(), splsoftserial(),
splstatclock(), spltty(), splvm(), splx()
単一プロセッサでは、割り込みレベルを調整した方が効率がよいし、
並列性も高くなる。しかし、SMP では、この方法は使えない。
ジャイアント・ロック(giant lock)。splhigh() に頼ったプログラミング。
カーネルの割り込み処理のプログラムは難しい。
割り込みをプロセス間通信に変換してメッセージ・パッシングの世界でものを考
えたい。
割り込み禁止の時間が短くなり、応答性(responsiveness)が上がる。
本当の割り込み禁止や、割り込みレベルによる優先度付け(prioritize)ができなくなる。
次の内容を含む「テキスト」ファイルを作成し、
レポート提出ページ
から提出しなさい。
回答は、講義内容にそったものにしなさい。Wikipedia その他の信頼できない
ソースから得た情報を回答しないこと。
締切りは、2017年10月11日、 23:59:59 とする。
並行プログラムの難しさを、逐次プログラムと比較して述べなさい。
Write difficulties of concurrent programs by comparing with sequential
programs.
並行プログラムは、並列プログラムと分散プログラムに分類される。
並列プログラムと分散プログラムの共通点を述べなさい。
Concurrent programs are classified into two types: parallel programs
and distributed programs.
Write common ideas beteen parallel programs and distributed programs.
並列プログラムと分散プログラムの相違点を述べなさい。
Write differences beteen parallel programs and distributed programs.
相互排除の実現に割り込み禁止を使うことの利点を述べなさい。
Write advantages of using disabling interrupts in implementing
mutual exclusion.
相互排除の実現に割り込み禁止を使うことの限界を述べなさい。
Write limitations of using disabling interrupts in implementing mutual
exclusion.
Last updated: 2017/10/06 08:20:18
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>