Nachosを学ぶ

概要

Nachos(Not Another Completely Heuristic Operating System)はカリフォルニア大学バークレー校で開発された教育用のオペレーティングシステム。

C++で記述されていて、MIPSやx86上のlinuxやSolarisなどで動く・・・んだと思う。

Nachos自体はユーザーレベルで動作し、Nachosのユーザープログラムは MIPSシミュレーターで動作する。

MIPSシミュレーターはディレクトリmachine以下でMachineクラスとして実装されている。userprog/exception.ccあたりも利用しているので machineディレクトリ以外も気をつけなければならないところがあるかも。

クラス一覧

ヘッダファイルからなんとなく読み取ったこと。

• filesysディレクトリ
  • DirectoryEntry (ディレクトリエントリ。ディレクトリ中のファイルを表現する。ファイル名とヘッダのディスク中の位置を保持する(sector))
  • Directory (UNIX-likeのディレクトリ)
  • FileHeader (ファイルヘッダ(UNIXでいうならi-node)ファイル本体がディスク中のどこにあるかといった情報を持つ)
  • FileSystem (2つのうちどちらか。STUBはUNIX関数をラップしたもので,realはディスクの処理をシミュレートする)
  • OpenFile (FileSystemに合わせて2つある。個々のファイルのread,write,closeなどを扱う)
  • SynchDisk (スレッドからのリクエストに対してディスク操作し、割り込みをかけて通知するようにみせる)
• machineディレクトリ
  • Console (コンソールデバイス)
  • Disk (ディスクIOデバイス。セクタ番号でアドレッシング。UNIXファイルをディスクに見立てる)
  • PendingInterrupt (将来発生するのでスケジューリングされる割り込み)
  • Interrupt (ハードウェア割り込みをシミュレートする)
  • Instruction (MIPSプログラムを読み込んだ個々の命令。opCodeはMIPSのopcodeフィールドとは異なる)
  • Machine (シミュレーター)
  • PacketHeader (ネットワークパケットのヘッダ)
  • Network (ネットワークデバイス。固定長のパケットを転送できる。)
  • Statistics (statistics=統計。Nachosの振舞についての統計情報。時間、ディスクIOなど。)
  • Timer (ハードウェアタイマー)
  • TranslationEntry (変換テーブルのエントリ。ページテーブルかTLB(Translation Lookaside Buffer)。どちらも仮想->物理アドレス変換)
• networkディレクトリ
  • MailHeader (Mailのヘッダ)
  • Mail (Mailメッセージ)
  • MailBox (メールボックス)
  • PostOffice (メールボックスへのメッセージの送信と受信を扱う)
• threadsディレクトリ
  • ListElement (単方向リスト。ソートされたリストを利用する場合のためのkeyとvoid* itemを持つ)
  • List (単方向リスト。ListElementを管理する。firstとlastへのポインタを保持)
  • Scheduler (スケジューラ/ディスパッチャ。現在動作しているスレッドと動作可能なスレッドを保持する)
  • Semaphore (セマフォ。Pメソッド(down)とVメソッド(up)がある。)
  • Lock (ロック。BUSYかFREE状態をとる。Acquire(手に入れる),Releaseメソッドがある。必要なら要素を付け足してね、と書いてある。)
  • Condition (condition variable。値を持たない。Wait,Signal,Broadcastメソッドがある。Mesa-styleってなんだろう。)
  • SynchList (synchronized list.Removeするとき空なら要素が追加される間で待つ。同時にアクセスできるのは1スレッドだけ)
  • Thread ("thread control block"を定義。stack(bottom),stackTop,status,machineState(レジスタの状態)などをメンバとして持つ)
• userprogディレクトリ
  • AddrSpace (ユーザプログラムの実行に関する情報を持つが、いまはthreadがCPU状態等を保存してる?)
  • BitMap (ビット列。セット、クリア、テストができる)

Machineクラスメモ

