Definition von PDEVS

• Grundidee von Atomic PDEVS:
  • beschreibt Komponente durch ihr Verhalten
  • Bestandteile
    • Komponente hat Eingänge mit Werten aus Menge X
    • Komponente hat Ausgänge mit Werten aus Menge Y
    • Komponente ist in einem von vielen möglichen Zuständen aus der Menge S
    • Zustände haben eine Lebenszeit ta(s) (auch 0 oder ∞ möglich)
  • Verhalten
    • 
    • System sei im Zustand s₁
    • kein Input → Zustand geht nach der Zeit ta(s₁) in Folgezustand s₂ = δ_int(s₁) über
    • Input x nach Zeit e < ta(s₁) → Zustand geht in Folgezustand s₃ = δ_ext(s₁, e, x) über
    • Input genau bei anstehendem Zustandswechsel, also nach ta(s₁) → neuer Zustand mit δ_con(s₁, e, x)
  • Ausgabe
    • Ausgabewert λ(s₁), nur vom Zustand abhängig (Moore, nicht Mealy!)
    • direkt vor dem Wechsel des Zustands
    • also vor dem Aufruf von δ_int bzw. von δ_con
• Formale Definition von Atomic PDEVS:
  • Modell M gegeben durch M = (X, Y, S, δ_int, δ_ext, δ_con, λ, ta) mit
    

    • X = {(p, v) | p ∈ IPorts, v ∈ Xp}	Menge der Eingangsports und Werte
      Y = {(p, v) | p ∈ OPorts, v ∈ Yp}	Menge der Ausgangsports und Werte
      S	Menge der Zustände
      ta : S → [0, ∞]	Zeitfortschaltungsfunktion
      δint : S → S	interne Übergangsfunktion
      Q = {(s, e) | s ∈ S, 0 ≤ e < ta(s)}	Zustand s und Zeit e seit letzter Transition
      δext : Q × Xb → S	externe Übergangsfunktion
      δcon : S × Xb → S	konfluente Übergangsfunktion
      λ : S → Yb	Ausgabefunktion

  • IPorts bezeichnet die Eingabeports
    • am einfachsten IPorts = {1, 2, .., n_in} bei n_in Eingabeports
    • analog OPorts
  • Bedeutung von X^b
    • eine Eingabe enthält Port und (möglicherweise zusammengesetzten) Wert
    • es können mehrere Eingaben gleichzeitig an den Eingängen ankommen
    • darunter sogar mehrmals identische Werte
    • alle gleichzeitig eingetroffenen Port/Wert-Paare im Bag X^b (= Menge mit Wiederholungen) gesammelt
  • Eingabe-Beispiel mit n_in = 2
    • x = {{ (1,5), (2,3), (1,3), (2,3) }}
    • an Port 1 kommen gleichzeitig Werte 5 und 3 an
    • an Port 2 kommt Wert 3 zweimal gleichzeitig an
    • Reihenfolge der Werte ist irrelevant (wie bei Menge)
• Beispiel Generator:
  • einfaches Generatormodell von singleserver1B
    • liefert Entities (nur mit id) in festen Zeitabständen
    • Ausgang für Anzahl überflüssig, da mit Entity-id identisch
  • Anschlüsse
    • keine Eingänge, ein Ausgang A
    • A liefert in festen Zeitabständen t_G die Werte 1, 2, 3, ...
    • beginnt bei t_G
  • Implementierung in PDEVS
    • Zustand s speichert letzten ausgegebenen Wert, beginnt bei 0
    • ta(s) = t_G
    • λ(s) = s+1  (kommt vor dem Zustandswechsel!)
    • δ_int(s) = s+1
    • kein δ_ext, kein δ_con
• Beispiel Terminator:
  • einfaches Terminatormodell von singleserver1B
    • Eingang bekommt Entities
    • kein Ausgang
  • Implementierung in PDEVS
    • ein Eingang, kein Ausgang
    • Zustand s speichert Anzahl der eingegangenen Werte, beginnt bei 0
    • ta(s) = ∞
    • kein δ_int, kein λ, kein δ_con
    • δ_ext(s, e, {{(1,x₁), (1,x₂) ... (1,x_n)}}) = s+n
• Beispiel Server:
  • einfaches Servermodell mit Prozesszeit t_S
  • Anschlüsse
    • Eingang in für Entities
    • Ausgang out für Entities
    • Ausgang working (true/false) als Info zu vorgeschaltetem Block (Queue)
  • Verhalten (Prinzip)
    • startet in Zustand "idle"
    • Entity am Eingang → wechselt in "processing"
    • gibt nach Zeit t_S Entity aus und geht wieder in "idle"
  • Problem
    • bei Übergang in "processing" muss working = 1 ausgegeben werden
    • ist aber externes Event, daher keine Ausgabe möglich
    • Trick: Zwischenzustand "goProcessing" mit ta = 0
    • 
