並行・並列・分散プログラミング/concurrent,parallel,and distributed programming

並行システム

                               システム情報系情報工学域,
			       システム情報工学研究科コンピュータサイエンス専攻
                               新城 靖
                               <yas@cs.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2013/2013-10-01
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/

■連絡事項

科目番号

  1. 01CH303: 一般コース
  2. 01CJ217: 高度IT専修コース

成績の付け方。次のものを合算する。

欠席した日についても、レポートを提出すること。 印刷物は、配布しない。必要なら自分で印刷しなさい。初回は特別に配布する。

■今日の重要な話

用語の意義 歴史 history 割り込みと並行プログラミング Interrupts and concurrent programming

■並行・並列・分散プログラミング(concurrent, parallel, and distributed programming)

◆逐次プログラミングと並行プログラミング(sequential and concurrent programming)

逐次 sequential
1度に1つの手続きが実行される
並行 concurrent
1度に複数の手続きが実行される
main()
{
	printf("hello, world!\n"); 
}
逐次プログラムでは、1度に1つの手続き(関数)(procedure(function))しか実行 されない。printf() が動くと main() は止まる。

複数の手続きを実行する主体は、「プロセス(process)」や「スレッド (thread)」。

縦軸時間、横軸空間、スレッドが協調している

図? 逐次プログラムと並行プログラムの動作(時間と空間の観点から)

並列処理と分散処理の目的

並列 parallel
1つの問題を(逐次処理より)速く(faster)解きたい
分散 distributed
逐次処理は非常に特殊。 並行プログラミング(並列、分散、その他)の共通の話 単一プロセッサでの並行プログラミングもある。後述。 concurrent programming in a single processor.

◆ソフトウェアの記述

2つの言語が必要
計算言語 computational languages
個々の活動を記述
協調言語 coordination languages
統一されたプログラムに組み立てるための「糊(glue)」
Java など、1つの言語で計算と協調が書けるものもある。

■歴史 history

歴史的に重要な出来事と並行プログラミングを学ぶ意義。

講義の最後には、ここで現れるキーワードを理解できることを目標にする(今 日の段階では理解できないものがあってもよい)。

◆Per Brinch Hansen

Per Brinch Hansen (Editor): "The Origins of Concurrent Programming: From Semaphores to Remote Procedure Calls", Springer (2002). ISBN: 0387954015.

Fundamental Concepts

Programming Language Concepts Java などの近代的なプログラミング言語は、だいたい持っている。 以前は、OS記述時に、アセンブリ言語やC言語で記述。

◆逐次プログラミングの発明 invention of sequential programming

ハードウェアは、本質的には並列。全部の素子が同時に動く。

プログラムカウンタの発明。プログラム内蔵方式。 ノイマン型コンピュータ。

当初のコンピュータに、OSはない。

◆マルチプログラミング multiprogramming

1台のコンピュータのメモリに、同時に複数のプログラムをロードして切り替 えながら動作させる。

ハードウェアは、高い。

高いCPUを有効に活用したい。

バッチ処理の誕生。入出力とCPU処理を「並列」動作させる。

ジョブが3つ、入力、処理、出力、異なるものは重なってもよい。

図? バッチ処理における CPU と入出力装置の並列動作 (parallel processing of CPU and I/O in batch processeing)

プロセスの概念の確立。プロセスとプログラムの分離。 一般のプログラミングは、逐次のまま。

OSだけ並行プログラミング

今でもOSの教科書には、セマフォやデッドロックの話が出ている。

Concurrent Pascal, Solo。

OSの実装では、実際には、「割り込み禁止」という軽量の相互排除命令が多 用された。

◆集中型システム(centralized systems)

OSがある集中型システム。 技術的に確立している。

CPU、メモリ、I/O、OS、アプリケーション

図? 集中型システムのハードウェア (hardware of a centralized system)

◆Unix fork-exit-wait

ユーザレベルの命令の例 fork join model

◆TSS (Time sharing system)

Time sharing system。

1台の中央の大型コンピュータ(mainframe)に、複数の「(文字)端末 (terminal)」を接続。

端末を使っている人からすると専有しているように見える。

TSS で複数のアプリケーションを同時に走らせる。 CPU が貴重な時代。CPU を遊ばせない。

メインフレーム1台、端末n台

