失われる更新とデッドロックを手で作る
目標
競合状態とデッドロックを文章で読む代わりに、自分で作り、自分でなくします。8つのステップを終えると、「ロックをかければよい」ではなく、どこまで囲むべきか、なぜ順序を統一する必要があるのか、どんなときはそもそも共有しないほうがよいのかを、手で確認することになります。
なぜ重要なのか
並行性のバグは、ほとんどの実行では何も起こしません。そのため、テストを通過して本番で爆発します。このラボのステップ2は、それを数値で見せます。同じプログラムを5回実行すると、5回とも違う値が出ます。
Pythonにはグローバルインタープリターロックがあるので、スレッドが本当に同時に実行されるわけではありません。それでも更新は消えます。競合状態の原因は並列実行ではなく、読んで書き換える区間が分かれているという事実だからです。インタープリターがその間でスレッドを切り替えさえすれば十分です。この点が、かえって概念を鮮明にしてくれます。
デッドロックも同じです。ステップ5とステップ6の間で変わるのは、ロックを取る順序だけです。ロックを増やすことも、待ち時間を延ばすこともしません。
ステップ
/root/conc/race.pyで更新が消えることを再現し、/root/conc/01-race.txtに残します。- 同じプログラムを5回実行し、
/root/conc/02-repeat.txtに回ごとの結果を残します。 /root/conc/lock.pyでロックをかけて損失をなくし、/root/conc/03-lock.txtに残します。/root/conc/local.pyでそもそも共有しない方法を作り、/root/conc/04-local.txtに残します。/root/conc/deadlock.py reverseでデッドロックを作り、/root/conc/05-deadlock.txtに残します。- 同じプログラムに
sameモードを加えてデッドロックをなくし、/root/conc/06-order.txtに残します。 - ステップ3とステップ4にかかった時間を集めて、
/root/conc/07-cost.txtに残します。 - 学んだことをまとめて、
/root/conc/08-notes.mdに残します。
参考
- 出力物はすべて
/root/conc/の下に置きます。先にmkdir -p /root/concを実行しておいてください。 - スレッド数は4、スレッド1つが増やす回数は50,000に合わせます。採点ツールがこの値を基準に見ます。
- 損失が見えないときは、
sys.setswitchinterval(0.000001)を入れてください。スレッドがより頻繁に切り替わり、もともとあった隙間が現れます。 - よくある間違い1:
counter += 1を1行で書くことです。隙間が狭く、損失が見えにくくなります。読み込みと書き込みを2つの文に分けてください。 - よくある間違い2: 2つ目のロックを時間制限なしで取ることです。プログラムが永遠に止まり、画面には何も出ません。
acquire(timeout=2)を使ってください。 - よくある間違い3: ステップ6でロックを1つにまとめてしまうことです。そうするとデッドロックは消えますが、学べることも消えます。ロックは2つのままにして、順序だけを変えます。
更新が消えることを再現する
/root/conc/race.pyを作ります。スレッド4つが同じグローバル変数をそれぞれ50,000回増やしますが、v = counterとcounter = v + 1の2つの文に分けて書きます。プログラムはexpected 200000とactual <실제값>の2行を出力する必要があり(プレースホルダーは実際の値です)、その出力を/root/conc/01-race.txtに残します。
増加1回が、読み込みと書き込みの2つの文に分かれていて初めて、その間に他のスレッドが割り込めます。counter += 1を1行で書くと、割り込める隙間が狭くなり、損失が見えにくくなります。
それでも損失が見えない場合は、sys.setswitchinterval(0.000001)でスレッドの切り替えを頻繁に起こしてください。これはバグを作るのではなく、すでにあったバグが現れる条件を作るものです。
同じプログラムを5回実行する
ステップ1のプログラムを5回実行し、/root/conc/02-repeat.txtに、1行目はexpected 200000、その次の5行は<회차> <actual 값>の形式で残します(プレースホルダーは、実行回の番号とactualの値です)。
for i in 1 2 3 4 5; do ...; doneで実行し、各実行のactualの値だけを取り出して書けば十分です。
値が毎回違うことが、このステップの要点です。競合状態はあるかないかではなく、現れるか現れないかの問題なので、テストを10回実行して10回通過しても、バグがないという意味ではありません。
ロックをかけて損失をなくす
/root/conc/lock.pyを作ります。ステップ1と同じ構造にthreading.Lockをかけて、損失をなくします。expected 200000、actual <값>、elapsed <밀리초>の3行を出力し(プレースホルダーは、それぞれ値とミリ秒です)、その出力を/root/conc/03-lock.txtに残します。
with lock:ブロックで、読み込みと書き込みを一緒に囲む必要があります。読み込みだけ、または書き込みだけを囲むと、その間がそのまま開いているので、損失が残ります。
elapsedには、スレッドを起動する直前から、すべてが合流した直後までの時間を、ミリ秒で書きます。ステップ7でこの値を使います。
そもそも共有しない方法
/root/conc/local.pyを作ります。スレッドごとに自分の分をローカル変数で数え、最後にまとめて同じ結果を出します。ロックやセマフォは使いません。出力形式はステップ3と同じで、その出力を/root/conc/04-local.txtに残します。
各スレッドが自分のローカル変数だけを増やし、終わるときに結果をリストの自分の位置に入れて、メインスレッドがすべての合流後に足せば十分です。共有がないので、守るものもありません。
採点ツールは、このファイルにLock、Semaphore、Conditionがないかも確認します。ロックを使わずに同じ正確さを得ることが、このステップの要点です。
ロックを逆の順序で取ってデッドロックを作る
/root/conc/deadlock.pyを作ります。python3 /root/conc/deadlock.py reverseで呼び出すと、2つのスレッドが2つのロックを逆の順序で取って、デッドロックを起こす必要があります。2つ目のロックはacquire(timeout=2)で取って、永遠に止まらないようにし、mode <갈래>とblocked <못 잡은 스레드 수>の2行を出力します(プレースホルダーは、モードの名前と、ロックを取れなかったスレッドの数です)。その出力を/root/conc/05-deadlock.txtに残します。
最初のロックを取った後、time.sleep(0.05)で少し休んで、相手にも自分の最初のロックを取らせてください。その隙間がないと、片方が先にすべて終わってしまい、デッドロックが起きません。
timeoutなしで取ると、プログラムが永遠に止まります。デッドロックは自然には解けないからです。時間制限を設けるのはデッドロックを直す方法ではなく、デッドロックが起きたことを観測する方法です。
順序を統一してデッドロックをなくす
deadlock.pyにsameモードを加えます。2つのスレッドがロックを同じ順序で取るように変えるだけで、残りはそのままにします。python3 /root/conc/deadlock.py sameの出力を/root/conc/06-order.txtに残します。blockedは0でなければなりません。
ロックをなくすことも、休む時間を削ることも、時間制限を延ばすこともしません。取る順序だけを統一します。それで、デッドロックの4つの条件のうち、循環待機が崩れます。
実務でロックの順序を文書で決めておく理由がこれです。各自が好きな順序で取ると、いつか2つの経路がすれ違います。
ロックがどれだけコストを取っていくかを測る
ステップ3とステップ4のプログラムのelapsedをそれぞれ取り出して、/root/conc/07-cost.txtにlock <밀리초>、local <밀리초>の2行で残します(プレースホルダーはミリ秒です)。
2つのプログラムは、同じ回数だけ同じ数を数えます。違うのは、共有変数をロックで守るか、そもそも共有しないかだけです。
ロックはタダではありません。そのため実務の方向は、ロックをうまく使うことより、ロックが必要ないようにすることです。ただし、分けて数える方式がいつでも可能とは限らないという点も、あわせて覚えておいてください。
何が何を防いだのかをまとめる
/root/conc/08-notes.mdに3行以上書きます。更新が消えた理由、ロックが防いでくれたもの、デッドロックをなくした方法を、それぞれ1文で書きます。
本文に임계、교착、순서が含まれている必要があります(韓国語の3つの語は、それぞれ「クリティカル」「デッドロック」「順序」を意味します)。
特に、ステップ5とステップ6の間で変えたものが何だったのかを、正確に書いておいてください。ロックを増やしたのでも、時間制限を延ばしたのでもありませんでした。