Machineで利用されるOP_xxxという定数は、MIPSのオペコードそのものではなく、変換テーブルを使って変換した後の定数値。

システムコールは例外を発生させることで処理されるが、Halt以外の処理は実装されていない。

Machine::OneInstruction内でMIPS用バイナリコードの読み込み、Machineで利用する内部構造(Instructionクラス)への変換(Decodeメソッド)を行ったのち、命令ごとに処理を行うが、OP_SYSCALLであった場合はMachine::RaiseExceptionが呼び出され、そこから exception.ccのExceptionHandlerが呼び出される。

threadsディレクトリを読む

Nachosのエントリポイントはthreads/main.ccのmain関数。 OSとしての処理の中心はthreadsディレクトリ内のファイルで実装されているようなので、このあたりから見ていく。

mainではInitialize関数でグローバルなデータ構造の初期化(currentThread = new Thread("main")なども)する。コマンドラインオプションに応じたテストの類も行う。

return(0)とあるが、その前のcurrentThread->Finish()時に他のスレッドが無ければ最終的に Cleanup関数を呼び出してその中のExit(0)で終了する。

Threadクラス

int* stackTopとint machineState[MachineStateSize]メンバは場所を変えるなと書かれている。

あと、スタックの容量にも気をつける。

Threadクラスのpublicメソッド

コンストラクタはデバッグ用の名前を引数にとり、nameに設定する。statusをJUST_CREATEDにする以外は、NULLに設定する。

デストラクタはスレッドの解放を行うが、this == currentThreadの場合はスタックの解放が行えないため不正である。スタックの解放にはDeallocBoundedArray関数を用いる。

Forkメソッドは引数にとった関数をスレッドで走らせる。 callerとcalleeが同時に動作実行される事を許す。 StackAllocateメソッドの呼び出しスタックの確保と初期設定を行った後で scheduler->ReadyToRun(this)でスケジューラーに登録する。

Yieldメソッドは他に実行可能なスレッドがあれば、CPUを放棄させる。その場合はscheduler->ReadyToRunメソッドで実行可能プロセスのリストにCPUを放棄したスレッドを追加する。

Sleepメソッドはスレッドを眠らせ、CPUを放棄させる。 Yieldと異なり、スレッドはブロック状態になるので実行可能リストには追加されない。他に実行可能スレッドが無い場合はInterrupt::Idleメソッドを呼び出し続ける。

Finishメソッドはスレッドの実行を終了する。 ThreadRootから処理終了時に呼ばれる。まだ実行中なので、即座にスタックの解放等を行うわけではなく、 threadToBeDestroyedにスレッドをセットしSleepする。実際にスレッドが解放されるのは次回のscheduler->Run()中である。

CheckOverflowメソッドはスタックがオーバーフローしているか確認する。 int* stackの値がStackAllocateメソッドでセットしたSTACK_FENCEPOSTか確認することでオーバーフローが起きたかどうかをチェックする。

setStatusメソッドはスレッドの状態を設定する。

getNameメソッドはデバッグ用のスレッドの名前(コンストラクタで設定)を返す。

Printメソッドはスレッドの名前を表示する。

SaveUserStateメソッドはユーザプログラムを動作させているmachineのレジスタを保存する。 userRegisters[i] = machine->ReadRegister(i)

RestoreUserStateメソッドはユーザプログラムを動作させているmachineのレジスタを復元する。 machine->WriteRegister(i, userRegisters[i])

Threadクラスメンバ変数

変数名	説明
AddrSpace* space	ユーザーコード
int* stackTop	スタックポインタ(スタックトップ)
int machineState[MachineStateSize]	stackTop以外のレジスタ
int* stack	スタックの底.mainスレッド(Initializeで作られるスレッドか)はNULL。
ThreadStatus status	スレッドの状態。ready,running,blocked,just_created
char* name	デバッグ用の名前
int userRegisters[NumTotalRegs]	user-level CPU register state(カーネルコード実行中とユーザコード実行中は別に保存するため)

