まっつーのブログ

本の感想や振り返りなど雑多に書いてます

第12章 並行プログラミング

CS:APP コンピュータ･システム

12章について
この章では、並行プログラミングを書くための基本的なメカニズムについて説明されていました。
プロセス、スレッド、マルチプレクシングと異なる手法を用いた実装方法をはじめ、それぞれの利点と欠点についても学ぶことができます。
以下まとめです。


プロセス

サーバが接続要求を受け取ったら子プロセスに処理を引き継がせることで、自身は別の接続要求を受け付けられる。

利点 : ユーザのアドレス空間が共有されないため、誤って別プロセスの仮想メモリを上書きする恐れがない。

欠点 : プロセスが状態情報を共有することが難しい。動作が遅い。


I/Oマルチプレクシング

エコー･サーバを作る場合、接続要求とキーボードからの入力の2つの I/O イベントに応答する必要がある。
しかし片方のイベントを待っているともう片方を待つことができない。 そのため、I/Oマルチプレクシングを利用することでプロセスを一時停止状態にし、準備ができたものから順に処理していく。


利点

  • フロー間でデータ共有やデバッグがしやすい。
  • イベント駆動設計はプロセス･ベースの設計よりも効率が良い。

欠点

  • コーディングが複雑になる。
  • マルチコア･プロセッサを十分に活用できない。


スレッド

スレッドはプロセスのコンテクストで走る論理フローである。
また最新のシステムでは、単一のプロセス内で並行して複数のスレッドを走らせることができる。

利点

具体的にいうと
グローバル変数とローカル静的変数(関数内で宣言されたstatic変数)は、スレッド間で読み書き可能だが、 static をつけずに関数の内側で宣言された変数は共有されない。


スレッドに基づく並行サーバ

全体の構造はプロセス･ベースの設計に似ている。
メイン･スレッドは繰り返し接続要求を待って、要求を処理するためのピア･スレッドを作成するから。


セマフォによるスレッドの同期

システムがスレッドのために正しい順番を選択してくれるかどうかを予測できない。

セマフォ

非負整数を持ったグローバル変数で、P および V とよばれる操作によってのみ変更される。

P(s) : s を 1 減算して処理に戻る。s が 0 なら 1 以上になるまで待ち状態にする。
V(s) : s を1 加算する。待ち状態のスレッドは、V 操作をすることで処理を再開させる。

// s の初期値 = 1
for (int i = 0; i < n; i++) {
    P(&s); // sが減算されて0になるので他のスレッドは待ち状態になる
    cnt += 1;
    V(&s); // sが加算されて他の1スレッドがcntにアクセスできる
}

バイナリ･セマフォ (ミューテックス) : 値が常に 0 か 1 のセマフォのこと。
計数セマフォ : 利用可能な資源の集合のカウンタとして使われる。

注意点
同期操作(P と V)は単一のメモリ更新に比べて非常にコストがかかる。そのため、可能であれば避けるようにする。
スレッドごとにローカル変数で前計算をした結果を最終的に同期操作を使って書き込むなどがよさそう。


事前スレッド化

新しいクライアントごとにスレッドを作成するとコストがかかるので事前にいくつかのスレッドを用意する。
メイン･スレッドといくつかのワーカー･スレッドで構成する。

// mainで事前にワーカー･スレッドを生成する
for (i = 0; i < 10; i++) {
    pthread_create(&tid, NULL, thread, NULL); // 処理が来るまで待たせる
}


平行プログラムの性能

例 : 4 コアシステム上で、n = 231 個の要素の数列の合計を求める場合

実行時間は 4 スレッドまでは減少するが、そこからはむしろ少し増加し始める。
1 つのコアで 1 スレッド動かしているときが最大のパフォーマンスを発揮する理由は、複数のスレッドのコンテクスト･スイッチのオーバーヘッドによるもの。


並行性の問題

スレッド･セーフ

スレッド･セーフな関数を使用する。
スレッド･アンセーフな関数を使う場合はミューテックスで保護する。


リエントラント性

リエントラントな関数は、複数のスレッドによって呼ばれるときに、いかなる共有データも参照しない。
同期操作が必要ないため効率が良い。

またスレッド･アンセーフな関数をリエントラントになるように書き換えればスレッド･セーフとして扱える。


暗黙的リエントラント

リエントラント関数が参照渡しを許可した場合、スレッドが非共有データへのポインタを渡したときだけリエントラントとなる。


デッドロック

ある一組のスレッドが一連のリソースの獲得で競合したまま、永久にブロックされた状態に陥っている状態のこと。
スレッドが同じ順番でミューテックスを獲得するならばデッドロックは発生しない。


感想

これまでスレッドを増やせば単純に速度が向上するのかと思っていましたが、制御によるオーバーヘッドなども考慮しないといけないみたいですね。
またリエントラントについても、これまで意識していなかったので、今後並行プログラミングを扱うときに意識してみようと思いました。

そして、約4ヶ月かかりましたが無事最終章まで読み切ることができました。
実際には、図やコードサンプル、練習問題など深く学べるのでコンピュータ･システム全体を学びたいという方にオススメです。
かなり厚みもあるので、自分はこれから枕にして寝ようと思います。
以上です。お読みいただきありがとうございました。


第11章 ネットワーク･プログラミング

CS:APP コンピュータ･システム

11章について
この章では、これまで学んできたことを結びつけてネットワークの概念について説明してありました。
最終的にシンプルなWebサーバーの実装を通じて体系的に学ぶことができます。
以下まとめです。


ネットワーク

すべてのネットワーク･アプリケーションはクライアント･サーバ･モデルに基づいている。
アプリケーションはサーバと 1 つ以上のクライアントからなる。

サーバは資源を管理し、その資源を操作することでクライアントにサービスを提供している。

