冬学期
「オペレーティングシステム」講義案内

例題集

What's New

常時追加・更新中. 新しいものが上．お知らせなど随時掲載しますので，ちょくちょく「再読み込み」してください．

(投稿日 3/3)
- 試験の配点・採点基準・解答例・補足説明などを過去問ページに記しました
- 採点済み解答用紙を事務から返却しています. 自分の答案がどう採点されたか知りたい人は取ってください (点数は記入していません. ◯と, 上の配点を元に自分で計算してください. 満点は100ではなく86です. 最高点80. 平均点39.3)

(投稿日 2/24) オペレーティングシステムの試験を受けているが, 課題を一部または全部提出していない人あてに以下のような連絡を, ITC-LMSに登録されたメールアドレスあてに送信しています(該当しない人には送っていません). メールが届かない事態を恐れてここにも掲示しますが, 不安な人はITC-LMS上で課題の提出状況が自分の理解とあっているか確かめて下さい.

(ITC-LMSに登録されたメールアドレスに送信しています).

田浦です.

このメールは, オペレーティングシステムの試験を受けているが, 課題を一部または全部がITC-LMS上で提出されていない人に送られています.

課題1: unagi_serverのスレッド用いたgetの並列化 (締め切り2018/12/1)
課題2: unagi_serverのスレッド用いた安全な並列化 (締め切り2018/12/1)

間違いがないか確認し, 「きちんと提出したはずなのにITC-LMS上で提出されていない. 何かの間違いのはず」という場合は連絡を下さい. その際, 授業でコードやレポートの提出に用いたdoss-gitlab上の課題提出フォルダへのリンクも送って下さい(例: https://doss-gitlab.eidos.ic.i.u-tokyo.ac.jp/xxxxxx/unagi/tree/master/submit ).

注: あくまでシステム上の間違いで提出したはずのレポートが受け取られていないことがないかを確認するための連絡です. これからのレポート提出を受け付けるという意味ではありません.

(投稿日 2/5) 申し訳ありません. 「第2回課題」の詳細をここに公表すると約束しておりましたが, それを準備する時間が取れずに今に至ってしまいました. 成績報告の締め切りを考えると, 今から数日後に課題の詳細を発表しても, 締切の近い課題を急に出すことになり, 試験後に諸々の予定を入れていた人の都合を考えると迷惑を受ける人もいるのではないかと思いますので, 「第2回課題(概要)」はとりやめます. 概要に基づいて課題を実行した人には申し訳ありません (が, 試験でも関連した問題を出したので役に立ったのではないかと思います:-). 所用に時間を取られすぎ, こちらの思っていた授業・演習の準備ができずに終わり, 申し訳なく思っております m(_ _)m
(投稿日 1/7) UTASにもアナウンスしましたが, 明日(1/8)は休講です. 各自演習に取り組むなどしてください(来る必要はありません). 課題に関する詳細は引き続きこのページ上に掲載するので見続けてください.
(投稿日 12/11) sli.do (イベントコード: os1211) の質問に, 「今までの演習でやったmutex等の機能はhimonoにも追加する必要があるのでしょうか」というのがありました. 答え: 必要ありません(必須課題とはしません). ただし提供されているコードはオプション(-t 1)でスレッドを立ち上げるようにはなっています. lockだけ追加してくれれば(恐らくそれほど大変ではない) スレッド機能を移行することは, 比較的簡単にできると思います.
(投稿日 12/11) 第2回課題(概要) のための説明
(投稿日 12/11) オンライン質問用 sli.do イベントコード os1211
(投稿日 12/4) 12/11 の時間内に, 以下の説明と, 演習の時間を作る予定. PCの準備をしてきてください.
(投稿日 12/4)
unagiサーバの次の(+最後の)課題は, 以下のようなものになる予定.
- データを永続化(= ファイルに格納)できるようにする. それにより,
現在のunagiサーバは, 起動時には常に空の状態であるし, データは全て主記憶にしかおかないので, 主記憶を越えるデータを扱うのは難しい (正確には「スラッシング」がおこる). どちらもちゃんとした検索エンジンにはあってはならない状態.

関連して,
- データの検索を高速に行うための, 索引付けの機能
も必要になる. 現在はすべての検索を, 全ドキュメントをスキャン(頭から終わりまで全て読む)することで実現しているが, 遅い. ただし索引は, 多分にアルゴリズムの要素が強くOSの本題とはやや離れる, 索引にも様々なやり方がある, 正しく自力で実装するのは大変, などの理由から, こちらで参照コードを提供する (しかし例によって, 出す方の準備が間に合っていない状態orz). 検索については, 配列の2分探索 (binary search) を復習しておくと良い (2分「木」探索ではなく, 配列の2分探索).

課題を行う上での解説がたくさん必要なので必要事項の解説を次週(12/11)に行う予定.
(投稿日 11/20) すぐ下の投稿に関連して, 発表者を軽く募集してみる.
(投稿日 11/20) 半分余談: SpectreとかMeltdownに関する最近の論文とそれに関する記事 (他にも多数)
(投稿日 11/11) 11/13 はこの授業ありません(全学的な補講日).
(投稿日 11/6) 今日授業で見せた実験を自分でやりたい人用のページ: メモリ管理に関する演習 (興味のある人用に公開します. 課題とは無関係です)
(投稿日 11/6) 課題の提出方法について演習・課題の実施手順のページに書きました(要約: 中身はgitで提出. ITC-LMSを使って報告のための提出. 締切はITC-LMSを参照). 個々の課題については, 課題の説明フォルダを参照.
(投稿日 11/6) 課題2について, 詳細をアップしました. 課題の説明フォルダの02thread_put.mdを見て下さい.
(投稿日 11/6) 予告: 以下の2個の課題の締切は,
多分, 3週間後(11/27 ごろ)
になる予定です. 相変わらず提出手順など詳細未定義ですいませんが, 追ってアナウンスします. 内容ですが, 長い作文は課しません. 所定の手順で走らせる(こちらで実行, 確認)ことができるコードを, gitlabで提出し, 正しく実行し, 性能測定を行ったということがわかるログのようなもの(だけ)の提出とする予定です (翻訳: 実際にプログラミングを実行する以外の部分を多く課さない). 詳細指示は常に gitlab の所定のフォルダに書きます.
(投稿日 11/6) 詳細は後日書きますが, 2個目の課題は以下のような感じになる予定です.
最初の課題(以下)を拡張して, put (ドキュメントの追加)要求が他の要求と並行してやってきても正しく処理できる(データが壊れない) ようにせよ. ヒント: 授業でやった Pthread の mutex を使えば良い. ただしそれだと get 要求まですべて排他制御して処理することになる. Pthreadの reader writer lock という物を使うと, reader しかいない間はそれらを並行に走らせることができる.
(投稿日 10/30) 今日の授業と演習に関する質問は, sli.do で「も」受け付けます. イベントコード os1030 を入力して下さい. なにか動かないみたいなことで悩まずお気軽に(追いつける限り処理します).
(投稿日 10/30) 演習・課題の実施手順詳細版. 以前の指示に従って作業をし始めている人も, こちらに従って下さい.
(投稿日 10/16) 詳細は後日書きますが, 最初の課題は以下のような感じになる予定です.
スレッドを用いて, サーバが複数の接続を並行に処理するようにせよ. そして, 多数の get, getc 要求を並行に処理できるようにせよ. ただしそのとき, put (ドキュメントの追加)要求が他の要求と並行にやってくることはないと仮定して良い. 言い換えれば, もしputが他の要求と並行にやってきたら, 異常動作, サーバが終了するなど, 何がおきても構わない (「動作は未定義」が仕様). putを並行処理することの何が問題かは本日の講義で理解してください. ヒント: 関係個所は run_server という関数. 接続を受付け, 出来た接続を処理する関数 server_process_connection が, 新しいスレッドによって処理されるように書き換える.
(投稿日 10/16) 演習の課題の詳細とか, 何を提出するのとか, 締め切りとか, どうなのっていう質問があると思いますがもう少しお待ちください m(_ _)m 詳細(難易度の調整, 提出方法, etc.)を詰めているところです (言い換え: 諸事情により田浦の処理が追いついていない). ある日突然難しい課題を出して「来週締め切り」とかはしませんので, 待っていてください.
(投稿日 10/9) 上記 (投稿日 10/30)の新しい手順に従って下さい. 以下をすでにやった人はすいませんがもう一度上記に従い, すでに書いたコードなどは変更点をマニュアルで切り貼りして下さい. 演習用題材をまずはダウンロードしてください. gitコマンドが使える場合は以下です.
git clone https://doss-gitlab.eidos.ic.i.u-tokyo.ac.jp/tau/unagi.git
使えない場合は, ダウンロードボタンがページの上の方にあるので, 好きなものを使ってダウンロードしてください. 今日は紹介と以降の予定を説明します. 質問を sli.doでevent code 4405 と入力して投げてください.
(投稿日 10/2) 10/2の授業中に見せたプログラムを, 自分で試してみたい人向けに公開します. ページの最下部にプログラムへのリンクがあります (注: 昨年度までの演習ページです. 今年度の演習では使う予定ありません. 自習したい人向け).
(投稿日 10/2) 次回(10/9)演習をします. PC持参お願いします. 以下のいずれかの環境を用意してください(gccでUnixシステムコールを使ったプログラムが動かせる環境). 事前テストの仕方や, 環境のセットアップの仕方は来週までにここにあげるのでこまめに見てください.
- Linux
- Mac OS
- Windowsしかない人は以下の選択肢. おすすめ順(調査の結果順序が変わるかも)
  - 仮想マシン + Linux
  - Windows + Bash on Windows (調査中)
  - Windows + cygwin (あまりおすすめしない)
(投稿日 9/21) 2018年版HP開設

以下は 2017 年度の記録

(投稿日 1/4) 新年最初の(唯一の)授業予定日1/9の授業は休講にします.
(投稿日 12/9) 今日の発表は非常に良い発表でした. 4年生以降, 自分で発表するときに真似して欲しい点がいっぱいありましたので書き残します.
(投稿日 12/12) 12/19の, 浅井さん, 王君による発表で取り上げる論文です. 興味のある人は事前に読んでおきましょう.
Performance Implications of Extended Page Tables on Virtualized x86 Processors 発表資料, 元論文
(投稿日 11/28) 12/19に, 浅井さん, 王君による発表があります.
発表テーマ: 仮想マシンに関して
(投稿日 11/21) 来週11/28に, 後半はメモリ管理に関する演習をします．この演習をやるために, 仮想マシンと, 仮想マシンへの小さなLinux環境のインストールをやっておいてください(授業中にやらないように).
(投稿日 9/25) 来週 10/3の時間内に演習を行うので，準備をしておいて下さい (特に普段Linuxを使っていない人は，環境を整えておいて下さい．トラブルがあったら質問・相談してください)
(投稿日 9/25) 2017年版HP開設

スライド0 (pdf, ppt), 資料0 (pdf, doc).
スライド1 (pdf, ppt). 資料1 (pdf, doc).
スライド2 (pdf, ppt). 資料2 (pdf, doc),
スライド3 (pdf, ppt), 資料3 (pdf, doc).
スライド4 (pdf, ppt), 資料4 (pdf, doc).
スライド5 (pdf, ppt), 資料5 (pdf, doc).
スライド6 (pdf, ppt), 資料6 (pdf, doc)
スライド7 (pdf, ppt), 資料7 (pdf, doc)
スライド8 (pdf, ppt),
スライド9 (pdf, ppt),

オペレーティングシステム(OS)とは

すでに自宅などでパソコンを使っている人は多いと思います．マイクロソフトのWindowsという製品名はほとんどの人が聞いたことがあるでしょう． Linuxというのももはや新聞に載る単語になりました．これらはみなオペレーティングシステムの実例です．通な人は"Solaris"というOSもあることを知っているでしょう．

OSはコンピュータを動かすにあたって，最も基本的なソフトウェアです． OSの厳密な「定義」は難しく，左のような言い方でごまかすのが普通です．OS が何か？という問いに対する短い答えを追い求める代わりに，OSのないコンピュータとそうでないコンピュータの(その上の応用ソフトウェアを作る人の立場から見た)違いについて簡単に触れるのが有益かと思います．

OSのない，「裸の」コンピュータでも，プログラムを作ることは可能です．しかしそれには非常な手間がかかります．まず，コンピュータにつながれた記憶装置（ハードディスク，CDROM，フロッピーディスク，メモリスティックなど）や，ネットワークとのデータのやり取りが恐ろしく大変になります．同じ記憶装置でもディスクとメモリスティックではデータの読み方が違います．「ディスクのどのトラックの何番目のセクタを読め」，というコマンドを発行する変わりに「"OS講義案内"というファイルを読みたい」という，より抽象的な命令で，プログラムが必要な情報を入手できれば便利です．OSはこのような外部記憶装置に対する，統一的なインタフェースを与え，プログラムが，必要な情報がハードディスクにあるのか，フロッピーにあるのか，などの（ほとんどの場合はどうでもいい）違いを考慮せずにプログラムを書くことを可能にします．
それだけではありません．もし一度に動くプログラムが一つだけであれば OSの役目はさほど大きくなかったでしょう．しかし実際にはひとつのコンピュータ内に同時にウェブブラウザが動き，ワープロが動き，ゲームが動きます．OS のないプログラムでこれを実現しようと思うと大変なことになります．コンピュータに搭載されているCPUは，与えられた命令列を順に実行するだけの機械です．裸のコンピュータで，ブラウザ，ワープロ，ゲームを同時に動かしたければ，それらを組み合わせた一つのプログラムを書いて，それぞれの実行を「少しずつ，代わりばんこに」実行するような処理を，プログラマが書かなくてはなりません．しかしそれは今日のプログラマが行っている作業ではなく，個々のプログラムはブラウザならブラウザ，ワープロならワープロ「のみ」に集中し，それらを「代わりばんこにちょっとずつ」実行するのはOSが行ってくれます．
最後に，OSの重要な機能に，保護機能があります．OSのない裸のコンピュータでは，一つのプログラムが処理を間違えると，コンピュータ全体が機能停止に陥ることが容易に起こり得ます．ワープロソフトのバグのせいで，コンピュータ全体が機能停止に陥り，リセットボタンを押す羽目になることが容易に起こるのです(Windows 98, Windows Meや，昔のMacintoshを利用している人は日常経験していることと思います)．これは，それに対し，基本的な「メモリ保護機能」を備えたコンピュータは，通常のプログラムが勝手に他のプログラムや OSのデータを破壊することがないように作られています．この機能なくしてはプログラム開発が困難になるばかりでなく，複数の利用者が安心して同時に利用可能なコンピュータを作ることは，そもそも不可能です．

なぜオペレーティングシステムを学ぶのか？

卒業論文，またはその後の研究において，オペレーティングシステムそのものや，ネットワーキング（インターネット），プログラミング言語，セキュリティ，並列・分散計算など，その他あらゆる，コンピュータの基盤に関わる研究をしたいと思っている人は，迷わずオペレーティングシステムを学ぶべきです．オペレーティングシステムを学ぶことは，大雑把に言って，コンピュータソフトウェアが根本的なところで「どう動くか」を学ぶことと同じです．

オペレーティングシステムの研究をしたい人にはなんの説明も必要がないでしょう
ネットワーキングのように，コンピュータの入出力機構はオペレーティングシステムの中にインプリメントされています．日々進化するネットワーキングハードウェアを実際にプログラムから利用可能にするためには，デバイスドライバと呼ばれるソフトウェアを書く必要がありますが，これを動かすためには，オペレーティングシステムが根本的なところでどう動いているのかを学ぶ必要があるでしょう．
プログラミング言語やライブラリの実装の中には，OSの提供する機能(仮想記憶など)を駆使したものがあります．たとえばメモリ管理やチェックポインティング（実行中プロセスの状態を退避する）ために，OSの仮想記憶が使われます．OSを学ぶと，素人（失礼!）にとっては「摩訶不思議な」機能の実装方法を理解することが出来ます．
セキュリティは，オペレーティングシステムのにならず様々なソフトウェア（時にはハードウェア）の連携により実現されるものですが，どのような役割分担がされていることを知ることは，将来新たな提案をするための第一歩といえるでしょう．
並列・分散計算は，ネットワーキングやセキュリティなどの技術を組み合わせて，多数の計算機を用いて高性能な計算を可能にする技術です．そこでは， OSを単なるブラックボックスとして見たのでは，機能や性能上の重要なポイントをしばしば見失ってしまいます．たとえば，OSは「あたかも各プログラムが 1つのコンピュータを占有しているかのような錯覚」を与えてプログラミングを簡単にしますが，実際には100msとか，そのくらいの間隔でプログラムの間を切り替えながら実行しています．この事実を知らずにいると，複数のプログラムの待ち合わせに，busy wait この言葉の意味がわからなければ授業にきてください）を用いることが，どのような場合に良く，どのような場合に悪い選択なのかが理解できません．

私はコンピュータのシステムそのものの勉強がしたいのではなく，コンピュータを使った情報処理（自然言語，画像，音声，etc.）ができればそれで満足だ，細かいOSの機能などはどうでもよい，という人もいることでしょう．そのような人にも，単位を取る以上の動機付けをあたえるとすると以下のようになるでしょう．

まず，およそどんなプログラムもOSの提供する機能を使わずにプログラムができることはありません．そのようなプログラムはアルゴリズムの授業に出てくるだけで，実際にはそれらのアルゴリズムを，ディスクやネットワークからの情報と組み合わせてプログラムを作ります．その意味で，およそプログラミングに関わる人は全て，OSが提供する機能(API)を学ぶ必要があります．しかし，APIを学ぶときに，UNIXやWindowsのマニュアルとにらめっこするのは，あまり知的なやり方ではないでしょう．そうではなく，どんなOSでも，（まともなOSならば)提供している「はずの」機能に対する鳥瞰図を得ておき，必要に応じてマニュアルを見るのが正しい方式です．
より重要なことは，マニュアルを読むのでもほとんどの場合，基本的なOS の背景知識が必要になることです．例えば以下はUNIXのmmapというAPIに関する説明です．これを初めて読んで，理解できる人は少ないでしょう．これがいったい何をするためにあるのか，どういう場面で役に立つのかを理解するには，マニュアルを奥深く読むのではなく，「OSの基本」について学ぶのが最も近道であり，まっとうな道です．

