Translation-Lookaside buffer

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

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

この記事は、ページング技術で使用されるメモリ管理ユニットの一つであるTLB（Translation-lookaside buffer）について調査するものです。

TLB?

仮想メモリ技術では、物理アドレス ↔ 仮想アドレスの相互変換は時間がかかる操作であり（アドレスを変換する過程でメモリを一度参照する必要があるため）、この操作を減らすための方法が考え出されました。基本的な原理はキャッシュと似ています。

各VPNに対応するPFNをTLBにテーブル形式で保存しておき、TLBに保存されているVPNであれば、PFNへの変換過程を経ずに直接メモリを使用できるようにするメモリ管理ユニットです。

TLBのアルゴリズム

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
		//PTBR -> page table base rigister (where page table start at memory)
    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
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()

TLBのアルゴリズムは上記のようになります。ここでSHIFTはOFFSETの数だけ割り当てられます。VPNとOFFSETが以下のように設定されているとすると、SHIFTの値は4になります。その場合、VPN_MASKの値は110000になるでしょう。

アルゴリズムの動作原理を簡単に説明してみましょう。まず、TLBに現在参照しているページが存在するかどうかを確認します。もし存在する場合は、TLBに保存されているPFNを直接取得します。これにより、仮想アドレスを物理アドレスに変換する過程を省略し、メモリへのアクセスを容易にすることができます。

しかし、TLBに一致するVPNが存在しない場合は、ページテーブルにアクセスして対応するPage Entityをメモリアクセスを通じて取得します。そして、この取得した値をTLBに挿入し、ifが開始する箇所（//TLB Hit）にジャンプします。

アルゴリズムの動作例

int sum = 0;
for (i = 0; i < 10; i++) {
sum += a[i];
}

より詳細な理解のために、配列の10個の要素を巡回するコードを使って、TLBがどのように動作するかを見てみましょう。TLBは何も保存されていないと仮定します。

a[0]、a[3]、a[7]にアクセスするときは、ページに初めてアクセスするので、TLBには値がなく、アルゴリズムのTLB Miss部分のコードと同様に、仮想アドレス→物理アドレスの変換処理が必要です。しかし、他の要素にアクセスするときは、TLBに保存されているページにアクセスするので、アドレス変換処理は必要ありません。この例では、Missは3、Hitは7で、ヒット率は70%となる例です。

TLB MISSを解決する方法

TLB Missが発生した場合の処理方法は、CPUの設計により異なります。CISC設計のCPUはこれをハードウェア回路で解決し、RISCはソフトウェア（OS）が解決する方式です。

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 Mis
		RaiseException(TLB_MISS)

OSによる解決方法は、Missが発生した場合、RaiseException(TLB_MISS)を通じて例外処理を起こし、トラップハンドラを呼び出すものです。トラップハンドラを呼び出すとカーネルモードに切り替わり、カーネルモードで仮想アドレスを物理アドレスに変換する特権命令を使用します。

このとき、ソフトウェアで解決する際に考慮すべき点が2つあります。通常のトラップハンドラは、呼び出されるとカーネルモードで処理を行い、実行中のプロセスの次の命令を実行します。しかし、TLB Missのシステムコールは、リターン後にトラップを引き起こした命令を再実行し、再実行時にHitが発生します。

ここで注意すべき重要な点は、オペレーティングシステムはトラップ発生の原因によって保存すべきPC値が異なるということです。

二つ目の問題は、TLB Missハンドラを実行する際にTLB Missが無限に繰り返されないよう注意が必要です。これは、TLB Missハンドラにアクセスする状況でMISSが発生する状況です。この問題の解決方法は、TLB Missハンドラを固定の物理メモリアドレスに保存することです（まるでプログラミングするときにグローバル変数を固定して使用するように）。最初から位置を固定することで、MISSが発生する確率をなくす方法です。

コンテキストスイッチとTLB

TLBは仮想メモリページの数をキャッシュする技術であるため、一つのプロセスだけで動作します。そのため、コンテキストスイッチが発生すると、これまでのプロセスの実行によって蓄積されたTLBは無用の長物となります。この問題はどのように解決できるでしょうか？

全てクリアする

文字通り、コンテキストスイッチが発生するとすべてが変わる方法です。実装は簡単ですが、コンテキストスイッチが頻繁に発生する場合、ほとんどの場合Missが発生し、TLBの意味がなくなる可能性があります。

各プロセスを識別する

アドレス空間識別子フィールドを追加して各プロセスを識別します。この方法では、コンテキストスイッチが発生してもTLBをクリアする必要がありません。

TLBの置換ポリシー

キャッシュにはいくつかの置換ポリシーがありますが、TLBにも置換ポリシーがいくつかあります。

最も簡単なものを見てみると、最近使用されたものを基に項目を置換するLRU（Least Recently Used）ポリシーがあります。