ピーターソンのアルゴリズム

ピーターソンのアルゴリズム

ピーターソンのアルゴリズムは、1981年にロチェスター大学のGary Petersonによって提案された相互排他のための方法です。このアルゴリズムは、共有メモリを用いて2つのプロセスが互いに競合することなくリソースを共有することを目的としています。特に、プロセスが同時にクリティカルセクションに入らないように制御するための仕組みを提供します。

アルゴリズムの基本操作

このアルゴリズムでは、主に二つの変数「flag」と「turn」を使用します。具体的には、次のような処理が行われます。

```c
flag[0] = 0;
flag[1] = 0;

// プロセスP0
flag[0] = 1;
turn = 1;
while (flag[1] && turn == 1);
// クリティカルセクション
...
flag[0] = 0;

// プロセスP1
flag[1] = 1;
turn = 0;
while (flag[0] && turn == 0);
// クリティカルセクション
...
flag[1] = 0;
```

ここで、「flag」の値が1のプロセスはクリティカルセクションに入りたいことを意味し、「turn」は次にクリティカルセクションに入る権限を持つプロセスを示します。具体的には、プロセスP0がクリティカルセクションに入るためには、プロセスP1がクリティカルセクションに入ることを望んでいないか、またはP1が「turn」を0に設定して、P0に優先権を与える必要があります。

アルゴリズムの特性

このアルゴリズムは、以下の3つのミューテックスの基本条件を満たします。

1. 相互排他

P0とP1は、同時にクリティカルセクションに入ることはありません。つまり、P0がクリティカルセクションにいるときは、必ず「flag[1]」または「turn」のいずれかが0であり、P1はクリティカルセクションにアクセスできません。

2. 進捗要求

プロセスP0がクリティカルセクションに入ることを希望していない場合、P1はすぐにクリティカルセクションにアクセス可能です。これにより、どちらのプロセスが先に入るかは明確に決まりません。

3. 有限の待ち時間

任意のプロセスは、クリティカルセクションに入るために適度に待たされることになります。もし他のプロセスに優先権を譲った場合、譲ったプロセスはその処理を終えて「flag」を0にするため、他方のプロセスがクリティカルセクションにアクセスすることが可能になります。

実装の注意点

最近のCPUは、効率を向上させるために命令やメモリアクセスの順序を変更することがあります。このようなプロセッサには、メモリアクセスの順序を固定する機能、たとえばメモリバリア命令が含まれています。ピーターソンのアルゴリズムをアウト・オブ・オーダー（命令の順序を変更する）実行プロセッサで実施するには、そのような機能を使い確実に順序が保たれるよう設計する必要があります。

さらに、現代のプロセッサには不可分操作の機能が有しており、具体的にはx86系プロセッサの「XCHG」命令や、それ以外のアーキテクチャに含まれる「Load-Link/Store-Conditional」命令があります。これらの命令を使用することで、共有メモリを利用した手法よりも効率的に同期処理を実現できます。

結論

ピーターソンのアルゴリズムは、シンプルで効果的な手法として多くの文献で紹介されています。しかし、その実際の使用にあたっては、ハードウェアやプロセッサの特性を十分に考慮する必要があります。「デッカーのアルゴリズム」や「ランポートのパン屋のアルゴリズム」など、他のアルゴリズムと共に理解を深めることが重要です。また、ミューテックスや排他制御に関する知識も不可欠です。

もう一度検索