Virtual Memory Ch. 9 SISTIM OPERASI (Operating System) IKI-20230 Johny Moningka (
[email protected]) Fakultas Ilmu Komputer Universitas Indonesia Semester 2000/2001
Virtual Memory n n n n n n
Background Demand Paging Performance of Demand Paging Page-Replacement Algorithms Allocation of Frames Thrashing
OS/ JM -2001/v1.1/2
1
Background n
Manajemen memori: n n
Alokasi “space” memori fisik kepada program yang diekesekusi (proses). Pendekatan: Alokasi space sesuai dengan kebutuhan “logical address” => seluruh program berada di memori fisik. • Kapasitas memori harus sangat besar untuk mendukung “multiprogramming”.
n n
Bagaimana jika kapasitas memori terbatas? Pendekatan: Teknik Overlay (programming) dapat memanfaatkan kapasitas kecil untuk program yang besar. • Batasan (tidak transparant, cara khusus): program sangat spesifik untuk OS tertentu.
OS/ JM -2001/v1.1/3
n
Q: Apakah sesungguhnya diperlukan seluruh program harus berada di memori? n n
n
Mayoritas kode program untuk menangani “exception”, kasus khusus dll. (sering tidak dieksekusi). Deklarasi data (array, etc) lebih besar dari yang digunakan oleh program.
IDEA: n
n
Sebagian saja program (kode yang sedang dieksekusi) berada di memori, tidak harus serentak semua program berada di memori. Jika kode program diperlukan maka OS akan mengatur dan mengambil page yang berisi program tersebut dari “secondary storage” ke “main memory”.
OS/ JM -2001/v1.1/4
2
Background (2) n
Pro’s (jika OS yang melakukan “overlay”) n
Programmer dapat membuat program sesuai dengan kemampuan “logical address” (virtual address) tanpa harus menyusun modul mana yang harus ada di memori. • Fungsi OS sebagai “extended machine”: memberikan ilusi seolah-olah memori sangat besar, memudahkan penulisan program dan eksekusi program.
n
Proses dapat dieksekusi tanpa memerlukan memori fisik yang besar => banyak proses. • Fungsi OS sebagai “resource manager”: menggunakan utilitas memori yang terbatas untuk dapat menjalankan banyak proses.
OS/ JM -2001/v1.1/5
Background (3) n
Konsep Virtual Memory: n
n
n
n
n
Pemisahan antara “user logical memory” (virtual) dengan “physical memory”. Logical address space (program) dapat lebih besar dari alokasi memori fisik yang diberikan. Hanya sebagian kecil dari program yang harus berada di memori untuk eksekusi. Terdapat mekanisme untuk melakukan alokasi dan dealokasi page (swapped out dan in) sesuai dengan kebutuhan (referensi program). Terdapat bagian dari disk menyimpan sisa page (program) yang sedang dijalankan di memori.
OS/ JM -2001/v1.1/6
3
Demand Paging n n
Umumnya basis VM => paging. Demand (sesuai dengan kebutuhan): n n n n
n
Ambil/bawa page ke memory hanya jika diperlukan. Umumnya program memerlukan page sedikit (one by one). Less I/O & less memory (more users). Transfer cepat (faster response).
Kapan page dibutuhkan? n n
Saat ekesekusi proses dan terjadi referensi logical address ke page tersebut. Page table menyimpan daftar page frame yang telah dialokasikan untuk proses tersebut.
OS/ JM -2001/v1.1/7
Valid-Invalid Bit n
n
n
Setiap entry pada page table terdapat bit: Valid dan Invalid mengenai keberadaan page di memori fisik (1 ⇒ in-memory, 0 ⇒ not-in-memory) Saat awal: page belum berada di memori maka bit adalah 0 (not in memory). Jika terjadi referensi dan page frame yang akan diakses bit Valid-Invalid 0 => page fault.
Frame #
valid -invalid bit
1 1 1 1 0
M 0 0 page table
OS/ JM -2001/v1.1/8
4
Page Fault (OS tasks) n n
1. 2. 3. 4.
Saat pertama kali referensi ke page, trap ke OS => page fault. OS melakukan evaluasi, apakah alamat logical tersebut “legal”? OK, tapi belum berada di memori. Get empty frame (frame free list). Swap page into frame. Reset tables, validation bit = 1. Restart instruction: yang terakhir eksekusi belum selesai, mis. n
block move
page di memori
page di disk
OS/ JM -2001/v1.1/9
No free frame? n n
Jika terdapat banyak proses, maka memori akan penuh (tidak ada page frame yang free). Page replacement (penggantian) n
n n
Mencari kandidat “page” untuk diganti di memori dan “kemungkinan tidak digunakan” (allocate but not in used). Swap page tersebut dengan page yang baru. Algoritma: efisien dan mencapai min. jumlah page faults (karena kemungkinan page yang diganti harus di swap in lagi). • Same page may be brought into memory several times.
OS/ JM -2001/v1.1/10
5
Page Replacement n
Penggantian page n
n n
n
Harus memilih page (frame yang telah dialokasikan) yang ada di memori (victim). Page tsb. harus di tulis/simpan ke disk (?). Load page baru ke frame tersebut.
Algoritma: n
n
Objektif: mengurangi “traffic” pages dari memori ke disk dan sebaliknya (page fault rate). Analisa: menggunakan “trace” (strings) dari page yang direference oleh processor dan melihat jumlah page fault yang terjadi.
OS/ JM -2001/v1.1/11
FIFO n
FIFO n n
n
Mengganti page yang terlama berada di memori. Data struktur FIFO queue yang menyimpan kedatangan pages di memori. Masalah: menambah page frame => page fault tidak berkurang.
OS/ JM -2001/v1.1/12
6
FIFO Algorithm n n
n
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 pages can be in memory at a time per process) 1 1 4 5
4 frames
2
2
1
3
3
3
2
4
1
1
5
4
2
2
1
5
3
3
2
4
4
3
9 page faults
10 page faults
FIFO Replacement – Belady’s Anomaly Seharusnya lebih banyak page frames ⇒ less page faults
OS/ JM -2001/v1.1/13
Optimal (Prediction) n
OPT (optimal) n
n
n
Mengganti page yang tidak akan digunakan (paling lama tidak diakses). Menggunakan priority lists page mana yang tidak akan diakses (“in the near future”). Sulit diterapkan (prediksi): terbaik dan “benchmark” untuk algoritma yang lain.
OS/ JM -2001/v1.1/14
7
Optimal Algorithm n Replace
page that will not be used for longest period of time. n 4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1
4
2
6 page faults
3 4
5
n How
do you know this? n Used for measuring how well your algorithm performs. OS/ JM -2001/v1.1/15
Least Recently Used n
LRU (least recently used) n
n
n
Mengganti page yang paling lama tidak digunakan/diakses. Asumsi page yang diakses sekarang => kemungkinan besar akan diakses lagi (predict?). Masalah: mendeteksi (memelihara) LRU semua page => bantuan hardware yang cukup rumit.
OS/ JM -2001/v1.1/16
8
LRU Algorithm n
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1
5
2
8 page faults
3
5
4
3
4
OS/ JM -2001/v1.1/17
LRU Approximation Algorithms n
Reference bit n n n
n
With each page associate a bit, initially = 0 When page is referenced bit set to 1. Replace the one which is 0 (if one exists). We do not know the order, however.
Second chance n n
Need reference bit. If page to be replaced (in clock order) has reference bit = 1. then: • set reference bit 0. • leave page in memory (berikan kesempatan kedua). • replace next page (in clock order), subject to same rules.
OS/ JM -2001/v1.1/18
9
