Daftar Isi:
Pembahasan kita pada artikel ini akan mengarah kepada 3 buah algoritma yang memiliki nama FIFO, Optimal dan LRU.
Tiga buah algoritma yang pasti akan sering muncul bersama-sama, khususnya di saat mempelajari tentang sistem operasi.
Dari nama yang sudah berbeda, tentu saja ketiga algoritma tersebut memiliki karakteristik, kelebihan dan kekurangan yang berbeda pula.
Baca Juga:
Biar tidak lama, mari kita langsung saja bahas ketiganya.
Baca Juga:
Pendahuluan
Sebelum membahas lebih dalam tentang FIFO, optimal atau LRU, ketahuilah bahwa ketiganya memiliki hubungan dengan hal yang bernama demand paging.
Demand paging merupakan sebuah instruksi yang ada untuk menyempurnakan konsep memori virtual.
Sebuah konsep yang menggunakan memori sekunder untuk menyelesaikan proses yang tidak bisa dilakukan di memori utama.
Baca Juga:
Dengan kata lain menggunakan ruang tak terpakai di memori sekunder sebagai memori utama yang bersifat sementara.
Sedangkan demand paging adalah metode untuk mencari ruang kosong di penyimpanan sekunder agar bisa sebuah memori virtual.
Tujuannya sederhana, agar sebuah page bisa ditaruh dan instruksi di dalamnya bisa diproses.
Namun ada sebuah pertanyaan “Bagaimana jika tidak ada ruang yang tersisa di dalam memori sekunder tersebut?
Jawabannya akan ada sebuah page yang tergantikan posisinya, atau istilahnya page replacement.
Kemudian muncul pertanyaan lagi “Page yang mana yang akan diganti?”
Inilah tugas dari ketiga algoritma itu tadi, menyeleksi sebuah page yang akan digantikan tempatnya.
Selain itu terdapat juga istilah page fault yang artinya interupsi di saat sebuah page membutuhkan tempat di dalam memori.
Setiap algoritma memiliki karakteristik masing-masing, karena itu jumlah page fault yang muncul pasti akan berbeda untuk setiap algoritma.
Tidak ada algoritma yang lebih baik, beda jumlah page atau frame maka page fault yang terjadi bisa saja semakin bertambah atau semakin berkurang.
Supaya tidak bingung, frame adalah wadah dari suatu page dan frame dalam pembahasan kali ini berada pada memori virtual.
Sekiranya itu saja pendahuluan singkat tentang memori virtual, demand paging dan page replacement, sekarang kita lanjut ke pembahasan utama.
Pembahasan tentang FIFO, optimal dan LRU, kita mulai dahulu dari FIFO.
FIFO (First In – First Out)
Sesuai namanya, algoritma ini menggantikan page yang pertama kali masuk atau yang statusnya paling tua di dalam sebuah frame.
Algoritma ini sangat mirip dengan sistem antrian pada umumnya, siapa yang pertama datang, maka ialah yang akan mendapatkan layanan lebih dulu.
Hanya saja pada algoritma ini, page yang pertama datang adalah page yang akan tergantikan tempatnya.
Contoh Kasus
Ada 4 buah slot frame dengan referensi string pada page yang datang secara berurutan yaitu 1-2-4-3-5-4-5-6-3-1-2.
Gambar di bawah adalah hasil page replacement dengan FIFO, tanda x melambangkan page fault.
Berikut penjelasan dari gambar di atas.
Pertama page string 1 datang, karena frame masih tersedia, maka page tadi langsung mendapatkan frame dan terjadilah page fault.
Sampai page string 3, page fault sudah terjadi 4 kali, sesuai dengan jumlah frame.
Kemudian page string 5 datang, namun sekarang sudah tidak ada frame yang tersedia.
Maka algoritma FIFO akan mencari page yang “tertua” dan page string 1 adalah page yang terpilih.
Maka page yang terpilih itu akan digantikan menjadi page string 5, total page fault terjadi 5 kali.
Lanjut dengan kedatangan dari page string 4 dan 5.
Page fault tidak akan terjadi karena keduanya sudah berada di dalam frame.
Dengan kata lain, tidak ada page yang tergantikan.
Page string 6 datang, karena tidak ada yang identik dengannya di dalam frame, terjadilah page fault.
Dan page dengan status tertua saat ini adalah page string 2, maka tempat dari page string 2 akan menjadi milik page string 6.
Kemudian masuk page string 3, pertukaran tempat tidak terjadi karena page tersebut sudah berada di dalam frame.
Lalu page string 1 datang, karena tidak ada yang identik dengan dirinya di dalam frame, maka algoritma FIFO akan mencari page tertua.
Dan page string 4 terpilih sebagai page yang sudah tinggal paling lama di dalam frame.
Maka page string 4 digantikan oleh page string 1, page fault terjadi lagi.
Terakhir, page string 2 datang, karena tidak ada page yang identik dengannya di dalam frame.
Maka algoritma FIFO memilih page string 3 sebagai page tertua.
Page string 3 pun berubah menjadi page string 2, page fault kembali terjadi.
Total page fault terjadi 8 kali.
Optimal
Algoritma yang mungkin cukup membingungkan, karena algoritma ini seolah-olah melihat ke masa depan.
Jika terjadi page fault dan tidak frame yang tersedia, maka algoritma ini akan mencari page dengan status page yang paling lama akan dikerjakan.
Jadi page yang berada di posisi paling belakang di dalam antrian akan menjadi page yang terpilih.
Jikalau penjelasan singkat tadi masih bingung, maka langsung saja masuk ke contoh kasus berikut.
Contoh Kasus
Masih dengan jumlah frame dan juga antrian page dengan referensi string yang sama.
Hasil akhirnya sudah tertera pada gambar di bawah.
Silahkan simak penjelasan berikut.
Dari awal tersedia 4 frame kosong, lalu datanglah page-page secara berurutan dengan string 1, 2, 4 dan 3.
Sampai page keempat, frame yang tersedia masih ada, karena itu page fault terjadi 4 kali.
Lanjut ke page string 5, karena ia tidak ada di dalam frame, terjadilah page fault.
Algoritma optimal memilih page string 2 yang akan diambil tempatnya.
Karena page string 2 berada di antrian paling belakang.
Kemudian page string 4 dan 5 datang, tidak ada page fault karena keduanya sudah berada di dalam frame.
Lalu datang page string 6 dan terjadilah page fault, algoritma optimal memilih page string 5.
Pertanyaannya mengapa page string 5 yang terpilih?
Lihatlah bahwa page-page yang berada di dalam frame secara berurutan adalah 1, 5, 4 dan 3.
Page string 1 dan 3 berada di dalam frame, serta page string 3 berada di paling belakang.
Tetapi kenapa yang terpilih adalah page string 5?
Jawabannya karena page string 5 tidak ada di antrian.
Jika semua page yang diperiksa berada di dalam antrian, page yang paling belakanglah yang terpilih.
Namun apabila ada page yang tidak berada di dalam antrian, maka page tersebut yang akan terpilih.
Muncul pertanyaan baru, “Kenapa page string 5, bukan yang 4?”.
Padahal keduanya sama-sama tidak ada di antrian.
Jawabannya sederhana, page string 5 adalah page yang diperiksa duluan.
Lalu page string 3 dan 1 datang, karena keduanya sudah berada di dalam frame, maka tidak terjadi page fault.
Terakhir, page string 2 datang dan ia tidak ada di dalam frame, page fault terjadi.
Akhirnya page string 1 terpilih karena ia adalah page pertama yang ditemukan sebagai page yang tidak ada di dalam antrian.
Page fault terjadi sebanyak 7 kali.
LRU (Least Recently Used)
Least Recently Used berarti “Yang jarang terpakai”.
Maka jelas bahwa page yang akan terpilih adalah page yang paling lama sudah tidak diakses atau digunakan.
Jadi algoritma ini hampir mirip dengan algoritma FIFO.
Maka dari itu, dengan tujuan menghilangkan kebingungan, langsung saja kita lanjut ke contoh.
Contoh Kasus
Masih dengan kasus yang sama seperti dua algoritma sebelumnya.
Hasil akhir bisa kalian lihat pada gambar di bawah.
Dan berikut adalah penjelasannya.
Pertama, karena ada empat frame, maka sampai antrian keempat akan terjadi page fault sebanyak 4 kali.
Kemudian datang page string 5, algoritma LRU akan memilih page string 1.
Karena pada gambar berikut, terlihat bahwa page string 1 adalah page yang paling lama sudah diakses.
Baik kita lanjut dulu sampai menemukan kasus yang dapat menjelaskan perbedaan di antara FIFO dan LRU.
Datang page string 4 dan 5 secara berurutan, page fault tidak terjadi karena kedua page tersebut sudah berada di dalam frame.
Lalu datanglah page string 6 yang memicu terjadinya page fault, lalu algoritma LRU akan memilih page string 2.
Karena bisa kalian lihat pada gambar antrian berikut, page dengan string 2 adalah page yang paling lama sudah diakses.
Page string 3 datang dan tidak terjadi page fault karena ia sudah ada di dalam frame.
Kemudian datang page string 1, algoritma LRU akan memilih page string 4 sebagai page yang meninggalkan frame.
Hal ini sesuai jika kita lihat pada gambar berikut.
Dan terakhir, datang page string 2.
Mungkin pertama kita akan mengira algoritma LRU memilih page string 3 yang meninggalkan tempatnya.
Tetapi kenapa yang terpilih adalah page string 5?
Memang page string 3 adalah page yang paling lama berada di dalam frame.
Namun ingat, LRU bukan FIFO yang memilih berdasarkan usia tertua, melainkan memilih berdasarkan kapan terakhir page tersebut diakses.
Bisa kalian lihat pada gambar di bawah, di mana page string 5 adalah page yang paling lama telah diakses.
Karena page string 3 sempat masuk ke dalam frame setelah page string 5.
Itu dia perbedaan di antara LRU dan FIFO, semoga kalian bisa memahaminya.
Hasil akhir, antrian sudah habis dan page fault terjadi sebanyak 8 kali.
Rangkuman
Baik itu tadi sekiranya penjelasan tentang algoritma FIFO, Optimal dan LRU.
Maafkan jika mungkin kurang jelas penjelasannya dan masih ada yang salah ataupun kurang.
Sedikit saran, akan lebih mudah mempelajari hal ini melalui media lain khususnya melalui video.
Kesimpulannya, entah itu FIFO, optimal atau LRU, menurut penulis sama saja.
Karena dari ketiganya, tidak ada yang lebih baik ataupun lebih buruk untuk satu sama lain.
Karena jumlah frame yang ada, kuantitas page yang datang serta variasi page-page tersebut akan selalu menghasilkan hasil yang berbeda.
Silahkan perbanyak latihan dan mengerjakan contoh untuk pemahaman yang lebih baik lagi.
Sekian dan terima kasih.