OSを学ぶ気になったでしょうか？

講義の進め方

普通の講義と同様，教室での講義をすることになると思います．ただし， OSは黒板の上で説明するだけで面白いものではありません．OSを学ぶのは，コンピュータの最もweirdな(「変な」)部分を学ぶことですから，コンピュータにたくさんさわらずに，あるいはさわったとしても，メールやWEBを使うだけではOSを「体感」することはできません（これはOSの役割が「縁の下の力持ち」でることを考えれば当たり前です）．したがって，ときおりプログラミング演習的な要素を取り入れる予定です．

単位も普通に試験で行うことになるでしょうが，これもOSは筆記試験だけで出来を決めるのは，体育の試験を筆記試験でやるのに近いものを感じます．そこで，プログラミング演習で力作を課して，その出来によっては試験を免除するということも考えています．詳細は授業中にお知らせします(どんなことが行われたかは以下を見ると少しはわかるでしょう)．要するにプログラミングのためにコンピュータを長時間触る(コンピュータ好きがコンピュータに「ハマル」)機会を作りたいと考えています．

また，もうひとつの選択肢として，授業の最後の方の時間を利用して，少し高度な内容を本や論文から調べて，発表してもらうという時間を作りました．ちょっと高度すぎたかも知れませんが，同様の主旨の企画は今年も作ろうかと思っています．

