WORKING SET DAN MODEL SEGMENTASI
Working Set
Working set Model merupakan model lokalitas dari eksekusi proses.
Model ini menggunakan parameter (delta) untuk definisi working set
window. Kumpulan dari halaman dengan halaman yang dituju yang paling
sering muncul disebut working set. Berdasarkan hal ini terdapat dua teknik
untuk memuatkan page, yaitu:
1. Prepaging, teknik memuatkan page-page lebih dulu sbelum proses
berjalan.
2. Demand paging, teknik yang segera memuatkan page begitu page
dibutuhkan. Keakuratan Working set tergantung pada pemilihan jika
terlalu kecil tidak akan mewakilkan seluruh lokalitas, jika terlalu
besar menyebabkan overlap, jika tidak terbatas working set adalah
kumpulan halaman sepanjang eksekusi program.
Prinsip Lokalitas
Prinsip Lokalitas adalah proses-proses cenderung menunggu
penyimpanan
secara
tak
seragam,
mempunyai
pola-pola
sangat
setempat. Prinsip lokalitas diperoleh dari observasi, bukan dari kajian
teori. Prinsip lokalitas menunjukan kecenderunag perilaku lingkingan
sistem bukan tepat eksak. Terdapat dua jenis lokalitas yaitu :
1. Lokalitas Berdasarkan Waktu (Temporaal Locality)
Lokalitas
berdasarkan
waktu
adalah
proses
cenderung terkonsentrasi acuannya ke satu interval waktu
eksekusi yang dekat. Lokasi-lokasi penyimpana akan diacu
kembali ke masa datang. Observasi berikut mendukung
prinsip, antara lain :
a. Looping
NR41 |2
b. Subrutin
c. Stack, dan
d. Variabel-variabel yang digunakan untuk interasi dan
penjumlahan total.
2. Lokalitas Menurut Ruang (Spatial Lokality)
Lokalitas
berdasarkan
ruang
adalah
proses
cenderung terkonsentrasi acuannya ke satu kelompok data
yang berdekatan. Begitu suatu lokasi diacu, cenderung akan
mengacu lokasi-lokasi di dekatnya. Observasi
berikut
mendukung prinsip ini, yaitu :
a. Tranversal pada array
b. Eksekusi kode yang sekuen
c. Kecenderungan pemrogram menempatkan variabel
yang terkait saling berdekatan.
Working Set of Program Behavior
Himpunan kerja secara informal didefinisikan sebagai kumpulan
page proses yang secara aktif diacu. Selain itu akan terjadi aktifitas page
fault yang berlebihan yang disebut trashing, yaitu setelah hanya beberapa
instruksi terjadi page fault. Jika himpunan kerja terdapat di memori, proses
akan berjalan tan pa menyebabkan banyak page fault sampai proses
berpindah ke fase eksekusi yang [Link] masa depan tidak diketahui,
himpunan kerja program di definisikan menjadi himpunan page yang diacu
program selama satu interval waktu terakir.
Himpunan kerja dari program pada satu waktu pada pengacuan memori
ke-t adalah W(t,q) = {i e N |page i muncul pada rt+q+1, ... ,rt}
Dimana rt
: Pengacuan memori saat t.
W(t,q) : himpunan page yang diacu selama q pengacuan memori
terakir. Dengan kata lain, himpunan kerja adalah himpunan page yang
diacu dalam jendela ukuran q yang dibentuk menurut waktu.
Prinsip-prinsip Working Set Model
NR41 |3
Prinsip yang digunakan adalah melacak dan menjamin himpunan
kerja terdapat di memori sebelum proses dijalenkan. Prinsip himpunan
kerja adalah [MIL-92] :
1. Program seharusnya dijalankan jika dan hanya jika himpunan kerja
berada di memori.
2. Pege tidak boleh dipindahkan dari memori.
Terdapat dua teknik untuk memuatkan page, yaitu :
1.
Prepaging.
Teknik memuatkan page-page lebih dulu sebelum
proses berjalan.
2.
Demand Paging.
Teknik yang segera memuatkan page begitu
page dibutuhkan.
Kebijakan Penggantian Lokal vs Global
Terdapat dua pendekatan untuk mengganti page, yaitu :
1. Penggantian lokal adapah page yang dipilih untuk diganti hanya pada
partisi dimana proses diletakan.
2. Penggantian global adalah page yang dipilih untuk diganti adalah tempat
kosong.
Penggantian likal cenderung melokalisasi dampak alokasi ke
masing-masing
[Link]
global
meningkatkan
derajat
kebergantungan antara strategi penggantian dan alokasi.
Frekuansi Page Fault
Frekuensi terjadinya page fault dapat dikendalikan dengan
algoritma PFF(Page Fault Frequency algorithm). Dengan PFF harus
didefinisikan ambang atas dan ambang bawah frekuensi page fault.
Parameter PFF adalah P : Jumlah Frekuensi page fault per T.
P = 1/T
Dimana :
T : Waktu fault kritis
P : Dalam jumlah page fault per milidetik
NR41 |4
Ukuran Page
Ukuran page ditentukan perancang sitem operasi. Ukuran page
harus ditentukan agar sistem berperilaku optimal. Penentuan ukuran page
memerlukan penilaian antara lain :
1. Ukuran page lebih kecil berarti jumlah page dan page frame lebih
banyak.
2. Ukuran page besar berarti informasi yang tidak diacu dimasukan ke
memori utama.
3. Transfer masukan/keluaran relatif sangat mengkonsumsi waktu.
4. Program cenderung mengikuti prinsip lokalitas yang cenderung
berukuran kecil.
Konsep Segmentasi
Konsep segmentasi adalah user atau programmer tidak memikirkan
sejumlah rutin program yang dipetakan ke main memori sebagai array
linier dalam byte tetapi memori dilihat sebagai kumpulan segmen dengan
ukuran berbeda-beda, tidak perlu berurutan diantara segment tersebut.
Segmentasi adalah skema manajemen memori yang memungkinkan user
untuk melihat memori tersebut. Ruang alamat logika adalah kumpulan
segmen. Setiap segmen mempunyai nama dan panjang. Spesifikasi
alamat berupa nama segmen dan offset. Segment diberi nomor dan
disebut dengan nomor segmen (bukan nama segmen) atau segment
number.
Segmen
dibentuk
secara
otomatis
oleh
compiler.
Sebuah program adalah kumpulan segmen. Suatu segmen adalah unit
logika seperti program utama, prosedur, fungsi, metode, obyek, variabel
lokal, variabel global, blok umum, stack, tabel simbol, array dan lain-lain.
Arsitektur Segmentasi
Alamat logika terdiri dari dua bagian yaitu nomor segmen (s) dan
offset (d) yang dituliskan dengan <nomor segmen, offset> Pemetaan
NR41 |5
alamat logika ke alamat fisik menggunakan tabel segmen (segment table),
terdiri dari :
1. Segmen basis (base) berisi alamat fisik awal
2. Segmen limit merupakan panjang segmen
Seperti tabel page, tabel segmen dapat berupa register atau
memori berkecepatan tinggi. Pada program yang berisi sejumlah segmen
yang besar, maka harus menyimpan tabel page di memori.
1. Segment-table base register (STBR) digunakan untuk menyimpan
alamat yang menunjuk ke segment table.
2. Segment-table length register (STLR) digunakan untuk menyimpan
nilai jumlah segmen yang digunakan program.
3. Untuk alamat logika (s, d), pertama diperiksa apakah segment
number s legal (s <STLR), kemudian tambahkan segment number
ke STBR, alamat hasil (STBR + s) ke memori dari segment table.
Implementasi arsitektur segmentasi
Pemetaan dari alamat logika ke alamat fisik membutuhkan 2 acuan
memori untuk setiap alamat logika. Hal ini akan menurunkan kecepatan
sistem dengan faktor 2. Solusi standard yang digunakan adalah dengan
cache (atau associative register) untuk menyimpan entri tabel segmen
yang sering digunakan.
Contoh Segmentasi
Misalnya alamat logika dengan nomor segment 0 offset 88 akan
dipetakan ke alamat fisik 1400 + 88 = 1488 karena offset < limit (88 <
1000). Alamat logika dengan nomor segment 1 offset 412 akan terjadi
error karena offset > limit (412 > 400). Alamat logika dengan nomor
segment 2 offset 320 akan dipetakan ke alamat fisik 4300 + 320 = 4620
karena offset < limit (320 < 400). Kelebihan Segmentasi adalah sebagai
berikut :
1. Memudahkan penanganan struktur data yang berkembang
2. Kompilasi data tidak mempengaruhi data yang lain (relink)
3. Memudahkan penggunaan memori bersama
4. Memudahkan proteksi.
NR41 |6
Sedangkan kelemahan segmentasi adalah segmen memiliki ukuran
yang bervariasi sehingga menyulitkan penanganan pertumbuhan dinamis
fragmentasi eksternal
Tiap segmen memori berisi barisan linear alamat 0 sampai
maksimum. Panjang tiap segmen dapat berbeda sampai panjang segmen
maksimum. Panjang segmen dapat berubah selama eksekusi. Dalam
segmentasi memungkinkan pemrogram memandang memori berisi
banyak ruang alamat atau segmen.
Spesifikasi alamat pada memori bersegmen ada dua dimensi.
Alamat terdiri dari 2 bagian :
1.
Nomor segmen
2.
Alamat pada segmen itu (offset)
Segmen dapat berisi :
1.
2.
3.
4.
Prosedur
Array
Stack
Atau kumpulan variable skalar
Teknik segmentasi mempunyai keunggulan dibanding ruang alamat
tak bersegmen, yaitu :
1.
Menyederhanakan penanganan struktur data yang berkembang
2.
Kompilasi ulang independen tanpa mentautkan kembali (Relink)
seluruh program
3.
Memudahkan pemkaian memori bersama diantara proses-proses
4.
Memudahkan untuk proteksi
Berikut skema sistem kombinasi paging dan segementasi :
NR41 |7
Segmentasi Secara Murni
Segmen-segmen dapat berukuran berbeda dan dinamis. Pengacuanpengacuan memori berbentuk (nomor segmen, offset).
Alamat maya adalah offset di segmen. Tiap proses mempunyai tabel
segmen. Ketika proses running, alamat awal tabel dimuatkan ke register
dasar. Nomor segmen digunakan untuk mencari deskriptor segmen yang
menediakan alamat fisik awal segmen, panjangnya dan bit-bit proteksi.
Alamat fisik dihitung dengan menambahkan alamat dasar segmen ke
alamat maya.
Memori Maya dengan Segmentasi Murni
Perangkat keras memberikan pengacuan memori suatu segmen tertentu.
Pilihan segmen dapat dibuat dengan sembarang kombinasi tersebut:
Instruksi
Target dari suatu alamat (program atau data)
Status saat itu (proses,sistem dan interupsi)
Alamat maya adalah offset disegmen. Tiap proses mempunyai tabel
segmen. Ketika proses runnig, alamat awal tabel dimuatkan ke register
dasar. Nomor segmen digunakan untuk mencari deskriptor segmen di
tabel segmen yang menyediakan alamat fisik awal dari segmen, panjang
NR41 |8
dan bit-bit proteksinya. Alamat fisik dihitung dengan menambahkan alamat
dasar segmen ke alamat maya.
Keunggulan
Segmen-segmen
berkorespondensi
dengan
unit-unit
program,sehingga segmen-segmen ideal untuk proteksi dan pemakaian
bersama. Biasanya program hanya menggunakan beberapa segmen
sehingga hanya ruang kecil yang diperlukan. Informasi deskriptor dapat
disimpan di register di MMU.
Kelemahan
Segme-segmen berukuran bervariasi menyebabkan fragmantasi
eksternal dan sulit menyelesaikan pertumbuhan dinamis. Segmensegmen tidak memetakan blok-blok dist untuk memori maya secara alami.
Contoh sistem
Intel 80386 dapat mengimplementasikan segmentasi murni jika tiap
segmen kurang dari 1 Mbyte. Untuk segmen-segmen lebih besar,
panjangnya harus kelipatan dari 4 Kb. Intel 8 0386 juga menyediakan
mekanisme pagingdua tingkat.
Perbandingan Antara Segmentasi Dan Paging
Ada beberapa perbandingan yang terdapat antara Segmentasi dan
Paging diantaranya adalah:
1.
Segmentasi melibatkan programer (programer perlu tahu
teknik yang digunakan), sedangkan dengan paging, programer
tidak perlu tahu teknik yang digunakan.
2.
Pada segmentasi kompilasi dilakukan secara terpisah
sedangkan pada paging, kompilasinya tidak terpisah.
3.
Pada segmentasi proteksinya terpisah sedangkan pada
paging proteksinya tidak terpisah.
NR41 |9
4.
Pada segmentasi ada shared code sedangkan pada paging
tidak ada shared code.
5.
Pada segmentasi terdapat banyak ruang alamat linier
sedangkan pada paging hanya terdapat satu ruang alamat linier.
6.
Pada segmentasi prosedur dan data dapat dibedakan dan
diproteksi terpisah sedangkan pada paging prosedur dan data tidak
dapat dibedakan dan diproteksi terpisah.
7.
Pada segmentasi pengubahan ukuran tabel dapat dilakukan
dengan mudah sedangkan pada Paging pengubahan ukuran tabel
tidak dapat dilakukan dengan mudah.
8.
Segmentasi digunakan untuk mengizinkan program dan data
dapat dipecahkan jadi ruang alamat mandiri dan juga untuk
mendukung sharing dan proteksi sedangkan paging digunakan
untuk mendapatkan ruang alamat linier yang besar tanpa perlu
membeli memori fisik lebih.
Perbandingan Antara Paging dan Segmentasi
Pertimbangan
Perlunya pemrogram
Paging
TIDAK
Segmentasi
YA
BANYAK
YA
YA
TIDAK
YA
TIDAK
YA
menyadari bahwa
teknik ini dipakai
Berapa banyak ruang
alamat linier yang
terdapat?
Dapatkan total ruang
alamat melampaui
ukuran memori fisik?
Dapatkan prosedur
dan data dibedakan
dan diproteksi secara
terpisah?
Dapatkah tabel-tabel
yang mempunyai
fluktuasi ukuran
N R 4 1 | 10
diakomodasikan
dengan mudah?
Apakah pemakaian
TIDAK
YA
Untuk mendapatkan
Untuk memungkinkan
bersama prosedureprosedur antara
pemakai-pemakai
difasilitas?
Kenapa teknik ini
ditemukan?
Keuntungan lain dari segmentasi adalah menyangkut
masalah pembagian penggunaan kode atau data. Setiap proses
mempunyai tabel segmennya sendiri, dimana ini akan digunakan
oleh dispatcher untuk menentukan tabel segmen dari perangkat
keras yang mana akan digunakan ketika proses yang bersangkutan
di eksekusi oleh CPU. Segmen akan berbagi ketika anggota dari
elemen tabel segmen yang berasal dari dua proses yang berbeda
menunjuk ke lokasi fisik yang sama. Pembagian tersebut terjadi
pada level segmen, maka, informasi apa pun dapat dibagi jika
didefinisikan pada level segmen. Bahkan beberapa segmen pun
dapat berbagi, sehingga sebuah program yang terdiri dari beberapa
segmen pun dapat saling berbagi pakai.
Kelemahan sistem ini adalah dimana segment - segment
berukuran bervariasi menyebabkan fragmentasi eksternal dan sulit
menyelesaikan pertumbuhan dinamis. Segment-segment tidak
memetakan blok-blok disk untuk memori maya secara alami.
Keunggulan sistem ini dimana segment-segment tersebut saling
berhubungan dengan unit-unit program, sehingga segment
segment ideal untuk proteksi dan pemakaian bersama sama.
Segmentasi Secara sederhana segmentasi bisa diartikan sebagai
suatu ruang alamat atau segment yang berada di memori.
Segment-segment itu dalam keadaan independent. Setiap segment
berisi alamat 0 sampai maksimum secara linier. Panjang setiap
N R 4 1 | 11
segment berbeda-beda sampai panjang maksimun, perobahan
panjang segment terjadi selama proses eksekusi. Hubungan Work
Set Model Dengan Page Fault Untuk mencegah thrashing maka
kita harus mengatur tingkat page fault yang terjadi. Jika page fault
sering terjadi maka dibutuhkan bingkai yang lebih banyak, jika page
fault jarang terjadi maka bingkai yang ada terlalu banyak, maka
diperlukan batasan untuk menentukan batas atas dan batas bawah
dari frekuensi page fault. Jika melewati batas atas maka proses
mendapat alokasi bingkai baru, jika melewati batas bawah maka
bingkai akan didealokasi dari proses.
Dalam working set strategi jika melewati batas atas maka
harus ada proses yang ditunda dan bingkai yang bebas akan
distribusikan untuk proses dengan frekuensi page fault yang tinggi.
total bingkai, maka akan terjadi thrashing. Jika ini terjadi maka
proses yang sedang berjalan akan diblok. Prinsip Lokalitas hide
Terdapat 2 jenis jenis lokalitas:
1.
Lokalitas berdasarkan waktu (temporal locality), proses
cenderung terkonsentrasi acuannya ke satu intercal waktu
eksekusi yang dekat. Observasi berikut mendukung prinsip,
antara lain : Looping, Subrutin, stack dan variable-variabel
2.
yang digunakan untuk iterasi dan penjumlahan total.
Lokalitas berdasarkan ruang (spatial locality),
proses
cenderung terkonsentrasi acuannya ke satu kelompok data
yang berdekatan. Observasi berikut mendukung prinsip ini,
antara lain: traversal pada array, eksekusi kode yang
sekuen, kecenderungan pemrogram menempatan variable
yang terkait saling berdekatan.
N R 4 1 | 12