OSテストのシケプリ

叩き台として作りますた。 修正などあれば、適宜お願いします。

07/14 20:00 -- version 1 by Y.Sawa

07/15 01:30 --update by Y.Sawa

--

デッドロックとは

 プロセス1が資源Aをロックしている状態でさらに資源Bをロックしようとする。
 プロセス2が資源Bをロックしている状態でさらに資源Aをロックしようとする。
 これが同時に起きると、どちらのプロセスも資源を使えず、またロック解除も行えない。
 これをデッドロックという。

プロセスの飢餓(餓死:starvation)とは

 スケジューリングには、以下のようなものがある。
 ・到着順(FIFO、FCFS)方式
   到着したものから順に最後まで終わらせていく方式。
 ・ラウンドロビンスケジューリング
   一定時間(time quantum)ごとに順番にプロセスやスレッドを選んで実行する。
 ・Shortest Job First CPUスケジューリング(処理時間順方式)
   過去の履歴等から一番早く終わるものから実行していく
 ・プライオリティスケジューリング(処理時間順方式)
   優先度の高いものから順に実行していく。
 ・フィードバック待ち行列方式
   優先度の高いものから実行するが、ただし一定時間で終わらなければ優先度を下げる。
 
 プライオリティスケジューリングでは、I/O処理の完了待ちなどの理由で
 優先度が低くても実行されることがあるが、
 そういったI/O処理などがないプログラムの優先度が高いと、
 優先度が低いものはまったく実行されないままである。これをプロセスの飢餓という。

スラッシングとは

 物理メモリの容量は、(近年増加しているとはいえ)あまり多いものではない。
 従って、ハードディスクによる仮想メモリなどを使用することが多い。
 すると、ハードディスクから物理メモリに読み込んだり物理メモリからハードディスクに
 書き込んだりするような処理を行う必要がある。
 この処理は、アプリケーションが多くのメモリを要求すればするほど発生するが、
 そうするとハードディスクやメモリへの読み込み・書き込み処理が
 処理の中で大部分を占めるようになり、外部からの入出力を受け付けられなくなったり
 などのようなCPU利用効率が低下した状態に陥る。
 この状態をスラッシングという。

CPU使用率とは

 各プロセスやカーネルCPU処理がCPUを占有する時間と
 Idle時間を含めた全時間の比である。

スループットとは

 単位時間当たりの処理能力のこと。これは高ければ高い程良い。

ターンアラウンドタイムとは

 指示を出してから、全てが完了するまでの時間。これは短くできる方が良い。

応答時間(レスポンスタイム)とは

 ターンアラウンドタイムと似ているが、入力完了から最初の応答が得られるまでの時間
 入力完了と、指示を出すタイミングは異なり、また最初の応答と全てが完了のタイミングも異なる。
 従って、ターンアラウンドタイムよりは必ず短い。これも短くできた方が良い。

待ち時間とは

 待っている時間。すなわち、自分の番になるまでの時間である。
 計算方法は、ターンアラウンドタイムから実実行時間を引いたもの。短くできた方が良い。
 一度自分の順番になってから、もう一回ready状態になったときの時間も加えられることに注意。

VFSとは

 様々なファイルシステムに対して、抽象的にアクセスできる仕組みのこと
 そのために、ファイルオープンやファイルリード等のようなシステムコール群の
 インターフェース(API)を提供する。
 そして、そのインターフェースに合致するような関数を各ファイルシステム用に作る。
 ユーザーはそのAPIに合致するように関数を呼び出せば、どのようなファイルシステムに
 対しても、同じようにアクセスできる。

プロテクションとは

 各ファイルにおいて、どのユーザーがどのような権限を持っているかを制御する機構のこと
 アクセスコントロール方式では各ファイルに、どのユーザーがどのような権限を持っているか
 という情報を持たせる。
 それに対して、Capability List方式では、各ユーザーに、どのファイルにどのような
 権限を持っているかを記述する。
 
 例えば、アクセスコントロール方式
 file hoge:
     sawa: write read, kojima: execute, nakajima: read
 file foo:
     sawa: execute, kojima: read
 というようなデータを記述する。
 
 Capability List方式
 domain sawa:
     hoge: write read, foo: execute
 domain kojima:
     hoge: execute, foo: read
 domain nakajima:
     hoge: read
 というデータを持たせる。

二相ロックとは

 使う資源を一度に全て確保してしまい、また一度に全て開放する手法。
 これにより、まず時間差で資源を確保することが無くなるのでデッドロックが少なくなる。
 そしてまた、トランザクションがひとつずつ実行されているのと同様の状態(直列化)を保持できる。

