DeadLock

Deadlock

Prinsip dari deadlock

Deadlock
ialah suatu kondisi permanen dimana proses tidak berjalan lagi
ataupun tidak ada komunikasi lagi antar proses.

Deadlock
disebabkan karena proses yang satu menunggu sumber daya yang
sedang dipegang oleh proses lain yang sedang menunggu sumber
daya yang dipegang oleh proses tersebut. Atau dengan kata lain
setiap proses dalam set menunggu untuk sumber yang hanya bisa
dikerjakan oleh proses lain dalam set yang sedang menunggu.
Contoh yang paling mudah ialah gambar berikut ini
Gambar 4-2. Contoh Deadlock Sederhana

Pada gambar diatas, tidak ada yang dapat maju karena
keduanya memperebutkan jalan yang sama ( yang dilingkari ),
demikian juga deadlock
saat semua proses memperebutkan sumber yang sama. Contoh lain
yang dapat merepresentasikan
deadlock
ialah jembatan gantung sebagai berikut :
Gambar 4-3. Contoh Deadlock di Jembatan Gantung

disadur dari Modern Operating
Systems , Tanenbaum , 1992 sehingga orang yang ada di sebelah kiri jembatan tidak
dapat melaju sebab terjadi
deadlock
di tengah jembatan ( bagian yang dilingkari ).Contoh lain ialah
di persimpangan jalan jalan berikut ini:
Gambar 4-4. Contoh Deadlock di Persimpangan Jalan

disadur dari buku Stallings, William, "Operating Systems -- Fourth Edition",
Prentice Hall, 2001 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 bisa dikatakan bahwa setiap mobil tidak bisa
meanjutkan perjalanan lagi atau dengan kata lain terjadi
deadlock.
Contoh lain pada proses yang secara umum terdiri dari tiga
tahap, yaitu untuk meminta, memakai, dan melepaskan sumber daya
yang di mintanya. Contoh kode-nya :
public class Proses {
public synchronized void getA() {
//proses untuk mendapat sumber daya a
}

public synchronized void getB(){
//proses untuk mendapat sumber daya b
}

public void releaseA(){
//proses untuk melepaskan sumber daya a
}

public void releaseB(){
//proses untuk melepaskan sumber daya b
}
}

public class Coba {
public static void main(String [] args) {
Proses P = new Proses();
Proses Q = new Proses();
P.getA();
Q.getB();
P.getB();
Q.getA();
}
}
tanpa adanya perintah untuk mereleased artinya saat P
mendapatkan A dan Q mendapatkan B, tetapi tidak dilepaskan,
maka saat P minta B dan Q minta A, maka keduanya akan saling
menunggu hingga salah satu melepaskan sumber dayanya, sedangkan
kebutuhan P ada pada Q dan Q ada pada P, sehingga terjadi
deadlock.
Secara umum kejadian ini dapat mudah terjadi dalam pemrograman
multi-thread. Sebab ada kemungkinan lebih besar untuk
menggunakan sumber daya bersama.Sumber Daya Kejadian deadlock
selalu tidak lepas dari sumber daya, seperti kita lihat dari
contoh contoh diatas, 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
bisa digunakan lagi berulang-ulang dan sumber daya yang bisa
digunakan dan habis dipakai atau bisa dikatakan sumber daya
sekali pakai.
Sumber Daya yang Bisa Dipakai Berulang-Ulang Sumber daya ini tidak habis dipakai oleh proses
manapun.Tetapi setelah proses berakhir, sumber daya ini
dikembalikan untuk dipakai oleh proses lain yang sebelumnya
tidak kebagian sumber daya ini. Contohnya prosesor, kanal
I/O, disk, semaphores. 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. Contoh lain yang menyebabkan
deadlock
dari sumber yang dapat dipakai berulang-ulang ialah berkaitan
dengan jumlah proses yang memakai memori utama. Contohnya
dapat dilihat dari kode berikut ini:
//dari kelas proses kita tambahkan method yaitu meminta
public void meminta( int banyakA ) {
//meminta dari sumber daya a
if ( banyakA < banyak )
banyak = banyak - banyakA;
else
wait();
}

