Programowanie współbieżne

obowiązkowe

Architektura komputerów i systemy operacyjne 1000-212bAKSO
Wstęp do programowania 1000-211bWPI

Założenia dotyczą cykli od 23/24.

Podstawowe problemy oraz techniki programowania systemów współbieżnych i rozproszonych. Klasyczne problemy współbieżności. Mechanizmy synchronizacji w modelu scentralizowanym: semafory i monitory. Metody synchronizacji w modelu rozproszonym, komunikacja synchroniczna i asynchroniczna. Weryfikacja poprawności programów współbieżnych. Wybrane algorytmy rozproszone. Miary złożoności programów współbieżnych.

Wykład:

- Podstawowe pojęcia współbieżności: proces, przeplot, wykonanie współbieżne

- Poprawność programów współbieżnych

- Modele współbieżności

- Klasyczne problemy współbieżności: wzajemne wykluczanie, czytelnicy i pisarze, pięciu filozofów, producenci i konsumenci

- Wybrane algorytmy wzajemnego wykluczania niekorzystające ze wsparcia sprzętu ani systemu operacyjnego

- Definicja i różne semantyki semaforów: semafor Dijkstry, semafory słabe, silne, silnie uczciwe

- Definicja i różne semantyki monitorów: monitor Hoare, realizacja za pomocą biblioteki pthread

- Metody weryfikacji poprawności programów współbieżnych: LTL, model checking, metody dedukcyjne

- Metody synchronizacji w modelu rozproszonym: komunikacja synchroniczna i asynchroniczna (przestrzeń krotek).

- Spójność i modele spójności: llinearizability (or atomicity), sequential consistency, causal consistency, eventual consistency

- Wydajność w modelu współbieżnym: praca, rozpiętość, zrównoleglenie, przyspieszenie

- Wybrane algorytmy rozproszone (wzajemne wykluczanie w systemach rozproszonych, synchronizacja zegarów logicznych, uzgadnianie)

Laboratorium:

- Procesy i wątki oraz metody ich synchronizacji w systemach zgodnych ze standardem POSIX

- Współbieżność w Javie (java.util.concurrent, implementacja monitora)

Ćwiczenia:

- Algorytmy wzajemnego wykluczania bez wsparcia sprzętu i systemu operacyjnego

- Semafory

- Monitory

- Synchroniczna wymiana komunikatów

- Asynchroniczna wymiana komunikatów

- Miary wydajności programów współbieżnych

1. M. Ben - Ari, Podstawy programowania współbieżnego i rozproszonego

2. Z. Gruźlewski, Z. Weiss, Programowanie współbieżne i rozproszone w przykładach i zadaniach

3.M. Herlihy, N. Shavit, Sztuka programowania wieloprocesorowego

4. H. Casanova, A. Legrand, Y. Robert, Parallel Algorithms

5. T. H.Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Alghorithms, 3rd edition

6.W. R. Stevens, Programowanie w środowisku systemu UNIX

7.B. Eckel, Thinking in Java

Wiedza - absolwent zna i rozumie:

- teoretyczne podstawy z zakresu programowania, algorytmów i złożoności (K_W02),

- zasady działania systemów operacyjnych ze szczególnym uwzględnieniem procesów, współbieżności, szeregowania zadań i zarządzania pamięcią (K_W07)

Umiejętności - absolwent potrafi:

- pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie (K_U02),

- samodzielnie planować i realizować własne uczenie się przez całe życie (K_U09),

- opisywać problemy związane z wykonywaniem programów współbieżnych (K_U10)

Kompetencje społeczne - absolwent jest gotów do:

- krytycznej oceny posiadanej wiedzy i odbieranych treści (K_K01),

- pracy z poszanowaniem uczciwości intelektualnej w działaniach własnych i innych osób; przestrzegania zasad etyki zawodowej i wymagania tego od innych oraz dbałości o dorobek i tradycje zawodu informatyka (K_K02),

- uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (K_K03)