土曜日

OSについて

そもそもOSとは？

OS（オペレーティングシステム）は、ハードウェアを制御し、OS以外のソフトウェアに対して基本的な機能を提供するソフトウェアである。代表的なものとして、Linux、Windows、macOSなどがある。ソフトウェアを使う以上は逃れることのできないほどOSというのはとても身近な存在だが、何をもってOSとするかという厳密な定義は存在しない。そもそもOSがなくてもソフトウェアを動かすことはできる。

しかし、当たり前だがソフトウェアはハードウェアの上で動作するため、その場合はハードウェアを直接制御するための実装が必要になる。また１つのソフトウェアだけではなく、複数のソフトウェアが同時に動作するとなると、複数のソフトウェア間でハードウェアという共通のリソースを共有するための仕組みが必要になる。これらの機能をソフトウェアを作るたびに実装するとなると非常に手間がかかる。そこで、それらの機能をまとめて提供するのがOSである。

しかし、OSの厳密な定義は存在しないので、どの機能を提供するかはOSによって異なるわけだが、現代のOSであれば基本的な機能は大体共通しているため、それらを学ぶことでOSについての理解を深めることができる。

OSの役割

OSの役割には大きく２つあり、ハードウェアリソースの管理と、ソフトウェアの実行の制御を行う。現代のコンピュータには、CPU、メモリ、ストレージ、その他の入出力装置などがあり、それらのハードウェアリソースを管理するために、メモリ管理、ファイル管理、入出力制御を行う。また、ソフトウェアの実行を制御するために、プロセス管理も行う。

メモリ管理
プロセス管理
ファイル管理
入出力制御

ここでは上記のうちメモリ管理とプロセス管理について理論的な部分を学ぶと同時に簡単な実装をしていくことで、OSの基本的な機能についての理解を深めていく。土曜日はメモリ管理、日曜日はプロセス管理について学ぶ。

環境構築

下記を実行し、必要なツールをインストールする。

macOS

brew install llvm qemu
git clone https://github.com/rihib/learn-os-on-weekends.git
cd learn-os-on-weekends/os

Ubuntu

sudo apt update && sudo apt install -y clang llvm lld qemu-system-riscv32 curl
git clone https://github.com/rihib/learn-os-on-weekends.git
cd learn-os-on-weekends/os
curl -LO https://github.com/qemu/qemu/raw/v8.0.4/pc-bios/opensbi-riscv32-generic-fw_dynamic.bin

また、os/run.shをUbutnu用に修正すること（参考）。

コンピュータのハードウェア

ISA

CPUの機種によって解釈できる機械語は異なる。CPUが解釈できる機械語命令や、使用できるレジスタなど、プログラムから見たときのCPUの仕様をISA（命令セットアーキテクチャ）と呼ぶ。詳細はARM? RISC-V? x86? 用語がごっちゃになっている人のためのCPUアーキテクチャの全体図を参照。

今回実装するOSは32bitのRISC-Vアーキテクチャに対応する。

ハードウェア構成

マザーボードはコンピュータの中心的な基盤となる回路基盤で、CPU、メモリ、ストレージ、入出力装置などの主要なコンポーネントを接続し、相互に通信させる役割を担っている。CPUとメインメモリはマザーボードを介してメモリバスと呼ばれる高速な信号線で接続される（より正確にはCPUはメモリコントローラーと繋がっており、CPUがメモリコントローラに指令を出すと、メモリコントローラーはメモリからキャッシュにデータを転送する。このCPU、メモリコントローラー、キャッシュのデータ伝送路のことをメモリバスと呼ぶ）。また、SSDやGPUなどの高速なデバイスもマザーボードを介してPCI express（PCIe）と呼ばれる高速なバスでCPUと接続される。

HDDやキーボード、USBなどの入出力装置はそれぞれを担当するデバイスコントローラに接続される。イーサネットやWi-Fiでパケットのやり取りに使用されるNICやWNICは入力装置でもあり出力装置でもあると言える。

