Concurrent Programming
Keywords |
Classification |
Keyword |
OFICIAL |
Computer Science |
Instance: 2020/2021 - 2S
Cycles of Study/Courses
Teaching language
Suitable for English-speaking students
Objectives
Introduce students to the fundamental theoretic and practical principals of concurrency, with emphasis on the correctness, design and implementation of models of concurrent computation using shared memory architectures.
Learning outcomes and competences
At the end of the course, students are expected to:
- understand the fundamentals of concurrency, the key issues related with the execution of concurrent programs and the specificities of modern shared memory architectures which are relevant to the performance of concurrent programs.
- be able to apply the theoretical principles which guide a good and correct design of a concurrent program, with particular emphasis on the concepts and formal aspects of synchronization.
- know the main synchronization primitives/libraries for the development of concurrent programs and be able to model and implement concurrent data structures, programs and/or applications correctly and efficiently by using primitives/libraries of modern programming languages for shared memory programming using processes and/or threads.
Working method
Presencial
Program
- Basic concepts: different types of architectures and concurrent applications. Concurrency as an abstraction of parallelism. Distinction between concurrency and parallelism; sequential and concurrent programs; sequential, concurrent, parallel and distributed programming. Processes.
- Introduction to modeling: abstraction, specification and modeling of sequential and concurrent systems. Labelled transition systems (LTS): states, atomic actions, behaviour and equivalence. Basic concepts of a process algebra: event prefix, choice, parallel composition and guards. Synchronous and asynchronous models. Interleaving. Shared atomic actions. Correction properties: safety, liveness and fairness.
- Principles of synchronization: distinction between communication and synchronization; competition and cooperation. Atomic operations in hardware and software. The critical region problem. Starvation versus deadlock. Requirements for the occurrence of deadlocks. Priority inversion. Classical problems of synchronization.
- Synchronization primitives: locks, semaphores, monitors and barriers.
- Programming with processes and threads: distinction between processes and threads. Main advantages and difficulties of using multithreaded processes. User threads versus kernel threads. Concurrent programming based on:(i) processes with advanced memory mapping techniques; (ii) multithreaded processes using libraries of a current programming language.
Mandatory literature
Herlihy Maurice;
The art of multiprocessor programming. ISBN: 9780123705914
Aceto Luca 070;
Reactive systems. ISBN: 978-0-521-87546-2
Complementary Bibliography
Michel Raynal.; Concurrent Programming: Algorithms, Principles and Foundations. , Springer, 2012
Roberto Gorrieri, Cristian Versari; Introduction to Concurrency Theory, Springer, 2015
Ben-Ari M. 1948-;
Principles of concurrent and distributed programming. ISBN: 9780321312839 pbk
Gregory R. Andrews; Foundations of Multithreaded, Parallel, and Distributed Programming., 2000
R. Milner;
Communication and concurrency. ISBN: 0-13-115007-3
Teaching methods and learning activities
Theoretical classes of exposition of the topics of the program and practical laboratory classes for demonstration and development of programs. Transition system simulators or state machines will be used for modeling.
Evaluation Type
Distributed evaluation with final exam
Assessment Components
designation |
Weight (%) |
Exame |
60,00 |
Trabalho laboratorial |
40,00 |
Total: |
100,00 |
Amount of time allocated to each course unit
designation |
Time (hours) |
Estudo autónomo |
56,00 |
Frequência das aulas |
56,00 |
Trabalho laboratorial |
50,00 |
Total: |
162,00 |
Eligibility for exams
Students must attend at least 75% of the pratical classes to be admitted to the exams.
Calculation formula of final grade
Distributed evaluation with final exam. Distributed evaluation will include both modeling (EM) and program implementation (EI). The final grade(FG) is obtained by weighting the distributed assessment scores and final exam (FE) as follows: FG = 4 * EM + 4 * EI + 12 * FE.