data structures and software dependability

• home

• contact

• members

• teaching

• research

• publications

• software

• events

Einführung in die Nebenläufigkeit

Vorlesung, Prof. Dr.-Ing. M. Heiner, WS 2015/2016

latest update: April 06, 2016, at 02:57 PM

I N D E X

Zielgruppe
Zusammenfassung
Ziele
Voraussetzungen
Organisatorischer Rahmen
Zum Übungsablauf
Bewertungskriterien
Literaturhinweise
Inhaltsübersicht
Materialien zur Vorlesung
Übungsseite

Zielgruppe

• Studierende der Informatik im Hauptstudium (Diplom-Studiengang), im Fachstudium (Bachelor-Studiengang) bzw. Master-Studiengang
• Studierende der Informations- und Medientechnik im Fachstudium (Bachelor-Studiengang) bzw. Master-Studiengang

Zusammenfassung (Modulbeschreibung bzw. Vorlesungsanzeiger)

• Säule: Grundlagen der Informatik, 8 Credits
• Grundlagen: Petrinetze zur Modellierung kausaler Beziehungen und damit anschaulichen Beschreibungen von Nebenläufigkeit, Synchronisation und Kommunikation;
• typische sprachliche Konstrukte zur Programmierung von Nebenläufigkeit;
• klassische Probleme der Sperr- und Ereignissynchronisation;

Ziele

• Grundtechniken zur modell-basierten systematischen Konstruktion nebenläufiger Systeme;
  • Konstruktion = Entwurf durch Modellierung + Implementierung
  • Modellierungssprache -> Petrinetze
  • Implementierungssprache(n) -> Java, Java-FC, Pascal-FC, ...
• Verständnis der grundlegenden Begriffe der Petrinetztheorie;
• tieferes Verständnis der Grundprinzipien nebenläufiger Systeme anhand von Petrinetzmodellen;
• Kenntnisse in grundlegenden nebenläufigen Programmierkonzepten, u. a. Java-Thread-Programmierung;

Voraussetzungen

• Grundlegende Kenntnisse in der imperativen Programmierung sequentieller Prozesse (Vorlesung Informatik I/Algorithmieren und Programmieren)
• objektorientierter Entwurf & Programmierung, Klassendiagramme (-> Vorlesung Informatik II/SE)
• grundlegendes Verständnis der Nebenläufigkeit (-> Vorlesung BS)

Organisatorische Rahmen

Hinweis

Nach der Rahmenregelung für alle PO haben sich alle Studierende für jeden Modul, den sie belegen wollen, innerhalb der ersten zwei Wochen schriftlich beim Prüfungsamt anzumelden. Von dieser Anmeldung kann man innerhalb der ersten sieben Wochen zurücktreten. Mit der Anmeldung zu einer Lehrveranstaltung ist man für die zugehörige Prüfung angemeldet. Siehe auch Allgemeine Prüfungsmodalitäten.

Ausserdem bitten wir zur Organisation des Übungsbetriebes um eine Anmeldung über LEHVIS.

Die Lehrveranstaltung besteht aus zwei Blöcken Vorlesung und einem Block Übung pro Woche.

Vorlesungen

donnerstags, 3. und 4. Block (11.00 - 14.15), VG 1c, R 2.01; Beginn: 15.10.2015

Übungen

donnerstags, 14.30-16.00, VG 1c, R 2.01; Beginn: 22.10.2015

Prüfung

mündlich oder schriftlich, Entscheidung wird zu Beginn des Semesters getroffen; Termin: 15.02.2016

Zum Übungsablauf