//mengubah kode pada mainnya sebagai berikut
public static void main ( String [] args ) {
Proses P = new Proses();
Proses Q = new Proses();
P.meminta(80);
Q.meminta(70);
P.meminta(60);
Q.meminta(80);
}

private int banyak = 200;
private int banyakA;
Setelah proses P dan Q telah melakukan fungsi meminta
untuk pertama kali, maka sumber daya yang tersedia dalam
banyak ialah 50 ( 200-70- 80). Maka saat P menjalankan fungsi
meminta lagi sebanyak 60, maka P tidak akan menemukan sumber
daya dari banyak sebanyak 60, maka P akan menunggu hingga
sumber daya yang diminta dipenuhi. Demikian juga dengan Q,
akan menunggu hingga permintaannya dipenuhi, akhirnya terjadi
deadlock. Cara mengatasinya
dengan menggunakan memori maya.
Sumber Daya Sekali Pakai Dalam kondisi biasa tidak ada batasan untuk memakai
sumber daya apapun, selain itu dengan tidak terbatasnya
produksi akan membuat banyak sumber daya yang tersedia.Tetapi
dalam kondisi ini juga bisa terjadi
deadlock. Contohnya://menambahkan method receive dan send
public void receive( Proses p ){
//method untuk menerima sumber daya
}

public void send ( Proses p ){
//method untuk memberi sumber daya
}
dari kedua fungsi tersebut ada yang bertindak untuk
menerima dan memberi sumber daya, tetapi ada kalanya proses
tidak mendapat sumber daya yang dibuat sehingga terjadi blok,
karena itu terjadi deadlock.
Tentu saja hal ini sangat jarang terjadi mengingat tidak
ada batasan untuk memproduksi dan mengkonsumsi, tetapi ada
suatu keadaan seperti ini yang mengakibatkan
deadlock. Hal ini mengakibatkan
deadlock
jenis ini sulit untuk dideteksi. Selain itu
deadlock
ini dihasilkan oleh beberapa kombinasi yang sangat jarang
terjadi.Kondisi untuk Terjadinya
deadlockMenurut Coffman( 1971 ) ada empat kondisi yang bisa
mengakibatkan terjadinya
deadlock, yaitu :

Mutual Eksklusif:
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.
Memegang dan menunggu: 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 bisa menyebabkan
kelaparan sumber daya sebab bisa saja sebuah proses tidak
mendapat sumber daya dalam waktu yang lamaTidak ada
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 berjalanCircular Wait: adanya kondisi seperti rantai,
yaitu sebuah proses membutuhkan sumber daya yang dipegang
proses berikutnya
Penanganan
deadlockBanyak cara untuk menanggulangi
deadlock:
Mengabaikan masalah
deadlock.
Mendeteksi dan memperbaikiPenghindaran yang terus menerus dan pengalokasian
yang baik dengan menggunakan protokol untuk memastikan
sistem tidak pernah memasuki keadaan
deadlock

. Yaitu dengan
deadlock

avoidance sistem untuk men- data informasi tambahan
tentang proses mana yang akan meminta dan menggunakan
sumber daya.Pencegahan yang secara struktur bertentangan dengan
4 kondisi terjadinya
deadlock

dengan
deadlock

prevention sistem untuk memasti- kan bahwa salah satu
kondisi yang penting tidak dapat menunggu.
Mengabaikan Masalah
deadlockMetode ini lebih dikenal dengan Algoritma Ostrich.
Dalam algoritma ini dikatakan bahwa untuk menghadapi
deadlock

