Algoritma pergantian page

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)
  

Pada algoritma ini ada pemberian status (2 bit : R dan M) untuk setiap page, berikut keterangannya:
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.