Bab 9: Virtual Memory. Latar Belakang

Bab 9: Virtual Memory  Latar Belakang  Demand Paging  Pembuatan Proses  Page Replacement  Alokasi Frame  Thrashing  Contoh Sistem Operasi

Operating System Concepts

10.1

Silberschatz, Galvin and Gagne 2002

Latar Belakang  Virtual memory – memisahkan memori logika dari

memori fisik.  Hanya bagian dari program yang berada di memori yang

akan k dieksekusi. di k k i  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 :  Demand paging  Demand segmentation


10.2


1

Virtual Memory lebih besari daripada Memori Fisik


10.3


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


10.4


2

Transfer Page dari Memori ke Ruang Disk yang Berurutan



10.5

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 valid–invalid invalid dengan 0 pada semua masukan. masukan  Contoh snapshop page table Frame #

valid-invalid bit

1 1 1 1 0  0 0 page table

 Selamat menterjemahkan alamat, jika bit valid-invalid dalam

masukan page table adalah 0  page fault.


10.6


3

Page Table jika beberapa Page tidak berada di Memori Utama


10.7


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  Pindah blok

 Lokasi auto increment/decrement Operating System Concepts

10.8


4

Langkah-langkah menangani Page Fault


10.9


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


10.10


5

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)


10.11


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)


10.12


6

Pembuatan Proses  Virtual memory mempunyai keuntungan laing selama

pembuatan proses: - Copy-on-Write - Memory-Mapped Files


10.13


Copy-on-Write  Copy-on-Write (COW) mengijinkan baik proses parent

dan child menginisialisasi page yang sama. Jik salah Jika l h satu t proses memodifikasi difik i shared h d 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


10.14


7

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()  Juga memungkinkan beberapa proses untuk memetakan file

yang sama pada page di memori yang sama


10.15


Memory Mapped Files


10.16


8

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


10.17


Kebutuhan Page Replacement


10.18


9

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. 4. Restart proses.


10.19


Page Replacement


10.20


10

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, 4, 1 1, 6 6, 1 1, 6 6, 1 1, 6 6, 1 1, 6 6, 1

 Pada contoh berikut, string referensi sbb

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.


10.21


Graf Page Fault VS Jumlah Frame


10.22


11

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)

 4 frame

1

1

4

5

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

page g faults 10 p

 FIFO Replacement – Belady’s Anomaly  Lebih banyak frames  page fault lebih kecil Operating System Concepts

10.23


Page Replacement FIFO


10.24


12

Ilustrasi Belady’s Anamoly pada FIFO



10.25

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

4

2

6 page faults

3 4

5

 Bagaimana cara mengetahuinya?  Digunakan untuk mengukur bagaimana performansi dari

algoritma. Operating System Concepts

10.26


13

Page Replacement Optimal


10.27


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

2 3

5

4

3

4

 Implementasi Counter  Setiap masukan page mempunyai counter; setiap waktu page direferensi melalui masukan, copy clock ke dalam counter.  Jika sebuah page perlu diubah, cari counter untuk menentukan mana yang diubah.


10.28


14

Page Replacement LRU


10.29


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


10.30


15

Penggunaan Stack untuk menyimpan Page Referensi yang Sering digunakan


10.31


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


10.32


16

Alokasi Fix  Alokasi sama (equal) – contoh, jika 100 frame dan 5

proses, masing-masing mendapat 20 page.  Alokasi proporsional – Alokasi berdasarkan ukuran proses. si  ukuran proses pi S   si

m  total jumlah frame ai  alokasi untuk pi 

si m S m  64

si  10 s2  127 10  64  5 137 127 a2   64  59 137 a1 


10.33


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.


10.34


17

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.


10.35


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.


10.36


18

Thrashing

 Mengapa paging bekerja?

M d l lokalitas Model l k li  Proses migrasi dari satu lokasi ke lokasi lain.  Lokasi kemungkinan overlap.

 Mengapa terjadi thrashing?

 ukuran lokasi > total ukuran memori


10.37


Contoh Sistem Operasi  Windows NT  Solaris 2


10.38


19

Windows NT  Menggunakan demand paging dengan clustering.

Clustering membawa page fault.  Proses diset working set minimum dan working set

maximum. maximum  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.  Working set trimming menghapus page dari proses yang mempunyai page melebihi working set minimum.


10.39


Solaris 2  Menyimpan daftar page bebas untuk menentukan proses yang

fault.  Lotsfree – p parameter threshold untuk memulai p paging. 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.  Pageout dipanggil lebih sering tergantung jumlah ketersediaan

memori bebas.


10.40


20

Solar Page Scanner


10.41


21

Bab 9: Virtual Memory. Latar Belakang

Recommend Documents