VIRTUAL MEMORY II
Overlay
:
Program
dipecah menjadi bagian-bagian yang dapat dimuat memori, jika memori terlalu
kecil untuk menampung seluruhnya sekaligus. Overlay disimpan pada disk dan di-keluar-masukkan dari
dan ke memori oleh sistem operasi. Pembagian dilakukan oleh programmer.
Virtual
memory (Memori maya) :
sistem operasi menyimpan bagian-bagian
proses yang sedang digunakan di memori utama dan sisanya di disk.
Virtual memory
dapat diimplementasikan dengan tiga cara, yaitu:
Ø Paging
Ø Segmentasi
Ø Kombinasi
paging dan segmentasi
1. Paging
Sistem paging
mengimplementasikan ruang alamat besar pada memori kecil menggunakan index
register, base register, segment register, dll.
Istilah pada sistem
paging:
- Alamat
virtual = V; Alamat yg dihasilkan dgn perhitungan menggunakan index register,
base register, segment reg dsb.
-
Alamat nyata (real address = R); Alamat yang tesedia di memori utama
fisik.
- Page;
Unit terkecil virtual address space.
- Page
frame; Unit terkecil memori fisik.
- Page
fault; Permintaan alokasi page ke memori yang belum dipetakan.
- MMU
(Memory Management Unit); Chip atau kumpulan chip yang memetakan alamat maya ke
alamat fisik.
2.
Tabel Page
Alamat virtual dibagi menjadi dua bagian:
- Nomer
Page (bit-bit awal)
- Offset
(bit-bit akhir)
Secara metematis:
tabel page merupakan fungsi dgn nomer page sebagai argumen dan nomer frame
sebagai hasil.
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
Nomer page = 2
Offset 12 bit dicopy persis dari input ke output
Tabel Page
|
0
|
010
|
1
|
Present/absent bit
|
||
1
|
001
|
1
|
||||
2
|
110
|
1
|
110
|
|||
3
|
000
|
1
|
||||
4
|
100
|
1
|
||||
5
|
011
|
1
|
||||
6
|
000
|
0
|
||||
7
|
000
|
0
|
||||
8
|
000
|
0
|
||||
9
|
101
|
1
|
||||
10
|
000
|
0
|
||||
11
|
111
|
1
|
||||
12
|
000
|
0
|
||||
13
|
000
|
0
|
||||
14
|
000
|
0
|
||||
15
|
000
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
Cara
Kerja Pemetaan oleh MMU
 |
3.
Memori Asosiatif
Tabel Page biasanya
diletakkan di memori, dengan demikian diperlukan dua kali referensi ke memori :
sekali untuk mencari page, dan sekali untuk mencari data yang akan diproses.
Solusi:
Komputer
dilengkapi dengan komponen hardware kecil untuk pemetaan alamat virtual ke
alamat fisik tanpa menelusuri seluruh tabel page.
Komponen
ini disebut memori asosiatif atau translation lookaside buffer, yang
biasanya berada di dalam MMU, dan berisi beberapa entri.
Valid entry
 |
