Virtual Memory

Virtual MemoryVirtual Memory

PembahasanPembahasan

• OverviewOverview• Demand PagingDemand Paging

OverviewOverview

• Konsep manajemen memori sebelumnya :Konsep manajemen memori sebelumnya :– Me-maintain banyak proses yang running dalam Me-maintain banyak proses yang running dalam

memori secara multiprogrammingmemori secara multiprogramming– Proses berada dalam memori fisik sebelum Proses berada dalam memori fisik sebelum

dieksekusidieksekusi• Dalam overlaying user harus men-dekomposisi struktur Dalam overlaying user harus men-dekomposisi struktur

program dalam algoritmanya dan menspesifikasi modul-program dalam algoritmanya dan menspesifikasi modul-modul overlaynyamodul overlaynya

OverviewOverview

• Isi program :Isi program :– Algoritma utama yang aktif mengolah dataAlgoritma utama yang aktif mengolah data– Penanganan kondisi error (exceptional condition) Penanganan kondisi error (exceptional condition)

yang amat jarang terjadiyang amat jarang terjadi– Struktur data dynamic allocated yang terpakai Struktur data dynamic allocated yang terpakai

secara efektifsecara efektif– Struktur data fixed allocated yang biasanya hanya Struktur data fixed allocated yang biasanya hanya

sebagian yang digunakansebagian yang digunakan– Modul-modul tertentu yang jarang digunakanModul-modul tertentu yang jarang digunakan

OverviewOverview• Keuntungan jika tidak semua bagian tersebut Keuntungan jika tidak semua bagian tersebut

ada di memori (hanya bagian yang paling aktif) ada di memori (hanya bagian yang paling aktif) ::– Program tidak terkendalakan oleh jumlah memori Program tidak terkendalakan oleh jumlah memori

fisik ; program bisa amat besarfisik ; program bisa amat besar– Program-program pengendali error Program-program pengendali error (error handling(error handling) )

jarang digunakan.jarang digunakan.– Array, list Array, list atau tabel yang dialokasikan melebihi atau tabel yang dialokasikan melebihi

kapasitas yang digunakan.kapasitas yang digunakan.– Program-program yang dijalankan belakangan.Program-program yang dijalankan belakangan.– Lebih banyak program yang dapat running secara Lebih banyak program yang dapat running secara

konkuren di memori; utilisasi CPU meningkatkonkuren di memori; utilisasi CPU meningkat– Lebih sedikit I/O untuk loading/swapping ; program Lebih sedikit I/O untuk loading/swapping ; program

user lebih cepatuser lebih cepat

OverviewOverview

• Konsep Virtual MemoryKonsep Virtual Memory– Melihat memori sebagai “cache” dan disk sebagai Melihat memori sebagai “cache” dan disk sebagai

“memori”“memori”– Implementasi dengan demand paging : bagian Implementasi dengan demand paging : bagian

program berada dalam memori adalah page-page program berada dalam memori adalah page-page yang sesuai dengan kebutuhanyang sesuai dengan kebutuhan

– Dapat diimplementasikan melalui :Dapat diimplementasikan melalui :• Demand pagingDemand paging• Demand segmentation (page segmentasi)Demand segmentation (page segmentasi)

Diagram Virtual Memory lebih Diagram Virtual Memory lebih besar dari Physical Memorybesar dari Physical Memory

Demand PagingDemand Paging

• Sama dengan teknik paging dengan swappingSama dengan teknik paging dengan swapping• Proses berada dalam secondary storage Proses berada dalam secondary storage

(biasanya disk) yang terbagi dalam sejumlah (biasanya disk) yang terbagi dalam sejumlah pagepage

• Untuk dapat dieksekusi maka page proses Untuk dapat dieksekusi maka page proses yang diperlukan harus ada di memoriyang diperlukan harus ada di memori– Jika belum ada maka page di-swap in (dalam hal ini Jika belum ada maka page di-swap in (dalam hal ini

swapper lebih tepat disebut pager, swap-in/out swapper lebih tepat disebut pager, swap-in/out menjadi page-in/out)menjadi page-in/out)

Demand Paging Virtual Memory - Demand Paging Virtual Memory - Physical MemoryPhysical Memory

Demand Demand pagepage

Apakah page di memori ?

Ada, lalu akses

Tidak ada, maka page di load

