Paging dan Segmentasi

Sistem Paging

Sistem paging mengimplementasikan ruang alamat besar pada memori kecil menggunakan index register, base register, dan segment register dan lain-lain.

Istilah pada sistem paging:

·         Alamat Maya

·         Alamat Nyata

·         Page

·         Page Frame

·         Page Fault

·         MMU

Pengertian dari istilah Paging

·         Alamat Maya : Alamat yang dihasilkan perhitungan menggunakan index register, base register, segment register dan sebagainya.

·         Alamat Nyata : Alamat di memori fisik.

·         Page : Unit terkecil virtual address space.

·         Page Frame : Unit terkecil memori fisik.

·         Page Fault : Exception untuk permintaan alokasi page ke memori.

·         Memory Management Unit (MMU) : chip atau kumpulan chip yang memetakan alamat maya ke alamat fisik.

Konsep Dasar

Memori fisik dibagi menjadi blok-blok dengan ukuran tertentu disebut frame. Sedangkan memori logika dibagi menjadi blok-blok yang disebut page. Setiap alamat yang diberikan oleh CPU dibagi menjadi 2 bagian, yaitu nomor page dan offset.

·         Page number digunakan sebagai indeks ke dalam table page (page table). Page table berisi alamat basis dari setiap page pada memori fisik.

·         Page offset mengkombinasikan alamat basis dengan page offset untuk mendefinisikan alamat memori fisik yang dikirim ke unit memori.

Pemetaan Page Menjadi Page Frame

Penggantian Page

Saat terjadi page fault berarti harus diputuskan page frame di memori fisik yang harus diganti. Banyaknya page fault menghasilkan banyak overhead.

·         Algoritma Penggantian Page

·         Algoritma penggantian page acak

Setiap terjadi page fault, page yang diganti dipilih secara acak. ini terdapat kemungkinan proses yang baru berjalan bisa digantikan oleh proses lain jadi sangat merugikan dan percobaan menunjukkan rate page fault yang sangat tinggi ketika menggunakan teknik ini.

·         Algoritma penggantian page optimal

·         Memilih page yang baru terpakai untuk digantikan oleh string acuan terbaru

·         Algoritma penggantian page LRU (Least Recently Used)

Berdasarkan observasi, page page yang digunakan pada beberapa instruksi terakhir berkemungkinan besar akan dipakai kembali nantinya. Page-page yang lama tidak digunakan akan tetap tak digunakan dalam waktu lama. Pada algoritma ini ketika terjadi page fault maka memindahkan page yang tak digunakan paling lama.

·         Algoritma penggantian page FIFO

Memilih memindahkan page yang sering digunakan yang telah berada dimemori untuk waktu yang lama.

·         Algoritma penggantian page NRU (Not Recently Used)

·         Algoritma penggantian page modifikasi dari FIFO

·         Algoritma penggantian page kesempatan kedua

·         Algoritma penggantian clock page 

Masalah pada Paging

·         Working set model

·         Penggantian lokal vs global

·         Frekuensi page fault

·         Ukuran page

Kerugian dan Keuntungan Paging

1.       Jika kita membuat ukuran dari masing-masing pages menjadi besar:

·         Keuntungan: akses memori akan relatif lebih cepat.

·         Kerugian: kemungkinan terjadinya fragmentasi internal yang sangat besar.

2.      Jika kita membuat ukuran dari masing-masing pages menjadi kecil:

·         Keuntungan: akses memori akan relatif lebih lambat.

·         Kerugian: kemungkinan terjadinya fragmentasi internal akan menjadi lebih kecil.

Segmentasi

Deskripsi Segmentasi

·         Segmentasi memungkinkan pemrogram memandang memori sebagai berisi banyak ruang alamat atau segmen.

·         Dengan segmentasi, pemrogram tidak berurusan dengan batasan memori yang disebabkan kapasistas memori utama.

Keunggulan Teknik Segmentasi

·         Menyederhanakan penanganan struktur data yang berkembang

·         Kompilasi ulang independen

·         Memudahkan pemakaian memori bersama diantara proses-proses

