Algoritma Pergantian Halaman

Algoritma Pergantian Halaman Kelompok 116-34 Jaka Ramdani (1204000483) Hera Irawati (1202000532) Renza Azhari (1202000826)

Silahkan menggandakan dan menyebarluaskan slide ini tanpa menghilangkan nota hak cipta ini. Kelompok 11634

Overview       

Latar belakang Algoritma First In First Out (FIFO) Algoritma Optimal Algoritma Least Recently Used (LRU) Algoritma NRU (Not Recently Used) Algortima Page Buffering Other Algorithm:    



Algoritma Not Frequently Used (NFU) Algoritma Aging Algoritma Second-Chance Algoritma Clock Page

Summary Silahkan menggandakan dan menyebarluaskan slide ini tanpa menghilangkan nota hak cipta ini. Kelompok 11634

Latar Belakang  

Memilih halaman yang akan digantikan Meminimalkan jumlah kesalahan halaman (page fault) 



Makin banyak frame yang tersedia makin sedikit kemungkinan terjadi kesalahan halaman

Meningkatkan utilisasi CPU dan throughput


Algoritma First In First Out (FIFO)  

  

Prinsipnya adalah mengantri Halaman yang diganti adalah halaman yang paling lama berada di memori Diimplementasikan dengan FIFO Queue Lebih murah Kelemahan: 



Mungkin membuang halaman yang penting  page in memory the longest may be often used Menimbulkan anomali Belady  page fault bertambah ~ jumlah frame meningkat Silahkan menggandakan dan menyebarluaskan slide ini tanpa menghilangkan nota hak cipta ini. Kelompok 11634

Algoritma Optimal  





Halaman yang diganti adalah halaman yang tidak akan digunakan untuk waktu yang lama The best possible page replacement algorithm  page fault rate-nya paling rendah Tidak dapat diimplementasikan  tidak mungkin mengetahui halaman yang akan diakses berikutnya Digunakan untuk mengevaluasi algoritma pergantian halaman


Algoritma Least Recently Used (LRU) 

Asumsi: halaman yang sering digunakan akan digunakan kembali dalam waktu dekat 



Mengganti halaman yang sudah lama tidak digunakan

Dua kemungkinan implementasi: 

Stack  Stack menandakan halaman-halaman di memori  Halaman yang diganti yang berada di paling bawah stack  Lebih mahal <= update isi stack setiap kali mengakses halaman


Cont… 

Counter 



Counter atau logical clock pada setiap page table entry (initial value = 0) Counter bertambah setiap kali halaman diakses  





Membutuhkan extra write to memory Ubah counter kembali 0 secara periodik

Halaman yang diganti adalah halaman yang memiliki nilai terkecil Sedikit sekali mesin yang mendukung hardware counter


Algoritma NRU (Not Recently Used)  

Ada bit acuan dan bit modifikasi yang di-update setiap kali mengakses halaman Pembagian kelas untuk setiap halaman berdasarkan bit acuan dan bit modifikasi tiap kali ada page fault    

 

Kelas 0: tidak diakses, tidak dimodifikasi Kelas 1: tidak diakses, dimodifikasi Kelas 2: diakses, tidak dimodifikasi Kelas 3: diakses, dimodifikasi

Ganti halaman dari kelas yang paling rendah secara acak Lebih mementingkan halaman yang diakses daripada halaman yang dimodifikasi


Algoritma Page Buffering  



Frame kosong sebagai pool/buffer Ketika terjadi page fault, halaman yang ingin dibaca dimasukkan ke dalam frame kosong. Plus 



Proses dapat dengan cepat dikembalikan ke ready queue

Minus 

Less pages are in use overall Silahkan menggandakan dan menyebarluaskan slide ini tanpa menghilangkan nota hak cipta ini. Kelompok 11634

Other Algorithm… 

Algoritma Not Frequently Used (NFU) 

Setiap halaman memiliki counter (initially 0) 





Pada setiap clock interval, semua halaman yang pernah diakses pada interval tsb di-increment counter-nya dengan bit R, yang bernilai 0 atau 1 Halaman dengan nilai paling kecil akan diganti

Algoritma Aging 

Modifikasi dari algoritma NFU  

Bit counter digeser satu bit ke kanan sebelum ditambahkan bit R Bit R ditambahkan di paling kiri Silahkan menggandakan dan menyebarluaskan slide ini tanpa menghilangkan nota hak cipta ini. Kelompok 11634

Cont… 

Algoritma Second-Chance  Modifikasi dari algoritma FIFO   

Ada bit acuan yang bisa bernilai 0 atau 1 Bit acuan = 0  halaman dapat diganti Bit acuan = 1  pindahkan halaman ke akhir antrian, ubah bit acuan jadi 0

Tidak efisien; selalu memindahkan halaman dalam antrian Algoritma Clock Page  Penyempurnaan second-chance dengan circular queue  Ada pointer yang menunjuk ke oldest page  Cek bit acuan pada halaman yang ditunjuk pointer 




Summary 

Pendekatan untuk pemindahan halaman: "Jika tidak ada frame yang kosong, cari frame yang tidak sedang digunakan atau yang tidak akan digunakan dalam jangka waktu yang lama, lalu kosongkan dengan memindahkan isinya ke dalam ruang pertukaran dan ubah semua tabelnya sebagai indikasi bahwa halaman tersebut tidak akan lama berada di dalam memori."


Algoritma Pergantian Halaman

Recommend Documents