Open Source Note

Pada algoritma ini setiap kali terjadi page fault penggantian page nya di pilih dengan cara acak. Dan teknik ini tidak memerlukan informasi apapun untuk menentukan page yang di ganti tersebut. Itu karena semua page di memori utamanya mempunyai bobot yang sama sehingga tidak ada kriteria tertentu untuk di pilih. 

Karena teknik ini mengganti page dengan  cara acak dan bebas, maka bisa saja page yang sedang diacu (page yang seharusya tidak di ganti) pun dapat di pilih, sehingga menimbulkan rate terjadinya page fault yang sangat tinggi. 

Algoritma ini di sebut juga sebagai Algoritma utopia (ideal tanpa dapat di jadikan kenyataan), mengapa demikian? Sebab algoritma ini tak mungkin di buat prosedur yang dapat mengetahui peluang pemakaian suatu page kembali di masa datang. 

Mekanisme dari algoritma ini adalah dengan mengumpulkan dan memakai informasi untuk menentukan page yang di ganti sehingga mendekati optimal. Dasar dari algoritma ini yakni memilih page yang berpeluang dapat di pakai kembali di masa yang akan datang yang paling kecil. Maksudnya memakai kembali page yang kemungkinan kecil tidak dapat di gunakan lagi, otimalisasi page. 

Algoritma ini penting untuk kajian teoritis sebagai pembanding bagi algoritma-algoritma penggatian page yang lain.

Berdasarkan pembagian kelas tersebut diatas, maka untuk pemilihan page pengganti dilihat dari kelas yang bernomor paling rendah, tapi apabila terdapat page-page di kelas tersebut pemilihan dilakukan secara acak. Dan apabila kelas tersebut kosong maka dipilih page dikelas yang paling tinggi, begitupun seterusnya.

Inti dari algoritma ini adalah mengasumsikan kelas-kelas  bernomor lebih rendah akan baru akan di gunakan kembalil dalamwaktu relatif lama.

Cara kerja algoritma ini simple, seperti halnya dengan antrian tak berprioritas. Dimana page yang masuk lebih dulu maka akan keluar lebih dulu juga. Oleh karena algoritma ini menggunakan struktur data stack, yaitu jika tidak ada frame yang kosong pada saat terjadi page fault maka frame yang berada pada stack paling bawah akan dipilih. 

Algoritma ini dapat memindahkan page yang sering digunakan berdasarkan informasi mengenai lamanya berada di memori. Dan bisa saja page itu selalu berada di memori karena selalu digunakan.

• Algoritma Penggantian Page Modifikasi dari Algoritma FIFO 

Untuk menyempurnakan kelemahan dari algoritma FIFO maka algoritma tersebut dimodifikasi, yakni dengan hanya memindahkan page yang tidak diacu dan dengan menambahkan bit R mencatat apakah page diacu atu tidak. Bila bit R bernilai 1 maka diacu, bila bernilai 0 tidak diacu. 

Ada 2 variasi FIFO, yakni:

• Algoritma penggantian page kesempatan kedua (second chance page replacement agorithm)

                Merupakan penyempurnaan dari Algoritma FIFO, bedanya jika FIFO menggunakan struktur  data stack, maka second chance ini menggunakan circular queue. Yakni page yang baru digunakan akan di beri nilai 1 pada reference bitnya, jika halaman sudah bernilai 1 pada reference bit-nya maka tidak langsung diganti walaupun dia berada pada tumpukan terbawah (berbeda dengan FIFO).

• Algoritma penggantian clock page (clock page replacement algorithm)

                Algoritma ini merupakan perbaikan dari kelemahan second chance yang mana tidak efisien karena memindahkan page-page di senarainya. Pada  algoritma ini, semua page merupakan  senarai melingkar membentuk pola jam. Terdapat petunjuk (pointer) ke page tertua.

Kedua algoritma ini adalah sama, hanya berbeda pada implementasinya, jika second chance menggunakan senarai lurus tidak sirkular, sedangkan clock page menggunakan senarai sirkular.

• Algoritma Penggantian Page LRU (Least Recently Used)

Performance dari algoritma ini mendekati algoritma optimal yang di kenal sangat sulit dalam pengimplementasiannya, hanya saja LRU menjadi lebih mahal sebab algoritma ini harus mengelola informasi seluruh page di memori dengan membuat linked list untuk mendata page mana yang paling lama tidak terpakai, serta harus mengupdate setiap kali ada page yang di akses.

Itulah beberapa point tentang algoritma penggantian page, 

hmm,, mudah-mudahan bermanfaat ya,,,  

Terima Kasih Sudah Membaca,, ^_^