·         Memudahkan untuk proteksi

Perbandingan antara Paging dan Segmentasi

Ada beberapa perbedaan antara Segmentasi dan Paging diantaranya adalah :

·         Pada segmentasi kompilasi dilakukan secara terpisah sedangkan padapaging, kompilasinya tidak terpisah.

·         Pada segmentasi ada shared code sedangkan pada paging tidak ada shared code.

·         Pada segmentasi terdapat banyak ruang alamat linier sedangkan pada paginghanya terdapat satu ruang alamat linier.

·         Pada segmentasi pengubahan ukuran tabel dapat dilakukan dengan mudah sedangkan pada Paging pengubahan ukuran tabel tidak dapat dilakukan dengan mudah.

·         Segmentasi digunakan untuk mengizinkan program dan data dapat dipecahkan jadi ruang alamat mandiri dan juga untuk mendukung sharing dan proteksi sedangkan paging digunakan untuk mendapatkan ruang alamat linier yang besar tanpa perlu membeli memori fisik lebih.

Kombinasi Paging dan Segmentasi

·         Ruang alamat pemakai dibagi menjadi sejumlah segmen sesuai kehendak pemrogram.

·         Setiap segmen dibagi menjadi sejumlah page berukuran tetap, berukuran sama dengan page frame memori utama.

Sumber : kuliahasyik.files.wordpress.com/2013/04/memori-virtual

http://reviandireza.blogspot.com/2013/04/sistem-operasi-manajemen-memori.html

http://bisnisonline-rumah.blogspot.com/2012/02/perbedaan-segmentasi-dan-paging.html

http://diyanarswine.blogspot.com/2013/04/masalah-sistem-paging-penggantian-page.html

Mutual Exclusion

Pengertian Mutual Exclusion adalah Sebuah cara untuk memastikan bahwa jika satu proses yang menggunakan dimodifikasi data bersama, proses lain akan dikeluarkan dari melakukan hal yang sama.

Secara formal, sementara satu proses mengeksekusi variabel bersama, semua proses lain yang ingin melakukannya pada saat waktu yang sama harus terus menunggu, ketika proses yang telah selesai mengeksekusi variabel bersama, salah satu proses menunggu, sedangkan proses yang telah selesai melaksanakan variabel bersama, salah satu proses yang menunggu untuk melakukannya harus diizinkan untuk melanjutkan. Dengan cara ini, setiap proses mengeksekusi data bersama (variabel) termasuk semua orang lain dari melakukannya secara bersamaan. Ini disebut Mutual Exclusion.

Perhatikan bahwa mutual exclusion harus ditegakkan hanya ketika akses proses berbagi dimodifikasi Data - ketika proses sedang melakukan operasi yang tidak bertentangan dengan satu sama lain mereka harus diizinkan untuk melanjutkan bersamaan.

Kondisi Mutual Exclusion

Jika kita bisa mengatur hal-hal sehingga tidak ada dua proses yang pernah di bagian kritis mereka secara bersamaan, kita bisa menghindari kondisi lomba. Kita perlu empat kondisi untuk mengadakan memiliki solusi yang baik untuk masalah critical section (mutual exclusion). 

1. Tidak ada dua proses mungkin pada saat yang sama di dalam bagian kritis mereka. 
2. Tidak ada asumsi yang dibuat tentang kecepatan relatif proses atau jumlah CPU.
3. Tidak ada proses yang harus di luar critical section-nya harus memblokir proses lainnya. 
4.  Tidak ada proses yang harus menunggu lama untuk sewenang-wenang memasuki bagian kritis.

Sumber : http://www.personal.kent.edu/~rmuhamma/OpSystems/Myos/mutualExclu.htm

Dead Lock

Pengertian Deadlock adalah Deadlock atau bisa disebut dengan Jalan Buntu.  Secara garis besar Jalan buntu, mogok. Proses saling tunggu menunggu sumber lain selamanya, sementara satu proses hanya boleh menggunakan satu sumber daya, dan masing-masing tidak bisa melepaskan yang sedang digunakan.

Arti istilah Deadlock detection dianggap berkaitan erat dengan pengertian berikut

