daisuzz.log

"コンピュータシステムの理論と実装 第12章 オペレーティングシステム" を読んだ

「コンピュータシステムの理論と実装」を読んだメモを書いていきます。

前回コンパイラの実装については、以下の記事に書いています。

iikanji.hatenablog.jp

メモ

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

  • コンピュータのハードウェアとソフトウェアのギャップを埋める
    • Hello Worldを標準出力するためには、スクリーンのピクセルに対応したメモリマップにビットを書き込む必要がある
    • 高水準言語では、print(“Hello World”)、という記述だけで標準出力をできるようにして、細かいことはOSに任せたい
  • 書籍では、以下を行うシンプルなOSを実装する
    • ハードウェアに特化した機能をソフトウェアに対して提供する
    • 高水準言語をサブルーチンと抽象データ型で拡張する
  • 世間で使われているOSと比べると以下のような基礎的な要素が不足している
  • 一般的にOSは高水準言語で実装され、バイナリへとコンパイルされる

数学操作

  • 一般的には加算はハードウェアで実現され、乗算や除算はハードウェア/ソフトウェアどちらかで実現される
  • ハードウェアで実現するとソフトウェアで実現するのに比べて、コストはかかるがパフォーマンスは良くなる
  • 効率
    • nビットのバイナリに対して、nに比例する計算アルゴリズムを採用する
    • nビットのバイナリの値に比例する計算アルゴリズムでは計算時間が指数関数になってしまう
  • 乗算
    • 小学校で習う掛け算の筆算と同じアルゴリズムを使う
    • x * yの場合yの桁を右から見ていき、yの桁の値が1の場合、xを(yの桁分-1)左にシフトした値の合計を計算する
  • 除算
    • xからyを繰り返し引き、x<yになるまでの回数を計算するアルゴリズムだと0(x)になってしまう
    • xから引く値をyではなくy*Tとすれば、引き算の回数を省略できる
    • Tは、nの累乗(n進数の場合)とする

数字の文字列表示

  • int→string
    • 入力mをn進数のnで割ったあまりを末尾に追加
    • mが10未満であればあまりを返し、そうでない場合はmをnで割った値を入力として再帰呼び出しした結果を返す
  • string→int
    • 文字列の各桁に対して、n進数のnをかけて足していく

メモリ管理

  • ヒープへのメモリ割り当てとメモリ領域の破棄をOSが行う
  • 再利用を考慮したメモリ割り当てアルゴリズム
    • 利用可能なメモリセグメントをLinkedListで管理する(これをfreeListと呼ぶ)
    • 各セグメントはセグメントの長さと、リストの次のセグメントへのポインタを持つ
    • メモリ割り当て
      • freeListの中から割り当てに適したセグメントを見つけるために探索を行う
        • best-fitアルゴリズム
          • freeListの中で一番sizeに近いセグメントを返す
        • first-fitアルゴリズム
          • freeListの中で一番最初にsizeよりも大きいセグメントを返す
      • 探索で見つけたセグメントからsize+1分の部分セグメントの生成して、その部分セグメントのベースアドレスを返す
    • メモリの破棄
      • ベースアドレス-1のアドレスに破棄対象のメモリサイズが格納されているので、それを利用してfreeListに利用可能なセグメントとして追加する
  • 動的メモリ割り当てを実行させたままにしていると、メモリの断片化(フラグメンテーション)が発生する
  • デフラグをおこなうことで、断片化したセグメントを物理的に連続したメモリ領域として結合する

文字列

  • 可変長配列として扱う
  • 文字列のライフサイクルを通して文字列の最大長分のメモリは確保される

入出力管理

  • キーボード、マウス、スクリーン、ネットワークカードなどの入出力装置のデータを読み書きするための操作をカプセル化し、デバイスドライバという名前の関数群として提供する

グラフィック出力

  • ほとんどのコンピュータはラスター、またはビットマップと呼ばれる技術を利用している
  • ピクセル描画、直線描画、円描画、文字出力

キーボード操作

  • キーボードの入力判定
    • キーボードのデータにアクセスする方法はキーボードのインターフェースによって決まる
    • Hackの場合、RAM領域と紐づいているため、該当のRAM領域のデータを検証することで入力判定ができる
  • 単一文字の読み込み
    • キーの押し込みやキーを離す操作をイベントとして文字の読み込み処理を実装する
    • 入力された文字をグラフィカルにフィードバックするために、現在のカーソル位置に文字を表示させる
  • 文字列の読み込み
    • 文字列の入力はEnterキーが押されて終わりと考えられる
    • Enterキーによって改行文字が入力されるまではバックスペースによる文字の消去も許容する

実装

Jack OSはJack言語の拡張として実装するため、Jack言語を用いてOSを構成する以下8つのクラスを実装する。

  • Math
  • String
    • 内部でchar型の配列を保持する
    • maxLength分のメモリを宣言時に確保
    • 実際の長さはcurrentLengthを増減させて管理する
  • Array
    • 内部でメモリの割り当て関数とメモリ破棄関数を呼び出す
  • Output
    • 各文字のビットマップを配列で管理
    • カーソルの移動と、指定した文字の表示と削除を行う
  • Screen
    • スクリーン上の座標に対応したメモリを書き換えることで図形を描写する
  • Keyboard
    • キーボード入力を保持したメモリの値を読み込んで入力判定を行う
    • カーソル位置を移動させることでbackspaceに対応
    • 改行文字が入力されると読み込み処理を終了する
  • Memory
    • 利用可能なメモリセグメントを連結リストで管理
    • 各セグメントはlength, nextを保持
    • 動的メモリを割り当てる際には各セグメントのlengthを参照して割り当て可能なセグメントを探索する
    • first-fit
      • 要求されたサイズを満たす最初のセグメントを見つける
    • best-fit
      • 要求されたサイズに最も近いセグメントを見つける
    • メモリの断片化が発生する場合はデフラグを行うことで空きメモリを物理的に連結させる
  • Sys
    • Sys.init()がVM言語で書かれたブートストラップコードから呼び出される
    • Sys.init()が他のOSクラスのinitを呼び出した後でMain.main()を呼び出すことでプログラムを実行する

Jack言語で実装したソースコードは以下。

github.com

感想

動的メモリ割り当てのアルゴリズムやStringがどうやって実現されているか、ブートストラップコードから呼ばれたSys.initがどういう初期化処理を行なっているのかを知ることができて面白かった。 一方で、Math,Output,Screen,Keyboardといった計算ライブラリや標準入出力を行うOSは、実装自体が泥臭いものが多く、ハマったときのデバッグがかなりつらかった。

これで書籍の内容は一通り終わったので、今度はより現実的なVMの仕様を学ぶためにJVMについて調べてみたり、JavaGCの仕組みについて調べてみたり、もしくは↓のOSの自作書籍を買ったのでこれを進めていこうと思っている。