Programowanie współbieżne i rozproszone w przykładach i zadaniach

Description

1. Wstęp.....................................................................................................................................9 2. Podstawowe pojęcia i problemy...........................................................................................13 2.1 Proces ............................................................................................................................13 2.2 Procesy współbieżne......................................................................................................13 2.2.1 Podział czasu...........................................................................................................14 2.2.2 Jednoczesność ........................................................................................................14 2.2.3 Komunikacja i synchronizacja ..................................................................................14 2.2.4 Program współbieżny...............................................................................................15 2.2.5 Wątki........................................................................................................................15 2.3 Wzajemne wykluczanie ..................................................................................................16 2.3.1 Zasób dzielony i sekcja krytyczna............................................................................16 2.3.2 Problem wzajemnego wykluczania ..........................................................................16 2.3.3 Wymagania czasowe ...............................................................................................17 2.4 Bezpieczeństwo i żywotność ..........................................................................................17 2.4.1 Własność bezpieczeństwa .......................................................................................17 2.4.2 Własność żywotności...............................................................................................18 2.4.3 Sprawiedliwość ........................................................................................................18 2.5 Blokada i zagłodzenie.....................................................................................................18 2.5.1 Blokada....................................................................................................................18 2.5.2 Zagłodzenie .............................................................................................................19 2.6 Klasyczne problemy współbieżności ..............................................................................20 2.6.1 Problem producenta i konsumenta ..........................................................................20 2.6.2 Problem czytelników i pisarzy ..................................................................................20 2.6.3 Problem pięciu filozofów ..........................................................................................21 2.7 Mechanizmy niskopoziomowe ........................................................................................22 2.7.1 Przerwania ...............................................................................................................23 2.7.2 Arbiter pamięci .........................................................................................................23 2.7.3 Instrukcje specjalne .................................................................................................24 2.8 Mechanizmy wysokopoziomowe ....................................................................................24 2.8.1 Mechanizmy synchronizacji .....................................................................................24 2.8.2 Mechanizmy komunikacji i synchronizacji................................................................26 2.8.3 Klasyfikacja ..............................................................................................................28 2.8.4 Rodzaje programów współbieżnych.........................................................................29 2.8.5 Notacja.....................................................................................................................31 3. Semafory ..........................................................................................................................32 3.1 Wprowadzenie................................................................................................................32 3.1.1 Semafor jako abstrakcyjny typ danych.....................................................................32 3.1.2 Semafor ogólny........................................................................................................32 3.1.3 Semafor binarny.......................................................................................................34 3.1.4 Rozszerzenia i modyfikacje .....................................................................................35 3.1.5 Ograniczenia............................................................................................................36 3.2 Przykłady........................................................................................................................37 3.2.1 Wzajemne wykluczanie............................................................................................37 3.2.2 Producenci i konsumenci .........................................................................................37 3.2.3 Czytelnicy i pisarze ..................................................................................................39 23.2.4 Pięciu filozofów ........................................................................................................41 3.3 Zadania ..........................................................................................................................42 3.3.1 Implementacja semafora ogólnego za pomocą binarnego.......................................42 3.3.2 Implementacja semafora dwustronnie ograniczonego .............................................42 3.3.3 Implementacja semafora uogólnionego ...................................................................42 3.3.4 Implementacja semafora typu AND .........................................................................42 3.3.5 Implementacja semafora typu OR............................................................................43 3.3.6 Dwa bufory...............................................................................................................43 3.3.7 Linia produkcyjna .....................................................................................................43 3.3.8 Przejazd przez wąski most ......................................................................................43 3.3.9 Gra w „łapki" ............................................................................................................43 3.3.10 Obliczanie symbolu Newtona.................................................................................44 3.3.11 Lotniskowiec ..........................................................................................................44 3.4 Rozwiązania ...................................................................................................................44 3.4.1 Implementacja semafora ogólnego za pomocą binarnego.......................................44 3.4.2 Implementacja semafora dwustronnie ograniczonego .............................................46 3.4.3 Implementacja semafora uogólnionego ...................................................................46 3.4.4 Implementacja semafora typu AND .........................................................................49 3.4.5 Implementacja semafora typu OR............................................................................52 3.4.6 Dwa bufory...............................................................................................................54 3.4.7 Linia produkcyjna .....................................................................................................55 3.4.8 Przejazd przez wąski most ......................................................................................56 3.4.9 Gra w „łapki" ............................................................................................................56 3.4.10 Obliczanie symbolu Newtona.................................................................................57 3.4.11 Lotniskowiec ..........................................................................................................58 4 Monitory ............................................................................................................................60 4.1 Wprowadzenie................................................................................................................60 4.1.1 Pojęcie monitora ......................................................................................................60 4.1.2 Ograniczenia............................................................................................................62 4.1.3 PascaLC ..................................................................................................................62 4.1.4 Concurrent Pascal ...................................................................................................63 4.1.5 Pascal Plus ..............................................................................................................64 4.1.6 Modula 2 ..................................................................................................................65 4.1.7 Modula 3 ..................................................................................................................66 4.1.8 Concurrent Euclid ....................................................................................................67 4.1.9 Zestawienie..............................................................................................................67 4.2 Przykłady........................................................................................................................68 4.2.1 Wzajemne wykluczanie............................................................................................68 4.2.2 Producenci i konsumenci .........................................................................................69 4.2.3 Czytelnicy i pisarze ..................................................................................................70 4.2.4 Pięciu filozofów ........................................................................................................71 4.3 Zadania ..........................................................................................................................73 4.3.1 Trzy grupy procesów................................................................................................73 4.3.2 Przetwarzanie potokowe..........................................................................................73 4.3.3 Producenci i konsumenci z losową wielkością wstawianych i pobieranych porcji....74 4.3.4 Producenci i konsumenci z asynchronicznym wstawianiem i pobieraniem..............74 4.3.5 Baza danych ............................................................................................................74 4.3.6 Prom jednokierunkowy............................................................................................75 4.3.7 Trzy drukarki ............................................................................................................75 4.3.8 Lotniskowiec ............................................................................................................75 34.3.9 Stolik dwuosobowy ..................................................................................................76 4.3.10 Zasoby dwóch typów ............................................................................................76 4.3.11 Algorytm bankiera .................................................................................................76 4.3.12 Rodzina procesów ................................................................................................77 4.3.13 Szeregowanie żądań do dysku .............................................................................78 4.3.14 Asynchroniczne wejście-wyjście ............................................................................78 4.3.15 Dyskowa pamięć podręczna ..................................................................................79 4.3.16 Pamięć operacyjna — strefy dynamiczne .............................................................79 4.3.17 Strategia buddy.....................................................................................................80 4.4 Rozwiązania ..................................................................................................................81 4.4.1 Trzy grupy procesów...............................................................................................81 4.4.2 Przetwarzanie potokowe.........................................................................................83 4.4.3 Producenci i konsumenci z losową wielkością wstawianych i pobieranych porcji ...83 4.4.4 Producenci i konsumenci z asynchronicznym wstawianiem i pobieraniem..............84 4.4.5 Baza danych ............................................................................................................86 4.4.6 Prom jednokierunkowy.............................................................................................89 4.4.7 Trzy drukarki ............................................................................................................90 4.4.8 Lotniskowiec ..........................................................................................................91 4.4.9 Stolik dwuosobowy .................................................................................................92 4.4.10 Zasoby dwóch typów ...........................................................................................93 4.4.11 Algorytm bankiera ................................................................................................94 4.4.12 Rodzina procesów ................................................................................................96 4.4.13 Szeregowanie żądań do dysku .............................................................................97 4.4.14 Asynchroniczne wejście-wyjście .........................................................................100 4.4.15 Dyskowa pamięć podręczna ...............................................................................101 4.4.16 Pamięć operacyjna — strefy dynamiczne ...........................................................103 4.4.17 Strategia buddy..................................................................................................105 5. Symetryczne spotkania .....................................................................................................108 5.1 Wprowadzenie............................................................................................................108 5.1.1 Trochę historii .......................................................................................................108 5.1.2 Struktura programu ..............................................................................................108 5.1.3 Instrukcje .............................................................................................................109 5.1.4 Spotkania.............................................................................................................110 5.1.5 Deklaracje .............................................................................................................111 5.1.6 Ograniczenia.........................................................................................................112 5.2 Przykłady.....................................................................................................................112 5.2.1 Wzajemne wykluczanie.........................................................................................112 5.2.2 Producent i konsument ........................................................................................117 5.2.3 Czytelnicy i pisarze ...............................................................................................118 5.2.4 Pięciu filozofów .....................................................................................................121 5.3 Zadania ......................................................................................................................122 5.3.1 Producent i konsument z rozproszonym buforem .................................................122 5.3.2 Powielanie plików..................................................................................................123 5.3.3 Problem podziału .................................................................................................123 5.3.4 Obliczanie histogramu ..........................................................................................124 5.3.5 Korygowanie logicznych zegarów .........................................................................124 5.3.6 Głosowanie ...........................................................................................................125 5.3.7 Komunikacja przez pośrednika ............................................................................126 5.3.8 Centrala telefoniczna ...........................................................................................126 5.3.9 Obliczanie iloczynu skalarnego............................................................................127 45.3.10 Obliczanie współczynników rozwinięcia dwumianu Newtona (a + b)n ..............127 5.3.11 Mnożenie macierzy przez wektor........................................................................127 5.3.12 Obliczanie wartości wielomianu .........................................................................128 5.3.13 Mnożenie wielomianów......................................................................................129 5.3.14 Sito Eratostenesa................................................................................................129 5.3.15 Sortowanie oscylacyjne .....................................................................................130 5.3.16 Tablica sortująca.................................................................................................131 5.3.17 Porównywanie ze wzorcem................................................................................131 5.4 Rozwiązania ...............................................................................................................132 5.4.1 Producent i konsument z rozproszonym buforem ................................................132 5.4.2 Powielanie plików..................................................................................................134 5.4.3 Problem podziału ..................................................................................................136 5.4.4 Obliczanie histogramu .........................................................................................137 5.4.5 Korygowanie logicznych zegarów ........................................................................138 5.4.6 Głosowanie ..........................................................................................................139 5.4.7 Komunikacja przez pośrednika ............................................................................140 5.4.8 Centrala telefoniczna ............................................................................................141 5.4.9 Obliczanie iloczynu skalarnego.............................................................................142 5.4.10 Obliczanie współczynników rozwinięcia dwumianu Newtona (n + b)n ...............143 5.4.11 Mnożenie macierzy przez wektor........................................................................144 5.4.12 Obliczanie wartości wielomianu .........................................................................144 5.4.13 Mnożenie wielomianów.......................................................................................146 5.4.14 Sito Eratostenesa...............................................................................................146 5.4.15 Sortowanie oscylacyjne .....................................................................................147 5.4.16 Tablica sortująca.................................................................................................148 5.4.17 Porównywanie ze wzorcem................................................................................148 5.5 Symetryczne spotkania w innych językach..................................................................149 5.5.1 occam ...................................................................................................................149 5.5.2 Parallel C ............................................................................................................152 5.5.3 Edip......................................................................................................................154 6 Asymetryczne spotkania w Adzie........................................................................................156 6.1 Wprowadzenie............................................................................................................156 6.1.1 Informacje ogólne ................................................................................................156 6.1.2 Deklaracje i instrukcje sterujące............................................................................156 6.1.3 Procedury i funkcje ..............................................................................................157 6.1.4 Pakiety ..................................................................................................................158 6.1.5 Procesy i wejścia ................................................................................................158 6.1. WPROWADZENIE .....................................................................................................159 6.1.6 Instrukcja accept ...................................................................................................159 6.1.7 Instrukcja select ....................................................................................................160 6.1.8 Atrybuty.................................................................................................................161 6.1.9 Ograniczenia.........................................................................................................162 6.2 Przykłady....................................................................................................................162 6.2.1 Wzajemne wykluczanie.........................................................................................162 6.2.2 Producent i konsument .........................................................................................163 6.2.3 Czytelnicy i pisarze ...............................................................................................165 6.2.4 Pięciu filozofów .....................................................................................................167 6.3 Zadania .......................................................................................................................169 6.3.1 Implementacja semafora dwustronnie ograniczonego ..........................................169 6.3.2 Implementacja semafora unixowego.....................................................................170 56.3.3 Implementacja monitora ograniczonego ...............................................................170 6.3.4 Zasoby dwóch typów ............................................................................................170 6.3.5 Szeregowanie żądań do dysku .............................................................................170 6.3.6 Algorytm Ricarta i Agrawali ...................................................................................170 6.3.7 Centrala telefoniczna ............................................................................................170 6.3.8 Sito Eratostenesa..................................................................................................171 6.4 Rozwiązania ................................................................................................................171 6.4.1 Implementacja semafora dwustronnie ograniczonego ..........................................171 6.4.2 Implementacja semafora unixowego.....................................................................172 6.4.3 Implementacja monitora ograniczonego ...............................................................174 6.4.4 Zasoby dwóch typów ............................................................................................174 6.4.5 Szeregowanie żądań do dysku ............................................................................175 6.4.6 Algorytm Ricarta i Agrawali ...................................................................................177 6.4.7 Centrala telefoniczna ...........................................................................................178 6.4.8 Sito Eratostenesa..................................................................................................180 7 Przestrzeń krotek w Lindzie ...............................................................................................182 7.1 Wprowadzenie............................................................................................................182 7.1.1 Przestrzeń krotek ..................................................................................................182 7.1.2 Operacja INPUT....................................................................................................182 7.1.3 Operacja OUTPUT................................................................................................183 7.1.4 Wybór selektywny ................................................................................................183 7.1.5 Operacja READ ....................................................................................................184 7.1.6 Ograniczenia.........................................................................................................184 7.2 Przykłady....................................................................................................................185 7.2.1 Wzajemne wykluczanie.........................................................................................185 7.2.2 Producenci i konsumenci ......................................................................................186 7.2.3 Czytelnicy i pisarze ..............................................................................................187 7.3 Zadania ......................................................................................................................191 7.3.1 Zasoby dwóch typów .............................................................................................191 7.3.2 Obliczanie histogramu ...........................................................................................191 7.3.3 Głosowanie ............................................................................................................191 7.3.4 Komunikacja przez pośrednika ..............................................................................192 7.3.5 Centrala telefoniczna ............................................................................................192 7.3.6 Mnożenie wielomianów..........................................................................................192 7.3.7 Mnożenie macierzy ................................................................................................192 7.3.8 Problem ośmiu hetmanów .....................................................................................192 7.3.9 Obliczanie całki oznaczonej...................................................................................193 7.4 Rozwiązania ................................................................................................................193 7.4.1 Zasoby dwóch typów .............................................................................................193 7.4.2 Obliczanie histogramu ...........................................................................................195 7.4.3 Głosowanie ...........................................................................................................197 7.4.4 Komunikacja przez pośrednika .............................................................................198 7.4.5 Centrala telefoniczna ............................................................................................198 7.4.6 Mnożenie wielomianów.........................................................................................199 7.4.7 Mnożenie macierzy ...............................................................................................201 7.4.8 Problem ośmiu hetmanów ....................................................................................202 7.4.9 Obliczanie całki oznaczonej...................................................................................204 8 Semafory w systemie Unix..................................................................................................206 8.1 Wprowadzenie..............................................................................................................206 8.1.1 Operacje semaforowe............................................................................................206 68.1.2 Jednoczesne operacje semaforowe......................................................................207 8.1.3 Funkcje na semaforach.........................................................................................207 8.1.4 Realizacja .............................................................................................................208 8.1.5 Ograniczenia.........................................................................................................210 8.2 Przykłady.....................................................................................................................211 8.2.1 Wzajemne wykluczanie.........................................................................................211 8.2.2 Producenci i konsumenci ......................................................................................212 8.2.3 Czytelnicy i pisarze ...............................................................................................213 8.2.4 Pięciu filozofów .....................................................................................................215 8.2.5 Implementacja monitora ograniczonego ...............................................................216 8.3 Zadania .......................................................................................................................218 8.3.1 Implementacja semafora binarnego......................................................................218 8.3.2 Implementacja semafora typu OR.........................................................................219 8.3.3 Czytelnicy i pisarze — rozwiązanie poprawne ......................................................219 8.3.4 Implementacja monitora ogólnego ........................................................................219 8.3.5 Zasoby dwóch typów ............................................................................................219 8.4 Rozwiązania ................................................................................................................219 8.4.1 Implementacja semafora binarnego......................................................................219 8.4.2 Implementacja semafora typu OR.........................................................................221 8.4.3 Czytelnicy i pisarze — rozwiązanie poprawne ......................................................223 8.4.4 Implementacja monitora ogólnego ........................................................................224 8.4.5 Zasoby dwóch typów ............................................................................................225 9 Komunikaty i kanały w systemie Unix ................................................................................227 9.1 Wprowadzenie.............................................................................................................227 9.1.1 Potoki i gniazda.....................................................................................................227 9.1.2 Kanały i podkanały................................................................................................228 9.1.3 Operacje na kanałach ...........................................................................................228 9.1.4 Realizacja .............................................................................................................229 9.1.5 Ograniczenia.........................................................................................................231 9.2 Przykłady.....................................................................................................................231 9.2.1 Wzajemne wykluczanie.........................................................................................231 9.2.2 Producenci i konsumenci ......................................................................................233 9.2.3 Czytelnicy i pisarze ...............................................................................................233 9.2.4 Implementacja monitora ograniczonego ...............................................................237 9.3 Zadania .......................................................................................................................238 9.3.1 Implementacja semafora typu OR........................................................................238 9.3.2 Implementacja monitora ogólnego ........................................................................238 9.3.3 Problem podziału ..................................................................................................238 9.3.4 Zasoby dwóch typów ............................................................................................238 9.3.5 Lotniskowiec .........................................................................................................238 9.3.6 Głosowanie ...........................................................................................................238 9.3.7 Komunikacja przez pośrednika .............................................................................239 9.4 Rozwiązania ................................................................................................................239 9.4.1 Implementacja semafora typu OR.........................................................................239 9.4.2 Implementacja monitora ogólnego ........................................................................239 9.4.3 Problem podziału .................................................................................................241 9.4.4 Zasoby dwóch typów ............................................................................................242 9.4.5 Lotniskowiec .........................................................................................................243 9.4.6 Głosowanie ...........................................................................................................245 9.4.7 Komunikacja przez pośrednika .............................................................................245 710 Zdalne wywołanie procedur w systemie Unix...................................................................247 10.1 Wprowadzenie...........................................................................................................247 10.1.1 Idea zdalnego wywołania procedury ...................................................................247 10.1.2 Reprezentacja danych ........................................................................................247 10.1.3 Proces obsługujący.............................................................................................248 10.1.4 Proces wołający ..................................................................................................250 10.1.5 Rozgłaszanie ......................................................................................................251 10.1.6 Ograniczenia.......................................................................................................253 10.2 Przykłady...................................................................................................................253 10.2.1 Wzajemne wykluczanie.......................................................................................254 10.3 Zadania .....................................................................................................................263 10.3.1 Problem podziału ................................................................................................263 10.3.2 Korygowanie logicznych zegarów .......................................................................263 10.3.3 Głosowanie .........................................................................................................263 10.3.4 Komunikacja przez pośrednika ...........................................................................263 10.3.5 Powielanie plików................................................................................................263 10.3.6 Powielanie plików - dostęp większościowy .........................................................263 10.3.7 Wyszukiwanie adresów.......................................................................................264 10.4 Rozwiązania ..............................................................................................................265 10.4.1 Problem podziału ................................................................................................265 10.4.2 Korygowanie logicznych zegarów .......................................................................266 10.4.3 Głosowanie .........................................................................................................267 10.4.4 Komunikacja przez pośrednika ...........................................................................268 10.4.5 Powielanie plików................................................................................................269 10.4.6 Powielanie plików - dostęp większościowy .........................................................272 10.4.7 Wyszukiwanie adresów.......................................................................................273 11 Potoki w systemie MS-DOS .............................................................................................276 11.1 Wprowadzenie...........................................................................................................276 11.2 Przykłady...................................................................................................................276 11.2.1 Producent i konsument .......................................................................................276 11.3 Zadania .....................................................................................................................277 11.3.1 Obliczanie histogramu ........................................................................................278 11.3.2 Obliczanie współczynników rozwinięcia dwumianu Newtona (a + b)n ................278 11.3.3 Obliczanie wartości wielomianu ..........................................................................278 11.3.4 Sito Eratostenesa................................................................................................278 11.3.5 Porównywanie ze wzorcem.................................................................................278 11.3.6 Problem ośmiu hetmanów ..................................................................................278 11.4 Rozwiązania ..............................................................................................................278 11.4.1 Obliczanie histogramu ........................................................................................279 11.4.2 Obliczanie współczynników rozwinięcia dwumianu Newtona (a + b)n ................279 11.4.3 Obliczanie wartości wielomianu ..........................................................................281 11.4.4 Sito Eratostenesa................................................................................................281 11.4.5 Porównywanie ze wzorcem.................................................................................282 11.4.6 Problem ośmiu hetmanów ..................................................................................283 Literatura................................................................................................................................285