Saya Sang Vector. Ayo Pesan Sekarang. Hanya Disini.

Yang mau Pesan

Senin, 24 Juni 2013

System Paging



Sistem Paging

A.     Memori Maya
Program yang dijalankan harus dimuat di memori utama. Masalah muncul ketika program lebih besar dibanding memori utama yang tersedia.

Terdapat dua solusi maalah ini, yaitu:
1.      Overlay
2.      Memori maya ( virtual memori )

I.                    Konsep Overlay
Program dipecah menjadi bagian-bagian yang dapat dimuat memori, disebut overlay. Overlay yang belum diperlukan (tidak sedang dieksekusi) disimpan di disk, overlay ini dimuatkan ke memori begitu diperlukan (kode di overlay akan di eksekusi).

Pertukaran overlay masuk dan keluar memori dilakukan sistem operasi. Pembagian program menjadi overlay-overlay dilakukan pemrograman. Pembagian program menjadi potongan-potongan kecil dan modular menghabiskan banyak waktu.

 













Gambar 1 Struktur umum overlay

Teknik overlay telah ditinggalkan karena teknik memori maya telah dapat diimplementasikan dengan murah dan berkinerja bagus.




II.                 Konsep memori maya
Memori maya adalah kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Konsep memori maya pertama kali dikemukakan Fotheringham pada 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 dapat menyimpan bagian-bagian proses yang sedang digunakan memori utama dan sisanya didisk.

Penggunaan
Program 10 Megabyte, dapat berjalan di mesin 2 Megabyte, yaitu memilih bagian proses sebesar 2 Megabyte secara hati-hati dan ditaruh di memori. Bagian-bagian proses di-swap antara disk dan memori saat diperlukan secara otomatis oleh sistem operasi.

Memori Maya dan Multiprogramming
Memori maya dapat dilakukan pada sistem multiprogramming.
Misalnya
-          10 prpgram 2 Mb dapat berjalan di memori 4 Mb.
Tiap program dialokasikan 256 kilobyte dan bagian-bagian proses di-swap masuk-keluar memori begitu diperlukan.
Memori maya meningkatkan efisiensi sistem multiprogramming. Memori maya dan multiprogramming adalah dua konsep yang saling melengkapi. Saat proses menunggu bagiaannya di-swap masuk ke memori, menunggu selesainya operasi masukan/keluaran, proses di-block, jatah layanan pemroses diberikan ke proses lain.

Prinsip berikut berlaku :
Kecepatan maksimum eksekusi proses di memori maya dapat sama tapi tidak pernah melampaui kecepatan eksekusi proses yang sama di sistem tanpa memori maya.

Memori maya dapat dilakukan dengan tiga cara, yaitu :
1.      Paging
2.      Segmentasi
3.      Kombinasi paging dan segmentasi

B.      Deskripsi Sistem Paging
Sistem paging mengimplementasikan ruang alamat besar pada memori kecil menggunakan index register, base register, segment register, dan segment register, dan lain-lain. Pemakai seolah mempunyai ruang memori sangat besar tanpa mengelola overlay.

Beberapa istilah pada sistem paging adalah
1.      Alamat maya (virtual address)
2.      Alamat nyata (real address)
3.      Page
4.      Page frame
5.      Page fault
6.      MMU




Alamat Maya
Alamat maya adalah alamat yang dihasilkan perhitungan menggunakan index register, base register, segment register dan sebagainya. Ruang alamat yang dibentuk alamat maya disebut ruang alamat maya (virtual address space), v. jumlah alamat pada V disimbolkan dengan V. alamat maya ini yang diacu proses yang running.

Alamat Nyata
Alamat nyata adalah alamat di memori utama fisik. Ruang alamat yang dibentuk alamat nyata disebut ruang alamat nyata (real address space), R. jumlah alamat pada R disimbolkan dengan R.
Pada implentasi sistem memori maya, normalnya V >> R.

Page
Page adalah unit terkecil virtual address space. Ruang alamat maya proses merupakan kelipatan page yang berukuran sama.

Page Frame

Page frame adalah unit terkecil memori fisik. Memori fisik secara konseptual dibagi sejumlah unit berukuran tetap disebut page frame. Page frame sering juga disingkat frame.











            Memori maya                                                              Memori nyata












Gambar 2 Hubungan antara ruang alamat maya dan alamat fisik.

Page Fault
Page fault adalah exception untuk permintaan alokasi ‘page’ kememori dalam konteks memori maya, page fault sering juga disingkat fault.

Memory Management Unti ( MMU )
Chip atau kumpulan chip yang memetakan alamat maya ke alamat fisik.
1.      Pada komputer tanpa memori maya, alamat langsung diletakkan ke bus dan menyebabkan word memori fisik alamat itu dibaca dan ditulis.
2.      Pada komputer dan memori maya, alamat tidak diletakkan di bus secara langsung tapi lewat MMU yang kemudian memetakan alamat maya ke alamat memori fisik.
Pada pemroses modern, MMU sudah menyatu di pemroses (on-chip).










 
Text Box: Pemroses
Mengirim
Alamat maya
Ke MMU
                                               









 




Text Box: MMU mengirim alamat
fisik ke memori
Bus


Gambar 3 Posisi dan fungsi MMU

Memori fisik berisi sejumlah page frame yang memuat sebagian page-page. Terdapat mekanisme translasi (penerjemahan) alamat (dilakukan MMU) untuk memetakan page maya ke alamat fisik. Sistem memori maya mempunyai properti alamat-alamat kontigu (berurutan) pada ruang alamat maya yang tidak harus kontigu di memori nyata. Property ini disebut kontigu semu (artificial contiguity).








Text Box: Memori maya
Text Box: Pemetaan alamat (MMU)
Text Box: Memori nyata

 

















                                         

