ALGORITMA PAGE REPLACEMENT Abas Ali Pangera, Dony Ariyus, Jurusan Teknik Informatika, STMIK AMIKOM Yogyakarta, Jl. Ring Road Utara, Condong Catur, Sleman, Yogyakarta - Indonesia
Pada saat terjadinya page fault berarti harus diputuskan page frame di memori fisik yang harus diganti. Kinerja sistem akan baik jika page yang diganti dipilih yang tidak akan digunakan di masa yang akan datang. Jika page yang diganti akan kembali digunakan maka page akan dikembalikan secepatnya yang berarti terjadi page fault berulang kali. Banyaknya page fault menghasilkan banyak overheard. 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 page replacement di antaranya adalah: 1. Algoritma page replacement acak 2. Algoritma page replacement FIFO 3. Algoritma page replacement Optimal 4. Algoritma page replacement NRU 5. Algoritma page replacement second chance page 6. Algoritma page replacement Clock 7. Algoritma page replacement LRU 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 pada Gambar 10-7.
Grafik Jumlah Page Fault Terhadap Jumlah Frame Terdapat beberapa algoritma page replacement antara lain algoritma first in first our (FIFO), optimal dan least recently use (LRU). Pada sub bab 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 Random Pada page replacement dengan menggunakan algoritma acak (random) setiap terjadi page fault, page yang diganti dipilih secara acak. Teknik ini tidak memakai informasi apapun dalam menentukan page yang diganti, semua page di memori utama mempunyai bobot sama untuk dipilih. Cara pemilihan dengan cara acak atau sembarang page, termasuk page yang sedang diacu( page yang seharusnya tidak diganti, pilihan terburuk. Teknik random ini sangat buruk, percobaan menunjukan algoritma acak menimbulkan rate terjadinya page fault yang sangat tinggi 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 seperti:
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. Tampaknya beralasan bila dinyatakan bahwa bila lebih banyak page dialokasikan untuk proses, maka page-fault yang akan terjadi lebih sedikit. Belady justru menemukan fenomena menyimpang dari prasangka umum atau disebut dengan anomaly. Pola-pola pengacuan tertentu menyebabkan lebih banyak page fault bila alokasi page untuk proses ditambah. Fenomena menyimpang ini sebut dengan anomaly belady
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 seperti:
Algoritma NRU (Not-Recently User) Algoritma NRU, page diberi dua bit mencatat status page, Bit R dan M: • Bit R : menyatakan page sedang di acu o Bit R = 1 berarti sedang diacu o Bit R = 0 berarti tidak sedang diacu • Bit M : menyatakan page telah dimodifikasi o Bit M = 1 dimodifikasi o Bit M = 0 tidak di modifikasi
Dengan 2 bit, maka page dikelompokkan menjadi 4 kelas page yaitu: • Kelas 0 : tidak sedang diacu, belum dimodifikasi (R=0 M=0) • Kelas 1 : tidak sedang diacu, telah dimodifikasi (R=0, M=1) • Kelas 2 : sedang diacu, belum dimodifikasi (R=1, M=0) • Kelas 3: sedang diacu, telah dimodifikasi (R=1, M=1) Algoritma ini memilih menganti kelas page bernomor terendah bila terdapat page dikelas tersebut secara acak, bila kelas tersebut kosong maka dipilih kelas page bernomor lebih tinggi dan seterusnya. Pada algoritma ini diasumsikan kelas bernomor lebih rendah akan baru yang akan digunakan kembali dalam waktu relatif lama. Implementasi algoritma ini sangat efisien karena tidak banyak langkah dalam pemilihan page. Tapi algoritma ini memang tidak optimal, tapi dalam kondisi-kondisi normal sudah cukup memandai. Algoritma Second Chance Page Algoritma ini merupakan varian dari FIFO, saat terjadi fault, algoritma ini memilih page elemen terdepan diganti bila bit R benilai 0, bila bit R bernilai 1, maka bit page terdepan senarai direset menjadi bernilai 0 dan diletakkan ke ujung belakang senarai, mekanisme ini kembali diterapkan ke element berikutnya.
Algoritma Clock Algoritma ini merupakan modifikasi dari algoritma FIFO, kelemahan FIFO dengan memindahkan page yang sering digunakan yang lama berada di memori. Kemungkinan ini dapat dihindari dengan hanya memindahkan page tidak diacu. Page ditambah bit R mencatat apakah page diacu atau tidak. Bit R bernilai 1 bila diacu dan bernilai 0 bila tidak diacu Pada algoritma ini, semua page merupakan senarai melingkar membentuk pola jam dan terdapat pointer yang menunjuk ke arah page terlama, ketika terjadi page fault, page yang ditunjuk diperiksa. • Jika bit R bernilai 0, maka page diganti, sedangkan page baru ditempatkan di tempat page yang diganti dan penunjuk dimajukan satu posisi ke page berikutnya
•
Jika bit R benilai 1, maka bit R direset menjadi 0, dan penunjuk dimajukan satu posisi, hal ini dilakukan sampai page dengan bit R benilai 0 Sebagai contoh diasumsikan terdapat buffer sirkular yang berisi n frame pada memori utama untuk pengantian page. Sebelum pengantian page dari buffer dengan page baru 727, pointer frame berikutnya menunjuk pada frame 2, berisi page 45. karena page pada frame 2 berisi page 456 sama dengan 1, maka page ini tidak digantikan melainkan bit disetel 0 dan pointer dimajukan, demikian juga dengan page 191 di dalam frame 3 tidak digantikan, bitnya disetel 0 dan pointer dimajaukan. Di dalam frame berikutnya, frame 4, bit disetel 0, karena itu, page 556 digantikan dengan page 727, frame tersebut disetel 1 dan pointer dimajukan ke frame 5,
Bentuk Buffer Pada Saat Pengantian Page
Bentuk Buffer Pada Saat Pengantian Page Berikutnya
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 seperti :
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-ofuse 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 seperti:.
Perbandingan Algoritma Page Replacement Setiap algoritma page repleacement mempunyai kelebihan dan kekurangan masing-masing, pada contoh kasus di bawah ini string acuan atau page address diasumsikan dengan: 2 3 2 1 5 2 4 5 3 2 5 2 yang berarti bahwa page pertama yang direferensikan adalah 2, page kedua yang direferensikan adalah 3, dan seterusnya Algoritma Page Replacement Optimal
Pada contoh ini diasumsikan suatu alokasi frame tetap (ukuran resident set yang tetap) bagi proses yang terdiri dari tiga frame. Eksekusi proses tersebut memerlukan referensi ke lima page yang berbeda. Pada algoritma ini menghasilkan tiga page fault setelah alokasi frame telah diisi Algoritma Page Replacement LRU
Algoritma ini menangani page di dalam memori yang tidak pernah direferensikan dalam waktu yang terlama. Berdasarkan prinsip lokalitas, maka page itu adalah page yang paling kecil kemungkinannya untuk direferensikan dalam waktu dekat, algoritma LRU dapat berfungsi sebaik algoritma optimal. Pada algoritma ini menghasilkan empat fault setelah alokasi frame telah diisi. Algoritma Page Replacement FIFO
Algoritma FIFO memperlakukan page frame yang dialokasikan ke sebuah proses sebagai buffer sirkular, dan page-page itu dipindahkan dengan cara round robin. Algoritma FIFO menghasilkan enam buat page fault. Pada algoritma LRU mengetahui bahwa page 2 dan 5 lebih direferensikan disbanding page-page lain, sedangkan dengan FIFO tidak demikian. Algoritma Page Replacement Clock
Keterangan: *: yang diacu >: ditunjuk pointer Pada algoritma clock sederhana memerlukan bit tambahan pada setiap framenya, yang dikenal sebagai use bit. Pada algoritma ini, pengacuan pengantian page apabila page use = 0 dan pointer menunjuk pada use = 1. pada contoh di atas algoritma clock menghasilkan 5 page fault Pertimbangan pemilihan algoritma penggantian page Pemilihan algoritma penggantian dan aturan alokasi adalah keputusan-keputusan utama yang kita buat untuk sistem pemberian page Masih banyak pertimbangan seperti: • Sebelum Pemberian Page: Sebuah ciri dari sistem demand-paging adalah adanya page fault yang terjadi saat proses dimulai. Situasi ini adalah hasil dari percobaan untuk mendapatkan tempat pada awalnya. Situasi yang sama mungkin muncul di lain waktu. Saat proses swapped-out dimulai kembali, seluruh halaman ada di disk dan setiap halaman harus dibawa masuk oleh page-fault-nya masing-masing. Sebelum pemberian halaman mencoba untuk mencegah tingkat tinggi dari paging awal. Stateginya adalah untuk membawa seluruh halaman yang akan dibutuhkan pada satu waktu ke memori. Pada sistem yang menggunakan model working-set, sebagai contoh, kita tetap dengan setiap proses sebuah daftar dari halaman-halaman di working-set-nya. ika kita harus menunda sebuah proses (karena menunggu I/O atau kekurangan frame bebas), kita mengingat working-set untuk proses itu. Saat proses itu akan melanjutkan kembali (I/O komplit atau frame bebas yang cukup), kita secara otomatis membawa kembali ke memori seluruh working-set sebelum memulai kembali proses tersebut. Sebelum pemberian halaman bisa unggul di beberapa kasus. Pertanyaan sederhananya adalah apakah biaya untuk menggunakan sebelum pemberian halaman itu lebih rendah daripada biaya melayani page-fault yang berhubungan. Itu mungkin menjadi kasus dimana banyak halaman dibawa kembali ke memori dengan sebelum pemberian halaman tidak digunakan.
•
•
Ukuran Halaman: terdapat beberapa pertimbangan dalam menentukan ukuran page, diantaranya adalah: • Ukuran page lebih kecil berarti jumlah page dan page frame lebih banyak sehingga memerlukan tabel page lebih besar • Ukuran page besar, berarti jumlah informasi yang tidak diacu juga dimasukkan ke memori utama sehingga terjadi fragmentasi internal yang tinggi • Transfer I/O relatif sangat mengkonsumsi waktu sehingga perlu meminimumkan jumlah transfer I/O saat program berjalan • Program cenderung mengikuti prinsip lokalitas yang cenderung berukuran kecil Tabel page yang Dibalik: Kegunaan dari bentuk manajemen halaman adalah untuk mengurangi jumlah memori fisik yang dibutuhkan untuk melacak penerjemahan alamat virtual-to-physical. Kita menyelesaikan metode penghematan ini dengan membuat tabel yang memiliki hanya satu masukan tiap halaman memori fisik, terdaftar oleh pasangan (pengenal proses, nomor halaman). Karena mereka tetap menjaga informasi tentang halaman memori virtual yang mana yang disimpan di setiap frame fisik, tabel halaman yang terbalik mengurangi jumlah fisik memori yang dibutuhkan untuk menyimpan informasi ini. Bagaimana pun, tabel halaman yang dibalik tidak lagi mengandung informasi yang lengkap tentang alamat ruang logical dari sebuah proses, dan informasi itu dibutuhkan jika halaman yang direferensikan tidak sedang berada di memori. Demand paging membutuhkan informasi ini untuk memproses page faults. Agar informasi ini tersedia, sebuah tabel halaman luar (satu tiap proses) harus tetap dijaga. Setiap tabel tampak seperti tabel halaman tiap proses tradisional, mengandung informasi dimana setiap halaman virtual berada.
•
Tetapi, melakukan tabel halaman luar menegasikan kegunaan tabel halaman yang dibalik? Sejak tabel-tabel ini direferensikan hanya saat page fault terjadi, mereka tidak perlu untuk tersedia secara cepat. Namun, mereka masing-masing diberikan atau dikeluarkan halaman dari memori sesuai kebutuhan. Sayangnya, sebuah page fault mungkin sekarang muncul di manager memori virtual menyebabkan halaman lain fault seakan-akan halaman ditabel halaman luar perlu untuk mengalokasikan virtual page di bantuan penyimpanan. Ini merupakan kasus spesial membutuhkan penanganan di kernel dan delay di proses melihat halaman. Struktur Program: Demand paging didesain untuk menjadi transparan kepada program pemakai. Di banyak kasus, pemakai sama sekali tidak mengetahui letak halaman di memori. Di kasus lain, bagaimana pun, kinerja sistem dapat ditingkatkan jika pemakai (atau kompilator) memiliki kesadaran akan demand paging yang mendasar Pemilihan yang hati-hati dari struktur data dan struktur permograman dapat meningkatkan locality dan karenanya menurunkan laju page fault dan jumlah halaman di himpunan kerja. Sebuah stack memiliki locality yang baik, sejak akses selalu dibuat di atas. Sebuah hash table, di sisi lain, didesain untuk menyebar referensi-referensi, menghasilkan locality yang buruk. Tentunya, referensi akan locality hanyalah satu ukuran dari efisiensi penggunaan struktur data. Faktor-faktor lain yang berbobot berat termasuk kecepatan pencarian, jumlah total dari referensi dan jumlah total dari halaman yang disentuh.
•
•
Penyambungan Masukan dan Keluaran : Saat demand paging digunakan, kita terkadang harus mengizinkan beberapa halaman untuk dikunci di memori. Salah satu situasi muncul saat I/O sering diimplementasikan oleh pemroses I/O yang terpisah. Sebagai contoh, sebuah pengendali pita magnetik pada umumnya diberikan sejumlah bytes untuk memindahkan dan sebuah alamat memoro untuk buffer. Saat pemindahan selesai, CPU diinterupsi. Kita harus meyakinkan urutan dari kejadian-kejadian berikut tidak muncul: Sebuah proses mengeluarkan permintaan I/O, dan diletakkan di antrian untuk I/O tersebut. Sementara itu, CPU diberikan ke proses-proses lain. Proses-proses ini menyebabkan kesalahan penempatan halaman, dan, menggunakan algoritma penggantian global, salah satu dari mereka menggantikan halaman yang mengandung memory buffer untuk proses yang menunggu. Halaman itu dikeluarkan. Kadang-kadang kemudian, saat permintaan I/O bergerak maju menuju ujung dari antrian device, I/O terjadi ke alamat yang telah ditetapkan. Bagaimana pun, frame ini sekarang sedang digunakan untuk halaman berbeda milik proses lain. Pemrosesan Waktu Nyata : Dengan menggunakan memori untuk data yang aktif, dan memindahkan data yang tidak aktif ke disk, kita meningkatkan throughput. Bagaimana pun, proses individual dapat menderita sebagai hasilnya, sebab mereka sekarang dapat menyebabkan page faults tambahan selama eksekusi mereka. Pertimbangkan sebuah proses atau thread waktu-nyata. Sebuah proses mengharapkan untuk memperoleh kendali CPU, dan untuk menjalankan penyelesaian dengan delay yang minimum. Memori virtual adalah saingan yang tepat untuk perhitungan waktu-nyata, sebab dapat menyebabkan delay jangka panjang, yang tidak diharapkan pada eksekusi sebuah proses saat halaman dibawa ke memori. Untuk itulah, sistem-sistem waktu-nyata hampir tidak memiliki memori virtual.
Daftar Pustaka Ariyus,Dony,2006, “Computer Security”, Andi Offset, Yogyakarta Ariyus, Dony,2005,” kamus hacker”, Andi offset, Yogyakarta Bob DuCharme, 2001,” The Operating System Handbook or, Fake Your Way Through Minis and Mainframes” Singapore: McGraw-Hill Book Co Bill Venners.1998. “Inside the Java Virtual Machin”e . McGraw-Hill. Deitel, Harvey M, 2004 “ operating systems” 3th Edition, Massachusetts: Addison-Wesley Publshing Company Gary B. Shelly, 2007, ”Discovering Computers: Fundamentals” Thomson Gollmann, Dieter,1999 “Computer Security” Jhon Willey & Son Inc, Canada
Grosshans,D. 1986,” File system: design and implementation”, Englewwod Cliffs, New Jersey : Prentice-Hall Inc. Harvey M Deitel dan Paul J Deitel. 2005. Java How To Program. Sixth Edition. Prentice Hall. Hoare, C.A.R. 1985” Communication sequential processes”Englewood Cliffs, New Jersey, Prentice Hall Inc Jean Bacon, Tim Harris, 2003 “Operating Systems: Concurrent and Distributed Software Design” Massachhussets. Addison Wesley Kenneth H Rosen. 1999. “Discrete Mathematics and Its Application”. McGraw Hill. Madnick,Stuart E dan John J. Donovan, 1974 “ operating system”, Singapore: McGraw-Hill Book Co Michael Kifer and Scott A. Smolka, 2007 Introduction to Operating System Design and Implementation The OSP 2 Approach, Springer-Verlag London Microsoft 1999. Microsoft Windows User Experience. Microsoft Press. Milenkovie, Milan. 1992. “Operationg system: Concepts and Design”, Singapore: McGraw-Hill Book Co Randall Hyde. 2003. The Art of Assembly Language. First Edition. No Strach Press Robert betz, 2001 “Intoduction to Real-time operation system”, Department of Electrical and Computer Engineering University of Newcastle, Australia Robert Love. 2005. Linux Kernel Development . Second Edition. Novell Press Ron White,1998, How Computers Work, Fourth Edition, Que corporation, A Division of Macmillan Computer Publishing, USA Shay, William A. 1993, “ Introduction to Operationg System” New York: HarperCollins College Publishers Silberschatz, Peter Galvin, dan Grag Gagne. 2000. “Applied Operating System, 1s”t “ John Wile & Hiil Book Co Silberschatz, A., dan Galvin, P.2003, “Operating Sistem Concept. Sixth Edition”. Massachhussets. Addisson- Wasley Silberschatz, Peter Galvin, dan Grag Gagne. 2005. “Operating Systems Concepts”. Seventh Edition. John Wiley & Sons.
Stalling, William, 1995, “Operating Sistems”. New Jersey. Prentice – Hall Stalling, William, 1996” Computer Organization and Architecture”. New Jersey. Prentice – Hall Stalling William, 1995, “Network and Internetwork Security” Prentice-Hall, USA Tanenbaum, Andrew S, 1992 “Modern Operating Sistems”. New Jersey. Prentice – Hall Taenbaum, Andrew S, 2006, “Operating Systems Design and Implementation, Third Edition” Massachusetts
