bankár algoritmus

Magyar

Kiejtés

• IPA: [ ˈbɒŋkaːrɒlɡoritmuʃ]

Főnév

bankár algoritmus

1. (matematika, algoritmusok)

1. Bankár-algoritmus (Banker’s Algorithm)

A Bankár-algoritmus egy erőforrás-ütemezési algoritmus, amelyet Edsger W. Dijkstra javasolt. Az algoritmus célja annak biztosítása, hogy egy többfolyamatú rendszer ne kerüljön holtpontra (deadlock). Az algoritmus a biztonságos állapot fogalmán alapul, és csak akkor teljesít egy erőforrás-allokációs kérelmet, ha az a rendszer számára biztonságos állapotot eredményez.

—

1. Alapfogalmak

1. Erőforrások: - Az erőforrások különböző típusokba vannak sorolva, például CPU-idő, memória, perifériák.

2. Folyamatok: - A rendszerben több folyamat fut, amelyek erőforrásokat igényelnek és szabadítanak fel.

3. Biztonságos állapot: - A rendszer egy állapota akkor biztonságos, ha létezik olyan sorrend a folyamatok között, amely biztosítja, hogy mindegyikük be tudja fejezni végrehajtását az erőforrások helyes felszabadítása után.

4. Erőforrás-allokációs mátrixok: - Max: A folyamatok által igényelt maximális erőforrások. - Allocation: Az egyes folyamatok által jelenleg használt erőforrások. - Need: Az erőforrások száma, amelyet a folyamatok még igényelhetnek (${\textstyle Need=Max-Allocation}$). - Available: Az aktuálisan elérhető erőforrások száma.

—

1. Algoritmus lépései

1. Inicializáció - Számítsd ki a Need mátrixot: $$Need[i][j]=Max[i][j]-Allocation[i][j]$$

2. Biztonságossági ellenőrzés - Az algoritmus ellenőrzi, hogy a kért erőforrások kiosztása után a rendszer biztonságos állapotban marad-e: 1. Készíts egy másolatot az Available erőforrásokról. 2. Jelöld ki a folyamatokat, amelyek befejezhetők (minden ${\textstyle Need[i]\leq Available}$). 3. Ha egy folyamat befejeződik, szabadítsd fel az általa használt erőforrásokat, és add hozzá azokat az Available-hez. 4. Ismételd a lépéseket, amíg minden folyamat befejezhető vagy nincs több befejezhető folyamat.

3. Allokációs kérés feldolgozása - Ha egy folyamat ${\textstyle P_{i}}$ erőforrást kér: 1. Ellenőrizd, hogy a kérés nem haladja meg ${\textstyle P_{i}}$ Need értékét. 2. Ellenőrizd, hogy az Available erőforrások elegendők-e a kérelem teljesítéséhez. 3. Szimuláld az allokációt, és futtasd a biztonságossági ellenőrzést. 4. Ha a rendszer biztonságos marad, teljesítsd a kérelmet. Ellenkező esetben utasítsd el.

—

1. Példa

1. Adatok:

- Erőforrástípusok: ${\textstyle A,B,C}$ - Available: $${\begin{bmatrix}3&3&2\end{bmatrix}}$$

- Max: $${\begin{bmatrix}7&5&3\\3&2&2\\9&0&2\\2&2&2\\4&3&3\end{bmatrix}}$$

- Allocation: $${\begin{bmatrix}0&1&0\\2&0&0\\3&0&2\\2&1&1\\0&0&2\end{bmatrix}}$$

1. 1. Need mátrix számítása: $$Need=Max-Allocation$$ $$Need={\begin{bmatrix}7&4&3\\1&2&2\\6&0&0\\0&1&1\\4&3&1\end{bmatrix}}$$

1. 2. Biztonságos állapot ellenőrzése:

1. Az ${\textstyle Available=[3,3,2]}$: - ${\textstyle P_{1}}$: ${\textstyle Need[1]=[1,2,2]\leq Available}$, tehát futtatható. - Felszabadított erőforrások: ${\textstyle Available=[5,3,2]}$.

2. ${\textstyle P_{3}}$: ${\textstyle Need[3]=[6,0,0]\leq Available}$, futtatható. - Felszabadított erőforrások: ${\textstyle Available=[7,3,4]}$.

3. ${\textstyle P_{4}}$: ${\textstyle Need[4]=[0,1,1]\leq Available}$, futtatható. - Felszabadított erőforrások: ${\textstyle Available=[7,4,5]}$.

4. ${\textstyle P_{0}}$: ${\textstyle Need[0]=[7,4,3]\leq Available}$, futtatható. - Felszabadított erőforrások: ${\textstyle Available=[7,5,5]}$.

5. ${\textstyle P_{2}}$: ${\textstyle Need[2]=[4,3,1]\leq Available}$, futtatható.

1. 1. Biztonságos sorrend: $$P_{1},P_{3},P_{4},P_{0},P_{2}$$

A rendszer biztonságos állapotban van.

—

1. Python implementáció

“‘python import numpy as np

def is_safe_state(available, max_matrix, allocation): num_processes, num_resources = allocation.shape need = max_matrix - allocation work = available.copy() finish = [False] * num_processes safe_sequence = []

while True: found = False for i in range(num_processes): if not finish[i] and all(need[i] <= work): work += allocation[i] finish[i] = True safe_sequence.append(i) found = True if not found: break

return all(finish), safe_sequence

1. Adatok available = np.array([3, 3, 2]) max_matrix = np.array([ [7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3] ]) allocation = np.array([ [0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2] ])

1. Biztonság ellenőrzése is_safe, safe_sequence = is_safe_state(available, max_matrix, allocation)

if is_safe: print(f"A rendszer biztonságos állapotban van. Biztonságos sorrend: safe_sequence") else: print("A rendszer nem biztonságos állapotban van.") “‘

Kimenet: “‘ A rendszer biztonságos állapotban van. Biztonságos sorrend: [1, 3, 4, 0, 2] “‘

—

1. Előnyök

1. Holtpontra érzékeny: - Biztosítja, hogy a rendszer ne kerüljön holtpontra. 2. Pontosság: - Biztonságos állapotok pontos ellenőrzése.

—

1. Hátrányok

1. Számításigény: - Nagy számú folyamat és erőforrás esetén az algoritmus költséges lehet. 2. Ismétlődő kérések kezelése: - Túl gyakori erőforrás-igények esetén bonyolultabb az ütemezés.

—

1. Alkalmazások

1. Operációs rendszerek: - Erőforrások kiosztása és holtpontkezelés. 2. Számítógépes rendszerek: - Virtuális gépek erőforrás-kezelése. 3. Gyártási rendszerek: - Feladatok ütemezése és gépkapacitás kezelése.

—

1. Összegzés

A Bankár-algoritmus egy hatékony módszer holtpontok megelőzésére és biztonságos állapot fenntartására többfeladatos rendszerekben. Bár számításigényes lehet, alapvető eszköz az erőforráskezelés területén.

Fordítások

Tartalom

angol: Banker's algorithm (en)

További információk

• bankár algoritmus - Értelmező szótár (MEK)
• bankár algoritmus - Etimológiai szótár (UMIL)
• bankár algoritmus - Szótár.net (hu-hu)
• bankár algoritmus - DeepL (hu-de)
• bankár algoritmus - Яндекс (hu-ru)
• bankár algoritmus - Google (hu-en)
• bankár algoritmus - Helyesírási szótár (MTA)
• bankár algoritmus - Wikidata
• bankár algoritmus - Wikipédia (magyar)