Bab 6. Algoritma Ganti Halaman

Daftar Isi

Pendahuluan
Reference String
Algoritma FIFO (First In First Out)
Algoritma Optimal
Algoritma LRU (Least Recently Used)
Implementasi LRU
Algoritma Lainnya
Rangkuman
Rujukan

Pendahuluan

Ganti halaman dilakukan apabila terjadi page fault. Page fault bukan suatu jenis error yang fatal, page fault terjadi apabila ada halaman yang ingin diakses tetapi halaman tersebut tidak terdapat di dalam memori utama. Page fault pasti terjadi minimal satu kali saat pertama kali halaman itu ingin diakses.

Prinsip ganti halaman adalah sebagai berikut:

  1. Proses meminta halaman tertentu.

  2. Jika halaman berada di memori, tidak dilakukan ganti halaman.

  3. Jika halaman tidak berada di memori, maka:

    1. Jika ada frame kosong, maka halaman itu di-load ke dalam frame yang kosong tersebut.

    2. Jika tidak ada frame yang kosong, maka pilih halaman yang akan di-swap dengan menggunakan algoritma ganti halaman.

  4. Update tabel halaman dan table memori.

  5. Restart proses.

Gambar 6.1. Ilustrasi Swapping

Ilustrasi Swapping

Semakin banyak dilakukan swap, semakin sibuk pula CPU mengurus hal ini. Bila berkelanjutan, maka akan terjadi thrashing. Thrashing adalah keadaan di mana banyak terjadi page fault, sehingga mengakibatkan utilisasi CPU menurun drastis karena lebih sibuk mengurusi pergantian halaman daripada mengurusi proses.

Untuk menghindari hal ini, diperlukan pemilihan algoritma ganti halaman yang baik. Kriteria algoritma yang baik adalah:

  • Menyebabkan page fault rate yang rendah.

  • Tidak menyebabkan thrashing .

  • Tidak terlalu sulit untuk diimplementasikan.

Pada umumnya, semakin besar memori, semakin banyak pula jumlah frame-nya. Semakin banyak frame, semakin banyak pula jumlah halaman yang bisa masuk di memori, sehingga page fault rate menurun.

Rujukan

[Silberschatz2002] Abraham Silberschatz, Peter Galvin, dan Greg Gagne. 2002. Applied Operating Systems. Sixth Edition. John Wiley & Sons.

[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons.

[Tanenbaum1997] Andrew S Tanenbaum dan Albert S Woodhull. 1997. Operating Systems Design and Implementation. Second Edition. Prentice-Hall.

[WEBAmirSch2000] YairTheo AmirSchlossnagle. 2000. Operating Systems 00.418: Memory Management – http://www.cs.jhu.edu/ ~yairamir/ cs418/ os5/ . Diakses 29 Mei 2006.

[WEBEgui2006] Equi4 Software. 2006. Memory Mapped Files – http://www.equi4.com/mkmmf.html . Diakses 3 Juli 2006.

[WEBFunkhouser2002] Thomas Funkhouser. 2002. Computer Science 217 Introduction to Programming Systems: Memory Paging – http://www.cs.princeton.edu/ courses/ archive / spring02/ cs217/ lectures/ paging.pdf . Diakses 28 Juni 2006.

[WEBGottlieb2000] Allan Gottlieb. 2000. Operating Systems: Page tables – http://allan.ultra.nyu.edu/ ~gottlieb/ courses/ 1999-00-spring/ os/ lecture-11.html . Diakses 28 Juni 2006.

[WEBSolomon2004] Marvin Solomon. 2004. CS 537 Introduction to Operating Systems: Lecture Notes Part 7 – http://www.cs.wisc.edu/ ~solomon/ cs537/ paging.html . Diakses 28 Juni 2006.

[WEBWiki2006c] From Wikipedia, the free encyclopedia. 2006. Memory Management Unit – http://en.wikipedia.org/ wiki/ Memory_management_unit . Diakses 30 Juni 2006.

[WEBWiki2006d] From Wikipedia, the free encyclopedia. 2006. Page Fault – http://en.wikipedia.org/ wiki/ Page_fault . Diakses 30 Juni 2006.

[WEBWiki2006e] From Wikipedia, the free encyclopedia. 2006. Copy on Write – http://en.wikipedia.org/ wiki/ Copy_on_Write . Diakses 03 Juli 2006.

[WEBWiki2007] Wikipedia. 2007. Page Replacement Algortihm http://en.wikipedia.org/wiki/Page_replacement_algorithm . Diakses 4 April 2007.