Concurrent Programming

This is a module in the computer science Bachelor's programme and related programmes at Saarland University.

The module has been awarded the Preis des Fakultätentages Informatik 2013 and multiple Busy Beaver Awards for excellent teaching (in 2011, 2017, and 2019).

Concurrent Programming

In today's world, multi-core CPUs and other parallel architectures, such as graphics processors, are ubiquitous. However, programming and efficiently working with such systems is a major challenge, both theoretically and practically. This challenge arises due to the foundational principles underlying concurrency and the need to design efficient algorithms and software systems that can take advantage of these architectures.

The goal of the lecture is to familiarize students with the theory and application of concurrent programming. A tremendous challenge, without doubt.

In this course, participants will gain a comprehensive understanding of concurrency in computation as a foundational principle of modern computing sciences, both in theory and application. Through analysis and application of various formal models, participants will deepen their understanding of concurrency and learn to apply formal computing concepts correctly. The theoretical knowledge gained in the first part of the module will be applied to practical programming in the second part. Participants will learn about the programming paradigms "shared memory" and "message passing", starting with the programming language pseuCo. They will also learn to describe various phenomena of concurrent programming using formal models and derive concrete solutions for practical problems. Additionally, participants will examine concurrent programming practices with respect to their adequacy and effectiveness, focusing on the strategically adequate reaction to concurrency problems under tight time constraints.

Audience

The target audience of this module is primarily undergraduate students majoring in computer science or related fields. Students may enroll in this module as early as their second term. The only prerequisite is successful completion of the module Programming 1.

Organisation

The module starts on Tuesday, 11.04.2023. All elements will be held in-person.

Lectures are scheduled to take place in-person on Mondays from 14:15 to 16:00 and on Tuesdays from 10:15 to 12:00 in the lecture hall HS 002 located in building E1 3.

Our team of tutors will provide support through tutorials that we plan to offer in English and German (depending on demand). During the registration process, you will have the option to indicate your preferred language. The tutorials will be held on Wednesdays either from 8:15 to 10:00 or from 10:15 to 12:00. Additionally, you can attend the Concurrency Café, where you can ask questions and receive more direct help. The Concurrency Café takes place on Thursdays from 14:00 to 16:00 and on Fridays from 14:00 to 16:00. You can also ask questions at any time in our forum.

In addition to lectures and tutorials, the module includes weekly colloquia. Colloquia are 15-minute sessions assigned to you and 2-3 other students in a peer group. In a colloquium, your tutor will assess whether you have adequately grasped the current module content. There will be a total of 8 colloquia scheduled on Mondays or Tuesdays throughout the teaching term. Passing at least 7 colloquia is a prerequisite for passing the module. You can find more information about the colloquia on the Rules & Regulations page.

Note that this module spans the teaching term in a somewhat unusual manner. Lecture season finishes early (prior to the practical project phase), and some weeks do not feature two lectures. Please refer to our calendar for all dates.

Examination

The Concurrent Programming lecture is divided into two blocks: theory (𝓣) and application (𝓐), with each block spanning around four weeks. Following these blocks, the students will complete a practical project (𝓟) that concludes their learning experience. It is important to note that all three elements (𝓣, 𝓐, and 𝓟) must be passed to successfully pass the module (for more details, please refer to the Rules & Regulations page). There will be a written exam at the end of each lecture block, with the examination 𝓣 taking place on 22.05.2023 between 14:00 and 16:00 and the examination 𝓐 taking place on 01.08.2023 between 10:00 and 12:00. Re-examinations will be offered in early fall.

Registration

The registration will open during the first lecture on Tuesday, 11.04.2023 at 10:15.

Literature

The participants will get access to lecture material consisting of lecture notes and other resources that altogether cover the entire content of the lecture. Additional literature can also be found here.

Content

• Concurrency as a Concept
  • Potential Parallelism
  • Actual Parallelism
  • Conceptional Parallelism
• Concurrency in Practice
  • Object Orientation
  • Operation Systems
  • Multi-Core Processors, Coprocessors
  • Programmed Parallelism
  • Distributed Systems (Client-Server, Peer-to-Peer, Databases, Internet)
• The Difficulty of Concurrency
  • Ressource Conflicts
  • Fairness
  • Mutual Exclusion
  • Deadlock
  • Livelock
  • Starvation
• Foundations of Concurrency
  • Sequential vs. Concurrent Processes
  • States, Events, and Transitions
  • Transition Systems
  • Observable Behavior
  • Determinism vs. Nondeterminism
  • Algebras und Operators
• CCS: The Calculus of Communicating Systems
  • Construction of Processes: Sequence, Choice, Recursion
  • Concurrency
  • Interaction
  • Structural Operational Semantics
  • Equivalence of Observations
  • Implementation Relations
  • CCS with Message Passing
• Programming Concurrency
  • pseuCo
  • Message Passing in pseuCo
  • Shared Memory in pseuCo and Java
  • Monitors and Semaphors
  • Shared Objects and Threads in Java
  • Shared Objects and Threads as Transition Systems
• Programming and Analysis Support
  • Deadlock Detection
  • Verification of Safety and Liveness
  • Model-Based Design Supporting Concurrency
  • Software-Architectures Supporting Concurrency