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

ピーターソンのアルゴリズムは、通信のために共有メモリだけを使い2個のプロセス間でリソースを競合することなく共有する相互排他のためのアルゴリズムである。これは、1981年、ロチェスター大学の Gary Peterson が定式化した。

ハードウェアレベルでは一般に、アトミックなアクセスを達成するのにピーターソンのアルゴリズムを必要とすることはない。プロセッサにはテスト・アンド・セット命令などが装備されていて、同時並行的アクセスを実現できる。特殊なソフトウェアの技術は必要ではない。

1. アルゴリズム
---------

flag[0] = 0 flag[1] = 0

p0: flag[0] = 1 p1: flag[1] = 1 turn = 1 turn = 0while; while; // do nothing // do nothing // critical section // critical section ... ... // end of critical section // end of critical section flag[0] = 0 flag[1] = 0

このアルゴリズムでは、二つの変数 //flag// と //turn// を使用する。//flag// の値が 1 のとき、そのプロセスがクリティカルセクションに入りたいことを示している。//turn// はその時点で優先権を持つプロセスの識別子を保持する。プロセス P0 がクリティカルセクションに入るには、P1がクリティカルセクションに入ろうとしていないか、P1 が turn を 0 に設定して P0 に優先権を与えている必要がある。

このアルゴリズムは以下に述べるミューテックスの3つの基本条件を満たしている。

1.1. 相互排他
---------

P0とP1は決して同時にクリティカルセクションには入らない。P0がクリティカルセクションにあるとき//flag[1]//か//turn//のどちらかが 0 である。どちらにしても P1 はクリティカルセクションに入れない。

1.2. 進捗要求
---------

プロセス P0 がクリティカルセクションに入ろうとしていない場合、P1 は即座にクリティカルセクションに入ることができる。P0 と P1 の間でクリティカルセクションに入るべき順番は全く決まっていない。

1.3. 有限の待ち時間
------------

プロセスはクリティカルセクション1回分の処理時間以上に待たされることはない。他のプロセスに優先権を与えると、そのプロセスはクリティカルセクションの最後まで動作し、自身の//flag//を 0 にするので、もう一方のプロセスがクリティカルセクションに入ることができるようになる。

2. 2個のPOSIXスレッドを使用したC言語での実装例
----------------------------

/*

ANSI C89 source, KNF style implementation of Peterson's Algorithm.
Copyright  2005, Matthew Mondor
Released in the public domain .
Please fix any bugs as needed, preserving the KNF style and this comment,
unless considered inconvenient in which case you can do whatever you want
with the code.
/
include
include
include
include struct pa_desc { int *f0, *f1; int last; };

void pa_init; void pa_desc_init; void pa_desc_lock; void pa_desc_unlock;

void *thread0_main; void *thread1_main; void threadx_critical;

int main;

static int pa_f0, pa_f1, pa_last;

/* Shared */

define BUCKETS 100int gi, g[BUCKETS];

/*

Initializes the pa system. To be called by the process once before
initializing pa descriptors.
/void pa_init {

pa_f0 = pa_f1 = pa_last = 0; }

/*

Initializes a pa descriptor for use by a thread.
One thread should use id 0 and the other one id 1.
/void pa_desc_init {

assert;

if  { d->f0 = &pa_f0; d->f1 = &pa_f1; d->last = 1; } else if  { d->f0 = &pa_f1; d->f1 = &pa_f0; d->last = 0; } }

void pa_desc_lock {

for (*d->f0 = 1, pa_last = d->last;

d->f1 == 1 && pa_last == d->last; ) ;}

void pa_desc_unlock {

d->f0 = 0;}

/*

Main loop of the first concurrent thread
//* ARGSUSED */ void * thread0_main { struct pa_desc d;

pa_desc_init;

for  { pa_desc_lock; threadx_critical; pa_desc_unlock; }

/* NOTREACHED */ return NULL; }

/*

Main loop of the second concurrent thread
//* ARGSUSED */ void * thread1_main { struct pa_desc d;

pa_desc_init;

for  { pa_desc_lock; threadx_critical; pa_desc_unlock; }

/* NOTREACHED */ return NULL; }

/*

Critical function which would normally have concurrency issues if two
threads executed it without locking.
/void threadx_critical { int i;

/* Do something which would normally have dual concurrency issues */ for  g[i] = gi++; for   printf; }

/*

Test program which demonstrates that dual concurrency can be achieved
without locking using Peterson's algorithm. We run two concurrent threads
which voluntarily perform concurrency sensitive operations on a shared
memory region .
//* ARGSUSED */ int main { pthread_t tid1, tid2; pthread_attr_t tattr;

gi = 0; pa_init;

pthread_attr_init; pthread_attr_setdetachstate;

/* Note: a real application would perform error checking */ pthread_create; pthread_create;

pthread_join; pthread_join; /* NOTREACHED */

return EXIT_SUCCESS; }

<WtXmlEndTag />

3. 注
----

最近のCPUは実行効率を改善するために命令やメモリアクセスの並べ替えを行う。そのようなプロセッサには何らかの方法でメモリアクセスの順番を変えないようにする機能がある。例えばメモリバリア命令がそれである。ピーターソンのアルゴリズムなどをアウト・オブ・オーダー実行プロセッサで実装するには、一般にそのような操作を使用して設計した順番通りに処理が行われるようにしなければならない。

そのようなCPUには不可分操作機能も備わっている。例えば、x86系プロセッサの XCHG 命令、Alpha、MIPS、PowerPCなどのアーキテクチャのLoad-Link/Store-Conditional命令などである。これらの命令は共有メモリを使用した手法よりも効率的に同期プリミティブを構築するのに使われる。

4. 注釈
-----

5. 関連項目
-------

デッカーのアルゴリズム
ランポートのパン屋のアルゴリズム
ミューテックス
排他制御