Concurrent programming

obligatory courses

Computer architecture and operating systems 1000-212bAKSO
Introductory programming 1000-211bWPI

(in Polish) Założenia dotyczą cykli od 23/24.

The goal of the lecture is to present basic problems and techniques of programming in concurrent and distributed systems. The course is focused on two key issues: correctness and performance. In connection with fundamental problems of synchronisation such as mutual exclusion and readers-writers problem, the course presents solutions based upon shared variables and ones that require higher-level language support.

Lecture:

- Basic concepts of concurrency: process, interleaving, concurrent execution

- Correctness of concurrent programs

- Concurrency models

- Classic concurrency problems: mutual exclusion, readers and writers, dining philosophers, producers and consumers

- Selected mutual exclusion algorithms without hardware or operating system support

- Definition and various semaphore semantics: Dijkstra semaphore, weak semaphores, strong semaphores, strongly fair semaphores

- Definition and various monitor semantics: Hoare monitor, implementation using the pthread library

- Methods for verifying the correctness of concurrent programs: LTL, model checking, deductive methods

- Synchronization methods in the distributed model: synchronous and asynchronous communication (tuple space)

- Consistency and consistency models: linearizability (or atomicity), sequential consistency, causal consistency, eventual consistency

- Performance in the concurrency model: work, span, parallelism, speedup

- Selected distributed algorithms (mutual exclusion in distributed systems, logical clock synchronization, consensus)

Laboratory:

- Processes and threads and their synchronization methods in POSIX-compliant systems

- Concurrency in Java (java.util.concurrent, monitor implementation)

Exercises:

- Mutual exclusion algorithms without hardware and operating system support

- Semaphores

- Monitors

- Synchronous message exchange

- Asynchronous message exchange

- Performance metrics of concurrent programs

Knowledge – the graduate knows and understands

- Theoretical foundations of programming, algorithms, and complexity (K_W02).

- Principles of operating systems, with particular emphasis on processes, concurrency, task scheduling, and memory management (K_W07).

Skills – the graduate is able to

- Gather information from literature, knowledge bases, the Internet, and other reliable sources, integrate it, interpret it, draw conclusions, and formulate opinions (K_U02).

- Independently plan and pursue lifelong learning (K_U09).

- Describe issues related to the execution of concurrent programs (K_U10).

Social competencies – the graduate is ready to:

- Critically assess their own knowledge and received information (K_K01).

- Work with respect for intellectual integrity in their own activities and those of others, adhere to professional ethics, expect the same from others, and take care of the achievements and traditions of the IT profession (K_K02).

- Recognize the importance of knowledge in solving cognitive and practical problems, search for information in literature, and seek expert opinions (K_K03).