Virtual Memory

*Session 21 & Session 22

 

A)   Terminologi Virtual Memory

B)   Real vs Virtual Memory

• Real Memory
  – main memory.
  – RAM sesungguhnya.
• Virtual Memory
  – memori pada disk.
  – memungkinkan untuk multiprogramming yang efektif dan mengurangi kendala ketat user dari main memory.

C)   Dukungan yang dibutuhkan untuk Virtual Memory

D)   Paging

• Istilah virtual memory biasanya berhubungan dengan sistem yang menggunakan paging.
• Penggunaan paging untuk mencapai virtual memory pertama kali dilaporkan untuk komputer Atlas.
• Setiap proses memiliki page table sendiri.
  – setiap entri page table berisi nomor frame halaman yang sesuai dalam main memory.
  – Entri k berisi frame # dari halaman k (jika halaman k berada di dalam memori).

E)   Address Translation

   

F)   Page Table

• Page table sederhana: satu page table per proses.
• Ukuran adalah masalah – untuk alamat 32-bit, setengah untuk OS, setengah untuk ruang user, jumlah halaman dalam proses user adalah 232 / PageSize. Untuk PageSize = 210, tabel halaman akan memiliki 222 entri. PER PROSES!
• Solusi? Menghalamankan page table!

G)   Struktrur Hirarki Page Table

H)   Struktur Page Table Terbalik

• Page table sederhana, page table hirarki menempati banyak ruang: setiap proses memiliki PT sendiri, ukuran setiap PT sebanding dengan ukuran ruang alamat virtual.
• Pendekatan lain: satu page table memetakan semuanya di dalam memori. Ukuran page table adalah tetap.
• Bagian page number dari alamat virtual dipetakan menjadi nilai hash.
  – nilai hash menunjuk ke page table terbalik.
• Proporsi tetap dari real memory diperlukan untuk tabel, terlepas dari jumlah proses atau halaman virtual yang didukung.
• Struktur disebut terbalik karena mengindeks entri page table oleh nomor frame bukan page number virtual.

 

I)   Transaction Lookaside Buffer (TLB)

• Setiap referensi virtual memory dapat menyebabkan dua physical memory mengakses:
  – satu untuk mengambil entri page table.
  – satu untuk mengambil data (atau instruksi berikutnya).
• Untuk mengatasi efek menggandakan waktu akses memori, sebagian besar skema virtual memory menggunakan cache berkecepatan tinggi khusus yang disebut transaction lookaside buffer.

J)   Penggunaan TLB

K)   Page Size

• Semakin kecil ukuran halaman, semakin sedikit jumlah fragmentasi internal.
  – namun, lebih banyak halaman, dibutuhkan per proses.
  – lebih banyak halaman per proses berarti semakin besar page table.
  – untuk program besar dalam lingkungan yang sangat multiprogrammed, beberapa bagian dari proses aktif page table harus berada di virtual memory bukan main memory.
  – karakteristik fisik dari sebagian besar perangkat memori sekunder mendukung ukuran halaman yang lebih besar untuk transfer blok data yang lebih efisien.

 

L)   Segmentation

• Segmentasi memungkinkan programmer untuk melihat memori yang terdiri dari beberapa ruang alamat atau segmen.
• Keuntungan :
  – menyederhanakan penanganan struktur data yang berkembang.
  – memungkinkan program =diubah dan dikompilasi ulang secara independen.
  – cocok untuk berbagi data antara proses.
  – cocok untuk perlindungan.

M)   Segent Organization

• Setiap entri tabel segmen berisi alamat awal segmen yang sesuai dalam main memory dan panjang segmen.
• Sebuah bit diperlukan untuk menentukan apakah segmen tersebut sudah berada di dalam main memory.
• Bit lain diperlukan untuk menentukan apakah segmen telah dimodifikasi sejak dimuat di dalam main memory.

N)   Fetch Policy

Menentukan kapan halaman harus dibawa ke dalam memori.

 

O)   Placement Policy

• Menentukan di mana sepotong proses di dalam real memory berada.
• Masalah desain yang penting dalam sistem segmentasi.
• Paging atau paging gabungan dengan penempatan segmentasi adalah tidak relevan karena hardware melakukan fungsi dengan efisiensi yang sama terlepas dari lokasi page frame.
• Untuk strategi penempatan sistem NUMA harus menetapkan halaman ke memory module yang memberikan kinerja terbaik.

P)   Replacement Policy

• Berhubungan dengan pemilihan halaman di dalam main memory untuk diganti bila halaman baru harus dibawa.
  – tujuannya adalah halaman yang dihapus menjadi halaman yang paling tidak mungkin dirujuk dalam waktu dekat.
• Semakin rumit replacement policy, lebih besar overhead hardware dan software untuk menerapkannya.

Q)   Algoritma Dasar

 

R)   Optimal Policy

