やる気がストロングZERO

やる気のストロングスタイル

並行プログラミング入門を読んだ

並行プログラミング入門を読んだ

日本人が書いたということで読みやすかった。

1章 並行性と並列性

並行性と並列性の定義や、並列性の種類(タスク並列性・データ並列性・インストラクションレベル並列性)などについて、CPUレベルで行われいてる並列実行についてや、並列処理の複雑さの存在についてなど、サクサク飲み込める感じで説明してくれていた。

並列処理がどのように実行されているかが、より具体的にイメージできるようになった。

2章 プログラミングの基本

アセンブリ言語C言語とRust言語の、この本で必要になると思われる部分の知識をざっくり説明。 C言語にてメモリの変化を検知させるまで待ち受ける処理を普通に書くと、コンパイラによる最適化によって意図通りの挙動をしなくなる話が面白かった。

Rust言語について初見だったが、変数の所有権や状態遷移など並行プログラミングにかなり気を使った機能が存在するようだった。

3章 同期処理1

並行処理を行うと発生する不整合(レースコンディション)についての説明と、これを発生させないために並行しているプロセス間で同期処理の種類や仕組みの説明。

cpuレベルでアトミックに処理できる命令が存在している。

  • Compare and Swap
  • Test and Swap
  • Load-Link / Store-Conditional

並行処理を実装する時に「比較検証と値のセットをアトミックに行う」ライブラリ関数を叩いた経験はあったが、cpuレベルで命令が存在しているとは知らなかった。

このような命令を(おそらく)使って以下のような同期処理の概念が存在している

ミューテックス
メモリを使って1度に1プロセスしかクリティカルセクションを実行しない。
自分で実装する場合はコンパイラによる最適化に注意する。(フラグに使うメモリをキャッシュしてしまい、いつまでもロックが開放されない状態に陥る)

■ スピンロック
ロック開放を待つ間、ループで待つこと
愚直にやるとコストが高い(大量にフラグチェックをおこなう為)のでライブラリなどはうまいこと調整をしてるらしい

セマフォ
クリティカルセクション(同時実行制御する対象のセクション)を同時実行できる数(複数指定可能)を指定できるミューテックス

■ 条件変数
他のスレッドから通知を受けるまで処理を待機するスレッドに使う

■ バリア同期
全員揃ってから続きを実行

■ Readers-Writerロック
書き込みが行われないのであればレースコンディションの問題は起きないはずなので、読み込みの場合は並行同実行OK、書き込みが行われる場合は1プロセスでの排他制御するようなロックの仕方。


それぞれの実行速度についての検証もやってた。
やっぱり排他性が強いとスレッド数を増やしてもパフォーマンスはあまり伸びない。

4章 並行プログラミング特有のバグと問題点

並行プログラミング時に発生するバグについて解説。

デッドロック
DBでも身近な、双方がロック解放待ちになり処理が進まなくなってしまう状態のこと。

■ ライブロック
デッドロックを回避するためにリトライ処理など入れた時、処理としては動き続けているが全部のプロセスがリトライし続け、処理としてはまったく進まなくなってしまっているような状態

■ 飢餓
片方のプロセスがずっと処理され続けて、もう片方のプロセスが全く処理されないなどの状態。

■ 銀行化のアルゴリズム
リソース開放を待ち合ってデッドロックに陥る状態を回避するためのアルゴリズムの紹介

■ 再起ロック
ロックしているプロセス内で再起的に同じロックを取ろうとするとデッドロックする。(ロックをしているのは自分だが、処理が完了しないとロックが開放されず、ロックが開放されないと処理を完了できない)
その回避方法(カウンターを使ったロック実装)も説明されている。

■ 疑似覚醒
条件変数による「待ち」を行っている際に、意図せず処理が進捗してしまう現象について説明

■ シグナル
シグナルによる割り込みが絡んだデッドロックの説明と回避方法の説明

■ メモリバリア
cpuはパフォーマンス向上のためアウトオブオーダー実行と呼ばれる、指定された命令順序に沿わずに命令を実行する場合がある。 (メモリ読み込みにはコストがかかるため、待ってる間に次の命令を実行するなど)

これが原因でレースコンディションが発生する可能性があるためアウトオブオーダー実行を制御するcpu命令があり、それについての説明。

おそらくライブラリや言語に用意されている同期関数などは、こういった考慮が行われているのだと思う。

5章 非同期プログラミング

非同期プログラミングがどういうものかという解説と、非同期プログラミングを実現する方法の一例である「OSによるIO多重化」「Future」「async/await」について解説している。
基礎知識があまりなかったので、理解しながら読み進めるのに苦戦した。(まだ理解しきれていない部分もある)

■ 並行サーバー

同期プログラミングで構築され、リクエストを順にしか裁けないサーバーを反復サーバー、非同期プログラミングで構築され、リクエストを並行に捌けるサーバーを並行サーバーと呼んでいる。 ポートと待受けファイルディスクリプタの動きを見ながらのIO多重化の説明もある。IO多重化のお陰で、随時投げられるリクエストをすべて並行に受け付けることができるイメージが掴めた。

■ コルーチンとスケジューリング

コルーチンの説明と、コルーチンの継続実行を自動スケジューリングするイメージの説明。

このあたり、基礎知識がなく理解がなかなか進まなかったのだが、僕が「コルーチン」「並行処理」あたりをアバウトに結びつけてしまっていたのが原因っぽかった。

だいぶ調べてなんとなくわかってきたが、コルーチン自体はべつに並行処理のための仕組みというより、ただ単に「関数を任意の位置で中断し、任意のタイミングで途中から継続実行させることができる仕組み」でしかないっぽい。
これはイテレーターとかのために用意された仕組みだが、便利なので並行処理(async/await)でもベースとして利用されている、という感じのようだ。

コルーチン自体は並行処理とは関係ないが、もちろん処理を別スレッドで実行するように書いてやることは可能で、特定の処理が完了したタイミングで次の処理を継続実行してやるように組めば(このあたりがスケジューリングにあたる部分)、それがasync/awaitになる、というような感じなのかと理解した。

■ async/await

async/awaitの中心になるオブジェクトであるFutureについての説明など。

async/awaitを使うとコールバック地獄に陥りがちな非同期処理を逐次処理っぽくかけて理解しやすいコードになるとのこと。

後半のIO多重化とasync/awaitはちょっと読みきれず。。後ほどリトライ予定。。

■ 非同期ライブラリ

Rustのasync/await非同期ライブラリの紹介と使い方の紹介。 他にも注意点などの説明

6章 マルチタスク

1cpuで複数のプロセスを同時に処理(並行処理)する仕組みについての解説とRustによる実装例。
自分でこれを実装する機会はあまりないのかなと思うが、コードで示されることでOSやライブラリがどういうことを行っているのかがイメージできるようになった。 ユーザーランド(カーネルよりもこっち側、と理解している)で実装するスレッドを「グリーンスレッド」と呼ぶらしい。

マルチタスク 1cpuで処理するタスク・プロセスを切り替えるイメージについてジキルとハイドの人格入れ替えと紐づけて説明。

  • 公平性: すべてのタスクは公平に処理されるが、強い公平・弱い公平という概念がある
  • 強調的マルチタスキング: 各タスクが自分でタイミングを制御して別タスクにリソースを回しあうような手法。一つのタスクに欠陥があると他のタスクにリソースが回らない可能性がある
  • 非協調的マルチタスキング: 各タスクの事情を考慮せず、外部から強制的にリソースの受け渡しを制御されるような手法。一つのタスクに欠陥があっても別タスクにリソースを回せる

■ 協調的グリーンスレッドの実装

Rustで協調的グリーンスレッドを実装している。

アセンブリでCPUレジスタの値を直接読み取ったり書き込んだりしてプログラムの実行ポイントを切り替え制御しているのを見たとき、裏技っぽいというかCPUを騙しているというか、CPUは入力された処理をただこなしていくだけなんだな、というのがなんとなく理解できた。

アクターモデルの実装

上記で実装されたグリーンスレッドを、アクターモデルで動作するように追加実装する。 アクターモデルはスレッド同士がメッセージキューを介して協調動作するような構造のことを言うらしい。

7章 同期処理2

スピンロックやミューテックスを使えば基本的な動機はできるが、デッドロックや飢餓状態が起こる可能性には気をつけなければならない。 公平性やデッドロックをうまく解決する同期アルゴリズムについての説明。

■ 公平な排他制御

公平に実行リソースを渡すアルゴリズムをRustで説明している。 また、1つの共有資源を多数のスレッドが監視するとパフォーマンスが落ちるので、そのあたりを解決するアルゴリズム(MCSロック)についての解説がある。

■ ソフトウェアトランザクショナルメモリ

楽観的ロックとそのアルゴリズムについての説明。 「ロックが開放されるのを待つ」のではなく、とにかく実行してしまって(投機的実行)完了時に競合を検知すれば切り戻したり、再実行したりする手法。

■ ロックフリースタック

排他ロックを使わずに(楽観的ロックを使った)並行処理を行うデータ構造とアルゴリズムの説明で、スタックを例に説明している。 変更自体はCAS命令でアトミックに行う。

このとき起こり得る問題としてABA問題(競合チェックを値で行って問題を生じる)を解説し、解決方法としてLL/SC命令を用いた方法(値の変更ではなく、本質的に変更があったかどうかを見る)を解説している。(アセンブリを書いて実現してるようでかなりCPU依存なイメージ)

ロックフリーデータ構造をマルチスレッドで使うとデータ削除で問題がある場合があることが解説されている。

最後にロックフリーの分類(排他ロックフリー・ロックフリー・ウェイトフリー)についてのコメントがある。

8章 並行計算モデル

並行性と並列性の数式的な定義についての章っぽい。   個人的に数式での解説での理解効率がよくないため、今回は読むのを諦めてしまった。
いつか数式への苦手意識を克服してからまた挑戦しようと思います。