“DEADLOCK”

Oktober 18, 2010 at 1:05 pm Tinggalkan komentar

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 deadlock
Menurut Coffman( 1971 ) ada empat kondisi yang bisa mengakibatkan terjadinya deadlock, yaitu :
1. 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.
2. 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 lama
3. Tidak 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 berjalan
4. Circular Wait: adanya kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang dipegang proses berikutnya
Penanganan deadlock
Banyak cara untuk menanggulangi deadlock:
1. Mengabaikan masalah deadlock.
2. Mendeteksi dan memperbaiki
3. Penghindaran 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.
4. 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 deadlock
Metode 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 Memperbaiki
Caranya 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 kembali
setelah 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 :
1. Yang paling jarang memakai prosesor
2. Yang paling sedikit hasil programnya
3. Yang paling banyak memakai sumber daya sampai saat ini
4. Yang alokasi sumber daya totalnya tersedkit
5. 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( dalam arti tidak terkena deadlock), setelah itu baru dialokasikan. Ada dua cara yaitu:
1. Jangan memulai proses apapun jika proses tersebut akan membawa kita pada kondisi deadlock, sehingga tidak mungkin terjadi deadlock karena ketika akan menuju deadlock sudah dicegah
2. 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 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 Aman
Saat 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 Bankir
Menurut 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 :
1. Tersedia : jumlah sumber daya/dana yang tersedia
2. Maksimum : jumlah sumber daya maksimum yang diminta oleh setiap proses
3. Alokasi : jumlah sumber daya yang dibutuhkan oleh setiap proses
4. Kebutuhan : sumber daya yang sedang dibutuhkan oleh setiap proses

Pencegahan deadlock
Jika 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 :
1. 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.
2. 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.
3. 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.

4. Masalah Circular Wait Masalah ini dapat ditangani oleh sebuah protokol yang menjaga agar sebuah proses tidak membuat lingkaran siklus yang bisa mengakibatkan deadlock

Entry filed under: Uncategorized. Tags: .

“SISTEM INFORMASI AKUNTANSI ” (SIA) “E-BUSINESS”

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Kalender

Oktober 2010
S S R K J S M
« Sep   Nov »
 123
45678910
11121314151617
18192021222324
25262728293031

Most Recent Posts


%d blogger menyukai ini: