Przetwarzanie rozproszone: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Szopen (dyskusja | edycje)
1922 edycje
Szopen (dyskusja | edycje)
1922 edycje
Linia 25: Linia 25:
* '''Wykłady:'''  
* '''Wykłady:'''  


* Pierwszą część kursu stanowi moduł wprowadzający  w tematykę przetwarzania rozproszonego (2 godz.). Wykład rozpocznie się od krótkiego wprowadzenia, którego celem będzie zapoznanie słuchacza z bieżącym stanem wiedzy w tej dziedzinie. Następnie przedstawione zostaną proste definicje dotyczące środowiska przetwarzania. W kolejnych punktach wykładu przedstawione zostaną pewne reprezentatywne środowiska przetwarzania rozproszonego. Pierwszym takim środowiskiem będzie Internet. Przedstawiona zostanie jego krótka historia i obecne trendy rozwoju. Następnie krótko scharakteryzowane zostanie środowisko typu GRID. W kolejnym punkcie wykładu opisane zostaną popularne obecnie projekty nazywane potocznie @HOME. Jako przykłady posłużą projekty Seti@HOME, CureCancer, FightAnthrax. Na zakończenie omówiony zostanie projekt środowiska rozproszonego wyszukiwarki internetowej Google.  
* Moduł 1 - ''Wprowadzenie'' (2 godz.). W ramach modułu dotyczącego wprowadzenia do przetwarzania rozproszonego prezentowane są następujące zagadnienia:
podstawowe definicje (węzły, łącza komunikacyjne i ich właściwości, topologia przetwarzania), charakterystyka środowiska przetwarzania rozproszonego, przykłady środowisk rozproszonych (Internet, GRID, projekty ..@Home takie jak Seti@Home czy CureCancer, Google).


