Operating System I

Chapter 1 - OSとは何か

オペレーティング・システムとはなにか

OS(Operating System)とは、具体的には:

などが挙げられます。

OSも、動作するレイヤーこそ違えど我々が書くべきプログラムのひとつです。そのことを念頭に据えてオペレーティング・システムの世界を概観してみましょー。

OSの目的

OSが必要な理由は大まかには次のふたつです。これらの意味するところは、あとのほうでわかってきます。

  1. ユーザのプログラム(アプリケーション・プログラム)を実行し、ユーザが計算機で問題を解決するのを簡単にする
  2. 計算機システムを使いやすく整備する
計算機システムの構造

計算機システム全体は、大まかには次の4つのものから成り立っています。

  1. ハードウェア: ディスプレイやハードディスク、メモリとかその辺です
  2. OS: ここで話題にしている、オペレーティングシステムです。基本ソフトウェアと呼ぶこともありますね
  3. アプリケーション: OSの上で動作するプログラムです。ワープロからブラウザ、コンパイラも電卓も
  4. ユーザ: 計算機の利用者です。私でありアナタであり、場合によっては他の計算機である場合もあります
ストレージ

計算機システムでは、計算の経過や結果を保存するためのデータの保存領域が重要になります。ストレージと呼ばれます。
ストレージは、以下の3つのパラメータがあります。

  • 速度: 単位時間当たりに書き換えられるデータ量
  • コスト: 単位記憶容量当たりの製造コスト
  • 揮発性の有無: 給電が途絶えた際に記録が保持されるかどうか

基本的に、速度とコストはトレードオフの関係にあります。揮発性の有無は他のふたつとは独立のパラメータで、記憶の実現方式に依存するケースが多いです。
以下に、典型的な記憶機器を列挙します。上から高速・高コスト(小容量)順で、下にいくにつれて低速・低コスト(大容量)になります。

  • CPUレジスタ
  • CPUキャッシュ
  • メインメモリ
  • 電気ディスク
  • 磁気ディスク
  • 光学ディスク
  • 磁気テープ

それから、重要な機能のひとつに「キャッシュ」があります。キャッシュとは、頻繁にアクセスされるデータが遅いデバイスにある場合、速いデバイスに移しておくことで計算の高速化を図る手法です。

Chapter 2 - OSの構造

OSは以下の機能をユーザに提供します。

概ね、ハードウェアのラッパーであると考えてよさそうですね。

システムコール

上記の機能をユーザプログラムから利用するために、システムコールが用意されています。
システムコールは基本的にAPI(Application Programming Interface)の形態で提供されますが、実際にはシステムコールの実体はカーネルと呼ばれるプログラムの一部です。
ユーザプログラムに呼び出されたAPIは、関連付けられたシステムコールをOSの中から探し出して実行し、システムコールのステータス(成功したかどうかなど)と何かしらの値を返します。
APIから利用する限り、ユーザプログラムの開発者はシステムコールがどのように実装されているかに気を配る必要はないので、基本的にはAPIからの利用が推奨されています。
(講義ではここでMS-DOS, UNIX, Mac OS X, Solaris, VMware, Java Virtual Machineでの実装を紹介しています)

Chapter 3 - プロセス

プロセスとはなにか

OSの中では、常にたくさんのプロセスが動いています。

プロセスはときに「ジョブ」とも呼ばれるとおり、抽象的にはOSの作業のひとつの塊を意味します。プログラマ的に考えるなら、プログラムの実行時の実体がプロセスである、ともいえます。

わたしのメモリの中のプロセス

プロセスはメモリ上で、以下の4つの領域を持ちます:

  • stack: ローカル変数など、コンテキストに応じて増減するものが格納されています
  • data: グローバル変数など、プロセス内で共有されるデータが格納されています
  • heap: 動的に確保された領域mallocなどによって)が格納されます
  • text: プログラムのコードそのものが入ります。コードといってもソースコードではなく、コンパイラによって翻訳された機械語です。

この中で、stackとheapはプログラムの実行中に必要な領域が変化することがあります。stackは関数呼び出しがネストした場合、heapはmallocなどにより新たにメモリが要求された場合に増加し、それぞれその逆の場合に減少します。

プロセスの状態

複数のプロセスを同時に処理すること(マルチプロセス)を実現するため、プロセスは状態を持つことが多いです。

シンプルに考えるため、2状態のものを考えます。プロセスは、以下の2つの内どちらかの状態を持ちます:

  • Running
  • Not Running

それぞれ文字通りの意味で、あるプロセスがRunningであるとき他のプロセスはNot Runningです。

