- Algoritma Penggantian Page Acak
Pada algoritma pergantian
page acak setiap kali terjadi page fault penggantian page di pilih
secara acak atau default. Teknik ini tidak memerlukan informasi
apapun untuk menentukan page yang di ganti tersebut. 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 Penggantian Page Optimal
Cara kerja dari algoritma
penggantian page optimal 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,
- Algoritma Penggantian Page NRU (Not-recently
Used)
Bit R : referenced (menyatakan page yang sedang diacu)
Bit R = 0 berarti sedang diacu
Bit R = 1 berarti tidak sedang diacu
Bit M : modified (menyatakan page telah dimodifikasi)
Bit M = 1 berarti dimodifikasi
Bit M = 0 berarti tidak dimodifikasi
Sehingga, page-page dapat dikelompokan menjadi 4 kelas page, yaitu:
- Kelas 0 (R=0, M=0) : tidak sedang diacu dan belum dimodifikasi
- Kelas 1 (R=0, M=1) : tidak sedang diacu tapi telah dimodifikasi
- Kelas 2 (R=1, M=0) : sedang diacu tapi belum dimodifikasi
- Kelas 3 (R=1, M=1) : sedang diacu dan sudah dimodifikasi
Berdasarkan pembagian
kelas tersebut diatas,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. Intinya adalah mengasumsikan kelas-kelas
bernomor lebih rendah akan baru akan di gunakan kembalil dalam waktu
relatif lama.
- Algoritma Penggantian Page FIFO (First-In,
First-Out)
Cara kerja algoritma ini
dimana page yang masuk lebih dulu maka akan keluar lebih dulu juga.
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.
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)
- Algoritma penggantian clock page (clock page replacement algorithm)
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.
Sekian penjelasan materi tentang
algoritma pergantian page dari saya semoga bermanfaat.
0 komentar:
Posting Komentar