Programowanie współbieżne i rozproszone

brak

Wykład 1

Metody podające | Wykład informacyjny

Metody podające | Wykład problemowy

Laboratorium informatyczne lub pracownia fizyczna 2

Metody poszukujące | Metoda ćwiczeniowa

Metody poszukujące | Metoda problemowa

OCENA KOŃCOWA Z PRZEDMIOTU

jest ustalana zgodnie z algorytmem:

Ocena z formy: "Wykład 1" ocena * 50.00 %

+ Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 2" ocena * 50.00 %

Dodatkowe warunki zaliczenia przedmiotu:

Ocena końcowa jest średnią ocen z ćwiczeń i wykładu

Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Test / quiz - 100.00%

Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Obecność na wykładzie i ćwiczeniach jest obowiązkowa

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Wykonanie ćwiczenia - 50.00%

Odpowiedź ustna - 50.00%

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Brak

Wykład 1

Informacje podstawowe

Procesy ciężkie i lekkie (wątki), wywłaszczanie, izolacja pamięci, cykl życia procesu

Przerwania, procedury obsługi przerwań i DMA

Tryb jądra i tryb użytkownika, architektura systemu Linux

Powody stosowania współbieżności i rozpraszania obliczeń

Problemy związane z rozpraszaniem i współbieżnością

Poprawność procesów współbieżnych (własności bezpieczeństwa i żywotności)

Nieadekwatność testowania do weryfikacji poprawności programów współbieżnych

Formalizmy do modelowania programów współbieznych i rozproszonych

Problem ochrony sekcji krytycznych

Algorytm Dekkera

Algorytm piekarza

Mechanizm Test And Set

Po co potrzebne są sekcje krytyczne

Abstrakcja: muteksy

Zakleszczenia

Model korzystania z zasobów

Zagnieżdżone sekcje krytyczne i zakleszczenia

Warunki konieczne wystąpienia zakleszczenia

Graf przydziału zasobów i zakleszczenia

Zapobieganie zakleszczeniom

Stan bezpieczny i stan zagrożenia. Ciągi bezpieczne

Krawędzie deklaracji i wykrywanie stanu zagrożenie w przypadku jednoegzemplarzowych typów zasobów

Algorytm bankiera

Wykrywanie zakleszczeń. Algorytm grafu oczekiwania

Semafory i zmienne warunkowe

Semafory zliczające i binarne. Operacje Wait i Signal

Implementacje semaforów zliczających z aktywnym czekaniem i bez (ze wsparciem systemu operacyjnego)

Ochrona sekcji krytycznych przy pomocy semaforów. Uogólnione sekcje krytyczne

Sygnalizowanie przy pomocy semaforów

Spotkanie dwóch i wielu procesów (bariera) z wykorzystaniem semaforów i zmiennych warunkowych

Bariera wielokrotnego użytku

Wykorzystanie zmiennych warunkowych do oczekiwania na spełnienie warunku

Klasyczne problemy synchronizacji

Problem producenta/konsumenta

Problem czytelników i pisarzy

Problem obiadujących filozofów

Czas rozproszony

Synchroniczne i asynchroniczne przekazywanie komunikatów i ich wzajemna symulacja

Procesy w systemach rozproszonych jako ciągi zdarzeń. Zdarzenia wewnętrzne i zdarzenia odebrania i wysyłania komunikatów

Porządek zależności przyczynowej pomiędzy zdarzeniami w systemie rozproszonym

Diagramy czasoprzestrzenne zdarzeń

Logiczna i fizyczna współbieżność

Stan systemu rozproszonego. Globalny stan spójny

Własności kanałów komunikacyjnych: Kanały FIFO, kanały z CO (Casual Ordering), kanały niezawodne, kanały gubiące komunikaty

Zegary fizyczne i logiczne

Potrzeba ciągłej synchronizacji zegarów fizycznych. Maksymalne tempo odchylania.

Algorytm NTP (Cristiana) synchronizacji zegarów fizycznych

Skalarne zegary logiczne i algorytm synchronizacji Lamporta

Algorytm całkowicie uporządkowanego rozsyłania (korzystający z zegarów skalarnych)

Silne i słabe zegary logiczne

Zegary wektorowe i ich synchronizacja. Zastosowanie do wersjonowania danych.

Algorytmy wzajemnego wykluczania rozproszonego

Algorytm scentralizowany

Algorytm Lamporta

Algorytm Ricarta-Agrawala

Algorytmy oparte na zetonach

Algorytmy oparte na kworach

Tolerowanie awarii

Przyczyny awarii w systemach komputerowych

Cechy niezawodnych systemów (dostępność, niezawodność, bezpieczeństwo, obsługiwalność)

Rodzaje awarii (błędy przejściowe, sporadyczne, twarde, ludzkie)

Modele awarii (załamanie, błędy ominięcia, awarie odliczania czasu, błędy odpowiedzi, awarie bizantyjskie)

Radzenie sobie z błędami i awariami. Redundancja

Specyfika awarii w środowisku rozproszonym

Problem bizantyjskich generałów i rozwiązanie dla 4 generałów i jednego zdrajcy.

Stosowanie dzienników transakcyjnych

Atomowe protokoły zatwierdzania. Algorytm zatwierdzania dwufazowego.

Algorytm Map-Reduce. Obsługa awarii w Map-Reduce. Przykłady zastosowań

Szeregowalność i szeregowalność kolizyjna

Laboratorium informatyczne lub pracownia fizyczna 2

Procesy w systemie operacyjnym Linux

Procesy w systemie operacyjnym Linux. PID, PPID, PGID, SID. Terminal sterujący

Polecenia ps i kill

Rozwidlanie procesów. Funkcje fork() i execl()

Czekanie na zakończenie procesów potomnych. Funkcja wait(). Procesy zombi

Komunikacja pomiędzy spokrewnionymi procesami przy pomocy rurek

Deskryptory plików. Opakowywanie deskryptora strumieniem

Tworzenie rurek anonimowych i komunikacja przy pomocy rurek

Funkcja dup2(). Przekierowywanie standardowego wejścia i wyjścia.

Wątki w Pythonie

Tworzenie i łączenie wątków

Muteksy i zmienne warunkowe

Klasyczne problemy synchronizacji z wątkami, semaforami, muteksami i zmiennymi warunkowymi

semafory

Gniazda i programowanie rozproszone

Serwer i klient z wykorzystaniem gniazd TCP

Literatura podstawowa

