Posted by : Niam Tamami May 16, 2010

Paging merupakan kemungkinan solusi untuk permasalahan fragmentasi eksternal dimana ruang alamat logika tidak berurutan; mengijinkan sebuah proses dialokasikan pada memori fisik yang terakhir tersedia. Memori fisik dibagi ke dalam blok-blok ukuran tetap yang disebut frame. Memori logika juga dibagi ke dalam blok- blok dg ukuran yang sama yang disebut page. Semua daftar frame yang bebas disimpan. Untuk menjalankan program dengan ukuran n page, perlu menemukan n frame bebas dan meletakkan program pada frame tersebut. Tabel page (page table) digunakan untuk menterjemahkan alamat logika ke alamat fisik.

Setiap alamat dibangkitkan oleh CPU dengan membagi ke dalam 2 bagian
• Page number (p) digunakan sebagai indeks ke dalam table page (page table).
Page table berisi alamat basis dari setiap page pada memori fisik.
• Page offset (d) mengkombinasikan alamat basis dengan page offset untuk mendefinisikan alamat memori fisik yang dikirim ke unit memori.
Arsitektur dari sistem paging dapat dilihat pada Gambar


Ukuran page (juga frame) didefinisikan oleh perangkat keras. Ukuran page merupakan bilangan 2 pangkat k, mulai 512 (29) s/d 8192 (213) tergantung arsitektur computer. Bila ukuran ruang alamat logika 2m dan ukuran satu page adalah 2n address unit (byte/word) maka (m-n) bit orde tinggi dari alamat logika menunjukkan nomor page (page number) dan n bit orde rendah menunjukkan page offset.

                                                                  page number
             page offset
p
d

m-n

n



Proses pemetaan dari alamat logika ke alamat fisik yang menggunakan ukuran page 4 byte dan memori fisik 32 byte (8 page) dapat dilihat pada Gambar 7-13. Sebagai contoh alamat logika 2 berada pada page 0 akan dipetakan ke frame 5, sehingga alamat fisiknya adalah (5 X 4) + 2 = 22. Alamat logika 4 berada pada page 1 akan dipetakan ke frame 6, sehingga alamat fisiknya adalah (6 X 4) + 0 = 24. Alamat logika 9 berada pada page 3 akan dipetakan ke frame 1, sehingga alamat fisiknya adalah (1 X 4) + 1 = 5. Alamat logika 15 berada pada page 4 akan dipetakan ke frame 2, sehingga alamat fisiknya adalah (2 X 4) + 3 = 11.

Pada skema paging, tidak terjadi fragmentasi eksternal, karena “sembarang” frame dapat dialokasikan ke proses yang memerlukannya. Tetapi beberapa fragmentasi internal masih mungkin terjadi. Hal ini dikarenakan frame dialokasikan sebagai unit dan jika kebutuhan memori dari proses tidak menemukan page, maka frame terakhir mungkin tidak dialokasikan penuh.
Bila suatu proses datang untuk dieksekusi, maka ukurannya diekspresikan dengan page. Setiap page membutuhkan satu frame. Bila proses membutuhkan n page, maka proses tersebut juga membutuhkan n frame. Jika tersedia n frame, maka memori dialokasikan untuk proses tersebut. Alokasi page pada frame bebas dapat dilihat pada Gambar

Pada paging, user memandang memori sebagai bagian terpisah dari memori fisik aktual. Program user memandang memori sebagai satu ruang berurutan yang hanya berisi program user tersebut. Faktanya, program user terpecah pada memori fisik, yang juga terdapat program lain. Karena sistem operasi mengatur memori fisik, perlu diwaspadai lokasi detail dari memori fisik, yaitu frame mana yang dialokasikan, frame mana yang tersedia, berapa jumlah frame dan lain-lain. Informasi tersebut disimpan sebagai struktur data yang disebut “frame table”.

Implementasi Sistem Paging

