Operation System Concepts

OSについての教科書。メジャーなOSそれぞれで用いられている技術が解説されている。実装方法や思想の違いはあるけれども、基本的な仕組みは共通している。ベースを学ぶ本。※メモは途中から

• プロセス管理
• メモリ管理
• ストレージ管理
• セキュリティ
• 分散システム
• 特別な目的のシステム

英語の習熟が不十分なのでよくわからないところが多い。文章はわかっても、全体として何が言いたいのか不明なときが多い。とはいえ300ページ時点で最初のときより、はるかにわかる。慣れてきた。 章末にある問題は読むだけで、わからないものがほとんどであった。もっと考えよう。…ひどいものだが、それでも読みたいと思う。

何であれ自己満足に陥らないために大切なのは、テストだ…。章末問題は全然わからないし、後で何学んだかな？と思って書き出しても全然出てこない。ひどい。

とはいえ、前もって知っていたところもあるので、全然わからないということはまれだ。全部サイアクというわけじゃない。本文は読むのが遅い。が、各章の序文は非常に読みやすくすっと理解できる。少なくとも前には進んでいることがわかる。

• プロセス管理で必要なこと。マルチスレッド。スケジューリング。いくつかの戦略。長所と短所。
• プロセス、リソース、リクエスト。
• デッドロックしないように何が工夫されているか…防ぐ仕組み、検知する仕組み、復帰させる仕組み。各アルゴリズムの長所と短所。
• デッドロックが起こりうる条件。比喩→哲学者の食事、列。

• プロセスごとに2つのレジスタ…物理アドレスの下限、上限があり、CPUは範囲内でしかアクセスできない。これによって誤、不正アクセスを防ぐ?(レジスタはCPUとセットで、プロセスごとにはないと思うが…。)、物理アドレスを動かすのは難しいが、仮想アドレスを動かすのはカンタン。動かしやすくする。物理アドレスは制約がたくさんある…。
• 実行するときに物理アドレスと再配置アドレスをリンクさせる？論理アドレス。
• CPUは論理アドレスを使い、メモリは物理アドレスを使う。変換を行うのがMMU。
• ユーザープログラムは物理アドレスを見ることがない。
• スタブでロードを再利用する
• ロードするメモリを探す3つ戦略
• ページングの仕組み…図があるとわかった気になれる
• 階層になったページテーブル。p1+p2+d→大分類→小分類→idみたいな感じか？セクション＋ページ＋オフセット。この構造、パケットに似ている。
• 分割しまくる。2nd outer page。
• 32bit以上だと分割も数が多すぎになる。hashを使う？
• 共有して省メモリ。データ部分だけ、ユーザプロセスにする。

• たくさんメモリを割り当てても、必ずしもパフォーマンス改善につながらない。アルゴリズムを正しく選択しないと。
• page-fault rateとframeの数をちょうどいい感じにする…CPUとメモリのバランスを最適化。(frameってなんだっけ。)
• mapping
• buddy system, slab allocatorがよくわからず
• いろんなサイズのpageがある
• データ構造によってlocalityに違いがある…スタックはよいlocality→一番上ばかり使われるから。一方ハッシュはわるいlocality→アクセスがバラバラだから。データ利用の効率の違いになる。
• オブジェクト指向はlocalityが低くなる傾向がある
• I/Oとメモリ
• バーチャルメモリは、サイズが大きな論理アドレスが、小さな物理メモリにマッピングすることを可能にするためにある。
• PageとPage Frameの関係

• fileは一般的形式で、ユーザーによって決められる…文字列、ソースコード、バイナリ…
• OSが拡張子の対応方法を決めるのではなく、アプリケーションが決める。
• UNIXはファイルをシンプルなバイトの並びで定義している
• 論理レコードが物理レコードの始まりを示す…？
• 論理レコードから物理ブロックへの変換？…ブロックとレコードの関係がよくわからない。
• ディスクスペースは物理ブロックに分配されている。ブロックの最後はたいてい捨てられる。→internal fragmentationに苦しめられる
• シーケンシャルアクセス→順にアクセス…current pointer、next、rewindを使って、最も使われる。エディタやコンパイラはこの形式をよく使う。テープモデル。
• direct access→固定長の論理レコードを持つ。順番なし。ディスクモデル。
• indexファイルのindexを作る…
• パーミッションとかの各システムによる違い

