Deadlock — Minimale Ressourcen
Mindestanzahl an Ressourcen, ab der ein Deadlock prinzipiell vermieden wird: MinRes = Prozesse · (MaxBedarf − 1) + 1.
Deadlock — Minimale Ressourcen berechnen
Mindestanzahl an Ressourcen, ab der ein Deadlock prinzipiell vermieden wird: MinRes = Prozesse · (MaxBedarf − 1) + 1.
- MinRes — Min. Ressourcen
- Prozesse — Prozessanzahl
- MaxBedarf — Max. Bedarf pro Prozess
Worum geht es?
Wenn N Prozesse jeweils maximal M Exemplare einer Ressource benötigen, lässt sich ein Deadlock garantiert verhindern, sobald insgesamt mindestens N · (M − 1) + 1 Exemplare zur Verfügung stehen. Im schlimmsten Fall belegen alle Prozesse je (M − 1) Exemplare und blockieren sich gegenseitig — das eine zusätzliche Exemplar erlaubt mindestens einem Prozess, fertig zu werden, danach werden seine Ressourcen freigegeben.
Das ist die klassische Schubfach-Argumentation aus dem Banker-Kontext und liefert die Mindestanzahl, ab der eine sichere Allokation möglich ist.
Die Formel
MinRes = Prozesse · (MaxBedarf − 1) + 1
Umstellungen:
Prozesse = (MinRes − 1) / (MaxBedarf − 1)
MaxBedarf = (MinRes − 1) / Prozesse + 1Die Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| Prozesse | Prozessanzahl | — | Anzahl konkurrierender Prozesse. |
| MaxBedarf | Max. Bedarf pro Prozess | — | Maximaler Ressourcenbedarf eines einzelnen Prozesses. |
| MinRes | Min. Ressourcen | — | Mindestanzahl an Ressourcen zur Deadlock-Vermeidung. |
Minimal-Beispiel
Drei Prozesse, jeder benötigt maximal 2 Exemplare.
MinRes = 3 · (2 − 1) + 1
= 3 + 1
= 4Praxis-Beispiele
Beispiel 1 — Klassisches Schulbuch-Beispiel
5 Prozesse, jeweils max. 4 Bandlaufwerke nötig.
MinRes = 5 · (4 − 1) + 1
= 15 + 1
= 16Beispiel 2 — Max. Prozesse bei Ressourcenlimit
Bei 22 Ressourcen und MaxBedarf 5 pro Prozess.
Prozesse = (22 − 1) / (5 − 1)
= 21 / 4
= 5,25 → max. 5 ProzesseBeispiel 3 — Zulässiger MaxBedarf
10 Ressourcen, 3 Prozesse — welcher MaxBedarf bleibt sicher?
MaxBedarf = (10 − 1) / 3 + 1
= 3 + 1
= 4