Sistem Paging dan Segmentasi

SISTEM PAGING

1.    PENGERTIAN PAGING

Paging adalah suatu metode yang mengizinkan alamat logika proses untuk dipetakan ke alamat fisik memori yang tidak berurutan, yaitu sebagai solusi dari masalah fragmentasiekstern.

Metode dasar dari paging adalah dengan memecah memori fisik menjadi blok-blok yang berukuran tertentu (frame) dan memecah memori logika menjadi blok-blok yang berukuran sama (page).

Penerjemahan alamat virtual ke alamat fisik dilakukan oleh page table melalui perantara Memory Management Unit (MMU).Paging menjamin keamanan data di memori saat suatu proses sedang berjalan.Proteksi memori dapat diterapkan pada sistem paging dengan meletakkan bit proteksi pada setiap frame. Setiap sistem operasi mengimplementasikan paging dengan caranya masing-masing. Hierarchical paging dan hashed page table merupakan metode yang umum digunakan karena bisa menghemat ruang memori yang dibutuhkan.

Hal-hal penting dalam Paging

Tidak ada fragmentasi eksternal

User melihat ruang memori sebagai suatu kesatuan

Meningkatkan waktu context-switch

Kebanyakan dukungan paging terdapat pada hardware

Ukuran page: besar atau kecil

Ilustrasi konsep paging

Program yang harus dijalankan harus dimuatkan di memori utama. Maslah muncul ketika program lebih besar dari memori utama yang tersedia. Masalah inidiatasi dengan :

1.     Memori maya (virtual memori) Memori maya adalah  kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Konsep ini pertama kali dikemukakan Fotheringh pada 1961 untuk system computer Atlas di Universitas Manchester, inggris Gagasan memori maya adlah ukuran gabungan program, data dan stack melampui 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 di memori yang tidak diperlukandisingkirkan diganti bagian di disk yang diperluka itu.Memori maya dapat dilakukan dengan :

1. Paging

2. Segmentasi

3. Kombinasi paging dan segmentasi. (Eka Hermawan)

2.   Overlay Program dipecah menjadi bagian – bagian yang dapat dimuat memori, disebut overlay. Pertukaran (swap) overlay masuk dan keluar memori dilakukan system operasi.  Teknik overlay telah ditinggalkan karena teknik memori maya telah dapat diimplementasi dengan murah dan berkinerja bagus. (DIAN AGUSTIANA)

2. Penggunaan

program 10 Mbyte dapat berjalan dimesin 2 Mbyte, yaitu  memilih bagian proses sebesar  4Mbyte secara hati – hati dan ditaruh dimemori. Bagian-bagian proses di swap antara disk dan memori saat diperlukan secara otomatis oleh system operasi.

Memori maya dan Multiprogramming

Memori maya dapat dilakukan  pada system multiprogramming.

 Misalnya:

10 program Mb  dapat berjalan dimemori 4Mb.

tiap program dialokasikan 256b Kbyte dan bagian-bagian proses di-swap masuk-keluar  memori begitu diperlukan.

1.     Deskripsi Sistem Paging

Beberapa istilah pada system Paging :

Ø      Alamat maya

Lamat yang dihasilkan dengan perhitungan menggunakan index register,base register,segment register dan sebagainya.

Ø      Alamat nyata

Alamat yang tersedia di memori utama fisik.

Ø      Page

Unit terkecil virtual address space.

Ø      Page frame

Unit terkecil memori fisik.

Ø      Page fault

Exception untuk permintaan alokasi ‘page’ ke memori. (DIAN AGUSTIANA)

Langkah-langkah bila terjadi page fault

Apabila tidak ditemukan frame bebas maka dilakukan page replacement yaitu mencari beberapa page di memori yang tidak digunakan kemudian dilakukan swap out ke backing store. Terdapat beberapa algoritma page replacement dimana performansi algoritma diharapkan menghasilkan jumlah page fault minimum. Beberapa page kemungkinan dibawa ke memori beberapa kali.

