Section Artikel
Pengertian Algoritma FIFO
Algoritma FIFO (First-In-First-Out) menjadi algoritma yang paling sederhana. Prinsip dari algoritma ini adalah seperti prinsip antrian, halaman yang masuk lebih dulu maka akan keluar lebih dulu. Algoritma ini menggunakan struktur data stack.
Algoritma FIFO adalah suatu metode pengelolaan atau penyusunan data di dalam suatu struktur data, di mana elemen atau data yang pertama kali masuk ke dalam struktur data akan menjadi yang pertama kali dikeluarkan atau diproses.
Konsep FIFO mirip dengan antrian dalam kehidupan sehari-hari, di mana orang yang pertama kali datang ke antrian akan dilayani atau diberi perhatian lebih dulu sebelum orang yang datang kemudian.
Dalam konteks komputasi, algoritma FIFO umumnya digunakan dalam berbagai aplikasi seperti antrian pesan, manajemen memori, manajemen sumber daya, dan lain sebagainya. Contoh yang paling umum adalah penggunaan dalam struktur data yang disebut “queue” (antrian). Dalam queue, data yang dimasukkan pertama kali akan dikeluarkan pertama kali.
Apabila tidak ada frame kosong saat terjadi page fault, maka korban yang dipilih adalah frame yang berada di stack paling bawah, yaitu halaman yang berada paling lama berada di memori.
Pada awalnya, algoritma ini dianggap cukup handal dalam mengatasi masalah pergantian halaman, sampai pada tahun 70-an, Belady menemukan keanehan pada algoritma ini yang dikenal kemudian dengan anomali Belady. Anomali Belady adalah keadaan dimana page fault rate meningkat seiring dengan pertambahan jumlah frame.
Dalam pemrograman, algoritma FIFO dapat diimplementasikan menggunakan struktur data seperti array atau linked list. Penting untuk memahami konsep FIFO karena algoritma ini dapat membantu mengatur antrian tugas atau data dalam berbagai skenario, dari pengolahan data hingga manajemen sumber daya dalam sistem komputer.
Berikut beberapa istilah yang ada dalam algoritma FIFO.
1. Antrian
Dalam manajemen antrian, algoritma FIFO diterapkan. Elemen yang pertama kali tiba dalam antrian akan menjadi yang pertama kali diambil atau dilayani. Ini adalah prinsip yang umum digunakan dalam situasi di mana prioritas antrian adalah berdasarkan urutan kedatangan.
2. Pengolahan Data
Algoritma FIFO sering digunakan dalam pemrosesan data yang harus diolah dalam urutan yang masuk. Misalnya, jika Anda memiliki beberapa tugas yang harus dijalankan oleh sistem, Anda dapat menggunakannya dalam antrian FIFO untuk memastikan bahwa tugas yang pertama kali masuk akan segera diproses.
3. Manajemen Memori
Dalam sistem operasi, algoritma FIFO digunakan dalam manajemen memori virtual. Ketika diperlukan untuk menggantikan data dalam memori, data yang pertama kali dimasukkan akan menjadi yang pertama kali digantikan.
4. Algoritma Pencarian
Algoritma FIFO juga dapat digunakan dalam algoritma pencarian seperti Breadth-First Search (BFS) dalam eksplorasi graf. Algoritma BFS mencari semua simpul pada tingkat yang sama sebelum beralih ke tingkat berikutnya, sesuai dengan prinsip FIFO.
Kelebihan Algoritma FIFO
Menurut Sri Budiono 2017, algoritma FIFO memiliki kelebihan diantaranya sederhana, overhead kecil, dan dapat mencegah starvation. Namun, secara lebih lengkap kelebihan yang ada pada algoritma FIFO yaitu:
1. Prediktabilitas
Algoritma FIFO dapat diprediksi dalam arti bahwa urutan penggantian halaman bersifat deterministik dan tidak bergantung pada pola atau riwayat penggunaan halaman.
2. Sederhana dan Mudah Dipahami
Konsep FIFO sangat sederhana, di mana data atau elemen yang pertama kali masuk adalah yang pertama kali dikeluarkan. Karena sederhananya ini, algoritma FIFO mudah dipahami oleh programmer dan mudah diimplementasikan.
3. Layanan yang Adil
Algoritma FIFO memastikan bahwa setiap elemen atau data mendapatkan perlakuan yang adil berdasarkan urutan kedatangannya. Ini bermanfaat dalam situasi di mana kesetaraan prioritas antar elemen sangat penting.
4. Digunakan dalam Manajemen Antrian
Algoritma FIFO sangat berguna dalam manajemen antrian, seperti pada sistem antrian pelanggan atau antrian pesan. Hal ini memungkinkan pelayanan atau pengolahan data berdasarkan prinsip “siapa yang datang lebih dulu, dilayani lebih dulu.
5. Implementasi dalam Pemrograman
Algoritma FIFO sering digunakan dalam implementasi struktur data seperti queue. Ini memungkinkan pengelolaan data yang masuk dan keluar secara efisien, dengan kompleksitas waktu O(1) untuk operasi enqueue (memasukkan data) dan dequeue (mengeluarkan data).
6. Penggunaan dalam Manajemen Memori
Dalam manajemen memori, algoritma FIFO dapat membantu dalam alokasi dan pembebasan memori. Ketika memori penuh, blok memori yang pertama kali dialokasikan adalah yang pertama kali dibebaskan saat diperlukan.
7. Kesesuaian dalam Beberapa Kasus Pengolahan Data
Di beberapa situasi, seperti manajemen cache atau penjadwalan proses dalam sistem operasi, algoritma FIFO dapat memberikan hasil yang dapat diterima. Meskipun mungkin tidak selalu memberikan kinerja terbaik dalam situasi yang lebih kompleks, namun dalam beberapa kasus sederhana, algoritma ini dapat cukup efektif.
Kekurangan Algoritma FIFO
Meskipun Algoritma FIFO (First-In-First-Out) memiliki banyak kelebihan, tetapi juga memiliki beberapa kekurangan yang perlu dipertimbangkan dalam penggunaannya. Berikut adalah beberapa kekurangan utama dari algoritma FIFO:
1. Batas Prioritas dan Urgensi Tidak Diperhitungkan
Algoritma FIFO tidak mempertimbangkan prioritas atau urgensi dari elemen yang masuk dalam antrian. Ini bisa menjadi masalah jika ada situasi di mana elemen-elemen tertentu harus diproses lebih cepat atau dengan prioritas lebih tinggi daripada yang lain.
2. Kelangkaan Sumber Daya Tidak Diatasi
Algoritma FIFO tidak mempertimbangkan ketersediaan sumber daya saat memilih elemen untuk diproses. Ini bisa menjadi masalah dalam situasi di mana sumber daya tertentu terbatas atau harus diatur dengan bijaksana.
3. Dapat Membawa Pada Starvation
Starvation terjadi ketika elemen-elemen tertentu terjebak dalam antrian dan tidak pernah diproses karena selalu ada elemen-elemen baru yang masuk. Algoritma FIFO dapat berpotensi menyebabkan starvation, terutama jika ada elemen dengan prioritas lebih tinggi yang selalu masuk setelah elemen-elemen biasa.
4. Tidak Selalu Optimal dalam Pengolahan Data
Dalam beberapa kasus, algoritma FIFO mungkin tidak menghasilkan hasil yang optimal dalam pengolahan data. Terkadang, urutan kedatangan tidak selalu mencerminkan urgensi atau kompleksitas elemen.
5. Tidak Efektif dalam Beberapa Skenario
Dalam situasi di mana diperlukan keputusan dinamis dan kompleks untuk memilih elemen yang akan diproses, algoritma FIFO mungkin tidak cukup efektif. Contohnya Round Robin atau Shortest Job First dapat memberikan hasil yang lebih baik.
6. Tidak Memperhitungkan Waktu Pemrosesan
Algoritma FIFO tidak mempertimbangkan waktu pemrosesan yang diperlukan untuk setiap elemen. Ini berarti elemen yang lebih kompleks atau memerlukan waktu pemrosesan yang lama akan diolah tanpa mempertimbangkan efisiensi.
7. Tidak Fleksibel
Karena sifatnya yang sederhana, algoritma FIFO mungkin kurang fleksibel dalam menangani situasi yang beragam. Dalam beberapa kasus, penggunaan algoritma yang lebih kompleks dan adaptif bisa lebih bermanfaat.
8. Kerentanan Terhadap Thrashing
FIFO mungkin rentan terhadap thrashing, yang terjadi saat sistem menghabiskan banyak waktu menukar halaman masuk dan keluar dari memori tanpa membuat kemajuan pada beban kerja yang sebenarnya. Ini terjadi ketika jumlah halaman yang dibutuhkan oleh beban kerja melebihi memori fisik yang tersedia, dan algoritma FIFO tidak mengelola pertukaran halaman secara efisien.
Contoh Algoritma FIFO
Contoh sederhana penggunaan algoritma FIFO adalah antrian pesan teks. Jika Anda menerima beberapa pesan teks, pesan pertama yang masuk ke dalam kotak masuk Anda akan menjadi yang pertama kali Anda lihat dan baca. Pesan-pesan yang masuk kemudian akan diurutkan sesuai dengan urutan waktu masuknya.
Contoh Lain
Pada data contoh diatas diketahui Proses Pz dan Py datang pada waktu yang bersamaan, sehingga diperlukan kriteria tambahan untuk memutuskan proses yang akan running. Misalnya setiap proses dilengkapi dengan skala prioritas, sehingga kalau diasumsikan 1 lebih baik dari 2, maka pada proses diatas Py mendapat prioritas lebih dahulu dibandingkan Pz.
FIFO VS LIFO
FIFO dan LIFO adalah dua konsep yang berbeda dalam pengelolaan data atau elemen dalam suatu struktur. FIFO adalah singkatan dari “First-In, First-Out,” yang dalam bahasa Indonesia berarti “Pertama Masuk, Pertama Keluar.”
Dalam FIFO, barang atau item yang pertama kali masuk ke dalam sistem akan menjadi yang pertama kali dikeluarkan atau dijual. Metode ini mensyaratkan bahwa stok yang lebih lama harus dikeluarkan sebelum stok yang lebih baru.
Oleh karena itu, harga dan nilai stok yang dikeluarkan atau dijual dihitung berdasarkan harga yang lebih lama saat barang tersebut masuk ke dalam persediaan.
Sedangkan, LIFO adalah singkatan dari “Last-In, First-Out,” yang dalam bahasa Indonesia dapat diterjemahkan sebagai “Terakhir Masuk, Pertama Keluar.” Konsep LIFO berarti bahwa stok yang terbaru atau terakhir masuk dianggap sebagai stok yang paling pertama dikeluarkan atau dijual.
Dalam hal ini, harga dan nilai stok yang dikeluarkan atau dijual dihitung berdasarkan harga yang paling baru saat barang tersebut masuk ke dalam persediaan.
Berikut terdapat beberapa perbedaan antara FIFO dan LIFO:
Perbedaan Utama
- FIFO memprioritaskan elemen yang pertama kali masuk, sedangkan LIFO memprioritaskan elemen yang terakhir masuk.
- FIFO sering digunakan dalam konteks antrian dan pengolahan data yang mengikuti urutan kedatangan, sedangkan LIFO lebih cocok untuk situasi di mana tindakan terakhir perlu diakses atau diproses lebih dulu.
- FIFO digunakan untuk memastikan perlakuan yang adil terhadap elemen yang masuk lebih dulu, sedangkan LIFO digunakan ketika tindakan terbaru mungkin lebih relevan atau harus diproses lebih dahulu.
Perbedaan secara spesifik antara FIFO dan LIFO.
1. Prinsip
- Pada FIFO, elemen atau data yang pertama kali masuk ke dalam struktur akan menjadi yang pertama kali dikeluarkan atau diproses.
- Pada LIFO, elemen atau data yang terakhir masuk ke dalam struktur akan menjadi yang pertama kali dikeluarkan atau diproses.
2. Contoh Kasus
- Pada FIFO, antrian pesan teks, manajemen antrian pelanggan, antrian tugas, manajemen memori, dan sebagainya.
- Pada LIFO, implementasi undo/redo dalam aplikasi pengolah kata, manajemen tumpukan (stack) pada pemrograman, dan sebagainya.
3. Implementasi Umum
- Pada FIFO, queue (antrian) dalam struktur data, seperti implementasi menggunakan array atau linked list.
- Pada LIFO, stack (tumpukan) dalam struktur data, seperti implementasi menggunakan array atau linked list.
4. Contoh Implementasi
- Pada FIFO, ketika Anda menerima pesan teks, pesan pertama yang masuk akan menjadi yang pertama kali Anda lihat. Dalam antrian pelanggan, pelanggan yang datang pertama kali akan dilayani lebih dulu.
- Pada LIFO, tumpukan pemrograman, fungsi atau instruksi yang terakhir dimasukkan akan dieksekusi pertama kali.
