際際滷

際際滷Share a Scribd company logo
10 
Virtual Memori 
Edi Ismanto, S.T, M.Kom 
Mata Kuliah Sistem Operasi
2 
Virtual Memory 
 Latar Belakang 
 Demand Paging 
 Pembuatan Proses 
 Page Replacement 
 Alokasi Frame 
 Thrashing 
 Contoh Sistem Operasi
3 
Latar Belakang 
 Manajemen memori: 
 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. 
 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.
4 
Latar Belakang (cont.) 
 Q: Apakah sesungguhnya diperlukan seluruh 
program harus berada di memori? 
 Mayoritas kode program untuk menangani exception, 
kasus khusus dll. (sering tidak dieksekusi). 
 Deklarasi data (array, etc) lebih besar dari yang digunakan 
oleh program. 
 IDEA: 
 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.
5 
Latar Belakang (cont.) 
 Pros (jika OS yang melakukan overlay) 
 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. 
 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.
6 
Latar Belakang (cont.) 
 Konsep Virtual Memory: 
 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. 
 Virtual memory dapat diimplementasikan melalui : 
 Demand paging 
 Demand segmentation
7 
Virtual Memory Lebih Besar daripada 
Memori Fisik
8 
Demand Paging 
 Umumnya basis VM => paging. 
 Demand (sesuai dengan kebutuhan): 
 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? 
 Saat ekesekusi proses dan terjadi referensi logical address ke 
page tersebut. 
 invalid reference  abort 
 not-in-memory  bring to memory 
 Page table menyimpan daftar page frame yang telah 
dialokasikan untuk proses tersebut.
9 
Transfer Page Memory ke 
Contiguous Disk Space
10 
Valid-Invalid Bit 
 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.
11 
Page Table Ketika beberapa Page Tidak 
Berada di Main Memory
12 
Page Fault (OS tasks) 
 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. 
1. Get empty frame (frame free list). 
2. Swap page into frame. 
3. Reset tables, validation bit = 1. 
4. Restart instruction: yang terakhir 
eksekusi belum selesai, mis. 
 block move
13 
Tahap Penanganan Page Fault
14 
Tidak ada Frame yang bebas ? 
 Jika terdapat banyak proses, maka memori akan 
penuh (tidak ada page frame yang free). 
 Page replacement (penggantian) 
 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). 
 Page yang sama akan masuk ke memori pada waktu 
mendatang.
15 
Memory-Mapped File 
 Memory-mapped file I/O membolehkan file I/O diperlakukan sebagai 
rutin akses memori yang dipetakan sebagai blok disk ke dalam 
page memori 
 Suatu file diinisialisasikan menggunakan demand pagin. Suatu 
bagian page file dibaca dari file sistem ke page fisik. Subsequent 
membaca/menulis ke/dari file yang diperlakukan dalam urutan 
memori akses. 
 Secara sederhana file akses memperlakukan file I/O melalui memori 
melalui read() write() system calls. 
 Beberapa proses juga dapat dipetakan pada fiel yang sama pada 
memori yang di-share.
16 
Memory Mapped Files
17 
Page Replacement 
 Mencegah alokasi yang berlebihan dari memori 
dengan memodifikasi layanan rutin page-fault 
melalui page 
 Menggunakan modify bit untuk mengurangi 
overhead transfer page  hanya modifikasi page 
yang ditulis di disk. 
 Page replacement melengkapi pemisahan antara 
memori logik dan memori fisik  virtual memori yang 
besar dapat memenuhi kebutuhan memori fisik yang 
kecil.
18 
Kebutuhan Page Replacement
19 
Basic Page Replacement 
1. Tentukan lokasi yang diminta page pada disk. 
2. Tentuka frame bebas : 
 Jika tersedia frame bebas, maka dapat digunakan 
 Jika tidak tersedia frame bebas, gunakan algoritma penggantian 
untuk memilih kandidat frame. 
1. Baca page yang dituju ke dalam frame bebas (yang 
baru). Update page dan frame table. 
2. Restart process.
20 
Page Replacement
21 
Algoritma Page Replacement 
 Pilih page fault terendah. 
 Evaluasi algoritma dengan menjalankan 
particular string dari memori acuan (reference 
string) dan menghitung jumlah page fault dari 
string. 
 Contoh, reference string sebagai berikut : 
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
22 
Graph Page Faults vs. Jumlah Frame
23 
FIFO 
 FIFO 
 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.
24 
Algoritma FIFO 
 Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 
 3 frames (3 page yang dapat berada di memori pada suatu 
waktu per proses) 
 4 frames
25 
FIFO Page Replacement
26 
Ilustrasi Anomali Belady pada FIFO
27 
Optimal (Prediction) 
 OPT (optimal) 
 Mengganti page yang tidak digunakan dalam 
waktu dekat (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.
28 
Algoritma Optimal 
 Algoritma Optimal 
 Mengganti page yang tidak digunakan untuk periode waktu 
yang lama. 
 Contoh 4 frame 
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
29 
Optimal Page Replacement
30 
Least Recently Used 
 LRU (least recently used) 
 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.
31 
Algoritma LRU 
 Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
32 
LRU Page Replacement
33 
Algoritma Aproksimasi LRU 
 Reference bit 
 Setiap page berasosiasi dengan satu bit, inisialisasinya = 0 
 Ketika page dengan reference bit di set 1 
 Ganti satu dengan 0 (jika ada satu) 
 Second chance 
 Membutuhkan reference bit. 
 Jika page diganti (pada urutan clock) dengan reference bit 
= 1, maka 
 set reference bit 0. 
 Tinggalkan page di memori (berikan kesempatan kedua). 
 Ganti next page (dalam urutan clock) , subjek disamakan 
aturannya.
34 
Algoritma Second-Chance (clock) 
Page-Replacement Algorithm
35 
Alokasi Frame 
 Setiap proses membutuhkan minimum sejumlah 
pages. 
 Contoh : IBM 370  6 page untuk menangani 
instruksi SS MOVE : 
 instruksi 6 bytes, membutuhkan 2 pages. 
 2 pages untuk menangani from. 
 2 untuk menangani to. 
 Dua skema besar alokasi : 
 fixed allocation 
 priority allocation
36 
Fixed Allocation 
 Equal allocation  contoh jika 100 frame 
dan 5 proses, masing-masing 20 page. 
 Proportional allocation  mengalokasikan 
sesuai ukuran yang cocok dari proses
37 
Priority Allocation 
Menggunakan skema alokasi yang 
proporsional dengan mengedepankan 
menggunakan prioritas dibandingkan ukuran. 
 Jika proses Pi di-generate sebagai page 
fault, 
 Pilih satu replacement frame 
 Pilih replacement frame dari proses dengan 
prioritas terendah.
38 
Alokasi Global vs. Local 
 Global replacement  mengijinkan suatu 
proses untuk menyeleksi suatu frame yang 
akan fireplace dari sejumlah frame. 
 Local replacement proses hanya diijinkan 
menyeleksi frame-frame yang dialokasikan 
untuknya.
39 
Thrashing 
 Jika suatu proses tidak mempunyai page yang 
cukup, tingkat page fault menjadi tinggi If a process 
does not have enough pages, the page-fault rate is 
very high. Hal tersebut dapat dilihat dari : 
 Sistem operasi meningkatkan multiprogramming. 
 Utilisasi CPU meningkat sejalan dengan bertambahnya 
multiprogramming 
 Proses lain ditambahkan ke dalam sistem. 
 Thrashing 尊 suatu proses yang sibuk melakukan 
swap page in dan out.
40 
Thrashing 
 Mengapa paging dapat bekerja ? 
Model Lokalitas 
 Proses pemindahan dari satu lokasi ke lokasi lain. 
 Terjadi overlap lokalitas. 
 Mengapa thrashing terjadi ? 
S ukuran lokalitas  total ukuran memory
41 
Lokalitas pada Pola 
Memory-Reference Pattern
42 
Working-Set Model 
 D 尊 jendela working-set 尊 fixed number pada page references 
Contoh : 10,000 instruksi 
 WSSi (working set pada proses Pi) = 
jumlah page reference pada saat akhir D (beragam waktu) 
 jika D terlalu kecil akan mencakup seluruh lokalitas 
 jika D terlalu besar akan mencakup sebagian lokalitas. 
 jika D = 促  akan mencakup seluruh program 
 D = S WSSi 尊 total permintaan frames 
 if D  m  Thrashing 
 Kebijakan, jika D  m, maka menahan satu proses .
43 
Working-set model
44 
Pertimbangan Lain 
 Prepaging 
 Page size selection 
 fragmentation 
 table size 
 I/O overhead 
 locality

More Related Content

Virtual Memory

  • 1. 10 Virtual Memori Edi Ismanto, S.T, M.Kom Mata Kuliah Sistem Operasi
  • 2. 2 Virtual Memory Latar Belakang Demand Paging Pembuatan Proses Page Replacement Alokasi Frame Thrashing Contoh Sistem Operasi
  • 3. 3 Latar Belakang Manajemen memori: 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. 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.
  • 4. 4 Latar Belakang (cont.) Q: Apakah sesungguhnya diperlukan seluruh program harus berada di memori? Mayoritas kode program untuk menangani exception, kasus khusus dll. (sering tidak dieksekusi). Deklarasi data (array, etc) lebih besar dari yang digunakan oleh program. IDEA: 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.
  • 5. 5 Latar Belakang (cont.) Pros (jika OS yang melakukan overlay) 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. 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.
  • 6. 6 Latar Belakang (cont.) Konsep Virtual Memory: 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. Virtual memory dapat diimplementasikan melalui : Demand paging Demand segmentation
  • 7. 7 Virtual Memory Lebih Besar daripada Memori Fisik
  • 8. 8 Demand Paging Umumnya basis VM => paging. Demand (sesuai dengan kebutuhan): 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? Saat ekesekusi proses dan terjadi referensi logical address ke page tersebut. invalid reference abort not-in-memory bring to memory Page table menyimpan daftar page frame yang telah dialokasikan untuk proses tersebut.
  • 9. 9 Transfer Page Memory ke Contiguous Disk Space
  • 10. 10 Valid-Invalid Bit 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.
  • 11. 11 Page Table Ketika beberapa Page Tidak Berada di Main Memory
  • 12. 12 Page Fault (OS tasks) 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. 1. Get empty frame (frame free list). 2. Swap page into frame. 3. Reset tables, validation bit = 1. 4. Restart instruction: yang terakhir eksekusi belum selesai, mis. block move
  • 13. 13 Tahap Penanganan Page Fault
  • 14. 14 Tidak ada Frame yang bebas ? Jika terdapat banyak proses, maka memori akan penuh (tidak ada page frame yang free). Page replacement (penggantian) 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). Page yang sama akan masuk ke memori pada waktu mendatang.
  • 15. 15 Memory-Mapped File Memory-mapped file I/O membolehkan file I/O diperlakukan sebagai rutin akses memori yang dipetakan sebagai blok disk ke dalam page memori Suatu file diinisialisasikan menggunakan demand pagin. Suatu bagian page file dibaca dari file sistem ke page fisik. Subsequent membaca/menulis ke/dari file yang diperlakukan dalam urutan memori akses. Secara sederhana file akses memperlakukan file I/O melalui memori melalui read() write() system calls. Beberapa proses juga dapat dipetakan pada fiel yang sama pada memori yang di-share.
  • 17. 17 Page Replacement Mencegah alokasi yang berlebihan dari memori dengan memodifikasi layanan rutin page-fault melalui page Menggunakan modify bit untuk mengurangi overhead transfer page hanya modifikasi page yang ditulis di disk. Page replacement melengkapi pemisahan antara memori logik dan memori fisik virtual memori yang besar dapat memenuhi kebutuhan memori fisik yang kecil.
  • 18. 18 Kebutuhan Page Replacement
  • 19. 19 Basic Page Replacement 1. Tentukan lokasi yang diminta page pada disk. 2. Tentuka frame bebas : Jika tersedia frame bebas, maka dapat digunakan Jika tidak tersedia frame bebas, gunakan algoritma penggantian untuk memilih kandidat frame. 1. Baca page yang dituju ke dalam frame bebas (yang baru). Update page dan frame table. 2. Restart process.
  • 21. 21 Algoritma Page Replacement Pilih page fault terendah. Evaluasi algoritma dengan menjalankan particular string dari memori acuan (reference string) dan menghitung jumlah page fault dari string. Contoh, reference string sebagai berikut : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
  • 22. 22 Graph Page Faults vs. Jumlah Frame
  • 23. 23 FIFO FIFO 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.
  • 24. 24 Algoritma FIFO Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 page yang dapat berada di memori pada suatu waktu per proses) 4 frames
  • 25. 25 FIFO Page Replacement
  • 26. 26 Ilustrasi Anomali Belady pada FIFO
  • 27. 27 Optimal (Prediction) OPT (optimal) Mengganti page yang tidak digunakan dalam waktu dekat (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.
  • 28. 28 Algoritma Optimal Algoritma Optimal Mengganti page yang tidak digunakan untuk periode waktu yang lama. Contoh 4 frame 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  • 29. 29 Optimal Page Replacement
  • 30. 30 Least Recently Used LRU (least recently used) 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.
  • 31. 31 Algoritma LRU Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  • 32. 32 LRU Page Replacement
  • 33. 33 Algoritma Aproksimasi LRU Reference bit Setiap page berasosiasi dengan satu bit, inisialisasinya = 0 Ketika page dengan reference bit di set 1 Ganti satu dengan 0 (jika ada satu) Second chance Membutuhkan reference bit. Jika page diganti (pada urutan clock) dengan reference bit = 1, maka set reference bit 0. Tinggalkan page di memori (berikan kesempatan kedua). Ganti next page (dalam urutan clock) , subjek disamakan aturannya.
  • 34. 34 Algoritma Second-Chance (clock) Page-Replacement Algorithm
  • 35. 35 Alokasi Frame Setiap proses membutuhkan minimum sejumlah pages. Contoh : IBM 370 6 page untuk menangani instruksi SS MOVE : instruksi 6 bytes, membutuhkan 2 pages. 2 pages untuk menangani from. 2 untuk menangani to. Dua skema besar alokasi : fixed allocation priority allocation
  • 36. 36 Fixed Allocation Equal allocation contoh jika 100 frame dan 5 proses, masing-masing 20 page. Proportional allocation mengalokasikan sesuai ukuran yang cocok dari proses
  • 37. 37 Priority Allocation Menggunakan skema alokasi yang proporsional dengan mengedepankan menggunakan prioritas dibandingkan ukuran. Jika proses Pi di-generate sebagai page fault, Pilih satu replacement frame Pilih replacement frame dari proses dengan prioritas terendah.
  • 38. 38 Alokasi Global vs. Local Global replacement mengijinkan suatu proses untuk menyeleksi suatu frame yang akan fireplace dari sejumlah frame. Local replacement proses hanya diijinkan menyeleksi frame-frame yang dialokasikan untuknya.
  • 39. 39 Thrashing Jika suatu proses tidak mempunyai page yang cukup, tingkat page fault menjadi tinggi If a process does not have enough pages, the page-fault rate is very high. Hal tersebut dapat dilihat dari : Sistem operasi meningkatkan multiprogramming. Utilisasi CPU meningkat sejalan dengan bertambahnya multiprogramming Proses lain ditambahkan ke dalam sistem. Thrashing 尊 suatu proses yang sibuk melakukan swap page in dan out.
  • 40. 40 Thrashing Mengapa paging dapat bekerja ? Model Lokalitas Proses pemindahan dari satu lokasi ke lokasi lain. Terjadi overlap lokalitas. Mengapa thrashing terjadi ? S ukuran lokalitas total ukuran memory
  • 41. 41 Lokalitas pada Pola Memory-Reference Pattern
  • 42. 42 Working-Set Model D 尊 jendela working-set 尊 fixed number pada page references Contoh : 10,000 instruksi WSSi (working set pada proses Pi) = jumlah page reference pada saat akhir D (beragam waktu) jika D terlalu kecil akan mencakup seluruh lokalitas jika D terlalu besar akan mencakup sebagian lokalitas. jika D = 促 akan mencakup seluruh program D = S WSSi 尊 total permintaan frames if D m Thrashing Kebijakan, jika D m, maka menahan satu proses .
  • 44. 44 Pertimbangan Lain Prepaging Page size selection fragmentation table size I/O overhead locality