#1 並列処理、並行処理を右脳で理解しよう

ヘ音記号の覚え方

音楽の時間です。皆さん、小学生の頃にヘ音記号を習いましたでしょうか？
習っている方に質問ですが、以下の画像の音符は読めますでしょうか？

筆者が子供の頃、ヘ音記号は下から見て、ラード、味噌（ラ、ド、ミ、ソ）と覚えるよう指導されたことがあり。そのことを今でも覚えています。

上記の理由から、私は右脳（イメージ力）を活用することで物事を長期的に覚えやすくなると考えています。その信念のもと、プログラミングという世界をイメージ力を駆使して、物事の全体像を把握し、やんわりと覚えていくことを目指して執筆していきます。

それでは私と一緒に学んでいきましょう！

並列性と並行性の違い

並行性

並行（Parallel）とは、複数のタスクやプロセスが同時に実行されることを指します。複数のタスクが同じ時間枠で進行し、各タスクが一定の時間スライスを割り当てられて交互に処理されることがあります。このようなタスクの実行は、実際には同時に起こっているように見えることがありますが、実際にはシステムがタスクを切り替えているだけです。

下記の画像で説明すると、D電車からB電車、B電車からA電車、A電車からC電車にかけて、同じ時間枠の中で同時に運行している場合があるとします。その際に、画像ないの時間枠の中から見て、枠組みの内が並行実行中であるといえます。また、それ以外の時間枠は、待機状態中であるといえます。

並行性を理解するにおいて、どの視点で考えるかということが大事であると考えており、電車の運行に例えると、全国の電車の動きは一見並行性を持っているように見えますが、より詳細に見ると以下のような視点があります。

並行性の視点

全国の電車の動きは、多くの都市や駅で同時に発生しています。これらの電車は独立して動いており、異なる路線や時間帯によって、同時に複数の電車が動いていることがあります。このように、複数のタスクが同時に進行している構造が並行性の特徴であるといえます。

同期の視点

全国の電車の運行は、始発から終電までの間に、電車は特定の時刻に出発・到着するように計画されています。これにより、電車の運行が適切に同期され、混乱なく運行されるようになっています。

上記のように、電車の運行は、並行性の観点と同期の観点から考えることで、並行性における重要な概念を理解することができると考えています。

並列性

並列（Concurrent）とは、複数のタスクやプロセスが同じ時間に開始し、同時に進行しているように見えることを指します。これは、複数のタスクが同時に独立して処理されることを意味します。複数のコアやプロセッサを持つマルチコアプロセッサや、複数のマシンを持つクラスターなどが、並列処理を実現するために使用される場合があります。
簡単に言うと、並行は同じ時間枠で複数のタスクを切り替えながら進行し、並列は複数のタスクが同じ時間に実際に同時に進行している状態を指します。

並行性に伴う問題

さて、ここまでで並列性と並行性についての違いが、おおよそ理解できたでしょうか？
今回の話の主題は並行性であるため、そちらのトピックに焦点を合わせてお話しします。並行性を取り入れる際には、いくつか考慮すべき問題があります。
その中でも特に興味深い問題として、食事する哲学者問題があります。

食事する哲学者問題

食事する哲学者問題は、コンピュータ科学の並行処理分野でよく知られる問題の一つです。

哲学者は5人(下記画像では４人)が円卓に座っており、各哲学者の前にはお皿が置かれています。
哲学者たちは食事と思索を交互に行います。食事のためには2本のお箸が必要です。

制約

各哲学者は自分の左右にある2つのお箸を使って食事をします。
お箸は1本しかないため、お箸を共有する必要があります。

問題点

このシナリオでは、哲学者たちが同時に自分の左右にあるお箸を持とうとすると、競合してしまい、全哲学者が食事をすることができなくなる可能性があります。
この競合状態のことを「デッドロック」の一例として扱う事ができます。
この競合状態を避けながら、哲学者たちが食事をする方法を見つける必要があります。
円卓内で下記のような話し合いが行われているわけですね!

