SISTEM PAGING
Memori Maya
Program yang dijalankan harus dimuatdi memori utama. Masalah muncul ketika program lebih besar dibanding memori utama yang tersedia.
Terdapat dua solusi, yaitu :
1. Overlay
2. Memori Maya (virtual Memory)
Konsep Overlay
Dimana program yang dijalankan dipecah menjadi beberapa bagian yang dapat dimuat memori (overlay). Overlay yang belum diperlukan pada saat program berjalan (tidak sedang di eksekusi) disimpan di disk, dimana nantinya overlay tersebut akan dimuat ke memori begitu diperlukan dalam eksekusinya.
Konsep memori Maya
Adalah kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Konsep ini pertama kali dikemukakan Fotheringham pada tahun 1961 untuk sistem komputer Atlas di Universitas Manchester, Inggris.
Penggunaan
Program 10 Mbyte dapat berjalan dimesin 2 Mbyte, yaitu memilih bagian proses sebesar 2 Mbyte secara hati-hati dan ditaruh di memori. Bagian – bagian proses di-swap antara disk dan memori saat diperlukan secara otomatis oleh sistem operasi.
Deskripsi Sistem Paging
Sistem paging mengimplementasikan ruang alamat besar pada memori kecil menggunakan index register, base register, dan segment register dan lain-lain.
Istilah pada sistem paging:
– Alamat maya
– Alamat nyata
– Page
– Page frame
– Page fault
– MMU
• Alamat maya
alamat yang dihasilkan perhitungan menggunakan index register, base register, segment register dan sebagainya.
• Alamat nyata
alamat di memori utama fisik disebut memori ruang alamat nyata (real address space)
• Page
unit terkecil virtual address space. Merupakan proses kelipatan page yang berukuran sama.
• Page fram
unit terkecil memori fisik. Dibagi menjadi sejumlah unit berukuran tetap (page frame)
• Page fault
exception untuk permintaan alokasi page ke memori.
Hubungan Antara Ruang Alamat Maya dan Alamat fisik
• Memory Management Unit (MMU)
chip atau kumpulan chip yang memetakan alamat maya ke alamat fisik.
MMU mengirim alamat fisik ke Memori
Kontigu Semu
10.2.1 Pemetaan Alamat
MMU mempunyai fungsi sbg :
Ø Pemetaan memori maya ke memori fisik
Ø Menerbitkan exception page fault
10.2.1.1 Skema Pemetaan
10.3 Penggantian Page
• Saat terjadi page fault berarti harus diputuskan page frame di memori fisik yang harus diganti.
• Banyaknya page fault menghasilkan banyak overhead.
Algoritma penggantian page
- Algoritma penggantian page acak
- Algoritma penggantian page optimal
- Algoritma penggantian page NRU (Not Recently Used)
- Algoritma penggantian page FIFO
- Algoritma penggantian page modifikasi dari FIFO
o Algoritma penggantian page kesempatan kedua
o Algoritma penggantian clock page
- Algoritma penggantian page LRU (Least Recently Used)
Algoritma Penggantian Page FIFO (First In First out)
Mekanisme algoritma
Algoritma ini memerlukan pengellaan senarai page di memori. Elemen terdepan senarai adalah page tertua dan ujung belakang adalah page paling mutakhir datang.
- Bila terjadi page fault, page elemen terdepan (page tertua) diganti dan page baru ditambahkan di ujung belakang senarai.
Dengan informasi mengenai lamanya berada di memori, maka algoritma ini daat memindahkan page yang sering digunakan. Bisa page itu berada terus di memori karena selalu digunakan. Page itu karena mengikuti pola antrian berdasar lama berada di memori menjadi elemen terdepan, diganti dan segera harus masuk kembali ke memori sehingga terjadi page fault kembali.
Algoritma FIFO murni jarang digunakan, tetapi dikombinasikan (modifikasi)
Modifikasi terhadap FIFO
Kelemahan FIFO adalah Algritma dapat memilih memindahkan page yang sering digunakan yang lama berada di dalam memori. Kemungkinan ini dapat dihindari dengan memindahkan page tidak diacu.
Variasi FIFO :
- Algoritma penggantian page kesempatan kedua (second chance pace replacement algorithm).
- Algritma penggantian page clock(clock page replacement algrithm).
Algoritma Penggantian Page Kesempatan kedua
Mekanisme:
- Saat terjdi page fault, algoritma memilih page elemen terdepan diganti bila bit R bernilai 0
- Bila bit R bernilai 1, maka bit page terdepan senarai direset menjadi 0 dan diletakkan ke ujung belakang senarai. Mekanisame ini kembali diterapkan ke elemen berikutnya.
Algoritma Penggantian Page Clock
Algritm penggantian page kesempatan kedua adalah algoritma yang memadai namun tidak efisien untuk memindahkan page-page senarainya, algoritma penggantian page clock merupakan perbaikan algoritma pertama.
Mekanisme :
- Semua page merupakan senarai melingkar membentuk pla jam terdapat penunjuk (pointer) ke page tertua
Ketika terjadi page fault, page yang ditunjuk diperiksa .
- Jika bit R bernilai 0, page diganti. Page baru ditempatkan di tempat page diganti. Dan penunjuk dimajukkan satu posisi ke page berikutnya.
- Jika bit R bernilai 1, bit R di reset menjadi 0, dan penunjuk dimajukan satu posisi seterusnya sampai menemui page dengan bit R bernilai 0.
Kedua algoritma adalah sama, hanya berbeda dalam implementasi :
- Algritma penggantian page kesempatan kedua menggunakan senarai lurus tak sirkular.
- Algoritma penggantian page clock menggunkana senarai sirkular.
Contoh Eksekusi Paging
Algoritma Penggantian Page Optimal
| String Pengacuan | | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 2 |
| | | 2 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 2 | 2 2 |
| | | | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 3 | |
| | | | | 1 | 5 | 5 | 5 | 5 | 5 | 5 | 5 5 | |
| Fault | | F | F | | F | F | | F | | | F | |
Eksekusi dengan algoritma penggantian optimal
Algritma penggantian page LRU
| String Pengacuan | | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
| | | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 |
| | | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | |
| | | | | 1 | 1 | 1 | 4 | 4 | 4 | 2 | 2 | 2 | |
| Fault | | F | F | | F | F | | F | | F | F | | |
Eksekusi dengan algoritma penggantian LRU
Algoritma penggantian page FIFO
| String Pengacuan | | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
| | | 2 | 2 | 2 | 2 | 3 | 1 | 5 | 5 | 2 | 2 | 4 | 3 |
| | | 3 | 3 | 3 | 1 | 5 | 2 | 2 | 4 | 4 | 3 | 5 | |
| | | | | 1 | 5 | 2 | 4 | 4 | 3 | 3 | 5 | 2 | |
| Fault | | F | F | | | F | F | F | | F | | F | F |
Algoritma penggantian page clock
| String Pengacuan | | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
| | > | 2 | 2 | 2 | >2* | 2* | >2* | >2* | >2* | >2* | >2* | >2* | >2* |
| | > | 3 | 3 | 3 | 5 | 5 | 5 | 5* | 5 | 5 | 5* | 5* | |
| | | > | > | 1 | >1 | >1 | 4 | 4 | 3 | 3 | 3 | 3 | |
| Fault | | F | F | | F | F | | F | | F | | | |
KET
· * Diacu
· > ditunjuk pinter
Anomall pada FIFO (Belady’s Anomaly)
Apabila page yang dialokasikan untuk prses lebih banyak maka page faultnya akan relatif lebih sedikit, tetapi belady justru menemukan pada algritma FIFO, bahwa pada pola-pola pengacuan tertentu menyebabkan lebih banyak page fault bila alkasi page untuk proses ditambah. Fenomena ini disebut anomall belady.
Fenomena dapat diilustrasikan sbb:
- Program lima page
- Urutan page yang diacu adalah 0 1 2 3 4 0 1 4 0 1 2 3 4
| String Pengacuan | | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 0 | 1 | 2 | 3 | 4 |
| Page termuda Page tertua | | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 4 | 4 | 2 | 3 | 3 |
| | | 0 | 1 | 2 | 3 | 0 | 1 | 1 | 1 | 4 | 2 | 2 | |
| | | | 0 | 1 | 2 | 3 | 0 | 0 | 0 | 1 | 4 | 4 | |
| Fault | | | F | F | F | F | F | F | | | F | F | |
A
| String Pengacuan | | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 0 | 1 | 2 | 3 | 4 |
| Page termuda | | 0 | 1 | 2 | 3 | 3 | 3 | 4 | 0 | 1 | 2 | 3 | 4 |
| | | 0 | 1 | 2 | 2 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | |
| | | | 0 | 1 | 1 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | |
| Page tertua | | | | | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
| Fault | | F | F | F | F | | | F | F | F | F | F | F |
B
Anomali belady
Gambar 1 (a) FIFO dengan tiga frame menghasilkan 9 page fault
Gambar 2 (b) FIFO dengan empat page frame, menghasilkan 10 page fault.
Mesin Abstrak Eksekusi Program
Setiap proses di memri maya menghasilkan barisan pengacuan memori saat berjalan pengacuan memori berkorespndensi dengan satu age. Secara konseptual pengaksesan memori di cirikan senarai (berurutan ) nomor page, senarai ini disebut string pengacuan (reference string).
Sistem paging dicirikan tiga hal :
1. String pengacuan proses yang sedang di eksekusi
2. Algoritma penggantian page yang digunakan
3. Jumlah page frame yang tersedia (pada memori)
MESIN ABSTRAK
Mesin abstrak interpreter dengan properti :
1. Terdapat array internal, M, menyimpan status memori, array mempunyai n elemen seperti proses mempunyai n page memori maya
2. Array M terbagi 2:
- bagian atas/puncak, m isian , page di memori utama
- Bagian bawah/dasar berisi n-m isian, semua page yang pernah diacu sekali tapi telah dipindahkan dan tidak di memori utama.
3. Mulanya array M berupa himpunan kosong karena belum ada page yang telah diacu dan tak ada page yang berada dimemori,
Eksekusi dimulai, proses meulai mengeluarkan page sesuai string pengacuan, satu page pada satu saat, terhadap page itu, interpreter memeriksa apakah page berada di memori
Contoh
1. String pengacuan adalah 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1
2. Ruang alamatnya adalah 8 page dengan memori fisik 8 page
3. Algoritma penggantian dengan LRU
| String pengacuan | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 3 | 7 | 4 | 7 | 3 | 3 | 5 | 5 | 3 | 1 | 1 | 1 | 7 | 2 | 3 | 4 | 1 |
| | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 3 | 7 | 4 | 7 | 3 | 3 | 5 | 5 | 3 | 1 | 1 | 1 | 7 | 2 | 3 | 4 | 1 |
| | | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 3 | 7 | 4 | 7 | 7 | 3 | 3 | 5 | 3 | 3 | 3 | 1 | 7 | 2 | 3 | 4 |
| | | | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 3 | 3 | 4 | 4 | 7 | 7 | 7 | 5 | 5 | 5 | 3 | 1 | 7 | 2 | 3 |
| | | | | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 6 | 6 | 6 | 4 | 4 | 4 | 7 | 7 | 7 | 5 | 3 | 1 | 7 | 2 |
| | | | | | | 0 | 2 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 | 4 | 4 | 4 | 4 | 5 | 5 | 1 | 7 |
| | | | | | | | 0 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 6 | 6 | 6 | 6 | 4 | 4 | 5 | 5 |
| | | | | | | | | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | 6 |
| | | | | | | | | | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| Fault | | F | F | F | F | F | F | F | | F | | | | | F | | | F | | | | | | F | |
Eksekusi untuk string
Moddel ini mempunyai properti :
1. Ketika page diacu, selalu dipindahkan ke isian puncak dari array M
2. Jika page yang diacu ada di M, semua page diatasnya dipindah satu posisi ke bawah. Transisi dari dalam kotak keluar berkorespondensi dengan page dipindahkan dari memori
3. Page-page yang dibawah page yang diacu, tidak dipindhkan
4. Terdapat kelas algoritma dengan properti
M(m,r)<M(m+1,r),
Dimana
m adalah jumlah page frame memori disk
R adalah pengacuan memori
Masalah – maslah utama pada sistem paging
1. wrking set model
2. kebijaksanaan penggantian lokal vs global
3. frekuensi page fault
4. ukuran page
Prinsip lokalisasi
Prinsip lokalisasi adalah proses-proses cenderung mengacu penyimpan secara tak seragam, menpunyai pola-pola sangat stempat.
Ada 2 jenis lokalisasi :
- Lokalisasi berdasar waktu(temporal locality)
- Lokalisasi menurut ruang (spatial locality)
Masalah – masalah implementasi sistem paging
Perancang sistem paging berurusan beragam masalah implementasi sistem paging, antara lain:
- Back-up instruksi yang terakhir dijalankan sebelum terjadi page fault
- Buffer perangkat masukan/keluaran (penguncian page di memori).
- Page yang dipakai bersama
SEGMENTASI DAN KOMBINASI PAGING SEGMENTASI
Deskripsi segmentasi
Segmentasi memungkinkan pemrogram memandang memori sebagai berisi banyak ruang alamat atau segmen.Ruang-ruang alamat itu sepenuhnya independen. Spesifikasi alamat pada memori bersegmen adalah dua dimensi.Alamat terdiri dua bagian.Yaitu:
1. Nomor segmen
2. Alamat pada segmen itu(offset).
Segmen adalah entitas logika.segmen dapat berisi:
· Prosedur
· Array
· Stack
· Atau kumpulan variabel skalar.
Contoh Sistem Dengan Memori Maya
Memori Maya Dengan Segmentasi Murni
Perangkat keras memberikan pengacuan memori suatu segmentasi tertentu.Pilihan segmen dapat dibuat dengan sembarang kombinasi berikut:
· Instruksi
· Target dari suatu alamat(program atau data)
· Status saat itu(proses,sistem,interupsi).
Adapun keunggulan dan kelemahan segmentasi murni yaitu:
Keunggulan
Segmen-segmen berkorespondensi dengan unit-unit program,sehingga segmen-segmen ideal untuk proteksi dan pemaikaian bersama.Informasi dapat disimpan di register di MMU.
Kelemahan
Segmen-segmen berukuran bervariasi menyebabkan fragmentasi eksternal dan sulit menyelesaikan pertumbuhan dinamis.Segmen-segmen tidak memetakan blok-blok disk untuk memori maya secara alami.
Contoh sistem
Intel 80386 mengimplementasikan segmentasi murni jika tiap segmen kurang dari 1 Mbyte.Untuk segmen-segmen lebih besar,panjangnya harus kelipatan dari 4Kb.Intel 80386 juga menyediakan mekanisme paging dua tungkat.
Sumber : Sistem Operasi / Bambang Hariyanto / Sistem Paging
MASALAH SISTEM PAGING & PENGGANTIAN PAGE
Pengertian sistem paging
• Sistem paging adalah suatu sistem manajemen pada sistem operasi yang mengatur program yang sedang berjalan. Metode dasar dari paging adalah dengan memecah memori fisik menjadi blok-blok yang berukuran tertentu yang disebut dengan frame dan memecah memori logika menjadi bok-blok yang berukuran sama dengan frame yang disebut page.
• Fungsi sistem paging
• Untuk mengatasi apabila suatu program lebih besar dibandingkan dengan memori utama adalah dengan konsep overlay dan konsep memori maya(virtual memori),
• Konsep overlay
• Yang dimaksud konsep overlay Program dipecah menjadi bagian-bagian (OverLay) yang dapat dimuat ke memori.
• Overlay yang belum diperlukan disimpan di Disk.
• Overlay yang diperlukan akan dimuad ke memori
• Konsep memory maya
• Konsep Memori Maya, yaitu kemampuan untuk mengalamati ruang memori melebihi memori utama yang tersedia.
• Istilah memori maya diasosiasikan dengan kemampuan mengalamati memori melebihi memori yang tersedia.Konsep ini ditemukan Fotheringham (1961) pada system computer Atlas di Universitas Manchester, Inggris.
•
•
SO menyimpan bagian yang sedang digunakan (di memori) dan sisanya di disk. Saat diperlukan (bagian di disk), maka bagian di memori segera disingkirkan diganti dengan bagian di disk.
Contoh:
• Program 10Mb dapat berjalan di 2Mb.
• Memilih (secara hati-hati) sebesar 2Mb untuk dimuat ke memori.
• Bagian-bagian program di swap antara disk dan memori saat diperlukan.
Penggantian page
• Saat terjadi page fault, maka harus diputuskan page frame di memori fisik yang harus diganti.
• Kinerja system akan baik jika page yang diganti dipilih yang tidak sering digunakan yad.
• Jika page yang diganti sering digunakan, maka page tersebut akan dikembalikan secepatnya yang berarti page fault berulang kali.
• Banyaknya page fault akan menaikkan overhead
Macam-macam algoritma penggantian page
• Acak,
• Optimal,
• NRU (Not Recently Used),
• FIFO,
• Modifikasi FIFO
• LRU (Least Recently Used)
•
•
1.Algoritma penggantian page acak
Pada algoritma ini setiap terjadi page fault, page yang diganti dipilih secara acak. Pada algoritma ini terdapat kemungkinan proses yang baru berjalan bias digantikan (diberhentikan oleh proses lain) jadi sangat merugikan dan teknik ini sangat buruk, percobaan menunjukkan rate page fault yang sangat tinggi ketika menggunakan teknik ini (sangat merugikan).
2.Algoritma penggantian page optimal
Pada algoritma ini memilih page yang baru terpakai untuk digantikan oleh string acuan terbaru.
3. Algoritma penggantian page LRU
Berdasarkan observasi, page page yang digunakan pada beberapa instruksi terakhir berkemungkinan besar akan dipakai kembali nantinya. Page-page yang lama tidak digunakan akan tetap tak digunakan dalam waktu lama. Pada algoritma ini ketika terjadi page fault maka memindahkan page yang tak digunakan paling lama.
4. Algoritma penggantian page FIFO
Algoritma ini dapat memilih memindahkan page yang sering digunakan yang telah berada di memori untuk waktu yang lama.
http://diyanarswine.blogspot.com/2013/04/masalah-sistem-paging-penggantian-page.html, Senin, 22 April 2013
