雑記

いち情報系大学生

OS学習メモ2 (3.1-3.7章)

まとめ2回目。前回の続きで2.5章からまとめようかなって思ったのですが(ここ面白かったんですけど)実装メインの内容だったので、恐らくこれから手を動かしてやっていくうちに何度も後から見るだろうなって思ったので3章から。

3章 入出力

OSの主機能の一つはコンピュータの入出力デバイスを制御すること。デバイスに指令を送って、割り込みを受け取って、そして必要に応じてエラー処理をする。

 3.1.1 入出力デバイス

入出力デバイスは、ブロックデバイスとキャラクタデバイスの2つに分けられる。情報を固定長のブロックに格納するのがブロックデバイスで、それぞれのブロックを他のブロックとは独立して読み書きできるという特徴がある。そして、そんなブロック構造を意識せずに文字列を送受信できるのがキャラクタデバイスである。ただ、この分類はいくつかのデバイスには適合できないものもある。…とは言えこの2つの概念は、OSが入出力に依存しない処理を行うための基礎概念としては十分なもの。

 3.1.2 デバイスコントローラ

入出力装置は一般に電子部品と機械部品から成る。

これらは、多くの設計や製品に使えるよう切り離すことが可能で、電子部品はデバイスコントローラ/アダプタと呼ばれている。機械部品はデバイスそのもののこと。

 

OSは通常、デバイスそのものではなくコントローラに対して処理を行う。

コントローラの仕事は、連続したビット列をバイト列のブロックに変換して、必要に応じてエラー訂正を行うこと。チェックサムを計算してブロックにエラーが無ければ、メインメモリへコピーされる。

3.1.3 メモリマップドI/O

それぞれのコントローラは、CPUと通信するためにいくつかのレジスタを持っている。これらに書き込みを行うことで、OSはデバイスに対しデータの送受信やON/OFFを指定することができる。またレジスタを読み出すことでデバイスが次のコマンドが実行可能かどうかを知ることもできる。メモリマップドI/Oとは、通常のメモリアドレス空間上にI/Oレジスタが共存して、メモリのR/WのCPU命令をI/Oにも使用するというもの。

 

3.1.4 割り込み

制御レジスタは、「出力が完了したか,新しいデータを入力デバイスから受信したか」を判定するためのビットを1つ以上持っており、デバイスが新しいデータの送受信が可能になるまでCPUはこれをチェックする。これは、ポーリング又はビジーウェイトと呼ばれる。

これに加え、多くのコントローラは、コントローラ自身のレジスタが読み書き可能になると、割り込みによってそれをCPUに通知する。これによりCPUは処理が中断され、割り込みハンドラの実行が開始する。

 

3.1.5 DMA(Direct Memory Access)

大きなデータブロックを転送するディスク装置のようなデバイスでは、CPUがI/Oコントローラに対して一度に1バイトずつデータを要求していたのでは時間の無駄である。そこで、ハードウェアを利用した高速な転送を行うためにDMAを使う。


3.2 入出力ソフトウェア

3.2.1 入出力ソフトウェアの目標

入出力ソフトウェアの設計においては、特定のデバイスに限定されずにどんな入出力装置にもアクセスできるプログラムを書くこと、つまりデバイスに依存しないことが重要(ネーミング規定/エラー処理/転送時の同期非同期問題/バッファリング/デバイスの占有と共有 など)

 

入出力ソフトウェアは以下の4つの階層で構成できる

  __________________

  |  ユーザレベルの入出力ソフトウェア   |

  |__________________|

  |デバイスに依存しないOSソフトウェア  |

  |__________________|

  |     デバイスドライバ     |

  |__________________|

  |      割り込みハンドラ     |

  |__________________|

| ̄                        ̄|

|       ( ハードウェア)           | 

|______________________| 

 

3.2.2 割り込みハンドラ

割り込みを意識しなくて済むよう、OSは内部でその処理を隠す必要がある。一番良いのは、入出力が完了して割り込みが発生するまでドライバの入出力を中断してしまうこと。

 

3.2.3 デバイスドライバ

コンピュータシステムは、入出力デバイスを制御するためのデバイス固有のプログラムを必要とする。このデバイスドライバと呼ばれるプログラムは通常デバイスのメーカによって作成される。一般的にデバイスドライバの仕事は、上位のデバイスに依存しない、ソフトウェアからの抽象的な命令を受け付けてその要求を実行すること。

 

3.2.4 デバイスに依存しないOSソフトウェア

デバイスドライバとデバイスに依存しないOSソフトウェアの厳密な境界線はシステムによって異なる。この階層の基本的な機能は、全てのデバイスに共通な入出力機能を実装しユーザレベルのソフトウェアに対して統一したインターフェースを提供すること。

 

3.2.4  ユーザレベルの入出力ソフトウェア

大部分の入出力ソフトウェアはOSの内部にあるが、ユーザプログラムにリンクしてライブラリとなる部分があり、これはカーネル外で動作する。とは言っても全てのユーザレベル入出力ソフトウェアがライブラリ関数で構成されるというわけではなく、マルチプログラミングにおいて占有型の入出力デバイスを実装するときにはスプーリングシステムが用いられることがある。これはデーモンだけがデバイスにアクセスできるようにするというシステムで、ユーザが必要以上に資源を専有して他のプロセスが利用できなくなるということを防ぐ仕組み。

 

3.3 デッドロック

デッドロックとは、「2つ以上のプロセスがお互いの終了を待った結果、処理が先に進まなくなってしまっている状態」のこと。これを防ぐために、OSは、プロセスが特定資源へ排他的にアクセスできることを保証する機能を提供している。

 
3.3.2 デッドロックの現地