gambar 4 Kontigu semu
Pemakaian di bebaskan berurusan dengan letak prosedur  dan data diposisikan di memori nyata.Pemogram dapat menulis program seperti biasa,yaitu memperhatikan efisiensi algoritma dan struktur program,mengabaikan rincian struktur perangkat keras.Dengan sistem maya,memori dapat di pandang sebagai kontigu yang berukuran besar.
i.                     MMU (Memory Managemen Unit)
MMU mempunyai  fungsi sebagai berikut  :
·         Pemetaan memori maya ke memori fisik.
·         Bila alamat memori yang diminta tidak tersedia di memor i fisik,MMU menerbitkan exception adanya page-fault yang melewatkan ke sistem operasi untuk menanganinya.

·         Skema Pemetaan
Pada komputer dengan memori maya,alamat tidak di letakkan ke bus secara langsung tapi di lewatkan ke MMU yang memetakan alamat maya ke alamat memori  fisik.Pemetaan dapat dirumuskan secara formal sebagai berikut :
Skenario  pemetaan

Memori nyata
Alamat
Memori maya

















7
5
X
X
0
1
6
3
X
4
X
X
X
2
X
X
0-4K
4K-8K
8K-12K
12K-16K
16K-20K
20K-24K
24K-28K
28K-32K
32K-36K
36K-40K
40K-44K
44K-48K
48K-52K
52K-56K
56K-60K
60K-64K

Gambar 5 Relasi antara alamat maya dan alamat fisik



Misalnya instruksi:
MOV REG,oxo8
·         Alamat maya 8 dikirim ke MMU
·         MU mengetahui alamat 8 di page 0 (page 0 memuat alamat maya 0-4o95)
·         Dari tabel,page 0 dipetakan ke frame 7 (page 7 adalah alamat fisik 28672-32768)
·         MMU mentransformasikan alamat 8 sebagai (28672 + 8 = 28680)
·         MMU mengeluarkan alamat 28680 ke Bus.
Papan memori  tidak perlu mengetahui MMU, hanya bertanggung jawab untuk memenuhi permintaan membaca atau menulis alamat 28680.
Misalnya intruksi :
MOV REG,8192
Ditransformasi menjadi alamat fisik 20480 karena alamat 8192 terdapat di page 2 dan dipetakan ke frame 5 (alamat fisik 20480-24576).

·         10.2.1.2 Implementasi Pemetaan (Bagian Internal MMU)
Gambar 6 adalah komponen internal MMU untuk sitem paging.
Nomor page
Offset














Gambar  6 Komponen internal  MMU





Komponen terpenting MMU adalah
1. Registrasi alamat maya
2. Tabel page
3. Registri alamat fisik

Registri Alamat Maya
Menyimpan alamat maya yang diacu
Nilai di register alamat maya di bagi menjadi dua bagian,yaitu :
·         Sejumalah bit berorder tinggi menyatakan nomor page maya
·         Bit-bit sisa adalah offset alamat maya.

Tabel Page
Tiap elemen tabel sedikitnya berisi informasi berikut :
·         Present/absent bit
Bernilai satu apabila page dimemori fisik,bernilai 0 bila page tidak di memori fisik.
·         Nomor page frame dimana page berada.

Registri Alamat Fisik
Menyimpan alamat fisik yang disinyalkan ke bus.
Nilai di Register Alamat Fisik Dibagi Dua Bagian,Yaitu
·         Sejumlah bit berorder  tinggi menyatakan nomor page frame
·         Bit-bit sisa adalah offset  alamat frame.
Alamat maya dipecah menjadi  dua  yaitu
·         Nomor page maya (bit-bit berorder  tinggi)
·         Offset
Pemetaan
·         Nomor page maya digunakan sebagai indeks ke tabel page untuk menemukan isian page maya.
·         Dari isian tabel page dapat diketahui apakah page dipetakan ke memori fisik (dengan memeriksa present/absent bit)
·         Apabila alamat terdapat di memori  fisik maka isian di tabel page memuat nomor page
Frame.Nomor page frame di  tabel  page di kopi sebagai bit-bit berorder tinggi di registri alamat fisik dan di tambah offset di alamat maya.
·         Bila alamat tidak ada di memori  fisik maka MMU menerbitkan page foult.
·         MMU mengkopikan nomor page frame diisian tabel page dengan indeks nomor page  ke registri alamat fisik dan menambah dengan offset  alamat maya.







Cara kerja ini dapat dilihat pada gambar 7.



 





             

















 
















                Gambar  10-7 Cara kerja  pemetaan oleh MMU



Apabila ternyata nomor page tidak ada di memori fisik,yaitu nilai present/absent bit  di isian tabel page bernilai 0, MMU  menerbitkan page-foult.Rangkaian aksi  yang dilakukan adalah sebagai berikut :
1.      MMU memperingatkan page tidak ada di memori fisik dan pemmroses tidak melakukan  trap ke sistem operasi, disebut page-foult.
2.      Membebaskan bagian page frame memori  fisik yang jarang digunakan dengan menyimpan page frame itu ke disk.
3.      Memasukan page yang diacu ke bagian page frame yang dibebaskan.
4.      Mengkonsolidasi pemetaan antara memori maya<->memory fisik.
Ketika terjadi page foult, sistem operasi memilih frame di memori  fisikuntuk di ganti dengan page berguna yang akan masuk.
·         Jika page yang diganti telah dimodifikasi,page harus ditulis ke disk.Page yang telah dimodifikasi disebut dirty page.
·         Jika page belum diubah (misalnya page yang berisi teks biner program).kopian di disk masih up to date sehingga page tidak perlu ditulis di disk.

ii.                  Tabel-tabel Paging
Pemakaian tabel page pada sistem paging menimbulkan dua masalah utama,yaitu :
1.      Tabel page dapat berukuran lusr biasa besar
2.       Pemetaan harus dilakukan secara tepat

Tabel page dapat dapat berukuran luar biasa besar
Misalnya :
·          Register alamat maya 32 bit.
·          Ukuran page 4 Kilobyte  =  212 byte
Berarti terdapat 220 page(sejuta page lebih),yaitu
 Alamat maya 32 bit berarti memori dapat memuat 232 byte
 Karena masing-masing page adalah 212 byte  = 220 page
·         Register alamat maya 64 bit
·         Ukuran  page 4 Kilobyte
Berarti akan terdapat 242 page
Bila memori maya sangat besar  maka tidak mungkin menggunakan satu tabel tunggal  karena akan diperlukan ukuran tabel sangat besar.