Perangkat keras yang dibutuhkan untuk mendukung demand paging sama dengan perangkat keras untuk sistem paging dengan swapping yaitu

• Tabel page : tabel mempunyai kemampuan untuk memberi entry bit valid-invalid atau nilai khusus untuk bit proteksi

• Memori sekunder : digunakan untuk membawa page yang tidak di memori dan biasanya adalah disk kecepatan tinggi yang disebut swap device. (Eka Hermawan)

2. Memori Management Unit (MMU)

Chip atau kumpulan chip yang memetakan alamat maya ke alamat fisik.

·      Pada computer tanpa memori maya, alamat langsung diletakkan ke bus dan  menyebabkan word memori fisik alamat itu dibaca atau ditulis.

·      Pada computer dengan memori maya,alamat tidak diletakkan ke bus secara langsung, tapi lewat MMU yang kemudian memetakan akamat maya ke alamat memori fisik.(DIAN AGUSTIANA)

Memori fisik berisi sejumlah page frame yang memuat sebagian dari page-pageproses .Terdapat mekanisme translasi (penterjemahan) alamat (oleh MMU) untuk memetakan page may ke alamat fisik. Karena tiap page dipetakan secara terpisah,frame-frame proses tidak perlu menempati memori fisik berurutan.

Fungsi :

#Pemetaan memori maya ke memori fisik 

#Jika alamat memori yang diminta tidak tersedia di memori fisik . MMUmenerbitkan  exception page fault yang melewatkan ke system operasi untuk  menanganinya. (Eka Hermawan)

A.     Implementasi Pemetaan (Bagian Internal MMU)

1.       Komponen terpenting MMU:

b.      Register alamat maya

Register alamat maya dibagi menjadi 2 bagian :

Ø      Sejumlah bit berorder tinggi menyatakan nomor page maya

Ø      Bit-bit sisa adalah offset alamat maya

c.         Tabel Page

Tiap elemen table sedikitnya berisi informasi berikut :

Ø      Present/Absent bit

Ø      Nomor page frame

d.      Register alamat fisik

Menyimpan alamat fisik yang disinyalkan ke bus.

Nilai di register alamat fisik dibagi menjadi 2:

Ø      Sejumlah bit berorder tinggi menyatakan nomor page frame

Ø      Bit-bit sisa adalah offset alamat maya (DIAN AGUSTIANA)

2.     Pemetaan Alamat

#Nomor page maya digunakan sebagai indek ke tabel page untuk menemukan isian page maya.

#Dari isian tabel page dapat diketahui apakah page telah dipetakan kememori fisik (dengan memeriksa present/absent bit).

#Bila alamat terdapat di memori fisik, maka isian tabel page memuatnomor page frame. Nomor page frame di tabel page dikopi sebagai bitbit berorder tinggi di register alamat fisik dan ditambah offset alamat maya.

Ketika terjadi Page fault :

1. MMU memperingati page tidak dipetakan ke memori fisik danprocessor melakukan trap ke system operasi (disebut page fault).

2. Membebaskan bagian page frame memori fisik yang kurang jarangdigunakan dengan menyimpan page frame ke disk.

3. Memasukkan page yang diacu ke bagian page frame yang dibebaskan.

4. Mengkonsolidasi pemetaan antara memori maya ke memori fisik 

Ketika terjadi Page Fault, system operasi memilih frame di memori fisik untuk diganti dengan page berguna yang akan masuk.

·            Jika page yang diganti telah dimodifikasi, page harus dituis ke disk,Page yang telah dimodifikasi disebut dirty page

·             Jika page belum diubah, kopian di disk masih up-to-date sehingga tak perlu ditulis ke disk Pemakaian tabel page pada system paging menimbulkan masalah:Tabel Page dapat berukuran luar biasa besar.

Misal:Register alamat maya 32 bitUkuran page 4KB= 212

byteBerarti: terdapat 220page, yaitu : 

Alamat maya 32 bit berarti alamat maya dapat memuat 2 32 byte.Karena tiap page adalah 2 12 byteBerarti jumlah page 232 dibagi 212= 220

Page Pemetaan harus dilakukan secra cepat, pemetaaan alamat maya ke alamat fisik dilakukan setiap terjadi pengacuan memori.

Memori Asosiatif 

Memori asosiatif berisi sejumlah elemen tabel(antara 8 samapi 12 elemen).Tiap elemen berisi informasi-informasi mengenai page, yaitu:

•Nomor Page nyata

•Bit W, untuk mencatat apakah page telah dimodifikasi

•Bit-bit proteksi

•Nomor page frame dari page maya dst 

Mekanisme kerja:

Jika alamat maya dikirim MMU untuk penerjemahan, perangkat keras memeriksa apakah nomor page maya terdapat5 di memori asosiatif denganmembandingkan semua isian memori asosiatif secara simultan.

•Jika ditemukan di memori asosiatif dan pengaksesan tidak melanggar bit-bit proteksi maka page frame langsung ditanganimemori asosiatif tanpa melibatkan tabel page

•Jika page ditemukan di memori asosiatif tapi melanggar bit-bitproteksi, maka diterbitkan page fault

•Jika nomor page maya tidak terdapat di memori asosiatif, makaMMU mencari di tabel page.

 Salah satu elemen memori asosiatif disingkirkan dan diganti elemen tabel page yang ditemukan.Elemen yang disingkirkan dikembalikan ke tabel page di memori. Jika pageitu digubakan kembali, maka hanya akan ditangani memori asosiatif tanpa MMU. (Eka Hermawan)

3.    Penggantian Page

1. Algoritma – algoritma pengganti page

A.     Algoritma  Pengganti Page Acak

Mekanisme Algoitma

Setiap terjadi page fault, page yang diganti dipilih secara acak.

B.     Algoritma  Pengganti Page Optimal

Mekanisme Algoritma

Dasar algoritma ini adalah memilih page yang berpeluang dipakai kembali dimasa datang paling kecil.

C.     Algoritma  Pengganti Page Acak

Algoritma ini mengasumsikan kelas-kelas bernomor lebih rendah akan baru digunakan kembali dalam waktu relative lama.

2. Pemodelan Algoritma Paging

A.     Anomali Pada FIFO (Belady’s Anomaly)

Tampaknya beralasan bila dinyatakan bahwa bila lebih banyak page yang dialokasikan untuk proses, ,aka page default yang terjadi akan lebih sedikit.

B.     Mesin Abstak Eksekusi Program

Setiap proses dimemori maya menghasilkan barisan pengacuan memori saat berjalan. Pengacuan memori berkorespondensi dengan satu page. Secara konseptual, pengaksesan memori dicirikan senarai (berurutan) nomor page. Senarai ini disebut string pengacuan (renference string).

Ø                  Sistem Paging dicirikan tiga hal, yaitu :

1.                   String pengacuan proses yang sedang dieksekusi

2.                   Algoritma penggantian page yang digunakan

3.                   Jumlah page frame yang tersedia (pada memori)

Ø                  Mesin Abstrak

Terdapat mesin abstrak interpreterdengan property berikut :

1.                   Terdapat array internal, M, menyimpan status memori.

2.                   Array M terbagi menjadi 2, yaitu:

a.                   Bagian atas/ puncak, yaitu m isian, page dimemori utama.

b.                  Bagian bawah/ dasar berisi n-m isian, yaitu semua page yang pernah diacu sekali.

3.                  Mulanya array M berupa himpunan kosong karena belum ada page yang telah diacu dan tak ada page yang berada dimemori.