A. Silberschatz, P.B. Gavin, Podstawy systemów operacyjnych. Wydawnictwa Naukowo-Techniczne Warszawa 1998

M. Ben-Ari, Podstawy programowania współbieżnego Wydawnictwa Naukowo-Techniczne Warszawa 1989

A.S. Tanenbaum, M. Steen, Systemy rozproszone. Zasady i paradygmaty. Wydawnictwa Naukowo-Techniczne Warszawa 2006

Literatura dodatkowa

M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego. Wydawnictwa Naukowo-Techniczne, Warszawa 1996.

A.B. Downey, The Little Book of Semaphores http://www.greenteapress.com/semaphores/

E. W. Dijkstra, “Hierarchical ordering of sequential processes,” Acta Informatica, Vol. 1, pp. 115-138.

L. Lamport, “A New Solution of Dijkstra’s Concurrent Programming Problem”, Communications of the ACM, August 1974, Vol. 17, No. 8.

L. Lamport, “Time, Clocks, and the ordering of Events in a Distributed System”, Communications of the ACM, July 1978, Vol. 21, No. 7.

L. Lamport, S. Shostak, M. Pease, “The Byzantine Generals Problem”, ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, 382-401.

brak

Wykład 1

Metody podające | Wykład informacyjny

Metody podające | Wykład problemowy

Laboratorium informatyczne lub pracownia fizyczna 2

Metody poszukujące | Metoda ćwiczeniowa

Metody poszukujące | Metoda problemowa

OCENA KOŃCOWA Z PRZEDMIOTU

jest ustalana zgodnie z algorytmem:

Ocena z formy: "Wykład 1" ocena * 50.00 %

+ Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 2" ocena * 50.00 %

Dodatkowe warunki zaliczenia przedmiotu:

Ocena końcowa jest średnią ocen z ćwiczeń i wykładu

Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Test / quiz - 100.00%

Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Obecność na wykładzie i ćwiczeniach jest obowiązkowa

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Wykonanie ćwiczenia - 50.00%

Odpowiedź ustna - 50.00%

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Brak

Wykład 1

Informacje podstawowe

Procesy ciężkie i lekkie (wątki), wywłaszczanie, izolacja pamięci, cykl życia procesu

Przerwania, procedury obsługi przerwań i DMA

Tryb jądra i tryb użytkownika, architektura systemu Linux

Powody stosowania współbieżności i rozpraszania obliczeń

Problemy związane z rozpraszaniem i współbieżnością

Poprawność procesów współbieżnych (własności bezpieczeństwa i żywotności)

Nieadekwatność testowania do weryfikacji poprawności programów współbieżnych

Formalizmy do modelowania programów współbieznych i rozproszonych

Problem ochrony sekcji krytycznych

Algorytm Dekkera

Algorytm piekarza

Mechanizm Test And Set

Po co potrzebne są sekcje krytyczne

Abstrakcja: muteksy

Zakleszczenia

Model korzystania z zasobów

Zagnieżdżone sekcje krytyczne i zakleszczenia

Warunki konieczne wystąpienia zakleszczenia

Graf przydziału zasobów i zakleszczenia

Zapobieganie zakleszczeniom

Stan bezpieczny i stan zagrożenia. Ciągi bezpieczne

Krawędzie deklaracji i wykrywanie stanu zagrożenie w przypadku jednoegzemplarzowych typów zasobów

Algorytm bankiera

Wykrywanie zakleszczeń. Algorytm grafu oczekiwania

Semafory i zmienne warunkowe

Semafory zliczające i binarne. Operacje Wait i Signal

Implementacje semaforów zliczających z aktywnym czekaniem i bez (ze wsparciem systemu operacyjnego)

Ochrona sekcji krytycznych przy pomocy semaforów. Uogólnione sekcje krytyczne

Sygnalizowanie przy pomocy semaforów

Spotkanie dwóch i wielu procesów (bariera) z wykorzystaniem semaforów i zmiennych warunkowych

Bariera wielokrotnego użytku

Wykorzystanie zmiennych warunkowych do oczekiwania na spełnienie warunku

Klasyczne problemy synchronizacji

Problem producenta/konsumenta

Problem czytelników i pisarzy

Problem obiadujących filozofów

Czas rozproszony

Synchroniczne i asynchroniczne przekazywanie komunikatów i ich wzajemna symulacja

Procesy w systemach rozproszonych jako ciągi zdarzeń. Zdarzenia wewnętrzne i zdarzenia odebrania i wysyłania komunikatów

Porządek zależności przyczynowej pomiędzy zdarzeniami w systemie rozproszonym

Diagramy czasoprzestrzenne zdarzeń

Logiczna i fizyczna współbieżność

Stan systemu rozproszonego. Globalny stan spójny

Własności kanałów komunikacyjnych: Kanały FIFO, kanały z CO (Casual Ordering), kanały niezawodne, kanały gubiące komunikaty

Zegary fizyczne i logiczne

Potrzeba ciągłej synchronizacji zegarów fizycznych. Maksymalne tempo odchylania.

Algorytm NTP (Cristiana) synchronizacji zegarów fizycznych

Skalarne zegary logiczne i algorytm synchronizacji Lamporta

Algorytm całkowicie uporządkowanego rozsyłania (korzystający z zegarów skalarnych)

Silne i słabe zegary logiczne

Zegary wektorowe i ich synchronizacja. Zastosowanie do wersjonowania danych.

Algorytmy wzajemnego wykluczania rozproszonego

Algorytm scentralizowany

Algorytm Lamporta

Algorytm Ricarta-Agrawala

Algorytmy oparte na zetonach

Algorytmy oparte na kworach

Tolerowanie awarii

Przyczyny awarii w systemach komputerowych

Cechy niezawodnych systemów (dostępność, niezawodność, bezpieczeństwo, obsługiwalność)

Rodzaje awarii (błędy przejściowe, sporadyczne, twarde, ludzkie)

Modele awarii (załamanie, błędy ominięcia, awarie odliczania czasu, błędy odpowiedzi, awarie bizantyjskie)

Radzenie sobie z błędami i awariami. Redundancja

Specyfika awarii w środowisku rozproszonym

Problem bizantyjskich generałów i rozwiązanie dla 4 generałów i jednego zdrajcy.

Stosowanie dzienników transakcyjnych

Atomowe protokoły zatwierdzania. Algorytm zatwierdzania dwufazowego.

Algorytm Map-Reduce. Obsługa awarii w Map-Reduce. Przykłady zastosowań