ialah dengan berpura-pura bahwa tidak ada masalah apapun. Hal
ini seakan-akan 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 apapun. Jadi jika terjadi
deadlock,
maka tabel akan penuh, sehingga proses yang menjalankan
proses melalui operator harus menunggu pada waktu tertantu
dan mencoba lagi.Mendeteksi dan MemperbaikiCaranya ialah dengan cara mendeteksi jika terjadi
deadlock
pada suatu proses maka dideteksi sistem mana yang terlibat di
dalamnya. Setelah diketahui sistem mana saja yang terlibat
maka diadakan proses untuk memperbaiki dan menjadikan sistem
berjalan kembali. Ada beberapa jalan untuk kembali dari
deadlock:
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 bisa dikatakan tidak mungkin. Cara ini
bisa dilakukan dengan memilih korban yang akan dikorbankan
atau diambil sumber dayanya utuk sementara, tentu saja
harus dengan perhitungan yang cukup agar waktu yang
dikorbankan seminimal mungkin.
Lewat melacak kembalisetelah kita lakukan 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. Meskipun 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 membunuh proses yang menyebabkan
deadlock.Cara yang paling umum ialah membunuh semua proses
yang mengalami
deadlock. Cara ini paling umum
dilakukan dan dilakukan oleh hampir
semua sistem operasi. Namun, untuk beberapa sistem, kita
juga dapat membunuh 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 seleksi korban ialah :
Yang paling jarang memakai prosesorYang paling sedikit hasil programnyaYang paling banyak memakai sumber daya sampai
saat iniYang alokasi sumber daya totalnya
tersedkitYang memiliki prioritas terkecil
Menghindari
deadlockPada sistem kebanyakan permintaan terhadap sumber daya
dilakukan sebanyak sekali saja. Sistem sudah harus dapat
mengenali bahwa sumber daya itu aman atau tidak( dalam arti
tidak terkena
deadlock),
setelah itu baru dialokasikan. Ada dua cara yaitu: Jangan memulai proses apapun jika proses tersebut
akan membawa kita pada kondisi
deadlock,
sehingga tidak mungkin terjadi
deadlock

karena ketika akan menuju
deadlock

sudah dicegahJangan 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
deadlock

avoidance sistem 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
ataupun saat meminta permintaan sumber daya tambahan, sistem
harus selalu berada dalam kondisi aman.Kondisi AmanSaat kondisi aman, maka suatu sistem bisa
mengalokasikan sumber daya pada setiap proses ( sampai pada
batas maksimumnya )dengan urutan tertentu. Dengan gambar
sebagai berikut :Gambar 4-5. Kondisi Deadlock Dilihat dari Safe State

disadur dari buku Silberschatz, dkk,
Applied Operating System Concepts,2000
Dengan mengenal arti dari kondisi aman ini, kita bisa
membuat algoritma untuk menghindari
deadlock. Idenya ialah dengan
memastikan bahwa sistem selalu berada
dalam kondisi aman. Dengan asumsi bahwa dalam kondisi tidak
aman terkandung
deadlock.
Contoh penerapan algoritmanya ialah
algoritma bankir.
Algoritma BankirMenurut Dijstra (1965) algoritma penjadwalan dapat
menghindari
deadlock