図? メインフレームと端末(a mainframe and terminals)

◆Virtual Machine

1台のメインフレームに、同時に複数のOSを走らせるのが始り。 TSS の実装方法の1つでもあった。

最近は、 コンピュータの高速化で、性能が余ってきた。もともとハードウェアn台でやっ ていた仕事を、ハードウェアとしては1台に集約する。並列処理の逆。

図? サーバ3台、OS3種類、アプリケーションそれぞれ2つ

図? 仮想計算機によるサーバの集約(集約前) (before server consolidation by virtual machines)

図? ハードウェア1台、OS3種類、アプリケーションそれぞれ2つ

図? 仮想計算機によるサーバの集約(集約後) (after server consolidation by virtual machines)

1999年VMware Workstation 以降、パソコン用の VM も広く使われる。

◆データベース(database)

プログラムとデータを分離。データを複数のプログラムで共有(share)。 データを中心に考える。 データに integrity を持たせる。 integrity を満たしたデータだけを、きちんと 永続的(persistent)に保存する。

◆トランザクション(transaction)

複数のデータベースへの問い合わせ(検索、更新)を、できるだけ「並行 (concurrent)」に実行する。 効率のため。

最終結果は、1つひとつ逐次的(sequential)にやったものと同じ。 serializability。 integrity を満たす。

◆Local Area Networkとworkstation

Sun。

資源を共有したい。プリンタ。ディスク。

ディスクレス・ワークステーション。

Socket API。 NFS, NIS, RPC 出現。

◆Socket API

もともと Unix 4.2 BSD 用。 socket(), listen(), accept(), connect(), send(), recv(), select()。

複数の通信プロトコル(TCP/IP以外も)を扱える。

◆Remote Procedure Call(RPC)

遠隔手続呼出し。プロセス間通信(interprocess communication)だが、一見、 手続き呼び出し(procedure calls)に見える。

◆X Window

X Window。ウインドウのプログラミングは、本質的に並行(inherently concurrent)。 X Windowの実装は、クライアント・サーバ・モデル(client server model)に基づく。 ただし、後に、モデルを変更した。 サーバからクライアントへのイベント(events)の送信を付けた。 リスナ・パタン(listener pattern)へと発展。

◆並行プログラミング言語

◆Ada

Ada。アメリカ国防省(US DoD, Department of Defence) で仕様を決めた組み込みシステム(embedded systems)用の プログラミング言語。

◆プログラミング言語が提供する概念

並行実行(concurrent execution)。同期(synchronization)。非決定性 (non-determinism)。ガード付きコマンド(guarded commands)。

哲学者の食事問題(dining philosophers problem)。生産者消費者問題 (producer-consumer problem)/有限バッファ問題(bounded buffers)。デッド ロック(deadlock)。

初期の実装は、全部コルーチン(coroutine)。

◆エージェント(agents)

能動的なオブジェクト(active objects)。自律性(autonomous, autonomic)がある。

自律(autonomous, autonomic)の定義が人それぞれ。

人工知能(artificial intelligence)分野の用語でもある。

移動エージェント mobile agent

◆並列コンピュータ(parallel computers)