Szeregowalność i szeregowalność kolizyjna

Laboratorium informatyczne lub pracownia fizyczna 2

Procesy w systemie operacyjnym Linux

Procesy w systemie operacyjnym Linux. PID, PPID, PGID, SID. Terminal sterujący

Polecenia ps i kill

Rozwidlanie procesów. Funkcje fork() i execl()

Czekanie na zakończenie procesów potomnych. Funkcja wait(). Procesy zombi

Komunikacja pomiędzy spokrewnionymi procesami przy pomocy rurek

Deskryptory plików. Opakowywanie deskryptora strumieniem

Tworzenie rurek anonimowych i komunikacja przy pomocy rurek

Funkcja dup2(). Przekierowywanie standardowego wejścia i wyjścia.

Wątki w Pythonie

Tworzenie i łączenie wątków

Muteksy i zmienne warunkowe

Klasyczne problemy synchronizacji z wątkami, semaforami, muteksami i zmiennymi warunkowymi

semafory

Gniazda i programowanie rozproszone

Serwer i klient z wykorzystaniem gniazd TCP

Literatura podstawowa

A. Silberschatz, P.B. Gavin, Podstawy systemów operacyjnych. Wydawnictwa Naukowo-Techniczne Warszawa 1998

M. Ben-Ari, Podstawy programowania współbieżnego Wydawnictwa Naukowo-Techniczne Warszawa 1989

A.S. Tanenbaum, M. Steen, Systemy rozproszone. Zasady i paradygmaty. Wydawnictwa Naukowo-Techniczne Warszawa 2006

Literatura dodatkowa

M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego. Wydawnictwa Naukowo-Techniczne, Warszawa 1996.

A.B. Downey, The Little Book of Semaphores http://www.greenteapress.com/semaphores/

E. W. Dijkstra, “Hierarchical ordering of sequential processes,” Acta Informatica, Vol. 1, pp. 115-138.

L. Lamport, “A New Solution of Dijkstra’s Concurrent Programming Problem”, Communications of the ACM, August 1974, Vol. 17, No. 8.

L. Lamport, “Time, Clocks, and the ordering of Events in a Distributed System”, Communications of the ACM, July 1978, Vol. 21, No. 7.

L. Lamport, S. Shostak, M. Pease, “The Byzantine Generals Problem”, ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, 382-401.

brak

Wykład 1

Metody podające | Wykład informacyjny

Metody podające | Wykład problemowy

Laboratorium informatyczne lub pracownia fizyczna 2

Metody poszukujące | Metoda ćwiczeniowa

Metody poszukujące | Metoda problemowa

OCENA KOŃCOWA Z PRZEDMIOTU

jest ustalana zgodnie z algorytmem:

Ocena z formy: "Wykład 1" ocena * 50.00 %

+ Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 2" ocena * 50.00 %

Dodatkowe warunki zaliczenia przedmiotu:

Ocena końcowa jest średnią ocen z ćwiczeń i wykładu

Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Test / quiz - 100.00%

Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Obecność na wykładzie i ćwiczeniach jest obowiązkowa

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Wykonanie ćwiczenia - 50.00%

Odpowiedź ustna - 50.00%

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Brak

Wykład 1

Informacje podstawowe

Procesy ciężkie i lekkie (wątki), wywłaszczanie, izolacja pamięci, cykl życia procesu

Przerwania, procedury obsługi przerwań i DMA

Tryb jądra i tryb użytkownika, architektura systemu Linux

Powody stosowania współbieżności i rozpraszania obliczeń

Problemy związane z rozpraszaniem i współbieżnością

Poprawność procesów współbieżnych (własności bezpieczeństwa i żywotności)

Nieadekwatność testowania do weryfikacji poprawności programów współbieżnych

Formalizmy do modelowania programów współbieznych i rozproszonych

Problem ochrony sekcji krytycznych

Algorytm Dekkera

Algorytm piekarza

Mechanizm Test And Set

Po co potrzebne są sekcje krytyczne

Abstrakcja: muteksy

Zakleszczenia

Model korzystania z zasobów

Zagnieżdżone sekcje krytyczne i zakleszczenia

Warunki konieczne wystąpienia zakleszczenia

Graf przydziału zasobów i zakleszczenia

Zapobieganie zakleszczeniom

Stan bezpieczny i stan zagrożenia. Ciągi bezpieczne

Krawędzie deklaracji i wykrywanie stanu zagrożenie w przypadku jednoegzemplarzowych typów zasobów

Algorytm bankiera

Wykrywanie zakleszczeń. Algorytm grafu oczekiwania

Semafory i zmienne warunkowe

Semafory zliczające i binarne. Operacje Wait i Signal

Implementacje semaforów zliczających z aktywnym czekaniem i bez (ze wsparciem systemu operacyjnego)

Ochrona sekcji krytycznych przy pomocy semaforów. Uogólnione sekcje krytyczne

Sygnalizowanie przy pomocy semaforów

Spotkanie dwóch i wielu procesów (bariera) z wykorzystaniem semaforów i zmiennych warunkowych

Bariera wielokrotnego użytku

Wykorzystanie zmiennych warunkowych do oczekiwania na spełnienie warunku

Klasyczne problemy synchronizacji

Problem producenta/konsumenta

Problem czytelników i pisarzy

Problem obiadujących filozofów

Czas rozproszony

Synchroniczne i asynchroniczne przekazywanie komunikatów i ich wzajemna symulacja

Procesy w systemach rozproszonych jako ciągi zdarzeń. Zdarzenia wewnętrzne i zdarzenia odebrania i wysyłania komunikatów

Porządek zależności przyczynowej pomiędzy zdarzeniami w systemie rozproszonym

Diagramy czasoprzestrzenne zdarzeń

Logiczna i fizyczna współbieżność

Stan systemu rozproszonego. Globalny stan spójny

Własności kanałów komunikacyjnych: Kanały FIFO, kanały z CO (Casual Ordering), kanały niezawodne, kanały gubiące komunikaty

Zegary fizyczne i logiczne

Potrzeba ciągłej synchronizacji zegarów fizycznych. Maksymalne tempo odchylania.

Algorytm NTP (Cristiana) synchronizacji zegarów fizycznych

Skalarne zegary logiczne i algorytm synchronizacji Lamporta

Algorytm całkowicie uporządkowanego rozsyłania (korzystający z zegarów skalarnych)

Silne i słabe zegary logiczne

