example

メモリバリア付き粒度保証メモリアクセスプリミティブの使用例

以下では，「スレッド」ではなく，「プロセッサ」としている．ここでのプリミティブは，各スレッドが実際のプロセッサと 1対1に対応していることを期待しているためである．スレッド数が実際のプロセッサ数より多い場合は，スピンウェイト(同期成立までのスピンしての待ち合わせ) で無駄にプロセッサを働かせる可能性が高くなる．

単純な通知(単体の生産者)と受け取り(複数の消費者)

int progress;

void signal_progress(int newprg){
  atomic_write_int_to_finish_access(progress,newprg);
}

int wait_progress(int i){
  int prg;
  do{
    while(xread_int(progress) < i);
  }while((prg = atomic_read_int_to_start_access(progress)) < i);
  return prg;
}

あるプロセッサが計算するデータが揃うまで待機するときなどに同期が必要となる。この例では、ある単体のプロセッサがデータを生産するとカウンタを更新する。他の複数のプロセッサはカウンタが意図する値まで更新されるのを待つ (その後，計算済のデータを消費する)。

カウンタを用いたバリア同期(プロセッサ数P)

 int count = 0;
 
 void barrier_sync(int P){
   int v;
   do{
     v = xread_int(count);
   }while(cas_int_to_finish_access(count, v, (v+1 < P) ? v+1 : 0));
   do{
       while(xread_int(count) > 0);
   }while(atomic_read_int_to_start_access(count) > 0);
 }

複数のプロセッサで並列計算を行う場合、次の計算に使うデータが揃うまで待機するときなどにバリア同期が必要になる。この例では、プロセッサが処理を完了するごとに、カウンタをインクリメントして待ち状態に入り、全てのプロセッサの処理が終了すると、カウンタを0に戻して次の処理に入る。カウンタのインクリメントはcasプリミティブを使って不可分に行われる。カウンタが0に戻るまで待つことでバリア同期が取られる．
ただし，この方法では，1度しかバリア同期は取ることはできない．つまり，同じカウンタはそのまま再利用できない．なぜなら，まだ待っているスレッドがいるうちに，先に処理を進めたスレッドが再びバリア同期をとるために，カウンタを操作すると1度0にリセットしたという情報が失われるから． 2つのバリア同期関数を準備し，2つのカウンタを必ず交互に使うという手はあるが，次に示すフラグによるバリア同期を用いたほうがよい．
POSIX threadsを用いてバリア同期を記述する場合、pthread_mutex_lockなどを使ってスレッドの排他的制御を行ってカウンタを更新する必要があり、大きなオーバヘッドとなり得る。一方、共有メモリプリミティブではxreadとcasを使うことによりロックのコストをかけないで実現できる。

フラグによるバリア同期(プロセッサ数P)

 int ba[MAXPROC];
 
 void init_barrier_sync(int P){
   int i;
   for(i = 0; i < P; i++) ba[i] = 1;
 }
 
 void barrier_sync(int P, int myid){
   if (myid == 0){
     int i, b = -ba[0];
     for(i = 1; i < P; i++)
       do{
         while(xread_int(ba[i]) != b);
       }while(atomic_read_int(ba[i]) != b);
     start_access_after_read();
     atomic_write_int_to_finish_access(ba[0],b);
   }
   else {
     int b = -ba[myid];
     atomic_write_int_to_finish_access(ba[myid], b);
     do{
       while(xread_int(ba[0]) != b);
     }while(atomic_read_int_to_start_access(ba[0]) != b);
   }
 }

各プロセッサは同期のためのフラグをそれぞれ持ち、自分の処理が終了するとbarrier_sync 関数を呼び出し、フラグの正負を反転させて自プロセッサの処理が完了したことを示し、他のプロセッサの処理完了を待つ。プロセッサ全体の終了確認は、一つのスレッドが代表となり(例ではmyid == 0のプロセッサ)、他の全てのフラグをチェックすることにより他プロセッサの処理の完了を確認し、自身のフラグの正負を反転させることによって同期の完了を全体に通知する。

早い者勝ち判定による排他制御(2プロセッサの場合)

 int x1=0,x2=0;
 
 /* processor1 */
 atomic_write_int_to_start_access(x1, 1); 
 if (atomic_read_int(x2) == 0){
   .../* critical section */
 }

 
 
 /* processor2 */
 atomic_write_int_to_start_access(x2, 1); 
 if (atomic_read_int(x1) == 0){
   .../* critical section */
 }

この例では、メモリバリアによって、プロセッサ1ではx1の書き込みと x2の読み出しの完了順序が、プロセッサ2ではx2の書き込みとx1の読み出しの完了順序が保証されているので、2つのプロセッサが同時にクリティカルセクションに入らないことが保証される。この例では、ロックなどのコストが高く、同時アクセスを過度に制限するプリミティブを用いないで、早い者勝ちの判定ができる。

早い者勝ちによる要求(複数のクライアント)と受け取り(単体のサーバ)

 /* client */
 while(cas_int_to_finish_access(port, 0, request)){
   ... /* その他の処理(他への応答をする、など) */
 }

 /* server */
 do{
   while(xread_int(port) == 0);
 }while((req = atomic_read_int_to_start_access(port)) == 0);
 atomic_write_int(port, 0);
 ... /* reqに応える */

サーバとクライアントはportを通じて要求のやりとりを行う。 portへの要求をcasを使って行うことによって、ロックなしで排他的な書き込みを行うことができる。クライアントの書き込んだ要求をサーバが読み出すと，再び要求を受け付けるために0を書き込むことにする。

バージョン番号による構造体の不可分な更新(単体)と読み出し(複数可)

 /* writer */
 vn = obj->vn;
 atomic_write_int_to_start_write(obj->vn, 0);
 obj->f1 = f1;
 obj->f2 = f2;
 obj->f3 = f3;
 atomic_write_int_to_finish_write(obj->vn, vn+2);

 /* reader */
 do{
   do{
     while(xread_int(obj->vn) == 0);
     vn = atomic_read_int_to_start_read(obj->vn);
   }while(vn == 0);
   f1 = obj->f1;
   f2 = obj->f2;
   f3 = obj->f3;
 }while(atomic_read_int_to_finish_read(obj->vn) != vn);

バージョン番号が0のとき、構造体は更新中なので、読み出しは更新が完了するのを待つ。読み出しを開始する際には、その時点でのバージョン番号を読み出しておき、読み出し終了時点でのバージョンと比較し、読み出し中に更新がなかったかを確認し、あった場合は再度読み直す。このようにバージョン番号により、構造体の状態を管理し、コストが高く同時アクセスを過度に制限するロックなどを用いることなく、一貫性の保たれた構造体へのアクセスを実現している。

プリミティブ一覧へ戻る