Dr. Welf Löwe und Markus Noga 1
Gliederung: Teil 3 - Anpassungen
1. Einführung– Motivation– Definition, – Konzepte für Komponenten (klassische, kommerzielle, akademische)
2. Industrielle Komponentensysteme der 1. Generation1. CORBA 2. Enterprise JavaBeans3. (D)COM
3. Anpassungen – Daten und Funktion– Interaktion
• Kommunikation• Synchronisation• Protokolle
– Lebendigkeit
Dr. Welf Löwe und Markus Noga 2
Problem
Komponenten mit ZustandAufruf der Methoden (Dienste) bewirkt ZustandstransformationenNicht jeder Dienst kann in jedem Zustand erbracht werdenProtokoll beschreibt Folgen möglicher „Dienstleistungen“ einer Komponente
Beispiele
Komponente „Datei“:open (read | write )* closeKomponente „Keller“:(pushn popn)*Thermostat: (zu kalt | zu heiss)*Telefonleitung:Abheben (
Ziffer* ( Aufgelegt | Timeout | NummerKorrekt ( besetzt | klingelt ( Aufgelegt |
Angenommen Sprachdaten*(Aufgelegt|RemoteAufgelegt) ))))*
Dr. Welf Löwe und Markus Noga 4
Definitionen
Protokoll:– Menge von Folgen von Methodenaufrufen– Formale Sprache mit Methoden als Alphabet
Komponentenprotokoll K– Protokoll (Sprache), das legale Aufruffolgen von Methoden einer
Komponente definiert
Aufrufprotokoll A– Protokoll, das die tatsächliche Verwendung einer Komponente
definiert
Dr. Welf Löwe und Markus Noga 5
Korrekte Verwendung
Sei prefix(K) die Menge aller Methodenfolgen, die Anfang eines Satzes aus K sind. Komponente wird korrekt verwendet, wenn
A prefix(K)oder
A KFrage, ob Endzustand erreicht werden mussWas gelten muss, hängt von der Komponente ab (Datei vs. Keller)
Dr. Welf Löwe und Markus Noga 6
Anpassung
Wrapper um die Komponente– Generiert notwendige Methoden– Konsumiert überflüssige Methoden– Blockt Methoden, die ungelegen kommen, dadurch Umsortieren von
Methodenaufrufen zur Laufzeit
Insgesamt teuere Operationen
Was kann bereits statisch erkannt werden?
Dr. Welf Löwe und Markus Noga 7
Problem
...File f=new File();File g=new File();f=g;f.open(...);g.open(...);f.write(...);g.write(...);...
File g ist „Alias“ für File fUm festzustellen, ob Komponenten richtig verwendet werden, müssen „Aliases“ gefunden werden
Dr. Welf Löwe und Markus Noga 8
Problem
...File f=new File();File g=new File();if someFunc() f=g;f.open(...);g.open(...);f.write(...);g.write(...);...
File g ist vielleicht „Alias“ für File fFinden von „Aliases“ ist unentscheidbarErgebnis von someFunc() müsste statisch geraten werden können
Dr. Welf Löwe und Markus Noga 9
Aliasproblem
Komponente kann durch mehrere Ausdrücken (Zugriffspfaden) referenziert werden (alias)Komponentenprotokoll kann durch alle Aliases fortgeschaltet werdenFinden von Aliases ist unentscheidbar
Lösung– Points-To Analyse– Typsplitting
Dr. Welf Löwe und Markus Noga 10
Points-To Analyse
DatenflussanalyseDatenstruktur ist– Steuerflussgraph– SSA Graph des Programms
Jedem Ausdruck im Programm wird Menge von Definitionen zugeordnetAktualisierung bei Zuweisung, ProzeduraufrufMay und Must Problem unterschieden– Unterschiedliche Behandlung bei Zusammenflüssen im
Steuerflussgraph
Dr. Welf Löwe und Markus Noga 11
Points-To (May)
...File f=new File();File g=new File();if someFunc() f=g;f.open(...);g.open(...);f.write(...);g.write(...);...
new
new
if
=
f=#1 g=?
f=#2
f={#1,#2}
f={#1,#2}
f={#1,#2}
f={#1,#2}
f=#1
g=#2
g=#2
g=#2
g=#2
g=#2
g=#2
Dr. Welf Löwe und Markus Noga 12
Points-To (Must)
...File f=new File();File g=new File();if someFunc() f=g;f.open(...);g.open(...);f.write(...);g.write(...);...
new
new
if
=
f= #1 g=?
f= #2
f=
f=
f=
f=
f= #1 g=#2
g=#2
g=#2
g=#2
g=#2
g=#2
Dr. Welf Löwe und Markus Noga 13
Typsplitting
Jedes Objekt hat Protokoll als TypBeim Erzeugen von Aliases wird das Protokoll zwischen beiden Aliasausdrücken aufgeteilt Es entstehen zwei Sichten auf die Komponente, die zusammen das gesamte Protokoll bildenSchwierigkeiten – mit may-alias– Zusammenflüssen im Steuerfluss
Dr. Welf Löwe und Markus Noga 14
Beispiel Typsplitting
...File (open, write*, close) f=new File();init(f);f.write(...); //f ist vom Typ: File (write*, close) ...f.close(...);...
void init (File (open write) g){g.open(...);g.write(...);
}
Dr. Welf Löwe und Markus Noga 15
Problem
...loop{x=new K();x.init();x.doSome(); x.close();
}...
new K() steht für eine Menge von Komponenteninstanzen zur LaufzeitAbstrakte Namen zur Bezeichnung in der statischen Analyse
Problem
Fabrik(){K[] container;init(){ loop{container.add(new K()); }}get(){return(container.get());}
} x=get();y=get();x.init();y.init(); ...
Abstrakte Namen können konkrete Komponenten nicht immer unterscheidenProblem unentscheidbar
Dr. Welf Löwe und Markus Noga 17
Namensschemaproblem
Potentiell beliebige Anzahl von von dynamisch erzeugten KomponenteninstanzenMuss für statische Analyse zu endlicher Anzahl abstrahiert werdenAnalyse muss fehlerhaft sein
Dr. Welf Löwe und Markus Noga 18
Mögliche Namensschemata
Alle (dynamischen) Objekte sind einsAlle (dynamischen) Objekte gleichen Typs (der gleichen Komponente) zu einem abstrakten zusammenfassenAlle Objekte, die an der gleichen Stelle erzeugt wurden, zusammenfassenAlle Objekte, die an der gleichen Stelle erzeugt wurden, wobei diese Erzeugung von der gleichen Prozedur aufgerufen wurdeLetzteres verallgemeinerbar auf Aufrufpfade der Länge k
Dr. Welf Löwe und Markus Noga 19
Problem
Mehrere Klienten greifen auf identische Komponente zuKlienten laufen parallel aber nicht synchronBeobachtbares Verhalten der Umgebung ist nicht deterministisch– Reihenfolge der Methodenaufrufe, wie sie an der Komponente
ankommen, ist Verzahnung („Interleaving“) der Aufrufe der beteiligten Klienten
– Eingeschränkt durch Abhängigkeiten der Klienten untereinander
Dr. Welf Löwe und Markus Noga 20
Problem Nebenläufigkeit
Sei A1 das Aufrufprotokoll von Klient 1 und A2 das Aufrufprotokoll von Klient 2Sei f1: m1,m2, ... , mn A1 die Aufruffolge von Klient 1 und f2: m‘1,m‘2, ... , m‘k A2 die Aufruffolge von Klient 2An der Komponente kann jede Folge der Bauart: m‘‘1, m‘‘2, ... , m‘‘n+k ankommen mit m‘‘i f1 m‘‘i f2 und Folgen f1 und f2 sind TeilfolgenAufrufprotokoll ist Produkt der Sprachen A1 A2 Verallgemeinerung auf k Klienten A1 A2 ... Ak Exponentielles Wachstum:– Der Sprache (nicht so schlimm)– Der Sprachdefinition
Dr. Welf Löwe und Markus Noga 21
Beispiel Keller
S SS | push S pop|
S SS | push S pop|
S‘ (S|S) (S|S)
S push push S‘pop pop|
S push push S‘pop pop |
S push S‘ pop|
S push S‘ pop|
Dr. Welf Löwe und Markus Noga 22
Beispiel: 2 Klienten für eine Datei
open
read/write
close
open
read/write
close
Nebenläufige Klienten der Datei
open
read/write
close
open
read/write
close
open
read/write
close
openread/write
close
read/write
read/write
open close
Legale Aufrufe an eine Datei
open close
open
read/write
close
open
read/write
close
read/write
read/write
open close
Dr. Welf Löwe und Markus Noga 25
Problem
Ein Klient und eine Komponente im SystemKomponente ist web-DienstAufrufprotokoll A: z.B. sei f: m1,m2, ... , mn A
Komponentenprotokoll K: z.B. sei g: m1,m2, ... , mn K
Web-Kommunikation ist nicht reihenfolgeerhaltendAn der Komponente kommen die Aufrufe in vertauschter Reihenfolge an, z.B. f‘: m2,m1, ... , mn mit f‘ K
Immer Anpassungen zur Laufzeit notwendig
Dr. Welf Löwe und Markus Noga 26
Statische Analyse
Simulieren der Methodenaufrufe zur Übersetzungszeitexpr.m() erzeugt sog. „Update“ der Menge von Objekten, die expr bezeichnet– Mögliche Aliases – „weak update“ – alter Zustand wird als möglicher
aktueller gemerkt– Garantierte Aliases – „strong update“ – alter Zustand wird
fortgeschaltet
Aussagen– Garantiert korrekt – Fehler können nicht ausgeschlossen werden– Fehler garantiert
Dr. Welf Löwe und Markus Noga 27
Program Slicing
Aufgabe: lösche Programmstellen, die zu Aufrufen an die Komponente keinen Beitrag leistenZiel: konservative AbschätzungDatenstruktur ist Aufrufgraph oder SteuerflussgraphAnfang: potentielle Erzeugungen und AufrufeLösche alle Knoten, die nicht auf einem Pfad vom Programmanfang main zur Erzeugung einer Instanz oder zum Aufruf an eine Instanz führenUngenau, da in gelöschten Prozeduren berechnete Werte den Steuerfluss zum Aufruf beeinflussen können
Dr. Welf Löwe und Markus Noga 28
Berechnung der Aufrufprotokolls
Definition einer GrammatikJeder Methode der Komponente entspricht TerminalsymbolJeder anderen Methode entspricht Nichtterminalmain – Satzsymbol Methodenrümpfe entsprechen rechten Seiten von Produktionen– Schleife: * – Bedingung: |– Methodenaufruf: Terminal oder Nichtterminal
Dr. Welf Löwe und Markus Noga 29
Beispiel
main{File f=new File();start(f);
}start(File f){
f.open(...);doSome(f);f.close();
}doSome(File f){
loop char c=f.read();f.write(„bla“);
}
Main Start
Start open DoSome close
DoSome read* write
Dr. Welf Löwe und Markus Noga 30
Ergebnis
Kontextfreie GrammatikDefiniert Obermenge A‘ des Aufrufprotokolls A
A A‘ A‘ K A K
Wie ist K definiert?
Dr. Welf Löwe und Markus Noga 31
Endlicher Automat
K ist durch endlichen Automaten gegebenAlternativ regulärer Ausdruck oder GrammatikA‘ K ist unentscheidbar, da A‘ kontextfreiLösung: finde reguläre Obermenge A‘‘ von A‘
A A‘ A‘‘ A‘‘ K A K
Finden einer möglichst genauen regulären Obermenge einer kontextfreien Sprache?
Dr. Welf Löwe und Markus Noga 32
Reguläre Obermenge kontextfreier Sprachen
Grammatik in Greibach Normalform:– N t– N t N‘– N N‘N‘‘
Immer möglich für jede KfGKonstruiere Endlichen AutomatenJedem Nichtterminal N werden 2 Zustände zugeordnet: SN (vor Akzeption), S‘N (nach Akzeption)– N t SN t S‘N S‘N SF
– N t N‘ SN t SN‘ S‘N‘ S‘N
– N N‘N‘‘ SN SN‘ S‘N‘ SN‘‘ S‘N‘‘ S‘N
Dr. Welf Löwe und Markus Noga 33
Eigenschaften
Ist regulär (per Konstruktion)Akzeptiert Obermenge der SpracheIst nicht unnötig groß, d.h., wenn die Sprache regulär ist (nur unglücklicher Weise kontextfrei definiert), so wird der Automat konstruiert, der die Sprache exakt akzeptiert
Zustandsexplosion bei Nebenläufigkeit
open
read/write
close
open
read/write
close
open
read/write
close
openread/write
close
read/write
read/write
open close
Dr. Welf Löwe und Markus Noga 35
Modellprüfung
Ursprung: Formale Logik– Gegeben eine Formel und– ein mathematisches Modell M der Formel – Wird von M erfüllt?
Anwendung auf Software– Formel ist Spezifikation,– Modell M ist Umsetzung:– Erfüllt M seine Spezifikation ?
Ablaufaussagen erfordern Zeitbegriff– Temporales Zeitmodell: (, )– Quantitatives Zeitmodell: (, , |·|)
• für Echtzeitprobleme, • reduzierbar auf temporales Zeitmodell
Dr. Welf Löwe und Markus Noga 36
Erreichbarkeitsanalyse
Aufgabe– Gegeben ein Zustand– Welche Zustände sind erreichbar?
Algorithmus– Beginne mit Z={Start}– Solange z Z, z nicht bearbeitet
Z := Z {y | y ist von z direkt erreichbar}– Terminiert, da Zustandsmenge endlich
Anwendung auf Modellprüfung– Gegeben eine Formel und einen Startzustand– Gilt auf allen Ausführungspfaden, auf einem Ausführungspfad ...– Berechne erreichbare Zustände und prüfe !
Dr. Welf Löwe und Markus Noga 37
Grenzen der expliziten Darstellung
Berechnung der Erreichbarkeit ist linear in Größe– des Zustandsraums– der Übergangsrelation– der zu beweisenden Formel
In der Praxis– Systeme sind Komposition paralleler Komponenten– Zustandsraum wächst exponentiell (Zustandsexplosion)– In expliziter Darstellung nicht beherrschbar
Ausweg– Implizite Darstellung mit booleschen Formeln (symbolisch)– Zustandsraum ist n-dimensionaler boolescher Raum– Kodierung als geordnete binäre Entscheidungsdiagramme (OBDD)
Dr. Welf Löwe und Markus Noga 38
Klammersprachen
DycksprachenWohlgeformte Klammerausdrücke über einem Alphabet von Klammern Beispiel Warenkorb – Paar: Auswahl (X) – Zurücklegen (X) – Ware X beliebig
Inklusionsproblem entscheidbar
Dr. Welf Löwe und Markus Noga 39
Kontextfreie Sprachen
Inklusionsproblem unentscheidbar im allgemeinenAnsatz: transformiere beide Grammatiken– Konstruiere Greibach Normalform– Eliminiere Kettenproduktionen– Eliminiere nicht erreichbare Produktionen– Eliminiere nicht terminierende produktionen
Vergleiche auf strukturelle InklusionSemientscheidbar
Dr. Welf Löwe und Markus Noga 40
Prädikatenlogik
Natürliche Form der KomponentenprotokollspezifikationJeder Dienst hat Vorbedingung (pre-condition)– Prädikatenlogische Formel über dem Zustand der
Komponenteninstanz und den Parametern
Jeder Dienst garantiert Nachbedingung (post-condition)– Prädikatenlogische Formel über dem Zustand der
Komponenteninstanz und den Parametern vor Dienstausführung und über dem Zustand der Komponenteninstanz und dem Resultat nach Dienstausführung
– Eigentlich Temporallogik
Nachbedingung impliziert die Gültigkeit von anderen Vorbedingungen
Dr. Welf Löwe und Markus Noga 41
Beispiel
class Stack(T) {
pre: true;push(T t);post: Stack.count == Stack.count‘ +1
pre: Stack.count != 0;pop(T t);post: Stack.count == Stack.count‘ -1;
}
Dr. Welf Löwe und Markus Noga 42
Prädikatenlogik
Statisch unentscheidbarBeobachtung in der Praxis:– Teil des Zustandes, der relevant ist für korrekte Verwendung ist als
Dienst an der Schnittstelle verfügbar– Bsp.: Funktion isEmpty() beim Stack
Lösung zur Laufzeit immer möglich
Dr. Welf Löwe und Markus Noga 43
Guarded Methods
Dienste sind durch Wächter (guards) geschütztGarantieren, dass kein Dienst aufgerufen wird, wenn die Komponente im falschen Zustand istKorrektheit dynamisch gesichert durch Umordnen von MethodenaufrufenLaufzeitprobleme– Teuer Operationen (Kerneintritt notwendig)– Verwaltung von Methodenwarteschlangen
Lebendigkeit (Verklemmungsfreiheit) offenes Problem
Dr. Welf Löwe und Markus Noga 44
Kriterien
Vollständige Spezifikation des Komponentenverhaltens?
Automatische Tests auf Konsistenz?
Verständlichkeit / Effizienz der Spezifikation?
Effizienz der Ausführung?
Dr. Welf Löwe und Markus Noga 45
Spezifikationstechniken im Vergleich
Vollständig Test Spec Code
Sequence Diagrams -- -- ++ +
Endliche Automaten - + + +
Modellprüfung -/+ + + +
PrädikatenlogischeFormeln
+ - + +
Guards ++ ++ - --
Dr. Welf Löwe und Markus Noga 46
Zusammenfassung
Alias-Problem (unentscheidbar)Abstrakte Namen finden (exakt sein unmöglich, exponentielles Wachstum der Datenstruktur mit der Genauigkeit)Aufrufprotokoll Finden (unentscheidbar auch ohne Alias- und Namensproblem)Nebenläufige Aufrufer (exponentieles Wachstum möglicher Sequenzen)Kanäle, die die Ordnung nicht erhalten (exponentieles Wachstum möglicher Sequenzen)Sprachinklusion (unentscheidbar oberhalb von regulären Sprachen)
Dr. Welf Löwe und Markus Noga 47
Warum geht alles gut
Komponenten in der Praxis haben einfache Schnittstellen (sonst können die Dienste nicht verwendet werden)– Einfache Protokolle
Komponenten in der Praxis grobgranular (sonst macht Wiederverwendung keinen Sinn) – Wenige Instanzen
Hierarchischer Aufbau von Systemen– Aufrufer in lokalen Subsystemen zu finden
Gegenstand aktueller Forschung – richtige Mischung von statischen und dynamischen Techniken wird gesucht
Dr. Welf Löwe und Markus Noga 48
Best practice
Garantiere Korrektheit durch guardsAnalysiere (statisch), welche guards wegfallen dürfenAnalysiere (statisch oder dynamisch), ob System lebendig– Verklemmungsvermeidung (statisch)– Verklemmungsentdeckung (dynamisch)
Verweben von guards und Komponenten