Zenn
📚

Nand2Tetris読書会（12章）

2022/08/12に公開
#
勉強会
#
読書会
idea

概要

Nand2Tetris読書会 を開催しています。
今回取り上げるのは、12章『オペレーションシステム』です。

前の記事は こちら。

内容

オペレーションシステム(OS)の役割:

  • コンピュータのハードウェアとソフトウェアシステムのギャップを埋める
  • プログラマーやユーザーにとってコンピュータ全体をより扱いやすくする

今回のOSで目指すのは以下の2つ。

  • ハードウェアに特化したサービスをカプセル化
    → ソフトウェアから使いやすいサービスに
  • 高水準言語を、ファンクションと抽象データ型で拡張

本章で構築するOSは、標準ライブラリとの境界線が曖昧であり、OSをJackの標準ライブラリと捉えられる。

OSと他のプログラムの比較:

言語 実行されるハードウェアへの理解
OS 高水準言語(Jack) 必要
他のプログラム 高水準言語(Jack) 不要

本章のポイントは以下の2つ。

  • ソフトウェアエンジニアリングの観点では、高水準言語、コンパイラ、OSを完成させる
  • コンピュータサイエンスの観点では、サービスの効率さのために処理時間にも注意する

コンピュータシステムは、数学操作(加算、乗算、除算、etc.)をサポートしなければならない。
通常、加算はハードウェア(ALU)で行われるが、乗算と除算をハードウェアとソフトウェアのどちらで扱うかはコストとパフォーマンスに依存する。

乗算、除算、平方根をソフトウェアで効率良く計算するために、本章で紹介されるアルゴリズムをベースにできる。
数学アルゴリズムは、n ビット(n = 16, 32, 64のどれか)のバイナリ数に対して処理をする。

例: 乗算( x*y )
x を y 回足す
→ n のサイズ(2^n) ∝ 処理時間
→ 時間がかかる
提案するアルゴリズムなら n ∝ 処理時間 とできる。

  • 乗算
    • 掛け算の筆算と同じ考え方で、バイナリも計算できる
    • プリミティブなALU操作で簡単に計算可能
    • 処理時間は O(n)
  • 除算 ( x/y )
    • x から大きい塊からなる y を引く
    • 繰り返し処理において、最大のシフトをした y で x を割る
    • 処理時間は O(n)
  • 平方根
    • 単調増加、逆関数は乗算であることから、二分探索で計算できる
    • 処理時間は O(n)

コンピュータは数をバイナリコードで表現するが、人間にとっては10進数で表現する方が自然。
そこで、人が数字を読む/入力するときに、10進数 ⇆ バイナリコード の変換をする必要がある。
一般的に、この変換はOSが提供する文字列ルーチンが行う。

  • 文字列 → ASCIIコード
    • 文字列の表す数字にASCIIコードの 0 に相当する数字を加算
  • ASCIIコード → 文字列
    • ASCIIコードの値からASCIIコードの 0 に相当する数字を減算

プログラムのライフサイクルでは、変数ごとにメモリに割り当てられるタイミングが異なる (動的メモリ割り当て)

例:

  • スタティック変数は、コンパイラによってコンパイル時に割り当てられるかも
  • ローカル変数は、サブルーチンが呼び出されるたびにスタック上に割り当てられる
  • その他のメモリは、プログラム実行中に動的に割り当てられる

OSは、ヒープ (動的に割り当てられるRAMセグメント) を管理する責任を負う。

  • 動的メモリの割り当て (alloc())
  • 動的メモリの破棄 (deAlloc())
    • ガーベジコレクション: 配列やオブジェクトが不要になったとき、その配列やオブジェクト自動的に破棄する仕組み。代表的なのはJavaのGC。
    • GCを備えない言語では、使用しないメモリ領域の破棄作業はプログラマが明示的にやらないといけない。