ネットワークから受信したデータは、DMA転送によってアダプタからI/Oバスとメモリ･バスを超えてメモリにコピーされる。
また同様にデータはメモリからネットワークにもコピーされる。

  • DMA転送 : CPUを介さずに周辺機器やメインメモリ(RAM)などの間で直接データ転送を行う方式。


イーサネット

パソコンなどの機器を有線接続する際の通信規格のこと。
ケーブルの形と機器の差し込み口が統一されないとケーブルが差せないが、イーサネットによりメーカーの異なる機器同士でも接続できる。

同軸ケーブル、光ファイバー、LANケーブルなどがある。


ルータ

複数の互換性のない LAN がルータとよばれる専用コンピュータによって接続される。
各ルータは接続されているそれぞれのネットワーク用のアダプタポートを持つ。


プロトコルの機能

異なるネットワーク間の違いを取り除く。
各ホストとルータで動作しているプロトコル･ソフトウェアの層でプロトコルを実装している。

各ホストはインターネット･アドレスを少なくとも1つ割り当てられる。
データをパケットとよばれる別々の塊に詰め込むための方法を定義することで違いをなくしている。


グローバルIPインターネット

インターネットを世界中に広がった次の性質を持つホストの集まりと考える。

ホストの集合 : 32 ビットの IPアドレスの集合にマップされる。
IPアドレスの集合 : インターネット･ドメイン名とよばれる識別子の集合にマップされる。

インターネット･ホストのプロセスはコネクション越しに他のホストのプロセスと通信できる。


インターネット･ドメイン名

人間が分かりやすいようにドメイン名を別に定義している。
通信自体はIPアドレスを使っている。

(例)
ドメイン名 : example.com
IPアドレス : 192.0.2.1
ドメイン名があればいちいちIPアドレスを入力しなくていいので便利。

1988年まではテキストファイルで手動で管理されていたが、現在はDNSとよばれる世界中に分散したデータベースで管理しているという。


TCP/IP : プロトコル群のことで、それぞれのプロトコルは異なる機能を提供している。

TCP : プロセス間で信頼性の高い全二重のコネクションを提供するために、IP の上に構築する複雑なプロトコル。

IP : 基本的な名前づけの体系と、インターネットのあるホストから別のホストにパケットを送ることができる配送メカニズムを提供する。

UDP : IP をわずかに拡張したもの。パケットがホスト間ではなく、プロセス間で転送される。


IPアドレス

符号なしの 32 ビット整数。

TCP/IP では、最上位バイトから下位バイトに向けて順に記述するビッグエンディアンが用いられるため、 IPアドレスの構造体のアドレスは、リトルエンディアンであっても、常にビッグエンディアンのネットワーク･バイト･オーダで格納される。


インターネット･コネクション

クライアントとサーバはコネクション越しにデータのストリームを送受信することで通信を行う。


ソケット

各ソケットはインターネット･アドレスと 16 ビット整数のポートからなり、対応するソケット･アドレスを持つ。


ソケット･ペア

コネクションは 2 つのソケット･アドレスによって一意に特定される。
この一対のソケット･アドレスはソケット･ペアとよばれる。

(クライアントのIP : クライアントのポート, サーバーのIP : サーバーのポート) として表される。

クライアントのソケット･アドレス : 128.2.192.242:51213
ウェブサーバのソケット･アドレス : 208.216.181.15:80
ソケット･ペア : (128.2.192.242:51213, 208.216.181.15:80)


ウェブの基本の話

クライアントとサーバは HTTP を用いてやり取りを行う。

ウェブ･サーバはクライアントに 2 つの異なる方法でコンテンツを提供する。

  • ディスク上のファイルを取ってきて、その中身をクライアントに返す。
  • 実行可能ファイルを実行し、その出力をクライアントに返す。

Webサーバによって返されるコンテンツは、サーバが扱うファイルに関連付けられ、それぞれ URL とよばれる一意の名前を持つ。


HTTPトランザクション

HTTP は Linux の Telnet を用いることができる。

  • Telnet : ネットワークに接続された機器を遠隔操作するために使用するアプリケーション層プロトコルのこと。


HTTPリクエスト

HTTPリクエストは、リクエスト行とリクエスト･ヘッダ、ヘッダのリストを終わらせる空行からなる。

リクエスト行の形式 : method URI version

HTTP は GET, POST, PUT, DELETE, など多くのメソッドをサポートしている。

version フィールドはリクエストが従うべき HTTP のバージョンを示す。
最新のバージョンは、HTTP/1.1 で、初期のシンプルなバージョンに HTTP/1.0 がある。


HTTPレスポンス

HTTPレスポンスはレスポンス行とレスポンス･ヘッダ、ヘッダのリストを終わらせる空行、レスポンス本体からなる。

レスポンス行の形式 : version status-code status-message

status-code はリクエストの性質を湿す3桁の正の整数のこと。 404, 200 とか。


子プロセスの出力先

CGI は動的コンテンツを標準出力に送る。
そのため子プロセスは CGI をロードして実行する前にリダイレクトする。
親プロセスは子プロセスが生成したコンテンツのタイプやサイズを知らないため、子プロセスはレスポンスヘッダの Content-type と Content-length を生成する責任がある。


感想

これまで学んできた知識が繋がってなるほどなぁという感じでした。
表面的なことだけではなく、内部的にどのような仕組みになっているのか学ぶことができてよかったです。
またこの章では、エコー･サーバの実装例など、コードが豊富に記載されていました。
今後ウェブサーバを実装する課題に取り組むときにまた読み返してみようと思います。


第10章 システム･レベルI/O

CS:APP コンピュータ･システム

10章について
この章では、ファイルやディレクトリプタといったUNIX I/Oの基本的なコンセプトについて説明されていました。
Webサーバの実装や並行プログラミングにつながる章となっています。
以下まとめです。


ファイルあれこれ

オープン

ファイルをオープンするとそのファイルを特定するディスクリプタを返す。
カーネルはオープンしたファイルのすべての情報を追跡するが、アプリケーションはディスクリプタを追跡するだけ。


