並行プログラミング入門
パフォーマンスのある低レイヤー言語と抽象度の高い高レイヤー言語の使い分けについての著者の意見に好感がもてる
計算とは
あるデータに対して何らかの演算を行うこと
本書での「プロセス」
計算を実行する主体
何?aumy.icon
実行前、実行、待機、終了の4状態をとる
https://scrapbox.io/files/61c83ce000523d001d8d9734.png
なぜ待機するのか?
データの到着を待つ
上の「計算とは」より、データがなければ計算はできない
計算リソースの空きを待つ
自発的に待つ
タイマなど
何もする必要がないときに
OSプロセスとは、カーネルから見たプロセス
スレッドとは、OSプロセスの中にあるプロセス
各スレッドはプロセスの仮想メモリ空間とシステムリソースを共有している
プロセスごとにシステムリソースが分けられている
たとえば、プロセスAの10というファイルディスクリプタとプロセスBの10というファイルディスクリプタはほとんどの場合別ファイルを指す 複数のタスクが同時に実行される
OSプロセスやスレッドを複数のCPUで同時に実行する
データを分割して並列に処理する
ベクトル $ [1,2,3,4] と $ [5,6,7,8] を足すとき、4回の計算を4つの演算器で別々に計算させれば1ステップで計算できる
Intel CPUのAVXやGPU内部での演算など
4スレッドで並行実行するのもデータ並列性。タスク並列性でデータ並列性を実現している
インストラクションレベル並列性
インストラクション (CPUの命令語) レベルで並列化を行う
メモリプリフェッチ
メモリ読み込みしている最中に加算や減算などの演算を並列に実行する
aumy.icon へ~こんな概念があるんですね~という感じで飛ばし読みしています 並行だけに
計算パス数爆発
並行処理が$ n個あったらその実行パスは$ n!ある
そのうちの1パスだけで起きるバグがあったら?
関数のローカル変数を保存するためのメモリ領域
Rustの借用が保証すること
ある値に破壊的代入を行えるプロセスは同時に2つ以上存在しない
ある時刻で、ある値に破壊的代入できるプロセスが存在する場合、その時刻では、その値を読み書き可能なプロセスは他に存在しない
これらの保証により並行プログラミングの問題を軽減する
値を複数のプロセスで共有して更新すると状態爆発してバグの温床になる
shared-nothing
複数のプロセスで共有資源を一切持たないようにする
「ある時刻で」
code:rs
fn func() {
let mut x = Foo(10);
{
// まだミュータブル借用してないので使用できる
println!("x.0 = {}", x.0);
let a = &mut x;
println!("a.0 = {}", a.0);
// すでにミュータブル借用があるので使用できない
println!("x.0 = {}", x.0);
a.0 = 3;
// ここで値が変わっている
println!("x.0 = {}", x.0);
}
}
code:rs
fn func() {
let mut x = Foo(10);
{
let a = &mut x;
println!("a.0 = {}", a.0);
// まだ借用されていないためエラーじゃない
a.0 = 20;
let b: &Foo = a;
// すでに借用されているためエラー
a.0 = 30;
println!("a.0 = {}", a.0);
println!("b.0 = {}", b.0);
}
}
code:rs
fn func() {
let mut x = Foo(10);
{
let a = &mut x;
println!("a.0 = {}", a.0);
// まだ借用されていないためエラーじゃない
a.0 = 20;
let b: &Foo = a;
println!("a.0 = {}", a.0);
println!("b.0 = {}", b.0);
println!("b.0 = {}", b.0); // 最後の利用 ここでbが借用を返す
a.0 = 30;
}
}
オーバーヘッド
複数から参照されたときいつ解放するべきか
code:rs
use std::{thread, time};
fn f2() {
let v = 10;
let f22 = move || {
println!("thread f22 started");
thread::sleep(time::Duration::from_secs(2));
v
};
let handle = thread::spawn(f22);
println!("thread started");
let result = handle.join();
println!("result = {:?}", result);
}
fn main() {
f2()
}
race condition
競合状態
複数のプロセスが並行して共有リソースにアクセスした結果異常な状態になること
クリティカルセクション
critical section
レースコンディションを引き起こすコード部分
atomic operation
不可分操作
それ以上分割できない処理
ある処理がアトミックである ⇒ その処理の途中状態はシステム的に観測することができず、かつ、もしその処理が失敗した場合は完全に処理前の状態に復元される。
最近のCPUではアトミック処理用の命令がある
x86_64とARM、RISC-Vなどでアトミック処理用の命令が違う
mutex
mutual exclusion
同期処理の方法
クリティカルセクションを実行可能なプロセスの数を高々1つに制限する
aumy.iconでたな高々
クリティカルセクション実行権限を得ることを「ロックを獲得する」という
クリティカルセクション実行権限を解放することを「ロックを解放する」という
スピンロック
リソースの空きをポーリングして確認するロック獲得の方法
空いているか否か共有変数を置いておいてループ回して確認する
ロック獲得時にはアトミック処理を使うことで同時に掴まれないようにする
ポーリング (polling)
定期的に問い合わせして確認する
「空いているか?」という確認を定期的に行うことで、リソースが空いたことを検知する
スピンロックの場合はめっちゃループ回して確認する
単体で使ったり自前実装するもんではない
共有変数の確認で無駄にCPUを使用してしまう
セマフォ
semaphore
ミューテックスに対して最大 $ N プロセスまで同時にロックを獲得できる
当然ながらレースコンディションを防げない
リソース利用に制限を設けたいときに使う
条件変数
バリア同期
Readers-Writerロック
プロセスを分類する
Reader
読み込み
Writer
読み書き
ロックを獲得中のReaderが0以上存在可能
ロックを獲得中のWriterは0か1個存在可能
ReaderとWriterは同時にロック獲得不可能
Rustの借用チェッカーやんけ!
Rustでは標準ライブラリとして同期処理がある
型システムによる防御
保護したい物体にクリティカルセクション外でアクセスしたり
ロックを解放し忘れたり