SISTEM PAGING

SISTEM PAGING

Sistem Paging Adalah sistem manajemen pada sistem operasi dalam mengatur program yang sedang berjalan. Program yang berjalan harus dimuat di memori utama. Kendala yang terjadi apabila suatu program lebih besar dibandingkan dengan memori utama yang tersedia.

Untuk mengatasi hal tersebut Sistem Paging mempunyai 2 solusi, yaitu:

·         Konsep Overlay

Dimana program yang dijalankan dipecah menjadi beberapa bagian yang dapat dimuat memori (overlay). Overlay yang belum diperlukan pada saat program berjalan (tidak sedang di eksekusi) disimpan di disk, dimana nantinya overlay tersebut akan dimuat ke memori begitu diperlukan dalam eksekusinya.

·         Konsep Memori Maya (virtual Memory)

Adalah kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Konsep ini pertama kali dikemukakan Fotheringham pada tahun 1961 untuk sistem komputer Atlas di Universitas Manchester, Inggris.

Gagasan Memori Maya adalah ukuran gabungan program, data dan stack melampaui jumlah memori fisik yang tersedia. Sistem operasi menyimpan bagian-bagian proses yang sedang digunakan di memori utama dan sisanya di disk. Begitu bagian di disk diperlukan maka bagian memori yang tidak diperlukan disingkirkan dan diganti bagian disk yang diperlukan.

Pengertian Memori Maya

Didalam menejemen memori dengan system partisi statis dan system dinamis sudah dapat menyelesaikan masalah menejemen memori didalam banyak hal, tetapi masih memiliki kekurangan atau keterbatasan di dalam pengakses. Dimana keterbatasan akses hanya sebatas addres memori yang ada secara fisik ( memori nyata ).

Misalnya memori 64 MB maka addres maksimum yang dapat diakses hanya sebesar 64 MB saja. Pada hal banyak program yang akan diakses yang melebihi 64 MB. Untuk mengatasi hal tersebut agar kemampuan akses lebih besar lagi maka dibentuklah memori maya ( yang pertama sekali di kemukakan oleh Fotheringham pada tahun 1961 untuk system komputer Atlas di Universitas Manchester, Inggris).

Dengan memori maya program yang besar tadi akan dapat diterapkan pada memori kecil saja, misalnya program 500 MB dapat ditempatkan secara maya di memori 64 MB. Untuk mengimplementasikan memori maya tersebut dapat dilakukan dengan tiga cara :

1.      Memori system Paging

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

·                   Pemetaan Memori Sistem Paging

Sistem kinerja komputer akan menerjemahkan alamat maya menjadi alamat fisik. Dengan kata lain dalam system memori maya alamat memori tidak langsung di tuliskan ke BUS tetapi terlebih dahulu dimasukkan ke MMU untuk diterjemahkan. Ada dua kemungkinan keluaran MMU yaitu :

1. Alamat yang dicari ada dimemori nyata, maka proses dapat langsung dikerjakan.

2. Alamat yang dicari tidak ada didalam memori nyata, maka MMU mengeluarkan page fault, yaitu permintaan alokasi memori untuk proses itu.

MMU mempunyai fungsi untuk memetakan memori maya ke memori fisik. Apabila alamat memori yang dipetakan tidak tersedia di memori fisik, MMU menertibkan exception page fault yang melewatkan ke system operasi untuk menengani.

Implementasi Pemetaan Memori sistem paging

Apabila exception page fault meminta alokasi memori akan ditangani oleh system operasi yaitu memilih partisi yang telah selesai diakses dan kemungkinan proses ini akan digunakan lagi, dalam waktu yang lama lagi. Jika sudah dipilih maka program akan dikosongkan dari memori dan selanjutnya program yang alamatnya yang diminta akan dimasukkan ke memori.

·         Proses Pemetaan Pada MMU

Dibawah ini adalah suatu proses pemetaaan memori yang terjadi pada MMU. Alamat maya terdiri dari bagian nomor page dan offset. Alamat ini dicarikan didalam tabel page, bila ketemu maka MMU mengeluarkan page frame (register alamat fisik). Register alamat fisik terdiri darei nomor page dan offset, dimana nomor page frame lebih sedikit dari nomor page.

Apabila alamat tersebut tidak ada pada tabel page maka MMU mengeluarkan page fault.

2.      Sistem Segmentasi

·         Pengertian Segmentasi

