並行処理と並列処理

並行処理（Concurrent Processing）

複数の処理を同時に実行すること。ただしある瞬間には1つの処理だけを実行している。シングルコアCPUで実装可能。擬似的に同時に進んでいるように見える。普通の人の頭は並行処理しかできない。

並列処理（Parallel Processing）

複数の処理を同時に実行すること。ある瞬間に複数の処理を実行している。マルチコアCPUやマルチプロセッサー、GPUなど、ハードウェアのサポートが必要。伝説によれば聖徳太子の頭では並列処理ができたようだ。

同期処理と非同期処理

通常、コンピュータプログラムは休む暇なく次から次へと処理を実行するが、どうしても休まざるを得ないこともある。代表的なのが I/O だ。ユーザーの入力を待つ、ファイルへの書き込みを待つ、ネットワーク経由でデータを取得する、タイマーの設定時間を待つなど、CPU とは桁違いに遅い処理を実行するときに待ちが発生する。

このときにじっと待つのが同期処理（Synchronous Processing）で、一時的に中断して別の処理に実行の機会を譲るのが非同期処理（Asynchronous Processing）である。

協調的なマルチタスキングと非協調的なマルチタスキング

1945年に誕生した ENIAC をはじめとして初期のコンピュータは、電気配線の組み替えでプログラムを表現するにせよ、紙のパンチカードでプログラムを表現するにせよ、一回に一つのプログラムのみロードして実行する機械であった。一つのコンピュータに複数の端末をつなぎ、各端末に少しずつ実行時間を割り当てて高速に切り替えるタイムシェアリングシステムが1960年代始めに実用化されると、人間が考えながらコンピュータへプログラムを入力するような対話型コンピューティングが可能になった。複数のプログラムに実行時間を細切れで与えて処理が並行して進められるマルチタスク機能は、1971年に誕生したUNIXにも受け継がれた。

一つのプログラムが自主的に処理を中断して、他のプログラムに実行機会を譲る方式を協調的なマルチタスキング（Co-operative multitasking）と呼ぶ。一方、強制的に実行中のプログラムを一時停止させて他のプログラムを実行する方式を非協調的なマルチタスキング（Preemptive multitasking）と呼ぶ。タイムシェアリングシステムは preemptive システムの一種であり、UNIXをはじめとする多くの OS のプロセス管理も preemptive である。例外として、たとえば 1990年にリリースされた Windows 3.1 は co-operative multitasking を採用していたため、実行中のプログラムの一つがシステム全体をフリーズさせることがあった。

プロセスとスレッド

現代の OS上で動作するプロセスは preemptive なマルチタスクで動作している。一つのプロセス内でマルチタスクを実現したい場合は、スレッド（Thread）を用いる。OS が各プロセスに割り当てる読み書き可能なメモリには、スタックとヒープの2種類がある。プロセス内でスレッドを立ち上げると、各スレッド毎にスタック領域が割り当てられる。ヒープ領域はスレッド間で共有する。


一つのプロセスに割り当てられるメモリのレイアウト

一つのアプリケーションを一つのプロセス、一つのスレッドで実装するか、一つのプロセス、複数のスレッドで実装するか、複数のプロセスで実装するかは、アプリケーション開発者の任意である。例えば複数のクライアントを同時に相手しなければならないウェブサーバーは、マルチプロセスかつマルチスレッドで動作するのが通例だ。最近のウェブブラウザはタブで複数のサイトを同時に利用できるが、2022年時点の Chrome の場合はデフォルトでサイト毎にプロセスを立ち上げる ようになっている。

ウェブブラウザはシングルスレッド

ウェブブラウザの一つのタブは、<iframe> や Web Worker を用いない限りはシングルスレッドで動作している。画面のレイアウトも画像の表示も JavaScript の実行も、全て一つのメインスレッドで処理する。

そのため、以下のような行儀の悪い JavaScript が含まれていると、そのタブはフリーズする。

<html>
<body>
<script type="text/javascript">
while (true) {}
</script>
<p>test</p>
</body>
</html>

リモートのウェブサーバへリクエストを送るなどの、I/Oにアクセスする関数を呼んだときに、I/Oの処理終了待ちでプログラムが一時的に止まることを「ブロックする」と表現する。I/O操作にはブロッキングAPIとノンブロッキングAPIがある。ブロッキングAPIは同期処理、ノンブロッキングAPIは非同期処理とも呼ばれる。

シングルスレッドである JavaScript は、全てがノンブロッキングAPI、つまり非同期処理で構成されている。例外として alert() 関数や synchronous XHR が挙げられるが、2022年現在、どちらもあまり利用されなくなっている。

AJAX を実現する手段として、1999年に原型が誕生した XHR（XMLHTTPRequest）はよく使われていたが、いま新たに作られるWebアプリケーションは、2015年ころに誕生した後進の fetch API を使うのが普通だろう。

JavaScript の非同期処理

JavaScript で非同期処理を実装する方法はいくつかある。一番最初に使われていたのが callback だった。

setTimeout(() => {
  console.log('called');
}, 1000);

