Programowanie współbieżne i rozproszone

Forma zajęć

Wykład (30 godzin) + laboratorium/ćwiczenia (30 godzin)

Opis

Celem wykładu jest zaprezentowanie najważniejszych technik stosowanych do synchronizacji procesów i realizacji komunikacji między nimi oraz problemów, jakie stają przed programistą opracowującym programy współbieżne. Omówiony zostanie scentralizowany i rozproszony model programu współbieżnego. Problematyka zostanie przedstawiona na przykładzie klasycznych problemów współbieżności oraz procesów i wątków w systemie operacyjnym Linux. Przedstawione też będą klasyczne algorytmy rozproszone oraz zagadnienia związane z weryfikacją programów współbieżnych oraz notacje do opisu współbieżności.

Sylabus

Autor

• Marcin Engel — Uniwersytet Warszawski

Wymagania wstępne

• Wstęp do programowania
• Systemy operacyjne
• Środowisko programisty

Zawartość

• Klasyczne problemy współbieżności
• Mechanizmy synchronizacji procesów w modelu scentralizowanym i rozproszonym:
  • semafory
  • monitory
  • muteksy
  • spotkania (Ada)
• Procesy i wątki w systemie Linux i najważniejsze metody ich synchronizacji
• Algorytmy rozproszone: wzajemnego wykluczania, elekcji i uzgadniania
• Poprawność programów współbieżnych i jej weryfikacja
• Procesy i wątki w systemie Linux i najważniejsze metody ich synchronizacji
• Notacje do opisu współbieżności:
  • CSP
  • Sieci Petriego

Literatura

1. M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego. Wydawnictwa Naukowo-Techniczne, Warszawa 1996.
2. Z. Weiss, T. Gruźlewski, Programowanie współbieżne i rozproszone w przykładach i zadaniach. Wydawnictwa Naukowo-Techniczne, Warszawa 1993.
3. M. Rochkind, Programowanie w systemie Unix dla zaawansowanych. Wydawnictwa Naukowo-Techniczne, Warszawa 1997.
4. M.K. Johnson, E.W. Troan, Oprogramowanie użytkowe w systemie Linux. Wydawnictwa Naukowo-Techniczne, Warszawa2000.

Moduły

Moduły wykładowe

1. Wprowadzenie do programowania współbieżnego
2. Komunikacja asynchroniczna w modelu rozproszonym
3. Linda
4. Komunikacja synchroniczna na przykładzie Ady
5. Communicating Sequential Processes
6. CSP cd.
7. Algorytmy rozproszone: synchronizacja zegarów logicznych, wzajemne wykluczanie, elekcja
8. Rozproszony algorytm uzgadniania
9. Mechanizmy scentralizowane. Semafory
10. Semafory cd.
11. Monitory
12. Muteksy i inne mechanizmy synchronizacyjne
13. Specyfikowanie i weryfikacja własności programów współbieżnych. CTL

Moduły ćwiczeniowe

1. Ćwiczenia. Algorytm Petersona
2. Ćwiczenia. Tworzenie programów w modelu asynchronicznym
3. Ćwiczenia. Linda
4. Ćwiczenia. Ada
5. Ćwiczenia. CSP
6. Ćwiczenia. Semafory
7. Ćwiczenia. Monitory

Moduły laboratoryjne

1. Laboratorium. Procesy w systemie Linux
2. Laboratorium. Sygnały w Linuksie
3. Laboratorium. Łącza nienazwane
4. Laboratorium. IPC Kolejki komunikatów
5. Laboratorium. Algorytm Ricarta-Agrawali
6. Laboratorium. IPC. Semafory
7. Laboratorium. IPC. Segmenty pamięci dzielonej
8. Laboratorium. Wątki i muteksy w Linuksie