005 - デッドロック検出

並行処理環境におけるデッドロックとは， 複数のスレッドがお互いにいくつかの資源を使い終わるのを待っていて先に進めないという望ましくない状況を指す． あなたには， 与えられた命令列を複数のスレッドが並行に実行したときにデッドロックが発生する可能性があるか否かを判定するプログラムを作って欲しい．

命令列は '0' から '9' までの数字または 'u' からなる列で， それぞれの文字がひとつの命令を表している． 10 個のスレッドが同じひとつの命令列を実行しようとしており， 各スレッドは命令列の先頭から末尾まで順に命令を実行し， すべての命令を実行し終えると終了する．

数字の命令 k は L₀ から L₉ まで 10 個あるロックと呼ばれる共有資源のうち L_k を獲得する命令である． あるスレッドが L_k を獲得すると， 同じスレッドが 'u' 命令によってロックを解放するまでの間， そのロックはスレッドに保持される． 獲得したスレッド自身も含めすべてのスレッドは， 保持されている状態のロックを新たに獲得することはできない．

より厳密に記述すると，全てのスレッドが終了するまで，以下の処理が繰り返される．

1. まだ終了していないスレッドがひとつ任意に選ばれる．
2. 選ばれたスレッドの次のまだ実行していない命令を実行しようと試みる．
• 次の命令が数字 k であり， ロック L_k がどのスレッドにも保持されていないならば， そのスレッドは命令 k を実行し，ロック L_k を獲得する．
• 次の命令が数字 k であり， ロック L_k が既にどれかのスレッドに保持されていれば， 命令 k は実行されない．
• 次の命令が 'u' であるとき， 命令 'u' を実行し，そのスレッドが保持していたロックをすべて解放する．

このように実行を進めていくと， まだ終了していないスレッドの次に実行する命令が全て， 保持されているロックの獲得命令という状態に陥ることがある． こうなると，以降どのスレッドを選んでも命令が実行されることはない． この状態をデッドロックと呼ぶ．

命令列によっては，スレッドをどのような順番で選んで実行しても決してデッドロックに陥らない． このような命令列は安全であるという． そうでない場合，言い換えるとひとつ以上の実行順序でデッドロックに陥る場合， 命令列は危険であるという． あなたには， 与えられた命令列が安全であるか危険であるかを判定するプログラムを作って欲しい．

入力は 50 個以下のデータセットからなる． 各データセットは次の形式で表される．

n
s

n は命令列の長さ，s は命令列を表す文字列である． n は，正の整数であり，10,000 を超えない． s の各文字は '0' から '9' までの数字または 'u' であり，必ず 'u' で終わる．

入力の終わりは，ゼロだけからなる行で表される．

各データセットについて，与えられた命令列が安全ならば "SAFE"，危険ならば "UNSAFE" と 1 行に出力せよ．

11
01u12u0123u
6
01u10u
8
201u210u
9
01u12u20u
3
77u
12
9u8u845u954u
0

SAFE
UNSAFE
SAFE
UNSAFE
UNSAFE
UNSAFE

2 番目の入力 "01u10u" はデッドロックとなる可能性がある． ひとつのスレッドが最初の 4 命令 "01u1" を続けて実行した場合， このスレッドはロック L₁ を保持している． この状態で別のスレッドが最初の命令 '0' を実行すると，こちらのスレッドは L₀ を獲得する． こうなると，ひとつ目のスレッドは既にふたつ目のスレッドに保持されている L₀ を獲得しようとする． 一方，ふたつ目のスレッドはひとつ目のスレッドに保持されている L₁ を獲得しようとする．結果，デッドロックが発生する．

→ →
図1: Sample Input 2 "01u10u" が危険な理由．

一方で，3 番目の入力 "201u210u" は安全である． ひとつのスレッドが "201u21" を実行し，もう一方が "20" を実行するとデッドロックになると考えるかもしれないが， この状況は決して発生しない．なぜなら，ロック L₂ をふたつのスレッドが同時に保持することはないからである．