動的メモリの割り当て・破棄の関数について、簡易版と改善版のふたつのバージョンを考える。

  • 簡易版メモリ割り当てアルゴリズム
    • alloc: まだ割り当てが行われていないヒープ領域の先頭を指すポインタを、指定されたサイズのメモリブロックの先頭に移す。
    • deAlloc: 何もしない。
  • 改善版メモリ割り当てアルゴリズム
    メモリセグメントを、freeList と呼ばれる連結リストで管理。
    各セグメントは、自身のセグメントの長さ、リストの次のセグメントへのポインタの2つのフィールドを含む。
    • alloc: 指定されたサイズよりも長いセグメントを探索し、セグメントが見つかったら freeList を更新する。
      探索の際には、以下のどちらかのアルゴリズムを用いる。
      • best-fit: 指定されたサイズに最も近い長さのセグメントを見つける
      • first-fit: 指定されたサイズを満たす最初のセグメントを見つける
    • deAlloc: 指定されたオブジェクトを freeList に追加する。

改善版メモリ割り当てプログラムでは、断片化(フラグメンテーション)が問題となる。
これは、利用可能なメモリ領域が細切れになることで、断片化を解消するには「デフラグ」という操作が必要となる。
デフラグにより、断片化の状態になったメモリ領域を freeList の論理的に断片化されたセグメントではなく、物理的に連続したメモリ領域に結合できる。
デフラグは、オブジェクトを破棄するとき、あるいは alloc() 呼び出しで適切なセグメントが見つからなかったときに行える。

高水準の命令の中には、s1="New York" や s2=readLine("enter a city") のような、可変長な文字列を扱うケースがある。
このときに使われる String オブジェクトは、配列を用いて実現できる。
文字列が生成されると、ある最大長の配列を割り当てるが、ある時点での文字列の実際の長さは配列長より短くなる可能性がある。

コンピュータの入出力装置として、キーボードやスクリーンなどが一般的である。
高水準言語では、プログラマーのために装置の技術的詳細を抽象化するために、デバイスドライバ (デバイスのインターフェイスの詳細をカプセル化して、その装置にアクセスする関数群) を提供している。
本書で扱うのは、グラフィック出力と文字出力である。

現在のほとんどのコンピュータで使われているビットマップスクリーンでは、個別のピクセル描画の命令のみが行われる。
ピクセルは、行と列で位置が指定され、スクリーンの左上の座標を (0, 0) として、行は左から右へ、列は上から下へ向かって数が増える。
Hack の場合はスクリーンのインターフェイスが RAM 常駐のメモリマップに基づくもの (5章で学習) なので、適切な RAM 位置にバイナリ値を書き込むことで、ピクセルの描画を実現できる。

与えられた2点を結ぶ直線を描画するとき、上下左右の4方向のみにしか動かせないペンを使って、直線を近似したものを描画する。
始点からペンを結ぶ直線の傾きと、実際に描こうとしている直線との傾きを比較して、ペンを動かす方法を決定しながらピクセルを連続して描画していく。

本書で扱う円描画のアルゴリズムは、乗算、平方根、直線描画の3つのルーチンを使って実現する。
円の中心を (x, y), 半径を r としたとき、y-r から y+r までの範囲の行に対して、弧の長さに相当する長さの水平線を描画すれば、円が完成する。
しかし、本書で紹介されるアルゴリズムでは、ループ処理で毎回平方根の計算をするため効率が悪い。

文字出力では、スクリーンにテキストを出力するために、スクリーンを文字指向のものに分割する。
その後、スクリーンに表示したい文字に対して、フォントをデザインする。
これは、文字ごとにビットマップを使って実装できる。
通常、文字は左から右へと表示される。
そこで、文字描画のモジュールに、次の文字が描画されるスクリーンの位置を表す"カーソル"というオブジェクトを持たせる。
カーソルは、line, column という2つの要素を持つ。
カーソルがスクリーンの最下部に達した場合は、スクロール操作をする、(0, 0) の位置にカーソルを戻す という対応が考えられる。

