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

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ピーターソンのアルゴリズムは、通信のために共有メモリだけを使い「2個」のプロセス間でリソースを競合することなく共有する相互排他のためのアルゴリズムである。これは、1981年、ロチェスター大学の Gary Peterson が定式化した。（注："Operating Systems Review, January 1990 ('Proof of a Mutual Exclusion Algorithm', M Hofri)" で議論されているように、ピーターソンのアルゴリズムは2個以上のプロセスに一般化できる）

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

[編集] アルゴリズム

 flag[0]   = 0
 flag[1]   = 0
 turn      = 0
 
 p0: flag[0] = 1                        p1: flag[1] = 1
     turn = 1                               turn = 0
     while( flag[1] && turn == 1 );         while( flag[0] && turn == 0 );
             // 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つの基本条件を満たしている。

[編集] 相互排他

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

[編集] 進捗要求

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

[編集] 有限の待ち時間

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

[編集] 2個のPOSIXスレッドを使用したC言語での実装例


/*
 * ANSI C89 source, KNF style implementation of Peterson's Algorithm.
 *
 * Copyright (c) 2005, Matthew Mondor
 * Released in the public domain (may be licensed under the GFDL).
 *
 * 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 <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

struct pa_desc {
        int     *f0, *f1;
        int     last;
};

void    pa_init(void);
void    pa_desc_init(struct pa_desc *, int);
void    pa_desc_lock(struct pa_desc *);
void    pa_desc_unlock(struct pa_desc *);

void    *thread0_main(void *);
void    *thread1_main(void *);
void    threadx_critical(void);

int     main(int, char **);

static int      pa_f0, pa_f1, pa_last;

/* Shared */
#define BUCKETS 100
int             gi, g[BUCKETS];

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

        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(struct pa_desc *d, int id)
{

        assert(id == 0 || id == 1);

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

void
pa_desc_lock(struct pa_desc *d)
{

        for (*d->f0 = 1, pa_last = d->last;
            *d->f1 == 1 && pa_last == d->last; ) ;
}

void
pa_desc_unlock(struct pa_desc *d)
{

        *d->f0 = 0;
}

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

        pa_desc_init(&d, 0);

        for (;;) {
                pa_desc_lock(&d);
                threadx_critical();
                pa_desc_unlock(&d);
        }

        /* NOTREACHED */
        return NULL;
}

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

        pa_desc_init(&d, 1);

        for (;;) {
                pa_desc_lock(&d);
                threadx_critical();
                pa_desc_unlock(&d);
        }

        /* NOTREACHED */
        return NULL;
}

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

        /* Do something which would normally have dual concurrency issues */
        for (i = 0; i < BUCKETS; i++)
                g[i] = gi++;
        for (i = 0; i < BUCKETS; i++)
                (void) printf("g[%d] = %d\n", i, g[i]);
}

/*
 * 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 (gi, g[BUCKETS]).
 */
/* ARGSUSED */
int
main(int argc, char **argv)
{
        pthread_t       tid1, tid2;
        pthread_attr_t  tattr;

        gi = 0;
        pa_init();

        pthread_attr_init(&tattr);
        pthread_attr_setdetachstate(&tattr, 0);

        /* Note: a real application would perform error checking */
        pthread_create(&tid1, &tattr, thread0_main, NULL);
        pthread_create(&tid2, &tattr, thread1_main, NULL);

        pthread_join(tid1, NULL);
        pthread_join(tid2, NULL);
        /* NOTREACHED */

        return EXIT_SUCCESS;
}

[編集] 注

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

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