ryo’s blog

日々学んだことをまとめています.

2021年振り返り

軽い自己紹介

25歳ソムリエの Ryo です。以前はミシュラン2つ星レストランやワインバーに勤めていました。
現在はエンジニア転職を目指して、42TokyoでC言語を中心にコンピュータの基礎から学習しています。

はじめに

2021年を一言で表すと
「42」
これにつきます。
1月に入学試験のPiscineに参加し、4月に入学してから毎日約10時間以上を学習に費やしてきました。
そんな怒涛の一年間を振り返ってみます。

42で行ったこと

カリキュラム

  • libc, fgets, printfの再実装

  • TCP/IPサブネットマスクなどネットワークの基礎知識を学ぶ課題

  • DockerでLEMP環境の構築

  • シグナルを使ったメッセージの送受信を行う課題

  • 2つのスタックを限られた操作でソートする課題

  • X Window Systemのラッパーライブラリを利用してfractalを表示する課題

  • 食事をする哲学者の問題

  • bashの再実装(ペア課題)

  • debianをインストールしてパスワードポリシーやパーティションなどの基本設定を行う課題

  • IPv4のルーティングを学ぶ課題

その他

  • テストフレームワークの実装(ペア課題)

  • Go, Node.js, Vue.js の基本的な構文を学ぶ課題

  • 2週間に渡るPython版Piscineの参加

  • コードレビューを100回行う(課題によるが1回につき1時間程度)

  • 亀山会長に腹筋を見せる

  • Tutorになる

個人的に行ったこと
触った技術

C言語
1年間ほとんどCでコードを書いてました。 libcの再実装から始まり、2ヶ月間かけてbashの再実装を行ったりしました。

C++
主に競プロで利用していました。42の課題を通して基本的な構文やオブジェクト指向プログラミングについて学び始めています。

Python
42のPython Piscineをきっかけにちょっとした作業で使ったりしています。 Discord Botの作成、NBA API を利用したデータのグラフ化などを行いました。

Go
42の課題で軽く触れました。これから本格的に勉強していく予定です。

Node.js
Node.jsとsqlite3を利用してCRUD操作を行うREST APIを作成しました。

Vue.js
42の課題で軽く触れました。

印象的な課題

約2ヶ月に渡るbashの再実装は、これまで取り組んできた課題の中で一番濃かったです。
GitやNotionを利用して細かく情報共有を行いながら課題を進めていきました。
マニュアルやbashのソースを読みこむ必要があり、実装量も多いため時間をかけた分、学ぶことがたくさんあったように思います。
ここでコードの読みやすさや一貫性、機能の疎結合化などを意識するようになりました。
またペアの方がエンジニアとして10年以上の経験があったため、課題の取り組み方や実装方針の立て方、困難にぶつかったときの解決方法などを教わりました。
現在はここで学んだことを意識して日々の課題に取り組んでいます。

印象的なできごと

詳細は省きますが、亀山会長に腹筋を見ていただくという貴重な経験をしました。今年こそはマッチョになりたいです。
42TokyoのTutorになれたことも印象的でした。今後も積極的にコミュニティに貢献していきます。

今やっていること

Raytracingのペア課題に取り組んでいます。これでC言語の課題が終わるので1月中に完成させたいです。 C++、Goの勉強も少しづつ行っています。

今年の目標
  • firstcircle突破

  • AtCoder 入緑

  • アルバイト or インターン or 就職

  • ブログを月1回以上更新

改めて1年間を振り返って

42Tokyoで多種多様な人達と出会い、ともに成長していくことができたと思います。 さまざまな価値観や考え方に触れることで自分にない気づきを得ることもありました。 今後もピアラーニングを通じて成長していきたいです。

おわりに

出会ったすべての人に感謝です。2022年も頑張ります。

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

制作物

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);

シミュレーション方法

f:id:ryo_manba:20211228232250p:plain

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

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

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

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

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

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

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

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

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

f:id:ryo_manba:20211228232413p:plain
シミュレーション回数を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プレイヤーを決めてみた

はじめに

スター選手が多いことから伝説とされる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()

実行してみる。

f:id:ryo_manba:20211223124035p:plain

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

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

f:id:ryo_manba:20211223124038p:plain

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


そして本題の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()

実行してみる。

f:id:ryo_manba:20211223124016p:plain

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

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

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


終わりに

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

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

おまけ(2003年ドラフト)

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

f:id:ryo_manba:20211223124031p:plain

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

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

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章 ネットワーク・プログラミング

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 は LinuxTelnet を用いることができる。

  • 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

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章 仮想メモリ

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 が頻繁に呼ばれると、ヒープがごみでいっぱいになり、最悪の場合、仮想アドレス空間をすべて消費してしまう。


感想

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