Zegary wektorowe i ich synchronizacja. Zastosowanie do wersjonowania danych.

Algorytmy wzajemnego wykluczania rozproszonego

Algorytm scentralizowany

Algorytm Lamporta

Algorytm Ricarta-Agrawala

Algorytmy oparte na zetonach

Algorytmy oparte na kworach

Tolerowanie awarii

Przyczyny awarii w systemach komputerowych

Cechy niezawodnych systemów (dostępność, niezawodność, bezpieczeństwo, obsługiwalność)

Rodzaje awarii (błędy przejściowe, sporadyczne, twarde, ludzkie)

Modele awarii (załamanie, błędy ominięcia, awarie odliczania czasu, błędy odpowiedzi, awarie bizantyjskie)

Radzenie sobie z błędami i awariami. Redundancja

Specyfika awarii w środowisku rozproszonym

Problem bizantyjskich generałów i rozwiązanie dla 4 generałów i jednego zdrajcy.

Stosowanie dzienników transakcyjnych

Atomowe protokoły zatwierdzania. Algorytm zatwierdzania dwufazowego.

Algorytm Map-Reduce. Obsługa awarii w Map-Reduce. Przykłady zastosowań

Szeregowalność i szeregowalność kolizyjna

Laboratorium informatyczne lub pracownia fizyczna 2

Procesy w systemie operacyjnym Linux

Procesy w systemie operacyjnym Linux. PID, PPID, PGID, SID. Terminal sterujący

Polecenia ps i kill

Rozwidlanie procesów. Funkcje fork() i execl()

Czekanie na zakończenie procesów potomnych. Funkcja wait(). Procesy zombi

Komunikacja pomiędzy spokrewnionymi procesami przy pomocy rurek

Deskryptory plików. Opakowywanie deskryptora strumieniem

Tworzenie rurek anonimowych i komunikacja przy pomocy rurek

Funkcja dup2(). Przekierowywanie standardowego wejścia i wyjścia.

Wątki w Pythonie

Tworzenie i łączenie wątków

Muteksy i zmienne warunkowe

Klasyczne problemy synchronizacji z wątkami, semaforami, muteksami i zmiennymi warunkowymi

semafory

Gniazda i programowanie rozproszone

Serwer i klient z wykorzystaniem gniazd TCP

Literatura podstawowa

A. Silberschatz, P.B. Gavin, Podstawy systemów operacyjnych. Wydawnictwa Naukowo-Techniczne Warszawa 1998

M. Ben-Ari, Podstawy programowania współbieżnego Wydawnictwa Naukowo-Techniczne Warszawa 1989

A.S. Tanenbaum, M. Steen, Systemy rozproszone. Zasady i paradygmaty. Wydawnictwa Naukowo-Techniczne Warszawa 2006

Literatura dodatkowa

M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego. Wydawnictwa Naukowo-Techniczne, Warszawa 1996.

A.B. Downey, The Little Book of Semaphores http://www.greenteapress.com/semaphores/

E. W. Dijkstra, “Hierarchical ordering of sequential processes,” Acta Informatica, Vol. 1, pp. 115-138.

L. Lamport, “A New Solution of Dijkstra’s Concurrent Programming Problem”, Communications of the ACM, August 1974, Vol. 17, No. 8.

L. Lamport, “Time, Clocks, and the ordering of Events in a Distributed System”, Communications of the ACM, July 1978, Vol. 21, No. 7.

L. Lamport, S. Shostak, M. Pease, “The Byzantine Generals Problem”, ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, 382-401.

brak

Wykład 1

Metody podające | Wykład informacyjny

Metody podające | Wykład problemowy

Laboratorium informatyczne lub pracownia fizyczna 2

Metody poszukujące | Metoda ćwiczeniowa

Metody poszukujące | Metoda problemowa

OCENA KOŃCOWA Z PRZEDMIOTU

jest ustalana zgodnie z algorytmem:

Ocena z formy: "Wykład 1" ocena * 50.00 %

+ Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 2" ocena * 50.00 %

Dodatkowe warunki zaliczenia przedmiotu:

Ocena końcowa jest średnią ocen z ćwiczeń i wykładu

Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Test / quiz - 100.00%

Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Obecność na wykładzie i ćwiczeniach jest obowiązkowa

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Wykonanie ćwiczenia - 50.00%

Odpowiedź ustna - 50.00%

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Brak

Wykład 1

Informacje podstawowe

Procesy ciężkie i lekkie (wątki), wywłaszczanie, izolacja pamięci, cykl życia procesu

Przerwania, procedury obsługi przerwań i DMA

Tryb jądra i tryb użytkownika, architektura systemu Linux

Powody stosowania współbieżności i rozpraszania obliczeń

Problemy związane z rozpraszaniem i współbieżnością

Poprawność procesów współbieżnych (własności bezpieczeństwa i żywotności)

Nieadekwatność testowania do weryfikacji poprawności programów współbieżnych

Formalizmy do modelowania programów współbieznych i rozproszonych

Problem ochrony sekcji krytycznych

Algorytm Dekkera

Algorytm piekarza

Mechanizm Test And Set

Po co potrzebne są sekcje krytyczne

Abstrakcja: muteksy

Zakleszczenia

Model korzystania z zasobów

Zagnieżdżone sekcje krytyczne i zakleszczenia

Warunki konieczne wystąpienia zakleszczenia

Graf przydziału zasobów i zakleszczenia

Zapobieganie zakleszczeniom

Stan bezpieczny i stan zagrożenia. Ciągi bezpieczne

Krawędzie deklaracji i wykrywanie stanu zagrożenie w przypadku jednoegzemplarzowych typów zasobów

Algorytm bankiera

Wykrywanie zakleszczeń. Algorytm grafu oczekiwania

Semafory i zmienne warunkowe

Semafory zliczające i binarne. Operacje Wait i Signal

Implementacje semaforów zliczających z aktywnym czekaniem i bez (ze wsparciem systemu operacyjnego)

Ochrona sekcji krytycznych przy pomocy semaforów. Uogólnione sekcje krytyczne

Sygnalizowanie przy pomocy semaforów

Spotkanie dwóch i wielu procesów (bariera) z wykorzystaniem semaforów i zmiennych warunkowych

Bariera wielokrotnego użytku

Wykorzystanie zmiennych warunkowych do oczekiwania na spełnienie warunku

Klasyczne problemy synchronizacji

Problem producenta/konsumenta

Problem czytelników i pisarzy

Problem obiadujących filozofów

Czas rozproszony

Synchroniczne i asynchroniczne przekazywanie komunikatów i ich wzajemna symulacja

Procesy w systemach rozproszonych jako ciągi zdarzeń. Zdarzenia wewnętrzne i zdarzenia odebrania i wysyłania komunikatów

Porządek zależności przyczynowej pomiędzy zdarzeniami w systemie rozproszonym

Diagramy czasoprzestrzenne zdarzeń

Logiczna i fizyczna współbieżność

Stan systemu rozproszonego. Globalny stan spójny

Własności kanałów komunikacyjnych: Kanały FIFO, kanały z CO (Casual Ordering), kanały niezawodne, kanały gubiące komunikaty

Zegary fizyczne i logiczne

Potrzeba ciągłej synchronizacji zegarów fizycznych. Maksymalne tempo odchylania.

Algorytm NTP (Cristiana) synchronizacji zegarów fizycznych

Skalarne zegary logiczne i algorytm synchronizacji Lamporta

Algorytm całkowicie uporządkowanego rozsyłania (korzystający z zegarów skalarnych)

Silne i słabe zegary logiczne

Zegary wektorowe i ich synchronizacja. Zastosowanie do wersjonowania danych.

Algorytmy wzajemnego wykluczania rozproszonego

Algorytm scentralizowany

Algorytm Lamporta

Algorytm Ricarta-Agrawala

Algorytmy oparte na zetonach

Algorytmy oparte na kworach

Tolerowanie awarii

Przyczyny awarii w systemach komputerowych

Cechy niezawodnych systemów (dostępność, niezawodność, bezpieczeństwo, obsługiwalność)

Rodzaje awarii (błędy przejściowe, sporadyczne, twarde, ludzkie)

Modele awarii (załamanie, błędy ominięcia, awarie odliczania czasu, błędy odpowiedzi, awarie bizantyjskie)

Radzenie sobie z błędami i awariami. Redundancja

Specyfika awarii w środowisku rozproszonym

Problem bizantyjskich generałów i rozwiązanie dla 4 generałów i jednego zdrajcy.

Stosowanie dzienników transakcyjnych

Atomowe protokoły zatwierdzania. Algorytm zatwierdzania dwufazowego.

Algorytm Map-Reduce. Obsługa awarii w Map-Reduce. Przykłady zastosowań

Szeregowalność i szeregowalność kolizyjna

Laboratorium informatyczne lub pracownia fizyczna 2

Procesy w systemie operacyjnym Linux

Procesy w systemie operacyjnym Linux. PID, PPID, PGID, SID. Terminal sterujący

Polecenia ps i kill

Rozwidlanie procesów. Funkcje fork() i execl()

Czekanie na zakończenie procesów potomnych. Funkcja wait(). Procesy zombi

Komunikacja pomiędzy spokrewnionymi procesami przy pomocy rurek

Deskryptory plików. Opakowywanie deskryptora strumieniem

Tworzenie rurek anonimowych i komunikacja przy pomocy rurek

Funkcja dup2(). Przekierowywanie standardowego wejścia i wyjścia.

Wątki w Pythonie

Tworzenie i łączenie wątków

Muteksy i zmienne warunkowe

Klasyczne problemy synchronizacji z wątkami, semaforami, muteksami i zmiennymi warunkowymi

semafory

Gniazda i programowanie rozproszone

Serwer i klient z wykorzystaniem gniazd TCP

Literatura podstawowa

A. Silberschatz, P.B. Gavin, Podstawy systemów operacyjnych. Wydawnictwa Naukowo-Techniczne Warszawa 1998

M. Ben-Ari, Podstawy programowania współbieżnego Wydawnictwa Naukowo-Techniczne Warszawa 1989

A.S. Tanenbaum, M. Steen, Systemy rozproszone. Zasady i paradygmaty. Wydawnictwa Naukowo-Techniczne Warszawa 2006

Literatura dodatkowa

M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego. Wydawnictwa Naukowo-Techniczne, Warszawa 1996.

A.B. Downey, The Little Book of Semaphores http://www.greenteapress.com/semaphores/

E. W. Dijkstra, “Hierarchical ordering of sequential processes,” Acta Informatica, Vol. 1, pp. 115-138.

L. Lamport, “A New Solution of Dijkstra’s Concurrent Programming Problem”, Communications of the ACM, August 1974, Vol. 17, No. 8.

L. Lamport, “Time, Clocks, and the ordering of Events in a Distributed System”, Communications of the ACM, July 1978, Vol. 21, No. 7.

L. Lamport, S. Shostak, M. Pease, “The Byzantine Generals Problem”, ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, 382-401.

Wykład 1

Metody podające | Wykład informacyjny

Metody podające | Wykład problemowy

Laboratorium informatyczne lub pracownia fizyczna 2

Metody poszukujące | Metoda ćwiczeniowa

Metody poszukujące | Metoda problemowa

OCENA KOŃCOWA Z PRZEDMIOTU

jest ustalana zgodnie z algorytmem:

Ocena z formy: "Wykład 1" ocena * 100.00 %

+ Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 2" ocena * 100.00 %

Dodatkowe warunki zaliczenia przedmiotu:

Ocena końcowa jest średnią ocen z ćwiczeń i wykładu

Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Odpowiedź ustna - 100.00%

Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Obecność na wykładzie jest obowiązkowa

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Wykonanie ćwiczenia - 50.00%

Odpowiedź ustna - 50.00%

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Brak

Wykład 1

Informacje podstawowe

Procesy ciężkie i lekkie (wątki), wywłaszczanie, izolacja pamięci, cykl życia procesu

Przerwania, procedury obsługi przerwań i DMA

Tryb jądra i tryb użytkownika, architektura systemu Linux

Powody stosowania współbieżności i rozpraszania obliczeń

Problemy związane z rozpraszaniem i współbieżnością

Poprawność procesów współbieżnych (własności bezpieczeństwa i żywotności)

Nieadekwatność testowania do weryfikacji poprawności programów współbieżnych

Formalizmy do modelowania programów współbieznych i rozproszonych

Problem ochrony sekcji krytycznych

Algorytm Dekkera

Algorytm piekarza

Mechanizm Test And Set

Po co potrzebne są sekcje krytyczne

Abstrakcja: muteksy

Zakleszczenia

Model korzystania z zasobów

Zagnieżdżone sekcje krytyczne i zakleszczenia

Warunki konieczne wystąpienia zakleszczenia

Graf przydziału zasobów i zakleszczenia

Zapobieganie zakleszczeniom

Stan bezpieczny i stan zagrożenia. Ciągi bezpieczne

Krawędzie deklaracji i wykrywanie stanu zagrożenie w przypadku jednoegzemplarzowych typów zasobów

Algorytm bankiera

Wykrywanie zakleszczeń. Algorytm grafu oczekiwania

Semafory

Semafory zliczające i binarne. Operacje Wait i Signal

Implementacje semaforów zliczających z aktywnym czekaniem i bez (ze wsparciem systemu operacyjnego)

Słabe i silne semafory

Ochrona sekcji krytycznych przy pomocy semaforów. Uogólnione sekcje krytyczne

Sygnalizowanie przy pomocy semaforów

Spotkanie dwóch i wielu procesów (bariera) z wykorzystaniem semaforów

Bariera wielokrotnego użytku

Równoważność semaforów binarynych i zliczających

Klasyczne problemy synchronizacji

Problem producenta/konsumenta

Problem czytelników i pisarzy

Problem obiadujących filozofów

Problem palaczy papierosów

Wysokopoziomowe mechanizmy synchronizacji

Warunkowe regiony krytyczne

Regiony krytyczne a semafory

Problem producenta/konsumenta a warunkowe regiony krytyczne

Monitory i zmienne warunkowe

Problem producenta-konsumenta i monitory

Obiadujący filozofowie i monitory

Równoważność monitorów i semaforów

Pamięć transakcyjna i kompozycjonalność kodu

Plany wykonania: szeregowe, szeregowalne i szeregowalne kolizyjnie

Atomowość, izolacja , spójność

Blokady i algorytm blokowania dwufazowego

Czas rozproszony

Synchroniczne i asynchroniczne przekazywanie komunikatów i ich wzajemna symulacja

Procesy w systemach rozproszonych jako ciągi zdarzeń. Zdarzenia wewnętrzne i zdarzenia odebrania i wysyłania komunikatów

Porządek zależności przyczynowej pomiędzy zdarzeniami w systemie rozproszonym

Diagramy czasoprzestrzenne zdarzeń

Logiczna i fizyczna współbieżność

Stan systemu rozproszonego. Globalny stan spójny

Własności kanałów komunikacyjnych: Kanały FIFO, kanały z CO (Casual Ordering), kanały niezawodne, kanały gubiące komunikaty

Zegary fizyczne i logiczne

Potrzeba ciągłej synchronizacji zegarów fizycznych. Maksymalne tempo odchylania.

Algorytm NTP (Cristiana) synchronizacji zegarów fizycznych

Skalarne zegary logiczne i algorytm synchronizacji Lamporta

Algorytm całkowicie uporządkowanego rozsyłania (korzystający z zegarów skalarnych)

Silne i słabe zegary logiczne

Zegary wektorowe i ich synchronizacja. Zastosowanie do wersjonowania danych.

Algorytmy wzajemnego wykluczania rozproszonego

Algorytm scentralizowany

Algorytm Lamporta

Algorytm Ricarta-Agrawala

Algorytmy oparte na zetonach

Algorytmy oparte na kworach

Tolerowanie awarii

Przyczyny awarii w systemach komputerowych

Cechy niezawodnych systemów (dostępność, niezawodność, bezpieczeństwo, obsługiwalność)

Rodzaje awarii (błędy przejściowe, sporadyczne, twarde, ludzkie)

Modele awarii (załamanie, błędy ominięcia, awarie odliczania czasu, błędy odpowiedzi, awarie bizantyjskie)

Radzenie sobie z błędami i awariami. Redundancja

Specyfika awarii w środowisku rozproszonym

Problem bizantyjskich generałów i rozwiązanie dla 4 generałów i jednego zdrajcy.

Stosowanie dzienników transakcyjnych

Atomowe protokoły zatwierdzania. Algorytm zatwierdzania dwufazowego.

Algorytm Map-Reduce. Obsługa awarii w Map-Reduce. Przykłady zastosowań

Laboratorium informatyczne lub pracownia fizyczna 2

Procesy w systemie operacyjnym Linux

Procesy w systemie operacyjnym Linux. PID, PPID, PGID, SID. Terminal sterujący

Polecenia ps i kill

Rozwidlanie procesów. Funkcje fork() i execl()

Czekanie na zakończenie procesów potomnych. Funkcja wait(). Procesy zombi

Sygnały w systemie Linux

Podstawowe sygnały. Cechy sygnałów. Maskowanie

Deklarowanie własnych procedur obsługi sygnałów. Funkcja signal()

Wysyłanie sygnałów. Funkcja kill()

Odbieranie statusu zakończenia potomka w procedurze obsługi sygnału SIGCHLD

Komunikacja pomiędzy spokrewnionymi procesami przy pomocy rurek

Deskryptory plików. Opakowywanie deskryptora strumieniem

Tworzenie rurek anonimowych i komunikacja przy pomocy rurek

Funkcja dup2(). Przekierowywanie standardowego wejścia i wyjścia.

Obiekty IPC Sys V

Segmenty pamięci dzielonej

Tablice semaforów

Klasyczne problemy synchronizacji z wykorzystaniem semaforów i segmentów pamięci dzielonej

Wątki

Tworzenie i łączenie wątków

Muteksy i zmienne warunkowe

Klasyczne problemy synchronizacji z wątkami, muteksami i zmiennymi warunkowymi

Gniazda i programowanie rozproszone

Serwer i klient z wykorzystaniem gniazd TCP

Literatura podstawowa

A. Silberschatz, P.B. Gavin, Podstawy systemów operacyjnych. Wydawnictwa Naukowo-Techniczne Warszawa 1998

M. Ben-Ari, Podstawy programowania współbieżnego Wydawnictwa Naukowo-Techniczne Warszawa 1989

A.S. Tanenbaum, M. Steen, Systemy rozproszone. Zasady i paradygmaty. Wydawnictwa Naukowo-Techniczne Warszawa 2006

Literatura dodatkowa

M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego. Wydawnictwa Naukowo-Techniczne, Warszawa 1996.

A.B. Downey, The Little Book of Semaphores http://www.greenteapress.com/semaphores/

E. W. Dijkstra, “Hierarchical ordering of sequential processes,” Acta Informatica, Vol. 1, pp. 115-138.

L. Lamport, “A New Solution of Dijkstra’s Concurrent Programming Problem”, Communications of the ACM, August 1974, Vol. 17, No. 8.

L. Lamport, “Time, Clocks, and the ordering of Events in a Distributed System”, Communications of the ACM, July 1978, Vol. 21, No. 7.

L. Lamport, S. Shostak, M. Pease, “The Byzantine Generals Problem”, ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, 382-401.

Wykład 1

Metody podające | Wykład informacyjny

Metody podające | Wykład problemowy

Laboratorium informatyczne lub pracownia fizyczna 2

Metody poszukujące | Metoda ćwiczeniowa

Metody poszukujące | Metoda problemowa

OCENA KOŃCOWA Z PRZEDMIOTU

jest ustalana zgodnie z algorytmem:

Ocena z formy: "Wykład 1" ocena * 100.00 %

+ Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 2" ocena * 100.00 %

Dodatkowe warunki zaliczenia przedmiotu:

Ocena końcowa jest średnią ocen z ćwiczeń i wykładu

Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Odpowiedź ustna - 100.00%

Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Obecność na wykładzie jest obowiązkowa

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia:

Wykonanie ćwiczenia - 50.00%

Odpowiedź ustna - 50.00%

Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 2" ustalana jest na podstawie następującej skali:

Poniżej 50.00% - ocena 2

50.00% i więcej - ocena 3

60.00% i więcej - ocena 3,5

70.00% i więcej - ocena 4

80.00% i więcej - ocena 4,5

90.00% i więcej - ocena 5

Dodatkowe warunki zaliczenia formy:

Brak

Wykład 1

Informacje podstawowe

Procesy ciężkie i lekkie (wątki), wywłaszczanie, izolacja pamięci, cykl życia procesu

Przerwania, procedury obsługi przerwań i DMA

Tryb jądra i tryb użytkownika, architektura systemu Linux

Powody stosowania współbieżności i rozpraszania obliczeń

Problemy związane z rozpraszaniem i współbieżnością

Poprawność procesów współbieżnych (własności bezpieczeństwa i żywotności)

Nieadekwatność testowania do weryfikacji poprawności programów współbieżnych

Formalizmy do modelowania programów współbieznych i rozproszonych

Problem ochrony sekcji krytycznych

Algorytm Dekkera

Algorytm piekarza

Mechanizm Test And Set

Po co potrzebne są sekcje krytyczne

Abstrakcja: muteksy

Zakleszczenia

Model korzystania z zasobów

Zagnieżdżone sekcje krytyczne i zakleszczenia

Warunki konieczne wystąpienia zakleszczenia

Graf przydziału zasobów i zakleszczenia

Zapobieganie zakleszczeniom

Stan bezpieczny i stan zagrożenia. Ciągi bezpieczne

Krawędzie deklaracji i wykrywanie stanu zagrożenie w przypadku jednoegzemplarzowych typów zasobów

Algorytm bankiera

Wykrywanie zakleszczeń. Algorytm grafu oczekiwania

Semafory

Semafory zliczające i binarne. Operacje Wait i Signal

Implementacje semaforów zliczających z aktywnym czekaniem i bez (ze wsparciem systemu operacyjnego)

Słabe i silne semafory

Ochrona sekcji krytycznych przy pomocy semaforów. Uogólnione sekcje krytyczne

Sygnalizowanie przy pomocy semaforów

Spotkanie dwóch i wielu procesów (bariera) z wykorzystaniem semaforów

Bariera wielokrotnego użytku

Równoważność semaforów binarynych i zliczających

Klasyczne problemy synchronizacji

Problem producenta/konsumenta

Problem czytelników i pisarzy

Problem obiadujących filozofów

Problem palaczy papierosów

Wysokopoziomowe mechanizmy synchronizacji

Warunkowe regiony krytyczne

Regiony krytyczne a semafory

Problem producenta/konsumenta a warunkowe regiony krytyczne

Monitory i zmienne warunkowe

Problem producenta-konsumenta i monitory

Obiadujący filozofowie i monitory

Równoważność monitorów i semaforów

Pamięć transakcyjna i kompozycjonalność kodu

Plany wykonania: szeregowe, szeregowalne i szeregowalne kolizyjnie

Atomowość, izolacja , spójność

Blokady i algorytm blokowania dwufazowego

Czas rozproszony

Synchroniczne i asynchroniczne przekazywanie komunikatów i ich wzajemna symulacja

Procesy w systemach rozproszonych jako ciągi zdarzeń. Zdarzenia wewnętrzne i zdarzenia odebrania i wysyłania komunikatów

Porządek zależności przyczynowej pomiędzy zdarzeniami w systemie rozproszonym

Diagramy czasoprzestrzenne zdarzeń

Logiczna i fizyczna współbieżność

Stan systemu rozproszonego. Globalny stan spójny

Własności kanałów komunikacyjnych: Kanały FIFO, kanały z CO (Casual Ordering), kanały niezawodne, kanały gubiące komunikaty

Zegary fizyczne i logiczne

Potrzeba ciągłej synchronizacji zegarów fizycznych. Maksymalne tempo odchylania.

Algorytm NTP (Cristiana) synchronizacji zegarów fizycznych

Skalarne zegary logiczne i algorytm synchronizacji Lamporta

Algorytm całkowicie uporządkowanego rozsyłania (korzystający z zegarów skalarnych)

Silne i słabe zegary logiczne

Zegary wektorowe i ich synchronizacja. Zastosowanie do wersjonowania danych.

Algorytmy wzajemnego wykluczania rozproszonego

Algorytm scentralizowany

Algorytm Lamporta

Algorytm Ricarta-Agrawala

Algorytmy oparte na zetonach

Algorytmy oparte na kworach

Tolerowanie awarii

Przyczyny awarii w systemach komputerowych

Cechy niezawodnych systemów (dostępność, niezawodność, bezpieczeństwo, obsługiwalność)

Rodzaje awarii (błędy przejściowe, sporadyczne, twarde, ludzkie)

Modele awarii (załamanie, błędy ominięcia, awarie odliczania czasu, błędy odpowiedzi, awarie bizantyjskie)

Radzenie sobie z błędami i awariami. Redundancja

Specyfika awarii w środowisku rozproszonym

Problem bizantyjskich generałów i rozwiązanie dla 4 generałów i jednego zdrajcy.

Stosowanie dzienników transakcyjnych

Atomowe protokoły zatwierdzania. Algorytm zatwierdzania dwufazowego.

