VIRTUAL MEMORY Overlay : Program dipecah menjadi bagian-bagian yang dapat dimuat memori, jika memori terlalu kecil untuk menampung seluruhnya sekaligus. Overlay disimpan pada disk dan dikeluar-masukkan dari dan ke memori oleh sistem operasi. Pembagian dilakukan oleh programmer. Sistem Operasi Bagian Kode dan data pemakai yang harus selalu tinggal di memori utama selama eksekusi program Fase inisialisasi Fase Pemrosesan
Fase Keluaran
Daerah Overlay 1 2 3
Gambar 1. Struktur Umum Overlay 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
Sistem Operasi – Manajemen Memori 1
1/8
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. CPU card CPU mengirim alamat virtual ke MMU
CPU
MEMORI
DISK CONTROLLER
MMU
BUS MMU mengirim alamat fisik ke memori
Gambar 2.
Posisi dan fungsi MMU
(Tanenbaum, Bab 3, Hlm. 90)
Sistem Operasi – Manajemen Memori 1
2/8
Alamat 0–4 K 4K–8 K 8 K – 12 K 12 K – 16 K 16 K – 20 K 20 K – 24 K 24 K – 28 K 28 K – 32 K 32 K – 36 K 36 K – 40 K 40 K – 44 K 44 K – 48 K 48 K – 52 K 52 K – 56 K 56 K – 60 K 60 K – 64 K
Memori Nyata
Memori Virtual 2 1 6 0 4 3 X X X 5 X 7 X X X X
0–4 K 4K–8 K 8 K – 12 K 12 K – 16 K 16 K – 20 K 20 K – 24 K 24 K – 28 K 28 K – 32 K
Page frame
Virtual page
Gambar 3. Relasi Antara Alamat Virtual dan Alamat Fisik (Tanenbaum, Bab 3, Hlm. 91)
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. Nomer Page
Offset
Tabel Page
Nomer Frame
Sistem Operasi – Manajemen Memori 1
Offset
3/8
0
0
1
0
0
Nomer page = 2 Tabel Page
0
0
0
0
0
0
0
0
0
1
0
0
0
0
Offset 12 bit dicopy persis dari input ke output
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
0
0
010 001 110 000 100 011 000 000 000 101 000 111 000 000 000 000
0
1 1 1 1 1 1 0 0 0 1 0 1 0 0 0 0
0
Present/absent bit 110
0
0
0
0
0
0
0
1
Gambar 4. Cara Kerja Pemetaan oleh MMU (Tanenbaum, Bab 3, Hlm. 92)
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.
Sistem Operasi – Manajemen Memori 1
4/8
Valid entry
1 1 1 1 1 1 1 1
No. page Modified Protection 140 1 RW 20 0 R X 130 1 RW 129 1 RW 19 0 R X 21 0 R X 860 1 RW 861 1 RW
No. frame 31 38 29 62 50 45 14 75
Gambar 5. Memori asosiatif untuk mempercepat paging (Tanenbaum, Bab 3, Hlm. 103)
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.
Sistem Operasi – Manajemen Memori 1
5/8
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
Fault
2 2
3 2 3
2 2 3
F F
1 2 3 1 F
5 2 3 5 F
2 2 3 5
4 4 3 5 F
5 4 3 5
3 4 3 5
2 2 3 5 F
5 2 3 5
2 2 3 5 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.
Sistem Operasi – Manajemen Memori 1
6/8
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
Fault
2 2
3 2 3
2 2 3
1 2 3 1
F F
5 2 3 5 F
2 2 3 5 F
4 4 3 5 F
5 4 3 5
3 4 3 5 F
2 2 3 5
5 2 3 5 F
2 2 3 5 F 8 Fault
Anomali pada FIFO (Belady’s Anomaly) String Pengacuan Page Termuda Page Tertua Fault
0 0
1 1 0
2 2 1 0
3 3 2 1
F F
0 0 3 2 F
1 1 0 3 F
4 4 1 0 F
0 4 1 0
1 4 1 0 F
2 2 4 1
3 3 2 4 F
4 3 2 4 F 9 Fault
1 3 2 1 0 F
4 4 3 2 1 F
0 0 4 3 2
1 1 0 4 3 F
2 2 1 0 4
3 3 2 1 0 F
4 4 3 2 1 F 10 Fault
(a)
String Pengacuan Page Termuda
Page Tertua Fault
0 0
1 1 0
2 2 1 0
F F
3 3 2 1 0
0 3 2 1 0 F (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.
Sistem Operasi – Manajemen Memori 1
7/8
Waktu load
0 A
3 B
7 C
8 D
12 E
14 F
15 G
Page yang di-load pertama kali.
18 H
Page yang terakhir di-load.
(a) Waktu load
3 B
7 C
8 D
12 E
14 F
15 G
18 H
20 A
A dianggap sebagai page yang baru di-load
(b) Gambar 1. (a) Page dalam urutan FIFO. (b) Daftar page setelah page fault pada waktu 20 dan bit R page A dalam keadaan set. (Tanenbaum, Bab 3, Hlm. 110)
Pada algoritma ini, daftar page bisa juga dibuat berbentuk jam (clock page replacement algorithm) Algoritma penggantian page clock String Pengacuan >
Fault
2
3
2
1
2 >
2 3 >
2 3 >
>2* 2* 3 5 1 >1
F
F
F
5
F
2
4
5
2* 5 >1
2* 5 4
>2* >2 5* 5 4 3
F
3
2
5
>2* >2* >2* 5 5* 5* 3 3 3
F
6 Fault
Keterangan : * diacu > ditunjuk pointer
Sistem Operasi – Manajemen Memori 1
2
8/8
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
Fault
2 2
3 2 3
2 2 3
F F
Sistem Operasi – Manajemen Memori 1
1 2 3 1 F
5 2 5 1 F
2 2 5 1
4 4 5 4 F
5 4 5 4
3 3 5 4 F
2 3 5 2 F
5 3 5 2
2 3 5 2 7 Fault
9/8