Sistem Operasi

ALGORITMA PAGE REPLACEMENT

Terdapat    beberapa    algoritma    page    replacement,   setiap    sistem    operasi mempunyai skema yang unik.   Algoritma page replacement secara umum diinginkan yang   mempunyai   rata-rata   page   fault   terendah.               Algoritma   dievaluasi   dengan menjalankannya  pada  string tertentu  dari  memory reference  dan menghitung jumlah page fault.   String yang  mengacu ke memori disebut reference string (string acuan). String   acuan   dibangkitkan   secara   random   atau   dengan   menelusuri   sistem   dan menyimpan  alamat  dari  memori  acuan. Misalnya  jika  ditelusuri  proses  tertentu, disimpan alamat berikut :

0100,  0432,   0101,   0612,   0102,   0103,   0104,

0101,  0611,   0102,   0103,   0104,   0101,   0610,

0102,  0103,   0104,   0101,   0609,   0102,   0105 dimana 100 byte per page direduksi ke string acuan :

1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

Untuk menentukan jumlah page fault untuk string acuan dan algoritma page- replacement tertentu, harus diketahui jumlah page frame tersedia juga harus diketahui. Semakin tinggi jumlah frame lebih tinggi, semakin rendah jumlah page fault.   Hal ini

Terdapat beberapa algoritma page replacement antara lain algoritma first in first our  (FIFO),  optimal  dan  least  recently  use  (LRU).                                      Pada  sub  bab  berikut  akan diilustrasikan algoritma page replacement tersebut dengan menggunakan string acuan7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

8.5.1.  Algoritma FIFO

Algoritma  FIFO  merupakan  algoritma  paling  sederhana. Algoritma  FIFO diasosiasikan dengan sebuah page bila page tersebut dibawa ke memori.  Bila ada suatu page yang akan ditempatkan, maka posisi page yang paling lama yang akan digantikan. Algoritma ini tidak perlu menyimpan waktu pada saat sebuah page dibawa ke memori.

Meskipun algoritma FIFO mudah dipahami dan diimplementasikan, performansi tidak selalu bagus  karena algoritma FIFO menyebabkan Belady’s anomaly.   Belady’s anomaly  mematahkan fakta bahwa untuk beberapa algoritma page replacement,  bila rata-rata  page  fault  meningkat,  akan  meningkatkan  jumlah  alokasi  frame.                                                                                       Sebagai contoh, jika menggunakan string acuan :1, 2, 3, 4, 1, 2, 5, 1, 2, 5, 1, 2, 3, 4, 5

8.5.2.  Algoritma Optimal

Algoritma   optimal   merupakan   hasil   penemuan   dari   Belady’s   anomaly. Algoritma  ini  mempunyai  rata-rata  page  fault  terendah.                         Algoritma  optimal  akan mengganti page yang tidak akan digunakan untuk periode waktu terlama.  Algoritma ini   menjamin  rata-rata  page  fault  terendah  untuk  jumlah  frame  tetap  tetapi  sulit implementasinya.  Ilustrasi dari algoritma optimal dapat dilihat pada Gambar 8-10.

8.5.3.  Algoritma Least Recently Use (LRU)

Algoritma   LRU  merupakan  perpaduan  dari  algoritma  FIFO  dan  optimal. Prinsip dari algoritma LRU adalah mengganti page yang sudah tidak digunakan untuk periode waktu terlama.  Ilustrasi algoritma LRU dapat dilihat pada Gambar 8-11.

Untuk mengimplementasikan algoritma LRU, digunakan dua model yaitu :

•    Counter : setiap entry tabel pagee diasosiasikan dengan sebuah “time-of-use” dan sebuah clock logika atau counter ditambahkan ke CPU.  Clock ini dinaikkan untuk setiap acuan ke  memori.   Jika sebuah acuan ke page dibuat, isi clock register di- copy ke time-of-use pada tabel page untuk page tersebut.

•    Stack : stack dari nomor page diatur.   Jika sebuah page digunakan acuan, maka page dihapus dari stack dan meletakkan pada top of stack.  Dengan cara ini, stack selalu  digunakan page dan bagian bawah untuk page LRU.   Implementasi   stack

untuk algoritma LRU diilustrasikan pada Gambar 8-12.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s