• Implementierung des Servers in PDEVS:
  • Eingang "in", Ausgänge "out", "working"
  • Zustand
    • phase: hat Werte 0|1|2 ("idle"|"goProcessing"|"processing")
    • entity: speichert die Entität (id = 1, 2, ..., 0 bei leer)
  • ta(s), λ(s), δ_int wie im Bild
  • δ_ext
    • bei "idle" Entity speichern und in "goProcessing"
    • bei "goProcessing"/"processing": Fehler (Eingang ist blockiert)
  • δ_con
    • erst δ_int, dann δ_ext
    • in "goProcessing": Fehler
    • in "processing": alte Entität raus, neue rein
    • Achtung: ist komplizierter (s.u.)
• Beispiel Queue:
  • einfaches Queuemodell ohne Kapazitätsbeschränkung
  • Anschlüsse
    • Eingang in für Entities
    • Eingang bl für Blocking-Status des Ausgangs
    • Ausgang out für Entities
  • Verhalten
    • 
• Implementierung der Queue in PDEVS:
  • Eingänge "in", "bl", Ausgang "out"
  • Zustand
    • phase: hat Werte 0|1|2|3 ("empty unblocked"|"empty blocked"|"queueing unblocked"|"queueing blocked")
    • queue: speichert den Vektor der Entitäten (ids als Werte)
    • n: speichert Länge der Queue (zur einfachen Anzeige)
  • Zustandsbeschreibung ist redundant
    • verschiedene Phasen für empty/queueing nicht nötig, da schon aus Länge von queue klar
    • erleichtert aber Verständnis und vereinfacht Programmierung
  • ta(s), λ(s), δ_int wie im Bild
  • δ_ext wie im Bild
    • bei mehreren bl-Werten letzten nehmen (sollte nicht sein)
    • bei mehreren in-Werten alle anhängen
    • bei in- und bl-Werten: beides bearbeiten und entsprechend weiterschalten
  • δ_con
    • erst δ_int, dann δ_ext
    • Achtung: Bug, s.u.!
• Coupled PDEVS:
  • Grundidee
    • Komponente besteht aus mehreren Atomic-PDEVS-Blöcken
    • hat selbst (externe) Ein- und Ausgänge
    • Verbindungen der externen Anschlüsse mit internen Komponenten definiert
    • Verbindungen der internen Komponenten untereinander definiert
    • verboten: Ausgang einer Komponente direkt an ihren Eingang
  • Eigenschaften
    • Ablauf genau definiert  [L8, Kap. 14.4], [16]
    • Coupled-PDEVS-Block kann als Atomic-PDEVS-Block definiert werden
    • → beliebige Hierarchiestufen aus Atomic- und Coupled-PDEVS-Komponenten möglich
  • formale Definition
    • Modell M gegeben durch N = (X, Y, D, M_D, C_EI, C_EO, C_I} mit

    • X = {(p, v) | p ∈ IPorts, v ∈ Xp}	Menge der Eingangsports und Werte
      Y = {(p, v) | p ∈ OPorts, v ∈ Yp}	Menge der Ausgangsports und Werte
      D	Menge der Komponentennamen
      MD = {Md | d∊D)	Menge der Atomic-PDEVS-Komponenten
      CEI ⊆ {(iN, d, i) | iN∊iPorts, d∊D, i∊IPortsd}	Menge der Verbindungen von externen Inputs zu Inputs interner Komponenten
      CEO ⊆ {(d, o, oN) | oN∊OPorts, d∊D, o∊OPortsd}	Menge der Verbindungen von Outputs interner Komponenten zu externen Outputs
      CI  ⊆ {(d1, o, d2, i) | d1,d2∊D, o∊OPortsd1, i∊IPortsd2}	Menge der Verbindungen zwischen internen Komponenten

• Gesamtmodell singleserver1B als Coupled PDEVS:
  • graphisch
    • 
  • keine Eingänge, keine Ausgänge (root model)
  • D = {"gen", "queue", "server", "term"}
  • M_D = {M_Generator, M_Queue, M_Server, M_Terminator}
  • C_EI, C_EO leer (mangels externer Anschlüsse)

  • CI =	('gen', 'out', 'queue', 'in'), ('queue', 'out', 'server', 'in'),
    	('server', 'out', 'term', 'in'), ('server', 'working', 'queue', 'bl')}

• Weiterentwicklung RPDEVS [14,15]:
  • Problem
    • betrachte Mealy-Komponente M₁ mit nachfolgender Komponente M₂
    • M₁ benötigt internen Zwischenzustand
    • ihr Output kommt später als der Output von M₂
    • → Ausgang von M₂ reagiert verspätet
  • Lösungsidee: λ hängt auch von Inputwerten ab → RPDEVS (Revised PDEVS)
  • detaillierte Umsetzung
    
    • macht Simulator deutlich komplizierter
    • macht Modellierung deutlich einfacher
  • ist das die Lösung?