Deadlock
Deadlock
dalam arti sebenarnya adalah kebuntuan. Kebuntuan yang dimaksud dalam sistem
operasi adalah kebuntuan proses. Jadi Deadlock ialah suatu kondisi dimana
proses tidak berjalan lagi atau tidak ada komunikasi lagi antar proses.
Deadlock disebabkan karena proses yang satu menunggu sumber daya yang sedang
dipegang oleh proses lain, proses lain itu pun sedang menunggu sumber daya yang
dipegang olehnya. Dengan kata lain setiap proses dalam set menunggu untuk
sumber yang hanya dapat dikerjakan oleh proses lain dalam set sedang menunggu.
Contoh sederhananya ialah pada gambar berikut ini.
Gambar Deadlock
terjadi pada persimpangan jalan
Dalam
kasus ini setiap mobil bergerak sesuai nomor yang ditentukan, tetapi tanpa
pengaturan yang benar, maka setiap mobil akan bertemu pada satu titik yang
permanen (yang dilingkari) atau dapat dikatakan bahwa setiap mobil tidak dapat
melanjutkan perjalanan lagi atau dengan kata lain terjadi Deadlock. Kejadian
Deadlock selalu tidak lepas dari sumber daya, bahwa hampir seluruhnya merupakan
masalah sumber daya yang digunakan bersama-sama. Oleh karena itu, kita juga
perlu tahu tentang jenis sumber daya, yaitu: sumber daya dapat digunakan lagi
berulang-ulang dan sumber daya yang dapat digunakan dan habis dipakai atau
dapat dikatakan sumber daya sekali pakai. Sumber daya ini tidak habis dipakai
oleh proses mana pun.Tetapi setelah proses berakhir, sumber daya ini
dikembalikan untuk dipakai oleh proses lain yang sebelumnya tidak kebagian
sumber daya ini. Contohnya prosesor, Channel I/O, disk, semaphore. Contoh peran
sumber daya jenis ini pada terjadinya Deadlock ialah misalnya sebuah proses
memakai disk A dan B, maka akan terjadi Deadlock jika setiap proses sudah
memiliki salah satu disk dan meminta disk yang lain. Masalah ini tidak hanya
dirasakan oleh pemrogram tetapi oleh seorang yang merancang sebuah sistem
operasi. Cara yang digunakan pada umumnya dengan cara memperhitungkan dahulu
sumber daya yang digunakan oleh proses-proses yang akan menggunakan sumber daya
tersebut. Deadlock dari sumber yang dapat dipakai berulang-ulang ialah
berkaitan dengan jumlah proses yang memakai memori utama. Ada empat kondisi
yang dapat menyebabkan terjadinya deadlock. Keempat kondisi tersebut tidak
dapat berdiri sendiri, namun saling mendukung.
1. Mutual
exclusion. Hanya ada satu proses yang boleh memakai sumber daya, dan proses
lain yang ingin memakai sumber daya tersebut harus menunggu hingga sumber daya
tadi dilepaskan atau tidak ada proses yang memakai sumber daya tersebut.
2. Hold
and wait. Proses yang sedang memakai sumber daya boleh meminta sumber daya
lagi maksudnya menunggu hingga benar-benar sumber daya yang diminta tidak
dipakai oleh proses lain, hal ini dapat menyebabkan kelaparan sumber daya sebab
dapat saja sebuah proses tidak mendapat sumber daya dalam waktu yang lama.
3. No
preemption. Sumber daya yang ada pada sebuah proses tidak boleh diambil
begitu saja oleh proses lainnya. Untuk mendapatkan sumber daya tersebut, maka
harus dilepaskan terlebih dahulu oleh proses yang memegangnya, selain itu
seluruh proses menunggu dan mempersilahkan hanya proses yang memiliki sumber
daya yang boleh berjalan.
4. Circular
wait. Kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya
yang dipegang proses berikutnya.
Sebuah
sistem komputer terdiri dari berbagai macam sumber-daya (resources), seperti:
Ø Fisik
(Perangkat, Memori)
Ø Logika
(Lock, Database record)
Ø Sistem
Operasi (PCB Slots)
Ø Aplikasi
(Berkas)
Diantara
sumber-daya tersebut ada yang preemptable dan ada juga yang tidak. Sumber-daya
ini akan digunakan oleh proses-proses yang membutuhkannya. Mekanisme hubungan
dari proses-proses dan sumber-daya yang dibutuhkan/digunakan dapat di
diwakilkan dengan graf. Graf adalah suatu struktur diskrit yang terdiri dari
vertex dan sisi, dimana sisi menghubungkan vertexvertex yang ada. Berdasarkan
tingkat kompleksitasnya, graf dibagi menjadi dua bagian, yaitu simple graf dan
multigraf. Simpel graf tidak mengandung sisi paralel (lebih dari satu sisi yang
menghubungkan dua vertex yang sama). Berdasarkan arahnya graf dapat dibagi menjadi
dua bagian yaitu graf berarah dan graf tidak berarah. Graf berarah
memperhatikan arah sisi yang menghubungkan dua vertex, sedangkan graf tidak
berarah tidak memperhatikan arah sisi yang menghubungkan dua vertex. Dalam hal
ini akan dibahas mengenai implementasi graf dalam sistem operasi. Salah satunya
dalah graf alokasi sumber daya. Graf alokasi sumber daya merupakan graf
sederhana dan graf berarah. Graf alokasi sumber daya adalah bentuk visualisasi
dalam mendeteksi maupun menyelesaikan masalah deadlock. Graf alokasi sumber
daya mempunyai komponen- komponen layaknya graf biasa. Hanya saja dalam graf
alokasi sumber daya ini, vertex dibagi menjadi dua jenis yaitu:
1.
Proses P= {P0, P1, P2, P3,..., Pi,..., Pm}. Terdiri dari semua proses yang ada
di sistem. Untuk
proses,
vertexnya digambarkan sebagai lingkaran dengan nama prosesnya.
2.
Sumber daya R= {R0, R1, R2, R3,..., Rj,..., Rn}. Terdiri dari semua sumber daya
yang ada di
sistem.
Untuk sumber daya, vertexnya digambarkan sebagai segi empat dengan instansi
yang dapat dialokasikan serta nama sumber dayanya.
Sisi,
E={Pi®Rj,…, Rj®Pi} terdiri dari dua jenis, yaitu:
a.
Sisi permintaan: Pi®Rj Sisi permintaan menggambarkan adanya suatu proses Pi
yang meminta
sumber
daya Rj.
b.
Sisi alokasi: Rj®Pi. Sisi alokasi menggambarkan adanya suatu sumber daya Rj
yang
mengalokasikan
salah satu instansi-nya pada proses Pi.
Misalkan
suatu graph pengalokasian sumber daya dengan ketentuan sebagai berikut:
Himpunan
P,R dan E:
•
P={P1, P2, P3}
•
R={R1, R2, R3, R4}
•
E={P1®R1, P2®R3, R1®P3, R2®P2, R2®P1, R3®P3}
Instansi
sumber daya:
ü R1
memiliki satu instansi
ü R2
memiliki dua instansi
ü R3
memiliki satu instansi
ü R4
memiliki tiga instansi
Status
Proses:
ü Proses
P1 mengendalikan sebuah instansi R2 dan menunggu sebuah instansi dari R1.
ü Proses
P2 mengendalikan sebuah instansi dari R1 dan R2, dan menunggu sebuah instansi
R3
ü Proses
P3 mengendalikan sebuah instansi dari R3.
Pada
gambar graph di atas tidak terdapat adanya cycle, sehingga proses tidak
mengalami terjadinya deadlock. Sekarang perhatikan graph berikut yang terdapat
cycle dan memungkinkan terjadinya deadlock.
Terdapat
dua cycle (circuit) pada graph di atas yaitu:
P1®R1®P2®R3®P3®R2®P1
dan P2®R3®P3®R2®P2
Proses
P1, P2 dan P3 terjadi deadlock. Proses P2 menunggu R3, dimana sedang
dikendalikan oleh P3. Proses P3 di sisi lain sedang menunggu proses P1 dan P2
melepas sumber daya R2. Kemudian P1 menunggu proses P2 melepas sumber daya R1.
Sekarang perhatikan graph berikut yang terdapat cycle P1®R1®P3®R2®P1.
Walaupun
terdapat cycle namun pada proses-proses tersebut tidak terjadi deadlock. Proses
P4 akan melepas instansi sumber daya R2 yang akan dialokasikan untuk proses P3.
Solusi
Penanggulangan Deadlock
Add
beberapa cara untuk menanggulangi terjadinya deadlock, diantaranya adalah:
ü Mengabaikan
masalah deadlock.
ü Mendeteksi
dan memperbaiki
ü Penghindaran
yang terus menerus dan pengalokasian yang baik dengan menggunakan protocol
untuk memastikan sistem tidak pernah memasuki keadaan deadlock. Yaitu dengan
deadlock avoidance sistem untuk mendata informasi tambahan tentang proses mana
yang akan meminta dan menggunakan sumber daya.
ü Pencegahan
yang secara struktur bertentangan dengan empat kondisi terjadinya deadlock
dengan deadlock prevention sistem untuk memastikan bahwa salah satu kondisi
yang penting tidak dapat menunggu.
Mengabaikan
Masalah Deadlock
Untuk
memastikan sistem tidak memasuki deadlock, sistem dapat menggunakan pencegahan
deadlock atau penghindaran deadlock. Penghindaran deadlock membutuhkan
informasi tentang sumber daya yang mana yang akan suatu proses meminta dan
berapa lama akan digunakan. Dengan informasi tersebut dapat diputuskan apakah
suatu proses harus menunggu atau tidak. Hal ini disebabkan oleh keberadaan
sumber daya, apakah ia sedang digunakan oleh proses lain atau tidak. Metode ini
lebih dikenal dengan Algoritma Ostrich. Dalam algoritma ini dikatakan bahwa
untuk menghadapi Deadlock ialah dengan berpura-pura bahwa tidak ada masalah apa
pun. Hal ini seakanakan melakukan suatu hal yang fatal, tetapi sistem operasi
Unix menanggulangi Deadlock dengan cara ini dengan tidak mendeteksi Deadlock
dan membiarkannya secara otomatis mematikan program sehingga seakan-akan tidak
terjadi apa pun. Jadi jika terjadi Deadlock, maka tabel akan penuh, sehingga
proses yang menjalankan proses melalui operator harus menunggu pada waktu
tertentu dan mencoba lagi.
Mendeteksi
dan Memperbaiki
Caranya
ialah dengan cara mendeteksi jika terjadi deadlock pada suatu proses
maka dideteksi system mana yang terlibat di dalamnya. Setelah diketahui sistem
mana saja yang terlibat maka diadakan proses untuk memperbaiki dan menjadikan
sistem berjalan kembali. Jika sebuah sistem tidak memastikan deadlock akan
terjadi, dan juga tidak didukung dengan pendeteksian deadlock serta
pencegahannya, maka kita akan sampai pada kondisi deadlock yang dapat
berpengaruh terhadap performance sistem karena sumber daya tidak dapat
digunakan oleh proses sehingga proses-proses yang lain juga terganggu. Akhirnya
sistem akan berhenti dan harus direstart.
Hal-hal
yang terjadi dalam mendeteksi adanya Deadlock adalah:
ü Permintaan
sumber daya dikabulkan selama memungkinkan.
ü Sistem
operasi memeriksa adakah kondisi circular wait secara periodik.
ü Pemeriksaan
adanya deadlock dapat dilakukan setiap ada sumber daya yang hendak
digunakan oleh sebuah proses.
ü Memeriksa
dengan algoritma tertentu.
Ada
beberapa jalan untuk kembali dari Deadlock, yaitu:
ü Lewat
Preemption
Dengan
cara untuk sementara waktu menjauhkan sumber daya dari pemakainya, dan
memberikannya pada proses yang lain. Ide untuk memberi pada proses lain tanpa
diketahui oleh pemilik dari sumber daya tersebut tergantung dari sifat sumber
daya itu sendiri. Perbaikan dengan cara ini sangat sulit atau dapat dikatakan
tidak mungkin. Cara ini dapat dilakukan dengan memilih korban yang akan
dikorbankan atau diambil sumber dayanya untuk sementara, tentu saja harus
dengan perhitungan yang cukup agar waktu yang dikorbankan seminimal mungkin.
Setelah kita melakukan preemption dilakukan pengkondisian proses tersebut dalam
kondisi aman. Setelah itu proses dilakukan lagi dalam kondisi aman tersebut.
ü Lewat
Melacak Kembali
Setelah
melakukan beberapa langkah preemption, maka proses utama yang diambil sumber
dayanya akan berhenti dan tidak dapat melanjutkan kegiatannya, oleh karena itu
dibutuhkan langkah untuk kembali pada keadaan aman dimana proses masih berjalan
dan memulai proses lagi dari situ. Tetapi untuk beberapa keadaan sangat sulit
menentukan kondisi aman tersebut, oleh karena itu umumnya dilakukan cara
mematikan program tersebut lalu memulai kembali proses. Meski pun sebenarnya
lebih efektif jika hanya mundur beberapa langkah saja sampai deadlock tidak
terjadi lagi. Untuk beberapa sistem mencoba dengan cara mengadakan pengecekan
beberapa kali secara periodik dan menandai tempat terakhir kali menulis ke
disk, sehingga saat terjadi deadlock dapat mulai dari tempat terakhir
penandaannya berada.
ü Lewat
mematikan proses yang menyebabkan Deadlock
Cara
yang paling umum ialah mematikan semua proses yang mengalami deadlock. Cara ini
paling umum dilakukan dan dilakukan oleh hampir semua sistem operasi. Namun,
untuk beberapa sistem, kita juga dapat mematikan beberapa proses saja dalam
siklus deadlock untuk menghindari deadlock dan mempersilahkan proses lainnya
kembali berjalan. Atau dipilih salah satu korban untuk melepaskan sumber
dayanya, dengan cara ini maka masalah pemilihan korban menjadi lebih selektif,
sebab telah diperhitungkan beberapa kemungkinan jika si proses harus melepaskan
sumber dayanya.
Kriteria
pemilihan korban ialah:
ü Yang
paling jarang memakai prosesor
ü Yang
paling sedikit hasil programnya
ü Yang
paling banyak memakai sumber daya sampai saat ini
ü Yang
alokasi sumber daya totalnya tersedkit
ü Yang
memiliki prioritas terkecil
Menghindari
Deadlock
Pada
sistem kebanyakan permintaan terhadap sumber daya dilakukan sebanyak sekali
saja. Sistem sudah harus dapat mengenali bahwa sumber daya itu aman atau tidak
(tidak terkena deadlock), setelah itu baru dialokasikan. Ada dua cara yaitu:
ü Jangan
memulai proses apa pun jika proses tersebut akan membawanya pada kondisi
deadlock, sehingga tidak mungkin terjadi deadlock karena pada saat akan menuju
deadlock, proses sudah dicegah.
ü Jangan
memberi kesempatan pada suatu proses untuk meminta sumber daya lagi jika
penambahan ini akan membawa kita pada suatu keadaan deadlock. Jadi diadakan dua
kali penjagaan, yaitu saat pengalokasian awal, dijaga agar tidak deadlock dan
ditambah dengan penjagaan kedua saat suatu proses meminta sumber daya, dijaga
agar jangan sampai terjadi deadlock. Pada sistem deadlock avoidance
(penghindaran) dilakukan dengan cara memastikan bahwa program memiliki maksimum
permintaan. Dengan kata lain cara sistem ini memastikan terlebih dahulu bahwa
sistem akan selalu dalam kondisi aman. Baik mengadakan permintaan awal atau pun
saat meminta permintaan sumber daya tambahan, sistem harus selalu berada dalam
kondisi aman.
Status
Aman
Status
ini terjadi jika sistem dapat mengalokasikan sumber daya bagi tiap proses dalam
keadaan tertentu dan masih dapat terjadi deadlock. Status aman bukanlah status
deadlock, jadi status deadlock merupakan status tidak aman, tetapi tidak
selamanya status tidak aman mengakibatkan status deadlock melainkan ada kemungkinan
dapat terjadi.
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:
ü Sulit
untuk mengetahui seluruh sumber daya yang dibutuhkan proses pada awal eksekusi.
ü Jumlah
proses yang tidak tetap dan berubah-ubah.
ü Sumber
daya yang tadinya tersedia dapat saja menjadi tidak tersedia kembali.
ü Proses-proses
yang dieksekusi haruslah tidak dibatasi oleh kebutuhan sinkronisasi antar
proses.
ü Algoritma
ini menghendaki memberikan semua permintaan selama waktu yang berhingga.
Metode
ini mengunakan pendekatan dengan teknik untuk menentukan
apakahdeadlock 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 mainframeberukuran
besar.
Metode
ini akan menghapus proses-proses yang terlibat pada kondisi deadlockdengan
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 deadlockdapat
diatasi (memakan banyak waktu).
- Menghapus
proses berdasarkan prioritas, waktu eksekusi, waktu untuk selesai, dan
kedalaman dari rollback.
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.
Tidak ada komentar:
Posting Komentar