まっつーのブログ

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

モンテカルロ法を用いた四目並べAIを作ってみた

C/C++

制作物

github.com

はじめに

C++で立体四目並べのプログラムを作成しました。

ただ交互にコマを置いていくだけだと、おもしろくない(そもそも戦う相手がいない)ので、敵を作ることにします。
なるべく強キャラにするため、モンテカルロ法というアルゴリズムを用いて実装してみました。

モンテカルロ法って？

ランダムな候補手で終局までゲームをシミュレーションし、その中でもっとも勝率の高いものを次の手として選択するアルゴリズムとなっています。

シミュレーション回数が少ないと得られる結果はデタラメとなってしまいますが、回数を増やすことでより統計的な分布を得ることができます。

このアルゴリズムを利用したコンピュータ囲碁が世界トップ棋士を倒したことが一時期話題になっていましたね。

実装

四目並べの盤面を 縦 6 x 横 7 としているため、置ける手数は 7 通りあります。
それぞれ 1~7 に対して順番にシミュレーションを行うことで最善の手を選ぶような実装にします。

実装する上で注意する点は

  • 勝利判定
  • 盤面の継承
  • シミュレーション方法

の3点でした。

順に説明していきます。

勝利判定
愚直に縦横斜めに4つコマが並んでいるかをチェックします。
またすべてのコマが埋まっている場合引き分けとなります。

盤面の継承
シミュレーションをするために、ユーザーの代わりのAIと相手のターンにプレイするAIの2つで盤面を共有する必要があります。
そのため、それまでの盤面のコピーのオブジェクトを生成して、2つのAIそれぞれでコピーしたオブジェクトを参照するようにしました。

そうすることで本来の盤面に影響を及ぼさずにシミュレーションを行うことができます。

Board copyBoard = board; // これまでの盤面のコピー
 // それぞれ同じ盤面を参照する。
Cpu userCpu(1, copyBoard);
Cpu ememyCpu(2, copyBoard);

シミュレーション方法

それぞれの手に対して、最も勝率が高いものを探します。

シミュレーションの流れは以下になります。

  1. プレイヤーがコマを置く。

  2. int score[7] を0初期化する。

  3. 一手目を決め打ちする。(1~7)

  4. 互いにランダムでコマを置きあい、勝利したら score[一手目] += 1(scoreを増やす)

  5. 指定されたシミュレーション回数分 3、4 を繰り返す。

  6. もっともscoreが高い手を選択してコマを置く。

  7. 決着がつくまで 1 から繰り返す。

シミュレーション回数を100にした場合の例

void Cpu::montecarlo(const Board &board, int depth)
{
    if (depth >= g_maxDepth) return; // 指定した回数になるまでシミュレーションを行う
    playOut(board, depth);
    montecarlo(board, depth + 1);
}

こんな感じで再帰的にシミュレーションしていました。


以上の3点に気をつけることで、つよつよの四目並べAIを作ることができました。
めでたしめでたし。

感想

今回の実装はいわゆる原始モンテカルロ法でそれぞれの手に対して複数回のシミュレーションを行うだけでした。そのため実装もかなりシンプルにできたと思います。
それぞれの手を成長させていくモンテカルロ木探索というアルゴリズムもあるので気が向いたら試してみたいです。

興味ある方はぜひ戦ってみてください〜。

参考

モンテカルロ木探索-コンピュータ囲碁に革命を起こした新手法

nba_apiを使って1996年ドラフトNo.1プレイヤーを決めてみた

Python
はじめに

スター選手が多いことから伝説とされる1996年ドラフトで
誰がNo.1なのかnba_apiを使って決めてみました。

方法としては、各スタッツの合計値をもとにグラフで表示し確認しています。
言語はPythonです。


制作物

github.com


まずはnba_apiを使って、stats.nba.comから情報を取得します。
サイト内にあるサンプルコードをもとに試してみます。

from nba_api.stats.endpoints import commonplayerinfo

def main():
    # データを取得
    player_info = commonplayerinfo.CommonPlayerInfo(player_id=2544)

    # DataFrameオブジェクトに変換
    pd = player_info.player_headline_stats.get_data_frame()
    print(pd)

if __name__ == '__main__':
    main()

$ python3 main.py
   PLAYER_ID   PLAYER_NAME TimeFrame   PTS  AST  REB    PIE
0       2544  LeBron James   2021-22  25.9  6.8  6.6  0.161

いい感じに選手の情報が取得できていますね。


次にこの情報を元にmatplotを使ってグラフにしてみます。

from nba_api.stats.endpoints import commonplayerinfo
import matplotlib
import matplotlib.pyplot as plt

