Thrashing
Jika suatu proses tidak memiliki frame yang cukup, walau pun kita memiliki kemungkinan untuk mengurangi banyaknya frame yang dialokasikan menjadi minimum, tetap ada halaman dalam jumlah besar yang memiliki kondisi aktif menggunakannya. Maka hal ini akan mengakibatkan kesalahan halaman. Pada kasus ini, kita harus mengganti beberapa halaman menjadi halaman yang dibutuhkan walau pun halaman yang diganti pada waktu dekat akan dibutuhkan lagi. Hal ini mengakibatkan kesalahan terus menerus.
Aktivitas yang tinggi dari paging disebut thrashing. Suatu proses dikatakan thrashing jika proses menghabiskan waktu lebih banyak untuk paging daripada eksekusi (proses sibuk untuk melakukan swap-in swap-out).
Penyebab Thrashing
Penyebab dari thrashing adalah utilisasi CPU yang rendah. Jika utilisasi CPU terlalu rendah, kita menambahkan derajat dari multiprogramming dengan menambahkan proses baru ke sistem.
Sejalan dengan bertambahnya derajat dari multiprogramming, utilisasi CPU juga bertambah dengan lebih lambat sampai maksimumnya dicapai. Jika derajat dari multiprogramming ditambah terus menerus, utilisasi CPU akan berkurang dengan drastis dan terjadi thrashing. Untuk menambah utilisasi CPU dan menghentikan thrashing, kita harus mengurangi derajat dari multiprogramming.
Kita dapat membatasi efek dari thrashing dengan menggunakan algoritma penggantian lokal atau prioritas. Dengan penggantian lokal, jika satu proses mulai thrashing, proses tersebut tidak dapat mencuri frame dari proses yang lain dan menyebabkan proses tersebut tidak langsung mengalami thrashing. Jika proses thrashing, proses tersebut akan berada di antrian untuk melakukan paging yang mana hal ini memakan banyak waktu. Rata-rata waktu layanan untuk kesalahan halaman akan bertambah seiring dengan makin panjangnya rata-rata antrian untuk melakukan paging. Maka, waktu akses efektif akan bertambah walau pun untuk suatu proses yang tidak thrashing.
Untuk menghindari thrashing, kita harus menyediakan sebanyak mungkin frame sesuai dengan kebutuhan suatu proses. Cara untuk mengetahui berapa frame yang dibutuhkan salah satunya adalah dengan strategi Working Set yang akan dibahas pada bagian 10.5.2 yang mana strategi tersebut dimulai dengan melihat berapa banyak frame yang sesungguhnya digunakan oleh suatu proses. Ini merupakan model lokalitas dari suatu eksekusi proses.
Selama suatu proses dieksekusi, model lokalitas berpindah dari satu lokalitas ke lokalitas lainnya. Lokalitas adalah kumpulan halaman yang secara aktif digunakan bersama. Suatu program pada umumnya dibuat pada beberapa lokalitas, sehingga ada kemungkinan dapat terjadi overlap. Thrashing dapat muncul bila ukuran lokalitas lebih besar dari ukuran memori total.
Model Working Set
Model
Working Set didasarkan pada asumsi
lokalitas. Model ini menggunakan parameter
(delta) untuk mendefinisikan jendela
Working Set.
Idenya adalah untuk menentukan
halaman yang dituju yang paling sering muncul.
Kumpulan dari halaman dengan
halaman yang dituju yang paling sering muncul
disebut
Working Set.
Working Set adalah
pendekatan dari program lokalitas.
Contoh 4-1. Tabel Halaman
Jika terdapat tabel halaman yang dituju dengan
isinya
1 3 5 7 2 5 8 9 dengan
|
Keakuratan
Working Set
tergantung pemilihan dari
:
Jika
terlalu kecil, tidak akan dapat mewakilkan
keseluruhan dari lokalitas.
Jika
terlalu besar, akan menyebabkan
overlap beberapa lokalitas.
Jika
tidak terbatas,
Working Set adalah kumpulan
halaman sepanjang eksekusi proses.
Jika kita menghitung ukuran dari
Working Set,
WWSi, untuk setiap proses pada sistem, kita hitung
dengan
D =
WSSi,
dimana D merupakan total
demand untuk
frame.
Jika total demand lebih dari total banyaknya frame yang tersedia (D > m), thrashing dapat terjadi karena beberapa proses akan tidak memiliki frame yang cukup. Jika hal tersebut terjadi, dilakukan satu pengeblokan dari proses-proses yang sedang berjalan.
Strategi Working Set menangani thrashing dengan tetap mempertahankan derajat dari multiprogramming setinggi mungkin.
Kesulitan dari model Working Set ini adalah menjaga track dari Working Set. Jendela Working Set adalah jendela yang bergerak. Suatu halaman berada pada Working Set jika halaman tersebut mengacu ke mana pun pada jendela Working Set. Kita dapat mendekati model Working Set dengan fixed interval timer interrupt dan reference bit.
Contoh:
= 10000 reference,
Timer interrupt
setiap 5000 reference.
Ketika kita mendapat interrupt, kita kopi dan hapus nilai reference bit dari setiap halaman. Jika kesalahan halaman muncul, kita dapat menentukan current reference bit dan 2 pada bit memori untuk memutuskan apakah halaman itu digunakan dengan 10000 ke 15000 reference terakhir.
Jika digunakan, paling sedikit satu dari bit-bit ini akan aktif. Jika tidak digunakan, bit ini akan menjadi tidak aktif.
Halaman yang memiliki paling sedikit 1 bit aktif, akan berada di working-set.
Hal ini tidaklah sepenuhnya akurat karena kita tidak dapat memberitahukan dimana pada interval 5000 tersebut, reference muncul. Kita dapat mengurangi ketidakpastian dengan menambahkan sejarah bit kita dan frekuensi dari interrupt.
Contoh: 20 bit dan interrupt setiap 1500 reference.
Frekuensi Kesalahan Halaman
Working-set dapat berguna untuk prepaging, tetapi kurang dapat mengontrol thrashing. Strategi menggunakan frekuensi kesalahan halaman mengambil pendekatan yang lebih langsung.
thrashing memiliki kecepatan kesalahan halaman yang tinggi. Kita ingin mengontrolnya. Ketika terlalu tinggi, kita mengetahui bahwa proses membutuhkan frame lebih. Sama juga, jika terlalu rendah, maka proses mungkin memiliki terlalu banyak frame. Kita dapat menentukan batas atas dan bawah pada kecepatan kesalahan halaman seperti terlihat pada gambar berikut ini.
Jika kecepatan kesalahan halaman yang sesungguhnya melampaui batas atas, kita mengalokasikan frame lain ke proses tersebut, sedangkan jika kecepatan kesalahan halaman di bawah batas bawah, kita pindahkan frame dari proses tersebut. Maka kita dapat secara langsung mengukur dan mengontrol kecepatan kesalahan halaman untuk mencegah thrashing.