Memori Virtual

Setiap proses melihat memori sebagai deretan alamat yang dimulai dari nol, padahal DRAM fisik ditempati bersama oleh banyak proses sekaligus. Memori virtual (virtual memory) menjembatani kedua pandangan itu, yaitu mekanisme penerjemahan alamat virtual menjadi alamat fisik yang dikerjakan perangkat keras bersama sistem operasi. Topik ini membahas page, page table beserta entrinya, peran TLB, dan simulasi penerjemahan alamat yang dapat dihitung ulang.

Page dan dua bentuk alamat#

Memori virtual membagi ruang alamat menjadi page, yaitu blok berukuran tetap yang umumnya 4 KiB, dan membagi DRAM fisik menjadi frame dengan ukuran yang sama. Alamat virtual pun terbagi dua bagian, yaitu nomor page virtual dan offset di dalam page, dengan jumlah bit offset sebesar $\log_2(\text{ukuran page})$. Offset tidak pernah diterjemahkan, sehingga byte ke-$n$ dalam sebuah page virtual selalu jatuh pada byte ke-$n$ dalam frame tujuannya.

Ukuran page yang kecil membuat pemetaan lebih halus tetapi membuat page table membengkak, sedangkan ukuran yang besar boros bila page hanya terisi sebagian. Nilai 4 KiB menjadi kompromi yang paling umum, dan beberapa arsitektur menambahkan page besar untuk keperluan khusus. Contoh pada topik ini memakai page 256 byte agar angkanya ringkas, dengan cara pembagian bit yang sama persis.

Page table dan PTE#

Pemetaan dari page virtual ke frame disimpan dalam page table, yaitu tabel per proses yang diindeks oleh nomor page virtual. Setiap entri disebut PTE (page table entry) dan memuat setidaknya nomor frame tujuan beserta bit valid, ditambah sejumlah bit izin seperti baca, tulis, dan eksekusi. Bit valid menyatakan apakah page itu sedang berada di memori utama, sedangkan bit izin menentukan akses yang diizinkan. Diagram berikut merangkum alur penerjemahan untuk contoh dengan page 256 byte.

Diagram di atas memperlihatkan dua jalur menuju nomor frame. Nomor page virtual dijadikan indeks untuk membaca satu PTE pada page table, nomor frame dari PTE digabungkan dengan offset yang asli, dan hasilnya adalah alamat fisik. Penerjemahan seperti ini terjadi pada hampir setiap akses memori, sehingga kecepatannya menentukan kecepatan seluruh program.

TLB sebagai cache terjemahan#

Membaca page table pada setiap akses memori praktis menggandakan jumlah akses, sehingga prosesor menyimpan terjemahan terkini dalam TLB. TLB adalah cache kecil yang fully associative atau berasosiatif tinggi, dan isinya berupa pasangan nomor page virtual dengan nomor frame. TLB hit menyelesaikan penerjemahan tanpa menyentuh page table, sedangkan TLB miss memaksa pembacaan PTE sebelum akses dapat dilanjutkan.

Lokalitas temporal dan spasial membuat TLB bekerja sangat efektif, karena page yang baru dipakai cenderung dipakai lagi dan page bertetangga diakses berurutan. Tingkat hit TLB pada beban nyata biasanya di atas 99 persen, sehingga biaya penerjemahan menjadi nyaris tak terlihat. Struktur ini sekaligus memperlihatkan kegunaan desain fully associative, yaitu diterapkan pada cache kecil dengan sedikit isi.

Perhatikan bahwa TLB menyimpan terjemahan, bukan data program. Isinya jauh lebih kecil daripada cache data, tetapi setiap entrinya melayani seluruh page, yaitu ribuan byte sekaligus. Pergantian proses pun mengharuskan TLB dibersihkan atau diberi tanda milik proses, karena peta alamat setiap proses berbeda.

Simulasi penerjemahan alamat#

Skrip berikut memelihara page table kecil dengan page 256 byte dan mengeksekusi enam akses virtual. TLB dimulai dalam keadaan kosong, terjemahan baru masuk ke TLB setelah dibaca dari page table, dan PTE dengan bit valid 0 memicu pesan page fault. Hasilnya mencakup TLB miss, TLB hit, dan page fault dalam satu rangkaian akses.

# Penerjemahan alamat virtual menjadi alamat fisik pada sistem mini.
# Page berukuran 256 byte, ruang virtual memuat 8 page, dan
# page table memetakan sebagian page virtual ke frame fisik.

UKURAN_PAGE = 256
BIT_OFFSET = UKURAN_PAGE.bit_length() - 1  # 8 bit untuk offset

# page table: nomor page virtual -> (nomor frame, bit valid)
page_table = {
    0: (2, 1),
    1: (4, 1),
    2: (0, 1),
    3: (5, 1),
    4: (0, 0),  # bit valid 0: belum dipetakan, siap memicu page fault
    5: (3, 1),
}

def terjemahkan(tlb, alamat_virtual):
    """Kembalikan baris keterangan hasil satu penerjemahan."""
    vpn = alamat_virtual >> BIT_OFFSET
    offset = alamat_virtual & (UKURAN_PAGE - 1)
    if vpn in tlb:
        fisik = (tlb[vpn] << BIT_OFFSET) | offset
        return f"0x{alamat_virtual:04X} -> TLB hit  -> 0x{fisik:03X}"
    frame, valid = page_table[vpn]
    if not valid:
        return f"0x{alamat_virtual:04X} -> page fault (page {vpn} belum dipetakan)"
    tlb[vpn] = frame  # terjemahan baru masuk ke TLB
    fisik = (frame << BIT_OFFSET) | offset
    return f"0x{alamat_virtual:04X} -> TLB miss -> 0x{fisik:03X}"

tlb = {}  # TLB dimulai dari keadaan kosong
for alamat in (0x00FA, 0x0123, 0x00FA, 0x02C4, 0x0410, 0x05B7):
    print(terjemahkan(tlb, alamat))

0x00FA -> TLB miss -> 0x2FA
0x0123 -> TLB miss -> 0x423
0x00FA -> TLB hit  -> 0x2FA
0x02C4 -> TLB miss -> 0x0C4
0x0410 -> page fault (page 4 belum dipetakan)
0x05B7 -> TLB miss -> 0x3B7

Enam baris keluaran itu mencakup seluruh kemungkinan. Dua akses pertama miss dan mengisi TLB, kemudian akses ketiga menemukan page 0 yang sama sehingga menjadi TLB hit dan menghasilkan alamat fisik 0x2FA yang persis sama. Akses ke 0x0410 jatuh pada page 4 yang bit validnya 0, sehingga tidak ada frame yang dapat dicantumkan. Akses terakhir menunjukkan bahwa page 5 dipetakan ke frame 3, karena pemetaan ditentukan oleh isi page table dan bukan oleh urutan page virtual.

Page fault secara singkat#

PTE dengan bit valid 0 berarti page yang diminta tidak sedang berada di memori utama. Perangkat keras menanggapi kondisi itu dengan page fault, yaitu pengecualian yang menyerahkan kendali kepada sistem operasi. Penangan page fault memeriksa keabsahan akses, memuat page yang diminta dari disk ke frame kosong, memperbarui PTE, lalu mengulangi instruksi yang tersendat. Mekanisme pemuatan dan penggantiannya dibahas lebih lanjut pada jalur sistem operasi.

Bila memori penuh, satu page yang berada di memori harus dikorbankan, dan sistem operasi memilih korban dengan aturan yang mirip dengan penggantian cache, misalnya page yang paling lama tidak dipakai. Oleh karena itu, page fault bukan error program, melainkan bagian normal dari mekanisme yang disebut demand paging, yaitu memuat page hanya ketika pertama kali dibutuhkan. Meskipun normal, page fault yang terjadi terus-menerus membuat program melambat secara tajam, karena setiap kejadiannya melibatkan disk yang latensinya ratusan ribu kali lipat DRAM.

Kesalahan umum#

Tiga kekeliruan berikut paling sering muncul ketika penerjemahan alamat baru dipelajari.

1. Menukar page dan frame. Page milik ruang alamat virtual, sedangkan frame milik memori fisik, dan keduanya berukuran sama tetapi berbeda kedudukan. Perbaikannya adalah menyebut pemiliknya setiap kali salah satu istilah dipakai.
2. Menerjemahkan offset. Offset diteruskan apa adanya dari alamat virtual ke alamat fisik karena page dan frame berukuran sama. Perbaikannya adalah mengingat bahwa hanya nomor page yang berubah bentuk.
3. Mengira seluruh isi page table tersimpan di TLB. TLB hanya menyimpan terjemahan yang sering dipakai, sedangkan page table tetap menjadi sumber kebenarannya. Perbaikannya adalah memperlakukan TLB miss sebagai bagian normal, bukan sebagai kegagalan.

Ringkasan#

• Alamat virtual terbagi menjadi nomor page virtual dan offset, dan offset diteruskan tanpa perubahan ke alamat fisik.
• Page table memetakan page virtual ke frame melalui PTE yang memuat nomor frame, bit valid, dan bit izin.
• TLB menyimpan terjemahan terkini sehingga sebagian besar akses tidak perlu membaca page table.
• Bit valid 0 memicu page fault, dan sistem operasi memuat page yang diminta sebelum instruksi diulang.

Referensi#

• X86 Paging — OSDev Wiki — Dokumentasi mekanisme paging x86, mencakup format PTE, tingkatan page table, dan TLB.
• Computer Systems: A Programmer’s Perspective — Randal Bryant dan David O’Hallaron — Buku yang membahas memori virtual dan TLB dari sudut pandang pemrogram.