Algoritma FIFO

Algoritma FIFO (First In First Out)

Prinsip yang digunakan dalam algoritma FIFO yaitu  halaman yang diganti adalah  halaman yang paling lama berada di memori. Algoritma ini adalah algoritma pemindahan  halaman yang paling mudah diimplementasikan, akan tetapi paling jarang digunakan dalam bentuk aslinya, biasanya dikombinasikan dengan algoritma lain. Algoritma ini adalah algoritma yang paling sederhana. Prinsip dari algoritma ini adalah seperti prinsip antrian (antrian tak berprioritas), halaman yang masuk lebih dulu maka akan keluar lebih dulu juga.

Pengimplementasian algoritma FIFO dilakukan dengan menggunakan antrianuntuk menandakan halaman yang sedang berada di dalam memori. Setiap halaman baru yang diakses diletakkan di bagian belakang (ekor) dari antrian. Apabila antrian telah penuh dan ada halaman yang baru diakses maka halaman yang berada di bagian depan (kepala) dari antrian akan diganti.

Kelemahan dari algoritma FIFO adalah kinerjanya yang tidak selalu baik. Hal ini disebabkan karena ada kemungkinan halaman yang baru saja keluar dari memori ternyata dibutuhkan kembali. Di samping itu dalam beberapa kasus, tingkat kesalahan halaman justru bertambah seiring dengan meningkatnya jumlah frame, yang dikenal dengan nama Anomali Belady.

Kelemahan FIFO yang jelas adalah algoritma dapat memilih 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.

Variasi dari FIFO antara lain:

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

• Algoritma penggantian clock page (clock page replacement algorithm)

Pada awalnya, algoritma ini dianggap cukup mengatasi masalah tentang pergantian halaman, sampai pada tahun 70-an, Belady menemukan keanehan pada algoritma ini yang dikenal kemudian dengan anomali Belady. Anomali Belady adalah keadaan di mana page fault rate meningkat seiring dengan pertambahan jumlah frame

Sumber & referensi : 

https://www.google.co.id/amp/s/wunderbarerwelt.wordpress.com/2014/02/15/algoritma-fifo-optimal-dan-lru/amp/