Solusi
Menggunakan tabel-tabel bertingkat (serupa indeks bertingkat diterganisasi  berkas)
Beberapa rancangan tabel  paging untuk beragam sesuai sistem komputer,yaitu:
·         DEC PDP-11 menggunakan panjang satu tingkat(one-level paging)
·         DEC  VAX menggunakan paging  dua tingkat(two-level paging)
·         SUN SPARC menggunakan  paging tiga tingkat(three-level paging)
·         MOTOROLA 68030 menggunakan paging empat tingkat(four-level paging)

Pemetaan Harus Dilakukan Secara Cepat
Pemetaan  alamat  maya ke alamat fisik dilakukan setiap terjadi pengacuan memori.

Instruksi komputer biasanya berbentuk :
            Operator operand  1, operand  2,.....,operand_N
Pada tiap instruksi,setidaknya terdapat 1 atau 2 operan . Operan-operan merupakan  pengacuan ke memori karena operan disimpan di memori berarti untuk satu instruksi sedikitnya terjadi 1 sampai 2 pengacuan memori.Jika satu  instruksi memerlukan 10ns, maka pemetaan harus dilakukan  beberapa ns saja agar tidak terjadi bottleneck.

Kesimpulan
Pada pemproses dengan memori maya, pengelolaan page besar dan cepat merupakan konstrain utama perancangan dan pembangunan pemproses.

10.2.3 Memori Asosiatif
Dari observasi disimpulkan,sebagian besar program cenderung melakukan banyak pengacuan ke sejumlah kecil page (prinsip lokalitas).Sebenarnya hanya sejumlah kecil elemen tabel page yang sering dibaca.
Berdasarkan fakta ini,sistem komputer dengan memori maya dapat  memanfaatkan sifat ini untuk mempercepat proses pengacuan tanpa melibatkan tabel page.Sistem komputer dilengkapi perangkat pemetaan alamat maya ke alamat fisik tanpa lewat tabel page.Perangkat ini disebut assosiatif (associative memory)  atau  TLB(translation lookaside buffer).Perangkat ini dapat dipasang di MMU.
Memori asosiatif berisi sejumlah elemen tabel (antara 8 sampai 32 elemen) .Tiap elemen berisi  informasi-informasi mengenai page,yaitu:
·         Nomor page maya
·         Bit W, untuk mencatat apakah page telah dimodifikasi.
·         Bit-bit  proteksi
·         Nomor page frame dari page maya
·         Dan sebagainya
Mekanisme Kerja Memori Asosiatif
Jika alamat maya dikirim ke  MMU untuk penerjemahan, Perangkat keras memeriksa apakah nomor page  maya terdapat dimemori asosiatif dengan membandingkan semua isian memori asosiatif secara simultan (yaitu bersamaan atau paralel). Mekanisme paralel ini sangat mempercepat.
·         Jika ditemukan di memori asosiatif dan pengaksesan  tidak melanggar bit-bit proteksi,maka page frame langsung ditanngani memori  asosiatif tanpa melibatkan tabel page.
·         Jika page ditemukan di memori asosiatif tapi melanggar bit-bit proteksi,maka diterbitkan protection fault.Proteksi ini juga dilakukan tabel  page(bila isian tabel page dilengkapi  bit-bit  proteksi).
·         Jika nomor page maya  tidak terdapat dimemori asosiasi,maka MMU mencari di tabel page.Salah satu elemen memori asosiatif  disingkirkan dan diganti elemen tabel page yang ditemukan.Elemen yang disingkirkan   dan diganti elemen  tabel page di memori.Jika page itu kembali digunakan,maka hanya akan ditangani memori asosiatif tanpa MMU.
Rasio pengacuan memori yang hanya  melalui memori asosiatif disebut hit ratio.Semakin tinggi hit oleh :
·         Waktu akses tabel page
·         Waktu akses memori  asosiatif
·         Nilai hit-ratio
Kebanyakan sistem komputer modern dilengkapi memori asosiatif.MIPS R 2000 merupakan sistem yang  hanya mengandalkan  memori asosiatif tanpa tabel page.MIPS R2000 adalah mesin RISC berunjuk kerja tinggi.

C.      Penggantian Page
Saat terjadi page foult berarti harus diputuskan page  frame dimemori fisik yang harus digant.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 foult berulang kali.Banyaknya page foult menghasilkan banyak overhead.
Algoritma penggantian page antara lain :
1.      Algoritma penggantian page acak (random page replacement algorithm)
2.      Algoritma penggantian page optimal
3.      Algoritma penggantian page NRU
4.      Algoritma penggantian page  FIFO
5.      Algoritma penggantian  page modifikasi dari algoritma FIFO
6.      Algoritma penggantian page LRU

v  Algoritma-algoritma Penggantian Page

-           Algoritma Penggantian Page Acak
Mekanisme algoritma
Setiap terjadi  page foult,page yang diganti di pilih secara aca.
Teknik ini tidak memakai  informasi apapun dalam menetukan 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).
Teknik ini sangat buruk,percobaan menunjukan algoritma acak  menimbulkan rate terjadinya page foult yang sangat tinggi.

-            Algoritma Penggantian Page Optimal
Mekanisme algoritma
            Dasar algoritma ini adalah memilih page yang berpeluang dipakai kembali di masa datang yang paling kecil.
Strategi ini akan menghasilkan jumlah page-foult paling sedikit.Algoritma  ini  adalah algoritma utopia (ideal tanpa dapat dijadikan kenyataan) karena tak mungkin dibuat prosedur  yang  dapat mengetahui  peluang pemakaian suatu page kembali ke masa datang. Metode ini tak mungkin diterapkan.
Pendekatan ini dapat dilakukan dengan simulasi.Tapi  simulasi hanya spesifik  suatu program.Bila yang terbaik tak dimungkinkan,maka yang perlu dilakukan adalah berusaha mendekatinya.Algoritma penggantian page diusahakan  kinerjanya mendekati optimal.
Algoritma prnggantian page optimal penting untuk kajian teoretis,sebagai pembanding bagi algoritma-algoritma penggantian  page  yang  lain.

