Sistem Paging dan Algoritma Paging

I. SISTEM PAGING

A.  DEFINISI SISTEM PAGING

Sistem Paging Adalah sistem manajemen pada sistem operasi dalam mengatur program yang sedang berjalan. Program yang dijalankan harus dimuat di memori utama. Masalah muncul ketika program lebih besar dibanding di memori utama yang tersedia. Terdapat dua solusi masalah ini,yaitu :

1.      Overlay

Overlay adalah program dipecah menjadi bagian-bagian yang dapat dimuat di memori. Overlay yang belum diperlukan (tidak sedang dieksekusi) disimpan di disk, overlay ini dimuatkan ke memori begitu diperlukan (kode overlay akan dieksekusi).

2.      Memori Maya (Virtual Memory)

Memori maya adalah kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Memori maya dapat dilakukan pada sistem multiprogramming.

B. HAL-HAL YANG BERKAITAN DENGAN SISTEM PAGING

Istilah-istilah pada Sistem Paging :

1.      Alamat Maya (Virtual Address)

Adalah alamat yang dihasilkan perhitungan menggunakan index register, base register,segment regoster dan sebagainya.

2.      Alamat nyata (real Address)

Alamat maya adalah alamat utama di memori fisik.

3.      Page

Page adalah unit terkecil virtual address space

4.      page frame

Page frame adalah unit terkecil memori fiisk. Memori fisik secara konseptual dibagi menjadi sejumlah unit berukuran tetap disebut page frame. Page frame sering juga disingkat frame.

5.      Page fault

Page fault adalah exception untuk permintaan alokasi page ke memori. Dalam konteks memori maya, page fault sering juga disingkat fault.

6.      MMU (Memory Management Unit)

MMU berfungsi :

·         Pemetaan memori maya ke memori fisik

·         Bila alamat memori yang diminta tidak tersedia di memori fisik, MMU menerbitkan exception adanya page fault yang melewatkan ke sistem operasi untuk menanganinya.

Untuk menginplementasikan addres maya yang besar ke dalam memori yang kecil diperlukan index register, base register, segment register dan MMU ( Memory Menegement Unit ).

C.MASALAH YANG TERJADI PADA PAGING

a. Masalah Utama Sistem Paging

 1.  Working Set Model

·         Prinsip Lokalitas

Prinsip Lokalitas adalah proses-proses cenderung mengacu penyimpan secara tak seragam, mempunyai pola-pola sangat setempat.

·         Working set of Program Behavior

Himpunan kerja secara informal didefinisikan sebagai kumpulan page proses yang secara aktif diacu. Denning menyatakan bahwa agar suatu program berjalan secara efisien, himpunan kerja harus dijaga berada di memori utama. Selain itu akan terjadi aktivitas page fault yang berlebihan. Peristiwa page fault yang sangat berlebihan disebut trashing, yaitu setelah hanay beberapa intruksi terjadi page fault.

Prinsip yang digunakan oleh Working Set Model ini adalah dengan melacak dan menjamin himpunan kerja terdapat di memori sebelum proses dijalankan. Cara ini mengurangi terjadinya page fault.

    2.  Kebijaksanaan penggantian lokal vs global

Terdapat dua pendekatan untuk mengganti page, yaitu :

·         Penggantian lokal adalah page yang dipilih untuk diganti hanya pada partisi dimana proses diletakkan.

·         Penggantian global adalah page yang dipilih untuk diganti adalah tempat kosong dengan tidak memperdulikan partisi proses.

3.   Frekuensi page fault

Frekuensi terjadinya page fault dapat dikendalikan dengan algoritma PFF (Pafe Fault Frequency Algorithm).

4.      Ukuran page

Ukuran page ditentukan perancang sistem operasi. Ukuran page harus ditentukan agar sistem berperilaku opimal. Penentuan ukuran page memerlukan penilaian dan pemahaman mendalam perangkat keras, perangkat lunak dan aplikasi sistem.

b. Masalah Implementasi Sistem Paging

1.Back-up Intruksi

Bila terjadi page fault berarti sebgaian intruksi telah dijalankan. Pengkopina program counter dan informasi register-register pemroses harus dilakukan. Setelah pergantian page selesai maka intruksi yang menyebabkan page fault dapat dijalankan kembali dengan konteksnya.

Masalah yang harus diatasi adalah untuk mengulangi intruksi, sistem harus menetukan byte pertama intruksi.

 2. Buffer Perangkat Masukan / Keluaran (Penguncian Page)

Pergantian page akan menimbulkan masalah mengacaukan proses yang melakukan operasi masukan / keluaran jika :

·         Buffer perangkat masukan / keluaran ikut tergusur

·         Adanya buffer satu perangkat masukan / keluaran menjaid rangkap.

3.Pemakaian Page Bersama

Apabila beberapa pemakai menggunakan program yang sama maka terjadi perngakapan page (page yang sam aterdapat di banyak bagian di memori). Lebih efisien menggunakan page secara bersama, menghindari keharusan mempunyai copyan-copyan page yang sama di saat yang sama.

4.Backing Store
Masalah lain adalah menyangkut dimana diletakkan page yang keluar dari memori utama. Terdapat dua algoritma untuk mengatasi hal ini, yaitu :

·         Menggunakan ruang ganti khusus

·         Dialokasikan berdasarkan kebutuhan

5.Paging Daemon
Paging bekerja bagus saat terdapat banyak page frame bebas yang dapat diklaim begitu page fault terjadi. Jika setiap page frame penuh dan telah dimodifikasi, sebelum page baru dimasukkan, pag eharus ditulis terlebih dahulu ke disk.

Untuk menjamin pasokan (supply) page frame yang banyak, sistem paging biasanya mempunyai proses background, disebut Paging Daemon.

6.Penanganan Page Fault (Page Fault Handling)
Implementasi sistem paging harus mengatasi rincian aksi yang harus dilakukan saat terjadi page fault.

 II. ALGORITMA SISTEM PAGING

1. Pengertian tentang Algortima Pengganti Page Acak

Dari segi mekanisme algoritma tersebut, setiap akan timbul page fault, page yang diganti dengan pilihan secara acak. Untuk segi tekniknya sendiri pun algoritma ini tidak usah perlu menggunakan informasi dalam menentukan page yang diganti, didalam memory utama itu sendiri sudah mempunyai bobot yang sama untuk dipilih, karena teknik ini dapat dipakai untuk memilih page sembarang. Termasuk page yang sudah dipilih dengan benar-benar  / page yang tidak seharusnya diganti.

Contoh gambar dari Algoritma page acak

2. Pengertian tentang Algoritma Pengganti Page Optimal

Pengertian dari algoritma ini sendiri yaitu algoritma yang page nya paling optimal. Untuk prinsip dari algoritma ini sangat efisien sekali karena hanya mengganti halaman yang sudah tidak terpakai lagi dalam jangka waktu lama sehingga page fault yang terjadi akan berkurang dan terbebas dari anomali Belady  Selain itu juga page fault dari algoritma ini memiliki rate paling tinggi dari algoritma lainnya dari semua kasus, akan tetapi tidak belum bias disebut sempurna karena sulit untuk di mengerti dan dari segi system pun belum tentu bisa mengetahui page untuk berikutnya tetapi dapat di simulasikan hanya untuk suatu program. Untuk intinya gunakanlah hingga mendekati page optimal agar bisa memanfaatkannya.

 

Contoh gambar dari Algoritma page optimal

3. Pengertian tentang Algoritma Page NRU (Not-Recently Used)

Untuk mekanisme dari algoritma ini diberi dua bit untuk mencatat status page, diantaranya bit M dan R yaitu :

Bit M : Page yang telah dimodifikasi
Bit M = 0 berarti tidak dimodif
Bit M = 1 berarti sudah dimodif

Bit R : Page yang sedang dipacu / referenced
Bit R = 1 berarti sedang di acu
Bit R = 0 berarti tidak sedang di acu

Adanya dua bit di atas maka akan dapat dikelompokkan menjadi 4 kelas page, yaitu :
Kelas 0 => Tidak sedang di acu / belum di modif (R=0, M=0)
Kelas 1 => Tidak sedang di acu / telah di modif (R=0, M=1)
Kelas 2 => Sedang di acu / belum di modif (R=1, M=0)
Kelas 3 => Sedang di acu / telah di modif (R=1, M=1)

Jadi apabali algoritma ini diasumsikan kelas-kelas bernomor lebih rendah baru akan di gunakan kembali dalam relatif jangka waktu lama.
Intinya algoritma ini mudah dipahami dan dikembangkan karena sangat efisien walaupun tak banyak langkah dalam pemilihan page dan kelemahannya juga tidak optimal tapi dalam kondisi normal yang memadai.

4. Pengertian tentang Algoritma page FIFO (First In First Out)

Inti dari algoritma ini adalah simple / paling sederhana karena prinsipnya sama seperti prinsip antrian tak berprioritas. Page yang masuk terlebih dahulu maka yaitu yang akan keluar duluan juga. Untuk algoritma ini menggunakan structure data stack. Jadi kerjanya yaitu dimana kalau tidak ada frame yang kosong saat terjadi page fault maka korban yang dipilih adalah frame dengan stack paling bawah seperti hal nya halaman yang sudah lama tersimpan didalam memory maka dari itu algoritma ini juga bisa memindahkan page yang sering digunakan.

 

Contoh gambar dari Algoritma page FIFO

Utamanya algoritma ini di anggap cukup mengatasi pergantian page sampai pada tahun 70-an, pada saat itu juga Belady menemukan keganjalan pada algoritma ini dan dikenal dengan anomali Belady. Anomali Belady itu sendiri ialah keadaan dimana page fault rate meningkat seiring dengan pertambahannya jumlah frame.

 

Contoh gambar dari Anomali Belady

5. Pengertian tentang Algoritma page Modifikasi FIFO

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)

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.

                              

Contoh gambar dari Algoritma page Modifikasi FIFO

6. Pengertian tentang Algoritma page 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. ama 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.

Contoh gambar dari Algoritma page LRU

TERIMAKASIH