• パーミッション、オーナー、タイムスタンプ、サイズ、…などのメタデータと、アドレス部分で構成されている。アドレスは辿っていく方式。メモリ管理の手法と同じで、ブロックで区切って穴を埋めていくことで、記憶空間を最大限使用できる。external fragmentationが必要ではない。ただし途中から読み込みができない。

↓しばらく飛んで

パスワードなど。認証はむずい。パスワードはメジャーな方法だが、難しすぎるとメモして流失し，短すぎると総当りされる。ワンタイムパスワードなどもあるがメンドー。生体認証などがトレンドになっている。

侵入や不正な行動を検知するプログラムがある。本当にヤバい行為かをうまく判断することが必要。 たとえば多すぎても意味がなくなる。

電磁波を読み取られることもあるので、非常に高いレベルのセキュリティを実現するには建物など物理面でも専用の設備を使用する必要がある。

Distributed Systemとはメモリなどを共有していないプロセッサのこと。それぞれ独立している。

LAN,WAN。

それぞれのネットワークの物理的な接続の形の利点。円、星、木構造…は信頼性やコストで一長一短である。

ネットワークコミュニケーションのデザインには5つの問題がある。

• 名前付け
• routing
• packet
• 接続
• 競合

名付け…wiki.a9ne.comの場合、comのname serverに最初にといあわせてa9ne.comのアドレス?をもらう。次にa9ne.comのname serverにwikiを問い合わせる?とにかく、最初はグローバルなアドレスのname serverからはじまるというコト。

routing。前で言ったように、通信する経路はさまざまである。 経路を決める戦略として、固定とか動的に決めるとかある。 普通はコスト的にどこかを経由することになるので、動的に決めるのが便利である。通信する中で経路の情報をやりとりするプロトコルを使う。

ルーターは、データを他のネットワークから受け取ると自分のネットワークに流すか、ほかの目的地の経由かを判断する。

packet。メッセージの長さは不定長だが、不便なので固定長のpacketを用いる。 一度パケットの交換を確認できると、sessionをつくる。 やりとりには3つの方法がある。

• circuit switching → ハード的に一つのリンクを作る。接続中はほかのは使えない。電話線でインターネットをするときどっちかしか使えないのと同じ。
• message switching
• packet switching → 分割して送信して、送信先で組み立てる。同時に通信ができる。それぞれが目的地を持っている。

• 帯域を最も効率的に使うためpacketが用いられる。
• 同時送信して競合が起こると、通知して再送信することを要求する。
• それぞれのレイヤーは対応したレイヤーと通信する。それぞれのレイヤーはプロトコルを持っている。実装がハードウェアのときもある。

Physical Layerは0か1かで表され、ハードウェアに組み込まれている。

• パケットにはそれぞれのレイヤーのヘッダーがくっついている。
• ISOネットワーキングよりTCP/IPのほうがはやい

DFSの目的はファイルが分散システムの間で物理的に分散しているとき、同じ共有をサポートすること。

• 影響力のあるものに、AFS(Andrew File System)がある。
• service: ひとつまたは複数のマシンで実行され、clientに機能を提供しているソフトウェア。
• server: ひとつのマシンで実行されているサービスソフトウェア。
• client: クライアントインターフェースを構成する、ひとまとまりの操作を使ってサービスを呼び出せるようにするプロセス。?
• DFSはそれらのservice, server, client, 記憶装置が分散システムの間で分散したファイルシステムである。
• サービスの活動はネットワークを通して行われる。ストレージも中央ではなく分散している。
• たが、複数性や分散は見えないようにしている。
• ネーミングは物理と論理のマッピング(対応付け)である。→ ネットワーク、メモリでも出てくる
  • ファイルの名前は物理的な記憶場所のいかなるヒントも与えない
  • ファイルの名前はもし物理的な記憶場所が変わっても変える必要はない。
  • 場所に依存しないので、共有したときに同じ名前を使用できる。