Secara sederhana segmentasi bisa diartikan sebagai suatu ruang alamat atau segment yang berada di memori. Segment-segment itu dalam keadaan independent. Setiap segment berisi alamat 0 sampai maksimum secara linier. Panjang setiap segment berbeda-beda sampai panjang maksimun, perobahan panjang segment terjadi selama proses eksekusi.

Segment stack bertambah ketika terjadi operasi push dan turun saat operasi pop, dimana setiap segment merupakan ruang alamat terpisah segment-segment dapat tumbuh dan mengkerut secara bebas tanpa mempengaruhi yang lain.

Alamat terdiri dari dua bagian pada memori bersegment yaitu :

1.      Nomor segment

2.      Alamat pada segment ( offset ).

Segment dapat berisi :

1.      Prosedure

2.      Array

3.      Stack

4.      Kumpulan variable skala.

·         Sistem Segmentasi

Sistem dengan memori maya dengan segmentasi murni adalah alamat maya adalah offset di segment, setiap proses mempunyai tabel segment dan pada saat proses running alamat awal maya tabel dimuatkan ke register dasar. Nomor segment digunakan mencari deskriptor segment di tabel segment yang menyediakan alamat fisik awal dari segment, panjang dan bit-bit proteksinya. Alamat fisik dihitung dengan menambahkan alamat dasar segment ke alamat maya.

Skema Segmentasi

Keunggulan sistem ini dimana segment-segment tersebut saling berhubungan dengan unit-unit program, sehingga segment – segment indeal untuk proteksi dan pemakaian bersama.

Kelemahan sistem ini adalah dimana segment – segment berukuran bervariasi menyebabkan fragmentasi eksternal dan sulit menyelesaikan pertumbuhan dinamis. Segment-segment tidak memetakan blok-blok disk untuk memori maya secara alami.

3.      Teknik Kombinasi Paging Dan Segmentasi

Teknik kombinasi pacing dan segmentasi adalah ruang alamat pemakai dibagi menjadi sejumlah segment sesuai dengan kehendak pemrogram. Segment tersebut dibagi menjadi sejumlah page berukuran tetap dan berukuran sama dengan page frame memori utama. Jika segment kurang dari ukuran page, maka segnent hanya memerlukan satu page.

Dari segi pandangan pemrogram, alamat maya masih berisi nomor segment dan offset di segment itu. Dari segi pandangan sistem, offset segment dipandang sebagai nomor page dan offset page untuk page di segment yang dispesifiksikan. Penggabungan dengan proses adalah tabel segment dan sejumlah tabel page, merupakan satu tabel persegment proses.

Saat proses running, register menyimpan alamat awal tabel segment untuk proses, pemroses menggunakan bagian nomor segment untuk mengindeks tabel segment proses guna menemukan tabel page untuk segment. Bagian angka page alamat maya digunakan untuk indeks tabel page dan mencari nomor page korespondensi. Angka tersebut kemudian dikombinasikan dengan bagian offset alamat maya untuk menghasilkan alamat nyata yang diinginkan.

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:

1. Proses meminta halaman tertentu.
2. Jika halaman berada di memori, tidak dilakukan ganti halaman.
3. Jika halaman tidak berada di memori, maka:
1. Jika ada frame kosong, maka halaman itu di-load ke dalam frame yang kosong tersebut.
2. Jika tidak ada frame yang kosong, maka pilih halaman yang akan di-swap dengan menggunakan algoritma ganti halaman.
4. Update tabel halaman dan table memori.
5. Restart proses.

ilustrasi Swapping

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.

Pada umumnya, semakin besar memori, semakin banyak pula jumlah frame-nya. Semakin banyak frame, semakin banyak pula jumlah halaman yang bisa masuk di memori, sehingga page fault rate menurun.

ALGORITMA PENGGANTIAN PAGE

Saat terjaid page fault berarti harus diputuskan page frame di memori fisik yang harus diganti. Kinerja sistem akan baik jika page yang diganti dipilih yang tidak akan digunakan di masa datang. Jika page yang diganti akan kembali digunakan, maka page akan dikembalikan secepatnya yang berarti terjadi page fault berulang kali. Banyaknya page fault menghasilkan banayk overhead.

 

1        Algoritma penggantian page acak

Mekanisme algoritma :

Setiap terjadi page fault, page yang di ganti di pilih secara acak.

Teknik ini tidak memakai informasi apapun dalam menentukan page yang di ganti,semua page di memori utama mempunyai bobot sama untuk di pilih.teknik ini memiliki sembarang page,termasuk page yang sedang di acu,teknik ini sangat buruk,percobaan menunjukkan algoritma acak menimbulkan rate terjadinya page fault yang sangat tinggi.

2        Algoritma pengganti page optimal

Mekanisme algoritma

Dasar Algoritma ini adalah memiliki page yang berpeluang di pakai kembali di masa datang yang paling kecil.

Pendekatan ini dapat dilakukan dengan simulasi,tapi hanya spesifik suatu program.bila yang terbaik tidak di mungkinkan,maka yang perlu di lakukan adalah berusaha mendekatinya.algoritma pengganti page mengumpulkan dan memakai informasi untuk menentukan page yang di ganti sehingga mendekati optimal.

Algoritma pengganti page optimal penting untuk kajian teoretis,sebagai pembanding bagi algoritma-algoritma yang lain.

Ilustrasi gambar :

3        Algoritma pengganti page NRU

Mekanisme algoritma

Pada algoritma ini,page di beri dua bit mencatat setatus page,bit R dan M, yaitu:

Bit R         : referenced(menyatakan page sedang di acu)

Bit R         = 1 berati sedang di acu

= 0 berati tidak sedang di acu

Bit M         : modified (menyatakan page telah di modifikasi)

Bit M         = 1 berati di modifikasi

= 0 berati tidak di modifikasi

Dengan 2 bit,maka page-page di kelompokan menjadi 4 kelas page yaitu:

Kelas 0      : tidak sedang di acu,belum di modifikasi (R=0,M=0)

Kelas 1      : tidak sedang di acu,telah di modifikasi (R=0,M=1)

Kelas 2      : sedang di acu,belum di modifikasi (R=1,M=0)

Kelas 3      : sedang di acu,telah di modifikasi (R=1,M=1)

1.      Memilih mengganti page kelas bernomor terendah secara acak

2.      Bila kelas tersebut kosong maka di pilih page di kelas yang lebih tingggi,dan seterusnya.

4        Algoritma pengganti page FIFO

Mekanisme algoritma

Algoritma ini memerlukan pengelolaan senari page di memeori,elemen terdepan senari adalah page tertua dan ujung belakang adalah page paling akhir datang. 

Bila terjadi page fault,page elemen terdepan(page tertua) di ganti dan page baru di tambahkan di ujung belakang senari.Algoritma FIFO murni jarang digunakan,tetapi di kombinasikan (modif)

Ilustrasi gambar :

5        Algoritma penggantian Modifikasi dari FIFO

Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering di gunakan yang lama berada di memeori.kemungkinan ini dapat di hindari dengan hanya memindahkan page tidak di acu.page di tambah bit R mencatat apakah page di acu atau tidak,bit R bernilai 1 bila di acu dan bernilai 0 bila tidak di acu.

Variasi dari FIFO antara lain :

1.      Algoritma Penggantian page kesempatan kedua

Mekanisme algoritma

Saat terjadi page fault,algoritma memilih page elemen terdepan di ganti bila bit R bernilai 0

2.      Algoritma penggantian clock page

Bila bit R berniali 1 ,maka bit page terdepan senarai diseret menjadi 0 dan di letekan di ujung belakang senarai.mekanisme ini kembali di terapkan ke elemen erikutnya.

6        Algoritma penggantian page LRU

Mekanisme algoritma

Algoritma LRU adalah ketika terjadi page fault maka memindahkan page yang tidak di gunakan paling lama.

Masalah

Sangat mahal

Kemahalan disebabkan harus mengelola senarai informasi seluruh page di memori.senarai harus terurut berdasarkan kemutkhiran penggunaan.senarai harus di perbaharui setiap terjadi pengacuan memori.begitu terjadi pengacuan memori,harus di lakukan operasi menemukan page di senarai.di pindahkan sebagai terdepan yaitu paling akhir di acu.

Ilustrasi gambar :

MASALAH UTAMA PADA SYSTEM PAGING:

1        Working Set Model

Prinsip Lokalitas

Terdapat 2 jenis jenis lokalitas:

1.      Lokalitas berdasarkan waktu (temporal locality), proses cenderung terkonsentrasi acuannya ke satu intercal waktu eksekusi yang dekat.  Observasi berikut mendukung prinsip, antara lain : Looping, Subrutin, stack dan variable-variabel yang digunakan untuk iterasi dan penjumlahan total.

2.      Lokalitas berdasarkan ruang (spatial locality), proses cenderung terkonsentrasi acuannya ke satu kelompok data yang berdekatan. Observasi berikut mendukung prinsip ini, antara lain: traversal pada array, eksekusi kode yang sekuen, kecenderungan pemrogram menempatan variable yang terkait saling berdekatan.

Prinsip lokalitas diperoleh dari observasi bukan dari kajian teoritis. Menunjukkan kecenderungan prilaku lingkungan system bukan tepat eksak.

Konsekuensi prinsip lokalitas adalah program dapat berjalan secara efisien saat satu subset page berkecenderungan tinggi saling mengacu terdapat di memory.

Thrashing: peristiwa page fault yang sangat berlebihan.

Salah satu cara menghindari thrashing adalah dengan menyediakan sebanyak mungkin bingkai sesuai dengan kebutuhan proses. Untuk mengetahui berapa bingkai yang dibutuhkan adalah dengan strategi working set. Strategi ini dimulai dengan melihat berapa banyak bingkai yang digunakan oleh suatu proses. Working set model mengatakan bahwa sistem hanya akan berjalan secara efisien jika proses diberikan bingkai yang cukup, jika bingkai tidak cukup untuk menampung semua proses maka suatu proses akan ditunda, dan memberikan halamannya untuk proses yang lain.

Working set model merupakan model lokalitas dari eksekusi proses. Model ini menggunakan parameter (delta) untuk definisi working set window. Kumpulan dari halaman dengan halaman yang dituju yang paling sering muncul disebut working set.

Berdasarkan hal ini terdapat dua teknik untuk memuatkan page, yaitu:

·         Prepaging, teknik memuatkan page-page lebih dulu sbelum proses berjalan.

·         Demand paging, teknik yang segera memuatkan page begitu page dibutuhkan.

Keakuratan Working set tergantung pada pemilihan :

1.      jika terlalu kecil tidak akan mewakilkan seluruh lokalitas.

2.      jika terlalu besar menyebabkan overlap.

3.      jika tidak terbatas working set adalah kumpulan halaman sepanjang eksekusi program.

Jika total permintaan > total bingkai, maka akan terjadi thrashing. Jika ini terjadi maka proses yang sedang berjalan akan diblok.

2        Kebijaksanaan Penggantian Local Vs Global

Terdapat dua pendekatan untuk mengganti page, yaitu:

·         Penggantian local 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 mempedulikan partisi proses. Dengan penggantian global, page fault suatu proses dapat dilayani dengan memindahkan page yang dimiliki proses lain.

3        Frekuensi Page Fault

Frekuensi terjadinya page fault dapat dikendalikan dengan algoritma PFF (page fault frequency algorithm). Dengan PFF harus didefinisikan ambang batas dan ambang bawah frekuensi page fault. Bila proses melampaui ambang batas frekuensi page fault maka dialokasikan lebih banyak page memory fisik untuk prose situ. Apabila proses telah mancapai amabang bawah frekuensi page fault maka alokasi page dihentikan.

4        Ukuran Page

Ukuran page ditentukan oleh perancang system operasi.. ukuran page harus ditentukan agar system berperilaku optimal.  Beberapa pertimbangan, antara lain:

·         Ukuran page lebih kecil berarti jumlah page dan page frame lebih banyak sehingga memerlukan table page lebih besar.

·         Ukuran page besar, berarti sejumlah informasi yang tidak diacu juga dimasukkan ke memory utama sehingga terjadi fragmentasi internal yang tinggi.

·         Transfer masukan/ keluaran relative sangat mengkonsumsi waktu sehingga perlu meminimumkan  Transfer masukan/ keluaran saat program berjalan.

·         Program cenderung mengikuti prinsip lokalitas yang cenderun berukuran kecil.

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).

Perlu diingat bahwa status (register, condition code, counter insruksi) dari proses yang diinterupsi ketika terjadi page fault akan disimpan sehingga proses dapat diulang kembali di tempat dan status yang sama, kecuali jika halaman yang diinginkan sekarang telah berada di memori dan dapat diakses.

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

Langkah-Langkah dalam Menangani Page Fault

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 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.

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

-  restart proses (1-100 microseconds)