複数スレッドの並行処理で典型的な問題として、Producer-Consumer問題というのがある。
スレッドであるproducerとconsumerはそれぞれの仕事のペースについて同期を行うことができないため、それぞれのペースの違いによって、取得する値がおかしくなったり、共有している資源のデータ構造によってはエラーが発生したりする。更に厄介な点として、ここで発生するエラーが確率的に起こるということで（スレッドの状態は確率的なので）、複雑なマルチスレッドプログラムについて、プログラマが致命的なエラーに気づけないという事態も発生する点が挙げられる。
Producer-Consumer問題をもう少し説明する
登場人物はProducerとConsumerの２人である。実は、現実のシチュエーションではproducerやconsumerは複数人登場するのだが、ここでは簡単のためにproducerが一人、consumerが一人と考えよう。この２人はスレッドであり、２人は共通の資源を持っている。この共通の資源というのは例えばスタックだったり、キューだったり、あるいはただの変数だったりする。ここでは一番単純なケースとして一つの変数を共有しているケースを考えてみる。
ここでproducerの仕事は新しく発生した値を共通の変数にセットすることである。consumerの仕事は新しくセットされた値を読み出す（消費する）ことである。
理想的にはproducerが 1-> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 と共通資源に値をセットしたとき、consumerが 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 というように値を読み出してほしい。ただし、工夫無しでこれを実装するとこの通りにはならず、consumerの読み出す値が飛び飛びになったり重複を含んだりする。
理由としては、producerとconsumerの仕事のペースに違いがあるからということになる。
producerがconsumerよりもハイペースに仕事をする場合、consumerがセットされた値を消費する前にproducerが値を書き換えてしまうため、取得された値が飛び飛びになる。(case 1)
consumerがproducerよりもハイペースに仕事をする場合、producerが値を更新する前にconsumerが複数回値を読みに行ってしまうので、取得されて値は重複を含んだものになる。(case 2)
これを解消するためには、
producerはconsumerが値を取得するまでは値を生産しない(case 1 の回避)
consumerはproducerが値を更新するまでは値を取得しない(case 2 の回避)
が必要だ。これを実現するためにはsemaphoreを使うとよく、
・producerが値を更新するまでは、consumerを寝かせておき、producerが値を更新したタイミングでconsumerを起こす
・consumerが値を値を取得するまでは、producerを寝かせておき、consumerが値を更新したタイミングでproducerを起こす
というようにする。
複数のconsumer、producerがいる場合を考えてて、値の更新時、取得時は資源をロックしておく。資源のロックには排他制御用のbinary semaphore(mutexと呼ぶ）を利用する。
ここではただの変数が共通資源なので考えていないが、共通資源がスタックやキューのようなものである場合、バッファサイズも考慮する必要があり、これにはcounting semaphoreを用いる。
ちなみに、semaphoreを利用しない手もあり、その一つとして最も単純なビジーウェイト(文化圏によってはspin lockというらしい）を用いる方法がある。値の更新や取得に関するフラグ変数を作っておきwhileでチェック動作を繰り返して、trueになったときに資源をロックして操作を行う。ただし、これはプロセッサの利用を阻害するため実装として好ましくない。また、whileの条件文がtrueになってから資源をロックするまでには多少のタイムラグがあり、ソフトウェア実装の場合はここで割り込みが入って、結果、複数スレッドがcritical regionに入ってしまう危険がある。回避策としては割り込み不可命令(atomic operation)を用いることが考えられるが、ここまで来るとソフトウェアらしい高級感はなくなってくる(気がする）。
0 件のコメント:
コメントを投稿
注: コメントを投稿できるのは、このブログのメンバーだけです。