-           Algoritma Penggantian Page NRU(Not-Recently Used)
Mekanisme algoritma
            Pada algoritma ini,page diberi dua bit mencatat status page,bit R dan M,yaitu:
            Bit R :  referenced (menyatakan page sedang di acu)
                        Bit R  =  1 nerarti sedang di acu
                        Bit R =  0 berarti tidak sedang di acu
            Bit M  : modified  (menyatakan page telah dimodifikasi)
                        Bit M  = 1 berarti dimodifikasi
                        Bit M  =  0 berarti tidak  dimodifikasi
            Dengan 2 bit,maka page-page dikelompokkan menjadi  4 kelas page,yaitu
                        Kelas 0 : Tidak sedang diacu,belum dimodifikasi  (R=0, M=0)
                        Kelas  1 : Tidak sedang diacu,telah dimodifikasi  (R=0, M=1)
                        Kelas  2 : Sedang diacu,belum dimodifikasi (R=1, M=0)
                        Kelas  3 : Sedang diacu,telah dimodifikasi (R=1, M=1)
·         Memilih mengganti page kelas bernomor  terendah(bila terdapat page-page di kelas itu)secara acak.
·         Bila kelas tersebut kosong maka dipilih page di kelas lebih tinggi, dan seterusnya.
Algoritma ini mengasumsikan kelas-kelas bernomor lebih rendah baru akan digunakan kembali dalam waktu relatif lama.
Algoritma ini mudah dipahami dan diimplementasikan.Implementasi  algoritma ini sangat  efisien karena  tak banyak langkah dalam pemilihan page.Algoritma ini memenag tidak optimal,tapi dalam kondisi-kondisi normal telah memadai .

-           Algoritma Penggantian Page FIFO (First-In,First-Out)
Mekanisme algoritma
            Algoritma ini memerlukan pengelolaan senarai page di memori.Elemen terdepan senarai
adalah page tertua dan ujung belakang adalah page paling akhir datang.
·         Bila terjadi  page foult ,page elemen terdepan (page tertua) di ganti dan  page baru ditambahkan di ujung belakang senarai .

-          Modifikasi Terhadap FIFO
Kelemahan FIFO adalah algoritma dapat memilih memindahkan page yang sering digunakan yang lama berada di memori.
Variasi FIFO yaitu :
1.      Algoritma pergantian page kesempatan kedua.
Mekanisme algoritma :
·         Saat terjadi page-fault, algoritma 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.
2.      Algoritma penggantian clock-page.
Mekanisme algoritma :
·         Pada algoritma ini, semua page merupakan senarai melingkar membentuk pola jam.
Ketika terjadi page fault, page yang ditunjuk diperiksa.
·         Jika bit R bernilai 0 maka page diganti. Page baru ditempatkan di tempat page diganti dan penunjuk dimajukan satu posisi ke page berikutnya.
·         Jika bit R bernilai 1 maka bit R diseret menjadi 0 dan penunjuk dimajukan satu posisi dan seterusnya sampai menemui page dengan bit R bernilai 0.
Kedua algoritma adalah hanya terdapat perbedaan di implementasi, yaitu ;
·         Algoritma penggantian page kesempatan kedua menggunakan senarai lurus tidak sirkular, sedangkan clock page menggunakan senarai sirkular.

-          Algoritma Penggantian Page LRU(Least Recently Used).
Mekanisme algoritma :
Algoritma LRU adalah ketika terjadi page fault maka memindahkan page yang tidak digunakan paling lama.
Masalah : sangat mahal. Yaitu disebabkan harus mengelola senarai informasi seluruh page di memori.

-          Contoh Eksekusi Paging
Algoritma penggantian page optimal (6 Fault)
String pengacuan

2
3
2
1
5
2
4
5
3
2
5
2


2
2
2
2
2
2
4
4
4
2
2
2


3
3
3
3
3
3
3
3
3
3
3




1
5
5
5
5
5
5
5
5
Fault

F
F

F
F

F


F


Algoritma penggantian page LRU (7 Fault)
String pengacuan

2
3
2
1
5
2
4
5
3
2
5
2


2
2
2
2
2
2
2
2
3
3
3
3


3
3
3
5
5
5
5
5
5
5
5




1
1
1
4
4
4
2
2
2
Fault

F
F

F
F

F

F
F



Algoritma penggantian page FIFO (9 Fault)
String pengacuan

2
3
2
1
5
2
4
5
3
2
5
2


2
2
2
2
5
5
5
5
3
3
3
3


3
3
3
3
2
2
2
2
2
5
5




1
1
1
4
4
4
4
4
2
Fault

F
F

F
F
F
F

F

F
F

Algoritma penggantian clock page (6 Fault)
String pengacuan

2
3
2
1
5
2
4
5
3
2
5
2

2
2
2
>2*
2*
2*
>2*
>2*
>2
>2*
>2*
>2*

3
3
3
5
5
5
5*
5
5
5*
5*


1
>1
>1
4
4
3
3
3
3
Fault

F
F

F
F

F

F



Keterangan :   * diacu
                        >ditunjuk pointer

Memodelkan Algoritma Paging

Anomaly belady
Belady menemukan fenomena menyimpang dari prasangka umum yaitu pada algoritma FIFO maka pada pola-pola pengacuan tertentu menyebabakan lebih banyak page fault bila alokasi page untuk proses ditambah. Fenomena ini disebut anomal belady.
Fenomena dapat diilustrasikan sebagai berikut :
·         Program dengan lima page
·         Urutan page yang diacu : 0 1 2 3 4 0 1 4 0 1 2 3 4

String pengacuan

0
1
2
3
4
0
1
4
0
1
2
3
4



0
1
2
3
0
1
4
4
4
2
3
3



0
1
2
3
0
1
1
1
4
2
2




0
1
2
3
0
0
0
1
4
4
Fault

F
F
F
F
F
F
F
F


F
F


(a)


String pengacuan

0
1
2
3
4
0
1
4
0
1
2
3
4



0
1
2
3
3
3
4
0
1
2
3
4



0
1
2
2
2
3
4
0
1
2
3