デバイスコントローラは入出力装置を制御するための制御レジスタを持っており、プロセッサは制御レジスタに命令を書き込んだり、制御レジスタの値を読み出すことで入出力装置を制御する。通常これらのデバイスコントローラは、チップセットと呼ばれるLSIに集約されていて、チップセットはマザーボードを介してCPUと、PCIeベースの通信プロトコルを使用したDMI（Direct Media Interface）と呼ばれる高速なバスで接続される。

今回の実装では、実際のハードウェアを使用することはできないため、QEMUと呼ばれるエミュレーターを使用する。os/run.shにQEMUを起動するコマンドが記述されている。

マルチコア

CPUが機械語命令を順次実行していく流れのことをハードウェアスレッドという。コンピュータの性能を向上させるには大きく、クロック周波数を高くする方法と複数のプロセッサを用いて複数のハードウェアスレッドを並列に動作させる方法がある。複数のプロセッサを持つCPUのことをマルチコアCPUと呼ぶ。前者の方法はクロック周波数が3GHzを超えたあたりから頭打ちになりつつあり、現在は後者の方法が中心となっている。

今回のOSではマルチコアには対応しない。

ブートストラップ

電源を入れてからOSが起動するまでの一連の動作をブートストラップ（ブート）と呼ぶ。通常のプログラムはカーネルによってメモリ上に載せられるが、OSもソフトウェアである以上、実行するにはメモリ上にプログラムを載せる必要がある。一般的にOSはストレージ上に通常のファイルとして格納されているため、これをOSが起動していない状態で読み込む必要がある。

そこでROMやフラッシュメモリなどの不揮発性メモリ上にブートストラップローダと呼ばれるプログラムを用意しておき、電源投入時にこれが動作することで、ストレージ内の特定の場所に置かれたブートローダと呼ばれるプログラムをメモリにロードして起動する。ブートローダはストレージ内に置かれているカーネルを読み込み、メモリ上に載せ、最後にカーネルに制御を移す。

具体的には下記の流れでブートが行われる。

電源を入れるとパワーオンリセットと呼ばれる回路によりプロセッサがリセットされる。これにより、プロセッサはあらかじめ定められた状態に設定され、特定の物理アドレスから実行を開始する。そこにはBIOSの実行開始アドレスにジャンプする機械語命令が入っている
BIOSは最初にハードウェアの簡単な診断を行うPOST（power on self test）と呼ばれる処理を実行し、搭載している物理メモリの容量の確認や、起動に必要な周辺機器の検出と初期化などを行う
ブートデバイス（OSがインストールされているストレージ）の先頭にあるMBR（master boot record）と呼ばれる領域を読み込む。MBRにはブートストラップコードと呼ばれる小さい機械語プログラムとストレージのパーティション情報が含まれている。次にブートストラップコードに制御を移す
ブートストラップコードはパーティション情報をチェックし、ブート可能とマークされているパーティションの先頭から、セカンダリブートローダと呼ばれる小さなプログラムをロードし、実行する
セカンダリブートローダは、OSを使わずに直接、ストレージにアクセスし、カーネルを読み込む
読み込んだカーネルの実行開始アドレスにジャンプし、カーネルの起動処理が始まる

今回はOpenSBIを使用してブートを行う。SBI（Supervisor Binary Interface）とは、ファームウェアがOSに提供する機能を定義しているインターフェースで、いわばカーネルが利用できるAPIのようなものである。SBIの仕様書はGitHub上で公開されており、デバッグコンソール上での文字の表示や、再起動・シャットダウン、タイマーの設定など、あると便利な機能が定義されている。

SBIの実装例として有名なのがOpenSBIで、QEMUではデフォルトでOpenSBIが起動し、ハードウェア特有の初期化処理を済ませた後、カーネルを起動してくれる。OpenSBIは、RISC-Vアーキテクチャにおけるハードウェア抽象化レイヤーの一部として機能しており、OSがハードウェアリソースを扱いやすくするための役割を果たしている。OpenSBIは、OSに対して、標準化されたインターフェース（SBI）を提供する。このインターフェースを通じて、OSはハードウェアの詳細に依存せずに、標準化された方法でハードウェアリソースにアクセスできる。例えば、CPUの起動やシャットダウン、タイマーの設定、コンソールI/Oなど、低レベルのハードウェア操作を抽象化し、OSがこれらの操作を直接扱わなくても済むようにしている。

