クリティカルリージョン(Critical Region)

まずは、クリティカルリージョン(Critical Region)という概念について押さえていきます。

クリティカルリージョンとは、

共有資源の変更を行うプログラム

のことです。

具体例を見た方がわかりやすかったので、具体例をみていきます。

クリティカルリージョン(Critical Region)具体例

講義スライド(102)から引用

排他制御の必要性を説明する際に問題になった部分ですね。

色枠で囲まれているプログラムは、共有資源の変更を行っており、排他制御なしで並行処理を行うと、実行順によって不整合を起こすプログラムです。

このプログラムを、クリティカルCritical Region)と呼びます。

ロックによる排他制御と無限後退

では、続いて排他制御のアプローチについてまとめていきます。 1つ目は、ロックによる排他制御です。

基本的な考え方は以下の通りです

1. 各資源 S 毎に共有メモリ上に一ビットの錠（Lock) を割り当てる．
2. Lock == 1 なら使用中，Lock == 0 なら資源使用可と約束．
3. Lock を取得する処理，Lock を解放する処理を作成．

このアプローチは、一見するとうまくいきそうな気がしますよね。

しかし、このアプローチは、

Lock自身が共有資源。
Lockの取得と解放もまたクリティカルリージョン
つまり、Lockについても排他制御をしないといけない

ということになってしまいます。

排他制御のアプローチのはずのLockを利用するためにさらに、排他制御をするという無限後退。。w

ということで、このロックによる排他制御ではうまくはいきません。

test and set 命令

では、どうするか？ですが、 test and set 命令を使えば解決します。

test and set 命令は、Lockなどの共有資源へのメモリアクセスを排除した状態で、読み込みと書き込みを実行します。一連の処理を不可分で実行するというわけですね。

このような処理をアトミックなメモリアクセスと呼びます。

今までのアプローチでは読み込みと書き込みをそれぞれの命令として実行していたため、実行順序によってデータの不整合を起こしてしまいました。

が、ハードウェアの命令として用意して、それを使用することでロックによる排他制御の無限後退問題を解決するというわけですね。

test and set 命令をProducer-Consumer問題に適用してみる

process Producer
{
    while (TRUE) {
        while(!text-and-set(Lock));
        if (index == MAX)
        {
        }
        else {
            {data作成;}
            index = index + 1;
            Buffer[index] = data
        }
        Lock = 0;
    }
}

このコードは以下のようなロジックで動きます。