Diagram Graf

Komponen Alokasi Sumber Daya

Graf alokasi sumber daya mempunyai komponen-komponen layaknya graf biasa. Hanya saja dalam graf alokasi sumber daya ini, vertex dibagi menjadi 2 jenis yaitu:

1. Proses.�
   P = {P0, P1, P2, P3,.... , Pi}. P terdiri dari semua proses yang ada di sistem. Untuk proses, vertexnya digambarkan sebagai lingkaran dengan nama prosesnya.
   
   Gambar 24.1. Proses Pi
2. Resource .�
   Sumber daya R= {R0, R1, R2, R3, ...., Rj}. R terdiri dari semua sumber daya yang ada di sistem. Untuk sumber daya, vertexnya digambarkan sebagai segi empat dengan titik ditengahnya yang menunjukkan jumlah instans yang dapat dialokasikan serta nama sumber dayanya.
   
   Gambar 24.2. Sumber daya Rj

Proses dan resource dihubungkan oleh sebuah edge (sisi). Untuk edge, terdiri dari dua jenis yaitu:

1. Edge permintaan: Pi->Rj.�
   Edge permintaan menggambarkan adanya suatu proses Pi yang meminta sumber daya Rj
   
   Gambar 24.3. Proses Pi meminta sumber daya Rj
2. Edge Alokasi Sumber Daya: Rj->Pi.�
   Edge alokasi sumber daya menggambarkan adanya suatu sumber daya Rj yang mengalokasikan sumber dayanya pada Pi
   
   Gambar 24.4. Resource Rj meminta sumber daya Pi

Setelah mengetahui bentuk vertex dan edge yang digunakan, kita akan lihat bagaimana salah satu contoh penggunaan graf alokasi sumber daya.

Gambar 24.5. Contoh graf alokasi sumber daya

Graf diatas terdiri dari 6 vertex dan 5 edge, V= {P0, P1, P2, R0, R1, R2}

E = {P0-> R0, R0-> P1, R1-> P1, R2-> P0, R2-> P2}. Keterangan Graf diatas :

1. P0 meminta sumber daya dari R0
2. R0 memberikan sumber dayanya kepada P1
3. R1 memberikan salah satu instans sumber dayanya kepada P1
4. R2 memberikan salah satu instans sumber dayanya kepada P0
5. R2 memberikan salah satu instans sumber dayanya kepada P2

Setelah suatu proses telah mendapatkan semua sumber daya yang diperlukan maka sumber daya tersebut dilepas dan dapat digunakan oleh proses lain.Sebuah proses menggunakan resource dengan urutan sebagai berikut:

1. Mengajukan permohonan (request). Bila Permohonan tidak dapat dikabulkan dengan segera (misal karena resource sedang digunakan oleh proses lain), maka proses itu harus menunggu sampai resource yang dimintanya tersedia.
2. Menggunakan resource (use). Proses dapat menggunakan resource, misal : printer untuk mencetak, disk drive untuk melakukan operasi M/K , dan sebagainya .
3. Melepaskan resource (release). Setelah proses menyelesaikan penggunaan resource, maka resource harus dilepaskan sehingga dapat digunakan oleh proses lain.

Metode Penghindaran

Bila metode prevention lebih menekankan pada cara permintaan sehingga keempat kondisi yang dapat menyebabkan deadlock tidak terjadi bersamaan, maka metode avoidance lebih mengarah pada perlunya informasi tambahan dari proses mengenai bagaimana resource akan diminta.
Pada saat sebuah proses mengajukan permintaan untuk menggunakan resource yang tersedia, maka algoritma avoidance akan bekerja dengan mendeteksi apakah alokasi yang diberikan dapat menyebabkan sistem dalam safe state. Bila keadaan hasilnya sistem safe state, maka resource akan dialokasikan untuk proses tersebut, tetapi bila sebaliknya maka permintaan akan ditolak.
Sebuah sistem berada dalam safe state bila terdapat safe sequence dimana proses yang memerlukan resource dapat ditangani. Bila P1 selesai menggunakan resource dan melepaskannya, maka P2 dapat menggunakan resource yang sedang digunakannya dan resource yang dilepas oleh P1 dapat digunakan P2 untuk menyelesaikan tugasnya dan kemudian melepaskan resource untuk digunakan oleh P3, dan seterusnya

Algoritma Graf Alokasi Sumber Daya Untuk Mencegah Deadlock

