VIRTUAL MEMORY (Memori Virtual)

 

 A. Background (Latar Belakang)

• Virtual Memori= pemisahan memori fisik dengan memori logis
  
• Tujuan utama dari virtual memori ini yaitu membuat kapasitas memori lebih besar, dengan meminimalisir I/O, meminimalisir penggunaan memori fisik, memperbanyak jumlah user, dan meningkatkan respon
• Dalam penerapannya, menggunakan teknik: demand paging & demand segmentation
• Perbedaan memori virtual dengan memori fisik
  
• Ruang Alamat Virtual/Virtual-address Space (VAS)
  • Ruangan antara stack dan heap disebut lubang
  • Stack pada alamat logis akan mulai dari max., lalu bertumbuh ke bawah sedangkan heap akan tumbuh ke atas. Ruangan ini akan digunakan secara maksimal, sehingga memori fisik tidak perlu digunakan. Lalu sistem akan membagikan atau memetakan ke alamat virtual.
    

B. Demand Paging (Halaman Permintaan)

• Perpaduan antara swapping (menukar) dan paging (menyimpan ke memori) artinya page yang dibawa atau dikirim ke memori adalah page yang dibutuhkan saja.
• Keuntungan: meminimalisir I/O; meminimalisir penggunaan memori; respon cepat; lebih banyak user yang dapat dijangkau.
• Teknik –> Lazy swapper: jangan pernah swap page ke memori jika betul-betul diperlukan
  –> Pager: swapper (melakukan manipulasi seluruh proses) yang berhubungan dengan page.
• Pager hanya berfungsi membawa pages ke memori. Untuk menerapkan demand paging, maka diperlukan fungsionalitas MMU baru, supaya bisa mendeteksi dan memilih page untuk dibawa ke memori.
• Valid-Invalid Bit= hardware yang diperlukan untuk mengetahui bahwa page sudah berada di memori atau belum.
  • v: page ada di memori
  • i: page tidak ada di memori
  • page fault: jika page-nya i atau invalid, lalu page akan ditrap oleh SO
  • Cara menangani Page fault:
    • Saat page sedang ditrap oleh SO, SO akan melihat tabel lain untuk menentukan valid-invalid.
    • Jika page tersebut valid, maka akan diswapping ke free frame di memori
    • Lalu program ulang tabel pages supaya status page tersebut bertanda “v” yang artinya sudah berada di memori
    • Restart instruksi
      

• Komponen hardware yang dibuthkan untuk Demand Paging:
  • Tabel Page (valid-invalid bit)
  • Memori sekunder (untuk melakukan swapping dan menjadi tempat penampungan memori sementara)
  • Instruksi restart
• Kegiatan utama:
  • Merespon gangguan yang terjadi
  • Membaca page yang akan diswapping ke memori
  • Restart proses
• Nilai Page Fault –> 01
  • Tidak ada page fault –> p = 0
  • Seluruh referensi adalah fault –> p = 1
• Effective Access Time (EAT)
  EAT = (1 – p) x akses memori + p (page fault overhead + swap page out + swap page in)
  • Ex: akses memori: 100 nano detik
    Rata-rata page fault: 4 ms
    EAT      = (1 – p) x 100 + p (4.000.000)
    = 100 – 100p + 4.000.000p
  •                      = 100 + p x 3.999.900
  • Artinya, jika terdapat 1 dari 1000 akses menyebabkan page fault, maka EAT-nya
    adalah: p = 1 : 1000 = 0,001
    EAT      = 100 + 0,001 x 3.999.900
    = 4,1 mikro detik

 

C. Copy-on-Write (COW)

• Teknik yang efisien dalam mengsalin karena hanya page yang dimodifikasi yang disalin.
• Pada awalnya, terdapat beberapa proses yang berbagi pada page yang sama, lalu salah satu proses memodifikasi page tersebut, maka hanya page tersebut yang akan disalin sedangkan page yang lain tidak akan disalin. Lalu page yang dimodifikasi tsb dialokasikan ke free frame.
• Menggunakan teknik zero-fill-on-demand pages
• Jika tidak ada free frame, maka menggunakan page replacement, artinya keluarkan page yang sedang tidak digunakan, lalu isi page tersebut.

 

D. Page Replacement (Penggantian Halaman)

