Hatena::ブログ(Diary)

I CAN ’CAUSE I THINK I CAN! このページをアンテナに追加 RSSフィード

, and twitter /真面目なブログ

2009/12/12(Sat)

移動しました

雑記

ブログはこっちに移動することにしました。よろしくでーす。

Permalink | コメント(0) | トラックバック(0) | 18:57 移動しましたを含むブックマーク 移動しましたのブックマークコメント

2009/11/11(Wed)

Operating System I #2

雑記, 講義

Chapter 6 - プロセス間同期

Chapter 4まででマルチタスクの実現のための仕組みを説明しましたが、マルチタスクであるが故に起きる問題があります。

クリティカルセクション(Critical Section Problem)

ある計算機上で複数のプロセスが動いているとき、競合が発生することがあります。具体的には:

  • 共有している変数の変更
  • DBにおけるテーブルの更新（Operating System Conceptには挙げられていますが、実際にはDBの場合はこんなにシンプルじゃない気がする）
  • ファイルの更新

というようなものが挙げられます。あるプロセスとあるプロセスが同時にこういった処理を行うと、最終的な結果に不整合が発生することが考えられます（2009年8月9日時点のWikipediaの解説がわかりやすいです）。

こういった処理をクリティカル・セクション（Critical Section:以下"CS")と呼びます。

クリティカルセクションを処理する

CSを処理するプログラムは次のようなセクションにわかれます。

  • entry section: CS処理の前処理（資源のロックなど）
  • critical section
  • exit section: CS処理の後処理（資源のロックの解放など）
  • remainder section: 残りの処理（要するにクリティカルセクションとは関係ない処理

それと同時に、CSを処理するプログラムには次の3つの性質が求められます:

  1. 相互排他: あるプロセスがCSを処理している間は、別のプロセスはCSを処理できない
    • 原文ではMutal Exclusionで、これは割と有名なMutexの語源らしい
  2. 連続性: CSの入り口（entry sectionね、たぶん）で待っているプロセスのみ、次にCSを処理するプロセスとして選ばれうる
    • でも、Progressの意味合いからすると「Critical sectionを処理せずにremainder sectionを処理することはない」または「Critical sectionに入れないからといって、critical sectionを飛ばしてremainder sectionに入っちゃうようなプロセスは選んであげない」のようにも読めるのだよなあ
  3. 有限の待ち時間: プロセスがentry sectionで待たされる時間は有限か、制限がある（原文では"There exists a bound, or limit on the number of times..."となっており、boundはcritical sectionが有限時間で終わる（ことが推奨される）こと、limitは有限時間でcritical sectionを負えないプロセスは強制終了するべきであることを意味している、と思う）
ピーターソンの方法

上記の性質を満たすCS問題の解法として、2つのフラグ変数と1つの状態変数を用いる"ピーターソンの方法"があります。2つのフラグ変数というわけで、この方法はプロセスがふたつの場合にしか利用できません。

PiとPjの場合を見てみます。

int turn;
boolean flag[2];
do{
  // entry section
  flag[i] = TRUE;
  turn = j;
  while( flag[j] && turn == j);

  // Here is cretical section

  // exit section
  flag[i] = FALSE;

  // remainder section
}while(1);
// ※C言語でシンタックスハイライトしていますが、C言語ではありません
// entry sectionでturn = jする理由がいまいちわからないなー
同期ハードウェア

ピーターソンの方法はソフトウェア的な実現でしたが、ハードウェア的な実現もできます。

セマフォ

ピーターソンの方法や、ハードウェアを利用した方法を抽象化したのがセマフォです。

セマフォは整数値を持つオブジェクトで、WaitとSignalという2つの操作だけが提供されています。

Waitは次のように表現されます:

wait(s){
  while( s <= 0)
    ;
  s--;
}

Signalはこうです:

signal(s){
  s++;
}

例によってC言語ではありませんので念のため...

waitがentry sectionのための関数で、signalがexit sectionのための関数です。間違えると混乱する点が、セマフォの初期値は0ではないということです。

要するに:

  • 初期値nのセマフォ
  • CSを処理する前（entry section, セマフォではwaitですね）にデクリメントする
  • CSが終わったら（exit sectionなのでセマフォではsignal）インクリメントする
  • waitしたとき、セマフォが0になっていたら待ち続ける

ということなので、結果的に:

ということになります。

バイナリセマフォ（Mutex）

で、初期値が1のセマフォなら同時にCSに入れるプロセスの数は1個なので、相互排他が実現できていることになります。n>1の場合と異なり特殊なので、特別にバイナリセマフォとも呼ばれますし、Mutex（ミューテックス）とも呼ばれます。

セマフォの場合、ピーターソンの方法と違ってCSを処理したいプロセスがn個あっても大丈夫なので、非常に実用的です。実用的なのでいろんな本に載っていて、学術的なテキスト（Operating System Concepts）に載っていてちょっとびっくりしました...

参考文献

  1. ”Operating System Concepts” 2004/12 (Abraham Silberschatz他)
  2. Wikipedia - セマフォ
  3. Wikipedia - ミューテックス
  4. ファイヤープロジェクト - セマフォ

Permalink | コメント(0) | トラックバック(0) | 01:02 Operating System I #2を含むブックマーク Operating System I #2のブックマークコメント

2009/11/09(Mon)

Operating System I

雑記, 講義

Chapter 1 - OSとは何か

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

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

などが挙げられます。

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

OSの目的

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

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

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

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

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

ストレージは、以下の3つのパラメータがあります。

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

基本的に、速度とコストはトレードオフの関係にあります。揮発性の有無は他のふたつとは独立のパラメータで、記憶の実現方式に依存するケースが多いです。

以下に、典型的な記憶機器を列挙します。上から高速・高コスト（小容量）順で、下にいくにつれて低速・低コスト（大容量）になります。

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

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と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

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

Permalink | コメント(0) | トラックバック(0) | 00:49 Operating System Iを含むブックマーク Operating System Iのブックマークコメント

プロフィール

Tnzk

Tnzk

倉世古 恭平( Tnzk) - 筑波大 情報科学類 2009年度AC

2009年の目標
最新タイトル
最近のトラックバック
最近のコメント