Sistem Operasi
Virtual Memory
DAFTAR ISI9.1 Tujuan
9.2 Latar Belakang
9.3 Demand Paging
9.3.1 Deskripsi Sistem Paging
9.3.2 Demand Paging
9.3.3 Skema Bit Valid – Tidak Valid
9.3.4 Penanganan Page Fault
9.3.5 Kinerja
9.3.6 EAT Demand Paging
9.4 Copy-On-Write
9.4.1 Pendahuluan
9.4.2 Dasar Penggantian Halaman
9.5 Algoritma Penggantian Halaman
9.5.1 Pendahuluan
9.5.2 Reference String
9.5.3 Algoritma Penggantian Page Acak
9.5.4 Algoritma FIFO (First In First Out)
9.5.5 Algoritma Optimal
9.5.6 Implementasi LRU
9.5.7 Algoritma Penggantian Page NRU (Not-Recenly Used)
9.5.8 Algoritma Lainnya
9.6 Alokasi Page Frame
9.6.1 Pendahuluan
9.6.2 Jumlah Bingkai
9.6.3 Strategi Alokasi Bingkai
9.6.4 Alokasi Global dan Lokal
9.1 Tujuan- Untuk menjelaskan keuntungan dari sistem memori virtual
- Untuk menjelaskan konsep dari demand paging, algoritma penggantian halaman, dan juga alokasi page frame
- Untuk mendiskusikan prinsip dari model working set
9.2 Latar Belakang
Selama bertahun-tahun, pelaksanaan manajemen memori pada intinya adalah dengan menempatkan semua bagian proses yang akan dijalankan ke dalam memori sebelum proses dapat mulai dieksekusi. Dengan demikian semua bagian proses tersebut harus memiliki alokasi sendiri di dalam memori fisik.
Pada kenyataannya tidak semua bagian dari program tersebut akan diproses, misalnya:
- Ada pernyataan-pernyataan atau pilihan yang hanya akan dieksekusi jika kondisi tertentu dipenuhi
- Terdapat fungsi-fungsi yang jarang digunakan
- Pengalokasian memori yang lebih besar dari yang sebenarnya dibutuhkan.
Setiap program yang dijalankan harus berada di memori. Memori merupakan suatu tempat penyimpanan utama (primary storage) yang bersifat sementara (volatile). Ukuran memori yang terbatas dapat menimbulkan masalah bagaimana menempatkan program yang berukuran yang lebih besar dari ukuran memori fisik (memori utama) dan masalah penerapan multiprogramming yang membutuhkan tempat yang lebih besar di memori.
Memori virtual adalah suatu teknik yang memisahkan antara memori logis dan memori fisiknya. Memori logis merupakan kumpulan keseluruhan halaman dari suatu program. Tanpa memori virtual, memori logis akan langsung dibawa ke memori fisik (memori utama). Disinilah memori virtual melakukan pemisahan dengan menaruh memori logis ke secondary storage (disk sekunder) dan hanya membawa halaman yang diperlukan ke memori utama (memori fisik). Teknik ini menempatkan keseluruhan program di disk sekunder dan membawa halaman-halaman yang diperlukan ke memori fisik sehingga memori utama hanya akan menyimpan sebagian alamat proses yang sering digunakan dan sebagian lainnya akan disimpan dalam disk sekunder dan dapat diambil sesuai dengan kebutuhan. Jadi jika proses yang sedang berjalan membutuhkan instruksi atau data yang terdapat pada suatu halaman tertentu maka halaman tersebut akan dicari di memori utama. Jika halaman yang diinginkan tidak ada maka akan dicari ke disk sekunder.
Jadi memory virtual adalah kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Konsep memori maya pertama kali dikemukakan Fotheringham pada 1961 untuk sistem komputer Atlas di Universitas Manchester, Inggris.
Gagasan memori virtual adalah ukuran gabungan program, data, dan stack melampaui jumlah memori fisik yang tersedia. Sistem operasi dapat menyimpan bagian-bagian proses yang sedang digunakan di memori utama dan sisanya di disk. Begitu bagian di disk diperlukan maka bagian di memori yang tidak diperlukan disingkirkan diganti bagian di disk yang diperlukan itu.
Contoh penggunaannya adalah program 10 Megabyte dapat berjalan di mesin 2 Megabyte, yaitu memilih bagian proses sebesar 2 Megabyte secara hati-hati dan ditaruh di memori. Bagian-bagian proses di-swap antara disk dan memori saat diperlukan secara otomatis oleh sistem operasi. Memori virtual juga dapat digunakan dalam multiprogramming seperti 10 program 2 Mb dapat berjalan di memori 4 Mb. Tiap program dialokasikan 256 Kilobyte dan bagian-bagian proses di-swap masuk keluar memori begitu diperlukan. Saat proses menunggu bagiannya diswap masuk ke memori, menunggu selesainya operasi masukan/keluaran, proses di-block, jatah layanan pemroses diberikan ke proses lain.
Memori virtual tidak mengubah kode program. Kecepatan eksekusi melambat dipengaruhi waktu tunda pengambilan bagian-bagian proses di memori sekunder saat proses berjalan. Prinsip yang berlaku kecepatan maksimum eksekusi proses di memori virtual dapat sama tapi tidak pernah melampaui kecepatan eksekusi proses yang sama di sistem tanpa memori virtual.
Gambar 9.1. Memori Virtual
Pada gambar diatas ditunjukkan ruang sebuah memori virtual yang dibagi menjadi bagian-bagian yang sama dan diidentifikasikan dengan nomor virtual pages. Memori fisik dibagi menjadi page frames yang berukuran sama dan diidentifikasikan dengan nomor page frames. Bingkai (frame) menyimpan data dari halaman. Atau memori virtual memetakan nomor virtual pages ke nomor page frames. Mapping (pemetaan) menyebabkan halaman virtual hanya dapat mempunyai satu lokasi alamat fisik.
Dalam sistem paging, jika sebuah ruang diperlukan untuk proses dan halaman yang bersangkutan tidak sedang digunakan, maka halaman dari proses akan mengalami paged out (disimpan ke dalam disk) atau swap out, memori akan kosong untuk halaman aktif yang lain. Halaman yang dipindah dari disk ke memori ketika diperlukan dinamakan paged in (dikembalikan ke memori) atau swap in. Ketika sebuah item dapat mengalami paging, maka item tersebut termasuk dalam item yang menempati ruang virtual, yang diakses dengan alamat virtual dan ruangan yang ada dialokasikan untuk informasi pemetaan. Sistem operasi mengalokasikan alamat dari item tersebut hanya ketika item tersebut mengalami paging in.
Keuntungan yang diperoleh dari penyimpanan hanya sebagian program saja pada memori fisik adalah:
- Berkurangnya proses M/K yang dibutuhkan (lalu lintas M/K menjadi rendah)
- Ruang menjadi lebih leluasa karena berkurangnya memori fisik yang digunakan
- Meningkatnya respon karena menurunnya beban M/K dan memori
- Bertambahnya jumlah pengguna yang dapat dilayani. Ruang memori yang masih tersedia luas memungkinkan komputer untuk menerima lebih banyak permintaan dari pengguna.
Prinsip dari memori virtual adalah bahwa “Kecepatan maksimum ekseskusi proses di memori virtual dapat sama, tetapi tidak akan pernah melampaui kecepatan eksekusi proses yang sama di sistem yang tidak menggunakan memori virtual”.
Memori virtual dapat diimplementasikan dengan tiga cara:
- Demand Paging yaitu dengan menerapkan konsep pemberian halaman pada proses
- Demand segmentation, lebih kompleks diterapkan ukuran segmen yang bervariasi.
- Kombinasi paging dan segmentation
Hole / large bank space yang terdapat pada gambar di atas dapat digunakan jika ruang logika stack dan heap bertambah merupakan konsep dari alokasi dynamic memory. Virtual address space yang mempunyai hole disebut sparse address space
Gambar 9.3. Shared library dengan menggunakan memori virtual
Rujukan
Dr. Bambang Hariyanto. 2006. Sistem Operasi. Revisi Keempat. Informatika.
[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons.
[Tanenbaum1997] Andrew S Tanenbaum dan Albert S Woodhull. 1997. Operating Systems Design and Implementation. Second Edition. Prentice-Hall.
[WEBbebasvlsm2006] Masyarakat Digital Gotong Royong .2006. Pengantar Sistem Operasi Komputer http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-2/index.html .
[WEBAmirSch2000] Yair Amir dan Theo Schlossnagle. 2000. Operating Systems 00.418: Memory Management http://www.cs.jhu.edu/ ~yairamir/ cs418/ os5/ .
[WEBCACMF1961] John Fotheringham. “ Dynamic Storage Allocation in the Atlas Computer Including an Automatic Use of a Backing Store http://www.eecs.harvard.edu/ cs261/ papers/ frother61.pdf ”. Communications of the ACM . 4. 10. October 1961.
[WEBFunkhouser2002] Thomas Funkhouser. 2002. Computer Science 217 Introduction to Programming Systems: Memory Paging http://www.cs.princeton.edu/ courses/ archive / spring02/ cs217/ lectures/ paging.pdf .
[WEBGottlieb2000] Allan Gottlieb. 2000. Operating Systems: Page tables http://allan.ultra.nyu.edu/ ~gottlieb/ courses/ 1999-00-spring/ os/ lecture-11.html .
[WEBHP1997] Hewlett-Packard Company. 1997. HP-UX Memory Management Overview of Demand Paging http://docs.hp.com/en/5965-4641/ch01s10.html .
[WEBJupiter2004] Jupitermedia Corporation. 2004. Virtual Memory http://www.webopedia.com/ TERM/ v/ virtual_memory.html .
[WEBOCWEmer2005] Joel Emer dan Massachusetts Institute of Technology. 2005. OCW Computer System Architecture Fall 2005 Virtual Memory Basics http://ocw.mit.edu/ NR/ rdonlyres/ Electrical -Engineering -and -Computer -Science/ 6 -823Computer -System -ArchitectureSpring2002/ C63EC0D0 -0499 -474F -BCDA -A6868A6827C4/ 0/ lecture09.pdf .
[WEBRegehr2002] John Regehr dan University of Utah. 2002. CS 5460 Operating Systems Demand Halamand Virtual Memory http://www.cs.utah.edu/ classes/ cs5460-regehr/ lecs/ demand_paging.pdf .
[WEBSolomon2004] Marvin Solomon. 2004. CS 537 Introduction to Operating Systems: Lecture Notes Part 7 http://www.cs.wisc.edu/ ~solomon/ cs537/ paging.html .
[WEBKUSJOKO2004] Kuspriyanto dan Putut Joko Wibowo. 2004. Desain Memori Virtual Pada Mikroarsitektur PowerPC, MIPS, Dan X86 http://www.geocities.com/transmisi_eeundip/kuspriyanto.pdf .
Kembali ke daftar isi
9.3 Demand Paging
9.3.1 Deskripsi Sistem Paging
Sistem Paging mengimplentasikan ruang alamat besar pada memori kecil menggunakan index register, base register, dan segment register, dan lain-lain. Pemakai seolah mempunyai ruang memori sangat besar tanpa mengelola overlay.
Beberapa istilah pada sistem paging adalah virtual address, real address, page, page frame, page fault, MMU.
Virtual Address adalah alamat yang dihasilkan perhitungan menggunakan index register, base register, segment register, dan sebagainya. Ruang alamat yang dibentuk virtual address adalah disebut virtual address space dilambangkan dengan V. Jumlah alamat pada V disimbolkan dengan │V│. Virtual address ini yang diacu pada proses yang running.
Real Address adalah alamat di memori utama fisik. Ruang alamat yang dibentuk real address disebut real address space dilambangkan dengan R. Jumlah alamat pada R disimbolkan dengan │R│. Pada implementasi sistem memori virtual, normalnya │V│>>│R│.
Meski pengacuan proses dilakukan berdasarkan memori virtual, proses sesungguhnya berjalan di memori nyata. Virtual address harus dipetakan menjadi real address saat proses dieksekusi. Pemetaan harus dilakukan dengan sangat cepat atau kinerja komputer akan menurun drastis.
Sistem komputer akan menerjemahkan memori virtual menjadi alamat fisik. Bagian yang bertugas untuk memetakan adalah MMU.
Page adalah unit terkecil virtual address space. Ruang memori virtual proses merupakan kelipatan page yang berukuran sama.
Page frame adalah unit terkecil memori fisik. Memori fisik secara konseptual dibagi menjadi sejumlah unit berukuran tetap disebut page frame. Page frame sering disingkat frame.
Gambar 9.4. Hubungan antara ruang alamat virtual dan alamat fisik
Page fault adalah exception untuk permintaan alokasi page ke memori. Dalam konteks memori maya, page fault sering disingkat fault.
Memory Management Unit (mmu) adalah chip atau kumpulan chip yang memetakan virtual address ke real address.
Gambar 9.5. Posisi dan fungsi MMU
Memori fisik berisi sejumlah page frame yang memuat sebagian page-page proses. Terdapat mekanisme translasi (penerjemahan) alamat (dilakukan MMU) untuk memetakan page virtual ke alamat fisik. Karena masing-masing page dipetakan secara terpisah, frame-frame proses tidak perlu menempati memori fisik berurutan.
Sistem memori virtual mempunyai properti alamat-alamat kontigu (berturutan) pada ruang alamat virtual tidak harus kontigu di memori nyata. Properti ini disebut kontigu semu (artificial contiguity).
Gambar 9.6. Kontigu semu
Pemakai dibebaskan berurusan dengan letak prosedur dan data diposisikan di memori nyata. Pemrograman dapat menulis program seperti biasa, yaitu memperhatikan efisiensi algoritma dan struktur program, mengabaikan rincian struktur perangkat keras. Dengan sistem virtual, memori dapat dipandang sebagai kontigu yang berukuran besar.
Skema Pemetaan
Pada komputer dengan memori virtual, alamat tidak diletakkan ke bus secara langsung tapi dilewatkan ke MMU yang memetakan alamat virtual ke alamat memori fisik. Pemetaan dapat dirumuskan secara formal sebagai berikut:
Misalkan
Ruang alamat maya adalah V = {0,1,…,v-1}
Ruang alamat fisik adalah M = {0,1,…,m-1}
Umumnya ruang alamat virtual lebih besar dibanding alamat fisik (v > m).
MMU melakukan mekanisme translasi alamat mengasosiasikan alamat virtual ke alamat fisik. MMU merealisasikan fungsi f: V → M, yaitu:
f(x) = {r, jika item x terdapat di memori fisik dengan lokasi di r}
{page fault jika item x tidak terdapat dalam memori fisik}
Gambar 9.7. Relasi antara alamat virtual dan alamat fisik
Misalnya instruksi:
MOV REG, 0×08
9.3.2 Pengertian Demand Paging
Demand Paging atau permintaan pemberian halaman adalah salah satu implementasi dari memori virtual yang paling umum digunakan. Sistem Demand Paging pada prinsipnya hampir sama dengan sistem permintaan halaman yang menggunakan swapping, hanya saja pada sistem demand paging, halaman tidak akan dibawa ke dalam memori fisik sampai ia benar-benar diperlukan. Oleh sebab itu dibutuhkan bantuan perangkat keras untuk mengetahui lokasi dari halaman saat ia diperlukan. Daripada melakukan swapping, keseluruhan proses ke dalam memori utama, digunakanlah yang disebut lazy swapper yaitu tidak pernah menukar sebuah halaman ke dalam memori utama kecuali halaman tersebut diperlukan. Keuntungan yang diperoleh dengan menggunakan demand paging sama dengan keuntungan pada memori virtual di atas.
Gambar 9.8. Proses swapping program ke dalam memori
Saat melakukan pengecekan pada halaman yang dibutuhkan oleh suatu proses, terdapat tiga kemungkinan kasus yang dapat terjadi, yaitu:
9.3.3 Skema Bit Valid – Tidak Valid
Dalam menentukan halaman mana yang ada di dalam memori utama dan halaman mana yang tidak ada di dalam memori utama, diperlukan suatu konsep, yaitu skema bit valid – tidak valid. Kondisi valid berarti bahwa halaman yang dibutuhkan itu legal dan berada di dalam memori utama (kasus pertama). Sementara tidak valid/invalid adalah kondisi dimana halaman tidak ada di memori utama namun ada di disk sekunder (kasus kedua) atau halaman memang benar-benar tidak ada baik di memori utama maupun disk sekunder (kasus ketiga).
Pengaturan bit dilakukan sebagai berikut:
Page fault adalah interupsi yang terjadi ketika halaman yang diminta/dibutuhkan oleh suatu proses tidak berada di memori utama. Proses yang sedang berjalan akan mengakses page table (tabel halaman) untuk mendapatkan referensi halaman yang diinginkan. Page fault dapat diketahui/dideteksi dari penggunaan skema bit valid-tidak valid ini. Bagian inilah yang menandakan terjadinya suatu permintaan pemberian halaman .
Jika suatu proses mencoba untuk mengakses suatu halaman dengan bit yang di-set tidak valid maka page fault akan terjadi. Proses akan dihentikan sementara halaman yang diminta/dibutuhkan dicari didalam disk.
Gambar 9.9. Tabel Halaman dengan Skema Bit Valid – Tidak valid
9.3.4 Penanganan Page Fault
Prosedur untuk menangani page fault adalah sebagai berikut:
Pada berbagai kasus yang terjadi, ada tiga komponen yang akan dihadapi pada saat melayani page fault:
9.3.5 Kinerja
Dalam proses demand paging, jika terjadi page fault maka diperlukan waktu yang lebih lambat untuk mengakses memori daripada jika tidak terjadi page fault. Hal ini dikarenakan perlu adanya penanganan page fault itu sendiri. Kinerja demand paging ini dapat dihitung dengan menggunakan effective access time yang dirumuskan sebagai berikut:
effective access time = (1 – p) x ma + p x page fault time
ma adalah memory access time, yang pada umumnya berkisar antara 10 hingga 200 nanosecond. p adalah probabilitas terjadinya page fault, yang berkisar antara 0 hingga 1. Jika p sama dengan 0 yang berarti bahwa tidak pernah terjadi page fault, maka effective access time akan sama dengan memory access time, dan itulah yang diharapkan. Sedangkan jika p sama dengan 1, yang berarti bahwa semua halaman mengalami page fault, maka effective access time-nya akan semaikin meningkat.
Untuk mendapatkan effective access time, kita harus mengetahui waktu yang diperlukan untuk menangani page fault. Komponen-komponen dalam penanganan page fault terdiri dari tiga kelompok besar, yaitu melayani interupsi dari page fault, membaca halaman, dan mengulang kembali proses.
Penggunaan effective access time dapat ditunjukkan dalam contoh berikut.
Contoh 9.1. Contoh penggunaan effective address
Diketahui waktu pengaksesan memori (ma) sebesar 100 ns. Waktu page fault sebesar 20 ms. Maka effective access time = (1 – p) x ma + p x page fault time = (1 – p) x 100 + p x 20000000 = 100 – 100p + 20000000p = 100 + 19.999.900p nanosecond
Pada demand paging, diusahakan agar kemungkinan terjadinya page fault rendah, karena bila effective access time-nya meningkat, maka proses akan berjalan lebih lambat.
9.3.6 EAT Demand Paging
Waktu akses memory = 200 nanosecond
Rata-rata waktu page-fault service time = 8 milliseconds
1 ms=106 ns
EAT = ((1 – p) x 200) + (p x (8 milliseconds))
= ((1 – p) x 200) + (p x 8,000,000)
= 200 + (p x 7,999,800)
Jika 1 dari 1.000 kali akses terjadi fault, maka EAT = 8.2 microseconds.
EAT bertambah menjadi 40 kali lipat dari waktu akses memory
Jika ingin EAT tidak lebih dari 220ns (waktu akses memori bertambah 10 %) maka :
220 > 200+7.999.800 x p
20 > 7.999.800 x p
p < 0,0000025, artinya p harus lebih kecil dari kejadian page-fault sekali dalam 400.000 kali akses
Tiga komponen waktu utama saat terjadi page fault:
- service page fault interrupt (1-100 microseconds)
- baca page/page switch time (8 millisecond)
Rujukan
Dr. Bambang Hariyanto. 2006. Sistem Operasi. Revisi Keempat. Informatika.
[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons.
[Tanenbaum1997] Andrew S Tanenbaum dan Albert S Woodhull. 1997. Operating Systems Design and Implementation. Second Edition. Prentice-Hall.
[WEBbebasvlsm2006] Masyarakat Digital Gotong Royong .2006. Pengantar Sistem Operasi Komputer http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-2/index.html .
[WEBUniversitasMalikulsaleh] Gabungan Kelompok Kerja 21–28 IKI-20230 Semester Genap. 2003. Sistem Operasi. http://ikc.unimal.ac.id/umum/ibam/ibam-os-html/x3883.html .
[WEBUIOCW] Heri Kurniawan. 2006. Sistem Operasi. http://ocw.ui.ac.id/IKI20230_:_Sistem_Operasi_(Lecture_Notes) .
[WEBUniversityofMassachusetts] Emery Beger. 2006. Demand Paging. http://www.cs.umass.edu/~emery/cmpsci377/lectures/cmpsci377-13.ppt .
[WEBUppsalaUniversitet] Léon Mugwaneza. 2008. Demand Paging & Page Replacement. http://www.it.uu.se/edu/course/homepage/os/vt08 .
[WEBStanfordUniversity] John Ousterhout. 2010. Demand Paging & Thrashing. http://www.stanford.edu/class/cs140/cgi-bin/lecture.php?topic=paging .
[WEBEducationGrid] Satish Babu, dkk. 2007. Demand Paged Virtual Memory. http://www.edugrid.ac.in/webfolder/OpSystems/8_VirtualMem/Uni_Washington/Demand%20Paged%20Virtual%20Memory.pdf.
[WEBUCBerkeley] Prof. John Kubiatowicz. 2009. Caching & Demand Paging. http://www.cs.berkeley.edu/~kubitron/courses/cs162-F09/Lectures/lec14-demandpage.ppt .
[WEBUSCUPSTATE] Prof. John Kubiatowicz. 2009. Caching & Demand Paging. http://faculty.uscupstate.edu/fli/spr06/scsc511/Slides/14.ppt .
[WEBUCSECSE] Alex C. Snoeren. 2010. Principle of Operating System:Demand Paging. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.9714&rep=rep1&type=pdf .
Kembali ke daftar isi
9.3.1 Deskripsi Sistem Paging
Sistem Paging mengimplentasikan ruang alamat besar pada memori kecil menggunakan index register, base register, dan segment register, dan lain-lain. Pemakai seolah mempunyai ruang memori sangat besar tanpa mengelola overlay.
Beberapa istilah pada sistem paging adalah virtual address, real address, page, page frame, page fault, MMU.
Virtual Address adalah alamat yang dihasilkan perhitungan menggunakan index register, base register, segment register, dan sebagainya. Ruang alamat yang dibentuk virtual address adalah disebut virtual address space dilambangkan dengan V. Jumlah alamat pada V disimbolkan dengan │V│. Virtual address ini yang diacu pada proses yang running.
Real Address adalah alamat di memori utama fisik. Ruang alamat yang dibentuk real address disebut real address space dilambangkan dengan R. Jumlah alamat pada R disimbolkan dengan │R│. Pada implementasi sistem memori virtual, normalnya │V│>>│R│.
Meski pengacuan proses dilakukan berdasarkan memori virtual, proses sesungguhnya berjalan di memori nyata. Virtual address harus dipetakan menjadi real address saat proses dieksekusi. Pemetaan harus dilakukan dengan sangat cepat atau kinerja komputer akan menurun drastis.
Sistem komputer akan menerjemahkan memori virtual menjadi alamat fisik. Bagian yang bertugas untuk memetakan adalah MMU.
Page adalah unit terkecil virtual address space. Ruang memori virtual proses merupakan kelipatan page yang berukuran sama.
Page frame adalah unit terkecil memori fisik. Memori fisik secara konseptual dibagi menjadi sejumlah unit berukuran tetap disebut page frame. Page frame sering disingkat frame.
Gambar 9.4. Hubungan antara ruang alamat virtual dan alamat fisik
Page fault adalah exception untuk permintaan alokasi page ke memori. Dalam konteks memori maya, page fault sering disingkat fault.
Memory Management Unit (mmu) adalah chip atau kumpulan chip yang memetakan virtual address ke real address.
- Pada komputer tanpa memori virtual, alamat langsung diletakkan ke bus dan menyebabkan word memori fisik alamat itu dibaca atau ditulis.
- Pada komputer dengan memori virtual, alamat tidak diletakkan ke bus secara langsung tapi lewat MMU yang kemudian memetakan virtual address ke alamat memori fisik.
Gambar 9.5. Posisi dan fungsi MMU
Memori fisik berisi sejumlah page frame yang memuat sebagian page-page proses. Terdapat mekanisme translasi (penerjemahan) alamat (dilakukan MMU) untuk memetakan page virtual ke alamat fisik. Karena masing-masing page dipetakan secara terpisah, frame-frame proses tidak perlu menempati memori fisik berurutan.
Sistem memori virtual mempunyai properti alamat-alamat kontigu (berturutan) pada ruang alamat virtual tidak harus kontigu di memori nyata. Properti ini disebut kontigu semu (artificial contiguity).
Gambar 9.6. Kontigu semu
Pemakai dibebaskan berurusan dengan letak prosedur dan data diposisikan di memori nyata. Pemrograman dapat menulis program seperti biasa, yaitu memperhatikan efisiensi algoritma dan struktur program, mengabaikan rincian struktur perangkat keras. Dengan sistem virtual, memori dapat dipandang sebagai kontigu yang berukuran besar.
Skema Pemetaan
Pada komputer dengan memori virtual, alamat tidak diletakkan ke bus secara langsung tapi dilewatkan ke MMU yang memetakan alamat virtual ke alamat memori fisik. Pemetaan dapat dirumuskan secara formal sebagai berikut:
Misalkan
Ruang alamat maya adalah V = {0,1,…,v-1}
Ruang alamat fisik adalah M = {0,1,…,m-1}
Umumnya ruang alamat virtual lebih besar dibanding alamat fisik (v > m).
MMU melakukan mekanisme translasi alamat mengasosiasikan alamat virtual ke alamat fisik. MMU merealisasikan fungsi f: V → M, yaitu:
f(x) = {r, jika item x terdapat di memori fisik dengan lokasi di r}
{page fault jika item x tidak terdapat dalam memori fisik}
Gambar 9.7. Relasi antara alamat virtual dan alamat fisik
Misalnya instruksi:
MOV REG, 0×08
- Alamat maya 8 dikirim ke MMU
- MU mengetahui alamat 8 di page 0 (page 0 memuat alamat maya 0-4095)
- Dari tabel, page 0 dipetakan ke frame 7 (page 7 adalah alamat fisik 28672-32768)
- MMU mentransformasikan alamat 8 sebagai (28672 + 8 = 28680)
- MMU mengeluarkan alamat 28680 ke bus
9.3.2 Pengertian Demand Paging
Demand Paging atau permintaan pemberian halaman adalah salah satu implementasi dari memori virtual yang paling umum digunakan. Sistem Demand Paging pada prinsipnya hampir sama dengan sistem permintaan halaman yang menggunakan swapping, hanya saja pada sistem demand paging, halaman tidak akan dibawa ke dalam memori fisik sampai ia benar-benar diperlukan. Oleh sebab itu dibutuhkan bantuan perangkat keras untuk mengetahui lokasi dari halaman saat ia diperlukan. Daripada melakukan swapping, keseluruhan proses ke dalam memori utama, digunakanlah yang disebut lazy swapper yaitu tidak pernah menukar sebuah halaman ke dalam memori utama kecuali halaman tersebut diperlukan. Keuntungan yang diperoleh dengan menggunakan demand paging sama dengan keuntungan pada memori virtual di atas.
Gambar 9.8. Proses swapping program ke dalam memori
Saat melakukan pengecekan pada halaman yang dibutuhkan oleh suatu proses, terdapat tiga kemungkinan kasus yang dapat terjadi, yaitu:
- Halaman ada dan sudah langsung berada di memori utama – statusnya adalah valid (“v” atau “1″)
- Halaman ada tetapi belum berada di memori utama atau dengan kata lain halaman masih berada di disk sekunder – statusnya adalah tidak valid/invalid (“i” atau “0″)
- Halaman benar – benar tidak ada, baik di memori utama maupun di disk sekunder (invalid reference) – statusnya adalah tidak valid/invalid (“i” atau “0″)
9.3.3 Skema Bit Valid – Tidak Valid
Dalam menentukan halaman mana yang ada di dalam memori utama dan halaman mana yang tidak ada di dalam memori utama, diperlukan suatu konsep, yaitu skema bit valid – tidak valid. Kondisi valid berarti bahwa halaman yang dibutuhkan itu legal dan berada di dalam memori utama (kasus pertama). Sementara tidak valid/invalid adalah kondisi dimana halaman tidak ada di memori utama namun ada di disk sekunder (kasus kedua) atau halaman memang benar-benar tidak ada baik di memori utama maupun disk sekunder (kasus ketiga).
Pengaturan bit dilakukan sebagai berikut:
- Bit = 1 berarti halaman berada di memori utama
- Bit = 0 berarti halaman tidak berada di memori utama
Page fault adalah interupsi yang terjadi ketika halaman yang diminta/dibutuhkan oleh suatu proses tidak berada di memori utama. Proses yang sedang berjalan akan mengakses page table (tabel halaman) untuk mendapatkan referensi halaman yang diinginkan. Page fault dapat diketahui/dideteksi dari penggunaan skema bit valid-tidak valid ini. Bagian inilah yang menandakan terjadinya suatu permintaan pemberian halaman .
Jika suatu proses mencoba untuk mengakses suatu halaman dengan bit yang di-set tidak valid maka page fault akan terjadi. Proses akan dihentikan sementara halaman yang diminta/dibutuhkan dicari didalam disk.
Gambar 9.9. Tabel Halaman dengan Skema Bit Valid – Tidak valid
9.3.4 Penanganan Page Fault
Prosedur untuk menangani page fault adalah sebagai berikut:
- CPU mengambil (load) instruksi dari memori untuk dijalankan. Pengambilan instruksi dilakukan dari halaman pada memori dengan mengakses tabel halaman. Ternyata pada tabel halaman bit ter-set tidak valid atau invalid (i).
- Interupsi page fault terjadi sehingga interupsi tersebut menyebabkan perangkat keras melakukan trap yaitu menjebak proses tersebut ke dalam sistem operasi.
- Jika referensi alamat yang diberikan ke sistem operasi ilegal atau dengan kata lain halaman yang ingin diakses tidak ada (tidak berada di disk), maka proses akan dihentikan. Namun jika referensi alamatnya adalah legal maka halaman yang diinginkan akan diambil dari disk.
- Halaman yang diinginkan akan dibawa dari disk ke memori utama (memori fisik).
- Tabel halaman akan diatur ulang lagi sesuai dengan kondisi yang baru. Jika tidak terdapat ruang kosong (free frame) di memori utama (fisik) untuk menaruh halaman yang baru maka dilakukan penggantian halaman dengan memilih salah satu halaman pada memori utama untuk digantikan dengan halaman yang baru tersebut. Penggantian halaman dilakukan dengan menggunakan algoritma tertentu. Jika halaman yang digantikan tersebut sudah dimodifikasi oleh proses maka halaman tersebut harus ditulis kembali ke disk.
- Setelah halaman yang diinginkan sudah dibawa ke memori utama (fisik) maka proses dapat diulang kembali. Dengan demikian proses sudah bisa mengakses halaman karena halaman telah diletakkan ke memori utama (fisik).
Pada berbagai kasus yang terjadi, ada tiga komponen yang akan dihadapi pada saat melayani page fault:
- Melayani interupsi page fault
- Membaca halaman
- Mengulang kembali proses
9.3.5 Kinerja
Dalam proses demand paging, jika terjadi page fault maka diperlukan waktu yang lebih lambat untuk mengakses memori daripada jika tidak terjadi page fault. Hal ini dikarenakan perlu adanya penanganan page fault itu sendiri. Kinerja demand paging ini dapat dihitung dengan menggunakan effective access time yang dirumuskan sebagai berikut:
effective access time = (1 – p) x ma + p x page fault time
ma adalah memory access time, yang pada umumnya berkisar antara 10 hingga 200 nanosecond. p adalah probabilitas terjadinya page fault, yang berkisar antara 0 hingga 1. Jika p sama dengan 0 yang berarti bahwa tidak pernah terjadi page fault, maka effective access time akan sama dengan memory access time, dan itulah yang diharapkan. Sedangkan jika p sama dengan 1, yang berarti bahwa semua halaman mengalami page fault, maka effective access time-nya akan semaikin meningkat.
Untuk mendapatkan effective access time, kita harus mengetahui waktu yang diperlukan untuk menangani page fault. Komponen-komponen dalam penanganan page fault terdiri dari tiga kelompok besar, yaitu melayani interupsi dari page fault, membaca halaman, dan mengulang kembali proses.
Penggunaan effective access time dapat ditunjukkan dalam contoh berikut.
Contoh 9.1. Contoh penggunaan effective address
Diketahui waktu pengaksesan memori (ma) sebesar 100 ns. Waktu page fault sebesar 20 ms. Maka effective access time = (1 – p) x ma + p x page fault time = (1 – p) x 100 + p x 20000000 = 100 – 100p + 20000000p = 100 + 19.999.900p nanosecond
Pada demand paging, diusahakan agar kemungkinan terjadinya page fault rendah, karena bila effective access time-nya meningkat, maka proses akan berjalan lebih lambat.
9.3.6 EAT Demand Paging
Waktu akses memory = 200 nanosecond
Rata-rata waktu page-fault service time = 8 milliseconds
1 ms=106 ns
EAT = ((1 – p) x 200) + (p x (8 milliseconds))
= ((1 – p) x 200) + (p x 8,000,000)
= 200 + (p x 7,999,800)
Jika 1 dari 1.000 kali akses terjadi fault, maka EAT = 8.2 microseconds.
EAT bertambah menjadi 40 kali lipat dari waktu akses memory
Jika ingin EAT tidak lebih dari 220ns (waktu akses memori bertambah 10 %) maka :
220 > 200+7.999.800 x p
20 > 7.999.800 x p
p < 0,0000025, artinya p harus lebih kecil dari kejadian page-fault sekali dalam 400.000 kali akses
Tiga komponen waktu utama saat terjadi page fault:
- service page fault interrupt (1-100 microseconds)
- baca page/page switch time (8 millisecond)
- Rata-rata latency: 3 ms, seek: 5 ms, transfer: 0.05 ms
Rujukan
Dr. Bambang Hariyanto. 2006. Sistem Operasi. Revisi Keempat. Informatika.
[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons.
[Tanenbaum1997] Andrew S Tanenbaum dan Albert S Woodhull. 1997. Operating Systems Design and Implementation. Second Edition. Prentice-Hall.
[WEBbebasvlsm2006] Masyarakat Digital Gotong Royong .2006. Pengantar Sistem Operasi Komputer http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-2/index.html .
[WEBUniversitasMalikulsaleh] Gabungan Kelompok Kerja 21–28 IKI-20230 Semester Genap. 2003. Sistem Operasi. http://ikc.unimal.ac.id/umum/ibam/ibam-os-html/x3883.html .
[WEBUIOCW] Heri Kurniawan. 2006. Sistem Operasi. http://ocw.ui.ac.id/IKI20230_:_Sistem_Operasi_(Lecture_Notes) .
[WEBUniversityofMassachusetts] Emery Beger. 2006. Demand Paging. http://www.cs.umass.edu/~emery/cmpsci377/lectures/cmpsci377-13.ppt .
[WEBUppsalaUniversitet] Léon Mugwaneza. 2008. Demand Paging & Page Replacement. http://www.it.uu.se/edu/course/homepage/os/vt08 .
[WEBStanfordUniversity] John Ousterhout. 2010. Demand Paging & Thrashing. http://www.stanford.edu/class/cs140/cgi-bin/lecture.php?topic=paging .
[WEBEducationGrid] Satish Babu, dkk. 2007. Demand Paged Virtual Memory. http://www.edugrid.ac.in/webfolder/OpSystems/8_VirtualMem/Uni_Washington/Demand%20Paged%20Virtual%20Memory.pdf.
[WEBUCBerkeley] Prof. John Kubiatowicz. 2009. Caching & Demand Paging. http://www.cs.berkeley.edu/~kubitron/courses/cs162-F09/Lectures/lec14-demandpage.ppt .
[WEBUSCUPSTATE] Prof. John Kubiatowicz. 2009. Caching & Demand Paging. http://faculty.uscupstate.edu/fli/spr06/scsc511/Slides/14.ppt .
[WEBUCSECSE] Alex C. Snoeren. 2010. Principle of Operating System:Demand Paging. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.9714&rep=rep1&type=pdf .
Kembali ke daftar isi
9.4 Copy-on-Write
9.4.1 Pendahuluan
Pada pembahasan sebelumnya dijelaskan bahwa memori virtual memungkinkan proses untuk saling berbagi pakai memori. Proses ini adalah proses untuk berbagi pakai halaman (page sharing) memori virtual. Karena setiap proses membutuhkan halaman tersendiri, maka dibutuhkan teknik untuk mengaturnya. Teknik yang digunakan untuk mengoptimasi pembuatan dan penggunaan halaman adalah teknik copy-on-write, atau yang biasa disingkat dengan COW.
Pembuatan proses baru dengan menggunakan sistem call fork() menciptakan proses anak sebagai duplikat dari proses induknya. Setelah berhasil menciptakan proses anak, kemudian proses anak tersebut langsung memanggil sistem call exec(), yang berarti bahwa proses anak juga menduplikasi ruang alamat yang dimiliki proses induknya, beserta halaman yang diaksesnya. Padahal, hasil kopian dari halaman tersebut belum tentu berguna, yaitu jika tidak ada proses modifikasi pada halaman tersebut. Akan tetapi, dengan menggunakan teknik copy-on-write maka proses anak dan induk dapat bersama-sama menggunakan (mengakses) halaman yang sama.
Suatu halaman yang diakses secara bersama-sama (shared) oleh beberapa proses ditandai dengan COW (copy-on-write) jika suatu proses ingin memodifikasi (menulis) suatu halaman. Dan apabila hal tersebut terjadi, maka akan dibuat salinan dari halaman yang di-shared tersebut.
Sebagai contoh, sebuah proses anak akan memodifikasi suatu halaman yang terdiri dari sebagian dari stack. Sistem operasi akan mengenali halaman ini sebagai halaman copy-on-write. Sistem operasi kemudian akan membuat salinan dari halaman ini dan memetakannya kepada ruang alamat yang dimiliki proses anak. Proses anak kemudian memodifikasi halaman salinan yang telah berada di ruang alamat proses anak tersebut. Pada saat teknik copy-on-write ini digunakan, hanya halaman yang bisa dimodifikasi (oleh proses anak atau proses induk) saja yang disalin, sedangkan halaman yang tidak dimodifikasi dapat dibagi (di-share) untuk proses induk dan proses anak. Sebagai catatan, bahwa hanya halaman yang dapat dimodifikasi saja yang ditandai sebagai copy-on-write, sedangkan halaman yang tidak dapat dimodifikasi (misalnya halaman yang terdiri dari kode-kode yang bisa dieksekusi) tidak perlu ditandai karena tidak akan terjadi modifikasi pada halaman tersebut.
Pada banyak sistem operasi, disediakan sebuah pool yang terdiri dari halaman-halaman yang kosong untuk meletakkan halaman hasil duplikasi dengan teknik copy-on-write. Selain untuk meletakkan halaman hasil duplikasi tersebut, pool ini juga digunakan pada saat sebuah proses mengalami penambahan stack atau heap. Teknik yang digunakan sistem operasi untuk menyediakan halaman kosong tersebut dikenal dengan zero-fill-on-demand. Teknik ini dilakukan dengan mengosongkan halaman-halaman sebelum digunakan oleh proses yang baru.
Copy-on-write dapat diilustrasikan pada gambar 4 dan 5.
Gambar 9.11. Sebelum modifikasi pada page C
Gambar 9.12. Setelah modifikasi pada page C
9.4.2 Dasar Penggantian Halaman
Pada pembahasan mengenai masalah page-fault, diasumsikan bahwa setiap halaman minimal mengalami satu kali page fault, yaitu pada saat diakses pertama kali. Akan tetapi, tidak semua halaman tersebut akan digunakan oleh suatu proses. Jika terdapat sebuah proses yang memiliki sepuluh halaman, dan hanya menggunakan setengah di antaranya, yaitu lima halaman, maka demand paging menyimpan kelima proses yang tidak dibutuhkan tersebut agar tidak diakses oleh M/K. Dengan begitu, kita dapat meningkatkan degree of multiprogramming, yaitu dengan menjalankan proses dua kali lebih banyak. Jika kita memiliki empat puluh bingkai, kita dapat menjalankan delapan proses. Bandingkan dengan jika kesepuluh halaman tersebut dipanggil, maka hanya dapat dijalankan maksimum empat proses.
Jika kita meningkatkan degree of multiprogramming, yaitu dengan menjalankan proses lebih banyak, maka dapat terjadi over-allocating memory. Misalnya kita menjalankan enam proses yang masing-masing memiliki sepuluh halaman dan seluruhnya dipanggil (di-load) ke memori, maka akan dibutuhkan 60 bingkai, padahal yang tersedia hanya empat puluh bingkai. Over-allocating memory juga dapat terjadi jika terdapat page fault, yaitu pada saat sistem operasi mendapatkan halaman yang dicari pada disk kemudian membawanya ke memori fisik tetapi tidak terdapat bingkai yang kosong pada memori fisik tersebut.
Sistem operasi memiliki dua cara untuk menangani masalah ini. Yang pertama dengan men-terminasi proses yang sedang mengakses halaman tersebut. Akan tetapi, cara ini tidak dapat dilakukan karena demand paging merupakan usaha sistem operasi untuk meningkatkan utilisasi komputer dan throughput-nya.
Cara yang kedua yaitu dengan penggantian halaman (page replacement). Sistem operasi dapat memindahkan suatu proses dari memori fisik, lalu menghapus semua bingkai yang semula digunakannya, dan mengurangi level of multiprogramming (dengan mengurangi jumlah proses yang berjalan).
Prinsip kerja penggantian halaman adalah sebagai berikut. “Jika tidak ada bingkai yang kosong, maka dicari (dengan suatu algoritma ganti halaman) salah satu bingkai yang sedang tidak digunakan dan kemudian dikosongkar. Suatu bingkai dapat dikosongkan dengan memindahkan isinya ke dalam ruang pemindahan kemudian mengubah semua tabel halaman hingga mengindikasikan bahwa halaman yang dipindah tersebut sudah tidak berada di memori fisik. Lalu bingkai yang telah kosong tersebut dapat digunakan oleh halaman yang akan ditempatkan di memori fisik”.
Dengan memodifikasi urutan penanganan page fault, maka dapat dijabarkan urutan proses page replacement sebagai berikut.
Gambar 9.13. Membutuhkan Page Replacement
Hal tersebut dapat diselesaikan dengan menggunakan bit modifikasi (modify bit/dirty bit ). Setiap halaman atau bingkai memiliki bit modifikasi yang sesuai pada perangkat keras. Bit modifikasi untuk sebuah halaman diatur oleh perangkat keras pada saat suatu byte atau word dituliskan ke halaman tersebut, yang menunjukan bahwa halaman tersebut telah dimodifikasi. Waktu suatu halaman dipilih untuk dipindahkan dari memori fisik ke disk, diperiksa terlebih dahulu bit modifikasinya di disk. Jika bit modifikasinya ada, maka halaman tersebut harus ditulis ke disk. Namun, apabila bit modifikasinya belum ada di disk, maka halaman tersebut belum dimodifikasi karena halaman tersebut masih berada di memori utama. Oleh karena itu, jika salinan dari halaman tersebut masih terdapat di disk (belum ditimpa oleh halaman lain) maka penulisan halaman dari memori utama ke disk tidak diperlukan. Hal ini juga berlaku pada halaman read-only, yaitu halaman yang tidak dapat dimodifikasi. Sehingga waktu yang diperlukan untuk penanganan page fault dapat berkurang dengan cukup signifikan karena berkurangnya waktu M/K dari dan ke disk.
Gambar 9.14. Page Replacement
Rangkuman
Memori virtual adalah teknik yang memisahkan antara alamat memori logis dengan alamat memori fisik. Hal tersebut berguna agar pengguna (programmer) tidak perlu menentukan alamat fisik dari program yang dijalankan. Memori vitual memungkinkan beberapa proses berjalan dengan alamat memori fisik yang terbatas. Teknik permintaan halaman (demand paging) digunakan untuk mengimplementasikan konsep memori virtual. Jika halaman yang diminta tidak terdapat pada memori utama, maka akan terjadi page fault. Page fault ini dapat ditangani dengan beberapa tahapan. Dengan adanya page fault ini, maka kinerja demand paging dapat dihitung berdasarkan memory access time dan page fault time (waktu yang dibutuhkan dalam penanganan page fault). Kinerja demand paging ini biasa disebut dengan effective access time.
Pada pembuatan suatu proses baru (proses anak), maka baik proses induk maupun proses anak dapat mengakses suatu halaman yang sama tanda perlu membuat salinannya terlebih dahulu, yaitu dengan teknik copy-on-write. Jika proses anak hendak memodifikasi halaman tersebut, maka baru akan dibuatkan salinan dari halaman tersebut untuk kemudian dimodifikasi oleh proses anak. Halaman yang disalin tersebut dinamakan halaman copy-on-write .
Jika ada suatu halaman diminta/dibutuhkan oleh suatu proses dan ternyata halaman tersebut terdapat di disk, maka halaman tersebut akan dipindahkan ke memori utama. Namun, jika di memori utama tidak lagi terdapat bingkai yang kosong (free frame) untuk ditempati oleh halaman tersebut, maka akan terjadi penggantian halaman (page replacement) dengan memilih suatu bingkai pada memori dan menggantikan isinya dengan halaman tersebut. Pada pemilihan suatu bingkai ini, dibutuhkan suatu algoritma penggantian halaman.
Rujukan
Dr. Bambang Hariyanto. 2006. Sistem Operasi. Revisi Keempat. Informatika.
[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons.
[Tanenbaum1997] Andrew S Tanenbaum dan Albert S Woodhull. 1997. Operating Systems Design and Implementation. Second Edition. Prentice-Hall.
[WEBbebasvlsm2006] Masyarakat Digital Gotong Royong .2006. Pengantar Sistem Operasi Komputer http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-2/index.html .
[WEBwikipedia] Article: Copy-on-write. http://en.wikipedia.org/wiki/Copy-on-write .
[WEBUniversityofToronto] Computer Science. 2007. Virtual Memory Mechanism. http://www.cs.toronto.edu/~demke/369S.07/Lectures/VirtualMemory_full.pdf.
9.4.1 Pendahuluan
Pada pembahasan sebelumnya dijelaskan bahwa memori virtual memungkinkan proses untuk saling berbagi pakai memori. Proses ini adalah proses untuk berbagi pakai halaman (page sharing) memori virtual. Karena setiap proses membutuhkan halaman tersendiri, maka dibutuhkan teknik untuk mengaturnya. Teknik yang digunakan untuk mengoptimasi pembuatan dan penggunaan halaman adalah teknik copy-on-write, atau yang biasa disingkat dengan COW.
Pembuatan proses baru dengan menggunakan sistem call fork() menciptakan proses anak sebagai duplikat dari proses induknya. Setelah berhasil menciptakan proses anak, kemudian proses anak tersebut langsung memanggil sistem call exec(), yang berarti bahwa proses anak juga menduplikasi ruang alamat yang dimiliki proses induknya, beserta halaman yang diaksesnya. Padahal, hasil kopian dari halaman tersebut belum tentu berguna, yaitu jika tidak ada proses modifikasi pada halaman tersebut. Akan tetapi, dengan menggunakan teknik copy-on-write maka proses anak dan induk dapat bersama-sama menggunakan (mengakses) halaman yang sama.
Suatu halaman yang diakses secara bersama-sama (shared) oleh beberapa proses ditandai dengan COW (copy-on-write) jika suatu proses ingin memodifikasi (menulis) suatu halaman. Dan apabila hal tersebut terjadi, maka akan dibuat salinan dari halaman yang di-shared tersebut.
Sebagai contoh, sebuah proses anak akan memodifikasi suatu halaman yang terdiri dari sebagian dari stack. Sistem operasi akan mengenali halaman ini sebagai halaman copy-on-write. Sistem operasi kemudian akan membuat salinan dari halaman ini dan memetakannya kepada ruang alamat yang dimiliki proses anak. Proses anak kemudian memodifikasi halaman salinan yang telah berada di ruang alamat proses anak tersebut. Pada saat teknik copy-on-write ini digunakan, hanya halaman yang bisa dimodifikasi (oleh proses anak atau proses induk) saja yang disalin, sedangkan halaman yang tidak dimodifikasi dapat dibagi (di-share) untuk proses induk dan proses anak. Sebagai catatan, bahwa hanya halaman yang dapat dimodifikasi saja yang ditandai sebagai copy-on-write, sedangkan halaman yang tidak dapat dimodifikasi (misalnya halaman yang terdiri dari kode-kode yang bisa dieksekusi) tidak perlu ditandai karena tidak akan terjadi modifikasi pada halaman tersebut.
Pada banyak sistem operasi, disediakan sebuah pool yang terdiri dari halaman-halaman yang kosong untuk meletakkan halaman hasil duplikasi dengan teknik copy-on-write. Selain untuk meletakkan halaman hasil duplikasi tersebut, pool ini juga digunakan pada saat sebuah proses mengalami penambahan stack atau heap. Teknik yang digunakan sistem operasi untuk menyediakan halaman kosong tersebut dikenal dengan zero-fill-on-demand. Teknik ini dilakukan dengan mengosongkan halaman-halaman sebelum digunakan oleh proses yang baru.
Copy-on-write dapat diilustrasikan pada gambar 4 dan 5.
Gambar 9.11. Sebelum modifikasi pada page C
Gambar 9.12. Setelah modifikasi pada page C
9.4.2 Dasar Penggantian Halaman
Pada pembahasan mengenai masalah page-fault, diasumsikan bahwa setiap halaman minimal mengalami satu kali page fault, yaitu pada saat diakses pertama kali. Akan tetapi, tidak semua halaman tersebut akan digunakan oleh suatu proses. Jika terdapat sebuah proses yang memiliki sepuluh halaman, dan hanya menggunakan setengah di antaranya, yaitu lima halaman, maka demand paging menyimpan kelima proses yang tidak dibutuhkan tersebut agar tidak diakses oleh M/K. Dengan begitu, kita dapat meningkatkan degree of multiprogramming, yaitu dengan menjalankan proses dua kali lebih banyak. Jika kita memiliki empat puluh bingkai, kita dapat menjalankan delapan proses. Bandingkan dengan jika kesepuluh halaman tersebut dipanggil, maka hanya dapat dijalankan maksimum empat proses.
Jika kita meningkatkan degree of multiprogramming, yaitu dengan menjalankan proses lebih banyak, maka dapat terjadi over-allocating memory. Misalnya kita menjalankan enam proses yang masing-masing memiliki sepuluh halaman dan seluruhnya dipanggil (di-load) ke memori, maka akan dibutuhkan 60 bingkai, padahal yang tersedia hanya empat puluh bingkai. Over-allocating memory juga dapat terjadi jika terdapat page fault, yaitu pada saat sistem operasi mendapatkan halaman yang dicari pada disk kemudian membawanya ke memori fisik tetapi tidak terdapat bingkai yang kosong pada memori fisik tersebut.
Sistem operasi memiliki dua cara untuk menangani masalah ini. Yang pertama dengan men-terminasi proses yang sedang mengakses halaman tersebut. Akan tetapi, cara ini tidak dapat dilakukan karena demand paging merupakan usaha sistem operasi untuk meningkatkan utilisasi komputer dan throughput-nya.
Cara yang kedua yaitu dengan penggantian halaman (page replacement). Sistem operasi dapat memindahkan suatu proses dari memori fisik, lalu menghapus semua bingkai yang semula digunakannya, dan mengurangi level of multiprogramming (dengan mengurangi jumlah proses yang berjalan).
Prinsip kerja penggantian halaman adalah sebagai berikut. “Jika tidak ada bingkai yang kosong, maka dicari (dengan suatu algoritma ganti halaman) salah satu bingkai yang sedang tidak digunakan dan kemudian dikosongkar. Suatu bingkai dapat dikosongkan dengan memindahkan isinya ke dalam ruang pemindahan kemudian mengubah semua tabel halaman hingga mengindikasikan bahwa halaman yang dipindah tersebut sudah tidak berada di memori fisik. Lalu bingkai yang telah kosong tersebut dapat digunakan oleh halaman yang akan ditempatkan di memori fisik”.
Dengan memodifikasi urutan penanganan page fault, maka dapat dijabarkan urutan proses page replacement sebagai berikut.
- Mencari lokasi dari halaman yang dicari di disk.
- Mencari bingkai yang kosong di memori fisik:
- Jika ada bingkai yang kosong, maka gunakan bingkai tersebut.
- Jika tidak ada bingkai yang kosong, gunakan algoritma ganti halaman untuk memilih bingkai “korban”
- Pindahkan bingkai “korban” tersebut ke disk dan sesuaikan tabel halaman.
- Masukkan halaman yang berasal dari disk tersebut ke dalam bingkai yang baru dikosongkan tersebut. Sesuaikan tabel halaman.
- Lanjutkan proses yang telah diinterupsi.
Gambar 9.13. Membutuhkan Page Replacement
Hal tersebut dapat diselesaikan dengan menggunakan bit modifikasi (modify bit/dirty bit ). Setiap halaman atau bingkai memiliki bit modifikasi yang sesuai pada perangkat keras. Bit modifikasi untuk sebuah halaman diatur oleh perangkat keras pada saat suatu byte atau word dituliskan ke halaman tersebut, yang menunjukan bahwa halaman tersebut telah dimodifikasi. Waktu suatu halaman dipilih untuk dipindahkan dari memori fisik ke disk, diperiksa terlebih dahulu bit modifikasinya di disk. Jika bit modifikasinya ada, maka halaman tersebut harus ditulis ke disk. Namun, apabila bit modifikasinya belum ada di disk, maka halaman tersebut belum dimodifikasi karena halaman tersebut masih berada di memori utama. Oleh karena itu, jika salinan dari halaman tersebut masih terdapat di disk (belum ditimpa oleh halaman lain) maka penulisan halaman dari memori utama ke disk tidak diperlukan. Hal ini juga berlaku pada halaman read-only, yaitu halaman yang tidak dapat dimodifikasi. Sehingga waktu yang diperlukan untuk penanganan page fault dapat berkurang dengan cukup signifikan karena berkurangnya waktu M/K dari dan ke disk.
Gambar 9.14. Page Replacement
Rangkuman
Memori virtual adalah teknik yang memisahkan antara alamat memori logis dengan alamat memori fisik. Hal tersebut berguna agar pengguna (programmer) tidak perlu menentukan alamat fisik dari program yang dijalankan. Memori vitual memungkinkan beberapa proses berjalan dengan alamat memori fisik yang terbatas. Teknik permintaan halaman (demand paging) digunakan untuk mengimplementasikan konsep memori virtual. Jika halaman yang diminta tidak terdapat pada memori utama, maka akan terjadi page fault. Page fault ini dapat ditangani dengan beberapa tahapan. Dengan adanya page fault ini, maka kinerja demand paging dapat dihitung berdasarkan memory access time dan page fault time (waktu yang dibutuhkan dalam penanganan page fault). Kinerja demand paging ini biasa disebut dengan effective access time.
Pada pembuatan suatu proses baru (proses anak), maka baik proses induk maupun proses anak dapat mengakses suatu halaman yang sama tanda perlu membuat salinannya terlebih dahulu, yaitu dengan teknik copy-on-write. Jika proses anak hendak memodifikasi halaman tersebut, maka baru akan dibuatkan salinan dari halaman tersebut untuk kemudian dimodifikasi oleh proses anak. Halaman yang disalin tersebut dinamakan halaman copy-on-write .
Jika ada suatu halaman diminta/dibutuhkan oleh suatu proses dan ternyata halaman tersebut terdapat di disk, maka halaman tersebut akan dipindahkan ke memori utama. Namun, jika di memori utama tidak lagi terdapat bingkai yang kosong (free frame) untuk ditempati oleh halaman tersebut, maka akan terjadi penggantian halaman (page replacement) dengan memilih suatu bingkai pada memori dan menggantikan isinya dengan halaman tersebut. Pada pemilihan suatu bingkai ini, dibutuhkan suatu algoritma penggantian halaman.
Rujukan
Dr. Bambang Hariyanto. 2006. Sistem Operasi. Revisi Keempat. Informatika.
[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons.
[Tanenbaum1997] Andrew S Tanenbaum dan Albert S Woodhull. 1997. Operating Systems Design and Implementation. Second Edition. Prentice-Hall.
[WEBbebasvlsm2006] Masyarakat Digital Gotong Royong .2006. Pengantar Sistem Operasi Komputer http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-2/index.html .
[WEBwikipedia] Article: Copy-on-write. http://en.wikipedia.org/wiki/Copy-on-write .
[WEBUniversityofToronto] Computer Science. 2007. Virtual Memory Mechanism. http://www.cs.toronto.edu/~demke/369S.07/Lectures/VirtualMemory_full.pdf.
9.5 Algoritma Penggantian Halaman
9.5.1 Pendahuluan
Ganti halaman dilakukan apabila terjadi page fault. Page fault bukan suatu jenis error yang fatal, page fault terjadi apabila ada halaman yang ingin diakses tetapi halaman tersebut tidak terdapat di dalam memori utama. Page fault pasti terjadi minimal satu kali saat pertama kali halaman itu ingin diakses.
Prinsip ganti halaman adalah sebagai berikut:
Semakin banyak dilakukan swap, semakin sibuk pula CPU mengurus hal ini. Bila berkelanjutan, maka akan terjadi thrashing. Thrashing adalah keadaan di mana banyak terjadi page fault, sehingga mengakibatkan utilisasi CPU menurun drastis karena lebih sibuk mengurusi pergantian halaman daripada mengurusi proses.
Untuk menghindari hal ini, diperlukan pemilihan algoritma ganti halaman yang baik. Kriteria algoritma yang baik adalah:
9.5.2 Reference String
Reference string adalah string yang merepresentasikan halaman-halaman yang ingin digunakan/di-load . Kegunaannya adalah untuk menyederhanakan alamat dan mempermudah melihat page fault rate yang terjadi serta mensimulasikan algoritma ganti halaman. Biasanya reference string berisi kumpulan alamat-alamat halaman yang dikelompokkan berdasarkan aturan reduksi reference string. Bila pereduksian alamat sebanyak 1000 bytes, maka alamat-alamat yang berurutan sebanyak 1000 bytes diwakili oleh satu buah reference string. Misalnya 0003, 0563, 0094 diwakili oleh reference string 0. Demikian juga 1745, 1003, 1999 diwakili oleh reference string 1 dan seterusnya.
Contoh:
Urutan alamat yang digunakan oleh sebuah proses adalah 0301, 0213, 0312, 0321, 0341, 0421, 0431, 0132, 0431, 0152. Maka, reference string-nya dengan reduksi 100 bytes adalah 3, 2, 3, 4, 1, 4, 1.
Bagaimana cara men-generate sebuah reference string dari urutan alamat? Reference string dihasilkan dari bit tertentu dari sebuah alamat (biasanya bit kedua dari kiri, yang berarti direduksi 100 bytes), maka alamat 0431 menjadi 4, 0241 menjadi 2, dan 0252 menjadi 2.
Apabila terdapat urutan alamat yang string acuannya sama berturut-turut, misalnya 0431 dan 0452, maka tetap ditulis sebagai 4, karena tidak me-load halaman yang baru.
9.5.3 Algoritma Penggantian Page Acak
Mekanisme algoritma
Setiap terjadi page fault, page yang diganti dipilih secara acak.
Teknik ini tidak memakai informasi apapun dalam menentukan page yang diganti. Semua page di memori utama mempunyai bobot sama untuk dipilih. Teknik ini dapat memilih sembarang page, termasuk page yang sedang diacu (page yang seharusnya tidak diganti, pilihan terburuk).
Teknik ini sangat buruk, percobaan menunjukkan algoritma acak menimbulkan rate terjadinya page fault yang sangat tinggi.
9.5.4 Algoritma FIFO (First In First Out)
Algoritma ini adalah algoritma yang paling sederhana. Prinsip dari algoritma ini adalah seperti prinsip antrian (antrian tak berprioritas), halaman yang masuk lebih dulu maka akan keluar lebih dulu juga. Algoritma ini menggunakan struktur data stack. Apabila tidak ada frame kosong saat terjadi page fault, maka korban yang dipilih adalah frame yang berada di stack paling bawah, yaitu halaman yang berada paling lama berada di memori. Dengan hanya informasi mengenai lama berada di memori, maka algoritma ini dapat memindahkan page yang sering digunakan. Boleh jadi page itu berada terus di memori karena selalu digunakan. Page itu karena mengikuti pola antrian berdasar lamanya berada di memori menjadi elemen terdepan, diganti, dan segera harus masuk kembali ke memori sehingga terjadi page fault kembali.
Gambar 9.16. Algoritma FIFO
Pada awalnya, algoritma ini dianggap cukup mengatasi masalah tentang pergantian halaman, sampai pada tahun 70-an, Belady menemukan keanehan pada algoritma ini yang dikenal kemudian dengan anomali Belady. Anomali Belady adalah keadaan di mana page fault rate meningkat seiring dengan pertambahan jumlah frame , seperti yang bisa dilihat pada contoh di bawah ini.
Gambar 9.17. Anomali Algoritma FIFO
Ketika jumlah frame ditambah dari 3 frame menjadi 4 frame, jumlah page fault yang terjadi malah bertambah (dari 14 page fault menjadi 15 page fault ). Hal ini biasanya terjadi pada kasus yang menginginkan halaman yang baru saja di-swap-out sebelumnya. Oleh karena itu, dicarilah algoritma lain yang mampu lebih baik dalam penanganan pergantian halaman seperti algoritma optimal.
Algoritma FIFO murni jarang digunakan, tetapi dikombinasikan (modifikasi).
Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering digunakan yang lama berada di memori. Kemungkinan ini dapat dihindari dengan hanya memindahkan page tidak diacu Page ditambah bit R mencatat apakah page diacu atau tidak. Bit R bernilai 1 bila diacu dan bernilai 0 bila tidak diacu.
Variasi dari FIFO antara lain:
Mekanisme algoritma
Algoritma penggantian page kesempatan kedua merupakan algoritma yang memadai tapi tidak efisien karena memindahkan page-page di senarainya. Algoritma penggantian clock page merupakan perbaikan algoritma pertama.
Mekanisme algoritma
Algoritma ini adalah algoritma yang paling optimal sesuai namanya. Prinsip dari algoritma ini adalah mengganti halaman yang tidak akan terpakai lagi dalam waktu lama, sehingga efisiensi pergantian halaman meningkat (page fault yang terjadi berkurang) dan terbebas dari anomali Belady. Strategi ini akan menghasilkan jumlah page-fault paling sedikit. Algoritma ini memiliki page fault rate paling rendah di antara semua algoritma di semua kasus. Akan tetapi, optimal belum berarti sempurna karena algoritma ini ternyata sangat sulit untuk diterapkan. Sistem tidak dapat mengetahui halaman-halaman mana saja yang akan digunakan berikutnya. Pendekatan ini dapat dilakukan dengan simulasi. Tapi simulasi hanya spesifik untuk suatu program. Bila yang terbaik tak dimungkinkan, maka yang perlu dilakukan adalah berusaha mendekatinya. Algoritma penggantian page diusahakan kinerjanya mendekati optimal. Tiap algoritma penggantian page mengumpulkan dan memakai informasi untuk menentukan page yang diganti sehingga mendekati optimal.
Gambar 9.18. Algoritma Optimal
9.5.5 Algoritma LRU (Least Recently Used)
Dikarenakan algoritma optimal sangat sulit dalam pengimplementasiannya, maka dibuatlah algoritma lain yang performance-nya mendekati algoritma optimal dengan sedikit cost yang lebih besar. Algoritma ini mengganti halaman yang paling lama tidak dibutuhkan. Asumsinya, halaman yang sudah lama tidak digunakan sudah tidak dibutuhkan lagi dan kemungkinan besar, halaman yang baru di-load akan digunakan kembali.
Sama seperti algoritma optimal, algoritma LRU tidak mengalami anomali Belady. Algoritma ini memakai linked list untuk mendata halaman mana yang paling lama tidak terpakai. Linked list inilah yang membuat cost membesar, karena harus meng-update linked list tiap saat ada halaman yang di akses. Halaman yang berada di linked list paling depan adalah halaman yang baru saja digunakan. Semakin lama tidak dipakai, halaman akan berada semakin belakang dan di posisi terakhir adalah halaman yang paling lama tidak digunakan dan siap untuk di-swap.
Gambar 9.19. Algoritma LRU
9.5.6 Implementasi LRU
Ada beberapa cara untuk mengimplementasikan algoritma LRU. Tetapi, yang cukup terkenal ada 2, yaitu counter dan stack. Contoh algoritma di atas menggunakan stack.
Counter . Cara ini dilakukan dengan menggunakan counter atau logical clock. Setiap halaman memiliki nilai yang pada awalnya diinisialisasi dengan 0. Ketika mengakses ke suatu halaman baru, nilai pada clock di halaman tersebut akan bertambah 1. Semakin sering halaman itu diakses, semakin besar pula nilai counter-nya dan sebaliknya. Untuk melakukan hal itu dibutuhkan extra write ke memori. Selain berisi halaman-halaman yang sedang di-load, memori juga berisi tentang counter masing-masing halaman. Halaman yang diganti adalah halaman yang memiliki nilai clock terkecil, yaitu halaman yang paling jarang diakses. Kekurangan dari cara ini adalah memerlukan dukungan tambahan counter pada hardware.
Stack. Cara ini dilakukan dengan menggunakan stack yang menandakan halaman-halaman yang berada di memori. Setiap kali suatu halaman diakses, akan diletakkan di bagian paling atas stack. Apabila ada halaman yang perlu diganti, maka halaman yang berada di bagian paling bawah stack akan diganti sehingga setiap kali halaman baru diakses tidak perlu mencari kembali halaman yang akan diganti. Dibandingkan pengimplementasian dengan counter, cost untuk mengimplementasikan algoritma LRU dengan menggunakan stack akan lebih mahal karena seluruh isi stack harus di-update setiap kali mengakses halaman, sedangkan dengan counter, yang dirubah hanya counter halaman yang sedang diakses, tidak perlu mengubah counter dari semua halaman yang ada.
Gambar 9.20. Algoritma LRU dengan Stack
9.5.7 Algoritma Penggantian Page NRU (Not-Recenly Used)
Mekanisme algoritmanya
Pada algoritma ini, page diberi dua bit mencatat status page, bit R dan M, yaitu:
Bit R : referenced (menyatakan page sedang diacu)
Bit R = 1 berarti sedang diacu
Bit R = 0 berarti tidak sedang diacu
Bit M : modified (menyatakan page telah dimodifikasi)
Bit M = 1 berarti dimodifikasi
Bit M = 0 berarti tidak dimodifikasi
Dengan 2 bit, maka page-page dikelompokkan menjadi 4 kelas page, yaitu
Kelas 0 : Tidak sedang diacu, belum dimodifikasi (R=0, M=0)
Kelas 1 : Tidak sedang diacu, telah dimodifikasi (R=0, M=1)
Kelas 2 : Sedang diacu, belum dimodifikasi (R=1, M=0)
Kelas 3 : Sedang diacu, telah dimodifikasi (R=1, M=1)
Memilih mengganti page kelas bernomor terendah (bila terdapat page-page di kelas itu) secara acak.
Bila kelas tersebut kosong maka dipilih page di kelas lebih tinggi, dan seterusnya.
Algoritma ini mengasumsikan kelas-kelas bernomor lebih rendah akan baru akan digunakan kembali dalam waktu relatif lama.
Algoritma ini mudah dipahami dan diimplementasikan. Implementasi algoritma ini sangat efisien karena tak banyak langkah dalam pemilihan page. Algoritma ini memang tidak optimal, tapi dalam kondisi-kondisi normal telah memadai.
9.5.8 Algoritma Lainnya
Sebenarnya masih banyak algoritma ganti halaman yang lain selain 3 algoritma utama yang telah dibahas sebelumnya (utama bukan berarti paling sering dipakai). Berikut ini adalah 2 contoh algoritma lain yang juga cukup popular dan mudah diimplementasikan.
Algoritma yang pertama adalah algoritma second chance. Algoritma second chance berdasarkan pada algoritma FIFO yang disempurnakan. Algoritma ini menggunakan tambahan berupa reference bit yang nilainya 0 atau 1. Jika dalam FIFO menggunakan stack , maka second chance menggunakan circular queue . Halaman yang baru di-load atau baru digunakan akan diberikan nilai 1 pada reference bit-nya. Halaman yang reference bit-nya bernilai 1 tidak akan langsung diganti walaupun dia berada di antrian paling bawah (berbeda dengan FIFO).
Urutan langkah kerja algoritma second chance adalah sebagai berikut:
Gambar 9.21. Algoritma Second Chance
Gambar 9.22. Algoritma FIFO
Algoritma kedua adalah algoritma random. Algoritma random adalah algoritma yang cukup sederhana juga selain algoritma FIFO. Dalam algoritma ini, halaman yang dipilih menjadi korban dipilih secara acak.
Meskipun terdengar asal, tetapi algoritma ini relatif low cost, karena tidak memerlukan stack, queue atau counter. Dibandingkan dengan FIFO, rata-rata kasus menunjukkan page fault rate algoritma random lebih rendah daripada algoritma FIFO. Sedangkan dibandingkan dengan LRU, algorima random ini lebih unggul dalam hal memory looping reference , karena algoritma random sama sekali tidak memerlukan looping.
Gambar 9.23. Algoritma Random
Rangkuman
Page fault terjadi apabila terdapat halaman yang ingin diakses tetapi halaman tersebut tidak terdapat di dalam memori utama.
Jika terjadi page fault dan tidak ada frame yang kosong, maka dipilih frame tumbal yang akan di-swap.
Pemilihan halaman dilakukan dengan algoritma ganti halaman. Algoritma dipilih yang paling rendah page fault rate-nya dan tidak sulit untuk diimplementasikan.
Contoh algoritma ganti halaman:
[Silberschatz2002] Abraham Silberschatz, Peter Galvin, dan Greg Gagne. 2002. Applied Operating Systems. Sixth Edition. John Wiley & Sons.
[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons.
[Tanenbaum1997] Andrew S Tanenbaum dan Albert S Woodhull. 1997. Operating Systems Design and Implementation. Second Edition. Prentice-Hall.
[WEBAmirSch2000] YairTheo AmirSchlossnagle. 2000. Operating Systems 00.418: Memory Management – http://www.cs.jhu.edu/ ~yairamir/ cs418/ os5/ .
[WEBEgui2006] Equi4 Software. 2006. Memory Mapped Files – http://www.equi4.com/mkmmf.html .
[WEBFunkhouser2002] Thomas Funkhouser. 2002. Computer Science 217 Introduction to Programming Systems: Memory Paging – http://www.cs.princeton.edu/ courses/ archive / spring02/ cs217/ lectures/ paging.pdf .
[WEBGottlieb2000] Allan Gottlieb. 2000. Operating Systems: Page tables – http://allan.ultra.nyu.edu/ ~gottlieb/ courses/ 1999-00-spring/ os/ lecture-11.html .
[WEBSolomon2004] Marvin Solomon. 2004. CS 537 Introduction to Operating Systems: Lecture Notes Part 7 – http://www.cs.wisc.edu/ ~solomon/ cs537/ paging.html .
[WEBWiki2006c] From Wikipedia, the free encyclopedia. 2006. Memory Management Unit – http://en.wikipedia.org/ wiki/ Memory_management_unit .
[WEBWiki2006d] From Wikipedia, the free encyclopedia. 2006. Page Fault – http://en.wikipedia.org/ wiki/ Page_fault .
[WEBWiki2006e] From Wikipedia, the free encyclopedia. 2006. Copy on Write – http://en.wikipedia.org/ wiki/ Copy_on_Write .
[WEBWiki2007] Wikipedia. 2007. Page Replacement Algortihm http://en.wikipedia.org/wiki/Page_replacement_algorithm .
Kembali ke daftar isi
9.5.1 Pendahuluan
Ganti halaman dilakukan apabila terjadi page fault. Page fault bukan suatu jenis error yang fatal, page fault terjadi apabila ada halaman yang ingin diakses tetapi halaman tersebut tidak terdapat di dalam memori utama. Page fault pasti terjadi minimal satu kali saat pertama kali halaman itu ingin diakses.
Prinsip ganti halaman adalah sebagai berikut:
- Proses meminta halaman tertentu.
- Jika halaman berada di memori, tidak dilakukan ganti halaman.
- Jika halaman tidak berada di memori, maka:
- Jika ada frame kosong, maka halaman itu di-load ke dalam frame yang kosong tersebut.
- Jika tidak ada frame yang kosong, maka pilih halaman yang akan di-swap dengan menggunakan algoritma ganti halaman.
- Update tabel halaman dan table memori.
- Restart proses.
Semakin banyak dilakukan swap, semakin sibuk pula CPU mengurus hal ini. Bila berkelanjutan, maka akan terjadi thrashing. Thrashing adalah keadaan di mana banyak terjadi page fault, sehingga mengakibatkan utilisasi CPU menurun drastis karena lebih sibuk mengurusi pergantian halaman daripada mengurusi proses.
Untuk menghindari hal ini, diperlukan pemilihan algoritma ganti halaman yang baik. Kriteria algoritma yang baik adalah:
- Menyebabkan page fault rate yang rendah.
- Tidak menyebabkan thrashing .
- Tidak terlalu sulit untuk diimplementasikan.
9.5.2 Reference String
Reference string adalah string yang merepresentasikan halaman-halaman yang ingin digunakan/di-load . Kegunaannya adalah untuk menyederhanakan alamat dan mempermudah melihat page fault rate yang terjadi serta mensimulasikan algoritma ganti halaman. Biasanya reference string berisi kumpulan alamat-alamat halaman yang dikelompokkan berdasarkan aturan reduksi reference string. Bila pereduksian alamat sebanyak 1000 bytes, maka alamat-alamat yang berurutan sebanyak 1000 bytes diwakili oleh satu buah reference string. Misalnya 0003, 0563, 0094 diwakili oleh reference string 0. Demikian juga 1745, 1003, 1999 diwakili oleh reference string 1 dan seterusnya.
Contoh:
Urutan alamat yang digunakan oleh sebuah proses adalah 0301, 0213, 0312, 0321, 0341, 0421, 0431, 0132, 0431, 0152. Maka, reference string-nya dengan reduksi 100 bytes adalah 3, 2, 3, 4, 1, 4, 1.
Bagaimana cara men-generate sebuah reference string dari urutan alamat? Reference string dihasilkan dari bit tertentu dari sebuah alamat (biasanya bit kedua dari kiri, yang berarti direduksi 100 bytes), maka alamat 0431 menjadi 4, 0241 menjadi 2, dan 0252 menjadi 2.
Apabila terdapat urutan alamat yang string acuannya sama berturut-turut, misalnya 0431 dan 0452, maka tetap ditulis sebagai 4, karena tidak me-load halaman yang baru.
9.5.3 Algoritma Penggantian Page Acak
Mekanisme algoritma
Setiap terjadi page fault, page yang diganti dipilih secara acak.
Teknik ini tidak memakai informasi apapun dalam menentukan page yang diganti. Semua page di memori utama mempunyai bobot sama untuk dipilih. Teknik ini dapat memilih sembarang page, termasuk page yang sedang diacu (page yang seharusnya tidak diganti, pilihan terburuk).
Teknik ini sangat buruk, percobaan menunjukkan algoritma acak menimbulkan rate terjadinya page fault yang sangat tinggi.
9.5.4 Algoritma FIFO (First In First Out)
Algoritma ini adalah algoritma yang paling sederhana. Prinsip dari algoritma ini adalah seperti prinsip antrian (antrian tak berprioritas), halaman yang masuk lebih dulu maka akan keluar lebih dulu juga. Algoritma ini menggunakan struktur data stack. Apabila tidak ada frame kosong saat terjadi page fault, maka korban yang dipilih adalah frame yang berada di stack paling bawah, yaitu halaman yang berada paling lama berada di memori. Dengan hanya informasi mengenai lama berada di memori, maka algoritma ini dapat memindahkan page yang sering digunakan. Boleh jadi page itu berada terus di memori karena selalu digunakan. Page itu karena mengikuti pola antrian berdasar lamanya berada di memori menjadi elemen terdepan, diganti, dan segera harus masuk kembali ke memori sehingga terjadi page fault kembali.
Gambar 9.16. Algoritma FIFO
Pada awalnya, algoritma ini dianggap cukup mengatasi masalah tentang pergantian halaman, sampai pada tahun 70-an, Belady menemukan keanehan pada algoritma ini yang dikenal kemudian dengan anomali Belady. Anomali Belady adalah keadaan di mana page fault rate meningkat seiring dengan pertambahan jumlah frame , seperti yang bisa dilihat pada contoh di bawah ini.
Gambar 9.17. Anomali Algoritma FIFO
Ketika jumlah frame ditambah dari 3 frame menjadi 4 frame, jumlah page fault yang terjadi malah bertambah (dari 14 page fault menjadi 15 page fault ). Hal ini biasanya terjadi pada kasus yang menginginkan halaman yang baru saja di-swap-out sebelumnya. Oleh karena itu, dicarilah algoritma lain yang mampu lebih baik dalam penanganan pergantian halaman seperti algoritma optimal.
Algoritma FIFO murni jarang digunakan, tetapi dikombinasikan (modifikasi).
Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering digunakan yang lama berada di memori. Kemungkinan ini dapat dihindari dengan hanya memindahkan page tidak diacu Page ditambah bit R mencatat apakah page diacu atau tidak. Bit R bernilai 1 bila diacu dan bernilai 0 bila tidak diacu.
Variasi dari FIFO antara lain:
- Algoritma penggantian page kesempatan kedua (second chance page replacement algorithm)
- Algoritma penggantian clock page (clock page replacement algorithm)
Mekanisme algoritma
- Saat terjadi 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. Mekanisme ini kembali diterapkan ke elemen berikutnya.
Algoritma penggantian page kesempatan kedua merupakan algoritma yang memadai tapi tidak efisien karena memindahkan page-page di senarainya. Algoritma penggantian clock page merupakan perbaikan algoritma pertama.
Mekanisme algoritma
- Pada algoritma ini, semua page merupakan senarai melingkar membentuk pola jam. Terdapat penunjuk (pointer) ke page tertua.
- Jika bit R bernilai 0, maka page diganti. Page baru ditempatkan di tempat page diganti, dan penunjuk dimajukan satu posisi ke page berikutnya.
- Jika bit R bernilai 1, maka bit R direset menjadi 0, dan penunjuk dimajukan satu posisi. Seterusnya sampai menemui page dengan bit R bernilai 0.
- Algoritma penggantian page kesempatan kedua menggunakan senarai lurus tidak sirkular.
- Algoritma penggantian clock page menggunakan senarai sirkular.
Algoritma ini adalah algoritma yang paling optimal sesuai namanya. Prinsip dari algoritma ini adalah mengganti halaman yang tidak akan terpakai lagi dalam waktu lama, sehingga efisiensi pergantian halaman meningkat (page fault yang terjadi berkurang) dan terbebas dari anomali Belady. Strategi ini akan menghasilkan jumlah page-fault paling sedikit. Algoritma ini memiliki page fault rate paling rendah di antara semua algoritma di semua kasus. Akan tetapi, optimal belum berarti sempurna karena algoritma ini ternyata sangat sulit untuk diterapkan. Sistem tidak dapat mengetahui halaman-halaman mana saja yang akan digunakan berikutnya. Pendekatan ini dapat dilakukan dengan simulasi. Tapi simulasi hanya spesifik untuk suatu program. Bila yang terbaik tak dimungkinkan, maka yang perlu dilakukan adalah berusaha mendekatinya. Algoritma penggantian page diusahakan kinerjanya mendekati optimal. Tiap algoritma penggantian page mengumpulkan dan memakai informasi untuk menentukan page yang diganti sehingga mendekati optimal.
Gambar 9.18. Algoritma Optimal
9.5.5 Algoritma LRU (Least Recently Used)
Dikarenakan algoritma optimal sangat sulit dalam pengimplementasiannya, maka dibuatlah algoritma lain yang performance-nya mendekati algoritma optimal dengan sedikit cost yang lebih besar. Algoritma ini mengganti halaman yang paling lama tidak dibutuhkan. Asumsinya, halaman yang sudah lama tidak digunakan sudah tidak dibutuhkan lagi dan kemungkinan besar, halaman yang baru di-load akan digunakan kembali.
Sama seperti algoritma optimal, algoritma LRU tidak mengalami anomali Belady. Algoritma ini memakai linked list untuk mendata halaman mana yang paling lama tidak terpakai. Linked list inilah yang membuat cost membesar, karena harus meng-update linked list tiap saat ada halaman yang di akses. Halaman yang berada di linked list paling depan adalah halaman yang baru saja digunakan. Semakin lama tidak dipakai, halaman akan berada semakin belakang dan di posisi terakhir adalah halaman yang paling lama tidak digunakan dan siap untuk di-swap.
Gambar 9.19. Algoritma LRU
9.5.6 Implementasi LRU
Ada beberapa cara untuk mengimplementasikan algoritma LRU. Tetapi, yang cukup terkenal ada 2, yaitu counter dan stack. Contoh algoritma di atas menggunakan stack.
Counter . Cara ini dilakukan dengan menggunakan counter atau logical clock. Setiap halaman memiliki nilai yang pada awalnya diinisialisasi dengan 0. Ketika mengakses ke suatu halaman baru, nilai pada clock di halaman tersebut akan bertambah 1. Semakin sering halaman itu diakses, semakin besar pula nilai counter-nya dan sebaliknya. Untuk melakukan hal itu dibutuhkan extra write ke memori. Selain berisi halaman-halaman yang sedang di-load, memori juga berisi tentang counter masing-masing halaman. Halaman yang diganti adalah halaman yang memiliki nilai clock terkecil, yaitu halaman yang paling jarang diakses. Kekurangan dari cara ini adalah memerlukan dukungan tambahan counter pada hardware.
Stack. Cara ini dilakukan dengan menggunakan stack yang menandakan halaman-halaman yang berada di memori. Setiap kali suatu halaman diakses, akan diletakkan di bagian paling atas stack. Apabila ada halaman yang perlu diganti, maka halaman yang berada di bagian paling bawah stack akan diganti sehingga setiap kali halaman baru diakses tidak perlu mencari kembali halaman yang akan diganti. Dibandingkan pengimplementasian dengan counter, cost untuk mengimplementasikan algoritma LRU dengan menggunakan stack akan lebih mahal karena seluruh isi stack harus di-update setiap kali mengakses halaman, sedangkan dengan counter, yang dirubah hanya counter halaman yang sedang diakses, tidak perlu mengubah counter dari semua halaman yang ada.
Gambar 9.20. Algoritma LRU dengan Stack
9.5.7 Algoritma Penggantian Page NRU (Not-Recenly Used)
Mekanisme algoritmanya
Pada algoritma ini, page diberi dua bit mencatat status page, bit R dan M, yaitu:
Bit R : referenced (menyatakan page sedang diacu)
Bit R = 1 berarti sedang diacu
Bit R = 0 berarti tidak sedang diacu
Bit M : modified (menyatakan page telah dimodifikasi)
Bit M = 1 berarti dimodifikasi
Bit M = 0 berarti tidak dimodifikasi
Dengan 2 bit, maka page-page dikelompokkan menjadi 4 kelas page, yaitu
Kelas 0 : Tidak sedang diacu, belum dimodifikasi (R=0, M=0)
Kelas 1 : Tidak sedang diacu, telah dimodifikasi (R=0, M=1)
Kelas 2 : Sedang diacu, belum dimodifikasi (R=1, M=0)
Kelas 3 : Sedang diacu, telah dimodifikasi (R=1, M=1)
Memilih mengganti page kelas bernomor terendah (bila terdapat page-page di kelas itu) secara acak.
Bila kelas tersebut kosong maka dipilih page di kelas lebih tinggi, dan seterusnya.
Algoritma ini mengasumsikan kelas-kelas bernomor lebih rendah akan baru akan digunakan kembali dalam waktu relatif lama.
Algoritma ini mudah dipahami dan diimplementasikan. Implementasi algoritma ini sangat efisien karena tak banyak langkah dalam pemilihan page. Algoritma ini memang tidak optimal, tapi dalam kondisi-kondisi normal telah memadai.
9.5.8 Algoritma Lainnya
Sebenarnya masih banyak algoritma ganti halaman yang lain selain 3 algoritma utama yang telah dibahas sebelumnya (utama bukan berarti paling sering dipakai). Berikut ini adalah 2 contoh algoritma lain yang juga cukup popular dan mudah diimplementasikan.
Algoritma yang pertama adalah algoritma second chance. Algoritma second chance berdasarkan pada algoritma FIFO yang disempurnakan. Algoritma ini menggunakan tambahan berupa reference bit yang nilainya 0 atau 1. Jika dalam FIFO menggunakan stack , maka second chance menggunakan circular queue . Halaman yang baru di-load atau baru digunakan akan diberikan nilai 1 pada reference bit-nya. Halaman yang reference bit-nya bernilai 1 tidak akan langsung diganti walaupun dia berada di antrian paling bawah (berbeda dengan FIFO).
Urutan langkah kerja algoritma second chance adalah sebagai berikut:
- Apabila terjadi page fault dan tidak ada frame yang kosong, maka akan dilakukan razia (pencarian korban) halaman yang reference bit-nya bernilai 0 dimulai dari bawah antrian (seperti FIFO).
- Setiap halaman yang tidak di- swap (karena reference bit-nya bernilai 1), setiap dilewati saat razia reference bit-nya akan diset menjadi 0.
- Apabila ditemukan halaman yang reference bit-nya bernilai 0, maka halaman itu yang di-swap.
- Apabila sampai di ujung antrian tidak ditemukan halaman yang reference bit-nya bernilai 0, maka razia dilakukan lagi dari awal.
Gambar 9.21. Algoritma Second Chance
Gambar 9.22. Algoritma FIFO
Algoritma kedua adalah algoritma random. Algoritma random adalah algoritma yang cukup sederhana juga selain algoritma FIFO. Dalam algoritma ini, halaman yang dipilih menjadi korban dipilih secara acak.
Meskipun terdengar asal, tetapi algoritma ini relatif low cost, karena tidak memerlukan stack, queue atau counter. Dibandingkan dengan FIFO, rata-rata kasus menunjukkan page fault rate algoritma random lebih rendah daripada algoritma FIFO. Sedangkan dibandingkan dengan LRU, algorima random ini lebih unggul dalam hal memory looping reference , karena algoritma random sama sekali tidak memerlukan looping.
Gambar 9.23. Algoritma Random
Rangkuman
Page fault terjadi apabila terdapat halaman yang ingin diakses tetapi halaman tersebut tidak terdapat di dalam memori utama.
Jika terjadi page fault dan tidak ada frame yang kosong, maka dipilih frame tumbal yang akan di-swap.
Pemilihan halaman dilakukan dengan algoritma ganti halaman. Algoritma dipilih yang paling rendah page fault rate-nya dan tidak sulit untuk diimplementasikan.
Contoh algoritma ganti halaman:
- Algoritma FIFO
- Algoritma Optimal
- Algoritma LRU
- Algoritma Second Chance
- Algoritma Random
[Silberschatz2002] Abraham Silberschatz, Peter Galvin, dan Greg Gagne. 2002. Applied Operating Systems. Sixth Edition. John Wiley & Sons.
[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons.
[Tanenbaum1997] Andrew S Tanenbaum dan Albert S Woodhull. 1997. Operating Systems Design and Implementation. Second Edition. Prentice-Hall.
[WEBAmirSch2000] YairTheo AmirSchlossnagle. 2000. Operating Systems 00.418: Memory Management – http://www.cs.jhu.edu/ ~yairamir/ cs418/ os5/ .
[WEBEgui2006] Equi4 Software. 2006. Memory Mapped Files – http://www.equi4.com/mkmmf.html .
[WEBFunkhouser2002] Thomas Funkhouser. 2002. Computer Science 217 Introduction to Programming Systems: Memory Paging – http://www.cs.princeton.edu/ courses/ archive / spring02/ cs217/ lectures/ paging.pdf .
[WEBGottlieb2000] Allan Gottlieb. 2000. Operating Systems: Page tables – http://allan.ultra.nyu.edu/ ~gottlieb/ courses/ 1999-00-spring/ os/ lecture-11.html .
[WEBSolomon2004] Marvin Solomon. 2004. CS 537 Introduction to Operating Systems: Lecture Notes Part 7 – http://www.cs.wisc.edu/ ~solomon/ cs537/ paging.html .
[WEBWiki2006c] From Wikipedia, the free encyclopedia. 2006. Memory Management Unit – http://en.wikipedia.org/ wiki/ Memory_management_unit .
[WEBWiki2006d] From Wikipedia, the free encyclopedia. 2006. Page Fault – http://en.wikipedia.org/ wiki/ Page_fault .
[WEBWiki2006e] From Wikipedia, the free encyclopedia. 2006. Copy on Write – http://en.wikipedia.org/ wiki/ Copy_on_Write .
[WEBWiki2007] Wikipedia. 2007. Page Replacement Algortihm http://en.wikipedia.org/wiki/Page_replacement_algorithm .
Kembali ke daftar isi
9.6 Alokasi Page Frame
9.6.1 Pendahuluan
Setiap proses perlu mendapat alokasi memori agar proses tersebut dapat dieksekusi dengan baik. Masalah selanjutnya adalah bagaimana caranya untuk mengalokasikan memori bagi setiap proses yang ada. Saat proses akan dieksekusi, terjadi page fault sehingga sistem akan menggantinya dengan halaman di memori. Untuk melakukan penggantian ini diperlukan bingkai yang terdapat di sistem. Proses dapat menggunakan setiap bingkai yang sedang bebas di sistem. Hal ini mengakibatkan perlu adanya pengaturan lebih lanjut agar tiap proses bisa mendapatkan bingkai yang cukup untuk melakukan penggantian ini.
9.6.2 Jumlah Bingkai
Hal yang perlu diperhatikan dalam strategi alokasi bingkai adalah berapa jumlah bingkai yang harus dialokasikan pada proses tersebut. Jumlah bingkai yang dialokasikan tidak boleh melebihi jumlah bingkai yang tersedia. Hal lain yang perlu diperhatikan adalah jumlah bingkai minimum yang harus dialokasikan agar instruksi dapat dijalankan, karena jika terjadi kesalahan halaman sebelum eksekusi selesai, maka instruksi tersebut harus diulang. Sehingga jumlah bingkai yang cukup harus tersedia untuk menampung semua halaman yang dibutuhkan oleh sebuah instruksi.
9.6.3 Strategi Alokasi Bingkai
Ada dua jenis algoritma yang biasa digunakan untuk pengalokasian bingkai, yaitu:
S = Si
m = jumlah total bingkai
ai = alokasi bingkai untuk Pi ((Si/S ) x m)
m = 64
S1 = 10
S2 = 127
a1 = (10/137) x 64 = 5 bingkai
a2 = (127/137) x 64 = 59 bingkai
Dalam pengalokasian bingkai, salah satu hal yang penting adalah penggantian halaman. Kita dapat mengklasifikasikan algoritma penggantian halaman ke dalam dua kategori:
Masalah pada algoritma penggantian global adalah proses tidak dapat mengontrol page fault rate proses itu sendiri. Keunggulan algoritma ini adalah menghasilkan system throughput yang lebih bagus, oleh karena itu algoritma ini lebih sering dipakai.
Rujukan
[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons.
[WEBAmirSch2000] Yair Amir dan Theo Schlossnagle. 2000. Operating Systems 00.418: Memory Management http://www.cs.jhu.edu/ ~yairamir/ cs418/ os5/ .
[WEBFunkhouser2002] Thomas Funkhouser. 2002. Computer Science 217 Introduction to Programming Systems: Memory Paging http://www.cs.princeton.edu/ courses/ archive / spring02/ cs217/ lectures/ paging.pdf .
[WEBGottlieb2000] Allan Gottlieb. 2000. Operating Systems: Page tables http://allan.ultra.nyu.edu/ ~gottlieb/ courses/ 1999-00-spring/ os/ lecture-11.html .
[WEBSolomon2004] Marvin Solomon. 2004. CS 537 Introduction to Operating Systems: Lecture Notes Part 7 http://www.cs.wisc.edu/ ~solomon/ cs537/ paging.html .
[WEBWiki2006f] From Wikipedia, the free encyclopedia. 2006. Page replacement algorithms http://en.wikipedia.org/ wiki/ Page_replacement_algorithms .
[FlynnMcHoes2006] Ida M. Flynn dan Ann Mclver McHoes. 2006. Understanding Operating Systems. Fourth Edition. Thomson Course Technology.
Kembali ke daftar isi
Materi Selajutnya bisa dilihat di http://outofthebox.students-blog.undip.ac.id/2010/09/27/so-chapter-9-virtual-memory/
9.6.1 Pendahuluan
Setiap proses perlu mendapat alokasi memori agar proses tersebut dapat dieksekusi dengan baik. Masalah selanjutnya adalah bagaimana caranya untuk mengalokasikan memori bagi setiap proses yang ada. Saat proses akan dieksekusi, terjadi page fault sehingga sistem akan menggantinya dengan halaman di memori. Untuk melakukan penggantian ini diperlukan bingkai yang terdapat di sistem. Proses dapat menggunakan setiap bingkai yang sedang bebas di sistem. Hal ini mengakibatkan perlu adanya pengaturan lebih lanjut agar tiap proses bisa mendapatkan bingkai yang cukup untuk melakukan penggantian ini.
9.6.2 Jumlah Bingkai
Hal yang perlu diperhatikan dalam strategi alokasi bingkai adalah berapa jumlah bingkai yang harus dialokasikan pada proses tersebut. Jumlah bingkai yang dialokasikan tidak boleh melebihi jumlah bingkai yang tersedia. Hal lain yang perlu diperhatikan adalah jumlah bingkai minimum yang harus dialokasikan agar instruksi dapat dijalankan, karena jika terjadi kesalahan halaman sebelum eksekusi selesai, maka instruksi tersebut harus diulang. Sehingga jumlah bingkai yang cukup harus tersedia untuk menampung semua halaman yang dibutuhkan oleh sebuah instruksi.
9.6.3 Strategi Alokasi Bingkai
Ada dua jenis algoritma yang biasa digunakan untuk pengalokasian bingkai, yaitu:
- Algoritma Fixed Allocation . Algoritma fixed allocation dibedakan menjadi dua macam yaitu equal allocation dan proportional allocation. Pada algoritma equal allocation jumlah bingkai yang diberikan pada setiap proses jumlahnya sama (m/n bingkai, m = jumlah bingkai, n = jumlah proses), misalnya: ada 5 buah proses dan 100 bingkai tersisa, maka tiap proses akan mendapatkan 20 bingkai. Algoritma ini kurang baik digunakan jika proses-proses yang ada besarnya berbeda-beda (proses yang besar diberikan bingkai yang sama dengan proses yang kecil), misalnya: ada 2 buah proses sebesar 10 K dan 127 K, ada 64 bingkai bebas. Jika kita memberikan bingkai yang sama yaitu sebesar 32 untuk tiap proses maka misalnya saja proses satu ternyata hanya memerlukan 10 bingkai, dan alhasil 22 bingkai pada proses pertama akan terbuang percuma. Untuk mengatasi masalah tersebut algoritma proportional allocation-lah yang cocok digunakan, yaitu pengalokasian bingkai disesuaikan dengan besarnya suatu proses, contoh:
S = Si
m = jumlah total bingkai
ai = alokasi bingkai untuk Pi ((Si/S ) x m)
m = 64
S1 = 10
S2 = 127
a1 = (10/137) x 64 = 5 bingkai
a2 = (127/137) x 64 = 59 bingkai
- Algoritma Priority Allocation . Algoritma priority allocation merupakan algoritma pengalokasian dengan memberikan jumlah bingkai sesuai dengan prioritas proses tersebut. Pendekatannya mirip dengan proportional allocation, perbandingan frame-nya tidak tergantung ukuran relatif dari proses, melainkan lebih pada prioritas proses atau kombinasi ukuran dan prioritas. Jika suatu proses mengalami page fault maka proses tersebut akan menggantinya dengan salah satu frame yang dimiliki proses tersebut atau menggantinya dengan frame dari proses yang prioritasnya lebih rendah. Dengan kedua algoritma di atas, tetap saja alokasi untuk tiap proses bisa bervariasi berdasarkan derajat multiprogrammingnya. Jika multiprogrammingnya meningkat maka setiap proses akan kehilangan beberapa frame yang akan digunakan untuk menyediakan memori untuk proses lain. Sedangkan jika derajat multiprogramming-nya menurun, frame yang sudah dialokasikan bisa disebar ke proses-proses lainnya.
Dalam pengalokasian bingkai, salah satu hal yang penting adalah penggantian halaman. Kita dapat mengklasifikasikan algoritma penggantian halaman ke dalam dua kategori:
- Penggantian Global. Penggantian secara global memperbolehkan suatu proses mencari bingkai pengganti dari semua bingkai yang ada, meskipun bingkai tersebut sedang dialokasikan untuk proses lain. Hal ini memang efisien, tetapi ada kemungkinan proses lain tidak mendapatkan bingkai karena bingkainya terambil oleh proses lain.
- Penggantian Lokal. Penggantian lokal hanya mengijinkan proses untuk mencari bingkai pengganti dari bingkai-bingkai yang memang dialokasikan untuk proses tersebut.
Masalah pada algoritma penggantian global adalah proses tidak dapat mengontrol page fault rate proses itu sendiri. Keunggulan algoritma ini adalah menghasilkan system throughput yang lebih bagus, oleh karena itu algoritma ini lebih sering dipakai.
Rujukan
[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons.
[WEBAmirSch2000] Yair Amir dan Theo Schlossnagle. 2000. Operating Systems 00.418: Memory Management http://www.cs.jhu.edu/ ~yairamir/ cs418/ os5/ .
[WEBFunkhouser2002] Thomas Funkhouser. 2002. Computer Science 217 Introduction to Programming Systems: Memory Paging http://www.cs.princeton.edu/ courses/ archive / spring02/ cs217/ lectures/ paging.pdf .
[WEBGottlieb2000] Allan Gottlieb. 2000. Operating Systems: Page tables http://allan.ultra.nyu.edu/ ~gottlieb/ courses/ 1999-00-spring/ os/ lecture-11.html .
[WEBSolomon2004] Marvin Solomon. 2004. CS 537 Introduction to Operating Systems: Lecture Notes Part 7 http://www.cs.wisc.edu/ ~solomon/ cs537/ paging.html .
[WEBWiki2006f] From Wikipedia, the free encyclopedia. 2006. Page replacement algorithms http://en.wikipedia.org/ wiki/ Page_replacement_algorithms .
[FlynnMcHoes2006] Ida M. Flynn dan Ann Mclver McHoes. 2006. Understanding Operating Systems. Fourth Edition. Thomson Course Technology.
Kembali ke daftar isi
Materi Selajutnya bisa dilihat di http://outofthebox.students-blog.undip.ac.id/2010/09/27/so-chapter-9-virtual-memory/
Tidak ada komentar:
Posting Komentar