Swap page


• Pertanyaan saat page-in :Pertanyaan saat page-in :– Page mana yang akan di page-out ?Page mana yang akan di page-out ?– Apakah frame yang akan ditempati kosong ?Apakah frame yang akan ditempati kosong ?– Jika suatu page yang di page-out merupakan data, Jika suatu page yang di page-out merupakan data,

perlu / tidak page di storage di-refresh ?perlu / tidak page di storage di-refresh ?


• Periksa tabel internal (biasanya pada PCB = Periksa tabel internal (biasanya pada PCB = process control blockprocess control block) apakah referensi ) apakah referensi valid/invalidvalid/invalid

• Bila valid tapi belum ada maka di page-inBila valid tapi belum ada maka di page-in• Jika invalid, maka batalkan prosesJika invalid, maka batalkan proses

Transfer of a Paged Memory to Transfer of a Paged Memory to Contiguous Disk SpaceContiguous Disk Space

Dukungan HardwareDukungan Hardware

• Page table : tabel memiliki valid/invalid bit serta Page table : tabel memiliki valid/invalid bit serta bit proteksi khususbit proteksi khusus

• Secondary memory : memori yang menyimpan Secondary memory : memori yang menyimpan seluruh page (biasanya disk)seluruh page (biasanya disk)– Dikenal sebagai swap device dan bagian disk yang Dikenal sebagai swap device dan bagian disk yang

digunakan untuk swap disebut swap space (backing digunakan untuk swap disebut swap space (backing store)store)

Valid-Invalid BitValid-Invalid Bit• Masing-masing entry page table memiliki nilai :Masing-masing entry page table memiliki nilai :

– (1 (1 in-memory, 0 in-memory, 0 not-in-memory) not-in-memory)

• Inisialisasi valid–invalid bit di-set 0 untuk semua entry Inisialisasi valid–invalid bit di-set 0 untuk semua entry page tablepage table

• Contoh page table :Contoh page table :

• Selama translasi address, jika valid–invalid bit dalam Selama translasi address, jika valid–invalid bit dalam page table adalah 0 page table adalah 0 page fault. page fault.

111

1

0

00

Frame # valid-invalid bit

page table

Page Table When Some Pages Page Table When Some Pages Are Not in Main MemoryAre Not in Main Memory

Dukungan SoftwareDukungan Software

• Kendala arsitektur : kemampuan me-restart Kendala arsitektur : kemampuan me-restart instruksi setelah terjadi page-faultinstruksi setelah terjadi page-fault

• Page fault bisa terjadi pada :Page fault bisa terjadi pada :– Memory (data) referenceMemory (data) reference– Instruction fetchInstruction fetch

Contoh :Contoh :

• Instruksi 3 address “ADD C, A, B” dilakukan Instruksi 3 address “ADD C, A, B” dilakukan dalam beberapa tahap :dalam beberapa tahap :– Fetch instruksi ADDFetch instruksi ADD– Fetch data A ke dalam register RaFetch data A ke dalam register Ra– Fetch data B ke dalam register RbFetch data B ke dalam register Rb– Add Ra dan Rb dan hasilnya di register RcAdd Ra dan Rb dan hasilnya di register Rc– Store hasil Rc ke CStore hasil Rc ke C

• Page fault terjadi pada salah satu tahap Page fault terjadi pada salah satu tahap memerlukan pengulangan dari awalmemerlukan pengulangan dari awal

Steps in Handling a Page FaultSteps in Handling a Page Fault

Apa yang terjadi jika tidak ada Apa yang terjadi jika tidak ada frame yang kosong ?frame yang kosong ?

• Page replacement Page replacement – temukan page dalam – temukan page dalam memori, tetapi tidak sedang digunakan, swap-memori, tetapi tidak sedang digunakan, swap-out page tersebutout page tersebut– Algoritma yang digunakanAlgoritma yang digunakan– Performance – algoritma yang digunakan adalah Performance – algoritma yang digunakan adalah

yang menghasilkan jumlah minimum page faultyang menghasilkan jumlah minimum page fault

Performance Demand PagingPerformance Demand Paging

• Rasio Page Fault 0 Rasio Page Fault 0 pp 1.0 1.0– if if pp = 0 no page faults = 0 no page faults – if if pp = 1, every reference is a fault = 1, every reference is a fault

