bab 9: virtual memory latar belakang
TRANSCRIPT
1
Bab 9: Virtual Memory
Latar Belakang
Demand Paging
Pembuatan Proses
Page Replacement
Alokasi Frame
Thrashing
Contoh Sistem Operasi
Silberschatz, Galvin and Gagne 200210.1Operating System Concepts
Latar Belakang
Virtual memory – memisahkan memori logika dari memori fisik. Hanya bagian dari program yang berada di memori yang
k di k k iakan dieksekusi.
Ruang alamat logika dapat lebih besar daripada ruang alamat fisik.
Mengijinkan ruang alamat digunakan bersama-sama untuk beberapa proses.
Mengijinkan pembuatan proses yang lebih efisien.
Virtual memory dapat diimplementasikan dengan :
Silberschatz, Galvin and Gagne 200210.2Operating System Concepts
Virtual memory dapat diimplementasikan dengan : Demand paging
Demand segmentation
2
Virtual Memory lebih besari daripada Memori Fisik
Silberschatz, Galvin and Gagne 200210.3Operating System Concepts
Demand Paging
Membawa page ke dalam memori hanya jika diperlukan Memerlukan I/O yang lebih kecil
Memerlukan memori yang lebih kecil
Respon yang lebih cepat
User yang lebih banyak
Page diperlukan referensikan Referensi invalid abort
Tidak dalam memori bawa ke memori
Silberschatz, Galvin and Gagne 200210.4Operating System Concepts
3
Transfer Page dari Memori ke Ruang Disk yang Berurutan
Silberschatz, Galvin and Gagne 200210.5Operating System Concepts
Bit Valid-Invalid
Untuk setiap masukan ke page table entry, akan dihubungkan dengan bit valid–invalid (1 dalam memori, 0 tidak dalam memori)
Inisialisasi bit valid invalid dengan 0 pada semua masukan Inisialisasi bit valid–invalid dengan 0 pada semua masukan.
Contoh snapshop page table
111
10
Frame # valid-invalid bit
Silberschatz, Galvin and Gagne 200210.6Operating System Concepts
Selamat menterjemahkan alamat, jika bit valid-invalid dalam masukan page table adalah 0 page fault.
00
page table
4
Page Table jika beberapa Page tidak berada di Memori Utama
Silberschatz, Galvin and Gagne 200210.7Operating System Concepts
Page Fault
Jika terdapat masukan yang direferensi ke page, referensi pertama akan trap ke OS page fault
OS melihat ke tabel lain untuk menentukan: Referensi Invalid abort.
Sedang tidak berada di memori.
Dapatkan frame kosong.
Swap page ke dalam frame.
Reset tabel, validasi bit = 1.
Restart instruksi: Least Recently Used
Silberschatz, Galvin and Gagne 200210.8Operating System Concepts
Restart instruksi: Least Recently Used Pindah blok
Lokasi auto increment/decrement
5
Langkah-langkah menangani Page Fault
Silberschatz, Galvin and Gagne 200210.9Operating System Concepts
Apa uang terjadi jika tidak terdapat frame bebas?
Page replacement – mencari beberapa page di dalam memori, titapi tidak digunakan, swap keluar algoritma
performansi – menginginkan algoritma yang menghasilkan jumlah page fault minimal
Page yang sama mungkin dibawa ke memori beberapa kali
Silberschatz, Galvin and Gagne 200210.10Operating System Concepts
6
Performansi dari Demand Paging
Rata-rata Page Fault 0 p 1.0 Jika p = 0 tidak ada page faults
Jika p = 1, setiap referensi gagal
Effective Access Time (EAT)
EAT = (1 – p) x akses memori
+ p (waktu page fault
+ [swap page out ]
+ swap page in
+ waktu restart)
Silberschatz, Galvin and Gagne 200210.11Operating System Concepts
+ waktu restart)
Contoh Demand Paging
Waktu akses memori = 1 microsecond
50% dari waktu page harus dilakukan modifikasi sehingga perlu di swap out.
Waktu Swap Page = 10 msec = 10,000 msec
EAT = (1 – p) x 1 + p (15000)
1 + 15000P (in msec)
Silberschatz, Galvin and Gagne 200210.12Operating System Concepts
7
Pembuatan Proses
Virtual memory mempunyai keuntungan laing selama pembuatan proses:
- Copy-on-Write
- Memory-Mapped Files
Silberschatz, Galvin and Gagne 200210.13Operating System Concepts
Copy-on-Write
Copy-on-Write (COW) mengijinkan baik proses parent dan child menginisialisasi page yang sama.
Jik l h t difik i h dJika salah satu proses memodifikasi shared page, page akan di-copy.
COW memungkinkan pembuatan proses yang lebih efisian karena hanya memodifikasi page yang di-copy
Page bebas dialokasikan dari sebuah pool
Silberschatz, Galvin and Gagne 200210.14Operating System Concepts
8
Memory-Mapped Files
Memory-mapped file I/O memungkinkan file I/O diperlakukan sebagai routine memory access dengan memetakan blok disk ke page di memory
Sebuah file diinisialisasi read menggunakan demand paging. File dibaca dari sistem file ke page pada memori fisik sesuai ukuran page. Read/write ke/dari file diperlakukan seperti akses memori
Akses file dengan memperlakukan file I/O sebagai akses memori lebih sederhana daripada sistem call read() write()
Silberschatz, Galvin and Gagne 200210.15Operating System Concepts
Juga memungkinkan beberapa proses untuk memetakan file yang sama pada page di memori yang sama
Memory Mapped Files
Silberschatz, Galvin and Gagne 200210.16Operating System Concepts
9
Page Replacement
Mencegah over-allocation dari memori dengan rutin modifikasi page-fault untuk melakukan page replacement
Menggunakan bit modify (dirty) untuk mengurangi kegagalan transfer page – hanya page yang dimodifikasi yang ditulis di disk
Page replacement membedakan memori logika dan memori fisik – memori virtual besar dapat disediakan pada memori fisik yang kecil
Silberschatz, Galvin and Gagne 200210.17Operating System Concepts
Kebutuhan Page Replacement
Silberschatz, Galvin and Gagne 200210.18Operating System Concepts
10
Dasar-dasar Page Replacement
1. Cari lokasi page pada disk.
2. Cari frame bebas:- jika terdapat frame bebas, gunakan.- jika tidak ada frame bebas, gunakan algoritma
page replacement untuk memilih frame korban.
3. Baca page yang tepat ke frame bebas. Update tabel page.
Silberschatz, Galvin and Gagne 200210.19Operating System Concepts
4. Restart proses.
Page Replacement
Silberschatz, Galvin and Gagne 200210.20Operating System Concepts
11
Algoritma Page Replacement
Mencari rata-rata page-fault terkecil.
Evaluasi algoritma dengan menjalankan pada sekumpulan string memori referensi dan menghitung jumlah page fault pada string
String acuan dibangkitkan secara random atau dengan menelusuri sistem dan menyimpan alamat dari memory Contoh : jika ditelusuri proses tertentu, disimpan alamat berikut :
0100, 0432, 0101, 0612,0102, 0103, 0104,
0101, 0611, 0102, 0103,0104, 0101, 0610,
0102, 0103, 0104, 0101,0609, 0102, 0105
dimana 100 byte per page direduksi ke string referensi :1 4 1 6 1 6 1 6 1 6 1
Silberschatz, Galvin and Gagne 200210.21Operating System Concepts
1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1
Pada contoh berikut, string referensi sbb
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
Graf Page Fault VS Jumlah Frame
Silberschatz, Galvin and Gagne 200210.22Operating System Concepts
12
Algoritma First-In-First-Out (FIFO)
String Referensi: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
3 frame (3 page dapat di memori pada satu waktu per proses)
11 4 5
4 frame
1
2
3
1
2
3
4
1
2
5
3
4
9 page faults
1
2
1
2
5
1
4
5 10 page faults
Silberschatz, Galvin and Gagne 200210.23Operating System Concepts
FIFO Replacement – Belady’s Anomaly Lebih banyak frames page fault lebih kecil
33 2
p g
44 3
Page Replacement FIFO
Silberschatz, Galvin and Gagne 200210.24Operating System Concepts
13
Ilustrasi Belady’s Anamoly pada FIFO
Silberschatz, Galvin and Gagne 200210.25Operating System Concepts
Algoritma Optimal
Mengganti page yang tidak akan digunakan untuk periode waktu yang terlama.
Contoh 4 frame
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
2
3
4
6 page faults
4
Silberschatz, Galvin and Gagne 200210.26Operating System Concepts
Bagaimana cara mengetahuinya?
Digunakan untuk mengukur bagaimana performansi dari algoritma.
4 5
14
Page Replacement Optimal
Silberschatz, Galvin and Gagne 200210.27Operating System Concepts
Algoritma Least Recently Used (LRU) Mengganti page yang sudah tidak digunakan untuk
periode waktu yang terlama.
String Referensi: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1 5
Implementasi Counter Setiap masukan page mempunyai counter; setiap waktu
2
3 4
4 3
5
Silberschatz, Galvin and Gagne 200210.28Operating System Concepts
page direferensi melalui masukan, copy clock ke dalam counter.
Jika sebuah page perlu diubah, cari counter untuk menentukan mana yang diubah.
15
Page Replacement LRU
Silberschatz, Galvin and Gagne 200210.29Operating System Concepts
Algoritma LRU (Lanj.)
Implementasi Stack – menyimpan stack yang berisi nomor page dalam bentuk double link: Page yang direferensi:
Pindahkan ke atas
Membutuhkan 6 pointer yang diubah
Tidak ada pencarian replacement
Silberschatz, Galvin and Gagne 200210.30Operating System Concepts
16
Penggunaan Stack untuk menyimpan Page Referensi yang Sering digunakan
Silberschatz, Galvin and Gagne 200210.31Operating System Concepts
Allokasi Frame
Setiap proses membutuhkan jumlah page minimum.
Contoh: IBM 370 – 6 page untuk menangani instruksi SS MOVE: Instruksi 6 byte, bisa ditambah 2 page.
2 page untuk menangani from.
2 page untuk menangani to.
Dua skema utama alokasi Alokasi fix
Alokasi prioritas
Silberschatz, Galvin and Gagne 200210.32Operating System Concepts
17
Alokasi Fix
Alokasi sama (equal) – contoh, jika 100 frame dan 5 proses, masing-masing mendapat 20 page.
Alokasi proporsional – Alokasi berdasarkan ukuran proses.
mS
spa
m
sS
ps
iii
i
ii
untuk alokasi
framejumlah total
prosesukuran
10
64m
Silberschatz, Galvin and Gagne 200210.33Operating System Concepts
5964137127
56413710
127
10
2
1
2
a
a
s
si
Alokasi Prioritas
Menggunakan skema alokasi proposional menggunakan prioritas, bukan ukuran.
Jika proses Pi membangkitkan page fault, Memilih untuk replacement satu dari framenya.
Memilih untuk reprecement sebuah frame dari sebuah proses dengan nomor prioritas terendah.
Silberschatz, Galvin and Gagne 200210.34Operating System Concepts
18
Alokasi Global vs. Lokal
Replacement Global – proses memilih sebuah replacement frame dari sekumpulan semua frame; satu proses dapat mengambil sebuah frame dari yang lain.
Replacement Local – setiap proses dari hanya dari kumpulan alokasi frame nya sendiri.
Silberschatz, Galvin and Gagne 200210.35Operating System Concepts
Thrashing
Jika sebuah proses tidak “cukup” page, rata-rata page-fault sangat tinggi. Hal ini menyebabkan: Utilitas CPU yang rendah.
Sistem opreasi perlu meningkatkan tingkat multiprogramming.
Proses lain ditambahkan ke sistem.
Thrashing sebuah proses yang sibuk melakukan swapping page ke dalam dan keluar.
Silberschatz, Galvin and Gagne 200210.36Operating System Concepts
19
Thrashing
Mengapa paging bekerja?M d l l k li
Silberschatz, Galvin and Gagne 200210.37Operating System Concepts
Model lokalitas Proses migrasi dari satu lokasi ke lokasi lain.
Lokasi kemungkinan overlap.
Mengapa terjadi thrashing? ukuran lokasi > total ukuran memori
Contoh Sistem Operasi
Windows NT
Solaris 2
Silberschatz, Galvin and Gagne 200210.38Operating System Concepts
20
Windows NT
Menggunakan demand paging dengan clustering. Clustering membawa page fault.
Proses diset working set minimum dan working set maximummaximum.
Working set minimum adalah jumlah minimum page pada proses yang dijamin mendapat lokasi memori
Sebuah proses mungkin digunakan untuk beberapa page dapat ditambahkan ke working set maximum.
Jika jumlah memori bebas dalam sistem memenuhi threshold, automatic working set trimming digunakan untuk menyimpan jumlah memori bebas.
Silberschatz, Galvin and Gagne 200210.39Operating System Concepts
Working set trimming menghapus page dari proses yang mempunyai page melebihi working set minimum.
Solaris 2
Menyimpan daftar page bebas untuk menentukan proses yang fault.
Lotsfree – parameter threshold untuk memulai paging.p p g g
Paging dibentuk dengan proses pageout.
Pageout mencari page menggunakan algoritma modified clock.
Scanrate adalah rata-rata page mana yang dicari. Jangkauan dari slowscan ke fastscan.
Silberschatz, Galvin and Gagne 200210.40Operating System Concepts
Pageout dipanggil lebih sering tergantung jumlah ketersediaan memori bebas.
21
Solar Page Scanner
Silberschatz, Galvin and Gagne 200210.41Operating System Concepts