つかびーの技術日記

(情報)工学修士, 元SIer SE, 現Web系 SEの技術blogです。Scala, Java, JS, TS, Python, Ruby, AWS, GCPあたりが好きです。

JavaのレースコンディションをCollectionで実演して学んでみる

   

レースコンディション＝競合状態

個人的な見解ですが、学術分野以外ではあまり使われない言葉です。意味も結構広いですし。

今回はこのレースコンディション、スレッドセーフがテーマです。実際にスレッドセーフでないメソッドを利用して問題が発生する様子を見てみます。

スレッドセーフ

Javaでスレッドセーフと言えばAPIドキュメントを見ているとよく目に留まるアレが思いつきます。例えばArrayListのJavadocに以下の記述があります。

Note that this implementation is not synchronized.
この実装は同期化されません。

この文に続く説明を見ると分かりますが、複数スレッドでアクセスして、１スレッドでも変更を伴う操作をするとまずいようです。これはスレッドセーフではありません。逆に複数スレッドを意識して正しく設計・実装されたものはスレッドセーフです。例えばArrayListのスレッドセーフ版はCollections.synchronizedListメソッドによって取得できます。

スレッドセーフでないAPIを理解するためのレースコンディションの理解

情報工学の教育分野ではレースコンディションを、変数を加算するときのアトミック性に注目して説明することが多いように思います。例えば共有の変数count(初期値0)があったとして、二つのスレッドで1ずつ加算することを考えます。普通に考えれば結果は2になってほしいです。例えば(少々乱暴ですが)以下のような実行順序で。

  1. スレッドAはcount変数の値(0)をレジスタ1に格納する
    count=0, レジスタ1=0
  2. スレッドAはレジスタ1の値を1加算する
    count=0, レジスタ1=1
  3. スレッドAはレジスタ1の値(1)をcount変数に格納する
    count=1, レジスタ1=1
  4. スレッドBはcount変数の値(1)をレジスタ1に格納する
    count=1, レジスタ1=1
  5. スレッドBはレジスタ1の値を1加算する
    count=1, レジスタ1=2
  6. スレッドBはレジスタ1の値(2)をcount変数に格納する
    count=2, レジスタ1=2

結果はcount=2になりました。スレッドが並列に動作する場合、以下のようになったりします。

  1. スレッドAはcount変数の値(0)をレジスタ1に格納する
    count=0, レジスタ1=0, レジスタ2=0
  2. スレッドBはcount変数の値(0)をレジスタ2に格納する
    count=0, レジスタ1=0, レジスタ2=0
  3. スレッドBはレジスタ2の値を1加算する
    count=0, レジスタ1=0, レジスタ2=1
  4. スレッドBはレジスタ2の値(1)をcount変数に格納する
    count=1, レジスタ1=0, レジスタ2=1
  5. スレッドAはレジスタ1の値を1加算する
    count=1, レジスタ1=1, レジスタ2=1
  6. スレッドAはレジスタ1の値(1)をcount変数に格納する
    count=1, レジスタ1=1, レジスタ2=1

結果はcount=1になりました。処理順が変わったために、状態が変わってしまいました。これがレースコンディションです。

ArrayListのレースコンディション問題の再現

前置きは終わりにして、実際どうしたら問題が発生するのか再現してみます。

import java.util.ArrayList;
import java.util.List;

public class MainArrayList {
  private static int THREAD_COUNT = 100;

  public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();

    List<Thread> threads = new ArrayList<>();
    for (int i = 0; i < THREAD_COUNT; i++) {
      threads.add(new Thread(new AccessList(list, "Thread" + i)));
    }

    for (Thread t : threads) {
      t.start();
    }
  }

}
import java.util.List;

public class AccessList implements Runnable {
  private List<Integer> list;
  private String id;

