本節では、スワップ(swap)と呼ばれる値の交換によってデッドロックの理解を進めていきます。先の節では int型の配列を扱いましたが、今回は Point型の配列を扱います。
例えば、Point型配列 pointsの points[2]と points[5]の内容を入れ替えようとすると、以下のようなソースコードになります。
int tempX = points[2].x; int tempY = points[2].y; points[2].x = points[5].x; points[2].y = points[5].y; points[5].x = tempX; points[5].y = tempY;
このように、変数 tempX, tempYを使用することによって、値を変更することができます。
なお、今回扱うプログラムでは、Point型インスタンスの yのほうはランダム値としますが、xのほうは重複しない値(1~10)とします。
シングルスレッドで値の交換をするプログラムを挙げます。キーボードから指定した回数だけ、値の交換を実施します。その後、値を表示し、データの破損がないかどうかをチェックします。
ソースコードは以下の通り。
Q401/MySystem.java
(ライブラリをそのまま利用します)
Q401/Q401.java
import java.awt.Point; /** * Point型インスタンスの交換を行います。 */ public class Q401 { /** * 交換回数。 */ private int swapCount; /** * ポイント群。 */ private Point[] points = new Point[10]; /** * メインメソッド。 * @param args 引数 */ public static void main(String[] args) { Q401 q401 = new Q401(); q401.execute(); } /** * 実行します。 */ public void execute() { System.out.println("現在のスレッドは" + Thread.currentThread().getName() + "です。"); // 初期値の設定 for(int i = 0; i < this.points.length; i ++) { this.points[i] = new Point(i + 1, (int)(Math.random() * 10)); } this.printPoints("交換前"); this.swapCount = MySystem.in.getInt("スレッドごとの交換回数は"); this.swapPoints(this.swapCount); this.printPoints(this.swapCount + "回交換後"); this.checkPoints(); } /** * ポイント群を表示します。 * @param message メッセージ */ private void printPoints(String message) { System.out.print(message + ": "); for(int i = 0; i < this.points.length; i ++) { System.out.print("(" + this.points[i].x + "," + this.points[i].y + ")"); if(i != this.points.length - 1) { System.out.print(","); } } System.out.println(); } /** * 指定された回数、ポイント型インスタンスを交換します。 * @param times 回数 */ private void swapPoints(int times) { for(int i = 0; i < times; i ++) { this.swap(); } } /** * 交換します。 */ private void swap() { int value1 = (int)(Math.random() * this.points.length); int value2 = (int)(Math.random() * this.points.length); int tempX = this.points[value1].x; int tempY = this.points[value1].y; this.points[value1].x = this.points[value2].x; this.points[value1].y = this.points[value2].y; this.points[value2].x = tempX; this.points[value2].y = tempY; } /** * ポイント群の値をチェックします。 */ private void checkPoints() { boolean isAllOK = true; for(int j = 0; j < this.points.length; j ++) { boolean isOK = false; for(int i = 0; i < this.points.length; i ++) { if(this.points[i].x == j + 1) { isOK = true; } } if(! isOK) { System.out.println((j + 1) + "が見つかりません。"); isAllOK = false; } } if(isAllOK) { System.out.println("異常はありませんでした。"); } } }
100万回を指定したときの実行結果の例は以下の通り。
現在のスレッドはmainです。 交換前: (1,3),(2,3),(3,5),(4,0),(5,3),(6,5),(7,2),(8,9),(9,6),(10,5) スレッドごとの交換回数は? 1000000 1000000回交換後: (4,0),(9,6),(7,2),(6,5),(8,9),(10,5),(2,3),(5,3),(1,3),(3,5) 異常はありませんでした。
値の交換が上手くできていることが分かります。
続いて、マルチスレッド化します。スワップの部分にはマルチスレッド対策を含めていませんので、バグが発生します。
ソースコードは以下の通り。
Q402/MySystem.java
(ライブラリをそのまま利用します)
Q402/Q402.java
import java.awt.Point; /** * Point型インスタンスの交換をマルチスレッドで行います。失敗例。 */ public class Q402 implements Runnable { /** * 交換回数。 */ private int swapCount; /** * ポイント群。 */ private Point[] points = new Point[10]; /** * メインメソッド。 * @param args 引数 */ public static void main(String[] args) { Q402 q401 = new Q402(); q401.execute(); } /** * 実行します。 */ public void execute() { System.out.println("現在のスレッドは" + Thread.currentThread().getName() + "です。"); // 初期値の設定 for(int i = 0; i < this.points.length; i ++) { this.points[i] = new Point(i + 1, (int)(Math.random() * 10)); } this.printPoints("交換前"); this.swapCount = MySystem.in.getInt("スレッドごとの交換回数は"); // 別スレッドを起動します。 Thread thread = new Thread(this); thread.start(); this.swapPoints(this.swapCount); try { Thread.sleep(2000); } catch (InterruptedException e) { ; // 何もしない } this.printPoints(this.swapCount + "回交換後"); this.checkPoints(); } @Override public void run() { System.out.println("現在のスレッドは" + Thread.currentThread().getName() + "です。"); this.swapPoints(this.swapCount); System.out.println(Thread.currentThread().getName() + "は終了。"); } /** * ポイント群を表示します。 * @param message メッセージ */ private void printPoints(String message) { System.out.print(message + ": "); for(int i = 0; i < this.points.length; i ++) { System.out.print("(" + this.points[i].x + "," + this.points[i].y + ")"); if(i != this.points.length - 1) { System.out.print(","); } } System.out.println(); } /** * 指定された回数、ポイント型インスタンスを交換します。 * @param times 回数 */ private void swapPoints(int times) { for(int i = 0; i < times; i ++) { this.swap(); } } /** * 交換します。 */ private void swap() { int value1 = (int)(Math.random() * this.points.length); int value2 = (int)(Math.random() * this.points.length); int tempX = this.points[value1].x; int tempY = this.points[value1].y; this.points[value1].x = this.points[value2].x; this.points[value1].y = this.points[value2].y; this.points[value2].x = tempX; this.points[value2].y = tempY; } /** * ポイント群の値をチェックします。 */ private void checkPoints() { boolean isAllOK = true; for(int j = 0; j < this.points.length; j ++) { boolean isOK = false; for(int i = 0; i < this.points.length; i ++) { if(this.points[i].x == j + 1) { isOK = true; } } if(! isOK) { System.out.println((j + 1) + "が見つかりません。"); isAllOK = false; } } if(isAllOK) { System.out.println("異常はありませんでした。"); } } }
100万回を指定したときの実行結果の例は以下の通り。
現在のスレッドはmainです。 交換前: (1,3),(2,3),(3,5),(4,7),(5,9),(6,6),(7,1),(8,9),(9,8),(10,6) スレッドごとの交換回数は? 1000000 現在のスレッドはThread-0です。 Thread-0は終了。 1000000回交換後: (6,3),(6,3),(6,3),(6,3),(6,3),(6,3),(6,3),(6,3),(6,3),(6,3) 1が見つかりません。 2が見つかりません。 3が見つかりません。 4が見つかりません。 5が見つかりません。 7が見つかりません。 8が見つかりません。 9が見つかりません。 10が見つかりません。
データが破損していることが分かります。
スワップはやはり同期をとらなければならない、と言うことで、swapメソッドを synchronizedなインスタンスメソッドに変更します。自分自身(this)をロック対象にして同期をとります。
ソースコードは以下の通り。
Q403/MySystem.java
(ライブラリをそのまま利用します)
Q403/Q403.java
import java.awt.Point; /** * Point型インスタンスの交換をマルチスレッドで行います。成功例。 */ public class Q403 implements Runnable { /** * 交換回数。 */ private int swapCount; /** * ポイント群。 */ private Point[] points = new Point[10]; /** * メインメソッド。 * @param args 引数 */ public static void main(String[] args) { Q403 q401 = new Q403(); q401.execute(); } /** * 実行します。 */ public void execute() { System.out.println("現在のスレッドは" + Thread.currentThread().getName() + "です。"); // 初期値の設定 for(int i = 0; i < this.points.length; i ++) { this.points[i] = new Point(i + 1, (int)(Math.random() * 10)); } this.printPoints("交換前"); this.swapCount = MySystem.in.getInt("スレッドごとの交換回数は"); // 別スレッドを起動します。 Thread thread = new Thread(this); thread.start(); this.swapPoints(this.swapCount); try { Thread.sleep(2000); } catch (InterruptedException e) { ; // 何もしない } this.printPoints(this.swapCount + "回交換後"); this.checkPoints(); } @Override public void run() { System.out.println("現在のスレッドは" + Thread.currentThread().getName() + "です。"); this.swapPoints(this.swapCount); System.out.println(Thread.currentThread().getName() + "は終了。"); } /** * ポイント群を表示します。 * @param message メッセージ */ private void printPoints(String message) { System.out.print(message + ": "); for(int i = 0; i < this.points.length; i ++) { System.out.print("(" + this.points[i].x + "," + this.points[i].y + ")"); if(i != this.points.length - 1) { System.out.print(","); } } System.out.println(); } /** * 指定された回数、ポイント型インスタンスを交換します。 * @param times 回数 */ private void swapPoints(int times) { for(int i = 0; i < times; i ++) { this.swap(); } } /** * 交換します。 */ private synchronized void swap() { int value1 = (int)(Math.random() * this.points.length); int value2 = (int)(Math.random() * this.points.length); int tempX = this.points[value1].x; int tempY = this.points[value1].y; this.points[value1].x = this.points[value2].x; this.points[value1].y = this.points[value2].y; this.points[value2].x = tempX; this.points[value2].y = tempY; } /** * ポイント群の値をチェックします。 */ private void checkPoints() { boolean isAllOK = true; for(int j = 0; j < this.points.length; j ++) { boolean isOK = false; for(int i = 0; i < this.points.length; i ++) { if(this.points[i].x == j + 1) { isOK = true; } } if(! isOK) { System.out.println((j + 1) + "が見つかりません。"); isAllOK = false; } } if(isAllOK) { System.out.println("異常はありませんでした。"); } } }
100万回を指定したときの実行結果の例は以下の通り。
現在のスレッドはmainです。 交換前: (1,2),(2,2),(3,8),(4,5),(5,9),(6,0),(7,8),(8,5),(9,7),(10,7) スレッドごとの交換回数は? 1000000 現在のスレッドはThread-0です。 Thread-0は終了。 1000000回交換後: (8,5),(5,9),(6,0),(2,2),(1,2),(4,5),(7,8),(9,7),(3,8),(10,7) 異常はありませんでした。
例えば、メインスレッドが point[5]と point[4]の内容を交換しようとし、もう一方のスレッドが points[0]と points[1]の内容を交換しようとしているときには同期をとる必要はありません。処理の対象が異なるのだから、バグは発生しないはずです。Q403プロジェクトでは、メソッドに synchronized修飾子を使用しており、ロック対象は自分自身(this)だったため、このように同期をとる必要がない場合にも同期をとってしまっています。
このようなことは、例えばネットワークを介するなど処理時間がかかる場合にはもったいないことなります。そこで、Q404プロジェクトでは、メソッドの内部に 2つの synchronizedブロックを用いて、ロック対象を自分自身(this)ではなく、交換対象とする Point型インスタンスを指定することで、極力同期をとらないようにしてみます。
synchronizedブロックを 2つ使用して、プログラムを製作します。
ソースコードは以下の通り。
Q404/MySystem.java
(ライブラリをそのまま利用します)
Q404/Q404.java
import java.awt.Point; /** * Point型インスタンスの交換をマルチスレッドで行います。デッドロック発生例。 */ public class Q404 implements Runnable { /** * 交換回数。 */ private int swapCount; /** * ポイント群。 */ private Point[] points = new Point[10]; /** * メインメソッド。 * @param args 引数 */ public static void main(String[] args) { Q404 q401 = new Q404(); q401.execute(); } /** * 実行します。 */ public void execute() { System.out.println("現在のスレッドは" + Thread.currentThread().getName() + "です。"); // 初期値の設定 for(int i = 0; i < this.points.length; i ++) { this.points[i] = new Point(i + 1, (int)(Math.random() * 10)); } this.printPoints("交換前"); this.swapCount = MySystem.in.getInt("スレッドごとの交換回数は"); // 別スレッドを起動します。 Thread thread = new Thread(this); thread.start(); this.swapPoints(this.swapCount); try { Thread.sleep(2000); } catch (InterruptedException e) { ; // 何もしない } this.printPoints(this.swapCount + "回交換後"); this.checkPoints(); } @Override public void run() { System.out.println("現在のスレッドは" + Thread.currentThread().getName() + "です。"); this.swapPoints(this.swapCount); System.out.println(Thread.currentThread().getName() + "は終了。"); } /** * ポイント群を表示します。 * @param message メッセージ */ private void printPoints(String message) { System.out.print(message + ": "); for(int i = 0; i < this.points.length; i ++) { System.out.print("(" + this.points[i].x + "," + this.points[i].y + ")"); if(i != this.points.length - 1) { System.out.print(","); } } System.out.println(); } /** * 指定された回数、ポイント型インスタンスを交換します。 * @param times 回数 */ private void swapPoints(int times) { for(int i = 0; i < times; i ++) { this.swap(); } } /** * 交換します。 */ private void swap() { int value1 = (int)(Math.random() * this.points.length); int value2 = (int)(Math.random() * this.points.length); synchronized(this.points[value1]) { synchronized(this.points[value2]) { int tempX = this.points[value1].x; int tempY = this.points[value1].y; this.points[value1].x = this.points[value2].x; this.points[value1].y = this.points[value2].y; this.points[value2].x = tempX; this.points[value2].y = tempY; } } } /** * ポイント群の値をチェックします。 */ private void checkPoints() { boolean isAllOK = true; for(int j = 0; j < this.points.length; j ++) { boolean isOK = false; for(int i = 0; i < this.points.length; i ++) { if(this.points[i].x == j + 1) { isOK = true; } } if(! isOK) { System.out.println((j + 1) + "が見つかりません。"); isAllOK = false; } } if(isAllOK) { System.out.println("異常はありませんでした。"); } } }
1000回を指定したときの実行結果の例は以下の通り。
現在のスレッドはmainです。 交換前: (1,0),(2,4),(3,5),(4,0),(5,9),(6,9),(7,6),(8,0),(9,0),(10,0) スレッドごとの交換回数は? 1000 現在のスレッドはThread-0です。 Thread-0は終了。 1000回交換後: (10,0),(1,0),(9,0),(4,0),(6,9),(5,9),(7,6),(2,4),(3,5),(8,0) 異常はありませんでした。
上手く交換できているように見えます。そこで大きな値を指定してみることにします。
100万回を指定したときの実行結果の例は以下の通り。
現在のスレッドはmainです。 交換前: (1,7),(2,1),(3,8),(4,1),(5,1),(6,4),(7,1),(8,6),(9,6),(10,7) スレッドごとの交換回数は? 1000000 現在のスレッドはThread-0です。
プログラムはいつまで経っても終了しません。デッドロックが発生したのです。
今回は 2つの synchronizedブロックを使用しています。たとえば points[3]と points[5]を交換することになったとき、以下のような処理が行われます。
ところで、もし、メインスレッドが points[3]と point[5]を交換しようとし、別スレッドが points[5]と points[3]を交換しようとし、それが偶然にもほぼ同じタイミングで発生したら、どうなるでしょうか。
そして、メインスレッドも別スレッドも、相手スレッドのロック解放を待つだけとなってしまい、プログラムは前に進まなくなってしまいます。このような状態をデッドロックと呼びます。
今回の例において、僕の環境では 1000回を指定した場合には、ほとんどデッドロックが発生しませんでした。逆に言えば、デッドロックの発生頻度は「1000回に 1回未満」ということでもあります。ということは、実際にデッドロックが発生しても、再現することは極めて困難ということになります。という訳で、デバッグ作業が極めて困難になります。
今回の例では、メインスレッドと別スレッドにおいて、何も考えずにロックをしようとしていたことが原因となっていました。メインスレッドが points[3]→points[5]の順番でロックし、別スレッドも points[3]→points[5]の順番でロックをしようとしたならば、デッドロックは発生しません。別スレッドが points[5]→points[3]の順番でロックをしようとしたからデッドロックが発生してしまったのです。
次の Q405プロジェクトでは、ロックをする順番に注意することでデッドロックを回避してみます。
先に書いたようにインスタンスをロックする順番が大切です。今回は、ロックするオブジェクトを配列の添え字の小さいほうから順番にロックすることとします。これによって、今回のプログラムではデッドロックの問題を回避することができます。
ソースコードは以下の通り。
Q405/MySystem.java
(ライブラリをそのまま利用します)
Q405/Q405.java
import java.awt.Point; /** * Point型インスタンスの交換をマルチスレッドで行います。成功例。 */ public class Q405 implements Runnable { /** * 交換回数。 */ private int swapCount; /** * ポイント群。 */ private Point[] points = new Point[10]; /** * メインメソッド。 * @param args 引数 */ public static void main(String[] args) { Q405 q401 = new Q405(); q401.execute(); } /** * 実行します。 */ public void execute() { System.out.println("現在のスレッドは" + Thread.currentThread().getName() + "です。"); // 初期値の設定 for(int i = 0; i < this.points.length; i ++) { this.points[i] = new Point(i + 1, (int)(Math.random() * 10)); } this.printPoints("交換前"); this.swapCount = MySystem.in.getInt("スレッドごとの交換回数は"); // 別スレッドを起動します。 Thread thread = new Thread(this); thread.start(); this.swapPoints(this.swapCount); try { Thread.sleep(2000); } catch (InterruptedException e) { ; // 何もしない } this.printPoints(this.swapCount + "回交換後"); this.checkPoints(); } @Override public void run() { System.out.println("現在のスレッドは" + Thread.currentThread().getName() + "です。"); this.swapPoints(this.swapCount); System.out.println(Thread.currentThread().getName() + "は終了。"); } /** * ポイント群を表示します。 * @param message メッセージ */ private void printPoints(String message) { System.out.print(message + ": "); for(int i = 0; i < this.points.length; i ++) { System.out.print("(" + this.points[i].x + "," + this.points[i].y + ")"); if(i != this.points.length - 1) { System.out.print(","); } } System.out.println(); } /** * 指定された回数、ポイント型インスタンスを交換します。 * @param times 回数 */ private void swapPoints(int times) { for(int i = 0; i < times; i ++) { this.swap(); } } /** * 交換します。 */ private void swap() { int value1 = (int)(Math.random() * this.points.length); int value2 = (int)(Math.random() * this.points.length); if(value1 != value2) { int min = Math.min(value1, value2); int max = Math.max(value1, value2); // 小さいほうからロックする synchronized(this.points[min]) { synchronized(this.points[max]) { int tempX = this.points[value1].x; int tempY = this.points[value1].y; this.points[value1].x = this.points[value2].x; this.points[value1].y = this.points[value2].y; this.points[value2].x = tempX; this.points[value2].y = tempY; } } } } /** * ポイント群の値をチェックします。 */ private void checkPoints() { boolean isAllOK = true; for(int j = 0; j < this.points.length; j ++) { boolean isOK = false; for(int i = 0; i < this.points.length; i ++) { if(this.points[i].x == j + 1) { isOK = true; } } if(! isOK) { System.out.println((j + 1) + "が見つかりません。"); isAllOK = false; } } if(isAllOK) { System.out.println("異常はありませんでした。"); } } }
100万回を指定したときの実行結果の例は以下の通り。
現在のスレッドはmainです。 交換前: (1,5),(2,8),(3,4),(4,4),(5,9),(6,7),(7,1),(8,9),(9,8),(10,1) スレッドごとの交換回数は? 1000000 現在のスレッドはThread-0です。 Thread-0は終了。 1000000回交換後: (6,7),(7,1),(5,9),(8,9),(2,8),(10,1),(9,8),(4,4),(1,5),(3,4) 異常はありませんでした。
上手く値交換ができたことが分かります。
端的に表現するならば、以下のような感じになります。