クローズ

カーネルはオープン時に作成したデータ構造を解放し、ディスクリプタを戻す。
プロセスが何らかの理由で終了したとき、カーネルはオープン中のすべてのファイルをクローズする。


読み書き

ファイルサイズ以上の読み込み操作を行うと、ファイル終端(EOF)とよばれる状態になり、アプリケーションに検出される

読み込み : ファイルからメモリにコピーする。
書き込み : メモリからファイルにコピーする。


ファイルタイプ

ディレクトリ、ソケット、名前付きパイプなどがある。


ショート･カウント

状況によって要求より少ないバイト数しか転送しないことがある。

(例) 30バイトのファイルに対し、50バイト読み込もうとした場合。
read はショート･カウント 20 を返す。
その後にショート･カウント 0 を返すことでEOFを知らせる。


ファイルのメタデータの読み込み

stat や fstat 関数を呼び出すことでファイルについての情報(メタデータ)を取り出せる。


ディレクトリの読み込み

opendir, readdir, closedir 関数でディレクトリの情報を扱うことができる。


カーネルのファイル管理

カーネルはオープンしたファイルを 3つの関連するデータ構造を用いて表現している。


ディスクリプタ･テーブル(プロセスごとに一つ)

ファイル･ディスクリプタによってエントリに索引がつけられている個別のディスクリプタ･テーブルを持っている。


ファイル･テーブル (すべてのプロセスで共有)

各エントリは、ファイルポジションや、参照カウント、v-ノード･テーブルなどを持っている。
ディスクリプタをクローズすると、参照カウントを減少させ、0 になるとファイル･テーブルのエントリを削除する。


v-ノード･テーブル (すべてのプロセスで共有)

stat 構造体のほとんどの情報が格納されている。


ファイルの共有

同じファイルに対して 2回 open 関数を呼び出すことで、ファイル共有ができる。


ファイルの継承

forkした場合、親プロセスと子プロセスが同じオープン･ファイル･テーブルとファイル･ポジションを共有する。
ファイル･テーブルのエントリを削除するには、親と子で両方ともクローズする必要がある。


標準I/O

標準I/Oライブラリはオープンしたファイルをストリームとして、モデル化している。
すべての ANCI C プログラムはオープン中の 3つのストリーム stdin, stdout, stderr を持った状態で実行を開始する。


ソケット

Linux のネットワーク抽象化は、ソケット とよばれるファイル･タイプがある。
ソケット･ディスクリプタを読み書きすることで他のコンピュータ上で動作しているプロセスと通信する。


感想

次章以降につながる事前知識のような感じだったので、スムーズに読みすすめられました。
実際にはRIOパッケージを用いた安全な読み書きについても書かれていました。
コードサンプルが多かったので理解しやすかったです。


第9章 仮想メモリ

CS:APP コンピュータ･システム

9章について
この章では、メモリマッピングの手法や、アドレス変換の流れ、アロケータの仕組みなど仮想メモリについて説明されていました。
あらゆるシステム設計において中心的存在である仮想メモリについて学ぶことができます。
以下まとめです。


仮想メモリの特徴

仮想メモリはアクティブな領域のみを主記憶に保持して、必要に応じてディスクとメモリ間のデータ転送を繰り返す。
また各プロセスに一様なアドレス空間を提供することでメモリ管理を簡単にする。
アドレス空間が他のプロセスによって破損するのを防いでくれるといった特徴もある。


物理アドレシング : 初期のPCで使用されていた手法。単純な構成。

仮想アドレシング : CPU は仮想アドレスを生成して主記憶をアクセスし、主記憶に送られる前に適切な物理アドレスへ変換する。


キャッシュの構成

SRAMキャッシュ : CPU と主記憶との間に位置する L1, L2, L3 キャッシュ。

DRAMキャッシュ : 主記憶内に下層ページを保持する VM システムのキャッシュ。SRAM と比べて 10倍は遅い。

SRAM に比べて DRAM キャッシュにおけるキャッシュ･ミスに時間がかかる理由はディスクかにアクセスする必要があるから。


ページ･テーブル

アドレス変換ハードウェアは、仮想アドレスを物理アドレスに変換するたびにページ･テーブルをリードする。
ページ･テーブルは、ページ･テーブル･エントリ(PTE)の配列のこと。

仮想アドレス空間内の各ページは、ページ･テーブル内で決まったオフセットに位置する一つの PTE を持つ。


ページ･ヒット : アドレス変換ハードウェアは、PTE の場所を特定しインデクスとして仮想アドレスを使用する。

ページ･フォールト : DRAM のキャッシュ･ミスのこと。


アドレス変換

仮想アドレス空間と物理アドレス空間との間のマッピングのこと。
仮想アドレスは、 仮想ページ･オフセットと仮想ページ番号から構成される。
変換を行うことで、プログラム内ではアドレスを連続的に使用できるようになる。


メモリ･マッピング

Lnux が仮想メモリ領域を初期化する場合、その領域をディスク上のオブジェクトに関連付けることで初期化を行う。

メモリ領域は、通常ファイルか匿名ファイルのどちらかにマップされる。

  • 通常ファイル : マップされるファイルの領域はページ･サイズの大きさに分割され、仮想ページの内容は、分割された各ファイルの内容で初期化される。

  • 匿名ファイル : 匿名ファイルはカーネルによって作られ、その内容はゼロで初期化されている。

どちらの場合も、一度仮想ページが初期化されればカーネルが保持しているスワップ･ファイルとの間でスワップ･イン、スワップアウトされる。


Linux の仮想メモリ･システム

Linux は仮想メモリを領域 (セグメント)の集まりとして構成する。
コード、データ、ヘッド、共有ライブラリ、ユーザ･スタックはすべて異なる領域にある。
またどの領域にも属さない仮想ページは存在しないので参照できない。


共有オブジェクト