Algoritma ini dapat dipakai untuk mencegah deadlock jika sumber daya hanya memiliki satu instans. Pada algoritma ini ada komponen tambahan pada edge yaitu Claimed Edge. Sama halnya dengan edge yang lain, claimed edge menghubungkan antara sumber daya dan simpul.
Claimed edge Pi ---> Rj berarti bahwa proses Pi akan meminta sumber daya Rj pada suatu waktu. Claimed edge sebenarnya merupakan edge permintaan yang digambarkan sebagai garis putus-putus. Ketika proses Pi memerlukan sumber daya Rj, claimed edge diubah menjadi edge permintaan. Dan setelah proses Pi selesai menggunakan Rj, edge alokasi diubah kembali menjadi claimed edge. Dengan algoritma ini bentuk perputaran pada graf tidak dapat terjadi. Sebab untuk setiap perubahan yang terjadi akan diperiksa dengan algoritma deteksi perputaran.
Algoritma ini memerlukan waktu n ² dalam mendeteksi perputaran dimana n adalah jumlah proses dalam sistem. Jika tidak ada perputaran dalam graf, maka sistem berada dalam status aman. Tetapi jika perputaran ditemukan maka sistem berada dalam status tidak aman. Pada saat status tidak aman ini, proses Pi harus menunggu sampai permintaan sumber dayanya dipenuhi.

Gambar 24.6. Graf Alokasi Sumber Daya dalam status aman

Pada saat ini R1 sedang tidak mengalokasikan sumber dayanya, sehingga P1 dapat memperoleh sumber daya R1. Namun, jika claimed edge diubah menjadi edge permintaan dan kemudian diubah menjadi edge alokasi, hal ini dapat menyebabkan terjadinya perputaran.

Gambar 24.7. Graf dengan Deadlock

Dari gambar diatas kita dapat melihat terjadinya deadlock yang disebabkan oleh P0 memerlukan sumber daya R0 untuk menyelesaikan prosesnya, sedangkan R0 dialokasikan untuk P1. Di lain pihak P1 memerlukan sumber daya R1 sedangkan R1 dialokasikan untuk P2. P2 memerlukan sumber daya R2 akan tetapi R2 mengalokasikan sumber dayanya pada P1.

1. R2 ->P0 ->R0 ->P1 -> R1 -> P2 -> R2
2. R2 -> P1-> R1 -> P2 -> R2

Gambar 24.8. Contoh Graf tanpa Deadlock

Gambar di atas menunjukkan beberapa hal sebagai berikut:

1. P0 meminta sumber daya dari R1
2. R1 memberikan sumber dayanya kepada P1
3. R1 memberikan satu instans sumber dayanya kepada P2
4. P2 meminta sumber daya pada P0
5. R0 memberikan sumber daya pada P3
6. P3 meminta sumber daya pada R2
7. R2 mengalokasikan sumber daya pada P0

Metode Pendeteksian

Deadlock akan terjadi, jika dan hanya jika grafik tunggu memiliki siklus di dalamnya.Untuk mendeteksi deadlock, sistem harus memiliki grafik tunggu dan menjalankan algoritma deteksi deadlock secara periodik. Hal yang harus diperhatikan adalah seberapa sering algoritma deteksi harus dipanggil. Hal ini tergantung dari dua faktor:

1. Frekuensi terjadinya deadlock pada umumnya
2. Jumlah proses yang akan terpengaruh ketika deadlock terjadi.

Bila deadlock terjadi maka algoritma deteksi harus sering dipanggil. Resource yang dialokasikan ke proses-proses yang mengalami deadlock tidak akan digunakan sampai kondisi deadlock diatasi. Bila deadlock tidak segera diatasi maka jumlah proses yang terlibat dalam deadlock akan semakin bertambah.
Salah satu ciri terjadinya deadlock adalah ketika beberapa proses mengajukan permohonan untuk resource, tetapi permohonan ini tidak dapat dipenuhi dengan segera. Sistem dapat saja memanggil algoritma deteksi setiap kali permohonan untuk resource tidak dapat diperoleh dengan segera. Namun,semakin sering algoritma deteksi dipanggil, maka waktu overhead yang dibutuhkan untuk komputasi menjadi semakin besar.
Jika semua sumber daya hanya memiliki satu instans, deadlock dapat dideteksi dengan mengubah graf alokasi sumber daya menjadi graf tunggu. Ada pun caranya sebagai berikut:

Gambar 24.10. Contoh Graf Alokasi Sumber Daya yang akan diubah menjadi graf tunggu

1. Cari sumber daya Rm yang memberikan instansnya pada Pi dan Pj yang meminta sumber daya pada Rm.
2. Hilangkan sumber daya Rm dan hubungkan edge Pi dan Pj dengan arah yang bersesuaian yaitu Pj -> Pi.
3. Lihat apakah terdapat perputaran pada graf tunggu? deadlock terjadi jika dan hanya jika pada graf tunggu terdapat perputaran.

Gambar 24.11. Contoh Graf Tunggu

Untuk mendeteksi deadlock, sistem perlu membuat graf tunggu dan secara berkala memeriksa apakah ada perputaran atau tidak. Untuk mendeteksi adanya perputaran diperlukan operasi sebanyak n ², dimana n adalah jumlah simpul dalam graf alokasi sumber daya.