SISTEM PAGGING (MASALAH PERGANTIAN PAGE) DAN SEGMENTASI

SISTEM PAGING

Disusun oleh:

PUJI RUSIANA-KA D3-12.2.00013

NIKEN HERGARISTI-KA D3-12.2.00010

ANA RIZKY P/KA DIII-12.2.00003

NOVIANA  ERNIS S/KA DIII-12.2.00012

Sistem Paging merupakan 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, ada 2 solusi untuk menyelesaikannya, yaitu :

1. Konsep Overlay

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

2. Konsep Memori Maya

Yaitu kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. 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. Jika bagian di disk diperlukan maka bagian dimemori yang tidak diperlukan disingkirkan diganti bagian di disk yang diperlukan itu.

(Buku SISTEM OPERASI – BAMBANG HARIYANTO, Ir halaman 173-174)

Beberapa istilah pada sistem paging :

1. Alamat Maya (Virtual Address)

Alamat yang dihasilkan dengan perhitungan menggunakan index register, base register, segment register dsb. Jumlah alamat pada V disimbolkan dengan |V|.

2. Alamat Nyata (Real Address)

Alamat yang tersedia di memori utama fisik. Jmlah alamat pada R disimbolkan dengan|R|. Ada implementasi sistem memori maya, normalnya |V|>>|R|.

3. Page

Unit terkecil virtual address space.

4. Page Frame

Unit terkecil memori fisik. Page Frame disebut jugan dengan Frame.

5. Page Fault

Excption untuk permintaan alokasi ‘page’ ke memori.

6. Memory Management Unit (MMU)

Chip atau kumpulan yang memetakkan alamat maya ke alamat fisik.

·         Pada komputer tanpa memori maya, almat langung diletakkan ke bus dan menyebabkan word memori fisik alamatitu dibaca atau ditulis. 
·         Pada komputer dengan memori maya, alamat tidak diletakkan ke bus secara langsung, tapi lewat MMU yang kemudian memetakkan alamat maya ke alamat memori fisik.

(Buku Sistem Operasi – Bambang Hariyanto hal 175-176)

(PUJI RUSIANA-KA D3-12.2.00013)

PENGGANTIAN PAGE

Algoritma Penggantian Page antara lain :
1. Algoritma Peggantian Page Acak
Teknik ini tidak memakai informasi apapun dalam menentukan page yang diganti. Semua page dimemori utama mempunyai bobot sama untuk dipilih. Teknik ini dapat memilih sembarang page, termasuk page yang sedang diacu (page yang seharusnya tidak diganti, pilihan terburuk).

2. Algoritma Penggantian Page Optimal

Dasar algoritma ini adalah memilih page yang berpeluang dipakai kembali dimasa datang paling kecil. Strategi ini akan menghasilkan jumlah page fault paling sedikit. Algoritma ini merupakan algoritma utopia (ideal tanpa dapat dijadikan kenyataan) karna tak mungkin dibuat prosedur yang dapat mengetahui pemakaian suatu page kembali dimasa datang

3. Algoritma Penggantian Page NRU (Not Recently Used)

Pada algoritma ini, page diberi 2 bit mencatat status page, R dan M.Algoritma ini mengasumsikan kelas-kelas bernomor lebih rendah akan baru akan digunakan kembali dalam waktu relatif lama.

4. Algoritma Penggantian Page FIFO

Algoritma ini memerlukan pengelolaan senarai page di memori.

MODIFIKASI TERHADAP FIFO

Variasi dari FIFO adalah :

·         Algoritma Penggantian Page Kesempatan Kedua

Mekanisme Algoritma :

- Saat terjadi page fault, algoritma dapat 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

·         Algoritma Penggantian Page Clock

Algoritma ini merupakan perbaikan algoritma pertama.

Mekanisme Algoritma :

- Semua page merupakan senarai melingkar membentuk pola jam. Terdapat penunjuk (pointer) ke page tertua. Ketika terjadi Page fault, page yang ditunjuk diiperiksa.

- Jika bit R bernilaii 0, maka page diganti. Page baru ditempatkan ditempat page diganti, dan penunjuk dimajukan satu posisi ke page berikutnya.

