Sistem Paging dan Algoritma Paging

I. SISTEM PAGING

A.  DEFINISI SISTEM PAGING

Sistem Paging Adalah sistem manajemen pada sistem operasi dalam mengatur program yang sedang berjalan. Program yang dijalankan harus dimuat di memori utama. Masalah muncul ketika program lebih besar dibanding di memori utama yang tersedia. Terdapat dua solusi masalah ini,yaitu :

1.      Overlay

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

2.      Memori Maya (Virtual Memory)

Memori maya adalah kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Memori maya dapat dilakukan pada sistem multiprogramming.

B. HAL-HAL YANG BERKAITAN DENGAN SISTEM PAGING

Istilah-istilah pada Sistem Paging :

1.      Alamat Maya (Virtual Address)

Adalah alamat yang dihasilkan perhitungan menggunakan index register, base register,segment regoster dan sebagainya.

2.      Alamat nyata (real Address)

Alamat maya adalah alamat utama di memori fisik.

3.      Page

Page adalah unit terkecil virtual address space

4.      page frame

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

5.      Page fault

Page fault adalah exception untuk permintaan alokasi page ke memori. Dalam konteks memori maya, page fault sering juga disingkat fault.

6.      MMU (Memory Management Unit)

MMU berfungsi :

·         Pemetaan memori maya ke memori fisik

·         Bila alamat memori yang diminta tidak tersedia di memori fisik, MMU menerbitkan exception adanya page fault yang melewatkan ke sistem operasi untuk menanganinya.

Untuk menginplementasikan addres maya yang besar ke dalam memori yang kecil diperlukan index register, base register, segment register dan MMU ( Memory Menegement Unit ).

C.MASALAH YANG TERJADI PADA PAGING

a. Masalah Utama Sistem Paging

 1.  Working Set Model

·         Prinsip Lokalitas

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

·         Working set 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 trashing, yaitu setelah hanay beberapa intruksi terjadi page fault.

Prinsip yang digunakan oleh Working Set Model ini adalah dengan melacak dan menjamin himpunan kerja terdapat di memori sebelum proses dijalankan. Cara ini mengurangi terjadinya page fault.

    2.  Kebijaksanaan penggantian lokal vs global

Terdapat dua pendekatan untuk mengganti page, yaitu :

·         Penggantian lokal adalah page yang dipilih untuk diganti hanya pada partisi dimana proses diletakkan.

·         Penggantian global adalah page yang dipilih untuk diganti adalah tempat kosong dengan tidak memperdulikan partisi proses.

3.   Frekuensi page fault

Frekuensi terjadinya page fault dapat dikendalikan dengan algoritma PFF (Pafe Fault Frequency Algorithm).

4.      Ukuran page

Ukuran page ditentukan perancang sistem operasi. Ukuran page harus ditentukan agar sistem berperilaku opimal. Penentuan ukuran page memerlukan penilaian dan pemahaman mendalam perangkat keras, perangkat lunak dan aplikasi sistem.

b. Masalah Implementasi Sistem Paging

1.Back-up Intruksi

Bila terjadi page fault berarti sebgaian intruksi telah dijalankan. Pengkopina program counter dan informasi register-register pemroses harus dilakukan. Setelah pergantian page selesai maka intruksi yang menyebabkan page fault dapat dijalankan kembali dengan konteksnya.

Masalah yang harus diatasi adalah untuk mengulangi intruksi, sistem harus menetukan byte pertama intruksi.

 2. Buffer Perangkat Masukan / Keluaran (Penguncian Page)

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

·         Buffer perangkat masukan / keluaran ikut tergusur

·         Adanya buffer satu perangkat masukan / keluaran menjaid rangkap.

3.Pemakaian Page Bersama

Apabila beberapa pemakai menggunakan program yang sama maka terjadi perngakapan page (page yang sam aterdapat di banyak bagian di memori). Lebih efisien menggunakan page secara bersama, menghindari keharusan mempunyai copyan-copyan page yang sama di saat yang sama.

4.Backing Store
Masalah lain adalah menyangkut dimana diletakkan page yang keluar dari memori utama. Terdapat dua algoritma untuk mengatasi hal ini, yaitu :

·         Menggunakan ruang ganti khusus

·         Dialokasikan berdasarkan kebutuhan

5.Paging Daemon
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, pag eharus ditulis terlebih dahulu ke disk.

Untuk menjamin pasokan (supply) page frame yang banyak, sistem paging biasanya mempunyai proses background, disebut Paging Daemon.