Flynn の分類 (Flynn's taxonomy)

MIMD の分類

Machシステムでの分類 ( Mach operating system kernel, Mach microkernel )

データフローコンピュータ(data flow computer)。関数型プログラミング (functional programming)。論理型プログラミング(logic programming)。第五 世代コンピュータ(the fifth generation computer)。

逐次に対して、どうやって並列性(parallelism)を抽出するかが主眼。 逐次プログラムでは、マルチプロセッサで走らせても1倍。

特定用途のマルチプロセッサ(special purpose parallel computer)。

スパコン(super computers)。ベクトルコンピュータ(vector computers)。

Occam/Transputer。CSPの実装。

MMU (memory management unit)の活用。分散共有メモリ(distributed shared memory, distributed virtual memory)。

◆共有メモリ型マルチプロセッサ、SMP (Shared memory multiprocessor)

(CPU+Cache)*n+メ
モリ

図? 共有メモリ型マルチプロセッサ(バス共有) (Shared memory multiprocessor (with a shared bus))

◆クロスバースイッチ(crossbar switch)

n*CPU-n*Memory

図? 共有メモリ型マルチプロセッサ(クロスバースイッチ) (shared memory multiprocessor with a crossbar switch)

複数のCPUが別のメモリに同時にアクセスできる。 同じメモリならバスと同様に衝突する。

◆共有メモリ型マルチプロセッサとスレッド(shared memory multiprocessor and threads)

共有メモリ型マルチプロセッサをうまく使いたいが、fork() は、重たい。 軽いプロセス(lightweight processes)、スレッド(threads)の研究。

OSは、ジャイアント・ロック(giant lock)。

◆非均質共有メモリ型マルチプロセッサ(shared memory multiprocessor with non-uniform memory access)

CPU、メモリ、相互結合ネットワーク

図? 非均質共有メモリ型マルチプロセッサ (shared memory multiprocessor with non-uniform memory access)

相互結合ネットワークで、遠隔のメモリを CPU から直接アドレスでアクセス できる。ただし、速度は 100 倍くらい遅い。

◆LANに接続されたコンピュータ群(multiple computers connected to a LAN)

PC*3--hub

図? LANに接続されたPC

遠隔のメモリは、アクセスできない(no remote memory access)。 機種が違う(heterogeneous)こともある。

◆オブジェクト指向プログラミング(object oriented programming)

プログラムをオブジェクト(objects)の集合で書く。 オブジェクトは、人間のように、自律(autonomous, autonomic)している。 オブジェクトの内部のデータは外から触れない。データベースの逆。 オブジェクトの内部をアクセスするには、メッセージ(message)を送るしかない。

オブジェクト指向プログラミングは、本質的には並行プログラミング。 実際問題は単に手続き呼出しの実装が多い。

obj1.method1();

Smalltalk 80

オブジェクト指向データベース(object-oriented databases)の矛盾。

◆Apertos/Aperios/Muse

Sony CSL (Computer Science Laboratory) 横手らによるオブジェクト指向OS。

◆ORB

Object Request Broker。複数の言語を繋ぎたい。 オブジェクト指向が入った RPC 。

◆通信ライブラリ(Communication Library)

◆実時間OS(Realtime operating systems)

Arts, RT-Mach, TRON。

ある時間内にある処理が完了することを保証する(guarantee)。

「速い」とか「現在」という意味はない。

◆TRON

The Realtime Operating system Nucleus。 Tron住宅。 Ubiquitousより前。

◆組み込みシステム(embedded systems)

機器の内部にあり、表面的にはパソコンのようなキーボードやモニタは現れな い。 小さいものに組込むのが流行り。

以前は工場の「制御用(control)」。

家電製品。炊飯器など。

◆物のインターネット

The Internet of Things. Cyber-Physical Systems (CPS).

◆パソコン(Personal Computers)

比較的あたらし。

◆CP/M (Control Program for Microcomputers)

パソコン用の(フロッピ・)ディスクOS((floppy)Disk Operating System)。 一度に1つだけプログラムが動く。 キーボード入出力、フロッピ・ディスクのDMA転送完了には割り込みを使う。

◆Macintosh Multi-finder

「パソコンで」、一度に複数のプログラムを切り替えながら使える。

◆MS-DOS

CP/M に、Unix 的な機能を入れた。
  1. 階層化ディレクトリ(hierarchical directories)。mkdir, chdir
  2. 子プロセスは作れる(child processes)。(自分は止まる。)

◆MS Windows

「パソコンで」、複数のプログラムを同時に動かしても、うまく動くようになっ た。

MS Windows 95 は、内部的には、COM/OLE と呼ばれる ORB の固まりで作られ ている。

パソコンでは、保護の概念が希薄。

◆Internet

TCP/IPの4層モデル。 OSI の7層モデル(seven layer model)より古い。

クライアント・サーバ・モデル(client server model)。

inetd (Internet daemon)。

◆UUCP (Unix-to-Unix Copy)

貧乏人の Internet。poor man's Internet

今の用語だとモデム(modem)によるダイヤルアップ(dial up)接続を用いた peer-to-peer (P2P) 型のファイル転送(file transfer)。 電子メール(email)とネットニュース(netnews, Usenet)の記事を運ぶ。

ニュースシステム(news system)の仕組みは、分散システムの優れた例になっている。

◆ftp

ソフトの配布と論文投稿。 anonymous ftp。archie. 夜中に走らせるのが礼儀。

◆World Wide Web

文字たけでなく、絵が出る。ヘルパーで音も出る。

クライアント・サーバ・モデル(client server model)。 バッチ処理風(batch processing like)。

◆CGI

Common Gateway Interface。

最近では、多くの人が、CGI ではじめて並行プログラミングに出会う。

ロックしないとダメ。デッドロックが起り得る。

◆Java Applet

Webブラウザで、アニメーションを行うために登場。

◆Java Servlet

重たい fork() を避ける。

◆XML Web Service

近代的な RPC。

HTML。XML。HTTP。SOAP。

◆Intel Hyperthreading

プログラム・カウンタ回りだけ増やしたもの。

◆Multi-core

1つのチップに、複数の CPU を載せる。

今の段階では、単に、CPU 2 個あるものを 1 個にまとめたようなもの。 昔の SMP −> UMA の再現。コア数、チップ数が増えるに従い、 不均質になる。

◆P2P

Peer-to-peer 。

クライアント・サーバの意義が大事。 クライアント・サーバが現れる前の状況に戻ってはいけない。

Single Point of Failure を避けるという考え方はよい。

◆クラウド・コンピューティング(cloud computing)

メインフレームによるTSSの再来か。

■割り込み(interrupt)

マルチプロセッサではない、単一CPUのシステムで、効率的に並行プログラム を記述するための仕組み。 CPU と周辺装置の並列処理に使う。 ハードウェアの直接的なサポートがある。

割り込みのプログラミングは、非常に難しい。デバッガが使えない。 printf() もつかえない。

ただし、並行性の記述については、スレッドのデッドロックよりは、場合によっ ては簡単かもしれない。

もともとスレッドのプログラムを割り込みのプログラムに書き換えるのは 難しい。

◆周辺装置(peripheral devices)

入出力装置(デバイス)、デバイス(device) とは、コンピュータの箱の中に内蔵されているハードウェアの部品やケーブル で外で接続する部品。 普通は、CPU とメモリ以外のことを指す。 周辺装置(peripheral device)、 入出力装置(IO device)とも呼ばれる。

◆ハードウェアの構成(hardware components)

メモリ、CPU、デバイスは、バス(bus)(システム・バス(system bus))を通 じて接続されている。

図1 バスにより接続されたCPU、メモリ、デバイス

図? バスにより接続されたCPU、メモリ、デバイス(CPU, memory, and I/O devices connected with a bus)

バス(bus):何本かの配線の束

アドレスバス (address bus)
メモリのアドレスを示すための線
データバス (data bus)
データを送るための線
コントロールバス (control bus)
その他、制御用の線

◆デバイス・コントローラ(device controller)

各デバイスとCPU で実行されるプログラムとデバイスとり橋渡しをする機器。

例:キーボード用のコントローラの働き

データが、電気信号などの形で送られてくる。コントローラの中のレジスタ(register) (小容量のメモリ)に保存され。

◆CPUとデバイスの間のデータの受け渡しの方法

CPU から見える場所

  1. デバイス・コントローラが I/O 空間にあり、ポート番号(port number)と 呼ばれる番地が振られている。CPU が、ポート番号を指定して入出力命令(I/O instruction)を実行すると、I/O 空間にあるレジスタの内容が読み書きできる (I/O 空間を示す信号線が1になる)。
  2. デバイス・コントローラが、普通のメモリと同じ空間にあり、メモリ番地 (memory address)が振られている。CPU が、その番地へ普通のロード命令 (load instruction)やストア命令(store instruction)でアクセスすると、コン トローラのレジスタの内容が読み書きできる。MMIO (Memory mapped I/O).
入出力の時に CPU が働くかどうか
  1. CPU が入出力命令(I/O instruction)、あるいは、ロード命令(load instruction)や/ストア命令(store instruction)を実行する。
  2. DMA (Direct Memory Access)やバスマスタと呼ばれる機器があり、その 機器がCPU が普通に命令を実行している合間をぬって一時的にバスを乗っ取り、 データをメモリにコピーする。

◆ポーリングと割り込み(polling and interrupt)

CPU の速度に比べて、デバイスの速度は遅い。

解決策
ポーリング(polling)
周期的(periodic)にデバイス・コントローラの状態をチェックする。
割り込み(interrupt)
入出力が可能になった/DMA転送が完了した時にデバイスがCPUに知らせる。
割り込みのタイミング
入力デバイス(input device)
コントローラは、入力データが到着すると、制御バスの割り込み要求(IRQ, Interrupt Request)信号線を1にする。 DMAを使っている時には、メモリへのコピーが完了した時に 信号線を1にする。
出力デバイス(output device)
コントローラは、出力用バッファ(output buffer)が空(empty)になると、 割り込み要求信号線を1にする。
CPU は、割り込み要求を受け付けると、現在実行中の処理を中断して、 割り込みサービスルーチン(Interrupt Service Routine) あるいは 割り込みハンドラ(interrupt handler) と呼ばれるプログラムを実行する。 割り込み処理ルーチンでは、実際に入力命令を実行したり、 次のデータを出力を開始する。 最後に、割り込み処理から復帰する命令を実行する。すると、先ほど中断してい た処理が再開される。

◆OSの上半分と下半分(top half and bottom half)

図? ユーザ・モードのユーザ・プロセス、カーネル・モードのユーザ・プロセス、割り込みハンドラ、デバイス、共有データ

図? OSの上半分と下半分

カーネル・モードのユーザ・プロセスと割り込みハンドラが共有データをアクセ スする。

注意: Linux では、top half と bottom half を別の意味で使っている。 http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2012/2013-01-29/index.html 参照。

◆相互排除(mutual exclusion)

相互排除(mutual exclusion): ある資源をアクセスできるスレッドの数を多くても1つにする。

プログラムの字面上、相互排除が必要な部分を 際どい部分(critical section) ( クリティカルセクション ) という。

◆割り込み禁止(disabling interrupts)

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.

◆割り込みハンドラ(割り込み禁止なし==バグ入り) (interrupt hander without disabling interrupts (with a bug))

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 ;
}

