IF Notes

Memori Virtual, Demand Paging, dan Penggantian Page

8 min read

Back to IF2130 Sistem Operasi

Topic

Questions/Cues

  • Apa itu Memori Virtual & Keuntungannya?
  • Bagaimana Ruang Alamat Virtual didesain?
  • Apa itu Demand Paging?
  • Bagaimana Page Fault terjadi & ditangani?
  • Langkah-langkah penanganan Page Fault?
  • Apa itu Pure Demand Paging?
  • Bagaimana Kinerja Demand Paging?
  • Apa itu Copy-on-Write (COW)?
  • Kapan Penggantian Page (Page Replacement) diperlukan?
  • Peran Modify Bit (Dirty Bit)?
  • Algoritma: FIFO?
  • Masalah: Belady’s Anomaly?
  • Algoritma: Optimal (OPT)?
  • Algoritma: LRU (Least Recently Used)?
  • Mengapa perlu Algoritma Aproksimasi LRU?
  • Contoh Aproksimasi LRU? (Reference Bit, Second-Chance)
  • Aproksimasi LRU Lanjutan? (Enhanced Second-Chance)
  • Algoritma Berbasis Hitungan & Buffering?

Swapping

  • Swapping itu proses mindahin seluruh program (atau sebagian) dari memori utama (RAM) ke penyimpanan cadangan (biasanya disk cepat), terus nanti dibawa balik lagi ke RAM kalau mau dijalanin lagi. Ini bikin seolah-olah RAM kita lebih besar, jadi bisa ngejalanin lebih banyak program. Program yang lagi nganggur bisa di-swap out (dikeluarin ke disk) biar RAM-nya bisa dipakai program yang lagi aktif. Nanti kalau program nganggur itu aktif lagi, dia di-swap in (dimasukin lagi ke RAM).
  • Swapping seluruh proses itu sekarang jarang dipakai karena lama. Kebanyakan sistem sekarang pakai variasi swapping dengan paging, artinya yang dipindahin itu page-page-nya, bukan seluruh proses.

Konsep Memori Virtual

Memori Virtual adalah sebuah teknik yang memisahkan antara memori logis (yang dilihat pengguna/program) dengan memori fisik (RAM asli). Ini menciptakan ilusi bagi program bahwa ia memiliki ruang memori yang sangat besar dan berdekatan, padahal kenyataannya data bisa tersebar di RAM fisik atau bahkan disimpan sementara di disk.

Keuntungan Utama:

  • Program bisa lebih besar dari RAM fisik: Hanya bagian program yang sedang aktif yang perlu ada di memori.
  • Peningkatan Utilisasi & Multiprogramming: Lebih banyak program bisa berjalan bersamaan karena setiap program hanya memakan sedikit RAM fisik.
  • Pembuatan Proses Lebih Cepat: Teknik seperti Copy-on-Write memungkinkan proses baru dibuat dengan cepat tanpa menyalin seluruh memori induknya.
  • Memungkinkan Berbagi Memori: Proses-proses dapat berbagi library atau data dengan mudah.

Umumnya, ruang alamat virtual didesain agar fleksibel. Bagian stack (untuk variabel fungsi) dimulai dari alamat teratas dan “tumbuh” ke bawah, sementara bagian heap (untuk alokasi dinamis) dimulai dari bawah dan “tumbuh” ke atas. Ruang kosong besar di antara keduanya menjadi hole yang tidak menggunakan RAM fisik sampai benar-benar dibutuhkan.

Memori virtual ini biasanya diimplementasiin pakai teknik demand paging.

Demand Paging & Page Fault

Demand Paging

  • Ini adalah metode implementasi Memori Virtual yang paling umum. Prinsipnya adalah “kemalasan”: sebuah page dari program tidak akan dimuat dari disk ke RAM sampai ia benar-benar dibutuhkan (“on demand”).
  • Mekanisme ini menggunakan bit valid-invalid pada page table. valid berarti page ada di RAM, invalid berarti tidak ada di RAM (masih di disk).
  • Kalau program mau akses page yang bitnya 0, terjadilah PAGE FAULT.
  • Jika ada referensi ke page, referensi tersebut akan menghasilkan trap ke OS  page fault. OS memeriksa tabel lain untuk memutuskan:
    • Referensi invalid abort.
    • Memang sedang tidak ada di memori.

** Langkah Penanganan Page Fault **

  1. Trap ke OS: Kendali langsung berpindah dari program ke sistem operasi.
  2. Simpan Konteks: OS menyimpan register dan status proses saat ini.
  3. Validasi: OS memeriksa apakah akses tersebut legal. Jika tidak (misalnya, akses ke alamat di luar jangkauan), proses akan dihentikan.
  4. Cari Frame Kosong: OS mencari frame kosong di RAM dari daftar frame bebas (free-frame list).
  5. Jika Frame Penuh: Jika tidak ada frame kosong, OS harus menjalankan algoritma penggantian page (dibahas di bawah) untuk memilih frame “korban”.
  6. Baca dari Disk: OS menjadwalkan operasi I/O untuk membaca page yang diminta dari backing store (disk) ke frame yang telah disiapkan.
  7. Update Page Table: Setelah I/O selesai, OS memperbarui page table proses, menandai page tersebut sebagai valid dan mencatat nomor frame-nya.
  8. Lanjutkan Proses: OS mengembalikan kendali ke proses, dan instruksi yang menyebabkan fault akan diulang kembali—kali ini berhasil.

Dalam kasus ekstrem, eksekusi proses dapat dimulai tanpa page di memori (pure demand paging). Proses akan langsung mengalami page fault untuk instruksi pertama, dan page-page lainnya akan dibawa ke memori sesuai kebutuhan.

Kinerja sangat dipengaruhi oleh tingkat page fault (p). Waktu akses efektif (EAT) dihitung sebagai EAT = (1 – p) × (waktu akses memori) + p × (waktu penanganan page fault). Karena waktu penanganan page fault sangat lama (melibatkan akses disk), nilai p harus dijaga sangat rendah agar sistem tidak terasa lambat.

Pembuatan Proses: Copy-on-Write (COW) Teknik optimasi saat membuat proses baru (misalnya dengan fork()). Awalnya, proses induk dan anak berbagi page yang sama (ditandai read-only). Baru ketika salah satu dari mereka mencoba menulis ke sebuah page, salinan dari page tersebut dibuat khusus untuk proses yang menulis. Ini membuat fork() sangat cepat.

Penggantian Page (Page Replacement)

  • **Kapan Diperlukan?: ** Ketika terjadi page fault tetapi tidak ada frame yang kosong di memori. OS harus memilih salah satu page yang sudah ada di memori untuk diusir (evict) agar bisa menyediakan ruang bagi page yang baru.
  • Peran Modify Bit (Dirty Bit): Untuk optimasi, setiap entri page table memiliki modify bit.
    • Jika sebuah page dimodifikasi (ditulis), hardware akan menyetel modify bit-nya menjadi 1 (dirty).
    • Saat penggantian, jika page korban dirty, ia harus ditulis kembali ke disk
    • Jika tidak dirty (clean), ia bisa langsung ditimpa tanpa perlu I/O tulis, ini sangat menghemat waktu.
  • Algoritma-Algoritma Penggantian Page:
    • FIFO (First-In, First-Out): Mengganti page yang paling lama berada di memori. Implementasinya mudah (menggunakan antrean), tetapi performanya seringkali buruk.
    • Belady’s Anomaly: Masalah aneh pada FIFO di mana menambah jumlah frame yang tersedia justru dapat meningkatkan jumlah page fault.
    • Optimal (OPT atau MIN): Mengganti page yang baru akan digunakan lagi paling lama di masa depan. Ini adalah algoritma dengan performa terbaik secara teoretis, tetapi tidak dapat diimplementasikan karena membutuhkan pengetahuan tentang masa depan.
    • LRU (Least Recently Used): Mengganti page yang paling lama tidak digunakan. Merupakan pendekatan yang sangat baik dan tidak menderita Belady’s Anomaly. Implementasi murninya mahal karena memerlukan hardware khusus (seperti timestamp atau stack) untuk melacak setiap akses.
  • Algoritma Aproksimasi LRU: Karena LRU murni mahal, digunakan algoritma perkiraan.
    • Reference Bit: Setiap page memiliki 1 bit referensi. Hardware menyetelnya ke 1 setiap kali page diakses. OS secara periodik mengosongkannya. Algoritma akan mencari page dengan bit referensi 0 sebagai korban.
    • Second-Chance (Algoritma Jam): Pada dasarnya FIFO, tetapi sebelum mengusir page, ia memeriksa reference bit. Jika 1, page diberi “kesempatan kedua”: bitnya di-reset ke 0 dan ia dipindahkan ke belakang antrean. Jika 0, ia langsung diganti.
    • Enhanced Second-Chance: Menggunakan kombinasi (reference bit, modify bit) untuk mengklasifikasikan page ke dalam 4 kelas prioritas. Korban dipilih dari kelas dengan prioritas terendah (misal, kelas (0,0): tidak baru diakses & tidak dimodifikasi).
  • Algoritma Lain:
    • Counting Algorithms: Mencatat jumlah akses ke setiap page (misalnya LFU - Least Frequently Used).
    • Page-Buffering Algorithms: Selalu menjaga sejumlah kecil frame tetap bebas. Saat fault terjadi, page baru langsung dimuat ke frame bebas, sementara proses pemilihan dan pengusiran korban dilakukan di latar belakang.

Summary

Memori Virtual memisahkan pandangan logis program dari RAM fisik, memungkinkan program berjalan meski ukurannya lebih besar dari memori, yang diimplementasikan melalui Demand Paging. Mekanisme ini hanya memuat page ke RAM saat terjadi Page Fault. Jika RAM penuh, OS harus melakukan Penggantian Page dengan memilih page korban menggunakan berbagai algoritma. Algoritma seperti FIFO sederhana namun tidak efisien, OPT ideal namun tidak mungkin, sementara LRU sangat baik tetapi mahal, sehingga sistem modern sering menggunakan algoritma aproksimasi LRU (seperti Second-Chance) yang menyeimbangkan antara kinerja dan kompleksitas implementasi, dengan Modify Bit sebagai optimasi krusial untuk mengurangi operasi I/O.

Graph View

Backlinks