6.Penanganan Page Fault (Page Fault Handling)
Implementasi sistem paging harus mengatasi rincian aksi yang harus dilakukan saat terjadi page fault.

 II. ALGORITMA SISTEM PAGING

1. Pengertian tentang Algortima Pengganti Page Acak

Dari segi mekanisme algoritma tersebut, setiap akan timbul page fault, page yang diganti dengan pilihan secara acak. Untuk segi tekniknya sendiri pun algoritma ini tidak usah perlu menggunakan informasi dalam menentukan page yang diganti, didalam memory utama itu sendiri sudah mempunyai bobot yang sama untuk dipilih, karena teknik ini dapat dipakai untuk memilih page sembarang. Termasuk page yang sudah dipilih dengan benar-benar  / page yang tidak seharusnya diganti.

Contoh gambar dari Algoritma page acak

2. Pengertian tentang Algoritma Pengganti Page Optimal

Pengertian dari algoritma ini sendiri yaitu algoritma yang page nya paling optimal. Untuk prinsip dari algoritma ini sangat efisien sekali karena hanya mengganti halaman yang sudah tidak terpakai lagi dalam jangka waktu lama sehingga page fault yang terjadi akan berkurang dan terbebas dari anomali Belady  Selain itu juga page fault dari algoritma ini memiliki rate paling tinggi dari algoritma lainnya dari semua kasus, akan tetapi tidak belum bias disebut sempurna karena sulit untuk di mengerti dan dari segi system pun belum tentu bisa mengetahui page untuk berikutnya tetapi dapat di simulasikan hanya untuk suatu program. Untuk intinya gunakanlah hingga mendekati page optimal agar bisa memanfaatkannya.

 

Contoh gambar dari Algoritma page optimal

3. Pengertian tentang Algoritma Page NRU (Not-Recently Used)

Untuk mekanisme dari algoritma ini diberi dua bit untuk mencatat status page, diantaranya bit M dan R yaitu :

Bit M : Page yang telah dimodifikasi
Bit M = 0 berarti tidak dimodif
Bit M = 1 berarti sudah dimodif

Bit R : Page yang sedang dipacu / referenced
Bit R = 1 berarti sedang di acu
Bit R = 0 berarti tidak sedang di acu

Adanya dua bit di atas maka akan dapat dikelompokkan menjadi 4 kelas page, yaitu :
Kelas 0 => Tidak sedang di acu / belum di modif (R=0, M=0)
Kelas 1 => Tidak sedang di acu / telah di modif (R=0, M=1)
Kelas 2 => Sedang di acu / belum di modif (R=1, M=0)
Kelas 3 => Sedang di acu / telah di modif (R=1, M=1)

Jadi apabali algoritma ini diasumsikan kelas-kelas bernomor lebih rendah baru akan di gunakan kembali dalam relatif jangka waktu lama.
Intinya algoritma ini mudah dipahami dan dikembangkan karena sangat efisien walaupun tak banyak langkah dalam pemilihan page dan kelemahannya juga tidak optimal tapi dalam kondisi normal yang memadai.

4. Pengertian tentang Algoritma page FIFO (First In First Out)

Inti dari algoritma ini adalah simple / paling sederhana karena prinsipnya sama seperti prinsip antrian tak berprioritas. Page yang masuk terlebih dahulu maka yaitu yang akan keluar duluan juga. Untuk algoritma ini menggunakan structure data stack. Jadi kerjanya yaitu dimana kalau tidak ada frame yang kosong saat terjadi page fault maka korban yang dipilih adalah frame dengan stack paling bawah seperti hal nya halaman yang sudah lama tersimpan didalam memory maka dari itu algoritma ini juga bisa memindahkan page yang sering digunakan.

 

Contoh gambar dari Algoritma page FIFO

Utamanya algoritma ini di anggap cukup mengatasi pergantian page sampai pada tahun 70-an, pada saat itu juga Belady menemukan keganjalan pada algoritma ini dan dikenal dengan anomali Belady. Anomali Belady itu sendiri ialah keadaan dimana page fault rate meningkat seiring dengan pertambahannya jumlah frame.

 

Contoh gambar dari Anomali Belady

5. Pengertian tentang Algoritma page Modifikasi FIFO

Algoritma FIFO murni jarang digunakan, tetapi dikombinasikan (modifikasi).

Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering digunakan yang lama berada di memori. Kemungkinan ini dapat dihindari dengan hanya memindahkan 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 antara lain:
– Algoritma penggantian page kesempatan kedua (second chance page replacement algorithm)
-Algoritma penggantian clock page (clock page replacement algorithm)

