東京大学「オペレーティングシステム」講義案内
田浦健次朗

1 What’s new

• 常時追加・更新中

• 新しいものが上

• お知らせなど随時掲載しますので， ちょくちょく「再読み込み」してください

• (投稿日: 2024/12/04) 12/04

  1. メモリ管理 ページ置換アルゴリズム
  2. ファイルシステム ファイルシステム, キャッシュ
  3. 演習 os10_cache
  4. ファイルシステム 先読み
  5. 演習 os11_prefetch

• (投稿日: 2024/10/29) 10/30 予定

  1. デッドロックをなにかに例える話に「いいね」をつけて下さい
  2. メモリ管理 アドレス変換の仕組み (MMU, ページテーブル, TLB), メモリ管理API, ページング, ページ置換アルゴリズム
  3. 演習 os09_vm

• (投稿日: 2024/11/02)

  1. os02_processの解答例を公開しました
  2. os03_threadの解答例を公開しました
  3. os05_mutexの解答例を公開しました

• (投稿日: 2024/10/29) 10/30 予定

  1. 並行処理と同期 デッドロック
  2. 演習 os07_atomic
  3. デッドロックをなにかに例える話
  4. メモリ管理 論理アドレス, 物理アドレス, アドレス変換
  5. 演習 os08_addr

• (投稿日: 2024/10/23) 10/23 予定

  1. 並行処理と同期 バリア同期, 条件変数
  2. 演習 os05_mutex, os06_cond_var
  3. 並行処理と同期 不可分更新命令, ビジーウェイト, 同期の実装, デッドロック
  4. デッドロックをなにかに例える話 (今日説明を終えられた場合)

• (投稿日: 2024/10/15) 10/16 予定

  1. OSをなにかに例える話, 溢れた分 遅ればせながら「いいね」がついたものを表示しています
  2. スケジューリング
  3. 演習 os04_sched
  4. 並行処理と同期 排他制御
  5. 演習 os05_mutex

• (投稿日: 2024/10/08) 10/09 予定

  1. 前回の宿題 (人数制限を超えましたと言って入れなかった人はこちら, ただし今はどちらも入れるようになっていると思います)に「いいね」を付けて下さい
  2. プロセス
  3. 演習 os02_process
  4. スレッド
  5. 演習 os03_thread
  6. スケジューリング

• (投稿日: 2024/10/01) 10/02 予定

  1. イントロ
  2. Jupyter環境お試し
  • Jupyter環境ユーザ名・パスワード入手 (UTOLの課題)
  • os00_intro
  • os01_install_linux
  1. プロセス
  • os02_process
  1. 振り返り課題 (毎週; 授業の翌日まで)
  2. 本日の宿題 OSをなにかに例えて下さい (締め切り: 明日まで). UTokyo Accountでサインインして下さい.
  • 一部の人が入れないと連絡を受けました。上記に入れなかった人はこちら からお願いします(一つのイベントの最大参加者数100人であることをを認識しておりませんでした)

• (投稿日: 2024/9/28) 2024年版HP開設

2 スライド

1. イントロ
2. プロセス
3. スレッド
4. スケジューリング
5. 並行処理と同期
6. メモリ管理 (仮想記憶)
7. ファイルシステム
8. ファイルディスクリプタと擬似ファイル
9. シグナル
10. ユーザレベル仮想記憶 API とその応用

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

• すでに自宅などでパソコンを使っている人は多いと思います． Windows, Mac OSという製品名はほとんどの人が聞いたことがあるでしょう． これらはみなオペレーティングシステムの実例です． サーバ用にはLinuxというOSが圧倒的に普及していますし, スマホ用のOSであるAndroidもLinuxが元になって作られています.

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

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

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

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

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

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

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

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

5 講義の進め方

• 普通の講義と同様，教室での講義をすることになると思います．ただし， OSは黒板の上で説明するだけで面白いものではありません．OSを学ぶのは，コ ンピュータの最もweirdな(「変な」)部分を学ぶことですから，コンピュータ にたくさんさわらずに，あるいはさわったとしても，メールやWEBを使うだけ ではOSを「体感」することはできません（これはOSの役割が「縁の下の力持ち」 でることを考えれば当たり前です）．したがって，ときおりプログラミング演 習的な要素を取り入れる予定です．
• 単位も普通に試験で行うことになるでしょ うが，これもOSは筆記試験だけで出来を決めるのは，体育の試験を筆記試験で やるのに近いものを感じます．そこで，プログラミング演習で力作を課して， その出来によっては試験を免除するということも考えています．詳細は授業中 にお知らせします(どんなことが行われたかは以下 を見ると少しはわかるでしょう)．要するにプログラミングのためにコン ピュータを長時間触る(コンピュータ好きがコンピュータに「ハマル」)機会を 作りたいと考えています．
• また，もうひとつの選択肢として，授業の最後の方の時間を利用して，少 し高度な内容を本や論文から調べて，発表してもらうという時間を作りました． ちょっと高度すぎたかも知れませんが，同様の主旨の企画は今年も作ろうかと 思っています．

6 評価 (2020年度)について

7 教科書・参考書

• 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] (http://www.amazon.co.jp/exec/obidos/tg/detail/glance/-/english-books/0136386776/0136386776/249-9962019-8008335) (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)を解説．システムプログラマとしての腕を上げたい人向き

8 講義項目(予定)

• 概論
  • 「裸の」コンピュータ
    • CPU
    • メモリ
    • 入出力機器
  • プログラマから見たOS: 基本概念
    • CPUの抽象化: スレッドとプロセス
    • メモリの抽象化: アドレス空間
    • 外部記憶装置の抽象化: ファイルシステム
    • ネットワークの抽象化: ソケット
  • プロセスとスレッド
    • 提供される抽象化
    • スレッド，プロセス
    • シグナル
  • CPUの割り当て(スケジューリング)アルゴリズム
  • 仮想記憶
    • 提供される抽象化: アドレス空間
    • 物理アドレスと論理アドレス
    • ページ表とTLB
    • ページング
    • ページ置換アルゴリズム
  • 仮想記憶プリミティブとその応用
    • ページ保護のためのAPI
    • チェックポインティング
    • 効率的な自動メモリ管理
  • ファイルシステム
    • 提供される抽象化
      • ドライブ，ディレクトリ，ファイル
      • open/read/write
      • ファイルのメモリへのマッピング
      • アクセス制御
      • 権限委譲