* Celem kolejnej części kursu, składającej się z dwóch modułów (4 godz.) będzie zapoznanie słuchacza z podstawowymi pojęciami i problemami związanymi z przetwarzaniem rozproszonym. Wykład obejmie omówienie m. in. definicji procesu sekwencyjnego, komunikatu, kanału komunikacyjnego czy też stanu kanału. W dalszej części wykładu omówione zostaną różnego rodzaju operacje komunikacyjne, a także  scharakteryzowane zostaną rodzaje komunikacji. Student zapozna się także z formalnym modelem procesu sekwencyjnego. Zdefiniowane zostanie pojęcie zdarzenia i podane zostaną definicje różnych ich rodzajów. Kolejnym tematem który zostanie poruszony będzie pojęcie warunku uaktywnienia i definicje z tym związane. Przedstawione zostaną klasyczne modele żądań oraz omówione zostaną ich definicje formalne i własności, a także zaprezentowana zostanie w sposób graficzny ich główna idea. Następnie przedstawiona będzie definicja procesu rozproszonego, wykonania, globalnego stanu spójnego czy też historii realizacji. Następnie zdefiniowana i omówiona zostanie relacja poprzedzania zdarzeń, a także zaprezentowane i omówione zostaną diagramy przestrzenno-czasowe. Przedstawione zostaną pojęcia przetwarzania niedeterministycznego i grafu stanów osiągalnych. Przedostatnim tematem poruszonym w trakcie tego wykładu będzie mechanizm monitora procesu. Na zakończenie krótko omówiona zostanie ujednolicona konwencja zapisu algorytmów, które będą prezentowane na kolejnych wykładach.
* Moduł 2 - ''Przetwarzanie rozproszone'' (2 godz.). W ramach modułu dotyczącego wprowadzenia do przetwarzania rozproszonego prezentowane są następujące zagadnienia: definicje (proces sekwencyjny, komunikaty, kanały komunikacyjne, stan kanału, operacje komunikacyjne (indywidualne i grupowe operacje komunikacyjne, komunikacja synchroniczna i asynchroniczna), model formalny procesu sekwencyjnego (stan procesu, funkcja tranzycji), zdarzenia (zdarzenia wysłania i odbioru, zdarzenia wewnętrzne, zdarzenia gotowe), warunki uaktywnienia (zbiór warunkujący, predykat ''ready'', predykat ''activate''), modele żądań (model jednostkowy, model AND, model OR, podstawowy model ''k spośród r'', model OR-AND, dysjuncyjny model ''k spośród r'', model predykatowy).


* Trzecia część kursu (2 godz) ma na celu  zaznajomienie studenta z pojęciem zegara logicznego, scharakteryzowanie różnych rodzajów kanałów komunikacyjnych, a także przedstawienie analizy poprawności i złożoności algorytmów rozproszonych. Przedstawione zostaną dwa typy zegarów logicznych tzw. zegary skalarne i wektorowe oraz pojęcia z tym związane. Następnie zaprezentowane i omówione zostaną kanały komunikacyjne FIFO i typu FC. Dla każdego z omawianych mechanizmów przedstawiony zostanie przykładowy algorytm zawierający jego implementację. Zdefiniowane zostaną także pojęcia takie, jak rząd funkcji, czy też funkcja kosztu. Pojęcia te zostaną wykorzystane następnie przy omawianiu złożoności komunikacyjnej i czasowej algorytmów rozproszonych. Na zakończenie przedstawione zostaną warunki poprawności algorytmu rozproszonego.
* Moduł 3 -
 
* Tematyka czwartej części kursu, składająca się z dwóch modułów (4 godz.), związana jest z problematyką detekcji zakleszczenia. Wykład obejmie omówienie podstawowych pojęć związanych z przedstawianą tematyką. Przedstawione zostaną definicje zakleszczenia dla różnych modeli żądań. Następnie omówiona zostanie klasyfikacja problemów detekcji zakończenia. Przedstawione zostanie sześć przykładowych algorytmów detekcji zakleszczenia: dla modeli OR, AND, algorytmy detekcji zakleszczenia w środowisku synchronicznym i asynchronicznym dla modelu ''k spośród r'', dwufazowy algorytm detekcji zakleszczenia i na koniec algorytm detekcji zakleszczenia dla modelu predykatowego.
 
* Kolejna część kursu składa się z dwóch modułów (4 godz.) i poświęcona jest problematyce konstrukcji spójnego obrazu stanu globalnego. Omówione zostaną podstawowe pojęcia związane z przedstawianą tematyką, takie jak konfiguracja, konfiguracja spójna, odcięcie, linia odcięcia, predykaty globalne, modele stanów globalnych. Pokazane zostaną relacje między tymi pojęciami. Wyjaśnione zostanie znaczenie problemu wyznaczania stanu globalnego oraz przyczyny dla których jest to problem nietrywialny. Zostanie omówiona koncepcja konstrukcji spójnego obrazu stanu globalnego przy przyjęciu pewnych dodatkowych, upraszczających założeń. Przedstawione też będą następujące algorytmy: algorytm Chandy-Lamporta dla kanałów FIFO, algorytm Matterna stosujący zegary wektorowe, Lai-Yang dla kanałów non-FIFO, algorytm kolorujący procesy i wiadomości, oraz dwa algorytmy dla kanałów typu FC (Chandy-Lamporta i stosujący znaczniki BF i FF). Dla niektórych algorytmów zostanie omówiona ich złożoność czasowa oraz dowiedziona ich poprawność.
 
* Szósta część kursu, składająca się z dwóch modułów (4 godz.), zajmuje się tematyką detekcji zakończenia. Wykład obejmie przedstawienie przykładów ilustrujących potrzebę problemy detekcji zakończenia w systemach rozproszonych (zakończenie sortowania rozproszonego oraz algorytm Matterna konstrukcji spójnego obrazu stanu globalnego), następnie różne definicje zakończenia (zarówno nieformalną jak i formalną, a także definicja klasyczna zakończenia), pojęcia zakończenia dynamicznego i statycznego i relacje między nimi,  zagadnienia związane z detekcją zakończenia w różnych modelach przetwarzania, takich jak model synchroniczny i dyfuzyjny. Student zapozna się również z algorytmami detekcji zakończenia Dijkstry, Feijena, van Gastarena, algorytmem Dijkstry-Scholtena oraz algorytmem Misry dla systemów asynchronicznych, a także z detekcją zakończenia w atomowym modelu przetwarzania: algorytmem z wykorzystaniem liczników wiadomości, jednofazowy algorytm detekcji zakończenia, wektorowy algorytm detekcji zakończenia. Przedstawione zostaną również algorytmy detekcji zakończenia statycznego oraz dynamicznego.  Zostaną również pokazane dowody poprawności tych algorytmów oraz uwagi na temat ich złożoności obliczeniowej.
 
* Siódma część kursu (3 godz.) ma na celu wprowadzenie do tematyki przetwarzania rozproszonego w środowisku zawodnym. Obejmie ona omówienie podstawowych definicji związanych z niezawodnością, w tym pojęcia awarii, błędu i wady oraz klasy awarii. Następnie wprowadzone zostaną precyzyjne definicje mechanizmów (abstrakcji) kanałów komunikacyjnych o różnych właściwościach. W kontekście niezawodności scharakteryzowane zostaną też podstawowe modele systemów rozproszonych: model asynchroniczny, synchroniczny i częściowo synchroniczny. W kolejnym punkcie zaprezentowany będzie mechanizm detektora awarii. Przedstawione zostaną podstawowe klasy detektorów i relacje pomiędzy poszczególnymi klasami, wybrane metryki służące do oceny detektorów awarii, oraz  implementacje detektorów awarii klas P, <math>\Diamond</math>P. Na zakończenie omówiony będzie problem elekcji w środowisku zawodnym i jego związek z detektorami awarii.
 
* Celem przedostatniej części kursu (4 godz.) jest prezentacja zagadnień związanych z implementacją niezawodnej komunikacji w zawodnym środowisku rozproszonym. Wykład obejmie omówienie abstrakcyjnych mechanizmów rozgłaszania wiadomości, takich jak: podstawowe rozgłaszanie niezawodne (ang. ''best-effort''), zgodne rozgłaszanie niezawodne (ang. ''regular reliable broadcast''), jednolite rozgłaszanie niezawodne (ang. ''uniform reliable broadcast'') i probabilistyczne rozgłaszanie niezawodne (ang. ''probabilistic reliable broadcast''). Przedstawione zostaną wybrane algorytmy implementujące wspomniane operacje rozgłaszania wiadomości, w tym: algorytm podstawowego rozgłaszania niezawodnego pasywny i aktywny, algorytmy zgodnego rozgłaszania niezawodnego z potwierdzeniami od wszystkich i z potwierdzeniami od większości, aktywny i pasywny algorytm probabilistycznego rozgłaszania niezawodnego, algorytmy zgodnego rozgłaszania niezawodnego z przyczynowym i globalnym uporządkowaniem wiadomości.
 
* Ostatnia część kursu (3 godz.) obejmuje  tematykę konsensusu i jego wykorzystania w systemach rozproszonych. Wykład obejmie omówienie różnych problemów decyzyjnych oraz konsensus jako przykład tego rodzaju problemów. Pokazana jest niemożliwość rozwiazania konsensusu w asynchronicznym środowisku przetwarzania, jeżeli choć jeden proces może ulec awarii. Omówione zostaną problemy konsensusu (podstawowego), konsensusu (jednolitego), konsensusu probabilistycznego i algorytmy je  rozwiązujące, takie jak  algorytmy rozgłoszeniowy oraz hierarchiczny dla konsensusu podstawowego. Wyjaśnione zostanie na czym polega ważność tego problemu oraz relacje z innymi zagadnieniami pojawiającymi się w systemach rozproszonych.


* '''Laboratoria:'''
* '''Laboratoria:'''

Wersja z 13:27, 4 wrz 2006

Forma zajęć

Wykład (30 godzin) + laboratorium (30 godzin)

Opis

Celem przedmiotu jest przedstawienie podstawowych modeli i problemów przetwarzania rozproszonego oraz przykładów ich zastosowań.

Wykład wprowadza podstawowe pojęcia i modele przetwarzania rozproszonego: formalny model środowiska i procesu (algorytmu) rozproszonego, analizę aktywności i warunki uaktywnienia procesów, klasyczne modele żądań, relację poprzedzania, diagramy przestrzenno-czasowe, grafy stanów osiągalnych, niedeterminizm przetwarzania, spójność obrazu stanu globalnego, predykaty globalne i ich własności, skalarne i wektorowe zegary logiczne, warunki poprawności algorytmów, złożoność czasowa i komunikacyjna. Omawiane są następnie zagadnienia komunikacji zachowującej uporządkowanie wiadomości, konstrukcji spójnego obrazu stanu globalnego, detekcji zakleszczenia rozproszonego oraz detekcji zakończenia przetwarzania rozproszonego. Wreszcie przedstawiona jest problematyka związana z niezawodnością przetwarzania w zawodnym środowisku rozproszonym, w tym zagadnienia: modelowania i klasyfikacji awarii, konstrukcji niezawodnych kanałów komunikacyjnych, realizacji detektorów awarii, niezawodnej komunikacji grupowej oraz konsensusu rozproszonego i jego zastosowań. Laboratorium pozwala nabrać praktycznej intuicji w konstrukcji i implementacji aplikacji rozproszonych w przykładowym środowisku. W ramach laboratoriów studenci konfrontują uzyskane wiadomości z praktyczną implementacją algorytmów rozproszonych, projektują i realizują algorytmy rozproszone w wybranym środowisku przetwarzania rozproszonego.

Sylabus

Autor sylabusa

  • Prof. dr hab. inż. Jerzy Brzeziński
  • E-mail: Jerzy.Brzeziński@put.poznan.pl

Autorzy kursu

  • Kurs został przygotowany przez zespół pracowników Instytutu Informatyki Politechniki Poznańskiej: prof. dr hab. inż. Jerzego Brzezińskiego, w składzie: dr inż. Michał Sajkowski, mgr inż. Jacek Kobusiński oraz mgr inż. Arkadiusz Danilecki.

Wymagania wstępne

  • Znajomość tematyki omawianej w ramach przedmiotu Systemy operacyjne
  • Podstawowe wiadomości z zakresu sieci komputerowych
  • Laboratoria wymagają znajomości języka C. Przygotowanie do pracy w omawianych środowiskach MPI oraz PVM wymaga podstawowych umiejętności związanych z konfiguracją i zarządzaniem systemu.

Zawartość

  • Wykłady:
  • Moduł 1 - Wprowadzenie (2 godz.). W ramach modułu dotyczącego wprowadzenia do przetwarzania rozproszonego prezentowane są następujące zagadnienia:

podstawowe definicje (węzły, łącza komunikacyjne i ich właściwości, topologia przetwarzania), charakterystyka środowiska przetwarzania rozproszonego, przykłady środowisk rozproszonych (Internet, GRID, projekty ..@Home takie jak Seti@Home czy CureCancer, Google).

  • Moduł 2 - Przetwarzanie rozproszone (2 godz.). W ramach modułu dotyczącego wprowadzenia do przetwarzania rozproszonego prezentowane są następujące zagadnienia: definicje (proces sekwencyjny, komunikaty, kanały komunikacyjne, stan kanału, operacje komunikacyjne (indywidualne i grupowe operacje komunikacyjne, komunikacja synchroniczna i asynchroniczna), model formalny procesu sekwencyjnego (stan procesu, funkcja tranzycji), zdarzenia (zdarzenia wysłania i odbioru, zdarzenia wewnętrzne, zdarzenia gotowe), warunki uaktywnienia (zbiór warunkujący, predykat ready, predykat activate), modele żądań (model jednostkowy, model AND, model OR, podstawowy model k spośród r, model OR-AND, dysjuncyjny model k spośród r, model predykatowy).
  • Moduł 3 -
  • Laboratoria:
  • Pierwszą część zajęć laboratoryjnych kursu stanowi dziewięć modułów (20 godz.) poświęconych implementacji algorytmów rozproszonych za pomocą biblioteki PVM. Pierwszym zagadnieniem poruszonym w ramach laboratoriów będzie przygotowanie środowiska PVM do pracy. Przedstawiona zostanie podstawowa funkcjonalność biblioteki PVM. W ramach ćwiczeń pokazane zostaną programy demonstrujące wybraną użyteczność biblioteki PVM, a także implementacje algorytmów wyliczania liczby Π metodą Monte-Carlo, łamania haseł, zegarów logicznych i detekcji zakończenia przetwarzania.
  • Drugą część zajęć laboratoryjnych kursu stanowią cztery moduły (10 godz.) przedstawiające alternatywne wobec PVM środowisko MPI. W ramach laboratorium przedstawiona zostanie instalacja i konfiguracja środowiska oraz wybrana część jego funkcjonalności.

Literatura

Literatura podstawowa

  1. Ben-Ari M. Podstawy programowania współbieżnego i rozproszonego, WNT, 1990
  2. Brzeziński J. Ocena stanu globalnego w systemach rozproszonych, OWN 2001
  3. Guerraoui R., Rodrigues L. Introduction to Reliable Distributed Programming, Springer-Verlag, 2006
  4. Lynch N. A. Distributed algorithms, Morgan Kaufmann Publishers, 1996
  5. Müllender S., ed. Distributed Systems, Addison-Wesley, 1993
  6. Tel G. Introduction to Distributed Algorithms, Cambridge University Press, 1994


Literatura uzupełniająca

  1. Attiya H., Welch J. Distributed computing. Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, 2004
  2. Chow R., Johnson T. Distributed Operating Systems & Algorithms, Addison Wesley Longman, 1997
  3. Garg K. V.: Principles of Distributed Systems, Kluwer Academic Publishers, 1996
  4. Raynal M. Distributed Algorithms and Protocols, John Wiley & Sons, 1988
  5. Sinha P. K.. Distributed Operating Systems. Concepts and Design, IEEE Computer Society Press, 1997
  6. Tanenbaum A. S.: Distributed Systems Principles and Paradigms, Prentice Hall 2002
  7. Tanenbaum A. S. Rozproszone Systemy Operacyjne, PWN, 1997

Moduły

Wykłady

  1. Wykład Wprowadzenie (pdf, pdf kolor, pdf notatki) / Laboratorium - Wprowadzenie do środowiska PVM (wersja pdf)
  2. Wykład Przetwarzanie rozproszone (pdf, pdf kolor,pdf notatki) / Laboratorium - Pierwsze kroki w PVM (wersja pdf)
  3. Wykład Proces rozproszony (pdf, pdf kolor,pdf notatki) / Laboratorium - Komunikacja między procesami (wersja pdf)
  4. Wykład Zegary logiczne, złożoność obliczeniowa (pdf,pdf kolor,pdf notatki) / Laboratorium - Zegary logiczne (wersja pdf)
  5. Wykład Detekcja zakleszczenia I (pdf,pdf kolor, pdf notatki) / Laboratorium - Komunikacja grupowa (wersja pdf)
  6. Wykład Detekcja zakleszczenia II (pdf,pdf kolor, pdf notatki) / Laboratorium - Obliczanie liczby Pi metodą montecarlo (wersja pdf)
  7. Wykład Konstrukcja spójnego obrazu stanu globalnego I (pdf,pdf kolor,pdf notatki) / Laboratorium - Łamanie haseł (wersja pdf)
  8. Wykład Konstrukcja spójnego obrazu stanu globalnego II (pdf, pdf kolor,pdf notatki) / Laboratorium - Zaawansowane operacje grupowe (wersja pdf)
  9. Wykład Detekcja zakończenia I (pdf, pdf kolor, pdf notatki) / Laboratorium - Detekcja zakończenia (wersja pdf)
  10. Wykład Detekcja zakończenia II (pdf, pdf kolor, pdf notatki) / Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Microsoft Windows (wersja pdf)
  11. Wykład Niezawodność przetwarzania (pdf, pdf kolor, pdf notatki) / Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Linux (wersja pdf)
  12. Wykład Niezawodne rozgłaszanie (pdf,pdf kolor,pdf notatki) / Laboratorium - Pierwsze kroki w środowisku MPI (wersja pdf)
  13. Wykład Problemy konsensusu (pdf,pdf kolor,pdf notatki) / Laboratorium - Komunikacja kolektywna w środowisku MPI (wersja pdf)

Tylko laboratoria:

  1. Laboratorium - Wprowadzenie do środowiska PVM (wersja pdf)
  2. Laboratorium - Pierwsze kroki w PVM (wersja pdf)
  3. Laboratorium - Komunikacja między procesami (wersja pdf)
  4. Laboratorium - Zegary logiczne (wersja pdf)
  5. Laboratorium - Komunikacja grupowa (wersja pdf)
  6. Laboratorium - Obliczanie liczby Pi metodą montecarlo (wersja pdf)
  7. Laboratorium - Łamanie haseł (wersja pdf)
  8. Laboratorium - Zaawansowane operacje grupowe (wersja pdf)
  9. Laboratorium - Detekcja zakończenia (wersja pdf)
  10. Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Microsoft Windows (wersja pdf)
  11. Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Linux (wersja pdf)
  12. Laboratorium - Pierwsze kroki w środowisku MPI (wersja pdf)
  13. Laboratorium - Komunikacja kolektywna w środowisku MPI (wersja pdf)
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Przetwarzanie_rozproszone&oldid=41842”