SISTEM PAGING DAN SEGMENTASI

SISTEM PAGING

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

Kini teknik Overlay telah ditinggalkan karena teknik memori maya telah dapat diimplementasikan dengan murah dan berkinerja bagus.

2.      Konsep Memori Maya

Yaitu kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Konsep ini dikemukakan Fotheringham pada 1961. 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.

Sistem paging mengimplementasikan ruang alamat besar pada memori kecil menggunakan ibdex register, base register dan segment register, dll. Pemakai seolah-olah mempunyai ruang memori sangat besar tanpa mengelola overlay.

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

TABEL-TABEL PAGING

Pemakaian tabel page pada sistem paging menimbulkan 2 masalah utama, yaitu :

1.      Tabel page dapat berukuran luar biasa besar

Bila memori maya sangat besar maka tidak mungkin menggunakan satu tabel tunggal karena akan memerlukan tabel berukuran sangat besar. Solusinya menggunakan tabeltabel bertingkat (seruap indeks bertingkat di organisasi berkas).

2.      Pemetaan harus dilakukan secara cepat.

Pemetaan alamat maya ke alamat fisik dilakukan setiap terjadi pengacuan memori. Pada pemroses dngan memori maya, pengelolaan page besar dan cepat merupakan konstrain uutama perancangan dan pembangunan pemroses.

PENGGANTIAN PAGE

Saat terjadi 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 dimasa datang. Jika age yang diganti akan kembali digunakan, maka page akan dikembalikan secepatnya yang berarti terjadi page fault berulang kali.
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). Akan tetapi, teknik ini sangat buruk, percobaan menunjukan rate page fault sangat tinggi.

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. Dan metode ini tak mungkn diterapkan.

Algoritma ini penting untuk kajian teoritis, sebagai pembanding bagi algoritma-algoritma peggantian page yang lain.

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.

Algoritma ini mudah dipahami dan diimplementasikan. Implementasi algoritma ini sangat efisien karna tak banyak langkah dalam pemilihan page. Akan tetapi, algoritma ini tidak optimal, tapi dalam kondisi-kondisi normal telah memadai.

4. Algoritma Penggantian Page FIFO

Algoritma ini dapat memilih memindahkan page yang sering digunakan yang lama berada dimemori. Kemungkinan ini dapat dihindari dengan hanya memindahkan page tidak diacu.

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. Mekanisme ini kembali diterapkan ke elemen berikutnya.

• 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 age 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)

Page-page pada beberapa intruksi terakhir berkemungkinan besar akan dipakai kembali. Page-page yang lama tidak digunakan akan tetap tak digunakan dalam waktu lama. 

Mekanisme algoritma :

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

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

Setiap proses dimemori maya menghasilkan barisan pengacuan memori saat berjalan. Pengacuan memori berkorespondensi dengan satu page.
Sistem Oaging dicirikan 3 hal :
- String pengacuan proses yang sedang dieksekusi
- Algoritma penggantian page yang digunakan.
Jumlah page frame yang tersedia (pada memori)

Terdapat mesin abstrak interpreter dengan properti berikut:

1.    Terdapat array internal, 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 array M 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 string pengacuan, 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 page pindah dari bagian puncak ke bagian dasar, serta page yang diperlukan dimasukkan ke puncak. 

Masalah-masalah Utama pada Sistem Paging

Masalah-masalah Utama pada Sistem Paging adalah working set model, 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).

Prinsip lokalitas diperoleh dari observasi, bukan kajian teoritis. Prinsip lokalitas menunjukkan kecenderungan kelakuan lingkungan sistem bukan tepat eksak. Gambar 4-14 menunjukkan pola pengacuan selama eksekusi yang mendukung adanya prinsip lokalitas. Bagian gelap menunjukkan pengacuan dilakukan di sekitar lokalitas yang saling berdekatan.

Gambar Pola Pengacuan-pengacuan Page Selama Eksekusi Sistem

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

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.

Masalah-Masalah Implementasi Sistem Paging

Perancang sistem paging berurusan beragam masalah implementasi sistem paging, antara lain backup instruksi yang terakhir dijalankan sebelum terjadi page fault, buffer perangkat masukan/keluaran (penguncian page di memori), page yang dipakai bersama, backing store, dan paging daemon, serta penanganan page fault (page fault handling).

a.Backup Instruksi

Bila terjadi page fault berarti sebagian instruksi telah dijalankan. Pengkopian program counter dan informasi register-register pemroses harus dilakukan. Setelah penggantian page selesai maka instruksi yang menyebabkan page fault dapat dijalankan kembali dengan konteksnya. Masalah yang harus diatasi adalah untuk mengulangi instruksi, sistem harus menentukan byte pertama instruksi. Kesulitan timbul karena nilai program counter saat terjadi page fault bergantung pada operan yang menyebabkan fault dan mikrokode pemroses. Masalah memburuk pada instruksi di mode autoincrement, sangat bergantung pada rincian-rincian mikrokode, yaitu:

• Jika increment scsungguhnya dilakukan sebelum pengacuan memori, maka sistem operasi harus decrement register secara perangkat lunak sebelum mengulangi instruksi yang menyebabkan page fault.

• Jika increment dilakukan setelah pengacuan memori, maka tidak perlu dilakukan decrement register oleh sistem operasi.

Perancang pemroses menyediakan solusi untuk masalah ini. Beragam cara diterapkan, tergantung mesin yang digunakan. Beberapa mesin yang menyediakan solusi antara lain POP-11/45, VAX, Motorola 68010, dan lain-lain.

b.Buffer I/O (Penguncian Page di Memori)

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

• Buffer perangkat masukan/keluaran ikut tergusur.

• Adanya buffer satu perangkat masukan/keluaran menjadi rangkap.

• Masalah diatasi dengan dua alternatif yaitu:

o   Penguncian buffer perangkat masukan/keluaran sehingga tidak menjadi sasaran penggantian.

o   Buffer perangkat masukan/keluaran ditempatkan di kernel dan dikopi semua data ke page-page proses pemakai.

c.Pemakaian Page Bersama

Bila beberapa pemakai menggunakan program yang sama, maka terjadi perangkapan page (page yang sama terdapat di banyak bagian di memori). Lebih efisien bila menggunakan page secara bersama, menghindari keharusan mempunyai kopian-kopian page yang sama di saat yang sama. Masalah yang muncul adalah tidak semua page dapat dipakai bersama (Kode biner program (program text) adalah shareable (dapat dipakai bersama) sedang data tidak shareable), dan akhir suatu proses (Masalah berikutnya adaiah bila salah satu proses hendak membuangpage dari memori karena proses berakhir).

Solusi untuk kasus ini adalah saat proses berakhir, sistem operasi memeriksa apakah page-page masih digunakan proses-proses lain. Bila masih dipakai proses lain, maka sistem operasi tidak membebaskan page-page tersebut dari memori. 

d.Backing Store

Masalah lain adalah menyangkut dimana diletakkan page yang keluar dari memori utama. Terdapat beragam algoritma untuk mengatasi hal ini, yaitu menggunakan ruang penggantian khusus, atau dialokasikan berdasar kebutuhan.  

Proses dapat meningkat ukurannya sehingga ruang di disk yang dialokasikan di awal tidak dapat memuatnya. Proses lebih baik menyimpan daerah swap terpisah untuk teks, data, dan stack serta memungkinkan masing-masing daerah berisi lebih dari satu potongan.

Keunggulannya adalah proses-proses di memori tidak terikat ketat dengan suatu ruang swap. Sedangkan kelemahannya adalah, alamat disk perlu disimpan sehingga mengetahui letak lokasi page yang diganti, atau yang disimpan di disk.

e.Paging Daemons

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, page lama harus ditulis lebih dulu ke disk. Untuk menjamin suplai page frame yang banyak, sistem paging biasanya mempunyai proses background, disebut paging daemon. Paging daemon sleep  untuk kebanyakan waktu, dibangunkan secara periodik untuk menginspeksi keadaan memori.

Paging daemon yang menyimpan suplai page frame menghasilkan kinerja lebih baik dibandingkan dengan menggunakan semua memori, kemudian mencoba menemukan frame saat itu juga.

f.Penanganan Page Fault (Page Fault Handling)