仮想アドレス空間にマップされた共有オブジェクトに書き込みを行うと、同じ共有オブジェクトを仮想メモリにマップしている他のプロセスにもその書き込み結果が見える。
そのため複数の共有領域にマップされていても共有オブジェクトのコピーは一つしか物理メモリ上に保持する必要はない。


コピー･オン･ライト

プライベート･オブジェクトを仮想メモリにマップする場合に使う。
スタート時点では、プライベート･オブジェクトも共有オブジェクトとまったく同じようにマップされている。

例外が発生した場合、書き込み対象となったページを物理メモリ上に新しくコピーして、そのページを指すように変更する。


(例) fork で子プロセスを生成する場合
どちらかのプロセスに書き込みを行うまでは、子プロセスは、親プロセスのコピーそのもの。
書き込みを行ったときに新しいページが作られる。


動的メモリ･アロケータ

ブロック

アロケータはヒープをさまざまなサイズのブロックの集合として扱う。
ブロックは、割り当て済かフリーのいずれかである仮想メモリの連続したチャンク(塊)である。
フリー･ブロックは、アプリケーションによって明示的に割り当てされるまでは、フリーの状態のまま。


明示的なアロケータ : アプリケーションが割り当て済ブロックをすべて明示的にフリーにする必要がある。malloc で確保した領域を free で解放する。
暗黙のアロケータ : 使われなくなったブロックを自動的にフリーにする手続きは、ガーベジ･コレクションとよばれる。


malloc

malloc は、指定されたサイズバイトのメモリ･ブロックへのポインタを返す。
ブロックのアドレスは、32ビット･モードでは 8の倍数、64ビット･モードでは 16の倍数となる。

free

割り当てたヒープのブロックを解放する。
引数で与えられるポインタは、割り当てしたブロックの先頭を指していなければならない。


アロケータの目標

  • 要求にかかる時間を高速にする: 割り当てと解放の要求を満たすのにかかる平均時間を最小にすることで、スループットを最大にできる。

  • メモリの使用効率を最大にする : 割り当て可能な仮想メモリの量は、ディスク上のスワップ領域の総量に制限される。

ヒープ利用率を犠牲にしてスループットを最大にするのは、容易に行えるのでそのバランスを取るのが難しい。


断片化(フラグメンテーション)

ヒープ利用率の悪化の第一の原因は、断片化と呼ばれる現象で未使用のメモリが利用できなくなる。


内部断片化

割り当てされたブロックが、データを格納する場所よりも大きい場合に起きる。
(例) malloc(10)に対して、データを3バイト分しか格納しない場合、 7バイトが内部断片化する。


外部断片化

利用可能なメモリの総和は十分にあるのに、連続していないため要求を満たせない場合に起きる。

0:フリー･ブロック
1:割り当て済
*:ポインタの位置

0000000000000 # ヒープ領域
*
1110000000000 # p1 = malloc(3)
*  *
1112222200000 # p2 = malloc(5)
*  *    *
1112222233330 # p3 = malloc(4)
*       *
1110000033330 # free(p2)
*  *    *
1114400033330 # p4 = malloc(2)

上記の場合最終的にメモリの総和は 4 バイトあるが連続している領域が最大で 3 バイトなので、3 バイトまでしか割り当てられない。
外部断片化は、未来の要求パタンにも依存するため予測が難しい。


アロケータ

アロケータは、ブロックの境界を区別したり、割り当てされたブロックとフリー･ブロックを区別するための何らかのデータ構造を必要とする。

アロケータのデータ構造は、1 つのブロックは 1 ワードのヘッダ、ペイロード、パティングから構成される。


暗黙のフリー･リスト

ヒープの構成のこと。連続した割り当て済ブロックとフリー･ブロックの連なりとして構成できる。

利点 : 実装が単純であること。
欠点 : 割り当て済ブロックの特定にかかるコストがかかること。


明示的なフリー･リスト

双方向連結リストを使うと、ファースト･フィットの割り当て時間が｢ブロック総数に比例｣から｢フリー･ブロックの数に比例｣に減る。


ガーベジコレクション

動的なストレージのアロケータで、プログラムから必要とされなくなった割り当て済ブロックを自動的に解放する。

メモリを有向グラフと考え、ルート･ノードから到達不能なブロックは、｢ごみ｣として扱う。
到達可能なグラフに何かの表現を与え、定期的に到達不能なノードを解放して、それらをフリー･リストに戻すことで回収する。


メモリ･リーク

割り当てしたブロックを解放するのを忘れて、ヒープにごみを作ってしまうこと。
leak が頻繁に呼ばれると、ヒープがごみでいっぱいになり、最悪の場合、仮想アドレス空間をすべて消費してしまう。


感想

これまでの章に比べてかなり難しかったです。。
その分重要だとも思うので、練習問題などを用いて復習してみようと思います。
個人的には、コピーオンライトの仕組みが好きでした。


第8章 例外的な制御フロー

CS:APP コンピュータ･システム

8章について
この章では、制御フローについて学んでいきます。
例外的な制御フローについて学ぶことで、アプリケーションがどのようにオペレーティング・システムと相互作用するかを理解しやすくなります。
また try, catch ,throw などの構文が理解しやすくなるそうです。
以下まとめです。


例外的な制御フローって？

制御転送 : プロセッサに電源を入れてから切るまでの、プログラム･カウンタの遷移のこと。
制御フロー : 連続する制御転送のこと。

制御フローに対して突発的な変更を行うことで、さまざまな状況に反応する。
この突発的な変更のことを例外的な制御フローとよぶ。

例外

例外ハンドラ

プロセッサはイベントの発生を検出すると、例外テーブルとよばれるジャンプ･テーブルを介して、例外ハンドラをよぶ。
例外ハンドラが処理を終了すると、種類に応じて以下のどれかが起きる。

  1. 制御を現在の命令に戻す。
  2. 例外が起きなければ次に実行されていたはずの命令に戻す。
  3. ブログラムを中断させる。


