02 並列・並行プログラミング

このセクションでは、並列・並行プログラミングに入門します。まずは「並列」「並行」のキーワードについて解説します。そして実際にコードを書きながら、並列・並行プログラミングのスキルを体得していきます。 # 2.1 並列・並行とは? **コンピュータでは、同時に複数のタスクを実行することができます**。あなたも、Spotifyで音楽を聞きながらWordでレポートを書き、時折ブラウザで調べ物をする…といった経験があるはずです。同時に複数のアプリケーションを動かしていますね。以下のコマンドで、コンピュータで動作しているタスクの一覧を確認できます。いくつ動いていましたか? 私のmacOSでは、606個ものタスクが動作していました。 ```sh $ ps -A # タスク一覧 $ ps -A | wc -l # タスク数 ``` なぜ、1台のコンピュータで600個以上ものタスクを同時に動作させることができるのでしょうか? 人間は、基本的には同時に1つのことしかできません。そもそも、**同時とは何でしょうか**? コンピュータで同時に処理を実行するには、**空間分割**と**時間分割**の2つのアプローチがあります。**空間分割は本当に同時に実行する方法**であり、**時間分割は同時に実行しているかのように見せかける方法**です。現代のコンピュータシステムは、**空間分割のアプローチを取る並行処理（Parallel Processing）**、**時間分割のアプローチを取る並列処理（Concurrent Processing）** の両者を組み合わせて、効率的にタスクを同時実行します。 ## 2.1.1 並列処理現代のコンピュータは、CPUの中に実行コアが複数個あります。あなたのコンピュータにコアがいくつあるかは、以下のコマンドで確認することができます。 ```sh $ cat /proc/cpuinfo # Linux（WSL含む） $ system_profiler SPHardwareDataType # macOS ``` **複数のコアがあるコンピュータでは、（物理的に）同時に複数のタスクを実行することができます**。これを**並列処理**といいます。複数のタスクをコアごとに割り振るので、空間分割のアプローチと言われます。私のMacbook Proには12個の物理コアがあるので、最大12個のタスクを同時に実行することができます。 Fig 1に、CPUコアが2つあるコンピュータで、2つのタスクを同時に実行している様子を図示しました。この例では、タスク1はコア1、タスク2はコア2で同時に実行されます。 ![[parallel.excalidraw.svg]] <center> Fig 1: 並列処理（空間分割アプローチ）のイメージ </center> 私はコンピュータサイエンス学徒として、空間分割のアプローチを家事にも応用していました。私の住んでいた寮には洗濯機が4つあったので、長い間溜め込んだ大量の洗濯物を4つの洗濯機に分割して放り込み、およそ1/4の時間で洗濯を終えていました。洗濯の空間分割は、並列処理が最高の性能を発揮する理想的なケースです。ほとんどのケースでは、コア数を$N$としたとき$1/N$の実行時間を達成するようなパフォーマンスは引き出せないことに注意が必要です（参考: [[アムダールの法則]]）。 ## 2.1.2 並行処理セクション2.1.1では、複数のコアを使用した並列処理について学びました。しかし、ここで1つの疑問が湧いてきます。私のMacBook Proには12コアしかないのに、なぜ12個以上のアプリを同時に実行できるのでしょうか? どうやって600個以上のタスクを同時に実行していたのでしょうか!? **コンピュータは、原理的に1つのコアで1つのタスクしか実行できません**。黎明期のコンピュータシステムでは、本当にタスクを1つづつ実行していました。会社に1台しかないコンピュータの前に、ユーザーが長蛇の列をなし、前の人の計算が終わったら次の人…という流れです。現代の感覚で言えば、まずブラウザで下調べを完全に終えてから、Wordでレポートを書いて、すべてが終わったら音楽を聞く…といった感じでしょうか。しかし、現代のコンピュータシステムでは、コアの数よりも多くのタスクを同時に実行しています。その秘密は、**コアの数よりも多くのタスクを同時に実行しているように見せかける**ことにあります。実のところ、OSが**短時間でタスクをこまめに切り替えて実行する**ことで、あたかも同時に多くのタスクをこなしているかのように見せかけています。これは**時間分割のアプローチであり、並行処理と呼ばれます**。タスクAを短時間（通常数ミリ秒）実行し、別のタスクBに切り替えまた短時間実行し、またAに戻して…ということを行っています。 Fig 2に、CPUコア1つを使って、2つのタスクを同時に実行している様子を図示しました。この例では、まずタスク1が開始され、コア1で少し実行されたあと、次に開始したタスク2に道をゆずります。タスク2はしばらくコア1で実行されたあと、またタスク1にゆずります。こうした裏技的テクニック―各アプリをちょっとずつ高速に切り替えて実行する―を用いることで、ユーザーにあたかもすべて同時に実行しているかのように見せかけることに成功しています。 ![[concurrent.excalidraw.svg]] <center> Fig 2: 並行処理（時間分割）のイメージ </center> これは、単に複数のタスクを並行して実行できる以上の意味を持ちます。**I/O待ちの間に別のタスクを実行することで、CPUをフル活用できる**のです。I/O待ちとは、ネットワークのパケットが届くのを待っていたり、ハードディスクからファイルを読み出すのを待っている間のことを指します。その間、各タスクは処理を進めることができないので、その間に他のタスクをやってしまうことで、トータル実行時間を減らすことができます。並行処理は、家事のワークフローによく似ています。例えば洗濯機を回している間じっと待ち、終わって干し終えてから料理を作っていては、お腹をすかせてしまいます。しかし並行処理のテクニックを使えば、まず洗濯機のスタートボタンを押して、終了するまでの間に料理の下ごしらえをすることができます。人間は1人しかいなくても、時間分割のテクニックによって効率よく家事を進めることができるのです。 ## 2.1.3 OSにおけるタスクのスケジューリング現代の各OSでは、**時間分割および空間分割の両方のアプローチを用いて効率よくタスクを実行しています**。Fig 3に、現代のOSにおけるマルチタスキングの様子を示しました。OSは、タスクの実行を開始すると適切なコアに割り当て並列実行します。そしてコアがいっぱいになると、各コアで実行するタスクをこまめに切り替えて、並行実行をするのです（具体的にどのようにスケジューリングするのかについては様々なアルゴリズムが提案されており、OSの教科書等に詳しい説明があると思います）。 ![[process-exec.excalidraw.svg]] <center> Fig 3: 現代のOSにおけるマルチタスキングの様子 </center> ## 2.1.4 まとめセクション2.1では、複数のプログラムを同時に実行するための**並列処理および並行処理の概念を学びました**。また、現代のOSは両者を組み合わせて効率よくアプリケーションを実行するということを確認しました。次のセクションでは、タスクというキーワードをもう少し詳細に見ていきます。そして、セクション2の後半ではOSが提供するマルチタスク関連のAPIに触れ、実際に並列・並行プログラミングにチャレンジします! > [!abstract] 課題 > 並行と並列について、その違いに触れながら説明してください # 2.2 プロセスとスレッドセクション2.1では、並列処理と並行処理の概念について学びました。ここからは、各OSがどのようにタスクを実行し、並列・並行処理をサポートしているかを見ていきます。まず、プロセスとスレッドという2つの用語について確認しましょう。各OSでは、タスクが**プロセス**という単位で実行されます。プロセスには、OSによってプログラムが使用できる仮想メモリ空間が割り当てられます。そして各プロセスには、1つ以上の**スレッド**が存在します。スレッドごとプログラムカウンタやレジスタが提供され、**スレッドの中でプログラムは逐次的に実行されます**。（ここ浮いてるので直す→）**OSはスレッドごとスケジューリングを行い実行します**。[^1] [^2] ![[process.excalidraw.svg]] <center> Fig 4: プロセスとスレッド </center> **通常のプログラムでは、スレッドは1つです**。プログラムを実行すると、1つのプロセスが作成され、必要なメモリ領域が確保されます。そして1つのスレッドが作成され、その中でプログラムが順番に実行されます。例えば以下のPythonプログラムは、プログラムをただ上から下に実行するだけです（Fig 5）。 ```python def main(): s = "2025" + "09" print(f"{s} Delight合宿") main() ``` ![[single_thread.excalidraw.svg]] <center> Fig 5: シングルスレッドプログラムの実行イメージ </center> # 2.3 マルチスレッドプログラミングセクション2.2の終わりに、一般的なシングルスレッドプログラムの例を確認しました。では、どうすればプロセスの中に複数のスレッドを作成できるのでしょうか? 本セクションでは、1つのプロセスに複数のスレッドを作成し、並列・並行処理を行う**マルチスレッドプログラミングの書き方を学びます**。スレッドを複数作成するには、OSの提供するAPIを活用する必要があります。UNIX環境の場合、[[pthread]]というC言語APIが提供されています。Pythonの場合は、[threading](https://docs.python.org/ja/3.13/library/threading.html) ライブラリが提供されており、本ゼミではこちらを使用してマルチスレッド処理を実装します。 ## 2.3.1 まず書いてみようマルチスレッドプログラミングを行う前に、まずは処理に時間のかかる関数を作って、何回か呼び出してみましよう。 **コード1: 逐次処理** ```python:heavy.py import time def heavy(i: int): time.sleep(3) # 3秒寝る（ダミーの負荷） print(f"Done! ({i})") def main(): heavy(1) heavy(2) heavy(3) print("Finish!") main() ``` **コード1の実行結果** ```sh hiroki@HirokiMBP16 codes % uv run --python 3.13t 02/heavy.py Done! (1) # 開始から3秒後表示される Done! (2) # 開始から6秒後表示される Done! (3) # 開始から9秒後表示される Finish! ``` `heavy`は重たい処理を再現した関数です。実際のアプリケーションではネットワーク待ちであったり高負荷な計算であったりすることが一般的ですが、今回はダミーを作るだけなので、指定秒数分処理を止める関数である`time.sleep`を呼び出して3秒間経過させています。実行結果を観察すると、3秒経過するごとに`Done`と表示されていき、開始から9秒ほど経過した時点で`Finish!`と表示されてプログラムが終了していることがわかります。コード1の速度を改善するために、Heavy関数を3つ同時に実行してみましょう。早速、threadingライブラリを用いてマルチスレッドプログラムを書いていきます。理解は後回しでよいので、まずはコード2を写経してみましょう。 **コード2: スレッドを作り、重たい処理を同時に呼び出す** ```python:02/multithread.py import threading import time def heavy(i: int): time.sleep(3) print(f"Done! (child thread {i})") def main(): t1 = threading.Thread(target=heavy, args=(1,)) t2 = threading.Thread(target=heavy, args=(2,)) t3 = threading.Thread(target=heavy, args=(3,)) t1.start() t2.start() t3.start() print("Hello, from main thread") t1.join() t2.join() t3.join() print("Finish!") main() ``` **コード2の実行結果** ```sh:実行結果 hiroki@HirokiMBP16 codes % uv run --python 3.13t 02/multithread.py Hello, from main thread # 3秒後… Done! (child thread 1) Done! (child thread 2) Done! (child thread 3) Finish! ``` 実行すると、プログラムの実行開始から3秒ほどでプログラムが終了することがわかります。これで処理時間が1/3となりました。おめでとうございます! このプログラムは、以下の処理から構成されます。 1. まずスレッドを3つ作成する（これらを子スレッドと呼ぶことにします） 2. 子スレッドで同時に`heavy`関数を実行する 3. 子スレッドの終了を待機し、プログラムを終了するまず`main`関数の冒頭で`threading.Thread`クラスのインスタンスを3つ作成しています（`t1, t2, t3`）。引数`target`には、スレッドで実行したい関数を指定します。また`args`には、`target`関数に渡したい引数を指定します。 `threading.Thread`のインスタンスを作成しただけでは、まだスレッドは作成されません。`start`メソッドを呼び出して、実際にスレッドを作成する必要があります。スレッドを開始すると、メインスレッドを含めた各スレッドは各々の処理を進めます。メインスレッドは、`join`メソッドで各スレッドの終了を待つことができます。逆に、`join`を呼び出すまでは他スレッドを気にかけることなく、他の処理を進めることができます（他スレッドが`sleep`している間に、`print("Hello, from main thread")`が実行されていることに注目）。上記のプログラムは、Fig 6のように実行されます。 ![[multi_thread.excalidraw.svg]] <center> Fig 6: コード2の動作の流れ </center> ### 2.3.2 例: モンテカルロ法による円周率の計算 **コードn: モンテカルロ法による円周率の計算（シングルスレッド）** ```python:pi_single.py import time import random import math def point() -> bool: x = random.random() y = random.random() return math.sqrt(x**2 + y**2) < 1.0 def pi(times: int) -> float: hit = 0 for i in range(times): if point(): hit += 1 return 4 * (hit/times) def main(): times = 10_000_000 start = time.time() result = pi(times) end = time.time() print(f"pi ≒ {result} ({end-start:.2f}s)") main() ``` **コードnの実行結果** ```sh hiroki@HirokiMBP16 codes % uv run --python 3.13t 02/pi_single.py pi ≒ 3.1409244 (2.28s) ``` **コードn: モンテカルロ法による円周率の計算（マルチスレッド）** ``` ``` ### 2.3.3 共有メモリへのアクセス Fig 4の通り、単一プロセス内において複数のスレッド間でメモリ空間が共有されています。つまり、各スレッドは同じ変数にアクセスし読み書きすることができます。 - Lockの話 - x += 1ではなく, y = x, x = y+1に分解して、こわれるやつをやってみたい **コード3: 共有変数を介したメッセージング** ```python import threading import time from typing import List class Mailbox: mailbox: List[str] lock: threading.Lock def __init__(self): self.mailbox = [] self.lock = threading.Lock() def send(self, message: str): self.lock.acquire() self.mailbox.append(message) self.lock.release() def read(self) -> str | None: result: str | None = None self.lock.acquire() try: result = self.mailbox.pop() except IndexError: pass self.lock.release() return result mailbox = Mailbox() def sender(): for i in range(5): time.sleep(2) mailbox.send(f"Hello, from sender ({i})") def main(): t = threading.Thread(target=sender) t.start() i = 0 while i < 5: message = mailbox.read() if message is None: time.sleep(1) continue print(f"Received: \"{message}\"") i += 1 t.join() main() ``` **コード3の実行結果** ```shell hiroki@HirokiMBP16 codes % uv run --python 3.13t 02/multithread.py Received: "Hello, from sender (0)" Received: "Hello, from sender (1)" Received: "Hello, from sender (2)" Received: "Hello, from sender (3)" Received: "Hello, from sender (4)" ``` コード3では、Mailboxクラスを作成しました。 - どこかでGILの話をして、実は並行でしかない、ということを書かねば - Mailboxを通じたチャットアプリ、作ってみるといいかも前ページ: [[01 イントロダクション]] 次ページ: [[03 ネットワークについての基礎知識]] [^1]: （うんちく）プロセスとスレッドという概念は、macOSのカーネルの一部で用いられている[[Mach]]からもたらされました。 [^2]: （発展的内容）多くの言語では、各言語がOSのスレッドの上に構築された非同期ランタイムを提供しています。これを利用して[[グリーンスレッド]]モデルの軽量スレッド（[[Coroutines]]）を利用することができます。RustやPythonでは`async/await`キーワードを利用して、並行プログラミングを行えます。今回の講座では軽量スレッドは用いませんが、実際のプログラムでは幅広く利用されています。