Sistem Paging

Program yang harus dijalankan harus dimuatkan di memori utama. Masalah muncul ketika program lebih besar dari memori utama yang tersedia. Masalah ini diatasi dengan :
1. Overlay
2. Memori maya (virtual memori)

Konsep Overlay
Program dipecah menjadi bagian-¬bagian yang dapat dimuat ke memori, disebut overlay. Overlay yang belum diperlukan disimpan di disk, overlay dimuatkan ke memori begitu diperlukan (kode overlay akan dieksekusi).
Pertukaran overlay masuk dan keluar memori dilakukan system operasi. Pembagian menjadi overlay-¬overlay dilakukan programmer. Teknik ini telah ditinggalkan karena teknik memory maya telah dapat diimplementasikan dengan murah dan berkinerja bagus.


Konsep Memori Maya
Memori maya adalah kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Gagasan memori maya adalah ukuran gabungan program, data dan stack melampui jumlah memori fisik yang tersedia. Sistem operasi menyimpan bagian¬ bagian proses yang sedang digunakan di memori utama dan sisanya di disk. Begitu bagian di disk diperlukan maka bagian di memori yang tidak diperlukan disingkirkan diganti bagian di disk yang diperlukan itu. Memori maya dapat dilakukan dengan 3 cara, yaitu :
1. Paging
2. Segmentasi
3. Kombinasi paging dan segmentasi.

Diskripsi Sistem Paging
Sistem Paging mengimplementasikan ruang alamat besar pada memori kecil menggunakan index register, base register, segmen register dll. Beberapa istilah dalam sistem paging :
- Alamat maya (virtual address), adalah alamat yang dihasilkan dengan perhitungan menggunakan index register, base register, segmen register dan sebagainya. Ruang alamat maya yang terbentuk disebut dengan ruang alamat maya.
- Alamat nyata (real address), adalah alamat yang tersedia di memory utama fisik. Ruang alamat nyata yang dibentuk disebut dengan ruang alamat nyata. Meskipun pengacuan proses dilakukan berdasar alamat maya, proses sesungguhnya berjalan di memori nyata. Alamat maya harus dipetakan menjadi alamat nyata saat proses dieksekusi. Sistem computer akan menerjemahkan alamat maya menjadi alamat fisik, bagian yang berfungsi memetakan adalah Memory Management Unit (MMU).
- Page, yaitu unit trkecil ruang alamat maya (virtual address space). Ruang alamat maya proses merupakan kelipatan page yang berukuran sama.
- Page Frame, yaitu unit terkecil memori fisik. Memori fisik secara konseptual dibagi
menjadi sejumlah unit berukuran tetap disebut dengan page frame disingkat frame.
- Page Fault, yaitu exception untuk meminta alokasi page ke memori. Dalam kontek memori maya sering disingkat fault.
- Memori Managemen Unit
• Pada computer tanpa memori maya, alamat langsung diletakkan ke bus dan menyebabkan word memori fisik alamat itu dibaca dan ditulisi.
• Pada computer dengan memori maya, alamat tidak diletakkan ke bus secara langsung tapi lewat MMU yang kemudian memetakan alamat ke alamat memori fisik.
Memori fisik berisi sejumlah page frame yang memuat sebagian dari page¬page proses. Terdapat mekanisme translasi (penterjemahan) alamat (oleh MMU) untuk memetakan page maya ke alamat fisik. Karena tiap page dipetakan secara terpisah, frame-¬frame proses tidak perlu menempati memori fisik berurutan.

Page Replacement
Page replacement diperlukan pada situasi dimana proses dieksekusi perlu frame bebas tetapi tidak tersedia frame bebas. Terdapat beberapa algoritma page replacement antara lain algoritma first in first our (FIFO), optimal dan least recently use (LRU).

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

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

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