DEADLOCK
Deadlock adalah suatu kondisi dimana dua proses atau lebih tidak dapat meneruskan eksekusinya oleh pemroses. Pada umumnya deadlock terjadi karena proses mengalami startvation, yaitu suatu job yang sedang dieksekusi dan eksekusi job tersebut tidak ada hentinya, tidak diketahui kapan berhentinya proses tersebut atau bahkan job yang antri bisa dikatakan mempunyai status mati, padahal proses-proses lain sedang menunggu sumber daya proses.
Kondisi Deadlock merupakan kondisi terparah karena banyak proses dapat terlibat dan semuanya tidak dapat mengakhiri prosesnya secara benar.
Deadlock adalah suatu kondisi dimana dua proses atau lebih tidak dapat meneruskan eksekusinya oleh pemroses. Pada umumnya deadlock terjadi karena proses mengalami startvation, yaitu suatu job yang sedang dieksekusi dan eksekusi job tersebut tidak ada hentinya, tidak diketahui kapan berhentinya proses tersebut atau bahkan job yang antri bisa dikatakan mempunyai status mati, padahal proses-proses lain sedang menunggu sumber daya proses.
Kondisi Deadlock merupakan kondisi terparah karena banyak proses dapat terlibat dan semuanya tidak dapat mengakhiri prosesnya secara benar.
1. Resources-Allocation Graph
Sebuah cara visual (matematika) untuk menentukan
apakah ada deadlock, atau kemungkinan terjadinya. G = (V, E) Graf berisi node
and edge. Node V terdiri dari proses-proses = {P1, P2, P3, ...} dan jenis
resource. {R1, R2, ...} Edge E adalah (Pi, Rj) atau (Ri, Pj) Sebuah panah dari
process ke resource menandakan proses meminta resource. Sebuah panah dari resource
ke process menunjukkan sebuah instance dari resource telah dtempatkan ke
proses. Process adalah lingkaran, resource adalah kotak; titik-titik
merepresentasikan jumlah instance dari resource Dalam tipe. Meminta poin-poin
ke kotak, perintah datang dari titik.
2. Model Sistem
Menurut Coffman dalam bukunya "Operating System"
menyebutkan empat syarat bagi terjadinya deadlock, yaitu:
a.
Mutual Exclusion
Suatu kondisi dimana setiap sumber daya diberikan
tepat pada satu proses pada suatu waktu.
b.
Hold and Wait
Kondisi yang menyatakan proses-proses yang sedang memakai suatu sumber
daya dapat meminta sumber daya yang lain.
c.
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.
d.
Circular Wait
Kondisi yang menyatakan bahwa adanya rantai saling meminta sumber daya
yang dimiliki oleh suatu proses oleh proses lainnya
3. Strategi menghadapi
Deadlock
Strategi untuk menghadapi deadlock dapat dibagi menjadi tiga
pendekatan, yaitu:
a.
Mengabaikan adanya
deadlock.
b.
Memastikan bahwa
deadlock tidak akan pernah ada, baik dengan metode Pencegahan, dengan mencegah
empat kondisi deadlock agar tidak akan pernah terjadi. Metode Menghindari
deadlock, yaitu mengizinkan empat kondisi deadlock, tetapi menghentikan setiap
proses yang kemungkinan mencapai deadlock.
c.
Membiarkan deadlock
untuk terjadi, pendekatan ini membutuhkan dua metode yang saling mendukung,
yaitu:
-
Pendeteksian deadlock,
untuk mengidentifikasi ketika deadlock terjadi.
-
Pemulihan deadlock,
mengembalikan kembali sumber daya yang dibutuhkan pada proses yang memintanya.
Dari penjabaran pendekatan diatas, terdapat empat metode
untuk mengatasi deadlock yang akan terjadi, yaitu:
a. Strategi Ostrich
Pendekatan yang paling sederhana adalah dengan
menggunakan strategi burung unta: masukkan kepala dalam pasir dan seolah-olah
tidak pernah ada masalah sama sekali. Beragam pendapat muncul berkaitan dengan
strategi ini. Menurut para ahli Matematika, cara ini sama sekali tidak dapat
diterima dan semua keadaan deadlock harus ditangani. Sementara menurut para
ahli Teknik, jika komputer lebih sering mengalami kerusakkan disebabkan oleh
kegagalan hardware, error pada kompilator atau bugs pada sistem operasi. Maka ongkos
yang dibayar untuk melakukan penanganan deadlock sangatlah besar dan lebih baik
mengabaikan keadaan deadlock tersebut. Metode ini diterapkan pada sistem
operasi UNIX dan MINIX.
4 . Mencegah Deadlock
Metode ini merupakan metode yang paling sering digunakan.
Metode Pencegahan dianggap sebagai solusi yang bersih dipandang dari sudut
tercegahnya deadlock. Tetapi pencgahan akan mengakibatkan kinerja utilisasi
sumber daya yang buruk.
Metode pencegahan menggunakan pendekatan dengan cara
meniadakan empat syarat yang dapat menyebabkan deadlock terjadi pada saat
eksekusi Coffman (1971).
Syarat pertama yang akan dapat ditiadakan adalah
Mutual Exclusion, jika tidak ada sumber daya yang secara khusus diperuntukkan
bagi suatu proses maka tidak akan pernah terjadi deadlock. Namun jika
membiarkan ada dua atau lebih proses mengakses sebuah sumber daya yang sama
akan menyebabkan chaos. Langkah yang digunakan adalah dengan spooling sumber
daya, yaitu dengan mengantrikan job-job pada antrian dan akan dilayani
satu-satu.
Beberapa masalah yang mungkin terjadi adalah:
a.
Tidak semua dapat
di-spool, tabel proses sendiri tidak mungkin untuk di-spool
b.
Kompetisi pada ruang
disk untuk spooling sendiri dapat mengarah pada deadlock
Hal inilah yang menyebabkan mengapa syarat pertama
tidak dapat ditiadakan, jadi mutual exclusion benar-benar tidak dapat
dihilangkan.
Cara kedua dengan meniadakan kondisi hold and wait
terlihat lebih menjanjikan. Jika suatu proses yang sedang menggunakan sumber
daya dapat dicegah agar tidak dapat menunggu sumber daya yang lain, maka
deadlock dapat dicegah. Langkah yang digunakan adalah dengan membuat proses
agar meminta sumber daya yang mereka butuhkan pada awal proses sehingga dapat
dialokasikan sumber daya yang dibutuhkan. Namun jika terdapat sumber daya yang
sedang terpakai maka proses tersebut tidak dapat memulai prosesnya.
Masalah yang mungkin terjadi:
a.
Sulitnya mengetahui
berapa sumber daya yang dibutuhkan pada awal proses
b.
Tidak optimalnya
pengunaan sumber daya jika ada sumber daya yang digunakan hanya beberapa waktu
dan tidak digunakan tapi tetap dimiliki oleh suatu proses yang telah memintanya
dari awal.
Meniadakan syarat ketiga non preemptive ternyata tidak
lebih menjanjikan dari meniadakan syarat kedua, karena dengan meniadakan syarat
ketiga maka suatu proses dapat dihentikan ditengah jalan. Hal ini tidak
dimungkinkan karena hasil dari suatu proses yang dihentikan menjadi tidak baik.
Cara terakhir adalah dengan meniadakan syarat keempat
circular wait. Terdapat dua pendekatan, yaitu:
a.
Mengatur agar setiap
proses hanya dapat menggunakan sebuah sumber daya pada suatu waktu, jika
menginginkan sumber daya lain maka sumber daya yang dimiliki harus dilepas.
b.
Membuat penomoran pada
proses-proses yang mengakses sumber daya. Suatu proses dimungkinkan untuk dapat
meminta sumber daya kapan pun, tetapi permintaannya harus dibuat terurut.
Masalah yang mungkin terjadi dengan mengatur bahwa
setiap proses hanya dapat memiliki satu proses adalah bahwa tidak semua proses
hanya membutuhkan satu sumber daya, untuk suatu proses yang kompleks dibutuhkan
banyak sumber daya pada saat yang bersamaan. Sedangkan dengan penomoran masalah
yang dihadapi adalah tidak terdapatnya suatu penomoran yang dapat memuaskan
semua pihak.
Secara ringkas pendekatan yang digunakan pada metode
pencegahan deadlock dan masalah-masalah yang menghambatnya, terangkum dalam
tabel dibawah ini.
5. Menghindari Deadlock
Pendekatan metode ini adalah dengan hanya memberi
kesempatan ke permintaan sumber daya yang tidak mungkin akan menyebabkan
deadlock. Metode ini memeriksa dampak pemberian akses pada suatu proses, jika
pemberian akses tidak mungkin menuju kepada deadlock, maka sumber daya akan
diberikan pada proses yang meminta. Jika tidak aman, proses yang meminta akan
di-suspend sampai suatu waktu permintaannya aman untuk diberikan. Kondisi ini
terjadi ketika setelah sumber daya yang sebelumnya dipegang oleh proses lain telah
dilepaskan.
Kondisi aman yang dimaksudkan selanjutnya disebut
sebagai safe-state, sedangkan keadaan yang tidak memungkinkan untuk diberikan
sumber daya yang diminta disebut unsafe-state.
a.
Kondisi Aman (Safe
state)
Suatu keadaan dapat dinyatakan sebagai safe state jika tidak terjadi
deadlock dan terdapat cara untuk memenuhi semua permintaan sumber daya yang
ditunda tanpa menghasilkan deadlock. Dengan cara mengikuti urutan tertentu.
b.
Kondisi Tak Aman
(Unsafe state)
Suatu state dinyatakan sebagai state tak selamat (unsafe state) jika
tidak terdapat cara untuk memenuhi semua permintaaan yang saat ini ditunda
dengan menjalankan proses-proses dengan suatu urutan.
6. Algoritma Bankir
Algoritma penjadualan ini diungkapkan oleh Dijkstra
(1965) lebih dikenal dengan nama Algoritma Bankir. Model ini menggunakan suatu
kota kecil sebagai percontohan dengan suatu bank sebagai sistem operasi,
pinjaman sebagai sumber daya dan peminjam sebagai proses yang membutuhkan
sumber daya. Deadlock akan terjadi apabila terdapat seorang peminjam yang belum
mengembalikan uangnya dan ingin meminjam kembali, padahal uang yang belum
dikembalikan tadi dibutuhkan oleh peminjam lain yang juga belum mengembalikan uang
pinjamannya.
Beberapa kelemahan algoritma Bankir Tanenbaum (1992),
Stallings (1995) dan Deitel (1990) adalah sebagai berikut:
a.
Sulit untuk mengetahui
seluruh sumber daya yang dibutuhkan proses pada awal eksekusi.
b.
Jumlah proses yang
tidak tetap dan berubah-ubah.
c.
Sumber daya yang
tadinya tersedia dapat saja menjadi tidak tersedia kembali.
d.
Proses-proses yang
dieksekusi haruslah tidak dibatasi oleh kebutuhan sinkronisasi antar proses.
e.
Algoritma ini
menghendaki memberikan semua permintaan selama waktu yang berhingga.
7. Mendeteksi Deadlock
dan Memulihkan Deadlock
Metode ini mengunakan pendekatan dengan teknik untuk
menentukan apakah deadlock sedang terjadi serta proses-proses dan sumber daya
yang terlibat dalam deadlock tersebut. Setelah kondisi deadlock dapat
dideteksi, maka langkah pemulihan dari kondisi deadlock dapat segera dilakukan.
Langkah pemulihan tersebut adalah dengan memperoleh sumber daya yang diperlukan
oleh proses-proses yang membutuhkannya. Beberapa cara digunakan untuk
mendapatkan sumber daya yang diperlukan, yaitu dengan terminasi proses dan
pre-emption (mundur) suatu proses. Metode ini banyak digunakan pada komputer
mainframe berukuran besar.
a. Terminasi Proses
Metode ini akan menghapus proses-proses yang terlibat
pada kondisi deadlock dengan mengacu pada beberapa syarat. Beberapa syarat yang
termasuk dalam metode ini adalah, sebagai berikut:
-
Menghapus semua proses
yang terlibat dalam kondisi deadlock (solusi ini terlalu mahal).
-
Menghapus satu persatu
proses yang terlibat, sampai kondisi deadlock dapat diatasi (memakan banyak
waktu).
-
Menghapus proses
berdasarkan prioritas, waktu eksekusi, waktu untuk selesai, dan kedalaman dari
rollback.
b. Resources Preemption
Metode ini lebih menekankan kepada bagaimana
menghambat suatu proses dan sumber daya, agar tidak terjebak pada unsafe
condition.
Beberapa langkahnya, yaitu:
-
Pilih salah satu -
proses dan sumber daya yang akan di-preempt.
-
Rollback ke safe state
yang sebelumnya telah terjadi.
Mencegah suatu proses agar tidak terjebak pada starvation
karena metode ini.
STARTVATION
Startvation adalah keadaan dimana pemberian akses bergantian terus menerus, dan ada suatu proses yang tidak mendapatkan gilirannya. Juga dapat dimaksudkan bahwa kondisi bila beberapa proses-proses menunggu alokasi sumber daya sampai tak berhingga, sementara proses-proses lain dapat memperoleh alokasi sumber daya.
Hal ini disebabkan bias pada kebijaksanaan atau strategi alokasi sumber daya. Kondisi seperti ini harus dihindari pada sistem operasi karena tidak adil, tapi dikehendaki penghindaran dilakukan seefisien mungkin. Penanganan ini merupakan persoalan yang sulit untuk menemukan kriteria yang benar, adil dan efesien dalam suatu strategi Sistem Operasi.
Perhatikan contoh berikut:
a. terdapat tiga proses, P1, P2, dan P3.
b. P1, P2 dam P3 memerlukan pengaksesan sumber daya R secara periodik.
Skenario berikut terjadi:
c. P1 sedang diberi sumber daya R, P2 dan P3 blocked menunggu sumber daya R.
d. Ketika P1 keluar dari critical section, P2 dan P3 diijinkan mengakses R.
e. Asumsi P3 diberi hak akses. Kemudian setelah selesai, hak akses kembali diberikan ke P1 yang satu itu kembali membutuhkan sumber daya R.
Jika pemberian hak akses bergantian terus menerus antara P1 dan P3, maka P2 tidak pernah memperoleh pengaksesan sumber daya R, meski tidak ada deadlock. Pada situasi ini, P2 mengalami situasi yang disebut dengan startvation
Startvation adalah keadaan dimana pemberian akses bergantian terus menerus, dan ada suatu proses yang tidak mendapatkan gilirannya. Juga dapat dimaksudkan bahwa kondisi bila beberapa proses-proses menunggu alokasi sumber daya sampai tak berhingga, sementara proses-proses lain dapat memperoleh alokasi sumber daya.
Hal ini disebabkan bias pada kebijaksanaan atau strategi alokasi sumber daya. Kondisi seperti ini harus dihindari pada sistem operasi karena tidak adil, tapi dikehendaki penghindaran dilakukan seefisien mungkin. Penanganan ini merupakan persoalan yang sulit untuk menemukan kriteria yang benar, adil dan efesien dalam suatu strategi Sistem Operasi.
Perhatikan contoh berikut:
a. terdapat tiga proses, P1, P2, dan P3.
b. P1, P2 dam P3 memerlukan pengaksesan sumber daya R secara periodik.
Skenario berikut terjadi:
c. P1 sedang diberi sumber daya R, P2 dan P3 blocked menunggu sumber daya R.
d. Ketika P1 keluar dari critical section, P2 dan P3 diijinkan mengakses R.
e. Asumsi P3 diberi hak akses. Kemudian setelah selesai, hak akses kembali diberikan ke P1 yang satu itu kembali membutuhkan sumber daya R.
Jika pemberian hak akses bergantian terus menerus antara P1 dan P3, maka P2 tidak pernah memperoleh pengaksesan sumber daya R, meski tidak ada deadlock. Pada situasi ini, P2 mengalami situasi yang disebut dengan startvation
Sumber:
http://jaringan-kabel.blogspot.com/2012/07/algoritma-deadlock.html
Tidak ada komentar:
Posting Komentar