0
1
1
1
2
3
4
0
1
2





0
0
0
1
2
3
4
0
1
Fault

F
F
F
F
F
F
F
F


F
F


(b)
·         Gambar (a) dengan tipe page frame menghasilkan 9 fault.
·         Gambar (b) dengan empat page frame menghasilkan 10 fault.

v  Mesin abstrak eksekusi program
Terdapat mesin abstrak interpreter dengan property berikut :
1.      Terdapat array internal, M, menyimpan status memori. Array mempunyai n elemen seperti proses mempunyai n page memori maya.
2.      Array M terbagi 2 :
·         Bagian atas/puncak, yaitu m isian, page dimemori tujuan.
·         Bagian bawah/dasar berisi n-m isian, yaitu semua page yang pernah diacu sekali tapi telah dipindahkan dan tidak dimemori utama.
3.      Mualanya 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 isian bagian puncak array M).
Contoh :
1.      String pengacuan : 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1
2.      Ruang alamat maya : 8 page
3.      Algoritma penggantian dengan LRU
String pengacuan

0
2
1
3
5
4
6
3
7
4
7
3
3
5
5
3
1
1
1
7
2
3
4
1


0
2
1
3
5
4
6
3
7
4
7
3
3
5
5
3
1
1
1
7
2
3
4
1


0
2
1
3
5
4
6
3
7
4
7
7
3
3
5
3
3
3
1
7
2
3
4



0
2
1
3
5
4
6
3
3
4
4
7
7
7
5
5
5
3
1
7
2
3




0
2
1
3
5
4
6
6
6
6
4
4
4
7
7
7
5
3
1
7
2





0
2
1
1
5
5
5
5
5
6
6
6
4
4
4
4
5
5
1
7






0
2
1
1
1
1
1
1
1
1
1
6
6
6
6
4
4
5
5







0
0
2
2
2
2
2
2
2
2
2
2
2
2
6
6
6
6









0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Fault

F
F
F
F
F
F
F

F




F


F





F











Model ini mempunyai property yaitu :
1.      Ketika page diacu, selalu dipindahkan ke isian puncak dari array M.
2.      Jika page yang diacu ada di M, semua page diatasnya dipindah satu posisi ke bawah. Transisi dari dalam kotak ke luar berkorespondensi dengan page dipindahkan dari memori.
3.      Page-page yang dibawah page yang diacu, tidak dipindakhan.
Jika kita tingkatkan ukuran memori dengan satu page maka setelah proses dieksekusi kembali pada setiap titik eksekusi yang sama, semua page pada eksekusi pertama juga terdapat pada eksekusi kedua dengan satu tambahan page. Algoritma




D.  Masalah-Masalah Utama Pada System Paging

1.      Working set model
a)      Prinsip lokalitas
Suatu proses-proses yang cenderung mengacu penympanan secara tak seragam, mempunyai pola-pola sangat setempat.
Ada 2 jenis lokalitas yaitu :
1.      Lokalitas berdasar waktu
Lokalitas berdasar waktu adalah proses cenderung terkonsentrasi acuannya ke satu interval waktu eksekusi yang dekat. Observasi berikut mendukung prinsip :
·         Looping
·         Subrutin
·         Stack dan variable-variabel yang digunakan untuk iterasi dan penjumlahan total.
2.      Lokalitas berdasar ruang
Lokalitas berdasar ruang adalah proses cenderung terkonsentrasi acuannya ke satu kelompok data yang berdekatan. Observasi berikut mendukung prinsip ini :
·         Traversal pada array
·         Eksekusi kode yang sekuen
·         Kecenderungan pemrogram menempatkan variable yang terkait saling berdekatan.

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

2.      Working set of program behavior
Himpunan kerja secara informal didefiisikan sebagai kumpulan page proses yang secara aktif diacu. Dennnig 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 hanya beberapa instruksi terjadi page fault.


Himpunan kerja dari program pada satu waktu pada pengacuan memori ke-t adalah :
W(t,θ) + {i € N | page I muncul pada rt-0+1, …, rt}
Dimana : rt menyatakan pengacuan memori saat t.
   W(t,θ) himpunan page yang diacu selama θ pengacuan memori terakhir.
Dengan kata lain, himpunan kerja adalah himpunan page yang diacu dalam jendela ukuran θ yang dibentuk menurut waktu. Begitu program dieksekusi, ukuran himpuanan kerja dan identitas page beragam menurut waktu.


3.     Prinsip-prinsip Working Set Model

Prinsip yang digunakan adalah melacak dan menjamin himpunan kerja terdapat di memori sebelum proses dijalankan. Cara ini mengurangi terjadinya page fault.
Prinsip-prinsip himpunan kerja :
1.      Program seharusnya dijalankan jika dan hanya jika himpunan kerja berada di memori.
2.      Page tidak boleh dipindahkan dari memori jika page anggota himpunan kerja dari program yang running.
Berdasarkan hal ini terdapat dua teknik untuk memuat page, yaitu :
·         Prepaging adalah teknik memuatkan page-page lebih dulu sebelum prose berjalan.
·         Demand paging adalah teknik yang segera memuatkan page begitu page dibutuhkan.

  1. Apabila ternyata nomor page tidak ada dimemori fisik, yaitu nilai present/absent bit di isian table page bernilai 0, MMU menerbitkan page-fault. Rangkain aksi yang dilakukan adalah sebagai berikut :
1.      MMU memperingkatkan page tidak dipetakkan ke memori fisik dan pemroses melakukan trap ke sisitem operasi, disebut page fault.
2.      Membebaskan bagian page frame memori fisik yang jarang digunakan dengan menyimpan page frame itu ke disk.
3.      Mengkonsolidasikan pemetaan antara memori maya « memory fisik.
Ketika terjadi page fault, system operasi memilih frame di memori fisik untuk diganti page berguna yang akan masuk.
·         Jika page yang diganti telah dimodifikasi, page harus ke disk. Page yang telah dimodifikasi disebut dirty page.
·         Jika page belum diubah (misalnya page yang berisi teks biner progam), kopian di disk masih up to date sehingga page tidak perlu ditulis ke disk.
Tabel – tabel Paging
pemakaian tabel page pada system paging menimbulkan dua masalah utama, yaitu:
1.      Tabel page dapat berukuran luar bias besar.
2.      Pemetaan harus dilakukan secara cepat.
Tabel page dapat berukuran luar biasa besar
            Misalnya