1秒後にコンソールに called と表示するプログラムだ。ちなみに setTimeout は JavaScript の機能ではなく、ブラウザの window オブジェクトが提供する機能である。

これだけならシンプルだが、複数の非同期処理を順番に実行したい場合、Callback地獄（Callback Hell）と呼ばれる見通しの悪いコードになる。

function increment(x, callback) {
  setTimeout(() => {
    callback(x + 1)
  }, 1000)
}

increment(0, (first) => {
  increment(first, (second) => {
    increment(second, (third) => {
      increment(third, (fourth) => {
        console.log(fourth)
      })
    })
  })
})

Callback hell を解消するために JavaScript（ECMAScript 2015）に導入されたのが Promise だ。

const increment = (value) => {
  return new Promise((resolve, reject) => {
    setTimeout(() => resolve(value + 1), 1000)
  })
}

increment(0)
  .then((value) => increment(value))
  .then((value) => increment(value))
  .then((value) => increment(value))
  .then((value) => console.log(value))

だいぶ見通しが良くなった。

ちなみに Promise（約束）という言葉は Daniel P. Friedman と David Wise が 1978年に初めて使用し、Barbara Liskov と Liuba Shrira がプログラミング言語の要素として持たせることを 1988年に提唱している。Liskov は「リスコフの置換原則（Liskov Substitution Principle）」として、オブジェクト指向言語の根幹をなす概念の提唱者としても名を残している。アメリカの大学でコンピュータサイエンスの博士号を取得した初めての女性でもある。

from Medium
https://medium.com/a-computer-of-ones-own/barbara-liskov-inventor-of-abstract-data-types-9f8908fdcf86

Barbara Liskov MIT computer scientist 2010

ECMAScript 2017 では、async/await が導入された。これは Promise のシンタックスシュガーであるが、非同期処理を同期処理のように書けるため、さらに見通しが良くなる。

const increment = (value) => {
  return new Promise((resolve, reject) => {
    setTimeout(() => resolve(value + 1), 1000)
  })
}

const doIncrements = async () => {
  let value = await increment(0)
  value = await increment(value)
  value = await increment(value)
  value = await increment(value)
  console.log(value)
}

doIncrements()

並行処理の実現方法

並行（Concurrent）、並列（Parallel）処理の実現方法は、多数存在する。

  • マルチプロセス（preemptive）
  • マルチスレッド（preemptive）
  • イベントループ（co-operative）
  • 非同期処理（asynchronous）
  • コルーチン（coroutine）、ファイバー（Fiber）
  • ベクトル演算、GPU

非同期処理については既に述べた。以下ではイベントループとコルーチンについて触れてみよう。

イベントループ

GUIシステムはUIの描画やユーザーからのマウス、タップのイベントをイベントループで処理している。これはウェブブラウザでも Android でも Windows でも同じで、現存する GUIシステムのほとんどはイベントループ方式を採用している。

擬似コードでイベントループを表現すると、以下のようになる。

event = messageQueue.nextEvent()
while (event != null) {
    process(event)
    event = messageQueue.nextEvent()
}

イベントはメッセージキューに格納され、FIFO (First in, first out) で取り出される。キューにメッセージが無ければ nextEvent() はブロックする。GUIの場合、このループは、必ず一つのスレッドで実行される。画面の描画やユーザーイベントを並行で処理すると前後関係が崩れて意図した結果が得られない。キューにイベントを追加する処理はどのスレッドから実行しても構わないが、キューからイベントを取り出して処理するのは、特定の一つのスレッドに限定する必要がある。

ウェブブラウザはウィンドウ単位でイベントループを持っている。シングルスレッドでこのイベントループを動かし、画面の描画からユーザーイベントの処理まで全てを受け持っているので、重い処理やブロックするような処理を実行すると、ウインドウ全体が停止する。

JavaScript はシングルスレッドであるものの、時間のかかる処理のほぼ全てが非同期APIとして提供されていて、ブラウザが用意した API によりネットワークリクエストを並行実行することも簡単にできるようになっている。当初はシングルスレッドだった JavaScript ではあるが、現在は Web worker によってマルチスレッドを利用することも可能になった。

MacOS、iOS の GUI もメインスレッドでイベントループを実行するという構造になっている。マルチスレッドが利用可能なため、重い処理はスレッドを作成して UIのメインスレッドとは並行して実行させる必要がある。自前でスレッドを作成することも可能ではあるが、多くの場合、2009年の MacOS 10.6、2010年の iOS 4 で利用できるようになった GDC（Grand Central Dispatch）を利用することになる。メインスレッドのメッセージキューとは別に、他のスレッドで処理される複数のメッセージキューが優先度別に用意されているため、開発者自らスレッド管理をすることなく、キューにメッセージを送るだけで並行処理できるようになっている。Apple によると、GCD のキューにメッセージを入れるのは CPU の命令数にしてわずか 15個で実現できる非常に軽い処理である一方で、スレッドを立ち上げるのは数百個の命令を実行する重い処理であるという。素晴らしい軽さと使い勝手を持つ GCD ではあるが、複数の処理を順番に実行したい場合、JavaScript のところで説明した Callback hell のようなネストされたコードになりがちという弱点がある。それを解消するのが、2021年の Swift 5.5 で GCD を置き換えるものとしてサポートされた async/await である。

