Algoritma-algoritma Penggantian Page

Saat terjadi page fault berarti harus diputuskan page frame dari memori fisik yang harus diganti. Kinerja sistem akan baik jika page yang diganti dipilih yang tidak akan digunakan di masa 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 overhead.

Algoritma-algoritma penggantian page antaralain:

1. Algoritma penggantian page acak (random page replacement algorithm)

Mekanisme algoritma ini: Setiap terjadinya page fault maka page diganti dan dipilih secara acak.

Teknik ini tidak memakai informasi apapun dalam menentukkan page yang diganti. Semua page dimemori utama mempunyai bobot sama untuk dipilih. Teknik ini dapat memilih sembarang page, termasuk page yang sedang diacu (page yang seharusnya tidak diganti, pilihan terburuk).

Teknik ini terbilang sangat buruk, percobaan menunjukkan algoritma acak menimbulkan peringkat terjadinya page fault sangat tinggi.

2. Algoritma penggantian page optimal

Mekanisme Algoritma ini: memilih page yang berpeluang dipakai kembali dimasa datang yang paling kecil.

Strategi ini akan menghasilkan jumlah page fault paling sedikit. Algoritma ini adalah algoritma utopia (ideal tanpa dapat dijadikan kenyataan) karena tak mungkin dibuat prosedur yang dapat mengetahui peluang pemakaian suatu page kembali dimasa datang. Metode ini tak mungkin diterapkan.

Pendekatan ini dapat dilakukkan dengan simulasi. Tapi simulasi hanya spesifik suatu program. Bila yang terbaik tak dimungkinkan, maka yang perlu dilakukkan adlaah berusaha mendekatinya. Algoritma penggantian page diusahakan inerjanya mendekati optimal. Tiap algoritma penggantian page mengumpulkan dan memakai informasi untuk menentukkan page yang diganti sehingga mendekati optimal.

Algortima penggantian page optimal penting untuk kajian teoritis, sebagai pembanding bagi algoritma-algoritma penggantian page yang lain.

3. Algoritma penggantian page NRU (Not Recently Used)

Mekanisme algoritma ini: Pada algortima ini, page diberi dua bit mencatat status page, bit R dan bit M.

Bit R yaitu referenced (menyatakan page sedang diacu)

Bit R = 1 berarti sedang diacu

Bit R = 0 berarti tidak sedang diacu

Bit M yaitu modified (menyatakan page telah dimodifikasi)

Bit M = 1 berarti dimodifikasi

Bit M = 0 berarti tidak dimodifikasi

Dengan 2 bit, maka page-page dikelompokkan menjadi 4 kelas page, yaitu:

Kelas 0 = Tidak sedang diacu, belum dimodifikasi (R=0, M=0)

Kelas 1 = Tidak sedang diacu, telah dimodifikai (R=0, M=1)

Kelas 2 = Sedang diacu, belum dimodifikasi (R=1, M=0)

Kelas 3 = Sedang diacu, telah dimodifikasi (R=1, M=1)

• Memilih mengganti page kelas bernomor rendah (bila terdapat page-page dikelas itu) secara acak.

• Bila kelas tersebut kosong maka dipilih page dikelas lebih tinggi, dan seterusnya.

Algoritma ini mengasumsikan kelas-kelas bernomor lebih rendah akan baru akan digunakan kembali dalam waktu relatif lama.

Algoritma ini mudah dipahami dan diimpleentasikan. Implementasi algoritma ini sangat efisiensi karena tak banyak langkah dalam pemilihan page. Agoritma ini memang tidak optimal, tapi dalam kondisi-kondisi normal telah memadai.

Algoritma-algoritma penggantian page selanjutnya >> klik disini.