Paging

このテキストは、運営している韓国のブログを日本語に翻訳したものです。

韓国のブログ：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/

セグメンテーションのように可変長の領域を割り当てて仮想メモリを実装する方法もありますが、生まれつきの制約からくるフラグメンテーション、つまり空き領域のメモリ管理の難しさから、割り当てが複雑になることが避けられません。そのため、可変長ではなく配列のように一定の固定長でメモリを分割して仮想メモリを割り当てる方法が生まれ、これをページングと呼びます。ページングで分割された物理メモリの各領域をページフレームと呼びます。

利点

柔軟性と管理のシンプルさ

ページングを使用すれば、セグメンテーションのようにヒープやスタックがどの方向に拡大するか、どのように使用されるかについての仮定をしなくても良いです。セグメンテーションではヒープやスタックが物理メモリの連続した領域に位置しているため、増加方向、使用範囲などを考慮しなければなりませんでした。しかし、ページング技術では初めから区間が分割されていたため、各ページの順序だけを考慮すればヒープやスタックを簡単に実装でき、ヒープやスタックの使用範囲の制限も設けずに仮想メモリの実装に大きな困難はありません。

本のページが散らばっていても目次があれば論理的に正しく読むことができるのと同じ原理です。

また、目次の機能を果たすものをページング技術ではページテーブルと呼びます。そして、このページテーブルは各プロセスごとに存在します。

ページの区分方法

各プロセスごとに、現在どのページを読んでいるか（CPUのPCのような役割）を保存する場所が必要です。

例えば、メモリのサイズを64（2^6）単位で定義した場合、6ビットでページを区分することができます。VPN（Virtual page number）はどのページであるかを確認する役割を果たし、オフセットは各ページのどこに位置しているかを保存する役割を果たします。通常、各プロセスの最上位ビットを使用してこれを実装します。

このように表示したページの位置は物理アドレスに変換することができます。このとき、仮想メモリであれ、物理メモリであれ、ページのサイズは変わらないため、VPN（Virtual page number）→PFN（Physical Frame number）だけが変更されます。オフセットは変更されません。

仮定

ここでは、混乱を避けるために、各プロセスのテーブルは配列形式で物理メモリに保存されていると仮定して説明します。

ページテーブルの構造

1つのページには複数のPTEが存在することがあります。

ページテーブルアドレス変換アルゴリズム

// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT

// Form the address of the page-table entry (PTE)
PTEAddr = PTBR + (VPN * sizeof(PTE))

// Fetch the PTE
PTE = AccessMemory(PTEAddr)

// Check if process can access the page
if (PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
    RaiseException(PROTECTION_FAULT)
else
    // Access is OK: form physical address and fetch it
    offset = VirtualAddress & OFFSET_MASK
    PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
    Register = AccessMemory(PhysAddr)

ページテーブルアドレスの変換には、次のプロセスのアルゴリズムが必要です。

ここで重要な点は、VPNをPTEに変換するのに1回のメモリアクセス、

PTEを取得し、PFNを使用してデータにアクセスするのに1回、

計2回のメモリアクセスが発生することです。1つの命令を実行するのに基本的に2回のメモリアクセスが必要なら、プロセスは2倍遅くなります。それだけメモリアクセスはCPUにとって非常に大きな操作です。これがページング技術の欠点です。