• Proses:
  • Setelah proses memodifikasi page, maka akan terbentuk salinan page dari page yang dimodifikasi tersebut, lalu pindahkan dulu page salinan tersebut pada disk.
  • Lalu cari free frame: jika ada, maka gunakan; jika tidak ada, maka gunakan metode algoritma page replacement untuk mencari frame yang tidak terpakai untuk dikorbankan.
  • Swapping page salinan ke free frame tersebut, lalu isi/tulis, serta update tabel page dan tabel frame
  • Restart instruksi
  • Keuntungan: mengurangi alokasi berlebihan yang terjadi karena layanan page fault, meluangkan lebih banyak kapasitas pada memori virtual
  • Ada dua algoritma yang perlu diperhatikan pada page replacement yaitu frame dan page:
    –> page: nilai page fault serendah mungkin
  • –> frame: frame mana yang harus digantikan, banyaknya frame yang digunakan dalam satu proses
• Algoritma Page Replacement:
  1. Algoritma First-In-First-Out (FIFO)
     • Page yang paling lama tinggal di frame atau page yang dialokasikan lebih awal menjadi page yang di-replace.
     • Anomali Belady: lebih banyak frame maka nilai page fault-nya lebih besar
       
  2. Algoritma Optimal
     • Page yang tidak akan digunakan dalam jangka waktu yang lama akan di-replace.
     • Algoritma ini memerlukan analisis yang cukup sulit karena memerlukan beberapa aspek yang perlu dipertimbangkan untuk me-replace suatu page
     • Algoritma ini memungkinkan untuk mempunyai nilai page fault terendah
     • Algoritma ini digunakan untuk menunjukkan seberapa baik algoritma yang dilakukan oleh setiap individu
  3. Algoritma Least Recently Used (LRU)
     • Page yang paling lama tidak di-replace atau bukan baru saja digunakan/di-replace akan di-replace
       
     • LRU lebih baik dari FIFO lebih buruk dari Optimal
     • Gabungan dari FIFO dengan Optimal
     • Cara pengimplementasian LRU:
       • Dengan Counter: berdasarkan waktu pada entry page, memerlukan pencarian pada tabel
       • Dengan Stack: suatu page yang direferensi di pindah ke atas, tidak menggunakan pencarian, memerlukan biaya yang besar
  4. Algoritma Second Chance
     • FIFO + bit referensi dari hardware
     • Menggunakan clock replacement
     • Page akan di-replace jika bit referensi-nya 0, jika bit referensi-nya 1, maka atur supaya bit referensi 0, lalu tinggalkan page di memori, lalu di-replace
     • Kondisi (referensi, modifikasi)
       • (0,0): pas untuk di-replace
       • (0,1): tidak baru digunakan, tetapi dimodifikasi
       • (1,0): baru digunakan, tetapi tidak dimodifikasi
       • (1,1): baru digunakan dan baru dimodifikasi

 

E. Allocation of Frames (Alokasi Frame)

• Tujuan: mengorganisir pemakaian frame pada setiap proses agar setiap proses dapat berjalan dengan efektif, misalnya setiap proses membutuhkan minimal frame agar proses dapat berjalan.
• Skema utama alokasi frame:
  1. Alokasi Fix (Fixed Allocation)
     • Alokasi Sama (Equal Allocation): pembagian frame pada setiap proses sama rata, misal –> terdapat 200 frame dan 10 proses, maka masing-masing proses mendapatkan 20 frame
     • Alokasi Proporsional (Proportional Allocation): pembagian proses berdasarkan ukuran masing-masing proses. Misal:
       si1 (ukuran proses p1) = 20   ;   si2 = 180
       S (jumlah semua si) = 20 + 180 = 200
       m (total frame)= 100
       a1 (alokasi p1) = si1/S x m = 20/200×100 = 10   ;   a2 = 180/200×100=90
  2. Alokasi Prioritas (Priority Allocation)
     • Menggunakan alokasi proporsional, tetapi lebih sering menggunakan prioritas proses dibandingkan ukuran proses
• Alokasi Global & Local
  1. Alokasi Global: suatu proses dapat memilih frame dari proses lain untuk di-replace
  2. Alokasi Lokal: suatu proses hanya dapat memilih frame dari proses dirinya sendiri untuk di-replace

 

F. Thrashing (Labrakan)