Coffmanはデッドロックの発生条件として以下の4つを定めており、これらが全て揃うとデッドロックが発生する。

 

①現時点で、各リソースはたった一つのプロセスに割り当てられている。もしくは利用可能な状態になっているかのどちらかであること

②現時点で先に獲得したリソースがあっても、さらに新しいリソースを要求できること

③プロセスに割り当てられているリソースは、そのプロセスが明示的に解放しなければ強制的に取り上げられることがない

④2つ以上のプロセスが環状につながっていて、それぞれが次のプロセスが保有するリソースを待っている状態

 

続く以下は回避策

 
3.3,3 ダチョウアルゴリズム(ostrich algorithm)

デッドロックが発生する可能性は、実は非常に小さい。そんなデッドロックの問題を解消するためにわざわざ制約をかけたりするよりも(ダチョウが砂の中に頭を突っ込んで見ないふりをするかのように)問題を無視してしまえという方式(名前のセンスが好き)

 

3.3.4 検知して回復する方法

リソースの要求や解放が行われるたびにリソースグラフ(有向グラフを使ってリソースの状態を表したもの)を更新して、グラフがリング状になっていないことをチェックする。もしなっていた場合はリングの中のプロセスのうち1つを削除する

 

3.3.5 デッドロック防止

そもそも構造的にデッドロックが起きないように出来ないかを考える。
先に挙げたCoffmanの発生条件を解消するような制約を考える

①1つのプロセスに排他的に割り当てるリソースがなければデッドロックは起きないため、スプーリングを用いてこれを解決する。…と言っても、全てのデバイスでスプーリングができるわけではない。

②リソースを保有しているプロセスが他のリソースを待ち合わせないようにするという方法。しかし、この方法はリソースを最適に使われない等の問題点がある。

③プリンタの出力最中で強制的にリソースを取り上げるのが困難であるように、3つ目の条件からのアプローチは難しい

④これにはいくつかの方法がある。1つ目は「プロセスには一度に1つのリソースしか使用を認めない」というルールにすること。ただし、プロセスが巨大なファイルをテープ装置からプリンタにコピーする場合がある場合この方法は成り立たない。2つ目の方法は、全てのリソース全体に通し番号を付ける方法。プロセスは必要とするリソースを要求できるが、必ず全てのリソースを番号順に要求しなければいけないというもの。

 

3.3.6 デッドロック回避

確かな情報が予めわかっていれば、リソースの要求を慎重に分析して適切に割当を行うことでデッドロックは回避できる。銀行家のアルゴリズムや2相ロックなどがある。

少し飛びます

3.6 RAMディスク

メモリドライバを使うと、メモリの任意の場所にアクセスすることができる。主な用途は、メモリの一部を普通のディスク装置のように利用することであり、ここではRAMディスクドライバとして説明されている。

ブロックデバイスはブロックの読み/書きという2つのコマンドが使われる記憶媒体である。通常ブロックは回転系のメモリ(フロッピーディスク等)に格納されるが、RAMディスクはもっと単純で、あらかじめ割り当てた主メモリの一部にブロックを格納する

 

RAMディスクは割り当てるメモリ容量によっていくつかのブロックに分けられる。各々のブロックサイズは実際のディスク装置を使う場合と同じ。ドライバはブロックを読み書きするためのメッセージを受信した時、要求されたブロックがRAMディスクディスクのメモリ上のどこにあるかを計算し、フロッピーディスクやハードディスクではなく、メモリに対してブロック読み書きを実行する。

少し飛びます


3.7 ディスク

3.7.1 ディスクのハードウェア

ディスクの構造説明を読んで図にしてみたけど..
こんな感じ...

(追:シリンダって書いてる部分は「ディスク」です。ディスクが重なったものがシリンダですね)

f:id:unyamahiro:20180501113713p:plain

通常フロッピーディスクでは1周あたり8-32個のセクタを、ハードディスクでは数百以上のセクタを持つ。最も単純な設計では各トラックは同じ数のセクタを持っている。全てのセクタは同じバイト数であるが、当然外周のセクタはディスク中心付近のセクタよりも物理的に長い。データ密度は一番中心のシリンダが明らかに高く、あるディスク装置の設計では内側のトラックを読み書きする時にヘッドの電流を変化させるものがある。これはディスクコントローラのハードウエアで処理されていてユーザに見えることはない。


3.7.2 RAID

Reduntant Array of Independent Disksの頭文字を取ったもの
ディスクアクセスの性能とデータ保護の目的で使われる。

RAID0:ストライピング書きこむデータを分割し、複数のドライブで読み書きを行うことによって高速化

RAID1:ミラーリング同じデータを複数のドライブに書きこむことで冗長性を向上させ可用性を高める。


(
この本にはその他のレベル(RAID2以上)は書いてませんでした)


3.7.3 ディスクのソフトウェア

ディスクブロックを読み書きするのにかかる時間は、シーク(アームが該当シリンダに移動する)、回転待ち(該当セクタをヘッドの下に持ってくる)、データ転送の3つによって決定される。ほとんどのディスクでは、中でもシーク時間が他の2つに比べて大きな割合を占めているので、これを減らすことでシステム効率を改善できる。

・ディスクアームのスケジューリングアルゴリズム
先着順/最短シーク優先/エレベータアルゴリズム


・エラー処理
・トラック単位のキャッシュ機能

 

とりあえず今回ここまで。