os/run.shを実行してみて、OpenSBIが起動し、booted!という文字列が表示されるか確認すること。Ctrl+a/xでQEMUを停止できる。os/kernel.cを見ると、OpenSBIを利用したputchar関数の実装やブートを行う処理が実装されている。

os/kernel.ld（詳細は後述）を見てみると、KEEP(*(.text.boot));という記述があるが、これは.text.bootセクションを先頭に配置するという意味である。os/kernel.cのboot関数を見ると.text.bootセクションに配置されるように記述されているのがわかる。つまりOpenSBIからカーネルに制御が移るとまず最初にこのboot関数が実行されるようになっているのである。これによってスタックポインタの初期化をした後にkernel_main関数を呼び出すようになっている。

プロセッサの動作モード

一般的にプロセッサはカーネル（特権）モードとユーザーモードと呼ばれる２つの動作モードを持つ。カーネルモードはカーネルを実行するためのモードであり、プロセッサの全ての動作を際限なく行えるのに対し、ユーザーモードはユーザープログラムを実行するためのモードであり、特権命令（システムに影響を与える可能性がある機械語命令）の実行やハードウェアへの直接アクセスが禁止される。ユーザーモードでこれらを実行しようとすると特権違反例外が発生し、カーネルに制御が移る。

RISC-Vには、下記の３つの動作モードがある。今回のOSでは、明示的にUモードに移行する（ユーザープログラムの実装を参照）までの間はSモードで動作する。

Mモード：OpenSBIが動作するモード
Sモード：カーネルが動作するモード
Uモード：アプリケーションが動作するモード

RISC-Vには、下記のような特権命令がある。特権命令はUモードの時は実行できない。CSR (Control and Status Register) とは、CPUの動作設定を格納するレジスタである。

命令とオペランド

概要

疑似コード

csrr rd, csr

CSRの値をrdに読み込む

rd = csr;

csrw csr, rs

rsの値をCSRに書き込む

csr = rs;

csrrw rd, csr, rs

CSRの値をrdに読み込み、rsの値をCSRに書き込む

rd, csr = csr, rs;

sret

Sモードで発生したトラップから復帰する

sfence.vma

MMUのTLBをフラッシュする。またメモリフェンスの役割も果たす

その他に下記のようなアセンブリ命令がある。

命令

概要

疑似コード

addi rd, rs, imm

rsに即値immを加算し、rdに格納する

rd = rs + imm;

sw rs, imm(rd)

rdにimmを加算したアドレスにrsの値を格納する

*(rd + imm) = rs;

lw rd, imm(rs)

rsにimmを加算したアドレスから値を読み込み、rdに格納する

rd = *(rs + imm);

mv rd, rs

rsの値をrdにコピーする

rd = rs;

call label

labelにジャンプする

goto label;

ret

raレジスタに格納されているリターンアドレスにジャンプする

goto ra;

ecall

トラップハンドラを呼び出す

割り込み

プロセッサは、システムで何らかの急いで処理すべき事象が発生したときに、実行中のプログラムを一時中断し、別のプログラムを実行する、割り込みと呼ばれる機能を持っている。このときに実行するプログラムを割り込みハンドラと呼ぶ。割り込みには、外部割り込みと内部割り込みがある。

外部割り込み（ハードウェア割り込み）は、プロセッサ外部のデバイスで何らかの事象が発生したことをプロセッサに通知するための割り込みである。プロセッサは外部からの割り込みを受け付けるためのIRQ（割り込み信号線）を持つ。単に割り込みといった場合は、通常外部割り込みを指す。

コンピュータは指定した周期でプロセッサに割り込みをかけるタイマと呼ばれるデバイスを備えている。この割り込みをタイマ割り込みという。OSには定期的に実行する様々な処理があり、タイマ割り込みはそのために使用される。タイマ割り込みは外部割り込みの一種である。