Algoritma yang pertama adalah algoritma second chance. Algoritma second chance berdasarkan pada algoritma FIFO yang disempurnakan. Algoritma ini menggunakan tambahan berupa reference bit yang nilainya 0 atau 1. Jika dalam FIFO menggunakan stack , maka second chance menggunakan circular queue . Halaman yang baru di-load atau baru digunakan akan diberikan nilai 1 pada reference bit-nya. Halaman yang reference bit-nya bernilai 1 tidak akan langsung diganti walaupun dia berada di antrian paling bawah (berbeda dengan FIFO).

Urutan langkah kerja algoritma second chance adalah sebagai berikut:

– Apabila terjadi page fault dan tidak ada frame yang kosong, maka akan dilakukan razia (pencarian korban) halaman yang reference bit-nya bernilai 0 dimulai dari bawah antrian (seperti FIFO).

– Setiap halaman yang tidak di- swap (karena reference bit-nya bernilai 1), setiap dilewati saat razia reference bit-nya akan diset menjadi 0.

                              

Contoh gambar dari Algoritma page Modifikasi FIFO

6. Pengertian tentang Algoritma page LRU (Least Recently Used)

Dikarenakan algoritma optimal sangat sulit dalam pengimplementasiannya, maka dibuatlah algoritma lain yang performance-nya mendekati algoritma optimal dengan sedikit cost yang lebih besar. ama seperti algoritma optimal, algoritma LRU tidak mengalami anomali Belady. Algoritma ini memakai linked list untuk mendata halaman mana yang paling lama tidak terpakai. Linked list inilah yang membuat cost membesar, karena harus meng-update linked list tiap saat ada halaman yang di akses.

Contoh gambar dari Algoritma page LRU

TERIMAKASIH

Fungsi-fungsi PIN pada kabel UTP

EIA/TIA-568A & EIA/TIA-568B merupakan standar internasional pengkabelan dengan jack RJ-45 dan kabel UTP/STP kategori 3, 5, dan 6 (4 twisted pair) yang digunakan dalam teknologi ethernet dan PABX. Urutan dengan standar EIA/TIA-568A (putih hijau, hijau, putih orange, biru, putih biru, orange, putih coklat, coklat) dan EIA/TIA-568B (putih orange, orange, putih hijau, biru, putih biru, hijau, putih coklat, coklat) biasa digunakan untuk interkoneksi antar hardware maupun antar jaringan. Penggunaan susunan yang lain diperbolehkan, namun harus memenuhi kriteria pada no. 1 dan seterusnya.

•     Pin 1 & 2, dalam ethernet digunakan sebagai Tx. Untuk menghindari interferensi, maka harus dijadikan 1 pair (putih orange – orange atau putih hijau – hijau) untuk memenuhi kebutuhan elektris dalam protokol high-speed-LAN.

•      Pin 3 & 6, dalam ethernet digunakan sebagai Rx. Untuk menghindari interferensi, maka harus dijadikan 1 pair (putih orange – orange atau putih hijau – hijau) untuk memenuhi kebutuhan elektris dalam protokol high-speed-LAN.

•       Pin 4 & 5, “the central two pins” digunakan untuk membawa sinyal telepon (internet bukan hanya ethernet) atau sinyal suara dalam standar telekomunikasi. Untuk keperluan ini, sudah seharusnya jadi 1 pair di tengah (biru – biru putih)

•          Pin 7 & 8, biasanya digunakan untuk teknologi Power over Ethernet (PoE), yaitu untuk meningkatkan power pada perangkat VOIP, wireless LAN access point, webcam, ethernet hub, komputer, dan perangkat lain yang tidak memungkinkan untuk memberikan suplai power secara terpisah. Dalam hal ini tentunya pin 7 & 8 harus merupakan 1 pair (putih coklat – coklat).

 Dibawah ini merupakan gambar untuk penjelasan yang diatas :

                                                  Gambar 1. Susunan Stright

Straight
1. Putih Orange —— 1. Putih Orange
2. Orange —— 2. Orange
3. Putih Hijau —— 3. Putih Hijau
4. Biru —— 4. Biru
5. Putih Biru —— 5. Putih Biru
6. Hijau —— 6. Hijau
7. Putih Coklat —— 7. Putih Coklat
8. Coklat —— 8. Coklat

                                             Gambar 2. Susunan Cross

