並行プログラミング入門-Rust、C、アセンブリによる実装からのアプローチ


並行プログラミング入門 ―Rust、C、アセンブリによる実装からのアプローチ


オライリー・ジャパン


著者:高野祐輝


はじめに

1章 並行性と並列性
1.1 プロセス
1.2 並行性
1.3 並列性
1.3.1 タスク並列性
1.3.2 データ並列性
1.3.3 インストラクションレベル並列性
1.4 並行と並列処理の必要性
1.4.1 並列処理と性能向上
1.4.2 並行処理の必要性と計算パス数爆発

2章 プログラミングの基本
2.1 アセンブリ言語
2.1.1 アセンブリ言語の基本
2.1.2 x86-64アセンブリの基礎
2.2 C言語
2.2.1 Pthreads
2.2.2 volatile修飾子
2.2.3 スタックメモリとヒープメモリ
2.3 Rust言語
2.3.1 型システム
2.3.2 基本的な文法
2.3.3 所有権
2.3.4 ライフタイム
2.3.5 借用
2.3.6 メソッド定義
2.3.7 トレイト
2.3.8 ?演算子とunwrap
2.3.9 スレッド

3章 同期処理1
3.1 レースコンディション
3.2 アトミック処理
3.2.1 Compare and Swap
3.2.2 Test and Set
3.2.3 Load-Link / Store-Conditional
3.3 ミューテックス
3.3.1 スピンロック
3.3.2 Pthreadsのミューテックス
3.4 セマフォ
3.4.1 LL/SC命令を用いた実装
3.4.2 POSIXセマフォ
3.5 条件変数
3.6 バリア同期
3.6.1 スピンロックベースのバリア同期
3.6.2 Pthreadsを用いたバリア同期
3.7 Readers-Writerロック
3.7.1 スピンロックベースのRWロック
3.7.2 PthreadsのRWロック
3.7.3 実行速度計測
3.8 Rustの同期処理ライブラリ
3.8.1 ミューテックス
3.8.2 条件変数
3.8.3 RWロック
3.8.4 バリア同期
3.8.5 セマフォ
3.9 パン屋のアルゴリズム

4章 並行プログラミング特有のバグと問題点
4.1 デッドロック
4.2 ライブロックと飢餓
4.3 銀行家のアルゴリズム
4.4 再帰ロック
4.5 擬似覚醒
4.6 シグナル
4.7 メモリバリア

5章 非同期プログラミング
5.1 並行サーバ
5.2 コルーチンとスケジューリング
5.2.1 コルーチン
5.2.2 スケジューリング
5.3 async/await
5.3.1 Futureとasync/await
5.3.2 IO多重化とasync/await
5.4 非同期ライブラリ

6章 マルチタスク
6.1 マルチタスク
6.1.1 ジキル博士とハイド氏
6.1.2 協調と非協調的マルチタスク
6.2 協調的グリーンスレッドの実装
6.2.1 ファイル構成と型、関数、変数
6.2.2 コンテキスト
6.2.3 スレッド生成、破棄とスケジューリング
6.2.4 グリーンスレッドの実行例
6.3 アクターモデルの実装

7章 同期処理2
7.1 公平な排他制御
7.1.1 弱い公平性を担保するロック
7.1.2 チケットロック
7.1.3 MCSロック
7.2 ソフトウェアトランザクショナルメモリ
7.2.1 STMの特徴
7.2.2 TL2のアルゴリズム
7.2.3 TL2の実装
7.2.4 STMを用いた食事する哲学者問題
7.2.5 TL2の改良
7.3 ロックフリーデータ構造とアルゴリズム
7.3.1 ロックフリースタック
7.3.2 ABA問題
7.3.3 マルチスレッドでの参照に関する問題
7.3.4 ロックフリーの分類

8章 並行計算モデル
8.1 数学的表記
8.2 λ計算
8.2.1 関数
8.2.2 カリー化
8.2.3 高階関数
8.2.4 λ抽象
8.2.5 束縛変数と自由変数
8.2.6 α変換
8.2.7 β簡約
8.2.8 評価戦略
8.2.9 不動点コンビネータ
8.3 アクターモデル
8.3.1 データの送受信
8.3.2 アクターの生成
8.3.3 変数束縛と制約
8.3.4 操作的意味論
8.3.5 バリア同期
8.3.6 同期的通信
8.4 π計算
8.4.1 データの送受信
8.4.2 構文
8.4.3 変数束縛
8.4.4 α変換
8.4.5 操作的意味論
8.4.6 多項π計算
8.4.7 バリア同期
8.4.8 セッション型

付録A AArch64アーキテクチャ
A.1 レジスタ
A.2 基本演算命令
A.3 メモリ読み書き
A.4 条件付き命令実行とジャンプ
A.5 呼び出し規約
A.6 例

付録B x86-64アーキテクチャ
B.1 レジスタ
B.2 AT&T記法
B.2.1 オペレーションサフィックス
B.2.2 ソースとデスティネーションの位置
B.2.3 メモリアドレッシング
B.3 基本演算命令
B.3.1 データコピー
B.3.2 算術とビット演算命令
B.3.3 比較とジャンプ命令

参考文献

おわりに
設計指針
おすすめ書籍
謝辞

索引