• Die Übungen dienen zur Klärung von Fragen zum Vorlesungsstoff und vor allem zur Diskussion/Präsentation der Aufgaben bzw. Lösungen der Übungsblätter.
• Die erste Übung wird zur Einführung in die benutzte Software genutzt.
• Im Verlaufe des Semesters wird es SECHS Übungsblätter geben, die von jedem Studenten individuell zu bearbeiten sind.
• Abgabe der Lösungen: in Papierform direkt beim Übungsbetreuer in der jeweiligen Übung in der jeweiligen Kalenderwoche, zusätzlich sind alle Programmquellen dem Übungsbetreuer in einer email termingerecht mittels LEHVIS zuzustellen.
• Die Lösung gilt nur als abgegeben, wenn beide Komponenten (Papierform, email) abgegeben wurden.
• Verspätete Abgaben werden nur im begründeten Ausnahmefall akzeptiert, ansonsten erfolgt die Bewertung mit "ungenügend". Die Entscheidung hierzu liegt beim Übungsbetreuer.
• Alle Lösungen sind in einer für Informatiker angemessenen Form einzureichen, alle Programme sind gemäß den Vorgaben zu dokumentieren.
  
  ACHTUNG: Massive Verstöße führen zur Ablehnung der Lösung, d.h. die Lösung gilt als nicht abgegeben. Die Entscheidung hierzu liegt beim Übungsbetreuer.

Bewertungskriterien

Die Prüfung zur Lehrveranstaltung setzt sich aus den folgenden zwei Bestandteilen zusammen:
(1) Übungsteilnahme UND
(2) Klausur/Prüfungsgespräch zum Abschluß der Lehrveranstaltung.
Es müssen beide Kriterien erfolgreich absolviert werden.

(1) Übungsteilnahme

Im Verlaufe des Semesters wird es SECHS Übungsblätter geben, die von jedem Studenten individuell zu bearbeiten sind. Alle Übungsblätter werden nach folgendem Schema bewertet:

Code	Schlagwort	Kommentar
0	ungenügend	nicht abgegebene oder nicht fristgerecht abgegebene oder unvollständige Lösungen werden automatisch mit "ungenügend" bewertet;
		dasselbe gilt für eingereichte Programme, die sich nicht erfolgreich übersetzen lassen.
1	nachbesserungsfähig	es gibt bei Bedarf eine EINWÖCHIGE Frist zur Nachbearbeitung, um evtl. "bestanden"zu erreichen;
		wird diese Frist nicht eingehalten, wird das Blatt mit "ungenügend"bewertet.
2	bestanden	das sollte der Regelfall sein

Die Übungsteilnahme wird mit erfolgreich bewertet, wenn alle Übungsblätter als "bestanden" bewertet werden. Bei Bedarf gibt es ein Wiederholungsübungsblatt, das dann im Anschluß an das Semester, aber innerhalb des ersten Monats der vorlesungsfreien Zeit, zu bearbeiten ist. Gegenstand der Bewertung der Übungsteilnahme ist die über das Semester gesammelte Dokumentation der Lösungen aller Übungsblätter.

(2) Klausur/Prüfungsgespräch

Eine Klausur wird mit erfolgreich (bestanden) bewertet, wenn mindestens 50 % der maximalen Punktzahl erreicht werden. Die Benotung erfolgt nach dem üblichen Notenspiegel. Eine Klausur wird ohne Unterlagen (d.h. auch ohne Handy) geschrieben. Wörterbücher werden bei Bedarf vom Lehrstuhl gestellt. Dauer der Klausur: 2h.

Ein Prüfungsgespräch besteht aus zwei Teilen: 1h Vorbereitungszeit + 1h mündliche Prüfung. Während dieser Zeit sind keine Unterlagen oder andere Hilfsmittel (d.h. auch kein Handy) zugelassen. Wörterbücher werden bei Bedarf vom Lehrstuhl gestellt. Ein Prüfungsgespräch wird mit erfolgreich (bestanden) bewertet, wenn mindestens 50 % der zu erwartenden Leistung gezeigt werden.

Die Entscheidung, ob die Prüfung als Klausur oder Prüfungsgespräch (also schriftlich oder mündlich) erfolgt, wird zu Beginn des Semesters (in Abhängigkeit von der Teilnehmerzahl) gefällt.