単位のとり方

試験を受ける
授業内演習/その後の課題提出(2-3回)?
プログラミングチャレンジ: 授業中に述べたプログラム，それと同程度に高度なシステムプログラミング課題を達成する．課題案は授業中に紹介する．
本・論文購読チャレンジ: OSに関係する本のチャプターや論文を読んで内容を授業時間中に発表する．チーム(できれば2人まで．最大3人まで)発表可．最近の話題, OSの授業でカバーする話題の一歩先にあるような話について, 原典に当たって調べて発表してくれることを期待.
- Meltdown脆弱性について
- Intel SGXとはなにか? 脆弱性は?
- 仮想マシンの仕組み
- コンテナの仕組み
代表的カンファレンス. 多くは「何のことかわからない」論文かもしれませんが, これらの目次をスキャンして, 「読めそう, 面白そう」というものがあったら食らいつくという姿勢で良いです.

試験勉強の方が楽かもしれないが，興味・意欲のある人の取り組みを歓迎します．

教科書・参考書

特定の教科書は使いません．以下は私が参考にする本で，興味があれば入手してください．図書に推薦してありますので，おそらく図書に入荷すると思います(入荷していなかったら知らせてください)．どれか一冊読んでみたいが，迷っている人は1. を見るとよいと思います．このリストは今後も更新していきます．以下のいくつかの本には邦訳が出ています．英語で読むことをお勧めしますが，もし興味があれば探ってみてください．

