Banker Algoritması (Banker's Algorithm)

İşletim sistemi tasarımında kaynaklar üzerindeki kilitlenmeyi (deadlock) engelleme amaçlı algoritmadır. 

Şöyle bir sistem olduğunu varsayın:

      Allocation          Max        Available

       A B C D           A B C D     A B C D

P0    0 0 1 2             0 0 1 2       1 5 2 0

P1    1 0 0 0             1 7 5 0

P2    1 3 5 4             2 3 5 6

P3    0 6 3 2             0 6 5 2

P4    0 0 1 4             0 6 5 6

Sistemi Banker algoritmasına göre cevaplayınız.

a) Need (İhtiyaç) matrisini bulunuz?

Need=Max(Azami) - Allocation(Ayrım)

           Max    -   Allocation        Need

       A B C D      A B C D           A B C D           

P0    0 0 1 2   -     0 0 1 2             0 0 0 0

P1    1 7 5 0   -     1 0 0 0             0 7 5 0

P2    2 3 5 6   -     1 3 5 4             1 0 0 2

P3    0 6 5 2   -     0 6 3 2             0 0 2 0

P4    0 6 5 6   -     0 0 1 4             0 6 4 2

b)  Sistem güvenli durumda mıdır?

       Need                       Available

      A B C D                      A B C D 

P0   0 0 0 0                        1 5 2 0

P1   0 7 5 0

P2   1 0 0 2

P3   0 0 2 0

P4   0 6 4 2

  

 1. Work=Available

 2. Work=1 5 2 0

 3. Need<=Work

 4. Work=Work+Allocation

 5. P0: Finish[0]=T;

 6. Work=1 5 3 2

 7. P2: Finish[2]=T;

 8. Work=2 8 8 6

 9. P3: Finish[3]=T;

10. Work=2 14 11 8

11. P4: Finish[4]=T;

12. Work=2 14 12 12

13. P1: Finish[1]=T;

14. Work=3 14 12 12

Evet, sistem şu sıra ile P0; P2; P3; P4; P1 güvenli durumdadır.

Güvenlik Algoritması

Work = Available
Finish [i] = false, i = 0, 1,…,n- 1
1. Aşağıdaki şartları sağlayan i değerini bul: 
(a) Finish [i] = false
(b) Need <= Work
Şartları sağlayan bir i yoksa, 3. adıma git varsa devam et
2.  Work = Work + Allocation
Finish[i] = true
1. Adıma git
3. Tüm i değerleri için Finish [i] == true ise sistem güvenli durumdadır.

Deadlock(Kilitlenme) Simülasyonu

c) P1 işleminin (0, 4, 2, 0) isteği karşılanabilir mi?

Need=Max-Allocation

P1 işlemi için uygulanacak işlemler;

Need=Need – Request

Allocation=Allocation + Request

Available=Available – Request

           Max    -   Allocation        Need              Available

       A B C D      A B C D           A B C D             A B C D          

P0    0 0 1 2   -     0 0 1 2             0 0 0 0               1 1 0 0

P1    1 7 5 0   -     1 4 2 0             0 3 3 0

P2    2 3 5 6   -     1 3 5 4             1 0 0 2

P3    0 6 5 2   -     0 6 3 2             0 0 2 0

P4    0 6 5 6   -     0 0 1 4             0 6 4 2

 1. Work=Available

 2. Work=1 1 0 0

 3. Need<=Work

 4. Work=Work+Allocation

 5. P0: Finish[0]=T;

 6. Work=1 1 1 2

 7. P2: Finish[2]=T;

 8. Work=2 4 6 6

 9. P3: Finish[3]=T;

10. Work=2 10 9 8

11. P4: Finish[4]=T;

12. Work=2 10 10 12

13. P1: Finish[1]=T;

14. Work=3 14 12 12

P0; P2; P3; P4; P1 sırasıyla güvenli durumda ve P1’in (0,4,2,0) isteği karşılanabilir.

P_i İşlemi için Kaynak-İstek Algoritması

1.Eğer Request <= Need ise 2. adıma git, değilse hata ver maksimum
istek sayısı aşıldı.
2.Eğer Request <= Available ise, 3. adıma git, değilse, P(i)  beklemeli
 yeterli kaynak yok.
3.Kaynak-atama durumunu değiştirerek P(i)’nin istediği kaynakları 
P(i) ’ye verir gibi yap:
Available = Available  – Request;
Allocation(i) = Allocation(i) + Request(i);
Need(i) = Need(i) – Request(i);
Eğer güvenli ise, kaynaklar P(i) ’ye verilir
Güvenli değilse, P(i) beklemelidir ve kaynak-atama durumu eski 
haline getirilmelidir

Bir sonraki yazımda görüşmek üzere…