実際には、5状態のモデルが利用されることが多いです:

  • New: あたらしく生成されたばかりの状態です
    • [Admit]->Ready
  • Ready: 実行される準備ができた状態です
    • [CPU Dispatched]->Running
  • Running: 実行中の状態です
    • [Interrupt]->Ready
    • [I/O event wait]->Waiting
    • [Exit]->Terminated
  • Waiting: 入出力の完了を待っている状態です
    • [I/O event completed]->Ready
  • Terminated: 実行が終了し、OSにより削除されるのを待っている状態です

[カッコ]内のイベントで対応する状態に変化します...が、こちら図を見るほうがわかりやすいです。

Process Controll Block

CPUがプロセス(と、その状態)を管理するため、Process Controll Block:PCBというデータが準備されます。PCBの中には以下のような情報が格納されています。

  • プロセスの状態: 先ほど説明したプロセスの状態です
  • プログラムカウンタ: 現在どこまでプログラムを実行したか(実際には、次に実行すべき命令があるアドレスはどこか
  • レジスタ: RunningだったときのCPUのレジスタの状態(レジスタは次にRunningになったプロセスにより上書きされてしまうので、ReadyやWaitingになる際には一時退避しておく必要がある)
  • CPUのスケジューリング情報(Chaper 5で)
  • メモリ管理情報(Chapter 8で)
  • プロセスの管理情報(Process numberやProgrammCounterもここに含まれる?)
  • 入出力情報

Chapter 4 - スレッド

マルチタスクを実現するためにプロセスという考え方が生み出されましたが、より効率的で先進的な並列プログラミングのためにスレッドという考え方も現れました。

スレッドとは、ひとつのプロセスの中でtextとdataとfiles(PCBにおける入出力情報、どんなファイルやデバイスを開いているか、など)を共有し、スレッドごとに独立のレジスタ領域とstack領域を持たせたものです。

スレッドを利用するメリットは以下の4つがあります:

  1. 応答性: 重い処理とUIのイベント処理を別のスレッドにすることで、体感速度や利便性の向上が見込める
  2. リソースの共有: dataやfiles, textは共有される
  3. エコノミー: リソースを共有しているので、実行しているプロセスの切り替えに比べてスレッドの切り替えは計算機的コストが低い
  4. マルチコアCPUの機能を利用できる: マルチコアCPUを利用している場合、スレッドごとに別のコアで処理できる

Chaper 5 - CPUスケジューリング

マルチタスクOSでは、プロセスを実行する順番も大切になります。どういった順番でプロセスを実行するかを決めることをスケジューリングといいます。

マルチタスクの実現方式 - preemptivbe, non-preemptive

スケジューリングにはプリエンプティブなものとノン・プリエンプティブなものがあります。

プリエンプティブなマルチタスクとは、プロセスの実行をOSが強制的に中断でき、OSの裁量でスケジューリングできるものを言います。preemptionとは横取りのことで、CPUがプロセスの実行権限を横取りすることからこう呼びます。近代的なOSはだいたいプリエンプティブです。

ノン・プリエンプティブなマルチタスクとは、プロセスの実行の中断をプロセス自身に委ねており、OSにスケジューリングの権限が(基本的には)ないものを言います。ノン・プリエンプティブ以外にコーペレイティブ(cooperative)とも呼ばれます。こちらは「協調的な」などといった意味で、マルチタスクの実現にプロセスの協調が必要なことからこう呼ばれます。

スケジューリングの評価尺度

プリエンプティブにせよノンプリエンプティブにせよスケジューリングのアルゴリズムには種々ありますが、その前にスケジューリングをどのように評価したらよいかを考えます。

  • CPU utilization: 計算リソースを余すことなく利用するには、できるだけCPU使用率を高く保つ必要があります
  • Through put: 単位時間当たりに処理できるプロセスの数
  • Turnaround time: CPUでの計算時間やメモリの確保、I/O待ちなども含めたひとつのプロセスの開始から終了までの時間
  • Waiting time: 計算時間以外の待ち時間
  • Response time: ユーザの操作に対して応答が帰るまでの時間インタラクティブなシステムでは、ビジーになってばかりでは利便性に劣ります。Response timeはChapter 4において、スレッドを使うことで改善できることがわかっていますね。
First Come, First Served: FIFS

先に入ってきたプロセスから処理します。早い者勝ちで、基本的にノンプリエンプティブな方式です。

Shortest Job First

処理に要する時間が短いプロセスから処理します。これはプリエンプティブでもノンプリエンプティブでもいけます。

処理に要する時間がわからなければならないので、実用は困難です。バッチ処理とかで使われるらしい?

Priority Scheduling

プロセスに優先度をつけて、優先度の高い順に処理していきます。プリエンプティブでもノンプリエンプティブでも大丈夫です。

Round Robin

プロセスの処理内容に関わらず、一定の時間間隔で実行するプロセスを切り替える方式です。プリエンプティブです。