理学部情報科学科3S
書かないと記憶の彼方に消えてしまうと思うので簡単な振り返りメモです。
対象読者 : そこのあなた
後輩に有益かどうかはわかりません。2Aについては同期のブログ
kammer0820.hatenablog.comが詳しいです。
課題のネタバレなどはなるべくないように注意したつもりなのでご安心ください(?)
諸々の成果物は以下にあげてあります。
github.com
ネタバレ回避のためにバイナリのみです。(使い方のdocumentはそのうち整理したい)
- 月2 オペレーティングシステム
- 月3,4 システムプログラミング実験
- 火2 離散数学
- 火3,4 関数論理型プログラミング実験
- 水2 情報論理
- 木2 言語処理系論
- 木3,4 ハードウェア実験
- 金2 計算機構成論
- 金3,4 情報科学演習Ⅰ
- 課外
- まとめ
月2 オペレーティングシステム
講義名のとおりOSの仕事や仕組みを一通り学びました。
- プロセス管理、プロセス間通信
- CPUスケジューリング、リアルタイムスケジューリング
- メモリ管理(仮想記憶、ページングなど)
- I/Oシステム
- ファイルシステム、ディスクスケジューリング
などです。はじめの方はシスプロと連携が取れている感じになっていて、ここで学んだことをシスプロで実際に触ってみることが多かったですが途中からお互いに独自路線に走っていきます。
スライドの量が膨大な上に抽象的な図が多くて試験前に焦りますが試験はスケジューリングなどの計算問題がほとんどを占めるので無意味に暗記しなくても大丈夫です。試験は1問15分で解くことが想定されていて、試験時間が75分で、大問が6問でした(?)
月3,4 システムプログラミング実験
各週でやったことを順に書きます。
パソコンの常識みたいなのがある程度教えてもらえるので純粋培養競技プログラマーみたいな人でも安心です。このあたりでman pageを読みまくったり困ったらとりあえずstraceしてみることを覚えました
- マルチスレッドプログラミング
pthreadを使って遊びます。２分探索木をスレッドセーフに書き換えたり、Bounded bufferを書いたりします。
- ソケットプログラミング
UDP echo serverやTCP echo serverを書いたりネットワークのスループットを測ったりしました。マルチクライアントに対応するのにpthreadを用いるのは楽でしたがepollを使う方法は大変だった記憶があります。epollの仕様難しい。
- シェル作成
普段つかっているbashのようなものを作ります。2Aの計算機プログラミングで吉本先生が板書していたよくわからないforkのコードの意味がようやくわかりました。多段パイプやリダイレクト、fg,bgなどのジョブ管理を実装しました。プロセスごとにファイルディスクリプタの状況が違うとかを理解しておらずめっちゃハマりました。各々なにかしらに躓いたりテストスクリプト通らん！とか言いながら夜までみんなで実装するのは結構楽しかったです。
最後に完成版として提出したishは上げてあります。多分いじわるすると壊れます。
- カーネルプログラミング
linuxカーネルのコードを読んだり、システムコールを追加したりします。カーネルのコードがどこまでいってもマクロだらけでびっくりしました(小学生並みの感想)
- ベアメタルプログラミング
ベアメタルプログラムはOSに依存せずに自力でハードウェア上で動作するもののことで、OSに依存しないので下手をするとパソコンがぶっ壊れますが、
TAさんが準備してくださった環境のおかげで仮想マシン上の、ものはクラッシュしてもPC全体はクラッシュしないようになっていました
MMUの仕様を理解して指定された物理アドレスを指定された仮想アドレスにマッピングしたり、atomic命令を用いてspinlockを実装したり、タイマのレジスタを読みだしたりしました。
TAさんが準備してくださった環境のおかげで実装量がとても少なかったです。
NIC(Network Interface Controller)のドライバを書いて、パケットを送受信してMACアドレスを読み取ったり,ARP requestを受信してARP replyを送ったりしました。documentを読みまくりますが、結構わかりづらかったり似たような表だらけだったりで大変でした。
火2 離散数学
グラフ理論、線形計画、フロー、双対性、マトロイドなどを扱いました。個人的にはほぼ既知の内容でしたがいつも結果ばかり使っていて証明できるかは怪しかったのでよい復習になりました。
テストで行列を答案に写し間違えたりすると無駄な単体法を実行して終了するので注意しましょう！
火3,4 関数論理型プログラミング実験
主にOCamlとPrologを扱います。毎回レポートが100点満点で採点される1300点満点の競技です(違う)
- 序盤
OCamlの基礎的な文法や型の扱い、モジュールシステムやモナドなどを扱いました。モナド難しかったです。
- 中盤
OCamlでOCamlライクな関数型言語のインタプリタを作成します。序盤に比べてやればできる課題が多かった印象です。
最新verとして提出したOCamlインタプリタは上げてあります。
- 終盤
いきなり大きくかわって論理型言語としてPrologを扱います。SLD導出や閉世界仮説について学びました。最後にはPrologライクな言語のインタプリタを作成しました。
本筋とは関係ない単一化とかでめちゃくちゃバグらせて悲しかったですが最後は納得のいくインタプリタができたのでよかったです。こちらも上がってます。
- 最終課題
これまた打って変わってリバーシのAIを実装する課題がでました。これについては別記事で上げてあります(リバーシAIを実装した話 - okura diary)
水2 情報論理
大きく２つに分けるとLogicとComputabilityの授業です。LogicではEquational logic,Propositional logic,Predicate logicなどを扱い、それらの健全性、完全性などを学びました。別のformalismとしてResolutionを学んだりHerbrand's structureやSkolemizationも学びます。ComputabilityではPrimitive recursive functionから始まってrecursive function,while program,universal recursive functionなどを学び、それからSmn定理やrecursion theorem,Rice's theoremなどをやってからHaltがnot recursiveでrecursively enumerable(RE)なことやnot HaltがREでないことを示し、そして最後にGödel's incompleteness theoremを示す、という流れでした。前期教養の記号論理学では自然演繹を扱いますがこの授業ではシーケント計算(LK)を扱います。記号論理学よりもformalな内容で新鮮で面白かったし、蓮尾先生の教科書がとてもわかりやすく楽しかったです。
木2 言語処理系論
いわゆるコンパイラの授業です、コンパイラの流れにしたがって字句解析、構文解析、意味解析、中間コード生成、レジスタ割り付け、最適化などを一通り学びます。小林先生のスライドは各ステップが細かくのっているので後からみてもわかりやすいです。FLと内容が結構重複している上にFLで先にやることが多いの授業は気軽に聞けます。
試験には毎年LR(0)オートマトンやSLR構文解析表が出るのでたくさん書いてオートマトン職人になりましょう、あと二村射影が出ます[要出典]
木3,4 ハードウェア実験
はじめの方はブレッドボードで回路を作ったりします、どれだけ確認しても正しいのにうまく動かなくて、結果汎用ICが壊れてたことがありました(つらい)
途中からはvivadoをつかってFPGAで遊びます。IPコアを組み合わせて遊ぶ分には楽しいのですが、後半でSystem Verilogでモジュールを書く必要がでてきてからは全然テストを通ってくれなかったりして大変でした。具体的には浮動小数点加算(fadd)やUARTでの通信、AXI4バスの転送などをやりました。デバッグ方法が難しくて毎回長い時間溶けましたが班員に助けてもらいつつなんとか乗り越えてました。低レイヤーの厳しさを痛感しました。
金2 計算機構成論
コンピュータアーキテクチャの授業です。坂井先生が書かれた教科書(指定されている)がわかりやすくて、4月の1週目に全部読んでしまいました。簡単な模式図から始まって各ユニットがどんどん詳細になっていくのでとてもわかりやすいし視覚的にも楽しいです。途中にアーキテクチャから１つ選んで発表するという回があります。
内容としてはパイプライン、キャッシュ、仮想記憶、並列実行(複数命令発行、アウトオブオーダー実行など)などで、OSとかぶる部分が結構あります。
課外
- パタヘネゼミ
パタヘネの上下巻を読んで発表しあいました。OSや計算機構成論とかぶる部分が多いですがここで複数回触れていたおかげでより頭に定着したような気がします。
来年こそは...見とけよ。
まとめ
充実してたかどうかはわかりませんが、課題に追われたり地下や食堂で駄弁ったりいろいろ楽しかったのでOKです。