No.
page
|
Modified
|
Protection
|
No.
frame
|
1
|
140
|
1
|
RW
|
31
|
1
|
20
|
0
|
R X
|
38
|
1
|
130
|
1
|
RW
|
29
|
1
|
129
|
1
|
RW
|
62
|
1
|
19
|
0
|
R X
|
50
|
1
|
21
|
0
|
R X
|
45
|
1
|
860
|
1
|
RW
|
14
|
1
|
861
|
1
|
RW
|
75
|
Memori
asosiatif untuk mempercepat paging
Bagian
referensi memori yang dapat dipenuhi dari memori asosiatif disebbut hit
ratio. Makin tinggi hit ratio, makin baik performance manajemen memori
khususnya, dan komputer umumnya.
ALGORITMA
PENGGANTIAN PAGE
Saat terjadi fault
berarti harus diputuskan page frame yang harus diganti.
1.
Algoritma
penggantian page acak:
Page
yg dikeluarkan untuk memberi tempat ke yang baru ditentukan secara acak tanpa
kriteria tertentu.
2.
Algoritma
penggantian page optimal:
Setiap page diberi label untuk
menandai berapa instruksi lagi baru dia digunakan. Page dengan label tertinggi
(waktu dari sekarang sampai pemakaian berikutnya paling lama) yang akan
dikeluarkan.
Algoritma
Penggantian Page Optimal
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
|
6 Fault
|
3. Algoritma penggantian page NRU (not
recently used):
Setiap page diberi status bit R (referenced)
dan M (modified).
Bit
bernilai 0 jika page belum direferensi/dimodifikasi, dan 1 jika sebaliknya.
Dari nilai desimalnya didapat 4 kelas:
R
|
M
|
Kelas
|
Keterangan
|
|
0
|
0
|
0
|
not referenced,
|
not modified
|
0
|
1
|
1
|
not referenced,
|
modified
|
1
|
0
|
2
|
referenced,
|
not modified
|
1
|
1
|
3
|
referenced,
|
modified
|
Page dengan kelas terkecillah yang akan dikeluarkan
4. Algoritma penggantian page FIFO (First
In First Out):
Page
yang paling dulu masuk ke memori dari semua page yang ada dikeluarkan.
Algoritma Penggantian Page FIFO
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
|
F
|
F
|
8 Fault
|
Anomali pada FIFO
(Belady’s Anomaly)
String Pengacuan
|
0
|
1
|
2
|
3
|
0
|
1
|
4
|
0
|
1
|
2
|
3
|
4
|
||
Page Termuda
|
0
|
1
|
2
|
3
|
0
|
1
|
4
|
4
|
4
|
2
|
3
|
3
|
||
0
|
1
|
2
|
3
|
0
|
1
|
1
|
1
|
4
|
2
|
2
|
||||
Page Tertua
|
0
|
1
|
2
|
3
|
0
|
0
|
0
|
1
|
4
|
4
|
||||
Fault
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
9 Fault
|
(a)
String Pengacuan
|
0
|
1
|
2
|
3
|
0
|
1
|
4
|
0
|
1
|
2
|
3
|
4
|
||
Page Termuda
|
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
|
|||||
Page Tertua
|
0
|
0
|
0
|
1
|
2
|
3
|
4
|
0
|
1
|
|||||
Fault
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
10 Fault
|
(b)
5. Algoritma penggantian page Modifikasi FIFO (Second Chance):
Mencari page yang berada di memori paling lama, tetapi juga tidak dipakai.
Jika sebuah page dipakai (direferensi) bit R diset. Jika
sistem menemukan bahwa bit R page yang paling lama ter-set, page tersebut tidak
jadi dikeluarkan, tetapi bit R-nya di-reset.
Waktu load
0
|
3
|
7
|
8
|
12
|
14
|
15
|
18
|
|||||||
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
Page
yang di-load pertama kali Page
yang terakhir di-load.
(a)
Page dalam urutan FIFO
Waktu load
3
|
7
|
8
|
12
|
14
|
15
|
18
|
20
|
|||||||
B
|
C
|
D
|
E
|
F
|
G
|
H
|
A
|
A dianggap sebagai page yang baru di-load.
(b)
Daftar page setelah page fault pada waktu 20 dan bit R page A dalam keadaan
set.
Pada algoritma ini,
daftar page bisa juga dibuat berbentuk jam (clock page replacement algorithm)
Algoritma penggantian page clock
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
|
6 Fault
|
Keterangan : *
adalah diacu dan > adalah ditunjuk pointer
6.
Algoritma
penggantian page LRU (Least Recently Used):
Yang
dikeluarkan ialah page yang sudah tidak terpakai dalam waktu paling lama.
Algoritma Penggantian Page LRU
String Pengacuan
|
2
|
3
|
2
|
1
|
5
|
2
|
4
|
5
|
3
|
2
|
5
|
2
|
||
2
|
2
|
2
|
2
|
2
|
2
|
4
|
4
|
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
|
7 Fault
|
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.
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.
SEGMENTASI
Compiler bisa memiliki beberapa tabel dengan alamat virtual yang terpisah,
misalnya terdiri dari tabel-tabel untuk:
1. Source
text,
2. Tabel
simbol,
3. Tabel untuk semua konstanta integer dan floating point,
4. Parse
tree, berisi analisis sintaksis program, dan
5. Stack
yang digunakan untuk pemanggilan prosedur.
Tabel 1 s/d 4 bisa
bertambah pada saat kompilasi berjalan, sehingga dengan sistem paging yang
berukuran tetap, batas satu page bisa terlampaui.
Dengan alasan ini
dipakai bagian-bagian dengan alamat yang relatif independen, yang disebut segmen. Setiap segmen mempunyai ukuran
yang berbeda dengan yang lain. Panjang segmen juga bisa berubah selama
eksekusi.
Program harus
menyediakan alamat yang terdiri dari dua bagian:
-
nomer segmen
-
alamat di dalam segmen
Segmentasi juga
memberikan fasilitas pemakaian bersama prosedur atau data antar beberapa
proses. Contoh umumnya adalah shared
library.
Segmen
|
Segmen
|
Segmen
|
Segmen
|
Segmen
|
|||||
0
|
1
|
2
|
3
|
4
|
|||||
0
|
0
|
0
|
Konstanta
|
0
|
0
|
||||
4K
|
4K
|
4K
|
4K
|
||||||
Source
|
Parse
|
Call
|
|||||||
text
|
tree
|
stack
|
|||||||
8K
|
8K
|
8K
|
8K
|
||||||
Tabel
|
|||||||||
simbol
|
|||||||||
12K
|
12K
|
12K
|
12K
|
||||||
16K
|
16K
|
||||||||
20K
|
Memori
yang tersegmentasi memungkinkan setiap tabel bertambah atau berkurang.
Pertimbangan
|
Paging
|
Segmentasi
|
Apakah
programmer harus menyadari bahwa teknik ini sedang digunakan?
|
Tidak
|
Ya
|
Berapa banyak
ruang alamat linier yang ada?
|
1
|
Banyak
|
Dapatkah ruang alamat total melebihi ukuran
memori fisik?
|
Ya
|
Ya
|
Apakah tabel yang ukurannya berubah-ubah
dapat diakomodasi?
|
Tidak
|
Ya
|
Dapatkan
prosedur dan data dibedakan dan diproteksi secara terpisah?
|
Tidak
|
Ya
|
Adakah fasilitas pemakaian bersama prosedur
antar user?
|
Tidak
|
Ya
|
Mengapa teknik ini diciptakan?
|
Untuk mendapatkan ruang alamat linier yang
besar tanpa harus membeli memori fisik tambahan
|
Untuk memungkinkan program dan data dibagi
menjadi ruang alamat yang secara logik independen dan untuk membantu
pemakaian bersama dan proteksi
|
Perbandingan
paging dan segmentasi.
Checkerboarding: Timbulnya
blok-blok memori yang kosong (hole) pada saat isi segmen dikeluarkan. Hal ini
diatasi dengan pemampatan (compaction).
Segmentasi
dengan Paging : Setiap segmen dapat dianggap sebagai satu virtual memori, dan
masing-masing dibagi menjadi page-page.
Salah satu mesin
yang memakai cara ini adalah MULTICS. Setiap program MULTICS memiliki satu
tabel segmen, dengan satu descriptor per segmen. Segmen descriptor berisi keterangan apakah segmen yang bersangkutan
ada di memori atau tidak.
Segmen
descriptor
|
Tabel page untuk segmen 0
|
||||
 36