·         Register alamat mya 32 bit
·         Ukuran page 4 Kilobyte = 212 byte
Berarti terdapat 220 page (sejuta page lebih), yaitu alamat maya 32 bit berarti memori dapat memuat 232 byte karena masing – masing page adalah 212 byte. Berarti jumlah page adalah 232 dibagi 212 = 220 page.
·         Register alamat mya 64 bit.
·         Ukuran page 4 Kilobyte, berarti akan terdapat 242 page.
Bial memori mya sangat besar maka tidak mungkin menggunakan satu tabel tunggal karena akan diperlukan ukuran tabel sangat besar.
Solusi
Menggunakan tabel – tabel bertingkat (serupa indeks bertingkat di organisasi berkas).
Beberapa rancangan tabel paging untuk beragam sesuai system komputer, yaitu:
·         DEC PDP-11 menggunakan paging satu tingkat (one-level paging)
·         DEC VAX menggunakan paging dua tingkat (two-level paging)
·         SUN SPARC menggunakan paging empat tingkat (four-level paging)
Pemetaan Harus Dilakukan Secara Cepat
Pemetaan alamat maya ke alamat fisik dilakukan setiap terjadi pengacuan memori.
Intruksi computer biasanya berbentuk:
            Operator operand_1, operand_2,…,operand_N

Pada tiap intruksi, setidaknya terdapat 1 atau 2 operan, operan – operan merupakan pengacuan ke  memori karena operan disimpan di memori berarti untuk satu interaksi setidaknya terjadi 1 sampai 2 pengacuan memori. Jika satu intruksi memerlukan 10 ns, maka pemetaan harus dilakukan beberapa ns saja agar tidak terjadi bottleneck.
Kesimpulan
Pada pemroses dengan memori maya, pengelolaan page besar dan cepat merupakan konstrain utama perancangan dan pembangunan pemroses.

Memori Asosiatif
Dari obsevasi disimpulkan, sebagian besar program cenderung melakukan banyak pengacuan ke sejumlah kecil page (prinsip lokalits). Sebenarnya hanya sejumlah kecil elemen tabel page yang sering dibaca.
Berdasarkan fakta ini, system komputer dengan memori maya dapat memanfaatkan sifat ini untuk mempercepat proses pengacuan tanpa melibatkan tabel page. Sistem komputer dilengkapi perangkat pemetaan alamat maya ke alamat fisik tanpa lewat tabel page. Perangkat ini disebut memori asosiatif (associative memory) atau TLB (translation lookasiade buffer). Perangkat ini dapat dipasang di MMU.
Memori asosiatif berisi sejumlah elemen tabel (antara 8 sampai 32 elemen). Tiap elemen berisi informasi – informasi mengenai page, yaitu:
·         Jika ditemukkan dimemori asosiatif dan pengaksesan tidak melanggar bit-bit proteksi, maka page frame langsung ditangani memori asosiatif tanpa melibatkan tabel page.
·         Jika page ditemukan di memori asosiatif tapi melanggar bit-bit proteksi, maka diterbitkan protection fault. Proteksi ini juga dilakukan tabel page (bila isian tabel page dilengkapi bit-bit proteksi).
·         Jika nomor page maya tidak terdapat di memori asosiasi, maka MMU 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 page itu kembali digunakan, maka hanya akan ditangani memori asosiatif tanpa MMU.
Rasio pengacuan memori yang melalui memori asosiatif disebut hit ratio. Semakin tinggi hit ratio, semakin bagus kinerja system. Dengan memori asosiatif maka kinerja rata-rata system dipengaruhi oleh
·         Waktu akse tabel page.
·         Waktu akses memori asosiatif.
·         Nilai hit-ratio.

Penggantian Page
Saat terjadi page fault berarti harus diputuskan page frame di memori fisik yang harus diganti. Kinerja system 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 banyak overhead.
Algoritma penggantian page anta lain:
  1. Algoritma penggantian page acak (random page replacement algorithm)
  2. Algoritma penggantian page optimal
  3. Algoritma penggantian page NRU
  4. Algoritma penggantian page modifikasi dari algoritma FIFO
  5. Algoritma penggantian page LRU

Algoritma – algoritma Penggantian Page
  1. Algoritma Penggantian page acak
Mekanisme algoritma
            Setiap terjadi page fault, page yang diganti dipilih secara acak.
Teknik ini tidak memakai informasi apapun dalam menentukan page yang diganti. Semua page di memori utama mempunyai bobot sama untuk dipilih. Teknik ini dapat memilih sembarang page, termasuk page yang sedang diacu (page yang seharusnya tidak diganti, pilihan terburuk).
Teknik ini sangat buruk, percobaan menunjukkan algoritma acak menimbulkan rate terjadinya page fault yang sangat tinggi.
  1. Algoritma Penggantian Page Optimal
Mekanisme algoritma
            Dasar algoritma ini adalah memilih page yang berpeluang dipakai kembali di masa datang yang paling kecil. Strategi ini akan menghasilkan jumlah page fault paling sedikit. Algoritma ini adalah algoritma utopia (ideal tanpa dapat dijadikan kenyataan) karena tak mungkin dibuat prosedur yang dapat mengetahui peluang pemakaian suatu page kembali di masa datang. Metode ini tak mungkin diterapkan.
Pendekatan ini dapat dilakukkan dengan simulasi. Tapi, simulasi hanya spesifik suatu program. Bila yang terbaik tak dimungkinkan, maka yang perlu dilakukan adalah berusaha mendekatinya. Algoritma penggantian page diusahakan kinerjanya mendekati optimal. Tiap algoritma penggantian page mengumpulkan dan memakai  informasi untuk menentukan page yang diganti sehingga mendekati optimal.
Algoritma penggantian page optimal penting untuk kajian teoretis, sebagai pembanding bagi algoritma-algoritma penggantian page yang lain.

  1. Algoritma Penggantian Page NRU (Not-Recentli Used)