Begitu eksekusi dimulai mengeluarkan page sesuai string pengacuan, satu page pada satu saat. Terhadap page itu, interpreter memeriksa apakah page berada dimemori (yaitu merupakan isian bagian puncak array M) (DIAN AGUSTIANA)

DIAN AGUSTIANA – 12.2.00006

4.    Masalah Utama Pada System Paging:

1.     Working Set Model

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

Terdapat 2 jenis jenis lokalitas:

Ø      Lokalitas berdasarkan waktu (temporal locality),

Ø       Lokalitas berdasarkan ruang (spatial locality),

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

·        Prinsip-Prinsip Working Set Model

Prinsip yang digunakan adalah melacak dan menjamin himpunan kerja terdapat di memori sebelum proses dijalankan.

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

·           Prepaging, Teknik memuatkan page-page lebih dahulu sebelum proses berjalan.

·           Demand Paging, Teknik yang segera memuatkan page begitu page dibutuhkan.

2.     Kebijakan Penggantian Lokal Vs Global

Terdapat Dua Pendekatan untuk mengganti page, yaitu;

·           Penggantian local adalah page yang dipilih untuk diganti hanya pada partisi dimana proses diletakan.

·           Penngantian Global Adalah page yang dipilih untuk diganti adalah tempat kosong dengan tidak memperdulikan partisi proses. (Endang)

3.    Frekuansi page fault

Frekuensi terjadinya page fault dapat dikendalikan dengan algortima pagefault frequency algorthm(PFF) Dengan PFF harus didefinisikan ambang atsdan ambang bawah frekuensi page faul. Jika proses melampui ambang atasfrekuensi page fault maka dialokasikan page memori fisik untuk proses itulebih banyak. Jika proses telah mencapai ambang bawah frekuansi pagefault, maka proses dihentikan.

Implementasi:

1. Sistem operasi mendefinisikan frekuensi page fault kritis sistem.

2. Sistemoperasi mengukur waktu(proses)maya dan menyimpan waktupage fault akhir di PCB3. Ketika terjadi page fault, sistem operasi bertindak:

•Jika page fault terjadi kurang dari T=1/P ms detik yang lalu,proses beroperasi diatas ambang maka page frame baruditambahkan.(T= waktu fault kritis, P : Jumlah page fault permilidetik).Selain itu, berarti proses beroperasi dibawah ambang PFF, makapage frame bit R=0 dan W=0 dibebaskan untuk alokasi page baruproses lain.

4.    Ukuran Page

Pertimbangan menentukan ukuran page

•Ukuran page lebih kecil berarti jumlah page dan page frame lebihbanyak berarti tabel page lebih besar.

•Ukuran page besar, berarti sejumlah informasi yang tidak diacu jugadimasukkan ke memori utama sehingga terjadi fragmentasi internal yang tinggi.

•Transfer Input/Output relaftif sangat mengkonsumsi waktu sehinggaperlu meminimumkan jumlah transfer Input/Output saat programberjalan.

•Program cenderung mengikuti prinsip lokaslitasyang cenderungberukuran kecil.Masala-masalah Implementasi Sistem Paging. (Eka Hermawan)

(Endang)_12.2.00008) (Buku Pak Bambang)

SEGMENTASI DAN KOMBINASI PAGING SEGMENTASI

1.     Deskripsi Segmentasi

Segmentasi memungkinkan pemrogram memandang memori sebagai isi dari banyak ruang alamat atau segmen. Ruang-ruang alamat sepenuhnya independen. Tiapsegmen berisi barisan liner alamat 0 sampai maksimum. Panjang tiap segmen dapatberbeda sampai panjang segmen maksimum. Dengan segmentasi pemrogram tidak berurusan dengan batasan-batasan memori yang disebabkan kapasitas memori utama.Panjang segmen dapat berubah selama eksekusi. Segmen stack bertambah ketikaterjadi operasi Push dan turun saat operasi pop. Segmen dapat menjadi penuh ketikamencapai ukuran maksimum, tapi hal ini jarang terjadi karena segmen berukuran besar.

