02 マルチスレッドプログラミング

このセクションでは、マルチスレッドプログラミングに入門します。**マルチスレッドプログラミングは並列および並行処理のために使われます**。まずは「並列」「並行」などのキーワードについて解説します。そして実際にコードを書きながら、マルチスレッドプログラミングのスキルを体得していきます。 # 2.1 並列・並行とは? コンピュータシステムでは、同時に複数のタスクを実行することができます。あなたも、Spotifyで音楽を聞きながらWordでレポートを書き、時折ブラウザで調べ物をする…といった経験があるはずです。同時に複数のアプリケーションを動かしていますね。以下のコマンドで、コンピュータで動作しているタスクの一覧を確認できます。いくつ動いていましたか? 私のmacOSでは、606個ものタスクが動作していました。 ```sh $ ps -A # タスク一覧 $ ps -A | wc -l # タスク数 ``` なぜ、1台のコンピュータで600個以上ものタスクを同時に動作させることができるのでしょうか? 人間は、基本的には同時に1つのことしかできません。コンピュータもそうなのではないでしょうか? そもそも、**同時とは何でしょうか**? コンピュータで同時に処理を実行するには、**空間分割**と**時間分割**（Time sharing）の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）。 **コードx: シングルスレッドプログラムの例** ```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 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!`と表示されてプログラムが終了していることがわかります。 ## 2.3.2 マルチスレッドプログラムコード1の速度を改善するために、Heavy関数を3つ同時に実行してみましょう。早速、threadingライブラリを用いてマルチスレッドプログラムを書いていきます。理解は後回しでよいので、まずはコード2を写経してみましょう。 **コード2: スレッドを作り、時間のかかる処理を同時に呼び出す** ```python 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.3 共有メモリへのアクセスと排他制御 (TODO: 計算の分配→集約、あるいは協調で共有変数が必要という話を書く) Fig 4の通り、単一プロセス内において複数のスレッド間でメモリ空間が共有されています。つまり、各スレッドは同じ変数にアクセスし読み書きすることができます。マルチスレッドプログラミングの技法を用いて、$\sum^{1,000,000}_{x=1}x$、つまり1から1,000,000までの総和を計算するプログラムを書いてみましょう。 **コードx: 共有メモリへアクセス** ```python import threading from typing import List total = 0 def sum_range(start: int, stop: int): global total for i in range(start, stop): total += i def main(): threads: List[threading.Thread] = [] for i in range(10): t = threading.Thread(target=sum_range, args=(100_000*i, 100_000*(i+1)+1)) t.start() threads.append(t) for t in threads: t.join() print(f"Sum: {total}") main() ``` **コードxの実行結果** ```sh # 1回目の実行 hiroki@HirokiMBP16 codes % uv run --python 3.13t 02/multithread_without_lock.py Sum: 62940737991 # 2回目の実行 hiroki@HirokiMBP16 codes % uv run --python 3.13t 02/multithread_without_lock.py Sum: 57834651570 ``` プログラムは一見正しいように思えますが、実行するたびに結果が変わってしまいます。そして毎回、正しい答えである500,000,500,000よりも小さな値になるようです。なぜこのようなことが起こるのでしょうか? 並行プログラミングでは、こうした奇妙な挙動がしばしば発生します。そのため多くのプログラマーが苦手意識を持っているようですが、多くの問題は適切に対処することが可能です。実は、**更新がロストしているのです**（トランザクションの分野では[[Lost Update]]と呼ばれる挙動です）。Fig xにコードxで更新のロストが発生するメカニズムを図解しました。コード中の`total += i`という操作は、以下2つの`read/write`操作にわけて実行されることに注意が必要です。 1. `total`の中身をレジスタに読み込む: `reg = read(total)` 2. 読み込んだ値に`i`を加算し、`total`に書き込む: `write(total, reg+i)` ここで、スレッド2と3が同時に値を読み込み、しばらくしてからその値に加算したものを書き戻すシーンを考えます。スレッド2は`i==100_000`だったので100,001を書き込みますが、その直後に`i==1`だったスレッド1が1を書き込みます。そうすると、本来100,002となるべき`total`は、残念ながらスレッド2の書き込みが無かったことにされ、1となってしまいます。このようなメカニズムで、足し算を2回したはずなのに、どちらかの計算がなかったことになってしまうのです。 ![[shared_memory_race.excalidraw.svg]] <center> Fig x: コードxにおける更新ロストのメカニズム </center> 更新のロストを含む**タイミングのズレが引き起こす異常な振る舞いのことを、[[競合状態]]（Race Condition）といいます**。競合状態には他にも、変数の中途半端な状態が見えるなど、様々な種類があります。競合状態に陥ることを防ぐには、どうすればいいのでしょうか? 一つの手法は、[[Lock]]オブジェクトを使うことです。**Lockを用いると、プログラム中に1つのスレッドしか同時に実行できないコードブロックであるクリティカルセクション（[[Critical section]]）を作ることができます**。**1度に1つのスレッドでのみ実行されるという特性を[[Mutex]]（相互排他）といい**、そのような特性を保証する制御を排他制御といいます。 [^3] Lockは、`acquire`メソッド（`lock`とも）でクリティカルセクションへのアクセス権（ロック）を取得します。ある瞬間にロックを取得できるスレッドは1つだけなので、他のスレッドがまだロックを保持している場合呼び出しはブロッキングされます。また、`release`メソッド（`unlock`とも）でロックを開放し、他のスレッドにアクセス権を明け渡します。 Fig xはLock変数`l`を用いて2つのスレッド間で排他制御を行っている様子です。まず、スレッド1がロックを取得します。少し遅れてスレッド2がロックを取得しようとしますが、スレッド1がロックを取得中のため呼び出しがブロッキングされています。その後スレッド1はクリティカルセクションの実行を終えて、ロックを開放します。それと同時に、待ち構えていたスレッド2がロックを取得してクリティカルセクションの実行を開始し、しばらくしてロックを開放しています。 ![[lock.excalidraw.svg]] <center> Fig x: ロックを用いた排他制御 </center> 話をコードxに戻しましょう。結果がおかしかった原因は、複数のスレッドが同時に加算操作をしており更新のロストが発生していたためでした。そこで、Lockオブジェクトを用いて加算操作の周囲をクリティカルセクションにすることで、問題に対処しましょう。早速、先程のコードを、Lockを用いて排他制御を行う安全なコードに書き換えてみましょう。 **コードx: 共有メモリへアクセス（Lock使用バージョン）** ```python import threading from typing import List total = 0 lock = threading.Lock() def sum_range(start: int, stop: int): global total, lock for i in range(start, stop): lock.acquire() # ロックを取得 # ここからクリティカルセクション total += i # ここまでクリティカルセクション lock.release() # ロックを開放 def main(): threads: List[threading.Thread] = [] for i in range(10): t = threading.Thread(target=sum_range, args=(100_000*i, 100_000*(i+1)+1)) t.start() threads.append(t) for t in threads: t.join() print(f"Sum: {total}") main() ``` **コードxの実行結果** ```sh hiroki@HirokiMBP16 codes % uv run --python 3.14t 02/multithread_lock.py Sum: 500005000000 ``` これで正しい結果が得られました! ## 2.3.4 演習: モンテカルロ法による円周率の計算マルチスレッドプログラミングにより親しんでもらうために、演習課題を1つ出します。 > [!abstract] 課題 > スレッドを1+5つ用い、モンテカルロ法による円周率の並列計算を行ってください。試行回数は5,000,000回としてください。モンテカルロ法による円周率の計算では、一辺$2r$の正方形とその中にピッタリ収まる半径$r$の円を考えます。$t$回にわたって正方形の中にランダムに点を打ち込み、それが円の領域内に入った回数$h$をカウントします。ある領域の中に入った点の数はその面積に比例するはずなので、以下の近似式がなりたちます。 $ \frac{h}{t} \approx \frac{\pi r^2}{(2r)^2} = \frac{\pi}{4} $ よって、$4h/t$を求めることで$\pi$の近似値を得ることができます。より$\pi$に近い値を求めるには試行回数を多くする必要がある（今回は5,000,000回）ので、並列処理を行って計算時間を短縮することを狙いましょう [^4] 。オススメのアプローチは、まずシングルスレッドのプログラムを実装して、どこが並列化できそうか考えてみることです（ヒント: `for`, `while`などのループは、特に結果が前回のイテレーションに依存しない場合並列化できることがほとんどです）。 ## 2.3.5 まとめセクション2.3では、まず**プロセスとスレッドの概念を学び**、**複数のスレッドを作成するプログラムの書き方を学びました**。また、プログラマの宿敵である**競合状態**の解決方法として、**Lockによる排他制御を学びました**。最後に以下の課題をこなして、2章を終えましょう。 > [!abstract] 課題 > なぜネットワークプログラミングを行う上でマルチスレッドプログラミングが必要なのでしょうか? 「並行」という言葉に触れながら説明してみましょう。 --- 前ページ: [[01 イントロダクション]] 次ページ: [[03 ネットワークについての基礎知識]] [^1]: （うんちく）プロセスとスレッドという概念は、macOSのカーネルの一部で用いられている[[Mach]]からもたらされました。 [^2]: （発展的内容）多くの言語では、各言語がOSのスレッドの上に構築された非同期ランタイムを提供しています。これを利用して[[グリーンスレッド]]モデルの軽量スレッド（[[Coroutines]]）を利用することができます。RustやPythonでは`async/await`キーワードを利用して、並行プログラミングを行えます。今回の講座では軽量スレッドは用いませんが、実際のプログラムでは幅広く利用されています。 [^3]: （発展的内容）こんなことが実現できる理由は、現代的なCPUが[[CAS]]命令をサポートしていることにあります。また、そのような命令に頼ることなくMutexを実現するアルゴリズムも多数提案されています（[[Peterson's algorithm]]など）。気になる方は勉強してみてください。 [^4]: 実はPythonで実装すると、シングルスレッドより計算時間が伸びてしまいます。Python 3.13tのマルチスレッド性能は非常に悪いことが知られており（[参考](https://gihyo.jp/article/2025/03/monthly-python-2503)）、今後の性能改善に期待です。