ABA problemとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > ABA problemの意味・解説 

ABA問題

(ABA problem から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/01/10 03:53 UTC 版)

ABA問題: ABA problem)とは、マルチスレッドプログラミングにおいて同期化の過程で発生する問題であり、ある記憶域を二回読み出し、二回の読み出しが同じ値であることを「変更がない」とみなすことにしたとき、二回の読み出しの間に別のスレッドが値を変更し、他の作業を行った後また元の値に戻すと、最初のスレッドが誤って「変更がなかった」とみなしてしまうというものである。

ABA 問題は、複数のスレッドや(or プロセス)が共有されたメモリにアクセスする場合に生じる。下記のイベントの流れは、ABA 問題を発生させる。

  • プロセス が共有メモリから値 A を読み出す
  • プリエンプトされ、プロセス が実行される
  • は、共有メモリの値 A を値 B に書き換え、さらにプリエンプションの前に A に書き戻す
  • は実行を再開し、共有メモリの値が変更していないことを確認して実行を継続する

は実行を継続するが、共有メモリの変更が分からなかったことにより、誤った振る舞いをする可能性がある。

ABA問題に遭遇する一般的なケースとして、ロックフリーのデータ構造を実現する場合がある。ある要素がリストから削除され、解放された後、新しい要素が割り当てられて、リストに追加されると、新規に割り当てられた要素と、削除された要素がメモリ管理上の最適化によって同じものになることがよくある。新しい要素のポインタは古いものと同一になり、ここで ABA 問題を生じる。

下記の ロックフリースタックを考える:

  /* ABA 問題を生じるロックフリースタック */
  class Stack {
    volatile Obj* top_ptr;
    //
    // トップのオブジェクトをポップし、そのポインタを返す
    //
    Obj* Pop() {
      while(1) {
        Obj* ret_ptr = top_ptr;
        if (!ret_ptr) return NULL;
        Obj* next_ptr = ret_ptr->next;
        // トップのノードはまだ ret であり、スタックに変更があったと考えない
        // (これは、ABA 問題のために正しいとはいえない)
        // トップを次の要素に(アトミックに)変更
        if (CompareAndSwap(top_ptr, ret_ptr, next_ptr)) {
          return ret_ptr;
        }
        // スタックは変更され、最初からやり直し
      }
    }
    //
    // obj_ptr で指すオブジェクトをスタックにプッシュする
    //
    void Push(Obj* obj_ptr) {
      while(1) {
        Obj* next_ptr = top_ptr;
        obj->next = next_ptr;
        // トップノードがまだ next であると、スタックに変更があったと考えない
        // (これは、ABA 問題のために正しいとはいえない)
        // トップを obj に(アトミックに)変更
        if (CompareAndSwap(top_ptr, next_ptr, obj_ptr)) {
          return;
        }
        // スタックは変更され、最初からやり直し
      }
    }
  };

このコードは通常は並列的なアクセスの問題を生じないが、ABA 問題を生じる。下記のようなシーケンスを考える。

スタックが初期状態で トップ → A → B → C というデータを持っているとする。

まずスレッド 1 が top から開始し、

  ret = A;
  next = B;

CompareAndSwapの直前に割り込まれると、

  { // スレッド 2 が pop を実行:
    ret = A;
    next = B;
    CompareAndSwap(A, A, B)  // 成功, top = B
    return A;
  } // 新しいスタックは トップ -> B -> C
  { // スレッド 2 が pop を再び実行:
    ret = B;
    next = C;
    CompareAndSwap(B, B, C)  // 成功, top = C
    return B;
  } // 新しいスタックは トップ -> C
  delete B;
  { // スレッド 2 が A をトップに載せる:
    A->next = C;
    CompareAndSwap(C, C, A)  // 成功, top = A
  }

現在、スタックの内容は top → A → C である。

ここでスレッド 1 が再開すると、CompareExchange(A, A, B)が実行される。

この処理は、top == ret (いずれも A)であるから、必ず成功し、top を next (この場合B) に割り当てる。しかし、B は解放済みであるから、何らかの問題が生じる。

対策

一般的な対策としては、タグとなるビットを追加して変更を表現することである。たとえばポインタのコンペア・アンド・スワップでは、アドレスの下位のビットで、ポインタの示すデータが何回書き換わったかを表現する。これにより、アドレスが同じであってもタグビットが異なるため、次回のコンペア・アンド・スワップを失敗させることができる。タグビットはすぐに一周してしまうので、これで問題が完全に解決するわけではない。アーキテクチャによっては、ダブルワードのコンペア・アンド・スワップを提供しており、もっと大きなタグを使うことができる。この場合には A が最初とわずかに異なっているので、 ABA' 問題と呼ばれることもある。

確実だが高価な方法として、データ要素そのものではない中間ノードを用いる方法がある。中間ノードはデータ要素のように変更・削除されないようにできるので、要素が挿入されたり削除された場合でも不変性を保証できる[Valois]。

他には、ハザードポインタを用いる方法がある。これはリストにはない箇所を示すポインタである。ハザードポインタは変更中の状態を表現し、後でデータを同期する必要があることを示す[Doug Lea]。

アーキテクチャによってはもっと大きなアトミック操作を可能にするものがある。たとえば、二重リンクリストをアトミックに更新できるものもある。

また、アーキテクチャによってはLoad-Link/Store-Conditional命令を提供しているものがあり、これはアドレスの示す箇所に他のストアが行われない場合に限りストアを実行するというものである。記憶域がある値を持っていることと、記憶域が変化したことという二つの概念をうまく分離することができる。DEC AlphaPowerPC がこの命令をサポートしている。

参考文献

  1. Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup. Lock-free Dynamically Resizable Arrays

「ABA problem」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ABA problem」の関連用語

ABA problemのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ABA problemのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのABA問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS