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
Target group
Summary
Objectives
Preconditions
Organisation
About the exercises
Assessment criteria
References
Table of Contents - progress line
Materials
Exercises
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.
thursdays, 3. und 4. block (11.30 - 14.45), VG 1c, R 2.01;
mondays, 17:30-19:00, VG 1c, R 2.01;
begin: 3rd teaching week
tutor: Jacek [period] Chodak [snail] b-tu [period] de
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
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.
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:
Code | keyword | comment |
0 | failed | Not submitted, delayed or incomplete submissions are automatically assessed as failed. |
1 | open to improvement | If 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. |
2 | passed | This 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.
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).
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.
a very small selection of useful literature:
Remark: all keywords given below represent exam-related aspects.
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;
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;
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;
(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---------------------
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;
High-level classes; Semaphore, Exchanger, CountdownLatch, CyclicBarrier, BlockingQueue;
Low-level classes: atomic data types, Lock;