並行・並列・分散プログラミングとは

並行システム

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

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

■成績の付け方

次の3つを合算する。

■今日の重要な話

用語の意義 歴史 割込みと並行プログラミング

■並行・並列・分散プログラミング

◆逐次プログラミングと並行プログラミング

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

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

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

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

並列アプリケーションと分散アプリケーションの目的

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

◆ソフトウェアの記述

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

■歴史

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

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

◆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言語で記述。

◆逐次プログラミングの発明

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

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

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

◆マルチプログラミング

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

ハードウェアは、高い。

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

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

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

図? バッチ処理における CPU と入出力装置の並列動作

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

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

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

Concurrent Pascal, Solo。

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

◆集中型システム

OSがある集中型システム。

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

図? 集中型システムのハードウェア

◆Unix fork-exit-wait

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

◆TSS

Time sharing system。

1台の中央のコンピュータ(メインフレーム)に、複数の「(文字)端末」を接続。

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

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

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

図? メインフレームと端末

◆Virtual Machine

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

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

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

図? 仮想計算機によるサーバの集約(集約前)

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

図? 仮想計算機によるサーバの集約(集約後)

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

◆データベース

プログラムとデータを分離。 データを中心に考える。 データに integrity を持たせる。 integrity を満たしたデータだけを、きちんと 永続的に保存する。

◆トランザクション

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

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

◆Local Area Networkとworkstation

Sun。

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

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

NFS, NIS, RPC 出現。

◆X Window

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

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

◆Ada

Ada。アメリカ国防省で仕様を決めた組込み機器用のプログラミング言語。

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

並行実行。同期。非決定性。ガード付きコマンド。

哲学者の食事問題。生産者消費者問題/有限バッファ問題。デッドロック。

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

◆エージェント

能動的なオブジェクト。自律性がある。

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

人工知能分野の用語でもある。

移動エージェント mobile agent

◆並列コンピュータ

Flynn の分類

MIMD の分類

Machシステムでの分類

データフローコンピュータ。関数型言語。論理型言語。 第五世代コンピュータ。

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

特定用途のマルチプロセッサ。

スパコン。ベクトルコンピュータ。

Occam/Transputer。CSPの実装。

MMUの活用。分散共有メモリ。

◆共有メモリ型マルチプロセッサ、SMP

(CPU+Cache)*n+メモリ

図? 共有メモリ型マルチプロセッサ(バス共有)

◆クロスバースイッチ

n*CPU-n*Memory

図? 共有メモリ型マルチプロセッサ(クロスバースイッチ)

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

◆共有メモリ型マルチプロセッサとスレッド

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

OSは、ジャイアント・ロック。

◆非均質共有メモリ型マルチプロセッサ

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

図? 非均質共有メモリ型マルチプロセッサ

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

◆LANに接続されたコンピュータ群

PC*3--hub

図? LANに接続されたPC

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

◆オブジェクト指向

メッセージ・パッシングは、本質的には並行プログラミング。 実際問題は単に手続き呼出し。

obj1.method1();

Smalltalk 80

◆Apertos/Aperios/Muse

Sony CSL 横手らによるオブジェクト指向OS。

◆ORB

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

◆通信ライブラリ

◆実時間OS

Arts, RT-Mach, TRON。

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

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

◆TRON

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

◆組込みシステム

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

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

家電製品。東芝 RD-X4EX, RD-Z1 のバグ。 RD-X2 のジャイアントロック。

◆パソコン

比較的あたらし。

◆CP/M

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

◆Macintosh Multi-finder

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

◆MS-DOS

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

◆MS Windows

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

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

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

◆Internet

TCP/IPの4層モデル。OSIの7層モデルより古い。

Socket API。もともと Unix 4.2 BSD 用。 socket(), accept(), connect(), select()。

クライアント・サーバ・モデル。

inetd。

◆UUCP

貧乏人の Internet。

今の用語だとモデムによるファイル転送によるP2P。 電子メールとネットニュースの記事を運ぶ。

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

◆ftp

夜中に走らせる。ソフトの配布と論文投稿。

◆World Wide Web

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

クライアント・サーバ・モデル。 バッチ処理。

◆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 を避けるという考え方はよい。

◆クラウド・コンピューティング

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

■割込み

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

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

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

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

◆周辺装置

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

◆ハードウェアの構成

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

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

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

バス:何本かの配線の束

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

◆デバイス・コントローラ

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

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

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

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

CPU から見える場所

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

◆ポーリングと割込み

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

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

◆OSの上半分と下半分

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

図? OSの上半分と下半分

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

◆相互排除

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

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

◆割り込み禁止

CPUには、割込みを禁止する命令がある。

割込みを禁止は、相互排除に使える。 割り込み禁止の状態で、自分が動いていれば、他のモジュールが動くことはあり得ない。

CPUの命令で1命令から数命令で実装可能である。

◆割込みハンドラ(割り込み禁止なし)

int shared_resource ;

user_process()
{
    int x;
    x = shared_resource ;
    x = x + 1 ;
    shared_resource = x ;
}

interrupt_hander()
{
    int x;
    x = shared_resource ;
    x = x + 1 ;
    shared_resource = x ;
}

◆割り込みレベル

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

    splhigh(); /* 割り込み禁止 */
    <際どい部分。この間は、相互排除される>
    spl0(); /* 割り込み許可 */

◆割込みハンドラ(割り込み禁止有り)

上のプログラムを書き直す。
int shared_resource ;

user_process()
{
    int x;
    splhigh();
    x = shared_resource ;
    x = x + 1 ;
    shared_resource = x ;
    sp0();
}

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

◆割込みからメッセージへ

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

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

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

■練習問題1 並行・並列・分散プログラミングとは

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

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

★問題(103) きわどい部分

上の「割込みハンドラ(割り込み禁止有り)」のプログラ ムについて以下の問題に答えなさい。