Virtual Machineとは

 ハードウェアの上に、仮想的にハードウェア機能と同じ機能を提供
 仮想計算機同士は保護(通信は可能だが、メモリは非共有)
 仮想計算機上で特権モードでも、実際の計算機ではユーザーモード
 QUEM、VMWare、Java VM

ここからその他解説

システムコール関連

 基本は演習にて。
 ・プロセス制御
   fork, kill
 ・ファイル管理
   open, read/write, close, link
 ・デバイス管理
   ioctl -- deviceを管理する
 ・情報管理
   どんなのがあるんだろうね？
 ・Communications
   pipeとか？
 過去問では、実際のプログラムを記述させるものもあり。演習でやった実装を思いだせば大丈夫だと思うけど。

同期問題関連

 ・Race Condition(競合状態)
   二つのプロセスが同時に同じ値をインクリメントすると、場合によっては1しか増えなかったりする。
 ・クリティカルセクション(きわどい領域)問題
   プログラムの競合アクセスがあり、同期を取る必要があるプログラム部分
   排他制御が必要となる。(Mutual Exclusion)
   また、少なくとも一つのプロセスは実行する必要がある(全てが待ち状態にはならない)(Progress)
   さらに、各プロセスは有限時間で実行完了(Bounded Waiting)
 ・Busy Wait
   無限ループでプロセスを待たせること。良くない。
 ・Bounded-Buffer問題
   排他処理が必要。
 ・Readers-Writers問題
   reader同士は共有可能。writerのみ排他的というモデルを考え、それを以下に実装するか。
 ・Dining-Philosophers問題
   複数資源を必要とし、かつ資源取得の順序付けが循環的である場合、デッドロックが発生する。

プロセス間交信

 ・通信路の確保
   パイプやソケットのようにプロセス同士が、お互いのプロセスを知っている場合(直接交信)と、
   メールのようにお互いに知らなくても良い場合(間接交信)がある。
 ・ブロッキング処理
   通信時において同期を取るのがブロッキング。取らないのがノンブロッキング
 ・バッファリング処理
   バッファが0だと、ブロッキング処理となる。
   バッファが有限(Bounded capacity)だと、バッファがいっぱいの時には送信プロセスは待つ
   バッファが無限(Unbounded capacity)だと、送信プロセスは待たなくて良い
 ・シグナル
   killシステムコールによる通信

スレッドとプロセス

 OS演習で実装した通り。
 スレッドの利点：
 ・別の作業を同時に処理できる(例えばユーザーへの応答と、内部の計算処理)
 ・資源を共有できる
 ・メモリの有効利用
 ・各スレッドは、別のCPUに割り当てることが出来るので、
   マルチCPUの場合でも処理を振り分け可能
 
 ユーザーレベルスレッドと、カーネルレベルスレッド
 ・ユーザーレベルスレッドはユーザーレベルで実現。スケジューリングもユーザーレベル。
 ・カーネルレベルスレッドはオペレーティングシステムカーネルで実現。
 
 マルチスレッド実現モデル
 ・ユーザーレベルスレッドと、カーネルレベルスレッドとの対応
 ・Many-to-One、One-to-One、Many-to-Many

トランザクション

 ・ACID特性
   Atomic(原始性)、Consist(一貫性)、Isolated(隔離性)、Durable(永続性、耐久性)
 ・Atomic
   各トランザクションが中途半端に実行されていることを禁止する。
   もし、途中でエラー終了した場合は、そのトランザクション実行前にまき戻す
 ・Consist
   トランザクションの開始時点で矛盾がなければ、終了時点でも矛盾がない
 ・Isolated
   並列実行しても、順に実行した場合と同様の結果が出ること。
   すなわち、ロックを駆使して調整する必要がある。
 ・Durable
   トランザクションが終了した場合、その後再実行の必要がないこと。
   つまり、一度実行すれば障害が発生してもデータベースから消えない。

CPUスケジューリング関連

 ・コンテキストスイッチ
   プロセス切り替えのこと。オーバーヘッドがすごい。
   実行中のプロセスの状態をPCBに保存。次に実行するプロセスの上体を取り出す。
 ・new -> ready, ready -> run, run -> wait, wait -> ready, run -> terminate
   他のプロセスに横取りされない場合は、この状態変移となる。
   横取りの場合には、run -> readyになる。
 ・Preemptive、Nonpreemptive
   Preemptiveは一定時間経ったりすると、CPUスケジューラーによって横取りが発生
   Nonpreemptiveは横取りされない。
 ・ラウンドロビン
   上述。超重要。