Banker's algorithm

Banker's algorithm (tsz. Banker's algorithms)

1. (informatika) bankár algoritmus

A Bankár algoritmus egy dinamikus erőforrás-kezelési algoritmus, amit Edsger Dijkstra dolgozott ki 1965-ben. Az algoritmus célja, hogy a rendszert holtpontmentesen működtesse úgy, hogy az erőforrások elosztását biztonságosan végezze el, és biztosítsa, hogy a rendszer soha ne kerüljön nem biztonságos állapotba. A Bankár algoritmus működése alapvetően azon alapul, hogy minden egyes erőforrás-igénylési kérés előtt a rendszer egy biztonságos állapotot vizsgál, hogy elkerülje a holtpontot, és garantálja a folyamatok sikeres végrehajtását.

1. Erőforrás-osztályok többszörös példányból állnak: Egy adott erőforrás típusból több példány létezik. Például egy “nyomtató” erőforrást több példányban is rendelkezésre bocsáthatunk.
2. Minden folyamat előre meghatározza maximális erőforrás-igényét: Minden folyamat meghatározza, hogy maximum hány erőforrást igényelhet különböző típusú erőforrásokból.
3. A folyamatok várakozhatnak: Ha egy folyamat nem tudja megszerezni az összes szükséges erőforrást, akkor várakoznia kell, amíg más folyamatok felszabadítják az erőforrásokat.
4. A folyamatok erőforrásokat visszaadnak: Ha egy folyamat megkapja az erőforrásokat, akkor azokat a véges időn belül vissza kell adnia, hogy más folyamatok is használhassák őket.

A Bankár algoritmus segítségével a rendszer folyamatosan figyeli, hogy a kért erőforrások rendelkezésre állnak-e, és hogy a kérés teljesítése után a rendszer biztonságos állapotban marad-e. Ha a kérés teljesítése nem vezet biztonságos állapothoz, akkor azt elutasítja, és a folyamatnak várakoznia kell.

A Bankár algoritmushoz több adatszerkezet is szükséges:

• MAX: Ez egy n x m méretű mátrix, amely a folyamatok maximális erőforrás-igényeit tartalmazza. MAX azt jelzi, hogy az i-edik folyamat maximum hány erőforrást kérhet a j típusú erőforrásból.
• FOGLAL: Ez egy n x m méretű mátrix, amely azt tartalmazza, hogy az i-edik folyamat jelenleg hány erőforrást használ a j típusú erőforrásból.
• MÉG: Ez egy n x m méretű mátrix, amely azt mutatja, hogy az i-edik folyamatnak még hány erőforrásra van szüksége a befejezéshez. MÉG = MAX - FOGLAL.
• KÉR: Ez egy n x m méretű mátrix, amely az i-edik folyamat kért erőforrásait tartalmazza. Ha egy folyamat kérése meghaladja a rendszer által biztosított erőforrásokat, akkor a kérés elutasításra kerül.
• SZABAD: Ez egy vektor, amely a különböző típusú erőforrások szabad példányait jelzi.

A Bankár algoritmus három fő lépést követ, amikor egy folyamat kéri az erőforrást:

1. A kérés ellenőrzése:
   • Ha a kérés meghaladja a folyamat maximális igényét, akkor azonnal hibát jelez.
   • Ha a kért erőforrások nem állnak rendelkezésre (a kért erőforrások száma nagyobb, mint a szabad erőforrások száma), akkor a kérés nem teljesíthető, és a folyamat várakozik.
2. A nyilvántartás frissítése: Ha a kérés teljesíthető, a rendszer frissíti az erőforrás-nyilvántartást:
   • A SZABAD vektort csökkenti a kért erőforrásokkal.
   • A FOGLAL mátrixot frissíti azzal, hogy a kért erőforrást hozzáadja a folyamat által használt erőforrásokhoz.
   • A MÉG mátrixot csökkenti a kért erőforrással.
3. Biztonságos állapot ellenőrzése: A rendszer ekkor megvizsgálja, hogy a kért erőforrásokkal a rendszer biztonságos állapotban marad-e. Ehhez a következő lépések szükségesek:
   • A rendszer keres egy folyamatot, amely képes végrehajtani a szükséges munkát a most rendelkezésre álló szabad erőforrásokkal.
   • Ha nem található ilyen folyamat, és van várakozó folyamat, akkor holtpont léphet fel.
   • Ha sikerül találni egy folyamatot, akkor annak által birtokolt erőforrásokat visszaadjuk, és újra próbálkozunk.