dan algoritma penjadwalan itu lebih dikenal dengan sebutan
algoritma bankir. Algoritma ini dapat digambarkan sebagai
seorang bankir dikota kecil yang berurusan dengan kelompok
orang yang meminta pinjaman. Jadi kepada siapa dia bisa
memberikan pinjamannya.Dan setiap pelanggan memberikan
batas pinjaman maksimum kepada setiap peminjam dana.Tentu saja si bankir tahu bahwa si peminjam tidak
akan meminjam dana maksimum yang mereka butuhkan dalam
waktu yang singkat melainkan bertahap. Jadi dana yang ia
punya lebih sedikit dari batas maksimum yang dipinjamkan.
Lalu ia memprioritaskan yang meminta dana lebih banyak,
sedangkan yang lain disuruh menunggu hingga peminta dana
yang lebih besar itu mengembalikan pinjaman berikut
bunganya, baru setelah itu ia meminjamkan pada peminjam
yang menunggu.Jadi algoritma bankir ini mempertimbangkan apakah
permintaan mereka itu sesuai dengan jumlah dana yang ia
miliki, sekaligus memperkirakan jumlah dana yang mungkin
diminta lagi. Jangan sampai ia sampai pada kondisi dimana
dananya habis dantidak bisa meminjamkan uang lagi. Jika
demikian maka akan terjadi kondisi
deadlock.
Agar kondisi aman, maka asumsi setiap pinjaman harus
dikembalikan waktu yang tepat.Secara umum algoritma bankir dapat dibagi menjadi 4
struktur data :
Tersedia : jumlah sumber daya/dana yang
tersediaMaksimum : jumlah sumber daya maksimum yang
diminta oleh setiap prosesAlokasi : jumlah sumber daya yang dibutuhkan oleh
setiap prosesKebutuhan : sumber daya yang sedang dibutuhkan
oleh setiap proses
Pencegahan
deadlockJika pada awal bab ini kita membahas tentang ke-empat
hal yang menyebabkan terjadinya
deadlock. Maka pada bagian ini,
kita akan membahas cara menanggulangi
keempat penyebab
deadlock
itu, sehingga dengan kata lain kita mengadakan pencegahan
terhadap
deadlock.
Penanggulangannya ialah sebagai berikut : Masalah Mutual Eksklusif Kondisi ini tidak dapat
dilarang, jika aksesnya perlu bersifat spesial untuk
satu proses, maka hal ini harus di dukung oleh
kemampuan sistem operasi. Jadi diusahakan agar tidak
mempergunakan kondisi spesial tersebut sehingga sebisa
mungkin
deadlock
bisa dihindari.Masalah Kondisi Menunggu dan Memegang
Penanggulangan
deadlock

dari kondisi ini lebih baik dan menjanjikan, asalkan
kita bisa menahan proses yang memegang sumber daya
untuk tidak menunggu sumber daya laun, kita bisa
mencegah
deadlock. Caranya ialah
dengan meminta semua sumber daya yang
ia butuhkan sebelum proses berjalan. Tetapi masalahnya
sebagian proses tidak mengetahui keperluannya sebelum
ia berjalan. Jadi untuk mengatasi hal ini, kita dapat
menggunakan algoritma bankir. Yang mengatur hal ini
bisa sistem operasi ataupun sebuah protokol. Hasil yang
bisa terjadi ialah sumber daya lebih di-spesifikasi dan
kelaparan sumber daya, atau proses yang membutuhkan
sumber daya yang banyak harus menunggu sekian lama
untuk mendapat sumber daya yang dibutuhkan.Masalah tidak ada
Preemption

Hal ketiga ialah jangan sampai ada
preemption

pada sumber daya yang telah dialokasikan. Untuk
memastikan hal ini, kita bisa menggunakan protokol.
Jadi jika sebuah proses meminta sumber daya yang tidak
dapat dipenuhi saat itu juga, maka proses mengalami
preempted. Atau dengan kata lain ada sumber daya
dilepaskan dan diberikan ke proses yang menunggu, dan
proses itu akan menunggu sampai kebutuhan sumber
dayanya dipenuhi.Atau kita harus mencek sumber daya yang dimaui
oleh proses di cek dahulu apakah tersedia. Jika ya maka
kita langsung alokasikan, sedangkan jika tidak tersedia
maka kita melihat apakah ada proses lain yang menunggu
sumber daya juga. Jika ya, maka kita ambil sumber daya
dari proses yang menunggu tersebut dan memberikan pada
proses yang meminta tersebut. Jika tidak tersedia juga,
maka proses itu harus menunggu. Dalam menunggu,
beberapa dari sumber dayanya bisa saja di preempted,
tetapi jika ada proses yang memintanya. Cara ini
efektif untuk proses yang menyimpan dalam memory atau
register.Masalah Circular Wait Masalah ini dapat
ditangani oleh sebuah protokol yang menjaga agar sebuah
proses tidak membuat lingkaran siklus yang bisa
mengakibatkan
deadlock