並行処理=一つのまとまった問題を複数で同時に解くこと

まずは、概念的なところから理解していきます。

この講義では冒頭で

「計算機システムは、人間の知的活動をモデル化して作られたもの。なので、人間社会で起こる問題もそのまま受け継がれる」

という説明あるのですが、これに倣うと並行処理についても同様に人間社会の話としても概念的には理解することができます。

並行処理とだけ聞くと難しそうなイメージを持っていましたが、要するに「一つのまとまった問題を複数で同時に解くこと」と定義できます。

一つのまとまった問題を複数で同時に解くこと、日常生活でも仕事でも、同じことをやっておりますよね。

排他制御の必要性

続いて、並行処理の話に排他制御が登場する理由についてです。

まずは、概念的な理解からですが、話はかなりシンプルです。

複数プロセスが同時に進行
↓
資源を競合
↓
競合の調停が必要

というお話です。

現実社会に置き換えてみると、すっと理解できるっすね。

複数人で一つの作業に同時にとりかかる場合には、道具や分担箇所などなど調停をしながら進めるはずです。

Producer Consumer問題

では、さらに具体的に排他制御の必要性について書いていきます。

まず講義では、以下のようなコードを例に説明しています

Producer スレッド

process Producer {
    while (TRUE) {
        if (index == MAX)
        {}
        else
        {
            {data 作成;}
            index = index + 1;
            Buffer[index] = data
        }
    }
}

Consumer スレッド

process Consumer {
    while (TRUE) {
        if (index == 0)
        {}
        else
        {
            data = Buffer[index];
            index = index - 1;
            {data の処理;}
        }
    }
}

それぞれについて、何をしているのか？を整理しましょう。

講義スライドより引用

Producer スレッド

Producerでは、データを生成して、その後

index = index + 1;
Buffer[index] = data

共有メモリのindexを一つ上げて、Bufferにデータを書き込みに行ってます。

Consumerスレッド

Consumer側では、まずは

if (index == 0)
        {}

indexの値を参照しています。indexが1以上でなければ使用すべきデータがないからですね。

indexが1以上、つまりProducerによってデータが生成された場合に

data = Buffer[index];
index = index - 1;

Bufferからデータを取り出して、indexを1つ下げます。

ProducerとConsumerによるデータの不整合

コードを読んで見る限り、うまくProducerとConsumerが協調し合いながらうまく動きそうですよね。

しかし、並行処理、つまり２つのスレッドが同時に実行される場合を考えてみると、不整合がおきます。

今、２つのスレッドが同時に実行されると書きましたが、実際には２つのスレッドは同時ではなくコンテキストの切り替えながら実行されます。この切り替えの順番のランダム性が不整合を起こします。

実際にみていきましょう。

「正しい」挙動をする順番

まず、「正しい」挙動をする順番について確認します。

ProducerとConsumerがうまく動く場合には、以下の順序で実行される必要があります。

Producer側でindexを更新して、Bufferにデータを格納

1. index = index + 1;
2. Buffer[index] = data

Consumer側でBufferからデータを取り出し、indexを更新

3. data = Buffer[index];
4. index = index - 1;

不整合

では、次にデータの不整合を起こす順序についてです。

indexが1という設定で順を追ってみましょう。

Consumer側でindexを読み込み
1. index;  // index = 1

Producer側でindexを読み込み
2. index; // index = 1

Producer側でindexを更新と書き込みを実行
3. index = index + 1; // index = 2

Consumer側でindexを更新と書き込みを実行
4. index = index - 1; // index = 0

この時、Consumerのコンテキスト上ではindexは1のままなので、indexは1つ減り、0になります。

Producerは、メモリにindex=2という値で書き込んでいるはずが、実行順序のせいでindexは0という状態になっています。

これが不整合の例です。

なるほど、コンテキストスイッチを理解しておくとすんなり理解できるっすね。