Siehe auch "Allgemeine Prüfungsmodalitäten für Diplom- und Master-Prüfungen".

Allgemeines

Ein Credit entspricht 30 Arbeitstunden (Bachelorstudienordnung, §7). Somit gilt

Lehrveranstaltung: 8 Credits = 240 Arbeitsstunden; bei 16 Wochen (15 Wochen Vorlesung + 1 Woche Prüfungszeit) macht das 15 Arbeitstunden pro Woche! Davon sind 4.5 h sogenannte Kontaktstunden, womit 10.5 Stunden pro Woche zur Vor-/Nachbereitung der Vorlesung bzw. Bearbeitung der Übungsaufgaben verbleiben.

Diese Aufwandskalkulation ist bei der Stoffauswahl und dem Verfassen der Aufgabenblätter berücksichtigt worden.

Literaturhinweise

eine sehr kleine Auswahl nützlicher Literatur:

(1) Programmierung von Nebenläufigkeit

• T Axford:
  Concurrent Programming;
  Wiley & Sons 1989
• M Ben-Ari:
  Principles of Concurrent and Distributed Programming;
  Prentice Hall 1990
• D Burns:
  Concurrent Programming;
  Addison Wesley 1993
• Herrtwich, Hommel:
  Nebenläufige Programme (Titel der Erstausgabe: Kooperation und Konkurrenz);
  Springer Verlag 1994

(2) Programmierung von Nebenläufigkeit in Java

• D Lea:
  Concurrent Programming in Java;
  Addison-Wesley 1997
• B Goetz, T Peierls, J Bloch, J Bowbeer, D Holmes, D Lea:
  Java Concurrency in Practice;
  Addison Wesley Professional, 2006
• S Oaks, H Wrong:
  Java Threads;
  O'Reilly 1997
• R Oechsle:
  Parallele Programmierung mit Java Threads;
  Fachbuchverlag Leipzig 2001
• J Nowak:
  Fortgeschrittene Programmierung mit Java 5: Generics, Annotations, Concurrency und Reflection;
  dpunkt.verlag 2005

(3) Formale Modelle, allgemein

• C Lewerentz, T Lindner:
  Formal Development of Reactive Systems - Case Study Production;
  LNCS 891, Springer 1995
• J Magee, J Kramer:
  Concurrency, State Models & Java Programs;
  John Wiley & Sons 1999 CD provided by this book, siehe auch http://www.doc.ic.ac.uk/~jnm/book/

(4) Petrinetze

• B Baumgarten:
  Petri-Netze, Grundlagen und Anwendungen;
  Wissenschaftsverlag 1990
• F Bause, P Kritzinger:
  Stochastic Petri Nets - An Introduction to the Theory
  Vieweg Verlag 2. Aufl. 2002
• CA Petri:
  Kommunikation mit Automaten (in German)
  Ph.D., TH Darmstadt 1962
• CA Petri, W Reisig:
  Petri net;
  Scholarpedia 3(4):6477
• W Reisig:
  Petrinetze: Modellierungstechnik, Analysemethoden, Fallstudien;
  Vieweg+Teubner Juli 2010
• PH Starke:
  Analyse von Petri-Netz-Modellen;
  B. G. Teubner 1990
• Petri Nets World Homepage

(5) eine kleine Auswahl hilfreicher Papiere zu Petrinetzen:

• Desel, J; Juhas, G:
  “What Is a Petri Net?” - Informal Answers for the Informed Reader;
  in H Ehrig et al. (Eds.): Unifying Petri Nets, LNCS 2128, pp. 1-25, Springer 2001.
• M Heiner, D Gilbert, R Donaldson:
  Petri Nets for Systems and Synthetic Biology;
  in M Bernardo, P Degano, and G Zavattaro (eds.): SFM 2008, Springer LNCS 5016, pp. 215-264, 2008.
