Sistem Operasi – 16 – Memory 4: Demand Paging Policy

Demand paging policy determine which pages should only be brought into memory if the executing process demands them. This article learn how this process happen and available algorithm to implement.

Read more: Sistem Operasi – 16 – Memory 4: Demand Paging Policy

Sumber Utama

Time seek	Note from CS162 Lecture 16: Memory 4: Demand Paging Policies
3:36	average memory access time
24:39	demand paging cost model
31:18	what factors lead to page-fault?
39:14	demand paging replacement policy
47:07	example of demand paging replacement policy: FIFO
51:48	example of demand paging replacement policy: MIN/LRU
56:45	example when LRU has bad performance as bad as FIFO, but MIN do much better
58:13	menambah ukuran RAM tidak selalu memperbaiki page-fault rate
1:00:47	approximating LRU: clock algorithm
1:18:42	approximating LRU: second-chance list algorithm
1:27:00	approximating LRU: Reverse page mapping (aka coremap)
1:28:26	summary

Poin-poin Penting

• demand page costing model (effective access time) hanya memperhatikan miss rate, dan mengabaikan conflict miss.
  • effective access time → EAT = hit time + miss rate * miss penalty
  • desain cache pada page table menghasilkan fully-associative cache, dikarenakan semua alamat pada physical memory, dapat dialamati pada page table, sehingga conflict miss bisa diabaikan.
• penyebab page-fault yang bisa ditangani → compulsory misses, dan policy misses.
  • policy misses lebih dominan
• demand-paging policy terbaik adalah MIN, yaitu mencari mana page yang di masa depan, paling lama tidak dipakai-nya.
  • seandainya kita dapat mengetahui masa depan, lalu melihat jika proses A, dimana sudah di-load ke physical memory sebuah page x, dan sekarang tidak dipakai, dan akan dipakai lagi setelah x 300 cycle kedepan, sedangkan page y di proses B, baru akan dipakai lagi setelah 500 cycle kedepan, maka page y akan di-remove, supaya ada tempat buat page z oleh process C.
  • LRU (least recently used) adalah pendekatan pada MIN, sebab tidak ada yang bisa mengetahui masa depan, dan LRU adalah pendekatan untuk mengetahui masa depan menggunakan data masa lalu.
    • LRU, adalah metode menghapus page yang paling lama tidak dipakai. jika suatu page itu paling lama tidak dipakai, ada kemungkinan di masa depan juga lama tidak dipakai, tapi kan ini tidak ada jaminan.
    • bukti bahwa LRU tidak sama dengan MIN, dan hanya merupakan pendekatan saja terhadap MIN, ada pada video menit ke 56:45, dimana ada kasus page retrieve A B C D A B C D A B C D
      • pada contoh ini, umur A pada siklus pertama sama denga B, C, dan D, sehingga FIFO dan LRU memiliki value yang sama, menghasilkan page-fault di setiap demand-paging di siklus kedua dan siklus berikutnya.

---

Latar Belakang

dengan asumsi memory access time 200ns (contohnya cache L2 memiliki tipikal access time 500ns), dan acess time ke disc 8ms (tipikal HDD 5-10ms), dan disyaratkan 10% slow-down karena page-fault, maka hanya boleh 1 page-fault dalam 400,000 memory access → extraordinary important to have no page-fault. Untuk mencegah terjadinya page-fault, dilakukan hal-hal berikut:

• yang sudah ada di physical memory (RAM), jangan sembarangan membuang. ada demand-paging policy, misalnya LRU (least recently used).
• loading page dengan baik, sehingga yg akan diakses processor ada di RAM. salah satunya dengan pre-fecthing.

Demand paging cost model

• dikarenakan demand paging itu menyerupai cache, maka cost model dapat dihitung dengan pendekatan average access time (lebih tepatnya effective access time):
  • EAT = hit rate * hit time + miss rate * miss time
  • EAT = hit time + miss rate * miss penalty
• contoh:
  • memory access time = 200 ns
  • average page-fault service time = 8ms
  • jika p = peluang untuk terjadi cache miss, maka 1-p = peluang cache hit
  • maka EAT dapat dihitung sebagai berikut:
    • EAT = 200ns + p * 8ms
    • EAT = 200ns + p * 8,000,000ns
• contoh, dalam bentuk lain:
  • jika 1 dari 1000 memory access menyebabkan page-fault, maka EAT = 8.2µs
  • ini sama dengan menurukan performa 40x (bayangkan, dibandingkan dengan full 100% hit rate, kejadian 1 page fault dari 1000 access, itu menurukan kecepatan total sampai 40x → pretty bad).
• contoh, dalam bentuk lain lagi:
  • dibutuhkan slow down hanya 10% atau kurang.
  • EAT < 200ns * 1.1 → p < 2.5*10^-6
  • 1 page-fault dalam 400,000

Apa saja penyebab page-fault?

• compulsory misses: page belum ada di memory sebelumnya, misalnya program baru saja start.
  • solusi:
    • prefetching: load page ke RAM sebelum dibutuhkan. butuh prediksi mana page yang kira-kira dibutuhkan. gimana caranya prediksi ini??
• capasity misses, solusinya:
  • naikkan kapasitas RAM (not so elegant)
  • jika ada beberapa proses dalam RAM, sesuaikan persentase alokasi memory untuk setiap process, sehingga mendapatkan overall performance yg lebih baik.
• conflict misses, technically does not exists, karena virtual memory ini fully-associative.
• policy misses, page ada di RAM, tapi dikeluarkan dari RAM secara prematur karena efek dari bad demand-paging policy.

Page replacement policy

Kelemahan LRU sebagai page replacement policy

1. membutuhkan update pada linked-list yg mengimplementasikan LRU. jika ada page-table yang diakses maka page ini akan menjadi least recently used page, maka harus dipindahkan ke header. untuk memindahkannya memang O(1), tetapi mencari dimana object yang harus dipindahkan itu O(n)
2. kita bisa menghindari linked-list backed LRU, bisa menggunakan map dengan key berupa timestamp, tapi untuk mencari siapa yg akan dikeluarkan dari cache, butuh sorting timestamp yang kompleksitinya n log(n).

Contoh demand paging policy: FIFO

Contoh deman paging policy: MIN/LRU

Contoh deman paging policy: clock algorithm

ini adalah pendekatan terhadap LRU. jadi ini adalah pendekatan terhadap pendekatan terhadap MIN. clock algorithm adalah: saat page fault, akan me-replace old page, tidak selalu oldest.