• ディスクのないシステムもある。ネットワークのソフトウェアを保存する場所すらない。ブート時に特殊なことをする。
• 流行は、ローカルディスクとファイルサーバを両方使うクライアントである。OSやネットワークソフトウェアはローカルに保存しておき、ユーザーデータはリモートに保存する。
• NFSはSunの network file system。多くのUNIXシステムがサポートするファイルシステム。接続したときのマウントが自動でされるようになった。
• もっとも複雑でメンテナンスが難しいのがNFSである。どこでもアタッチできるので、木構造がいびつになるため。
• ネットワークとディスク入出力を減らすため、キャッシュをうまく利用する。アクセスはリモートからローカルにキャッシュしたものに対して行われる。これで同じリソースに対する追加のトラフィックが発生しない。いっぽうで元のファイルに変更を反映させる必要がある。
• キャッシングユニットを大きくするとヒット率が上がるが、失敗したときのペナルティも大きくなる(以前の章でやったな)。
• キャッシュする場所はどこがいいか、ディスクか、メモリか?ー早くて、大容量化が進みコストの低くなってきているメモリ。ディスクだと復元できたりもする。
• キャッシュアップデートの方針(ディスクとの整合性を保つため…)
• サーバ側もキャッシュを持ち、書き込みのときに使う?(よくわからない)
• キャッシュを最新のものに保つ仕組みは、サーバかクライアントが持つか両方がある。
• 書き込むときは常にキャッシュを更新し、読み込みは時間で定期的に読み込む。
• キャッシュ…
  • ローカル: 早いが矛盾する可能性
  • リモート: 矛盾しないが遅い
• statefulとstatelessなサービス。クライアントのリクエストの内容について知っているか否かでわける。知っていれば効率的にでき、statefulといえる。
• よくわからん!!つまらん!!
• AFSシステムの基本は、サーバーからファイル全体をキャッシュすることである。
• キャッシュ一貫性
• AFSは機能豊富なDFSであり、場所に依存しない+透明性に特徴あり。一貫性のセマンティクスを提供。キャッシングとレプリケーションを使用してパフォーマンスを向上させる。

OSによるプロセス同期は以前の章でやったが、今回は集中型同期メカニズムを分散環境に拡張する方法、分散システムでデッドロックを処理する方法、をやる。¹⁾

• 実行の順番を決定することは重要である。最悪デッドロックが起きるかもしれない。ローカルにあるような集中システムでは共通のクロックとメモリがあるため、順番を特定することができるが、分散システムでは難しい。これを説明していく。
• 「AのあとB」のような関係があると前後が決定する。ない場合は並列して実行できる。
• 時空図で表す。
• 共通のクロックがないのでタイムスタンプを使うとか。
• 論理クロックを追加する。タイムスタンプを追加する。小さければ先に実行されたとみなせるが、すべてを保証するわけではない。実行するプロセッサのさの違いによって入れ替わることがある。
• すべてにタイムスタンプをやる方法はデッドロックや飢餓を起こさないが、名前付け、一つのプロセスがだめになると動かなくなる、などの問題がある。
• トークンを発行する方法もある。トークンを持っているプロセスしかアクセスできないので、一度に一つしかアクセスできない。
• いじめっ子アルゴリズム…失敗していないプロセスの中からコーディネーターを決める。デッドロックを特定する?
• めっちゃ出てくるコーディネーターって何？失敗したときに重要なようだが
• デッドロックを検知するのか、予防するのか？

今までの章では一般的なコンピュータシステムだったが、この章では特別な目的のシステムを扱う。リアルタイムさが要求されるような、特にマルチメディアシステムについて。