Algorytm Map-Reduce. Obsługa awarii w Map-Reduce. Przykłady zastosowań

Laboratorium informatyczne lub pracownia fizyczna 2

Procesy w systemie operacyjnym Linux

Procesy w systemie operacyjnym Linux. PID, PPID, PGID, SID. Terminal sterujący

Polecenia ps i kill

Rozwidlanie procesów. Funkcje fork() i execl()

Czekanie na zakończenie procesów potomnych. Funkcja wait(). Procesy zombi

Sygnały w systemie Linux

Podstawowe sygnały. Cechy sygnałów. Maskowanie

Deklarowanie własnych procedur obsługi sygnałów. Funkcja signal()

Wysyłanie sygnałów. Funkcja kill()

Odbieranie statusu zakończenia potomka w procedurze obsługi sygnału SIGCHLD

Komunikacja pomiędzy spokrewnionymi procesami przy pomocy rurek

Deskryptory plików. Opakowywanie deskryptora strumieniem

Tworzenie rurek anonimowych i komunikacja przy pomocy rurek

Funkcja dup2(). Przekierowywanie standardowego wejścia i wyjścia.

Obiekty IPC Sys V

Segmenty pamięci dzielonej

Tablice semaforów

Klasyczne problemy synchronizacji z wykorzystaniem semaforów i segmentów pamięci dzielonej

Wątki POSIX

Tworzenie i łączenie wątków

Muteksy i zmienne warunkowe

Klasyczne problemy synchronizacji z wątkami, muteksami i zmiennymi warunkowymi

Gniazda i programowanie rozproszone

Serwer i klient z wykorzystaniem gniazd TCP

Literatura podstawowa

A. Silberschatz, P.B. Gavin, Podstawy systemów operacyjnych. Wydawnictwa Naukowo-Techniczne Warszawa 1998

M. Ben-Ari, Podstawy programowania współbieżnego Wydawnictwa Naukowo-Techniczne Warszawa 1989

A.S. Tanenbaum, M. Steen, Systemy rozproszone. Zasady i paradygmaty. Wydawnictwa Naukowo-Techniczne Warszawa 2006

Literatura dodatkowa

M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego. Wydawnictwa Naukowo-Techniczne, Warszawa 1996.

A.B. Downey, The Little Book of Semaphores http://www.greenteapress.com/semaphores/

E. W. Dijkstra, “Hierarchical ordering of sequential processes,” Acta Informatica, Vol. 1, pp. 115-138.

L. Lamport, “A New Solution of Dijkstra’s Concurrent Programming Problem”, Communications of the ACM, August 1974, Vol. 17, No. 8.

L. Lamport, “Time, Clocks, and the ordering of Events in a Distributed System”, Communications of the ACM, July 1978, Vol. 21, No. 7.

L. Lamport, S. Shostak, M. Pease, “The Byzantine Generals Problem”, ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, 382-401.

Wykład informacyjny z elementami prezentacji multimedialnych.

Metoda ćwiczeniowa.

Ocena z wykładu wystawiana jest na podstawie egzaminu ustnego sprawdzającego wiedzę teoretyczną studenta.

Ocena z ćwiczeń wystawiana jest na podstawie kilku wybranych (trudniejszych) ćwiczeń programistycznych z zajęć dla których student musi przedstawić i omówić rozwiązanie. Ocena bierze pod uwagę trudność wybranych ćwiczeń, jakość rozwiązania i umiejętność wyjaśnienia przez studenta problemu i rozwiązania.

Ocena końcowa to średnia ocen z wykładu i ćwiczeń.

Jeśli prowadzący ćwiczenia i wykład to ta sama osoba, egzamin ustny i sprawdzenie ćwiczeń powinno odbyć się w tym samym czasie.

1. Synchronizacja procesów współbieżnych: mechanizmy niskopoziomowe (algorytm Dekkera, synchronizacja sprzętowa dzięki testuj-i-ustaw), semafory liczące i binarne, muteksy, monitory, zmienne warunkowe.

2. Mechanizmy współbieżności: procesy ciężkie, procesy lekkie (wątki systemowe), wątki poziomu użytkownika, wielozadaniowość kooperacyjna.

3. Mechanizmy komunikacji międzyprocesowej: pamięć dzielona, kolejki komunikatów, komunikaty synchroniczne i asynchroniczne.

4. Klasyczne problemy współbieżności: spotkanie dwóch i n procesów, producentów-konsumentów, czytelników i pisarzy, głodnych filozofów.

5. Unikanie i rozpoznawanie zakleszczeń.

6. Naturalna współbieżność: przetwarzanie potokowe.

7. Specyfika przetwarzania rozproszonego.

8. Mechanizmy komunikacji rozproszonej.

9. Problemy współbieżności, np.:

a. Relacja uprzedniości zdarzeń w środowisku rozproszonym.

b. Wzajemne wykluczanie w środowisku rozproszonym.

c. Problem bizantyjskich generałów.

10. Zegary logiczne skalarne i wektorowe. Synchronizacja zegarów w środowisku rozproszonym.

11. Rozproszone podejmowanie decyzji, w szczególności transakcje rozproszone.

12. Mechanizmy współbieżności w systemie Linux

1. A. Silberschatz, P.B. Gavin, Podstawy systemów operacyjnych. Wydawnictwa Naukowo-Techniczne Warszawa 1998

2. M. Ben-Ari, Podstawy programowania współbieżnego Wydawnictwa Naukowo-Techniczne Warszawa 1989

3. A.S. Tanenbaum, M. Steen, Systemy rozproszone. Zasady i paradygmaty. Wydawnictwa Naukowo-Techniczne Warszawa 2006

Literatura uzupełniająca:

1. M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego. Wydawnictwa Naukowo-Techniczne, Warszawa 1996.

2. A.B. Downey, The Little Book of Semaphores http://www.greenteapress.com/semaphores/

3. E. W. Dijkstra, “Hierarchical ordering of sequential processes,” Acta Informatica, Vol. 1, pp. 115-138.

4. L. Lamport, “A New Solution of Dijkstra’s Concurrent Programming Problem”, Communications of the ACM, August 1974, Vol. 17, No. 8.

5. L. Lamport, “Time, Clocks, and the ordering of Events in a Distributed System”, Communications of the ACM, July 1978, Vol. 21, No. 7.

6. L. Lamport, S. Shostak, M. Pease, “The Byzantine Generals Problem”, ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, 382-401.