Tytuł oryginału: C++ Concurrency in Action: Practical Multithreading
Tłumaczenie: Mikołaj Szczepaniak
Projekt okładki: Anna Mitka
Materiały graficzne na okładce zostały wykorzystane za zgodą Shutterstock Images LLC.
ISBN: 978-83-246-5086-6
Original edition copyright © 2012 by Manning Publications Co.
All rights reserved.
Polish edition copyright © 2013 by HELION SA.
All rights reserved.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any
means, electronic or mechanical, including photocopying, recording or by any information storage
retrieval system, without permission from the Publisher.
Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej
publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną,
fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje
naruszenie praw autorskich niniejszej publikacji.
Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich
właścicieli.
Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte
w tej książce informacje były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za
ich wykorzystanie, ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich.
Autor oraz Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne
szkody wynikłe z wykorzystania informacji zawartych w książce.
Wydawnictwo HELION
ul. Kościuszki 1c, 44-100 GLIWICE
tel. 32 231 22 19, 32 230 98 63
e-mail: helion@helion.pl
WWW: http://helion.pl (księgarnia internetowa, katalog książek)
Drogi Czytelniku!
Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres
http://helion.pl/user/opinie?gimpbi
Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.
Printed in Poland.
Spis treci
Sowo wstpne .......................................................................................................................................... 11
Podzikowania .......................................................................................................................................... 13
O tej ksice .............................................................................................................................................. 15
Rozdzia 1. Witaj, wiecie wspóbienoci w C++!
19
1.1.
Czym jest wspóbieno? ........................................................................................................... 20
1.1.1. Wspóbieno w systemach komputerowych ................................................................. 20
1.1.2. Modele wspóbienoci ..................................................................................................... 22
1.2.
Dlaczego warto stosowa wspóbieno? ................................................................................. 25
1.2.1. Stosowanie wspóbienoci do podziau zagadnie ......................................................... 25
1.2.2. Stosowanie wspóbienoci do podniesienia wydajnoci ................................................. 26
1.2.3. Kiedy nie naley stosowa wspóbienoci ....................................................................... 27
1.3.
Wspóbieno i wielowtkowo w jzyku C++ .................................................................... 28
1.3.1. Historia przetwarzania wielowtkowego w jzyku C++ ................................................ 29
1.3.2. Obsuga wspóbienoci w nowym standardzie ............................................................... 30
1.3.3. Efektywno biblioteki wtków jzyka C++ .................................................................. 30
1.3.4. Mechanizmy zwizane z poszczególnymi platformami ................................................... 32
1.4. Do
dziea!
...................................................................................................................................... 32
1.4.1. „Witaj wiecie wspóbienoci” ......................................................................................... 32
1.5. Podsumowanie
.............................................................................................................................. 34
Rozdzia 2. Zarzdzanie wtkami
35
2.1. Podstawowe
zarzdzanie
wtkami
............................................................................................. 36
2.1.1 Uruchamianie
wtku .......................................................................................................... 36
2.1.2. Oczekiwanie na zakoczenie wtku .................................................................................. 39
2.1.3. Oczekiwanie w razie wystpienia wyjtku ....................................................................... 39
2.1.4. Uruchamianie wtków w tle .............................................................................................. 42
2.2. Przekazywanie
argumentów
do funkcji wtku ......................................................................... 43
2.3. Przenoszenie
wasnoci wtku .................................................................................................... 46
2.4.
Wybór liczby wtków w czasie wykonywania ........................................................................... 49
2.5. Identyfikowanie
wtków
............................................................................................................. 52
2.6. Podsumowanie
.............................................................................................................................. 54
Rozdzia 3. Wspódzielenie danych przez wtki
55
3.1.
Problemy zwizane ze wspódzieleniem danych przez wtki ................................................. 56
3.1.1. Sytuacja wycigu ................................................................................................................ 58
3.1.2. Unikanie problematycznych sytuacji wycigu .................................................................. 59
3.2. Ochrona
wspódzielonych
danych
za pomoc muteksów ........................................................ 60
3.2.1. Stosowanie muteksów w jzyku C++ ............................................................................. 60
3.2.2. Projektowanie struktury kodu z myl o ochronie wspódzielonych danych ................. 62
Kup książkę
Poleć książkę
6
Spis treci
3.2.3. Wykrywanie sytuacji wycigu zwizanych z interfejsami ................................................ 63
3.2.4. Zakleszczenie: problem i rozwizanie .............................................................................. 71
3.2.5. Dodatkowe wskazówki dotyczce unikania zakleszcze ................................................. 73
3.2.6. Elastyczne blokowanie muteksów za pomoc szablonu std::unique_lock ...................... 79
3.2.7. Przenoszenie wasnoci muteksu pomidzy zasigami .................................................... 80
3.2.8. Dobór waciwej szczegóowoci blokad .......................................................................... 82
3.3.
Alternatywne mechanizmy ochrony wspódzielonych danych ................................................ 84
3.3.1. Ochrona wspódzielonych danych podczas inicjalizacji .................................................. 84
3.3.2. Ochrona rzadko aktualizowanych struktur danych .......................................................... 88
3.3.3. Blokowanie rekurencyjne .................................................................................................. 90
3.4. Podsumowanie
.............................................................................................................................. 91
Rozdzia 4. Synchronizacja wspóbienych operacji
93
4.1.
Oczekiwanie na zdarzenie lub inny warunek ........................................................................... 94
4.1.1. Oczekiwanie na spenienie warunku za pomoc zmiennych warunkowych .................. 95
4.1.2. Budowa kolejki gwarantujcej bezpieczne przetwarzanie wielowtkowe
przy uyciu zmiennych warunkowych .............................................................................. 97
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci ........................................... 102
4.2.1. Zwracanie wartoci przez zadania wykonywane w tle ................................................... 103
4.2.2. Wizanie zadania z przyszoci ...................................................................................... 106
4.2.3. Obietnice (szablon std::promise) ..................................................................................... 109
4.2.4. Zapisywanie wyjtku na potrzeby przyszoci ................................................................ 111
4.2.5. Oczekiwanie na wiele wtków ........................................................................................ 112
4.3. Oczekiwanie
z
limitem
czasowym
............................................................................................ 115
4.3.1. Zegary ............................................................................................................................... 115
4.3.2. Okresy ............................................................................................................................... 117
4.3.3. Punkty w czasie ................................................................................................................ 118
4.3.4. Funkcje otrzymujce limity czasowe .............................................................................. 120
4.4.
Upraszczanie kodu za pomoc technik synchronizowania operacji ..................................... 121
4.4.1. Programowanie funkcyjne przy uyciu przyszoci ....................................................... 122
4.4.2. Synchronizacja operacji za pomoc przesyania komunikatów ..................................... 127
4.5. Podsumowanie
............................................................................................................................ 131
Rozdzia 5. Model pamici jzyka C++ i operacje na typach atomowych
133
5.1.
Podstawowe elementy modelu pamici ................................................................................... 134
5.1.1. Obiekty i miejsca w pamici ............................................................................................ 134
5.1.2. Obiekty, miejsca w pamici i przetwarzanie wspóbiene ............................................ 135
5.1.3. Kolejno modyfikacji ...................................................................................................... 136
5.2.
Operacje i typy atomowe jzyka C++ .................................................................................... 137
5.2.1. Standardowe typy atomowe ............................................................................................ 138
5.2.2. Operacje na typie std::atomic_flag .................................................................................. 141
5.2.3. Operacje na typie std::atomic<bool> ............................................................................ 143
5.2.4. Operacje na typie std::atomic<T*> — arytmetyka wskaników ................................. 146
5.2.5. Operacje na standardowych atomowych typach cakowitoliczbowych ........................ 147
5.2.6. Gówny szablon klasy std::atomic<> ............................................................................. 147
5.2.7. Wolne funkcje dla operacji atomowych .......................................................................... 150
5.3.
Synchronizacja operacji i wymuszanie ich porzdku ............................................................ 151
5.3.1. Relacja synchronizacji ...................................................................................................... 152
5.3.2. Relacja poprzedzania ....................................................................................................... 154
5.3.3. Porzdkowanie pamici na potrzeby operacji atomowych ............................................ 155
5.3.4. Sekwencje zwalniania i relacja synchronizacji ............................................................... 175
Poleć książkę
Kup książkę
Spis treci
7
5.3.5. Ogrodzenia ....................................................................................................................... 178
5.3.6. Porzdkowanie operacji nieatomowych za pomoc operacji atomowych ..................... 180
5.4. Podsumowanie
............................................................................................................................ 182
Rozdzia 6. Projektowanie wspóbienych struktur danych przy uyciu blokad
183
6.1.
Co oznacza projektowanie struktur danych pod ktem wspóbienoci? ............................ 184
6.1.1. Wskazówki dotyczce projektowania wspóbienych struktur danych ........................ 185
6.2.
Projektowanie wspóbienych struktur danych przy uyciu blokad .................................... 186
6.2.1. Stos gwarantujcy bezpieczestwo przetwarzania wielowtkowego
przy uyciu blokad ........................................................................................................... 187
6.2.2. Kolejka gwarantujca bezpieczestwo przetwarzania wielowtkowego
przy uyciu blokad i zmiennych warunkowych ............................................................. 190
6.2.3. Kolejka gwarantujca bezpieczestwo przetwarzania wielowtkowego
przy uyciu szczegóowych blokad i zmiennych warunkowych .................................... 194
6.3.
Projektowanie zoonych struktur danych przy uyciu blokad ............................................. 207
6.3.1. Implementacja tablicy wyszukiwania gwarantujcej bezpieczestwo
przetwarzania wielowtkowego przy uyciu blokad ...................................................... 207
6.3.2. Implementacja listy gwarantujcej bezpieczestwo przetwarzania
wielowtkowego przy uyciu blokad .............................................................................. 213
6.4. Podsumowanie
............................................................................................................................ 218
Rozdzia 7. Projektowanie wspóbienych struktur danych bez blokad
219
7.1.
Definicje i ich praktyczne znaczenie ....................................................................................... 220
7.1.1. Rodzaje nieblokujcych struktur danych ........................................................................ 220
7.1.2. Struktury danych bez blokad ........................................................................................... 221
7.1.3. Struktury danych bez oczekiwania ................................................................................. 222
7.1.4. Zalety i wady struktur danych bez blokad ...................................................................... 222
7.2.
Przykady struktur danych bez blokad .................................................................................... 223
7.2.1. Implementacja stosu gwarantujcego bezpieczestwo przetwarzania
wielowtkowego bez blokad ............................................................................................ 224
7.2.2. Eliminowanie niebezpiecznych wycieków — zarzdzanie pamici
w strukturach danych bez blokad .................................................................................... 228
7.2.3. Wykrywanie wzów, których nie mona odzyska, za pomoc wskaników ryzyka ........ 233
7.2.4. Wykrywanie uywanych wzów metod zliczania referencji .......................................... 242
7.2.5. Zmiana modelu pamici uywanego przez operacje na stosie bez blokad ................... 247
7.2.6. Implementacja kolejki gwarantujcej bezpieczestwo przetwarzania
wielowtkowego bez blokad ............................................................................................ 252
7.3.
Wskazówki dotyczce pisania struktur danych bez blokad ................................................... 264
7.3.1. Wskazówka: na etapie tworzenia prototypu naley stosowa tryb
std::memory_order_seq_cst ............................................................................................ 265
7.3.2. Wskazówka: naley uywa schematu odzyskiwania pamici bez blokad .................... 265
7.3.3 Wskazówka: naley unika problemu ABA .................................................................... 266
7.3.4. Wskazówka: naley identyfikowa ptle aktywnego oczekiwania i wykorzystywa
czas bezczynnoci na wspieranie innego wtku ............................................................. 267
7.4. Podsumowanie
............................................................................................................................ 267
Rozdzia 8. Projektowanie wspóbienego kodu
269
8.1.
Techniki dzielenia pracy pomidzy wtki ............................................................................... 270
8.1.1. Dzielenie danych pomidzy wtki przed rozpoczciem przetwarzania ....................... 271
8.1.2. Rekurencyjne dzielenie danych ...................................................................................... 272
8.1.3. Dzielenie pracy wedug typu zadania ............................................................................. 276
Poleć książkę
Kup książkę
8
Spis treci
8.2.
Czynniki wpywajce na wydajno wspóbienego kodu ..................................................... 279
8.2.1. Liczba procesorów ........................................................................................................... 280
8.2.2. Wspózawodnictwo o dane i ping-pong bufora .............................................................. 281
8.2.3. Faszywe wspódzielenie ................................................................................................. 284
8.2.4. Jak blisko naley rozmieci dane? ................................................................................. 285
8.2.5. Nadsubskrypcja i zbyt intensywne przeczanie zada ................................................. 285
8.3.
Projektowanie struktur danych pod ktem wydajnoci przetwarzania wielowtkowego ..... 286
8.3.1. Podzia elementów tablicy na potrzeby zoonych operacji .......................................... 287
8.3.2. Wzorce dostpu do danych w pozostaych strukturach ................................................. 289
8.4.
Dodatkowe aspekty projektowania wspóbienych struktur danych ................................... 291
8.4.1. Bezpieczestwo wyjtków w algorytmach równolegych .............................................. 291
8.4.2. Skalowalno i prawo Amdahla ....................................................................................... 298
8.4.3. Ukrywanie opónie za pomoc wielu wtków .............................................................. 300
8.4.4. Skracanie czasu reakcji za pomoc technik przetwarzania równolegego .................... 301
8.5.
Projektowanie wspóbienego kodu w praktyce ..................................................................... 303
8.5.1. Równolega implementacja funkcji std::for_each ........................................................... 304
8.5.2. Równolega implementacja funkcji std::find .................................................................. 306
8.5.3. Równolega implementacja funkcji std::partial_sum ..................................................... 312
8.6. Podsumowanie
............................................................................................................................ 322
Rozdzia 9. Zaawansowane zarzdzanie wtkami
323
9.1. Pule
wtków
................................................................................................................................ 324
9.1.1. Najprostsza moliwa pula wtków .................................................................................. 324
9.1.2. Oczekiwanie na zadania wysyane do puli wtków ........................................................ 327
9.1.3. Zadania oczekujce na inne zadania ............................................................................... 330
9.1.4. Unikanie wspózawodnictwa w dostpie do kolejki zada ............................................ 333
9.1.5. Wykradanie zada ............................................................................................................ 335
9.2. Przerywanie
wykonywania
wtków .......................................................................................... 340
9.2.1. Uruchamianie i przerywanie innego wtku .................................................................... 340
9.2.2. Wykrywanie przerwania wtku ....................................................................................... 342
9.2.3. Przerywanie oczekiwania na zmienn warunkow ........................................................ 343
9.2.4. Przerywanie oczekiwania na zmienn typu std::condition_variable_any ..................... 346
9.2.5. Przerywanie pozostaych wywoa blokujcych ............................................................ 348
9.2.6. Obsuga przerwa ............................................................................................................ 349
9.2.7. Przerywanie zada wykonywanych w tle podczas zamykania aplikacji ........................ 350
9.3. Podsumowanie
............................................................................................................................ 352
Rozdzia 10. Testowanie i debugowanie aplikacji wielowtkowych
353
10.1. Rodzaje bdów zwizanych z przetwarzaniem wspóbienym ............................................ 354
10.1.1. Niechciane
blokowanie
............................................................................................... 354
10.1.2. Sytuacje
wycigu
......................................................................................................... 355
10.2. Techniki
lokalizacji
bdów
zwizanych
z przetwarzaniem wspóbienym ........................ 357
10.2.1.
Przegldanie kodu w celu znalezienia ewentualnych bdów .................................. 357
10.2.2.
Znajdowanie bdów zwizanych z przetwarzaniem wspóbienym
poprzez testowanie kodu ................................................................................................. 359
10.2.3.
Projektowanie kodu pod ktem atwoci testowania ................................................. 361
10.2.4.
Techniki testowania wielowtkowego kodu .............................................................. 363
10.2.5.
Projektowanie struktury wielowtkowego kodu testowego ...................................... 366
10.2.6. Testowanie
wydajnoci
wielowtkowego kodu ......................................................... 369
10.3. Podsumowanie
............................................................................................................................ 370
Poleć książkę
Kup książkę
Spis treci
9
Dodatek A Krótki przegld wybranych elementów jzyka C++11
371
A.1. Referencje do r-wartoci ........................................................................................................... 371
A.1.1. Semantyka przenoszenia danych ..................................................................................... 372
A.1.2. Referencje do r-wartoci i szablony funkcji .................................................................... 375
A.2. Usunite
funkcje
......................................................................................................................... 376
A.3. Funkcje
domylne
...................................................................................................................... 377
A.4. Funkcje
constexpr
...................................................................................................................... 381
A.4.1. Wyraenia constexpr i typy definiowane przez uytkownika ........................................ 382
A.4.2. Obiekty constexpr ............................................................................................................ 385
A.4.3. Wymagania dotyczce funkcji constexpr ........................................................................ 385
A.4.4. Sowo constexpr i szablony .............................................................................................. 386
A.5. Funkcje
lambda
.......................................................................................................................... 386
A.5.1. Funkcje lambda odwoujce si do zmiennych lokalnych ............................................. 388
A.6. Szablony
zmiennoargumentowe
............................................................................................... 391
A.6.1. Rozwijanie paczki parametrów ....................................................................................... 392
A.7. Automatyczne okrelanie typu zmiennej ................................................................................. 395
A.8. Zmienne lokalne wtków ........................................................................................................... 396
A.9. Podsumowanie
............................................................................................................................ 397
Dodatek B Krótkie zestawienie bibliotek przetwarzania wspóbienego
399
Dodatek C Framework przekazywania komunikatów i kompletny przykad
implementacji systemu bankomatu
401
Dodatek D Biblioteka wtków jzyka C++
419
D.1. Nagówek
<chrono>
................................................................................................................. 419
D.1.1.
Szablon klasy std::chrono::duration ............................................................................ 420
D.1.2.
Szablon klasy std::chrono::time_point ....................................................................... 429
D.1.3. Klasa
std::chrono::system_clock
................................................................................. 431
D.1.4. Klasa
std::chrono::steady_clock
.................................................................................. 433
D.1.5.
Definicja typu std::chrono::high_resolution_clock ................................................... 435
D.2. Nagówek
<condition_variable>
............................................................................................ 435
D.2.1. Klasa
std::condition_variable
...................................................................................... 436
D.2.2. Klasa
std::condition_variable_any
.............................................................................. 444
D.3. Nagówek
<atomic>
................................................................................................................. 452
D.3.1. Definicje
typów
std::atomic_xxx
................................................................................ 454
D.3.2. Makra
ATOMIC_xxx_LOCK_FREE
........................................................................ 454
D.3.3. Makro
ATOMIC_VAR_INIT
..................................................................................... 455
D.3.4. Typ
wyliczeniowy
std::memory_order
....................................................................... 455
D.3.5. Funkcja
std::atomic_thread_fence
............................................................................. 456
D.3.6. Funkcja
std::atomic_signal_fence
.............................................................................. 457
D.3.7. Klasa
std::atomic_flag
.................................................................................................. 457
D.3.8.
Szablon klasy std::atomic ............................................................................................ 460
D.3.9. Specjalizacje
szablonu
std::atomic
............................................................................. 471
D.3.10. Specjalizacje szablonu std::atomic<typ-cakowitoliczbowy> ................................. 472
D.4. Nagówek
<future>
.................................................................................................................. 489
D.4.1.
Szablon klasy std::future ............................................................................................. 490
D.4.2.
Szablon klasy std::shared_future ................................................................................ 495
D.4.3.
Szablon klasy std::packaged_task ............................................................................... 501
D.4.4.
Szablon klasy std::promise .......................................................................................... 507
D.4.5.
Szablon funkcji std::async ........................................................................................... 513
Poleć książkę
Kup książkę
10
Spis treci
D.5. Nagówek
<mutex>
.................................................................................................................. 514
D.5.1. Klasa
std::mutex
.......................................................................................................... 515
D.5.2. Klasa
std::recursive_mutex
......................................................................................... 518
D.5.3. Klasa
std::timed_mutex
............................................................................................... 520
D.5.4. Klasa
std::recursive_timed_mutex
............................................................................. 524
D.5.5.
Szablon klasy std::lock_guard ..................................................................................... 529
D.5.6.
Szablon klasy std::unique_lock ................................................................................... 530
D.5.7.
Szablon funkcji std::lock ............................................................................................. 540
D.5.8.
Szablon funkcji std::try_lock ....................................................................................... 541
D.5.9. Klasa
std::once_flag
..................................................................................................... 541
D.5.10. Szablon funkcji std::call_once .................................................................................... 542
D.6. Nagówek
<ratio>
..................................................................................................................... 543
D.6.1.
Szablon klasy std::ratio ................................................................................................ 544
D.6.2. Alias
szablonu
std::ratio_add
...................................................................................... 544
D.6.3. Alias
szablonu
std::ratio_subtract
............................................................................... 545
D.6.4. Alias
szablonu
std::ratio_multiply
.............................................................................. 545
D.6.5. Alias
szablonu
std::ratio_divide
.................................................................................. 546
D.6.6.
Szablon klasy std::ratio_equal ..................................................................................... 547
D.6.7.
Szablon klasy std::ratio_not_equal ............................................................................. 547
D.6.8.
Szablon klasy std::ratio_less ........................................................................................ 547
D.6.9.
Szablon klasy std::ratio_greater .................................................................................. 548
D.6.10. Szablon klasy std::ratio_less_equal ............................................................................ 548
D.6.11. Szablon klasy std::ratio_greater_equal ....................................................................... 548
D.7. Nagówek
<thread>
................................................................................................................. 549
D.7.1. Klasa
std::thread
.......................................................................................................... 549
D.7.2.
Przestrze nazw std::this_thread ................................................................................ 558
Materiay dodatkowe
561
Skorowidz 563
Poleć książkę
Kup książkę
Synchronizacja
wspóbienych operacji
W tym rozdziale zostan omówione
nastpujce zagadnienia:
Q
oczekiwanie na zdarzenie;
Q
oczekiwanie na jednorazowe zdarzenia za pomoc
przyszoci;
Q
oczekiwanie z limitem czasowym;
Q
upraszczanie kodu za pomoc technik
synchronizowania operacji.
W poprzednim rozdziale przeanalizowalimy rozmaite sposoby ochrony danych wspó-
dzielonych przez wiele wtków. Okazuje si jednak, e w pewnych przypadkach jest
potrzebna nie tyle ochrona danych, co synchronizacja dziaa podejmowanych przez
róne wtki. Wtek moe na przykad czeka z realizacj wasnej operacji na zako-
czenie pewnego zadania przez inny wtek. Ogólnie w wielu przypadkach wtek oczeku-
jcy na okrelone zdarzenie lub spenienie pewnego warunku jest najwygodniejszym
rozwizaniem. Mimo e analogiczne rozwizanie mona zaimplementowa w formie
mechanizmu okresowego sprawdzania flagi zakoczonego zadania lub innej wartoci
zapisanej we wspódzielonych danych, taki model byby daleki od ideau. Konieczno
synchronizacji operacji wykonywanych przez róne wtki jest do typowym scena-
riuszem, zatem biblioteka standardowa jzyka C++ oferuje mechanizmy uatwiajce
obsug tego modelu, w tym zmienne warunkowe i tzw. przyszoci.
W tym rozdziale omówi techniki oczekiwania na zdarzenia przy uyciu zmiennych
warunkowych oraz sposoby upraszczania synchronizacji operacji za pomoc przyszoci.
Poleć książkę
Kup książkę
94
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
4.1.
Oczekiwanie na zdarzenie lub inny warunek
Przypumy, e podróujemy nocnym pocigiem. Jednym ze sposobów zagwaranto-
wania, e wysidziemy na waciwej stacji, jest unikanie snu i sprawdzanie wszystkich
stacji, na których zatrzymuje si nasz pocig. W ten sposób nie przegapimy naszej stacji,
jednak po dotarciu na miejsce bdziemy bardzo zmczeni. Alternatywnym rozwiza-
niem jest sprawdzenie rozkadu jazdy pod ktem godziny przyjazdu, ustawienie budzika
z pewnym wyprzedzeniem wzgldem tej godziny i pójcie spa. To rozwizanie jest
do bezpieczne — nie przegapimy naszej stacji, ale jeli pocig si spóni, wstaniemy
zbyt wczenie. Nie mona te wykluczy sytuacji, w której wyczerpi si baterie
w budziku — w takim przypadku moemy zaspa i przegapi swoj stacj. Idealnym
rozwizaniem byaby moliwo pójcia spa i skorzystania z pomocy czego (lub kogo),
co obudzioby nas bezporednio przed osigniciem stacji docelowej.
Jaki to ma zwizek z wtkami? Jeli jeden wtek czeka, a inny wtek zakoczy jakie
zadanie, ma do wyboru kilka moliwych rozwiza. Po pierwsze, moe stale spraw-
dza odpowiedni flag we wspódzielonych danych (chronionych przez muteks); flaga
zostanie ustawiona przez drugi wtek w momencie zakoczenia zadania. Takie rozwi-
zanie jest nieefektywne z dwóch powodów: wtek, który wielokrotnie sprawdza wspo-
mnian flag, zajmuje cenny czas procesora, a muteks zablokowany przez oczekujcy
wtek nie jest dostpny dla adnego innego wtku. Oba te czynniki dziaaj na nieko-
rzy oczekujcego wtku, poniewa ten wtek zajmuje zasoby potrzebne take do
dziaania wtku, na który czeka, co opónia wykonanie zadania i ustawienie odpowied-
niej flagi. Sytuacja przypomina unikanie snu przez ca podró pocigiem i prowadze-
nie rozmowy z maszynist — maszynista zajty rozmow musi prowadzi pocig nieco
wolniej, zatem póniej dotrzemy na swoj stacj. Podobnie wtek oczekujcy zajmuje
zasoby, które mogyby by uywane przez pozostae wtki w systemie, przez co czas
oczekiwania moe by duszy, ni to konieczne.
Druga opcja polega na przechodzeniu wtku oczekujcego w stan upienia na
krótkie momenty i okresowym wykonywaniu testów za pomoc funkcji
std::this_
´
thread::sleep_for()
(patrz punkt 4.3):
bool flag;
std::mutex m;
void wait_for_flag()
{
std::unique_lock<std::mutex> lk(m);
while(!flag)
{
lk.unlock();
Odblokowuje muteks
std::this_thread::sleep_for(std::chrono::milliseconds(100));
Czeka 100 ms
lk.lock();
Ponownie blokuje muteks
}
}
Wywoanie funkcji w ptli odblokowuje muteks przed przejciem w stan upienia
i ponownie blokuje ten muteks po wyjciu z tego stanu — dziki temu drugi wtek
ma szanse uzyskania dostpu do flagi i jej ustawienia.
Opisane rozwizanie jest o tyle dobre, e upiony wtek nie zajmuje bezproduk-
tywnie czasu procesora. Warto jednak pamita, e dobór waciwego czasu upienia
Poleć książkę
Kup książkę
4.1.
Oczekiwanie na zdarzenie lub inny warunek
95
jest do trudny. Zbyt krótki czas przebywania w tym stanie spowoduje, e wtek bdzie
traci czas procesora na zbyt czste testy; zbyt dugi czas upienia bdzie oznacza, e
wtek bdzie przebywa w tym stanie nawet po zakoczeniu zadania, na które oczekuje,
zatem opónienie w dziaaniu wtku oczekujcego bdzie zbyt due. Takie „zaspanie”
wtku rzadko ma bezporedni wpyw na wynik operacji wykonywanych przez program,
ale ju w przypadku szybkiej gry moe powodowa pominicie niektórych klatek
animacji, a w przypadku aplikacji czasu rzeczywistego moe oznacza pominicie
przydziau czasu procesora.
Trzecim, najlepszym rozwizaniem jest uycie gotowych elementów biblioteki stan-
dardowej jzyka C++ umoliwiajcych oczekiwanie na okrelone zdarzenie. Najprost-
szym mechanizmem oczekiwania na zdarzenie generowane przez inny wtek (na przy-
kad zdarzenie polegajce na umieszczeniu dodatkowego zadania w potoku) jest tzw.
zmienna warunkowa. Zmienna warunkowa jest powizana z pewnym zdarzeniem lub
warunkiem oraz co najmniej jednym wtkiem, który czeka na spenienie tego warunku.
Wtek, który odkrywa, e warunek jest speniony, moe powiadomi pozostae wtki
oczekujce na t zmienn warunkow, aby je obudzi i umoliwi im dalsze przetwarzanie.
4.1.1.
Oczekiwanie na spenienie warunku
za pomoc zmiennych warunkowych
Biblioteka standardowa jzyka C++ udostpnia dwie implementacje mechanizmu
zmiennych warunkowych w formie klas
std::condition_variable
i
std::condition_
´
variable_any
. Obie klasy zostay zadeklarowane w pliku nagówkowym
<condition_
´
variable>
. W obu przypadkach zapewnienie waciwej synchronizacji wymaga uy-
cia muteksu — pierwsza klasa jest przystosowana tylko do obsugi muteksów typu
std::mutex
, natomiast druga klasa obsuguje wszystkie rodzaje muteksów speniajcych
pewien minimalny zbiór kryteriów (std przyrostek
_any
). Poniewa klasa
std::condition_
´
variable_any
jest bardziej uniwersalna, z jej stosowaniem wi si dodatkowe
koszty w wymiarze wielkoci, wydajnoci i zasobów systemu operacyjnego. Jeli wic
nie potrzebujemy dodatkowej elastycznoci, powinnimy stosowa klas
std::condition_
´
variable
.
Jak naleaoby uy klasy
std::condition_variable
do obsugi przykadu opisanego
na pocztku tego podrozdziau — jak sprawi, e wtek oczekujcy na wykonanie jakie-
go zadania bdzie upiony do momentu, w którym bd dostpne dane do przetwo-
rzenia? Na listingu 4.1 pokazano przykad kodu implementujcego odpowiednie roz-
wizanie przy uyciu zmiennej warunkowej.
Listing 4.1. Oczekiwanie na dane do przetworzenia za pomoc klasy
std::condition_variable
std::mutex mut;
std::queue<data_chunk> data_queue;
std::condition_variable data_cond;
void data_preparation_thread()
{
while(more_data_to_prepare())
{
data_chunk const data=prepare_data();
Poleć książkę
Kup książkę
96
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
std::lock_guard<std::mutex> lk(mut);
data_queue.push(data);
data_cond.notify_one();
}
}
void data_processing_thread()
{
while(true)
{
std::unique_lock<std::mutex> lk(mut);
data_cond.wait(
lk,[]{return !data_queue.empty();});
data_chunk data=data_queue.front();
data_queue.pop();
lk.unlock();
process(data);
if(is_last_chunk(data))
break;
}
}
Na pocztku kodu zdefiniowano kolejk , która bdzie uywana do przekazywania
danych pomidzy dwoma wtkami. Kiedy dane s gotowe do przetworzenia, wtek,
który je przygotowa, blokuje muteks chronicy kolejk za pomoc klasy
std::lock_
´
guard
i umieszcza nowe dane w kolejce . Wtek wywouje nastpnie funkcj ska-
dow
notify_one()
dla obiektu klasy
std::condition_variable
, aby powiadomi ocze-
kujcy wtek (jeli taki istnieje) o dostpnoci nowych danych .
W tym modelu drug stron komunikacji jest wtek przetwarzajcy te dane. Wtek
przetwarzajcy najpierw blokuje muteks, jednak tym razem uyto do tego celu klasy
std::unique_lock
zamiast klasy
std::lock_guard
— przyczyny tej decyzji zostan
wyjanione za chwil. Wtek wywouje nastpnie funkcj
wait()
dla obiektu klasy
std::condition_variable
. Na wejciu tego wywoania wtek przekazuje obiekt blokady
i funkcj lambda reprezentujc warunek, który musi zosta speniony przed przyst-
pieniem do dalszego przetwarzania . Funkcje lambda to stosunkowo nowy element
(wprowadzony w standardzie C++11), który umoliwia pisanie funkcji anonimowych
w ramach innych wyrae. Wspomniane rozwizanie wprost idealnie nadaje si do
wskazywania predykatów w wywoaniach takich funkcji biblioteki standardowej jak
wait()
. W tym przypadku prosta funkcja lambda
[]{return !data_queue.empty();}
sprawdza, czy struktura reprezentowana przez zmienn
data_queue
nie jest pusta, tj.
czy kolejka zawiera jakie dane gotowe do przetworzenia. Funkcje lambda zostan szcze-
góowo omówione w czci A.5 dodatku A.
Implementacja funkcji
wait()
sprawdza warunek (wywoujc przekazan funkcj
lambda), po czym zwraca sterowanie, jeli ten warunek jest speniony (jeli funkcja
lambda zwrócia warto
true
). Jeli warunek nie jest speniony (jeli funkcja lambda
zwrócia warto
false
), funkcja
wait()
odblokowuje muteks i wprowadza biecy wtek
w stan blokady (oczekiwania). Kiedy zmienna warunkowa jest powiadamiana za pomoc
funkcji
notify_one()
wywoanej przez wtek przygotowujcy dane, wtek oczekujcy jest
budzony (odblokowywany), ponownie uzyskuje blokad muteksu i jeszcze raz sprawdza
warunek. Jeli warunek dalszego przetwarzania jest speniony, funkcja
wait()
zwraca
Poleć książkę
Kup książkę
4.1.
Oczekiwanie na zdarzenie lub inny warunek
97
sterowanie z zachowaniem blokady muteksu. Jeli warunek nie jest speniony, wtek
odblokowuje muteks i ponownie przechodzi w stan oczekiwania. Wanie dlatego w przy-
kadzie naleao uy klasy
std::unique_lock
zamiast klasy
std::lock_guard
— wtek
oczekujcy musi odblokowa muteks na czas oczekiwania i zablokowa go ponownie
po otrzymaniu powiadomienia, a klasa
std::lock_guard
nie zapewnia takiej elastycz-
noci. Gdyby muteks pozosta zablokowany przez cay czas upienia tego wtku, wtek
przygotowujcy dane nie mógby zablokowa tego muteksu i doda elementu do kolejki,
zatem warunek budzenia wtku oczekujcego nigdy nie zostaby speniony.
Na listingu 4.1 uyem prostej funkcji lambda , która sprawdza, czy struktura
kolejki nie jest pusta. Okazuje si, e w tej roli równie dobrze mona by uy dowolnej
funkcji lub obiektu wywoywalnego. Jeli programista dysponuje ju funkcj spraw-
dzajc odpowiedni warunek (funkcja moe oczywicie by nieporównanie bardziej
zoona ni prosty test z powyszego przykadu), moe przekaza t funkcj bezpo-
rednio na wejciu funkcji
wait()
, bez koniecznoci opakowywania jej w ramach wyra-
enia lambda. Po wywoaniu funkcji
wait()
zmienna warunkowa moe sprawdzi
wskazany warunek na wiele rónych sposobów, jednak podczas tego testu muteks
zawsze jest zablokowany, a funkcja
wait()
natychmiast zwraca sterowanie, pod warun-
kiem e przekazana funkcja sprawdzajca ten warunek zwrócia warto
true
. Jeli
wtek oczekujcy ponownie uzyskuje muteks i sprawdza warunek, mimo e nie otrzy-
ma powiadomienia od innego wtku i jego dziaania nie s bezporedni odpowiedzi
na takie powiadomienie, mamy do czynienia z tzw. pozornym budzeniem (ang. spu-
rious wake). Poniewa optymalna liczba i czstotliwo takich pozornych budze s
z definicji trudne do oszacowania, funkcja sprawdzajca prawdziwo warunku nie
powinna powodowa adnych skutków ubocznych. Gdyby ta funkcja powodowaa skutki
uboczne, programista musiaby przygotowa swój kod na wielokrotne wystpowanie
tych skutków przed spenieniem warunku.
Moliwo odblokowania obiektu klasy
std::unique_lock
nie jest uywana tylko
dla wywoania funkcji
wait()
— analogiczne rozwizanie zastosowalimy po uzyskaniu
danych do przetworzenia, ale przed przystpieniem do waciwego przetwarzania .
Przetwarzanie danych moe by czasochonn operacj, a jak wiemy z rozdziau 3.,
utrzymywanie blokady muteksu duej, ni to konieczne, nie jest dobrym rozwizaniem.
Stosowanie struktury kolejki do przekazywania danych pomidzy wtkami (jak na
listingu 4.1) jest do typowym rozwizaniem. Jeli projekt aplikacji jest waciwy,
synchronizacja powinna dotyczy samej kolejki, co znacznie ogranicza liczb poten-
cjalnych problemów i problematycznych sytuacji wycigu. Spróbujmy wic wyodrb-
ni z listingu 4.1 uniwersaln kolejk gwarantujc bezpieczne przetwarzanie wielo-
wtkowe.
4.1.2.
Budowa kolejki gwarantujcej bezpieczne przetwarzanie
wielowtkowe przy uyciu zmiennych warunkowych
Przed przystpieniem do projektowania uniwersalnej kolejki warto powici kilka
minut analizie operacji, które trzeba bdzie zaimplementowa dla tej struktury danych
(podobnie jak w przypadku stosu gwarantujcego bezpieczestwo przetwarzania wielo-
wtkowego z punktu 3.2.3). Przyjrzyjmy si kontenerowi
std::queue<>
dostpnemu
w bibliotece standardowej jzyka C++ (patrz listing 4.2), który bdzie stanowi punkt
wyjcia dla naszej implementacji.
Poleć książkę
Kup książkę
98
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
Listing 4.2. Interfejs kontenera std::queue
template <class T, class Container = std::deque<T> >
class queue {
public:
explicit queue(const Container&);
explicit queue(Container&& = Container());
template <class Alloc> explicit queue(const Alloc&);
template <class Alloc> queue(const Container&, const Alloc&);
template <class Alloc> queue(Container&&, const Alloc&);
template <class Alloc> queue(queue&&, const Alloc&);
void swap(queue& q);
bool empty() const;
size_type size() const;
T& front();
const T& front() const;
T& back();
const T& back() const;
void push(const T& x);
void push(T&& x);
void pop();
template <class... Args> void emplace(Args&&... args);
};
Jeli pominiemy operacje konstruowania, przypisywania i wymiany, pozostan nam
zaledwie trzy grupy operacji: operacje zwracajce stan caej kolejki (
empty()
i
size()
),
operacje zwracajce pojedyncze elementy kolejki (
front()
i
back()
) oraz operacje
modyfikujce kolejk (
push()
,
pop()
i
emplace()
). Mamy wic do czynienia z sytuacj
analogiczn do tej opisanej w punkcie 3.2.3 (gdzie omawialimy struktur stosu), zatem
opisany interfejs jest naraony na te same problemy zwizane z sytuacjami wycigów.
W tym przypadku naley poczy funkcje
front()
i
pop()
w jedno wywoanie, tak jak
wczeniej poczylimy funkcje
top()
i
pop()
dla struktury stosu. Warto jeszcze zwróci
uwag na pewien nowy element w kodzie z listingu 4.1 — podczas uywania kolejki
do przekazywania danych pomidzy wtkami wtek docelowy zwykle musi czeka na
te dane. Warto wic zaimplementowa funkcj
pop()
w dwóch wersjach — pierwsza
funkcja,
try_pop()
, próbuje pobra warto z kolejki, ale zawsze zwraca sterowanie
bezporednio po wywoaniu, nawet jeli kolejka nie zawieraa adnej wartoci (wtedy
funkcja sygnalizuje bd); druga funkcja,
wait_and_pop()
, czeka na pojawienie si
w kolejce wartoci do pobrania. Po wprowadzeniu zmian zgodnie ze schematem opi-
sanym ju przy okazji przykadu stosu interfejs struktury kolejki powinien wyglda
tak jak na listingu 4.3.
Listing 4.3. Interfejs struktury danych threadsafe_queue
#include <memory>
Dla typu std::shared_ptr
template<typename T>
class threadsafe_queue
Poleć książkę
Kup książkę
4.1.
Oczekiwanie na zdarzenie lub inny warunek
99
{
public:
threadsafe_queue();
threadsafe_queue(const threadsafe_queue&);
threadsafe_queue& operator=(
const threadsafe_queue&) = delete;
Dla uproszczenia wyklucza moliwo
przypisywania
void push(T new_value);
bool try_pop(T& value);
std::shared_ptr<T> try_pop();
void wait_and_pop(T& value);
std::shared_ptr<T> wait_and_pop();
bool empty() const;
};
Podobnie jak w przypadku stosu, na listingu 4.3 usunito konstruktory i operator
przypisania, aby uproci analizowany kod. Tak jak wczeniej, take tym razem funk-
cje
try_pop()
i
wait_for_pop()
wystpuj w dwóch wersjach. Pierwsza przeciona
wersja funkcji
try_pop()
zapisuje pobran warto we wskazywanej zmiennej, tak
aby mona byo uy tej wartoci w roli statusu; funkcja zwraca warto
true
, jeli
uzyskaa jak warto — w przeciwnym razie funkcja zwraca warto
false
(patrz
cz A.2 dodatku A). Druga przeciona wersja nie moe dziaa w ten sam spo-
sób, poniewa natychmiast zwraca uzyskan warto. Jeli jednak funkcja nie uzyskaa
adnej wartoci, moe zwróci wskanik równy
NULL
.
Jaki to ma zwizek z listingiem 4.1? Okazuje si, e moemy wyodrbni kod funkcji
push()
i
wait_and_pop()
z tamtego listingu i na tej podstawie przygotowa now imple-
mentacj (patrz listing 4.4).
Listing 4.4. Funkcje push() i wait_and_pop() wyodrbnione z listingu 4.1
#include <queue>
#include <mutex>
#include <condition_variable>
template<typename T>
class threadsafe_queue
{
private:
std::mutex mut;
std::queue<T> data_queue;
std::condition_variable data_cond;
public:
void push(T new_value)
{
std::lock_guard<std::mutex> lk(mut);
data_queue.push(new_value);
data_cond.notify_one();
}
void wait_and_pop(T& value)
{
Poleć książkę
Kup książkę
100
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
std::unique_lock<std::mutex> lk(mut);
data_cond.wait(lk,[this]{return !data_queue.empty();});
value=data_queue.front();
data_queue.pop();
}
};
threadsafe_queue<data_chunk> data_queue;
void data_preparation_thread()
{
while(more_data_to_prepare())
{
data_chunk const data=prepare_data();
data_queue.push(data);
}
}
void data_processing_thread()
{
while(true)
{
data_chunk data;
data_queue.wait_and_pop(data);
process(data);
if(is_last_chunk(data))
break;
}
}
Muteks i zmienna warunkowa s teraz elementami skadowymi obiektu klasy
threadsafe_
´
queue
, zatem nie jest potrzebne stosowanie odrbnych zmiennych , a wywoanie
funkcji
push()
nie wymaga zewntrznych mechanizmów synchronizacji . Jak wida,
take funkcja
wait_and_pop()
uwzgldnia stan zmiennej warunkowej .
Napisanie drugiej wersji przecionej funkcji
wait_and_pop()
nie stanowi adnego
problemu; take pozostae funkcje mona niemal skopiowa z przykadu stosu pokaza-
nego na listingu 3.5. Ostateczn wersj implementacji kolejki pokazano na listingu 4.5.
Listing 4.5. Kompletna definicja klasy kolejki gwarantujcej bezpieczestwo
przetwarzania wielowtkowego (dziki uyciu zmiennych warunkowych)
#include <queue>
#include <memory>
#include <mutex>
#include <condition_variable>
template<typename T>
class threadsafe_queue
{
private:
mutable std::mutex mut;
Muteks musi by modyfikowalny
std::queue<T> data_queue;
std::condition_variable data_cond;
public:
threadsafe_queue()
{}
Poleć książkę
Kup książkę
4.1.
Oczekiwanie na zdarzenie lub inny warunek
101
threadsafe_queue(threadsafe_queue const& other)
{
std::lock_guard<std::mutex> lk(other.mut);
data_queue=other.data_queue;
}
void push(T new_value)
{
std::lock_guard<std::mutex> lk(mut);
data_queue.push(new_value);
data_cond.notify_one();
}
void wait_and_pop(T& value)
{
std::unique_lock<std::mutex> lk(mut);
data_cond.wait(lk,[this]{return !data_queue.empty();});
value=data_queue.front();
data_queue.pop();
}
std::shared_ptr<T> wait_and_pop()
{
std::unique_lock<std::mutex> lk(mut);
data_cond.wait(lk,[this]{return !data_queue.empty();});
std::shared_ptr<T> res(std::make_shared<T>(data_queue.front()));
data_queue.pop();
return res;
}
bool try_pop(T& value)
{
std::lock_guard<std::mutex> lk(mut);
if(data_queue.empty())
return false;
value=data_queue.front();
data_queue.pop();
return true;
}
std::shared_ptr<T> try_pop()
{
std::lock_guard<std::mutex> lk(mut);
if(data_queue.empty())
return std::shared_ptr<T>();
std::shared_ptr<T> res(std::make_shared<T>(data_queue.front()));
data_queue.pop();
return res;
}
bool empty() const
{
std::lock_guard<std::mutex> lk(mut);
return data_queue.empty();
}
};
Poleć książkę
Kup książkę
102
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
Mimo e
empty()
jest sta funkcj skadow i mimo e parametr
other
konstruktora
kopiujcego jest sta referencj, pozostae wtki mog dysponowa niestaymi refe-
rencjami do tego obiektu i wywoywa funkcje skadowe zmieniajce jego stan, zatem
blokowanie muteksu wci jest konieczne. Poniewa blokowanie muteksu jest operacj
zmieniajc stan obiektu, obiekt muteksu naley oznaczy jako modyfikowalny (ang.
mutable) , tak aby mona byo blokowa ten muteks w ciele funkcji
empty()
i kon-
struktora kopiujcego.
Zmienne warunkowe s przydatne take w sytuacji, w której wiele wtków czeka na
to samo zdarzenie. Jeli celem stosowania wtków jest dzielenie obcienia i jeli tylko
jeden wtek powinien reagowa na powiadomienie, mona zastosowa dokadnie tak
sam struktur jak ta z listingu 4.1 — wystarczy uruchomi wiele instancji wtku prze-
twarzajcego dane. Po przygotowaniu nowych danych wywoanie funkcji
notify_one()
spowoduje, e jeden z wtków aktualnie wykonujcych funkcj
wait()
sprawdzi waru-
nek. Poniewa do struktury
data_queue
wanie dodano nowe dane, funkcja
wait()
zwróci sterowanie. Nie wiadomo, do którego wtku trafi powiadomienie ani nawet czy
istnieje wtek oczekujcy na to powiadomienie (nie mona przecie wykluczy, e
wszystkie wtki w danej chwili przetwarzaj swoje dane).
Warto te pamita o moliwoci oczekiwania na to samo zdarzenie przez wiele
wtków, z których kady musi zareagowa na powiadomienie. Opisany scenariusz moe
mie zwizek z inicjalizacj wspódzielonych danych, gdzie wszystkie wtki przetwa-
rzajce operuj na tych samych danych i musz czeka albo na ich inicjalizacj (w takim
przypadku istniej lepsze mechanizmy — patrz punkt 3.3.1 w rozdziale 3.), albo na ich
aktualizacj (na przykad w ramach okresowej, wielokrotnej inicjalizacji). W opisanych
przypadkach wtek przygotowujcy dane moe wywoa funkcj skadow
notify_all()
dla zmiennej warunkowej (zamiast funkcji
notify_one()
). Jak nietrudno si domyli,
funkcja powoduje, e wszystkie wtki aktualnie wykonujce funkcj
wait()
sprawdz
warunek, na który czekaj.
Jeli wtek wywoujcy w zaoeniu ma oczekiwa na dane zdarzenie tylko raz, czyli
jeli po spenieniu warunku wtek nie bdzie ponownie czeka na t sam zmienn
warunkow, by moe warto zastosowa inny mechanizm synchronizacji ni zmienna
warunkowa. Zmienne warunkowe s szczególnie nieefektywne w sytuacji, gdy warun-
kiem, na który oczekuj wtki, jest dostpno okrelonego elementu danych. W takim
przypadku lepszym rozwizaniem jest uycie mechanizmu przyszoci.
4.2.
Oczekiwanie na jednorazowe zdarzenia
za pomoc przyszoci
Przypumy, e planujemy podró samolotem. Po przyjedzie na lotnisko i przejciu
rozmaitych procedur wci musimy czeka na komunikat dotyczcy gotowoci naszego
samolotu na przyjcie pasaerów (zdarza si, e pasaerowie musz czeka wiele godzin).
Moemy oczywicie znale sposób, aby ten czas min nieco szybciej (moemy na
przykad czyta ksik, przeglda strony internetowe lub uda si na posiek do
drogiej lotniskowej kawiarni), jednak niezalenie od sposobu spdzania czasu czekamy
na jedno — sygna wzywajcy do udania si na pokad samolotu. Co wicej, interesu-
jcy nas lot odbdzie si tylko raz, zatem przy okazji nastpnego wyjazdu na wakacje
bdziemy czekali na inny lot.
Poleć książkę
Kup książkę
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci
103
Twórcy biblioteki standardowej jzyka C++ rozwizali problem jednorazowych
zdarze za pomoc mechanizmu nazwanego przyszoci (ang. future). Wtek, który
musi czeka na okrelone jednorazowe zdarzenie, powinien uzyska przyszo repre-
zentujc to zdarzenie. Wtek oczekujcy na t przyszo moe nastpnie okresowo
sprawdza, czy odpowiednie zdarzenie nie nastpio (tak jak pasaerowie co jaki czas
zerkaj na tablic odlotów), i jednoczenie pomidzy tymi testami wykonywa inne
zadanie (spoywa drogi deser w lotniskowej kawiarni). Alternatywnym rozwizaniem
jest wykonywanie innego zadania do momentu, w którym dalsze dziaanie nie jest mo-
liwe bez okrelonego zdarzenia, i przejcie w stan gotowoci na przyszo. Przyszo
moe, ale nie musi by powizana z danymi (tak jak tablica odlotów moe wskazywa
rkawy prowadzce do waciwych samolotów). Po wystpieniu zdarzenia (po osigni-
ciu gotowoci przez przyszo) nie jest moliwe wyzerowanie tej przyszoci.
W bibliotece standardowej jzyka C++ istniej dwa rodzaje przyszoci zaimple-
mentowane w formie dwóch szablonów klas zadeklarowanych w nagówku biblioteki
<future>
: przyszoci unikatowe (
std::future<>
) oraz przyszoci wspódzielone (
std::
´
shared_future<>
). Wymienione klasy opracowano na bazie typów
std::unique_ptr
i
std::shared_ptr
. Obiekt typu
std::future
jest jedyn instancj odwoujc si do
powizanego zdarzenia, natomiast do jednego zdarzenia moe si odwoywa wiele
instancji typu
std::shared_future
. W drugim przypadku wszystkie instancje s gotowe
jednoczenie i wszystkie mog uzyskiwa dostp do dowolnych danych powizanych
z danym zdarzeniem. Wanie z myl o powizanych danych zaprojektowano te szablony
klas — tak jak w przypadku szablonów
std::unique_ptr
i
std::shared_ptr
, parametry
szablonów
std::future<>
i
std::shared_future<>
reprezentuj wanie typy powizanych
danych. W razie braku powizanych danych naley stosowa nastpujce specjalizacje
tych szablonów:
std:future<void>
i
std::shared_future<void>.
Mimo e przyszoci
su do komunikacji pomidzy wtkami, same obiekty przyszoci nie oferuj mecha-
nizmów synchronizowanego dostpu. Jeli wiele wtków potrzebuje dostpu do jednego
obiektu przyszoci, naley chroni ten dostp za pomoc muteksu lub innego mecha-
nizmu synchronizacji (patrz rozdzia 3.). Jak napisz w punkcie 4.2.5 w dalszej czci
tego podrozdziau, wiele wtków moe uzyskiwa dostp do wasnej kopii obiektu typu
std::shared_future<>
bez koniecznoci dodatkowej synchronizacji, nawet jeli wszystkie
te kopie odwouj si do tego samego asynchronicznego wyniku.
Najprostszym przykadem jednorazowego zdarzenia jest wynik oblicze wykonywa-
nych w tle. Ju w rozdziale 2. napisaem, e klasa
std::thread
nie udostpnia prostych
mechanizmów zwracania wartoci wynikowych dla tego rodzaju zada, i zapowiedzia-
em wprowadzenie odpowiednich rozwiza w rozdziale 4. przy okazji omawiania przy-
szoci — czas zapozna si z tymi rozwizaniami.
4.2.1.
Zwracanie wartoci przez zadania wykonywane w tle
Przypumy, e nasza aplikacja wykonuje czasochonne obliczenia, które ostatecznie
pozwol uzyska oczekiwany wynik. Zaómy, e warto wynikowa nie jest potrzebna
na tym etapie dziaania programu. By moe udao nam si wymyli sposób poszu-
kiwania odpowiedzi na pytanie o ycie, wszechwiat i ca reszt stawiane w ksikach
Poleć książkę
Kup książkę
104
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
Douglasa Adamsa
1
. Moglibymy oczywicie uruchomi nowy wtek, który wykona
niezbdne obliczenia, jednak takie rozwizanie wizaoby si z koniecznoci przeka-
zania wyników z powrotem do wtku gównego, poniewa klasa
std::thread
nie oferuje
alternatywnego mechanizmu zwracania wartoci wynikowych. W takim przypadku
sporym uatwieniem jest uycie szablonu funkcji
std::async
(zadeklarowanego w pliku
nagówkowym
<future>
).
Asynchroniczne zadanie, którego wynik nie jest potrzebny na biecym etapie dzia-
ania programu, mona rozpocz za pomoc funkcji
std::async
. Zamiast zwracania
obiektu klasy
std::thread
, który umoliwi oczekiwanie na zakoczenie danego wtku,
funkcja
std::async
zwraca obiekt klasy
std::future
, który w przyszoci bdzie zawiera
warto wynikow. W miejscu, w którym aplikacja bdzie potrzebowaa tej wartoci,
naley wywoa funkcj
get()
dla obiektu przyszoci — wywoanie tej funkcji zablo-
kuje wykonywanie biecego wtku do momentu osignicia gotowoci przez przy-
szo, po czym zwróci uzyskan warto. Prosty przykad uycia tych elementów poka-
zano na listingu 4.6.
Listing 4.6. Przykad uycia szablonu klasy std::future do uzyskania wartoci
wynikowej asynchronicznego zadania
#include <future>
#include <iostream>
int find_the_answer_to_ltuae();
void do_other_stuff();
int main()
{
std::future<int> the_answer=std::async(find_the_answer_to_ltuae);
do_other_stuff();
std::cout<<"Odpowied brzmi "<<the_answer.get()<<std::endl;
}
Szablon funkcji
std::async
umoliwia przekazywanie dodatkowych argumentów na
wejciu wywoywanej funkcji — wystarczy doda te argumenty do wywoania (podob-
nie jak w przypadku klasy
std::thread
). Jeli pierwszy argument reprezentuje wskanik
do funkcji skadowej, drugi argument zawiera obiekt, dla którego ma zosta wywoana
ta funkcja skadowa (bezporednio, za porednictwem wskanika lub poprzez opako-
wanie
std::ref
), a pozostae argumenty s przekazywane na wejciu tej funkcji skado-
wej. W przeciwnym razie drugi i kolejne argumenty s przekazywane na wejciu funkcji
skadowej lub wywoywalnego obiektu wskazanego za porednictwem pierwszego argu-
mentu. Tak jak w przypadku klasy
std::thread
, jeli argumenty maj posta r-wartoci,
zostan utworzone kopie poprzez przeniesienie oryginalnych wartoci. Dziki temu
moemy stosowa typy oferujce tylko moliwo przenoszenia zarówno w roli obiektów
funkcji, jak i w roli argumentów. Przykad takiego rozwizania pokazano na listingu 4.7.
1
W ksice Autostopem przez Galaktyk zbudowano komputer Deep Thought, który mia odpowiedzie
na pytanie o ycie, wszechwiat i ca reszt. Odpowiedzi na to pytanie bya liczba 42.
Poleć książkę
Kup książkę
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci
105
Listing 4.7. Przekazywanie argumentów na wejciu funkcji wtku std::async
#include <string>
#include <future>
struct X
{
void foo(int,std::string const&);
std::string bar(std::string const&);
};
X x;
auto f1=std::async(&X::foo,&x,42,"witaj");
auto f2=std::async(&X::bar,x,"egnaj");
struct Y
{
double operator()(double);
};
Y y;
auto f3=std::async(Y(),3.141);
auto f4=std::async(std::ref(y),2.718);
Wywouje y(2.718)
X baz(X&);
std::async(baz,std::ref(x));
Wywouje baz(x)
class move_only
{
public:
move_only();
move_only(move_only&&)
move_only(move_only const&) = delete;
move_only& operator=(move_only&&);
move_only& operator=(move_only const&) = delete;
void operator()();
};
auto f5=std::async(move_only());
Domylnie to od stosowanej implementacji zaley, czy funkcja
std::async
uruchamia
nowy wtek, czy wskazane zadanie bdzie wykonywane w sposób synchroniczny (wów-
czas biecy wtek bdzie czeka na osignicie gotowoci przez przyszo). W wikszo-
ci przypadków standardowe rozwizanie jest wystarczajce, jednak programista moe
wybra waciwy tryb za pomoc dodatkowego parametru funkcji
std::async
przeka-
zywanego przed funkcj do wywoania. Wspomniany parametr typu
std::launch
moe
mie albo warto
std::launch::deferred
(wówczas wywoanie funkcji jest odkadane
do momentu wywoania funkcji
wait()
lub
get()
dla danej przyszoci), albo warto
std::
´
launch::async
(wówczas funkcja musi by wykonywana w odrbnym wtku), albo
warto
std::launch::deferred | std::launch::async
(wówczas decyzja naley do
implementacji). Ostatnia opcja jest stosowana w roli wartoci domylnej. Jeli wywo-
anie funkcji jest odkadane na przyszo, moe nigdy nie nastpi. Na przykad:
auto f6=std::async(std::launch::async,Y(),1.2);
Wykonywane w nowym wtku
auto f7=std::async(std::launch::deferred,baz,std::ref(x));
auto f8=std::async(
std::launch::deferred | std::launch::async,
baz,std::ref(x));
auto f9=std::async(baz,std::ref(x));
f7.wait();
Wywoanie odroczonej funkcji
Wywouje p->foo(42,"witaj"),
gdzie p jest reprezentowane przez &x
Wywouje tmpx.bar("egnaj"),
gdzie tmpx jest kopi x
Wywouje tmpy(3.141), gdzie tmpy
jest tworzone za pomoc konstruktora
przenoszcego Y()
Wywouje tmp(), gdzie tmp jest konstruowany
na podstawie wywoania std::move(move_only())
Wykonywane w ramach
funkcji wait() lub get()
Wybór
implementacji
Poleć książkę
Kup książkę
106
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
Jak si przekonasz w dalszej czci tego rozdziau (i ponownie w rozdziale 8.), funkcja
std::async
uatwia dzielenie algorytmów na wspóbienie wykonywane zadania. Oka-
zuje si jednak, e nie jest to jedyny sposób kojarzenia obiektu typu
std::future
z zada-
niem — alternatywnym rozwizaniem jest opakowanie zadania w ramach instancji
szablonu klasy
std::packaged_task<>
lub napisanie kodu bezporednio ustawiajcego
wartoci za pomoc szablonu klasy
std::promise<>
. Szablon klasy
std::packaged_task
jest abstrakcj wyszego poziomu (w porównaniu z szablonem
std::promise
), zatem
wanie ten szablon omówimy jako pierwszy.
4.2.2.
Wizanie zadania z przyszoci
Szablon klasy
std::packaged_task<>
wie przyszo z funkcj lub wywoywalnym
obiektem. W momencie wywoania obiektu typu
std::packaged_task<>
wywoana zostaje
powizana funkcja lub wywoywalny obiekt, a sama przyszo przechodzi w stan goto-
woci (warto wynikowa zostaje umieszczona w powizanych danych). Opisan struktur
mona wykorzysta w roli elementu skadowego podczas budowy puli wtków (patrz
rozdzia 9.) lub dowolnego innego schematu zarzdzania zadaniami polegajcego na
przykad na wykonywaniu kadego zadania w osobnym wtku lub sekwencyjnym wyko-
nywaniu zada w jednym wtku dziaajcym w tle. Jeli jedn wiksz operacj mona
podzieli na wiele autonomicznych podzada, kade z tych podzada mona opakowa
w ramach obiektu klasy
std::packaged_task<>
, aby nastpnie przekaza ten obiekt do
mechanizmu szeregowania zada lub do puli wtków. W ten sposób mona skutecznie
ukry szczegóy zwizane z poszczególnymi zadaniami — mechanizm szeregowania zada
operuje na obiektach klasy
std::packaged_task<>
, nie na poszczególnych funkcjach.
Parametr szablonu klasy
std::packaged_task<>
reprezentuje sygnatur funkcji —
na przykad dla funkcji, która nie otrzymuje adnych parametrów i nie zwraca wartoci,
naleaoby uy sygnatury
void()
, natomiast dla funkcji otrzymujcej niesta refe-
rencj do wartoci typu
std::string
i wskanik do wartoci typu
double
oraz zwraca-
jcej warto typu
int
naleaoby uy sygnatury
int(std::string&,double*)
. Podczas
konstruowania obiektu klasy
std::packaged_task
naley przekaza funkcj (lub wywo-
ywalny obiekt) otrzymujc na wejciu wskazane parametry i zwracajc typ, który
mona przekonwertowa na wskazany typ danych. Dokadne dopasowanie typów nie
jest wymagane — istnieje moliwo skonstruowania obiektu klasy
std::packaged_task
´
<double(double)>
na podstawie funkcji otrzymujcej na wejciu warto typu
int
i zwracajcej warto typu
float
, poniewa wymienione typy mog by automatycznie
konwertowane.
Typ wartoci zwracanych przez wskazan funkcj identyfikuje typ zwracany przez
funkcj skadow
get_future()
konstruowanego obiektu klasy
std::future<>
, nato-
miast lista argumentów zdefiniowana w ramach sygnatury funkcji jest uywana do
wyznaczania sygnatury operatora wywoania funkcji zadania reprezentowanego przez
ten obiekt. Przykad czciowej definicji klasy
std::packaged_task<std::string(std::
´
vector<char>*,int)>
pokazano na listingu 4.8.
Instancja klasy
std::packaged_task
jest obiektem wywoywalnym i jako taka moe
by opakowana w ramach obiektu klasy
std::function
, przekazana do obiektu kla-
sy
std::thread
w roli funkcji wtku, przekazana do dowolnej innej funkcji oczekujcej
wywoywalnego obiektu, a nawet bezporednio wywoana. W momencie wywoania
Poleć książkę
Kup książkę
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci
107
Listing 4.8. Czciowa definicja specjalizacji szablonu klasy
std::packaged_task<>
template<>
class packaged_task<std::string(std::vector<char>*,int)>
{
public:
template<typename Callable>
explicit packaged_task(Callable&& f);
std::future<std::string> get_future();
void operator()(std::vector<char>*,int);
};
obiektu klasy
std::packaged_task
jako obiektu funkcji argumenty przekazane na wejciu
operatora wywoania s przekazywane do opakowanej funkcji, a zwracana warto jest
zapisywana jako asynchroniczny wynik w obiekcie typu
std::future
(obiekt mona
nastpnie uzyska za pomoc funkcji
get_future()
). Oznacza to, e moemy opakowa
zadanie w obiekcie klasy
std::packaged_task
i uzyska przyszo przed przekazaniem
tego obiektu do miejsca, gdzie zostanie wywoany. W momencie, w którym program
bdzie potrzebowa wyniku, wystarczy poczeka na osignicie gotowoci przez t przy-
szo. Praktyczny przykad takiego rozwizania opisano w nastpnym podpunkcie.
P
RZEKAZYWANIE ZADA POMIDZY WTKAMI
Wiele frameworków graficznego interfejsu uytkownika wymaga, aby aktualizacje tego
interfejsu byy wykonywane przez okrelone wtki. Oznacza to, e jeli jaki inny wtek
musi zaktualizowa graficzny interfejs uytkownika, powinien wysa komunikat do
waciwego wtku, aby wyznaczony wtek wykona to zadanie w jego imieniu. Szablon
klasy
std::packaged_task
oferuje odpowiednie rozwizania bez koniecznoci stosowania
niestandardowych komunikatów dla kadego zadania zwizanego z dziaaniem graficz-
nego interfejsu uytkownika (patrz listing 4.9).
Listing 4.9. Uruchamianie kodu w wtku graficznego interfejsu uytkownika
za pomoc szablonu klasy std::packaged_task
#include <deque>
#include <mutex>
#include <future>
#include <thread>
#include <utility>
std::mutex m;
std::deque<std::packaged_task<void()> > tasks;
bool gui_shutdown_message_received();
void get_and_process_gui_message();
void gui_thread()
{
while(!gui_shutdown_message_received())
{
get_and_process_gui_message();
std::packaged_task<void()> task;
{
Poleć książkę
Kup książkę
108
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
std::lock_guard<std::mutex> lk(m);
if(tasks.empty())
continue;
task=std::move(tasks.front());
tasks.pop_front();
}
task();
}
}
std::thread gui_bg_thread(gui_thread);
template<typename Func>
std::future<void> post_task_for_gui_thread(Func f)
{
std::packaged_task<void()> task(f);
std::future<void> res=task.get_future();
std::lock_guard<std::mutex> lk(m);
tasks.push_back(std::move(task));
return res;
}
Powyszy kod jest bardzo prosty: wtek graficznego interfejsu uytkownika dziaa
w ptli do momentu otrzymania komunikatu sygnalizujcego konieczno zamknicia
tego interfejsu . W ciele tej ptli wtek sprawdza komunikaty dotyczce graficznego
interfejsu uytkownika (na przykad tego, e uytkownik klikn jaki element inter-
fejsu) oraz ewentualne zadania w kolejce zada. Jeli kolejka nie zawiera adnych zada
, wtek przechodzi do nastpnej iteracji ptli; w przeciwnym razie wtek odczytuje
zadanie z kolejki , zwalnia blokad tej kolejki, po czym uruchamia to zadanie .
W momencie zakoczenia zadania powizana z nim przyszo przechodzi w stan
gotowoci.
Umieszczenie zadania w kolejce jest równie proste: nowe, opakowane zadanie jest
tworzone na podstawie wskazanej funkcji , przyszo jest uzyskiwana z obiektu zada-
nia za pomoc funkcji skadowej
get_future()
i wreszcie zadanie jest umieszczane
na licie przed zwróceniem przyszoci do kodu wywoujcego . Kod, który wysya
komunikat do wtku interfejsu uytkownika, moe albo poczeka na przyszo (jeli
wykonanie zadania jest niezbdne do dalszego dziaania), albo porzuci t przyszo
(jeli nie potrzebuje wyniku przetwarzania).
W tym przykadzie uylimy do reprezentacji zada klasy
std::packaged_task
´
<void()>
. Klasa opakowuje funkcj (lub inny obiekt wywoywalny), która nie otrzy-
muje adnych parametrów i zwraca
void
(jeli wskazana funkcja zwraca inn warto,
wynik zostanie porzucony). W tym przypadku zastosowano najprostsze moliwe zada-
nie, jednak (jak ju wiemy) szablon klasy
std::packaged_task
moe by równie dobrze
stosowany w implementacjach bardziej zoonych rozwiza — wystarczy w roli para-
metru szablonu uy innej sygnatury funkcji, zmieni typ zwracanych wartoci (a wic
take typ danych przechowywanych w ramach stanu przyszoci) i zmieni typy argu-
mentów operatora wywoania funkcji. Przedstawiony przykad mona by atwo rozsze-
rzy o moliwo przekazywania argumentów do zada, które maj by wykonywane
przez wtek graficznego interfejsu uytkownika, i zwracania wartoci w ramach obiektu
typu
std::future
(zamiast samego sygnau o zakoczeniu zadania).
Poleć książkę
Kup książkę
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci
109
Co naley zrobi z zadaniami, których nie mona wyrazi w formie prostych wywo-
a funkcji, i zadaniami, których wyniki mog pochodzi z wielu rónych miejsc? Obsuga
takich przypadków wymaga jeszcze innego sposobu tworzenia przyszoci — bezpo-
redniego ustawiania wartoci za pomoc szablonu
std::promise
.
4.2.3.
Obietnice (szablon std::promise)
Programici pracujcy nad aplikacjami, które musz obsugiwa wiele pocze sie-
ciowych, czsto ulegaj pokusie obsugi kadego poczenia w osobnym wtku, ponie-
wa takie rozwizanie uatwia zrozumienie i zaimplementowanie mechanizmów komu-
nikacji sieciowej. Takie rozwizanie sprawdza si w przypadku niewielkiej liczby
pocze (a wic take niewielkiej liczby wtków). Okazuje si jednak, e w razie
wzrostu liczby pocze opisany model staje si nieefektywny, poniewa dua liczba
wtków zajmuje zbyt wiele zasobów systemu operacyjnego, a czste przeczanie
kontekstu (jeli liczba wtków przekracza wspóbieno sprztow) ma negatywny
wpyw na wydajno aplikacji. W skrajnych przypadkach aplikacja uruchamiajca duo
nowych wtków moe wyczerpa zasoby systemu operacyjnego przed osigniciem limitu
pocze sieciowych. Wanie dlatego nawet w aplikacjach obsugujcych bardzo duo
pocze sieciowych stosuje si stosunkowo niewiele wtków (czasem tylko jeden
wtek) odpowiedzialnych za obsug tych pocze, zatem kady wtek musi obsugi-
wa wiele pocze jednoczenie.
Przeanalizujmy przykad wtku obsugujcego poczenia. Pakiety danych przy-
chodz za porednictwem rónych pocze w przypadkowej kolejnoci; podobnie
pakiety danych przeznaczone do wysania s kolejkowane w przypadkowej kolejnoci.
W wielu przypadkach pozostae elementy aplikacji bd oczekiway albo na wysanie
danych, albo na otrzymanie nowego pakietu danych za porednictwem okrelonego po-
czenia sieciowego.
Szablon klasy
std::promise<T>
umoliwia ustawienie wartoci (typu
T
), któr w przy-
szoci bdzie mona odczyta za porednictwem powizanego obiektu klasy
std::
´
future<T>
. Para klas
std::promise
i
std::future
to jeden z mechanizmów umoli-
wiajcych implementacj interesujcego nas rozwizania — wtek oczekujcy moe
wstrzyma dziaanie w oczekiwaniu na przyszo, natomiast wtek udostpniajcy
dane moe uy obiektu obietnicy do ustawienia powizanej wartoci, tak aby odpo-
wiednia przyszo przesza w stan gotowoci.
Obiekt klasy
std::future
powizany z danym obiektem klasy
std::promise
mona
uzyska za pomoc funkcji skadowej
get_future()
, a wic tak samo jak w przypadku
obiektu klasy
std::packaged_task
. W momencie ustawienia wartoci obiektu obietnicy
(za pomoc funkcji skadowej
set_value()
) obiekt przyszoci przechodzi w stan goto-
woci i jako taki moe zosta uyty do pobrania zapisanej wartoci. Jeli nastpi znisz-
czenie obiektu klasy
std::promise
bez wczeniejszego ustawienia wartoci, zamiast
oczekiwanej wartoci zostanie ustawiony stosowny wyjtek. Sposób przekazywania wyjt-
ków pomidzy wtkami zostanie opisany w punkcie 4.2.4.
Na listingu 4.10 pokazano przykad kodu wtku, który przetwarza poczenia w opi-
sany powyej sposób. W prezentowanym przykadzie uylimy pary klas
std::promise
´
<bool>
i
std::future<bool>
do identyfikacji udanej transmisji bloku danych wycho-
dzcych; warto powizana z obiektem przyszoci ma posta prostej flagi sukcesu
Poleć książkę
Kup książkę
110
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
lub niepowodzenia. W przypadku pakietów przychodzcych funkcj danych powiza-
nych z obiektem przyszoci peni waciwa tre tych pakietów.
Listing 4.10. Obsuga wielu pocze w jednym wtku przy uyciu obiektów obietnic
#include <future>
void process_connections(connection_set& connections)
{
while(!done(connections))
{
for(connection_iterator
connection=connections.begin(),end=connections.end();
connection!=end;
++connection)
{
if(connection->has_incoming_data())
{
data_packet data=connection->incoming();
std::promise<payload_type>& p=
connection->get_promise(data.id);
p.set_value(data.payload);
}
if(connection->has_outgoing_data())
{
outgoing_packet data=
connection->top_of_outgoing_queue();
connection->send(data.payload);
data.promise.set_value(true);
}
}
}
}
Funkcja
process_connections()
wykonuje ptl do momentu, w którym funkcja
done()
zwróci warto
true
. W kadej iteracji tej ptli kod aplikacji sprawdza kolejno kade
poczenie
i pobiera dane przychodzce (jeli istniej) lub wysya kolejkowane
dane wychodzce . Zakadamy, e pakiet przychodzcy zawiera jaki identyfikator i wa-
ciwe dane. Identyfikator jest odwzorowywany na odpowiedni obiekt klasy
std::promise
(na przykad metod odnajdywania w kontenerze asocjacyjnym) , natomiast warto
jest przypisywana do ciaa pakietu. W przypadku pakietów wychodzcych zastosowa-
no mechanizm kolejki pakietów oczekujcych na wysanie — program sprawdza stan
kolejki i wysya ewentualne pakiety dla danego poczenia. Po wysaniu pakietu w obiek-
cie obietnicy powizanym z tymi danymi wychodzcymi jest ustawiana warto
true
,
która oznacza pomyln transmisj danych . Zgodno opisanego modelu z rzeczy-
wistymi protokoami komunikacji sieciowej zaley tylko od tych protokoów. Struktura
na bazie obietnicy i przyszoci nie pasuje co prawda do kadego scenariusza, ale pod
wieloma wzgldami przypomina model asynchronicznych operacji wejcia-wyjcia sto-
sowany w niektórych systemach operacyjnych.
W dotychczas prezentowanym kodzie cakowicie ignorowalimy problem wyjt-
ków. Wyobraenie wiata, w którym wszystko dziaa, jak naley, jest by moe kuszce,
ale nie ma wiele wspólnego z rzeczywistoci. Nie mona wykluczy, e dysk zostanie
Poleć książkę
Kup książkę
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci
111
zapeniony, e program nie bdzie móg znale potrzebnych danych, e nastpi awa-
ria poczenia sieciowego lub e w wyniku bdu nie bdzie dostpna baza danych.
Jeli operacja wykonywana w jednym wtku potrzebuje do dziaania wyniku innego
wtku, warto uwzgldni moliwo zasygnalizowania bdu w formie wyjtku — zaka-
danie, e w kodzie stosujcym obiekty klasy
std::packaged_task
czy
std::promise
wszystko zawsze bdzie dziaao prawidowo, byoby zbyt optymistyczne. Biblioteka
standardowa jzyka C++ oferuje wygodne mechanizmy obsugi wyjtków w tego rodzaju
scenariuszach i umoliwia zapisywanie wyjtków w ramach wyników powizanych z tymi
obiektami.
4.2.4.
Zapisywanie wyjtku na potrzeby przyszoci
Przeanalizujmy nastpujcy fragment kodu. Jeli na wejciu funkcji
square_root()
prze-
kaemy warto
-1
, zgoszony zostanie wyjtek (to on trafi do kodu wywoujcego t
funkcj):
double square_root(double x)
{
if(x<0)
{
throw std::out_of_range(“x<0”);
}
return sqrt(x);
}
Przypumy teraz, e zamiast wywoa funkcj
square_root()
w biecym wtku, jak
w poniszym wierszu:
double y=square_root(-1);
uyjemy wywoania asynchronicznego w nastpujcej formie:
std::future<double> f=std::async(square_root,-1);
double y=f.get();
Idealnym rozwizaniem byoby zapewnienie dokadnie takiego samego zachowania
jak w przypadku kodu jednowtkowego — skoro zmiennej
y
w obu przypadkach jest
przypisywany wynik funkcji, wtek wywoujcy funkcj
f.get()
powinien mie dostp
take do ewentualnych wyjtków (tak jak odpowiedni kod jednowtkowy).
Okazuje si, e wanie tak dziaa prezentowane rozwizanie: jeli funkcja
square_
´
root
wywoana za porednictwem funkcji
std::async
zgosi jaki wyjtek, wyjtek
ten zostanie zapisany w obiekcie przyszoci (w miejscu dla wartoci wynikowej), przy-
szo przejdzie w stan gotowoci, a funkcja
get()
spowoduje ponowne zgoszenie zapi-
sanego wyjtku. (Uwaga: standard jzyka C++ nie okrela, czy ponowne zgoszenie
dotyczy oryginalnego obiektu wyjtku, czy jego kopii; róne kompilatory i biblioteki
stosuj w tym wzgldzie odmienne rozwizania). To samo dotyczy funkcji opakowanej
w ramach obiektu klasy
std::packaged_task
— jeli po wywoaniu zadania opakowana
funkcja zgosi jaki wyjtek, wyjtek jest zapisywany w obiekcie przyszoci zamiast
waciwego wyniku. Aby ponownie zgosi ten wyjtek, wystarczy wywoa funkcj
get()
.
Szablon klasy
std::promise
oferuje oczywicie analogiczne rozwizanie, które wymaga
bezporedniego wywoania funkcji. Aby zapisa wyjtek zamiast wartoci wynikowej,
wystarczy wywoa funkcj skadow
set_exception()
zamiast funkcji
set_value()
.
Poleć książkę
Kup książkę
112
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
Wspomniana funkcja jest zwykle stosowana w bloku
catch
odpowiedzialnym za obsug
wyjtku zgoszonego w trakcie dziaania algorytmu — wyjtek jest umieszczany w obiek-
cie obietnicy:
extern std::promise<double> some_promise;
try
{
some_promise.set_value(calculate_value());
}
catch(...)
{
some_promise.set_exception(std::current_exception());
}
W powyszym kodzie uyto funkcji
std::current_exception()
do pobrania zgoszonego
wyjtku; alternatywnym rozwizaniem byoby wywoanie funkcji
std::copy_exception()
w celu zapisania nowego wyjtku bez jego bezporedniego zgaszania:
some_promise.set_exception(std::copy_exception(std::logic_error("foo ")));
Opisane rozwizanie jest nieporównanie bardziej czytelne ni stosowanie bloku
try
-
catch
,
jeli tylko potencjalny wyjtek jest znany z wyprzedzeniem. W ten sposób mona nie
tylko uproci kod, ale te uatwi optymalizacj tego kodu przez kompilator.
Innym sposobem zapisywania wyjtku w przyszoci jest zniszczenie obiektu klasy
std::promise
lub
std::packaged_task
powizanego z obiektem przyszoci bez uprzed-
niego wywoania funkcji ustawiajcej (w przypadku obiektu obietnicy) lub uruchomie-
nia opakowanego zadania. Jeli obiekt przyszoci nie bdzie gotowy, w obu przypadkach
destruktor klasy
std::promise
lub
std::packaged_task
zapisze w powizanym stanie
wyjtek typu
std::future_error
z kodem bdu
std::future_errc::broken_promise
.
Tworzc przyszo, zapowiadamy (skadamy obietnic), e udostpnimy jak warto
lub jaki wyjtek; zniszczenie róda tej wartoci lub tego wyjtku bez uprzedniego
dostarczenia zapowiedzianego zasobu amie t obietnic. Gdyby w opisanym przypadku
kompilator niczego nie zapisa w obiekcie przyszoci, wtki oczekujce mogyby czeka
w nieskoczono.
Do tej pory we wszystkich przykadach stosowaem szablon klasy
std::future
.
Warto jednak pamita o pewnych ograniczeniach szablonu
std::future
, w tym o mo-
liwoci oczekiwania na wynik przez zaledwie jeden wtek. W razie koniecznoci zaim-
plementowania modelu, w którym na jedno zdarzenie bdzie oczekiwao wiele wtków,
naley uy raczej szablonu klasy
std::shared_future
.
4.2.5.
Oczekiwanie na wiele wtków
Mimo e szablon klasy
std::future
obsuguje wszystkie mechanizmy synchronizacji
potrzebne do przesyania danych pomidzy wtkami, wywoania funkcji skadowych
okrelonego obiektu klasy
std::future
nie s synchronizowane z wywoaniami funkcji
pozostaych obiektów tej klasy. Jeli wiele wtków uzyskuje dostp do jednego obiektu
klasy
std::future
bez stosowania dodatkowych mechanizmów synchronizacji, aplika-
cja jest naraona na wycig danych i niezdefiniowane zachowania. Problem wynika
z projektu tego rozwizania — szablon klasy
std::future
modeluje unikatow wasno
asynchronicznego wyniku, a jednorazowy charakter funkcji
get()
i tak wyklucza sens
Poleć książkę
Kup książkę
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci
113
wspóbienego dostpu. Skoro po pierwszym wywoaniu funkcji
get()
nie mona ju
pobra adnych danych, z natury rzeczy dane mog by pobrane tylko przez jeden wtek.
Jeli jednak projekt naszej aplikacji wspóbienej wymaga, aby wiele wtków mogo
czeka na to samo zdarzenie, nie wszystko stracone — wystarczy uy szablonu klasy
std::shared_future
. O ile szablon klasy
std::future
oferuje tylko moliwo przeno-
szenia, zatem wasno przyszoci mona przenosi pomidzy rónymi obiektami, ale
tylko jeden obiekt moe si jednoczenie odwoywa do jednego asynchronicznego
wyniku, o tyle szablon klasy
std::shared_future
oferuje moliwo kopiowania, zatem
moe istnie wiele obiektów odwoujcych si do tego samego stanu.
W przypadku szablonu
std::shared_future
funkcje skadowe wywoywane dla poje-
dynczego obiektu wci nie s synchronizowane, zatem warunkiem unikania wycigów
danych w zwizku z dostpem do tego samego obiektu z poziomu wielu wtków jest
ochrona tego dostpu za pomoc blokady. Najlepszym sposobem jest kopiowanie tego
obiektu, tak aby kady wtek uzyskiwa dostp do wasnej kopii. Dostp do wspódzie-
lonego, asynchronicznego stanu z poziomu wielu wtków jest bezpieczny, jeli tylko
kady z tych wtków uzyskuje dostp do stanu za porednictwem wasnego obiektu
klasy
std::shared_future
. Przykad takiego rozwizania pokazano na rysunku 4.1.
Rysunek 4.1.
Uycie
wielu obiektów klasy
std::shared_future
w celu uniknicia
wycigów danych
Jednym z moliwych zastosowa szablonu klasy
std::shared_future
jest implementa-
cja równolegego wykonywania jakiej operacji w modelu zblionym do zoonego
arkusza kalkulacyjnego, gdzie kada komórka zawiera warto, która moe by uywana
Poleć książkę
Kup książkę
114
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
we wzorach w wielu pozostaych komórkach. Wzory potrzebne do obliczania wyników
w komórkach zalenych mog uywa obiektu klasy
std::shared_future
podczas odwo-
ywania si do pierwszej komórki. Jeli wzory we wszystkich komórkach bd prze-
twarzane równolegle, zadania odwoujce si do gotowych wartoci zostan zrealizo-
wane natychmiast, natomiast zadania zalene od innych, jeszcze przetwarzanych komórek
bd musiay poczeka na osignicie gotowoci przez tamte komórki. Takie rozwi-
zanie umoliwia maksymalne wykorzystanie dostpnej wspóbienoci sprztowej.
Obiekty klasy
std::shared_future
, które wskazuj pewien asynchroniczny stan, s
konstruowane na podstawie obiektów klasy
std::future
odwoujcych si do tego stanu.
Poniewa obiekty klasy
std::future
nie wspódziel wasnoci tego asynchronicznego
stanu z adnymi innymi obiektami, wasno naley przenie do obiektu klasy
std::
´
shared_future
za pomoc funkcji
std::move
, pozostawiajc oryginalny obiekt klasy
std::future
z pustym stanem (jak w przypadku uycia konstruktora domylnego):
std::promise<int> p;
std::future<int> f(p.get_future());
assert(f.valid());
Przyszo f jest prawidowa
std::shared_future<int> sf(std::move(f));
assert(!f.valid());
Przyszo f ju nie jest prawidowa
assert(sf.valid());
Przyszo sf jest teraz prawidowa
Obiekt przyszoci
f
jest pocztkowo prawidowy , poniewa odwouje si do asyn-
chronicznego stanu obietnicy
p
, jednak po przeniesieniu tego stanu do obiektu
sf
to
obiekt
sf
jest prawidowy , natomiast obiekt
f
jest ju nieprawidowy .
Jak w przypadku wszystkich obiektów z moliwoci przenoszenia, przeniesienie
wasnoci jest wykonywane automatycznie dla r-wartoci, zatem moemy skonstruowa
obiekt klasy
std::shared_future
bezporednio na podstawie wartoci zwróconej przez
funkcj skadow
get_future()
obiektu klasy
std::promise
:
std::promise<std::string> p;
std::shared_future<std::string> sf(p.get_future());
Automatyczne
przeniesienie wasnoci
W powyszym kodzie wasno jest przenoszona automatycznie — obiekt klasy
std::
´
shared_future<>
jest konstruowany na podstawie r-wartoci typu
std::future<std::
´
string>
.
Szablon klasy
std::future
oferuje jeszcze inne rozwizanie uatwiajce stosowanie
obiektów klasy
std::shared_future
przy uyciu nowego mechanizmu automatycznego
okrelania typu zmiennej na podstawie inicjalizatora (patrz cz A.6 dodatku A). Sza-
blon klasy
std::future
definiuje funkcj skadow
share()
, która tworzy nowy obiekt
klasy
std::shared_future
i bezporednio przenosi wasno do tego obiektu. Uycie tego
rozwizania moe nam oszczdzi sporo pisania i znacznie uatwia modyfikowanie kodu:
std::promise< std::map< SomeIndexType, SomeDataType, SomeComparator,
SomeAllocator>::iterator> p;
auto sf=p.get_future().share();
W tym przypadku typ zmiennej
sf
jest identyfikowany jako
std::shared_future<
std::map< SomeIndexType, SomeDataType, SomeComparator, SomeAllocator>::iterator>
,
czyli konstrukcja, której wielokrotne stosowanie w kodzie byoby do kopotliwe.
Poleć książkę
Kup książkę
4.3.
Oczekiwanie z limitem czasowym
115
W razie zmiany komparatora lub alokatora wystarczy zmodyfikowa typ obiektu obiet-
nicy; typ obiektu przyszoci zostanie automatycznie zaktualizowany i dostosowany do
tej zmiany.
W pewnych przypadkach dobrym rozwizaniem jest ograniczanie maksymalnego
czasu oczekiwania na zdarzenie (z uwagi na ograniczony czas dziaania okrelonej sekcji
kodu lub ze wzgldu na istnienie innych wanych zada, którymi dany wtek moe si
zaj, jeli oczekiwane zdarzenie nie wystpi odpowiednio wczenie). Z myl o takich
przypadkach wiele funkcji oczekiwania oferuje wersje z moliwoci okrelenia limitu
czasowego.
4.3.
Oczekiwanie z limitem czasowym
Wszystkie wywoania blokujce, które stosowalimy w dotychczasowych przykadach,
blokoway wykonywanie wtków przez nieokrelony czas, tj. do momentu wystpienia
oczekiwanego zdarzenia. W wielu przypadkach takie rozwizanie jest wystarczajce,
jednak w niektórych sytuacjach lepszym wyjciem jest okrelenie maksymalnego czasu
oczekiwania. Stosowanie takich limitów czasowych moe mie na celu potwierdzenie
prawidowego dziaania aplikacji (w formie komunikatu dla uytkownika lub innego
procesu) lub przerwanie oczekiwania, jeli na przykad uytkownik klikn przycisk
Anuluj.
Istniej dwa rodzaje limitów czasowych stosowanych dla operacji blokujcych: limity
okrelajce maksymalny czas blokowania wtku (na przykad 30 milisekund) oraz limity
bezwzgldne, gdzie oczekiwanie nie moe trwa duej ni do okrelonego punktu
w czasie (na przykad do godziny 17:30:15.045987023 dnia 30 listopada 2012 roku).
Wikszo funkcji oczekujcych wystpuje w wersjach obsugujcych obie formy limi-
tów czasowych. Wersje obsugujce wzgldne limity czasowe (okrelajce czas trwania
operacji) s oznaczane przyrostkiem
_for
, natomiast bezwzgldne limity czasowe ozna-
cza si przyrostkiem
_until
.
Na przykad klasa
std::condition_variable
definiuje dwie przecione wersje funk-
cji skadowej
wait_for()
i dwie przecione wersje funkcji skadowej
wait_until()
,
czyli odpowiedniki obu wersji funkcji
wait()
uzupenione o obsug wzgldnych i bez-
wzgldnych limitów czasowych — pierwsza wersja czeka na sygna, upynicie limitu
czasowego lub bezporednie budzenie; druga wersja w momencie budzenia sprawdza
przekazany predykat i zwraca sterowanie, pod warunkiem e albo ten predykat jest
prawdziwy (w wyniku sygnau umieszczonego w zmiennej warunkowej), albo osignito
limit czasowy.
Zanim przeanalizujemy szczegóowe aspekty stosowania funkcji uwzgldniajcych
limity czasowe, warto powici chwil na omówienie sposobu okrelania czasu w jzyku
C++, w tym dostpnych zegarów.
4.3.1.
Zegary
W kontekcie elementów biblioteki standardowej jzyka C++ zegar jest dla programu
ródem informacji o biecej godzinie. W szczególnoci zegar jest klas udostpnia-
jc cztery odrbne informacje:
Poleć książkę
Kup książkę
116
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
Q
bieca godzina;
Q
typ wartoci uywanych do reprezentowania godzin uzyskiwanych z obiektu
zegara;
Q
okres reprezentowany przez jeden takt zegara;
Q
to, czy takty zegara maj sta dugo, czyli moliwo traktowania zegara
jako stabilnego.
Biec godzin reprezentowan przez zegar mona uzyska, wywoujc statyczn funk-
cj skadow
now()
klasy zegara; na przykad funkcja
std::chrono::system_clock::now()
zwróci biec godzin reprezentowan przez zegar systemowy. Typ punktów w czasie
dla poszczególnych zegarów jest reprezentowany przez skadow definicj typu
time_
´
point
, zatem kada funkcja
zegar::now()
zwraca warto typu
zegar::time_point
.
Okres taktu zegara jest wyraany w formie uamka sekundy reprezentowanego
przez skadow definicj typu
period
— w przypadku zegara wykonujcego 25 taktów
w cigu sekundy
period
definiuje typ
std::ratio<1,25>
, natomiast w przypadku zegara
wykonujcego jeden takt na 2,5 sekundy skadowa
period
definiuje typ
std::ratio<5,2>
.
Jeli okrelenie okresu taktu nie jest moliwe do momentu uruchomienia programu
lub jeli ten okres moe si zmienia w czasie dziaania aplikacji, okres mona zdefi-
niowa w formie redniego czasu trwania taktu, najkrótszego moliwego taktu lub innej
wartoci przewidzianej przez twórców biblioteki. Nie mona jednak zakada, e obser-
wowany okres taktu zegara podczas jednej próby uruchomienia programu bdzie odpo-
wiada rzeczywistemu okresowi danego zegara.
Jeli takty zegara maj sta czstotliwo (niezalenie od tego, czy ta czstotli-
wo pasuje do przyjtego okresu) i jeli nie moemy zmieni dugoci taktu, mamy do
czynienia z tzw. stabilnym zegarem (ang. steady clock). Skadowa statyczna
is_steady
klasy stabilnego zegara ma warto
true
(w przypadku niestabilnego zegara ta sama ska-
dowa ma warto
false
). Zegar systemowy (reprezentowany przez klas
std::chrono::
´
system_clock
) zwykle nie jest stabilny, poniewa mona dostosowywa jego czsto-
tliwo (nawet jeli zmiany czstotliwoci s wprowadzane automatycznie z uwzgld-
nieniem przesuni wzgldem zegara lokalnego). Kada taka zmiana moe spowodo-
wa, e wywoanie funkcji
now()
zwróci warto wczeniejsz ni zwrócona przez
poprzednie wywoanie tej funkcji, co oczywicie narusza wymaganie staej czstotli-
woci zegara (i dugoci taktu). Jak si za chwil przekonasz, stabilne zegary s szcze-
gólnie przydatne podczas oblicze z uwzgldnieniem limitów czasowych — z myl
o tych i podobnych zastosowaniach twórcy biblioteki standardowej udostpnili taki
zegar w formie klasy
std::chrono::steady_clock
. Biblioteka standardowa jzyka C++
zawiera te inne klasy zegarów: wspomnian wczeniej klas
std::chrono::system_clock
,
która reprezentuje zegar „czasu rzeczywistego” w danym systemie i która udostpnia
funkcj konwersji punktów w czasie na i z wartoci typu
time_t
, oraz klas
std::
´
chrono::high_resolution_clock
, która zapewnia najkrótszy moliwy takt zegara (a wic
take najwysz moliw czstotliwo) sporód wszystkich zegarów tej biblioteki.
Drugi z zegarów mona wykorzysta w roli punktu wyjcia dla definicji alternatyw-
nych rozwiza. Wymienione zegary zdefiniowano (wraz z pozostaymi elementami
zwizanymi z obsug czasu) w pliku nagówkowym
<chrono>
.
Zanim przystpimy do omawiania metod reprezentowania punktów w czasie, warto
powici chwil analizie technik reprezentowania okresów.
Poleć książkę
Kup książkę
4.3.
Oczekiwanie z limitem czasowym
117
4.3.2.
Okresy
Okres (czas trwania) to najprostszy aspekt obsugi czasu. Okres zaimplementowano
w szablonie klasy
std::chrono::duration<>
(wszystkie elementy jzyka C++ zwizane
z obsug czasu i uywane przez bibliotek wtków nale do przestrzeni nazw
std::
´
chrono
). Pierwszy parametr tego szablonu okrela typ reprezentacji (na przykad
int
,
long
lub
double
); drugi parametr jest uamkiem okrelajcym liczb sekund repre-
zentowanych przez jednostk okresu. Na przykad liczba minut przechowywana w war-
toci typu
short
jest reprezentowana przez klas
std::chrono::duration<short,std::
´
ratio<60,1>>
, poniewa minuta skada si z 60 sekund. Liczba milisekund prze-
chowywanych w wartoci typu
double
jest reprezentowana przez klas
std::chrono::
´
duration<double,std::ratio<1,1000>>
, poniewa kada milisekunda trwa jedn
tysiczn cz sekundy.
Biblioteka standardowa oferuje zbiór predefiniowanych definicji typów w prze-
strzeni nazw
std::chrono
dla rónych okresów (wyraanych w nanosekundach, mikro-
sekundach, milisekundach, sekundach, minutach i godzinach). Wszystkie te definicje
stosuj na tyle elastyczne typy cakowitoliczbowe, e mog reprezentowa na przykad
okresy ponad 500-letnie w wybranych jednostkach czasu. Przestrze nazw zawiera
take definicje typów dla rzdów wielkoci ukadu SI: od
std::atto
(10
–18
) do
std::exa
(10
18
) (i wicej, jeli tylko dana platforma obsuguje 128-bitowe typy cakowitoliczbowe).
Za pomoc tych typów mona operowa na niestandardowych okresach, na przykad
klasa
std::duration<double,std::centi>
obsuguje liczb setnych czci sekundy repre-
zentowanych przez liczb typu
double
.
Konwersja pomidzy okresami jest wykonywana automatycznie, pod warunkiem
e nie wymaga obcicia wartoci ródowej — oznacza to, e konwersja godzin na
sekundy jest moliwa, ale ju konwersja sekund na godziny nie zostanie wykonana auto-
matycznie. Konwersj mona te wykona jawnie za pomoc funkcji
std::chrono::
´
duration_cast<>
:
std::chrono::milliseconds ms(54802);
std::chrono::seconds s=
std::chrono::duration_cast<std::chrono::seconds>(ms);
Poniewa wynik jest obcinany (nie zaokrglany), zmienna
s
bdzie zawieraa warto 54.
Okresy obsuguj dziaania arytmetyczne, zatem moemy dodawa i odejmowa
okresy, aby otrzymywa nowe okresy, bd mnoy lub dzieli okresy przez stae wybra-
nego typu danych (czyli pierwszego parametru szablonu klasy). Oznacza to, e wyraenie
5*seconds(1)
ma tak sam warto jak wyraenia
seconds(5)
i
minutes(1) – seconds(55)
.
Liczb jednostek skadajcych si na dany okres mona uzyska za pomoc funkcji
skadowej
count()
. Oznacza to, e wywoanie
std::chrono::milliseconds(1234).count()
zwróci warto
1234
.
Wymuszanie oczekiwania na podstawie okresu (czasu trwania) wymaga stosowania
instancji typu
std::chrono::duration<>
. Moemy na przykad spowodowa, e czas
oczekiwania na gotowo obiektu przyszoci wyniesie 35 milisekund:
std::future<int> f=std::async(some_task);
if(f.wait_for(std::chrono::milliseconds(35))==std::future_status::ready)
do_something_with(f.get());
Poleć książkę
Kup książkę
118
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
Wszystkie funkcje oczekiwania zwracaj status okrelajcy, czy koniec oczekiwania
wynika z wyczerpania limitu czasowego, czy z wystpienia zdarzenia, na które czeka
dany wtek. W tym przypadku wtek czeka na przyszo, zatem funkcja zwraca warto
std::future_status::timeout
w przypadku wyczerpania limitu czasowego; warto
std::future_status::ready
, jeli przyszo jest gotowa; lub warto
std::future_
´
status::deferred
, jeli zadanie przyszoci zostao odoone na póniej. Czas ocze-
kiwania okresowego jest mierzony przy uyciu stabilnego, wewntrznego zegara biblio-
teki, zatem 35 milisekund oznacza wanie 35 milisekund, nawet jeli w czasie oczekiwa-
nia zegar systemowy zostanie przestawiony (w przód lub w ty). Nie mona oczywicie
zapomina o kaprysach systemu szeregowania zada i o zrónicowanej precyzji zega-
rów systemów operacyjnych, które mog spowodowa, e rzeczywisty czas dzielcy
wywoanie funkcji
wait()
od zwrócenia sterowania bdzie duo duszy ni 35 ms.
Skoro potrafimy ju stosowa okresy, moemy przej do analizy modelu punktów
w czasie.
4.3.3.
Punkty w czasie
Punkt w czasie jest reprezentowany przez instancj szablonu klasy
std::chrono::
´
time_point<>
. Pierwszy parametr tego szablonu wskazuje zegar, natomiast drugi para-
metr okrela jednostki miary (w tej roli naley uy specjalizacji szablonu klasy
std::chrono::duration<>
). Warto punktu w czasie reprezentuje czas (w formie wielo-
krotnoci wskazanego okresu) od konkretnego punktu w czasie nazywanego epok zegara.
Epoka zegara jest prost waciwoci, która jednak nie jest bezporednio dostpna
ani wprost definiowana przez standard jzyka C++. Do najczciej stosowanych
epok naley pónoc 1 stycznia 1970 roku i moment uruchomienia komputera, na którym
dziaa dana aplikacja. Zegary mog stosowa jedn epok lub róne, niezalene epoki.
Jeli dwa zegary stosuj t sam epok, definicja typu
time_point
w klasie jednego zegara
moe wskazywa drug klas jako typ zegara powizanego z dan definicj
time_point
.
Mimo e nie mona bezporednio uzyska epoki, mamy do dyspozycji funkcj
time_
´
since_epoch()
, któr moemy wywoa dla danej instancji typu
time_point
. Funkcja
skadowa
time_since_epoch()
zwraca warto okresu reprezentujc czas od epoki zegara
do okrelonego punktu w czasie.
Punkt w czasie mona zdefiniowa na przykad w formie obiektu klasy
std::chrono::
´
time_point<std::chrono::system_clock, std::chrono::minutes>
. Tak skonstruowany
obiekt zawiera czas wzgldem zegara systemowego, tyle e mierzony w minutach (nie
wedug standardowej precyzji zegara systemowego, czyli sekund lub czci sekundy).
Na obiektach klasy
std::chrono::time_point<>
mona wykonywa operacje doda-
wania i odejmowania okresów, których wynikiem s nowe punkty w czasie. Oznacza
to, e na przykad w wyniku dodawania
std::chrono::high_resolution_clock::now()
+ std::chrono::nanoseconds(500)
otrzymamy punkt w czasie, który nastpi za 500
nanosekund (liczc od teraz). Wyraenia tego typu s przydatne podczas obliczania
bezwzgldnego limitu czasowego w sytuacji, gdy maksymalny czas wykonywania bloku
kodu jest znany z wyprzedzeniem. Takie rozwizanie wymaga jednak wielu wywoa
funkcji oczekujcych lub funkcji poprzedzajcych funkcj oczekujc i zaliczanych do
bloku, który podlega ograniczeniu czasowemu.
Poleć książkę
Kup książkę
4.3.
Oczekiwanie z limitem czasowym
119
Istnieje te moliwo odjcia jednego punktu w czasie od innego, pod warunkiem
e oba punkty bazuj na tym samym zegarze. Wynikiem tej operacji jest okres, który
reprezentuje czas dzielcy oba punkty. W ten sposób mona na przykad sprawdza czas
wykonywania bloków kodu:
auto start=std::chrono::high_resolution_clock::now();
do_something();
auto stop=std::chrono::high_resolution_clock::now();
std::cout<<”Wykonanie funkcji do_something() zajo “
<<std::chrono::duration<double,std::chrono::seconds>(stop-start).count()
<<” sekund.”<<std::endl;
Parametr zegara szablonu klasy
std::chrono::time_point<>
decyduje nie tylko o epoce.
W przypadku przekazania punktu w czasie na wejciu funkcji oczekujcej, która sto-
suje bezwzgldny limit czasowy, wybrany zegar bdzie uywany do mierzenia czasu.
Warto pamita o moliwoci zmiany wskaza zegara i o tym, e funkcja oczekujca
nie zwróci sterowania do momentu, w którym funkcja
now()
tego zegara nie zwróci
wartoci póniejszej od wskazanego limitu czasowego. Jeli zegar zostanie przesta-
wiony w przód, czny czas oczekiwania moe by krótszy (w porównaniu z czasem
mierzonym przez stabilny zegar); a jeli zegar zostanie cofnity, czny czas oczekiwa-
nia zostanie wyduony.
Jak nietrudno odgadn, punkty w czasie s uywane w wersjach funkcji oczekuj-
cych z przyrostkiem
_until
. Typowym zastosowaniem tego rozwizania jest wyznacza-
nie przesunicia wzgldem godziny zwracanej przez wywoanie
jaki-zegar
::now()
w wybranym punkcie programu. Punkty powizane z zegarem systemowym mona
uzyskiwa, konwertujc instancje typu
time_t
za pomoc statycznej funkcji skadowej
std::chrono::system_clock::to_time_point()
. Jeli na przykad maksymalny czas ocze-
kiwania na zdarzenie powizane ze zmienn warunkow wynosi 500 milisekund, mona
zastosowa konstrukcj podobn do tej z listingu 4.11.
Listing 4.11. Oczekiwanie na zmienn warunkow z uwzgldnieniem limitu
czasowego
#include <condition_variable>
#include <mutex>
#include <chrono>
std::condition_variable cv;
bool done;
std::mutex m;
bool wait_loop()
{
auto const timeout= std::chrono::steady_clock::now()+
std::chrono::milliseconds(500);
std::unique_lock<std::mutex> lk(m);
while(!done)
{
if(cv.wait_until(lk,timeout)==std::cv_status::timeout)
break;
}
return done;
}
Poleć książkę
Kup książkę
120
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
Rozwizanie z listingu 4.11 jest zalecanym sposobem oczekiwania na zmienne warun-
kowe z uwzgldnieniem limitu czasowego w sytuacji, gdy funkcja oczekujca nie
otrzymuje na wejciu adnego predykatu. Maksymalny czas wykonywania ptli jest
ograniczony. Jak napisaem w punkcie 4.1.1, jeli nie stosujemy dodatkowego predy-
katu, operowanie na zmiennych warunkowych wymaga uycia ptli, która obsuguje
nietypowe sposoby budzenia wtku. W przypadku wywoania funkcji
wait_for()
w ciele
ptli moe si zdarzy, e warunek wznowienia dziaania zostanie speniony bezpored-
nio przed upywem limitu czasowego, a w nastpnej iteracji czas oczekiwania bdzie
liczony od pocztku. Taka sytuacja moe mie miejsce wielokrotnie, zatem czny czas
oczekiwania byby nieograniczony.
Skoro dysponujemy ju podstawowymi narzdziami umoliwiajcymi stosowanie
limitów czasowych, pora omówi funkcje, w których mona uywa tych limitów.
4.3.4.
Funkcje otrzymujce limity czasowe
Najprostszym zastosowaniem limitu czasowego jest dodanie opónienia do przetwarza-
nia okrelonego wtku, tak aby ten wtek nie zajmowa czasu procesora (potrzebnego
innym wtkom) w czasie, gdy nie wykonuje adnych wartociowych zada. Przykad
takiego rozwizania opisaem w podrozdziale 4.1, gdzie kod wielokrotnie sprawdza
stan flagi gotowoci w ptli. Do opóniania dziaania (usypiania) wtków su funkcje
std::this_thread::sleep_ for()
i
std::this_thread::sleep_until()
. Obie funkcje
dziaaj jak proste budziki — wtek jest usypiany albo na okrelony okres (za pomoc
funkcji
sleep_for()
), albo do wskazanego punktu w czasie (za pomoc funkcji
sleep_
´
until()
). W przykadowych rozwizaniach z podrozdziau 4.1 naleaoby uy funkcji
sleep_for()
, poniewa w przypadku okresowo wykonywanych operacji wtek powi-
nien by wstrzymywany na pewien czas (nie do okrelonego punktu w czasie). Funkcja
sleep_until()
umoliwia planowanie budzenia wtku w okrelonym punkcie w czasie.
Funkcja
sleep_until()
moe wic suy na przykad do uruchamiania procedury two-
rzenia kopii zapasowej o pónocy, drukowania listy pac o 6 rano lub wstrzymywania
wtku do momentu wywietlenia nastpnej klatki podczas odtwarzania zapisu wideo.
Usypianie wtku to oczywicie nie jedyne zastosowanie limitów czasowych — jak
ju wspomniaem, limity tego typu mona stosowa cznie ze zmiennymi warunko-
wymi i przyszociami. Istnieje nawet moliwo stosowania limitów czasowych pod-
czas prób uzyskania blokady muteksu, jeli tylko uyty muteks obsuguje takie dziaa-
nie. Standardowe muteksy typów
std::mutex
i
std::recursive_mutex
nie obsuguj
limitów czasowych dla operacji blokowania, ale ju muteksy typów
std::timed_mutex
i
std::recursive_timed_mutex
dopuszczaj takie dziaanie. Oba te typy udostpniaj
funkcje skadowe
try_lock_for()
i
try_lock_until()
, które próbuj uzyska blokad
muteksu odpowiednio w okrelonym czasie lub przed osigniciem okrelonego punktu
w czasie. W tabeli 4.1 opisano funkcje biblioteki standardowej jzyka C++, które obsu-
guj limity czasowe, wraz z ich parametrami i typami zwracanych wartoci. W miejsce
parametru opisanego jako
okres
naley przekaza obiekt klasy
std::duration<>
, nato-
miast parametr
punkt_w_czasie
naley zastpi obiektem klasy
std::time_point<>
.
Skoro wiemy ju, jak dziaaj zmienne warunkowe, obiekty przyszoci i obietnic
oraz opakowane zadania, czas przeanalizowa te mechanizmy w nieco szerszym kon-
tekcie, w szczególnoci przyjrze si technikom upraszczania (za pomoc tych mecha-
nizmów) synchronizacji operacji wykonywanych przez róne wtki.
Poleć książkę
Kup książkę
4.4.
Upraszczanie kodu za pomoc technik synchronizowania operacji
121
Tabela 4.1.
Funkcje otrzymujce limity czasowe
Klasa lub przestrze nazw
Funkcje
Zwracane wartoci
Przestrze nazw
std::this_thread
sleep_for(okres)
sleep_until(punkt_w_czasie)
Nie dotyczy
std::condition_variable
lub
std::condition_variable_any
wait_for(blokada, okres)
wait_until(blokada,
punkt_w_czasie
)
std::cv_status::timeout
lub
std::cv_status::no_timeout
wait_for(blokada, okres,
predykat
)
wait_until(blokada,
punkt_w_czasie
, predykat)
bool
— warto zwrócona
przez
predykat
po obudzeniu
wtku.
std::timed_mutex
lub
std::recursive_timed_mutex
try_lock_for(okres)
try_lock_until
´
(punkt_w_czasie)
bool
— warto
true
,
jeli udao si uzyska blokad;
w przeciwnym razie warto
false
std::unique_lock<Typ
´
ZMoliwociBlokady
´
Czasowej
>
unique_lock
´
(typ_blokowalny, okres)
unique_lock(typ_blokowalny,
punkt_w_czasie
)
Nie dotyczy — funkcja
owns_lock()
wywoana
dla nowo skonstruowanego
obiektu zwraca warto
true
,
jeli udao si uzyska blokad
(w przeciwnym razie zwraca
warto
false
).
try_lock_for(okres)
try_lock_until
´
(punkt_w_czasie)
bool
— warto
true
, jeli
udao si uzyska blokad;
w przeciwnym razie warto
false
std::future<TypWartoci>
lub
std::shared_future<
´
TypWartoci
>
wait_for(okres)
wait_until(punkt_w_czasie)
Jeli wyczerpano limit czasu
funkcji oczekujcej, zwraca
warto
std::future_status::timeout
;
jeli obiekt przyszoci
jest gotowy, zwraca warto
std::future_status::ready
;
jeli przyszo zawiera
odroczon funkcj, która
nie zostaa jeszcze wywoana,
zwraca warto
std::future_status::deferred
.
4.4.
Upraszczanie kodu za pomoc technik
synchronizowania operacji
Stosowanie mechanizmów synchronizacji, które opisaem w poprzednich podrozdzia-
ach, w roli gotowych elementów skadowych umoliwia programicie koncentrowanie
si na samych operacjach wymagajcych synchronizacji, nie na mechanice tej synchro-
nizacji. Mechanizmy synchronizacji pozwalaj uproci kod aplikacji choby dlatego,
e wprowadzaj do wiata programowania wspóbienego duo wicej elementów zna-
nych z programowania funkcyjnego. Zamiast bezporednio wspódzieli dane pomidzy
wtkami, kade zadanie moe otrzymywa potrzebne dane, a wynik przetwarzania moe
by przekazywany do wielu innych wtków za porednictwem obiektów przyszoci.
Poleć książkę
Kup książkę
122
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
4.4.1.
Programowanie funkcyjne przy uyciu przyszoci
Termin programowanie funkcyjne (ang. functional programming — FP) odnosi si do
stylu programowania, w którym wynik wywoania funkcji zaley wycznie od para-
metrów przekazanych na jej wejciu. Oznacza to, e na wynik funkcji nie ma wpywu
zewntrzny stan. Opisane dziaanie jest wic zgodne z matematycznym pojciem funk-
cji, gdzie kade uycie jednej funkcji z tymi samymi parametrami spowoduje otrzy-
manie dokadnie takiego samego wyniku. W ten sposób dziaa wiele matematycznych
funkcji biblioteki standardowej jzyka C++, jak
sin
,
cos
czy
sqrt
, oraz prostych ope-
racji na typach podstawowych, jak
3+3
,
6*9
czy
1.3/4.7
. Typowa funkcja nie modyfi-
kuje zewntrznego stanu; skutki wykonywania tej funkcji ograniczaj si tylko do
zwracanej wartoci.
Opisany model programowania uatwia interpretacj kodu, szczególnie jeli program
zawiera elementy przetwarzania wspóbienego, poniewa wiele problemów zwizanych
z pamici wspódzielon (opisanych w rozdziale 3.) w ogóle nie wystpuje w wiecie pro-
gramowania funkcyjnego. Skoro dane wspódzielone nie s modyfikowane, nie mog wy-
stpi sytuacje wycigów, zatem ochrona tych danych za pomoc muteksów jest po prostu
niepotrzebna. Wanie prostota tego modelu powoduje, e takie jzyki programowania jak
Haskell
2
, gdzie wszystkie funkcje domylnie speniaj warunek programowania funkcyj-
nego, zyskuj coraz wiksz popularno wród programistów systemów wspóbienych.
Poniewa niemal cay kod jest zgodny z zasadami programowania funkcyjnego, nieliczne
funkcje, które modyfikuj wspódzielony stan, na tyle wyróniaj si sporód pozostaych
elementów, e mona bez trudu oceni ich udzia w caej strukturze aplikacji.
Zalety programowania funkcyjnego nie ograniczaj si tylko do jzyków, w których
ten model jest domylnym paradygmatem. Jzyk C++ czy w sobie wiele paradyg-
matów, zatem take pisanie programów wedug zasad programowania funkcyjnego
jest moliwe w tym jzyku. W wersji C++11 programowanie funkcyjne jest jeszcze
prostsze ni w standardzie C++98 dziki wprowadzeniu funkcji lambda (patrz cz A.5
dodatku A), integracji funkcji
std::bind
zaczerpnitej z biblioteki Boost i dokumentu
TR1 oraz dodaniu automatycznego wnioskowania typów zmiennych (patrz cz A.7
dodatku A). Ostatnim elementem, który uatwia programowanie funkcyjne w jzyku
C++, s obiekty przyszoci — obiekt przyszoci mona przekazywa pomidzy
wtkami, tak aby wynik jednej operacji móg zalee od wyniku innej operacji i aby ta
zaleno nie wymagaa bezporedniego dostpu do wspódzielonych danych.
S
ZYBKIE SORTOWANIE W MODELU PROGRAMOWANIA FUNKCYJNEGO
Aby lepiej zrozumie moliwe zastosowania przyszoci w modelu programowania funk-
cyjnego, przeanalizujmy prost implementacj algorytmu sortowania szybkiego (ang.
quicksort). Podstawowa koncepcja tego algorytmu jest do prosta — naley z listy
wartoci wybra element dzielcy, osiowy (ang. pivot), po czym podzieli list na dwa
zbiory, z których jeden zawiera elementy mniejsze od elementu dzielcego, a drugi
zawiera elementy wiksze od wybranego elementu. Posortowana kopia listy jest uzyski-
wana poprzez sortowanie obu podzbiorów i poczenie odpowiednio posortowanej listy
zoonej z wartoci mniejszych od elementu dzielcego, samego elementu dzielcego
2
Patrz http://www.haskell.org/.
Poleć książkę
Kup książkę
4.4.
Upraszczanie kodu za pomoc technik synchronizowania operacji
123
i posortowanej listy wikszej od elementu dzielcego. Przykad sortowania listy dziesiciu
liczb cakowitych wedug opisanego schematu pokazano na rysunku 4.2. Na listingu 4.12
pokazano sekwencyjn implementacj tego algorytmu opracowan zgodnie z zasadami
programowania funkcyjnego; funkcja
sequential_quick_sort()
otrzymuje list i zwraca
jej posortowan kopi przez warto (zamiast sortowa list przekazan przez referen-
cj, jak w przypadku funkcji
std::sort()
).
Rysunek 4.2.
Rekurencyjne sortowanie w modelu programowania funkcyjnego
Listing 4.12. Sekwencyjna implementacja algorytmu sortowania szybkiego
template<typename T>
std::list<T> sequential_quick_sort(std::list<T> input)
{
if(input.empty())
{
return input;
}
std::list<T> result;
result.splice(result.begin(),input,input.begin());
T const& pivot=*result.begin();
auto divide_point=std::partition(input.begin(),input.end(),
[&](T const& t){return t<pivot;});
std::list<T> lower_part;
lower_part.splice(lower_part.end(),input,input.begin(),
divide_point);
auto new_lower(
sequential_quick_sort(std::move(lower_part)));
auto new_higher(
sequential_quick_sort(std::move(input)));
result.splice(result.end(),new_higher);
result.splice(result.begin(),new_lower);
return result;
}
Poleć książkę
Kup książkę
124
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
Mimo e zewntrzny interfejs tej implementacji jest zgodny z reguami programowania
funkcyjnego, wewntrzne mechanizmy zaimplementowano w „tradycyjny” sposób,
poniewa konsekwentne stosowanie modelu funkcyjnego wymagaoby wielu dodatko-
wych operacji kopiowania. W roli elementu dzielcego jest wybierany pierwszy element,
który jest wyodrbniany z listy za pomoc funkcji
splice()
. Chocia sortowanie na
bazie tak wybranego elementu dzielcego moe nie by optymalne (liczba operacji
porównania i wymiany moe by wiksza, ni to konieczne), pozostae operacje na
strukturze typu
std::list
bd wykonywane szybciej dziki efektywnemu przeszu-
kiwaniu listy. Wiadomo, e wyodrbniony element dzielcy musi si znale na licie
wynikowej, zatem jest od razu umieszczany w odpowiedniej strukturze. Poniewa
element dzielcy bdzie teraz porównywany z pozostaymi elementami, przekazujemy
referencj do tego elementu, aby unikn wielokrotnego kopiowania . Moemy nastp-
nie uy funkcji
std::partition
do podzielenia sekwencji na wartoci mniejsze od
elementu dzielcego i wartoci nie mniejsze od tego elementu . Najprostszym spo-
sobem okrelenia kryterium podziau jest uycie funkcji lambda — aby unikn kopio-
wania wartoci elementu dzielcego, zastosowano tutaj technik przechwytywania refe-
rencji (wicej informacji na temat funkcji lambda mona znale w czci A.5 dodatku A).
Funkcja
std::partition()
przetwarza przekazan list i zwraca iterator wskazujcy
pierwszy element, który nie jest mniejszy od wartoci elementu dzielcego. Kompletny
typ iteratora moe by do dugi, zatem w powyszym kodzie uyto mechanizmu auto-
matycznej identyfikacji typów, aby to kompilator automatycznie okreli odpowiedni
typ (patrz cz A.7 dodatku A).
Poniewa analizowana implementacja udostpnia interfejs zgodny z zasadami pro-
gramowania funkcyjnego, warunkiem rekurencyjnego posortowania obu „poówek” listy
jest utworzenie dwóch odrbnych list. Do tego celu moemy ponownie uy funkcji
splice()
, aby skopiowa wartoci z listy wejciowej (do elementu
divide_point
) i umie-
ci na nowej licie:
lower_part
. Reszta wartoci pozostanie na licie wejciowej.
Obie listy mona nastpnie posortowa za pomoc rekurencyjnych wywoa funkcji
sequential_quick_sort()
. Uycie funkcji
std::move()
podczas przekazywania
list na wejciu rekurencyjnych wywoa pozwala unikn kopiowania tych struktur
(wyniki obu wywoa s kopiowane automatycznie). I wreszcie moemy ponownie uy
funkcji
splice()
w celu uporzdkowania list reprezentujcych podzbiory elementów
oryginalnej struktury. Wartoci z listy
new_higher
trafiaj na koniec listy wynikowej
(za element dzielcy), natomiast wartoci z listy
new_lower
s umieszczane na pocztku
listy (przed elementem dzielcym).
S
ZYBKIE SORTOWANIE RÓWNOLEGE W MODELU PROGRAMOWANIA FUNKCYJNEGO
Poniewa ju w poprzednim przykadzie zastosowano reguy programowania funkcyj-
nego, konwersja tego algorytmu na wersj równoleg (korzystajc z obiektów przy-
szoci) nie jest specjalnie trudna (patrz listing 4.13). Zbiór operacji jest taki sam jak
w poprzedniej wersji, tyle e teraz cz tych operacji jest wykonywana równolegle.
W tej wersji uyto implementacji algorytmu sortowania szybkiego czcej obiekty przy-
szoci i model programowania funkcyjnego.
Jedn z najwaniejszych rónic dzielcych obie wersje jest to, e w wersji wspó-
bienej cz listy sprzed elementu dzielcego nie jest sortowana w biecym wtku,
tylko w dodatkowym wtku — w tym celu zastosowano funkcj
std::async()
. Druga
Poleć książkę
Kup książkę
4.4.
Upraszczanie kodu za pomoc technik synchronizowania operacji
125
Listing 4.13. Równolege sortowanie szybkie z wykorzystaniem przyszoci
template<typename T>
std::list<T> parallel_quick_sort(std::list<T> input)
{
if(input.empty())
{
return input;
}
std::list<T> result;
result.splice(result.begin(),input,input.begin());
T const& pivot=*result.begin();
auto divide_point=std::partition(input.begin(),input.end(),
[&](T const& t){return t<pivot;});
std::list<T> lower_part;
lower_part.splice(lower_part.end(),input,input.begin(),
divide_point);
std::future<std::list<T> > new_lower(
std::async(¶llel_quick_sort<T>,std::move(lower_part)));
auto new_higher(
parallel_quick_sort(std::move(input)));
result.splice(result.end(),new_higher);
result.splice(result.begin(),new_lower.get());
return result;
}
cz listy jest sortowana tak jak w poprzedniej wersji, a wic przy uyciu bezpored-
niego wywoania rekurencyjnego . Rekurencyjne wywoanie funkcji
parallel_quick_
´
sort()
pozwala wykorzysta dostpn wspóbieno sprztow. Jeli wywoanie
funkcji
std::async()
za kadym razem uruchamia nowy wtek, wystarcz trzy poziomy
rekurencji, aby program zosta podzielony na osiem wtków; w przypadku dziesiciu
poziomów rekurencji (czyli okoo tysica elementów) program w tej formie uruchomi
1024 wtki (o ile stosowany sprzt poradzi sobie z tak liczb). W razie wykrycia zbyt
duej liczby uruchomionych zada (jeli na przykad liczba równolegle realizowanych
zada przekroczy dostpn wspóbieno sprztow) biblioteka moe przej w tryb
synchronicznego uruchamiania nowych zada. Zadania bd wykonywane w wtku
wywoujcym funkcj
get()
, nie w nowym wtku, zatem program uniknie kosztów prze-
kazywania zadania pomidzy wtkami, jeli koszty tej operacji nie s rekompensowane
przez wzrost wydajnoci. Jeli nie przekazano wprost wartoci
std::launch::deferred
,
uruchamianie nowego wtku dla kadego zadania jest w peni zgodne z zaoeniami
implementacji
std::async
(nawet jeli prowadzi do nadsubskrypcji); podobnie jeli
nie przekazano wartoci
std::launch::async
, najlepszym rozwizaniem jest synchro-
niczne wykonywanie wszystkich zada. W przypadku stosowania biblioteki oferujcej
mechanizmy automatycznego skalowania warto sprawdzi w dokumentacji, jak te mecha-
nizmy bd dziaay w kontekcie tego algorytmu.
Zamiast funkcji
std::async()
moglibymy uy wasnej funkcji
spawn_task()
w roli
prostego opakowania szablonu klasy
std::packaged_task
i klasy
std::thread
(patrz
Poleć książkę
Kup książkę
126
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
listing 4.14). W takim przypadku naleaoby utworzy obiekt klasy
std::packaged_task
dla wyniku wywoania funkcji, odczyta obiekt przyszoci z obiektu zadania, uruchomi
zadanie w odpowiednim wtku, po czym zwróci obiekt przyszoci. Takie rozwiza-
nie samo w sobie nie przyniosoby co prawda adnych korzyci (prowadzioby raczej
do duej nadsubskrypcji), ale moe stanowi punkt wyjcia dla bardziej zaawansowa-
nych implementacji, które bd dodaway zadania do kolejki w celu przetworzenia
przez wtki robocze dostpne w puli. Zagadnienia zwizane z pulami wtków zostan
omówione w rozdziale 9. Wybór tego kierunku (zamiast stosowania funkcji
std::async
)
jest uzasadniony tylko w przypadku programistów, którzy maj pen wiadomo
skutków podejmowanych dziaa i chc mie pen kontrol nad sposobem budowy
puli wtków i wykonywania zada.
Listing 4.14. Prosta implementacja funkcji spawn_task
template<typename F,typename A>
std::future<std::result_of<F(A&&)>::type>
spawn_task(F&& f,A&& a)
{
typedef std::result_of<F(A&&)>::type result_type;
std::packaged_task<result_type(A&&)>
task(std::move(f)));
std::future<result_type> res(task.get_future());
std::thread t(std::move(task),std::move(a));
t.detach();
return res;
}
Wrómy teraz do funkcji
parallel_quick_sort()
. Poniewa do uzyskania listy
new_higher
uylimy bezporedniego wywoania rekurencyjnego, moemy uy funkcji
splice()
tak jak w algorytmie jednowtkowym . Okazuje si jednak, e zmienna
new_lower
zawiera obiekt klasy
std::future<std::list<T>>
, nie list, zatem przed wywoaniem
funkcji
splice()
musimy wywoa funkcj
get()
, aby uzyska odpowiedni warto .
Wywoanie w tej formie czeka na zakoczenie zadania wykonywanego w tle, po czym
przenosi wynik do wywoania funkcji
splice()
. Funkcja
get()
zwraca referencj do
r-wartoci wyniku, zatem lista moe zosta przeniesiona (wicej informacji na temat
referencji do r-wartoci i operacji przenoszenia mona znale w czci A.1.1 dodatku A).
Nawet jeli przyj, e funkcja
std::async()
w optymalny sposób wykorzystuje
dostpn wspóbieno sprztow, proponowana implementacja równolegego algorytmu
sortowania szybkiego wci nie jest optymalna. Funkcja
std::partition
realizuje co
prawda znaczn cz zada zwizanych z dziaaniem tego algorytmu, ale jej wywoanie
ma charakter typowo sekwencyjny. Czytelnicy zainteresowani moliwie najszybsz, rów-
noleg implementacj powinni sign po odpowiedni literatur akademick.
Programowanie funkcyjne nie jest jedynym paradygmatem programowania wspó-
bienego eliminujcym problem wspódzielenia zmiennych danych; innym przykadem
takiego paradygmatu jest komunikacja procesów sekwencyjnych (ang. Communicating
Sequential Processes — CSP)
3
, gdzie wtki s w zaoeniu cakowicie niezalene i nie
3
C.A.R. Hoare, Communicating Sequential Processes, Prentice Hall, 1985. Ksika jest dostpna za darmo
pod adresem http://www.usingcsp.com/cspbook.pdf.
Poleć książkę
Kup książkę
4.4.
Upraszczanie kodu za pomoc technik synchronizowania operacji
127
operuj na wspódzielonych danych — zamiast tego wymieniaj komunikaty za pored-
nictwem kanaów komunikacyjnych. Paradygmat CSP zastosowano w jzyku progra-
mowania Erlang (http://www.erlang.org/) oraz w rodowisku MPI (od ang. Message
Passing Interface) stosowanym w systemach implementowanych w jzykach C i C++,
które musz gwarantowa najwysz wydajno (http://www.mpi-forum.org/). Po tym,
co ju napisaem, jestem pewien, e wiadomo o moliwoci implementacji tego para-
dygmatu take w jzyku C++ nie bdzie dla czytelnika adnym zaskoczeniem — wystar-
czy odrobina dyscypliny. Sposób implementacji tego modelu omówi w nastpnym
punkcie.
4.4.2.
Synchronizacja operacji za pomoc przesyania komunikatów
Koncepcja paradygmatu CSP jest prosta — nie istniej adne wspódzielone dane,
a kady wtek mona traktowa jako zupenie niezaleny byt. Zachowanie wtku zaley
wycznie od komunikatów, które do niego trafiaj. Kady wtek jest wic swoist
maszyn stanów, która po otrzymaniu komunikatu aktualizuje swój stan i która moe
(ale nie musi) wysa co najmniej jeden komunikat do pozostaych wtków. Sposób prze-
twarzania komunikatu zaley od stanu pocztkowego „maszyny”. Jednym ze sposobów
pisania wtków tego typu jest stworzenie formalnego modelu i implementacja sko-
czonej maszyny stanów, jednak istniej te lepsze rozwizania — do wyraenia maszyny
stanów mona uy odpowiedniej struktury aplikacji. To, która metoda sprawdza si
lepiej w danym scenariuszu, zaley od szczegóowych wymaga dotyczcych zachowa
budowanego systemu i od umiejtnoci zespou programistów. Jeli jednak zdecydu-
jemy si na implementacj odrbnych wtków, sam podzia na niezalene procesy
moe prowadzi do wyeliminowania wielu komplikacji zwizanych ze wspóbienym
przetwarzaniem danych wspódzielonych i tym samym uatwi programowanie oraz
ograniczy liczb bdów.
Procesy w peni zgodne z paradygmatem CSP nie operuj na adnych wspódzie-
lonych danych, a caa komunikacja odbywa si za porednictwem kolejek komunikatów.
Poniewa jednak wtki jzyka C++ wspódziel przestrze adresow, wymuszenie
tego wymagania jest niemoliwe. W tej sytuacji bardzo due znaczenie ma dyscyplina
autorów aplikacji i bibliotek, poniewa to od nas zaley, czy nasze wtki bd si odwo-
ywa do wspódzielonych danych. Same kolejki komunikatów oczywicie musz by
wspódzielone (w przeciwnym razie wtki nie mogyby si komunikowa), jednak szcze-
góy implementacji tych kolejek mona opakowa w ramach bibliotek.
Wyobramy sobie, e implementujemy kod dla bankomatu. Kod tego systemu musi
obsugiwa interakcj z uytkownikiem, czyli osob wypacajc gotówk, musi komu-
nikowa si z systemem odpowiedniego banku oraz musi sterowa fizycznymi urz-
dzeniami odpowiedzialnymi za akceptacj karty, wywietlanie stosownych komunika-
tów, obsug klawiatury, wypat pienidzy i zwracanie karty.
Jednym ze sposobów obsugi wszystkich tych zada jest podzielenie kodu na trzy
niezalene wtki: jeden obsugujcy fizyczne urzdzenia, drugi implementujcy logik
samego bankomatu i trzeci odpowiedzialny za komunikacj z bankiem. Wtki mog si
komunikowa wycznie poprzez przekazywanie komunikatów (nie poprzez wspó-
dzielenie jakichkolwiek danych). Na przykad wtek obsugujcy fizyczne urzdzenia
mógby wysa do wtku logiki bankomatu komunikat o woeniu karty lub naciniciu
Poleć książkę
Kup książkę
128
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
przycisku przez uytkownika, natomiast wtek logiki mógby wysa do wtku obsu-
gujcego fizyczne urzdzenia komunikat okrelajcy kwot do wypacenia.
Jednym ze sposobów modelowania logiki bankomatu jest opracowanie maszyny
stanów. W kadym stanie wtek oczekuje na okrelony komunikat, który jest nastp-
nie odpowiednio przetwarzany. W wyniku przetwarzania tego komunikatu wtek moe
przej w nowy stan i kontynuowa cay cykl. Stany skadajce si na t prost imple-
mentacj pokazano na rysunku 4.3. W tej uproszczonej implementacji system oczekuje
na umieszczenie karty w bankomacie. Po woeniu karty system czeka, a uytkownik
wpisze kod PIN, naciskajc kolejno cyfry tego kodu. Uytkownik moe usun ostat-
ni wpisan cyfr. Po wpisaniu odpowiedniej liczby cyfr system weryfikuje kod PIN.
Jeli PIN jest nieprawidowy, cykl dziaania koczy si — bankomat zwraca kart i prze-
chodzi w stan oczekiwania na wsunicie karty przez klienta. Jeli kod PIN jest prawi-
dowy, system czeka na anulowanie transakcji albo na wybór kwoty do wypacenia.
W razie anulowania transakcji cykl pracy bankomatu koczy si i urzdzenie zwraca
kart. Jeli klient wybra kwot, przed wypaceniem gotówki system czeka na potwier-
dzenie ze strony banku, po czym albo wypaca gotówk, albo wywietla komunikat
„brak rodków” i (niezalenie od wyniku weryfikacji stanu konta) wysuwa kart. Sys-
temy prawdziwych bankomatów s oczywicie bardziej skomplikowane, jednak opisana
powyej maszyna stanów dobrze ilustruje istot tego rozwizania.
Rysunek 4.3.
Prosty model maszyny stanów dla bankomatu
Po zaprojektowaniu maszyny stanów dla logiki bankomatu moemy przystpi do imple-
mentacji tego rozwizania w formie klasy, która bdzie definiowaa po jednej funkcji
skadowej dla kadego stanu. Kada funkcja skadowa moe czeka na okrelony zbiór
komunikatów przychodzcych i odpowiednio obsugiwa te komunikaty (obsuga moe
polega na przechodzeniu do innego stanu). Kady typ komunikatów jest reprezentowany
Poleć książkę
Kup książkę
4.4.
Upraszczanie kodu za pomoc technik synchronizowania operacji
129
przez odrbn struktur. Na listingu 4.15 pokazano fragment prostej implementacji
logiki takiego systemu, w tym gówn ptl oraz implementacj pierwszego stanu, w któ-
rym system oczekuje na woenie karty.
Listing 4.15. Prosta implementacja klasy logiki systemu bankomatu
struct card_inserted
{
std::string account;
};
class atm
{
messaging::receiver incoming;
messaging::sender bank;
messaging::sender interface_hardware;
void (atm::*state)();
std::string account;
std::string pin;
void waiting_for_card()
{
interface_hardware.send(display_enter_card());
incoming.wait()
.handle<card_inserted>(
[&](card_inserted const& msg)
{
account=msg.account;
pin="";
interface_hardware.send(display_enter_pin());
state=&atm::getting_pin;
}
);
}
void getting_pin();
public:
void run()
{
state=&atm::waiting_for_card;
try
{
for(;;)
{
(this->*state)();
}
}
catch(messaging::close_queue const&)
{
}
}
};
Jak wida, wszystkie niezbdne operacje zwizane z synchronizacj przekazywania
komunikatów zostay ukryte w odpowiedniej bibliotece (implementacja tej biblioteki
zostanie pokazana w dodatku C wraz z kompletnym kodem tego przykadu).
Poleć książkę
Kup książkę
130
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
Jak ju wspomniaem, opisana tutaj implementacja jest mocno uproszczona w sto-
sunku do logiki obowizujcej w prawdziwych bankomatach, jednak przykad w tej
formie wystarczy do zrozumienia stylu programowania na bazie przekazywania komu-
nikatów. Nie musimy traci czasu na projektowanie synchronizacji i rozwizywanie
problemów zwizanych z przetwarzaniem wspóbienym — wystarczy ustali, jakie
komunikaty mog by odbierane i przetwarzane na poszczególnych etapach oraz które
komunikaty naley wysya. Maszyna stanów logiki bankomatu jest przetwarzana przez
jeden wtek; pozostae elementy systemu, jak interfejs czcy si z bankiem czy interfejs
terminala, s obsugiwane przez odrbne wtki. Ten styl projektowania oprogramowania
okrela si mianem modelu aktorów — w systemie istnieje wiele odrbnych aktorów
(kady dziaa w osobnym wtku), które wymieniaj pomidzy sob komunikaty niezbdne
do realizacji swoich zada. W modelu aktorów nie istnieje wspódzielony stan (wyjtkiem
jest mechanizm potrzebny do bezporedniego przekazywania komunikatów).
Dziaanie programu rozpoczyna si od funkcji skadowej
run()
, która ustawia
stan pocztkowy, czyli
waiting_for_card
, po czym wielokrotnie wywouje funkcj
skadow reprezentujc biecy stan (niezalenie od tego, który to stan). Funkcje
stanów maj posta prostych funkcji skadowych klasy
atm
. Take funkcja stanu
waiting_for_card
jest do prosta — jej dziaanie ogranicza si do wysania komu-
nikatu do interfejsu w celu wywietlenia na ekranie tekstu Czekam na kart ; zaraz
potem funkcja rozpoczyna oczekiwanie na komunikat do obsuenia . Jedynym rodza-
jem komunikatów, który moe by obsugiwany w tej czci kodu, jest komunikat
card_inserted
. Do jego obsugi uywamy funkcji lambda . Na wejciu funkcji
handle
mona przekaza dowoln funkcj lub dowolny obiekt funkcji, jednak najprostszym
rozwizaniem jest uycie funkcji lambda. atwo zauway, e wywoanie funkcji
handle()
znalazo si w acuchu obejmujcym wywoanie funkcji
wait()
, zatem w razie otrzy-
mania komunikatu, który nie pasuje do wskazanego typu, wtek zignoruje ten komu-
nikat i bdzie dalej czeka na komunikat waciwego typu.
Sama funkcja lambda zapisuje numer konta w zmiennej skadowej, zeruje biecy
kod PIN, wysya komunikat do sprztu odpowiedzialnego za obsug interfejsu ban-
komatu, aby wywietli prob o podanie kodu PIN, po czym przechodzi w stan po-
bierania tego kodu. Po zakoczeniu dziaania przez funkcj obsugujc komunikat
funkcja stanu zwraca sterowanie, a gówna ptla programu wywouje funkcj nowego
stanu .
Funkcja stanu
getting_pin
jest nieco bardziej skomplikowana, poniewa moe obsu-
giwa trzy róne typy komunikatów (patrz rysunek 4.3). Kod tej funkcji pokazano na
listingu 4.16.
Listing 4.16. Funkcja stanu getting_pin na potrzeby prostej implementacji systemu
bankomatu
void atm::getting_pin()
{
incoming.wait()
.handle<digit_pressed>(
[&](digit_pressed const& msg)
{
unsigned const pin_length=4;
pin+=msg.digit;
if(pin.length()==pin_length)
Poleć książkę
Kup książkę
4.5.
Podsumowanie
131
{
bank.send(verify_pin(account,pin,incoming));
state=&atm::verifying_pin;
}
}
)
.handle<clear_last_pressed>(
[&](clear_last_pressed const& msg)
{
if(!pin.empty())
{
pin.resize(pin.length()-1);
}
}
)
.handle<cancel_pressed>(
[&](cancel_pressed const& msg)
{
state=&atm::done_processing;
}
);
}
Tym razem funkcja musi przetwarza trzy róne typy komunikatów, zatem acuch
wywoania funkcji
wait()
obejmuje a trzy wywoania funkcji
handle()
. Kade
wywoanie funkcji
handle()
okrela typ komunikatu w formie parametru szablonu, po
czym przekazuje funkcj lambda, która otrzymuje na wejciu komunikat okrelonego
typu. Poniewa wszystkie te wywoania umieszczono w jednym acuchu wywoa,
implementacja funkcji
wait()
„wie”, e czeka na komunikat
digit_pressed
,
clear_
´
last_pressed
lub
cancel_pressed
. Komunikaty wszystkich innych typów bd (tak
jak wczeniej) ignorowane.
W tym przypadku otrzymanie komunikatu nie musi prowadzi do zmiany stanu.
Jeli na przykad wtek otrzyma komunikat
digit_pressed
i jeli wpisana cyfra nie bdzie
ostatni cyfr kodu, wystarczy t cyfr dopisa do acucha
pin
. Gówna ptla na
listingu 4.15 ponownie wywoa funkcj
getting_pin()
, aby czeka na nastpn cyfr
(bd wyzerowa kod PIN lub anulowa ca operacj).
Opisana procedura jest zgodna ze schematem pokazanym na rysunku 4.3. Kady
stan przedstawiony na tym rysunku jest implementowany przez inn funkcj skadow,
która czeka na odpowiednie komunikaty i na tej podstawie aktualizuje stan systemu.
Jak wida, opisany styl programowania moe znacznie uproci zadanie projekto-
wania systemu wspóbienego, poniewa kady wtek mona traktowa cakowicie
niezalenie od pozostaych. W opisanym modelu wiele wtków ma za zadanie oddzie-
lanie zagadnie i jako takie wymagaj od projektanta jasnych decyzji o podziale zada
pomidzy wtki.
4.5.
Podsumowanie
Synchronizacja operacji pomidzy wtkami jest wanym aspektem pisania aplikacji
stosujcej techniki przetwarzania wspóbienego — w razie braku synchronizacji wtki
dziaayby cakowicie niezalenie, zatem równie dobrze mogyby mie posta odrbnych
aplikacji uruchamianych w formie pewnej grupy (z racji pokrewnych zada). W tym
Poleć książkę
Kup książkę
132
R
OZDZIA
4.
Synchronizacja wspóbienych operacji
rozdziale omówiem rozmaite sposoby synchronizacji operacji, w tym podstawowe
zmienne warunkowe, przyszoci, obietnice i opakowywane zadania. Opisaem te spo-
soby rozwizywania problemów zwizanych z synchronizacj, w szczególnoci pro-
gramowanie funkcyjne, gdzie kade zadanie generuje wynik wycznie na podstawie
danych wejciowych (nie uwzgldnia zewntrznego rodowiska), oraz przekazywanie
komunikatów, gdzie komunikacja pomidzy wtkami odbywa si za porednictwem
asynchronicznych komunikatów (wysyanych przy uyciu podsystemu przekazywania
komunikatów).
Skoro omówiem ju wiele wysokopoziomowych rozwiza dostpnych w jzyku
C++, czas przyjrze si odpowiednim elementom niskopoziomowym, dziki którym
opisane mechanizmy mog funkcjonowa — w nastpnym rozdziale skoncentrujemy si
na modelu pamici jzyka C++ i operacjach atomowych.
Poleć książkę
Kup książkę
Skorowidz
A
accumulate_block, 293, 294
add_to_list(), 61
add_to_reclaim_list(), 239
aktywne oczekiwanie, 261
algorytm sortowania szybkiego, 330
analiza kodu, 357
próba szczegóowego wyjanienia komu, 358
przegldanie kodu, 357
pytania dotyczce przegldanego kodu, 358
asynchroniczne zadanie, 104
B
bariera, 316
bariery pamici, Patrz ogrodzenia
biblioteki jzyka C++, 29
ACE, 29
Boost, 29
Boost Thread Library, 30
C++ Thread Library, 30
efektywno klas, 30
mechanizm przyszoci, 103
okres, 117
przyszoci unikatowe, 103
przyszoci wspódzielone, 103
punkt w czasie, 118
RAII, 29
standardowa, 31
typy wywoywalne, 36
wolne funkcje, 150
zegar, 115
blokady wirujce, 221
bdzenie, Patrz uwizienie
Boost Thread Library, 30
buffer, 44
C
C++ Thread Library, 30
clear(), 138, 141
compare_exchange_strong(), 140, 144, 236, 248,
263
compare_exchange_weak(), 140, 144, 225, 247
D
data.push(), 188
data_cond.notify_one(), 191
definicja klasy stosu, 68
delete_nodes_with_no_hazards(), 238, 240
detach(), 38, 42
dispatch(), 405
do_something(), 63
do_sort(), 275, 333
done(), 110
Double-Checked Locking, 85
drzewo binarne, 209
dyndajcy wskanik, 226
Poleć książkę
Kup książkę
564
Skorowidz
E
empty(), 64, 102, 188
exchange(), 140, 143
F
faszywe wspódzielenie, 284, 287
fetch_add(), 140, 146, 249
fetch_and(), 147
fetch_or(), 140, 147
fetch_sub(), 146, 176
fetch_xor(), 147
find_entry_for(), 212
find_first_if(), 217
for_each(), 213, 216
frameworki aplikacji, 29
MFC, 29
free_external_counter(), 260
front(), 98
funkcja lambda, 122
funkcja pocztkowa, 33
funkcje
accumulate_block, 293, 294
add_to_list(), 61
add_to_reclaim_list(), 239
clear(), 138, 141
compare_exchange_strong(), 140, 144, 236,
248, 263
compare_exchange_weak(), 140, 144, 225, 247
constexpr, 381
wymagania, 385
data.push(), 188
data_cond.notify_one(), 191
delete_nodes_with_no_hazards(), 238, 240
detach(), 38, 42
dispatch(), 405
do_something(), 63
do_sort(), 275, 333
domylne, 377
dokumentacja, 378
wymuszanie generowania funkcji, 378
wymuszenie deklarowania konstruktora
kopiujcego, 378
wymuszenie generowania destruktora
wirtualnego, 378
zmiana dostpnoci funkcji, 378
done(), 110
empty(), 64, 102, 188
exchange(), 140, 143
fetch_add(), 140, 146, 249
fetch_and(), 147
fetch_or(), 140, 147
fetch_sub(), 146, 176
fetch_xor(), 147
find_entry_for(), 212
find_first_if(), 217
foo<int&>(), 375
for_each(), 213, 216
free_external_counter(), 260
front(), 98
get(), 125
get_event(), 301
get_future(), 106, 114
get_hazard_pointer_for_current_thread(), 234,
236
get_id(), 52
get_lock(), 80
get_tail(), 200
getting_pin(), 130
handle(), 130, 407
head.get(), 197
hello(), 33
interrupt(), 340, 342, 349
interruptible_wait(), 343, 348
interruption_point(), 341, 344, 351
is_lock_free(), 138
joinable(), 295
lambda, 386
wyraenie lambda, 386
z konstrukcj rozpoczynajc, 388
list_contains(), 61
load(), 140, 143
lock(), 60, 79, 80, 142
main(), 33, 36
memcmp(), 148
memcpy(), 148
my_thread, 37
my_x.do_lengthy_work(), 45
native_handle(), 32
nieskadowe, 150
notify_one(), 96
now(), 116
open_connection(), 87
parallel_accumulate(), 291, 296, 329
parallel_quick_sort(), 126, 275
pocztkowa, 33
pop(), 64, 188, 226, 228, 235, 245, 247, 254,
257, 261
pop_head(), 205
pop_task_from_other_thread_queue(), 339
process(), 82, 301
Poleć książkę
Kup książkę
Skorowidz
565
process_connections(), 110
process_data(), 81
push(), 64, 100, 191, 197, 201, 225, 229, 247,
254, 255, 261, 337
push_front(), 216
reclaim_later(), 236, 238, 239
remove_if(), 217
run(), 130
run_pending_task(), 331, 335
send_data(), 87
sequential_quick_sort(), 124
set(), 343
set_condition_variable(), 344
set_exception(), 111
set_new_tail(), 264
share(), 114
size(), 64
sleep_for(), 120
sleep_until(), 120
some_function, 47
spawn_task(), 125
splice(), 124
square_root(), 111
std::accumulate, 49
std::async(), 104, 125, 273, 281, 297
std::atomic_compare_exchange_strong, 469
std::atomic_compare_exchange_strong_explicit,
469
std::atomic_compare_exchange_weak, 470
std::atomic_compare_exchange_weak_explicit,
471
std::atomic_exchange, 467
std::atomic_exchange_explicit, 467
std::atomic_fetch_add, 476, 486
std::atomic_fetch_add_explicit, 476, 486
std::atomic_fetch_and, 478
std::atomic_fetch_and_explicit, 479
std::atomic_fetch_or, 479
std::atomic_fetch_or_explicit, 480
std::atomic_fetch_sub, 477, 487
std::atomic_fetch_sub_explicit, 478, 487
std::atomic_fetch_xor, 480
std::atomic_fetch_xor_explicit, 481
std::atomic_flag_clear, 459
std::atomic_flag_clear_explicit, 460
std::atomic_flag_test_and_set, 459
std::atomic_flag_test_and_set_explicit, 459
std::atomic_flag::clear, 459
std::atomic_flag::test_and_set, 458
std::atomic_init, 463
std::atomic_is_lock_free, 464
std::atomic_load, 465
std::atomic_load_explicit, 465
std::atomic_signal_fence(), 457
std::atomic_store, 466
std::atomic_store_explicit, 466
std::atomic_thread_fence(), 456
std::atomic<t*>::fetch_add, 486
std::atomic<t*>::fetch_sub, 487
std::atomic<typ-
cakowitoliczbowy>::fetch_add, 476
std::atomic<typ-
cakowitoliczbowy>::fetch_and, 478
std::atomic<typ-cakowitoliczbowy>::fetch_or,
479
std::atomic<typ-
cakowitoliczbowy>::fetch_sub, 477
std::atomic<typ-
cakowitoliczbowy>::fetch_xor, 480
std::atomic::compare_exchange_strong, 468
std::atomic::compare_exchange_weak, 469
std::atomic::exchange, 467
std::atomic::is_lock_free, 464
std::atomic::load, 464
std::atomic::store, 466
std::bind(), 45, 333
std::call_once, 86
std::chrono::duration_cast, 428
std::chrono::duration::count, 423
std::chrono::duration::max, 426
std::chrono::duration::min, 426
std::chrono::duration::zero, 425
std::chrono::steady_clock::now, 434
std::chrono::system_clock::from_time_t, 433
std::chrono::system_clock::now, 432
std::chrono::system_clock::to_time_t, 433
std::chrono::time_point::max, 431
std::chrono::time_point::min, 431
std::chrono::time_point::time_since_epoch, 430
std::condition_variable_any::notify_all, 446
std::condition_variable_any::notify_one, 446
std::condition_variable_any::wait, 447
std::condition_variable_any::wait_for, 448
std::condition_variable_any::wait_until, 450
std::condition_variable::notify_all, 437
std::condition_variable::notify_one, 437
std::condition_variable::wait, 344, 438
std::condition_variable::wait_for, 439
std::condition_variable::wait_until, 441
std::copy_exception(), 112
std::current_exception(), 112
std::find, 306
Poleć książkę
Kup książkę
566
Skorowidz
funkcje
std::for_each, 51, 304
std::future::get, 494
std::future::share, 492
std::future::valid, 492
std::future::wait, 493
std::future::wait_for, 493
std::future::wait_until, 494
std::kill_dependency(), 174
std::lock(), 72
std::move(), 46, 124, 329, 333
std::mutex::lock, 516
std::mutex::try_lock, 516
std::mutex::unlock, 517
std::notify_all_at_thread_exit, 443
std::packaged_task::get_future, 504
std::packaged_task::make_ready_at_thread_exit,
506
std::packaged_task::reset, 505
std::packaged_task::swap, 504
std::packaged_task::valid, 505
std::partial_sum, 312
std::partition(), 124
std::promise::get_future, 510
std::promise::set_exception, 512
std::promise::set_exception_at_thread_exit,
512
std::promise::set_value, 510
std::promise::set_value_at_thread_exit, 511
std::promise::swap, 509
std::recursive_mutex::lock, 519
std::recursive_mutex::try_lock, 519
std::recursive_mutex::unlock, 519
std::recursive_timed_mutex::lock, 526
std::recursive_timed_mutex::try_lock, 526
std::recursive_timed_mutex::try_lock_for, 526
std::recursive_timed_mutex::try_lock_until,
527
std::recursive_timed_mutex::unlock, 528
std::ref, 45
std::shared_future::get, 500
std::shared_future::valid, 498
std::shared_future::wait, 498
std::shared_future::wait_for, 499
std::shared_future::wait_until, 499
std::terminate(), 37, 349
std::this_thread::get_id, 52, 558
std::this_thread::sleep_for, 559
std::this_thread::sleep_until, 559
std::this_thread::yield, 559
std::thread::detach, 557
std::thread::get_id, 558
std::thread::hardware_concurrency, 49, 273,
276, 280, 324, 558
std::thread::join, 557
std::thread::joinable, 556
std::thread::native_handle, 553
std::thread::swap, 556
std::timed_mutex::lock, 521
std::timed_mutex::try_lock, 522
std::timed_mutex::try_lock_for, 522
std::timed_mutex::try_lock_until, 523
std::timed_mutex::unlock, 524
std::unique_lock::lock, 536
std::unique_lock::mutex, 539
std::unique_lock::operator, 539
std::unique_lock::owns_lock, 539
std::unique_lock::release, 539
std::unique_lock::swap, 535, 536
std::unique_lock::try_lock, 536
std::unique_lock::try_lock_for, 537
std::unique_lock::try_lock_until, 538
std::unique_lock::unlock, 537
store(), 140, 143, 177
submit(), 326, 329, 335
swap(), 64
test_and_set(), 138, 141
thread_a(), 76
thread_b(), 76
time_since_epoch(), 118
top(), 64
try_lock(), 76, 80
try_lock_for(), 120
try_lock_until(), 120
try_pop(), 98, 191, 197, 200, 202, 337
try_reclaim(), 230
try_steal(), 337
trywialne, 379
unlock(), 60, 80, 348
update_data_for_widget, 44
wait(), 96, 102, 318, 344, 348, 403
wait_and_dispatch(), 405, 407
wait_and_pop(), 98, 191, 202, 204
wait_for(), 115, 120, 344
wait_for_data(), 205
wait_until(), 115
worker_thread(), 326, 335
zegar::now(), 116
Poleć książkę
Kup książkę
Skorowidz
567
G
get(), 125
get_event(), 301
get_future(), 106, 114
get_hazard_pointer_for_current_thread(), 234, 236
get_id(), 52
get_lock(), 80
get_tail(), 200
getting_pin(), 130
H
handle(), 130, 407
head.get(), 197
hello(), 33
I
identyfikowanie wtków, 52
identyfikatory wtków, 52
interrupt(), 340, 342, 349
interruptible_wait(), 343, 348
interruption_point(), 341, 344, 351
is_lock_free(), 138
iteratory jednokrotnego przebiegu, 52
iteratory postpujce, 52
J
jzyk C++, 19
automatyczne okrelanie typu zmiennej, 395
biblioteka operacji atomowych, 31
biblioteka standardowa, 31
biblioteka wtków, 30
biblioteki, 29
efektywno klas, 30
frameworki aplikacji, 29
mechanizm deklarowania funkcji
jako usunitej, 376
mechanizm przyszoci, 103
miejsce w pamici, 134
model pamici, 133
muteks, 60
obiekty, 134
obsuga wspóbienoci, 28, 30
operacje atomowe, 137
porzdek modyfikacji, 136
RAII, 29
referencje do r-wartoci, 371
semantyka przenoszenia danych, 372
szablony zmiennoargumentowe, 391
paczka parametrów, 392
rozwinicie paczki, 392
typy definiowane przez uytkownika, 382
inicjalizacja statyczna, 384
warstwy abstrakcji, 30
wyraenia stae, 381
zastosowania, 381
wyraenie lambda, 37
wycig danych, 58
zmienne lokalne wtków, 396
join(), 39
joinable(), 295
K
klasy
dispatcher, 404
receiver, 403
scoped_thread, 48
sender, 402
std::thread, 36
std::atomic_flag, 457
std::chrono::high_resolution_clock, 116
std::chrono::steady_clock, 116, 433
std::chrono::system_clock, 116, 431
std::condition_variable, 95, 436
std::condition_variable_any, 95, 444
std::future<>, 103
std::mutex, 60, 515
std::once_flag, 541
std::recursive_mutex, 90, 517
std::recursive_timed_mutex, 524
std::shared_future<>, 103
std::thread, 549
std::thread::id, 550
std::timed_mutex, 520
thread_guard, 48
thread_pool, 331
komunikacja procesów sekwencyjnych, 126, 127
maszyna stanów, 127, 128
model aktorów, 130
model maszyny stanów, 128
konstruktor domylny, 52
konstruktor przenoszcy, 45
kontenery
std::map<>, 207
std::multimap<>, 207
std::queue<>, 97
std::stack, 64, 66
std::unordered_map<>, 207
std::unordered_multimap<>, 207
Poleć książkę
Kup książkę
568
Skorowidz
L
leniwa inicjalizacja, 85
linie pamici podrcznej, 284
list_contains(), 61
load(), 140, 143
lock(), 60, 79, 80, 142
l-warto, 80
M
main(), 33, 36
mechanizm przyszoci, 52, 102, 103
asynchroniczne zadanie, 104
obietnice, 109
oczekiwanie na wiele wtków, 112
przyszoci unikatowe, 103
przyszoci wspódzielone, 103
wizanie zadania z przyszoci, 106
wynik oblicze wykonywanych w tle, 103
wycig danych, 112
zapisywanie wyjtku, 111
memcmp(), 148
memcpy(), 148
model aktorów, 130
model pamici jzyka C++, 133
analiza podstawowych cech strukturalnych,
134
mechanizmy przetwarzania wspóbienego,
134
miejsce w pamici, 134
modele porzdkowania spójnego
niesekwencyjnie, 159
niezdefiniowane zachowanie, 136
obiekty, 134
ogrodzenia, 178
operacje atomowe, 136
podzia struktury, 135
porzdek modyfikacji, 136
porzdkowania pamici, 155
porzdkowanie poprzez wzajemne
wykluczanie, 155, 166
operacje uzyskiwania, 166
operacje zwalniania, 166
porzdkowanie spójne sekwencyjnie, 155, 156
porzdkowanie zagodzone, 155, 160
wyjanienie porzdkowania, 164
relacja poprzedzania, 152, 154
poprzedzanie wedug zalenoci, 173
przechodnio, 170
relacja wprowadzania zalenoci, 173
relacja synchronizacji, 152
sekwencja zwalniania, 175
wycig danych, 136
muteks, 59, 60, 220
blokowanie, 60
blokowanie rekurencyjne, 90
czytelników-pisarzy, 88
elastyczne blokowanie, 79
hierarchiczny, 77
l-warto, 80
niezdefiniowane zachowanie, 90
ochrona listy, 61
odblokowywanie, 60
przenoszenie wasnoci, 80
rekurencyjny, 90
r-warto, 80
stosowanie w jzyku C++, 60
szczegóowo blokady, 82
wirujcy, 142
zakleszczenie, 71
my_thread, 37
my_thread.detach(), 39
my_thread.join(), 39
my_x.do_lengthy_work(), 45
N
nadsubskrypcja, 51, 280, 285
native_handle(), 32
niezdefiniowane zachowanie, 58, 86, 90, 136
niezmienniki, 56, 355
niskie wspózawodnictwo, 282
notify_one(), 96
now(), 116
O
obiekty przyszoci, 122
ochrona wspódzielonych danych, 56
blokowanie rekurencyjne, 90
definicja klasy kolejki, 100, 190
definicja klasy stosu, 68, 187
Double-Checked Locking, 85
elastyczne blokowanie muteksu, 79
hierarchia blokad, 75
implementacja listy z obsug iteracji, 214
implementacja tablicy wyszukiwania, 210
jednowtkowa implementacja kolejki, 195
kolejka z mechanizmami blokowania i
oczekiwania, 203
kolejka ze szczegóowymi blokadami, 198
Poleć książkę
Kup książkę
Skorowidz
569
kolejka ze sztucznym wzem, 196
leniwa inicjalizacja, 85
lista jednokierunkowa, 194
metody zapewniania bezpieczestwa, 185
muteks, 59, 60
muteks czytelników-pisarzy, 88
niezdefiniowane zachowanie, 58
niezmienniki, 56
ochrona listy, 61
pami transakcyjna, 59
programowanie bez blokad, 59
przekazywanie referencji, 66
przenoszenie wasnoci muteksu, 80
stosowanie konstruktora, 67
struktury danych bez blokad, 220
sytuacja wycigu, 58
szczegóowo blokady, 82
szeregowanie, 185
tablica wyszukiwania, 207
unikanie zakleszcze, 71
wykrywanie sytuacji wycigu, 63
zakleszczenie, 71
zwracanie wskanika, 67
ogrodzenia, 178
open_connection(), 87
operacje atomowe, 136, 137
funkcje nieskadowe, 150
gówny szablon, 147
modele porzdkowania spójnego
niesekwencyjnie, 159
ogrodzenia, 178
operacje dostpne dla typów atomowych, 149
operacje adowania (odczytu), 140, 143
operacje odczyt-modyfikacja-zapis, 140, 141, 143,
operacje porównania-wymiany, 144
operacje wymiany i dodania, 146
operacje zapisu, 140, 141, 143
porównywanie bitowe, 148
porzdkowanie pamici, 155
porzdkowanie poprzez wzajemne
wykluczanie, 155, 166
operacje uzyskiwania, 166
operacje zwalniania, 166
porzdkowanie spójne sekwencyjnie, 155, 156
porzdkowanie zagodzone, 155, 160
wyjanienie porzdkowania, 164
pozorny bd, 144
relacja poprzedzania, 152, 154
poprzedzanie wedug zalenoci, 173
przechodnio, 170
relacja wprowadzania zalenoci, 173
relacja synchronizacji, 152
sekwencja zwalniania, 175
rozkazy porównywania i wymiany podwójnego
sowa, 149
sekwencja zwalniania zasobów, 147
standardowe definicje typów atomowych, 139
standardowe typy atomowe, 138
stos bez blokad, 250
tworzenie typów niestandardowych, 147
wolne funkcje, 150
operator przypisania z przenoszeniem, 45
P
pami transakcyjna, 59
paradygmat CSP, Patrz komunikacja procesów
sekwencyjnych
parallel_accumulate(), 291, 296, 329
parallel_quick_sort(), 126, 275
ping-pong buforów, 282
podzia zagadnie, 25
pop(), 64, 188, 226, 228, 235, 245, 247, 254, 257,
261
pop_head(), 205
pop_task_from_other_thread_queue(), 339
porównywanie bitowe, 148
potok, 278
pozorne budzenie, 97
prawo Amdahla, 299
problem ABA, 266
process(), 82, 301
process_connections(), 110
process_data(), 81
procesy demonów, 42
programowanie bez blokad, 59
programowanie funkcyjne, 122
algorytm sortowania szybkiego, 122
funkcja lambda, 122
obiekty przyszoci, 122
rekurencyjne sortowanie, 123
równolege sortowanie szybkie, 125
wnioskowanie typów zmiennych, 122
projektowanie uniwersalnej kolejki, 97
projektowanie wspóbienego kodu, 269
bezpieczestwo wyjtków, 291, 293, 297
algorytmy równolege, 291
czynniki wpywajce na wydajno kodu, 279
faszywe wspódzielenie, 284
liczba procesorów, 280
nadsubskrypcja, 280, 285
niskie wspózawodnictwo, 282
Poleć książkę
Kup książkę
570
Skorowidz
projektowanie wspóbienego kodu
ping–pong buforów, 282
przeczanie zada, 285
wspózawodnictwo o dane, 281
wybór najlepszego algorytmu, 281
wysokie wspózawodnictwo, 282
zmiana elementu danych, 280
faszywe wspódzielenie, 287
atwo testowania, 361
eliminacja wspóbienoci, 362
warunki struktury kodu, 361
mnoenie macierzy, 287
podzia elementów tablicy, 287
potok, 278
praktyka, 303
bariera, 316
implementacja równolegego algorytmu
wyszukiwania, 307
równolega implementacja funkcji
partial_sum, 319
równolega wersja funkcji std::for_each, 304
równolege obliczanie sum czciowych, 313
prawo Amdahla, 299
pula wtków, 276
ssiedztwo danych, 287
skalowalno, 291, 298
techniki dzielenia pracy pomidzy wtki, 270
dzielenie przed rozpoczciem przetwarzania,
271
dzielenie sekwencji zada, 278
dzielenie wedug typu zadania, 276
podzia ssiadujcych fragmentów danych,
272
rekurencyjne dzielenie danych, 272, 273
równolegy algorytm sortowania szybkiego,
273
sposób izolowania zagadnie, 277
techniki przetwarzania równolegego, 301
ukrywanie opónie, 300
wspózawodnictwo, 286
wzorce dostpu do danych, 289
przekazywanie argumentów do funkcji wtku, 43
konstruktor przenoszcy, 45
kopiowane, 43
operator przypisania z przenoszeniem, 45
przenoszenie, 45
przeczanie kontekstu, 21
przeczanie zada, 21, 22
przenoszenie wasnoci wtku, 46, 47
przetwarzanie wspóbiene, 29
bezpieczestwo, 184
definicja klasy kolejki, 190
definicja klasy stosu, 68
implementacja listy z obsug iteracji, 214
implementacja tablicy wyszukiwania, 210
kolejka z mechanizmami blokowania i
oczekiwania, 203
kolejka ze szczegóowymi blokadami, 198
mechanizmy przyszoci, 102
midzywtkowa relacja poprzedzania, 155
niechciane blokowanie, 354
oczekiwanie na zewntrzne dane wejciowe,
355
uwizienie, 354
zakleszczenie, 354
oczekiwanie na zdarzenie, 94
stos bez blokad, 227, 250
synchronizacja operacji, 93
sytuacje wycigu, 355
naruszone niezmienniki, 355
problemy zwizane z czasem ycia, 356
wycig danych, 355
tablica mieszajca, 209
tablica wyszukiwania, 207
techniki lokalizacji bdów, 357
analiza kodu, 357
próba szczegóowego wyjanienia komu, 358
pytania dotyczce przegldanego kodu, 358
testowanie wspóbienego kodu, 359
wspódzielenie danych przez wtki, 55
wywoanie blokujce z limitem czasowym, 115
zarzdzanie wtkami, 36
identyfikowanie wtków, 52
mechanizm przyszoci, 52
oczekiwanie na zakoczenie wtku, 39
oczekiwanie w razie wystpienia wyjtku, 39
odczenie wtku, 41
przekazywanie argumentów do funkcji wtku,
43
przenoszenie wasnoci wtku, 46
uruchamianie wtków w tle, 42
uruchamianie wtku, 36
wtki demonów, 42
wybór liczby wtków, 49
zmienna warunkowa, 95
pula wtków, 106, 276, 324
wizanie zadania z przyszoci, 106
push(), 64, 100, 191, 197, 201, 225, 229, 247, 254,
255, 261, 337
push_front(), 216
Poleć książkę
Kup książkę
Skorowidz
571
R
RAII, 29
reclaim_later(), 236, 238, 239
referencje do r-wartoci, 371
semantyka przenoszenia danych, 372
konstruktor kopiujcy, 374
konstruktor przenoszcy, 374
relacja poprzedzania, 154
poprzedzanie wedug zalenoci, 173
przechodnio, 170
relacja wprowadzania zalenoci, 173
relacja synchronizacji, 152
sekwencja zwalniania, 175
remove_if(), 217
Resource Acquisition Is Initialization, Patrz RAII
RIAA, 40
rozkazy porównywania i wymiany podwójnego
sowa, 149
równolego, Patrz zrównoleglanie zada
równolego danych, 26
run(), 130
run_pending_task(), 331, 335
r-warto, 80
S
ssiedztwo danych, 287
scoped_thread, 48
sekwencja zwalniania, 175
send_data(), 87
sequential_quick_sort(), 124
set(), 343
set_condition_variable(), 344
set_exception(), 111
set_new_tail(), 264
share(), 114
size(), 64
skalowalno, 298, 369
sleep_for(), 120
sleep_until(), 120
some_function, 47
spawn_task(), 125
splice(), 124
square_root(), 111
std::accumulate, 49
std::async, 104, 125, 273, 281, 297, 513
std::atomic, 138, 140, 147, 460
std::atomic_compare_exchange_strong, 469
std::atomic_compare_exchange_strong_explicit,
469
std::atomic_compare_exchange_weak, 470
std::atomic_compare_exchange_weak_explicit, 471
std::atomic_exchange, 467
std::atomic_exchange_explicit, 467
std::atomic_fetch_add, 476, 486
std::atomic_fetch_add_explicit, 476, 486
std::atomic_fetch_and, 478
std::atomic_fetch_and_explicit, 479
std::atomic_fetch_or, 479
std::atomic_fetch_or_explicit, 480
std::atomic_fetch_sub, 477, 487
std::atomic_fetch_sub_explicit, 478, 487
std::atomic_fetch_xor, 480
std::atomic_fetch_xor_explicit, 481
std::atomic_flag, 138, 141, 457
std::atomic_flag_clear, 459
std::atomic_flag_clear_explicit, 460
std::atomic_flag_test_and_set, 459
std::atomic_flag_test_and_set_explicit, 459
std::atomic_flag::clear, 459
std::atomic_flag::test_and_set, 458
std::atomic_init, 463
std::atomic_is_lock_free, 464
std::atomic_load, 465
std::atomic_load_explicit, 465
std::atomic_signal_fence(), 457
std::atomic_store, 466
std::atomic_store_explicit, 466
std::atomic_thread_fence(), 456
std::atomic<bool>, 143
std::atomic<int>, 147
std::atomic<T*>, 146
std::atomic<t*>::fetch_add, 486
std::atomic<t*>::fetch_sub, 487
std::atomic<typ-cakowitoliczbowy>::fetch_add,
476
std::atomic<typ-cakowitoliczbowy>::fetch_and,
478
std::atomic<typ-cakowitoliczbowy>::fetch_or,
479
std::atomic<typ-cakowitoliczbowy>::fetch_sub,
477
std::atomic<typ-cakowitoliczbowy>::fetch_xor,
480
std::atomic<unsigned long long>, 147
std::atomic::compare_exchange_strong, 468
std::atomic::compare_exchange_weak, 469
std::atomic::exchange, 467
std::atomic::is_lock_free, 464
std::atomic::load, 464
std::atomic::store, 466
Poleć książkę
Kup książkę
572
Skorowidz
std::bind, 45, 333
std::call_once, 86, 542
std::chrono::duration, 117, 420
std::chrono::duration_cast, 428
std::chrono::duration::count, 423
std::chrono::duration::max, 426
std::chrono::duration::min, 426
std::chrono::duration::zero, 425
std::chrono::high_resolution_clock, 116
std::chrono::steady_clock, 116, 433
std::chrono::steady_clock::now, 434
std::chrono::system_clock, 116, 431
std::chrono::system_clock::from_time_t, 433
std::chrono::system_clock::now, 432
std::chrono::system_clock::to_time_t, 433
std::chrono::time_point, 118, 429
std::chrono::time_point::max, 431
std::chrono::time_point::min, 431
std::chrono::time_point::time_since_epoch, 430
std::condition_variable, 95, 436
std::condition_variable_any, 95, 444
std::condition_variable_any::notify_all, 446
std::condition_variable_any::notify_one, 446
std::condition_variable_any::wait, 447
std::condition_variable_any::wait_for, 448
std::condition_variable_any::wait_until, 450
std::condition_variable::notify_all, 437
std::condition_variable::notify_one, 437
std::condition_variable::wait, 344, 438
std::condition_variable::wait_for, 439
std::condition_variable::wait_until, 441
std::copy_exception(), 112
std::current_exception(), 112
std::find, 306
std::for_each, 51, 304
std::future, 103, 106, 109, 112, 490
std::future::get, 494
std::future::share, 492
std::future::valid, 492
std::future::wait, 493
std::future::wait_for, 493
std::future::wait_until, 494
std::kill_dependency(), 174
std::lock, 72, 540
std::lock_guard, 60, 528
std::map<>, 207
std::move(), 46, 124, 329, 333
std::multimap<>, 207
std::mutex, 60, 515
std::mutex::lock, 516
std::mutex::try_lock, 516
std::mutex::unlock, 517
std::notify_all_at_thread_exit, 443
std::once_flag, 86, 541
std::packaged_task, 106, 391, 501
std::packaged_task::get_future, 504
std::packaged_task::make_ready_at_thread_exit,
506
std::packaged_task::reset, 505
std::packaged_task::swap, 504
std::packaged_task::valid, 505
std::partial_sum, 312
std::partition(), 124
std::promise, 109, 507
std::promise::get_future, 510
std::promise::set_exception, 512
std::promise::set_exception_at_thread_exit, 512
std::promise::set_value, 510
std::promise::set_value_at_thread_exit, 511
std::promise::swap, 509
std::queue<>, 97
std::ratio, 421, 544
std::ratio_equal, 546
std::ratio_greater, 548
std::ratio_greater_equal, 548
std::ratio_less, 547
std::ratio_less_equal, 548
std::ratio_not_equal, 547
std::recursive_mutex, 90, 517
std::recursive_mutex::lock, 519
std::recursive_mutex::try_lock, 519
std::recursive_mutex::unlock, 519
std::recursive_timed_mutex, 524
std::recursive_timed_mutex::lock, 526
std::recursive_timed_mutex::try_lock, 526
std::recursive_timed_mutex::try_lock_for, 526
std::recursive_timed_mutex::try_lock_until, 527
std::recursive_timed_mutex::unlock, 528
std::ref, 45
std::shared_future, 103, 113, 495
std::shared_future::get, 500
std::shared_future::valid, 498
std::shared_future::wait, 498
std::shared_future::wait_for, 499
std::shared_future::wait_until, 499
std::stack, 64, 66
std::string, 44
std::terminate(), 37, 349
std::this_thread::get_id, 52, 558
std::this_thread::sleep_for, 120, 559
std::this_thread::sleep_until, 120, 559
std::this_thread::yield, 559
Poleć książkę
Kup książkę
Skorowidz
573
std::thread, 43, 549
std::thread::detach, 557
std::thread::get_id, 558
std::thread::hardware_concurrency, 49, 273, 276,
280, 324, 558
std::thread::id, 550
std::thread::join, 557
std::thread::joinable, 556
std::thread::native_handle, 553
std::thread::swap, 556
std::timed_mutex, 520
std::timed_mutex::lock, 521
std::timed_mutex::try_lock, 522
std::timed_mutex::try_lock_for, 522
std::timed_mutex::try_lock_until, 523
std::timed_mutex::unlock, 524
std::try_lock, 541
std::unique_lock, 79, 80, 530
std::unique_lock::lock, 536
std::unique_lock::mutex, 539
std::unique_lock::operator, 539
std::unique_lock::owns_lock, 539
std::unique_lock::release, 539
std::unique_lock::swap, 535, 536
std::unique_lock::try_lock, 536
std::unique_lock::try_lock_for, 537
std::unique_lock::try_lock_until, 538
std::unique_lock::unlock, 537
std::unordered_map<>, 207
std::unordered_multimap<>, 207
store(), 140, 143, 177
submit(), 326, 329, 335
swap(), 64
synchronizacja wspóbienych operacji, 93
definicja klasy kolejki, 100
funkcje otrzymujce limity czasowe, 121
komunikacja procesów sekwencyjnych, 126
mechanizmy przyszoci, 102
obietnice, 109
oczekiwanie na wiele wtków, 112
oczekiwanie na zdarzenie, 94
operacje atomowe, 137
porzdek modyfikacji, 136
pozorne budzenie, 97
programowanie funkcyjne, 122
projektowanie uniwersalnej kolejki, 97
prosta kolejka komunikatów, 401
przekazywanie zada pomidzy wtkami, 107
upraszczanie kodu, 121
wizanie zadania z przyszoci, 106
wynik oblicze wykonywanych w tle, 103
wycig danych, 112
wywoanie blokujce z limitem czasowym, 115
zapisywanie wyjtku na potrzeby przyszoci,
111
zmienna warunkowa, 95
sytuacja wycigu, 58, 355
definicja klasy stosu, 68
przekazywanie referencji, 66
stosowanie konstruktora, 67
zwracanie wskanika, 67
szablon klasy
std::atomic, 138, 140, 147, 460
std::chrono::duration, 117, 420
std::chrono::time_point, 118, 429
std::future, 103, 109, 112, 490
std::lock_guard, 60, 528
std::packaged_task, 106, 391, 501
std::promise, 109, 507
std::ratio, 421, 544
std::ratio_equal, 546
std::ratio_greater, 548
std::ratio_greater_equal, 548
std::ratio_less, 547
std::ratio_less_equal, 548
std::ratio_not_equal, 547
std::shared_future, 103, 113, 495
std::unique_lock, 79, 80, 530
TemplateDispatcher, 405
szczegóowo blokady, 82
szeregowanie, 185
T
tablica mieszajca, 209
kubeek, 209
tablica posortowana, 209
tablica wyszukiwania, 207
operacje, 208
test_and_set(), 138, 141
testowanie wspóbienego kodu, 360
biblioteka podstawowych mechanizmów, 365
czynniki dotyczce rodowiska testowego, 361
projektowanie struktury wielowtkowego kodu
testowego, 366
identyfikacja odrbnych fragmentów
poszczególnych testów, 366
przykad testu dla struktury kolejki, 367
scenariusze testowania kolejki, 360
testowanie symulowanych kombinacji, 364
wady, 365
Poleć książkę
Kup książkę
574
Skorowidz
testowanie wspóbienego kodu
testowanie wydajnoci, 369
skalowalno, 369
testy siowe, 363
wady, 364
thread_a(), 76
thread_b(), 76
thread_guard, 48
thread_pool, 331
time_since_epoch(), 118
top(), 64
try_lock(), 76, 80
try_lock_for(), 120
try_lock_until(), 120
try_pop(), 98, 191, 197, 200, 202, 337
try_reclaim(), 230
try_steal(), 337
try-catch, 40
typy wywoywalne, 36
U
unlock(), 60, 80, 348
update_data_for_widget, 44
uwizienie, 223, 354
V
void(), 106
W
wait(), 96, 102, 318, 344, 348, 403
wait_and_dispatch(), 405, 407
wait_and_pop(), 98, 191, 202, 204
wait_for(), 115, 120, 344
wait_for_data(), 205
wait_until(), 115
warstwy abstrakcji, 30
wtki demonów, 42
wtki sprztowe, 21
wnioskowanie typów zmiennych, 122
worker_thread(), 326, 335
wskaniki ryzyka, 233
wspóbiene struktury danych, 184
aktywne oczekiwanie, 261
algorytmy blokujce, 220
bezpieczestwo przetwarzania
wielowtkowego, 184
blokady wirujce, 221
definicja klasy kolejki, 190
definicja klasy stosu, 187
drzewo binarne, 209
implementacja listy z obsug iteracji, 214
implementacja tablicy wyszukiwania, 210
jednowtkowa implementacja kolejki, 195
kolejka bez blokad, 252
uzyskiwanie nowej referencji, 259
zwalnianie licznika zewntrznego wza, 260
zwalnianie referencji do wza, 258
kolejka nieograniczona, 206
kolejka ograniczona, 206
kolejka z mechanizmami blokowania
i oczekiwania, 203
kolejka ze szczegóowymi blokadami, 198
kolejka ze sztucznym wzem, 196
kolejk z jednym producentem i jednym
konsumentem, 253
lista jednokierunkowa, 194
problem ABA, 266
projektowanie przy uyciu blokad, 186
stos bez blokad, 227, 250
struktury bez blokad, 220, 221
eliminowanie niebezpiecznych wycieków, 228
kolejka, 252
mechanizm odzyskiwania pamici, 230
problem ABA, 266
stos, 227
uwizienie, 223
wskazówki dotyczce pisania struktur, 264
zalety i wady, 222
zarzdzanie pamici, 228
zliczanie referencji, 242
zwalnianie wzów, 229
struktury bez oczekiwania, 222
szeregowanie, 185
tablica mieszajca, 209
kubeek, 209
tablica posortowana, 209
tablica wyszukiwania, 207
wskazówki dotyczce projektowania, 185
wskaniki ryzyka, 233
implementacja funkcji odzyskujcych wzy, 238
strategie odzyskiwania wzów, 240
wykrywanie wzów, 233
wywoania blokujce, 220
zagodzenie, 221
zliczanie referencji, 242
wspóbieno, 20
bezpieczestwo przetwarzania, 184
mechanizm przyszoci, 102
modele, 22
nadsubskrypcja, 280
oczekiwanie na zdarzenie, 94
Poleć książkę
Kup książkę
Skorowidz
575
operacje atomowe, 136, 137
podniesienia wydajnoci, 26
podzia zagadnie, 25
projektowanie struktury danych, 184
przeczanie kontekstu, 21
przeczanie zada, 21, 22
przykad programu, 32
równolego danych, 26
synchronizacja operacji, 93
w jzyku C++, 28
wtki sprztowe, 21
wspóbiene struktury danych, 184
z wieloma procesami, 23
z wieloma wtkami, 24
zarzdzanie wtkami, 36
zmienna warunkowa, 95
zrównoleglanie zada, 26
wspódzielenie danych przez wtki, 55
blokowanie rekurencyjne, 90
definicja klasy stosu, 68
Double-Checked Locking, 85
elastyczne blokowanie muteksu, 79
leniwa inicjalizacja, 85
lista dwukierunkowa, 56
muteks, 59
niezmienniki, 56
ochrona danych za pomoc muteksów, 60
pami transakcyjna, 59
problemy, 56
programowanie bez blokad, 59
przenoszenie wasnoci muteksu, 80
sytuacja wycigu, 58
szczegóowo blokady, 82
wycigu danych, 58
zakleszczenie, 71
wspózawodnictwo, 286
wybór liczby wtków, 49
nadsubskrypcja, 51
wyraenie lambda, 37
wysokie wspózawodnictwo, 282
zwikszenie prawdopodobiestwa, 283
wycig danych, 58, 112, 136, 355
niezdefiniowane zachowanie, 58
wywoanie blokujce z limitem czasowym, 115
funkcje otrzymujce limity czasowe, 121
limity bezwzgldne, 115
maksymalny czas blokowania wtku, 115
okres, 117
punkt w czasie, 118
wymuszanie oczekiwania na podstawie okresu,
117
zastosowanie limitu czasowego, 120
zegar, 115
Z
zaawansowane zarzdzanie wtkami, 323
przerywanie wykonywania wtków, 340
monitorowanie systemu plików w tle, 350
obsuga przerwa, 349
oczekiwanie na zmienn, 343, 346
pozostae wywoania blokujce, 348
przerywanie zada wykonywanych w tle, 350
punkt przerwania, 341
wykrywanie przerwania, 342
pula wtków, 324
algorytm sortowania szybkiego, 330
implementacja algorytmu sortowania
szybkiego, 332
implementacja prostej puli wtków, 325
kolejka umoliwiajca wykradanie zada, 336
lokalne kolejki zada, 334
z mechanizmem oczekiwania na zadanie, 327
z mechanizmem wykradania zada, 337
unikanie wspózawodnictwa w dostpie do
kolejki, 333
wtek roboczy, 324
wykradanie zada, 335
zakleszczenie, 71, 354
hierarchia blokad, 75
unikanie, 71, 73
zasada jednej odpowiedzialnoci, 277
zegar, 115
czasu rzeczywistego, 116
epoka zegara, 118
najkrótszy moliwy takt, 116
okres taktu, 116
stabilny, 116
zegar::now(), 116
zliczanie referencji, 242
licznik wewntrzny, 243
licznik zewntrzny, 243
stos bez blokad, 250
umieszczanie wza na stosie bez blokad, 243
wykrywanie uywanych wzów, 242
zdejmowanie wza ze stosu bez blokad, 245
zmienna warunkowa, 95
definicja klasy kolejki, 100
oczekiwanie na spenienie warunku, 95
pozorne budzenie, 97
projektowanie uniwersalnej kolejki, 97
zrównoleglanie
zada,
26
Poleć książkę
Kup książkę
576
Skorowidz
Poleć książkę
Kup książkę
Wyszukiwarka
Podobne podstrony:
informatyka jezyk c i przetwarzanie wspolbiezne w akcji anthony williams ebook
Jezyk C i przetwarzanie wspolbiezne w akcji
wyklady-pwir, Studia, 6. Semestr, Przetwazanie wspolbiezne
lab5 Przetwarzanie wspolbiezne Nieznany
lab 3 5 Przetwarzanie współbieżne
wyklady-pwir, Studia, 6. Semestr, Przetwazanie wspolbiezne
lab2 Przetwarzanie współbieżne
lab105 Przetwarzanie współbieżne
Przetwarzanie współbieżne
lab1 Przetwarzanie współbieżne
lab5 Przetwarzanie współbieżne
wyklady-pwir, Studia, 6. Semestr, Przetwazanie wspolbiezne
Prezentacja 2 analiza akcji zadania dla studentow
przetworniki indukcyjne
Prop aut W9 Ses cyfr Przetworniki fotoelektryczne
Przetworstwo produktow rolniczych
MLEKO I PRZETWORY MLECZNE (2)
więcej podobnych podstron