読了17:00

#### でのソフトウェア6.005

#### 目標+メッセージパッシング&共有メモリ+プロセス&スレッド+時間スライス+競合条件##同時実行*同時実行*は、複数の計算が同時に発生していることを意味し 並行性は、我々はそれを好きかどうか、現代のプログラミングのどこにでもあります：+ネットワーク内の複数のコンピュータ+一つのコンピュータ上で実行され+モバイルアプリは、（”クラウド内”）サーバー上でその処理の一部を行う必要があります。+グラフィカルユーザインタフェースは、ほとんどの場合、ユーザを中断しない背景作業を必要とします。 たとえば、EclipseはJavaコードの編集中にjavaコードをコンパイルします。並行性でプログラムできることは、将来的には依然として重要です。 プロセッサのクロック速度は、もはや増加していません。 代わりに、我々はチップの各新世代でより多くのコアを取得しています。 したがって、将来的には、計算をより速く実行するためには、計算を並行部分に分割する必要があります。##同時プログラミングのための二つのモデル同時プログラミングのための二つの一般的なモデルがあります：*共有メモリ*と*メッセー

**共有メモリ。* 同時実行の共有メモリモデルでは、同時実行モジュールは、メモリ内の共有オブジェクトを読み書きすることによって相互作用します。 共有メモリモデルの他の例：+AとBは、同じ物理メモリを共有する同じコンピュータ内の2つのプロセッサ（またはプロセッサコア）である可能性があり+AとBは、同じコンピュータ上で実行されている2つのプログラムであり、読み書きできるファイルと共通のファイルシステムを共有しています。+AとBは、同じJavaプログラム内の2つのスレッドであり（以下ではスレッドが何であるかを説明します）、同じJavaオブジェクトを共有します。

**メッセージパッシング。**メッセージパッシングモデルでは、並行モジュールは通信チャネルを介して互いにメッセージを送信することによ モジュールはメッセージを送信し、各モジュールへの着信メッセージは処理のためにキューに入れられます。 例としては、+AとBは、ネットワーク接続によって通信するネットワーク内の二つのコンピュータである可能性があります。+Aとbはwebブラウザとwebサーバーである可能性があります-AはBへの接続を開き、webページを要求し、BはwebページのデータをAに送り返します。+AとBはインスタン+AとBは、コマンドプロンプトに入力された`ls|grep`のように、入力と出力がパイプで接続されている同じコンピュータ上で実行されている2つのプログ##プロセス、スレッド、タイムスライシングメッセージパッシングと共有メモリモデルは、並行モジュールがどのように通信するかについ 並行モジュール自体には、プロセスとスレッドという2種類の異なるものがあります。**プロセス**。 プロセスは、同じマシン上の他のプロセスから*分離*されている実行中のプログラムのインスタンスです。 特に、それはマシンのメモリの独自のプライベートセクションを持っています。プロセス抽象化は*仮想コンピュータ*です。 それはそれ自体にマシン全体を持っているようにプログラムを感じさせます-新鮮なコンピュータが作成されたように、新鮮なメモリで、そのプログラネットワークを介して接続されたコンピュータと同じように、プロセスは通常、それらの間でメモリを共有しません。 プロセスは、別のプロセスのメモリまたはオブジェクトにまったくアクセスできません。 プロセス間でメモリを共有することは、ほとんどのオペレーティングシステムで*可能*ですが、特別な努力が必要です。 これとは対照的に、新しいプロセスは、`システム’である標準入力&出力ストリームで作成されるため、メッセージパッシングの準備が自動的に整います。アウト’と`System.in’あなたがJavaで使用してきたストリーム。**糸**。 スレッドは、実行中のプログラム内の制御の軌跡です。 それは、実行されているプログラム内の場所と、それを通って戻る必要がある場所につながったメソッド呼び出しのスタックと考えてください。プロセスが仮想コンピュータを表すのと同じように、スレッド抽象化は*仮想プロセッサ*を表します。 新しいスレッドを作成すると、プロセスによって表される仮想コンピュータ内の新鮮なプロセッサを作成することをシミュレートします。 この新しい仮想プロセッサは、同じプログラムを実行し、プロセス内の他のスレッドと同じメモリを共有します。スレッドはプロセス内のすべてのメモリを共有するため、スレッドは自動的に共有メモリの準備ができます。 単一のスレッドにプライベートな”スレッドローカル”メモリを取得するには特別な努力が必要です。 また、キューデータ構造を作成して使用することによって、メッセージパッシングを明示的に設定する必要があります。 私たちは、将来の読書でそれを行う方法について話します。

