Algoritma Page Replacement Clock

Algoritma Clock merupakan hasil modifikasi dari algoritma FIFO yang kedua dan juga merupakan model lain dari algoritma page replacement second chance page, namun dalam implementasinya menggunakan 'circular queue' dengan page berbentuk lingkaran.

Model lain dari Algoritma Second-Chance⇒Circular Queue (Algoritma clock)

-Page dalam bentuk lingkaran

-Jika :

·         Nilai bit = 0, ganti page

·         Nilai bit = 1

ü  Ubah nilai bit=0

ü  Pointer bergerak ke page berikutnya searah jarum jam

Contoh

Cara Kerja Algoritma Clock

– Algoritma Clock menggunakan prinsip Second-Chance tapi dengan antrian yang berbentuk melingkar

– Pada antrian ini terdapat pointer yang menunjuk ke halaman yang paling lama berada di antrian.
– Ketika terjadi kesalahan halaman, halaman yang ditunjuk oleh pointer akan diperiksa bit acuannya seperti pada Second-Chance.
– Jika bit acuan = 0, halaman tersebut akan langsung diganti. Jika bit acuan = 1, bit acuannya diubah menjadi 0 dan pointer akan bergerak searah jarum jam ke halaman yang berada di sebelahnya.

Kelebihandan Kekurangan Algoritma Clock

a.                Kelebihan Algoritma Clock :

·         Algoritma yang paling sederhana, dengan skema proses yang meminta CPU mendapatprioritas.

b.               KekuranganAlgoritma Clock

·         Waiting time yang rata-ratanyacukup lama.

·         Terjadinyaconvoy effect, yaitudimana proses-proses menunggu lama untuk menunggu satu proses besar yang sedang dieksekusi oleh CPU.

Algoritma Clock Halaman (atau Clock saja) menggunakan prinsip Second-Chance tapi dengan antrian yang berbentuk melingkar. Pada antrian ini terdapat pointer yang menunjuk ke halaman yang paling lama berada di antrian. Ketika terjadi kesalahan halaman, halaman yang ditunjuk oleh pointer akan diperiksa bit acuannya seperti pada Second-Chance. Jika bit acuan = 0, halaman tersebut akan langsung diganti. Jika bit acuan = 1, bit acuannya diubah menjadi 0 dan pointer akan bergerak searah jarum jam ke halaman yang berada di sebelahnya. Penggunaan antrian berbentuk melingkar menyebabkan halaman tidak perlu dipindahkan setiap saat, yang bergerak cukup pointer saja. Meski pun algoritma second-chance sudah cukup baik, namun pada kenyataannya penggunaan algortima tersebut tidak efisien. Algoritma clock adalah penyempurnaan dari algoritma tersebut. Pada prinsipnya kedua algoritma tersebut sama, hanya terletak perbedaan pada pengimplementasiannya saja. Algortima ini menggunakan antrian melingkar yang berbentuk seperti jam dengan sebuah penunjuk yang akan berjalan melingkar mencari halaman untuk diganti.