下記はSwiftで実装した食事する哲学者問題です。
このコードでは、5人の哲学者が食事を試みます。各哲学者は思考、フォークの取得、食事、フォークの解放というステップを繰り返します。
DispatchSemaphoreを使用してフォークを管理し、wait()とsignal()を呼び出すことで、哲学者が同時に同じフォークを取得しないように制御しています。

    func diningPhilosophers() {
	// 哲学者の数
        let numberOfPhilosophers = 5
	// フォーク
        let forks = [DispatchSemaphore](repeating: DispatchSemaphore(value: 1), count: numberOfPhilosophers)
	// 哲学者（スレッド）を表すオブジェクトの配列
        let philosophers = (0..<numberOfPhilosophers).map { philosopherNumber in
            return Thread {
                while true {
                    // 左右のフォークを取得
                    let leftFork = forks[philosopherNumber]
                    let rightFork = forks[(philosopherNumber + 1) % numberOfPhilosophers]
                    print("哲学者\(philosopherNumber)は思考中である。")
                    // ランダムな時間思考を続ける
                    usleep(UInt32.random(in: 1_000_000...2_000_000))
                    // 左右のフォークを取得するまで待機
                    leftFork.wait()
                    rightFork.wait()
                    print("哲学者\(philosopherNumber)は食事中である。")
                    // ランダムな時間食事を続ける
                    usleep(UInt32.random(in: 1_000_000...2_000_000))
                    // フォークを解放
                    leftFork.signal()
                    rightFork.signal()
                }
            }
        }
        philosophers.forEach { $0.start() }
        RunLoop.main.run()
    }
    

解決策

哲学者の問題を解決するためには、上記でも説明した、「デッドロック」を回避しながら哲学者が食事をする方法を実装する必要があります。

以下コードは、一般的な解決策の1つである「リソースの予約」で解決しています。
リソースの予約による解決策では、下記のルールを適用します。

1. 哲学者は食事の前にフォークの予約を試みます。ただし、予約に失敗した場合は、一度待つことにします。
2. フォークを取得する前に、左右の隣接する哲学者がフォークを取得できるかどうかを確認します。
3. 予約に成功した哲学者のみがフォークを取得し、食事を開始できます。
4. 食事が終了したら、フォークを解放し、予約を解除します。

各哲学者がフォークの予約を試み、予約に成功した場合にフォークを取得しす。予約に失敗した場合に
は待機し、他の哲学者がフォークを使うのを待ちます。食事が終了したら、フォークを解放して予約を解除します。
この方法を取り入れることで、デッドロックを回避しつつ、哲学者が安全に食事することができます。

    func diningPhilosophers() {
        // 哲学者の数
        let numberOfPhilosophers = 5
        // フォーク
        var forks = [DispatchSemaphore](repeating: DispatchSemaphore(value: 1), count: numberOfPhilosophers)
        // フォークの予約状況
        var reservations = [Bool](repeating: false, count: numberOfPhilosophers)
        // 哲学者（スレッド）を表すオブジェクトの配列
        let philosophers = (0..<numberOfPhilosophers).map { philosopherNumber in
            return Thread {
                while true {
                    print("哲学者\(philosopherNumber)は思考中である。")
                    usleep(UInt32.random(in: 1_000_000...2_000_000))
                    let leftForkIndex = philosopherNumber
                    let rightForkIndex = (philosopherNumber + 1) % numberOfPhilosophers
                    // フォークの予約を試みる
                    while reservations[leftForkIndex] || reservations[rightForkIndex] {
                        // 予約が取れるまで待つ
                        usleep(100)
                    }
                    // フォークの予約に成功したら、フォークを取得
                    reservations[leftForkIndex] = true
                    reservations[rightForkIndex] = true
                    forks[leftForkIndex].wait()
                    forks[rightForkIndex].wait()
                    print("哲学者\(philosopherNumber)は食事中である。")
                    usleep(UInt32.random(in: 1_000_000...2_000_000))
                    // 食事が終わったら、フォークを解放
                    forks[leftForkIndex].signal()
                    forks[rightForkIndex].signal()
                    // フォークの予約を解除
                    reservations[leftForkIndex] = false
                    reservations[rightForkIndex] = false
                }
            }
        }
        philosophers.forEach { $0.start() }
        RunLoop.main.run()
    }