def main():
    # データを取得
    player_info = commonplayerinfo.CommonPlayerInfo(player_id=2544)

    # DataFrameオブジェクトに変換
    pd = player_info.player_headline_stats.get_data_frame()

    # 各項目を取得
    pts   = pd['PTS'][0]
    ast   = pd['AST'][0]
    reb   = pd['REB'][0]
    name  = pd['PLAYER_NAME'][0]
    frame = pd['TimeFrame'][0]

    # matplotの設定
    left   = [1, 2, 3]
    label  = ['PTS', 'AST', 'REB']
    height = [pts, ast, reb]
    fig    = plt.figure('NBA STATS')

    plt.bar(left,height, tick_label=label, align='center')
    plt.title(name + ' (' + frame + ')')
    for x, y in zip(left, height):
        plt.text(x, y, y, ha='center', va='bottom')
    plt.show()

if __name__ == '__main__':
    main()

実行してみる。

おおー。いい感じにグラフにできました。
さすがレブロン、36歳でこのスタッツですからね。すごすぎる。

またplayer_idを変更することで他の選手のデータも取得できます。
以下に選手の情報がまとまっているので参考にしました。
https://github.com/djblechn-su/nba-player-team-ids/blob/master/NBA_Player_IDs.csv

ウェイドのスタッツもこんな感じで取れます。
引退してる選手に関してはキャリアスタッツが取得できるみたいですね。


そして本題の1996年のNo.1プレイヤーを決めていきます。
調べてみると ID が連番になっているみたい(なっていない選手もいるが今回は割愛)なので、ドラフト1位から順番に60位までの情報を取ってみます。

from nba_api.stats.endpoints import commonplayerinfo
import matplotlib
import matplotlib.pyplot as plt

ID_IVERSON = 947
NB_DRAFT   = 59

def get_info(id):
    player_info = commonplayerinfo.CommonPlayerInfo(player_id=id)
    return player_info.player_headline_stats.get_data_frame()

def get_players_info(start, end):
    pd = None
    for i in range(start, end):
        try:
            pd = get_info(i)
            print(pd['PLAYER_NAME'][0])
        except:
            continue

def main():
    get_players_info(ID_IVERSON, (ID_IVERSON + NB_DRAFT))

if __name__ == '__main__':
    main()

Allen Iverson
Marcus Camby
Shareef Abdur-Rahim
Stephon Marbury
Ray Allen
Antoine Walker
Lorenzen Wright
Kerry Kittles
...(下に続く)

正しくデータが取れてそうです。

あとはポイント、アシスト、リバウンドの平均値を計算してグラフにしてみます。

from nba_api.stats.endpoints import commonplayerinfo
import matplotlib
import matplotlib.pyplot as plt

class my_nba:
    ID_IVERSON = 947
    NB_DRAFT   = 59

    def __init__(self):
        self.pd      = None
        self.index   = []
        self.score   = []
        self.players = []

    def get_info(self, id):
        """
        選手情報を取得
        """
        player_info = commonplayerinfo.CommonPlayerInfo(player_id=id)
        self.pd = player_info.player_headline_stats.get_data_frame()

    def get_players_info(self, start, end):
        """
        指定された範囲の選手情報をインスタンス変数に追加していく
        """
        index = 1
        for i in range(start, end):
            try:
                self.get_info(i)
            except:
                continue
            try:
                pts   = self.pd['PTS'][0]
                ast   = self.pd['AST'][0]
                reb   = self.pd['REB'][0]
                name  = self.pd['PLAYER_NAME'][0]
            except IndexError:
                continue
            self.players.insert(0,name)
            self.index.append(index)
            index += 1
            score = (pts + ast + reb)
            self.score.insert(0,score)

    def plot_bar_graph(self, year):
        """
        横棒グラフを表示する
        """
        plt.barh(self.index, self.score, align="center")
        plt.yticks(self.index, self.players)
        plt.title(str(year) + " Draft Players Score")
        plt.show()

def main():
    print("Please wait...")
    nba = my_nba()
    nba.get_players_info(nba.ID_IVERSON, (nba.ID_IVERSON + nba.NB_DRAFT))
    nba.plot_bar_graph(1996)

if __name__ == '__main__':
    main()

実行してみる。

できました！(見づらいのでクリックして見てみてください)

1位 Allen Iverson
2位 Kobe Bryant
3位 Stephon Marbury
という結果となりました。

文句なしで1位はアイバーソンですね！
コービーファンとしては悔しい結果となりましたが、正しく表示できたので良しとしましょう。


終わりに

各ポジションごとに得点の重み付けを変えてみるとより面白いかなと思いました。また時間があるときに試してみようと思います。
それとPythonでグラフを線描するのが初めてだったので面白かったです。

NBA大好きなので今後も気分転換に遊んでみようと思います。
それでは良いNBAライフを！

おまけ(2003年ドラフト)

開始idをいじると他の年代も表示することができます。

未だに現役の選手に関しては昨年のスタッツになっています。
それにしてもレブロン強すぎる。。

第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 のような仕組みができるようなので、試してみようと思います。