キーボードでユーザーが入力するテキストを扱うことを想定して、キー入力を3つの抽象レベルで説明する。

  • キーボードの入力判定
    プログラムがハードウェアから直接取得したデータを見て、現在押されているキーが何かを判断する。
    このローデータへのアクセス方法はキーボードのインターフェイスによって異なる。
    Hack の場合は、キーボードのメモリマップに相当する RAM 領域の値を見ればよい。
  • 単一文字の読み込み
    キーが押されてから離されるまでの時間はユーザーの動作に依存するため予測できないため、それを考慮したコードを書かないといけない。
    また、キーボードが押されたときは、そのキーに対応した文字をスクリーンに出力するのが一般的である。
  • 文字列の読み込み
    通常、ユーザーが複数のキーを入力し終わったときの合図は Enter キーの押下である。
    また、Enter キーが押されるまではバックスペースで以前に打った文字を消せるべきである。

本章で扱う Jack OS の仕様は、9章ですでに扱ったものと同じ。

最後に、本章で学んだ Jack OS が含む要素、含まない要素をまとめる。

  • 含む要素
    • メモリ管理
    • I/O ドライバ
    • 初期化処理
    • ハードウェアで実装されていない数学関する
    • 文字列クラスなどのデータ型の実装
  • 含まない要素
    • マルチスレッドやマルチコア CPU への対応
    • 大容量記憶装置
      ファイルシステムを使ったデータの保存ができる
    • コマンドラインのインタフェース (Unix シェル、DOS など)
    • グラフィカルなツール (ウィンドウ、マウス、アイコンなど)
    • セキュリティ
    • 通信
    • ユーザーコードからの OS の提供サービスの利用を禁止

予習メモ

big O-記法

計算量には2種類ある。

  • 時間計算量: アルゴリズムの実行に必要な時間 (ステップ数)
  • 領域計算量: アルゴリズムの実行に必要なコンピュータのメモリ

big O-記法は、オーダー記法で使われる記法のひとつである。
オーダー記法の基本的な考え方は以下の通り。

  • 影響力が一番強い項以外は無視
  • 定数倍の差は無視 (係数は無視)

https://manabitimes.jp/math/1200

こちらの記事では、処理の具体例を挙げて代表的なオーダーが紹介されている。

https://zenn.dev/koffeecom/articles/7ba5c83a68cdb5

加算だけで実現される円描画のアルゴリズムとは？

直線描画のアルゴリズムである プレゼンハムのアルゴリズム を応用すると、整数の加算計算のみの高速描画が実現できる。

https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

ディスカッションメモ

動的メモリ割り当てで、領域が小さすぎたらセグメントを分けずにそのまま割り当てる場合があるが、その境界となる長さはいくつ？

特に決まった数字はない。
そもそもどの領域を割り当てるか、そのときのサイズはどうするべきかなどは長年にわたって議論されている。

例えば、アラインメントによって先頭のメモリアドレスが4の倍数となるようにする、確保領域の最小長を定めてその長さより短い領域を作らないようにする、といった工夫がなされている。

https://programming-place.net/ppp/contents/glossary/ta/dynamic_memory_allocation.html

感想

章の内容としては、前章よりもかなり分かりやすかったですが、久しぶりに円の公式などが出てきて、思い出すのに時間がかかりました。

演習問題は単調な実装が多く大変でしたが、パズルのような感覚で楽しみながら取り組めました。

最後に

『Nand2Tetris読書会始めました』の記事でも紹介していますが、読み進めているのはこちらの本です。
https://www.oreilly.co.jp/books/9784873117126/

初学者なりに書籍やその他に調べた内容をまとめていますが、理解が足りておらず間違ったことを書いているかもしれません。
そのような箇所を見つけた場合はコメントなどで指摘していただけると助かります。

GitHubで編集を提案

Discussion