コンピュータに1つまたは2つのプロセッサのみを持つ同時スレッドを多数持つにはどうすればよいですか？ プロセッサよりも多くのスレッドがある場合、同時実行は**時間スライス**によってシミュレートされます。 右の図は、実際のプロセッサが二つしかないマシンで、三つのスレッドT1、T2、およびT3がどのようにタイムスライスされるかを示しています。 図では、時間が下方に進むため、最初は一方のプロセッサがスレッドT1を実行し、もう一方のプロセッサがスレッドT2を実行し、次に2番目のプロセ スレッドT2は、同じプロセッサまたは別のプロセッサ上の次のタイムスライスまで、単に一時停止します。ほとんどのシステムでは、タイムスライシングは予期せず非決定的に行われ、スレッドはいつでも一時停止または再開される可能性があります。

mitx:c613ec53e92840a4a506f3062c994673Processes&Threads##共有メモリの例共有メモリシステムの例を見てみましょう。 この例のポイントは、並行プログラミングが微妙なバグを持つ可能性があるため、困難であることを示すことです。

銀行に共有メモリモデルを使用する現金機があると仮定すると、すべての現金機がメモリ内の同じ口座オブジ“Java//すべての現金マシンが単一の銀行口座を共有しているとしますprivate static int balance=0;private static void deposit(){balance=balance+1;}private static void delight(){balance=balance-1;}“顧客は現金マシンを使用して次のような取引を行います。“javadeposit();//putドル(); //take it back out”‘この単純な例では、すべてのトランザクションは一ドルの預金に続いて一ドルの引き出しであるため、アカウントの残高は変更されません。 一日を通して、私たちのネットワーク内の各現金機械は、入出金取引のシーケンスを処理しています。`’java//各ATMは、//残高を変更するトランザクションの束を行いますが、その後は変更されませんprivate static void cashMachine(){for(int i=0;i<TRANSACTIONS_PER_MACHINE;++i){deposit();//ドルを引き出しに入れます(); //take it back out}}”‘だから、一日の終わりには、実行されている現金マシンの数、または処理したトランザクションの数にかかわらず、口座残高はまだ0になると期しかし、このコードを実行すると、1日の終わりの残高が*0ではないことが頻繁にわかります。 複数の`cashMachine()`呼び出しが同時に実行されている場合（たとえば、同じコンピュータ内の別々のプロセッサ上で）、`balance’は一日の終わりにゼロにならない可能性があり なぜいけないか。##InterleavingHereは起こることができる一つのことです。 二つの現金機械、AとBは、両方が同時に預金に取り組んでいると仮定します。 Deposit()ステップは、通常、低レベルのプロセッサ命令に分解する方法です：“get balance(balance=0)add1write back the result(balance=1)“AとBが同時に実行されているとき、これらの低レベルの命令は相互にインターリーブされます（ある意味では同時である場合もありますが、今のところインターリーブについて心配しましょう）。:`’A get balance(balance=0)a add1a write back the result(balance=1)B get balance(balance=1)B add1B write back the result(balance=2)“このインターリーブは大丈夫です-私たちはbalance2で終わるので、AとBの両方が正常にドルに入れ しかし、インターリーブが次のようになった場合：“a get balance(balance=0)B get balance(balance=0)a add1B add1a write back the result(balance=1)B write back the result(balance=1)“バランスは今1です-Aのドルは失われました！ AとBの両方が同時に残高を読み、別々の最終残高を計算し、次に新しい残高を保管するために競争しました。##Race ConditionThisは**race condition**の例です。 競合状態とは、プログラムの正確さ（事後条件と不変条件の満足度）が、同時計算AとBのイベントの相対的なタイミングに依存することを意味します。”イベントのいくつかのinterleavingsは、単一の非concurrentプロセスが生成するものと一致しているという意味でOKかもしれませんが、他のinterleavingsは間違った答えを生成しま##コードを微調整しても、これらのバージョンの銀行口座コードはすべて同じ競合状態を示します。“java//version1private static void deposit(){balance=balance+1;}private static void delight(){balance=balance-1;}“`java//version2private static void deposit(){balance+=1;}private static void delight(){balance-=1;}”””java//version2private static void deposit(){balance+=1;}private static void delight(){balance-=1;};}`””java//version3private static void deposit(){++balance;}private static void delight(){–balance;}”`プロセッサがどのように実行されるかをJavaコードを見ているだけではわかりません。 不可分な操作-原子操作-が何であるかを知ることはできません。 それはJavaの1行だからといって原子的ではありません。 バランス識別子がライン内で一度だけ発生するため、バランスには一度だけ触れません。 Javaコンパイラ、そして実際にはプロセッサ自体は、コードから生成される低レベルの操作については何の約束もしません。 実際、典型的な最新のJavaコンパイラは、これらのバージョンの3つすべてでまったく同じコードを生成します。重要な教訓は、競合状態から安全であるかどうかを式を見ることでは判断できないということです。

