Logo

teaching

data structures and software dependability

computer science department

brandenburg university of technology cottbus - senftenberg

Introduction into Concurrency

Lecture, Prof. Dr.-Ing. M. Heiner, WS 2018/2019
This course will be in English.

Module
11884 - Introduction into Concurrency
12348 - Einführung in die Nebenläufigkeit

latest update: December 05, 2018, at 09:03 PM

I N D E X

Target group
Summary
Objectives
Preconditions
Organisation
About the exercises
Assessment criteria
References
Table of Contents - progress line
Materials
Exercises

Target group

  • Students of Computer Science (Informatics) - Bachelor, Master
  • Students of Information and Media Technique (IMT) - Bachelor, Master
  • Students of Cyber Security - Compulsory Elective Module for Computer Science

Summary

  • Category: Computer Science Foundations, 8 Credits
  • Foundations: Petri nets for the modelling of causal relations and thus intuitive description of concurrency, synchronisation and communication;
  • typical programming language constructs for the programming of concurrency (semaphores, [conditional] critical regions, monitors, rendezvous, channels);
  • classical problems of mutual exclusion and event synchronisation;

Objectives

  • basic techniques for model-based systematic construction of concurrent systems;
    • construction = design by modelling + implementation
    • modelling language -> Petri nets
    • implementation language -> Java (Java-FC, Pascal-FC, ..., Python)
  • comprehension of the fundamental concepts of Petri nets theory;
  • deeper insights into the basic principles of concurrent systems by help of Petri net models;
  • knowledge of the fundamental concepts of concurrency programming , such as Java thread programming;

Preconditions

  • basic knowledge and skills of
    • imperative programming of sequential processes (course Informatics I/Algorithms and Programming)
    • object-oriented design & programming, class diagrams (-> course Informatik II/Software Engineering)
  • basic understanding of concurrency concepts (-> course Operation Systems)

Organisation

Remark

According to the General Examination and Study Regulations, students have to register for modules (without a limited number of participants) during the first 3 weeks of the lecture period of each semester. You can withdraw your registration until one week before beginning of the examination period in which the examination is offered for the first time. Both steps are handled via the Online Portal. Please note, if you registered for a module, you are automatically registered for the corresponding exam.

The course consists of two blocks of Lectures and one block Exercise per week.

Lectures

thursdays, 3. und 4. block (11.30 - 14.45), VG 1c, R 2.01;

Exercises

mondays, 17:30-19:00, VG 1c, R 2.01; begin: 3rd teaching week
tutor: Jacek [period] Chodak [snail] b-tu [period] de

Final Exam

Written, without any auxiliary means; you will need paper and pencil, nothing else.
21.02.2019, 11.30-13.30 (the Thursday in the second week of the exam period February 2019)

About the exercises

  • The exercises will be managed via Moodle; please register for the course: 11884 Intoduction into concurrency | WiSe 18/19
  • The exercises may serve to clarify any questions regarding the materials covered in the lectures, but first of all to discuss and present the tasks and their solutions of the assignments.
  • The first exercise will serve for a general introduction into the software used throughout the course.
  • During the semester, there will be SIX assignments, which have to be solved by each student individually.
  • Solutions have to be submitted via Moodle; the specific submission deadlines are given on the assignments.
  • Delayed submissions are only accepted in well justified exceptional circumstances; otherwise this assignment is assessed with "failed". The decision is made by the responsible tutor.
  • All solutions have to be submitted electronically, non-obvious decisions in the proposed solutions have to be justified, programs have to be documented (use comments for this).
    Attention: Neglecting these rules results into non-acceptance of the submission; with other words: the submission is treated as not submitted. The decision is made by the responsible tutor.

Assessment criteria

The assessment of this course comprises two parts:
(1) Participation in the exercises accompanying the course AND
(2) Written examination at the end of the course.
Both criteria have to be passed.

(1) Participation in the exercises

During the course, there will be SIX assignments, which have to be solved by each student individually. All assignments will be assessed by the following scheme:

Codekeywordcomment
0failedNot submitted, delayed or incomplete submissions are automatically assessed as failed.
1open to improvementIf required, ONE additional WEEK is granted to improve the previously submitted solution to obtain passed. If this deadline is missed, the assignment is assessed as failed.
2passedThis should be the rule.

The (total) participation in the exercises is assessed as passed, if FIVE (out of six) assignments have been assessed with passed. If required, there will be one supplementary (seventh) assignment, which has to be solved within one month after the end of the course. Subject of the binary assessment re the participation in the exercise is the collection of all solutions which have been submitted during the course.

(2) Written examination

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.

References

a very small selection of useful literature:

(1) Programming of concurrency

  • 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) Programming of concurrency 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) Formal models, general

(4) Petri nets

(5) a small selection of useful Petri net papers:

Links of Interest

Table of Contents

Remark: all keywords given below represent exam-related aspects.

1. Introduction, Motivation, Basic Terminology

model-based systematic construction of concurrent (reactive) systems;
[teaching languages Pascal-FC, Java-FC] - Java - Python;
literature;
parallel - distributed - concurrent; why concurrency;
coarse-grained vs fine-grained concurrency;

2. Introduction into Petri nets

place/transition nets, tokens, marking (state), general firing rule, token game;
basic structures: causality, concurrency, synchronisation, conflict/non-determinism, confusion;
properties: boundedness, liveness, reversibility, dead (bad) states, safety properties;
reachability graph, coverability graph;

3. Basic process concepts in programming languages

process type (pattern of behaviour), process instance (object), process;
basics of Java thread programming and their Petri net representation;
the garden problem: process interference by (unsynchronised) use of shared variables;
coloured Petri nets as short-hand notation for place/transition nets;
cooperation/competition, event/mutex synchronisation;
low-level mutex algorithms (e.g. Peterson algorithm);
(integer) semaphore, modelling and analysis of "semaphore programs" with Petri nets;
deadlock analysis, stubborn set reduced reachability graph;
deadlock avoidance strategies, hierarchical resource organisation, (cycle-free) access graph;

---------------------progress line---------------------progress line---------------------

temporal logics (e.g. CTL) to specify special properties;
producer/consumer pattern and client/server pattern;
non-determinism by selective waiting;
the impact of time on Petri net resp. software properties;

Petri net theory:
structural properties: PUR, ORD, HOM, CSV, SCF, FT0, TF0, FP0, PF0, CON, SC;
net classes: SM; SG, FC, EFC, ES;
static analysis techniques: place/transitions invariants, 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);

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;

… the end …

Any comments or questions are welcome. Please direct them to monika [period] heiner [snail] b-tu [period] de Privacy Policy