図? 逐次プログラムと並行プログラムの動作(時間と空間の観点から)
並行システム
システム情報系/情報工学域,
システム情報工学研究群/情報理工学位プログラム
システム情報工学研究科/コンピュータサイエンス専攻
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2023/2023-04-14
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/
main()
{
printf("hello, world!\n");
}
逐次プログラムでは、1度に1つの手続き(関数)(procedure(function))しか実行
されない。printf() が動くと main() は止まる。
複数の手続きを実行する主体は、「プロセス(process)」や「スレッド (thread)」。
図? 逐次プログラムと並行プログラムの動作(時間と空間の観点から)
「分散 distributed (A)」は、逐次処理より遅くなっても良い。 次のようなことを実現したい。
講義の最後には、ここで現れるキーワードを理解できることを目標にする（今 日の段階では理解できないものがあってもよい）。
プログラムカウンタの発明。プログラム内蔵方式。 ノイマン型コンピュータ。
逐次処理は非常に特殊
ハードウェアは、高い。
高いＣＰＵを有効に活用したい。
バッチ処理の誕生。入出力とＣＰＵ処理を「並列」動作させる。
図? 3つのジョブの逐次処理 (Executing three jobs sequentially) 図? バッチ処理における CPU と入出力装置の並列動作 (parallel processing of CPU and I/O in batch processeing)
プロセスの概念の確立。プロセスとプログラムの分離。 一般のプログラミングは、逐次のまま。
ＯＳだけ並行プログラミング
Concurrent Pascal, Solo。
ＯＳの実装では、実際には、「割り込み禁止」という軽量の相互排除命令が多 用された。
図? 単一プロセッサ (a single processor system)
１台の中央の大型コンピュータ(mainframe)に、複数の「（文字）端末 (terminal)」を接続。
端末を使っている人からすると専有しているように見える。
TSS で複数のアプリケーションを同時に走らせる。 CPU が貴重な時代。CPU を遊ばせない。
図? メインフレームと端末(a mainframe and terminals)
最近は、
コンピュータの高速化で、性能が余ってきた。もともとハードウェアｎ台でやっ
ていた仕事を、ハードウェアとしては１台に集約する。並列処理の逆。
図? 仮想計算機によるサーバの集約(集約前) (before server consolidation by virtual machines) 図? 仮想計算機によるサーバの集約(集約後) (after server consolidation by virtual machines)
1999年VMware Workstation 以降、パソコン用の VM も広く使われる。
最終結果は、１つひとつ逐次的(sequential)にやったものと同じ。 serializability。 integrity を満たす。
資源を共有したい。プリンタ。ディスク。
ディスクレス・ワークステーション。
Socket API、X Window、 NFS, NIS, RPC 出現。
複数の通信プロトコル(TCP/IP以外も)を扱える。
RPC は、NFS (Network File System) の実装で使われている。 coins Linux azalea PC や violet サーバ、 全学計算機 icho01, icho02, kiri で、 どのコンピュータを使っても、自分のホームディレクトが見えるのは、NFS を 使っている。
NFS のために UID (user id) とパスワードを共有するために使われたのが NIS (Network Information System)。
哲学者の食事問題(dining philosophers problem)。生産者消費者問題 (producer-consumer problem)／有限バッファ問題(bounded buffers)。デッド ロック(deadlock)。
初期の実装は、全部コルーチン(coroutine)。
プログラムをオブジェクト(objects)の集合で書く。 オブジェクトは、人間のように、自律(autonomous, autonomic)している。 オブジェクトの内部のデータは外から触れない。データベースの逆。 オブジェクトの内部をアクセスするには、メッセージ(message)を送るしかない。
オブジェクト指向プログラミングは、本質的には並行プログラミング。 実際問題は単に手続き呼出しの実装が多い。
obj1.method1();
Smalltalk 80
オブジェクト指向データベース(object-oriented databases)の矛盾。
MS Windows 95 は、内部的には、COM/OLE と呼ばれる ORB の固まりで作られ ている。
パソコンでは、保護の概念が希薄。
図? マルチプロセッサ (a mult-processor)
今の段階では、単に、CPU 2 個あるものを 1 個にまとめたようなもの。 昔の SMP −＞ UMA の再現。コア数、チップ数が増えるに従い、 不均質になる。
クライアント・サーバ・モデル(client server model)。
inetd (Internet daemon)。
今の用語だとモデム(modem)によるダイヤルアップ(dial up)接続を用いた peer-to-peer (P2P) 型のファイル転送(file transfer)。 電子メール(email)とネットニュース(netnews, Usenet)の記事を運ぶ。
ニュースシステム(news system)の仕組みは、分散システムの優れた例になっている。
クライアント・サーバ・モデル(client server model)。 バッチ処理風(batch processing like)。
最近では、多くの人が、CGI ではじめて並行プログラミングに出会う。
ロックしないとダメ。デッドロックが起り得る。
HTML。XML。HTTP。SOAP。
クライアント・サーバの意義が大事。 クライアント・サーバが現れる前の状況に戻ってはいけない。
Single Point of Failure を避けるという考え方はよい。
ネットワークで接続された複数のコンピュータ(multiple computers that are connected with a network)から構成される分散システム(distributed systems)と対比する時には、集中型システム(centralized systems))と呼ばれ る。
技術的に確立している。
図? 単一プロセッサ (a single processor system)
Flynn の分類 (Flynn's taxonomy)
MIMD の分類
Machシステムでの分類 ( Mach operating system kernel, Mach microkernel )
図? 共有メモリ型マルチプロセッサ(バス共有) (Shared memory multiprocessor (with a shared bus))
図? 共有メモリ型マルチプロセッサ(クロスバースイッチ) (shared memory multiprocessor with a crossbar switch)
複数のCPUが別のメモリに同時にアクセスできる。 同じメモリならバスと同様に衝突する。
図? 非均質共有メモリ型マルチプロセッサ (shared memory multiprocessor with non-uniform memory access)
相互結合ネットワークで、遠隔のメモリを CPU から直接アドレスでアクセス できる。ただし、速度は 100 倍くらい遅い。
図? LANに接続されたPC
NORMAの一種。 機種が違う(heterogeneous)こともある。
図? 2次元トーラス
格子状だが、端が反対側とつながっている。 世の中、3次元なので、2次元トーラスの配線は簡単。3次元以上のトーラスも可能だが、配線が大変になる。
図? ハイパーキューブ(1次元-4次元)
2次元トーラスよりも、ノード間のホップ数が少ない。配線が大変になる。
割り込みのプログラミングは、非常に難しい。デバッガが使えない。 printf() もつかえない。
ただし、並行性の記述については、スレッドのデッドロックよりは、場合によっ ては簡単かもしれない。
もともとスレッドのプログラムを割り込みのプログラムに書き換えるのは 難しい。
図? バスにより接続されたＣＰＵ、メモリ、デバイス(CPU, memory, and I/O devices connected with a bus)
バス(bus)：何本かの配線の束
例：キーボード用のコントローラの働き
データが、電気信号などの形で送られてくる。コントローラの中のレジスタ(register) （小容量のメモリ）に保存され。
CPU から見える場所
CPU の速度に比べて、デバイスの速度は遅い。
図? OSの上半分と下半分
カーネル・モードのユーザ・プロセスと割り込みハンドラが共有データをアクセ スする。注意: Linux では、top half と bottom half を別の意味で使っている。 情報科学類「オペレーティングシステムII」の資料 参照。
相互排除(mutual exclusion)： ある資源をアクセスできる主体(スレッド)の数を多くても１つにする。
プログラムの字面上、相互排除が必要な部分を 際どい部分(critical section) ( クリティカルセクション ) という。
例: x86
di # disable interrupts
....
ei # enable 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 ;
}
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, ChatGPT, その他の信頼できないソースから得た内容をコピーして回答しないこと。
Answers are included in this page. You should not copy the contents from untested sources, including Wikipedia and ChatGPT.
Compare the following two items and write an important common thing and an important diffidence between these two items.
In this class, we classify distributed processing into Type (A) and Type (B). We often use distributed processing of Type (A) that is slower than sequential processing. In this case, answer an important advantage of using the distributed processing over using the sequential processing.
In the 4 x 3 tours, how many neighbor nodes does each node have? What is the max hop count?
In the interrupt hander with disabling interrupts, mark the critical section of the program.