Metode deteksi digunakan pada sistem yang mengijinkan terjadinya deadlock. tujuan metode ini adalah memeriksa apakah telah terjadi deadlock dan menentukan proses-proses dan sumber daya-sumber daya yang terlibat deadlock secara presisi. Begitu telah dapat ditentukan, sistem dipulihkan dari deadlock dengan metode pemulihan. Metode pemulihan dari deadlock, untuk menghilangkan deadlock system, sehingga beroperasi kembali, dan bebas dari deadlock. Proses-proses yang terlibat deadlock mungkin dapat menyelesaikan eksekusi dan membebaskan sumber daya-sumber daya.

Deadlock adalah suatu kondisi dimana dua proses atau lebih tidak dapat meneruskan eksekusinya. Proses menunggu terus menerus, sementara sumber daya yang ditunggu tidak akan pernah didapatkan.

Misalnya :

·         Dua proses P1 dan P2

·         Dua sumber daya kritis R1 dan R2

·         Proses P1 dan P2 harus mengakses keuda sumber daya Kondisi berikut dapat terjadi: R1 diberikan ke P1, sedang R2 diberikan ke P2. Karena untuk melanjutkan eksekusi, memerlukan kedua sumber daya sekaligus, maka kedua proses akan saling menunggu sumber daya lain selamanya. Metode mengatasi deadlock ini adalah sebagai berikut:

1.      Metode pencegahan terjadinya deadlock (deadlock prevention),

2.      Metode penghindaran terjadinya deadlock (deadlock avoidance),

3.      Metode deteksi dan pemulihan dari deadlock (deadlock detection and recovery).

Resource (1)

Contoh:

·         Bridge Crossing

·         Traffic hanya satu arah

·         Masing-masing bagian jembatan dapat digambarkan sebagai resource.

·         Jika deadlock terjadi, dapat diselesaikan dengan cara satu mobil mundur ke belakang.

·         Beberapa mobil harus kembali jika terjadi deadlock

·         Memungkinkan terjadinya starvation

Resources (2)

·         Deadlock terjadi ketika

·         Proses-proses diberikan hak akses secara eksklusif ke devices (resources)

·         Preemptable resources

·         Dapat diambil dari proses tanpa menimbulkan efek yang buruk

·         Nonpreemptable resources

·         Akan menyebabkan proses gagal jika diambil

4. Kondisi Terjadinya Deadlock

·         Kondisi Mutual exclusion

·         Nanya satu proses dalam satu waktu yang dapat memegang (hold) resource

·         Hold and wait condition

·         Suatu proses memegang satu resource dan me-request resource yang lain

·         No preemption condition

·         Resource hanya dapat di-release setelah proses menyelesaikan task-nya pada resource tersebut

·         Circular wait condition

·         Masing-masing proses menunggu resource yang digunakan oleh proses lain secara berantai.

·         Terdapat himpunan proses yang sedang menunggu {P0, P1, …, P0} sedemikian sehingga P0 menunggu resource yang dipegang oleh P1 , P1 sedang menunggu resource yang dipegang oleh P2, …, Pn–1 . Pn–1 menunggu resource yang dipegang oleh Pn . Dan Pn menunggu resource yang dipegang oleh P0 .

Metode-metode Penanganan Deadlocks

·         Memastikan bahwa sistem tidak akan pernah masuk ke dalam kondisi (state) deadlock.

·         Memungkinkan sistem untuk masuk ke dalam kondisi deadlock dan kemudian melakukan recovery (pemulihan).

·         Mengabaikan masalah deadlock dan membuat deadlock tidak pernah terjadi dalam sistem; digunakan pada OS umumnya (Unix).

Metode Pencegahan Deadlock (1)

Cara pencegahan (Prevention) dari sisi permintaan (request) resources :

·         Mutual Exclusion – tidak diperlukan untuk resource-resource yang di-share; harus dipegang (hold) untuk resource-resource yang tidak di-share (nonsharable resources).

·         Hold and Wait – harus dijamin bahwa kapanpun suatu permintaan proses pada resource, proses tersebut tidak memegang resource yang lain.