内部割り込みは、プログラムの実行に伴ってプロセッサ内部で発生する割り込みである。内部割り込みには（狭義の）ソフトウェア割り込みとトラップ（例外、フォールト）がある（内部割り込み自体をソフトウェア割り込みと呼ぶこともある）。

ソフトウェア割り込みは特別な機械語命令を実行することで発生し、プロセッサのモードをユーザーモードからカーネルモードに変更するために使用される。トラップはプログラムの実行中になんらかの例外的な事象が発生することで引き起こされる。例えばゼロ除算例外、未定義命令違反、特権違反例外、セグメンテーションフォールト（アクセスが許可されていないアドレスを参照）、ページフォールト（物理メモリが割り当てられていない仮想ページを参照しようとしたとき）などによって引き起こされる。

トラップ（例外）の実装

トラップが発生すると、RISC-Vでは下記の流れで処理が進む。

CPUはmedelegレジスタを確認して、トラップをどの動作モードで処理するかを決定する。今回はSモードで処理するようにOpenSBIによって設定されている
トラップ発生時のCPUの状態を各CSRに保存する
stvecレジスタの値をプログラムカウンタにセットして、カーネルのトラップハンドラ（例外処理プログラム）にジャンプする
トラップハンドラは、トラップ発生時の汎用レジスタの値を保存し、トラップの処理を行う
例外処理を済ませると、保存していた実行状態を復元し、トラップ発生箇所から実行を再開する

上記の２で保存されるCSRは下記の通りである。カーネルのトラップハンドラはこれらの情報をもとに、必要な処理を判断したり、トラップ発生時の状態を保存・復元する。

レジスタ

概要

scause

トラップの原因を示す

stval

トラップの付加情報（原因となったメモリアドレスなど）を示す。具体的な内容は例外の種類による

sepc

トラップが発生時のプログラムカウンタの値が入る

sstatus

トラップ発生時の動作モードを示す

上記の３を実現するには、stvecレジスタにトラップハンドラのアドレスをセットする必要がある。RISC-Vの仕様上、このときセットされるアドレスは必ず4バイト境界にアラインされている必要がある。

上記の４では、sp, ra, gp, tp, t0~t6, a0~a7, s0~s11の汎用レジスタの値を保存したい。RISC-Vには、カーネルが好きに使って良いsscratchレジスタと呼ばれるレジスタが用意されているので必要なら使うと良い。また、トラップの処理として、今回はトラップが発生したことがわかるようにカーネルパニックを発生させたい。このとき、原因や発生箇所がわかるようなメッセージを表示すること。os/kernel.hにパニックやCSRの値を読み書きするためのマクロが用意されているので、それを使うと良い。READ_CSR(reg)のようにすることで指定されたCSRの値を読み出し、値はuint32_t型で返される。またWRITE_CSR(reg, value)のようにすることで指定されたCSRに値を書き込むことができる。

raはリターンアドレスを格納するレジスタである。gpはグローバルポインタで、グローバル変数のアドレスを格納するレジスタである。tpはスレッドポインタで、スレッドローカル変数のアドレスを格納するレジスタである。t0~t6は一時レジスタで、関数内で一時的に使用するレジスタである。a0~a7は関数呼び出し時の引数を格納するレジスタである。s0~s11はスタックポインタを除く関数内で使用するレジスタである。トラップはシステムの正常な動作を中断し、例外処理に移行するため、トラップが終了した後に元の状態に正確に復帰できるようにするために、これらのレジスタの値を保存しておく必要がある。

上記の５では、前述したsret命令を使用することでトラップから復帰することができる。sret命令が実行されると、sstatusレジスタのSPPビットに設定された動作モードに復帰し、またsepcに格納されているアドレスがプログラムカウンタにセットされる。トラップが発生すると、SPPビットは、トラップがUモードで発生した場合は0に、そうでない場合は1に設定される。トラップハンドラから戻るためにsret命令が実行されると、SPPビットが0の場合はUモードに、SPPビットが1の場合はSモードに設定され、その後SPPビットは0に設定される。

最後にトラップを発生させ、正しく動作するかを確認すること。トラップを発生させるために、unimp命令を使用するとよい。この命令はRISC-Vの命令セットには存在しない架空の命令で、CPUが無効な機械語であると判断するようなバイナリ列を出力してくれる便利なコンパイラの機能である。

