hkucuk

Banker Algoritması: Deadlock Önleme Algoritması

27 Mart 2024 • ☕️ 3 dk okuma • 🏷 bilgisayar, yazılım, algoritma, os

Yazar tarafından şu dillere çevrildi: English


Banker Algoritması, işletim sistemlerinde kullanılan ve deadlock (kilitlenme) olasılığını azaltmaya yardımcı olan bir algoritmadır. Deadlock birbirlerine ihtiyaç duyan işlemlerin veya kaynakların birbirini beklemesi sonucunda oluşan ve sistemde ilerleme engelleyen bir durumdur. Banker Algoritması bu tür kilitlenmeleri önlemek için tasarlanmıştır ve özellikle kaynak yönetimi gerektiren sistemlerde kullanılır.

Banker Algoritması bir sistemdeki kaynakları ve bu kaynakların işlemler tarafından talep edilen miktarlarını izler. Herhangi bir zamanda sistemdeki toplam kaynak miktarı bilinir. Algoritma her işlem için talep edilen kaynak miktarını takip eder ve işlemlerin belirli kaynakları ne kadar süreyle veya miktarlarda talep edebileceğini sınırlar. Bu sınırlar sistemdeki mevcut kaynakların talep edilen kaynak miktarını karşılayabilecek durumda olmasını sağlar.

Çalışma Adımları

Banker Algoritması’nın çalışma adımları şu şekildedir:

  1. Başlangıçta sistemdeki toplam kaynak miktarı ve her işlemin talep edebileceği maksimum kaynak miktarı belirlenir.
  2. Bir işlem kaynakları talep etmek için Banker Algoritması’na başvurduğunda, sistemdeki mevcut kaynak miktarıyla işlemin talep ettiği kaynak miktarı karşılaştırılır.
  3. Eğer sistemdeki mevcut kaynaklar, işlemin talep ettiği kaynakları karşılayabiliyorsa, işlem çalıştırılır ve kaynaklar işlem tarafından kullanılır. Aksi takdirde işlem bekleme moduna alınır.
  4. Bir işlem kaynakları serbest bıraktığında, serbest bırakılan kaynaklar diğer işlemlerin kullanımına açılır.
  5. Sistemde herhangi bir zaman işlemler için gerekli minimum kaynak miktarı hesaplanır. Bu hesaplama sonucunda, sistemdeki kaynakların kullanımı optimize edilir ve deadlock riski azaltılır.

Algoritma Karmaşıklığı

Banker Algoritması’nın zaman karmaşıklığı O(n^2) veya daha azdır, burada n sistemdeki işlem sayısını temsil eder.

Kullanım Alanları

Banker Algoritması özellikle çoklu işlemci sistemlerinde ve dağıtık sistemlerde kullanılır. Örneğin çoklu kullanıcılı işletim sistemlerinde, aynı anda birden fazla kullanıcı tarafından kaynak talebinde bulunulabilir. Banker Algoritması, bu talepleri yönetir ve kaynakları etkin bir şekilde dağıtarak sistemdeki performansı optimize eder.

Bir diğer örnek ise veritabanı yönetim sistemleridir. Birden fazla kullanıcı veritabanı kaynaklarına ihtiyaç duyabilir ve bu kaynakların etkin bir şekilde yönetilmesi gerekir. Banker Algoritması, veritabanı sistemlerinde deadlock riskini azaltmak için kullanılabilir.

GoLang’de Banker Algoritması uygulaması:

package main

import "fmt"

// Function to check if the system is in a safe state
func isSafe(processes [][]int, avail []int, need [][]int, finish []bool) bool {
    work := make([]int, len(avail))
    copy(work, avail)

    for count := 0; count < len(processes); count++ {
        found := false
        for p := 0; p < len(processes); p++ {
            if !finish[p] {
                canAllocate := true
                for r := 0; r < len(avail); r++ {
                    if need[p][r] > work[r] {
                        canAllocate = false
                        break
                    }
                }
                if canAllocate {
                    for r := 0; r < len(avail); r++ {
                        work[r] += processes[p][r]
                    }
                    finish[p] = true
                    found = true
                }
            }
        }
        if !found {
            return false
        }
    }
    return true
}

func main() {
    // Example data
    processes := [][]int{{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}}
    avail := []int{3, 3, 2}
    max := [][]int{{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}}

    // Calculate need matrix
    need := make([][]int, len(processes))
    for i := range need {
        need[i] = make([]int, len(avail))
        for j := range need[i] {
            need[i][j] = max[i][j] - processes[i][j]
        }
    }

    // Initialize finish array
    finish := make([]bool, len(processes))

    // Check if system is in a safe state
    safe := isSafe(processes, avail, need, finish)

    // Print result
    if safe {
        fmt.Println("Safe state")
    } else {
        fmt.Println("Unsafe state")
    }
}

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

Safe state or Unsafe state

Programın çalışır haline şuradan erişilebilir.

Banker Algoritması deadlock olasılığını azaltmaya yardımcı olan önemli bir algoritmadır. Ancak her zaman işe yarar olmayabilir ve bazı durumlarda sistem performansını etkileyebilir. Bu nedenle kullanılacağı sistem ve koşullar dikkatlice değerlendirilmelidir. Ayrıca algoritmanın karmaşıklığı ve uygulanabilirliği göz önünde bulundurulmalıdır.

Kaynaklar