·         Algoritma Penggantian Page LRU (Least Recently Used)

Mekanisme algoritma :                                      

Ketika terjadi page fault maka memindahkan page yang tak digunakan paling lama.

(Buku Sistem Operasi – Bambang Hariyanto Ir halaman 181-185)

PEMODELAN ALGORITMA PAGING
Tampaknya beralasan bila dinyatakan bahwa bila lebih banyak page yang dialokasikan untuk proses, maka page fault yang terjadi akan lebih sedikit. Belady menemukan pada algoritma FIFO, bahwa pada pola-pola pengacuan tertentu menyebabkan lebih banyak page fault bila alokasi page untuk proses ditambah. Fenomenanya disebut Anomali Belady.
Fenomena dapat diilustrasikan yaitu :

·         Program dengan lima page 
·         Urutan page yang diacu adalah 0 1 2 3 4 0 1 4 0 1 2 3 4

MESIN ABSTRAKSI EKSEKUSI PROGRAM

Terdapat mesin abstrak interpreter dengan properti berikut:

1. Terdapat arrayinternal, M, menyimpan status memori. Array mempunyai n elemen seperti proses mempunyai npage memori maya.

2. Array M terbagi dua, yaitu:

1.       Bagian atas/puncak, yaitu m isian, page di memori utama.

2.       Bagian bawah/dasar berisi n-m isian, yaitu semua page yang pernah diacu sekali tapi telah dipindahkan dan tidak di memori utama.

3. Mulanya arrayM berupa himpunan kosong karena belum ada page yang telah diacu dan tak ada page yang berada di memori.

Begitu eksekusi dimulai, proses mulai mengeluarkan page sesuai stringpengacuan, satu page pada satu saat. Terhadap page itu, interpreter memeriksa apakah page berada di memori (yaitu merupakan isian bagian puncak array M). Jika page tidak ada di memori, dan jika terdapat slot kosong di memori (yaitu bagian puncak kurang dari m), maka page dimuat dan dimasukkan ke puncak M. Situasi ini hanya muncul di awal eksekusi. Jika memori telah penuh (yaitu bagian array M telah terisi m), algoritma penggantian dijalankan untuk mengganti page dari memori utama. Pada model ini, maka satu pagepindah dari bagian puncak ke bagian dasar, serta page yang diperlukan dimasukkan ke puncak.

(NIKEN HERGARISTI-KA D3-12.2.00010)

Masalah-masalah Utama pada Sistem Paging

Masalah-masalah Utama pada Sistem Paging adalah working setmodel, kebijaksanaan penggantian lokal vs global, dan frekuensi page fault, serta ukuran page.

Working Set Model

1.Prinsip Lokalitas

Prinsip lokalitas adalah proses-proses cenderung mengacu pada penyimpan secara tak seragam. Terdapat dua jenis lokalitas yaitu:

· Lokalitas berdasar waktu (temporal locality). 

· Lokalitas menurut ruang (spatial locality).

Lokalitas berdasar waktu adalah, proses cenderung terkonsentrasi acuannya kesatu interval waktu eksekusi yang dekat. Berarti lokasi-lokasi penyimpanan (kode biner program) paling mutakhir yang diacu cenderung akan diacu kembali di masa datang. Observasi berikut mendukung prinsip lokalitas, antara lain:

·         Looping.
·         Subrutin.       
·         Stack, dan
·         Variabel-variabel yang digunakan untuk iterasi dan penjumlahan total.

Lokalitas berdasar ruang adalah proses cenderung terkonsentrasi acuannya kesatu kelompok data yang berdekatan. Berarti pengacuan-pengacuan (untuk data) cenderung mengelompok ke range lokasi tertentu. Begitu suatu lokasi diacu, cenderung akan mengacu lokasi-lokasi didekatnya. Observasi berikut mendukung prinsip ini, antara lain:

·         Traversal pada array.
·         Eksekusi kode yang sekuen.
·         Kecenderungan pemrogram menempatkan variabel yang terkait saling berdekatan.