• Memilih page yang waktu referensi berikutnya adalah terpanjang.
• Menghasilkan tiga kesalahan page setelah alokasi frame telah diisi (tambahan ke pertama 3 kesalahan).

 

S)   Least Recently Used (LRU)

• Menggantikan page yang belum dirujuk untuk waktu yang lama.
• Dengan prinsip lokalitas, ini harus menjadi page yang paling tidak mungkin dirujuk dalam waktu dekat.
• Sulit diterapkan.
  – satu pendekatan untuk menandai setiap page dengan waktu referensi terakhir.
  – membutuhkan banyak overhead.
• Contoh :

 

T)   First-in-First-out (FIFO)

• Perlakuan page frame dialokasikan ke proses sebagai buffer lingkaran.
• Halaman dihapus dalam round-robin style.
  – replacement pilicy sederhana diterapkan.
• Halaman yang paling lama di dalam memori diganti.
• Contoh :

U)   Clock Policy

• Membutuhkan asosiasi tambahan bit dalam setiap frame.
  – disebut sebagai penggunaan bit.
• Ketika page dimuat pertama di dalam memori atau direferensikan, penggunaan bit diatur ke 1.
• Kumpulan frame dianggap buffer melingkar.
• Frame dengan penggunaan bit 1 dilewatkan oleh algoritma.
• Page frame divisualisasikan seperti diletakkan di dalam lingkaran.
• Contoh :

        

• Contoh kombinasi:

V)   Page Buffering

Meningkatkan kinerja paging dan memungkinkan penggunaan halaman sederhana replacement policy.

W)   Replacement Policy dan Ukuran Cache

• Dengan cache besar, penggantian halaman dapat memiliki dampak kinerja.
  – jika page frame dipilih untuk penggantian dalam cache, blok cache akan hilang beserta dengan halaman yang ditahan.
  – dalam sistem yang menggunakan page buffering, kinerja cache dapat ditingkatkan dengan kebijakan untuk penempatan page di page buffer.
  – sebagian besar sistem operasi menempatkan halaman dengan memilih sembarangan page frame dari page buffer.

X)   Ruang Lingkup Replacement

• Ruang lingkup strategi replacement dapat dikategorikan sebagai global atau lokal.
  – keduanya diaktifkan oleh page fault jika tidak ada page frame bebas.
• Lokal
  memilih hanya di antara resident page dari proses yang dihasilkan page fault.
• Global
  menganggap semua halaman dibuka di main memory.

Y)   Ringkasan Resident Set Management

Z)   Fixed Allocation, Local Scope

• Diperlukan untuk memutuskan sebelumnya jumlah alokasi untuk memberikan suatu proses.
• Jika alokasi terlalu kecil, akan ada tingkat page fault yang tinggi.
• Jika alokasi terlalu besar, akan ada juga beberapa program di main memory:
  – meningkatkan waktu diam prosesor.
  – meningkatkan waktu yang dihabiskan untuk pertukaran.

A.1)   Variable Allocation Global Scope

• Paling mudah untuk diterapkan.
  – diadopsi di sejumlah sistem operasi.
• OS menyimpan daftar frame bebas (konsep page buffer).
• Frame bebas ditambahkan ke kumpulan resident proses ketika page fault terjadi.
• Jika tidak ada frame yang tersedia, OS harus memilih halaman saat ini di dalam memori.
• Salah satu cara untuk melawan potensi masalah adalah dengan menggunakan page buffering.

A.2)   Variable Allocation Local Scope

• Ketika proses baru dimuat ke main memory, alokasikan sejumlah page frame sebagai kumpulan resident.
• Ketika page fault terjadi, pilih page untuk menggantikannya dari kumpulan resident proses yang mengalami kesalahan.
• Mengevaluasi kembali alokasi yang disediakan untuk proses dan meningkatkan atau menurunkannya untuk meningkatkan kinerja secara keseluruhan.
• Keputusan untuk menambah atau mengurangi ukuran kumpulan resident didasarkan pada penilaian terhadap tuntutan masa depan dari kemungkinan proses yang aktif.
• Contoh: strategi kumpulan pekerjaan.
• Key elemen:
  – kriteria yang digunakan untuk menentukan ukuran kumpulan resident.
  – waktu perubahan.

A.3)   Page Fault Frequency (PFF)

• Membutuhkan penggunaan bit untuk dihubungkan dengan setiap halaman dalam memori, set ke 1 ketika halaman tersebut diakses.
• Permulaan F mendefinisikan waktu penerimaan antara-kesalahan.
• Ketika kesalahan halaman terjadi, OS mencatat waktu virtual sejak halaman kesalahan terakhir untuk proses tersebut (memerlukan counter page reference).
  – If <F menambahkan page ke resident set (RS)
  – Else menghilankan RS dengan menghapus page apapun dengan menggunakan bit = 0, reset semua penggunaan bit lain ke 0
• Kinerja yang buruk ketika ada pergeseran ke sebuah wilayah baru.