例外のそれぞれには、例外番号が割り当てられている。
システムの起動時に、オペレーティング･システムは例外テーブルを確保し初期化する。
例外番号はその例外テーブルのインデクスとして使われる。

例外の4つのクラス

  1. 割り込み : ハードウェア割り込みに対する例外ハンドラは、割り込みハンドラとよばれる。
  2. トラップ : 命令実行の結果として発生する意図的な例外。read, fork, exitなどのシステムコールのこと。
  3. フォールト : エラーを訂正できる場合は、命令に制御を戻すが訂正できない場合は、abort ルーチンに制御を移す。
  4. アボート : アボートは回復不能なエラーによって起きる。プログラムを強制終了する。


Linux/x86-64 システムにおける例外

x86-64 では 最大で 256 個までのタイプの例外がある。

  • 除算エラー : ゼロ除算か、除算結果がオーバーフローした場合に発生する。

  • 一般保護フォールト : プログラムが仮想メモリ上の未定義領域を参照した場合や、読み出し専用のセグメントに書き込もうとした場合に起きる。

  • ページ･フォールト : ディスク上の適切な仮想メモリのページを物理メモリのベージにマップし、その後にファールディング命令を再開する。

  • マシン･チェック : フォールティング命令の実行中に検出された致命的なハードウェア･エラーの結果として発生する。


プロセス

例外はプロセスという機能を実現するための基本的な仕組みである。
システム内の各プログラムは、いずれかのプロセスのコンテクストで実行される。

プログラムを実行するたびに、シェルは新しいプロセスを作りその新しいプロセスのコンテクストで実行可能ファイルを実行する。


3つのプロセスを実行する場合

制御フローは 1つしかないがプロセス 1つ 1つに分割され、3つの論理フローとなる。
プロセスはプロセッサを順番に使うので、他のプロセスの実行中の間一時停止している。


平行と並列

倫理フローは、例外ハンドラ、プロセス、シグナル･ハンドラ、スレッドなど様々な形で現れる。

マルチタスク : 他のプロセスと交代しながら実行される場合。
タイム･スライス : 一つのプロセスがフローの一部を連続して実行する期間のこと。

平行フロー : 2 つのフローが時間的にオーバーラップして実行されるとき。
並列フロー : 2つのフローが、異なるプロセッサ･コアあるいはコンピュータ上で実行されている場合。


コンテクスト･スイッチ

例外的制御フローを利用した仕組みのことで、マルチタスクを実装するのに使う。
カーネルはプロセスごとにコンテクストを管理している。

コンテクスト : 一時的に停止されたプロセスを再開するためにカーネルが必要とする状態のこと。

スケジューリング : プロセスが実行されているいずれかの時点で、カーネルは現在実行中のプロセスを一時停止し、以前停止したプロセスを再開すること。


システム･コールにおけるエラー･ハンドリング

エラー処理は省略されがちだが、必ず行うべき。
しかしそのまま書くとコードが膨らんでしまうので、ラッパー関数を作成してエラー処理を行う。

// これを毎回書くとコードが膨む
if ((pid = fork()) < 0) {
    fprintf(stderr, "Error: fork failed\n");
    exit(0);
}

pid = xfork(); // 失敗した場合にラッパー関数がエラー処理をする


プロセスの生成と終了

プロセスは 3つの状態のどれかとなる。

  1. 実行中状態 : 実行中、あるいは実行待ちで、やがてスケジュールされる。
  2. 停止状態 : 実行が停止しており、スケジュールされることがない状態。
  3. 終了状態 : プロセスが永久に停止した状態。


プロセス生成

fork 関数によって子プロセスを生成できる。
子プロセスは親プロセスが持つユーザ･レベルの仮想アドレス空間のコピーを持つ。
コード･セグメント、データ･セグメント、ヒープ、共有ライブラリ、ユーザ･スタックがコピーされる。


子プロセスの回収

終了してるが、回収されていないプロセスをゾンビという。
親プロセスが終了すると、孤児となった子プロセスを init プロセスが引き取るようカーネルが処理を行う。
長く動き続けるプログラムの場合、システムのメモリ資源を消費したままなので、wait関数でゾンビを回収する。


プログラムとプロセスの違い

プログラム : コードとデータの集まり。
プロセス : 実行中のプログラムのプログラムの実体として具体的に存在するもの。

プロセス･グループ

ls | sort というコマンドを実行した場合、この 2つのプロセスは同じプロセス･グループに属している。

Ctrl+C を入力すると、プロセス･グループに属するすべてのプロセスに対して、SIGINT を送信する。

# 一度のSIGINTで終了する
cat | cat | cat


シグナル

シグナル : 小さなメッセージのようなもので、何らかのイベントがシステム内で発生したことをプロセスに通知するもの。

それぞれのシグナルは何らかのシステム･イベントに対応している。
またシグナル･ハンドラを用いて、シグナルをキャッチできる。

ペンディング･シグナル

送信されたもののまだ受信されていないシグナルのこと。
あるシグナル番号に対して一つしか持たないので、それ以降送られてきた場合は捨てられる。

ペンディング･シグナルの集合を pending というビット･ベクタに保持している。
ブロックされているシグナルの集合は blocked というビット･ベクタに保持している。


シグナル･ハンドラの書き方

  1. ハンドラはフラグをセットするだけにするなどシンプルにする。

  2. 非同期シグナル･セーフ関数だけをよぶ。

  3. errno が書き換わらないようにする。

     void sig_handler(int sig)
 {
     int tmp = errno;
     sleep(1); // errnoが書き換わる
     errno = tmp; // もとに戻す
 }

  4. データ構造へのアクセスを保護するためシグナルをブロックする。

     // keyの書き換え中に割り込みが発生するとvalueが変えられない
 struct t_dict {
     char *key;
     char *value;
 };

  5. グローバル変数はvolatileで宣言して、変数の値をキャッシュさせないようにする。

  6. sig_atomic_tで宣言して、 読み書きが1 命令で実装されているためアトミックであることを保証する。