Setiap sistem operasi mempunyai metode sendiri untuk menyimpan tabel page. Beberapa sistem operasi mengalokasikan sebuah tabel page untuk setiap proses. Pointer ke tabel page disimpan dengan nilai register lainnya dari PCB.
Pada dasarnya terdapat 3 metode yang berbeda untuk implementasi tabel page :

1. Tabel page diimplementasikan sebagai kumpulan dari “dedicated” register.
Register berupa rangkaian logika berkecepatan sangat tinggi untuk efisiensi translasi alamat paging. Contoh : DEC PDP-11. Alamat terdiri dari 16 bit dan ukuran page 8K. Sehingga tabel page berisi 8 entri yang disimpan pada register. Penggunaan register memenuhi jika tabel page kecil (tidak lebih dari 256 entry).
2. Tabel page disimpan pada main memori dan menggunakan page table base registe” (PTBR) untuk menunjuk ke tabel page yang disimpan di main memori. Penggunakan memori untuk mengimplementasikan tabel page akan memungkinkan tabel page sangat besar (sekitar 1 juta entry). Perubahan tabel page hanya mengubah PTBR dan menurunkan waktu context-switch. Akan tetapi penggunaan metode ini memperlambat akses memori dengan faktor 2. Hal ini dikarenakan untuk mengakses memori perlu dua langkah : pertama untuk lokasi tabel page dan kedua untuk lokasi alamat fisik yang diperlukan.
3. Menggunakan perangkat keras cache yang khusus, kecil dan cepat yang disebut associative register atau translation look-aside buffers (TLBs). Merupakan solusi standar untuk permasalahan penggunaan memori untuk implementasi tabel page. Sekumpulan associative register berupa memori kecepatan tinggi. Setiap register terdiri dari 2 bagian yaitu key dan value. Jika associative register memberikan item, akan dibandingkan dengan semua key secara simultan. Jika item ditemukan nilai yang berhubungan diberikan. Model ini menawarkan pencarian cepat tetapi perangkat keras masih mahal. Jumlah entry pada TLB bervariasi antara 8 s/d 2048.

Mekanisme penggunaan associative register (Gambar 7-15) adalah sebagai berikut :
• Associative register berisi hanya beberapa entry tabel page (sampai dengan ukuran maksimum).
• Jika memori logika dibangkitkan oleh CPU, nomor page berupa sekumpulan associative register yang berisi nomor page dan nomor frame yang berkorespondensi.
• Jika nomor page ditemukan pada associative register, nomor frame segera tersedia dan digunakan untuk mengakses memori.
• Sebaliknya, jika nomor page tidak ditemukan pada associative register, acuan memori ke tabel page harus dibuat.
• Jika nomor frame tersedia, maka dapat menggunakannya untuk mengakses ke memori yang tepat.
• Kemudian ditambahkan nomor page dan nomor frame ke associative register sehingga akan mudah ditemukan pada acuan berikutnya.
• Setiap kali tabel page baru dipilih, TLB harus dihapus untuk menjamin eksekusi proses berikutnya tidak menggunakan informasi translasi yang salah.

Persentasi waktu sebuah page number ditemukan pada associative register disebut hit ratio. Hit ratio 80% berarti penemuan page number yang tepat pada associative register adalah 80% dari waktu. Misalnya, untuk mencari entry di associative register memerlukan waktu 20 ns dan untuk mengakses memori memerlukan waktu 100 ns sehingga untuk memetakan ke memori memerlukan waktu
120 ns. Apabila tidak menemukan page number pada associative register (20 ns), maka harus lebih dahulu mengakses tabel page di memori (100 ns) dan kemudian akses ke lokasi memori yang tepat (100 ns). Maka effective access time (EAT) menjadi 0.8 X 120 + 0.2 X 220 = 140 ns

Artinya terjadi 40% penurunan kecepatan waktu akses memori.

