MUTUAL EXCLUSION DAN DEADLOCK
MUTUAL EXCLUSION
Mutual exclusion adalah upaya menjamin pengaksesan sumber daya dedicated benar-benar hanya oleh satu proses tunggal. Di sestem uniprosessor, status sumber daya dan pemakai dapat tersedia di memori bersama dan solusi terhadap mutual-exclusion dapat diimplementasikan menggunakan variabel bersama (misalnya semaphore) secara mudah. Di sistem tersebar, sumber daya dan pemakai tersebar tidak terdapat memori bersama. Pendekatan berbasis variabel bersama tidak dapat diterapkan, harus digunakan pendekatan berbasis message-passing
Sumber : Sistem Operasi / Bambang Hariyanto / Mutual Exclusion
Bagian program yang sedang mengakses memori atau sumberdaya yang dipakai bersama disebut critical section / region. Kesuksesan proses-proses kongkuren memerlukan pendefinisian critical section dan memaksakan mutual exclusion diantara proses-proses kongkuren yang sedang berjalan. Pemaksaan mutual exclusion merupakan landasan pemrosesan kongkuren, namun pemaksaan mutual exclusion dapat menimbulkan 2 masalah yaitu :
1. Deadlock
Adalah banyak proses yang saling menunggu hasil dari proses yang lain untuk dapat melanjutkan atau menyelesaikan tugasnya.
2. Startvation
Adalah suatu proses akan menunggu suatu kejadian atau hasil suatu proses lain supaya dapat menyelesaikan tugasnya, tetapi kejadian yang ditunggu tidak pernah terjadi karena selalu diambil lebih dulu oleh proses yang lain.
Tgl akses 22 April 2013
Syarat Mutual Exclusion :
Ø Hanya satu proses pada satu waktu yang dibolehkan ada dalam critical section bagi suatu resource.
Ø Proses yang berhenti pada noncritical section-nya harus melakukan demikian tanpa gangguan dengan proses lain.
Ø Tidak ada deadlock atau starvation.
Ø Proses harus tidak didelay akses ke suatu critical section saat tidak ada proses lain yang menggunakannya.
Ø Tidak ada asumsi mengenai kecepatan proses relatif atau jumlah proses.
Ø Proses tetap di dalam critical section-nya hanya selama waktu terbatas tertentu (finite).
Sumber : komputasi.files.wordpress.com/2009/03/so2009-05.pdf
Tgl akses 22 April 2013
DEADLOCK
ü Keadaan dimana 2 atau lebih proses saling menunggu meminta resources untuk waktu yang tidak terbatas lamanya.
ü Analoginya seperti pada kondisi jalan raya dimana terjadi kemacetan parah
ü Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan oleh 2 proses.
Strategi mengatasi Deadlock :
1. Prevention : memastikan paling sedikit satu penyebab Deadlock tidak berlaku.
§ Mutual Exclusion : membuat file spool untuk resource yang digunakan bersama-sama.
§ Hold and Wait : memaksa sebuah proses untuk melepaskan resource yang dimilikinya ketika meminta resource baru.
§ Circular Waiting : memberikan penamaan resource berdasarkan urutan atau level.
§ No Preemption : membolehkan adanya preemption
2. Avoidance : sistem menolak request terhadap resource yang berpotensi deadlock.
§ Resource manager menolak proses yang meminta resource yang berpotensi deadlock.
§ Jika ada permintaan resource yang maksimum digunakan, maka proses tersebut akan dipaksa untuk melepaskan resource yang sudah dimiliknya.
3. Detection and Recovery : membiarkan Deadlock terjadi, lalu mendeteksinya, kemudian melakukan recovery.
§ Membiarkan deadlock terjadi lalu mendeteksinya kemudian melakukan tindakan recovery seperlunya.
§ Algoritma yang paling dikenal adalah algoritma Ostrich
§ Tindakan recovery yang dilakukan adalah : melakukan preemption, membuat checkpoint untuk rollback lalu membunuh proses yang prioritasnya kecil.
Sumber : lecturer.d3ti.mipa.uns.ac.id/.../deadlockk.pdf
Tgl Akses : 22 April 2013
4 Karakteristik DeadLock :
- Mutual Exclusion : Suatu kondisi dimana setiap sumber daya diberikan tepat pada satu proses pada suatu waktu.
- Hold and Wait : Kondisi yang menyatakan proses-proses yang sedang memakai suatu sumber daya dapat meminta sumber daya yang lain.
- Non-pre-emptive : Kondisi dimana suatu sumber daya yang sedang berada pada suatu proses tidak dapat diambil secara paksa dari proses tersebut,sampai proses itu melepaskannya.
- Circular Wait : Kondisi yang menyatakan bahwa adanya rantai saling meminta sumber daya yang dimiliki oleh suatu proses oleh proses lainnya.
METODE-METODE DEADLOCK
Metode-metode Penanganan Deadlock :
· 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:
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 Penghindaran Deadlock :
· 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).
· 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.
Cara Pemulihan Deadlock:
· Menggagalkan semua proses yang deadlock.
· Mem-backup semua proses yang deadlock dan me-restart semua proses tersebut.
· Menggagalkan proses-proses yang deadlock secara berturut-turut hingga tidak ada deadlock.
· Menggagalkan pengalokasian resource-resource secara berturut-turut hingga tidak ada deadlock.
· Kriteria proses-proses yang akan disingkirkan :
~ Memiliki waktu proses (yang telah berjalan) kecil.
~ Jumlah keluaran sedikit.
~ Memiliki estimasi sisa waktu eksekusi terbesar.
~ Jumlah total resource terkecil yang telah dialokasikan
~ Memiliki prioritas terkecil
Tgl akses: 22 April 2013