·         Membutuhkan proses untuk me-request dan mengalokasikan resources sebelum memulai eksekusi, atau membolehkan proses untuk me-request resource hanya ketika proses tidak sedang memegang resource.

·         Utilisasi resource yang rendah memungkinkan terjadinya starvation.

Metode Pencegahan Deadlock (2)

·         No Preemption

·         Jika suatu proses yang memegang beberapa resource me-request resource yang lain yang tidak dapat secara langsung dialokasikan, maka semua resource yang sedang dipegang dibebaskan (released).

·         Preempted resources ditambahkan ke list resources dimana proses sedang menunggu.

·         Proses akan di-restart hanya jika dapat mengambil kembali (regain) resource, juga resource yang baru yang di-request.

·         Circular Wait

·         Membuat penomoran pada proses-proses yang mengakses resource. Suatu proses dimungkinkan untuk dapat meminta resource kapanpun, tetapi permintaannya harus dibuat terurut.

Syarat Langkah Kelemahan

·         Mutual Exclusion Spooling resource Dapat menyebabkan chaos

·         Hold & Wait Meminta resource diawal Sulit memperkirakan di awal dan tidak optimal

·         No Pre-emptive Mengambil resource di tengah jalan Hasil proses tidak akan baik

·         Circular Wait Penomoran permintaan resource Tidak ada penomoran yang memuaskan semua pihak

Metode Penghindaran Deadlock (1)

·         Memberi kesempatan ke permintaan resource yang tidak mungkin menyebabkan deadlock.

·         Jika pemberian akses tidak mungkin mengarah pada deadlock, maka resource akan diberikan pada proses yang meminta.

·         Jika tidak aman, proses yang meminta akan di-suspend sampai suatu waktu permintaannya aman untuk diberikan.

·         Kondisi aman (safe state)

·         Jika tidak terjadi deadlock

·         Kondisi tidak aman (unsafe state)

·         Jika tidak terdapat cara untuk memenuhi semua permintaan

Metode Penghindaran Deadlock (2)

·         Membutuhkan sistem yang memiliki informasi resource yang tersedia.

·         Masing-masing proses memastikan jumlah maksimum resource yang diperlukan.

·         Algoritma penghindaran (avoidence) deadlock memastikan tidak akan terjadi kondisi circular wait.

·         Kondisi (state) alokasi resource didefinisikan sebagai jumlah dan alokasi resource yang tersedia dan maksimum permintaan resource oleh proses.

Basic Facts

·         Jika sistem dalam kondisi aman (safe state) Þ tidak ada deadlock.

·         Jika sistem dalam kondisi tidak aman (unsafe state) Þ kemungkinan dapat terjadi deadlock

·         Pendekatan penghindaran (avoidence) memastikan bahwa sistem tidak akan pernah masuk ke dalam kondisi unsafe state.

Deteksi dan Pemulihan Deadlock

·         Menentukan apakah deadlock sedang terjadi, kemudian proses-proses dan resource yang terlibat dalam deadlock tersebut.

·         Setelah kondisi deadlock terdeteksi, maka langkah pemulihan deadlock dilakukan.

Cara Pemulihan Deadlock

·         Ada beberapa cara untuk pemulihan deadlock :

1.      Menggagalkan semua proses yang deadlock

2.      Mem-backup semua proses yang deadlock dan me-restart semua proses tersebut

3.      Menggagalkan proses-proses yang deadlock secara berturut-turut hingga tidak ada deadlock.

4.      Menggagalkan pengalokasian resource-resource secara berturut-turut hingga tidak ada deadlock.

·         Kriteria proses-proses yang akan disingkirkan :

1.      Memiliki waktu proses (yang telah berjalan) kecil.

2.      Jumlah keluaran sedikit

3.      Memiliki estimasi sisa waktu eksekusi terbesar.

4.      Jumlah total resource terkecil yang telah dialokasikan

5.      Memiliki prioritas terkecil   (Berbagai Sumber)

Sumber : http://info-dan-artikel.blogspot.com/2012/11/pengertian-deadlock-pada-so.html