並行プログラミング入門

―Rust、C、アセンブリによる実装からのアプローチ

[cover photo]
TOPICS
Programming
発行年月日
PRINT LENGTH
384
ISBN
978-4-87311-959-5
FORMAT
Print PDF EPUB
Ebook
3,520円
Ebookを購入する
Print
3,520円

複数のプログラムを同時に実行する「並行プログラミング」は、処理速度を飛躍的に向上させる手法で、タスク管理、プロセス管理、スレッド管理をはじめ、複雑な仕組みについての幅広い知識とテクニックが必要となります。本書はRustとアセンブリ、そして一部Cを用い、CPUのアトミック命令、グリーンスレッド、アクターモデル、π計算、ソフトウェア・トランザクショナルメモリ、async/awaitなど、並行プログラミングに関する理論的な背景から実装までをカバー。さらに、アセンブリ実装の理解を深めるため、AArch64とx86-64アーキテクチャの説明も付録として収録。一歩一歩、着実に理解できるように、その仕組みから順を追って詳しく説明します。GitHub上で公開されているソースコードを実際に動かしながら、並行プログラミングの知識と理解を深めることができます。

関連ファイル

正誤表

ここで紹介する正誤表には、書籍発行後に気づいた誤植や更新された情報を掲載しています。以下のリストに記載の年月は、正誤表を作成し、増刷書籍を印刷した月です。お手持ちの書籍では、すでに修正が施されている場合がありますので、書籍最終ページの奥付でお手持ちの書籍の刷版、刷り年月日をご確認の上、ご利用ください。

正誤表

目次

はじめに

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 比較とジャンプ命令

参考文献

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

索引