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する理由がいまいちわからないなー
同期ハードウェア

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

セマフォ

ピーターソンの方法や、ハードウェアを利用した方法を抽象化したのがセマフォです。
セマフォは整数値を持つオブジェクトで、WaitSignalという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になっていたら待ち続ける

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

  • n個のプロセスがcritical sectionに入っていたらセマフォは0
  • n+1個めのプロセスはwait内で待ち続ける
  • いずれかのプロセスがsignalすればセマフォ1なので、n+1個めのプロセスがCSに入る
  • CSに入るプロセスの数をn個に制限できる!

ということになります。

バイナリセマフォ(Mutex)

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

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

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

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

オープンソースカンファレンス2009 Tokyo/Fall

オープンソースの文化祭, オープンソースカンファレンス2009 Tokyo/Fallにつくらぐとして出展してきました.
つくらぐからは,

  • 配布: これまでの発表の概要をまとめた冊子
  • 展示: 第6回で発表したプログラム
  • 展示: 第2回で発表した機材

という感じでブースの設営を行いました.
個人的には準備した冊子200部+αがすべて受け取っていただけるかどうかがちょっと心配だったのですが, 幸い31日の16時時点で配布完了となりました. 手に取っていただいた皆さま, 貴重な時間をありがとうございました.
準備から終了まで, 万事滞りなく進行してとても満足. みんな楽しんでいたようなので, ぜひ2月のTokyo/Springも参加したいなあ.
以下, 写真など. 重いので別ページにしておきます.

続きを読む

つくらぐの活動の一環として、OSC 2009 Tokyo/Fall に出展します

筑波大学 Linux User Group(つくらぐ)の活動の一環として、オープンソースカンファレンス 2009 Tokyo/Fallに参加します。
参加日程は、

  • 30日: 無人・資料配布
  • 31日: ブースにメンバー数名・勉強会で発表された機材および資料配布

という感じです。30日は平日の金曜日で、きれいにみんな外せない講義が入っていたので泣く泣く無人ということになりました(日程自体は泊まり込みで参加しても日曜日がクッションになって良心的だと思います、念のため)。
31日はみんなで会場に向かい、ブースにいたり講演を見に行ったりする予定です。メンバーはそれとわかるようなストラップをぶらさげていますので、見かけたら声をかけてみてください。
終わったら詳細まとめようと思います。

termtterでのつぶやきにフッターをつける

movatwitterその他のtwitterクライアントだと発言にフッター(スラドにおける署名であるとか, 参加してるコミュニティの宣伝とかが書いてあるあれ)がつけられるけど, ターミナルからつぶやけるクライアントであるtermtterではデフォルトではできないみたい(ちゃんと調べたわけではないので, もしできるなら教えてください)。
幸いtermtterは拡張が簡単なので, 設定できるようにしてみる. あっさりできて楽しい.

インストール先を調べる

まず, termtterがインストールされているディレクトリを見つける.ソースからインストールした人は問題ないですが, gemから入れた人はややこしいところに入ってます.
調べるには以下のコマンドで:

$ gem which termtter
(checking gem termtter-1.3.1 for termtter)
/usr/lib/ruby/gems/1.8/gems/termtter-1.3.1/lib/termtter.rb

termtter.rbと同じディレクトリにpluginsディレクトリがあるので, ここに作成したプラグインを格納するみたい.上記の場合だと/usr/lib/ruby/gems/1.8/gems/termtter-1.3.1/lib/pluginsになります.

hookをpluginsディレクトリに入れる

上記のpluginsディレクトリに, ftr.rbというファイルを作成して, 以下のような内容で保存します.

# -*- coding: utf-8 -*-

Termtter::Client.register_hook(
  :name => :add_footr,
  :points => [:pre_exec_update],
  :exec_proc => lambda {|cmd, arg|
    arg << " #{config.footer}"
  }
)

hookっていうのは割り込みみたいなものだと考えればいいのかなあ. svnにもあったはず...
cmdは割り込んだコマンドで, argが引数です. pointsが割り込みのタイミングで, :pre_exec_updateはアップデートの実行前を指定することになるらしい.
フッタの内容はconfigファイルから読み込んでいるので, これを設定すれば動きます.

設定の変更

2ヶ所変更の必要があります.

フッタ内容の設定

冒頭にconfig.user_nameやconfig.passwordが書いてあるので, その辺でconfig.footerを設定します.

config.user_name = 'tnzk'
config.password = 'shachihoko'
config.footer = '[10/21 18:30- つくらぐ#6 http://bit.ly/utlug6]'

こんな感じ.

ftr.rbの読み込み

プラグインの自動読み込みを以下の記述で設定します.

Termtter::Client.init do |t|
   t.plug 'ftr'
end

Termtter::Client.initのブロック自体はデフォルトで存在するはずなので, そこにt.plug 'ftr'を追記するだけでOKです.
自動読み込みが不要ならこっちは書かなくても大丈夫です. termtterを起動してからplug ftrコマンドを実行すれば, 同じように有効化されます.

行動日程

往路

  1. 0728-0926: つくばーTX→南流山ーJR→南船橋ーJR→蘇我ーJR→木更津
  2. 0930-1020くらい: ホテルに荷物あづける
  3. 1030-1052: JR木更津ー路線バス→かずさアーク(会場)

復路

  1. 1509-1525: かずさアーク→JR木更津
  2. 1640-1840: 木更津→つくば