デッドロックについて java

Question

以下のソースにて、デッドロックは発生しますか？

※複数回、実行していますが、未だ、デッドロックは発生しておりません。

※標題：徹底攻略Java SE 11 Gold問題集［1Z0-816］対応
　初版第一刷
　著者：志賀 澄人
　発行所：株式会社インプレス
　引用頁：550

![イメージ説明](https://ddjkaamml8q8x.cloudfront.net/questions/2024-05-26/bda79ca3-2f19-40f5-a2df-a6b70cdac484.jpeg)

```java
public class Main {
    public static void main(String[] args) {
        Test t1 = new Test();
        Test t2 = new Test();

Sample s1 = new Sample();
        Sample s2 = new Sample();

new Thread(() -> {
            t1.execute(s1, s2);
        }).start();

new Thread(() -> {
            t2.execute(s1, s2);
        }).start();
    }
}

class Test {
    public synchronized void execute(Sample... samples) {
        for (int i = 0; i < 10; i++) {
            while (!samples[0].hello(this)) {
            }
            while (!samples[1].hello(this)) {
            }
            samples[1].bye();
            samples[0].bye();
        }
    }
}

class Sample {
    public Test test;

public synchronized boolean hello(Test test) {
        if (this.test == null) {
            this.test = test;
            return true;
        }
        return false;
    }

public synchronized void bye() {
        this.test = null;
    }
}
```

引用頁：595

解答

一方のスレッドが1つ目のインスタンスを使っているとき、もう一方のスレッドが2つ目のインスタンスを使っており、それぞれがもう１つのインスタンスを使おうとしたときに、synchronizedによってデッドロックが発生してしまう可能性があります。

Accepted Answer

# 05/30 01:15追記
解決済みになっていますが、本当に正しいのかちょっと疑わしいので情報をまとめておきます。

長々と書いてしまいましたが質問者さんや同様の疑問を抱いてこの質問に辿り着いた方の一助になれば…ということで。

## 勝手な用語の定義

* 広義のデッドロック
  複数の共有リソースを用いた処理において、複数のスレッド/プロセスが互いにリソースの解放待ちでそれ以上処理を進められなくなる状態
* 狭義のデッドロック
  広義のデッドロックのうち、言語特有のロック機能を用いているもの(Javaのsynchronized等)

※この記事のために私が勝手に導入した用語です

## 「徹底攻略Java SE 11 Gold問題集」の修正内容

以降、「徹底攻略Java SE 11 Gold問題集」のことを単に「書籍」と呼びます。

* 誤植修正前 (2021年9月21日 初版)
   * コード
     `t1.execute(s1, s2);`
     `t2.execute(s1, s2);`
   * 書籍の回答
     『デッドロックの可能性がある』
* 誤植修正後 (2023年11月1日 第1版第5刷)
   * コード
     `t1.execute(s1, s2);`
     `t2.execute(s2, s1);`
   * 書籍の回答
     『デッドロックの可能性がある』

※誤植修正前のコードでは、実際にはデッドロックは発生しない

(質問者さんの引用＆ikedasさんの書き込みより)

## 私の考える正しい解釈

一般的にデッドロックと言えば、広義のデッドロックを指すと私は考えています。

書籍でも同じく広義のデッドロックの意図で問題を作成したところ
誤植修正前にはコードの一部に誤りがあり、誤植修正後はコードと回答が一致するようになった…と考えています。

現時点でベストアンサーになっているjimbeさんの回答は、『狭義のデッドロックが起こらない』という趣旨なのか、
あくまで書籍の誤植修正前のコードについて論じているだけなのか判断が付きませんでした。

ただ、質問者さんは狭義のデッドロックについてだと解釈されているように思われます。
質問者さんが私の回答へのコメントで「デッドロックではなく、ただの無限ループ」と発言されていますが
実際は「狭義のデッドロックではないが、無限ループによる広義のデッドロック」という解釈が正しいと私は考えています。

## 一般的な定義ではなく、Java Gold試験におけるデッドロックの定義について
仮にJava Gold試験でのデッドロックの定義が狭義のデッドロックのことであるなら（例えばoracleの試験要綱等に記載があれば）
少なくとも試験においては一般的な（と私が考えている）定義ではなく、そちらに合わせて回答すべきです……が
そうすると書籍の方が誤った定義の出題をしていることになってしまいます。

試験のための知識だとしても、出題側がどういう意図なのか試験要綱や試験のための参考書の記述を確認してみてほしいです。

## コードの書き方の問題
今回のコードはあまり普通の書き方をされていないので、それも混乱の原因になったとは思います。
解放待ちにウェイトも付けず何も処理を入れないならば素直に`synchronized`で待てばよくて、空の無限ループは用いるべきではありません。
また質問者さんが引用されているコードが一字一句そのままであるなら、実用コードであれば存在するはずの共有リソースを用いた処理について何も（省略の旨のコメントすら）書かれておらず
実際にコードを走らせて検証してもおそらくタイミング問題でデッドロックが再現しにくいのではないかと思われます。

資格試験で理解度を問うためにわざと分かりにくいコードの書き方をしているのかな？くらいの解釈だったので特に言及しませでしたが……
実際のデッドロックを論じる検証コードであれば、普通は実処理を模したsleepを入れたり、確認のための標準出力処理を入れたりします。
デッドロックの再現はタイミング問題なので「何度実行してみても再現しない」というのもよくあり、そこでこのsleepを増減させたり標準出力をなくしたりと色々工夫して検証することになります。

そういう事情もあるので、たまたま実行した時にデッドロックが発生しないから「コードに問題がない」と短絡的に考えるのではなく、「デッドロックが発生しうる構造かどうか」を考える力が必要となります。
今回の誤植修正後のようなコードを対象にする場合などは、狭義のデッドロックか否かを論じても実用的にはとくに意味がないと考えています。
（「デッドロックは発生しないがリソースの取り合いで処理が終了しない構造なので修正しなければならない」みたいな意味の分からない会話が生まれてしまいます）

## 件のコードでの広義のデッドロック発生について

誤植修正前の説明は05/26時点で書いたので
誤植修正後のコードについて

`t1.execute(s1, s2);`
`t2.execute(s2, s1);`
の場合の実行イメージについて
以下のようなタイミングで実行されると広義のデッドロックが再現できます。

1. 初期状態 `s1.test == null` かつ `s2.test == null`
1. 2スレッドで(ほぼ)同時に最初の while 文を実行
   1. t1 のスレッドでループ判定の `!samples[0].hello(this)` を実行
      つまり s1.hello(t1) がtrueを返し、whileループ終了
   1. t2 のスレッドでループ判定の `!samples[0].hello(this)` を実行
      つまり s2.hello(t2) がtrueを返し、whileループ終了
   ※この時点で何も競合していない
1. 状態 `s1.test == t1` かつ `s2.test == t2`
1. 2スレッドでほぼ同時に次の while 文を実行
   1. t1 のスレッドでループ判定の `!samples[1].hello(this)` を実行
      つまり s2.hello(t1) がfalseを返し、whileループ継続 (無限に終わらない)
   1. t2 のスレッドでループ判定の `!samples[1].hello(this)` を実行
      つまり s2.hello(t2) がfalseを返し、whileループ継続 (無限に終わらない)
   ※メソッド呼び出しのsynchronizedで止まるわけではないが、t1,t2いずれもs1,s2という2つのリソースを占有できずに永遠に処理が進まない

## おまけ1

件のコードでのsynchronizedについて一応解説します

### Test.executeのsynchronized
Test.execute についてるsynchronizedは、実際のところ別インスタンスなので意味はありません。
ミスリードのために付けたのかもしれません。

### Sample.hello および Sample.bye のsynchronized
`s1.hello(t1)` と `s1.hello(t2)` など同時実行されることはありますが、既に論じられている通りこれらが直接デッドロックの原因になるわけではありません。
ならば意味がないかというとそんなことはなく、アトミック性や可視性を担保するために必須となります。

#### アトミック性
これがないと例えば、
t1スレッドで`this.test == null`がtrue判定されてから`this.test = test;`が実行される間に、t2スレッドでも`this.test == null`をtrue判定し、
`s1.test == t1` となった直後に `s1.test == t2` と上書き処理され、2スレッドで同時に s1.hello がtrueを返すような不整合状態が起こりえます。

#### 可視性
これがないと、それぞれのスレッドが最新のデータを見ない可能性があります。

例えば
t1スレッドで `s1.hello(t1)` を実行した結果 `s1.test == t1` の状態になったが
t2スレッドが最新のデータを読まずにローカルキャッシュの `s1.test == null` をそのまま用いて `s1.hello(t2)` を実行すると不整合状態になりえます。

## おまけ2

melianさんが挙げられている記事について
https://qiita.com/hanohrs/items/d0d3a5288db10b69d2a4#13-%E7%AB%A0-%E5%95%8F%E9%A1%8C-33

> 1. スレッド1が s1.hello() を実行し、s1.test が非 null になる
> 2. スレッド2がスレッド1が書き換えた s1.test を参照し、非 null なので、while ループを抜けられない
> 3. スレッド1が s1.bye() を実行し、スレッド1では s1.test が null に戻る
> 4. スレッド2が、s1.test が volatile でないのでスレッド1が更新した値を読むことができず、非 null の値を読み続けて while ループを抜けられない

t1：s1.hello を実行
t2：s2.hello を実行せず s1.hello を実行している (s2.hello を先に実行しているなら 広義のデッドロックで 3.の t1：s1.bye に辿り着けない)

…ということで、これは誤植修正前のコードについて論じていると思われ、
誤った前提（誤植修正前のコードでデッドロックの可能性がある）を元に誤った結論を導き出してしまっています。

ちなみに非デーモンスレッドの終了条件やsynchronized内の可視性あたりの勘違いがあるっぽいので
正直ちゃんと仕様を理解したうえでの推察とかではなく、たんなる想像を書いているのでは？…という気がするのであまり鵜呑みにしない方がよさげです。

スレッド終了…… 書籍のコードだとタイミング問題で先に "end" が出力されてからスレッド処理が継続する場合も普通にある。そもそも誤植修正前の場合絶対にデッドロックが起こらないので単に "end"出力→スレッド2つの処理が正常に終了…となったのを『スレッドの終了を待たずに正常終了してしまう』と勘違いしたのかも。

synchronized内の可視性…… synchronizedは入る時と出る時にローカルキャッシュを捨てて可視性を担保するので、『スレッド2が、s1.test が volatile でないのでスレッド1が更新した値を読むことができず』はあり得ない。

# 以下05/26時点の書き込み
現状のコードではデッドロックは発生しません。

Test.execute はこのコード内ではスレッド2つがそれぞれ１つずつ別のTestインスタンスを占有する形になっているので特に競合は発生しません。
現状に限れば synchronized が付いていても付いていなくても同じ挙動になります。

残りの問題 Sample の各メソッドについてですが
executeに含まれるforループ内からの呼び出しを、次のようなモデルで説明できます。
* 2つのスレッド t1,t2 がそれぞれリソース s1,s2 を取り合う
* 各スレッドは s1->s2 の順にリソースを占有し、両方を占有できたら s2->s1 の順で解放する
* 片方のスレッドがリソースを占有したら、もう片方は解放を待たねばならない
…なんですが、実はこれはもっとシンプルなモデルで説明ができてしまいます。
* 2つのスレッド t1,t2 がリソース s1 を取り合う
* 先に s1 を占有した方が、s2占有 -> s2解放 -> s1解放 を行う
* 片方のスレッドがリソースs1を占有したら、もう片方は解放を待つ

つまり2つのリソースを扱っていますが、実はスレッドのブロックに関わるのは実質1つのリソースだけであり
デッドロック発生の原因である「2つ以上のリソースが必要な処理で、別々のスレッドがそれぞれ別のリソースを占有したままお互いの解放を待つ」という状況が発生し得ません。

----
わざとデッドロックを起こしたければ、ループ状の配置となるように
```java
        new Thread(() -> {
            t1.execute(s1, s2);
        }).start();

new Thread(() -> {
            t2.execute(s2, s1); //引数の順番入れ替え
        }).start();
```
などと変更するとよいです

Answer

メソッドに付いている synchronized はそのメソッドを実行する時に this のロックを獲得しようとし、ロックが取れなかったら取れるまで待機し、取れ次第メソッドを実行して、メソッドの終了と共に解放すると理解しています。

Sample の hello() も bye() もメソッド内では何のロックも取りに行きませんので、たとえ t1 と t2 が同時に同じ Sample オブジェクトの hello() もしくは byte() を呼ぶことになったとしても、先にその Sample オブジェクトのロックを獲得したほうがメソッドを実行して解放し、続いてもう一方が獲得して…となるだけで、デッドロックになりようが無さそうに見えます。

質問へのコメントで melian さんが紹介されている Qiita の記事でも最後に書かれていますが、コードの不備(?)的に while が終わらないということはあるかもしれませんが、デッドロックが原因で処理が進まないという状況が見えません。

※ Qiita の記事を紹介頂いていたのは melian さんでした。失礼しました、すみません。

Answer

結論から言うとこのコードではデッドロックは発生しません。

Test の execute メソッドが synchronized であるため、t1 と t2 の execute メソッドは同時に実行されることはありません。
Sample の hello メソッドも synchronized であるため、同じ Sample インスタンスに対して同時に hello メソッドが実行されることはありません。

つまり、hello メソッドが true を返すためには this.test が null でなければならず、これは他のスレッドがその Sample インスタンスの bye メソッドを呼び出すまで待つ必要があることを意味します。
しかし、Test クラスの execute メソッドが同時に実行されないため、hello メソッドが永遠に true を返さないという状況は発生しません。

したがって、このコードではデッドロックは発生しません。

05/30 01:15追記

勝手な用語の定義

「徹底攻略Java SE 11 Gold問題集」の修正内容

私の考える正しい解釈

一般的な定義ではなく、Java Gold試験におけるデッドロックの定義について

コードの書き方の問題

件のコードでの広義のデッドロック発生について

おまけ1

Test.executeのsynchronized

Sample.hello および Sample.bye のsynchronized

アトミック性

可視性

おまけ2

以下05/26時点の書き込み

関連した質問