0 Daumen
208 Aufrufe

Frage:

Zeichnen Sie für den aktuellen Systemzustand (unter der Annahme von X = 0) den Betriebsmittelbelegungsgraphen.

Es gibt die fünf Ressourcen r1, r2, r3, r4 und r5. Für die vier Prozesse P1, P2, P3 und P4 ist die Zuteilungsmatrix Z und Anforderungsmatrix A gegeben.

Z =


r1
r2
r3
r4
r5
P1
0
1
1
1
0
P2
0
0
1
1
2
P3
1
0
2
1
0
P4
1
1
1
1
0


A =


r1
r2
r3
r4
r5
P1
3
1
2
1
0
P2
2
1
1
1
3
P3
3
1
2
1
0
P4
1
1
1
2
1

Im aktuellen Zustand sind die Folgenden Ressourcen noch frei (X ganze Zahl):

r1
r2
r3
r4
r5
X
0
0
1
1


Ansatz/Problem:

Wie gehe ich hier vor? Zuerst die Summe der einzelnen Spalten von Z bilden. Dann den Verfügbarkeitsbektor bilden, aber dann kommen bei mir Minuswerte raus, das kann ja nicht sein, oder?

Avatar von

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Um den Betriebsmittelbelegungsgraphen für den gegebenen Zustand zu zeichnen und zu verstehen, wie die Zuteilung und Anforderung der Ressourcen zu den Prozessen erfolgt, folgen wir schrittweise der Vorgehensweise.

1. Berechnen des Verfügbarkeitsvektors:

Der Verfügbarkeitsvektor (V) gibt an, wie viele Ressourcen jeder Art insgesamt noch verfügbar sind, nachdem die Ressourcen an die Prozesse zugeteilt wurden.

Zuerst berechnen wir die Summe jeder Spalte in der Zuteilungsmatrix Z:

\( Z = \begin{array}{c|ccccc} & r1 & r2 & r3 & r4 & r5 \\ \hline P1 & 0 & 1 & 1 & 1 & 0 \\ P2 & 0 & 0 & 1 & 1 & 2 \\ P3 & 1 & 0 & 2 & 1 & 0 \\ P4 & 1 & 1 & 1 & 1 & 0 \\ \end{array} \)

Summe der Zuteilungen pro Ressource:
\( \text{Sum-R1} = 0 + 0 + 1 + 1 = 2 \)
\( \text{Sum-R2} = 1 + 0 + 0 + 1 = 2 \)
\( \text{Sum-R3} = 1 + 1 + 2 + 1 = 5 \)
\( \text{Sum-R4} = 1 + 1 + 1 + 1 = 4 \)
\( \text{Sum-R5} = 0 + 2 + 0 + 0 = 2 \)

Der verfügbare Vektor X = [X, 0, 0, 1, 1] ist noch nicht vollständig da X als Variable vorhanden ist. Stattdessen formen wir den Gesamtbestand der Ressourcen (T).

Nehmen wir an, T ist der Gesamte Bestand der Ressourcen:
\( T = [T1, T2, T3, T4, T5] \)

Der verfügbare Vektor V erhält man dann durch Abzug der Zuteilungen:
\( V = T - \text{Sum}(Z) \)

\( V = [T1 - 2, T2 - 2, T3 - 5, T4 - 4, T5 - 2] = [X, 0, 0, 1, 1] \)

Setzen Sie niedrigste Werte an (positive) für zugeteilte Ressourcen:
\\
Angenommen die tatsächlichen Ressourcen sind den maximal förderlichen Zuweisungen damit X = 2:
\( T = [4, 2, 5, 5, 3] \)

V:
\( V = [2, 0, 0, 1, 1] \)

2. Darstellung des Betriebsmittelbelegungsgraphen:

- Knoten: Prozesse (P1, P2, P3, P4) und Ressourcen (r1, r2, r3, r4, r5)
- Kanten von Prozessen zu Ressourcen zeigen die Anforderung.
- Kanten von Ressourcen zu Prozessen zeigen die Zuweisung.

python
import matplotlib.pyplot as plt
import networkx as nx

# Initialisiere Graph und dessen Knoten und Kanten
G = nx.DiGraph()

# Ressourcen Knoten
resources = ['r1', 'r2', 'r3', 'r4', 'r5']

# Prozesse Knoten
processes = ['P1', 'P2', 'P3', 'P4']

G.add_nodes_from(resources)
G.add_nodes_from(processes)

# Edge Lists (Process -> Resource), (Resource -> Process)
allocation_edges = [('r1', 'P3'), ('r1', 'P4'), ('r2', 'P1'), 
                    ('r2', 'P4'), ('r3', 'P1'), ('r3', 'P2'), 
                    ('r3', 'P3'), ('r3', 'P4'), ('r4', 'P1'), 
                    ('r4', 'P2'), ('r4', 'P3'), ('r4', 'P4'),
                    ('r5', 'P2')]

demand_edges = [('P1', 'r1'), ('P1', 'r2'), ('P1', 'r3'), ('P1', 'r4'),
                ('P2', 'r1'), ('P2', 'r2'), ('P2', 'r3'),
                ('P2', 'r4'), ('P2', 'r5'), ('P3', 'r1'),
                ('P3', 'r2'), ('P3', 'r3'), ('P3', 'r4'),
                ('P4', 'r1'), ('P4', 'r2'), ('P4', 'r3'),
                ('P4', 'r4'), ('P4', 'r5')]

G.add_edges_from(allocation_edges, color='blue')
G.add_edges_from(demand_edges, color='red')

# Positionierung Knoten
pos = nx.spring_layout(G)

# Zeichne Knoten
nx.draw_networkx_nodes(G, pos, node_size=7000, node_color='#ffffff', edgecolors='black')

# Zeichne Kanten
edges = G.edges()
colors = [G[u][v]['color'] for u, v in edges]
nx.draw_networkx_edges(G, pos, width=2, edge_color=colors)
    
# Knotenlabels
labels = {{r: r for r in resources}, {p: p for p in processes}}
nx.draw_networkx_labels(G, pos, labels)

plt.title('Betriebsmittelbelegungsgraph')
plt.show()


Erläuterung:
- Blaue Kanten zeigen Zuweisungen von Ressourcen zu Prozessen.
- Rote Kanten zeigen Anforderungen von Prozessen an Ressourcen.

So kann man den Betriebsmittelbelegungsgraphen für den gegeben Standpunkt X=2 herstellen und prüfen ob Deadlocks oder Engpässe vorhanden sind.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community