Pengertian Virtual Memori

• Konsep dasar memori virtual
  

Sebagian besar algoritma manajemen memori memerlukan satu kebutuhan dasar

yaitu instruksi yang akan dieksekusi harus berada di memori fisik. Pada beberapa

kasus, keseluruhan program tidak diperlukan. Misalnya :

• Program mempunyai kode untuk menangani kondisi error yang tidak biasa. Karena error-error ini jarang terjadi, kode ini hampir tidak pernah dieksekusi.
  
• Array, list dan tabel dialokasikan lebih dari kapasitas memori yang diperlukan
  
• Pilihan dan gambaran program jarang digunakan
  

 
Pada kasus dimana keseluruhan program dibutuhkan, mungkin tidak semua diperlukan pada saat yang sama. Kemampuan mengeksekusi program hanya pada beberapa bagian dari memori mempunyai beberapa keuntungan yaitu :

• Program tidak terbatas jumlah memori fisik yang tersedia sehingga user dapat menulis program untuk ruang alamat virtual yang sangat besar yang berarti menyederhanakan programming task.
  
• Karena setiap program user dapat menggunakan memori fisik yang lebih kecil, pada waktu yang sama dapat menjalankan lebih banyak program.
  
• 
  
  
  
  I/O yang lebih sedikit diperlukan untuk load atau swap program user ke memori, sehingga setiap program user dapat berjalan lebih cepat.
  
  
  
  

Memori virtual adalah teknik yang memisahkan
memori logika user dari memori fisik. Menyediakan memori virtual yang sangat besar diperuntukkan untuk programmer bila tersedia memori fisik yang lebih kecil. Programmer tidak perlu

khawatir jumlah memori fisik yang tersedia, sehingga dapat berkonsentrasi pada

permasalahan pemrograman. Gambaran memori virtual dapat dilihat pada Gambar


 

• Demand paging adalah sistem paging dengan swapping seperti pada ilustrasi gambar dibawah.
  

Page diletakkan di memori hanya jika diperlukan. Hal ini menyebabkan kebutuhan

I/O lebih rendah, kebutuhan memori lebih rendah, respon lebih cepat dan lebih banyak user yang menggunakan.

Proses disimpan di memori sekunder (disk). Jika proses akan dieksekusi, maka

dipindah (swap) ke memori. Menggunakan lazy swapper untuk melakukan swapping

bila page tersebut akan digunakan yang berarti sebuah page tidak pernah ditukar ke

memori kecuali page diperlukan. Jika page diperlukan, dilakukan acuan ke page

tersebut, tetapi jika acuan invalid maka dilakukan penghentian.


 
Untuk membedakan antara page pada memori dengan page pada disk digunakan

valid-invalid bit. Tabel page
untuk page yang berada di memori diset "valid',

sedangkan tabel page untuk page yang tidak sedang di memori (ada pada disk) diset "invalid" seperti Gambar

 

Akses ke page yang diset "invalid" menyebabkan page fault, yang

menyebabkan trap ke sistem operasi. Karena status (register, kode kondisi, counter

instruksi) dari proses ter-interrupt disimpan bila terjadi page fault, proses dapat dimulai lagi pada tempat dan status yang sama, kecuali page yang cocok sedang di memori dan sedang diakses. Prosedur untuk menangani page fault seperti Gambar sebagai berikut :

1. Sistem operasi melihat tabel untuk menentukan jika acuan invalid maka proses dihentikan dan page sedang tidak berada di memori.
   
2. Jika acuan invalid dilakukan trap ke sistem operasi.
   
3. Sistem mencari frame kosong
   
4. Sistem melakukan proses swapping ke frame bebas.
   
5. Tabel page di-reset, bit valid-invalid diset 1 atau valid
   
6. instruksi di-restart.
   

 

 

Apabila tidak ditemukan
frame bebas maka dilakukan page replacement
yaitu

mencari beberapa page di memori yang tidak digunakan kemudian dilakukan swap out

ke backing store. Terdapat beberapa algoritma page replacement dimana performansi

algoritma diharapkan menghasilkan jumlah page fault minimum. Beberapa page

kemungkinan dibawa ke memori beberapa kali.

Perangkat keras yang dibutuhkan untuk mendukung demand paging
sama

dengan perangkat keras untuk sistem paging dengan swapping yaitu

• Tabel page : tabel mempunyai kemampuan untuk memberi entry bit valid-invalid atau nilai khusus untuk bit proteksi
  
• Memori sekunder : digunakan untuk membawa page yang tidak di memori dan biasanya adalah disk kecepatan tinggi yang disebut swap device.
  

 

• Unjuk Kerja DEMAND PAGING
  

 
Demand paging memberikan efek yang signifikan dalam kinerja sistem

computer. Diasumsikan ma adalah access time ke memori dan P adalah probabilitas terjadi page fault (0 ≤ p ≤ 1), maka effective access time didefinisikan sebagai :


 

EAT = (1-p) x ma + p x page_fault-time

 

Untuk menghitung effective access time, harus diketahui berapa waktu yang diperlukan untuk melayani page fault. Page fault menyebabkan terjadi