Silberschatz et al.
Operating System Concepts Ninth Edition (ISBN 0471694665)
大部な名著です．名著ですがちと高すぎます...
Silberschatz et al.
Applied Operating System Concepts (Windows Xp Update) (ISBN 0471263141)
内容的にはほぼ，Operating System Conceptsと同一ですが，Windows XPなどに関するCase Studyが充実しています．
D.M. Dhamdhere
Operating Systems (ISBN-10: 0070611947, ISBN-13: 978-0070611948)
基礎的な内容から，マルチプロセッサ，分散システムまで充実した内容．
Andrew S. Tanenbaum
Modern Operating Systems (ISBN 0136386776)
古典的な話と，分散システムの話を広くカバーしている
Andrew S. Tanenbaum and Albert S. Woodhull
Operating Systems: Design and Implementation, second edition (ISBN 0135881870)
Minixという小さなOSを，ソースコードを掲載しながら細部まで説明している．
前川守
オペレーティングシステム (ISBN 4000103466)
日本語の大部な教科書．
野口健一郎
オペレーティングシステム (ISBN 4274132501)
薄めの要点解説的な教科書．
以下は，いわゆる一般的なOSの教科書ではありませんが，興味を持つ人もいるでしょう．
Gary Nutt.
Kernel Projects for Linux (ISBN 0201612437)
邦訳: 実習Linuxカーネル理論と実習カーネルを効率的に理解するための実習書 (ISBN 4894714566)
ここにある数々のプログラミング課題がすべてできれば，授業に出る必要はない．
Beck et al.
Linux Kernel Programming (ISBN 0201719754)
Linuxカーネルについての詳細な解説
Uresh Vahalia
UNIX Internals The New Frontiers (ISBN 0-13-101908-2)
UNIXについての詳細な解説
Jim Mauro and Richard Mc Dougall
Solaris Internals Core Kernel Architecture (ISBN 0-13-022496-0)
Solaris (UNIXの一種)についての詳細な解説．
Remy Card, Eric Dumas, and Franck Mevel
The Linux Kernel Book (ISBN 0471981419)
Linuxについての詳細な解説．
W. Richard Stevens
Advanced Programming in the UNIX Environment (ISBN 0-201-56317-7)
UNIXの，内部ではなくシステムコール(API)を解説．システムプログラマとしての腕を上げたい人向き．

