Oleh : Arief Ristanto ( ) Edwin Kurniawan ( )

DIAGRAM GRAF Oleh : Arief Ristanto (1204000149) Edwin Kurniawan (1204000297)

Pengertian Graf {

{

{

{

Graf adalah suatu struktur diskrit yang terdiri dari vertex dan sisi, dimana terdapat sisi yang menghubungkan vertex-vertex yang ada. Penggolongan graf : z

1. Menurut kompleksitas

z

2. Menurut arah

Graf alokasi sumber daya merupakan sebuah graf sederhana yang berarah. Graf ini adalah bentuk visualisasi dalam pendeteksian dan penanganan masalah deadlock.

©2005 Arief R, Edwin K Silakan menggandakan dan menyebarkan dokumen ini tanpa mengubah nota hak cipta

2

1

Komponen Graf Alokasi Sumber Daya : Vertex (1) 1. Proses P= {P0, P1, P2, P3… , P, i,… , Pm}. Terdiri dari semua proses yang ada di sistem. Vertexnya digambarkan sebagai lingkaran dengan nama prosesnya.


3

Komponen Graf Alokasi Sumber Daya : Vertex (2) 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 titik di dalamnya menunjukan jumlah instans yang dapat dialokasikan. Jangan lupa memberi nama sumber dayanya.


4

2

Komponen Graf Alokasi Sumber Daya : Edge o

Request Edge :

o

Assignment Edge:

Jika edge berasal dari P menuju ke R.

Jika edge berasal dari R menuju ke P

Notasi: P Æ R

Notasi: R Æ P

Rj


Rj

5

Contoh: Graf Alokasi Sumber Daya


6

3

Penjelasan dari Graf Graf tadi terdiri dari 7 vertex, V= {P0, P1, P2, P3 R0, R1, R2, R3} dan 5 edge, E = {P0ÆR0, R0ÆP1, R1ÆP1, R2ÆP0, R2ÆP2}. Graf menunjukkan: 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 ©2005 Arief R, Edwin K Silakan menggandakan dan menyebarkan dokumen ini tanpa mengubah nota hak cipta

7

Deteksi “Deadlock” dengan Graf Alokasi Sumber Daya {

Untuk mengetahui ada atau tidaknya deadlock dalam suatu graf dapat dilihat dari perputaran dan resource yang dimilikinya. Yaitu: 1. Jika tidak ada perputaran berarti tidak deadlock. 2. Jika ada perputaran, ada potensi terjadi deadlock. 3. Resource dengan instan tunggal dan perputaran mengakibatkan deadlock.


8

4

Graf dengan “Deadlock”


9

Graf Tanpa “Deadlock”


10

5

Algoritma Graf Alokasi Sumber Daya untuk Mencegah “Deadlock” { { {

{

Pada algoritma ini ada komponen tambahan pada sisi yaitu claimed edge. Claimed edge sebenarnya merupakan sisi permintaan yang digambarkan sebagai garis putus-putus. Ketika proses Pi memerlukan sumber daya Rj, claimed edge diubah menjadi sisi permintaan. Dan setelah proses Pi selesai menggunakan Rj, sisi 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.


11

Graf Alokasi Sumber Daya Dalam Status Aman


12

6

Graf Alokasi Sumber Daya Dalam Status Tidak Aman


13

Penjelasan {

Pada gambar pertama, R1 sedang tidak mengalokasikan sumber dayanya, sehingga P1 dapat memperoleh sumber daya R1. Namun, jika R1 langsung memberikan resource-nya kepada P1, maka akan menyebabkan terjadinya perputaran pada graf (gambar ke 2). Perputaran mengindikasikan bahwa sistem berada dalam status tidak aman.


14

7

Implementasi Algoritma Bankir {

Dalam sebuah sistem terdapat 4 proses yang akan siap di ready queue. Proses(Waktu Datang, Permintaan R1, Permintaan R2) P1(0, 3, 2), P2(0, 2, 1), P3(1, 2, 2) P4(1, 2, 1). Jumlah sumber daya R1=4, R2=3 Pemberian sumber daya berdasarkan aturan berikut: 1. Jika sumber daya yang dibutuhkan proses telah terpenuhi semuanya pada Tn, maka padaTn+1, sumber daya dilepas dan dapat dipakai oleh proses lain pada Tn+1.


15

Implementasi Algoritma Bankir 2. Jika ada dua proses yang sedang meminta sumber daya dan sumber daya yang tersedia hanya mencukupi salah satu proses, maka proses dengan ID terkecil didahulukan. Jika sumber daya dapat memenuhi semua proses yang meminta, maka sumber daya yang tersedia diberikan kepada semua proses yang membutuhkan.


16

8

Implementasi Algoritma Bankir T0

T1


17



T2

18

9


T3


19



20

10

Deteksi Deadlock dengan Graf Tunggu


21

Penjelasan Graf Tunggu {

{

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: 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 sisi 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.


22

11

Implementasi Graf Tunggu


23

Rangkuman { { {

{ {

Untuk mendeteksi deadlock dan menyelesaikannya dapat digunakan graf sebagai visualisasinya. Jika dalam graf terlihat adanya perputaran, maka proses tersebut memiliki potensi terjadi deadlock. Namun, jika dalam graf tidak terlihat adanya perputaran, maka proses tersebut tidak akan terjadi deadlock. Resource dengan satu instans dan cycle mengakibatkan deadlock. Untuk mengatasi deadlock yang terjadi, kita bisa menggunakan algoritma graf alokasi sumber daya.


24

12

Oleh : Arief Ristanto ( ) Edwin Kurniawan ( )

Recommend Documents