プログラム

実行ファイルの構造

実行ファイルはヘッダと複数のセクションから構成される。ヘッダはマジックナンバ（ファイル形式を識別するための値）から始まり、実行ファイルのメタデータ（各セクションのサイズ、プログラムの実行開始アドレス、サポートするOSのバージョン、プロセッサの情報など）を格納している。セクションには下記がある。

テキスト：プログラムの機械語命令の部分を格納する
データ：プログラムが使用するデータのうち、初期値が与えられているものを格納する
BSS：初期値が与えられていないデータのための領域。実行ファイルにはBSSセクションのサイズ情報のみが格納される
共有ライブラリ情報：動的リンクする共有（動的）ライブラリに関する情報を格納する
リロケーションテーブル：プログラムを任意のアドレスに配置するための情報を格納する
シンボルテーブル：関数やグローバル変数などのシンボルとアドレスの対応表を格納する。動的リンクでは、共有ライブラリからプログラムのアドレスを参照するために用いる。デバッガはこの情報を使用することでシンボル名を使用してデバッグできるようにする
デバッグ情報：デバッグに必要な情報（ソースコードの行番号とアドレスの対応表など）が格納される。デバッガはこの情報も参照する。プログラムの開発段階でのみ使用される
その他：フォーマットによっては実行ファイルのアイコンの画像などを格納できるものもある

Cソースコードが実行ファイルになるまで

プリプロセス：マクロ展開、ファイルのインクルード、条件付きコンパイルが処理される
コンパイル：コンパイラはプリプロセスされたソースコードを受け取り、アセンブリ言語に変換する
1. 字句解析：トークンに分割
2. 構文解析：構文木に変換
3. 中間表現生成：ClangのようなLLVMを基盤とするコンパイラはLLVM IRを生成する
4. 最適化：LLVM IRはLLVMのバックエンドで最適化される。ループ最適化、デッドコード除去、インライン展開などが行われる
5. アセンブリコード生成：最適化された中間表現をターゲットアーキテクチャに応じたアセンブリコードに変換する
アセンブル：アセンブラはアセンブルコードをマシンコード（オブジェクトファイル）に変換する
リンク：リンカは全てのオブジェクトファイルと静的ライブラリをリンクし、未解決の外部シンボルを解決して１つの実行可能ファイルを生成する

os/run.shにClangを使ってCソースコードをコンパイルし、カーネルの実行ファイルを生成するコマンドが記述されている。

プログラムのロード

プログラムを実行するには、ストレージ上に実行ファイルとして格納されている機械語プログラムを、プロセッサのアドレス空間上にロードする必要がある。またスタックやヒープ領域などの実行中に必要なメモリ領域を確保し、初期化する必要もある。これらを行うプログラムはローダと呼ばれ、カーネルに組み込まれている。ロードにあたって、OSはプロセスにアドレス空間上の適当なメモリ領域を割り当てる。プロセスのメモリ空間は低位アドレスから順に下記の領域から構成される。

テキスト領域：プログラムを構成する機械語命令を格納する。実行ファイルのテキストセクションに対応する
データ領域：初期値が与えられているデータを格納する。実行ファイルのデータセクションに対応する
BSS領域：初期値が与えられていないデータのための領域。実行ファイルのBSSセクションに対応する
ヒープ領域：C言語のmalloc関数やC++言語のnew演算子のようにプログラムの実行中に動的に割り当てるメモリのための領域。通常アドレスの大きくなる方向に拡大する
スタック領域：機械語プログラム実行中に使用されるスタックのための領域。通常アドレスの小さくなる方向に拡大する

実行中に必要なデータを一時的に保持するために、スタック領域を使用する。一般的なプロセッサはスタックトップ（最後にpushしたデータ）のアドレスを持つスタックポインタ（SP）というレジスタを持っている。スタックはレジスタに格納できない関数の引数やリターンアドレス、ローカル変数などを保持する。