講義項目(予定)

概論

「裸の」コンピュータ

CPU
メモリ
入出力機器

プログラマから見たOS: 基本概念

CPUの抽象化: スレッドとプロセス
メモリの抽象化: アドレス空間
外部記憶装置の抽象化: ファイルシステム
ネットワークの抽象化: ソケット

プロセスとスレッド

提供される抽象化

スレッド，プロセス
シグナル

C言語と機械語
事例: i386, SPARC, Alpha, IA64
CPUの多重化: コルーチンの実現法
割り込み
スレッドの状態
CPUの割り当てアルゴリズム

仮想記憶

提供される抽象化: アドレス空間
物理アドレスと論理アドレス
ページ表とTLB
ページング
ページ置換アルゴリズム

仮想記憶プリミティブとその応用

ページ保護のためのAPI
チェックポインティング
効率的な自動メモリ管理

ファイルシステム

提供される抽象化

ドライブ，ディレクトリ，ファイル
open/read/write
ファイルのメモリへのマッピング
アクセス制御
権限委譲

空き領域管理
ディスクのスケジューリング

過去の発表 (の不完全なリスト)

最近(2012年度末)になってようやくまとめました. もし過去にこの授業で発表をした人がこのページをたまたまおとずれ, 自分の名前が無いことを発見したら, 気を悪くせず, 発表資料を田浦まで送って下さい. 資料がない場合でも(過去の記録を真面目に持っていないので) 発表したという事実と年度をお送り下さい. むしろ最近のものが欠けている.

冬学期「オペレーティングシステム」講義案内