非局所的ジャンプ

C では非局所的ジャンプというユーザ･レベルの例外的制御フローが提供されている。
ある関数から他の関数に直接飛び込むことができる、setjmpとlongjmpがある。
try catch throw の仕組みに似ている。

try : 例外を監視するブロックを宣言する。
catch : try ブロックで例外が発生した場合、ブロックを実行する。setjmp 関数に似ている。
throw : 例外を発生させる。longjmp 関数に似ている。


感想

以前簡易的なbashの再実装をしたことがあるので、概念的には知っていることがたくさんありました。
ですがその時に知らなかったような仕組みや、より安全なコードの書き方など学ぶことができたので良かったです。
C言語でもジャンプを利用して try catch のような仕組みができるようなので、試してみようと思います。


第7章 リンク

CS:APP コンピュータ･システム

7章について
この章では、そもそもリンクとはなんだろう？ということから始まり、静的リンクと動的リンクの違いや効率化の手法について説明されていました。
リンカが行っている動作について学ぶことで、リンクエラーを避けることができ、大きなプログラムを作成するときに便利になります。
以下まとめです。


リンクとは？

データを一つのファイルにまとめ上げ、メモリ上にコピーし実行できるようにすること。
コンパイル時のほか、ロード時や実行時にもプログラムによって行うことができる。

(例) main.o, func.o, lib.a など必要なものをまとめて a.out を作成する流れのこと。


静的リンク

静的リンカは再配置可能オブジェクト･ファイルおよびコマンド･ライン引数を入力として受け取り、ロードして動かすことのできるリンク済みの実行可能オブジェクト･ファイルを生成する。

実行可能ファイルを生成するためにシンボル解決と再配置の2つの作業を行う。

  • シンボル解決 : オブジェクト･ファイルはシンボルを定義･参照しているので、それを元に適切な処理をする。
  • 再配置 : 各シンボルの定義にメモリ位置を対応づけ、そのシンボルへの参照が対応づけたメモリ位置を指すようにする。


オブジェクト･ファイル

3種類存在する。

  • 再配置可能 : コンパイル時に他の再配置可能オブジェクト･ファイルと統合し、実行可能オブジェクト･ファイルを生成可能。
  • 実行可能 : 直接メモリにコピーし実行可能。
  • 共有 : ロード時もしくは実行時にメモリに関して読み込み動的にリンクできる。


再配置可能オブジェクト･ファイル

主要なセクション

  • .text: 機械語
  • .data: 読み書き可能なデータ(初期化されているグローバルおよび静的変数)
  • .rodata: リードオンリーのデータ
  • .bss: 初期値が 0 のデータ (初期化されていないグローバルおよび静的変数)

-g オプション付きで存在するセクション

  • .debug: ローカル変数および型のエントリを含む
  • .line: ソースの行番号と機械語との対応関係を持つ

-g オプションをつけずにコンパイルするとステップ実行ができなくなる原因は、このセクションを見ると理解できますね。


シンボル

再配置可能オブジェクト･モジュールには、シンボルに関する情報を含むシンボル･テーブルが存在する。

  • 大域シンボル : 他のモジュールから参照可能な(静的でない関数およびグローバル変数)

  • 外部的な大域シンボル : 他のモジュールで定義されている

  • 局所シンボル : そのモジュールでのみ定義･参照される (静的な関数および static 属性付きで定義されたグローバル変数)


シンボル解決

シンボルへの参照を、シンボル･テーブル内にあるシンボルの定義から一つ選び対応づけることで解決する。

  • 局所シンボルの場合 : 局所シンボルの定義はモジュールごとに一つしか存在しないので簡単。

  • 大域シンボルの場合 : 現在のモジュール内で定義されていないシンボルを見つけたとき、そのモジュールを外部へ探しに行く。リンカが参照されているシンボルの定義を見つけられなかったらエラーとなる。


strongシンボル: 関数および初期化済のグローバル変数
weakシンボル: 初期化されていないグローバル変数

以下のルールをもとに解決する。

  • 同名の strong シンボルが複数存在してはならない。
  • 同名の strong シンボルと weak シンボルが存在する場合、strong シンボルを選択する。
  • 同名の weak シンボルが複数存在する場合、任意の一つを選ぶ。

解決できない場合はエラーが発生する。

二重定義

// foo.c
int x = 10;

// bar.c
int x; 宣言だけならエラーにならない

// hoge.c 
int x = 1; // strongシンボルの二重定義でエラーになる。


グローバル変数によるバグ

// foo.c
int y = 1000;
int x = 1000; // foo.c内ではint

// bar.c
double x;

void f() {
    x = -0.0; // bar.c内ではxはdoubleとして扱われる
}

bar.c の x = -0.0 によって x と y のメモリ領域が倍精度浮動小数点数点表現された負のゼロで上書きされてしまう。

そのためx = 0x0 y = 0x80000000 という結果になる。


マングリング

C++ などではソース･コード内に同名の引数が異なるメソッドの定義を許している。 同名の関数や変数を識別するために名前をエンコードすることをマングリングとよぶ。

マングリングの例

int foo(int) {}
// _Z3fooi 

int foo(int, int, float) {}
// _Z3fooiif

例では、引数の頭文字を付加していますが、実際にはもう少し複雑な名前付けを行っています。


ライブラリが必要な理由

Pascal では標準関数が少ないため、コンパイラが関数の呼び出しを認識して適切なコードを直接生成する。

しかし、C言語など標準関数が多いものに関しては、そのやり方は向いていない。
なぜなら関数の追加や削除、修正するたびに、コンパイラのバージョンを新しくする必要があるためである。

そのため静的ライブラリ .a を活用する。
またライブラリを指定する際の原則はコマンド･ラインの末尾に置くこと。

(例)foo.cが lib1.a, lib3.a を呼び出し、それが lib2.a を呼び出す場合