## 再注文それは実際には、それよりもさらに悪いです。 銀行口座残高の競合状態は、異なるプロセッサ上のシーケンシャル操作の異なるインターリーブの観点から説明することができます。 しかし、実際には、複数の変数と複数のプロセッサを使用している場合、同じ順序で表示される変数の変更を数えることさえできません。ここに例があります：“javaprivate boolean ready=false;private int answer=0;//computeAnswerは一つのthreadprivate void computeAnswer(){answer=42;ready=true;}//useAnswerは別のthreadprivate void useAnswer(){while(!ready){スレッド.yield();}if(answer==0)throw new RuntimeException(“answerは準備ができていませんでした！”);}”‘私たちは、異なるスレッドで実行されている二つのメソッドを持っています。 ‘computeAnswer’は長い計算を行い、最終的に答え42を考え出し、答え変数に入れます。 次に、`ready`変数をtrueに設定して、もう一方のスレッド`useAnswer`で実行されているメソッドに、答えが使用できるように準備ができていることを通知します。 コードを見ると、readyが設定される前に`answer`が設定されているため、`useAnswer`が`ready`をtrueと見なすと、`answer`が42になると想定できるのは合理的ですよね？ そうではありません。問題は、現代のコンパイラとプロセッサがコードを高速にするために多くのことを行うことです。 これらのことの1つは、answerやreadyのような変数の一時的なコピーをより高速なストレージ（プロセッサ上のレジスタやキャッシュ）に作成し、一時的に作業してから、最終的にそれらをメモリ内の公式の場所に格納することです。 ストアバックは、コード内で変数が操作された順序とは異なる順序で発生する可能性があります。 ここでは、カバーの下で何が起こっているのかを説明します（ただし、明確にするためにJava構文で表現されています）。 プロセッサは、readyフィールドとanswerフィールドを操作するために、二つの一時変数`tmpr`と`tmpa`を効果的に作成しています:`’javaprivate void computeAnswer(){boolean tmpr=ready;int tmpa=answer;tmpa=42;tmpr=true;ready=tmpr;//<–useAnswer()がここでインターリーブするとどうなりますか？ //readyが設定されていますが、回答はありません。answer=tmpa;}“mitx:2bf4beb7ffd5437bbbb9c782bb99b54e競合条件##メッセージパッシングの例