1. Trap ke sistem operasi.
   
2. Menyimpan register dan status proses.
   
3. Menentukan interrupt adalah page fault
   
4. Memeriksa page acuan legal atau tidak dan menentukan lokasi page pada disk.
   
5. 
   
   
   
   Membaca dari disk ke frame bebas :
   
   1. Menunggu di antrian untuk perangkat sampai permintaan membaca dilayani.
      
   2. Menunggu perangkat mencari dan / atau waktu latency.
      
   3. Memulai transfer dari page ke frame bebas.
      
6. Sementara menunggu, alokasikan CPU untuk user lain.
   
7. Interrupt dari disk (melengkapi I/O).
   
8. Menyimpan register dan status process user lain.
   
9. Menentukan interrupt dari disk.
   
10. Memperbaiki tabel page dan tabel lain untuk menunjukkan page yang dimaksud sudah di memori.
    
11. Menunggu CPU dialokasikan untuk proses ini kembali.
    
12. Menyimpan kembali register, status proses dan tabel page baru, kemudian melanjutkan kembali instruksi yang di-interupsi.
    

 
Untuk Menghitung Effective Access Time
dari sistem demand paging perhatikan contoh berikut. Diasumsikan memory access 100 ns. Rata-rata waktu latency untuk hard disk adalah 8 ms, waktu pencarian 15 ms dan rata-rata transfer sebesar 1 ms. Total waktu paging ≈ 25 ms.

EAT = (1-p) x ma + p x page_fault-time


 

Effective access time     = (1-p) x (100) + p x (25 ms)

= (1-p) x 100 + p x 25000000

= 100 + 24999900 x p

 

Apabila satu dari 1000 akses menyebabkan page fault, maka effective access time = 25 micro-sec (lebih lambat dengan faktor 250). Tetapi bila menginginkan degradasi

kurang dari 10% maka

        110 > 100 + 25000000 x p

            10 > 250000000 x p

            p < 0.0000004

 

Dapat Disimpulkan system harus mempertahankan rata-rata page-fault yang rendah pada sistem demand-paging. Sebaliknya, jika effective access time meningkat maka akan memperlambat eksekusi
proses secara drastis.


 

• PAGE REPLACEMENT
  

Page replacement diperlukan pada situasi dimana proses dieksekusi perlu frame

bebas tetapi tidak tersedia frame bebas. Sistem harus menemukan satu frame yang

sedang tidak digunakan dan membebaskannya. Untuk membebaskan frame dengan cara

menulis isinya untuk ruang swap dan mengubah tabel page (dan tabel lain) yang

menunjukkan page tidak lagi di memori. Kebutuhan akan page replacement dapat

dilihat pada Gambar


 

 
Langkah-langkah untuk page fault yang memerlukan page replacement seperti

Gambar 8-6 adalah sebagai berikut :

1. Carilah lokasi page yang diharapkan pada disk.

2. Carilah frame kosong dg cara :

• Bila ada frame kosong, gunakan.

• Bila tidak ada, gunakan algoritma page replacement untuk menyeleksi frame

yang akan menjadi korban.

• Simpan page korban ke disk, ubah tabel page.

3. Baca page yang diinginkan ke frame kosong yang baru, ubah tabel page.

4. Mulai kembali proses user.


 

 

 

 

 

 

 

• ALGORITMA PAGE REPLACEMENT
  

Terdapat beberapa algoritma page replacement, setiap sistem operasi

mempunyai skema yang unik. Algoritma page replacement secara umum diinginkan

yang mempunyai rata-rata page fault terendah. Algoritma dievaluasi dengan

menjalankannya pada string tertentu dari memory reference dan menghitung jumlah

page fault. String yang mengacu ke memori disebut reference string (string acuan).

String acuan dibangkitkan secara random atau dengan menelusuri sistem dan menyimpan alamat dari memori acuan.


 

• Algoritma FIFO
  

Algoritma FIFO merupakan algoritma paling sederhana. Algoritma FIFO

diasosiasikan dengan sebuah page bila page tersebut dibawa ke memori. Bila ada suatu

page yang akan ditempatkan, maka posisi page yang paling lama yang akan digantikan.

Algoritma ini tidak perlu menyimpan waktu pada saat sebuah page dibawa ke memori.

Ilustrasi algoritma FIFO dapat dilihat pada Gambar


 
Meskipun algoritma FIFO mudah dipahami dan diimplementasikan, performansi

tidak selalu bagus karena algoritma FIFO menyebabkan Belady's anomaly. Belady's

anomaly mematahkan fakta bahwa untuk beberapa algoritma page replacement, bila

rata-rata page fault meningkat, akan meningkatkan jumlah alokasi frame. Sebagai

contoh, jika menggunakan string acuan :

1, 2, 3, 4, 1, 2, 5, 1, 2, 5, 1, 2, 3, 4, 5


   

• Algoritma Optimal
  

Algoritma optimal merupakan hasil penemuan dari Belady's anomaly.

Algoritma ini mempunyai rata-rata page fault terendah. Algoritma optimal akan

