WS 2010/2011: Einführung in die Nebenläufigkeit, Prof. Dr.-Ing. M. Heiner

latest update: December 15, 2010

 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, ...
• 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.30 - 14.45), LG 1c, R 215c;
Beginn: 14.10.2010

Übungen

freitags, 4. Block (13.15 - 14.45), LG 1c, R 215c; 
Beginn: 22.10.2010
Martin Schwarick, ms (at) informatik.tu-cottbus.de
für weitere Informationen siehe Übungsseite

Abschlußklausur

erste Woche des Prüfungszeitraumes im direkten Anschluß an das WS, gleiche Zeit und gleicher Raum wie Vorlesung;

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.
  
• mehr Infos zum Übungsbetrieb

Bewertungskriterien

Die Prüfung zur Lehrveranstaltung setzt sich aus den folgenden zwei Bestandteilen zusammen:
(1) Übungsteilnahme UND
(2) Klausur 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

Die Klausur wird mit erfolgreich bewertet, wenn mindestens 50 % der maximalen Punktzahl erreicht werden. Die Benotung erfolgt nach dem üblichen Notenspiegel. Diese Klausur wird ohne Unterlagen (d.h. auch ohne Handy und ohne Wörterbücher) geschrieben.

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

(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, 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 Homepage
  http://www.informatik.uni-hamburg.de/TGI/PetriNets/

(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.
• Murata, T.:
  Petri Nets: Properties, Analysis and Applications;
  Proc. of the IEEE 77(1989)4, pp. 541-580.

Inhaltsübersicht

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 und schlechte Zustände, Sicherheitseigenschaften;

3.  Grundlegende Prozeßkonzepte in Programmiersprachen

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

--------------- VORLESUNGSSTAND ------------- VORLESUNGSSTAND --------------------------

und client/server-Muster;
Nichtdeterminismus durch selektives Warten;
Einfluß der Zeit auf Petrinetz- bzw. Software-Eigenschaften;

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);

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;

  . . . T H E  E N D . . .

sachdienliche Hinweise zu dieser Seite bitte an: