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: February 11, 2019, at 02:32 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
  • Students of (Applied) Mathematics

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)
where: ZHG/SR1

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 (to obtain the credits) comprises two parts:
(1) Participation in the exercises accompanying the course AND
(2) 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) Examination

A written exam is marked as "passed", if at least 50 % of the maximal amount of points have been obtained. The grading follows the usual grading scheme. No auxiliary means are allowed during a written exam; this also excludes the use of mobiles. Dictionaries are provided on request. Duration of the written exam: 2h.

An oral exam comprises two parts: 1h preparation time + 1h oral exam. No auxiliary means are allowed during the whole time; this also excludes the use of mobiles. Dictionaries are provided on request. An oral exam is evaluated as "passed", if at least 50 % of the expected solutions are found. The grading follows the usual grading scheme.

The decision among written or oral examination will be taken at the begin of the semester (depending on the amount of participants).

Note

A credit corresponds to 30 working hours (see, e.g., Bachelor study regulation, §7), yielding the following calculation:

A course with 8 credits = 240 working hours; assuming 16 weeks (15 weeks lecturing + 1 week exam period) makes 15 working hours per week! Of those 15 hours, we have 4.5 of so-called contact hours, which leaves 10.5 hours per week to deepen the understanding of the lectures and preparing the solutions for the homework.

This calculation of expected work load has been taken into consideration when compiling the amount of material covered in the course and the design of the homework assignments.

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;
parallel - distributed - concurrent; why concurrency;
coarse-grained vs fine-grained concurrency;
literature;

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;
competition/cooperation, mutex/event synchronisation;
competition: mutex pattern, deadlock pattern;
cooperation: producer/consumer pattern and client/server pattern;

low-level mutex algorithms (e.g. Peterson algorithm);
(integer) semaphores, 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;
temporal logics (e.g. CTL) to specify special properties;
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;
dynamic analysis techniques: reachability graph, stubborn set reduced reachability graph, model checking;

4. High-level process concepts in programming languages

(conditional) critical regions, monitors (Concurrent Pascal);
rendezvous communication (Ada), communication via channels (Occam);
pros and cons, transformability;
a classification scheme of synchronisation concepts (addressing, synchronisation, waiting);

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

5. Distributed algorithms

algorithm design (exploring design alternatives) by help of Petri net modelling;
implementation via various synchronisation concepts;
rules of hierarchical process communication, (cycle-free) process graph;

6. Concurrency in Java 5.0

High-level classes; Semaphore, Exchanger, CountdownLatch, CyclicBarrier, BlockingQueue;
Low-level classes: atomic data types, Lock;

… the end …

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