mengganti page yang tidak akan digunakan untuk periode waktu terlama. Algoritma

ini menjamin rata-rata page fault terendah untuk jumlah frame tetap tetapi sulit

implementasinya. Ilustrasi dari algoritma optimal dapat dilihat pada Gambar

  

• Algoritma Least Recently Use (LRU)
  

Algoritma LRU merupakan perpaduan dari algoritma FIFO dan optimal.

Prinsip dari algoritma LRU adalah mengganti page yang sudah tidak digunakan untuk

periode waktu terlama. Untuk mengimplementasikan algoritma LRU, digunakan dua model yaitu :

• Counter : setiap entry tabel pagee diasosiasikan dengan sebuah "time-of-use" dan

sebuah clock logika atau counter ditambahkan ke CPU. Clock ini dinaikkan untuk

setiap acuan ke memori. Jika sebuah acuan ke page dibuat, isi clock register dicopy

ke time-of-use pada tabel page untuk page tersebut.

• Stack : stack dari nomor page diatur. Jika sebuah page digunakan acuan, maka

page dihapus dari stack dan meletakkan pada top of stack. Dengan cara ini, stack

selalu digunakan page dan bagian bawah untuk page LRU. Implementasi stack

untuk algoritma LRU diilustrasikan pada Gambar

• ALOKASI FRAME
  

Alokasi frame berhubungan dengan mekanisme alokasi sejumlah memori bebas

yang tetap diantara beberapa proses. Meskipun terdapat beberapa variasi pengalokasian frame bebas ke beberapa proses, tetapi strategi dasar jelas yaitu : proses user dialokasikan untuk sembarang frame bebas. Jumlah minimum frame per proses ditentukan oleh arsitektur dimana jumlah maksimum tergantung jumlah memori fisik yang tersedia. Jumlah minimim frame ditentukan oleh arsitektur instruction-set. Bila terjadi page fault sebelum eksekusi instruksi selesai, instruksi harus di-restart. Sehingga tersedia frame yang cukup untuk membawa semua page yang berbeda dimana sembarang instruksi dapat mengacu. Misalnya mikrokomputer menggunakan memori 128K yang dikomposisikan dengan page ukuran 1K, maka terbentuk 128 frame. Jika sistem operasi menggunakan 35K, maka 93 frame sisa digunakan program user. Bila suatu program menyebabkan page fault sebanyak 93 kali, maka menempati 93 frame bebas tersebut. Jika terjadi page fault ke 94, dari 93 frame yang terisi harus dipilih salah satu untuk diganti yang baru. Bila program selesai, 93 frame tersebut dibebaskan kembali.


 
Terdapat 2 bentuk Algoritma Pengalokasi yaitu equal allocation
dan proportional allocation. Pada equal allocation, jika terdapat m frame dan n proses, maka setiap
proses dialokasikan sejumlah frame yang sama (m/n frame). Pada proportional allocation setiap proses dialokasikan secara proporsional berdasarkan ukurannya. Jika ukuran virtual memori untuk proses p_i
adalah s_i dan total jumlah frame yang tersedia m.

Selain itu terdapat algoritma alokasi berprioritas yang menggunakan skema

proporsional dengan lebih melihat prioritas proses dari pada ukuran proses. Jika proses Pi membangkitkan page fault, dipilih satu dari frame-frame dari proses yang

mempunyai nomor prioritas terendah.


 

 

Global replacement
mengijinkan suatu proses untuk menyeleksi suatu frame yang akan dipindah dari sejumlah frame, meskipun frame tersebut sedang dialokasikan
ke proses yang lain. Pada Local Replacement, jumlah frame yang dialokasikan untuk
proses tidak berubah. Setiap proses dapat memilih dari frame-frame yang dialokasikan
untuknya.

Permasalahan pada global replacement adalah proses tidak dapat mengontrol
rata-rata page fault. Sejumlah page pada memori untuk sebuah proses tidak hanya
tergantung pada perilaku paging untuk proses tersebut, tetapi juga perilaku paging untuk
proses yang lain. Bagaimanapun, karena algoritma global replacement menghasilkan through put yang lebih besar, metode ini sering digunakan.

• Thrashing
  

Misalnya sembarang proses tidak mempunyai frame yang cukup. Meskipun secara teknis dapat mengurangi jumlah frame yang dialokasikan sampai minimum, terdapat sejumlah page yang sedang aktif digunakan. Jika suatu proses tidak memiliki jumlah frame yang cukup, maka sering terjadi page fault. Sehingga harus mengganti beberapa page. Tetapi karena semua page sedang digunakan, harus mengganti page yang tidak digunakan lagi. Konsekuensinya, sering terjadi page fault lagi dan lagi. Proses berlanjut page fault, mengganti page untuk page fault dan seterusnya. Kegiatan aktifitas paging yang tinggi disebut thrashing. Sebuah proses mengalami thrashing jika menghabiskan lebih banyak waktu untuk paging daripada eksekusi. Efek thrashing dapat dibatasi dengan menggunakan algoritma local (priority) replacement. Grafik terjadinya proses thrashing pada sistem multiprogramming dapat dilihat pada Gambar