Replacement Policy

Riffa Rufaida / 13507007

Alokasi Memori pada Linux Memori merupakan sumber daya penting yang harus dikelola. Umumnya pada komputer terdapat hierarki memori, dan bagian dari sistem operasi yang menangani hal tersebut merupakan memori manajer. Pengalokasian memori pada sistem operasi termasuk ke dalam manajemen memori. Manajer memori di Linux berusaha untuk mengefisienkan ruang alamat pada memori fisik, agar kecepatan memori tidak terlampau berkurang. Maka digunakan dua teknik alokasi memori utama, yaitu alokasi halaman yang ditangani oleh page allocator, dan alokasi slab yang ditangani oleh slab allocator. Alokasi halaman menggunakan algoritma buddy. Pada saat alokasi data di memori, maka blok di memori yang disediakan oleh kernel kepada suatu proses akan dibagi menjadi dua blok yang berukuran sama besar. Hal ini akan berlangsung hingga didapat blok yang sesuai dengan kebutuhan data dari proses tersebut. Kegiatan pembagian blok ini diperintahkan kepada kernel dengan pemanggilan system call kmalloc() yang dipanggil oleh page allocator. Pada saat pembebasan halaman, maka blok yang kini bebas (kosong) akan digabungkan kembali dengan blok tetangganya yang berukuran sama dan berstatus bebas.

Gambar 1 Contoh penggunaan alokasi halaman dengan algoritma buddy

Alokasi slab menggunakan algoritma slab. Slab merupakan halaman-halaman memori fisik yang berdekatan, digunakan untuk kegiatan pengalokasian memori. Sebuah cache akan terdiri dari satu atau lebih slab dan diisi oleh beberapa objek. Objek sendiri merupaka bentuk instansiasi dari struktur data kernel yang direpresentasikan oleh cache yang bersangkutan. Ketika sebuah cache dibuat maka semua objek (di dalam cache tersebut) berstatus free. Saat ada permintaan, maka objek-objek yang dibutuhkan dalam permintaan tersebut akan berubah status menjadi used. Ada 3 macam status dari sebuah slab, yang pertama adalah full, dimana semua objek dalam slab berstatus used, empty, semua objek di dalam

Riffa Rufaida / 13507007 slab berstatus free, dan partial, ada objek yang berstatus free maupun used. Alokasi slab memiliki keuntungan yaitu memperkecil kemungkinan terjadinya fragmentasi dan permintaan akan memori akan cepat terpenuhi –karena penggunaan cache-.

Gambar 2 Contoh penggunaan alokasi slab

Manajemen memori pada Linux melingkupi pengalokasian memori dinamis secara kontigu dan nonkontigu. Alokasi halaman dengan algoritma buddy dan alokasi slab merupakan pengalokasian memori secara kontigu. Pemetaan memori yang kontigu lebih banyak digunakan karena penggunaan cache yang lebih maksimal dan waktu akses memori yang lebih rendah. Namun jika permintaan akses akan memori area jarang, maka alokasi berdasarkan page frame yang non kontigu melalui linier address yang kontigu dapat digunakan. Referensi : [1] http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-2/ch09.html [2] http://kur2003.if.itb.ac.id/file/FMKL-K1-08.doc [3]http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/2005/116/36/OS/presentasi.pdf [4] http://lurik.its.ac.id/latihan/Presenta.pdf

Riffa Rufaida / 13507007

Algoritma Penggantian Page pada Linux Keterbatasan memori fisik mengharuskan Linux mengatur halaman-halaman mana saja yang harus diletakkan di dalam memori fisik atau swap-in dan juga halaman-halaman yang harus dikeluarkan dari memori fisik atau swap-out. Paging system dari memori virtual dapat dibagi menjadi dua : 1. The pageout-policy algorithm . Menentukan halaman-halaman mana saja yang di swapout dari memori fisik. 2. The paging mechanism. Menentukan halaman-halaman mana saja yang harus dibawa kembali ke dalam memori. Halaman-halaman ini pernah berada dalam memori sebelumnya. Page-out policy algorithm menggunakan modifikasi algoritma clock yang mengacu pada LRU(Least Recently Used) policy dalam menentukan halaman mana yang harus di swap-out. Pada algoritma clock yang simpel, ada bit use dan bit modify yang terasosiasi dengan setiap page di memori utama, dan dilakukan scanning pada seluruh page frame yang ada secara sirkular. Pada pass pertama, saat menunjuk pada sebuah page frame, bit use dokosongkan. Pada pass kedua, page frame yang belum pernah diakses akan tetap memiliki bit use yang kosong, dan akan disimpan ke dalam daftar bebas. Pada skema Linux, bit use diganti dengan 8 bit variabel age. Setiap kali sebuah page diakses, variabel age ditambah. Linux sendiri secara periodik menyisir page global dan mengurangi variabel age dari setiap page saat berkeliling pada keseluruhan page di memori utama. Sebuah page dengan age 0 adalah page “tua” yang dalam suatu jangka waktu tidak pernah direferensi dan merupakan kandidat terbaik untuk penggantian. Semakin besar nilai variabel age, semakin sering sebuah page digunakan dan semakin tidak cocok untuk penggantian. Dalam Linux, multipass clock digunakan, setiap satu kali pass dari clock, age dari suatu halaman akan disesuaikan. Makin sering suatu halaman di akses, makin tinggi age-nya, tapi age dari suatu halaman berkurang setiap satu kali pass. Algoritma ini merupakan algoritma penggantian global, yang berarti bahwa saat memindahkan sebuah page, page dari proses manapun yang dipindahkan tidak akan menjadi masalah. Ini menjadikan jumlah page dari masing-masing proses berubah-ubah setiap waktu.

Riffa Rufaida / 13507007

Gambar 1 Algoritma clock

Berikut adalah ilustrasi untuk algoritma clock. Di dalam memori virtual terdapat page 1, 2 dan 3 dengan pointer last-used di page 3. Flag use akan bernilai 1 jika page tersebut digunakan, sedangkan use akan bernilai 0 jika page tersebut dilewati pointer namun tidak digunakan. Ketika ada permintaan page 4, sedangkan tidak ada page 4 dalam memori virtual sehingga terjadi page fault, maka page 4 akan dimasukkan ke tempat yang masih kosong, pointer akan menunjuk ke page 4, dan use diubah menjadi 1. Saat datang permintaan page 3, pointer akan mencari page tersebut, sekaligus mengubah flag use menjadi 0 jika page tersebut hanya dilewati, tetapi tidak digunakan. Ketika ada permintaan untuk page 9, maka terjadi page fault karena page 9 tidak ada dalam memori virtual. Kemudian pointer akan mencari page yang nilai use-nya = 0, yaitu page 2. Hal yang serupa terulang ketika ada permintaan untuk page 5. Sehingga page 4 di swapped-out, dan nilai use dari page 3 diubah menjadi 0. [1] http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-2/ch09s06.html#c536f04 [2] Stallings, William. 2008. Operating Systems : Internal and Design Principles. Sixth Edition. Pearson.