Pengertian
Deadlock adalah 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. 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
- 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.
Contoh Kasus
Gambar
23.1. Contoh kasus deadlock pada lalu lintas di jembatan
|
|
Pada
contoh di atas, digambarkan ilustrasi dari kejadian deadlock pada dunia
nyata, yaitu pada lalu lintas di jembatan. Dapat dilihat bahwa kedua mobil yang
berada di tengah-tengah jembatan tidak dapat maju dan hanya menunggu.
Penyelesaian dari masalah tersebut adalah salah satu dari mobil tersebut
mundur, sehingga mobil yang lain dapat maju. Mobil pada kasus ini adalah
proses, sedangkan jembatan adalah sumber daya. Kedua mobil berebut untuk
menggunakan sumber daya, namun karena sumber daya tersebut hanya dapat
digunakan oleh satu proses saja, maka terjadilah deadlock. Kondisi
tersebut bila terjadi dalam waktu yang lama dapat menyebabkan terjadinya starvation.
|
|
Gambar di
atas adalah contoh lain terjadinya deadlock pada dunia nyata. Pada
gambar jelas terlihat bahwa lalu lintas terhenti dan terjadi antrian pada empat
arah datangnya mobil. Tidak ada mobil yang bisa melanjutkan perjalanan dan
hanya menunggu saja. Permasalahan ini dapat dipecahkan dengan cara salah satu
dari antrian tersebut mundur dan memberikan kesempatan antrian lain untuk
berjalan terlebih dahulu. Kasus seperti ini sangat potensial untuk terjadinya starvation.
Model Sistem
Keadaan
dimana suatu proses yang meminta sumber daya pasti terjadi dalam suatu sistem.
Untuk itu dibutuhkan cara pemodelan terhadapnya. Terdapat tipe sumber daya R 1, R 2, ..., R m. Contohnya adalah space pada memori dan juga komponen-komponen
M/K. Setiap tipe sumber daya R i tersebut memiliki W i instances. Misalnya sebuah
sumber daya M/K memiliki dua buah instances yang bisa diakses oleh proses.
Sebuah proses dalam
melakukan penggunaan terhadap suatu sumber daya melalui langkah-langkah sebagai
berikut:
·
Request . Pada langkah ini,
pertama kali proses mengajukan diri untuk bisa mendapatkan sumber daya. Proses
dapat meminta satu atau lebih sumber daya yang tersedia ataupun yang sedang
dimiliki oleh proses yang lain.
·
Use . Selanjutnya,
setelah proses mendapatkan sumber daya yang dibutuhkannya, proses akan
melakukan eksekusi. Sumber daya digunakan oleh proses sampai proses selesai
melakukan eksekusi dan tidak membutuhkan lagi sumber daya tersebut.
·
Release . Setelah
memanfaatkan sumber daya untuk melakukan eksekusi, proses pun akan melepaskan
sumber daya yang dimilikinya. Sumber daya tersebut dibutuhkan oleh proses lain
yang mungkin sedang menunggu untuk menggunakan.
Karakteristik
Setelah pada bagian sebelumnya kita telah
mengetahui mengenai pengertian dari deadlock dan bagaimana
memodelkannya, sekarang kita akan membahas secara mendalam mengenai
karakteristik dari terjadinya deadlock. Karakteristik-karakteristik
ini harus dipenuhi keempatnya untuk terjadi deadlock. Namun, perlu
diperhatikan bahwa hubungan kausatif antara empat karakteristik ini dengan
terjadinya deadlock adalah implikasi. Deadlock mungkin
terjadi apabila keempat karakteristik terpenuhi. Empat kondisi tersebut adalah:
- Mutual Exclusion . Kondisi yang pertama
adalah mutual exclusion yaitu proses memiliki hak milik
pribadi terhadap sumber daya yang sedang digunakannya. Jadi, hanya ada
satu proses yang menggunakan suatu sumber daya. Proses lain yang juga
ingin menggunakannya harus menunggu hingga sumber daya tersebut dilepaskan
oleh proses yang telah selesai menggunakannya. Suatu proses hanya dapat
menggunakan secara langsung sumber daya yang tersedia secara bebas.
- Hold and Wait . Kondisi yang kedua adalah hold
and wait yaitu beberapa proses saling menunggu sambil menahan
sumber daya yang dimilikinya. Suatu proses yang memiliki minimal satu buah
sumber daya melakukan request lagi terhadap sumber daya.
Akan tetapi, sumber daya yang dimintanya sedang dimiliki oleh proses yang
lain. Pada saat yang sama, kemungkinan adanya proses lain yang juga
mengalami hal serupa dengan proses pertama cukup besar terjadi. Akibatnya,
proses-proses tersebut hanya bisa saling menunggu sampai sumber daya yang
dimintanya dilepaskan. Sambil menunggu, sumber daya yang telah dimilikinya
pun tidak akan dilepas. Semua proses itu pada akhirnya saling menunggu dan
menahan sumber daya miliknya.
- No Preemption . Kondisi yang selanjutnya
adalah no preemption yaitu sebuah sumber daya hanya dapat
dilepaskan oleh proses yang memilikinya secara sukarela setelah ia selesai
menggunakannya. Proses yang menginginkan sumber daya tersebut harus
menunggu sampai sumber daya tersedia, tanpa bisa merebutnya dari proses
yang memilikinya.
- Circular Wait . Kondisi yang terakhir
adalah circular wait yaitu kondisi membentuk siklus yang
berisi proses-proses yang saling membutuhkan. Proses pertama membutuhkan
sumber daya yang dimiliki proses kedua, proses kedua membutuhkan sumber
daya milik proses ketiga, dan seterusnya sampai proses ke n-1 yang
membutuhkan sumber daya milik proses ke n. Terakhir, proses ke n membutuhkan
sumber daya milik proses yang pertama. Yang terjadi adalah proses-proses
tersebut akan selamanya menunggu. Circular wait oleh
penulis diistilahkan sebagai 'Lingkaran Setan' tanpa ujung.
Pemulihan
Pemulihan
kondisi sistem terkait dengan pendeteksian terhadap deadlock. Apabila menurut
algoritma pendeteksian deadlock sistem berada pada keadaandeadlock,
maka harus segera dilakukan mekanisme pemulihan sistem. Berbahaya apabila
sistem tidak segera dipulihkan dari deadlock,
karena sistem dapat mengalami penurunan performance dan akhirnya terhenti.
Cara-cara yang ditempuh
untuk memulihkan sistem dari deadlock adalah sebagai berikut:
1.
Terminasi
proses. Pemulihan sistem dapat
dilakukan dengan cara melalukan terminasi terhadap semua proses yang terlibat
dalam deadlock. Dapat
pula dilakukan terminasi terhadap proses yang terlibat dalam deadlock secara satu per satu sampai 'lingkaran
setan' atau circular wait hilang. Seperti diketahui bahwa circular wait adalah salah satu karakteristik
terjadinya deadlock dan merupakan kesatuan dengan tiga
karakteristik yang lain. Untuk itu, dengan menghilangkan kondisi circular wait dapat memulihkan sistem dari deadlock.Dalam melakukan
terminasi terhadap proses yang deadlock,
terdapat beberapa faktor yang menentukan proses mana yang akan diterminasi.
Faktor pertama adalah prioritas dari proses-proses yang terlibat deadlock. Faktor kedua adalah
berapa lama waktu yang dibutuhkan untuk eksekusi dan waktu proses menunggu
sumber daya. Faktor ketiga adalah berapa banyak sumber daya yang telah
dihabiskan dan yang masih dibutuhkan. Terakhir, faktor utilitas dari proses pun
menjadi pertimbangan sistem untuk melakukan terminasi pada suatu proses.
2.
Rollback and
Restart . Dalam memulihkan keadaan sistem yang deadlock, dapat dilakukan
dengan cara sistem melakukan preempt terhadap sebuah proses dan kembali ke state yang aman. Pada keadaan safe state tersebut, proses masih berjalan dengan
normal, sehingga sistem dapat memulai proses dari posisi aman tersebut. Untuk
menentukan pada saat apa proses akan rollback,
tentunya ada faktor yang menentukan. Diusahakan untuk meminimalisasi kerugian
yang timbul akibat memilih suatu proses menjadi korban. Harus pula dihindari
keadaan dimana proses yang sama selalu menjadi korban, sehingga proses tersebut
tidak akan pernah sukses menjalankan eksekusi.
Penanganan
1.
Pengabaian. Maksud dari pengabaian di sini adalah sistem mengabaikan
terjadinya deadlock dan pura-pura tidak tahu kalau deadlock terjadi. Dalam penanganan dengan cara
ini dikenal istilah ostrich
algorithm. Pelaksanaan algoritma ini adalah sistem tidak mendeteksi adanya deadlock dan secara otomatis mematikan proses
atau program yang mengalami deadlock.
Kebanyakan sistem operasi yang ada mengadaptasi cara ini untuk menangani
keadaan deadlock. Cara
penanganan dengan mengabaikan deadlock banyak dipilih karena kasus deadlock tersebut jarang terjadi dan relatif
rumit dan kompleks untuk diselesaikan. Sehingga biasanya hanya diabaikan oleh
sistem untuk kemudian diselesaikan masalahnya oleh user dengan cara melakukan terminasi denganCtrl+Alt+Del atau melakukan restart terhadap komputer.
2.
Pencegahan. Penanganan ini dengan cara mencegah terjadinya salah satu
karakteristik deadlock.
Penanganan ini dilaksanakan pada saat deadlock belum terjadi pada sistem. Intinya
memastikan agar sistem tidak akan pernah berada pada kondisi deadlock. Akan dibahas secara
lebih mendalam pada bagian selanjutnya.
3.
Penghindaran. Menghindari keadaan deadlock.
Bagian yang perlu diperhatikan oleh pembaca adalah bahwa antara pencegahan dan
penghindaran adalah dua hal yang berbeda. Pencegahan lebih kepada mencegah
salah satu dari empat karakteristik deadlock terjadi, sehingga deadlock pun tidak terjadi. Sedangkan
penghindaran adalah memprediksi apakah tindakan yang diambil sistem, dalam
kaitannya dengan permintaan proses akan sumber daya, dapat mengakibatkan
terjadi deadlock. Akan
dibahas secara lebih mendalam pada bagian selanjutnya.
4.
Pendeteksian dan
Pemulihan. Pada sistem yang sedang
berada pada kondisi deadlock,
tindakan yang harus diambil adalah tindakan yang bersifat represif. Tindakan
tersebut adalah dengan mendeteksi adanya deadlock,
kemudian memulihkan kembali sistem. Proses pendeteksian akan menghasilkan
informasi apakah sistem sedang deadlock atau tidak serta proses mana yang
mengalami deadlock. Akan
dibahas secara lebih mendalam pada bagian selanjutnya.
Pencegahan
Pencegahan deadlock dapat dilakukan dengan cara mencegah
salah satu dari empat karakteristik terjadinya deadlock. Berikut ini akan
dibahas satu per satu cara pencegahan terhadap empat karakteristik tersebut.
1.
Mutual
Exclusion . Kondisi mutual
exclusion pada sumber daya
adalah sesuatu yang wajar terjadi, yaitu pada sumber daya yang tidak dapat
dibagi (non-sharable). Sedangkan pada sumber daya yang bisa dibagi
tidak ada istilah mutual
exclusive. Jadi, pencegahan kondisi yang pertama ini sulit karena memang
sifat dasar dari sumber daya yang tidak dapat dibagi.
2.
Hold and Wait . Untuk kondisi
yang kedua, sistem perlu memastikan bahwa setiap kali proses meminta sumber
daya, ia tidak sedang memiliki sumber daya lain. Atau bisa dengan proses
meminta dan mendapatkan sumber daya yang dimilikinya sebelum melakukan eksekusi,
sehingga tidak perlu menunggu.
3.
No Preemption . Pencegahan
kondisi ini dengan cara membolehkan terjadinya preemption. Maksudnya bila
ada proses yang sedang memiliki sumber daya dan ingin mendapatkan sumber daya
tambahan, namun tidak bisa langsung dialokasikan, maka akan preempted. Sumber daya yang
dimiliki proses tadi akan diberikan pada proses lain yang membutuhkan dan
sedang menunggu. Proses akan mengulang kembali eksekusinya setelah mendapatkan
semua sumber daya yang dibutuhkannya, termasuk sumber daya yang dimintanya
terakhir.
4.
Circular Wait . Kondisi
'lingkaran setan' ini dapat 'diputus' dengan jalan menentukan total kebutuhan
terhadap semua tipe sumber daya yang ada. Selain itu, digunakan pula mekanisme
enumerasi terhadap tipe-tipe sumber daya yang ada. Setiap proses yang akan
meminta sumber daya harus meminta sumber daya dengan urutan yang menaik.
Misalkan sumber daya printer memiliki nomor 1 sedangkan CD-ROM memiliki nomor 3. Proses boleh
melakukan permintaan terhadap printer dan kemudian CD-ROM, namun tidak boleh
sebaliknya.
Pendeteksian
Pada
dasarnya kejadian deadlock sangatlah jarang terjadi. Apabila
kondisi tersebut terjadi, masing-masing sistem operasi mempunyai mekanisme
penanganan yang berbeda. Ada sistem operasi yang ketika terdapat kondisi deadlock dapat langsung mendeteksinya. Namun,
ada pula sistem operasi yang bahkan tidak menyadari kalau dirinya sedang
mengalami deadlock.
Untuk sistem operasi yang dapat mendeteksi deadlock,
digunakan algoritma pendeteksi. Secara lebih mendalam, pendeteksian kondisi deadlock adalah cara penanganan deadlock yang dilaksanakan apabila sistem telah
berada pada kondisi deadlock.
Sistem akan mendeteksi proses mana saja yang terlibat dalam kondisi deadlock. Setelah diketahui
proses mana saja yang mengalami kondisi deadlock,
maka diadakan mekanisme untuk memulihkan sistem dan menjadikan sistem berjalan
kembali dengan normal.
Mekanisme pendeteksian
adalah dengan menggunakan detection
algorithm yang akan
memberitahu sistem mengenai proses mana saja yang terkena deadlock. Setelah diketahui
proses mana saja yang terlibat dalam deadlock,
selanjutnya adalah dengan menjalankan mekanisme pemulihan sistem yang akan
dibahas pada bagian selanjutnya. Berikut ini adalah algoritma pendeteksian deadlock.
Penghindaran
Penghindaran terhadap deadlock adalah
cara penanganan yang selanjutnya. Inti dari penghindaran adalah jangan
sembarangan membolehkan proses untuk memulai atau meminta lagi. Maksudnya
adalah, jangan pernah memulai suatu proses apabila nantinya akan menuju ke
keadaan deadlock. Kedua, jangan memberikan kesempatan pada proses
untuk meminta sumber daya tambahan jika penambahan tersebut akan membawa sistem
pada keadaan deadlock. Tidak mungkin akan terjadi deadlock apabila
sebelum terjadi sudah kita hindari.
Langkah
lain untuk menghindari adalah dengan cara tiap proses memberitahu jumlah
kebutuhan maksimum untuk setiap tipe sumber daya yang ada. Selanjutnya
terdapat deadlock-avoidance algorithm yang secara rutin
memeriksa state dari sistem untuk memastikan tidak adanya
kondisi circular wait serta sistem berada pada kondisi safe
state. Safe state adalah suatu kondisi dimana semua proses
mendapatkan sumber daya yang dimintanya dengan sumber daya yang tersedia.
Apabila tidak bisa langsung, ia harus menunggu selama waktu tertentu, kemudian
mendapatkan sumber daya yang diinginkan, melakukan eksekusi, dan terakhir
melepas kembali sumber daya tersebut. Terdapat dua jenis algoritma penghindaran
yaitu resource-allocation graph untuk single instances
resources sertabanker's algorithm untuk multiple
instances resources.
Algoritma
penghindaran yang pertama yaitu resource-allocation graph akan
dijelaskan secara mendalam pada bab selanjutnya yaitu Diagram Graf. Untuk
algoritma yang kedua yaitu banker's algorithm akan dibahas
pada bab ini dan dilengkapi oleh pembahasan di bab selanjutnya.
Dalam banker's
algorithm, terdapat beberapa struktur data yang digunakan, yaitu:
- Available . Jumlah sumber daya yang
tersedia.
- Max . Jumlah sumber daya maksimum
yang diminta oleh tiap proses.
- Allocation . Jumlah sumber daya yang sedang
dimiliki oleh tiap proses.
- Need . Sisa sumber daya yang masih
dibutuhkan oleh proses, didapat dari max- allocation.
Kemudian
terdapat safety algorithm untuk menentukan apakah sistem
berada pada safe state atau tidak.
01 work dan finish adalah vektor yang
diinisialisasi:
work =
available
finish[i] = FALSE untuk i= 1,2,3,..,n-1.
02 cari i yang memenuhi finish[i] == FALSE dan
needi <= work
jika
tak ada, ke tahap 04
03 work = work + allocationi
finish
[i] = TRUE
kembali
ke tahap 02
04 jika finish[i]==TRUE untuk semua i, maka
sistem safe state.
Terdapat
juga algoritma lainnya yang menentukan apakah proses boleh melakukan permintaan
terhadap sumber daya tambahan atau tidak. Algoritma yang bertujuan memastikan
sistem tetap pada keadaan safe state ini dinamakan resource-request
algorithm.
Request = sumber daya yang dibutuhkan proses Pi.
Pada request,
Pi membutuhkan k instances dari Rj.
01 Jika Requesti <= Needi, ke tahap 02.
Selain
itu error karena melebihi maximum permintaan
02 Jika Requesti <= Available, ke tahap 03.
Selain
itu Pi harus menunggu karena tidak tersedia
03 Ubah kondisi state setelah request dikabulkan
Available = Available - Requesti
Allocationi = Allocationi + Requesti
Needi = Needi - Requesti
if safe
=> sumber daya dialokasikan pada Pi
if
unsafe => Pi menunggu, state kembali sebelumnya
Algoritma-algoritma
tersebut bertujuan untuk menghindarkan sistem dari terjadinya deadlock.
Keadaan dimana sistem bebas dari deadlock disebut safe
state. Jadi, semua kebutuhan proses akan sumber daya terpenuhi. Dampaknya
adalah sistem tidak mengalami deadlock. Selain safe state,
terdapat pula keadaan unsafe state. Pada keadaan ini, sistem
mempunyai kemungkinan untuk berada pada kondisi deadlock. Sehingga
cara yang paling jitu untuk menghindari deadlock adalah
memastikan bahwa sistem tidak akan pernah mengalami keadaan unsafe
state.
Referensi
0 komentar:
Post a Comment