このテキストは、運営している韓国のブログを日本語に翻訳したものです。
韓国のブログ：https://yunsuu.notion.site/e379eccd32c545419f0651f743c12c13?v=35310b282de24cc5a292fe45cc498a32&pvs=74
この記事は「Operating Systems: Three Easy Pieces」を読んでまとめた本です。
著者が無料で公開しているので、興味のある方はぜひ読んでみてください。
本にある良い問題は解いてgithubにアップロードしています。
github：https://github.com/yunsuu/ostep-homework-solution
本のリンク：https://pages.cs.wisc.edu/~remzi/OSTEP/
これまでに、ページテーブルがすべてカーネルが所有する物理メモリ領域に存在するという前提の理論を説明してきました。
しかし、ページテーブルはプロセスが増えるほどその数が増え、メインメモリに負担をかけるようになります。そのため、エンジニアたちはどうすればページテーブルを減らすことができるかを悩み、その一つの方法がSWAP方法です。
SWAP方法は、すべてのページテーブルをメインメモリに保存しておくことができないので、一部をDiskに保存しておき、必要に応じてDiskにあるページテーブル情報をMemoryにあるページテーブルと交換しながら、各プロセスが実際に持っているメモリよりもはるかに大きなメモリを持っていると錯覚させる技術です。
ディスクにページテーブル情報を保存している領域をSwap spaceと呼びます。各ページ情報が保存されている単位をBlockと呼び、このBlockの単位はMemoryのpage単位と同じです。
present bit
PTEに存在するbitであり、現在のページがメモリにあるかディスクにあるかを確認する役割のbitです。
ディスク↔メモリ交換技術を実装するために使用するビット。
1であれば物理メモリに存在し、0であればディスクのどこかに存在するという意味です。
物理メモリに存在しない（ディスクに存在する）ページをアクセスすることをページフォルトと言います。
ページフォルト
ページフォルトとは、上の図で説明すると、オペレーティングシステムがプロセス3を実行しようとしているが、メモリにプロセス3に関するページがなくて実行できない。これをページフォルトと言います。
ディスク上のスワップスペースに存在しているページの位置を特定し、それをメモリにロードします。
ディスクが関与するため、IO作業として分類されます。
ページフォルトが発生した該当のプロセスは、IO作業が終了するまでプロセスはブロックされた状態であることを記憶しなければなりません。
- ページがメモリに存在するかどうかを確認します。present bitが0であることを確認すると、ページフォルトを発生させます。
- ページフォルトが発生すると、ページフォルトトラップハンドラーを使用してOSカーネルモードに入ります。
- OSはディスクの中から該当のページを探して見つけます。
- 見つけたページ情報をメモリ（ページテーブル）にロードします。
メモリに空きがない場合は？
プロセス3を実行するためにメモリにページ情報をロードしようとしているが、メモリがいっぱいだ。このような場合、現在のメモリからどのものを排除するかを決めなければならず、これをページ交換ポリシーと呼びます。
ページ交換ポリシーはIO作業を伴うため、設計が間違っていると、プロセスの処理速度が非常に遅くなる可能性があります。
ページフォルト作動アルゴリズム
ハードウェア
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True) // TLB Hit
if (CanAccess(TlbEntry.ProtectBits) == True)
Offset = VirtualAddress & OFFSET_MASK
PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
Register = AccessMemory(PhysAddr)
else
RaiseException(PROTECTION_FAULT)
else // TLB Miss
PTEAddr = PTBR + (VPN * sizeof(PTE))
PTE = AccessMemory(PTEAddr)
if (PTE.Valid == False)
RaiseException(SEGMENTATION_FAULT)
else
if (CanAccess(PTE.ProtectBits) == False)
RaiseException(PROTECTION_FAULT)
else if (PTE.Present == True)
// assuming hardware-managed TLB
TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
RetryInstruction()
else if (PTE.Present == False)
RaiseException(PAGE_FAULT)
注意しなければならない分岐点
- ページが存在し、有効な場合
- ページが存在しないが有効な場合（ディスクにページがあるという意味）
- ページが無効な場合（バグが発生した場合）
ソフトウェア
PFN = FindFreePhysicalPage()
if (PFN == -1) { // No free page found
PFN = EvictPage() // Run replacement algorithm
DiskRead(PTE.DiskAddr, PFN) // Sleep (waiting for I/O)
PTE.present = True // Update page table with present
PTE.PFN = PFN // Bit and translation (PFN)
RetryInstruction() // Retry instruction
}
交換が起こる瞬間
ページ交換は、メモリの最大値、最小値を設定して、交換アルゴリズムの動作に利用します。
あまりにも満杯だと正しく動作しないので、ｗｗｗ；；；
これらをバックグラウンドで実行するプログラムをスワップデーモン、ページデーモンと呼びます。
最も重要な点
これらすべての作業は、プロセスが知らないでバックグラウンドで動いている恐ろしい事実…
プロセスが気にしないように構造を組むことで、プログラマーたちは楽になります。
（メモリ交換を気にしながらプログラムを組むなんて、Hello worldを出力するだけでも頭が痛くなりそうです。）