• M Heiner:
  Understanding Network Behaviour by Structured Representations of Transition Invariants – A Petri Net Perspective on Systems and Synthetic Biology;
  In Algorithmic Bioprocesses, (A Condon, D Harel, JN Kok, A Salomaa and E Winfree, Eds.), Springer, pages 367–389, 2009.
• Murata, T.:
  Petri Nets: Properties, Analysis and Applications;
  Proc. of the IEEE 77(1989)4, pp. 541-580.
• Silva, M:
  Half a century after Carl Adam Petri’s Ph.D. thesis: A perspective on the field;
  Annual Reviews in Control 37 (2013), pp. 191–219.

Inhaltsübersicht

Hinweis: alle Schlagworte stehen für Prüfungsschwerpunkte

1. Einführung, Motivation, Begriffliche Grundlagen

modell-basierte systematische Konstruktion nebenläufiger (insbesondere reaktiver) Systeme;
die Lehrsprache Java-FC;
Literatur;
parallel, verteilt, nebenläufig; warum Nebenläufigkeit;
grobkörnige und feinkörnige Nebenläufigkeit;

2. Einführung Petrinetze

Platz/Transitions-Netze, Markierung, allg. Schaltregel, Markenspiel;
Kausalität, Nebenläufigkeit, Synchronisation, Konflikt/Nichtdeterminismus, Konfusion;
Erreichbarkeitsgraph, Überdeckbarkeitsgraph;
wünschenswerte Eigenschaften: Beschränktheit, Lebendigkeit, Rücksetzbarkeit, Erreichbarkeit, tote (schlechte) Zustände, Sicherheitseigenschaften;

3. Grundlegende Prozeßkonzepte in Programmiersprachen

Prozeßtyp, Prozeßinstanz, Prozeß;
Kooperation/Konkurrenz, Ereignis-/Sperrsynchronisation;
low-level Mutex-Algorithmen (z.b. Peterson-Algorithmus);
gefärbte Petrinetze als Kurznotation für Platz/Transitions-Netze;
(integer-) Semaphore, Modellierung und Analyse von "Semaphore-Programmen" mit Petrinetzen;
Deadlockanalyse, stur-reduzierte Erreichbarkeitsgraph;
Deadlockvermeidungsstrategien, hierarchische Betriebsmittel-Organisation, (kreisfreier) Zugriffsgraph;
temporale Logik (CTL) zur Spezifikation spezieller Eigenschaften;
producer/consumer-Muster und client/server-Muster;
Nichtdeterminismus durch selektives Warten;
Einfluß der Zeit auf Petrinetz- bzw. Software-Eigenschaften;

Petrinetz-Theorie:
strukturelle Eigenschaften: PUR, ORD, HOM, CSV, SCF, FT0, TF0, FP0, PF0, CON, SC;
Netzklassen: SM; SG, FC, EFC, ES;
statische Analysetechniken: Platz/Transitions-Invarianten, CPI/CTI, Siphons, Traps, STP;

4. Kompakte Konstrukte zur Prozeßsynchronisation in Programmiersprachen

(bedingte) kritische Regionen, Monitore (Concurrent Pascal);
Rendezvous-Kommunikation (Ada),Kommunikation über Kanäle (Occam);
Vor- und Nachteile, Überführbarkeit;
Klassifikationsschema für Synchronisationskonzepte (Adressierung, Synchronisation, Warten);

---------------------Vorlesungsstand---------------------Vorlesungsstand---------------------

5. Beispiel für einen verteilten Algorithmus

Petrinetz-basierter Algorithmenentwurf;
Implementierung mit verschiedenen Synchronisationskonzepten;
Regelwerk hierarchischer Prozeßkommunikation, (kreisfreier) Prozeßgraph;

6. Nebenläufigkeit in Java 5.0

High-level-Klassen; Semaphore, Exchanger, CountdownLatch, CyclicBarrier, BlockingQueue;
Low-level-Klassen: atomic Datentypen, Lock;