しかし、実際はプロセスのメモリ空間は上記のように単純に構成されるわけではない。例えば、プロセスのメモリ空間はセキュリティの観点からランダム化されることが多い。これはASLR（Address Space Layout Randomization）と呼ばれ、プログラム実行時にスタック、ヒープ、実行ファイルのコードやデータセグメントなど、メモリ内の各種領域のアドレスをランダムに配置することで、攻撃者がアドレスを予測して攻撃を行うことを難しくする。ASLRは、バッファオーバーフローやリターンアドレスの上書きといったエクスプロイト技術に対して有効である。これらの攻撃は特定のメモリアドレスを狙うことが多いが、ASLRによってアドレスが予測不可能になるため、攻撃成功率が低下する。この技術は、Linux、Windows、macOSなど、多くのオペレーティングシステムで採用されており、セキュリティ対策の一環として標準的なものになっている。

os/kernel.ldはリンカスクリプトと呼ばれるファイルである。リンカスクリプトは、リンクプロセス中にリンカがオブジェクトファイルやライブラリをどのようにメモリ空間に配置するかを指定するためのスクリプトである。テキスト領域、データ領域、BSS領域などが定義されていることがわかる。os/run.shを見るとカーネルをビルドする際にkernel.ldをリンカスクリプトとして指定していることがわかる。またユーザー空間用のリンカスクリプトであるos/user.ldも使われており、カーネルアドレスと被らない領域（0x1000000から 0x1800000の間）にユーザープログラムを配置するように指定されている。

下記の流れでプログラムはロードされる。

実行ファイルのヘッダ部から各セグメントの大きさを読み取る
必要なメモリ領域を確保する
実行ファイルからテキストセクションとデータセクションの内容をメモリ上に読み込む
BSS領域を初期化する（一般的にはゼロクリアする）
スタック領域を初期化する（一般的にはゼロクリアする）
プログラムが動的リンクされる場合、動的リンクの準備を行う（メモリ上に共有ライブラリを配置するなど）

メモリ管理

動的メモリ割り当て

メインメモリには１バイトごとに１つの物理アドレスが割り当てられる。またプロセッサがアクセスできる物理アドレスの範囲を物理アドレス空間と呼ぶ。コンピュータでは、必要に応じてメモリ領域を動的に確保したり解放したりすることが一般的に行われる。このような処理は動的メモリ割り当てと呼ばれる。

動的メモリ割り当ての実装

物理メモリを動的に割り当てられるようにしたい。ただし、malloc関数のようにバイト単位で割り当てるのではなく、ページと呼ばれるまとまった単位で割り当てる。ページサイズは4KB（4096B）が一般的である（os/common.hにPAGE_SIZEが定義されている）。具体的には、ページ数を引数として渡されると、そのページ分の割り当て可能なメモリ領域の先頭アドレスを返す関数を実装すること。このとき、渡すメモリ領域はゼロクリアしてから返すことが一般的である。memset関数が用意されているので、それを使用する。動的に割り当て可能なメモリ領域はリンカスクリプトで定義されている__free_ramから__free_ram_endまでの領域とする。最後に実際に動的にメモリを割り当て、その物理アドレスを表示し、正しく動作することを確かめること。

今回は使い終わったメモリページを解放する処理は実装しない。自作OSを長時間実行することはないと思うので、メモリリークが発生しても問題ないためである。今回実装する割り当てアルゴリズムのことをLinearアロケータ（Bumpアロケータ）と呼び、解放処理が必要ない場面で実際に使われている。

仮想メモリ

仮想メモリは、プロセスが使用するアドレスと実際の物理アドレスを分離することで、メモリを仮想化する技術である。仮想記憶では、プロセスごとに専用の独立したアドレス空間を割り当てる。プロセスから見えるアドレスは物理アドレスではなく、仮想アドレスである。プロセスがメモリにアクセスするときは、仮想アドレスを物理アドレスに変換した上で物理メモリにアクセスする。

仮想メモリを用いることで、他のプロセスに割り当てられたメモリに影響されずに各プロセスに対して連続したアドレス空間を提供でき、また各プロセスのアドレス空間を分離することで互いに隔離し、システムの安定性を高めることができる。

