Sebuah page-table entry dapat berubah di memori ketika CPU lain masih menyimpan translasi alamat lama di translation lookaside buffer (TLB). Karena itu, memperbarui page table saja tidak selalu membuat mapping baru langsung berlaku pada setiap prosesor yang pernah menjalankan address space tersebut.

Sistem operasi menutup celah itu dengan invalidasi TLB. Ketika perubahan mapping dapat membuat translasi yang tersimpan menjadi tidak aman, prosesor yang mungkin masih menyimpan translasi tersebut harus menginvalidasinya sebelum kernel menganggap perubahan selesai secara global. Pada sistem multiprosesor, koordinasi invalidasi jarak jauh ini umum disebut TLB shootdown.

Mekanisme ini merupakan batas correctness, bukan sekadar optimasi cache. Translasi lama dapat menunjuk ke physical page yang sudah di-unmap, didaur ulang, diberi permission berbeda, atau digunakan kembali untuk mapping lain.

TLB terpisah dari page table

Translasi virtual memory pada dasarnya bersumber dari page table yang dikelola di memori, tetapi prosesor menghindari page-table walk untuk setiap memory reference. TLB menyimpan informasi translasi yang baru digunakan di dekat execution pipeline.

Cache tersebut menciptakan dua state yang berbeda:

page table di memori
        |
        | page-table walk
        v
translasi dalam TLB
        |
        v
memory access

Mengubah page-table entry memperbarui state pertama. Operasi itu sendiri tidak menjamin penghapusan langsung setiap entry yang cocok dari translation cache prosesor.

Arsitektur menyediakan mekanisme invalidasi eksplisit untuk kondisi ini. Instruksi dan cakupannya berbeda antararsitektur. Sistem operasi harus mengikuti aturan ordering dan invalidasi yang ditetapkan arsitektur, bukan menganggap store ke page table sebagai sinkronisasi yang memadai.

Translasi lama dapat bertahan setelah unmap

Bayangkan dua CPU menjalankan thread dari proses yang sama. CPU 0 dan CPU 1 sama-sama pernah mengakses virtual page V, sehingga keduanya dapat menyimpan translasi dari V ke physical page P.

CPU 0 TLB: V -> P
CPU 1 TLB: V -> P

page table: V -> P

CPU 0 kemudian masuk ke kernel dan menghapus mapping:

page table: V -> not present

CPU 1 mungkin masih memiliki V -> P di TLB. Jika arsitektur mengizinkan entry tersebut memenuhi akses berikutnya, CPU 1 masih dapat menggunakan P sampai entry diinvalidasi atau tergeser oleh mekanisme lain.

Risikonya meningkat jika kernel membuat P tersedia untuk dipakai kembali sebelum invalidasi remote selesai. Physical page itu dapat memperoleh fungsi berbeda sementara CPU 1 masih mempunyai translasi yang dapat menjangkaunya. Reklamasi yang benar karena itu harus mematuhi protokol invalidasi.

Perubahan permission menghadapi masalah serupa. Menghapus write permission dari page-table entry belum cukup jika prosesor lain masih dapat memakai translasi writable yang tersimpan. Invalidasi yang diwajibkan memastikan akses berikutnya diperiksa terhadap state mapping yang baru.

Invalidasi lokal tidak membersihkan TLB remote

Sebuah CPU dapat menginvalidasi translation entry miliknya sendiri dengan operasi spesifik arsitektur, tetapi CPU lain memiliki state translation cache terpisah. Satu prosesor tidak dapat menganggap invalidasi lokal telah mengubah TLB prosesor lain.

Urutan shootdown tipikal memiliki bentuk berikut:

CPU 0                         CPU 1

ubah page table
catat rentang invalidasi
kirim permintaan lintas CPU -> terima permintaan
                               invalidasi state TLB terkait
tunggu penyelesaian        <- kirim konfirmasi selesai
lanjutkan reklamasi

Ini merupakan urutan konseptual, bukan implementasi universal. Kernel dapat menggabungkan beberapa rentang, memakai tracking per-address-space, menunda pekerjaan ketika aturan mengizinkannya, atau memilih invalidasi lebih luas jika biayanya lebih rendah daripada banyak operasi sempit.

Properti pentingnya adalah penyelesaian: setiap CPU yang secara sah dapat menyimpan translasi lama yang tidak aman harus mencapai state ketika translasi itu tidak lagi dapat digunakan sebelum reklamasi atau perubahan protection yang bergantung padanya diteruskan.

Koordinasi lintas CPU menambah biaya skalabilitas

Invalidasi TLB lokal saja sudah mengganggu state translasi yang tersimpan. Remote shootdown menambahkan koordinasi antarprosesor. CPU pemrakarsa mungkin harus menentukan prosesor yang relevan, mengirim notifikasi antarprosesor, lalu menunggu invalidasi remote selesai.

Biayanya bergantung pada workload dan mesin. Nilainya berubah menurut arsitektur prosesor, implementasi kernel, jumlah CPU, penempatan address space, rentang invalidasi, dan banyaknya state translasi yang dibuang. Tidak ada satu nilai latensi yang berlaku untuk semua sistem.

Persoalan skalabilitas berasal dari sinkronisasi. Perubahan mapping yang membutuhkan tindakan pada banyak CPU dapat menghasilkan lebih banyak pekerjaan lintas CPU daripada perubahan yang terbatas pada satu prosesor. Aktivitas mmap, munmap, perubahan protection, allocator, atau reklamasi page yang sering dapat berinteraksi dengan overhead invalidasi TLB, tetapi dampak aktual harus diukur pada sistem target.

Invalidasi luas juga dapat membuang translasi yang tidak terkait dengan entry yang memicu operasi. Translasi tersebut kemudian mungkin membutuhkan page-table walk baru. Invalidasi sempit mempertahankan lebih banyak state TLB, tetapi dapat memerlukan lebih banyak operasi invalidasi. Kernel dan arsitektur menyediakan trade-off berbeda di antara pilihan ini.

Tracking CPU dapat membatasi target shootdown

Sebuah address space tidak selalu aktif pada semua CPU. Kernel dapat melacak prosesor yang sedang atau baru saja menjalankan address space tertentu dan memakai informasi tersebut untuk menghindari pengiriman pekerjaan invalidasi ke prosesor yang tidak mungkin memiliki translasi relevan.

Optimasi ini bergantung pada bookkeeping yang benar. Jika prosesor dapat mempertahankan translasi suatu address space setelah beralih darinya, kernel harus memperhitungkan kemungkinan tersebut sesuai arsitektur dan skema tagging address space.

Desain TLB bertag membuat kondisi ini lebih fleksibel. Identifier seperti x86 PCID atau Arm ASID memungkinkan translasi dari beberapa address space berada bersamaan tanpa complete TLB flush pada setiap context switch. Tag mengurangi invalidasi yang tidak perlu, tetapi tidak menghapus kebutuhan invalidasi ketika mapping yang diwakili tag valid berubah.

Pemakaian ulang tag juga memerlukan kontrol. Menetapkan kembali sebuah identifier ketika translasi lama dengan identifier tersebut masih dapat digunakan bisa membuat state lama terlihat sebagai bagian dari address space baru. Sistem operasi mengoordinasikan siklus hidup identifier dengan fasilitas invalidasi arsitektur.

Batching perubahan dapat mengurangi frekuensi sinkronisasi

Beberapa pembaruan page table terkadang dapat memakai satu fase invalidasi. Alih-alih memaksa sinkronisasi remote setelah setiap perubahan entry, kernel dapat mengumpulkan rentang terdampak dan menginvalidasinya bersama ketika aturan correctness mengizinkannya.

Batching tidak menghapus persyaratan ordering. Physical page atau permission lama tidak dapat dianggap aman untuk dihentikan sebelum seluruh invalidasi yang diperlukan untuk perubahan tersebut selesai.

Manfaatnya adalah lebih sedikit peristiwa koordinasi. Hal ini relevan pada operasi yang mengubah banyak mapping, seperti membongkar region besar atau mengubah protection pada banyak page. Kebijakan batching merupakan pilihan implementasi sistem operasi dan dapat berubah secara independen dari aturan arsitektural prosesor.

Huge page mengubah granularitas invalidasi

Sebuah TLB entry dapat mewakili area yang lebih besar daripada base-size page. Mapping huge page mencakup rentang virtual lebih besar, sehingga penggantian, pemecahan, atau perubahan mapping tersebut memengaruhi state translasi pada granularitas berbeda.

Sistem operasi harus menginvalidasi setiap translasi tersimpan yang dapat merepresentasikan mapping lama. Bergantung pada arsitektur dan operasi, tindakan itu dapat memerlukan invalidasi rentang, invalidasi entry pada beberapa ukuran page, atau operasi context-level yang lebih luas.

Kondisi ini kembali menunjukkan bahwa struktur page table dan state TLB bukan hal yang identik. Edit page table yang terlihat oleh software dapat berkaitan dengan translasi hardware yang tersimpan dengan representasi dan granularitas spesifik arsitektur.

Shootdown menjaga batas antara perubahan mapping dan penggunaan ulang

Kendala utamanya bersifat temporal. Memori page table dapat sudah berisi state baru sebelum setiap prosesor berhenti menggunakan state lama.

Urutan aman menetapkan batas antara kedua fase tersebut:

publikasikan state page table baru
        |
ordering yang diwajibkan
        |
invalidasi translasi relevan
        |
konfirmasi CPU terkait selesai menginvalidasi
        |
pakai ulang page atau andalkan permission baru

Detailnya berbeda antar keluarga prosesor dan sistem operasi, tetapi invariant-nya tetap sama: translasi lama yang dapat melanggar state mapping baru tidak boleh tetap dapat digunakan setelah kernel mulai bergantung pada state tersebut.

Invariant inilah yang mengubah pembaruan page table dari memory write lokal menjadi peristiwa sinkronisasi multiprosesor.

CPU Manajemen Memori TLB Memori Virtual Sistem Operasi