Mekanisme algoritma
            Pada algoritma ini, page diberi dua bit mencatat status page, bit R dan M yaitu:
            Bit R : referenced (menyatakan page sedang diacu)
                        Bit R = 1 berarti sedang diacu
                        Bit R = 0 berarti tidak sedang diacu
            Bit M : modified (menyatakan page dimodifikasi)
                        Bit M = 1 berarti dimodifikasi
                        Bit M = 0 berarti tidak dimodifikasi
            Dengan 2 bit, maka page-page dikelompokkan menjadi 4 kelas page, yaitu:
                        Kelas 0 : tidak sedang diacu, belum dimodifikasi (R=0,M=0)
                        Kelas 1 : tidak sedang diacu, telah dimodifikasi (R=0, M=1)
                        Kelas 2 : sedang diacu, belum dimodifikasi (R=1, M=0)
                        Kelas 3 : sedang diacu, telah dimodifikasi (R=1, M=1)
·         Memilih menggantikan page kelas bernomor terendah (bila terdapat page-page di kelas itu) secara acak.
·         Bila kelas tersebut kosong maka dipilih page di kelas lebih tinggi, dan seterusnya.
Algoritma ini mengansumsikan kelas-kelas bernomor lebih rendah akan baru akan digunakan kembali dalam waktu relative lama.
Algoritma ini mudah dipahami dan diimplementasikan. Implementasi algoritma ini sangat efisien karena tak banyak langkah dalam pemilihan page. Algoritma ini memang tidak optimal, tapi dalam kondisi-kondisi normal telah memadai.
  1. Algoritma Penggantian Page FIFO (First-In, First-Out)
Mekanisme algoritma
            Algoritma ini memerlukan pengelolaan senarai page di memori. Elemen terdepan senarai adalah page tertua dan ujng belakang adalah page paling akhir datang.