ページング方式

仮想アドレスと物理アドレスとの対応関係（マッピング）をバイト単位で指定できるようにすると、アドレス変換のための情報量が膨大になってしまうため、ある程度の大きさのメモリブロックを単位としてマッピングを行う。現在は固定長のメモリブロックを単位とするページング方式が主流である。

ページング方式では、仮想アドレス空間と物理アドレス空間を固定長（ページサイズ）のブロックに分割する。仮想アドレス空間のブロックを仮想ページ（ページ）、物理アドレス空間のブロックを物理ページ（ページフレーム）と呼ぶ。ページにはページ番号がついており、仮想アドレスや物理アドレスは先頭部分にそのアドレスが属するページ番号を持ち、ページ内オフセットがそれに続く構成になっている。

仮想アドレスから物理アドレスへの変換は、ページを物理ページにマッピングすることで行われる。プロセスに割り当てるメモリは物理アドレス空間上では連続している必要はないため、物理メモリの外部断片化が発生しない。

カーネルは空いている物理ページを連結リストやビットマップなどで管理する。カーネルは新しくプロセスを実行する場合などにプロセスに割り当てるページが必要になると、空いている物理ページを割り当てる。また、プロセスが終了した場合など、ページが不要になれば対応する物理ページを回収する。

ページテーブル

仮想アドレスから物理アドレスへの変換にはページテーブルと呼ばれるデータ構造を使用する。ページテーブルは仮想ページ番号でインデックスする配列であり、物理メモリ上に配置される。ページテーブルの要素をページテーブルエントリと呼び、１つのページテーブルエントリが１つの仮想ページに対応し、マッピングされている物理ページの番号や各種のフラグを格納している。

仮想アドレスを物理アドレスに変換する作業は、MMU（memory management unit）と呼ばれるハードウェアがページテーブルを参照することで動的に行われる（動的アドレス変換）。現代の一般的なプロセッサはMMUを内蔵している。

MMUには、使用するページテーブルの物理アドレスを保持するレジスタ（ページテーブルベースレジスタ）があり、異なるページテーブルを指すように変更することで、プロセッサが使用する仮想アドレス空間を切り替えることができる。

OSはプロセスごとにページテーブルを用意し、コンテキストスイッチによって実行するプロセスを切り替えるとき、ページテーブルベースレジスタの値を、次に実行するプロセスのページテーブルの先頭アドレスに設定し直す。

具体的には下記の流れでアドレス変換が行われる。

仮想アドレスから仮想ページ番号とページ内オフセットを求める
ページテーブルベースレジスタからページテーブルを参照し、仮想ページ番号をもとに、ページテーブルエントリを取得する
ページテーブルエントリから物理ページ番号を取得する
物理ページ番号とページ内オフセット（１で取得したもの）を組み合わせて物理アドレスを求める（物理ページ番号 * ページサイズ + ページ内オフセット）

多段ページテーブル

仮想アドレス空間が広くなると、その分、必要なページテーブルのサイズも大きくなる。例えば仮想アドレス空間が256TB、ページサイズが4KB、ページテーブルエントリが8Bの場合、ページテーブルとして、256 / 4 * 8 = 512GB必要になる。しかし、一般的にプロセスは仮想アドレス空間のごく一部しか使用しないため、ほとんどのページテーブルエントリは無駄となる。

そこで考え出されたのが、ページテーブルを階層化した多段ページテーブルである。多段ページテーブルでは、最下位のページテーブルは１段しかない場合のページテーブルと同様のページテーブルエントリを保持するが、最下位以外のページテーブルでは、各エントリは１つ下のページテーブルの物理アドレスを保持する。

多段ページテーブルでは、実際に使用する仮想アドレスの範囲に対応するページテーブルのみを用意すれば良いため、物理メモリを節約することができる。

TLB

ページテーブルを用いたアドレス変換では、メモリアクセスのたびにページテーブルの段数分のメモリ参照が追加で必要となるため、単純な実装ではただでさえ遅いメモリへのアクセスが非常に遅くなってしまう。このため、MMUは仮想アドレスから物理アドレスへのアドレス変換を高速化するためのTLB（トランスレーションルックアサイドバッファ）と呼ばれるハードウェアを備えている。