gcc foo.c lib1.a lib3.a lib2.a とする必要がある。


静的ライブラリの欠点

定期的に保守、更新する必要がある。
またライブラリの更新するたびに、再リンクする必要がある。


再配置

リンカがシンボル解決ステップを完了すると、コード内の各シンボルへの参照にただ一つの定義が対応づけられる。

セクションおよびシンボル定義を再配置 : 同じ型のすべてのセクションを統合し、一つの修正セクションにする。

セクション内のシンボルへの参照を再配置 : コード及びデータ･セクション内のシンボルへの参照を修正し、正しい実行時アドレスを指すようにする。

シンボルへの参照を再配置する : 相対アドレスまたは絶対アドレスを用いて重複する再配置する。


共有ライブラリって？

静的ライブラリの欠点を補うために生まれた。
実行時、もしくはロード時に任意のメモリ･アドレスに読み込み、メモリ上のプログラムとリンクすることができる。

複数プロセスが同じライブラリのコードをメモリ上で共有することで資源を節約できる。

.so 拡張子によって識別される。


共有ライブラリの実用

  • ソフトウェアの配布 : ユーザがアプリケーションを実行すると、新しい共有ライブラリが自動的にリンクおよびロードされる。
  • 高性能ウェブ･サーバの構築 : 口座残高、バナー広告などの動的コンテンツ。


共有ライブラリの効率化

共有ライブラリのメモリ資源節約のため、あらかじめアドレス空間内のある領域を各共有ライブラリに割り当てておく。
しかし、ライブラリを使用しない場合でも領域を確保するため空間効率が悪い。
また管理が難しく、割り当てた領域が重ならないように保証しなければならない。

これらの問題を避けるため、メモリ上のどこにでもロードできる形式(PIC)にコンパイルする。


ポジション非依存コード(PIC)

再配置なしにロード可能なコードのこと。

PIC としてコンパイルされた共有ライブラリは任意の位置にロード可能であり、実行時に複数のプロセスで共有できる。
PIC は PLT のように相対アドレッシングのみで構成されていていて、再配置可能なコード。


PIC関数呼び出し

コンパイラには関数の実行時アドレスを予測する方法がない。
通常の方法では、参照の再配置する再配置レコードを生成し、プログラムがロードされたときに動的リンカが解決できるようにする。

GNU では遅延束縛という技術を用いているこの問題を解決している。


遅延束縛

関数のアドレスの解決をそれが実際に呼び出されるまで遅延することで、動的リンカはロード時に不要な再配置を避ける。

関数が最初に呼び出されるときにはコストがかかるが、その後の各呼び出しは低コスト。


言語束縛

多くのライブラリは、C言語や C++ などのシステムプログラミング言語で書かれているが他の言語でも使えるようにしたもの。
ライブラリそのものを複数の言語で作成するよりも効率的となる。

またはシステム言語と同じ機能を高級言語で記述できないためという場合もある。


インターポジショニング

共有ライブラリの関数への呼び出しに介入し、代わりに独自のコードを実行できるようにすること。
特定のライブラリ関数のラッパー関数を作成して、全く別の実装に置き換えたりする。
コンパイル時やリンク時、実行時に行うことができる。


感想

オブジェクト･ファイルやライブラリをまとめる上で、内部的にどのように動作しているのか知ることができました。
シンプルに見えて、複雑なプロセスを経ていることが学べて良かったです。
個人的にこれまでは静的ライブラリを利用することが多かったですが、動的ライブラリや共有ライブラリなど、用途に合わせて使ってみようと思いました。


植山類さん講演会 (並行プログラミング)

講演会

先週に引き続き、リンカlldのオリジナル作者かつ現メンテナで、Cコンパイラ8ccの作者である植村類さんの講演会に参加しました。

今回は並行プログラミングを主題として、効率化の仕組みや類さんが自作されているリンカmoldについても教えていただきました。

特にlldとmoldの速度の違いに関してはとても興味深かったです。

ここから、学んだことをまとめています。

マルチコアマシン

  • 昔はシングルコアだけだった。

  • 今は PC やスマホもマルチコア

    • チップの微細化が進んでいるから。

  • 10 万円以下だと 4 ~ 6 コア

  • ハイエンドだと 16 ~ 64コア

    • 今の技術的には 64 コアくらいが上限。

    • 微細化が進めばもっと多くなるかも。

  • スパコンだともっと多かったりする。

性能向上

  • マルチコア構成により、複数のプログラムを同時に実行できる。

  • make -jN のように make を実行するとサブプロセスを N 個同時に実行できる。

    • 複数プロセスで実行するため素早く make できる。

マルチスレッドと共有資源

  • 1 つのプログラムをマルチコアマシンで速く動かすには、複数のスレッドを使う。

  • ローカル変数はスレッドごとに別。

    • スレッドごとに別々実行スタックを持つ。

  • マルチスレッドの例として Web サーバやレイトレーシング、GUI アプリなどが挙げられる。

  • スレッドもあまり細かくしすぎるとオーバーヘッドが大きくなる。

    • そのため効率が良くならないこともある。

  • 既存のプログラムをマルチスレッド化する万能の方法はない。

  • 個別に良い感じのタスク分割をする。

Web サーバでのマルチスレッド

  • コネクションが多すぎるとスケールしない。

  • 少ないスレッドでイベント駆動型のほうが良いのか？

    • どっちも派閥がある。

    • 一概にどちらが良いとは言えない。

  • google だとマルチスレッド。

  • 1スレッド1コネクションの方がプログラミングは楽。

タスク分割のガイドライン

  • スレッド間で共有するデータは少ないほうが良い。

    • データの整合性を保つための排他制御が必要になる。

  • タスクの粒度は大きい方が良い。

    • 小さい処理を分割してもオーバーヘッドの方が大きい。

  • タスクは多い方が良い。

  • スレッド間の関係は単純な方が良い。

