Rabu, 05 Juni 2013
Pengertian deadlock pada sistem operasi
Deadlock secara harfiah adalah kebuntuan, Di dalam sistem
operasi berarti suatu kondisi di mana sekumpulan proses tidak dapat berjalan
kembali atau tidak adanya komunikasi antar proses. Definisi lainnya yaitu sekumpulan
proses yang terblok yang tiap proses tersebut memegang sumber daya dan menunggu
untuk mendapatkan sumber daya yang dipegang oleh proses di dalam kumpulan
tersebut.
IlustrasiDeadlock
Penyebab utama terjadinya deadlock adalah terbatasnya sumber
daya yang akan digunakan oleh proses-proses. Tiap proses berkompetisi untuk
memperebutkan sumber daya yang ada. Jadi deadlock berhubungan erat dengan
tersedianya sumber daya dari komputer.
Penyebab utama terjadinya deadlock adalah terbatasnya sumber
daya yang akan digunakan oleh proses-proses. Tiap proses berkompetisi untuk
memperebutkan sumber daya yang ada. Jadideadlock berhubungan erat dengan
tersedianya sumber daya dari
komputer.
Karakteristik Deadlock
Menurut Coffman(1971) ada empat kondisi yang dapat menyebabkan
terjadinya deadloock. Keempat kondisi tersebut tidak dapat berdiri sendiri,
saling mendukung.
- Mutual Eksklusif: hanya ada satu proses yang bisa menggunakan sumber daya tersebut. Jika ada proses lain yang meminta sumber daya tersebut, maka proses itu harus menunggu sampai sumber daya dilepaskan.
- Memegang dan Menunggu: proses yang meminta sumber daya sudah memegang sumber daya lainnya(meminta sumber daya tambahan).
- Tidak ada Preemption: sumber daya yang sudah dialokasikan untuk sebuah proses tidak bisa diminta oleh proses lain. Sumber daya hanya bisa dilepaskan secara sukarela atau setelah proses tersebut selesai menggunakannya.
- Circular Wait(menunggu berputar): kondisi seperti rantai yaitu saling menunggu smber daya yang dipakai oleh proses yang menunggu sumber daya tersebut.
Method untuk Menangani Deadlock
Pada prinsipnya kita dapat menangani deadlock dengan
beberapa cara:
- Menggunakan protokol untuk pencegahan atau penghindaran deadlock, memastikan bahwa sistem tidak akan memasuki kondisi deadlock.
- Kita bisa mendeteksi terjadinya deadlock lalu memperbaiki.
- Kita juga bisa mengabaikan deadlock, hal ini dilakukan pada sistem operasi berbasis UNIX.
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. 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 system
karena sumber daya tidak dapat digunakan oleh proses sehingga proses-proses
yang lain juga terganggu. Akhirnya sistem akan berhenti dan harus direstart.
Pencegahan Deadlock
Pencegahannya sebagai berikut:
- Masalah Mutual Eksklusif, Kondisi ini tidak dapat dilarang, jika aksesnya perlu bersifat spesial untuk satu proses,maka hal ini harus didukung oleh kemampuan sistem operasi. Jadi diusahakan agar tidak menggunakan kondisi spesial tersebut sehingga sedapat mungkin deadlock dapat dihindari.
- Masalah Kondisi Menunggu dan Memegang Penanggulangan deadlock, dari kondisi ini lebih baik dan menjanjikan, asalkan kita dapat memegang sumber daya untuk menunggu sumber daya lain, kita dapat 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. Sistem operasi atau sebuah protokol mengatur hal ini. Hasil yang dapat terjadi adalah sumber daya lebih harus dispesifikasikan dan kelaparan sumber daya, atau proses yang membutuhkan sumber daya yang banyak harus menunggu sekian lama untuk mendapatkan sumber daya yang ia butuhkan.
- Masalah tidak preemption, Hal ketiga ialah jangan sampai ada preemption pada sumberv daya yang telah dialokasikan. Untuk memastikan hal ini, kita dapat menggunakan protocol. Jadi jika sebuah proses meminta sumber daya yang tidak dapat ia penuhi saat itu juga, maka proses mengalami preempted. Dengan kata lain ada sumber daya dilepaskan dan diberikan ke proses yang menunggu, dan proses itu akan menunggu sampai kebutuhan sumber dayanya dipenuhi. Cara lain yaitu dengan mengecek apakah sumber daya yang dicari proses tersedia atau tidak. Jika ada maka langsung dialokasikan tetapi jika tidak maka kita cek apakah ada proses lain yang sedang menunggu sumber daya juga. Jika ya maka kita ambil sumber daya dari proses yang sedang menunggu tersebut dan memberikan kepada proses yang meminta sumber daya tersebut. Jika tidak tersedia juga maka proses tersebut harus menunggu. Dalam menunggu beberapa dari sumber dayanya dapat saja dipreempted jika ada proses yang memintanya. Cara ini efektif untuk proses yang menyimpan dalam memory atau register.
- Masalah lingkaran tunggu, Masalah ini dapat ditangani oleh sebuah protocol yang menjaga agar sebuah proses tidak membuat lingkaran sikus yang dapat mengakibatkan deadlock dengan cara memberikan penomoran kepada sumber daya, dan bila suatu proses meminta sumber daya lagi maka ia hanya dapat meminta sumber daya yang nomornya lebih tinggi dari yang ia minta sebelumnya.
Penghindaran Deadlock
Algoritma Bankir Menurut Djikstra(1965) algoritma
penjadwalan dapat menghindari deadlock dan algoritma penjadwalan tersebut
dikenal dengan algoritma bankir. Algoritma ini dapat digambarkan, ada seorang
bankir yang akan meminjamkan kepada peminjam-peminjamnya. Setiap peminjam
memberikan batas pinjaman maksimum. Tentu saja bankir tahu bahwa peminjam tidak
akan meminjam dana maksimum secara langsung melainkan bertahap. Bankir
memprioritaskan kepada peminjam yang meminjam dana lebih banyak, sedangkan yang
lain disuruh menunggu hingga peminjam yang lebih besar mengembalikan dananya,
baru setelah itu ia meminjamkan kepada peminjam yang lain. Jadi algoritma
bankir disini mempertimbangkan apakah permintaan proses sesuai dengan jumlah
sumber daya yang ada dan sekaligus memperkirakan jumlah sumber daya yang
mungkin diminta lagi. Jangan sampai ketika ada proses yang meminta sumber daya
tetapi sumber dayanya habis atau tidak ada lagi jika tidak maka akan terjadi
deadlock.
Secara umum algoritma bankir dibagi menjadi 4 struktur data:
1. Tersedia: jumlah sumber daya yang tersedia
2. Alokasi: jumlah sumber daya yang dialokasikan untuk
setiap proses
3. Maksimum: jumlah permintaan sumber daya oleh proses
4. Kebutuhan: maksimum-alokasi(sisa sumber daya yang
dibutuhkan oleh proses setelah dikurangi dengan yang dialokasikan)
Pemulihan Deadlock
1. Terminasi Proses
Abort semua proses yang deadlock Metode ini akan mematahkan deadlock cycle, tetapi bisa saja
proses-proses yang deadlock telah dikomputasi dalam waktu yang lama dan
hasil-hasil komputasi parsial harus dibuang, sehingga ada kemungkinan harus
dikomputasi ulang. Abort satu proses pada satu waktu sampai deadlock
tereliminir. Metode ini sangat mungkin mendatangkan overhead, setelah setiap
proses di-abort, algoritma pendeteksian deadlock harus diminta kembali untuk
menentukan apakah masih ada proses-proses yang deadlock. Jika terminasi parsial
digunakan, kita harus menentukan proses-proses deadlock yang mana yang harus
diterminasi. Penentuan ini pada dasarnya berkaitan dengan ekonomi. Kita harus
abort proses-proses yang terminasinya minimum cost. Sayangnya, minimum cost
tidak ditentukan satu hal. Banyak faktor yang mempengaruhi pemilihan proses,
mencakup:
- Apa prioritas dari proses
- Berapa lama proses telah mengkomputasi dan berapa lama lagi proses akan mengkomputasi sebelum menyelesaikan tugasnya
- Berapa banyak dan apa tipe dari sumber daya yang digunakan oleh proses
- Berapa sumber daya lagi yang dibutuhkan proses supaya selesai
- Berapa banyak proses yang perlu diterminasi Apakah proses interactive atau batch
2. Preempt Sumber Daya
Mengeliminasi deadlock menggunakan preempt sumber daya
berarti kita berturut-turut preempt beberapa sumber daya dari suatu proses dan
memberikan sumber daya ini ke proses lain sampai deadlock cycle patah.
Pada preempt sumber daya terdapat :
- Memilih korban
Seperti pada terminasi proses, kita harus menentukan sumber
daya dan proses mana yang akan dipreempt dengan minimum cost. Faktor cost
mencakup parameter-parameter seperti jumlah dari sumber daya yang ditahan
proses-proses yang deadlock dan jumlah waktu dari proses yang telah digunakan
selama eksekusinya.
- Rollback
Jika kita preempt sebuah sumber daya dari sebuah proses,
proses tidak dapat berlanjut dengan eksekusi normal karena proses kehilangan
beberapa sumber daya yang diperlukan. Kita harus rollback proses ke beberapa
safe state dan restart dari state tersebut. Secara umum, sulit untuk menentukan
safe state. Solusi termudah adalah dengan total rollback, abort proses, dan
restart.
- Starvation
Dalam sebuah sistem di mana pemilihan korban berdasar primer
pada faktor cost, dapat terjadi suatu proses tidak pernah menyelesaikan
tugasnya karena suatu sumber daya selalu di-preempt pada proses yang sama. Kita
harus memastikan bahwa sebuah proses dapat dipilih sebagai korban hanya dengan
batasan waktu tertentu. Solusi pada umumnya adalah dengan menambahkan jumlah
rollback ke dalam faktor cost.
