プログラミング言語/並行処理言語

[[プログラミング言語|]]

コンカレントプログラミングとは、コンピュータプログラミングの手法の一つで、単一のコンピュータ内、あるいは複数のシステム間で同時に処理を実行するものである。後者の場合、分散コンピューティングという用語が使われる。マルチプロセッサ・マシンは、このようなプログラミングを活用することで、より優れた性能を発揮する。

現在では、CPU負荷の高いプログラムを2倍の速度で実行させるためには、並行プログラミングが唯一の方法となっています。 (歴史的には、クロック速度が2倍のCPUが現れるまで数年待つという方法もよく使われていたが、この傾向は2003年頃に終わった^[1]^[2]

並列プログラミングでは、1つのタスクを比較的独立して計算できるいくつかのサブタスクに分割し、それを集約して1つのまとまった解を形成する。並列プログラミングは、因数分解などの純粋に数学的な問題など、独立したタスクに容易に分解できるタスクに最も効果的である。

並列プログラミングを実現する一つの方法として、通信ネットワークで結ばれた別々のコンピュータで作業を行う分散コンピューティングという情報処理方法がある。

相互排他編集

定義: 1965年にE.W.Dijkstraによって正式に定義され、解決された[D65]。

非臨界部と臨界部という2つのセクションを交互に繰り返すプロセスの集合がある。この問題は、CSの直前と直後にそれぞれ実行されるtryとexitプロトコルの形で同期アルゴリズムを提供することである。

非臨界部(non-critical section)
試行プロトコル(trying protocol)
臨界部(critical section; CS)
終了プロトコル(exit protocol)

以下の性質が成立する。

相互排他

2つのプロセスが同時にCSに存在しないこと。

ロックアウトの自由度 :

あるプロセスが試行プロトコルに入った場合、最終的にCSに入る。

不必要な遅延がないこと。

臨界部に入ろうとするプロセスは、その臨界部を実行中の他のプロセス、またはその臨界部に入ろうとする他のプロセスによってのみ、それを阻止される。

境界出口

あるプロセスが終了プロトコルに入った場合、それ自身のステップ数に制限のある範囲内で非臨界部に入る。

相互排除のソリューション編集

[Y03]によれば、相互排他法の解は、賢い専門家が発明したものもあれば、コンピュータを使ったブルートフォースアプローチで見つけたものもあり、何千通りも存在するそうです。

有名どころを紹介します。
ダイクストラのアルゴリズム: 最初の試み。; [K66][D67]によれば、このアルゴリズムは、個々のコンピュータがアクセス権を争う際に、無限に待たされる可能性を許容している。
ランポートのベーカリーアルゴリズム

理解を容易にするために、元のベーカリーアルゴリズムを修正したものを2プロセスで始める。

2プロセスの場合

  
  Process p0 {
    // non-critical section
    // entry protocol
    turn0 = 1; // ※
    turn0 = turn1 + 1;
    while( turn1 != 0 && turn0 > turn1);
    //critical section
    turn0 = 0;
  }
  
  Process p1 {
    // non-critical section
    // entry protocol
    turn1 = 1; // ※
    turn1 = turn0 + 1;
    while( turn0 != 0 && turn1 >= turn0);
    //critical section
    turn1 = 0;
  }

非公式な証明

p1が非臨界部にいる間に、p0がその臨界部に入ろうとしたとする。このとき、p0はturn1が0であるため、アクセス権を獲得する。
p1が臨界部にあるときに、p0が臨界部に入ろうとしているとします。次に、ターン1が0ではなく、ターン0がターン1より大きいように設定されているため、p0はビジーウェイトになります。 p1が臨界部を終了すると、turn1を0に設定します。2つのサブケースがあります。いずれの場合も、p0は臨界部に入ります。
- p0がturn1をテストするとき、p1が非臨界部で実行されている場合（つまりturn1が0）、p0はその臨界部に入ることになります。
- 一方、p1が非臨界部を終了し、エントリプロトコルの一部としてturn1をturn0+1に設定するかもしれません。p0がこの条件を再テストすると、turn1がturn0より大きいので、偽であることがわかります。そのため、p0は臨界部に入ることになる。
p0とp1が前のケースと同じだとする。ここで、2番目の代入文の実行が機械語命令レベルでインターリーブされているとする。すると、次のような実行順序になることがある。
- p0 は、turn1 の値 (1) を読み取ります。
- p1 は、turn0 の値 (1) を読み取ります。
- p0 は 1 を加算し、その結果 (2) を turn0 に格納します。
- p0 は 1 を加算し、その結果 (2) を turn1 に格納します。

ターン変数の値は等しいが、p1の条件は>=を使うのに対し、p0の条件は>を使うので、p1はp0に従う。

なぜ※なのか？: ※コードの必要性は明白ではないかもしれません。; 詳細な議論はUCDAVIS: Bakery Algorithmを参照してください。; N個のプロセスに対して

  
  // declaration and initial values of global variables
  Entering: array [1..N] of bool = {false};
  Number: array [1..N] of integer = {0};
      
  lock(integer i)
  {
    Entering[i] = true;
    Number[i] = 1 + max(Number[1], ..., Number[N]);
    Entering[i] = false;
    for (j = 1; j <= N; j++) {
      // Wait until thread j receives its number:
      while (Entering[j]) { /* nothing */ }
      // Wait until all threads with smaller numbers or with the same
      // number, but with higher priority, finish their work:
      while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) {
      /* nothing */
      }
    }
  }
  unlock(integer i) { Number[i] = 0; }
  
  Thread(integer i) {
    while (true) {
        lock(i);
        // The critical section goes here...
        unlock(i);
        // non-critical section...
    }
  }

擬似コードでは、フォームの比較があります。

  
(a, b) < (c, d)

と同等である。

  
(a < c) or ((a == c) and (b < d))

なぜベーカリーアルゴリズムと呼ぶのか？

ランポートが思い描いたのは、入り口に番号札のあるパン屋さんです。そこで、お客さん一人一人にユニークな番号をつけます。番号は客が入店するたびに1ずつ増えていく。グローバル・カウンターには、現在サービスを提供している客の番号が表示される。他の客は、パン屋が今の客へのサービスを終えて次の番号が表示されるまで、行列で待たなければならない。買い物が終わると、その客は番号を失い、その後は好きなことができるようになるが、新しい番号をもらわなければ買い物ができない。