◆割り込みレベル(Interrupt level)

PDP-11 には、割り込み禁止のレベルが 7 段階(3ビット)あった。 SPL (Set Priority Level) 命令。

    splhigh(); /* 割り込み禁止 disable interrupt */
    <際どい部分。critical section.>
    spl0(); /* 割り込み許可 enable interrupt */

◆割り込みハンドラ(割り込み禁止有り)(interrupt hander with disabling interrupts (bug fixed))

上のプログラムを書き直す。
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();
}

◆多重割り込み(multiple interrupt)

多重の割り込みを許す。

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() に頼ったプログラミング。

◆割り込みからメッセージへの変換(translating interrupts into messages)

カーネルの割り込み処理のプログラムは難しい。 割り込みをプロセス間通信に変換してメッセージ・パッシングの世界でものを考 えたい。

割り込み禁止の時間が短くなり、応答性(responsiveness)が上がる。

本当の割り込み禁止や、割り込みレベルによる優先度付け(prioritize)ができなくなる。

■課題(assignment)1 並行・並列・分散プログラミング/concurrent,parallel,and distributed programming

次の内容を含む「テキスト」ファイルを作成し、 レポート提出ページ から提出しなさい。

回答は、講義内容にそったものにしなさい。Wikipedia その他の信頼できない ソースから得た情報を回答しないこと。

締切りは、2013年10月6日、 23:59:59 とする。

★問題(101) 並行プログラムの難しさ

並行プログラムの難しさを、逐次プログラムと比較して述べなさい。 Write difficulties of concurrent programs by comparing with sequential programs.

★問題(102) 並列プログラムと分散プログラムの共通点

並行プログラムは、並列プログラムと分散プログラムに分類される。 並列プログラムと分散プログラムの共通点を述べなさい。 Concurrent programs are classified into two types: parallel programs and distributed programs. Write common ideas beteen parallel programs and distributed programs.

★問題(103) 並列プログラムと分散プログラムの相違点

並列プログラムと分散プログラムの相違点を述べなさい。 Write differences beteen parallel programs and distributed programs.

★問題(104) 割り込み禁止の利点

相互排除の実現に割り込み禁止を使うことの利点を述べなさい。 Write advantages of using disabling interrupts in implementing mutual exclusion.

★問題(105) 割り込み禁止の限界

相互排除の実現に割り込み禁止を使うことの限界を述べなさい。 Write limitations of using disabling interrupts in implementing mutual exclusion.
Last updated: 2013/10/07 11:11:48
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>