並行処理の要約
並行処理は古くからある重要な概念です。昨今はマルチコアCPUが普及し、ますます重要になってきました。しかしながら、並行処理を正しく理解しようとすれば、OS・ハードウェア・コンパイラ・複数のプログラミング言語と多くの知識が必要な上、一般的なプログラマにとってなれない概念が多数あり、敷居が高い事は否めません。そこで、忙しいプログラマの為に、並行処理の要約を書く事を思い立ちました。並行処理の全てを書こうとすれば、数千ページの大著になりますので、この記事ではポイントだけを書きます。
OSに並行処理の概念が生まれたのは1965年～1980年です。それ以前のコンピュータは、一つのジョブが、テープなどの入出力装置の入出力操作の完了を待つために、実行中のジョブが止まると、CPUはその入出力操作が終わるまでアイドル状態でした。商用分野のデータ処理では、全実行時間の内、待ち時間が80％～90％を占めましたので、CPUのアイドル時間を減らす方法が必要となりました。そこで考えだされたのがマルチプログラミングです。
マルチプログラミングの考え方は、メモリを複数のパーティションに分けて、パーティションごとに異なるジョブを入れるというものです。こうする事により、1つのジョブが入出力を待っている間、他のジョブを実行する事が可能となりました。これで、アイドルタイムを削減する事に成功しましたが、応答時間が長いという問題が残りました。例えば、プログラムを一文字打ち間違えただけで、コンパイルが通らずに半日無駄にすることがありました。
応答時間を速くするために、時間ごとにジョブを割り当てる時分割方式が考えだされました。この考えは、マルチプログラミングを進化させました。
マルチプログラミングシステムを備えたコンピュータは、同時に複数の事が出来ます。例えば、音楽を聴きながら原稿を書いたりできます。しかし、単一CPUは1つのプログラムしか実行できません。複数のプログラムが同時に実行されているように見えるのは、OSが短い時間でプログラムを切り替えているからです。OS設計者は長年にわたって、並列性を容易に扱う為に概念的なモデル（逐次プロセス）を発展させてきました。その結果、プロセスモデルが誕生しました。
プロセスモデルは、コンピュータ上で実行する逐次的なプログラムを、プロセスと呼ぶ概念で考えて扱います。プロセス深く考えると難しい概念ですが、仮想的なCPUであり、CPUがプログラムを実行するにあたって必要な情報を集めたものと考えるとよいでしょう。
プロセスは、リソースのグルーピングと実行の独立した2つの概念でなりたっています。プロセスは扱いやすいものの、リソースと実行がセットであるため、色々な不便な面がありました。それで、この2つの概念を分離する方法が模索されました。その結果、実行の概念をスレッドと呼ぶものに任せ、プロセスはリソースのグルーピングをサポートする形態が考えだされました。今日マルチスレッドプログラミングと呼ばれる並行処理プログラミングは、このスレッドを操作する方式のプログラミング方法です。
スレッドが考えだされたおかげで、並行処理が行いやすくなりました。その反面、各スレッドは、所属しているプロセスのリソースを共有する為、難しい問題が生まれました。同じプロセスに所属するスレッドが、共有リソースを操作する場合、意図しない結果を生みます。例えば、複数のスレッドが、グローバル変数の値を変更する場合、値はスレッドの実行順序とタイミングにより変化しますので、予測できないものになります。この状態では、正常にプログラミングが出来ませんので、色々な概念が考えだされました。
色々な概念が生み出されましたが、共通している考え方があります。それは、1つのリソースに対して、複数処理を同時に行わないという考え方です。あるスレッドがリソースを操作する権利を獲得（ロック）すると、他のスレッドはそのリソースの権利が放棄されるまで待ちます。こうすれば、リソースの破壊、値の喪失、・・・といった問題が解決します。しかし、デッドロックや優先順位逆転といった、新しい問題が発生しました。
その新たなる問題から得た教訓は、ロックの期間は極力短くしなければならないという事です。また、リソースが確保できるまで待つという考えは、並列に動作できるスレッドの数を制限する事も意味しました。この状態では、複数のCPUがあっても、パフォーマンスが向上しません。マルチコアCPUが一般化している現在では、これは重要な問題です。
そこで、アトミック命令が考えだされました。アトミック命令というのは、単一不可分な命令の事を指します。例えば、並列処理では++iといった単純な命令でも値が予測不可能となります。この原因は、インクリメントは、読み込み・変更・書き込みの三つの操作から成り立っているからです。これを単一の命令で行う事が出来れば問題は発生しません。また、同様の考え方で、アトミック変数も考えだされました。
その他にも、ロック範囲を狭めるという考えから細粒度ロックが生み出され、そもそもロックをしなければいいという考えからロックフリーアルゴリズムが生み出されました。
今まで述べた概念は優れていますが、並行処理プログラミングは難しいものです。また、マルチコアCPUは一般化し、搭載できるコア数は上昇し続けています。そこで、並行処理を簡単にかつ、コア数の増加にも耐えられるように新しい技術が生み出されています。例えば、インテルTBB、OpenMP、並列パターンライブラリ (PPL)、並行指向プログラミング言語Erlangなどです。それと並行して、並行処理の概念の高度化は進み、データベースの世界から来たと思われるソフトウェアトランザクショナルメモリ（STM）、アクターモデルなどの新しい概念も登場しています。
OSに並行処理の概念が生まれたのは1965年～1980年です。それ以前のコンピュータは、一つのジョブが、テープなどの入出力装置の入出力操作の完了を待つために、実行中のジョブが止まると、CPUはその入出力操作が終わるまでアイドル状態でした。商用分野のデータ処理では、全実行時間の内、待ち時間が80％～90％を占めましたので、CPUのアイドル時間を減らす方法が必要となりました。そこで考えだされたのがマルチプログラミングです。
マルチプログラミングの考え方は、メモリを複数のパーティションに分けて、パーティションごとに異なるジョブを入れるというものです。こうする事により、1つのジョブが入出力を待っている間、他のジョブを実行する事が可能となりました。これで、アイドルタイムを削減する事に成功しましたが、応答時間が長いという問題が残りました。例えば、プログラムを一文字打ち間違えただけで、コンパイルが通らずに半日無駄にすることがありました。
応答時間を速くするために、時間ごとにジョブを割り当てる時分割方式が考えだされました。この考えは、マルチプログラミングを進化させました。
マルチプログラミングシステムを備えたコンピュータは、同時に複数の事が出来ます。例えば、音楽を聴きながら原稿を書いたりできます。しかし、単一CPUは1つのプログラムしか実行できません。複数のプログラムが同時に実行されているように見えるのは、OSが短い時間でプログラムを切り替えているからです。OS設計者は長年にわたって、並列性を容易に扱う為に概念的なモデル（逐次プロセス）を発展させてきました。その結果、プロセスモデルが誕生しました。
プロセスモデルは、コンピュータ上で実行する逐次的なプログラムを、プロセスと呼ぶ概念で考えて扱います。プロセス深く考えると難しい概念ですが、仮想的なCPUであり、CPUがプログラムを実行するにあたって必要な情報を集めたものと考えるとよいでしょう。
プロセスは、リソースのグルーピングと実行の独立した2つの概念でなりたっています。プロセスは扱いやすいものの、リソースと実行がセットであるため、色々な不便な面がありました。それで、この2つの概念を分離する方法が模索されました。その結果、実行の概念をスレッドと呼ぶものに任せ、プロセスはリソースのグルーピングをサポートする形態が考えだされました。今日マルチスレッドプログラミングと呼ばれる並行処理プログラミングは、このスレッドを操作する方式のプログラミング方法です。
スレッドが考えだされたおかげで、並行処理が行いやすくなりました。その反面、各スレッドは、所属しているプロセスのリソースを共有する為、難しい問題が生まれました。同じプロセスに所属するスレッドが、共有リソースを操作する場合、意図しない結果を生みます。例えば、複数のスレッドが、グローバル変数の値を変更する場合、値はスレッドの実行順序とタイミングにより変化しますので、予測できないものになります。この状態では、正常にプログラミングが出来ませんので、色々な概念が考えだされました。
色々な概念が生み出されましたが、共通している考え方があります。それは、1つのリソースに対して、複数処理を同時に行わないという考え方です。あるスレッドがリソースを操作する権利を獲得（ロック）すると、他のスレッドはそのリソースの権利が放棄されるまで待ちます。こうすれば、リソースの破壊、値の喪失、・・・といった問題が解決します。しかし、デッドロックや優先順位逆転といった、新しい問題が発生しました。
その新たなる問題から得た教訓は、ロックの期間は極力短くしなければならないという事です。また、リソースが確保できるまで待つという考えは、並列に動作できるスレッドの数を制限する事も意味しました。この状態では、複数のCPUがあっても、パフォーマンスが向上しません。マルチコアCPUが一般化している現在では、これは重要な問題です。
そこで、アトミック命令が考えだされました。アトミック命令というのは、単一不可分な命令の事を指します。例えば、並列処理では++iといった単純な命令でも値が予測不可能となります。この原因は、インクリメントは、読み込み・変更・書き込みの三つの操作から成り立っているからです。これを単一の命令で行う事が出来れば問題は発生しません。また、同様の考え方で、アトミック変数も考えだされました。
その他にも、ロック範囲を狭めるという考えから細粒度ロックが生み出され、そもそもロックをしなければいいという考えからロックフリーアルゴリズムが生み出されました。
今まで述べた概念は優れていますが、並行処理プログラミングは難しいものです。また、マルチコアCPUは一般化し、搭載できるコア数は上昇し続けています。そこで、並行処理を簡単にかつ、コア数の増加にも耐えられるように新しい技術が生み出されています。例えば、インテルTBB、OpenMP、並列パターンライブラリ (PPL)、並行指向プログラミング言語Erlangなどです。それと並行して、並行処理の概念の高度化は進み、データベースの世界から来たと思われるソフトウェアトランザクショナルメモリ（STM）、アクターモデルなどの新しい概念も登場しています。
スポンサーサイト