·         Bila terjadi page fault, page elemen terdeoan (page tertua) diganti dan page baru ditambahkan di ujung belakang senarai.
Dengan hanya informasi mengenai lam berada di memori, maka algoritma ini dapat memindahkan page yang sering digunakan. Boleh jadi page itu berada terus di memori karena selalu selalu digunakkan. Page itu karena mengikuti pola antrian berdasar lamanya berada dimemori menjadi elemen terdepan, diganti dan segera harus masuk kembali ke memori sehingga terjadi page fault kembali. Algoritma FIFO murni jarang digunakan, tetapi dikombinasikan (modifikasi).
  1. Modifikasi Terhadap FIFO
Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering digunakan yang lama berada di memori. Kemungkinan ini dapat dihindari dengan hanya menindahkan page tidak diacu. Page ditambah bit R mencatat apakah page diacu atau tidak. Bit R bernilai 1 bila diacu dan bernilai 0 bila tidak diacu.
Variasi dari FIFO anatara lain:
·         Algoritma penggantian page kesempatan kedua (second chance page replacement algorithm)
·         Algoritma penggantian clock page (clock page replacement algothm)
Algoritma Penggantian Page Kesempatan Kedua
Mekanisme algoritma
·         Saat terjadi page fault, algoritma memilih page elemen terdepan bila bit R bernilai 0.
·         Bila bit R bernilai1, maka bit page terdepan senarai diseret menjadi 0 dan diletakkan ke ujung belakang senarai. Mekanisme ini kembali diterapkan ke elemen berikutnya.
Algoritma Penggantian Clock Page
Algoritma penggantian page kesempatan kedua merupakan algoritma yang memadai tapi tidak efisien karena memindahkan page-page di senarainya. Algoritma penggantian clock page merupakan perbaikkan algoritma pertama.
Mekanisme algoritma
·         Pada algoritma ini, semua page merupakan senarai melingkar membentuk pola jam. Terdapat petunjuk (pointer) ke pege tertua.
Ketika terjadi page fault, page yang ditunjukkan diperiksa.
·         Jika bit R bernilai 0, maka [age diganti. Page baru ditempatkan ditempat page diganti, dan petunjuk dimajukkan satu posisi ke page berikutya.
·         Jika bit R bernilai 1, maka bit R diseret menjadi 0, dan penunjuk dimajukan satu posisi. Seterusnya sampai menemui pae dengan bit R bernilai 0.
Kedua algoritma adalah sama, hanya berbeda dalam implementasi, yaitu:
·         Algoritma penggantian page kesempatan kedua menggunakkan senarai lurus tidak sirkular.
·         Algoritma penggantian clock page menggunakan senarai sirkular.

  1. Algoritma Penggantian Page LRU (Leadt Recently Used)
Berdasarkan observasi, page-page pada beberapa intruksi terakhir berkemungkinan besar akan dipakai kembali. Page – page yang lama tidak digunakkan akan tetap tidak digunakkan dalam waktu lama.
Mekanisme algoritma
            Algoritma LRU adalah ketika terjadi page fault maka memindahkan page yang tidak digunakkan paling lama.
Masalah
·         Sangat mahal
Kemahalan disebabkan harus mengelola senarai informasi seluruh page di memori. Senarai harus terurut berdasar kemutakhiran penggunaan. Senarai harus diperbarui setiap terjadi pengacauan memori. Begitu terjadi pengacuan memori, harus dilakukan opersi menemukan page di senarai, dipindahkan sebagai terdepan yaitu paling mutakhir diacu. Meskipun ini memerlukan waktu yang sangat banyak.
Contoh Eksekusi Paging
Algoritma Penggantian Page Optimal
Siste, pengacuan          2 3 2 1 5 2 4 5 3 2 5 2
                                    2 2 2 2 2 2 4 4 4 2 2 2
                                       3 3 3 3 3 3 3 3 3 3 3
                                             1 5 5 5 5 5 5 5 5
                        Fault    F F   F F    F       F        6 Fault
SISTEM PANGING  DAN KOMBINASI
PAGING –SEGMENTASI

Menyedrhanakan Penanganan Struktur Data yang Berkembang
Kompilasi Ulankg Indepanden Tanpa Menautkan Kembali (relink) Seluruh Program
Tehnik ini memungkinkan program-program dikompilasi  ulang  secara independen tanpa perlu men-tautkan kembali seluruh program yang dimuatkan kembali.
Memudahkan Pemakaian memory Bersama diantara Proses – Proses
Tehnik inin memudahkan pemakaian memory bersama diantara proses-proses.Program dapat mendapatkan program ulitilitas atau table data berguna disegmen  yang dapat diacu oleh proses –proses lain.Segemntasi memberi fasilitas pemakaian bersama terhadap prosedur dan data untuk beberapa proses,berupa shared library.
Memudahkan Untuk Proteksi
Karena segmedapat dikonstruksikan berisi sekumpulan procedur atau data terdefinisi baik,program atuau administrator system dapat memberikan kewenanagn pengaksesan secara nyaman.

A.     Segemntasi Secara Mruni
Segmen-segmen dapat berukuran berbeda-beda dan dinamis.Pengacauan –pengacauan memoru berbetuk (nomor segmen,offside).Alamat maya adalah disegmen.Tiap proses mempunyai  table segmen.Ketika proses Running,alamat awal table dimuat ke register dasar  .Nomor segmen digunakan untuk mencari dikriptor segmen di table segmen yang menyediakan alamat fisisk awal segmen,panjangnya  dan bit-bit proteksi.Alamt fisik dihitung dengan menambahkan alamat dasar segmen ke almamat maya.
B.     Pebandinajgan Antara Paging dan Segmentasi.
Perbandingan mengenai  t eknik paging dan segmentasi (TAN-92).
Pertimbangan
Paging
Segmentasi
Perlunya program menyadari bahwa teknik ini daipakai.?
TIDAK
YA
Berapa banyak ruang alamat linear yang terdapat.?
1
BANYAK
Dapatkah total ruang alamat melampauai ukuran memori fisisk.?
TIDAK
YA
Dapatkah prosedur dan data diproteksi secara terpisah.?
TIDAK
YA
Dapatkah table-tabel yang mempunyai ukuran daiakomodasikan dengan mudah.?
TIDAK
YA
Apakah pemakaian bersama prosedur-prosedur antara pemakai difasilitasi.?
TIDAK
YA
Kenapa teknik ini ditemukan.?
Untuk mendapatkan alamat linear tanpa
Untuk memungkinkan.

C.            Teknik Kombinasi Paging

Teknik kombinasi paging 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 segipandangan 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 menggunakanbagian nomor segment untuk mengindeks tabel segment proses guna menemukan tabel page untuk segment.
D.     Contoh Sistem Paging dengan Memory Maya
I.                    Memory Maya dengan Segmentasi Murni
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.
Description: https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhvM8OGhH3jOQu2wmVIi_60ejN7R03yw09zbzrykJz4ypBsNSk17We8FvWZQZ_-9eeStQKhqkfkh7mUb_y6IYAcOfrO7uI4KCzoJk4GRDJp9_BU1e0smLFWWU_x0fLeRK1CJD3Gq3CGkFHX/s400/21.jpg
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.
II.                 One Level Paging
Nomor page maya digunakan sebgai index ke table page (page table ) yang biasanya berlokasi di memory utama.Isian table page berisi nomor page fisik dan bit-bit proteksi .Offset pada page fisik sama dengan offset pada page maya.Dalam beberapa kasus ,register panjang digunakan untuk menetapakn akhir tabeluntuk menghindari runag yang disediakan.
Keunggulan
Semua bentuk paging mengeliminasi frakmentasi external dan menyederhanakan alokasi dan pertumbuhan dinamis.
Kelemahan
Sejumlah besar ruang memory utama harus dicadangkan untuk table page sehingga menyediakan ruang alamat memory maya besar dengan page-page yang berukuran tertentu.Alokasi dan pertumbuhan dinamis table page besar dapat menjasdi masalah karena harus kontigu memory.
III.               Two Level Paging
Keunggulan
Mekanisme inimengkombinasikan keunggulan segmentasi  dan paging.Pemakaian bersama dapat dilakukan dilevel segmen ,mereduksi kebutuhan isian-isian table page yang redudan .Tabel-tabel page tidak perlu berada dimemory utama dan tidak perlu kontigu dimemory utama .Hal ini memungkinkan alokasi dan pertumbuhan table page yang sederhana dan memungkinkan menggunakan ruang alamat  maya yang elatif besar.
Kelemahan
Ruang alamat maya sangat besar  memerlukan jumlah ruang besar table segmen harus disimpan dimemory utama dan harus kontigu.Hal ini membuat alokasi pertumbuhan dinamis tabek segmen menjadi sulit.
IV.              Three Level Paging
Keunggulan
Mekanisme table page banyak tingkat untuk implementasi memory maya dengan ruang alamat sangat besar.Tabel page banyak tingkat memrlukan table-tabel page besar.Implementasi ruang memory maya sangat besar  dengan table tidak terlalu banyak.
V.                 Four Level Paging
Keunggulan
Mekanisme inin berguna untuk program yang menggunakan ruang alamat memory yang sangat besar.Program LISP besar yang secara kintinyu mengalokasikan dan melepaskan daerah memory adalah tipe aplikasi yang cocok dengan mekanisme ini.Tabel-tabel ini dapat dipandang sebagai  pohon  yang hanya berisi cabang – cabang yang diperlukan untuk mencapai yang sesungguhnya digunkan di tiap level.Cara ini mereduksi jumlah ruang untuk tabel-tabel  . Semua tabel kecauli table root dapat disimpan di disk.Biasanya ,table individu tidak lebih besar disbanding satu page,alokasi dan pertumbuhan dinamis table-tabel page adalah mudah.
Kelemahan
Kondisi terburuk  yang mungkin adalh kondisi unutk translasi memerlukan sebanyak empat pengacuan memory ,masing-masing menghasilakn page fault .Karena kebanyakan page hanya memiliki beberapa isian ,table-tabel akan mempunyai fragmentasi internal sangat besar.










0 komentar:

Posting Komentar

Share

Twitter Delicious Facebook Digg Stumbleupon Favorites