bit |
Page
0 entry
|
||||
Descriptor
segmen 0
|
Page
1 entry
|
Pointer-
|
|||
Descriptor
segmen 1
|
Page
2 entry
|
pointer
|
|||
Descriptor
segmen 2
|
Page
3 entry
|
ke page
|
|||
Descriptor
segmen 3
|
|||||
Descriptor
segmen 4
|
|||||
Descriptor
segmen 5
|
Tabel page untuk segmen 1
|
||||
Descriptor
segmen 6
|
Page
0 entry
|
||||
Descriptor
segmen 7
|
Page
1 entry
|
||||
Page
2 entry
|
|||||
Page
3 entry
|
|||||
Page
4 entry
|
|||||
Page
5 entry
|
|||||
Virtual address
MULTICS 34-bit:
Alamat
di dalam segmen
Nomer segmen
|
Nomer page
|
Offset di dalam
page
|
|
18
|
6
|
10
|
Nomer segmen
|
Nomer page
|
Offset di dalam
page
|
 Nomer |
|||||
segmen
|
|||||
 |
 Nomer |
||||
Descriptor
|
page
|
||||
 |
Page frame
|
 Offset |
|||
Segmen
|
Tabel page
|
||||
descriptor
|
Word
|
||||
Page
|
Konversi
alamat MULTICS menjadi alamat memori utama.
2.
Tabel Page
Alamat virtual dibagi menjadi dua bagian:
- Nomer
Page (bit-bit awal)
- Offset
(bit-bit akhir)
Secara metematis:
tabel page merupakan fungsi dgn nomer page sebagai argumen dan nomer frame
sebagai hasil.
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
Nomer page = 2
Offset 12 bit dicopy persis dari input ke output
Tabel Page
|
0
|
010
|
1
|
Present/absent bit
|
||
1
|
001
|
1
|
||||
2
|
110
|
1
|
110
|
|||
3
|
000
|
1
|
||||
4
|
100
|
1
|
||||
5
|
011
|
1
|
||||
6
|
000
|
0
|
||||
7
|
000
|
0
|
||||
8
|
000
|
0
|
||||
9
|
101
|
1
|
||||
10
|
000
|
0
|
||||
11
|
111
|
1
|
||||
12
|
000
|
0
|
||||
13
|
000
|
0
|
||||
14
|
000
|
0
|
||||
15
|
000
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
Cara
Kerja Pemetaan oleh MMU
|
3.
Memori Asosiatif
Tabel Page biasanya
diletakkan di memori, dengan demikian diperlukan dua kali referensi ke memori :
sekali untuk mencari page, dan sekali untuk mencari data yang akan diproses.
Solusi:
Komputer
dilengkapi dengan komponen hardware kecil untuk pemetaan alamat virtual ke
alamat fisik tanpa menelusuri seluruh tabel page.
Komponen
ini disebut memori asosiatif atau translation lookaside buffer, yang
biasanya berada di dalam MMU, dan berisi beberapa entri.
Valid entry
|
No.
page
|
Modified
|
Protection
|
No.
frame
|
1
|
140
|
1
|
RW
|
31
|
1
|
20
|
0
|
R X
|
38
|
1
|
130
|
1
|
RW
|
29
|
1
|
129
|
1
|
RW
|
62
|
1
|
19
|
0
|
R X
|
50
|
1
|
21
|
0
|
R X
|
45
|
1
|
860
|
1
|
RW
|
14
|
1
|
861
|
1
|
RW
|
75
|
Memori
asosiatif untuk mempercepat paging
Bagian
referensi memori yang dapat dipenuhi dari memori asosiatif disebbut hit
ratio. Makin tinggi hit ratio, makin baik performance manajemen memori
khususnya, dan komputer umumnya.
ALGORITMA
PENGGANTIAN PAGE
Saat terjadi fault
berarti harus diputuskan page frame yang harus diganti.
1.
Algoritma
penggantian page acak:
Page
yg dikeluarkan untuk memberi tempat ke yang baru ditentukan secara acak tanpa
kriteria tertentu.
2.
Algoritma
penggantian page optimal:
Setiap page diberi label untuk
menandai berapa instruksi lagi baru dia digunakan. Page dengan label tertinggi
(waktu dari sekarang sampai pemakaian berikutnya paling lama) yang akan
dikeluarkan.
Algoritma
Penggantian Page Optimal
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
|
6 Fault
|
3. Algoritma penggantian page NRU (not
recently used):
Setiap page diberi status bit R (referenced)
dan M (modified).
Bit
bernilai 0 jika page belum direferensi/dimodifikasi, dan 1 jika sebaliknya.
Dari nilai desimalnya didapat 4 kelas:
R
|
M
|
Kelas
|
Keterangan
|
|
0
|
0
|
0
|
not referenced,
|
not modified
|
0
|
1
|
1
|
not referenced,
|
modified
|
1
|
0
|
2
|
referenced,
|
not modified
|
1
|
1
|
3
|
referenced,
|
modified
|
Page dengan kelas terkecillah yang akan dikeluarkan
4. Algoritma penggantian page FIFO (First
In First Out):
Page
yang paling dulu masuk ke memori dari semua page yang ada dikeluarkan.
Algoritma Penggantian Page FIFO
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
|
F
|
F
|
8 Fault
|
Anomali pada FIFO
(Belady’s Anomaly)
String Pengacuan
|
0
|
1
|
2
|
3
|
0
|
1
|
4
|
0
|
1
|
2
|
3
|
4
|
||
Page Termuda
|
0
|
1
|
2
|
3
|
0
|
1
|
4
|
4
|
4
|
2
|
3
|
3
|
||
0
|
1
|
2
|
3
|
0
|
1
|
1
|
1
|
4
|
2
|
2
|
||||
Page Tertua
|
0
|
1
|
2
|
3
|
0
|
0
|
0
|
1
|
4
|
4
|
||||
Fault
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
9 Fault
|
(a)
String Pengacuan
|
0
|
1
|
2
|
3
|
0
|
1
|
4
|
0
|
1
|
2
|
3
|
4
|
||
Page Termuda
|
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
|
|||||
Page Tertua
|
0
|
0
|
0
|
1
|
2
|
3
|
4
|
0
|
1
|
|||||
Fault
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
10 Fault
|
(b)
5. Algoritma penggantian page Modifikasi FIFO (Second Chance):
Mencari page yang berada di memori paling lama, tetapi juga tidak dipakai.
Jika sebuah page dipakai (direferensi) bit R diset. Jika
sistem menemukan bahwa bit R page yang paling lama ter-set, page tersebut tidak
jadi dikeluarkan, tetapi bit R-nya di-reset.
Waktu load
0
|
3
|
7
|
8
|
12
|
14
|
15
|
18
|
|||||||
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
Page
yang di-load pertama kali Page
yang terakhir di-load.
(a)
Page dalam urutan FIFO
Waktu load
3
|
7
|
8
|
12
|
14
|
15
|
18
|
20
|
|||||||
B
|
C
|
D
|
E
|
F
|
G
|
H
|
A
|
A dianggap sebagai page yang baru di-load.
(b)
Daftar page setelah page fault pada waktu 20 dan bit R page A dalam keadaan
set.
Pada algoritma ini,
daftar page bisa juga dibuat berbentuk jam (clock page replacement algorithm)
Algoritma penggantian page clock
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
|
6 Fault
|
Keterangan : *
adalah diacu dan > adalah ditunjuk pointer
Tidak ada komentar:
Posting Komentar