Banker's Algorithm in Operating System [Příklad]

Co je to Banker's Algorithm?

Bankéřův algoritmus se používá hlavně v bankovním systému, aby se zabránilo zablokování. Pomůže vám určit, zda bude půjčka poskytnuta nebo ne.

Tento algoritmus se používá k testování bezpečné simulace alokace pro určení maximální částky dostupné pro všechny zdroje. Kontroluje také všechny možné činnosti, než určí, zda by alokace měla pokračovat či nikoli.

Například existuje X počet majitelů účtů u konkrétní banky a celková částka peněz na jejich účtech je G.

Když banka zpracovává půjčku na auto, softwarový systém setracVýše úvěru je částka poskytnutá na nákup automobilu z celkové částky (G + fixní vklad + měsíční příjem + zlato atd.), kterou banka má k dispozici.

Poskytuje autopůjčku pouze v případě, že zbývající částka stále přesahuje G, takže všichni majitelé účtu si mohou G kdykoli vybrat.

Zápisy bankéřských algoritmů

Zde je několik důležitých označení používaných v bankéřově algoritmu:

• X: Označuje celkový počet procesů v systému.
• Y: Označuje celkový počet zdrojů přítomných v systému.

Dostupný

[1:Y] označuje, kolik instancí každého typu zdroje je k dispozici.

Max

[1:X, 1:Y]: Vyjadřuje maximální počet zdrojů typu j, které může proces i vyžádat.

Přidělení

[1:X, 1:Y]: Označuje zdroje typu j aktuálně alokované procesu i.

Potřeba

Vyjadřuje, kolik dalších zdrojů každý typ procesu i ještě potřebuje k dokončení svého úkolu.

Příklad Bankerova algoritmu

Předpokládejme, že máme následující zdroje:

• 5 pero mechaniky
• 2 tiskárny
• 4 skenery
• 3 pevné disky

Zde jsme vytvořili vektor představující celkové zdroje: Dostupné = (5, 2, 4, 3).

Předpokládejme, že existují čtyři procesy. Dostupné zdroje jsou již alokovány podle maticové tabulky níže.

Název procesu	Pen Drive	Tiskárna	Skener	pevný disk
P	2	0	1	1
Q	0	1	0	0
R	1	0	1	1
S	1	1	0	1
Celková cena	4	2	2	3

Zde jsou alokované zdroje součtem těchto sloupců:

Přiděleno = (4, 2, 2, 3).

Vytváříme také matici pro zobrazení počtu každého zdroje potřebného pro všechny procesy. Tato matice se nazývá Potřeba = (3, 0, 2, 2).

Název procesu	Pen Drive	Tiskárna	Skener	pevný disk
P	1	1	0	0
Q	0	1	1	2
R	2	1	0	0
S	0	0	1	0

Dostupný vektor bude:

Dostupné = Dostupné – Přidělené

= (5, 2, 4, 3) – (4, 2, 2, 3)

= (1, 0, 2, 0)

Algoritmus požadavku na zdroj

Algoritmus pro požadavek na zdroj umožňuje reprezentovat chování systému, když konkrétní proces odešle požadavek na zdroj.

Pojďme si to vysvětlit pomocí následujících kroků:

Krok 1) Pokud je celkový počet požadovaných instancí všech zdrojů menší než proces, přejděte ke kroku 2.

Krok 2) Pokud je počet požadovaných instancí každého typu zdroje menší než počet dostupných zdrojů daného typu, bude proces přesunut do dalšího kroku. V opačném případě musí proces počkat z důvodu nedostupnosti dostatečných zdrojů.

Krok 3) Zdroj je alokován, jak je znázorněno v níže uvedeném pseudokódu.

Available = Available – Request (y)
Allocation(x) = Allocation(x) + Request(x)
Need(x) = Need(x) - Request(x)

Tento poslední krok se provádí proto, že systém musí předpokládat, že zdroje byly alokovány, takže po alokaci je k dispozici méně zdrojů.

Charakteristika Bankerova algoritmu

Zde jsou důležité charakteristiky bankéřova algoritmu:

• Uchovává mnoho zdrojů, které uspokojují požadavky alespoň jednoho klienta.
• Kdykoli proces získá všechny své zdroje, musí je v omezeném období vrátit.
• Když proces požaduje zdroj, může být nutné počkat.
• Systém má omezený počet zdrojů.
• Nabízí pokročilou funkci pro maximální alokaci zdrojů.

Nevýhoda Bankerova algoritmu

Zde jsou nevýhody/nevýhody používání bankéřova algoritmu:

• Neumožňuje procesu měnit svou maximální potřebu během zpracování.
• Umožňuje vyhovět všem žádostem v omezené lhůtě, ale jeden rok je pro to pevně stanovená lhůta.
• Všechny procesy musí předem znát a uvádět své maximální potřeby zdrojů.

Nejčastější dotazy