• Effective Access Time (EAT)Effective Access Time (EAT)EAT = (1 – EAT = (1 – pp) x memory access time) x memory access time

+ + pp (page fault overhead (page fault overhead+ [swap page out ]+ [swap page out ]+ swap page in+ swap page in+ restart overhead)+ restart overhead)

Contoh Demand PagingContoh Demand Paging

• Memory access time = 1 microsecond (1 Memory access time = 1 microsecond (1 sec)sec)• 50% dari waktu page yang digantikan (50% dari waktu page yang digantikan (replacereplace), ),

membutuhkan swap-outmembutuhkan swap-out• Swap Page Time = 10 msec = 10,000 Swap Page Time = 10 msec = 10,000 secsec

EAT = (1 – p) x 1 + p (15000)EAT = (1 – p) x 1 + p (15000)

= 1 + 15000p (dalam = 1 + 15000p (dalam sec)sec)

5000 5000 sec sec overhead overhead

Page Replacement PolicyPage Replacement Policy

• Performance (Performance (page fault ratiopage fault ratio) bergantung pada ) bergantung pada page replace policy agar page replace policy agar page fault rate page fault rate (PFR) (PFR) sekecil mungkin.sekecil mungkin.

• Jadi pemilihan policy untuk page replacement Jadi pemilihan policy untuk page replacement sangat kritis terhadap performance sistem sangat kritis terhadap performance sistem keseluruhan.keseluruhan.

Swap SpaceSwap Space

• Aspek penting dalam demand paging adalah menangani penggunaan swap space (ruang disk yang digunakan untuk swap)

• Suatu bagian dalam disk dijadikan swap space (di luar sistem file) sebagai penyimpan “virtual memory”

Over-Allocating MemoryOver-Allocating Memory

• Peningkatan degree of multiprogramming akan sampai pada situasi Over Allocating Memory– Saat terjadi page-fault & hendak page-in ternyata

tidak ada frame kosong tersedia– Solusi OS : terminate proses user ? NO.

Paging harus transparan bagi user.

SolusiSolusi

• Thrashing : swap-out suatu proses (penurunan degree of multiprogramming)

• Page replacement : mencari salah satu frame yang tidak sedang digunakan dan membebaskannya– Menuliskan isi sebelumnya ke swap-space– Mengubah page table dimana page tidak ada di

memori

Kebutuhan Page Replacement – Kebutuhan Page Replacement – Over-Allocating MemoryOver-Allocating Memory

Page Fault ServicePage Fault Service

• Menemukan lokasi dari page di dalam disk• Menemukan free-frame, jika ada gunakan frame

tersebut untuk page yang bersangkutan dan jika tidak ada :– Mencari frame yang akan di-replace– Page-out frame tersebut ke swap-space dan ubah

tabel page & frame– Page-in page yang diminta ke frame kosong yang

baru, serta ubah tabel page & frame– Mulai kembali ke user proses

Page ReplacementPage Replacement

Dirty bit (Modify-bit)Dirty bit (Modify-bit)• Saat tidak ditemukan frame kosong maka

dilakukan dua kali page transfer (in & out)• Untuk mengurangi overhead operasi ini

digunakan dirty-bit pada setiap page/frame untuk menunjukkan perlu/tidaknya page dalam disk diupdate (telah terjadi modifikasi)– Modify bit di-set ketika word/byte dalam page ditulis

(write) page telah dimodifikasi. page telah dimodifikasi.– Ketika memilih page untuk di-replace, modify bit dibaca Ketika memilih page untuk di-replace, modify bit dibaca

dulu.dulu.– Jika bit tersebut di-set, maka page tersebut sudah Jika bit tersebut di-set, maka page tersebut sudah

dimodifikasi sejak dibaca di disk dimodifikasi sejak dibaca di disk write page ke disk. write page ke disk.– Jika bit tersebut tidak di-set, maka page tersebut belum Jika bit tersebut tidak di-set, maka page tersebut belum

dimodifikasi sejak dibaca di memory dimodifikasi sejak dibaca di memory jika copy dari jika copy dari page tersebut di disk belum di overwrite, tidak perlu page tersebut di disk belum di overwrite, tidak perlu lagi write page memory ke disk karena sudah ada.lagi write page memory ke disk karena sudah ada.

Frame Allocation – Page Frame Allocation – Page ReplacementReplacement

• Dua masalah :– Frame allocation algorithm : menentukan berapa

banyak frame dialokasikan untuk suatu/setiap proses– Page-replacement algorithm : menentukan frame

mana yang dipilih untuk di page-out

• Pemilihan algoritma yang tepat sangat penting, karena pemrosesan pada disk I/O costnya mahal (berpengaruh pada effective acces time)

Page ReplacementPage Replacement

• Terdapat banyak skema/algoritma• Kriteria pemilihan algoritma yang sesuai :

meminimisasi page-fault rate• Evaluasi dengan string : string dari aktifitas-

aktifitas memory reference– String dari memory reference dinamakan reference

string– Secara empiris direkam dari referensi yang terjadi

pada running program– Secara hipotesis digenerate secara acak (random

number generator)– Menghitung jumlah page fault pada string tersebut

Page Fault vs Jumlah FramePage Fault vs Jumlah Frame

• Bertambahnya jumlah frame akibat penambahan physical memory space dapat mengurangi PFR

• Tanpa penambahan tersebut maka memperkecil ukuran frame/page yang akhirnya meningkatkan page fault

Grafik Page Faults vs Jumlah Grafik Page Faults vs Jumlah FrameFrame

Page Replacement PolicyPage Replacement Policy

• Algoritma First In First Out (FIFO)• Algoritma Optimal (OPT)• Algoritma Least Recently Used (LRU)• Algoritma Second Change (Clock)• Algoritma Enhanced Second Change (Clock)• Algoritma Counting• Algoritma Page Buffering

Reference StringReference String

• Dalam pembahasan algoritma-algoritma reference string disederhanakan dengan deretan page number (bukan address-address referensi)

• Contoh :– 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101,

0611, dst– Digantikan (page size = 100 byte) dengan : 1, 4, 1, 6,

1, 6, dst

Algoritma First In First Out Algoritma First In First Out (FIFO)(FIFO)

• Page yang di-replace adalah page yang paling “tua” (paling lama berada di memory secara terus menerus)

• Realisasinya setiap page menyimpan data waktu page yang bersangkutan di-page-in atau menggunakan struktur queue

• Mudah di-implementasikan tapi performance tidak selalu baik

FIFO Page ReplacementFIFO Page Replacement

• Reference string : 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

• Jumlah frame = 3• Page fault terjadi = 15 kali

Anomaly BeladyAnomaly Belady

• Anomali yang terjadi : PFR naik saat jumlah frame ditingkatkan

• Contoh, jika reference string :– 1,2,3,4,1,2,5,1,2,3,4,5– Jumlah frame = 3, PFR = 9 page fault– Jumlah frame = 4, PFR = 10 page fault

FIFO Illustrating Belady’s FIFO Illustrating Belady’s AnamolyAnamoly

Algoritma Optimal (OPT)Algoritma Optimal (OPT)

• Jika diketahui page-page mana yang berikutnya akan diakses, maka page yang tidak akan digunakan dalam waktu dekat (ie. Selang waktu terlama hingga diakses kembali) yang di-replace.

• Anomali Belady tidak berlaku• Secara teoritis paling optimal tapi dalam

kenyataannya sulit diimplementasikan

Optimal Optimal Page ReplacementPage Replacement• Reference string :

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1• Jumlah frame = 3• Page fault terjadi = 9 kali

Pada referensi ke-4 terlihat page 7 akan di-replace dengan page 2, karena page 7 baru akan digunakan pada referensi ke-18, sedangkan page 0 akan digunakan pada referensi ke-5 dan page 1 akan digunakan pada referensi ke-14

Algoritma Least Recently Used Algoritma Least Recently Used (LRU)(LRU)

• Algoritma LRU merupakan perpaduan antara FIFO dan OPT

• Mengaproksimasi Algoritma Optimal– Perkiraan akses yang akan datang (forward

information) diestimasi dengan menggunakan informasi akses yang lalu (backward information)

• Page dalam memori yang paling lama tidak diakses yang di-replace

• Jika SR = reverse S maka PFR OPT pada S sama dengan PFR LRU pada SR

LRU Page ReplacementLRU Page Replacement

• Reference string : 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

• Jumlah frame = 3• Page fault terjadi = 12 kali

END OF MODUL - 10END OF MODUL - 10

Virtual Memory

Documents