Sistem Paging
A.
Memori Maya
Program
yang dijalankan harus dimuat di memori utama. Masalah muncul ketika program
lebih besar dibanding memori utama yang tersedia.
Terdapat
dua solusi maalah ini, yaitu:
1.
Overlay
2.
Memori maya ( virtual memori )
I.
Konsep Overlay
Program
dipecah menjadi bagian-bagian yang dapat dimuat memori, disebut overlay.
Overlay yang belum diperlukan (tidak sedang dieksekusi) disimpan di disk,
overlay ini dimuatkan ke memori begitu diperlukan (kode di overlay akan di
eksekusi).
Pertukaran
overlay masuk dan keluar memori dilakukan sistem operasi. Pembagian program
menjadi overlay-overlay dilakukan pemrograman. Pembagian program menjadi
potongan-potongan kecil dan modular menghabiskan banyak waktu.
Gambar
1 Struktur umum overlay
Teknik
overlay telah ditinggalkan karena teknik memori maya telah dapat
diimplementasikan dengan murah dan berkinerja bagus.
II.
Konsep memori maya
Memori
maya adalah kemampuan mengalamati ruang memori melebihi memori utama yang
tersedia. Konsep memori maya pertama kali dikemukakan Fotheringham pada 1961
untuk sistem komputer Atlas di Universitas Manchester, Inggris.
Gagasan
memori maya adalah ukuran gabungan program, data, dan stack melampaui jumlah
memori fisik yang tersedia. Sistem operasi dapat menyimpan bagian-bagian proses
yang sedang digunakan memori utama dan sisanya didisk.
Penggunaan
Program
10 Megabyte, dapat berjalan di mesin
2 Megabyte, yaitu memilih bagian
proses sebesar 2 Megabyte secara
hati-hati dan ditaruh di memori. Bagian-bagian proses di-swap antara disk dan
memori saat diperlukan secara otomatis oleh sistem operasi.
Memori Maya dan Multiprogramming
Memori
maya dapat dilakukan pada sistem multiprogramming.
Misalnya
-
10 prpgram 2 Mb dapat berjalan di memori
4 Mb.
Tiap
program dialokasikan 256 kilobyte dan
bagian-bagian proses di-swap masuk-keluar
memori begitu diperlukan.
Memori
maya meningkatkan efisiensi sistem multiprogramming.
Memori maya dan multiprogramming adalah
dua konsep yang saling melengkapi. Saat proses menunggu bagiaannya di-swap masuk ke memori, menunggu
selesainya operasi masukan/keluaran, proses di-block, jatah layanan pemroses
diberikan ke proses lain.
Prinsip berikut berlaku :
Kecepatan
maksimum eksekusi proses di memori maya dapat sama tapi tidak pernah melampaui
kecepatan eksekusi proses yang sama di sistem tanpa memori maya.
Memori
maya dapat dilakukan dengan tiga cara, yaitu :
1.
Paging
2.
Segmentasi
3.
Kombinasi paging dan segmentasi
B.
Deskripsi Sistem Paging
Sistem
paging mengimplementasikan ruang alamat besar pada memori kecil menggunakan index register, base register, segment
register, dan segment register,
dan lain-lain. Pemakai seolah mempunyai ruang memori sangat besar tanpa
mengelola overlay.
Beberapa
istilah pada sistem paging adalah
1.
Alamat maya (virtual address)
2.
Alamat nyata (real address)
3.
Page
4.
Page frame
5.
Page fault
6.
MMU
Alamat Maya
Alamat
maya adalah alamat yang dihasilkan perhitungan menggunakan index register, base register, segment register dan sebagainya.
Ruang alamat yang dibentuk alamat maya disebut ruang alamat maya (virtual address space), v. jumlah alamat pada V disimbolkan
dengan V. alamat maya ini yang diacu proses yang running.
Alamat Nyata
Alamat
nyata adalah alamat di memori utama fisik. Ruang alamat yang dibentuk alamat
nyata disebut ruang alamat nyata (real address
space), R. jumlah alamat pada R disimbolkan dengan R.
Pada
implentasi sistem memori maya, normalnya V >> R.
Page
Page
adalah unit terkecil virtual address space. Ruang alamat maya proses merupakan
kelipatan page yang berukuran sama.
Page Frame
Page
frame adalah unit terkecil memori fisik. Memori fisik secara konseptual dibagi
sejumlah unit berukuran tetap disebut page frame. Page frame sering juga
disingkat frame.
|
|
|
|
|
|
|
|
|
|
|
Memori maya Memori
nyata
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Gambar 2
Hubungan antara ruang alamat maya dan alamat fisik.
Page
Fault
Page
fault adalah exception untuk permintaan alokasi ‘page’ kememori dalam konteks
memori maya, page fault sering juga disingkat fault.
Memory
Management Unti ( MMU )
Chip
atau kumpulan chip yang memetakan alamat maya ke alamat fisik.
1. Pada
komputer tanpa memori maya, alamat langsung diletakkan ke bus dan menyebabkan
word memori fisik alamat itu dibaca dan ditulis.
2. Pada
komputer dan memori maya, alamat tidak diletakkan di bus secara langsung tapi
lewat MMU yang kemudian memetakan alamat maya ke alamat memori fisik.
Pada
pemroses modern, MMU sudah menyatu di pemroses (on-chip).
Bus
Gambar
3 Posisi dan fungsi MMU
Memori fisik
berisi sejumlah page frame yang memuat sebagian page-page. Terdapat mekanisme
translasi (penerjemahan) alamat (dilakukan MMU) untuk memetakan page maya ke
alamat fisik. Sistem memori maya mempunyai properti alamat-alamat kontigu
(berurutan) pada ruang alamat maya yang tidak harus kontigu di memori nyata.
Property ini disebut kontigu semu (artificial
contiguity).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
gambar 4 Kontigu semu
Pemakaian di bebaskan
berurusan dengan letak prosedur dan data
diposisikan di memori nyata.Pemogram dapat menulis program seperti biasa,yaitu
memperhatikan efisiensi algoritma dan struktur program,mengabaikan rincian
struktur perangkat keras.Dengan sistem maya,memori dapat di pandang sebagai
kontigu yang berukuran besar.
i.
MMU (Memory Managemen Unit)
MMU mempunyai fungsi sebagai berikut :
·
Pemetaan
memori maya ke memori fisik.
·
Bila
alamat memori yang diminta tidak tersedia di memor i fisik,MMU menerbitkan
exception adanya page-fault yang melewatkan ke sistem operasi untuk
menanganinya.
·
Skema Pemetaan
Pada komputer dengan
memori maya,alamat tidak di letakkan ke bus secara langsung tapi di lewatkan ke
MMU yang memetakan alamat maya ke alamat memori
fisik.Pemetaan dapat dirumuskan secara formal sebagai berikut :
Skenario pemetaan
|
Memori
nyata
|
Alamat
|
Memori maya
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7
|
5
|
X
|
X
|
0
|
1
|
6
|
3
|
X
|
4
|
X
|
X
|
X
|
2
|
X
|
X
|
0-4K
|
4K-8K
|
8K-12K
|
12K-16K
|
16K-20K
|
20K-24K
|
24K-28K
|
28K-32K
|
32K-36K
|
36K-40K
|
40K-44K
|
44K-48K
|
48K-52K
|
52K-56K
|
56K-60K
|
60K-64K
|
Gambar 5 Relasi antara alamat maya dan alamat fisik
Misalnya instruksi:
MOV
REG,oxo8
·
Alamat
maya 8 dikirim ke MMU
·
MU
mengetahui alamat 8 di page 0 (page 0 memuat alamat maya 0-4o95)
·
Dari
tabel,page 0 dipetakan ke frame 7 (page 7 adalah alamat fisik 28672-32768)
·
MMU
mentransformasikan alamat 8 sebagai (28672 + 8 = 28680)
·
MMU
mengeluarkan alamat 28680 ke Bus.
Papan memori tidak perlu mengetahui MMU, hanya bertanggung
jawab untuk memenuhi permintaan membaca atau menulis alamat 28680.
Misalnya intruksi :
MOV
REG,8192
Ditransformasi menjadi alamat
fisik 20480 karena alamat 8192 terdapat di page 2 dan dipetakan ke frame 5
(alamat fisik 20480-24576).
·
10.2.1.2 Implementasi Pemetaan
(Bagian Internal MMU)
Gambar 6 adalah
komponen internal MMU untuk sitem paging.
Nomor
page
|
Offset
|
Gambar 6 Komponen internal MMU
Komponen terpenting MMU adalah
1. Registrasi alamat maya
2. Tabel page
3. Registri alamat fisik
Registri
Alamat Maya
Menyimpan alamat maya
yang diacu
Nilai di register
alamat maya di bagi menjadi dua bagian,yaitu :
·
Sejumalah
bit berorder tinggi menyatakan nomor page maya
·
Bit-bit
sisa adalah offset alamat maya.
Tabel
Page
Tiap elemen tabel
sedikitnya berisi informasi berikut :
·
Present/absent
bit
Bernilai satu apabila
page dimemori fisik,bernilai 0 bila page tidak di memori fisik.
·
Nomor
page frame dimana page berada.
Registri
Alamat Fisik
Menyimpan alamat fisik
yang disinyalkan ke bus.
Nilai di
Register Alamat Fisik Dibagi Dua Bagian,Yaitu
·
Sejumlah
bit berorder tinggi menyatakan nomor
page frame
·
Bit-bit
sisa adalah offset alamat frame.
Alamat maya dipecah menjadi dua
yaitu
·
Nomor
page maya (bit-bit berorder tinggi)
·
Offset
Pemetaan
·
Nomor
page maya digunakan sebagai indeks ke tabel page untuk menemukan isian page
maya.
·
Dari
isian tabel page dapat diketahui apakah page dipetakan ke memori fisik (dengan
memeriksa present/absent bit)
·
Apabila
alamat terdapat di memori fisik maka
isian di tabel page memuat nomor page
Frame.Nomor page frame
di tabel
page di kopi sebagai bit-bit berorder tinggi di registri alamat fisik
dan di tambah offset di alamat maya.
·
Bila
alamat tidak ada di memori fisik maka
MMU menerbitkan page foult.
·
MMU
mengkopikan nomor page frame diisian tabel page dengan indeks nomor page ke registri alamat fisik dan menambah dengan
offset alamat maya.
Cara kerja ini dapat dilihat pada
gambar 7.
Gambar 10-7 Cara kerja pemetaan oleh MMU
Apabila ternyata nomor page tidak
ada di memori fisik,yaitu nilai present/absent bit di isian tabel page bernilai 0, MMU menerbitkan page-foult.Rangkaian aksi yang dilakukan adalah sebagai berikut :
1.
MMU
memperingatkan page tidak ada di memori fisik dan pemmroses tidak
melakukan trap ke sistem operasi,
disebut page-foult.
2.
Membebaskan
bagian page frame memori fisik yang
jarang digunakan dengan menyimpan page frame itu ke disk.
3.
Memasukan
page yang diacu ke bagian page frame yang dibebaskan.
4.
Mengkonsolidasi
pemetaan antara memori maya<->memory fisik.
Ketika terjadi page foult, sistem
operasi memilih frame di memori
fisikuntuk di ganti dengan page berguna yang akan masuk.
·
Jika
page yang diganti telah dimodifikasi,page harus ditulis ke disk.Page yang telah
dimodifikasi disebut dirty page.
·
Jika
page belum diubah (misalnya page yang berisi teks biner program).kopian di disk
masih up to date sehingga page tidak perlu ditulis di disk.
ii.
Tabel-tabel Paging
Pemakaian tabel page pada sistem
paging menimbulkan dua masalah utama,yaitu :
1.
Tabel
page dapat berukuran lusr biasa besar
2.
Pemetaan harus dilakukan secara tepat
Tabel
page dapat dapat berukuran luar biasa besar
Misalnya
:
·
Register alamat maya 32 bit.
·
Ukuran page 4 Kilobyte = 212
byte
Berarti terdapat 220 page(sejuta
page lebih),yaitu
Alamat maya 32 bit berarti memori dapat memuat
232 byte
Karena masing-masing page adalah 212 byte = 220 page
·
Register
alamat maya 64 bit
·
Ukuran page 4 Kilobyte
Berarti akan terdapat 242 page
Bila memori maya sangat
besar maka tidak mungkin menggunakan
satu tabel tunggal karena akan
diperlukan ukuran tabel sangat besar.
Solusi
Menggunakan tabel-tabel
bertingkat (serupa indeks bertingkat diterganisasi berkas)
Beberapa rancangan tabel paging untuk beragam sesuai sistem komputer,yaitu:
·
DEC
PDP-11 menggunakan panjang satu tingkat(one-level paging)
·
DEC VAX menggunakan paging dua tingkat(two-level paging)
·
SUN
SPARC menggunakan paging tiga
tingkat(three-level paging)
·
MOTOROLA
68030 menggunakan paging empat tingkat(four-level paging)
Pemetaan
Harus Dilakukan Secara Cepat
Pemetaan alamat
maya ke alamat fisik dilakukan setiap terjadi pengacuan memori.
Instruksi komputer biasanya
berbentuk :
Operator operand 1, operand
2,.....,operand_N
Pada tiap instruksi,setidaknya
terdapat 1 atau 2 operan . Operan-operan merupakan pengacuan ke memori karena operan disimpan di
memori berarti untuk satu instruksi sedikitnya terjadi 1 sampai 2 pengacuan
memori.Jika satu instruksi memerlukan
10ns, maka pemetaan harus dilakukan
beberapa ns saja agar tidak terjadi bottleneck.
Kesimpulan
Pada pemproses dengan memori
maya, pengelolaan page besar dan cepat merupakan konstrain utama perancangan
dan pembangunan pemproses.
10.2.3
Memori Asosiatif
Dari observasi
disimpulkan,sebagian besar program cenderung melakukan banyak pengacuan ke
sejumlah kecil page (prinsip lokalitas).Sebenarnya hanya sejumlah kecil elemen
tabel page yang sering dibaca.
Berdasarkan fakta ini,sistem
komputer dengan memori maya dapat
memanfaatkan sifat ini untuk mempercepat proses pengacuan tanpa
melibatkan tabel page.Sistem komputer dilengkapi perangkat pemetaan alamat maya
ke alamat fisik tanpa lewat tabel page.Perangkat ini disebut assosiatif (associative
memory) atau TLB(translation lookaside buffer).Perangkat
ini dapat dipasang di MMU.
Memori asosiatif berisi sejumlah
elemen tabel (antara 8 sampai 32 elemen) .Tiap elemen berisi informasi-informasi mengenai page,yaitu:
·
Nomor
page maya
·
Bit
W, untuk mencatat apakah page telah dimodifikasi.
·
Bit-bit proteksi
·
Nomor
page frame dari page maya
·
Dan
sebagainya
Mekanisme
Kerja Memori Asosiatif
Jika alamat maya dikirim ke MMU untuk penerjemahan, Perangkat keras
memeriksa apakah nomor page maya
terdapat dimemori asosiatif dengan membandingkan semua isian memori asosiatif
secara simultan (yaitu bersamaan atau paralel). Mekanisme paralel ini sangat
mempercepat.
·
Jika
ditemukan di memori asosiatif dan pengaksesan
tidak melanggar bit-bit proteksi,maka page frame langsung ditanngani
memori asosiatif tanpa melibatkan tabel
page.
·
Jika
page ditemukan di memori asosiatif tapi melanggar bit-bit proteksi,maka
diterbitkan protection fault.Proteksi ini juga dilakukan tabel page(bila isian tabel page dilengkapi bit-bit
proteksi).
·
Jika
nomor page maya tidak terdapat dimemori
asosiasi,maka MMU mencari di tabel page.Salah satu elemen memori asosiatif disingkirkan dan diganti elemen tabel page
yang ditemukan.Elemen yang disingkirkan
dan diganti elemen tabel page di
memori.Jika page itu kembali digunakan,maka hanya akan ditangani memori
asosiatif tanpa MMU.
Rasio pengacuan memori yang
hanya melalui memori asosiatif disebut hit
ratio.Semakin tinggi hit oleh :
·
Waktu
akses tabel page
·
Waktu
akses memori asosiatif
·
Nilai
hit-ratio
Kebanyakan sistem komputer modern
dilengkapi memori asosiatif.MIPS R 2000 merupakan sistem yang hanya mengandalkan memori asosiatif tanpa tabel page.MIPS R2000
adalah mesin RISC berunjuk kerja tinggi.
C. Penggantian Page
Saat terjadi page foult berarti
harus diputuskan page frame dimemori
fisik yang harus digant.Kinerja sistem
akan baik jika page yang diganti dipilih yang tidak akan digunakan di
masa datang. Jika page yang diganti akan kembali digunakan maka page akan
dikembalikan secepatnya yang berarti terjadi page foult berulang kali.Banyaknya
page foult menghasilkan banyak overhead.
Algoritma penggantian page antara
lain :
1.
Algoritma
penggantian page acak (random page replacement algorithm)
2.
Algoritma
penggantian page optimal
3.
Algoritma
penggantian page NRU
4.
Algoritma
penggantian page FIFO
5.
Algoritma
penggantian page modifikasi dari
algoritma FIFO
6.
Algoritma
penggantian page LRU
v
Algoritma-algoritma
Penggantian Page
-
Algoritma Penggantian Page Acak
Mekanisme algoritma
Setiap terjadi page foult,page yang diganti di
pilih secara aca.
Teknik ini tidak memakai informasi apapun dalam menetukan page yang diganti.Semua page dimemori utama
mempunyai bobot sama untuk dipilih.Teknik ini dapat memilih sembarang
page,termasuk page yang sedang diacu (page yang seharusnya tidak diganti,pilihan
terburuk).
Teknik ini sangat buruk,percobaan
menunjukan algoritma acak menimbulkan
rate terjadinya page foult yang sangat tinggi.
-
Algoritma Penggantian Page Optimal
Mekanisme algoritma
Dasar
algoritma ini adalah memilih page yang berpeluang dipakai kembali di masa
datang yang paling kecil.
Strategi ini akan menghasilkan
jumlah page-foult paling sedikit.Algoritma
ini adalah algoritma utopia
(ideal tanpa dapat dijadikan kenyataan) karena tak mungkin dibuat prosedur yang
dapat mengetahui peluang
pemakaian suatu page kembali ke masa datang. Metode ini tak mungkin diterapkan.
Pendekatan ini dapat dilakukan
dengan simulasi.Tapi simulasi hanya
spesifik suatu program.Bila yang terbaik
tak dimungkinkan,maka yang perlu dilakukan adalah berusaha mendekatinya.Algoritma
penggantian page diusahakan kinerjanya
mendekati optimal.
Algoritma prnggantian page
optimal penting untuk kajian teoretis,sebagai pembanding bagi
algoritma-algoritma penggantian
page yang lain.
-
Algoritma Penggantian Page NRU(Not-Recently
Used)
Mekanisme algoritma
Pada
algoritma ini,page diberi dua bit mencatat status page,bit R dan M,yaitu:
Bit
R : referenced (menyatakan page sedang
di acu)
Bit
R =
1 nerarti sedang di acu
Bit
R = 0 berarti tidak sedang di acu
Bit
M : modified (menyatakan page telah dimodifikasi)
Bit
M = 1 berarti dimodifikasi
Bit
M =
0 berarti tidak dimodifikasi
Dengan
2 bit,maka page-page dikelompokkan menjadi
4 kelas page,yaitu
Kelas
0 : Tidak sedang diacu,belum dimodifikasi
(R=0, M=0)
Kelas 1 : Tidak sedang diacu,telah
dimodifikasi (R=0, M=1)
Kelas 2 : Sedang diacu,belum dimodifikasi (R=1,
M=0)
Kelas 3 : Sedang diacu,telah dimodifikasi (R=1,
M=1)
·
Memilih
mengganti page kelas bernomor
terendah(bila terdapat page-page di kelas itu)secara acak.
·
Bila
kelas tersebut kosong maka dipilih page di kelas lebih tinggi, dan seterusnya.
Algoritma ini
mengasumsikan kelas-kelas bernomor lebih rendah baru akan digunakan kembali
dalam waktu relatif lama.
Algoritma ini mudah dipahami dan
diimplementasikan.Implementasi algoritma
ini sangat efisien karena tak banyak langkah dalam pemilihan
page.Algoritma ini memenag tidak optimal,tapi dalam kondisi-kondisi normal
telah memadai .
-
Algoritma Penggantian Page FIFO
(First-In,First-Out)
Mekanisme algoritma
Algoritma
ini memerlukan pengelolaan senarai page di memori.Elemen terdepan senarai
adalah page tertua dan ujung
belakang adalah page paling akhir datang.
·
Bila
terjadi page foult ,page elemen
terdepan (page tertua) di ganti dan page
baru ditambahkan di ujung belakang senarai .
-
Modifikasi
Terhadap FIFO
Kelemahan
FIFO adalah algoritma dapat memilih memindahkan page yang sering digunakan yang
lama berada di memori.
Variasi
FIFO yaitu :
1. Algoritma pergantian page
kesempatan kedua.
Mekanisme
algoritma :
·
Saat terjadi page-fault, algoritma
memilih page elemen terdepan diganti bila bit R bernilai 0.
·
Bila bit R bernilai 1, maka bit page
terdepan senarai direset menjadi 0 dan diletakkan ke ujung belakang senarai.
2. Algoritma penggantian clock-page.
Mekanisme
algoritma :
·
Pada algoritma ini, semua page merupakan
senarai melingkar membentuk pola jam.
Ketika
terjadi page fault, page yang ditunjuk diperiksa.
·
Jika bit R bernilai 0 maka page diganti.
Page baru ditempatkan di tempat page diganti dan penunjuk dimajukan satu posisi
ke page berikutnya.
·
Jika bit R bernilai 1 maka bit R diseret
menjadi 0 dan penunjuk dimajukan satu posisi dan seterusnya sampai menemui page
dengan bit R bernilai 0.
Kedua
algoritma adalah hanya terdapat perbedaan di implementasi, yaitu ;
·
Algoritma penggantian page kesempatan
kedua menggunakan senarai lurus tidak sirkular, sedangkan clock page
menggunakan senarai sirkular.
-
Algoritma
Penggantian Page LRU(Least Recently Used).
Mekanisme algoritma :
Algoritma
LRU adalah ketika terjadi page fault maka memindahkan page yang tidak digunakan
paling lama.
Masalah
: sangat mahal. Yaitu disebabkan harus mengelola senarai informasi seluruh page
di memori.
-
Contoh
Eksekusi Paging
Algoritma
penggantian page optimal (6 Fault)
String
pengacuan
|
|
2
|
3
|
2
|
1
|
5
|
2
|
4
|
5
|
3
|
2
|
5
|
2
|
|
|
2
|
2
|
2
|
2
|
2
|
2
|
4
|
4
|
4
|
2
|
2
|
2
|
|
|
3
|
3
|
3
|
3
|
3
|
3
|
3
|
3
|
3
|
3
|
3
|
|
|
|
|
|
1
|
5
|
5
|
5
|
5
|
5
|
5
|
5
|
5
|
|
Fault
|
|
F
|
F
|
|
F
|
F
|
|
F
|
|
|
F
|
|
|
Algoritma
penggantian page LRU (7 Fault)
String
pengacuan
|
|
2
|
3
|
2
|
1
|
5
|
2
|
4
|
5
|
3
|
2
|
5
|
2
|
|
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
3
|
3
|
3
|
3
|
|
|
3
|
3
|
3
|
5
|
5
|
5
|
5
|
5
|
5
|
5
|
5
|
|
|
|
|
|
1
|
1
|
1
|
4
|
4
|
4
|
2
|
2
|
2
|
|
Fault
|
|
F
|
F
|
|
F
|
F
|
|
F
|
|
F
|
F
|
|
|
Algoritma
penggantian page FIFO (9 Fault)
String
pengacuan
|
|
2
|
3
|
2
|
1
|
5
|
2
|
4
|
5
|
3
|
2
|
5
|
2
|
|
|
2
|
2
|
2
|
2
|
5
|
5
|
5
|
5
|
3
|
3
|
3
|
3
|
|
|
3
|
3
|
3
|
3
|
2
|
2
|
2
|
2
|
2
|
5
|
5
|
|
|
|
|
|
1
|
1
|
1
|
4
|
4
|
4
|
4
|
4
|
2
|
|
Fault
|
|
F
|
F
|
|
F
|
F
|
F
|
F
|
|
F
|
|
F
|
F
|
Algoritma
penggantian clock page (6 Fault)
String
pengacuan
|
|
2
|
3
|
2
|
1
|
5
|
2
|
4
|
5
|
3
|
2
|
5
|
2
|
|
>
|
2
|
2
|
2
|
>2*
|
2*
|
2*
|
>2*
|
>2*
|
>2
|
>2*
|
>2*
|
>2*
|
|
>
|
3
|
3
|
3
|
5
|
5
|
5
|
5*
|
5
|
5
|
5*
|
5*
|
|
|
|
>
|
>
|
1
|
>1
|
>1
|
4
|
4
|
3
|
3
|
3
|
3
|
|
Fault
|
|
F
|
F
|
|
F
|
F
|
|
F
|
|
F
|
|
|
|
Keterangan
: * diacu
>ditunjuk pointer
Memodelkan
Algoritma Paging
Anomaly
belady
Belady menemukan fenomena menyimpang dari prasangka
umum yaitu pada algoritma FIFO maka pada pola-pola pengacuan tertentu
menyebabakan lebih banyak page fault bila alokasi page untuk proses ditambah.
Fenomena ini disebut anomal belady.
Fenomena dapat diilustrasikan sebagai berikut :
·
Program dengan lima page
·
Urutan page yang diacu : 0 1 2 3 4 0 1 4
0 1 2 3 4
String
pengacuan
|
|
0
|
1
|
2
|
3
|
4
|
0
|
1
|
4
|
0
|
1
|
2
|
3
|
4
|
|
|
|
0
|
1
|
2
|
3
|
0
|
1
|
4
|
4
|
4
|
2
|
3
|
3
|
|
|
|
0
|
1
|
2
|
3
|
0
|
1
|
1
|
1
|
4
|
2
|
2
|
|
|
|
|
|
0
|
1
|
2
|
3
|
0
|
0
|
0
|
1
|
4
|
4
|
|
Fault
|
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
|
|
F
|
F
|
|
(a)
String
pengacuan
|
|
0
|
1
|
2
|
3
|
4
|
0
|
1
|
4
|
0
|
1
|
2
|
3
|
4
|
|
|
|
0
|
1
|
2
|
3
|
3
|
3
|
4
|
0
|
1
|
2
|
3
|
4
|
|
|
|
0
|
1
|
2
|
2
|
2
|
3
|
4
|
0
|
1
|
2
|
3
|
|
|
|
|
|
0
|
1
|
1
|
1
|
2
|
3
|
4
|
0
|
1
|
2
|
|
|
|
|
|
|
0
|
0
|
0
|
1
|
2
|
3
|
4
|
0
|
1
|
|
Fault
|
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
|
|
F
|
F
|
|
(b)
·
Gambar (a) dengan tipe page frame
menghasilkan 9 fault.
·
Gambar (b) dengan empat page frame
menghasilkan 10 fault.
v Mesin abstrak eksekusi program
Terdapat mesin abstrak
interpreter dengan property berikut :
1. Terdapat
array internal, M, menyimpan status memori. Array mempunyai n elemen seperti
proses mempunyai n page memori maya.
2.
Array M terbagi 2 :
·
Bagian atas/puncak, yaitu m isian, page
dimemori tujuan.
·
Bagian bawah/dasar berisi n-m isian,
yaitu semua page yang pernah diacu sekali tapi telah dipindahkan dan tidak dimemori
utama.
3. Mualanya
array M berupa himpunan kosong karena belum ada page yang telah diacu dan tak
ada page yang berada di memori.
Begitu
eksekusi dimulai, proses mulai mengeluarkan page sesuai string pengacuan, satu
page pada satu saat. Terhadap page itu, interpreter memeriksa apakah page
berada di memori(yaitu isian bagian puncak array M).
Contoh :
1. String
pengacuan : 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1
2.
Ruang alamat maya : 8 page
3. Algoritma
penggantian dengan LRU
String
pengacuan
|
|
0
|
2
|
1
|
3
|
5
|
4
|
6
|
3
|
7
|
4
|
7
|
3
|
3
|
5
|
5
|
3
|
1
|
1
|
1
|
7
|
2
|
3
|
4
|
1
|
|
|
0
|
2
|
1
|
3
|
5
|
4
|
6
|
3
|
7
|
4
|
7
|
3
|
3
|
5
|
5
|
3
|
1
|
1
|
1
|
7
|
2
|
3
|
4
|
1
|
|
|
0
|
2
|
1
|
3
|
5
|
4
|
6
|
3
|
7
|
4
|
7
|
7
|
3
|
3
|
5
|
3
|
3
|
3
|
1
|
7
|
2
|
3
|
4
|
|
|
|
|
0
|
2
|
1
|
3
|
5
|
4
|
6
|
3
|
3
|
4
|
4
|
7
|
7
|
7
|
5
|
5
|
5
|
3
|
1
|
7
|
2
|
3
|
|
|
|
|
|
0
|
2
|
1
|
3
|
5
|
4
|
6
|
6
|
6
|
6
|
4
|
4
|
4
|
7
|
7
|
7
|
5
|
3
|
1
|
7
|
2
|
|
|
|
|
|
|
0
|
2
|
1
|
1
|
5
|
5
|
5
|
5
|
5
|
6
|
6
|
6
|
4
|
4
|
4
|
4
|
5
|
5
|
1
|
7
|
|
|
|
|
|
|
|
0
|
2
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
6
|
6
|
6
|
6
|
4
|
4
|
5
|
5
|
|
|
|
|
|
|
|
|
0
|
0
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
6
|
6
|
6
|
6
|
|
|
|
|
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
Fault
|
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
|
F
|
|
|
|
|
F
|
|
|
F
|
|
|
|
|
|
F
|
|
Model ini mempunyai property yaitu :
1. Ketika
page diacu, selalu dipindahkan ke isian puncak dari array M.
2.
Jika page yang diacu ada di M, semua
page diatasnya dipindah satu posisi ke bawah. Transisi dari dalam kotak ke luar
berkorespondensi dengan page dipindahkan dari memori.
3. Page-page
yang dibawah page yang diacu, tidak dipindakhan.
Jika
kita tingkatkan ukuran memori dengan satu page maka setelah proses dieksekusi
kembali pada setiap titik eksekusi yang sama, semua page pada eksekusi pertama
juga terdapat pada eksekusi kedua dengan satu tambahan page. Algoritma
D. Masalah-Masalah Utama Pada System
Paging
1. Working set model
a)
Prinsip
lokalitas
Suatu
proses-proses yang cenderung mengacu penympanan secara tak seragam, mempunyai
pola-pola sangat setempat.
Ada
2 jenis lokalitas yaitu :
1.
Lokalitas
berdasar waktu
Lokalitas berdasar waktu adalah
proses cenderung terkonsentrasi acuannya ke satu interval waktu eksekusi yang
dekat. Observasi berikut mendukung prinsip :
·
Looping
·
Subrutin
·
Stack dan variable-variabel yang
digunakan untuk iterasi dan penjumlahan total.
2.
Lokalitas
berdasar ruang
Lokalitas berdasar ruang adalah proses cenderung
terkonsentrasi acuannya ke satu kelompok data yang berdekatan. Observasi
berikut mendukung prinsip ini :
·
Traversal pada array
·
Eksekusi kode yang sekuen
·
Kecenderungan pemrogram menempatkan
variable yang terkait saling berdekatan.
Konsekuensi
Konsekuensi prinsip lokalitas adalah program dapat
berjalan secara efisien saat satu subset page berkecenderungan tinggi saling
mengacu terdapat di memori.
2.
Working
set of program behavior
Himpunan kerja secara
informal didefiisikan sebagai kumpulan page proses yang secara aktif diacu.
Dennnig menyatakan bahwa agar suatu program berjalan secara efisien, himpunan
kerja harus dijaga berada di memori utama. Selain itu akan terjadi aktivitas page
fault yang berlebihan. Peristiwa page fault yang sangat berlebihan disebut
thrashing, yaitu hanya beberapa instruksi terjadi page fault.
Himpunan kerja dari program pada satu waktu pada
pengacuan memori ke-t adalah :
W(t,θ) + {i € N | page
I muncul pada rt-0+1, …, rt}
Dimana : rt menyatakan
pengacuan memori saat t.
W(t,θ) himpunan page yang diacu selama θ
pengacuan memori terakhir.
Dengan kata lain, himpunan kerja adalah himpunan
page yang diacu dalam jendela ukuran θ yang dibentuk menurut waktu. Begitu
program dieksekusi, ukuran himpuanan kerja dan identitas page beragam menurut
waktu.
3.
Prinsip-prinsip
Working Set Model
Prinsip yang digunakan adalah melacak dan menjamin
himpunan kerja terdapat di memori sebelum proses dijalankan. Cara ini mengurangi
terjadinya page fault.
Prinsip-prinsip himpunan kerja :
1. Program
seharusnya dijalankan jika dan hanya jika himpunan kerja berada di memori.
2. Page
tidak boleh dipindahkan dari memori jika page anggota himpunan kerja dari
program yang running.
Berdasarkan hal ini terdapat dua teknik untuk memuat
page, yaitu :
·
Prepaging
adalah
teknik memuatkan page-page lebih dulu sebelum prose berjalan.
·
Demand
paging adalah teknik yang segera memuatkan page begitu page
dibutuhkan.
- Apabila ternyata nomor page tidak ada dimemori fisik, yaitu nilai present/absent bit di isian table page bernilai 0, MMU menerbitkan page-fault. Rangkain aksi yang dilakukan adalah sebagai berikut :
1.
MMU
memperingkatkan page tidak dipetakkan ke memori fisik dan pemroses melakukan
trap ke sisitem operasi, disebut page fault.
2.
Membebaskan
bagian page frame memori fisik yang jarang digunakan dengan menyimpan page
frame itu ke disk.
3.
Mengkonsolidasikan
pemetaan antara memori maya « memory fisik.
Ketika terjadi page
fault, system operasi memilih frame di memori fisik untuk diganti page berguna
yang akan masuk.
·
Jika
page yang diganti telah dimodifikasi, page harus ke disk. Page yang telah
dimodifikasi disebut dirty page.
·
Jika
page belum diubah (misalnya page yang berisi teks biner progam), kopian di disk
masih up to date sehingga page tidak perlu ditulis ke disk.
Tabel
– tabel Paging
pemakaian tabel page
pada system paging menimbulkan dua masalah utama, yaitu:
1.
Tabel
page dapat berukuran luar bias besar.
2.
Pemetaan
harus dilakukan secara cepat.
Tabel page dapat
berukuran luar biasa besar
Misalnya
·
Register
alamat mya 32 bit
·
Ukuran
page 4 Kilobyte = 212 byte
Berarti terdapat 220
page (sejuta page lebih), yaitu alamat maya 32 bit berarti memori dapat memuat
232 byte karena masing – masing page adalah 212 byte.
Berarti jumlah page adalah 232 dibagi 212 = 220
page.
·
Register
alamat mya 64 bit.
·
Ukuran
page 4 Kilobyte, berarti akan terdapat 242 page.
Bial memori mya sangat
besar maka tidak mungkin menggunakan satu tabel tunggal karena akan diperlukan
ukuran tabel sangat besar.
Solusi
Menggunakan tabel – tabel
bertingkat (serupa indeks bertingkat di organisasi berkas).
Beberapa rancangan
tabel paging untuk beragam sesuai system komputer, yaitu:
·
DEC
PDP-11 menggunakan paging satu tingkat (one-level paging)
·
DEC
VAX menggunakan paging dua tingkat (two-level paging)
·
SUN
SPARC menggunakan paging empat tingkat (four-level paging)
Pemetaan Harus
Dilakukan Secara Cepat
Pemetaan alamat maya
ke alamat fisik dilakukan setiap terjadi pengacuan memori.
Intruksi computer
biasanya berbentuk:
Operator
operand_1, operand_2,…,operand_N
Pada tiap intruksi, setidaknya
terdapat 1 atau 2 operan, operan – operan merupakan pengacuan ke memori karena operan disimpan di memori
berarti untuk satu interaksi setidaknya terjadi 1 sampai 2 pengacuan memori. Jika
satu intruksi memerlukan 10 ns, maka pemetaan harus dilakukan beberapa ns saja
agar tidak terjadi bottleneck.
Kesimpulan
Pada pemroses dengan memori maya,
pengelolaan page besar dan cepat merupakan konstrain utama perancangan dan
pembangunan pemroses.
Memori Asosiatif
Dari obsevasi disimpulkan,
sebagian besar program cenderung melakukan banyak pengacuan ke sejumlah kecil
page (prinsip lokalits). Sebenarnya hanya sejumlah kecil elemen tabel page yang
sering dibaca.
Berdasarkan fakta ini, system
komputer dengan memori maya dapat memanfaatkan sifat ini untuk mempercepat
proses pengacuan tanpa melibatkan tabel page. Sistem komputer dilengkapi
perangkat pemetaan alamat maya ke alamat fisik tanpa lewat tabel page.
Perangkat ini disebut memori asosiatif (associative memory) atau TLB
(translation lookasiade buffer). Perangkat ini dapat dipasang di MMU.
Memori asosiatif berisi sejumlah
elemen tabel (antara 8 sampai 32 elemen). Tiap elemen berisi informasi –
informasi mengenai page, yaitu:
·
Jika
ditemukkan dimemori asosiatif dan pengaksesan tidak melanggar bit-bit proteksi,
maka page frame langsung ditangani memori asosiatif tanpa melibatkan tabel
page.
·
Jika
page ditemukan di memori asosiatif tapi melanggar bit-bit proteksi, maka
diterbitkan protection fault. Proteksi ini juga dilakukan tabel page (bila isian
tabel page dilengkapi bit-bit proteksi).
·
Jika
nomor page maya tidak terdapat di memori asosiasi, maka MMU mencari di tabel
page. Salah satu elemen memori asosiatif disingkirkan dan diganti elemen tabel
page yang ditemukan. Elemen yang disingkirkan dikembalikan ke tabel page di
memori. Jika page itu kembali digunakan, maka hanya akan ditangani memori
asosiatif tanpa MMU.
Rasio pengacuan memori yang
melalui memori asosiatif disebut hit ratio. Semakin tinggi hit ratio, semakin
bagus kinerja system. Dengan memori asosiatif maka kinerja rata-rata system
dipengaruhi oleh
·
Waktu
akse tabel page.
·
Waktu
akses memori asosiatif.
·
Nilai
hit-ratio.
Penggantian Page
Saat terjadi page
fault berarti harus diputuskan page frame di memori fisik yang harus diganti.
Kinerja system akan baik jika page yang diganti dipilih yang tidak akan
digunakan di masa datang. Jika page yang diganti akan kembali digunakan, maka
page akan dikembalikan secepatnya yang berarti terjadi page fault berulang
kali. Banyaknya page fault menghasilkan banyak overhead.
Algoritma penggantian
page anta lain:
- Algoritma penggantian page acak (random page replacement algorithm)
- Algoritma penggantian page optimal
- Algoritma penggantian page NRU
- Algoritma penggantian page modifikasi dari algoritma FIFO
- Algoritma penggantian page LRU
Algoritma – algoritma
Penggantian Page
- Algoritma Penggantian page acak
Mekanisme algoritma
Setiap terjadi page fault, page yang
diganti dipilih secara acak.
Teknik ini tidak
memakai informasi apapun dalam menentukan page yang diganti. Semua page di
memori utama mempunyai bobot sama untuk dipilih. Teknik ini dapat memilih
sembarang page, termasuk page yang sedang diacu (page yang seharusnya tidak
diganti, pilihan terburuk).
Teknik ini sangat
buruk, percobaan menunjukkan algoritma acak menimbulkan rate terjadinya page
fault yang sangat tinggi.
- Algoritma Penggantian Page Optimal
Mekanisme algoritma
Dasar algoritma ini adalah memilih
page yang berpeluang dipakai kembali di masa datang yang paling kecil. Strategi
ini akan menghasilkan jumlah page fault paling sedikit. Algoritma ini adalah
algoritma utopia (ideal tanpa dapat dijadikan kenyataan) karena tak mungkin
dibuat prosedur yang dapat mengetahui peluang pemakaian suatu page kembali di
masa datang. Metode ini tak mungkin diterapkan.
Pendekatan ini dapat
dilakukkan dengan simulasi. Tapi, simulasi hanya spesifik suatu program. Bila
yang terbaik tak dimungkinkan, maka yang perlu dilakukan adalah berusaha
mendekatinya. Algoritma penggantian page diusahakan kinerjanya mendekati optimal.
Tiap algoritma penggantian page mengumpulkan dan memakai informasi untuk menentukan page yang diganti
sehingga mendekati optimal.
Algoritma penggantian
page optimal penting untuk kajian teoretis, sebagai pembanding bagi
algoritma-algoritma penggantian page yang lain.
- Algoritma Penggantian Page NRU (Not-Recentli Used)
Mekanisme algoritma
Pada algoritma ini, page diberi dua
bit mencatat status page, bit R dan M yaitu:
Bit R : referenced (menyatakan page
sedang diacu)
Bit R = 1 berarti sedang
diacu
Bit R = 0 berarti tidak
sedang diacu
Bit M : modified (menyatakan page
dimodifikasi)
Bit M = 1 berarti
dimodifikasi
Bit M = 0 berarti tidak
dimodifikasi
Dengan 2 bit, maka page-page
dikelompokkan menjadi 4 kelas page, yaitu:
Kelas 0 : tidak sedang
diacu, belum dimodifikasi (R=0,M=0)
Kelas 1 : tidak sedang
diacu, telah dimodifikasi (R=0, M=1)
Kelas 2 : sedang diacu,
belum dimodifikasi (R=1, M=0)
Kelas 3 : sedang diacu,
telah dimodifikasi (R=1, M=1)
·
Memilih
menggantikan page kelas bernomor terendah (bila terdapat page-page di kelas
itu) secara acak.
·
Bila
kelas tersebut kosong maka dipilih page di kelas lebih tinggi, dan seterusnya.
Algoritma ini
mengansumsikan kelas-kelas bernomor lebih rendah akan baru akan digunakan
kembali dalam waktu relative lama.
Algoritma ini mudah
dipahami dan diimplementasikan. Implementasi algoritma ini sangat efisien
karena tak banyak langkah dalam pemilihan page. Algoritma ini memang tidak
optimal, tapi dalam kondisi-kondisi normal telah memadai.
- Algoritma Penggantian Page FIFO (First-In, First-Out)
Mekanisme algoritma
Algoritma ini memerlukan pengelolaan
senarai page di memori. Elemen terdepan senarai adalah page tertua dan ujng
belakang adalah page paling akhir datang.
·
Bila
terjadi page fault, page elemen terdeoan (page tertua) diganti dan page baru
ditambahkan di ujung belakang senarai.
Dengan hanya informasi
mengenai lam berada di memori, maka algoritma ini dapat memindahkan page yang
sering digunakan. Boleh jadi page itu berada terus di memori karena selalu
selalu digunakkan. Page itu karena mengikuti pola antrian berdasar lamanya
berada dimemori menjadi elemen terdepan, diganti dan segera harus masuk kembali
ke memori sehingga terjadi page fault kembali. Algoritma FIFO murni jarang
digunakan, tetapi dikombinasikan (modifikasi).
- Modifikasi Terhadap FIFO
Kelemahan FIFO yang
jelas adalah algoritma dapat memilih memindahkan page yang sering digunakan
yang lama berada di memori. Kemungkinan ini dapat dihindari dengan hanya
menindahkan page tidak diacu. Page ditambah bit R mencatat apakah page diacu
atau tidak. Bit R bernilai 1 bila diacu dan bernilai 0 bila tidak diacu.
Variasi dari FIFO
anatara lain:
·
Algoritma
penggantian page kesempatan kedua (second chance page replacement algorithm)
·
Algoritma
penggantian clock page (clock page replacement algothm)
Algoritma Penggantian
Page Kesempatan Kedua
Mekanisme algoritma
·
Saat
terjadi page fault, algoritma memilih page elemen terdepan bila bit R bernilai
0.
·
Bila
bit R bernilai1, maka bit page terdepan senarai diseret menjadi 0 dan
diletakkan ke ujung belakang senarai. Mekanisme ini kembali diterapkan ke
elemen berikutnya.
Algoritma Penggantian
Clock Page
Algoritma penggantian
page kesempatan kedua merupakan algoritma yang memadai tapi tidak efisien
karena memindahkan page-page di senarainya. Algoritma penggantian clock page
merupakan perbaikkan algoritma pertama.
Mekanisme algoritma
·
Pada
algoritma ini, semua page merupakan senarai melingkar membentuk pola jam.
Terdapat petunjuk (pointer) ke pege tertua.
Ketika terjadi page
fault, page yang ditunjukkan diperiksa.
·
Jika
bit R bernilai 0, maka [age diganti. Page baru ditempatkan ditempat page
diganti, dan petunjuk dimajukkan satu posisi ke page berikutya.
·
Jika
bit R bernilai 1, maka bit R diseret menjadi 0, dan penunjuk dimajukan satu
posisi. Seterusnya sampai menemui pae dengan bit R bernilai 0.
Kedua algoritma adalah
sama, hanya berbeda dalam implementasi, yaitu:
·
Algoritma
penggantian page kesempatan kedua menggunakkan senarai lurus tidak sirkular.
·
Algoritma
penggantian clock page menggunakan senarai sirkular.
- Algoritma Penggantian Page LRU (Leadt Recently Used)
Berdasarkan observasi,
page-page pada beberapa intruksi terakhir berkemungkinan besar akan dipakai
kembali. Page – page yang lama tidak digunakkan akan tetap tidak digunakkan
dalam waktu lama.
Mekanisme algoritma
Algoritma LRU adalah ketika terjadi
page fault maka memindahkan page yang tidak digunakkan paling lama.
Masalah
·
Sangat
mahal
Kemahalan disebabkan
harus mengelola senarai informasi seluruh page di memori. Senarai harus terurut
berdasar kemutakhiran penggunaan. Senarai harus diperbarui setiap terjadi
pengacauan memori. Begitu terjadi pengacuan memori, harus dilakukan opersi
menemukan page di senarai, dipindahkan sebagai terdepan yaitu paling mutakhir
diacu. Meskipun ini memerlukan waktu yang sangat banyak.
Contoh Eksekusi Paging
Algoritma Penggantian Page
Optimal
Siste, pengacuan 2 3 2 1 5 2 4 5 3 2 5 2
2
2 2 2 2 2 4 4 4 2 2 2
3 3 3 3 3 3 3 3 3 3 3
1 5 5 5 5 5 5 5 5
Fault F F
F F F F
6 Fault
SISTEM PANGING DAN KOMBINASI
PAGING –SEGMENTASI
Menyedrhanakan Penanganan
Struktur Data yang Berkembang
Kompilasi Ulankg Indepanden Tanpa
Menautkan Kembali (relink) Seluruh Program
Tehnik ini memungkinkan
program-program dikompilasi ulang secara independen tanpa perlu men-tautkan
kembali seluruh program yang dimuatkan kembali.
Memudahkan Pemakaian memory
Bersama diantara Proses – Proses
Tehnik inin memudahkan pemakaian
memory bersama diantara proses-proses.Program dapat mendapatkan program
ulitilitas atau table data berguna disegmen
yang dapat diacu oleh proses –proses lain.Segemntasi memberi fasilitas
pemakaian bersama terhadap prosedur dan data untuk beberapa proses,berupa shared library.
Memudahkan Untuk Proteksi
Karena segmedapat dikonstruksikan
berisi sekumpulan procedur atau data terdefinisi baik,program atuau
administrator system dapat memberikan kewenanagn pengaksesan secara nyaman.
A. Segemntasi Secara Mruni
Segmen-segmen dapat berukuran
berbeda-beda dan dinamis.Pengacauan –pengacauan memoru berbetuk (nomor segmen,offside).Alamat maya adalah
disegmen.Tiap proses mempunyai table
segmen.Ketika proses Running,alamat awal table dimuat ke register dasar .Nomor segmen
digunakan untuk mencari dikriptor segmen di table segmen yang menyediakan
alamat fisisk awal segmen,panjangnya dan
bit-bit proteksi.Alamt fisik dihitung dengan menambahkan alamat dasar segmen ke
almamat maya.
B. Pebandinajgan Antara Paging dan
Segmentasi.
Perbandingan mengenai t eknik paging dan segmentasi (TAN-92).
Pertimbangan
|
Paging
|
Segmentasi
|
Perlunya program menyadari
bahwa teknik ini daipakai.?
|
TIDAK
|
YA
|
Berapa banyak ruang alamat
linear yang terdapat.?
|
1
|
BANYAK
|
Dapatkah total ruang alamat
melampauai ukuran memori fisisk.?
|
TIDAK
|
YA
|
Dapatkah prosedur dan data
diproteksi secara terpisah.?
|
TIDAK
|
YA
|
Dapatkah table-tabel yang
mempunyai ukuran daiakomodasikan dengan mudah.?
|
TIDAK
|
YA
|
Apakah pemakaian bersama
prosedur-prosedur antara pemakai difasilitasi.?
|
TIDAK
|
YA
|
Kenapa teknik ini ditemukan.?
|
Untuk mendapatkan alamat linear
tanpa
|
Untuk memungkinkan.
|
C. Teknik Kombinasi Paging
Teknik kombinasi
paging dan segmentasi adalah ruang alamat pemakai dibagi menjadi sejumlah
segment sesuai dengan kehendak pemrogram. Segment tersebut dibagi menjadi sejumlah page berukuran
tetap dan berukuran
sama dengan page frame
memori utama. Jika segment kurang dari ukuran page, maka segnent
hanya memerlukan satu page.
Dari segi pandangan pemrogram, alamat maya masih berisi nomor segment dan offset di
segment itu. Dari segipandangan sistem, offset segment dipandang sebagai nomor page dan offset page untuk page di
segment yang dispesifiksikan. Penggabungan dengan proses adalah tabel segment dan sejumlah tabel page, merupakan satu tabel persegment proses.
Saat proses running, register menyimpan alamat awal tabel
segment untuk proses, pemroses
menggunakanbagian nomor segment untuk mengindeks tabel segment proses guna menemukan tabel page untuk segment.
D. Contoh Sistem Paging dengan
Memory Maya
I.
Memory Maya dengan Segmentasi Murni
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.
II.
One
Level Paging
Nomor
page maya digunakan sebgai index ke table page (page table ) yang biasanya berlokasi di memory utama.Isian table
page berisi nomor page fisik dan bit-bit proteksi .Offset pada page fisik sama
dengan offset pada page maya.Dalam beberapa kasus ,register panjang digunakan
untuk menetapakn akhir tabeluntuk menghindari runag yang disediakan.
Keunggulan
Semua
bentuk paging mengeliminasi frakmentasi external dan menyederhanakan alokasi
dan pertumbuhan dinamis.
Kelemahan
Sejumlah
besar ruang memory utama harus dicadangkan untuk table page sehingga menyediakan
ruang alamat memory maya besar dengan page-page yang berukuran tertentu.Alokasi
dan pertumbuhan dinamis table page besar dapat menjasdi masalah karena harus
kontigu memory.
III.
Two
Level Paging
Keunggulan
Mekanisme
inimengkombinasikan keunggulan segmentasi
dan paging.Pemakaian bersama dapat dilakukan dilevel segmen ,mereduksi
kebutuhan isian-isian table page yang redudan .Tabel-tabel page tidak perlu
berada dimemory utama dan tidak perlu kontigu dimemory utama .Hal ini
memungkinkan alokasi dan pertumbuhan table page yang sederhana dan memungkinkan
menggunakan ruang alamat maya yang
elatif besar.
Kelemahan
Ruang
alamat maya sangat besar memerlukan
jumlah ruang besar table segmen harus disimpan dimemory utama dan harus
kontigu.Hal ini membuat alokasi pertumbuhan dinamis tabek segmen menjadi sulit.
IV.
Three
Level Paging
Keunggulan
Mekanisme
table page banyak tingkat untuk implementasi memory maya dengan ruang alamat
sangat besar.Tabel page banyak tingkat memrlukan table-tabel page
besar.Implementasi ruang memory maya sangat besar dengan table tidak terlalu banyak.
V.
Four
Level Paging
Keunggulan
Mekanisme
inin berguna untuk program yang menggunakan ruang alamat memory yang sangat
besar.Program LISP besar yang secara kintinyu mengalokasikan dan melepaskan
daerah memory adalah tipe aplikasi yang cocok dengan mekanisme ini.Tabel-tabel
ini dapat dipandang sebagai pohon yang hanya berisi cabang – cabang yang
diperlukan untuk mencapai yang sesungguhnya digunkan di tiap level.Cara ini
mereduksi jumlah ruang untuk tabel-tabel
. Semua tabel kecauli table root dapat disimpan di disk.Biasanya ,table
individu tidak lebih besar disbanding satu page,alokasi dan pertumbuhan dinamis
table-tabel page adalah mudah.
Kelemahan
Kondisi
terburuk yang mungkin adalh kondisi
unutk translasi memerlukan sebanyak empat pengacuan memory ,masing-masing
menghasilakn page fault .Karena kebanyakan page hanya memiliki beberapa isian
,table-tabel akan mempunyai fragmentasi internal sangat besar.
0 komentar:
Posting Komentar