共有データの古典的な問題

  • 銀行で同時に振り込みを行う。

    • 正しく制御しないと残高が合わないってことが起こり得る。

  • そのためロックを使って排他制御を行う。

  • 上手くロックしないとデッドロックが起こる。

    • 互いに相手の終了待ちとなり、いつまでも処理が進まなくなってしまう状態。
排他制御の責任はプログラマーにある？

  • もう少し低いレイヤーでいい感じに制御できないのか。

  • あることはあるが基本的にはプログラムで上手く排他制御するのがベター。

  • トランザクショナル･メモリ を用いて CPU によって排他制御が行うことも可能ではある。

    • 各実行スレッドがそのコピーをローカルに持ち、処理終了時点で参照数値が変更されていないことの確認と、結果の書き込みを一気に行う。

    • 失敗した場合、処理そのものを廃棄してやり直す。

高水準スレッドライブラリ

並行コンテナ

  • 別のスレッドからアクセスしても大丈夫な配列。

  • ベクタやハッシュテーブルなどのデータ構造と同じ API を提供している。

  • 中身の具体的な実装を気にすることなく使える。

Future

  • データの受け渡しとスレッドの同期を一体化したもの。

  • データを生成する側はデータを Future にセットする。

  • 受け取り側は、必要となった時に Future から読み取る。

Wait group

  • カウントダウン･ラッチともいう。

  • 全員の処理を完了するまでの待ち合わせポイントとして使うことができる。

    • メインのルーチンがサブルーチンが全て終わるまで待つ。

  • プロセスの wait みたいなイメージ。

アムダールの法則

  • 並列化されたプログラムの性能を決める要因

    1. 並列化されていない箇所が全体のどれくらいか。

    2. 何個のコアが利用可能か。

(例) シングルコアで30分かかる処理

  • 20分の処理は並列化されている。

  • コアがいくつあっても10分より短くすることができない。

  • 並列化された処理を増やすことが重要となる。

mold と lld の比較

  • lld は並列化されていない処理が多い。

    • 全体の処理時間の大半を占めている。

  • mold はほぼすべての処理が並列化されていないされている。

    • 短時間で処理可能。
mold の速度

  • 手元のマシンでcd出力ファイル 1GB あたり約 1 秒

  • cp で出力ファイルを別ファイルにコピーするのと比較して 2 倍遅い程度

  • かなり速いらしい。

  • 秘訣はたくさんのコアを有効に活用すること。

mold リンカの並列化手法

mold の目標

  • 利用可能なコアを使い切る。

  • 複雑のなことは行わない。

採用した手法

  • データパラレリズム

  • 同じ型のデータがたくさんあり、並列 for ループで同時に処理する。

  • リンカ全体としてはシングルスレッドの場合と同じ複雑さ。

  • 高水準スレッドライブラリはそこまでたくさん使っていない。

無理なく並列化できるデータ構造を考えることが大切。

Intel TBB

  • C++ライブラリ

  • 並列コンテナや 並列 for ループなど、マルチスレッドプログラミングのベースとなる機能

  • mold でも使っている。

並列forループ

  • 異なる繰り返しが同時に走るかもしれない for ループ。
tbb::parallel_for(0, 10000, [&](int i) {
    len[i] = strings[i].size();
});

  • 最大で10000 並列で実行してくれる。

  • 要素が少ないときに呼ぶとオーバーヘッドの方が無駄となる。

並列での名前解決

  • 基本的にはハッシュテーブル。

  • 並列化されたハッシュテーブルに並列 for ループで入れていく。

ファイルオフセットの決定

文字列をファイルに出力する場合

  • 各文字列ごとにファイル上での位置を決める必要がある。

  • 並列に足し算を行って、オフセットを求める。

入力文字
hello xxxx world

hello 文字列長 5 オフセット 5
xxxx  文字列長 4 オフセット 9
world 文字列長 5 オフセット　14

並行ハッシュマップ

  • mold では自作の並行ハッシュテーブルを利用している。

  • ハッシュテーブルのサイズを拡張する操作が遅い。

    • そのためリサイズしたくない。

    • あらかじめ大きなハッシュテーブルを用意する。

  • すべての要素数を数えればちょうどよい大きさのハッシュテーブルができる。

    • しかしそれだと時間がかかるので本末転倒。

  • ユニークな要素数を推定できるアルゴリズムを用いる。

HyperLogLog アルゴリズム

  1. 文字列ごとにハッシュ値計算する。

  2. ハッシュ値の最後に連続している 0 の数を数える。

(例) 最大で 0 が 5個連続しているものがあった場合

  • そのような要素が出現する確率は [tex: \frac {1} {28} = \frac {1} {256} ]

  • おそらく元の要素は 256 種類程度あったと推測できる。

  • 実際は複数の数をハッシュ値を使って複数の予測値を出して、それをすべて合わせることで、よりよい精度で推測を行う。

MapReduce パターン

  • 共有ライブラリのシンボルを参照している未定義シンボルがあり、PLT/GOTを作る場合などに用いられる。

  • ベクタを小さいブロックに分けて、並列に処理する。(Map フェーズ)

  • ブロックを処理した結果として、少量のデータを出力する。

  • 少量のデータをシングルスレッドで処理する。(Reduce フェーズ)

速いプログラムを書くために

  • 推測せず、計測する。

  • 凝ったコードより自然と速くなるようなデータ構造を考える。

  • 複数実装して、一番速いものを選ぶ。

  • 何度か同じプログラムを書く。

    • 再び作ることでより学べる。

    • 最初からいい感じに作るのは無理。

    • 同じ実装で改善できる範囲にも限界がある。

    • lldb で実装すると書き直しになるので mold を作った。

感想

並列処理を学ぶことの重要性を理解することができました。

工夫次第で劇的に性能向上が期待できるということが学べて良かったです。

また lld と mold の実行速度の違いを例として見ることができたのでよりイメージが湧きました。

最後に教えて頂いた効率的なコードの書き方を今後意識していこうと思います。