Az alábbi C++ kód bemutatja a Bankár algoritmus működését:

#include <iostream>
#include <vector>
using namespace std;

class BankersAlgorithm {
private:
    int n; // Number of processes
    int m; // Number of resource types
    vector<vector<int>> MAX;   // Maximum demand matrix
    vector<vector<int>> ALLOC; // Allocation matrix
    vector<vector<int>> NEED;  // Need matrix
    vector<int> AVAILABLE;     // Available resources

public:
    BankersAlgorithm(int num_processes, int num_resources) : n(num_processes), m(num_resources) {
        MAX.resize(n, vector<int>(m, 0));
        ALLOC.resize(n, vector<int>(m, 0));
        NEED.resize(n, vector<int>(m, 0));
        AVAILABLE.resize(m, 0);
    }

    void initialize(vector<vector<int>> max, vector<vector<int>> alloc, vector<int> available) {
        MAX = max;
        ALLOC = alloc;
        AVAILABLE = available;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                NEED = MAX - ALLOC;
            }
        }
    }

    bool isSafeState() {
        vector<int> work = AVAILABLE;
        vector<bool> finish(n, false);
        int count = 0;

        while (count < n) {
            bool progressMade = false;
            for (int i = 0; i < n; i++) {
                if (!finish) {
                    bool canFinish = true;
                    for (int j = 0; j < m; j++) {
                        if (NEED > work) {
                            canFinish = false;
                            break;
                        }
                    }

                    if (canFinish) {
                        for (int j = 0; j < m; j++) {
                            work += ALLOC;
                        }
                        finish = true;
                        count++;
                        progressMade = true;
                    }
                }
            }

            if (!progressMade) {
                return false;
            }
        }
        return true;
    }

    bool requestResources(int process, vector<int> request) {
        for (int i = 0; i < m; i++) {
            if (request > NEED) {
                cout << "Error: Process has exceeded maximum claim." << endl;
                return false;
            }
        }

        for (int i = 0; i < m; i++) {
            if (request > AVAILABLE) {
                cout << "Error: Not enough available resources." << endl;
                return false;
            }
        }

        for (int i = 0; i < m; i++) {
            AVAILABLE -= request;
            ALLOC += request;
            NEED -= request;
        }

        if (isSafeState()) {
            cout << "Request granted." << endl;
            return true;
        } else {
            for (int i = 0; i < m; i++) {
                AVAILABLE += request;
                ALLOC -= request;
                NEED += request;
            }
            cout << "Request denied. The system would be in an unsafe state." << endl;
            return false;
        }
    }
};

int main() {
    int n = 5;
    int m = 3;

    BankersAlgorithm ba(n, m);

    vector<vector<int>> max = {
        {7, 5, 3},
        {3, 2, 2},
        {9, 0, 2},
        {2, 2, 2},
        {4, 3, 3}
    };

    vector<vector<int>> alloc = {
        {0, 1, 0},
        {2, 1, 1},
        {3, 2, 2},
        {2, 1, 1},
        {0, 0, 2}
    };

    vector<int> available = {3, 3, 2};

    ba.initialize(max, alloc, available);

    vector<int> request = {1, 0, 2};
    ba.requestResources(1, request);

    request = {2, 1, 1};
    ba.requestResources(4, request);

    return 0;
}

1. Inicializálás: A MAX, ALLOC, AVAILABLE és NEED mátrixok segítségével tároljuk a szükséges adatokat.
2. Biztonságos állapot vizsgálata: Az isSafeState() függvényben ellenőrizzük, hogy a rendszer biztonságos állapotban van-e a kért erőforrások után.
3. Erőforrás kérésének feldolgozása: A requestResources() függvény végrehajtja a kérés ellenőrzését, frissíti az erőforrásokat, és ha a rendszer biztonságos állapotban marad, teljesíti a kérést.

A Bankár algoritmus célja, hogy biztosítsa a rendszer működését holtpontmentesen, folyamatosan figyelve, hogy minden kért erőforrás nem vezet-e nem biztonságos állapotba. A fenti kód szimulálja az algoritmus működését, és lehetővé teszi erőforrások biztonságos kezelését.

• Banker's algorithm - Szótár.net (en-hu)
• Banker's algorithm - Sztaki (en-hu)
• Banker's algorithm - Merriam–Webster
• Banker's algorithm - Cambridge
• Banker's algorithm - WordNet
• Banker's algorithm - Яндекс (en-ru)
• Banker's algorithm - Google (en-hu)
• Banker's algorithm - Wikidata
• Banker's algorithm - Wikipédia (angol)