【技術本】並行プログラミング入門
【技術本】並行プログラミング入門
https://amzn.to/40Rc2Rw
【技術本】並行プログラミング入門
へポスト
前提知識で以下の言語の基本知識、実装力が求められる。
・C言語
・RUST言語
・アセンブラ：少々
本の導入部は、並行処理の必要性から、並行プログラミングを実装で証明するためのC言語、RUST言語の説明まで、前提知識をざっくり紹介するところから始まる。言語紹介といっても、言語の基本構文をすでに理解している前提の内容である。
その後、並行プログラミングにおける同期処理の方法として、ミューテックス、スピンロック、セマフォ、バリア同期、Read-Writeロック、条件変数などを実装を踏まえ紹介し、パン屋のアルゴリズム（チケットを配ってその番号が最小の人に実行権が与えられるもの）を実装を踏まえ紹介している。また、楽観ロックを使った内容も実装を踏まえ紹介してくれている。
並行プログラミング特有のバグと問題点に関しては、デッドロック、ライブロック、餓鬼、再帰ロック、再入ロック、擬似覚醒、シグナル、アウトオーダ実行問題に対応するためのメモリバリアなどを実装を踏まえ紹介してくれている。
非同期プログラミングとして、RUSTのasync/awaitを利用した簡易エコーサーバでの並行処理を実装を踏まえ紹介。
マルチタスクにおいては、協調マルチタスクと、非協調マルチタスクのそれぞれの利点、欠点を踏まえ、実装紹介。
最後に並行計算モデルとして、アクターモデル、π計算の2つのモデルを実装を踏まえて紹介している。
並行プログラミングで必要な同期、非同期処理、マルチタスクの方法と、並行プログラミングにおけるレースコンディションなどの問題点という感じで、実現するために肝となる必要技術と、注意すべき問題点を簡潔に章単位でまとめてくれている。そして最後の総仕上げで知識を総動員した並行計算モデルを利用した実装へと、無理なく順を追って理解を進めることに配慮してくれている構成だと感じた。
並行プログラミングに興味がある人で、C,RUSTを使える人に価値が出てくる著作だと感じた。
------
以下、内容メモ
１章：並行性と並列性
プロセス：実行状態＞待機状態へ遷移する理由
１：処理するためのデータ到着を待つため
２：処理のリソースの空きを待つため
３：自発的に待機状態になるため>リソース占有回避
プロセス
プロセス毎に独立した仮想メモリ空間
スレッド
プロセスの中でスレッドが生成。プロセスのメモリ空間を共有。
並行性
複数のプロセスが同時に計算を進めている状態
＊それぞれのプロセスにおける実行状態、待機状態も含んだ期間の全体を指す
並列性
同じ時刻で、複数のプロセスが同時に計算を実行している状態
＊複数プロセスの同時時間に実行状態になった期間を指す
＞並行の中の、さらに同時実行されている期間が、並列
タスク並列性
複数のタスクが同時実行されること
データ並列性
データを複数に分割して、分割したデータに対して並列に処理する方法
ベクトルva=[1,2,3,4]とベクトルv2=[5,6,7,8]の加算を考える
v1+v2 = [1+5, 2+6, 3+7, 4+8]
= [6, 2+6, 3+7, 4+8]
= [6, 8, 3+7, 4+8]
= [6, 8, 10, 4+8]
= [6, 8, 10, 12]
もし演算器が４つあったら、それぞれの計算を4つの演算器で別々に計算させれば高速になる。
Interl CPUのAVX命令：ベクトル演算用の命令
アムダールの法則：一部処理の並列化が延滞的にどの程度高速化するか予測する法則
式：1/((1-P)+P/N)
一般的に、並列か不可能の割合が、並列可能な処理の割合よりも十分小さい時に、並列化
による高速化が有効に働く。
オーバヘッドを考慮した式
式：1/(H+(1-P)+P/N)
インストラクションレベル並列性
CPUの命令語レベルで並列を行う手法
ハードウェアやコンパイラが暗黙的に行う並列化
＞ループの条件文が原因で並列性が下がる＞ループを展開で対応
＞メモリプリフェッチ：メモリ読み込み（コストが大きい）と演算を並列にできる
パイプライン処理
命令実行を5つに分割すると以下になる
・命令読み込み
・命令解釈
・実行
・メモリアクセス
・書き込み
それぞれをパイプラインステージと呼ぶ。
分割する数のことをパイプライン段数とよぶ。＞段数５
ステージを一つずつずらすことで、複数の命令を同時実行できる。
しかし、並列に実行できない（パイプラインハザード）は以下の条件があるので注意。
・構造ハザード：ハードウェア的に同時アクセスできない場合
・データハザード：データ依存がある場合。命令１の結果を続く命令２で利用する時
・制御ハザード：条件分岐がある場合。命令２が命令１の結果によって実行が決まる時
並行と並列処理の必要性
マルチコアCPUの対等で、ソフトウェア側でも対応が必要になった。
半導体素子の微細化＞クロックを上げられる＞しかし消費電力が多くなり発熱が多くなる
＞半導体劣化が早まる＞動作周波数ではなく電圧を下げることで消費電力と発熱の問題を
対処
次は、半導体素子の微細化が進みすぎたため、リーク電流が問題になる。
リーク電流：勝手に漏れ出してしまう電流＞発熱、誤動作の原因
リーク電流は、量子トンネル効果で起きている＞対策は半導体素子を大きくするか、電圧を上げる必要がある。
このように、リーク電流に関する問題が、どれも限界に達したため、CPUは動作周波数の高速化から、マルチコア、メニコアCPUという方向に進化していった。（２０００年代前>半から中盤にかけてから）
並行処理のパス爆発
4つのプロセスの並行処理でも、処理順は２４通り（４の階乗）
デバッグが大変
>並行プログラミングの動作原理と理論モデルを学ぶ必要あり
-------
２章：プログラミングの基本
アセンブリ言語の基本
add x0 x1 x2; x0 = x1 + x2
ldr x0, [x1]; [x1]のメモリの値をx0に書き込み
str x0, [x1]; [x1]のメモリへx0の値を書き込み
mov x0 x1; x1の値をx0にコピー
x86-64アセンブリの基礎
add1 %ebx, $ecx; ebxとecxを足して結果をeaxに保存
movq %rbx, %rcx; rbxの値をrcxにコピー
movq(%rbx), %rax; rbxの指すメモリ上のデータをraxに転送
movq %rax, (%rbx); raxの値をrbxの指すメモリに転送
C言語
Pthreads:POSIX標準のインタフェースを備えるスレッドライブラリの総称
volatile修飾子：コンパイラの最適化を制御(あえて最適化させない)したメモリアクセスを実現できる
この修飾子をつけた変数は、コンパイラ最適化により、メモリからレジスタに読み込み、以降、メモリから参照しなくなる。
＞これが、複数のプロセスから同一メモリにアクセスを行いたい場合に、コンパイラの最適化によって、メモリアクセスを行わなくなってしまう問題が発生する。
＞並行プログラミングを難しくしている要因のひとつ。
immutable変数：破壊的代入が許されない変数
mutable参照
void wait whie_0(int *p){
while(*p == 0){}
}
void wait while_0(volatile int *p){
while(*p == 0){}
}
スタックメモリとヒープメモリ
・スタックメモリ：関数のローカル変数を保存するメモリ領域
高アドレスから程アドレスへと成長していく（積み上げ）
関数が呼び終わると解放される
・ヒープメモリ：関数のスコープに依存しないようなメモリを動的確保するメモリ領域
int *tmp = (int*)malloc(sizeof(int));
関数がリターンされた後でも値は存在。freeを呼び出すと解放
Rust言語：：：
FireFoxなどで採用
静的型づけ言語：型安全な型システムを備えている
＞型安全なプログラミングとunsafeなプログラミングをバランスよく記述できる
let文：変数定義
match式：switchにちかい。パターンマッチの機構を実現するもの
loop文：while(1)の代用>ループ内でif文で終了条件によりループを抜ける
参照取得と参照外し
関数ポインタ
クロージャ：関数のことであり、関数本体に加え関数の外でキャプチャされた自由変数の値も含んでいる。
所有権
ライフタイム：変数の生存期間
所有権の借用
＞所有権、所有権の借用を駆使して、並行処理における計算パス数爆発に対して制約を設けることで、状態管理を容易にしてバグを軽減させている。
借用を理解する上で重要な点：以下4つを理解する
mutable変数：破壊的代入可能な変数
immutable変数：破壊的代入が許されない変数
mutable参照
immutable参照
メソッド定義：関数定義
トレイト：javaでいうインタフェースとHaskellの型クラスの合いの子の機能
?演算子とuwarp
スレッド
-------
３章：同期処理１
並行処理は完全独立でなく、協調動作が必要＞タイミング同期、データ更新など＞同期処理
レースコンディション問題：
競合状態
複数プロセスが並行して共有リソースにアクセスした結果引き起こされる、予期しない異常な状態のこと
>並行プログラミングでは、これをいかに回避して正しくプログラミングするかが課題。
アトミック処理
不可分解操作＞途中状態はシステム的に観測されず、その処理が失敗した場合は完全に処理前の状態に復元される。＞正しく処理されたか、されないかのどちらかのみ
Cのアトミック処理
CAS関数（Compare and Swap）
__sync_bool_compare_and_swap(p, val, newval)
TAS関数（test and set)
__sync_lock_test_and_set(type *p, typr val)
CPUアーキテクチャ
Load-Link/Store-Conditional(LL/SC)命令がアトミック処理の実装に用いられる
＞競合した場合は書き込み失敗させ、もう一回操作を行うことで、見かけ上はアトミックに処理できる。
ミューテックス(MUTtual EXecution > mutex)の略
排他実行処理
事項可能なプロセスの数を高々一つに制限するような同期処理
排他実行のために共用フラグで判定する
＞TAS関数でmutexを実装例
スピンロック
ロックを取得できるまでループを繰り返し、リソースの空きをボーリングして確認するようなロックの獲得方法
＞TAS関数での実装例
一般的にアトミック命令は実行速度上のペナルティが大きいので、TASを呼び出す前に検査してからTASを行うよう改良すべき>これをTTAS(Test and Test and Set)呼ぶ
void spnlock_aqcuire(volatile bool *lock){ //valatileで*lockをメモリ最適化対象か
ら外す
for(;;){
while(*lock); //TAS前の検査
if(!test_and_set(lock))i //TAS呼び出し
break;
}
}
セマフォ
ミューテックスはロックを獲得できるプロセスは最大１つであった。
セマフォは、最大Nプロセスまで同時にロックを取得できる。
N=事前定義しておく値
条件変数
ある条件が満たされない場合＞プロセス待機
条件が満たされた場合＞待機中プロセスを実行
プロセスを待機したり実行するための交通信号（青と赤で通行を制御）みたいなものを条件変数と呼ぶ
バリア同期
全て揃ってから実行するといった同期をとるものをバリア同期という。
>スピンロックベースのバリア同期実装例
>PThreadsベースのバリア同期実装例
Reader-Writerロック
読み込みのみうプロセス(Reader)と書き込みのみ行うプロセス(Writer)に分類して、以下の制約を満たすように排他制御をする。
・ロックを獲得中のReaderが同時刻に複数（０以上）存在可能
・ロックを獲得中のWriterは同時刻に最大一つのみ存在可能
・ReaderとWriterが同時刻にロック獲得状態にならない
＞スピンロックベースのRWロック実装例
＞PThreadsベースのRWロック実装例
Rustの同期処理ライブラリ
・mutex
・条件変数
・RWロック
・バリア同期
・セマフォ
パン屋のアルゴリズム
アトミック命令をサポートしない場合の、後ミク命令を利用しない同期処理手法
その代表的アルゴリズム＞レスリー・ランポートのパン屋のアルゴリズムの紹介
日本では、病院や市役所でも用いられているアルゴリズム
はじめに受付を行い、その後に番号を記されたチケットを渡される。そのチケットは自分の優先順位を表しており、他の待っている人の知見と番号より、自分の番号が最も小さい
時に診察などを受けることができる、というアルゴリズム。
>RUSTでの実装例
-------
４章：並行プログラミング特有のバグと問題点
デッドロック
＞データベース処理でもおなじみ
>Reader-Writerロックでの再現例
ライブロックと餓鬼
ライブロック：リソースが獲得できずに次の処理が行われない状態
餓鬼：特定プロセスのみが、リソース獲得状態へ遷移しないような状態のこと
再帰ロック
ロックを獲得中のプロセスが、そのロックを解放前に、再度そのロックを獲得すること
再入可能ロック
再帰ロックを行ってもデッドロック状態に陥らず、処理を続行可能なロック機構のこと
擬似覚醒
ある条件が満たされるまで待機中のプロセスが、条件が満たされていないにかかわらず実行状態へ移行すること。
C言語＞wait中のシグナル割り込みが原因で、擬似覚醒が起こる
シグナル：割り込み
メモリバリア
アウトオーダ：機械語の命令順に処理は行われない実行方法
メモリ上にあるものより、キャッシュライン上にあるものを優先することで、単位時間あたりの実行命令数(IPC: instructions per second)を向上できる。そのため、機械語の並びを無視してキャッシュライン上の処理を優先する場合がある。それがアウトオーダ実行。
これは、並行処理中ではいくつかの問題を引き起こす＞それを保護するための処理がメモリバリア
------
５章：非同期プログラミング
処理中に発生する別の事象＞イベント、割り込み
同期プログラミング：記述順の順番通りに実行する
非同期プログラミング：割り込みがあったら随時受け取り、イベントに応じた動作を記述
できる。処理順は、イベント発生順になる。
実現方法は、コールバック、シグナル（割り込み）などを利用
並行サーバ
反復サーバ：クライアントからのリクエストを受け付けた順にしか処理しないサーバ
並行サーバ：リクエストを並行に処理するサーバ
コルーチンとスケジューリング
コルーチン：中断と再開ができる関数の総称＞任意の時点で中断と再開
yield
スケジューリング：中断と再開をスケジューリングして行うこと
async/await
非同期プログラミングを行うための言語機能
Rust version1.39以降で対応
非同期ライブラリ
Rustのasync/awaitによる非同期ライブラリのデファクトスタンダード＞Tokio
＊async中にブロッキングコード(sleepなど）を行うコードを記述すると、実行速度の劣>化やデッドロックが起きてしまう。＞悪い例
-----
６章：マルチタスク
プロセスの数がCPUより多い場合にどのように動作させるか
マルチタスクと並行はほぼ同じ意味
あるプロセスがCPUで実行中の時、そのレジスタをメモリに保存することでプロセスのあ>る時点での状態が保存される。
また、保存したレジスタをCPUへ復元することで、保存した状態に戻ることができる。
コンテキスト：レジスタ（やスタック情報）などのプロセスの状態に関する情報の事
コンテキストスイッチ：これらの一連のコンテキストの保存と復元の処理のこと
>CPUの数以上にプロセスを起動し実行できる仕組み：マルチタスク
協調と非協調的マルチタスク
協調的：プロセス短らが自発的にコンテキストの切り替えをする方法
非協調的：割り込みなどの外部の強制力によってコンテイストスイッチを行う方法
非協調マルチタスク：プリエンティブ・マルチタスキング
協調マルチタスク：ノンプリエンティブ・マルチタスキング
協調的マルチタスクの利点と欠点
利点
・マルチタスク機構の実装が簡単＞win3.1やクラシックMac OSで採用されていた
欠点
・プロセスが自発的にコンテキストスイッチをしなければならない。
＞バグでコンテキストスイッチせずに無限ループに入ってしまう
>OSクラッシュで再起動必須に・・・
Rust,Pythonのasync/awaitを用いた実装も同様の問題を抱えている
非協調的マルチタスクの利点と欠点
利点
・協調的マルチタスクで起きた無限ループなどは起きない＞他プロセスからプリエンプションされるからである。
欠点
・処理系の実装が難しい。
・公平性を保つため頻繁にコンテキスツイッチが必要でオーバヘッドが増える
アクターモデルの実装
アクターと呼ばれるプロセス同士がメッセージを交換し合う並行計算モデルのこと
------
７章：同期処理２
公平性：高速なCPUと低速なCPUでは、高速なCPU側ばかりロック取得できてしまう
それらを解決する発展的な同期処理方法について説明
公平な排他処理
・弱い公平性を担保するロック
スレッドにロック獲得優先権をもたす
リレーで優先券をバトンとして次々渡していくイメージ
次の人が用意できていなかった場合は、残りの他者で争奪させる。
・チケットロック
ロック獲得を試みるスレッドは番号の書かれたチケットを取得して、そのチケットの順番になるまで待機する。
・MCSロック
チケットロックの改良版：メモリの書き込み権限奪い合いのオーバヘッド削減
ソフトウェアトランザクショナルメモリ(STM)：：：：：：
楽観的ロックのこと
悲観的ロック：ミーテックスのようなロック
悲観的ロックは、ロック獲得しないとクリティカルセクションのコードが実行されなかったが、楽観的ロックはクリティカルセクション中のコードを投機的に実行し、実行した結果競合が検知されなければ結果をメモリにコミットする。
＊STMではクリティカルセクションのことをトランザクションという
STMの特徴
・トランザクション中のコードは２回以上実行される可能性がある
＞楽観ロックのため、競合検知後再トライする場合がある。
・トランザクション中に副作用のあるコードを実行すべきではない
・デッドロックしない
・複数のトランザクション処理を合成可能
TL2のアルゴリズム
RWロックのように、書き込みと読み込みトランザクションが分割
読み込みトランザクションは、書き込みトランザクションより高速
ロックフリーデータ構造とアルゴリズム：：：：：：：
ロックフリー：排他ロックを用いずに処理をおこおなうデータ構造とそうれに対する操作
アルゴリズムの総称
ロックフリースタック
pushとpop操作だけのリストとして実装
>ABA問題が発生する：A,B,Aと順に読み込んでも、最初と最後のAの値が同じでも意味的に異なっている場合のこと
ロックフリーの分類
・排他ロックフリー：排他ロックを用いない
・ロックフリー：排他ロックを用いない、ライブロックが起きない
・ウェイトフリー：排他ロックを用いない、ライブロックが起きない、飢餓が起きない
------
８章：並行計算モデル
以下のモデルの実装紹介
・アクターモデル
・π計算
ともにmessage passing方式
------
付録A：AArch64アーキテクチャ
付録B：x86-64アーキテクチャ
以上。
へポスト