,…I…y…„†[…e…B…fi…O…V…X…e…•‡Ì…J†[…l…‰fi®“ì‡Ì›Â”‰›»pdfauthor

平成２０年度卒業論文

オペレーティングシステムの

カーネル動作の可視化

概要

研究目的

今日のオペレーティングシステムは巨大なものとなってきており，ソースコードを読んだり，全 容を把握するのが難しくなっている．そこで，OS のソースコードを読み始める人を主な対象とし， 容易に実行できる，ソースコードを読みやすくするシステムを追求する．

方法

オペレーティングシステムのソースコードを可視化することによって把握を手助けする．ソース コードレベルの実行ログを取得し，実行ログから可視化を行う．プログラムアニメーションで表現 し，どのソースコードがどんな時に実行されるかを示す．

結論

可視化に必要な全ての実行ログを取得することはできなかった．ログが限られる中，可視化を行 うことができた．実行されたソースコードを確認でき，有効性を確認することができた．

目 次

第 1 章 序論 4 1.1 背景 . . . . 4 1.2 目的 . . . . 4 第 2 章 関連研究 5 2.1 実行ログの取得 . . . . 5 2.2 OSの機能の可視化 . . . . 5 第 3 章 方法 7 3.1 使用する OS . . . . 7 3.2 OSの動作環境 . . . . 7 3.3 ログ取得機能の追加方法 . . . . 7 3.4 取得するログの内容 . . . . 8 3.5 可視化 . . . . 8 第 4 章 実装 9 4.1 実行ログ . . . . 9 4.1.1 機械的な改変 . . . . 9 4.1.2 出力用の関数 . . . . 9 4.1.3 出力内容 . . . . 9 4.1.4 挿入場所 . . . . 10 4.1.5 出力関数 . . . . 10 4.2 コンソール出力 . . . . 11 4.3 可視化 . . . . 11

図 目 次

2.1 関連研究．[2]，pp.112，図 3. プロセススケジューリングの可視化 より引用． . . 6 3.1 構成図 . . . . 8 4.1 無限ループの解決法の概要 . . . . 10 4.2 作成した可視化システム . . . . 12 5.1 得られたログの一部 . . . . 14

第

1

章 序論

1.1

背景

今日，多くの計算機上でオペレーティングシステム (以下:OS と記述) が動作している．おのず と，多くの OS の開発者達が OS のソースコードを読む．しかし，多くの OS は巨大で複雑であり， 読みにくいものとなっている．例えば，Linux Kernel 2.6.0 はマイクロカーネル部のみで約 5 万行， 全部で 600 万行以上に上り，ソースコードやその動作の全容を把握することは難しい． ソースコードやその動作の全容を把握する手段として，実行状態の可視化がある．ソースコード における実行状態の可視化をするためには，ソースコードのどの部分が実行されたと言う情報，つ まり実行ログが必要になる．OS の実行ログの取得には，様々な方法が考えられる． まず，応用ソフトウェアの実行ログの取得ように，対象の OS に機械的に実行ログを取得する機 能を追加する方法が考えられる．それ以外には，例えば，インサーキット・エミュレータを用い， 計算機の実行ログを取得する方法が考えられる．この方法では，使用するハードウェアに対応した インサーキット・エミュレータを用意しなければならない．また，得られたレジスタの値や機械語 等から OS のソースコードへの対応付けをしなければならないという問題点がある．また，計算機 の仮想化ソフトウェア上で対象の OS を動かし，仮想化ソフトウェアから実行ログを取得する方法 が考えられる．この方法についても，仮想化ソフトウェアの改変を行ったり，実行ログからソース コードへの対応付けをしなければならないという問題点がある．

1.2

目的

本研究では，OS のソースコードを読み始める人を主な対象とし，容易に実行できる，ソースコー ドを読みやすくするシステムを追求する．機械的に実行ログを取得する機能を OS に追加し，可視 化するシステムを目指す．

第

2

章 関連研究

汎用計算機向けの OS のソースコードの可視化に関する研究は見当たらない．以下，OS の実行 ログの取得に関する研究と，OS の機能の可視化に関する研究を紹介する．

2.1

実行ログの取得

インサーキット・エミュレータを用いて実行ログを取得するものに，主にデバッグ向けではある が，PARTNER-Jet[1] がある．PARTNER-Jet は，OS のソースコードの実行位置も表示すること ができる．ただし，対象が主に組み込み向けの CPU に限られる．また，高価な専用ハードウェア が必要になる． OSを改変してログを取得する趣旨の関連研究では，出力として変数の値が多く，そのためのデー タ構造の提案が主となっている．

2.2

OS

の機能の可視化

OSの可視化に関する関連研究の一例として，可視化によるＯＳ教育支援環境の実現と評価 [2] を紹介する．この論文では，OS のプロセス管理，メモリ管理について可視化している．一例とし て，プロセススケジューリングの可視化を図 2.1 に掲載した．図 2.1 には，実行中のプロセス，実 行待ちのプロセス，一時停止されたプロセスがそれぞれ，緑色，黄色，赤色の四角で表示されて いる．これらの四角で表示されたプロセスがアニメーション動作することによって，プロセススケ ジューリングを可視化している． このように，今まで行われてきた OS の可視化に関する研究は，プロセススケジューリングや ページング等，OS の基本的な機能の可視化に留まっており，ソースコードの可視化に関する研究 は見当たらない．

第

3

章 方法

一度対象の OS を動かしてログを取り，その後得られたログを元に別の OS 上で可視化する．構 成図を図 3.1 に記載する．

3.1

使用する

OS

本研究では，可視化する対象の OS として，MINIX[5] を使用する．これは，MINIX はマイクロ カーネル部のみで約 4000 行と比較的短く，教育用に設計されているため実行効率よりも分かりや すさを優先してソースコードが書かれているためである．MINIX のバージョンは，本研究時点で 最新版である 3.1.2a を使用する．

3.2

OS

の動作環境

ログを取得するために，MINIX を計算機の仮想化ソフトウェアである VMWare Player[6] 上で 動作させる．VMWare Player のバージョンは，本研究時点で最新版である 2.0.5 build-109488 を 使用する．同じく計算機の仮想化ソフトウェアである QEMU[7] を使用してディスクイメージを作 成し，仮想計算機の設定ファイルは，MINIX の VMWare 用の配布パッケージに含まれているもの を使用する．そして，MINIX のインストール CD を用いてフルインストールし，研究を行う．パッ ケージのインストール等は行わない．

3.3

ログ取得機能の追加方法

MINIXのソースコードは，C 言語とアセンブラで書かれている．本研究では，MINIX のソース コードを改変する事により，ログを取得する機能を追加する． 3.2で述べた通り，MINIX には最低限の機能しかインストールされていないので，MINIX 上で はソースコードの大規模な改変はしにくい．そこで，VMWare Player 上で立ち上げた MINIX か らソースコードをホストマシンにコピーし，ソースコードの改変はホストマシン上で行う．ゲスト マシンとホストマシンとのファイルの送受信は，ゲストマシン上で ftp サーバを立て，ホストマシ ンから ftp クライアントでアクセスすることにより行う．改変したソースコードを MINIX 上でセ ルフコンパイルし，作成されたカーネルで再起動することによりログを取得する．

MINIXの改変については，MINIX の作者である Andrew S. Tanenbaum による MINIX の解説 本の翻訳である MINIX オペレーティング・システム [3]，OS―設計と理論および MINIX による 実装 [4] を参考にする．

図 3.1: 構成図

3.4

取得するログの内容

OSのソースコードにおける実行状態の可視化をするために，ソースコードの実行された位置を 示す実行ログを取得する．また，コンソール出力も取得する．一般に，普段 OS を使用していて見 えるものはコンソール出力である．コンソール出力とソースコードを同時に見せることで，どのタ イミングでソースコードのどの部分が実行されているかが分かり，ソースコードが読みやすくなる と考えたからである．

3.5

可視化

オブジェクト指向言語である Java[8] を使用して可視化システムを作成する．得られたログと MINIXのソースコードを用いて，実行ログに対応するソースコードの位置とコンソール出力を対 応させて表示する．ソースコードとコンソール出力を用いてプログラムアニメーションを行うこと により，OS のソースコードを分かりやすくするシステムを目指す．

第

4

章 実装

4.1

実行ログ

実行ログの量が多くなるため，OS のソースコードレベルの実行ログを取得することは難しい． 実行ログの出力処理の負荷が高いため，実行ログは出力し続けているが MINIX の起動が進まない 状態になることが多かった．また，OS は並列処理の同期を頻繁にとる．同期のバランスが崩れ， MINIXがフリーズしてしまうこともあった．これらの問題を解決するために，様々な実行ログの 取得方法を試した．

4.1.1

機械的な改変

C言語で書かれている MINIX のカーネルのソースコードに，4.1.2 に記載の，固有の引数を伴っ た出力用の関数の呼び出し文を挿入した．この挿入作業は，スクリプト言語である Python[9] を使 用して行った．{}(波括弧) の数や，変数宣言，return 文を基準にして，挿入するスクリプトを作成 した．

4.1.2

出力用の関数

カーネル内に，実行ログ出力用の関数 log out を作成した．関数 log out は，引数として実行ロ グの出力文字列を受け取り，OS に実装されている出力関数を用いて出力する．よって，「実行ログ の出力」の実行ログを出力しようとすることで，無限ループに陥る可能性がある．この解決法とし て，グローバル変数にて，log out 関数の最初の実行時のみ，実行ログを出力するようにした．図 4.1に無限ループの解決法の概要を掲載した．

4.1.3

出力内容

実行ログとして，CSV(Comma Separated Values, カンマ区切り) にて以下の出力を試した．経 過時間以外は，スクリプト言語による MINIX のソースコードの改変時に，log out の関数呼び出 しの引数としてあらかじめ記述した． ソースコードのファイル名．MINIX は複数のソースコードから成り立っているので，実行され たソースコードの特定の際に必要になる． ソースコード 1 ファイルごとに固有に対応付けたアルファベット 1 文字．ソースコードのファイ ル名の出力から出力文字列を減らし，出力の負荷の軽減を図ったもの．対応付けの一例を表 4.1 に 掲載した． 実行されたソースコードの行番号．

  int flag; log_out() {    if ( 0 == flag )   {      flag = 1;     出力関数 ();      flag = 0;   } }   図 4.1: 無限ループの解決法の概要 ファイル名 対応付けたアルファベット clock.c a debug.c b exception.c c .. . ... 表 4.1: ファイル名と対応付けたアルファベットの対応表 (一部) 関数ごとに対応付けた，ソースコード 1 ファイル内で固有のアルファベット 1 文字．関数ごと に，上から a，b，c，…と対応付ける．4.1.4 で，出力の回数制限をする際に使用する．

OSを起動してからの経過時間．関数 log out 内で，MINIX のカーネルに実装さている時間を返 す関数を呼び出すことにより経過時間を取得する．

kprintf

kprintf関数は libc で実装されている printf 関数のような，カーネル内で出力を行いたいとき に用いる一般的な関数である．kprintf 関数の出力は，syslog が受け取ることができる．syslog は， UNIXの標準的なログ管理システムである．kprintf 関数でカーネルから出力した後，syslog から ディスクに書き込んだり，ネットワークを介して送出することが可能である． outb outb関数は低位の出力関数であり，引数に出力先のポート番号と 1 バイトの出力値を指定するこ とにより，指定のデバイスへ出力ができる．VMWare Player には，仮想マシンからシリアルポー トへの出力を，ホストマシンのファイルに出力する機能がある．そこで，outb 関数の出力先ポー トにシリアルポートを指定し，上記の機能を利用してホストマシンのファイルに出力した．

4.2

コンソール出力

コンソール出力は，実行ログと同じ出力先に出力した．同じ出力先にすることで，実行ログとコ ンソール出力の，出力の前後関係を保持することが可能である．コンソール出力はドライバ内から の出力となるため，カーネル内で実行ログの出力用に使用したものと同じ関数は使用できない．そ の代わり，ドライバには類似した機能が用意されている．カーネル内で kprintf 関数と同等の出力 は printf 関数を使用することで，outb 関数と同等の出力は sys outb 関数を使用することで可能で ある． また，改行などの特殊文字は，エスケープシーケンスし，出力した．

4.3

可視化

可視化システムを紹介する．この可視化システムで，ソースコードのプログラムアニメーショ ン，そしてその時のコンソール出力を見ることができる．図 4.2 に，可視化システムのスクリーン ショットを掲載した． 画面中央左に実行中のソースコードを，中央右にコンソール出力を表示した．ソースコード画面 の上には，実行中のファイル名と実行中の行番号，関数に入ったところか出たところかを表示した． 画面右下，右から 2 番目の数字に，現在可視化している実行ログの位置を表示した．この実行 ログの位置の番号が，可視化しているシステムの実行中の時間と対応する．可視化中の実行位置の 遷移に伴って，実行ログの位置の番号も対応して変化する．実行ログの位置番号を入力することに よって，可視化しているシステムの実行位置を指定することもできる．また，1 番右の数字に，実 行ログの全数を表示した． 左下の Start ボタンを押すと，一定間隔ごとに，ログを 1 ステップずつアニメーションする．ア ニメーションの更新間隔は，Start ボタンの右上，更新間隔の領域にミリ秒単位で入力することに より，変更できる．また，このアニメーションは，Stop ボタンにより停止できる．Step ボタンを 押すと，実行位置が 1 ステップ分進む．また，RevStep ボタンを押すと，1 ステップ分戻る．Reset ボタンにて，システムの実行位置をログの先頭に戻すことができる．

第

5

章 結果と考察

5.1

実行ログの取得

kprintf関数を使用して実行ログを出力すると，syslog の起動前ではカーネルからの出力内容が 全て画面に出てしまった．この結果，大量の文字により画面に何が表示されているかも分からない 状態になった．kprintf 関数は，実行ログの出力には不適切であった．

よって，outb 関数を使用して実行ログを出力した．log out 関数呼び出しを，1 行 1 行に挿入し た場合や，関数の出入り口に挿入した場合では，実行ログを出力し続けたまま，MINIX は起動の 初期の画面から変化しなくなってしまった．出力されている実行ログは，文字化け等のない正常な ものであり，出力に時間がかかりすぎているものと考えた． 出力の多い関数からの log out 関数呼び出しを削除して起動，を繰り返した場合では，削除する につれ起動していくようになっていった．しかし，ある時を境に，一定の箇所で起動が停止するよ うになった．この時，ログの出力も同時に停止したので，MINIX がフリーズしたと考えた．また， 停止するまでに出力するログがかなり少なく (100KB 程度に) なるまで log out 関数呼び出しを削 除しても，改善することなく起動は停止した．これについて，プロセス間通信などの同期が必要な 機能のバランスが崩れ，MINIX が機能しなくなったと考えた． 関数ごとに出力回数を制限する方法を採用することにより，MINIX が正常に起動した．出力の 上限回数を 10000 回として得られた実行ログにより，可視化を行った． また，出力内容は，ソースコード 1 ファイルごとに固有に対応付けたアルファベット 1 文字，ソー スコードの関数の入り口か出口かを表したアルファベット 1 文字，関数ごとに対応付けた，ソース コード 1 ファイル内で固有のアルファベット 1 文字，実行されたソースコードの行番号とした．得 られたログの一部を図 5.1 に示した．

5.2

有効例

5.2.1

yes

yesコマンドを実行したときのログを取得し，可視化を行った．ログは 10 万行近くになったが， コマンド実行時のログの特定はコンソール出力画面よりすぐに判明した．更にコンソール画面から ログの位置を指定する Jump ボタンの機能により，瞬時にログを調べることができた． 画面装置への出力関数が連続的に実行されていることを見ることができた．また，途中でクロッ ク割り込みが入り，プロセスのスケジューリングが行われていることが確認できた．

5.2.2

ls

図 5.1: 得られたログの一部

5.3

不完全な実行ログ

実行ログの出力の際，出力の負荷が大きすぎると考えられ，完全な実行ログを得ることができな かった．VMWare Player がどういった実装をしているかは分からないが，シリアルポートからの 出力速度が遅いことから，シリアルポートからファイルに出力する設定でも，通常のシリアルポー トと同様に，出力にかかる時間分デバイスの使用を停止させていると考えられる．よって，出力が 遅いことが原因だと考えられた．これに関して，以下のような解決手段が考えられる． ソースコードが公開されている計算機の仮想化ソフトウェアを使用する．仮想化ソフトウェア側 でログ取得用の仮想デバイスを作成，ホストマシン側で仮想デバイスのデバイスドライバを作成す る．実行ログを，仮想デバイスを介して送出する． また，そうでなくても，イーサネットなどの既存でにあるシリアルポートより高速なデバイスを 使用する．いずれも，計算機の仮想化ソフトウェアやデバイスドライバを作成しなければならない． 計算機外に出さず，ディスクに書き込むプログラムを作成する手段も考えられる．ただしファ イルシステムの負荷は増大してしまう．ファイルシステムは，本研究で使用した MINIX の場合， ユーザプログラムとして実装されているので，該当プロセスの負荷が増大した実行ログにはなって

謝辞

やりたいように研究をやらせていただきながら，実力が足りなく，本研究が行き詰る中，寺田実 准教授の御指導のお陰でなんとか成功例を示すところまでこぎつけました．心からお礼を申し上げ ます． 東京大学情報基盤センターの丸山一貴助教には，本研究に限らず，たくさんの的確な助言を頂き ました．また，暖かく見守っていただき，ありがとうございました． 情報システム学研究科 (IS) 多田研究室博士課程二年の高須賀清隆さん，大量の赤入れをいただ き、ありがとうございました．来年度もよろしくお願いします． M2の安齋 嶺さん，計算機管理者お疲れ様でした． M1のみなさん，面倒をみてくれてありがとうございました． B4のみなさん、仲良くしてくれてありがとう． そして，論文提出間際には家事をほとんどできなかった．家族のみんな，支えてくれてありが とう．

参考文献

[1] JTAG ICE:PARTNER-Jetの製品解説ページ， http://www.kmckk.co.jp/jet/index.html. [2] 西野 洋介, 早川 栄一, 高橋 延匡, ”可視化によるＯＳ教育支援環境の実現と評価”, 情報処理学

会研究報告 システムソフトウェアとオペレーティング・システム, 2001-OS-88-15, pp.107-114. [3] MINIXオペレーティング・システム, Andrew S. Tanenbaum 著, 大西 照代 翻訳, 1989 年, 株

式会社アスキー.

[4] オペレーティングシステム―設計と理論および MINIX による実装, Andrew S. Tanenbaum 著, 千輝 順子 翻訳, 1998 年, ピアソン・エデュケーション.

[5] The MINIX 3 Operating System, http://www.minix3.org/.

[6] VMware Player、仮想マシン、仮想 PC - VMware, http://www.vmware.com/jp/products/player/. [7] QEMU, http://bellard.org/qemu/.

[8] Developer Resources for Java Technology, http://java.sun.com/.