次に、銀行口座の例へのメッセージパッシングのアプローチを見てみましょう。今だけでなく、現金機モジュールですが、アカウントも、モジュールです。 モジュールは互いにメッセージを送信することで相互作用します。 着信要求は、一度に1つずつ処理されるキューに配置されます。 送信者は、その要求への回答を待っている間に動作を停止しません。 独自のキューからのより多くの要求を処理します。 その要求への応答は、最終的に別のメッセージとして返されます。残念ながら、メッセージパッシングは競合状態の可能性を排除するものではありません。 各アカウントが対応するメッセージで`get-balance`と`withdraw`操作をサポートしているとします。 現金マシンAとBの2人のユーザーは、両方とも同じ口座からドルを引き出そうとしています。 “‘Get-balanceif balance>=1then delight1″‘問題は再びインターリーブですが、今回はAとBによって実行される*instructions*ではなく、銀行口座に送信された*messages*のインターリーブです。ここでの教訓の1つは、メッセージパッシングモデルの操作を慎重に選択する必要があることです。 “引き出し-if-sufficient-funds”は、単に”引き出し”よりも優れた操作になります。##並行性はテストとデバッグが難しい並行性がトリッキーであることをあなたに説得していない場合、ここでは最悪です。 テストを使用して競合状態を発見するのは非常に難しいです。 そして、テストがバグを発見したとしても、それを引き起こしているプログラムの部分にローカライズすることは非常に難しいかもしれません。並行性のバグは再現性が非常に低い。 それらを同じように二度起こらせることは困難である。 命令またはメッセージのインターリーブは、環境によって強く影響されるイベントの相対的なタイミングに依存します。 遅延は、他の実行中のプログラム、他のネットワークトラフィック、オペレーティングシステムのスケジューリングの決定、プロセッサ 競合状態を含むプログラムを実行するたびに、異なる動作が発生する可能性があります。 これらの種類のバグは**heisenbugs**であり、あなたがそれを見るたびに繰り返し現れる”bohrbug”とは対照的に、非決定的で再現が難しいです。 シーケンシャルプログラミングのほとんどすべてのバグはbohrbugsです。`Println`または`debugger`でそれを見ようとすると、heisenbugが消えることさえあります！ その理由は、印刷とデバッグが他の操作よりも非常に遅く、多くの場合100-1000倍遅くなり、操作のタイミングやインターリーブが劇的に変化するためです。 したがって、単純なprint文をcashMachine()に挿入します。“javaprivate static void cashMachine(){for(int i=0;i<TRANSACTIONS_PER_MACHINE;++i){deposit();//ドルを引き出しに入れます();//システムを取り戻します。出ろprintln(balance);//バグを消します！ }}“`…そして突然、バランスは常に必要に応じて0になり、バグは消えているように見えます。 しかし、それはマスクされているだけで、本当に固定されていません。 プログラム内の他の場所でタイミングを変更すると、突然バグが戻ってくる可能性があります。並行性は正しく取得するのが難しいです。 この読書のポイントの一部は、あなたを少し怖がらせることです。 次のいくつかの測定では、これらの種類のバグからより安全になるように、並行プログラムを設計する原則的な方法を見ていきます。mitx:704b9c4db3c6487c9f1549956af8bfc8並行性のテスト##要約+並行性: 同時に実行される複数の計算+共有メモリ&メッセージパッシングパラダイム+プロセス&スレッド+プロセスは仮想コンピュータのようなものです;スレッドは仮想プロセッサのようなものです+競合条件+結果の正しさ(事後条件と不変条件)がイベントの相対的なタイミングに依存するときこれらのアイデアは、主に悪い方法で良いソフトウェアの三つの重要な特性に接続します。 並行性は必要ですが、正確性には深刻な問題が発生します。 私たちは、次のいくつかの測定値でこれらの問題を修正する上で動作します。+**バグから安全。**並行性のバグは、見つけて修正するのが最も難しいバグの一部であり、避けるために慎重な設計が必要です。+**理解しやすいです。**並行コードが他の並行コードとどのようにインターリーブするかを予測することは、プログラマにとって非常に困難です。 プログラマがそれについて考える必要がないように設計するのが最善です。 +**変更の準備ができています。**ここでは特に関連しません。