virtual memory

virtual memory

Memori virtual (dalam bahasa Inggris: virtual Memory) adalah sebuah mekanisme yang digunakan oleh aplikasi untuk menggunakan sebagian dari memori sekunder seolah-olah ia menggunakannya sebagai RAM fisik yang terinstal di dalam sebuah sistem. Mekanisme ini beroperasi dengan cara memindahkan beberapa kode yang tidak dibutuhkan ke sebuah berkas di dalam hard drive yang disebut dengan swap file, page file atau swap partition.

Dalam sistem operasi berbasis Windows NT, terdapat sebuah komponen yang mengatur memori virtual, yakni Virtual Memory Manager (VMM). VMM dapat memetakan alamat-alamat virtual yang dimiliki oleh sebuah proses yang berjalan ke dalam page memori fisik di dalam komputer. Dengan cara begini, setiap proses pun dapat memperoleh memori virtual yang cukup agar dapat berjalan, dan yang terpenting adalah setiap proses tidak mengganggu memori yang sedang digunakan oleh proses lainnya. VMM menangani paging antara RAM dan page file, dengan memindahkan page dengan menggunakan sebuah cara yang disebut sebagai demand paging. Hasilnya, setiap aplikasi 32-bit pun dapat mengakses memori hingga 4 gigabyte (meskipun Windows hanya membatasi proses yang berjalan dalam modus pengguna hanya sebatas 2 GB saja).

 

  Memori virtual menggabungkan RAM aktif dan memori aktif dalam bentuk cakram ke dalam berbagai macam alamat yang berdekatan.

Keuntungan dan kelebihan virtual memory

Keuntungan sistem virtual memory:
• Konsep mesin virtual menyediakan proteksi yang lengkap untuk sumber daya system sehingga masing-masing mesin virtual dipisahkan mesin virtual yang lain. Isolasi ini tidak memperbolehkan pembagian sumber daya secara langsung
• Sistem mesin virtual adalah mesin yang sempurna untuk riset dan pengembangan system operasi. Pengembangan system dikerjakan pada mesin virtual, termasuk di dalamnya mesin fisik dan tidak mengganggu operasi system yang normal.

Kerugian sistem virtual memory:
• Konsep mesin virtual sangat sulit untuk mengimplementasikan kebutuhan dan duplikasi yang tepat pada mesin yang sebenarnya.

Fungsi Virtual Memory

Untuk mengoptimalkan kinerja dari komputer, dengan tambahan memory, maka kemungkinan terjadi crash sangat kecil sekali.

Ukuran dari paging file biasanya berbeda – beda.Untuk ukuran paging file linux ialah 2 kali lipat dari memory aslinya. Misalkan kita memakai memory berkapasitas 512 MB, maka ukuran paging filenya yaitu 1 GB. Walaupun tidak harus 2 GB, tapi untuk memaksimalkan kinerja maka sebaiknya 2 kali lipatnya. Untuk ukuran paging file di windows XP dan Vista Yaitu 1,5 kali dari kapasitas aslinya. Misalkan kita menggunakan memory sebesar 1 GB, maka paging filenya sebesar 1,5 GB. Dalam Xp maupun Vista paging file ini dinamai dengan pagefile.sys bila kita ingin mencarinya, pasti tidak akan ketemu, karena file ini disembunyikan atau hidden files.

  Demand Paging

Merupakan implementasi yang paling umum dari memori virtual.

Prinsip permintaan pemberian halaman (demand paging) hampir sama dengan sistem penomoran (paging) dengan menggunakan  swapping. Perbedaannya adalah page pada permintaan pemberian halaman tidak akan pernah di-swap ke memori sampai ia benar-benar diperlukan. Untuk itu diperlukan adanya pengecekan dengan bantuan perangkat keras mengenai lokasi dari page saat ia dibutuhkan. 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.

 

Sistem paging dengan swapping

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. Page yang sedang tidak berada di memori tersebut akan dibawa ke memori dari backing store. 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”

 

Beberapa page tidak sedang berada di memori

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 8-4 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.

Langkah-langkah bila terjadi page fault

 

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 system 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 fau.t

4. Memeriksa page acuan legal atau tidak dan menentukan lokasi page pada disk.

5. Membaca dari disk ke frame bebas :

a. Menunggu di antrian untuk perangkat sampai permintaan membaca dilayani.

b. Menunggu perangkat mencari dan / atau waktu latency.

c. 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.

Tidak semua langkah diatas diperlukan pada setiap kasus. Pada beberapa kasus, terdapat tiga komponen utama dari waktu pelayanan page fault yaitu

1. Melayani interrupt page fault.

2. Membaca page.

3. Memulai kembali proses.

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.

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

Perlu diperhatikan 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

Langkah-langkah untuk page fault yang memerlukan page replacement seperti

Gambar nya 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.

 

Langkah – langkah page replacement

 

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. Misalnya jika ditelusuri proses tertentu, disimpan alamat berikut :

0100, 0432, 0101, 0612, 0102, 0103, 0104,

0101, 0611, 0102, 0103, 0104, 0101, 0610,

0102, 0103, 0104, 0101, 0609, 0102, 0105

dimana 100 byte per page direduksi ke string acuan :

1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

Untuk menentukan jumlah page fault untuk string acuan dan algoritma pagereplacement

tertentu, harus diketahui jumlah page frame tersedia juga harus diketahui. Semakin tinggi jumlah frame lebih tinggi, semakin rendah jumlah page fault. Hal ini dapat dilihat dengan grafik

Grafik jumlah page fault terhadap jumlah frame

Terdapat beberapa algoritma page replacement antara lain algoritma first in first out (FIFO), optimal dan least recently use (LRU). Berikut akan diilustrasikan algoritma page replacement tersebut dengan menggunakan string acuan

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

 

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

 

Algoritma page replacement FIFO

 

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

dengan algoritma FIFO terjadi Belady’s anomaly

 

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

  

Belady’s anomaly

 

Algoritma page replacement optimal

 

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. Ilustrasi algoritma LRU sbb:

Algoritma page replacement LRU

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 sbb:

 

Implementasi LRU menggunakan stack

 

Pengalokasian 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 alokasi 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 pi adalah si dan total jumlah frame yang tersedia m, maka frame ke ai dapat dialokasikan ke proses pi sama dengan :

ai si /S x m

Dimana S = Σsi. Contohnya :

            m=64

            si=10

            s2=127

            a1=10/137 x 64 = 5

            a2=127/137 x 64 = 59

Selain itu terdapat algoritma alokasi berprioritas yang menggunakan skema proporsional dengan lebih melihat prioritas proses daripada ukuran proses. Jika proses Pi membangkitkan page fault, dipilih satu dari frame-frame dari proses yang mempunyai nomor prioritas terendah.

 ALOKASI GLOBAL DAN ALOKASI LOKAL

          Page replacement adalah faktor terpenting lain yang harus dipertimbangkan dalam alokasi frame. Pada multiple process yang berkompentisi mendapatkan frame, algoritma page replacement dikelompokkan dalam 2 kategori yaitu global replacement dan local replacement.

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 throughput 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 kemudian. 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 sbb:

Thrashing