Hit ratio berhubungan dengan jumlah associative register. Apabila jumlah associative register antara 16 s/d 512, maka hit ratio yang dapat dicapai antara 80% sampai 98%. Prosessor Motorola 68030 yang digunakan pada sistem Apple Mac mempunyai TLB 22 entry. CPU Intel 80486 mempunyai 32 register dan hit ratio 98%.

Proteksi

Pada model page, proteksi memori menggunakan bit proteksi yang diasosiasikan untuk setiap frame. Biasanya bit proteksi disimpan pada tabel page. Satu bit mendifinisikan satu page untuk “read and write” atau “read-only”. Setiap acuan ke memori melalui tabel page untuk menemukan nomor frame yang benar. Level proteksi
yang lebih baik dapat dicapai dengan menambah jumlah bit yang digunakan.

Pada tabel page diberi tambahan “valid-invalid” bit seperti pada Gambar 7-16. Nilai “valid” mengindikasikan bahwa page berada pada ruang alamat logika yang berarti merupakan page yang legal (valid). Nilai “invalid” mengindikasikan bahwa page tidak berada pada ruang alamat logika atau page yang illegal (invalid). Sistem operasi mengeset bit ini untuk setiap page untuk mengijinkan atau tidak mengakses page.

Multilevel Paging

Model multilevel paging digunakan pada sistem yang mempunyai ruang alamat logika yang sangat besar yaitu antara 232 s/d 264. Pada sistem ini, tabel page akan menjadi sangat besar. Misalnya untuk sistem dengan ruang alamat logika 32 bit dan ukuran page 4K byte, maka tabel page berisi 1 juta entry (232 / 212). Solusinya yaitu dengan melakukan partisi tabel ke beberapa beberapa bagian yang lebih kecil.
Untuk sistem dengan ruang alamat logika 32 bit dapat dipecahkan menggunakan skema two level paging. Pada skema ini alamat logika dibagi menjadi 20 bit untuk nomor page dan 12 bit untuk page offset. Karena tabel page juga merupakan page maka nomor page lebih jauh akan dipecah menjadi 10 bit untuk nomor page dan 10 bit untuk
page offset.

Dimana pi adalah indeks ke table page luar dan p2 adalah displacement dalam page pada table page luar. Skema tabel page pada two level paging dapat dilihat pada Gambar 7-17. Sedangkan arsitektur translasi alamat pada two level paging untuk mesin 32 bit dapat dilihat pada Gambar 7-18.
Untuk sistem dengan ruang alamat logika 64 bit tidak dapat menggunakan skema two-level paging. Solusi yang digunakan adalah dengan membagi tabel page luar ke dalam bagian yang lebih kecil : menggunakan skema three-level atau four-level paging. Multilevel paging dapat berakibat pada performansi sistem. Untuk skema three-level paging, jika kita menggunakan memori untuk menyimpan tabel, maka akan membutuhkan 4 kali akses memori. Tetapi jika menggunakan cache dengan hit ratio 98%, effective access time menjadi 0.98 X 120 + 0.02 X 420.
Shared Page

Pada skema paging, dimungkinkan untuk sharing kode umum seperti pada Gambar 7-19. Bentuk ini penting terutama pada lingkungan time sharing. Satu copy kode read-only dibagi ke beberapa proses (misalnya editor teks, compiler dan sistem window). Kode yang dibagi harus berada pada lokasi ruang alamat logika yang sama untuk semua proses.
Kode dan data pribadi (private) untuk setiap proses diletakkan terpisah dari kode dan data pribadi proses lain. Page untuk kode dan data pribadi dapat diletakkan di
sembarang tempat pada ruang alamat logika.


tested by 1kata

Leave a Reply

Subscribe to Posts | Subscribe to Comments

Entri Populer

tweet

- Copyright © 2013 blog.nitbot.com -Metrominimalist- Powered by Blogger - Designed by Johanes Djogan -