Threadクラスprivateメソッド

StackAllocateメソッドはForkメソッド内部で使われ、スタックの確保と初期設定を行う。スタックはAllocBoundedArray関数によって確保される。 AllocBoundedArrayはスタックの前後に1ページサイズ(getpagesizeの返り値)ずつ余分に領域を確保する。 i386ではstackTop = stack + StackSize - 4とされているが、-4は大事をとってるだけらしい。スタックにはSWITCH()でThreadRootを呼び出すための値を積んでいる。 machineStateに呼び出す関数やその引数などを設定する。

ThreadRootはアセンブラルーチン。 StartupPc,InitialPc,WhenDonePcレジスタの指す関数を順に実行する。WhenDonePCでthread->Finish()が呼び出されるはずなので、そのあとに処理は続かない。 i386ではInitialPCはESI,InitialArgはEDX,WhenDonePCはEDI,StartupPCはECXである。 ThreadRootが呼び出された時点でこれらのレジスタにはStackAllocateで設定した値がセットされている。おそらくSWITCHでスレッド先頭のmachineStateから読み込まれるのだろう。

例えばmachineState[InitialPC]はESI(%thread)というイメージ。switch.hでの定義の-1はint* stackTopの分(4バイト)の差だろう。

thread先頭からESI=24, EDX=16, EDI=28, ECX=12.

Schedulerクラス

スケジューラー。スレッドの切り替えはswitch.sのSWITCH手続きで行う。

Schedulerクラスpublicメソッド

コンストラクタはreadyListを初期化する。

デストラクタはreadyListを解放する。

ReadyToRunメソッドはスレッドを実行可能状態にし、実行可能スレッドのリストに追加する。 thread->setStatusでREADYをセットし、readyList->Append(thread)で最後尾にスレッドを追加する(エンキュー)。

FindNextToRunメソッドは次に実行すべきスレッドを返す。実行可能なスレッドが無ければNULLを返す。 readyList->Remove()の返り値を返している(デキュー)。

Runメソッドは引数に指定したスレッドを操作させる。切り替わる前のスレッドの状態はRunメソッドが呼び出される前にBLOCKEDかREADYになっているものとみなす。 currentThreadが変更されるのはこのメソッドの内部である。また、threadToBeDestroyedがセットされていればスレッドの切り替え後にそのスレッドを解放する。

PrintメソッドはreadyListの内容を表示する。

Schedulerクラスの変数

名前	説明
List* readyList	実行中で無いが実行可能なスレッドを保持するリスト。キューとして扱う。

SWITCH手続き

void SWITCH(Thread* oldThread, Thread* newThread)となっている。コンテキストスイッチを行うアセンブラルーチンで、CPUに依存する。

どうもswitch.sのうち必要な分だけ抜き出されてswtch.sになってる・・・っぽい。 ThreadRoot手続きもswtch.s(switch.s)にある。

EAXに引数の値(スレッドへのポインタ)をセットして使うので、EAX自体の値は_eax_saveという領域に一時保存して保存、復元する。リターンアドレスを4(%esp)にセットするのはなぜだろう。0(%esp)がSWITCHからのリターンアドレスだと思うのだが。

Semaphoreクラス

Semaphoreクラスpublicメソッド

コンストラクタはセマフォの値の初期値を引数にとる。キューの初期化をする。

デストラクタはキューを解放する。

Pメソッドはdown操作である。 value==0ならばスレッドをスリープする。 valueを1減少させる。

Vメソッドはup操作である。セマフォを待っているスレッドがあれば1つ起こす。 valueを1増加させる。

Semaphoreクラス変数

変数名	説明
List* queue	P(down)でスリープしているスレッドを保持するキュー
char* name	デバッグ用の名前
int value	セマフォの値。常に0以上

Lockクラス

実装が不完全

Conditionクラス

実装が不完全。