Implementasi sistem paging harus mengatasi rincian-rincian aksi yang harus dilakukan saat terjadi page fault. Rincian-rincian saat terjadi page fault adalah sebagai berikut:

1.    Perangkat keras melakukan trap ke kernel untuk menyimpan program counter di stack. Pada kebanyakan mesin, informasi mengenai keadaan instruksi saat itu disimpan di register-register pemroses secara khusus.

2.    Satu rutin assembly dimulai untuk menyimpan register-register umum dan informasi-informasi lain yang dapat hilang. Rutin ini memanggil sistem operasi.

3.    Sistem operasi mengetahui telah terjadi page fault dan mencoba menemukan virtual page yang diperiukan. Aksi ini sering dibantu perangkat keras dengan menyediakan register-register berisi informasi yang diperlukan. Jika tidak ada bantuan perangkat keras, sistem operasi harus mengambil program counter, mengambil instruksi, dan mem-parse secara perangkat lunak untuk mendapat gambaran apa yang terjadi saat fault.

4.    Begitu alamat maya yang menyebabkan fault diketahui, sistem operasi memeriksa apakah alamat valid, dan konsisten terhadap proteksi.

·   Jika tidak konsisten dengan proteksi, proses yang menyebabkan fault dikirimi sinyal atau dibunuh.

·   Jika alamat valid dan tak terjadi protection fault, sistem berusaha memperoleh page frame dari senarai frame bebas. Jika tak ada frame bebas, algoritma penggantian page dijalankan.

5.    Jika page frame telah dimodifikasi, page dijadwalkan untuk transfer ke disk dan terjadi context switch, menunda proses fault dan membiarkan/menyilahkan proses lain berjalan sampai transfer disk selesai. Pada suatu kejadian, frame ditandai sedang sibuk untuk mencegahnya digunakan untuk maksud lain.

6.    Begitu page frame bersih, sistem operasi melihat alamat disk dimana page diperlukan dan dijadwalkan operasi disk untuk membawanya sebagai frame yang disediakan. Sambil page dimuatkan, proses fault masih ditunda dan proses pemakai yang lain dijalankan, jika proses itu tersedia.

7.    Ketika interupsi disk mengindikasikan page telah tiba, tabel-tabel page diperbarui untuk merefleksikan posisinya dan frame ditandai sebagai dalam keadaan normal.

8.    Instruksi fault di-back up ke keadaan ketika dimulai dan program counter diriset untuk menunjuk ke instruksi itu.

9.    Proses fault dijadwalkan dan sistem operasi mengembalikan ke rutin bahasa assembly yang memanggilnya.

10.      Rutin ini menyimpan kembali register-register dan informasi yang dapat hilang lainnya, serta mengembalikan ke ruang pemakai untuk melanjutkan eksekusi, seperti bila tak terjadi fault.  

Contoh Kasus :

·          Organisasi Memory dan Arsitekturnya (Tugas yang dikerjakan oleh mahasiswa dan dipresentasikan di depan kelas)

·          Manajemen Memory (Tugas yang dikerjakan oleh mahasiswa dan dievaluasi bersama di kelas)

SEGMENTASI 
Segmentasi memungkinkan pemrogrammemandang memori sebagai berisi banyak ruang alamat atau segmen. Ruang-ruang alamat itu sepenuhna independen. Tiap segmen berisi barisan linear alamat 0 sampai maksimu. 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)

logical address space adalah kumpulan dari segmen-segmen yang mana tiap-tiap segmen mempunyai nama dan panjang. alamat tersebut menunjukkan alamat dari segmen tersebut dan offset-nya didalam segmen-segmen tersebut. pengguna kemudian menentukan pengalamatan dari setiap segmen menjadi dua bentuk, nama segmen dan offset dari segmen tersebut (Hal ini berbeda dengan pemberian halaman, dimana pengguna hanya menentukan satu buah alamat, dimana pembagian alamat menjadi dua dilakukan oleh perangkat keras, semua ini tidak dapat dilihat oleh user).

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.


 Sumber :
Buku Bambang Hariyanto
http://bugspin.blogspot.com/2012/07/sistem-operasi-segmentasi-memori.html
Tgl akses : 16 Juni 2013
Jam akses : 19.45