Spesifikasi alamat pada memori bersegmen adalah dua dimensi. Alamat terdiri dari duabagian yaitu;

1.      Nomor Segmen

2.      Alamat pada segmen itu (offset)

Segmen merupakan entitas logic. Segmen dapat berisi;

Ø                  Procedure

Ø                  Array

Ø                  Stack 

Ø                  Atau sekumpulan variable scalar

Teknik segmentasi mempunyai sejumlah keunggulan dibanding ruang alamat tak bersegmen, yaitu:

1. Menyederhanakan penanganan struktur data yang berkembang

2. Kompilasi ulang independen tanpa menghubungkan kembali seluruh program

3. Memudahkan pemakaian memory bersama diantara proses-proses.

4.   Memudahkan untuk proteksi

2.     Segmentasi secara murni

Segmen-segmen dapat berukuran berbeda dan dinamis. Pengacuan-pengacuan memori berbentuk (nomor, offset). Virtual address adalah offset di segmen. Tiap proses mempunyai tabel segmen. Ketika proses runnimg alamat awal tabel dimuatkan ke register

3.  Contoh Sistem Dengan Memori Maya

1. Memori Maya Dengan Segmentasi Murni

Perangkat keras memberikan pengacuan memori suatu segmen tertentu. Pilihan segmen dapat dibuat dengan semabrang kombinasi berikut :

·         Instruksi

·         Target dari suatu alamat (program atau data)

·         Status saat itu (proses, system,interupsi)

Alamat maya adalah offset di segmen. Tiap proses mempunyai tabel segmen. Ketika proses running, alamat awal table dimuatkan ke register dasar. Nomor segmen digunakan untuk mencari descriptor segmen di table segmen yang menyediakan alamat fisik awal dari segmenn panjang dan bit-bit proteksinya. Alamat fisik dihitung dengan menambahkan alamat dasar segmen ke alamat maya.

Keunggulan

Segmen-segmen berkorespodensi dengan unit-unit program, sehingga segmen-segmen ideal untuk proteksi dan pemakaian bersama. Biasanya program hanya menggunakan beberapa segmen sehingga hanya ruang kecil yang diperlukan. Informasi descriptor dapat disimpan di registry di MMU.

Kelemahan

Segmen-segmen berukuran bervariasi menyebabkan fragmentasi eksternal dan sulit menyelesaikan pertumbuhan dinamis. Segmen-segmen tidak memetakan blok-blok disk untuk memori maya secara alami. (Endang)

 (Endang_12.2.00008) (Buku Pak Bambang)

4. Arsitektur Segmentasi

Alamat logika terdiri dari dua bagian yaitu nomor segmen (s) dan offset (d) yang dituliskan dengan (nomor segmen, offset)

Pemetaan alamat logika ke alamat fisik menggunakan tabel segmen (segment table), terdiri dari
• Segmen basis (base) berisi alamat fisik awal
• Segmen limit merupakan panjang segmen

Seperti tabel page, tabel segmen dapat berupa register atau memori berkecepatan tinggi. Pada program yang berisi sejumlah segmen yang besar, maka harus menyimpan tabel page di memori.
• Segment-table base register (STBR) digunakan untuk menyimpan alamat yang menunjuk ke segment table.
• Segment-table length register (STLR) digunakan untuk menyimpan nilai jumlah segmen yang digunakan program.
• Untuk alamat logika (s, d), pertama diperiksa apakah segment number s legal (s < STLR), kemudian tambahkan segment number ke STBR, alamat hasil (STBR + s) ke memori dari segment table. Perangkat keras yang digunakan pada sistem segmentasi dapat dilihat pada Gambar