TLBはページテーブルエントリ専用のキャッシュメモリであり、連想メモリ（CAM: content addressable memory）と呼ばれる、高速に任意のエントリを検索できる特殊なメモリで構成されている。MMUは、仮想アドレスに対応するページテーブルエントリがTLB内に存在（TLBヒット）すれば、TLB内のページテーブルエントリを使用する。このときはページテーブルを参照する必要がないため、アドレス変換を高速に実行できる。一方、存在しなければ（TLBミス）、ページテーブルを参照してページテーブルエントリを取得し、取得したエントリをTLBに格納する。

一般的なプロセッサではTLBのエントリ数は数千個程度であり、TLBは仮想アドレスをキーとしてキャッシュされたページテーブルエントリを検索する。プロセスが異なれば同じ仮想アドレスでもページテーブルエントリは異なるため、プロセス間でコンテキストスイッチする場合、OSはTLBをクリアしなければならない。これをTLBフラッシュと呼び、そのための機械語命令がある。

多段ページテーブルの実装

ここではSv32方式のページテーブルを構築したい。Sv32とはRISC-Vのページング機構である。２段構造のページテーブルになっており、32ビットの仮想アドレスのうち、先頭の10ビットは１段目のページテーブルのインデックス、続く10ビットは２段目のインデックス、残りの12ビットはページ内オフセットを保持する。１段目のページテーブルエントリは２段目のページテーブルの物理アドレスを保持し、２段目のページテーブルエントリは物理ページの物理アドレスを保持する。

ページテーブルエントリには物理アドレスだけでなく、各種のフラグも保持する。RISC-Vのページテーブルエントリは32ビットで、上位22ビットが物理ページ番号、下位10ビットがフラグである。フラグはV（有効化フラグ）、R（読み込みフラグ）、W（書き込みフラグ）、X（実行可能フラグ）、U（ユーザーモードフラグ）がある。Vが0の場合はそのページテーブルエントリはマッピングされておらず、無効である。R、W、Xが0の場合はそれぞれ読み込み、書き込み、実行が禁止される。Uが0の場合はユーザーモードの場合にアクセスが禁止される。これらのフラグはos/kernel.hに定義されている。

ページテーブルは下記の流れで構築される。こうすることで、仮想ページと物理ページのマッピングを行うことができる。

仮想アドレスの最初の10ビット（vpn1）を１段目のページテーブル（table1）のインデックスとして使用する。続く10ビット（vpn0）を２段目のページテーブル（table0）のインデックスとして使用する。残りの12ビット（offset）をページ内オフセットとして使用する
上位22ビットにtable0の物理ページ番号、下位10ビットに有効化されたVフラグを格納した値をtable1[vpn1]に格納する
上位22ビットにマップする物理ページの番号、下位10ビットにVフラグを含む各種フラグを格納した値をtable0[vpn0]に格納する

os/common.hにis_alignedというアライメントされているかどうかを確かめるためのマクロが定義されているので必要に応じて使用すること。

下位12ビット（ページ内オフセット）が異なる仮想アドレス同士は同じページテーブルエントリを共有することになる。また、真ん中の10ビットが異なる仮想アドレス同士も同じ２段目のページテーブルを共有することになる。つまり、近い仮想アドレス同士は同じページテーブルエントリやページテーブルに存在することになる。プログラムには参照局所性という特性があり、ある時点で参照されたリソースは近い将来にも再び参照される可能性が高く（時間的局所性）、あるリソースが参照されたとき、その近くにあるリソースも参照される可能性が高い（空間的局所性）ため、このようなページング機構になっているおかげで、ページテーブルのサイズを小さく抑えられ、またTLBヒット率が高くなる。

仮想アドレス空間

仮想アドレス空間の構成はOSによって異なるが、低位領域をユーザープロセス用とし、高位領域をカーネル用とするのが一般的である。前者をユーザー空間、後者をカーネル空間と呼ぶ。

Previousはじめに Next日曜日

Last updated 3 months ago