こんにちは。現在、無事にアメリカに入国して秋学期を過ごしています。それに先駆けて、日本でオンラインで夏に一つ授業を取りました。 その授業の内容について内容を纏めようと思います。
進学する大学院の詳細や経緯は以下の記事をご参照いただければと思います。
Introduction to Computer Systemsとは
「Introduction to Computer Systems」という名前の通り、Systems Programming=低レイヤプログラミングの入門編となっています。主に以下の内容を扱います。
- バイトでのデータ表現（2の補数、浮動小数点など）
- x86_64 アセンブリ
- バッファオーバーフロー
- CPUキャッシュ
- メモリアロケータ（Malloc）
- プロセス・シグナリング
- ネットワークプログラミング
- 非同期処理・スレッディング
この授業を元に、米国の数百の大学でもSystems Programmingのカリキュラムが組まれているとのことです。
クラス番号の意味
CMUでは、授業にクラス番号がついていて、その番号で授業を呼びます。 Introduction to Computer Systemsは15-213という番号が付与されています。番号自体は以下の意味を表します。
| 番号 | 意味 |
|---|---|
| 15 | Computer Science Departmentの意味 |
| 213 | 頭の2はレベルを表す。2なので、学部生の2年目以降から受けられる。 |
15-213はCMUのZip Codeでもあり、そういった意味でもCMUを代表する授業、と言われるそうです。1
この後 内容はくわしく説明しますが、学部生2年目からこんなハードな授業を受けているのか、と衝撃を受けるぐらい難しい授業でした。自分が学部2年生の時はCプログラミングでif文を覚えて満足していた記憶があります。
授業の構成
授業は主に以下の構成です。
- 講義 週3~4
- Lab （プログラミング課題）週1
- 記述課題 週1
- 中間試験
- 最終試験
特に、この授業の核となっているのはLabと呼ばれるプログラミング課題です。 自分も割いた時間のほとんどはこのLabでした。あとで内容を詳しく説明したいと思います。
受けるために必要なスキル
この授業を受けるために必要な知識なのは「C言語のプログラミング能力」 です。 すべての課題がCで出ます。Cが書けないと難しいでしょう。
以下が理解できていればよいかと思います。
- 関数
- 基本的な制御構文（if, for, while）
- 配列
- 構造体
- 動的メモリ確保
実際に、授業でもCがわからない場合はK&R本を読むことを勧められます。
個人的にはK&R本は古めかしい表現が多いので、「苦しんで覚えるC言語」が必要なCの範囲をカバーしており、かつ読みやすい本かな、と思いました。
なぜ受けようと思ったか
この授業は以下の授業を取るのに必須科目となっています。 だいたいソフトウェアエンジニアが一度は学びたい「○○作ってみた」の授業を取るには、この授業の単位取得が必須です。 ここらへんの授業は自分にとっても全力で受けたい授業なので、前のめりで取ることにした次第です。
- Database Systems 自作DBMSを作る授業
- Distributed Systems 分散システムを自作する授業
- Compiler Design コンパイラを自作する授業
- Operating System Design and Implementation OSを自作する授業
特に、Database Systemsは何度か「DBを自作しよう系」のブログでも取り上げられたりしているので有名かと思います。
記事にもある通り、Database SystemsはYoutubeで公式に授業が全公開されています。
自習で受けたい人向けの情報
この授業、他の大学も含めCouseraなどのMOOCでは自分で調べた限り、取り扱いがありませんでした。 そのため残念ながらオンラインでは受講できません。しかし、授業の内容自体はほとんど公開されているので自習することができます。
スライド
以下で公開されています。
スライドが非常に見やすいので、英語が読める方はスライドだけでも授業の内容はおおよそ理解できるかと思います。 自分も授業はほとんど聞かず、スライドだけ読んで学習してました。
授業のビデオ
Youtubeに非公式でアップロードされています。
ちなみに、この授業のイントロで、以下の事項は禁止されており2、場合によっては退学になる旨の説明があります。 このYoutubeの授業を勝手にアップロードした学生の方は無事なのかが心配です。
- 授業のカリキュラムや課題の回答をインターネットに公開すること
- 授業を修了した人が課題を手伝ったり、課題を教えたりすること
テキスト
テキストは以下です。 テキストは日本語に翻訳されたものがあります。
このテキストは、CSを独学する方向けのおすすめ教材まとめサイト TeachYourselfCSでも最初の必読テキストして挙げられており、いかに必読かがわかります。
ちなみに、日本語版はKindle版でも一万六千円というぼったくりナイスな価格になっています。
もし英語が読める方なら、英語版のほうが良心的な値段（三千円ほど）でおすすめです。
逆に英語が読めない方は、このテキストの日本語版を購入して読みこんで、Labをやるとよいかと思います。
自分は、テキストは補助教材として授業でわからない箇所を読みこんで利用してました。
Lab
Labも以下のページで公開されています。この記事を見て興味を持った方は、とりあえずLabを一個、二個やってみるといいかもしれません。
解答はありませんが、「CS APP 3e lab answer」でGoogle検索すると、Githubで実装例がたくさん出てくるのでそれを参考にするとよいと思います。3
また、Ubuntu 14.04での動作を前提としているので、Mac/Windowsの方は、Dockerで環境を作っておくとおすすめです。 最近ですと、dev containersで簡単に開発環境が作れます。
Labとは
この授業の核心であるLabについて、説明します。Labと名前はついていますが、プログラミング課題のことです。 授業で取り扱った内容について、実際に実装をしたり、クイズを解いたり、爆弾を解体したり（？）します。
このプログラミング課題は得点がすべて自動でつき、AutolabというCMU内製のシステムで得点が表示されます。
また、このAutolab上で全生徒の得点がScoreboardというランキングボードに表示されます。 得点だけでなく、各課題に応じた内容でランキングがつけられるというなんともストイックな内容になってます。
例えば、mallocを自作するmalloclabでは、mallocのスループットがランキングになり順位が付けられます。
malloclabで満点が出て、やったー！と思ったら、ランキングは100位とかで絶望します。同時にCMUの学生がいかに優秀かを思い知らされたりします。
Lab - プログラミング課題の詳細
Coda Lab
かかる時間: ★★☆☆☆
難易度: ★☆☆☆☆
課題の内容
文字列の結合や分割を簡単に行えるTrie木のようなデータ構造を用いて文字列結合や分割の機能を実装します。
学べる内容
- 前提知識のCプログラミングの確認
感想
ここで、前提条件のCのプログラミング力の確認が行われます。 最初からmalloc、ポイントなどがバンバン出てくるので、ここで躓くと今後、かなり厳しい戦いになると予想されます。
あと、お題目が木なので、少しアルゴリズムの知識も試されます。再帰を使った木の探索などもここで復習しておくとよいでしょう。 今後のお題でも、自力でlinked listぐらいの実装は行うので、アルゴリズムも復習しておくとよいかと思います。
Data Lab
かかる時間: ★★★☆☆
難易度: ★★★☆☆
課題の内容
ビット演算、足し算のみを用いて、さまざまな数値計算を実装する、というもの。
例: ビット演算を用いて条件分岐を実装する
/* * conditional - same as x ? y : z * Example: conditional(2,4L,5L) = 4L * Legal ops: ! ~ & ^ | + << >> * Max ops: 16 * Rating: 3 */ long conditional(long x, long y, long z) { long mask = ~!!x + 1; return (y & mask) | (z & ~mask); }
学べる内容
- 2の補数
- int, long, shortの使い分け方
- ビット演算
- 数値型の変換基本ルール（unsigned, signed）
- 浮動小数点
感想
ビット演算に苦手意識がある人（>>をプログラム中に見るとびっくりして頭真っ白になっちゃう人）にはおすすめです。 私はこれで苦手意識が無くなりました。
Redditでは、前半戦の中で最も難しいLabであるという評価もありました。確かに他のLabと比べると問題量や考える量は多かったです。 わからん！ -> 1日放置して解決策が思いつく、みたいな形で一朝一夕では終わらないLabであるのは確かでした。
Bomb Lab
かかる時間: ★★☆☆☆
難易度: ★☆☆☆☆
課題の内容
Mr. Evil博士が作ったとされるbombプログラムの中身を解読して爆弾の解除を目指す、という設定のLab。これだけ、なぜか急に遊び心が満載です。
渡されるのはコンパイル済みのバイナリのみで元のCプログラムは渡されないため、gdbを用いてひたすらx86_64のアセンブラを解読します。 誤った文字列を入力して、爆弾が爆発した場合、サーバーに連携されて-0.5ポイントづつ得点が引かれます。なんと、シビアな作りなんでしょうか。
学べる内容
- レジスタの使われ方
- x86_64アセンブラ
- バイナリ解析
- gdbを用いたデバッグ
感想
ひたすらgdbでデバッグするので、なんか昔、映画で見たハッカーってこんな感じなんだろうな、という感じでした。
あと、この課題を終えると「アセンブラ 読める。。。読めるぞ。。。」とムスカ大佐ばりに呟けるようになります。
Attack Lab
かかる時間: ★★☆☆☆
難易度: ★★☆☆☆
課題の内容
deprecatedなfgetsを用いたプログラムに対してコードを注入し バッファオーバーフローを起こし、プログラム中の本来、実行されないはずの関数を呼び出します。
学べる内容
- バッファオーバーフローを用いた任意のコード注入
- ROP(Return Oriented Programming)を用いたコード実行
感想
前回に引き続きハッカー気分を味わえます。
バッファオーバーフローって、ぶっちゃけここ最近は起きてないでしょ？って思ってました。 が、授業で、Twilight HackというWiiのゼルダの伝説 トワイライトエクスプレスでバッファオーバーフローを起こしてWiiのフォームウェアを書き換えるバグがあるらしく、今でも現役であることを教わりました。
Cache Lab
かかる時間: ★★☆☆☆
難易度: ★★★☆☆
課題の内容
二つのパートに分かれており、1つめは「キャッシュシミュレーターの実装」、2つ目は「行列計算をキャッシュを有効活用して高速化する」ものです。
学べる内容
- L1キャッシュ、L2キャッシュなどCPUとメモリの間にあるキャッシュ機構の仕組み
- キャッシュを意識したコードの高速化やパフォーマンス改善
感想
一つ目のキャッシュシミュレーターの実装については、授業で習った概念をひたすら実装すれば完成するのでそこまで難しくないです。 しかし、二つ目の「行列計算をキャッシュを有効活用して高速化する」は、キャッシュの構造やプログラムのキャッシュへのアクセスパターンを分析する必要があるため大変でした。
自分は、自作のスプレッドシートでアクセスパターンを分析して、高速化する方法をずっと考えていました。
Malloc Lab
かかる時間: ★★★★☆
難易度: ★★★★☆
課題の内容
mallocを自作します。チェックポイントと最終で2回の提出があります。 チェックポイントはスループットの最大化、最終はメモリ領域の最大有効活用（Utilization）を目指すのが目標です。
学べる内容
- Cのmalloc、メモリアロケータがどのように実装されているか
- Garbage Collectionの仕組み
感想
この課題が一番難しいという評判で、その評判に恥じぬ難しさです。 難しい要因としては、以下があります。
- Cのポインタ計算がそこらじゅうで出てくる
- 目標の達成方法が一つではなく、様々なやり方がある
- 今までのLabと比べて規模が2倍以上ある
ただ、課題が動いた後の達成感はすごいです。 同じプログラムの先輩に話を聞く機会があり、「今学期で一番うれしかった瞬間は？」と聞かれ「Malloc Labのテストケースが全部通った時」と答えてクラスが笑いに包まれていました。
それぐらい本学では有名な難問だそうです。
Shell Lab
課題の内容
tshと呼ばれる簡易的なシェルプログラムを自作します。
学べる内容
- fork, execve, waitpidのシステムコール
- プロセス間でのシグナリング
- ファイルディスクリプタ
- 標準出力、標準入力、システムIO
感想
malloclabよりは簡単でした。フォーク、プロセスやファイルディスクリプタについて無知だったので勉強になりました。
Proxy Lab
課題の内容
ネットワークプロクシを自作します。クライアントからURLを受け取り、サーバーにHTTPリクエストを発行します。返ってきたコンテンツをクライアントに返却します。 こちらもチェックポイントと最終で2回の提出があります。
チェックポイントは基本的なHTTPリクエストの処理・プロクシの処理の実装、最終はHTTPコンテンツをキャッシュする機構を実装します。
学べる内容
- Cを用いたソケットプログラミング
- Mutexを用いた非同期処理
感想
malloclabよりは簡単でした。非同期処理について無知だったので（以下略