Cross
1. Putih Orange —— 3. Putih Hijau
2. Orange —— 6. Hijau
3. Putih Hijau —— 1. Putih Orange
4. Biru —— 4. Biru
5. Putih Biru —— 5. Putih Biru
6. Hijau —— 2. Orange
7. Putih Coklat —— 7. Putih Coklat
8. Coklat —— 8. Coklat

KESIMPULAN : 

HANYA ADA 4 KABEL(PIN) YANG DIGUNAKAN UNTUK MENTRANSFER DAN MENERIMA DATA YAITU 1,2,3.6.

•  PIN 1&2 UNTUK MENRANSFER DATA DAN 

•  PIN 3&6 UNTUK MENERIMA DATA.

Memory Direct Mapping

MAPPING (PEMETAAN)

Saluran cache lebih sedikit dibandingkan dengan blok memori utama sehingga diperlukan algoritma untuk pemetaan blok-blok memori utama ke dalam saluran cache. Selain itu, diperlukan juga alat untuk menentukan blok memori utama mana yang sedang memakai saluran cache. Pemilihan fungsi pemetaan akan menentukan bentuk organisasi cache. Terdapat tiga metode yang digunakan, tetapi pada saat ini saya hanya akan membahas satu saja yaitu :

“Pemetaan Langsung (Direct Mapping”)

• Pemetaan langsung adalah teknik yang paling sederhana, yaitu teknik ini memetakan blok memori utama hanya ke sebuah saluran cache saja. Jika suatu block ada di cache, maka tempatnya sudah tertentu. Keuntungan dari direct mapping adalah sederhana dan murah. Sedangkan kerugian dari direct mapping adalah suatu blok memiliki lokasi yang tetap (jika program mengakses 2 blok yang di map ke line yang sama secara berulang-ulang, maka cache-miss sangat tinggi). Setiap blok pada main memory dipetakan dengan line tertentu pada cache.di mana i adalah nomor line pada cache yang digunakan untuk meletakkan blok main memory ke-j.

Maka :

i = j modulo C

• Jika M = 64 dan C = 4, maka pemetaan antara line dengan blok menjadi seperti berikut :
• Line 0 can hold blocks 0, 4, 8, 12, …
• Line 1 can hold blocks 1, 5, 9, 13, …
• Line 2 can hold blocks 2, 6, 10, 14, …
• Line 3 can hold blocks 3, 7, 11, 15, …

• Pada cara ini, address pada main memory dibagi 3 field atau bagian, yaitu:
• Tag identifier.
• Line number identifier
• Word identifier (offset)

• Word identifier berisi informasi tentang lokasi word atau unit addressable lainnya dalam line tertentu pada cache.
• Line identifier berisi informasi tentang nomor fisik (bukan logika) line pada cache.
• Tag identifier disimpan pada cache bersama dengan blok pada line.
• Untuk setiap alamat memory yang dibuat oleh CPU, line tertentu yang menyimpan copy alamat tersebut ditentukan, jika blok tempat lokasi data tersebut sudah dikopi dari main memory ke cache.
• Tag yang ada pada line akan dicek untuk melihat apakah benar blok yang dimaksud ada pada line tersebut.

Gambar 1. Organisasi Memory Direct Mapping

   

   Keuntungan Menggunakan Direct Mapping antara lain :

o   Mudah dan Murah diimplementasikan

o   Mudah untuk menentukan letak salinan data main memory pada chace.

   Kerugian menggunakan Direct Mapping antara lain :

o   Setiap blok main memory hanya dipetakan pada 1 line saja.

o   Terkait dengan sifat lokal pada main memory, sangat mungkin mengakses blok yang dipetakan pada line yang sama pada cache. Blok seperti ini akan menyebabkan seringnya sapu masuk dan keluar data ke/dari cache, sehingga hit ratio mengecil. Hit ratio adalah perbandingan antara jumlah ditemukannya data pada cache dengan jumlah usaha mengakses cache.

Gambar 2. Contoh Pengalamatan Direct Mapping

Ringkasan direct mapping nampak pada tabel berikut:

Item	Keterangan
Panjang alamat	(s+w) bits
Jumlah unit yang dapat dialamati	2s+w words or bytes
Ukuran Bloks sama dengan ukuran Line	2w words or bytes
Jumlah blok memori utama	2s+ w/2w = 2s
Jumlah line di chace	M = 2r
Besarnya tag	(s - r) bits