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

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