マルチスレッドのプログラミング

質問

以下に示された関数transferは、与えられた2つのスタックstack1とstack2に対し、stack1から要素と取り出してstack2に入れる操作を目的として実装したものである。複数のスレッドがこの関数を呼ぶ可能性がある場合にはこの関数が目的通りに機能しない場合がある。

(1)機能しない場合の例を挙げよ。

(2)この関数を目的通りに機能させるための修正案を2つ示せ。

(3)前問で挙げた修正案のうち、どちらが並列性を高める上では優位であるかを論ぜよ。

void transfer(Stack stack1, Stack stak2)

{

if(stack1 == stack2) return;

stack1.mutex_lock();

Item item =stack1.pop();

if(item !=null)

{

stack2.mutex_lock();

stack2.push(item;)

stack2.mutex_unlock()

}

stack1.mutex_unlock()

}

http://docs.oracle.com/cd/E19683-01/816-3976/sync-45513/index.html

↑ここらへんを参考にしているのですが、答えを導けません。

ご教示お願い致します。

回答No.2

OrangeCup150 · ベストアンサー

大体 hirotn (#1)さんの回答であっていますが間違いがあります。

(1)
#1 さんの通りtransfer関数は引数のオブジェクトをロックする仕様であるため、２つのオブジェクトをロックするときの順序を拘束できないため、デッドロックとなる危険性があります。

(2)
#1 さんの(2)-Aは誤りです。デッドロックの回避方法は同時に取得することではなく、複数のオブジェクトをロックするときの順序を拘束することです。または、複数のオブジェクトのロックを単一のオブジェクトのロックに変更することが可能であればそうします。これは #1 さんの(2)-Bの解法にあたります。
別の解法は処理のロックをすることです。

Ａ．処理のロック
void transfer(Stack stack1, Stack stack2) // 原文にtypo有り
{
// データをロックするのではなく処理をロックする
transfer.mutex_lock();
// 中略
transfer.mutex_unlock();
}

つまり、transfer関数を実行するのは常に１つのスレッドに制限します。
（マルチスレッド処理の設計ミスの泥縄的解決方法です。また、Win16からWin32への移行と互換性でも似たようなこと（Win16 Mutexのこと）をしています。）

Ｂ．単一オブジェクトのロックへの変更
#1 の(2)-Bの通り

補足　複数のオブジェクトをロックする場合、ローカル変数は使用しません。（前述の通りロックの順序を拘束することができないため）グローバル変数を使用します。（グローバル変数一覧表を作成してロック順序を設計書にまとめます）ローカル変数が使用できるのは、単一オブジェクトのロックで処理ができるときだけです。

(3)
Ａ．処理のロックとＢ．単一オブジェクトのロックへの変更では、スレッド数と対象オブジェクト数が増えたときに処理能力に顕著な差が現れます。
Ａの方法ではtransfer関数の実行が常に１つのスレッドに制限されるためスレッド数と対象オブジェクト数が増えると必然的にパフォーマンスの劣化が現れます。
Ｂの方法ではtransfer関数の実行は複数のスレッドで可能であり同時実行の制限はロックするオブジェクトに依存するのでパフォーマンスの劣化は抑えられます。

Thread-A transfer(stack-A, stack-B)
Thread-B transfer(stack-B, stack-A)
Thread-C transfer(stack-C, stack-D)
Thread-D transfer(stack-D, stack-C)

上記の条件でＡの方法では Thread-A, B, C, D の内transfer関数は常に１つのスレッドの実行に限定されます。Ｂの方法では Thread-A, B と Thread-C, D の組で同時実行ができます。

お礼

大変丁寧な説明ありがとうございます！とてもよくわかりました。

回答No.1

hirotn

void transfer(Stack stack1, Stack stak2)

{

if(stack1 == stack2) return; 　★

stack1.mutex_lock();

Item item =stack1.pop();

if(item !=null)

{

stack2.mutex_lock();　☆

stack2.push(item;)

stack2.mutex_unlock()

}

stack1.mutex_unlock()

}

(1)スレッド１が、★～☆間を実行している間に、以下の呼び出しを実行するとデッドロックが発生する。
スレッド1 transfer(stack1, stack2)
スレッド2 transfer(stack2, stack1)

スレッド1 transfer(stack1, stack2)
stack1を専有
stack1をpop

stack2の専有解除待ち

スレッド2 transfer(stack2, stack1)
stack2を専有
stack2をpop
stack1の専有解除待ち　★デッドロック成立します。

(2)-A専有を同時に取得します

void transfer(Stack stack1, Stack stak2)

{
if(stack1 == stack2) return;
stack1.mutex_lock()
stack2.mutex_lock()
Item item =stack1.pop();
if(item !=null)
{
stack2.push(item;)
}
stack2.mutex_unlock()
stack1.mutex_unlock()
}

(2)-B専有開放を見直します
void transfer(Stack stack1, Stack stak2)

{
if(stack1 == stack2) return;
stack1.mutex_lock()
Item item =stack1.pop();
stack1.mutex_unlock()
if(item !=null)
{
stack2.mutex_lock()
stack2.push(item;)
stack2.mutex_unlock()
}
}

(3) (2)-Bの例では stack1.popとstack2.pushの処理をスレッド間では並列実行できるため。

お礼

ご丁寧にありがとうございます！