• Trashing = proses melakukan paging yang sangat tinggi dibandingkan dengan swap in/out (eksekusi) dikarenakan proses tidak cukup memiliki page sehingga menyebabkan page fault.
• Trashing juga dapat terjadi karena ukuran dari alokasi lokal lebih besar dibandingkan total ukuran memori
• Akibat: kerja CPU rendah, SO akan merespon untuk meningkatkan multiprogramming, sistem ketambahan proses-proses lain
• Working-set model
  • Δ= working set/nomor fix dari referensi page
  • WSSi (wroing set of process Pi) = total nomor referensi page
  • Δ terlalu kecil = tidak dapat menjangkau seluruh lokasi
  • Δ terlalu besar = menjangkau beberapa lokasi
  • Δ tak terbatas = menjangkau seluruh program
  • D = jumlah WSSi/total demand frames
  • D > m = thrashing, maka harus ditunda atau swap proses

 

G. Memory-Mapped Files (File Pemetaan Memori)

• File I/O sudah seperti memori akses yang rutin dengan memecahkan blok disk ke memori page.
• Menggunakan teknik demand paging
• Memory Mapped Files lebih sederhana dan cepat dibandingkan COW. Selain itu, Memory Mapped Files dapat dibaca dan ditulis, serta dishare, sedangkan COW hanya bisa dibaca dan ditulis, tidak dapat di-share

 

H. Allocating Kernel Memory (Alokasi Memori Kernel)

• Sistem buddy: alokasi memori dari ukuran pas dari fisik page
• Memori menggunakan 2 kekuatan allocator dalam pengalokasian, misal 256KB tersedia, kernel meminta 21KB. Lalu dibagi dua, dengan masing-masing 128KB. Setelah itu, salah satu dari kedua tersebut dibagi dua lagi menjadi masing-masing 64KB, lalu salah satu dibagi lagi menjadi 32KB
• Slab Allocator
  • Cache terdiri dari 1 atau lebih slab, lalu diisi oleh objek atau data struktur
  • Slab free: cache diciptakan, atau tandanya slab kosong
  • Full: semua slab sedang digunakan
  • Partial (sebagian): ada yang sudah digunakan dan ada yang kosong
  • Saat struktur data tersimpan, status objek digunakan
  • Jika objek di suatu slab penuh, maka objek yang lain akan dialokasikan ke slab yang kosong. Jika tidak ada slab yang kosong, maka slab baru yang akan dialokasikan.

 

I. Other Considerations (Pertimbangan Lainnya)

• Prepaging
  • Menyiapkan page yang dibutuhkan sebelum direferensi untuk mengurangi lonjakan nilai dari page faults
  • Ada resiko page yang sudah disiapkan tidak dipakai sehingga I/O dan memori akan terbuang sia-sia.
  • s: page yang disiapkan, a: page yang terpakai
  • s (1-a), if a near zero, maka kehilangan prepaging
• Page size
  • Hal-hal yang perlu diperhatikan: fragmentasi, I/O overhead, ukuran tabel page, lokalitas, resolusi, nomor dari page faults, ukuran dan efektivitas TLB
  • Selalu “²“ sekitar 4096 byte – 4.194.304 byte
• Jangkauan TLB
  • TLB Reach = ukuran TLB x ukuran page
  • Jika tidak ada lonjakan nilai page faults, worked set disimpan di TLB
  • Ukuran page perlu diperhatikan karena tidak semua apk memerlukan kapasitas yang besar, jika ukuran page-nya terlalu besar maka akan terjadi lonjakan fragmentasi
• I/O interlock
  • Beberapa page perlu di-lock supaya tidak terkena swap saat proses lain sedang berjalan

 

J. Operating-System Examples (Contoh Sistem Operasi)

• Windows
  • Teknik demand paging dengan pengelompokkan
  • Terdapat work set minimum dan maksimum
  • Pemangkasan work set dilakukan untuk mengembalikan jumlah memori bebas karena proses telah melebihi batas minimum page
• Solaris
  • Untuk menetapkan proses yang salah, free page perlu dipertahankan, istilah di page scanner:
    • Lotsfree: menunjukkan memori bebas menuju page start
    • Desfree: paging ditingkatkan
    • Minfree: swap
    • Paging to pageout
    • Pageout memakai algoritma jam yang dimodifikasi
    • Scanrate: kecepatan pemindaian
    • Menggunakan paging prioritas