Pemetaan dari alamat logika ke alamat fisik membutuhkan 2 acuan memori untuk setiap alamat logika. Hal ini akan menurunkan kecepatan sistem dengan faktor 2. Solusi standard yang digunakan adalah dengan cache (atau associative register) untuk menyimpan entri tabel segmen yang sering digunakan. Pemetaan alamat logika ke alamat fisik dengan menggunakan tabel segmen dapat dilihat pada Gambar

Misalnya alamat logika dengan nomor segment 0 offset 88 akan dipetakan ke alamat fisik 1400 + 88 = 1488 karena offset < limit (88 < 1000). Alamat logika dengan nomor segment 1 offset 412 akan terjadi error karena offset > limit (412 > 400). Alamat logika dengan nomor segment 2 offset 320 akan dipetakan ke alamat fisik 4300 + 320 =
4620 karena offset < limit (320 < 400).

Dimulai dengan model 80386, microprocessor Intel menampilkan translasi alamat dengan 2 cara berbeda, yang disebut real mode dan protected mode. Real mode untuk memelihara kompatibilitas prosesor dengan model yang lebih lama dan untuk OS agar dapat melakukan bootstrap.

• Segmentation Registers
Logical address terdiri atas dua bagian : segment identifier dan sebuah offset yang menunjukkan alamat yang bersangkutan pada segment. Segment identifier adalah sebuah 16-bit field yang disebut segment selector. Untuk mempermudah memperoleh segment selectors dengan cepat, prosesor menyediakan segmentation register yang tujuannya hanya untuk memegang segment selectors. Ada enam segmentation register : cs, ss, ds, es, fs, dan gs.

• Segment Descriptor
Setiap segment direpresentasikan dengan 8-byte segment descriptor yang menggambarkan karakteristik segment. Segment descriptor disimpan pada Global Descriptor Table(GDT) atau pada Local Descriptor Table(LDT).

• Segment Selectors
Untuk mempercepat pengubahan dari logical address ke linear address, Intel menyediakan nonprogrammable register tambahan untuk setiap dari 6 programmable segmentation register. Setiap segment selector di-load pada sebuah segmentation register, segment descriptor yang bersangkutan di-load dari memori ke nonprogrammable CPU register yang bersesuaian. Jadi, pengubahan dari logical address ke linear address dilakukan tanpa mengakses GDT atau LDT yang berada pada memori utama. Akses ke GDT atau LDT hanya diperlukan bila isi dari segmentation register berubah. Setiap segment selector mengandung hal-hal berikut :
- Sebuah index 13-bit yang menunjukkan masukan segment descriptor yang berhubungan yang terdapat pada GDT atau LDT.
- Sebuah TI (tabe indicator) flag yang menunjukkan apakah segment descriptor terdapat pada GDt (Ti = 0) atau pada LDT (TI = 1).
- Sebuah RPl (requestor privilege level) 2-bit field, yang membuat current privilege level cPu tepat saat segment selector yang berhubungan di-load ke register cs.

• Segmentation Unit
Segmentatipn Unit melakukan operasi-operasi berikut :
- Memeriksa TI dari segment selector, untuk memutuskan apakah descriptor table berada pada segment descriptor.
- Menghitung alamat dari segment descriptor dari index filed segment selector.
- Menambahkan ke Base field dari segment descriptor, offset dari logical address, sehingga diperoleh linear address.

CATHARINA R.L.N-12.2.00004  (Anggota)-Segmentasi-http://myblogninik.blogspot.com/2013/06/sistem-operasi-ii.html (11.39)

DIAN AGUSTIANA – 12.2.00006 (Anggota)-Sistem Paging

Buku “Sistem Operasi” Bambang Harianto

EKA HERMAWAN-12.2.00007     (Ketua)-Sistem Paging-

www.scribd.com ( Friday, June 28, 2013 19.05 WIB)

lecturer.eepis-it.edu (Wednesday,june 24,2013 18.52 wid) pdf

ENDANG-12.2.00008        (Anggota)-Segmentasi

Buku “Sistem Operasi” Bambang Harianto