マルチスレッドJavaプログラムにおいてデータ破壊を回避するには、共有データを、並行して行われる書換えやアクセスから保護しなくてはならない。synchronized メソッド、synchronized ブロック、java.util.concurrent の動的なロックオブジェクトなどを使うことで、オブジェクト単位でロックを行うことができる。しかし、ロックを過度に使用すると、デッドロックを引き起こす場合がある。
Java 言語は、デッドロックを防いだり、あるいは検出したりしてくれない[JLS 2005]。デッドロックは、2つ以上のスレッドが、複数のロックの要求と解放を異なる順序で行う場合に発生しうる。それゆえ、複数のロックの取得と解放を同じ順序で行い、デッドロックを回避することが求められる。
さらに付け加えるならば、同期を行うのは必要不可欠な場合のみに限定するべきである。たとえば、paint()、dispose()、stop()、destroy() といったメソッドは、アプレット中では決して同期してはならない。なぜなら、これらのメソッドは常に専用のスレッドから呼び出され、使用されるからである。なお、Thread.stop()および Thread.destroy() メソッドは、非推奨とされている。詳細は、「THI05-J. スレッドの強制終了にThread.stop()メソッドを使用しない」を参照。
本ルールは、限られたリソースの中で動作しなくてはならないプログラムにも適用される。たとえば、2つ以上のスレッドが互いに、リソース(データベース接続など)の解放を待つ場合、活性(liveness)の問題が発生しうる。 このような問題は、待ち状態にある各スレッドが、ランダムな時間間隔でリソース要求を再試行することで解決できる。
違反コード (異なるロック順序)
以下の違反コードでは、不適切な同期が原因でデッドロックが発生する可能性がある。balanceAmount フィールドは、特定の BankAccount オブジェクトの口座残高を表わす。ユーザは、ある口座から別の口座へ、指定した金額をアトミックに送金することが許されている。
final class BankAccount {
private double balanceAmount; // 銀行口座の総額
BankAccount(double balance) {
this.balanceAmount = balance;
}
// このインスタンスから引数baのBankAccountインスタンスに
// amountを送金する
private void depositAmount(BankAccount ba, double amount) {
synchronized (this) {
synchronized (ba) {
if (amount > balanceAmount) {
throw new IllegalArgumentException(
"Transfer cannot be completed"
);
}
ba.balanceAmount += amount;
this.balanceAmount -= amount;
}
}
}
public static void initiateTransfer(final BankAccount first,
final BankAccount second, final double amount) {
Thread transfer = new Thread(new Runnable() {
public void run() {
first.depositAmount(second, amount);
}
});
transfer.start();
}
}
このクラスのオブジェクトは、デッドロックを引き起こす可能性がある。2つの口座 a と b を持つ攻撃者は、それぞれのBankAccountオブジェクトから送金を開始する2つのスレッドを生成できる。たとえば以下のコードを考えてみよう。
BankAccount a = new BankAccount(5000); BankAccount b = new BankAccount(6000); BankAccount.initiateTransfer(a, b, 1000); // スレッド 1 を開始 BankAccount.initiateTransfer(b, a, 1000); // スレッド 2 を開始
送金は、各スレッド内で実行される。スレッド1は、口座 b に amount で指定した金額をアトミックに送金し、次に同じ金額を口座 a から引き落とす。スレッド2は、逆の操作、すなわち、口座 b から口座 a への送金を行う。depositAmount() メソッドが実行されるとき、スレッド1はオブジェクト a のロックを獲得する。このとき、スレッド2は、オブジェクト b のロックを、スレッド1より前に獲得するかもしれない。その場合、次にスレッド1が b のロックを要求しても、既にスレッド2によって獲得されている。スレッド2も、a のロックを要求するが、既にスレッド1に獲得されている。どちらのスレッドも処理を進めることができないデッドロック状態である。
この違反コードでデッドロックが発生するかどうかは、プラットフォーム固有のスレッドスケジューリングに依存する。デッドロックが発生するのは、次の2つの条件が成り立つ場合である。
- 2つのスレッドが2つのロックをそれぞれ異なる順序で要求する
- 各スレッドがロックを獲得した結果、他方のスレッドの送金が完了しない
適合コード (private static final 宣言されたロックオブジェクト)
送金処理を実行する前に private static final 宣言されたロックオブジェクトを用いて同期することにより、デッドロックを回避することができる。
final class BankAccount {
private double balanceAmount; // 銀行口座の総額
private static final Object lock = new Object();
BankAccount(double balance) {
this.balanceAmount = balance;
}
// このインスタンスから引数baのBankAccountインスタンスに
// amountを送金する
private void depositAmount(BankAccount ba, double amount) {
synchronized (lock) {
if (amount > balanceAmount) {
throw new IllegalArgumentException(
"Transfer cannot be completed");
}
ba.balanceAmount += amount;
this.balanceAmount -= amount;
}
}
public static void initiateTransfer(final BankAccount first,
final BankAccount second, final double amount) {
Thread transfer = new Thread(new Runnable() {
@Override public void run() {
first.depositAmount(second, amount);
}
});
transfer.start();
}
}
上記コードでは、2つのスレッドが並行してそれぞれ相手の口座に送金しようとする場合でも、デッドロックは発生しない。一方のスレッドが private 宣言されたロックを獲得、送金処理を完了、そしてロックを解放する。その後で、もう一方のスレッドが処理を進めることになる。
この解決方法では private static 宣言されたロックを用いることで、送金処理をひとつずつ実行するようにシステムに制約をかけている。これは性能面では不利となる。4つの異なる口座間で行われる2つの送金処理であっても、並行して実行することができない。BankAccount オブジェクトの数が増えるにしたがって飛躍的に大きくなるため、処理数の増大に対応できない。
適合コード (正しく順序付けられたロック)
以下の適合コードでは、複数のロックの獲得と解放を同じ順序で行うようにしている。この例では、BankAccount オブジェクトを順序付けることで、それに対応するロックも順序付けることができる。そのようなわけで、BankAccount クラスで java.lang.Comparable インタフェースを実装し、compareTo() メソッドをオーバーライドしている。
final class BankAccount implements Comparable<BankAccount> {
private double balanceAmount; // 銀行口座の総額
private final Object lock;
private final long id; // 各 BankAccount に固有の値
private static long NextID = 0; // 次の未使用ID
BankAccount(double balance) {
this.balanceAmount = balance;
this.lock = new Object();
this.id = this.NextID++;
}
@Override public int compareTo(BankAccount ba) {
return (this.id > ba.id) ? 1 : (this.id < ba.id) ? -1 : 0;
}
// このインスタンスから引数baのBankAccountインスタンスに
// amountを送金する
public void depositAmount(BankAccount ba, double amount) {
BankAccount former, latter;
if (compareTo(ba) < 0) {
former = this;
latter = ba;
} else {
former = ba;
latter = this;
}
synchronized (former) {
synchronized (latter) {
if (amount > balanceAmount) {
throw new IllegalArgumentException(
"Transfer cannot be completed");
}
ba.balanceAmount += amount;
this.balanceAmount -= amount;
}
}
}
public static void initiateTransfer(final BankAccount first,
final BankAccount second, final double amount) {
Thread transfer = new Thread(new Runnable() {
@Override public void run() {
first.depositAmount(second, amount);
}
});
transfer.start();
}
}
送金処理が発生する度に2つの BankAccount オブジェクトの順序を調べ、1番目のオブジェクトのロックを2番目のオブジェクトのロックより先に獲得する。したがって、2つのスレッドで同じ2つの口座間の送金処理を試みると、どちらも、2番目の口座よりも先に1番目の口座のロックを獲得しようとする。その結果、一方のスレッドが、両方のオブジェクトのロックを獲得し、送金処理を完了した後に、両方のロックを解放する。その後、もう一方のスレッドが送金処理を進めることになる。
この適合コードでは、送金処理の対象となる口座が重複していない限り、複数の送金処理を並行して実行できる。
適合コード (ReentrantLock クラス)
以下の適合コードでは、各 BankAccount オブジェクトは、それぞれ java.util.concurrent.locks.ReentrantLock を持っている。depositAmount() メソッドは、両方の口座のロックを試み、失敗した場合にはロックを解放して、必要なら処理を再試行するように設計されている。
final class BankAccount {
private double balanceAmount; // 銀行口座の総額
private final Lock lock = new ReentrantLock();
private final Random number = new Random(123L);
BankAccount(double balance) {
this.balanceAmount = balance;
}
// このインスタンスから引数baのBankAccountインスタンスに
// amountを送金する
private void depositAmount(BankAccount ba, double amount)
throws InterruptedException {
while (true) {
if (this.lock.tryLock()) {
try {
if (ba.lock.tryLock()) {
try {
if (amount > balanceAmount) {
throw new IllegalArgumentException(
"Transfer cannot be completed");
}
ba.balanceAmount += amount;
this.balanceAmount -= amount;
break;
} finally {
ba.lock.unlock();
}
}
} finally {
this.lock.unlock();
}
}
int n = number.nextInt(1000);
int TIME = 1000 + n; // livelock を防ぐための 1 秒 + ランダムな遅延
Thread.sleep(TIME);
}
}
public static void initiateTransfer(final BankAccount first,
final BankAccount second, final double amount) {
Thread transfer = new Thread(new Runnable() {
public void run() {
try {
first.depositAmount(second, amount);
} catch (InterruptedException e) {
Thread.currentThread().interrupt(); // 割込みステータスのリセット
}
}
});
transfer.start();
}
}
上記の適合コードでは、無期限にロックを保持するメソッドが存在せず、デッドロックは発生しない。実行中のオブジェクト自身のロックを獲得しても、もう一方のロックを獲得できない場合、スレッドは獲得済みのロックを解放し、一定時間スリープした後に再度ロックの獲得を試みる。
このような形でロックを行うコードは、固有ロックを使用して同期する従来のコードと似た振舞いをする。しかし、ReentrantLock は、固有ロックにはない機能をいくつか提供する。たとえば、tryLock() メソッドは、他のスレッドが既にロックを保持している場合、待機状態とならずに即座に false を返す。また、java.util.concurrent.locks.ReentrantReadWriteLock クラスは multiple-readers/single-writer セマンティクスを備えている。このクラスは、書込みは排他的に行い、読取りは複数のスレッドが並行して行えるようにしたい場合、便利に使える。
違反コード (異なるロック順序、再帰的)
以下の不変な WebRequest クラスは、サーバが受け取ったウェブリクエストをカプセル化している。
// 不変なWebRequestクラス
public final class WebRequest {
private final long bandwidth;
private final long responseTime;
public WebRequest(long bandwidth, long responseTime) {
this.bandwidth = bandwidth;
this.responseTime = responseTime;
}
public long getBandwidth() {
return bandwidth;
}
public long getResponseTime() {
return responseTime;
}
}
各リクエストは、応答時間とリクエストを処理するのに使用したネットワーク帯域幅を示す値を持つ。
以下の違反コード例では、ウェブリクエストを監視し、処理するのに必要となった帯域幅と応答時間の平均を求める計算用ルーチンを提供している。
public final class WebRequestAnalyzer {
private final Vector<WebRequest> requests = new Vector<WebRequest>();
public boolean addWebRequest(WebRequest request) {
return requests.add(new WebRequest(request.getBandwidth(),
request.getResponseTime()));
}
public double getAverageBandwidth() {
if (requests.size() == 0) {
throw new IllegalStateException("The vector is empty!");
}
return calculateAverageBandwidth(0, 0);
}
public double getAverageResponseTime() {
if (requests.size() == 0) {
throw new IllegalStateException("The vector is empty!");
}
return calculateAverageResponseTime(requests.size() - 1, 0);
}
private double calculateAverageBandwidth(int i, long bandwidth) {
if (i == requests.size()) {
return bandwidth / requests.size();
}
synchronized (requests.elementAt(i)) {
bandwidth += requests.get(i).getBandwidth();
// ロックを昇順で獲得する
return calculateAverageBandwidth(++i, bandwidth);
}
}
private double calculateAverageResponseTime(int i, long responseTime) {
if (i <= -1) {
return responseTime / requests.size();
}
synchronized (requests.elementAt(i)) {
responseTime += requests.get(i).getResponseTime();
// ロックを降順で獲得する
return calculateAverageResponseTime(--i, responseTime);
}
}
}
このアプリケーションで使用される WebRequestAnalyzer クラスは、セッターメソッド addWebRequest() を持ち、Vector クラスの requests を使用してウェブリクエストのリスト管理を行う。すべてのスレッドは、getAverageBandwidth() および getAverageResponseTime() メソッドを呼び出すことで、ウェブリクエストの帯域幅の平均値や応答時間の平均値を取得できる。
これらのメソッドでは、Vector の個々の要素(ウェブリクエスト)のロックを保持することにより、粒度の細かいロックを行っている。このようなロックを行うことにより、計算処理の実行中であっても新規のリクエストを追加することが可能となっている。したがって、このメソッドによって正確な統計値を得ることができる。
しかし、この違反コードではデッドロックが発生しうる。2つのメソッドのなかにある同期ブロックでの再帰呼出しが、互いに逆の順番で個々の要素の固有ロックを取得するからである。すなわち、calculateAverageBandwidth() メソッドでは、インデックス0から requests.size() - 1 まで昇順でロックを要求するが、一方で calculateAverageResponseTime() メソッドは、インデックス requests.size() - 1 から0まで降順でロックを要求している。再帰呼出しを行っているため、どちらのメソッドにおいても獲得済みのロックは解放しない。calculateAverageBandwidth() メソッドを呼び出すスレッドと calculateAverageResponseTime() メソッドを呼び出すスレッドが並行して処理を行うとデッドロックが発生する。
たとえば、Vector 上にリクエストが20件あり、1つのスレッドが getAverageBandwidth() メソッドを呼ぶ場合、そのスレッドは Vector 中の最初の要素である WebRequest 0 の固有ロックを取得する。その間に、別のスレッドが getAverageResponseTime() を呼ぶと、Vector 中の最後の要素である WebRequest 19 の固有ロックを取得する。したがって、いずれのスレッドもすべてのロックを取得して計算を続行することができずにデッドロックが発生する。
addWebRequest() メソッドと calculateAverageResponseTime() との間にも競合状態が存在することに注意。Vector に関する繰返し処理を行っている間に新しい要素が追加される可能性があり、追加される前に算出された結果を無効にしてしまうかもしれない。この競合状態は、要素の挿入前に Vector の最後の要素(Vector に少なくとも1つの要素が存在する場合)にロックを行うことにより防ぐことができる。
適合コード
以下の適合コードでは、2つのメソッドはどちらも、Vector 内の最初のウェブリクエストから順にロックを獲得、解放する。
public final class WebRequestAnalyzer {
private final Vector<WebRequest> requests = new Vector<WebRequest>();
public boolean addWebRequest(WebRequest request) {
return requests.add(new WebRequest(request.getBandwidth(),
request.getResponseTime()));
}
public double getAverageBandwidth() {
if (requests.size() == 0) {
throw new IllegalStateException("The vector is empty!");
}
return calculateAverageBandwidth(0, 0);
}
public double getAverageResponseTime() {
if (requests.size() == 0) {
throw new IllegalStateException("The vector is empty!");
}
return calculateAverageResponseTime(0, 0);
}
private double calculateAverageBandwidth(int i, long bandwidth) {
if (i == requests.size()) {
return bandwidth / requests.size();
}
synchronized (requests.elementAt(i)) {
// ロックを昇順で獲得する
bandwidth += requests.get(i).getBandwidth();
return calculateAverageBandwidth(++i, bandwidth);
}
}
private double calculateAverageResponseTime(int i, long responseTime) {
if (i == requests.size()) {
return responseTime / requests.size();
}
synchronized (requests.elementAt(i)) {
// ロックを昇順で獲得する
responseTime += requests.get(i).getResponseTime();
return calculateAverageResponseTime(++i, responseTime);
}
}
}
あるスレッドが平均帯域幅や平均応答時間を計算している間、他のスレッドによる干渉やデッドロックは発生しない。なぜなら、スレッドはまず始めに先頭のウェブリクエストのロックを獲得しなければならないが、このロックは、先行するスレッドの計算が完了してはじめて獲得できるからである。
2つの理由から、この適合コードでは addWebRequest() メソッドで Vector の最後の要素をロックする必要はない。ひとつは、すべてのメソッドがロックを昇順で獲得していること、そしてもうひとつは Vector の更新内容が必ず計算結果に反映されるからである。
リスク評価
誤った順序でロックの取得、解放を行うと、デッドロックにつながるおそれがある。
| ルール | 深刻度 | 可能性 | 修正コスト | 優先度 | レベル |
|---|---|---|---|---|---|
| LCK07-J | 低 | 高 | 高 | P3 | L3 |
自動検出
いくつかの静的解析ツールはこのルールへの違反を検出できる。
関連ガイドライン
| CERT C Secure Coding Standard | CON35-C. Avoid deadlock by locking in predefined order |
| MITRE CWE | CWE-833. Deadlock |
参考文献
| [JLS 2005] | Chapter 17, Threads and Locks |
| [Halloway 2000] | JDC Tech Tips 2000年3月28日 |
翻訳元
これは以下のページを翻訳したものです。
LCK07-J. Avoid deadlock by requesting and releasing locks in the same order (revision 179)
コメント
共 有