Android もマルチスレッドであるが、GUI はやはりメインスレッドのイベントループで処理している。Apple の GCD と同様に、メインスレッドのメッセージキューの他、I/Oスレッドで処理される I/O用のメッセージキュー等が用意されている。ネットワーク処理などは I/Oスレッドで実行しないと例外が発生するし、I/Oスレッドで UIの処理を実行しても例外が発生する。

GUIの実現手段としてのイベントキューの歴史は古く、Xerox Alto 上で動作した Smalltalk-76 には、既にユーザーイベントを集中管理する EventQueue が実装されている。Apple は 1976年に Apple I を、1978年に Apple II を発売しており、1978年には後継の Lisaプロジェクトを開始した。1979年に Xerox PARC にて Alto上で動作する Smalltalk-76 を見学して衝撃を受けた Steve Jobs は Lisa に同様の機能を持たせることを決意した。Lisa は GUI を備えた世界初のパーソナルコンピュータとして 1983年に発売された。途中で Lisaプロジェクトを追い出された Steve Jobs は Macintoshプロジェクトに加わった。GUI の概念は、Lisa の翌年1984年に発売された Macintosh にも受け継がれた。Lisa は US$9,995 だったが、最初の Macintosh (128K) は US$2,495 だった。Lisa と Macintosh は同じ CPU を使っていたが、Lisa の CPUクロックが 5MH であるのに対して Macintosh は 8MHz だった。そして Lisa が co-operative multitasking を実現していたのに対し、Macintosh はシングルタスクだった。Macintosh の方が安く、動作が軽かった。Lisa は商業的に失敗し、Macintosh は成功した。


SUMIM.ST, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons

Class new title: ’EventQueue’
    subclassof: Queue
    fields: ’primitivequeue readwriteelapsed time’
    declare: ’read elapsed write ’;
    asFollows

The EventQueue (Events) is a subclass of class Queue. It contains a regular queue which is filled from a block of memory (currently 128 words long), updated during the 60HZ interrupt. This block of memory is called the primitivequeue, and is unpacked into the regular queue when events are available upon receiving the message peek or next. The fundamental difference between peek and next is that next dequeues the current event and peek does not. Furthermore peek will return false when the queue is empty, and next, when the queue is empty, will create a time elapsed event and return that. An event will be of class UserEvent as created by the primitiveDequeue and next messages. The machine code thinks of events as a 4-word structure as follows:

Word 1:
    Left Byte:
        1 = Key down. 0 = Key up.
    Right Byte:
            8-bit Ascii value.
                    Mouse Buttons:  Left/Top        =    0
                                    Middle          =    1
                                    Right/Bottom    =    2
                    Keyset:         Leftmost        =    3
                                                    =    4
                                                    =    5
                                                    =    6
                                    Rightmost       =    7
                    Values 8 - 255, keyboard decodings as expected by rawkbd.

Word 2:             Time (sixtieths of a second since last event).

Word 3:             Cursor x coordinate (UserView htab accounted for).

Word 4:             Cursor y coordinate (UserView vtab accounted for)..

https://smalltalk76.com/0012-Events.st.html

Coroutine

2010年代から、スレッドよりも軽量であるとの触れ込みで Coroutine という並行処理技術が注目され始めた。2009年に登場した Go の Goroutine は Coroutine の一種である。

スレッドが多くの場合 preemptive なのに対して、coroutine は co-operative である。Coroutine は concurrency を提供するが、parallelism は提供しない。Coroutine は関数を一般化したもので、関数の処理を特定の場所で中断（suspend）し、ネットワーク経由でレスポンスを受け取るなど、中断する理由が無くなった後に再開（resume）することができる。

Coroutine は 1958年に Melvin Conway が提唱した用語で、マルチタスクをアセンブラで実装する手段として 1960-1980年代には一般的だった。多くの CPU は、coroutine の実現手段を命令レベルで持っているが、1972年に誕生した C をはじめとする高級言語のほとんどが coroutine を直接サポートしなかったこともあり、2000年代に入り CPUクロック数の高速化が頭打ちになってマルチコア化が進むと、処理のパラレル性を高めるためにスレッドが重用されるようになった。1995年に誕生して2000年前後に大流行した Java が、標準ライブラリとしてスレッドを備えていたのも大きかったと思われる。1993年に誕生した Lua での coroutineサポートなどの例外はあるものの、世の大勢として、coroutine は使われていなかった。

Concurrent programming の手法として Coroutine は一旦忘れ去られたが、2010年代に入り、スレッドよりも軽量な並行処理方法として再び注目されるようになった。

  • 1993年：Lua
  • 2009年：Go (goroutine)：元々は co-operative だったが、2020年の Go 1.14 で preemptive になった。
  • 2015年：JavaScript (ECMAScript 2015, ES6 の yield)
  • 2017年：Kotlin coroutine
  • 2021年：Swift 5.5 async / await