Working Set Model 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 thrashing, yaitu setelah hanya beberapa instruksi terjadi page fault. Jika himpunan kerja terdapat di memori, proses akan berjalan tanpa menyebabkan banyak page faultsampai proses berpindah ke fase eksekusi yang lain. Idealnya himpunan kerja program adalah kumpulan page terdiri, dan page-page program yang terlokalisasi pada waktu itu. Program berpindah dari satu lokalitas ke lokalitas lain saat dieksekusi, begitu juga page-page himpunan kerja.

(Buku Sistem Operasi – Bambang Hariyanto Ir halaman 189-190)

Prepaging merupakan teknik memuatkan page-page lebih dulu sebelum proses berjalan. Sementara Demand paging adalah teknik yang segera memuatkan page begitu page dibutuhkan. Model himpunan kerja menghendaki digunakan prepaging. Untuk implementasi model himpunan kerja, sistem operasi perlu mencatat page-page yang termasuk himpunan kerja. Salah satu cara memonitor informasi ini adalah dengan menggunakan algoritma pencatatan umur page.  

Page berisi bit-bit penghitung bernilai f bila termasuk himpunan kerja. Jika page tidak diacu selama n clock tick, maka page dibuang dari himpunan kerja. Parameter n ditentukan secara eksperimen untuk masing-masing sistem. Kinerja sistem biasanya tidak sensitif terhadap nilai eksak n.

(ANA RIZKY P/KA DIII-12.2.00003)

SEGMENTASI
Segmentasi memungkinkan pemrogram memandang memori sebagai berisi banyak ruang alamat atau segmen. Ruang-ruang alamat itu sepenuhna independen. Tiap segmen berisi barisan linear alamat 0 sampai maksimum. Panjang tiapsegemen dapat berbeda sampai panjang segmen maksimum. Dengan segmentasi, pemrogram tidak berurusan dengan batasan-batasan memori yang disebabkan kapasitas memori utama.

Spesifikasialamat pada memori bersegmen adalah 2 dimesi. Yaitu :

1.     Nomor segmen 
 2.    Alamat ada segmen itu. (offset)

Segmen merupakan entitas logic,dan dapat berisi:

a) Stack

      b) Procedure

c) Array

d) Kumpulan variable

(Buku Sistem Operasi – Bambang Hariyanto Ir halaman 197)

Keunggulan teknik segmentasi:

a) Penangan struktur data yang berkembang menjadi sederhana

b) Kompilasi ulang independen ,tidak me link kembali ke semua program

c) Pemakaian memori bersama antar proses menjadi mudah

d) Mudah untuk di proteksi

Untuk kemudahan pengimplementasian, segmen-segmen diberi nomor dan direferensikan dengan menggunakan penomoran tersebut, daripada dengan menggunakan nama. maka, logical address space terdiri dari dua tuple yaitu: (nomor-segmen, offset) Pada umumnya, program dari pengguna akan dikompilasi, dan kompilator tersebut akan membuat segmen-segmen tersebut secara otomatis. Jika mengambil contoh kompilator dari Pascal, maka kemungkinan kompilator tersebut akan membuat beberapa segmen yang terpisah untuk:

1.     Variabel Global, 
2.    Prosedur dari pemanggilan stack, untuk menyimpan parameter dan pengembalian alamat, 
3.    Porsi dari kode untuk setiap prosedur atau fungsi, dan
4.    Variabel lokal dari setiap prosedur dan fungsi.

Meskipun seorang pengguna dapat memandang suatu objek dalam suatu program sebagai alamat berdimensi dua, memori fisik yang sebenarnya tentu saja masih satu dimensi barisan byte. Jadi kita harus bisa mendefinisikan pemetaan dari dua dimensi alamat yang didefinisikan oleh pengguna ke satu dimensi alamat fisik. Pemetaan ini disebut sebagai sebuah segment table. Masing-masing masukan dari mempunyai segment base dan segment limit. Segment base merupakan alamat fisik dan segmen limit diartikan sebagai panjang dari segmen.

(NOVIANA  ERNIS S/KA DIII-12.2.00012)

SUMBER :

http://bugspin.blogspot.com/2012/07/sistem-operasi-segmentasi-memori.html (4 Juli 2013 19:00)