  public AccessList(List<Integer> list, String id) {
    this.list = list;
    this.id = id;
  }
  @Override
  public void run() {
    for (int i = 0; i < 100; i++) {
      System.out.println(String.format("id=%s,index=%d", id, i));
      list.add(i);
    }
    System.out.println(String.format("id=%s,list.size=%d", id, list.size()));
  }

}

100スレッドを実行して各スレッドで共有しているArrayListに100個ずつ要素を追加します。最後にprintlnで現在のArrayListのサイズを出力しています。つまり、最後に実行完了するスレッドでは、ArrayListのトータルサイズが出力されるはずです。

これを実行してみると10000だったり9999だったりします。9999のときは問題が発生しています。スレッドAもスレッドBも同じindexに要素を追加しようとしたため、先に書き込まれた分が上書きされてしまったという感じでしょう。これは多分正しいです。

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

これはArrayListのaddメソッドです。elementData[size++] = eによって要素を追加しています。ここで発生する問題は冒頭のレースコンディションの説明で利用したケースと同じです。

  1. スレッドAはsizeの値をレジスタ1に格納する
    レジスタ1=x
  2. スレッドBはsizeの値をレジスタ2に格納する
    レジスタ1=x, レジスタ2=x
  3. スレッドAはレジスタ1のインデックスの場所にeを格納する
  4. スレッドBはレジスタ2のインデックスの場所にeを格納する

※実際はアドレス計算などもありますが、ここでは省略しています。

ArrayListのサイズが10000になる場合もあるので、問題の再現性が100%でなく、非常にやっかいです。今回のサンプルコードは小さいのですぐ気付けますが、実際はこうはいかないでしょう。コードはもっと巨大ですし、エラーになるわけではないので、そもそも問題が発生していることに気付けない可能性さえあります。恐ろしいです。

HashMapのレースコンディション問題の再現

ArrayListと同じようなソースコードを用意してみます。今度はputで。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MainHashMap {
  private static int THREAD_COUNT = 100;

  public static void main(String[] args) {
    Map<String, Integer> map = new HashMap<>();

    List<Thread> threads = new ArrayList<Thread>();
    for (int i = 0; i < THREAD_COUNT; i++) {
      threads.add(new Thread(new AccessMap(map, "Thread" + i)));
    }

    for (Thread t : threads) {
      t.start();
    }

  }

}
import java.util.Map;

public class AccessMap implements Runnable {

  private Map<String, Integer> map;
  private String id;

  public AccessMap(Map<String, Integer> map, String id) {
    this.map = map;
    this.id = id;
  }

  @Override
  public void run() {
    for (int i = 0; i < 100; i++) {
      System.out.println(String.format("id=%s,index=%s", id, i));
      map.put(id + i, i);
    }
  }

}

これを実行するとプログラムが止まらなくなることがあります。無限ループです。

これについては以下のサイトが詳しいです。このサイトの良い所は2ページ目にHashMapの構造とループの原因を図示していることだと思います。

ThreadとHashMapに潜む無限回廊は実に面白い？

HashSetのレースコンディション問題の再現

HashMapと同じく無限ループが発生します。コードは省略します。

Collectionのレースコンディション対策

Collections.synchronized****メソッドを利用します。例えば上記のArrayListの例では初めにスレッド間で共有するArrayListをnewして作成しました。ここを変更します。

    List<Integer> list = Collections.synchronizedList(new ArrayList<Integer>());

これはスレッドセーフなので、何度実行しても問題は再現しませんでした。ちなみにこのメソッドが返すクラスはSynchronizedRandomAccessListです。

Collections.synchronized****は以下のように沢山あります。用途に合ったものを選べばOKです。

  • synchronizedCollection(Collection<T> c)
  • synchronizedList(List<T> list)
  • synchronizedMap(Map<K,V> m)
  • synchronizedSet(Set<T> s)
  • synchronizedSortedMap(SortedMap<K,V> m)
  • synchronizedSortedSet(SortedSet<T> s)

 

 - Java ,