• 厳しい時間の制約がある。デッドラインがすぐ来る。
• ソフト(レンジ、MP3プレーヤ、食洗機、PC…)とハード(車、飛行機の制御システム)なコンピュータがある。
• リアルタイムシステムのカーネルは極めて単純である。一般的なOSに比べて。
• リアルタイムシステムの2つの遅延…Interrupt latency, Dispatch latency
• rate-monotonic scheduling → CPUを必要とするやつは低優先
• Earliest-deadline-first scheduling → 早いものが高い優先順、理論的に最速
• Proportional Share Scheduling → プロセスタイムを分ける
• Multimedia Systems, 基本的にはメディアファイルは今までのファイルと同じだが、どこが違うか。アクセスのタイミング、大きさ。遅延に敏感。
• live stream → ネットラジオ
• on-demand stream → Netflix²⁾
• 直面する問題
  • 圧縮とデコードは、CPUパワーを必要鳥栖区
  • デッドラインに間に合うように優先順位を決めるタスクスケジュール
  • ファイルシステムは、継続的なメディアの要求に応えられるよう効率的である必要がある
  • ネットワークプロトコルは遅延を最小化しながら、帯域幅の要件をサポートする必要がある
• QoS(Quality of Service)の変数
  • 処理能力
  • 遅延 → クライアントがデータを受け取るのに待つ時間
  • jitter → ストリームの再生「中」に起こる遅延。多くの場合、5秒間の量のデータをバッファすることにより補正している。
  • 信頼性
• Admission control → リソースなどちゃんとリクエストを受け取る準備ができているとき、サービスをする。これは日常生活ではふつうに見られる。映画館とか。席が満杯だったら入れないじゃない。
• 関連するスケジューリング…CPU、ディスク(タイミング要件、レート要件がむずい。矛盾する)
• CPUの観点からは、締め切りが近いプロセスを実行するのがよいが、ディスクヘッドの動きは無視される。ディスクのスループットに悪影響が生じる。
• ネットワークを介してサーバがクライアントにコンテンツを送る方法
  • Unicasting: 1つのクライアントに送る
  • Broadcasting: すべてのクライアントに送る。データを受け取るか受け取らないかによらず。
  • Multicasting: クライアントのグループに送る
• Unicastingの1つのセッションごとに同じ内容を保持するのは大いなるムダである。Broadcastingも必要ないところに送るのでムダだ。ほとんどのストリーミングメディアはMulticastingで送られている。
• 最初にWEBサーバとメタファイルのやりとりをして、メディアサーバの位置を教えてもらってメディア用のプロトコルRTSPで通信する。HTTPSはステートレスなので、プレーヤー操作ができないため？
• RTSPは有限状態機械init, ready, playing を遷移するコマンドを提供する。
• QoSを保証することはできない、そのため受け入れのコントロール(アドミッションコントロール)で、リクエストごとにシステムが受け入れる要求にあうレベルを分ける。
• CPUとディスクスケジューリングは、たいていスケジューリングの基準として、メディアタスクの締め切り要求を用いる。
• ネットワークマネジメントは、遅延やjitterをコントロールし、また再生の間違う位置に移動させるため、プロトコルの使用を必要とする。

• カーネルとシステムを区別して考えると便利である。
• カーネルはコミュニティでゼロから書かれたソフトウェアで、システムはほかから持ってくることもある。部品はほかの部品を強制せず、ほかのものを使うこともできる。ディストリビューションはそうやっていろんなソフトウェアの組み合わせでファイルシステムパッケージシステム、ネットワーク監査を提供している。
• Linuxシステムを導入するには正確にコンパイルする必要があったが、ディストリビューションとしてコンパイル済みのLinuxシステム、ソフトウェアをパッケージするようになった。³⁾
• Linuxシステムは主に3つに分類される。
  • カーネル
  • システムライブラリ
  • システムユーティリティ
• カーネルはモノリシックなバイナリである…一度にすべて読み込まれることにより、切り替えコストがかからない。OSのすべての要素…タスク管理とかネットワーク…を含む。その下にモジュールがあり、これは読み込まれるかどうかは起動時に決定する。たとえばCDドライブが接続されていればCDドライブのドライバを読み込み、なければ読み込まない。