Przetwarzanie rozproszone
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
- Ben-Ari M. Podstawy programowania współbieżnego i rozproszonego, WNT, 1990
- Brzeziński J. Ocena stanu globalnego w systemach rozproszonych, OWN 2001
- Guerraoui R., Rodrigues L. Introduction to Reliable Distributed Programming, Springer-Verlag, 2006
- Lynch N. A. Distributed algorithms, Morgan Kaufmann Publishers, 1996
- Müllender S., ed. Distributed Systems, Addison-Wesley, 1993
- Tel G. Introduction to Distributed Algorithms, Cambridge University Press, 1994
Literatura uzupełniająca
- Attiya H., Welch J. Distributed computing. Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, 2004
- Chow R., Johnson T. Distributed Operating Systems & Algorithms, Addison Wesley Longman, 1997
- Garg K. V.: Principles of Distributed Systems, Kluwer Academic Publishers, 1996
- Raynal M. Distributed Algorithms and Protocols, John Wiley & Sons, 1988
- Sinha P. K.. Distributed Operating Systems. Concepts and Design, IEEE Computer Society Press, 1997
- Tanenbaum A. S.: Distributed Systems Principles and Paradigms, Prentice Hall 2002
- Tanenbaum A. S. Rozproszone Systemy Operacyjne, PWN, 1997
Moduły
Wykłady
- Wykład Wprowadzenie (pdf, pdf kolor, pdf notatki) / Laboratorium - Wprowadzenie do środowiska PVM (wersja pdf)
- Wykład Przetwarzanie rozproszone (pdf, pdf kolor,pdf notatki) / Laboratorium - Pierwsze kroki w PVM (wersja pdf)
- Wykład Proces rozproszony (pdf, pdf kolor,pdf notatki) / Laboratorium - Komunikacja między procesami (wersja pdf)
- Wykład Zegary logiczne, złożoność obliczeniowa (pdf,pdf kolor,pdf notatki) / Laboratorium - Zegary logiczne (wersja pdf)
- Wykład Detekcja zakleszczenia I (pdf,pdf kolor, pdf notatki) / Laboratorium - Komunikacja grupowa (wersja pdf)
- Wykład Detekcja zakleszczenia II (pdf,pdf kolor, pdf notatki) / Laboratorium - Obliczanie liczby Pi metodą montecarlo (wersja pdf)
- Wykład Konstrukcja spójnego obrazu stanu globalnego I (pdf,pdf kolor,pdf notatki) / Laboratorium - Łamanie haseł (wersja pdf)
- Wykład Konstrukcja spójnego obrazu stanu globalnego II (pdf, pdf kolor,pdf notatki) / Laboratorium - Zaawansowane operacje grupowe (wersja pdf)
- Wykład Detekcja zakończenia I (pdf, pdf kolor, pdf notatki) / Laboratorium - Detekcja zakończenia (wersja pdf)
- Wykład Detekcja zakończenia II (pdf, pdf kolor, pdf notatki) / Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Microsoft Windows (wersja pdf)
- Wykład Niezawodność przetwarzania (pdf, pdf kolor, pdf notatki) / Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Linux (wersja pdf)
- Wykład Niezawodne rozgłaszanie (pdf,pdf kolor,pdf notatki) / Laboratorium - Pierwsze kroki w środowisku MPI (wersja pdf)
- Wykład Problemy konsensusu (pdf,pdf kolor,pdf notatki) / Laboratorium - Komunikacja kolektywna w środowisku MPI (wersja pdf)
Tylko laboratoria:
- Laboratorium - Wprowadzenie do środowiska PVM (wersja pdf)
- Laboratorium - Pierwsze kroki w PVM (wersja pdf)
- Laboratorium - Komunikacja między procesami (wersja pdf)
- Laboratorium - Zegary logiczne (wersja pdf)
- Laboratorium - Komunikacja grupowa (wersja pdf)
- Laboratorium - Obliczanie liczby Pi metodą montecarlo (wersja pdf)
- Laboratorium - Łamanie haseł (wersja pdf)
- Laboratorium - Zaawansowane operacje grupowe (wersja pdf)
- Laboratorium - Detekcja zakończenia (wersja pdf)
- Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Microsoft Windows (wersja pdf)
- Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Linux (wersja pdf)
- Laboratorium - Pierwsze kroki w środowisku MPI (wersja pdf)
- Laboratorium - Komunikacja kolektywna w środowisku MPI (wersja pdf)
