前回までのあらすじ
実際に並行処理を記述する際にどのように手法を決めて実装していくのかという話が第2章のメインであった。 並行処理の方針を決める手法は以下の2通りで、第2章ではそれぞれの特徴やマナー、サンプルに触れながら内容が進んでいく。
- タスク分解
- データ分解(データをチャンクに分解)
加えて、筆者が並行処理を作成する際に、何を重要としているか(1にスケーラビリティ, 2にパフォーマンス)という話も登場した。詳細は、前回の記事をご参照下さい。
第3章
まずは、いつものように見出しからどんな情報が得られるかを観察。第3章は大きく以下のような構成になっている。
ご覧の通り、第3章は作成した並行処理に対してどのように検証作業を行なっていくのかがメイントピックになっており、並行処理を作成した後の話になる。しかし、並行処理を記述する際にも、第3章で登場する考え方(一般化方法)は非常に重要であり、「ちゃんと読んでね」という筆者のメッセージが込められているため、飛ばさずに読む。
並行処理の検証について
M.Ben-Ariという強すぎる方が記した著書「Principles of Concurrent and Distributed Programming」で並行処理、および分散プログラミングが仕様通りに動いているかを一般化(誰がやっても同じようになるように)したそうで、この一般化方法が並行アルゴリズムを設計する上で最も大切になるとのこと(絶対に後悔させないから読んでくれと熱いメッセージが記述されている)。まずはこのBen-Ariが提案した一般化方法を理解することからこの章は始まる
Ben-Ariの並行アルゴリズムの一般化
「うわー、理論的で絶対に難しいやろなぁ」と思いつつ読み進めてみると人生初遭遇の単語が多いが、書かれている内容は意外とシンプルで慌てる必要はなさそう。順に見ていく。
プログラムはアトミックな実行文の連続である
その通りだとしか言いようがない。アトミックというのは原子を英語でアトムというので、処理を構成する部品のことだと思えばいい。本書によると、この粒感はプログラムコードの1行に当たるものであったり、アセンブリ言語で記述された1行であったりと見方によって変化するようだが、並行アルゴリズムを設計する際には高級言語で記述するコードの1行だと考えるのが良いのだそう。
どんな複雑な処理であっても、コードを1つ1つ分解していけば、1行のプログラムコードの連続になるという主張になる
name = "OKB" # アトミック print(name) # アトミック if name != "OKB": # アトミック print("Who are you???") # アトミック
インタリーブ(意味: 相互に挟み込む)
並行プログラムは必ずしも複数のスレッドが毎回、同じ順番で実行されることはなく、実行する度に処理される順序や処理時間は変化する。しかし、毎回実行する度に結果が異なるというのは冪等性に欠けており並行プログラムとしては欠陥品と言える。この複数のスレッドの実行文がそれぞれ、実行される順序の組み合わせのことを「インタリーブ」と呼び、並行プログラムは実行されうる全てのインタリーブ(組み合わせ)で同じ結果になることを証明する必要がある
インタリーブの数はスレッド数が増えると指数関数的に増えるため、全てのインタリーブに注目するのではなく、連続的整合性を証明するために必要な部分のみを取捨選択することが重要になる。
軽くPythonでサンプルを記述してみた。以下の処理は買い物カゴに関数funcAが引数に渡されてきた値を追加し、関数funcBが先頭要素を取り出し、返すという極シンプルなもの。逐次処理でfuncA -> funcBという順に呼び出されるのであれば問題はなさそうだが、並行プログラムとして関数それぞれをスレッドで動作させるとどうだろうか。
# 買い物カゴ cart = [] # スレッドAに実行される関数 def funcA(goods): print("A was start") cart.append(goods) # スレッドBに実行される関数 def funcB(): print("B was start") # 買い物カゴから先頭要素をpop goods = cart.pop(0) return goods # 以下のように逐次実行されるなら問題はないが... funcA("orange") print(cart) funcB() print(cart)
インタリーブを考えると以下のようになる。print()の処理はどんな順で呼び出されても今の所は問題ないだろうからインタリーブからは外しておく。
- case: 1
- A: カートに値を追加
- B: カートから値を取得
- case: 2
- B: カートから値を取得
- A: カートに値を追加
case: 2の場合はリストに値が存在しないにも関わらずpop()を実行することになるため、実行時errorになる。これは先ほど述べた「実行されうる全てのインタリーブで同じ結果になる」という証明が出来ていないため、並行プログラムとしては欠陥品だと言える
Traceback (most recent call last): File "Main.py", line 17, in <module> funcB() File "Main.py", line 12, in funcB goods = cart.pop(0) IndexError: pop from empty list
Ben-Ariの4つの並行実行一般化まとめのまとめ
本書にあるものを噛み砕いて記述しておく。情報を整理して覚えやすくする。
- プログラムは連続したアトミックな実行文
- 並行プログラムは複数スレッドが実行する処理の組み合わせ(アトミックのインタリーブと本書に有り)
- 並行プログラムは実行されうる全てのインタリーブで結果が同じになるように
- どのインタリーブでも他スレッドの実行を妨げてはならない -> 他スレッドの処理を停止させたり、実行を占有してはならない
これでBen-Ariの並行アルゴリズムの一般化方法に関する知識を身につけたことになる。次にBen-Ariの一般化方法をどのように使用するのかという話になっていく。
例題: クリティカルセクション問題
並行アルゴリズムで共有変数を参照/更新する部分を「クリティカルセクション」と言い、並行アルゴリズムを設計する上で良い例題となるらしい(著者はクリティカルリージョンと言うのが好みの様)。クリティカルセクションでは以下2つの性質を満たす必要がある。
守るべき性質
- 排他制御(アクセス可能なスレッドは1つのみ)
- 他スレッドが共有変数を参照/更新 中は共有変数へのアクセスを禁止される。
- 他スレッドが他スレッドの共有変数へのアクセスを妨げてはならない
簡略化のためスレッドは2つで固定(スレッドzeroとスレッドone)してインタリーブを考える。コードをそのまま転載するのはアレなので、Pythonでそれっぽいものに書き換えたものを載せておく。
以下のコードはそのまま実行すると自動で終了しないので注意して下さい!!
第1段階
thread_number = 0 # 実行中のスレッド番号 def thread_zero(): while True: # spin wait(待機し続ける) while(thread_number == 1): pass # 共有変数へのアクセス critical_region_zero() # 実行スレッドを0から1に切り替え thread_number = 1 # 何かしらの処理 other_stuff_zero() def thread_one(): while True: # spin wait(待機し続ける) while(thread_number == 0): pass # 共有変数へのアクセス critical_region_one() # 実行スレッドを1から0に切り替え thread_number = 0 # 何かしらの処理 other_stuff_one()
それぞれのスレッドが実行される度にthread_numberの値を参照して、自分に実行権があるのかを確認する。実行権があればクリティカルリージョンへのアクセスを行う。アクセスが終了した際にthread_numberをzeroなら1に、oneなら0に切り替える。これで問題なく排他制御がされるはず。
しかしながら、これは互いのスレッドが動作していることが前提であり片方のスレッドが何かしらの原因で停止した際には、もう片方のスレッドはthread_numberの値が変わることを期待して待機し続けてしまい結果的にデッドロックが発生してしまう。
第2段階
thread_0_inside = 0 # zeroがクリティカルリージョン中か thread_1_inside = 0 # oneがクリティカルリージョン中か def thread_zero(): while True: while(thread_1_inside): pass # クリティカルリージョンへアクセス中ということを表明 thread_0_inside = 1 # 共有変数へのアクセス critical_region_zero() # クリティカルリージョンへのアクセスが終了したことを表明 thread_0_inside = 0 # 何かしらの処理 other_stuff_zero() def thread_one(): while True: while(thread_0_inside): pass # クリティカルリージョンへアクセス中ということを表明 thread_1_inside = 1 # 共有変数へのアクセス critical_region_one() # クリティカルリージョンへのアクセスが終了したことを表明 thread_1_inside = 0 # 何かしらの処理 other_stuff_one()
第1段階で課題となった「他方のスレッドが停止した場合にデッドロックが発生する」という問題に対応するために、他方のスレッドがクリティカルリージョンへアクセスしている際には自身の処理をスピンウェイトするという処理に更新された。こうすることで他方が何かしらの原因で停止したとしてもデッドロックは発生しなくなる。しかしながら、この方法には大きな問題がある。thread_0_insideの値、もしくはthread_1_insideの値を1に更新する最中に、他方のスレッドがクリティカルリージョンにアクセスしてしまう可能性がある。これは排他制御が機能していないことを意味している。
このようにそれぞれのスレッドが「アクセスするで」という意思を表明した後に、すぐにクリティカルリージョンにアクセスするような解法を著者は「自分勝手なスレッド」と言うそう。
第3段階
thread_0_wants_enter = 0 # zeroがクリティカルリージョンへのアクセスを依頼中か thread_1_wants_enter = 0 # oneがクリティカルリージョンへのアクセスを依頼中か def thread_zero(): while True: # zeroがクリティカルリージョンへのアクセスをしようとしていることを表明 thread_0_wants_enter = 1 while(thread_1_wants_enter): pass # 共有変数へのアクセス critical_region_zero() # zeroがクリティカルリージョンへのアクセスが終了したことを表明 thread_0_wants_enter = 0 # 何かしらの処理 other_stuff_zero() def thread_one(): while True: # oneがクリティカルリージョンへのアクセスをしようとしていることを表明 thread_1_wants_enter = 1 while(thread_0_wants_enter): pass # 共有変数へのアクセス critical_region_one() # oneがクリティカルリージョンへのアクセスが終了したことを表明 thread_1_wants_enter = 0 # 何かしらの処理 other_stuff_one()
先ほどの自分勝手なスレッドを改修して、第3段階ではクリティカルリージョンへのアクセスの意思を表明してから、他方のスレッドがアクセスしようとしていないかを確認するようになっている。こうすることで同時にクリティカルリージョンへアクセスする問題は発生しなくなり、排他制御が正常に行われると判断出来ると思いきや、先ほどと同じ様にデッドロックが発生しうる。
thread_0_wants_enterとthread_1_wants_enterがほぼ同時に1に更新された時に、お互いに値が0になるまでスピンウェイトする。これはいつまでたっても終わることがない。互いに「どうぞどうぞ」と道を永遠に譲り続ける状態となってしまう。
第4段階
import time import random thread_0_wants_enter = 0 # zeroがクリティカルリージョンへのアクセスを依頼中か thread_1_wants_enter = 0 # oneがクリティカルリージョンへのアクセスを依頼中か def thread_zero(): while True: # zeroがクリティカルリージョンへのアクセスをしようとしていることを表明 thread_0_wants_enter = 1 while(thread_1_wants_enter): # アクセスしたい表明を一旦取り下げる thread_0_wants_enter = 0 # ランダム秒だけ待機 time.sleep(random.uniform()) # 再度、アクセスを表明 thread_0_wants_enter = 1 # 共有変数へのアクセス critical_region_zero() # zeroがクリティカルリージョンへのアクセスが終了したことを表明 thread_0_wants_enter = 0 # 何かしらの処理 other_stuff_zero() def thread_one(): while True: # oneがクリティカルリージョンへのアクセスをしようとしていることを表明 thread_1_wants_enter = 1 while(thread_0_wants_enter): # アクセスしたい表明を一旦取り下げる thread_1_wants_enter = 0 # ランダム秒だけ待機 time.sleep(random.uniform()) # 再度、アクセスを表明 thread_1_wants_enter = 1 # 共有変数へのアクセス critical_region_one() # oneがクリティカルリージョンへのアクセスが終了したことを表明 thread_1_wants_enter = 0 # 何かしらの処理 other_stuff_one()
第3段階の単純なスピンウェイトを改めて、すでに他方のスレッドがクリティカルリージョンへアクセスした場合に自身がアクセスしたいという表明(thread_0_wants_enterもしくはthread_1_wants_enterを0に)を取り下げて、ランダム秒だけ待機する。2つの乱数が一致することが無い限り、お互いに道を譲り合うような状態は発生することが無くなり、デッドロックは起こり得ない。 お、完璧やんと思いつつ、実はまだ問題がある。
例えば、zeroのスレッドが処理を終了しthread_0_wants_enterの値を0に戻す。次に新たなスレッドがクリティカルリージョンへのアクセスを依頼する。依頼してきたのはzeroのスレッド。thread_1_wants_enterの値を確認し、0であれば(0と仮定)、thread_0_wants_enterを1に更新して、クリティカルリージョンへのアクセスを再度行う。アクセスが終了したタイミングでthread_0_wants_enterを0に更新する。再度、新たなスレッドがクリティカルリージョンへのアクセスを依頼する。依頼してきたのはzeroのスレッド...
このようにどちらかのスレッドが永遠にアクセス権限を独占してしまう可能性があるということが記述されている。この現象をスターベーション(枯渇)と言う。なるほど。この問題を解消するためにDekkerのアルゴリズムを実装するが、その前にデッドロックが発生する4条件について触れておく。
デッドロックを発生させる4つの条件
左側が本書から引用した言葉、右側が意味を噛み砕いた文章。
- 1.相互排他条件 -> 同時にいくつかのスレッドがアクセス可能。もしくは1スレッドのみがアクセス中
- 2.獲得後のウエイト -> アクセスを終了したスレッドが再度、続けてアクセスをしようとする
- 3.プリエンプトなし(先取する) -> 参照された値を削除して良いのは参照したスレッドのみ(値の解放)
- 4.循環待ち -> すでに他スレッドで参照されている値を参照しようとする
1, 2は何となくアカンのやろなぁと分かるが、3, 4に関しては場面想定が上手く出来ないが、鍵を持って箱を開けて得た中身の処理は開けた本人(スレッド)に責任を要求するという様に考えておけばいいだろう。
Dekkerのアルゴリズム
先ほど第4段階で実装したコードをDekkerのアルゴリズムの形に改修する。
auth = 0 # クリティカルリージョンへアクセス可能なスレッド番号(スイッチ) thread_0_wants_enter = 0 # zeroがクリティカルリージョンへのアクセスを依頼中か thread_1_wants_enter = 0 # oneがクリティカルリージョンへのアクセスを依頼中か def thread_zero(): while True: # zeroがクリティカルリージョンへのアクセスをしようとしていることを表明 thread_0_wants_enter = 1 while(thread_1_wants_enter): # アクセス権限があるかを確認 if auth == 1: # アクセスしたい表明を一旦取り下げる thread_0_wants_enter = 0 # アクセス権限がなければ待機 while auth == 1: pass # 再度、アクセスを表明 thread_0_wants_enter = 1 # 共有変数へのアクセス critical_region_zero() # アクセス権限を譲る auth = 1 # zeroがクリティカルリージョンへのアクセスが終了したことを表明 thread_0_wants_enter = 0 # 何かしらの処理 other_stuff_zero() def thread_one(): while True: # oneがクリティカルリージョンへのアクセスをしようとしていることを表明 thread_1_wants_enter = 1 while(thread_0_wants_enter): # アクセス権限があるかを確認 if auth == 0: # アクセスしたい表明を一旦取り下げる thread_1_wants_enter = 1 # アクセス権限がなければ待機 while auth == 0: pass # 再度、アクセスを表明 thread_1_wants_enter = 1 # 共有変数へのアクセス critical_region_one() # アクセス権限を譲る auth = 0 # oneがクリティカルリージョンへのアクセスが終了したことを表明 thread_1_wants_enter = 0 # 何かしらの処理 other_stuff_one()
構造としてはクリティカルリージョンにアクセス可能なスレッドをauth(本書にはfavoredとあり)という変数によって制御する。このauthはいわば、クリティカルリージョンへアクセスするための優先権となる。どちらかのスレッドがクリティカルリージョンへアクセスしようとしても、アクセスするための優先権がなければ、アクセスすることは出来ない。そのため、先ほどのように何度も同じスレッドがクリティカルリージョンへアクセスするという現象を回避することが出来る。より詳細なインタリーブは本書を読んでみてほしい。
性能評価
いたって単純。算出式の妥当性だとか、どうしてこの式が定義されているのかは追求しない。賢い人に任せる。 評価の軸は以下の2つ。
- 高速化率
- 実行効率
高速化率
「従来の逐次処理に対して、並行化したこの処理は300％早くなりました!」と言われるよりも「従来の逐次処理の3倍早くなりました」と言われた方が直感的で理解し易い。高速化率とは元の逐次処理が並行化したことで何倍早くなったのかを算出するための指標値になる。高速化率を算出するためには逐次処理の実行時間数値が必要になるので注意が必要。理想値はコア数に比例して高速化率も増えていくような数値になる。(コア数が10倍 -> 高速化率も10)
算出式は以下の2つが紹介されており、2つの算出式の違いはGustafson-Barsisの法則ではコア数が増えるにつれて、データ量の増加しているという前提が含まれているという点で算出方法が異なる。
Amdahlの法則: Amdahl's law - Wikipedia
Gustafson-Barsisの法則: Gustafson's law - Wikipedia
実行効率
高速化率をコア数で割れば算出可能。どれだけコンピューターリソースを上手く使えたかという指標になる。仮に90%という値が算出されたのであれば、残りの10%は処理全体を平均して、全てのコアが10%はアイドルになっていたということになる。この10%を減らすことが出来れば、完璧な効率化が出来たといえるが、実際になぜ実行効率の値が低いのかと言う原因は要因が複雑すぎるため、厳密な考察が必要だそう。
以上
