A.
"MASALAH
SISTEM PAGING & PENGGANTIAN PAGE"
Pengertian sistem paging
Sistem paging
adalah suatu sistem manajemen pada sistem operasi yang mengatur program yang
sedang berjalan. Metode dasar dari
paging adalah dengan memecah memori fisikmenjadi blok-blok yang berukuran
tertentu yang disebut dengan frame dan memecahmemori logika menjadi bok-blok
yang berukuran sama dengan frame yang disebut page.
Istilah pada sistem paging
·
Alamat maya: alamat yang dihasilkan perhitungan
menggunakan index register, base register, segment register dan sebagainya.
·
Alamat nyata: Alamat di memori fisik.
·
Page: Unit terkecil virtual address space.
·
Page frame : Unit terkecil memori fisik.
·
Page fault : Exception untuk permintaan alokasi ‘page’
ke memori.
·
MMU (Memory Management Unit) : Chip/kumpulan chip yang
memetakan alamat maya ke alamat fisik.
Fungsi sistem paging
Untuk mengatasi
apabila suatu program lebih besar dibandingkan dengan memori utama adalah
dengan konsep overlay dan konsep memori maya(virtual memori),
ü Konsep overlay
·
Yang dimaksud konsep overlay Program dipecah menjadi
bagian-bagian (OverLay) yangdapat dimuat ke memori.
·
Overlay
yang belum diperlukan disimpan di Disk.
·
Overlay yang diperlukan akan dimuad ke memori.
ü Konsep memory maya
·
Konsep Memori Maya, yaitu kemampuan untuk mengalamati
ruang memori melebihimemori utama yang tersedia.
·
Istilah memori maya diasosiasikan dengan kemampuan
mengalamati memori melebihimemori yang tersedia.Konsep ini ditemukan
Fotheringham (1961) pada system computer Atlas di Universitas Manchester,
Inggris.
·
SO menyimpan bagian yang sedang digunakan (di memori)
dan sisanya di disk. Saatdiperlukan (bagian di disk), maka bagian di memori
segera disingkirkan diganti denganbagian di disk.
Contoh:
•Program
10Mb dapat berjalan di 2Mb.
•Memilih (secara hati-hati) sebesar 2Mb untuk dimuat ke memori.
•Bagian-bagian program di swap antara disk dan memori saat diperlukan.*
(Ditulis Anan Widiyanto 12.3.00046)
PENGGANTIAN PAGE
·
Saat terjadi page fault, maka harus diputuskan page
frame di memori fisik yang harus diganti.
·
Kinerja system akan baik jika page yang diganti dipilih
yang tidak sering digunakan.
·
Jika page yang diganti sering digunakan, maka page
tersebut akan dikembalikan, secepatnyayang berarti page fault berulang kali.
·
Banyaknya page fault akan menaikkan overhead
Macam-macam algoritma penggantian page
·
Acak,
·
Optimal,
·
NRU (Not Recently Used),
·
FIFO,
·
Modifikasi FIFO
·
LRU (Least Recently Used)
1.
Algoritma penggantian page acak
Pada algoritma ini setiap
terjadi page fault, page yang diganti dipilih secara acak. Pada algoritma ini
terdapat kemungkinan proses yang baru berjalan bias digantikan (diberhentikan
oleh proses lain) jadi sangat merugikan dan teknik ini sangat buruk, percobaan
menunjukkan rate page fault yang sangat tinggi ketika menggunakan teknikini
(sangat merugikan).•
2.
Algoritma penggantian
page optimal
Pada algoritma ini
memilih page yang baru terpakai untuk digantikan oleh string acuan terbaru.
3.
Algoritma penggantian page
LRU
Berdasarkan observasi,
page page yang digunakan pada beberapa instruksi terakhirberkemungkinan besar
akan dipakai kembali nantinya. Page-page yang lama tidakdigunakan akan tetap
tak digunakan dalam waktu lama. Pada algoritma ini ketika terjadipage fault
maka memindahkan page yang tak digunakan paling lama.
4.
Algoritma penggantian page
FIFO
Algoritma ini dapat memilih
memindahkan page yang sering digunakan yang telah berada dimemori untuk waktu
yang lama.
(Ditulis Adi Suwanto 12.3.00043)
ISU DISAIN SISTEM PAGING
1. Model
Working Set
Ø Dalam bentuk paging murni, proses dimulai dengan memori kosong, dan
page-page dimasukkan ke dalamnya setelah diminta. Cara ini disebut demand paging.
Ø Locality of reference: Kecenderungan proses untuk memakai satu set page yang sama selama
beberapa saat.
Ø Satu set page tersebut di atas membentuk working set. Dalam hal ini, yang diusahakan oleh sistem operasi
adalah agar working set berada utuh di memori pada saat eksekusinya.
Ø Jika ukuran memori terlalu kecil untuk working set,
akan seringkali terjadi page fault. Hal ini
disebut thrashing.
Ø Banyak sistem paging yang mengusahakan agar working set sudah ada di
memori sebelum proses dimulai.
Pendekatan ini disebut model working set.
Tujuannya adalah untuk memperkecil jumlah terjadinya page fault (page yang
diminta tidak ada di memori).
Ø Memasukkan page ke memori sebelum proses dimulai juga disebut prepaging.
Ø Untuk pertama kali menentukan working set, dipakai sistem aging untuk mengetahui berapa kali
jumlah pemakaian setiap page.
2. Alokasi Global dan Lokal
o
Pada sistem timesharing, isi memori bisa seperti pada Gambar a.
o Misalkan diminta page A6. Jika dikeluarkan A5
untuk memberi tempat ke A6, berarti dilakukan alokasi lokal. Bila yang dikeluarkan adalah B3, dilakukan
alokasi global.
o Algoritma lokal berhubungan dengan pemberian jumlah frame yang sama
untuk setiap proses, sementara algoritma global secara dinamis mengalokasikan
frame untuk proses yang berjalan.
|
|
Age
|
|
|
|
|
A0
|
10
|
A0
|
|
A0
|
|
A1
|
7
|
A1
|
|
A1
|
|
A2
|
5
|
A2
|
|
A2
|
|
A3
|
4
|
A3
|
|
A3
|
|
A4
|
6
|
A4
|
|
A4
|
|
A5
|
3
|
A5 -> A6
|
|
A5
|
|
B0
|
9
|
B0
|
|
B0
|
|
B1
|
4
|
B1
|
|
B1
|
|
B2
|
6
|
B2
|
|
B2
|
|
B3
|
2
|
B3
|
|
B3 -> A6
|
|
B4
|
5
|
B4
|
|
B4
|
|
B5
|
6
|
B5
|
|
B5
|
|
B6
|
12
|
B6
|
|
B6
|
|
C1
|
3
|
C1
|
|
C1
|
|
C2
|
5
|
C2
|
|
C2
|
|
C3
|
6
|
C3
|
|
C3
|
(a) (b) (c)
Penggantian page global vs. lokal. (a) Konfigurasi awal.
(b) Penggantian page lokal. (c) Penggantian page global.
(Ditulis Yuyut Yanegar 12.3.00039)
3. Ukuran
Page
o
Ukuran page merupakan salah satu parameter yang ditentukan oleh perancang
sistem operasi.
o
Penentuan ukuran page yang optimum harus menyeimbangkan beberapa faktor.
o
Rata-rata, page terakhir hanya akan terisi setengah (fragmentasi internal),
berarti page sebaiknya kecil. Tetapi page yang kecil akan menghasilkan tabel
page yang panjang.
Ø
s (byte) = ukuran proses rata-rata
Ø p (byte) = ukuran page
Ø
e (byte) = ukuran setiap page entry
Ø s/p = perkiraan jumlah page yang dibutuhkan
per-proses
Ø se/p (byte) = ruang
untuk tabel page
Ø
p/2 = memori yang terbuang karena fragmentasi
Ø overhead = memori yang terpakai untuk tabel page dan
fragmen internal.
overhead = se/p + p/2
Ø
Ukuran tabel page
besar jika ukuran page kecil. Fragmen internal besar jika ukuranb page besar. Optimum harus ada di antaranya. Dengan mengambil penurunan pertama
terhadap p dan menyemakan dengan nol: -se/p2
+ ½ = 0
Ø Dari persamaan ini, ukuran page optimum adalah: p
= Ö(2se)
Ø
Sebagian besar komputer komersial menggunakan ukuran page antara 512 byte –
8K.
4. Isu
Implementasi
Ø Instruction backup
Instruksi yang menyebabkan referensi ke page yang belum ada di memori
(menyebabkan page fault) harus diulang ketika page tersebut telah tersedia.
Beberapa sistem operasi meng-copy setiap instruksi sebelum dilaksanakan
sehingga hal ini tidakmakan waktu terlalu lama.
Ø Locking pages in memory
Pada saat satu proses menjalani tahap I/O, proses
lain bisa dijalankan. Yang mungkin terjadi ialah page proses I/O tersebut
digantikan oleh proses yang kedua ini (jika dipakai alokasi global). Jalan
keluarnya ialah dengan me-lock page-page proses I/O.
Ø Shared pages
Dua atau lebih proses bisa memakai bersama page-page yang berasal dari
editor yang mereka pakai. Penutupan salah satu proses ini tanpa disengaja bisa mengosongkan juga page
yang dipakai bersama tersebut. Diperlukan suatu struktur data khusus untuk
memantau page-page yang dipakai bersama ini.
Ø Backing Store
Pada disk, disediakan area untuk menampung page yang dikeluarkan dari
memori (paged out) yang disebut swap area. Setiap proses memiliki swap area di
disk. Swap area ada yang statis ada juga yang dinamis.
Ø Paging Daemon
Untuk meyakinkan tersedianya frame bebas yang cukup banyak, banyak
sistem paging yang menggunakan proses background yang disebut paging daemon.
Jika jumlah frame bebas terlalu sedikit, paging daemon akan mengosongkan
beberapa page setelah menulisnya ke disk jika pernah dimodifikasi.
Ø Penanganan Page Fault
Urutan
langkah-langkah penanganan adalah sebagai berikut:
1. Hardware
melakukan trap ke kernel, program counter di-save ke stack. Pada banyak mesin,
beberapa informasi tentang status instruksi saat itu di-save di
register-register khusus CPU.
2. Rutin
kode assembly dimulai untuk men-save register-register umum dan informasi lain
yang bisa berubah, agar sistem operasi tidak merusaknya. Rutin ini memanggil
sistem operasi sebagai suatu prosedur.
3. Sistem
operasi menemukan bahwa terjadi page fault, dan mencoba menemukan page virtual
mana yang diperlukan. Seringkali salah satu register hardware berisi informasi
ini. Jika tidak, sistem operasi harus menarik program counter, mengambil
instruksi, dan melakukan parsing pada software untuk mengetahui apa yang
dilakukan sebelum terjadi fault.
4. Begitu
alamat virtual yang menyebabkan fault diketahui, sistem operasi memeriksa
apakah alamat ini valid dan proteksinya konsisten dengan akses. Jika tidak,
proses dikirimi sinyal atau ditutup. Jika alamat valid dan tidak ada
pelanggaran proteksi, sistem berusaha untuk mendapatkan frame page dari daftar
frame bebas. Jika tidak ada frame yang bebas, dijalankan algoritma penggantian
page untuk mencari yang bisa ditukar.
5. Jika
frame page yang dipilih telah dimodifikasi, page dijadwalkan untuk ditransfer
ke disk, dan terjadi pertukaran proses, menghentikan sementara proses yang
fault dan membiarkan yang lainnya berjalan hingga transfer disk selesai. Frame
ditandai terpakai untuk mencegah dipakai untuk tujuan lain.
6. Begitu
frame page bersih (apakah langsung atau setelah disave ke disk), sistem operasi
menelusuri alamat disk di mana page diperlukan, dan menjadwalkan operasi disk
untuk memasukkannya. Sementara page
dimasukkan, proses yang mengalami fault dihentikan sejenak dan yang lainnya
dijalankan, jika ada.
7. Ketika disk interrrupt menandai bahwa page telah ada, tabel
page di-update untuk menunjukkan posisinya, dan frame ditandai berada dalam
status normal.
8. Instruksi yang menyebabkan fault di-back-up ke status mulainya
dan program counter di-reset untuk menunjuk ke instruksi tersebut.
9. Proses yang fault tersebut dijadwalkan, dan sistem operasi
kembali ke rutin bahasa assembly yang memanggilnya.
10. Rutin ini mengembalikan register dan informasi lainnya ke
keadaan semula , dan kembali ke user untuk melanjutkan eksekusi, seakan-akan
tidak ada fault yang terjadi.*
(Ditulis Wahyu Liyanto 12.3.00037)
B. SISTEM SEGMENTASI
Pengertian
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
segment berbeda-beda sampai panjang maksimun, perobahanpanjang segment terjadi
selama proses eksekusi.
Segment
stack bertambah ketika terjadi operasi push dan
turun saat operasi pop, dimana setiap segment merupakan ruang
alamat terpisah segment-segment dapat tumbuh dan mengkerut secara bebas tanpa
mempengaruhi yang lain.
Alamat terdiri dari dua bagian pada memori bersegment yaitu :
1. Nomor segment
2. Alamat pada segment ( offset ).
Segment dapat
berisi :
1. Prosedure
2. Array
3. Stack
4. Kumpulan variable skala.
Sistem Segmentasi
Sistem dengan
memori maya dengan segmentasi murni adalah alamat maya adalah offset
di segment, setiap proses mempunyai tabel segment dan pada saat proses
running alamat awal maya tabel dimuatkan ke register dasar. Nomor segment
digunakan mencari deskriptor segment di tabel segment yang menyediakan
alamat fisik awal dari segment, panjang dan bit-bit
proteksinya. Alamat fisik dihitung dengan menambahkan alamat dasar
segment ke alamat maya.
Keunggulan
sistem ini dimana segment-segment tersebut saling berhubungan dengan unit-unit
program, sehingga segment – segment indeal untuk proteksi dan pemakaian
bersama.
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.
Thrashing: peristiwa page fault yang sangat berlebihan.
Salah satu cara
menghindari thrashing adalah dengan menyediakan sebanyak
mungkin bingkai sesuai dengan kebutuhan proses. Untuk mengetahui berapa bingkai
yang dibutuhkan adalah dengan strategi working set. Strategi ini
dimulai dengan melihat berapa banyak bingkai yang digunakan oleh suatu
proses. Working set model mengatakan bahwa sistem hanya akan
berjalan secara efisien jika proses diberikan bingkai yang cukup, jika bingkai
tidak cukup untuk menampung semua proses maka suatu proses akan ditunda, dan
memberikan halamannya untuk proses yang lain.
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 disebutworking set.
Berdasarkan hal ini
terdapat dua teknik untuk memuatkan page, yaitu:
·
Prepaging, teknik memuatkan page-page lebih dulu sbelum
proses berjalan.
·
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.
Jika
total permintaan > total bingkai, maka akan terjadi thrashing.
Jika ini terjadi maka proses yang sedang berjalan akan diblok.
- Kebijaksanaan
penggantian local vs global
Terdapat dua pendekatan untuk mengganti page, yaitu:
·
Penggantian local adalah page yang dipilih untuk diganti
hanya pada partisi dimana proses diletakkan.
·
Penggantian global adalah page yang dipilih untuk diganti
adalah tempat kosong dengan tidak mempedulikan partisi proses. Dengan
penggantian global, page fault suatu proses dapat dilayani dengan memindahkan
page yang dimiliki proses lain.
- Frekuensi
page fault
Frekuensi terjadinya
page fault dapat dikendalikan dengan algoritma PFF (page fault frequency
algorithm). Dengan PFF harus didefinisikan ambang batas dan ambang bawah
frekuensi page fault. Bila proses melampaui ambang batas frekuensi page fault
maka dialokasikan lebih banyak page memory fisik untuk prose situ. Apabila
proses telah mancapai amabang bawah frekuensi page fault maka alokasi page
dihentikan.
- Ukuran
page
Ukuran page
ditentukan oleh perancang system operasi.. ukuran page harus ditentukan agar
system berperilaku optimal. Beberapa pertimbangan, antara lain:
·
Ukuran page lebih kecil berarti jumlah page dan page frame
lebih banyak sehingga memerlukan table page lebih besar.
·
Ukuran page besar, berarti sejumlah informasi yang tidak
diacu juga dimasukkan ke memory utama sehingga terjadi fragmentasi internal
yang tinggi.
·
Transfer masukan/ keluaran relative sangat mengkonsumsi
waktu sehingga perlu meminimumkan Transfer masukan/ keluaran saat program
berjalan.
·
Program cenderung mengikuti prinsip lokalitas yang cenderun
berukuran kecil.
(Ditulis Jovie Tofan L 12.3.00025)
