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.
•
Kup książkę
•
Poleć książkę
•
Oceń książkę
•
Księgarnia internetowa
•
Lubię to! » Nasza społeczność
Spis tre'ci
S owo wst#pne .......................................................................................................................................... 11
Podzi#kowania .......................................................................................................................................... 13
O tej ksi$%ce .............................................................................................................................................. 15
Rozdzia 1. Witaj, #wiecie wspó bie$no#ci w C++!
19
1.1.
Czym jest wspó bie$no#&? ........................................................................................................... 20
1.1.1. Wspó!bie"no$% w systemach komputerowych ................................................................. 20
1.1.2. Modele wspó!bie"no$ci ..................................................................................................... 22
1.2.
Dlaczego warto stosowa& wspó bie$no#&? ................................................................................. 25
1.2.1. Stosowanie wspó!bie"no$ci do podzia!u zagadnie& ......................................................... 25
1.2.2. Stosowanie wspó!bie"no$ci do podniesienia wydajno$ci ................................................. 26
1.2.3. Kiedy nie nale"y stosowa% wspó!bie"no$ci ....................................................................... 27
1.3.
Wspó bie$no#& i wielow'tkowo#& w j(zyku C++ .................................................................... 28
1.3.1. Historia przetwarzania wielow'tkowego w j(zyku C++ ................................................ 29
1.3.2. Obs!uga wspó!bie"no$ci w nowym standardzie ............................................................... 30
1.3.3. Efektywno$% biblioteki w'tków j(zyka C++ .................................................................. 30
1.3.4. Mechanizmy zwi'zane z poszczególnymi platformami ................................................... 32
1.4.
Do dzie a! ...................................................................................................................................... 32
1.4.1. „Witaj $wiecie wspó!bie"no$ci” ......................................................................................... 32
1.5.
Podsumowanie .............................................................................................................................. 34
Rozdzia 2. Zarz'dzanie w'tkami
35
2.1.
Podstawowe zarz'dzanie w'tkami ............................................................................................. 36
2.1.1 Uruchamianie w'tku .......................................................................................................... 36
2.1.2. Oczekiwanie na zako&czenie w'tku .................................................................................. 39
2.1.3. Oczekiwanie w razie wyst'pienia wyj'tku ....................................................................... 39
2.1.4. Uruchamianie w'tków w tle .............................................................................................. 42
2.2.
Przekazywanie argumentów do funkcji w'tku ......................................................................... 43
2.3.
Przenoszenie w asno#ci w'tku .................................................................................................... 46
2.4.
Wybór liczby w'tków w czasie wykonywania ........................................................................... 49
2.5.
Identyfikowanie w'tków ............................................................................................................. 52
2.6.
Podsumowanie .............................................................................................................................. 54
Rozdzia 3. Wspó dzielenie danych przez w'tki
55
3.1.
Problemy zwi'zane ze wspó dzieleniem danych przez w'tki ................................................. 56
3.1.1. Sytuacja wy$cigu ................................................................................................................ 58
3.1.2. Unikanie problematycznych sytuacji wy$cigu .................................................................. 59
3.2.
Ochrona wspó dzielonych danych za pomoc' muteksów ........................................................ 60
3.2.1. Stosowanie muteksów w j(zyku C++ ............................................................................. 60
3.2.2. Projektowanie struktury kodu z my$l' o ochronie wspó!dzielonych danych ................. 62
Kup ksi
ąĪkĊ
Pole
ü ksiąĪkĊ
6
Spis tre'ci
3.2.3. Wykrywanie sytuacji wy$cigu zwi'zanych z interfejsami ................................................ 63
3.2.4. Zakleszczenie: problem i rozwi'zanie .............................................................................. 71
3.2.5. Dodatkowe wskazówki dotycz'ce unikania zakleszcze& ................................................. 73
3.2.6. Elastyczne blokowanie muteksów za pomoc' szablonu std::unique_lock ...................... 79
3.2.7. Przenoszenie w!asno$ci muteksu pomi(dzy zasi(gami .................................................... 80
3.2.8. Dobór w!a$ciwej szczegó!owo$ci 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ó bie$nych operacji
93
4.1.
Oczekiwanie na zdarzenie lub inny warunek ........................................................................... 94
4.1.1. Oczekiwanie na spe!nienie warunku za pomoc' zmiennych warunkowych .................. 95
4.1.2. Budowa kolejki gwarantuj'cej bezpieczne przetwarzanie wielow'tkowe
przy u"yciu zmiennych warunkowych .............................................................................. 97
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc' przysz o#ci ........................................... 102
4.2.1. Zwracanie warto$ci przez zadania wykonywane w tle ................................................... 103
4.2.2. Wi'zanie zadania z przysz!o$ci' ...................................................................................... 106
4.2.3. Obietnice (szablon std::promise) ..................................................................................... 109
4.2.4. Zapisywanie wyj'tku na potrzeby przysz!o$ci ................................................................ 111
4.2.5. Oczekiwanie na wiele w'tkó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 otrzymuj'ce limity czasowe .............................................................................. 120
4.4.
Upraszczanie kodu za pomoc' technik synchronizowania operacji ..................................... 121
4.4.1. Programowanie funkcyjne przy u"yciu przysz!o$ci ....................................................... 122
4.4.2. Synchronizacja operacji za pomoc' przesy!ania komunikatów ..................................... 127
4.5.
Podsumowanie ............................................................................................................................ 131
Rozdzia 5. Model pami(ci j(zyka C++ i operacje na typach atomowych
133
5.1.
Podstawowe elementy modelu pami(ci ................................................................................... 134
5.1.1. Obiekty i miejsca w pami(ci ............................................................................................ 134
5.1.2. Obiekty, miejsca w pami(ci i przetwarzanie wspó!bie"ne ............................................ 135
5.1.3. Kolejno$% modyfikacji ...................................................................................................... 136
5.2.
Operacje i typy atomowe j(zyka 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 wskaIników ................................. 146
5.2.5. Operacje na standardowych atomowych typach ca!kowitoliczbowych ........................ 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 porz'dku ............................................................ 151
5.3.1. Relacja synchronizacji ...................................................................................................... 152
5.3.2. Relacja poprzedzania ....................................................................................................... 154
5.3.3. Porz'dkowanie pami(ci na potrzeby operacji atomowych ............................................ 155
5.3.4. Sekwencje zwalniania i relacja synchronizacji ............................................................... 175
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
Spis tre'ci
7
5.3.5. Ogrodzenia ....................................................................................................................... 178
5.3.6. Porz'dkowanie operacji nieatomowych za pomoc' operacji atomowych ..................... 180
5.4.
Podsumowanie ............................................................................................................................ 182
Rozdzia 6. Projektowanie wspó bie$nych struktur danych przy u$yciu blokad
183
6.1.
Co oznacza projektowanie struktur danych pod k'tem wspó bie$no#ci? ............................ 184
6.1.1. Wskazówki dotycz'ce projektowania wspó!bie"nych struktur danych ........................ 185
6.2.
Projektowanie wspó bie$nych struktur danych przy u$yciu blokad .................................... 186
6.2.1. Stos gwarantuj'cy bezpiecze&stwo przetwarzania wielow'tkowego
przy u"yciu blokad ........................................................................................................... 187
6.2.2. Kolejka gwarantuj'ca bezpiecze&stwo przetwarzania wielow'tkowego
przy u"yciu blokad i zmiennych warunkowych ............................................................. 190
6.2.3. Kolejka gwarantuj'ca bezpiecze&stwo przetwarzania wielow'tkowego
przy u"yciu szczegó!owych blokad i zmiennych warunkowych .................................... 194
6.3.
Projektowanie z o$onych struktur danych przy u$yciu blokad ............................................. 207
6.3.1. Implementacja tablicy wyszukiwania gwarantuj'cej bezpiecze&stwo
przetwarzania wielow'tkowego przy u"yciu blokad ...................................................... 207
6.3.2. Implementacja listy gwarantuj'cej bezpiecze&stwo przetwarzania
wielow'tkowego przy u"yciu blokad .............................................................................. 213
6.4.
Podsumowanie ............................................................................................................................ 218
Rozdzia 7. Projektowanie wspó bie$nych struktur danych bez blokad
219
7.1.
Definicje i ich praktyczne znaczenie ....................................................................................... 220
7.1.1. Rodzaje nieblokuj'cych 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.
Przyk ady struktur danych bez blokad .................................................................................... 223
7.2.1. Implementacja stosu gwarantuj'cego bezpiecze&stwo przetwarzania
wielow'tkowego bez blokad ............................................................................................ 224
7.2.2. Eliminowanie niebezpiecznych wycieków — zarz'dzanie pami(ci'
w strukturach danych bez blokad .................................................................................... 228
7.2.3. Wykrywanie w(z!ów, których nie mo"na odzyska%, za pomoc' wskaIników ryzyka ........ 233
7.2.4. Wykrywanie u"ywanych w(z!ów metod' zliczania referencji .......................................... 242
7.2.5. Zmiana modelu pami(ci u"ywanego przez operacje na stosie bez blokad ................... 247
7.2.6. Implementacja kolejki gwarantuj'cej bezpiecze&stwo przetwarzania
wielow'tkowego bez blokad ............................................................................................ 252
7.3.
Wskazówki dotycz'ce pisania struktur danych bez blokad ................................................... 264
7.3.1. Wskazówka: na etapie tworzenia prototypu nale"y stosowa% tryb
std::memory_order_seq_cst ............................................................................................ 265
7.3.2. Wskazówka: nale"y u"ywa% schematu odzyskiwania pami(ci bez blokad .................... 265
7.3.3 Wskazówka: nale"y unika% problemu ABA .................................................................... 266
7.3.4. Wskazówka: nale"y identyfikowa% p(tle aktywnego oczekiwania i wykorzystywa%
czas bezczynno$ci na wspieranie innego w'tku ............................................................. 267
7.4.
Podsumowanie ............................................................................................................................ 267
Rozdzia 8. Projektowanie wspó bie$nego kodu
269
8.1.
Techniki dzielenia pracy pomi(dzy w'tki ............................................................................... 270
8.1.1. Dzielenie danych pomi(dzy w'tki przed rozpocz(ciem przetwarzania ....................... 271
8.1.2. Rekurencyjne dzielenie danych ...................................................................................... 272
8.1.3. Dzielenie pracy wed!ug typu zadania ............................................................................. 276
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
8
Spis tre'ci
8.2.
Czynniki wp ywaj'ce na wydajno#& wspó bie$nego kodu ..................................................... 279
8.2.1. Liczba procesorów ........................................................................................................... 280
8.2.2. Wspó!zawodnictwo o dane i ping-pong bufora .............................................................. 281
8.2.3. Fa!szywe wspó!dzielenie ................................................................................................. 284
8.2.4. Jak blisko nale"y rozmie$ci% dane? ................................................................................. 285
8.2.5. Nadsubskrypcja i zbyt intensywne prze!'czanie zada& ................................................. 285
8.3.
Projektowanie struktur danych pod k'tem wydajno#ci przetwarzania wielow'tkowego ..... 286
8.3.1. Podzia! elementów tablicy na potrzeby z!o"onych operacji .......................................... 287
8.3.2. Wzorce dost(pu do danych w pozosta!ych strukturach ................................................. 289
8.4.
Dodatkowe aspekty projektowania wspó bie$nych struktur danych ................................... 291
8.4.1. Bezpiecze&stwo wyj'tków w algorytmach równoleg!ych .............................................. 291
8.4.2. Skalowalno$% i prawo Amdahla ....................................................................................... 298
8.4.3. Ukrywanie opóInie& za pomoc' wielu w'tków .............................................................. 300
8.4.4. Skracanie czasu reakcji za pomoc' technik przetwarzania równoleg!ego .................... 301
8.5.
Projektowanie wspó bie$nego kodu w praktyce ..................................................................... 303
8.5.1. Równoleg!a implementacja funkcji std::for_each ........................................................... 304
8.5.2. Równoleg!a implementacja funkcji std::find .................................................................. 306
8.5.3. Równoleg!a implementacja funkcji std::partial_sum ..................................................... 312
8.6.
Podsumowanie ............................................................................................................................ 322
Rozdzia 9. Zaawansowane zarz'dzanie w'tkami
323
9.1.
Pule w'tków ................................................................................................................................ 324
9.1.1. Najprostsza mo"liwa pula w'tków .................................................................................. 324
9.1.2. Oczekiwanie na zadania wysy!ane do puli w'tków ........................................................ 327
9.1.3. Zadania oczekuj'ce na inne zadania ............................................................................... 330
9.1.4. Unikanie wspó!zawodnictwa w dost(pie do kolejki zada& ............................................ 333
9.1.5. Wykradanie zada& ............................................................................................................ 335
9.2.
Przerywanie wykonywania w'tków .......................................................................................... 340
9.2.1. Uruchamianie i przerywanie innego w'tku .................................................................... 340
9.2.2. Wykrywanie przerwania w'tku ....................................................................................... 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 pozosta!ych wywo!a& blokuj'cych ............................................................ 348
9.2.6. Obs!uga przerwa& ............................................................................................................ 349
9.2.7. Przerywanie zada& wykonywanych w tle podczas zamykania aplikacji ........................ 350
9.3.
Podsumowanie ............................................................................................................................ 352
Rozdzia 10. Testowanie i debugowanie aplikacji wielow'tkowych
353
10.1. Rodzaje b (dów zwi'zanych z przetwarzaniem wspó bie$nym ............................................ 354
10.1.1. Niechciane blokowanie ............................................................................................... 354
10.1.2. Sytuacje wy$cigu ......................................................................................................... 355
10.2. Techniki lokalizacji b (dów zwi'zanych z przetwarzaniem wspó bie$nym ........................ 357
10.2.1. Przegl'danie kodu w celu znalezienia ewentualnych b!(dów .................................. 357
10.2.2. Znajdowanie b!(dów zwi'zanych z przetwarzaniem wspó!bie"nym
poprzez testowanie kodu ................................................................................................. 359
10.2.3. Projektowanie kodu pod k'tem !atwo$ci testowania ................................................. 361
10.2.4. Techniki testowania wielow'tkowego kodu .............................................................. 363
10.2.5. Projektowanie struktury wielow'tkowego kodu testowego ...................................... 366
10.2.6. Testowanie wydajno$ci wielow'tkowego kodu ......................................................... 369
10.3. Podsumowanie ............................................................................................................................ 370
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
Spis tre'ci
9
Dodatek A Krótki przegl'd wybranych elementów j(zyka C++11
371
A.1. Referencje do r-warto#ci ........................................................................................................... 371
A.1.1. Semantyka przenoszenia danych ..................................................................................... 372
A.1.2. Referencje do r-warto$ci i szablony funkcji .................................................................... 375
A.2. Usuni(te funkcje ......................................................................................................................... 376
A.3. Funkcje domy#lne ...................................................................................................................... 377
A.4. Funkcje constexpr ...................................................................................................................... 381
A.4.1. Wyra"enia constexpr i typy definiowane przez u"ytkownika ........................................ 382
A.4.2. Obiekty constexpr ............................................................................................................ 385
A.4.3. Wymagania dotycz'ce funkcji constexpr ........................................................................ 385
A.4.4. S!owo constexpr i szablony .............................................................................................. 386
A.5. Funkcje lambda .......................................................................................................................... 386
A.5.1. Funkcje lambda odwo!uj'ce si( do zmiennych lokalnych ............................................. 388
A.6. Szablony zmiennoargumentowe ............................................................................................... 391
A.6.1. Rozwijanie paczki parametrów ....................................................................................... 392
A.7. Automatyczne okre#lanie typu zmiennej ................................................................................. 395
A.8. Zmienne lokalne w'tków ........................................................................................................... 396
A.9. Podsumowanie ............................................................................................................................ 397
Dodatek B Krótkie zestawienie bibliotek przetwarzania wspó bie$nego
399
Dodatek C Framework przekazywania komunikatów i kompletny przyk ad
implementacji systemu bankomatu
401
Dodatek D Biblioteka w'tków j(zyka 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-ca!kowitoliczbowy> ................................. 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 tre'ci
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
Materia y dodatkowe
561
Skorowidz
563
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
Synchronizacja
wspó/bie1nych operacji
W tym rozdziale zostan" omówione
nast$puj"ce zagadnienia:
oczekiwanie na zdarzenie;
oczekiwanie na jednorazowe zdarzenia za pomoc"
przysz#o$ci;
oczekiwanie z limitem czasowym;
upraszczanie kodu za pomoc" technik
synchronizowania operacji.
W poprzednim rozdziale przeanalizowali$my rozmaite sposoby ochrony danych wspó!-
dzielonych przez wiele w'tków. Okazuje si( jednak, "e w pewnych przypadkach jest
potrzebna nie tyle ochrona danych, co synchronizacja dzia!a& podejmowanych przez
ró"ne w'tki. W'tek mo"e na przyk!ad czeka% z realizacj' w!asnej operacji na zako&-
czenie pewnego zadania przez inny w'tek. Ogólnie w wielu przypadkach w'tek oczeku-
j'cy na okre$lone zdarzenie lub spe!nienie pewnego warunku jest najwygodniejszym
rozwi'zaniem. Mimo "e analogiczne rozwi'zanie mo"na zaimplementowa% w formie
mechanizmu okresowego sprawdzania flagi zako&czonego zadania lub innej warto$ci
zapisanej we wspó!dzielonych danych, taki model by!by daleki od idea!u. Konieczno$%
synchronizacji operacji wykonywanych przez ró"ne w'tki jest do$% typowym scena-
riuszem, zatem biblioteka standardowa j(zyka C++ oferuje mechanizmy u!atwiaj'ce
obs!ug( tego modelu, w tym zmienne warunkowe i tzw. przysz o#ci.
W tym rozdziale omówi( techniki oczekiwania na zdarzenia przy u"yciu zmiennych
warunkowych oraz sposoby upraszczania synchronizacji operacji za pomoc' przysz!o$ci.
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
94
R
OZDZIA
4.
Synchronizacja wspó bie%nych operacji
4.1.
Oczekiwanie na zdarzenie lub inny warunek
Przypu$%my, "e podró"ujemy nocnym poci'giem. Jednym ze sposobów zagwaranto-
wania, "e wysi'dziemy na w!a$ciwej stacji, jest unikanie snu i sprawdzanie wszystkich
stacji, na których zatrzymuje si( nasz poci'g. W ten sposób nie przegapimy naszej stacji,
jednak po dotarciu na miejsce b(dziemy bardzo zm(czeni. Alternatywnym rozwi'za-
niem jest sprawdzenie rozk!adu jazdy pod k'tem godziny przyjazdu, ustawienie budzika
z pewnym wyprzedzeniem wzgl(dem tej godziny i pój$cie spa%. To rozwi'zanie jest
do$% bezpieczne — nie przegapimy naszej stacji, ale je$li poci'g si( spóIni, wstaniemy
zbyt wcze$nie. Nie mo"na te" wykluczy% sytuacji, w której wyczerpi' si( baterie
w budziku — w takim przypadku mo"emy zaspa% i przegapi% swoj' stacj(. Idealnym
rozwi'zaniem by!aby mo"liwo$% pój$cia spa% i skorzystania z pomocy czego$ (lub kogo$),
co obudzi!oby nas bezpo$rednio przed osi'gni(ciem stacji docelowej.
Jaki to ma zwi'zek z w'tkami? Je$li jeden w'tek czeka, a" inny w'tek zako&czy jakie$
zadanie, ma do wyboru kilka mo"liwych rozwi'za&. Po pierwsze, mo"e stale spraw-
dza% odpowiedni' flag( we wspó!dzielonych danych (chronionych przez muteks); flaga
zostanie ustawiona przez drugi w'tek w momencie zako&czenia zadania. Takie rozwi'-
zanie jest nieefektywne z dwóch powodów: w'tek, który wielokrotnie sprawdza wspo-
mnian' flag(, zajmuje cenny czas procesora, a muteks zablokowany przez oczekuj'cy
w'tek nie jest dost(pny dla "adnego innego w'tku. Oba te czynniki dzia!aj' na nieko-
rzy$% oczekuj'cego w'tku, poniewa" ten w'tek zajmuje zasoby potrzebne tak"e do
dzia!ania w'tku, na który czeka, co opóInia wykonanie zadania i ustawienie odpowied-
niej flagi. Sytuacja przypomina unikanie snu przez ca!' podró" poci'giem i prowadze-
nie rozmowy z maszynist' — maszynista zaj(ty rozmow' musi prowadzi% poci'g nieco
wolniej, zatem póIniej dotrzemy na swoj' stacj(. Podobnie w'tek oczekuj'cy zajmuje
zasoby, które mog!yby by% u"ywane przez pozosta!e w'tki w systemie, przez co czas
oczekiwania mo"e by% d!u"szy, ni" to konieczne.
Druga opcja polega na przechodzeniu w'tku oczekuj'cego w stan u$pienia 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
}
}
Wywo!anie funkcji w p(tli odblokowuje muteks przed przej$ciem w stan u$pienia
i ponownie blokuje ten muteks po wyj$ciu z tego stanu — dzi(ki temu drugi w'tek
ma szanse uzyskania dost(pu do flagi i jej ustawienia.
Opisane rozwi'zanie jest o tyle dobre, "e u$piony w'tek nie zajmuje bezproduk-
tywnie czasu procesora. Warto jednak pami(ta%, "e dobór w!a$ciwego czasu u$pienia
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 w'tek b(dzie
traci! czas procesora na zbyt cz(ste testy; zbyt d!ugi czas u$pienia b(dzie oznacza!, "e
w'tek b(dzie przebywa! w tym stanie nawet po zako&czeniu zadania, na które oczekuje,
zatem opóInienie w dzia!aniu w'tku oczekuj'cego b(dzie zbyt du"e. Takie „zaspanie”
w'tku rzadko ma bezpo$redni wp!yw na wynik operacji wykonywanych przez program,
ale ju" w przypadku szybkiej gry mo"e powodowa% pomini(cie niektórych klatek
animacji, a w przypadku aplikacji czasu rzeczywistego mo"e oznacza% pomini(cie
przydzia!u czasu procesora.
Trzecim, najlepszym rozwi'zaniem jest u"ycie gotowych elementów biblioteki stan-
dardowej j(zyka C++ umo"liwiaj'cych oczekiwanie na okre$lone zdarzenie. Najprost-
szym mechanizmem oczekiwania na zdarzenie generowane przez inny w'tek (na przy-
k!ad zdarzenie polegaj'ce na umieszczeniu dodatkowego zadania w potoku) jest tzw.
zmienna warunkowa. Zmienna warunkowa jest powi'zana z pewnym zdarzeniem lub
warunkiem oraz co najmniej jednym w'tkiem, który czeka na spe!nienie tego warunku.
W'tek, który odkrywa, "e warunek jest spe!niony, mo"e powiadomi& pozosta!e w'tki
oczekuj'ce na t( zmienn' warunkow', aby je obudzi% i umo"liwi% im dalsze przetwarzanie.
4.1.1.
Oczekiwanie na spe)nienie warunku
za pomoc" zmiennych warunkowych
Biblioteka standardowa j(zyka C++ udost(pnia dwie implementacje mechanizmu
zmiennych warunkowych w formie klas
std::condition_variable
i
std::condition_
variable_any
. Obie klasy zosta!y zadeklarowane w pliku nag!ówkowym
<condition_
variable>
. W obu przypadkach zapewnienie w!a$ciwej synchronizacji wymaga u"y-
cia muteksu — pierwsza klasa jest przystosowana tylko do obs!ugi muteksów typu
std::mutex
, natomiast druga klasa obs!uguje wszystkie rodzaje muteksów spe!niaj'cych
pewien minimalny zbiór kryteriów (st'd przyrostek
_any
). Poniewa" klasa
std::condition_
variable_any
jest bardziej uniwersalna, z jej stosowaniem wi'"' si( dodatkowe
koszty w wymiarze wielko$ci, wydajno$ci i zasobów systemu operacyjnego. Je$li wi(c
nie potrzebujemy dodatkowej elastyczno$ci, powinni$my stosowa% klas(
std::condition_
variable
.
Jak nale"a!oby u"y% klasy
std::condition_variable
do obs!ugi przyk!adu opisanego
na pocz'tku tego podrozdzia!u — jak sprawi%, "e w'tek oczekuj'cy na wykonanie jakie-
go$ zadania b(dzie u$piony do momentu, w którym b(d' dost(pne dane do przetwo-
rzenia? Na listingu 4.1 pokazano przyk!ad kodu implementuj'cego odpowiednie roz-
wi'zanie przy u"yciu 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ó bie%nych 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 pocz'tku kodu zdefiniowano kolejk( , która b(dzie u"ywana do przekazywania
danych pomi(dzy dwoma w'tkami. Kiedy dane s' gotowe do przetworzenia, w'tek,
który je przygotowa!, blokuje muteks chroni'cy kolejk( za pomoc' klasy
std::lock_
guard
i umieszcza nowe dane w kolejce . W'tek wywo!uje nast(pnie funkcj( sk!a-
dow'
notify_one()
dla obiektu klasy
std::condition_variable
, aby powiadomi% ocze-
kuj'cy w'tek (je$li taki istnieje) o dost(pno$ci nowych danych .
W tym modelu drug' stron' komunikacji jest w'tek przetwarzaj'cy te dane. W'tek
przetwarzaj'cy najpierw blokuje muteks, jednak tym razem u"yto do tego celu klasy
std::unique_lock
zamiast klasy
std::lock_guard
— przyczyny tej decyzji zostan'
wyja$nione za chwil(. W'tek wywo!uje nast(pnie funkcj(
wait()
dla obiektu klasy
std::condition_variable
. Na wej$ciu tego wywo!ania w'tek przekazuje obiekt blokady
i funkcj( lambda reprezentuj'c' warunek, który musi zosta% spe!niony przed przyst'-
pieniem do dalszego przetwarzania . Funkcje lambda to stosunkowo nowy element
(wprowadzony w standardzie C++11), który umo"liwia pisanie funkcji anonimowych
w ramach innych wyra"e&. Wspomniane rozwi'zanie wprost idealnie nadaje si( do
wskazywania predykatów w wywo!aniach 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 cz($ci A.5 dodatku A.
Implementacja funkcji
wait()
sprawdza warunek (wywo!uj'c przekazan' funkcj(
lambda), po czym zwraca sterowanie, je$li ten warunek jest spe!niony (je$li funkcja
lambda zwróci!a warto$%
true
). Je$li warunek nie jest spe!niony (je$li funkcja lambda
zwróci!a warto$%
false
), funkcja
wait()
odblokowuje muteks i wprowadza bie"'cy w'tek
w stan blokady (oczekiwania). Kiedy zmienna warunkowa jest powiadamiana za pomoc'
funkcji
notify_one()
wywo!anej przez w'tek przygotowuj'cy dane, w'tek oczekuj'cy jest
budzony (odblokowywany), ponownie uzyskuje blokad( muteksu i jeszcze raz sprawdza
warunek. Je$li warunek dalszego przetwarzania jest spe!niony, funkcja
wait()
zwraca
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
4.1.
Oczekiwanie na zdarzenie lub inny warunek
97
sterowanie z zachowaniem blokady muteksu. Je$li warunek nie jest spe!niony, w'tek
odblokowuje muteks i ponownie przechodzi w stan oczekiwania. W!a$nie dlatego w przy-
k!adzie nale"a!o u"y% klasy
std::unique_lock
zamiast klasy
std::lock_guard
— w'tek
oczekuj'cy musi odblokowa% muteks na czas oczekiwania i zablokowa% go ponownie
po otrzymaniu powiadomienia, a klasa
std::lock_guard
nie zapewnia takiej elastycz-
no$ci. Gdyby muteks pozosta! zablokowany przez ca!y czas u$pienia tego w'tku, w'tek
przygotowuj'cy dane nie móg!by zablokowa% tego muteksu i doda% elementu do kolejki,
zatem warunek budzenia w'tku oczekuj'cego nigdy nie zosta!by spe!niony.
Na listingu 4.1 u"y!em prostej funkcji lambda
, która sprawdza, czy struktura
kolejki nie jest pusta. Okazuje si(, "e w tej roli równie dobrze mo"na by u"y% dowolnej
funkcji lub obiektu wywo!ywalnego. Je$li programista dysponuje ju" funkcj' spraw-
dzaj'c' odpowiedni warunek (funkcja mo"e oczywi$cie by% nieporównanie bardziej
z!o"ona ni" prosty test z powy"szego przyk!adu), mo"e przekaza% t( funkcj( bezpo-
$rednio na wej$ciu funkcji
wait()
, bez konieczno$ci opakowywania jej w ramach wyra-
"enia lambda. Po wywo!aniu funkcji
wait()
zmienna warunkowa mo"e 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 sprawdzaj'ca ten warunek zwróci!a warto$%
true
. Je$li
w'tek oczekuj'cy ponownie uzyskuje muteks i sprawdza warunek, mimo "e nie otrzy-
ma! powiadomienia od innego w'tku i jego dzia!ania nie s' bezpo$redni' odpowiedzi'
na takie powiadomienie, mamy do czynienia z tzw. pozornym budzeniem (ang. spu-
rious wake
). Poniewa" optymalna liczba i cz(stotliwo$% takich pozornych budze& s'
z definicji trudne do oszacowania, funkcja sprawdzaj'ca prawdziwo$% warunku nie
powinna powodowa% "adnych skutków ubocznych. Gdyby ta funkcja powodowa!a skutki
uboczne, programista musia!by przygotowa% swój kod na wielokrotne wyst(powanie
tych skutków przed spe!nieniem warunku.
Mo"liwo$% odblokowania obiektu klasy
std::unique_lock
nie jest u"ywana tylko
dla wywo!ania funkcji
wait()
— analogiczne rozwi'zanie zastosowali$my po uzyskaniu
danych do przetworzenia, ale przed przyst'pieniem do w!a$ciwego przetwarzania .
Przetwarzanie danych mo"e by% czasoch!onn' operacj', a jak wiemy z rozdzia!u 3.,
utrzymywanie blokady muteksu d!u"ej, ni" to konieczne, nie jest dobrym rozwi'zaniem.
Stosowanie struktury kolejki do przekazywania danych pomi(dzy w'tkami (jak na
listingu 4.1) jest do$% typowym rozwi'zaniem. Je$li projekt aplikacji jest w!a$ciwy,
synchronizacja powinna dotyczy% samej kolejki, co znacznie ogranicza liczb( poten-
cjalnych problemów i problematycznych sytuacji wy$cigu. Spróbujmy wi(c wyodr(b-
ni% z listingu 4.1 uniwersaln' kolejk( gwarantuj'c' bezpieczne przetwarzanie wielo-
w'tkowe.
4.1.2.
Budowa kolejki gwarantuj"cej bezpieczne przetwarzanie
wielow"tkowe przy u,yciu zmiennych warunkowych
Przed przyst'pieniem do projektowania uniwersalnej kolejki warto po$wi(ci% kilka
minut analizie operacji, które trzeba b(dzie zaimplementowa% dla tej struktury danych
(podobnie jak w przypadku stosu gwarantuj'cego bezpiecze&stwo przetwarzania wielo-
w'tkowego z punktu 3.2.3). Przyjrzyjmy si( kontenerowi
std::queue<>
dost(pnemu
w bibliotece standardowej j(zyka C++ (patrz listing 4.2), który b(dzie stanowi! punkt
wyj$cia dla naszej implementacji.
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
98
R
OZDZIA
4.
Synchronizacja wspó bie%nych 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);
};
Je$li pominiemy operacje konstruowania, przypisywania i wymiany, pozostan' nam
zaledwie trzy grupy operacji: operacje zwracaj'ce stan ca!ej kolejki (
empty()
i
size()
),
operacje zwracaj'ce pojedyncze elementy kolejki (
front()
i
back()
) oraz operacje
modyfikuj'ce kolejk( (
push()
,
pop()
i
emplace()
). Mamy wi(c do czynienia z sytuacj'
analogiczn' do tej opisanej w punkcie 3.2.3 (gdzie omawiali$my struktur( stosu), zatem
opisany interfejs jest nara"ony na te same problemy zwi'zane z sytuacjami wy$cigów.
W tym przypadku nale"y po!'czy% funkcje
front()
i
pop()
w jedno wywo!anie, tak jak
wcze$niej po!'czyli$my funkcje
top()
i
pop()
dla struktury stosu. Warto jeszcze zwróci%
uwag( na pewien nowy element w kodzie z listingu 4.1 — podczas u"ywania kolejki
do przekazywania danych pomi(dzy w'tkami w'tek docelowy zwykle musi czeka% na
te dane. Warto wi(c zaimplementowa% funkcj(
pop()
w dwóch wersjach — pierwsza
funkcja,
try_pop()
, próbuje pobra% warto$% z kolejki, ale zawsze zwraca sterowanie
bezpo$rednio po wywo!aniu, nawet je$li kolejka nie zawiera!a "adnej warto$ci (wtedy
funkcja sygnalizuje b!'d); druga funkcja,
wait_and_pop()
, czeka na pojawienie si(
w kolejce warto$ci do pobrania. Po wprowadzeniu zmian zgodnie ze schematem opi-
sanym ju" przy okazji przyk!adu stosu interfejs struktury kolejki powinien wygl'da%
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 moJliwoKL
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 usuni(to konstruktory i operator
przypisania, aby upro$ci% analizowany kod. Tak jak wcze$niej, tak"e tym razem funk-
cje
try_pop()
i
wait_for_pop()
wyst(puj' w dwóch wersjach. Pierwsza przeci'"ona
wersja funkcji
try_pop()
zapisuje pobran' warto$% we wskazywanej zmiennej, tak
aby mo"na by!o u"y% tej warto$ci w roli statusu; funkcja zwraca warto$%
true
, je$li
uzyska!a jak'$ warto$% — w przeciwnym razie funkcja zwraca warto$%
false
(patrz
cz($% A.2 dodatku A). Druga przeci'"ona wersja nie mo"e dzia!a% w ten sam spo-
sób, poniewa" natychmiast zwraca uzyskan' warto$%. Je$li jednak funkcja nie uzyska!a
"adnej warto$ci, mo"e zwróci% wskaInik równy
NULL
.
Jaki to ma zwi'zek z listingiem 4.1? Okazuje si(, "e mo"emy wyodr(bni% 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() wyodrQbnione 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ó bie%nych 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 sk!adowymi obiektu klasy
threadsafe_
queue
, zatem nie jest potrzebne stosowanie odr(bnych zmiennych , a wywo!anie
funkcji
push()
nie wymaga zewn(trznych mechanizmów synchronizacji . Jak wida%,
tak"e funkcja
wait_and_pop()
uwzgl(dnia stan zmiennej warunkowej .
Napisanie drugiej wersji przeci'"onej funkcji
wait_and_pop()
nie stanowi "adnego
problemu; tak"e pozosta!e funkcje mo"na niemal skopiowa% z przyk!adu stosu pokaza-
nego na listingu 3.5. Ostateczn' wersj( implementacji kolejki pokazano na listingu 4.5.
Listing 4.5. Kompletna definicja klasy kolejki gwarantuj=cej bezpieczeUstwo
przetwarzania wielow=tkowego (dziQki uJyciu zmiennych warunkowych)
#include <queue>
#include <memory>
#include <mutex>
#include <condition_variable>
template<typename T>
class threadsafe_queue
{
private:
mutable std::mutex mut;
Muteks musi byL 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ó bie%nych operacji
Mimo "e
empty()
jest sta!' funkcj' sk!adow' i mimo "e parametr
other
konstruktora
kopiuj'cego jest sta!' referencj', pozosta!e w'tki mog' dysponowa% niesta!ymi refe-
rencjami do tego obiektu i wywo!ywa% funkcje sk!adowe zmieniaj'ce jego stan, zatem
blokowanie muteksu wci'" jest konieczne. Poniewa" blokowanie muteksu jest operacj'
zmieniaj'c' stan obiektu, obiekt muteksu nale"y oznaczy% jako modyfikowalny (ang.
mutable
) , tak aby mo"na by!o blokowa% ten muteks w ciele funkcji
empty()
i kon-
struktora kopiuj'cego.
Zmienne warunkowe s' przydatne tak"e w sytuacji, w której wiele w'tków czeka na
to samo zdarzenie. Je$li celem stosowania w'tków jest dzielenie obci'"enia i je$li tylko
jeden w'tek powinien reagowa% na powiadomienie, mo"na zastosowa% dok!adnie tak'
sam' struktur( jak ta z listingu 4.1 — wystarczy uruchomi% wiele instancji w'tku prze-
twarzaj'cego dane. Po przygotowaniu nowych danych wywo!anie funkcji
notify_one()
spowoduje, "e jeden z w'tków aktualnie wykonuj'cych funkcj(
wait()
sprawdzi waru-
nek. Poniewa" do struktury
data_queue
w!a$nie dodano nowe dane, funkcja
wait()
zwróci sterowanie. Nie wiadomo, do którego w'tku trafi powiadomienie ani nawet czy
istnieje w'tek oczekuj'cy na to powiadomienie (nie mo"na przecie" wykluczy%, "e
wszystkie w'tki w danej chwili przetwarzaj' swoje dane).
Warto te" pami(ta% o mo"liwo$ci oczekiwania na to samo zdarzenie przez wiele
w'tków, z których ka"dy musi zareagowa% na powiadomienie. Opisany scenariusz mo"e
mie% zwi'zek z inicjalizacj' wspó!dzielonych danych, gdzie wszystkie w'tki przetwa-
rzaj'ce 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 przyk!ad w ramach okresowej, wielokrotnej inicjalizacji). W opisanych
przypadkach w'tek przygotowuj'cy dane mo"e wywo!a% funkcj( sk!adow'
notify_all()
dla zmiennej warunkowej (zamiast funkcji
notify_one()
). Jak nietrudno si( domy$li%,
funkcja powoduje, "e wszystkie w'tki aktualnie wykonuj'ce funkcj(
wait()
sprawdz'
warunek, na który czekaj'.
Je$li w'tek wywo!uj'cy w za!o"eniu ma oczekiwa% na dane zdarzenie tylko raz, czyli
je$li po spe!nieniu warunku w'tek nie b(dzie ponownie czeka! na t( sam' zmienn'
warunkow', by% mo"e warto zastosowa% inny mechanizm synchronizacji ni" zmienna
warunkowa. Zmienne warunkowe s' szczególnie nieefektywne w sytuacji, gdy warun-
kiem, na który oczekuj' w'tki, jest dost(pno$% okre$lonego elementu danych. W takim
przypadku lepszym rozwi'zaniem jest u"ycie mechanizmu przysz o#ci.
4.2.
Oczekiwanie na jednorazowe zdarzenia
za pomoc" przysz)o-ci
Przypu$%my, "e planujemy podró" samolotem. Po przyjeIdzie na lotnisko i przej$ciu
rozmaitych procedur wci'" musimy czeka% na komunikat dotycz'cy gotowo$ci naszego
samolotu na przyj(cie pasa"erów (zdarza si(, "e pasa"erowie musz' czeka% wiele godzin).
Mo"emy oczywi$cie znaleI% sposób, aby ten czas min'! nieco szybciej (mo"emy na
przyk!ad czyta% ksi'"k(, przegl'da% strony internetowe lub uda% si( na posi!ek do
drogiej lotniskowej kawiarni), jednak niezale"nie od sposobu sp(dzania czasu czekamy
na jedno — sygna! wzywaj'cy do udania si( na pok!ad samolotu. Co wi(cej, interesu-
j'cy nas lot odb(dzie si( tylko raz, zatem przy okazji nast(pnego wyjazdu na wakacje
b(dziemy czekali na inny lot.
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc$ przysz o'ci
103
Twórcy biblioteki standardowej j(zyka C++ rozwi'zali problem jednorazowych
zdarze& za pomoc' mechanizmu nazwanego przysz o#ci' (ang. future). W'tek, który
musi czeka% na okre$lone jednorazowe zdarzenie, powinien uzyska% przysz!o$% repre-
zentuj'c' to zdarzenie. W'tek oczekuj'cy na t( przysz!o$% mo"e nast(pnie okresowo
sprawdza%, czy odpowiednie zdarzenie nie nast'pi!o (tak jak pasa"erowie co jaki$ czas
zerkaj' na tablic( odlotów), i jednocze$nie pomi(dzy tymi testami wykonywa% inne
zadanie (spo"ywa% drogi deser w lotniskowej kawiarni). Alternatywnym rozwi'zaniem
jest wykonywanie innego zadania do momentu, w którym dalsze dzia!anie nie jest mo"-
liwe bez okre$lonego zdarzenia, i przej$cie w stan gotowo#ci na przysz!o$%. Przysz!o$%
mo"e, ale nie musi by% powi'zana z danymi (tak jak tablica odlotów mo"e wskazywa%
r(kawy prowadz'ce do w!a$ciwych samolotów). Po wyst'pieniu zdarzenia (po osi'gni(-
ciu gotowo#ci przez przysz!o$%) nie jest mo"liwe wyzerowanie tej przysz!o$ci.
W bibliotece standardowej j(zyka C++ istniej' dwa rodzaje przysz!o$ci zaimple-
mentowane w formie dwóch szablonów klas zadeklarowanych w nag!ówku biblioteki
<future>
: przysz o#ci unikatowe (
std::future<>
) oraz przysz o#ci 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' odwo!uj'c' si( do
powi'zanego zdarzenia, natomiast do jednego zdarzenia mo"e si( odwo!ywa% wiele
instancji typu
std::shared_future
. W drugim przypadku wszystkie instancje s' gotowe
jednocze$nie i wszystkie mog' uzyskiwa% dost(p do dowolnych danych powi'zanych
z danym zdarzeniem. W!a$nie z my$l' o powi'zanych 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' w!a$nie typy powi'zanych
danych. W razie braku powi'zanych danych nale"y stosowa% nast(puj'ce specjalizacje
tych szablonów:
std:future<void>
i
std::shared_future<void>.
Mimo "e przysz!o$ci
s!u"' do komunikacji pomi(dzy w'tkami, same obiekty przysz!o$ci nie oferuj' mecha-
nizmów synchronizowanego dost(pu. Je$li wiele w'tków potrzebuje dost(pu do jednego
obiektu przysz!o$ci, nale"y chroni% ten dost(p za pomoc' muteksu lub innego mecha-
nizmu synchronizacji (patrz rozdzia! 3.). Jak napisz( w punkcie 4.2.5 w dalszej cz($ci
tego podrozdzia!u, wiele w'tków mo"e uzyskiwa% dost(p do w!asnej kopii obiektu typu
std::shared_future<>
bez konieczno$ci dodatkowej synchronizacji, nawet je$li wszystkie
te kopie odwo!uj' si( do tego samego asynchronicznego wyniku.
Najprostszym przyk!adem jednorazowego zdarzenia jest wynik oblicze& wykonywa-
nych w tle. Ju" w rozdziale 2. napisa!em, "e klasa
std::thread
nie udost(pnia prostych
mechanizmów zwracania warto$ci wynikowych dla tego rodzaju zada&, i zapowiedzia-
!em wprowadzenie odpowiednich rozwi'za& w rozdziale 4. przy okazji omawiania przy-
sz!o$ci — czas zapozna% si( z tymi rozwi'zaniami.
4.2.1.
Zwracanie warto-ci przez zadania wykonywane w tle
Przypu$%my, "e nasza aplikacja wykonuje czasoch!onne obliczenia, które ostatecznie
pozwol' uzyska% oczekiwany wynik. Za!ó"my, "e warto$% wynikowa nie jest potrzebna
na tym etapie dzia!ania programu. By% mo"e uda!o nam si( wymy$li% sposób poszu-
kiwania odpowiedzi na pytanie o "ycie, wszech$wiat i ca!' reszt( stawiane w ksi'"kach
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
104
R
OZDZIA
4.
Synchronizacja wspó bie%nych operacji
Douglasa Adamsa
1
. Mogliby$my oczywi$cie uruchomi% nowy w'tek, który wykona
niezb(dne obliczenia, jednak takie rozwi'zanie wi'za!oby si( z konieczno$ci' przeka-
zania wyników z powrotem do w'tku g!ównego, poniewa" klasa
std::thread
nie oferuje
alternatywnego mechanizmu zwracania warto$ci wynikowych. W takim przypadku
sporym u!atwieniem jest u"ycie szablonu funkcji
std::async
(zadeklarowanego w pliku
nag!ówkowym
<future>
).
Asynchroniczne zadanie, którego wynik nie jest potrzebny na bie"'cym etapie dzia-
!ania programu, mo"na rozpocz'% za pomoc' funkcji
std::async
. Zamiast zwracania
obiektu klasy
std::thread
, który umo"liwi oczekiwanie na zako&czenie danego w'tku,
funkcja
std::async
zwraca obiekt klasy
std::future
, który w przysz!o$ci b(dzie zawiera!
warto$% wynikow'. W miejscu, w którym aplikacja b(dzie potrzebowa!a tej warto$ci,
nale"y wywo!a% funkcj(
get()
dla obiektu przysz!o$ci — wywo!anie tej funkcji zablo-
kuje wykonywanie bie"'cego w'tku do momentu osi'gni(cia gotowo#ci przez przy-
sz!o$%, po czym zwróci uzyskan' warto$%. Prosty przyk!ad u"ycia tych elementów poka-
zano na listingu 4.6.
Listing 4.6. PrzykYad uJycia szablonu klasy std::future do uzyskania wartoKci
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<<"OdpowiedC brzmi "<<the_answer.get()<<std::endl;
}
Szablon funkcji
std::async
umo"liwia przekazywanie dodatkowych argumentów na
wej$ciu wywo!ywanej funkcji — wystarczy doda% te argumenty do wywo!ania (podob-
nie jak w przypadku klasy
std::thread
). Je$li pierwszy argument reprezentuje wskaInik
do funkcji sk!adowej, drugi argument zawiera obiekt, dla którego ma zosta% wywo!ana
ta funkcja sk!adowa (bezpo$rednio, za po$rednictwem wskaInika lub poprzez opako-
wanie
std::ref
), a pozosta!e argumenty s' przekazywane na wej$ciu tej funkcji sk!ado-
wej. W przeciwnym razie drugi i kolejne argumenty s' przekazywane na wej$ciu funkcji
sk!adowej lub wywo!ywalnego obiektu wskazanego za po$rednictwem pierwszego argu-
mentu. Tak jak w przypadku klasy
std::thread
, je$li argumenty maj' posta% r-warto$ci,
zostan' utworzone kopie poprzez przeniesienie oryginalnych warto$ci. Dzi(ki temu
mo"emy stosowa% typy oferuj'ce tylko mo"liwo$% przenoszenia zarówno w roli obiektów
funkcji, jak i w roli argumentów. Przyk!ad takiego rozwi'zania pokazano na listingu 4.7.
1
W ksi'"ce Autostopem przez Galaktyk7 zbudowano komputer Deep Thought, który mia! odpowiedzie%
na pytanie o "ycie, wszech$wiat i ca!' reszt(. Odpowiedzi' na to pytanie by!a liczba 42.
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc$ przysz o'ci
105
Listing 4.7. Przekazywanie argumentów na wejKciu funkcji w=tku 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,"Gegnaj");
struct Y
{
double operator()(double);
};
Y y;
auto f3=std::async(Y(),3.141);
auto f4=std::async(std::ref(y),2.718);
WywoYuje y(2.718)
X baz(X&);
std::async(baz,std::ref(x));
WywoYuje 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());
Domy$lnie to od stosowanej implementacji zale"y, czy funkcja
std::async
uruchamia
nowy w'tek, czy wskazane zadanie b(dzie wykonywane w sposób synchroniczny (wów-
czas bie"'cy w'tek b(dzie czeka! na osi'gni(cie gotowo$ci przez przysz!o$%). W wi(kszo-
$ci przypadków standardowe rozwi'zanie jest wystarczaj'ce, jednak programista mo"e
wybra% w!a$ciwy tryb za pomoc' dodatkowego parametru funkcji
std::async
przeka-
zywanego przed funkcj' do wywo!ania. Wspomniany parametr typu
std::launch
mo"e
mie% albo warto$%
std::launch::deferred
(wówczas wywo!anie funkcji jest odk!adane
do momentu wywo!ania funkcji
wait()
lub
get()
dla danej przysz!o$ci), albo warto$%
std::
launch::async
(wówczas funkcja musi by% wykonywana w odr(bnym w'tku), albo
warto$%
std::launch::deferred | std::launch::async
(wówczas decyzja nale"y do
implementacji). Ostatnia opcja jest stosowana w roli warto$ci domy$lnej. Je$li wywo-
!anie funkcji jest odk!adane na przysz!o$%, mo"e nigdy nie nast'pi%. Na przyk!ad:
auto f6=std::async(std::launch::async,Y(),1.2);
Wykonywane w nowym w=tku
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();
WywoYanie odroczonej funkcji
WywoYuje p->foo(42,"witaj"),
gdzie p jest reprezentowane przez &x
WywoYuje tmpx.bar("Jegnaj"),
gdzie tmpx jest kopi= x
WywoYuje tmpy(3.141), gdzie tmpy
jest tworzone za pomoc= konstruktora
przenosz=cego Y()
WywoYuje tmp(), gdzie tmp jest konstruowany
na podstawie wywoYania 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ó bie%nych operacji
Jak si( przekonasz w dalszej cz($ci tego rozdzia!u (i ponownie w rozdziale 8.), funkcja
std::async
u!atwia dzielenie algorytmów na wspó!bie"nie wykonywane zadania. Oka-
zuje si( jednak, "e nie jest to jedyny sposób kojarzenia obiektu typu
std::future
z zada-
niem — alternatywnym rozwi'zaniem jest opakowanie zadania w ramach instancji
szablonu klasy
std::packaged_task<>
lub napisanie kodu bezpo$rednio ustawiaj'cego
warto$ci za pomoc' szablonu klasy
std::promise<>
. Szablon klasy
std::packaged_task
jest abstrakcj' wy"szego poziomu (w porównaniu z szablonem
std::promise
), zatem
w!a$nie ten szablon omówimy jako pierwszy.
4.2.2.
Wi"zanie zadania z przysz)o-ci"
Szablon klasy
std::packaged_task<>
wi'"e przysz!o$% z funkcj' lub wywo!ywalnym
obiektem. W momencie wywo!ania obiektu typu
std::packaged_task<>
wywo!ana zostaje
powi'zana funkcja lub wywo!ywalny obiekt, a sama przysz!o$% przechodzi w stan goto-
wo#ci (warto$% wynikowa zostaje umieszczona w powi'zanych danych). Opisan' struktur(
mo"na wykorzysta% w roli elementu sk!adowego podczas budowy puli w'tków (patrz
rozdzia! 9.) lub dowolnego innego schematu zarz'dzania zadaniami polegaj'cego na
przyk!ad na wykonywaniu ka"dego zadania w osobnym w'tku lub sekwencyjnym wyko-
nywaniu zada& w jednym w'tku dzia!aj'cym w tle. Je$li jedn' wi(ksz' operacj( mo"na
podzieli% na wiele autonomicznych podzada&, ka"de z tych podzada& mo"na opakowa%
w ramach obiektu klasy
std::packaged_task<>
, aby nast(pnie przekaza% ten obiekt do
mechanizmu szeregowania zada& lub do puli w'tków. W ten sposób mo"na skutecznie
ukry% szczegó!y zwi'zane 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 przyk!ad dla funkcji, która nie otrzymuje "adnych parametrów i nie zwraca warto$ci,
nale"a!oby u"y% sygnatury
void()
, natomiast dla funkcji otrzymuj'cej niesta!' refe-
rencj( do warto$ci typu
std::string
i wskaInik do warto$ci typu
double
oraz zwraca-
j'cej warto$% typu
int
nale"a!oby u"y% sygnatury
int(std::string&,double*)
. Podczas
konstruowania obiektu klasy
std::packaged_task
nale"y przekaza% funkcj( (lub wywo-
!ywalny obiekt) otrzymuj'c' na wej$ciu wskazane parametry i zwracaj'c' typ, który
mo"na przekonwertowa% na wskazany typ danych. Dok!adne dopasowanie typów nie
jest wymagane — istnieje mo"liwo$% skonstruowania obiektu klasy
std::packaged_task
<double(double)>
na podstawie funkcji otrzymuj'cej na wej$ciu warto$% typu
int
i zwracaj'cej warto$% typu
float
, poniewa" wymienione typy mog' by% automatycznie
konwertowane.
Typ warto$ci zwracanych przez wskazan' funkcj( identyfikuje typ zwracany przez
funkcj( sk!adow'
get_future()
konstruowanego obiektu klasy
std::future<>
, nato-
miast lista argumentów zdefiniowana w ramach sygnatury funkcji jest u"ywana do
wyznaczania sygnatury operatora wywo!ania funkcji zadania reprezentowanego przez
ten obiekt. Przyk!ad cz($ciowej definicji klasy
std::packaged_task<std::string(std::
vector<char>*,int)>
pokazano na listingu 4.8.
Instancja klasy
std::packaged_task
jest obiektem wywo!ywalnym i jako taka mo"e
by% opakowana w ramach obiektu klasy
std::function
, przekazana do obiektu kla-
sy
std::thread
w roli funkcji w'tku, przekazana do dowolnej innej funkcji oczekuj'cej
wywo!ywalnego obiektu, a nawet bezpo$rednio wywo!ana. W momencie wywo!ania
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc$ przysz o'ci
107
Listing 4.8. CzQKciowa 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 wej$ciu
operatora wywo!ania s' przekazywane do opakowanej funkcji, a zwracana warto$% jest
zapisywana jako asynchroniczny wynik w obiekcie typu
std::future
(obiekt mo"na
nast(pnie uzyska% za pomoc' funkcji
get_future()
). Oznacza to, "e mo"emy opakowa%
zadanie w obiekcie klasy
std::packaged_task
i uzyska% przysz!o$% przed przekazaniem
tego obiektu do miejsca, gdzie zostanie wywo!any. W momencie, w którym program
b(dzie potrzebowa! wyniku, wystarczy poczeka% na osi'gni(cie gotowo$ci przez t( przy-
sz!o$%. Praktyczny przyk!ad takiego rozwi'zania opisano w nast(pnym podpunkcie.
P
RZEKAZYWANIE ZADAi POMIjDZY WkTKAMI
Wiele frameworków graficznego interfejsu u"ytkownika wymaga, aby aktualizacje tego
interfejsu by!y wykonywane przez okre$lone w'tki. Oznacza to, "e je$li jaki$ inny w'tek
musi zaktualizowa% graficzny interfejs u"ytkownika, powinien wys!a% komunikat do
w!a$ciwego w'tku, aby wyznaczony w'tek wykona! to zadanie w jego imieniu. Szablon
klasy
std::packaged_task
oferuje odpowiednie rozwi'zania bez konieczno$ci stosowania
niestandardowych komunikatów dla ka"dego zadania zwi'zanego z dzia!aniem graficz-
nego interfejsu u"ytkownika (patrz listing 4.9).
Listing 4.9. Uruchamianie kodu w w=tku graficznego interfejsu uJytkownika
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ó bie%nych 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;
}
Powy"szy kod jest bardzo prosty: w'tek graficznego interfejsu u"ytkownika dzia!a
w p(tli do momentu otrzymania komunikatu sygnalizuj'cego konieczno$% zamkni(cia
tego interfejsu . W ciele tej p(tli w'tek sprawdza komunikaty dotycz'ce graficznego
interfejsu u"ytkownika (na przyk!ad tego, "e u"ytkownik klikn'! jaki$ element inter-
fejsu) oraz ewentualne zadania w kolejce zada&. Je$li kolejka nie zawiera "adnych zada&
, w'tek przechodzi do nast(pnej iteracji p(tli; w przeciwnym razie w'tek odczytuje
zadanie z kolejki , zwalnia blokad( tej kolejki, po czym uruchamia to zadanie .
W momencie zako&czenia zadania powi'zana z nim przysz!o$% przechodzi w stan
gotowo$ci.
Umieszczenie zadania w kolejce jest równie proste: nowe, opakowane zadanie jest
tworzone na podstawie wskazanej funkcji , przysz!o$% jest uzyskiwana z obiektu zada-
nia za pomoc' funkcji sk!adowej
get_future()
i wreszcie zadanie jest umieszczane
na li$cie przed zwróceniem przysz!o$ci do kodu wywo!uj'cego . Kod, który wysy!a!
komunikat do w'tku interfejsu u"ytkownika, mo"e albo poczeka% na przysz!o$% (je$li
wykonanie zadania jest niezb(dne do dalszego dzia!ania), albo porzuci% t( przysz!o$%
(je$li nie potrzebuje wyniku przetwarzania).
W tym przyk!adzie u"yli$my do reprezentacji zada& klasy
std::packaged_task
<void()>
. Klasa opakowuje funkcj( (lub inny obiekt wywo!ywalny), która nie otrzy-
muje "adnych parametrów i zwraca
void
(je$li wskazana funkcja zwraca inn' warto$%,
wynik zostanie porzucony). W tym przypadku zastosowano najprostsze mo"liwe zada-
nie, jednak (jak ju" wiemy) szablon klasy
std::packaged_task
mo"e by% równie dobrze
stosowany w implementacjach bardziej z!o"onych rozwi'za& — wystarczy w roli para-
metru szablonu u"y% innej sygnatury funkcji, zmieni% typ zwracanych warto$ci (a wi(c
tak"e typ danych przechowywanych w ramach stanu przysz!o$ci) i zmieni% typy argu-
mentów operatora wywo!ania funkcji. Przedstawiony przyk!ad mo"na by !atwo rozsze-
rzy% o mo"liwo$% przekazywania argumentów do zada&, które maj' by% wykonywane
przez w'tek graficznego interfejsu u"ytkownika, i zwracania warto$ci w ramach obiektu
typu
std::future
(zamiast samego sygna!u o zako&czeniu zadania).
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc$ przysz o'ci
109
Co nale"y zrobi% z zadaniami, których nie mo"na wyrazi% w formie prostych wywo-
!a& funkcji, i zadaniami, których wyniki mog' pochodzi% z wielu ró"nych miejsc? Obs!uga
takich przypadków wymaga jeszcze innego sposobu tworzenia przysz!o$ci — bezpo-
$redniego ustawiania warto$ci za pomoc' szablonu
std::promise
.
4.2.3.
Obietnice (szablon std::promise)
Programi$ci pracuj'cy nad aplikacjami, które musz' obs!ugiwa% wiele po!'cze& sie-
ciowych, cz(sto ulegaj' pokusie obs!ugi ka"dego po!'czenia w osobnym w'tku, ponie-
wa" takie rozwi'zanie u!atwia zrozumienie i zaimplementowanie mechanizmów komu-
nikacji sieciowej. Takie rozwi'zanie sprawdza si( w przypadku niewielkiej liczby
po!'cze& (a wi(c tak"e niewielkiej liczby w'tków). Okazuje si( jednak, "e w razie
wzrostu liczby po!'cze& opisany model staje si( nieefektywny, poniewa" du"a liczba
w'tków zajmuje zbyt wiele zasobów systemu operacyjnego, a cz(ste prze!'czanie
kontekstu (je$li liczba w'tków przekracza wspó!bie"no$% sprz(tow') ma negatywny
wp!yw na wydajno$% aplikacji. W skrajnych przypadkach aplikacja uruchamiaj'ca du"o
nowych w'tków mo"e wyczerpa% zasoby systemu operacyjnego przed osi'gni(ciem limitu
po!'cze& sieciowych. W!a$nie dlatego nawet w aplikacjach obs!uguj'cych bardzo du"o
po!'cze& sieciowych stosuje si( stosunkowo niewiele w'tków (czasem tylko jeden
w'tek) odpowiedzialnych za obs!ug( tych po!'cze&, zatem ka"dy w'tek musi obs!ugi-
wa% wiele po!'cze& jednocze$nie.
Przeanalizujmy przyk!ad w'tku obs!uguj'cego po!'czenia. Pakiety danych przy-
chodz' za po$rednictwem ró"nych po!'cze& w przypadkowej kolejno$ci; podobnie
pakiety danych przeznaczone do wys!ania s' kolejkowane w przypadkowej kolejno$ci.
W wielu przypadkach pozosta!e elementy aplikacji b(d' oczekiwa!y albo na wys!anie
danych, albo na otrzymanie nowego pakietu danych za po$rednictwem okre$lonego po!'-
czenia sieciowego.
Szablon klasy
std::promise<T>
umo"liwia ustawienie warto$ci (typu
T
), któr' w przy-
sz!o$ci b(dzie mo"na odczyta% za po$rednictwem powi'zanego obiektu klasy
std::
future<T>
. Para klas
std::promise
i
std::future
to jeden z mechanizmów umo"li-
wiaj'cych implementacj( interesuj'cego nas rozwi'zania — w'tek oczekuj'cy mo"e
wstrzyma% dzia!anie w oczekiwaniu na przysz!o$%, natomiast w'tek udost(pniaj'cy
dane mo"e u"y% obiektu obietnicy do ustawienia powi'zanej warto$ci, tak aby odpo-
wiednia przysz!o$% przesz!a w stan gotowo#ci.
Obiekt klasy
std::future
powi'zany z danym obiektem klasy
std::promise
mo"na
uzyska% za pomoc' funkcji sk!adowej
get_future()
, a wi(c tak samo jak w przypadku
obiektu klasy
std::packaged_task
. W momencie ustawienia warto$ci obiektu obietnicy
(za pomoc' funkcji sk!adowej
set_value()
) obiekt przysz!o$ci przechodzi w stan goto-
wo#ci i jako taki mo"e zosta% u"yty do pobrania zapisanej warto$ci. Je$li nast'pi znisz-
czenie obiektu klasy
std::promise
bez wcze$niejszego ustawienia warto$ci, zamiast
oczekiwanej warto$ci zostanie ustawiony stosowny wyj'tek. Sposób przekazywania wyj't-
ków pomi(dzy w'tkami zostanie opisany w punkcie 4.2.4.
Na listingu 4.10 pokazano przyk!ad kodu w'tku, który przetwarza po!'czenia w opi-
sany powy"ej sposób. W prezentowanym przyk!adzie u"yli$my pary klas
std::promise
<bool>
i
std::future<bool>
do identyfikacji udanej transmisji bloku danych wycho-
dz'cych; warto$% powi'zana z obiektem przysz!o$ci ma posta% prostej flagi sukcesu
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
110
R
OZDZIA
4.
Synchronizacja wspó bie%nych operacji
lub niepowodzenia. W przypadku pakietów przychodz'cych funkcj( danych powi'za-
nych z obiektem przysz!o$ci pe!ni w!a$ciwa tre$% tych pakietów.
Listing 4.10. ObsYuga wielu poY=czeU w jednym w=tku przy uJyciu 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 p(tl( do momentu, w którym funkcja
done()
zwróci warto$%
true
. W ka"dej iteracji tej p(tli kod aplikacji sprawdza kolejno ka"de
po!'czenie i pobiera dane przychodz'ce (je$li istniej') lub wysy!a kolejkowane
dane wychodz'ce . Zak!adamy, "e pakiet przychodz'cy zawiera jaki$ identyfikator i w!a-
$ciwe dane. Identyfikator jest odwzorowywany na odpowiedni obiekt klasy
std::promise
(na przyk!ad metod' odnajdywania w kontenerze asocjacyjnym) , natomiast warto$%
jest przypisywana do cia!a pakietu. W przypadku pakietów wychodz'cych zastosowa-
no mechanizm kolejki pakietów oczekuj'cych na wys!anie — program sprawdza stan
kolejki i wysy!a ewentualne pakiety dla danego po!'czenia. Po wys!aniu pakietu w obiek-
cie obietnicy powi'zanym z tymi danymi wychodz'cymi jest ustawiana warto$%
true
,
która oznacza pomy$ln' transmisj( danych . Zgodno$% opisanego modelu z rzeczy-
wistymi protoko!ami komunikacji sieciowej zale"y tylko od tych protoko!ów. Struktura
na bazie obietnicy i przysz!o$ci nie pasuje co prawda do ka"dego scenariusza, ale pod
wieloma wzgl(dami przypomina model asynchronicznych operacji wej$cia-wyj$cia sto-
sowany w niektórych systemach operacyjnych.
W dotychczas prezentowanym kodzie ca!kowicie ignorowali$my problem wyj't-
ków. Wyobra"enie $wiata, w którym wszystko dzia!a, jak nale"y, jest by% mo"e kusz'ce,
ale nie ma wiele wspólnego z rzeczywisto$ci'. Nie mo"na wykluczy%, "e dysk zostanie
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
4.2.
Oczekiwanie na jednorazowe zdarzenia za pomoc$ przysz o'ci
111
zape!niony, "e program nie b(dzie móg! znaleI% potrzebnych danych, "e nast'pi awa-
ria po!'czenia sieciowego lub "e w wyniku b!(du nie b(dzie dost(pna baza danych.
Je$li operacja wykonywana w jednym w'tku potrzebuje do dzia!ania wyniku innego
w'tku, warto uwzgl(dni% mo"liwo$% zasygnalizowania b!(du w formie wyj'tku — zak!a-
danie, "e w kodzie stosuj'cym obiekty klasy
std::packaged_task
czy
std::promise
wszystko zawsze b(dzie dzia!a!o prawid!owo, by!oby zbyt optymistyczne. Biblioteka
standardowa j(zyka C++ oferuje wygodne mechanizmy obs!ugi wyj'tków w tego rodzaju
scenariuszach i umo"liwia zapisywanie wyj'tków w ramach wyników powi'zanych z tymi
obiektami.
4.2.4.
Zapisywanie wyj"tku na potrzeby przysz)o-ci
Przeanalizujmy nast(puj'cy fragment kodu. Je$li na wej$ciu funkcji
square_root()
prze-
ka"emy warto$%
-1
, zg!oszony zostanie wyj'tek (to on trafi do kodu wywo!uj'cego t(
funkcj():
double square_root(double x)
{
if(x<0)
{
throw std::out_of_range(“x<0”);
}
return sqrt(x);
}
Przypu$%my teraz, "e zamiast wywo!a% funkcj(
square_root()
w bie"'cym w'tku, jak
w poni"szym wierszu:
double y=square_root(-1);
u"yjemy wywo!ania asynchronicznego w nast(puj'cej formie:
std::future<double> f=std::async(square_root,-1);
double y=f.get();
Idealnym rozwi'zaniem by!oby zapewnienie dok!adnie takiego samego zachowania
jak w przypadku kodu jednow'tkowego — skoro zmiennej
y
w obu przypadkach jest
przypisywany wynik funkcji, w'tek wywo!uj'cy funkcj(
f.get()
powinien mie% dost(p
tak"e do ewentualnych wyj'tków (tak jak odpowiedni kod jednow'tkowy).
Okazuje si(, "e w!a$nie tak dzia!a prezentowane rozwi'zanie: je$li funkcja
square_
root
wywo!ana za po$rednictwem funkcji
std::async
zg!osi jaki$ wyj'tek, wyj'tek
ten zostanie zapisany w obiekcie przysz!o$ci (w miejscu dla warto$ci wynikowej), przy-
sz!o$% przejdzie w stan gotowo#ci, a funkcja
get()
spowoduje ponowne zg!oszenie zapi-
sanego wyj'tku. (Uwaga: standard j(zyka C++ nie okre$la, czy ponowne zg!oszenie
dotyczy oryginalnego obiektu wyj'tku, czy jego kopii; ró"ne kompilatory i biblioteki
stosuj' w tym wzgl(dzie odmienne rozwi'zania). To samo dotyczy funkcji opakowanej
w ramach obiektu klasy
std::packaged_task
— je$li po wywo!aniu zadania opakowana
funkcja zg!osi jaki$ wyj'tek, wyj'tek jest zapisywany w obiekcie przysz!o$ci zamiast
w!a$ciwego wyniku. Aby ponownie zg!osi% ten wyj'tek, wystarczy wywo!a% funkcj(
get()
.
Szablon klasy
std::promise
oferuje oczywi$cie analogiczne rozwi'zanie, które wymaga
bezpo$redniego wywo!ania funkcji. Aby zapisa% wyj'tek zamiast warto$ci wynikowej,
wystarczy wywo!a% funkcj( sk!adow'
set_exception()
zamiast funkcji
set_value()
.
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
112
R
OZDZIA
4.
Synchronizacja wspó bie%nych operacji
Wspomniana funkcja jest zwykle stosowana w bloku
catch
odpowiedzialnym za obs!ug(
wyj'tku zg!oszonego w trakcie dzia!ania algorytmu — wyj'tek 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 powy"szym kodzie u"yto funkcji
std::current_exception()
do pobrania zg!oszonego
wyj'tku; alternatywnym rozwi'zaniem by!oby wywo!anie funkcji
std::copy_exception()
w celu zapisania nowego wyj'tku bez jego bezpo$redniego zg!aszania:
some_promise.set_exception(std::copy_exception(std::logic_error("foo ")));
Opisane rozwi'zanie jest nieporównanie bardziej czytelne ni" stosowanie bloku
try
-
catch
,
je$li tylko potencjalny wyj'tek jest znany z wyprzedzeniem. W ten sposób mo"na nie
tylko upro$ci% kod, ale te" u!atwi% optymalizacj( tego kodu przez kompilator.
Innym sposobem zapisywania wyj'tku w przysz!o$ci jest zniszczenie obiektu klasy
std::promise
lub
std::packaged_task
powi'zanego z obiektem przysz!o$ci bez uprzed-
niego wywo!ania funkcji ustawiaj'cej (w przypadku obiektu obietnicy) lub uruchomie-
nia opakowanego zadania. Je$li obiekt przysz!o$ci nie b(dzie gotowy, w obu przypadkach
destruktor klasy
std::promise
lub
std::packaged_task
zapisze w powi'zanym stanie
wyj'tek typu
std::future_error
z kodem b!(du
std::future_errc::broken_promise
.
Tworz'c przysz!o$%, zapowiadamy (sk!adamy obietnic(), "e udost(pnimy jak'$ warto$%
lub jaki$ wyj'tek; zniszczenie Iród!a tej warto$ci lub tego wyj'tku bez uprzedniego
dostarczenia zapowiedzianego zasobu !amie t( obietnic(. Gdyby w opisanym przypadku
kompilator niczego nie zapisa! w obiekcie przysz!o$ci, w'tki oczekuj'ce mog!yby czeka%
w niesko&czono$%.
Do tej pory we wszystkich przyk!adach stosowa!em szablon klasy
std::future
.
Warto jednak pami(ta% o pewnych ograniczeniach szablonu
std::future
, w tym o mo"-
liwo$ci oczekiwania na wynik przez zaledwie jeden w'tek. W razie konieczno$ci zaim-
plementowania modelu, w którym na jedno zdarzenie b(dzie oczekiwa!o wiele w'tków,
nale"y u"y% raczej szablonu klasy
std::shared_future
.
4.2.5.
Oczekiwanie na wiele w"tków
Mimo "e szablon klasy
std::future
obs!uguje wszystkie mechanizmy synchronizacji
potrzebne do przesy!ania danych pomi(dzy w'tkami, wywo!ania funkcji sk!adowych
okre$lonego obiektu klasy
std::future
nie s' synchronizowane z wywo!aniami funkcji
pozosta!ych obiektów tej klasy. Je$li wiele w'tków uzyskuje dost(p do jednego obiektu
klasy
std::future
bez stosowania dodatkowych mechanizmów synchronizacji, aplika-
cja jest nara"ona na wy#cig danych i niezdefiniowane zachowania. Problem wynika
z projektu tego rozwi'zania — szablon klasy
std::future
modeluje unikatow' w!asno$%
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$ przysz o'ci
113
wspó!bie"nego dost(pu. Skoro po pierwszym wywo!aniu funkcji
get()
nie mo"na ju"
pobra% "adnych danych, z natury rzeczy dane mog' by% pobrane tylko przez jeden w'tek.
Je$li jednak projekt naszej aplikacji wspó!bie"nej wymaga, aby wiele w'tków mog!o
czeka% na to samo zdarzenie, nie wszystko stracone — wystarczy u"y% szablonu klasy
std::shared_future
. O ile szablon klasy
std::future
oferuje tylko mo"liwo$% przeno-
szenia, zatem w!asno$% przysz!o$ci mo"na przenosi% pomi(dzy ró"nymi obiektami, ale
tylko jeden obiekt mo"e si( jednocze$nie odwo!ywa% do jednego asynchronicznego
wyniku, o tyle szablon klasy
std::shared_future
oferuje mo"liwo$% kopiowania, zatem
mo"e istnie% wiele obiektów odwo!uj'cych si( do tego samego stanu.
W przypadku szablonu
std::shared_future
funkcje sk!adowe wywo!ywane dla poje-
dynczego obiektu wci'" nie s' synchronizowane, zatem warunkiem unikania wy$cigów
danych w zwi'zku z dost(pem do tego samego obiektu z poziomu wielu w'tków jest
ochrona tego dost(pu za pomoc' blokady. Najlepszym sposobem jest kopiowanie tego
obiektu, tak aby ka"dy w'tek uzyskiwa! dost(p do w!asnej kopii. Dost(p do wspó!dzie-
lonego, asynchronicznego stanu z poziomu wielu w'tków jest bezpieczny, je$li tylko
ka"dy z tych w'tków uzyskuje dost(p do stanu za po$rednictwem w!asnego obiektu
klasy
std::shared_future
. Przyk!ad takiego rozwi'zania pokazano na rysunku 4.1.
Rysunek 4.1.
UJycie
wielu obiektów klasy
std::shared_future
w celu unikniQcia
wyKcigów danych
Jednym z mo"liwych zastosowa& szablonu klasy
std::shared_future
jest implementa-
cja równoleg!ego wykonywania jakiej$ operacji w modelu zbli"onym do z!o"onego
arkusza kalkulacyjnego, gdzie ka"da komórka zawiera warto$%, która mo"e by% u"ywana
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
114
R
OZDZIA
4.
Synchronizacja wspó bie%nych operacji
we wzorach w wielu pozosta!ych komórkach. Wzory potrzebne do obliczania wyników
w komórkach zale"nych mog' u"ywa% obiektu klasy
std::shared_future
podczas odwo-
!ywania si( do pierwszej komórki. Je$li wzory we wszystkich komórkach b(d' prze-
twarzane równolegle, zadania odwo!uj'ce si( do gotowych warto$ci zostan' zrealizo-
wane natychmiast, natomiast zadania zale"ne od innych, jeszcze przetwarzanych komórek
b(d' musia!y poczeka% na osi'gni(cie gotowo$ci przez tamte komórki. Takie rozwi'-
zanie umo"liwia maksymalne wykorzystanie dost(pnej wspó!bie"no$ci sprz(towej.
Obiekty klasy
std::shared_future
, które wskazuj' pewien asynchroniczny stan, s'
konstruowane na podstawie obiektów klasy
std::future
odwo!uj'cych si( do tego stanu.
Poniewa" obiekty klasy
std::future
nie wspó!dziel' w!asno$ci tego asynchronicznego
stanu z "adnymi innymi obiektami, w!asno$% nale"y przenie$% do obiektu klasy
std::
shared_future
za pomoc' funkcji
std::move
, pozostawiaj'c oryginalny obiekt klasy
std::future
z pustym stanem (jak w przypadku u"ycia konstruktora domy$lnego):
std::promise<int> p;
std::future<int> f(p.get_future());
assert(f.valid());
PrzyszYoKL f jest prawidYowa
std::shared_future<int> sf(std::move(f));
assert(!f.valid());
PrzyszYoKL f juJ nie jest prawidYowa
assert(sf.valid());
PrzyszYoKL sf jest teraz prawidYowa
Obiekt przysz!o$ci
f
jest pocz'tkowo prawid!owy , poniewa" odwo!uje si( do asyn-
chronicznego stanu obietnicy
p
, jednak po przeniesieniu tego stanu do obiektu
sf
to
obiekt
sf
jest prawid!owy , natomiast obiekt
f
jest ju" nieprawid!owy .
Jak w przypadku wszystkich obiektów z mo"liwo$ci' przenoszenia, przeniesienie
w!asno$ci jest wykonywane automatycznie dla r-warto$ci, zatem mo"emy skonstruowa%
obiekt klasy
std::shared_future
bezpo$rednio na podstawie warto$ci zwróconej przez
funkcj( sk!adow'
get_future()
obiektu klasy
std::promise
:
std::promise<std::string> p;
std::shared_future<std::string> sf(p.get_future());
Automatyczne
przeniesienie wYasnoKci
W powy"szym kodzie w!asno$% jest przenoszona automatycznie — obiekt klasy
std::
shared_future<>
jest konstruowany na podstawie r-warto$ci typu
std::future<std::
string>
.
Szablon klasy
std::future
oferuje jeszcze inne rozwi'zanie u!atwiaj'ce stosowanie
obiektów klasy
std::shared_future
przy u"yciu nowego mechanizmu automatycznego
okre$lania typu zmiennej na podstawie inicjalizatora (patrz cz($% A.6 dodatku A). Sza-
blon klasy
std::future
definiuje funkcj( sk!adow'
share()
, która tworzy nowy obiekt
klasy
std::shared_future
i bezpo$rednio przenosi w!asno$% do tego obiektu. U"ycie tego
rozwi'zania mo"e nam oszcz(dzi% sporo pisania i znacznie u!atwia 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 by!oby do$% k!opotliwe.
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 przysz!o$ci zostanie automatycznie zaktualizowany i dostosowany do
tej zmiany.
W pewnych przypadkach dobrym rozwi'zaniem jest ograniczanie maksymalnego
czasu oczekiwania na zdarzenie (z uwagi na ograniczony czas dzia!ania okre$lonej sekcji
kodu lub ze wzgl(du na istnienie innych wa"nych zada&, którymi dany w'tek mo"e si(
zaj'%, je$li oczekiwane zdarzenie nie wyst'pi odpowiednio wcze$nie). Z my$l' o takich
przypadkach wiele funkcji oczekiwania oferuje wersje z mo"liwo$ci' okre$lenia limitu
czasowego.
4.3.
Oczekiwanie z limitem czasowym
Wszystkie wywo!ania blokuj'ce, które stosowali$my w dotychczasowych przyk!adach,
blokowa!y wykonywanie w'tków przez nieokre$lony czas, tj. do momentu wyst'pienia
oczekiwanego zdarzenia. W wielu przypadkach takie rozwi'zanie jest wystarczaj'ce,
jednak w niektórych sytuacjach lepszym wyj$ciem jest okre$lenie maksymalnego czasu
oczekiwania. Stosowanie takich limitów czasowych mo"e mie% na celu potwierdzenie
prawid!owego dzia!ania aplikacji (w formie komunikatu dla u"ytkownika lub innego
procesu) lub przerwanie oczekiwania, je$li na przyk!ad u"ytkownik klikn'! przycisk
Anuluj
.
Istniej' dwa rodzaje limitów czasowych stosowanych dla operacji blokuj'cych: limity
okre$laj'ce maksymalny czas blokowania w'tku (na przyk!ad 30 milisekund) oraz limity
bezwzgl(dne, gdzie oczekiwanie nie mo"e trwa% d!u"ej ni" do okre$lonego punktu
w czasie (na przyk!ad do godziny 17:30:15.045987023 dnia 30 listopada 2012 roku).
Wi(kszo$% funkcji oczekuj'cych wyst(puje w wersjach obs!uguj'cych obie formy limi-
tów czasowych. Wersje obs!uguj'ce wzgl(dne limity czasowe (okre$laj'ce czas trwania
operacji) s' oznaczane przyrostkiem
_for
, natomiast bezwzgl(dne limity czasowe ozna-
cza si( przyrostkiem
_until
.
Na przyk!ad klasa
std::condition_variable
definiuje dwie przeci'"one wersje funk-
cji sk!adowej
wait_for()
i dwie przeci'"one wersje funkcji sk!adowej
wait_until()
,
czyli odpowiedniki obu wersji funkcji
wait()
uzupe!nione o obs!ug( wzgl(dnych i bez-
wzgl(dnych limitów czasowych — pierwsza wersja czeka na sygna!, up!yni(cie limitu
czasowego lub bezpo$rednie budzenie; druga wersja w momencie budzenia sprawdza
przekazany predykat i zwraca sterowanie, pod warunkiem "e albo ten predykat jest
prawdziwy (w wyniku sygna!u umieszczonego w zmiennej warunkowej), albo osi'gni(to
limit czasowy.
Zanim przeanalizujemy szczegó!owe aspekty stosowania funkcji uwzgl(dniaj'cych
limity czasowe, warto po$wi(ci% chwil( na omówienie sposobu okre$lania czasu w j(zyku
C++, w tym dost(pnych zegarów.
4.3.1.
Zegary
W kontek$cie elementów biblioteki standardowej j(zyka C++ zegar jest dla programu
Iród!em informacji o bie"'cej godzinie. W szczególno$ci zegar jest klas' udost(pnia-
j'c' cztery odr(bne informacje:
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
116
R
OZDZIA
4.
Synchronizacja wspó bie%nych operacji
bie$'ca godzina;
typ warto$ci u"ywanych do reprezentowania godzin uzyskiwanych z obiektu
zegara;
okres reprezentowany przez jeden takt zegara;
to, czy takty zegara maj' sta!' d!ugo$%, czyli mo"liwo$% traktowania zegara
jako stabilnego.
Bie"'c' godzin( reprezentowan' przez zegar mo"na uzyska%, wywo!uj'c statyczn' funk-
cj( sk!adow'
now()
klasy zegara; na przyk!ad funkcja
std::chrono::system_clock::now()
zwróci bie"'c' godzin( reprezentowan' przez zegar systemowy. Typ punktów w czasie
dla poszczególnych zegarów jest reprezentowany przez sk!adow' definicj( typu
time_
point
, zatem ka"da funkcja
zegar::now()
zwraca warto$% typu
zegar::time_point
.
Okres taktu zegara jest wyra"any w formie u!amka sekundy reprezentowanego
przez sk!adow' definicj( typu
period
— w przypadku zegara wykonuj'cego 25 taktów
w ci'gu sekundy
period
definiuje typ
std::ratio<1,25>
, natomiast w przypadku zegara
wykonuj'cego jeden takt na 2,5 sekundy sk!adowa
period
definiuje typ
std::ratio<5,2>
.
Je$li okre$lenie okresu taktu nie jest mo"liwe do momentu uruchomienia programu
lub je$li ten okres mo"e si( zmienia% w czasie dzia!ania aplikacji, okres mo"na zdefi-
niowa% w formie $redniego czasu trwania taktu, najkrótszego mo"liwego taktu lub innej
warto$ci przewidzianej przez twórców biblioteki. Nie mo"na jednak zak!ada%, "e obser-
wowany okres taktu zegara podczas jednej próby uruchomienia programu b(dzie odpo-
wiada! rzeczywistemu okresowi danego zegara.
Je$li takty zegara maj' sta ' cz(stotliwo#& (niezale"nie od tego, czy ta cz(stotli-
wo$% pasuje do przyj(tego okresu) i je$li nie mo$emy zmieni& d ugo#ci taktu, mamy do
czynienia z tzw. stabilnym zegarem (ang. steady clock). Sk!adowa statyczna
is_steady
klasy stabilnego zegara ma warto$%
true
(w przypadku niestabilnego zegara ta sama sk!a-
dowa ma warto$%
false
). Zegar systemowy (reprezentowany przez klas(
std::chrono::
system_clock
) zwykle nie jest stabilny, poniewa" mo"na dostosowywa% jego cz(sto-
tliwo$% (nawet je$li zmiany cz(stotliwo$ci s' wprowadzane automatycznie z uwzgl(d-
nieniem przesuni(% wzgl(dem zegara lokalnego). Ka"da taka zmiana mo"e spowodo-
wa%, "e wywo!anie funkcji
now()
zwróci warto$% wcze$niejsz' ni" zwrócona przez
poprzednie wywo!anie tej funkcji, co oczywi$cie narusza wymaganie sta!ej cz(stotli-
wo$ci zegara (i d!ugo$ci taktu). Jak si( za chwil( przekonasz, stabilne zegary s' szcze-
gólnie przydatne podczas oblicze& z uwzgl(dnieniem limitów czasowych — z my$l'
o tych i podobnych zastosowaniach twórcy biblioteki standardowej udost(pnili taki
zegar w formie klasy
std::chrono::steady_clock
. Biblioteka standardowa j(zyka C++
zawiera te" inne klasy zegarów: wspomnian' wcze$niej klas(
std::chrono::system_clock
,
która reprezentuje zegar „czasu rzeczywistego” w danym systemie i która udost(pnia
funkcj( konwersji punktów w czasie na i z warto$ci typu
time_t
, oraz klas(
std::
chrono::high_resolution_clock
, która zapewnia najkrótszy mo"liwy takt zegara (a wi(c
tak"e najwy"sz' mo"liw' cz(stotliwo$%) spo$ród wszystkich zegarów tej biblioteki.
Drugi z zegarów mo"na wykorzysta% w roli punktu wyj$cia dla definicji alternatyw-
nych rozwi'za&. Wymienione zegary zdefiniowano (wraz z pozosta!ymi elementami
zwi'zanymi z obs!ug' czasu) w pliku nag!ówkowym
<chrono>
.
Zanim przyst'pimy do omawiania metod reprezentowania punktów w czasie, warto
po$wi(ci% 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 obs!ugi czasu. Okres zaimplementowano
w szablonie klasy
std::chrono::duration<>
(wszystkie elementy j(zyka C++ zwi'zane
z obs!ug' czasu i u"ywane przez bibliotek( w'tków nale"' do przestrzeni nazw
std::
chrono
). Pierwszy parametr tego szablonu okre$la typ reprezentacji (na przyk!ad
int
,
long
lub
double
); drugi parametr jest u!amkiem okre$laj'cym liczb( sekund repre-
zentowanych przez jednostk( okresu. Na przyk!ad liczba minut przechowywana w war-
to$ci typu
short
jest reprezentowana przez klas(
std::chrono::duration<short,std::
ratio<60,1>>
, poniewa" minuta sk!ada si( z 60 sekund. Liczba milisekund prze-
chowywanych w warto$ci typu
double
jest reprezentowana przez klas(
std::chrono::
duration<double,std::ratio<1,1000>>
, poniewa" ka"da milisekunda trwa jedn'
tysi(czn' cz($% sekundy.
Biblioteka standardowa oferuje zbiór predefiniowanych definicji typów w prze-
strzeni nazw
std::chrono
dla ró"nych okresów (wyra"anych w nanosekundach, mikro-
sekundach, milisekundach, sekundach, minutach i godzinach). Wszystkie te definicje
stosuj' na tyle elastyczne typy ca!kowitoliczbowe, "e mog' reprezentowa% na przyk!ad
okresy ponad 500-letnie w wybranych jednostkach czasu. Przestrze& nazw zawiera
tak"e definicje typów dla rz(dów wielko$ci uk!adu SI: od
std::atto
(10
–18
) do
std::exa
(10
18
) (i wi(cej, je$li tylko dana platforma obs!uguje 128-bitowe typy ca!kowitoliczbowe).
Za pomoc' tych typów mo"na operowa% na niestandardowych okresach, na przyk!ad
klasa
std::duration<double,std::centi>
obs!uguje liczb( setnych cz($ci sekundy repre-
zentowanych przez liczb( typu
double
.
Konwersja pomi(dzy okresami jest wykonywana automatycznie, pod warunkiem
"e nie wymaga obci(cia warto$ci Iród!owej — oznacza to, "e konwersja godzin na
sekundy jest mo"liwa, ale ju" konwersja sekund na godziny nie zostanie wykonana auto-
matycznie. Konwersj( mo"na 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 zaokr'glany), zmienna
s
b(dzie zawiera!a warto$% 54.
Okresy obs!uguj' dzia!ania arytmetyczne, zatem mo"emy dodawa% i odejmowa%
okresy, aby otrzymywa% nowe okresy, b'dI mno"y% lub dzieli% okresy przez sta!e wybra-
nego typu danych (czyli pierwszego parametru szablonu klasy). Oznacza to, "e wyra"enie
5*seconds(1)
ma tak' sam' warto$% jak wyra"enia
seconds(5)
i
minutes(1) – seconds(55)
.
Liczb( jednostek sk!adaj'cych si( na dany okres mo"na uzyska% za pomoc' funkcji
sk!adowej
count()
. Oznacza to, "e wywo!anie
std::chrono::milliseconds(1234).count()
zwróci warto$%
1234
.
Wymuszanie oczekiwania na podstawie okresu (czasu trwania) wymaga stosowania
instancji typu
std::chrono::duration<>
. Mo"emy na przyk!ad spowodowa%, "e czas
oczekiwania na gotowo$% obiektu przysz!o$ci 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ó bie%nych operacji
Wszystkie funkcje oczekiwania zwracaj' status okre$laj'cy, czy koniec oczekiwania
wynika z wyczerpania limitu czasowego, czy z wyst'pienia zdarzenia, na które czeka!
dany w'tek. W tym przypadku w'tek czeka na przysz!o$%, zatem funkcja zwraca warto$%
std::future_status::timeout
w przypadku wyczerpania limitu czasowego; warto$%
std::future_status::ready
, je$li przysz!o$% jest gotowa; lub warto$%
std::future_
status::deferred
, je$li zadanie przysz!o$ci zosta!o od!o"one na póIniej. Czas ocze-
kiwania okresowego jest mierzony przy u"yciu stabilnego, wewn(trznego zegara biblio-
teki, zatem 35 milisekund oznacza w!a$nie 35 milisekund, nawet je$li w czasie oczekiwa-
nia zegar systemowy zostanie przestawiony (w przód lub w ty!). Nie mo"na oczywi$cie
zapomina% o kaprysach systemu szeregowania zada& i o zró"nicowanej precyzji zega-
rów systemów operacyjnych, które mog' spowodowa%, "e rzeczywisty czas dziel'cy
wywo!anie funkcji
wait()
od zwrócenia sterowania b(dzie du"o d!u"szy ni" 35 ms.
Skoro potrafimy ju" stosowa% okresy, mo"emy 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 okre$la jednostki miary (w tej roli nale"y u"y% specjalizacji szablonu klasy
std::chrono::duration<>
). Warto$% punktu w czasie reprezentuje czas (w formie wielo-
krotno$ci wskazanego okresu) od konkretnego punktu w czasie nazywanego epok' zegara.
Epoka zegara jest prost' w!a$ciwo$ci', która jednak nie jest bezpo$rednio dost(pna
ani wprost definiowana przez standard j(zyka C++. Do najcz($ciej stosowanych
epok nale"y pó!noc 1 stycznia 1970 roku i moment uruchomienia komputera, na którym
dzia!a dana aplikacja. Zegary mog' stosowa% jedn' epok( lub ró"ne, niezale"ne epoki.
Je$li dwa zegary stosuj' t( sam' epok(, definicja typu
time_point
w klasie jednego zegara
mo"e wskazywa% drug' klas( jako typ zegara powi'zanego z dan' definicj'
time_point
.
Mimo "e nie mo"na bezpo$rednio uzyska% epoki, mamy do dyspozycji funkcj(
time_
since_epoch()
, któr' mo"emy wywo!a% dla danej instancji typu
time_point
. Funkcja
sk!adowa
time_since_epoch()
zwraca warto$% okresu reprezentuj'c' czas od epoki zegara
do okre$lonego punktu w czasie.
Punkt w czasie mo"na zdefiniowa% na przyk!ad w formie obiektu klasy
std::chrono::
time_point<std::chrono::system_clock, std::chrono::minutes>
. Tak skonstruowany
obiekt zawiera czas wzgl(dem zegara systemowego, tyle "e mierzony w minutach (nie
wed!ug standardowej precyzji zegara systemowego, czyli sekund lub cz($ci sekundy).
Na obiektach klasy
std::chrono::time_point<>
mo"na wykonywa% operacje doda-
wania i odejmowania okresów, których wynikiem s' nowe punkty w czasie. Oznacza
to, "e na przyk!ad w wyniku dodawania
std::chrono::high_resolution_clock::now()
+ std::chrono::nanoseconds(500)
otrzymamy punkt w czasie, który nast'pi za 500
nanosekund (licz'c od teraz). Wyra"enia tego typu s' przydatne podczas obliczania
bezwzgl(dnego limitu czasowego w sytuacji, gdy maksymalny czas wykonywania bloku
kodu jest znany z wyprzedzeniem. Takie rozwi'zanie wymaga jednak wielu wywo!a&
funkcji oczekuj'cych lub funkcji poprzedzaj'cych funkcj( oczekuj'c' i zaliczanych do
bloku, który podlega ograniczeniu czasowemu.
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
4.3.
Oczekiwanie z limitem czasowym
119
Istnieje te" mo"liwo$% odj(cia 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 dziel'cy oba punkty. W ten sposób mo"na na przyk!ad 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() zaj[\o “
<<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 wej$ciu funkcji oczekuj'cej, która sto-
suje bezwzgl(dny limit czasowy, wybrany zegar b(dzie u"ywany do mierzenia czasu.
Warto pami(ta% o mo"liwo$ci zmiany wskaza& zegara i o tym, "e funkcja oczekuj'ca
nie zwróci sterowania do momentu, w którym funkcja
now()
tego zegara nie zwróci
warto$ci póIniejszej od wskazanego limitu czasowego. Je$li zegar zostanie przesta-
wiony w przód, !'czny czas oczekiwania mo"e by% krótszy (w porównaniu z czasem
mierzonym przez stabilny zegar); a je$li zegar zostanie cofni(ty, !'czny czas oczekiwa-
nia zostanie wyd!u"ony.
Jak nietrudno odgadn'%, punkty w czasie s' u"ywane w wersjach funkcji oczekuj'-
cych z przyrostkiem
_until
. Typowym zastosowaniem tego rozwi'zania jest wyznacza-
nie przesuni(cia wzgl(dem godziny zwracanej przez wywo!anie
jaki!-zegar::now()
w wybranym punkcie programu. Punkty powi'zane z zegarem systemowym mo"na
uzyskiwa%, konwertuj'c instancje typu
time_t
za pomoc' statycznej funkcji sk!adowej
std::chrono::system_clock::to_time_point()
. Je$li na przyk!ad maksymalny czas ocze-
kiwania na zdarzenie powi'zane ze zmienn' warunkow' wynosi 500 milisekund, mo"na
zastosowa% konstrukcj( podobn' do tej z listingu 4.11.
Listing 4.11. Oczekiwanie na zmienn= warunkow= z uwzglQdnieniem 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ó bie%nych operacji
Rozwi'zanie z listingu 4.11 jest zalecanym sposobem oczekiwania na zmienne warun-
kowe z uwzgl(dnieniem limitu czasowego w sytuacji, gdy funkcja oczekuj'ca nie
otrzymuje na wej$ciu "adnego predykatu. Maksymalny czas wykonywania p(tli jest
ograniczony. Jak napisa!em w punkcie 4.1.1, je$li nie stosujemy dodatkowego predy-
katu, operowanie na zmiennych warunkowych wymaga u"ycia p(tli, która obs!uguje
nietypowe sposoby budzenia w'tku. W przypadku wywo!ania funkcji
wait_for()
w ciele
p(tli mo"e si( zdarzy%, "e warunek wznowienia dzia!ania zostanie spe!niony bezpo$red-
nio przed up!ywem limitu czasowego, a w nast(pnej iteracji czas oczekiwania b(dzie
liczony od pocz'tku. Taka sytuacja mo"e mie% miejsce wielokrotnie, zatem !'czny czas
oczekiwania by!by nieograniczony.
Skoro dysponujemy ju" podstawowymi narz(dziami umo"liwiaj'cymi stosowanie
limitów czasowych, pora omówi% funkcje, w których mo"na u"ywa% tych limitów.
4.3.4.
Funkcje otrzymuj"ce limity czasowe
Najprostszym zastosowaniem limitu czasowego jest dodanie opóInienia do przetwarza-
nia okre$lonego w'tku, tak aby ten w'tek nie zajmowa! czasu procesora (potrzebnego
innym w'tkom) w czasie, gdy nie wykonuje "adnych warto$ciowych zada&. Przyk!ad
takiego rozwi'zania opisa!em w podrozdziale 4.1, gdzie kod wielokrotnie sprawdza!
stan flagi gotowo$ci w p(tli. Do opóIniania dzia!ania (usypiania) w'tków s!u"' funkcje
std::this_thread::sleep_ for()
i
std::this_thread::sleep_until()
. Obie funkcje
dzia!aj' jak proste budziki — w'tek jest usypiany albo na okre$lony okres (za pomoc'
funkcji
sleep_for()
), albo do wskazanego punktu w czasie (za pomoc' funkcji
sleep_
until()
). W przyk!adowych rozwi'zaniach z podrozdzia!u 4.1 nale"a!oby u"y% funkcji
sleep_for()
, poniewa" w przypadku okresowo wykonywanych operacji w'tek powi-
nien by% wstrzymywany na pewien czas (nie do okre$lonego punktu w czasie). Funkcja
sleep_until()
umo"liwia planowanie budzenia w'tku w okre$lonym punkcie w czasie.
Funkcja
sleep_until()
mo"e wi(c s!u"y% na przyk!ad do uruchamiania procedury two-
rzenia kopii zapasowej o pó!nocy, drukowania listy p!ac o 6 rano lub wstrzymywania
w'tku do momentu wy$wietlenia nast(pnej klatki podczas odtwarzania zapisu wideo.
Usypianie w'tku to oczywi$cie nie jedyne zastosowanie limitów czasowych — jak
ju" wspomnia!em, limity tego typu mo"na stosowa% !'cznie ze zmiennymi warunko-
wymi i przysz!o$ciami. Istnieje nawet mo"liwo$% stosowania limitów czasowych pod-
czas prób uzyskania blokady muteksu, je$li tylko u"yty muteks obs!uguje takie dzia!a-
nie. Standardowe muteksy typów
std::mutex
i
std::recursive_mutex
nie obs!uguj'
limitów czasowych dla operacji blokowania, ale ju" muteksy typów
std::timed_mutex
i
std::recursive_timed_mutex
dopuszczaj' takie dzia!anie. Oba te typy udost(pniaj'
funkcje sk!adowe
try_lock_for()
i
try_lock_until()
, które próbuj' uzyska% blokad(
muteksu odpowiednio w okre$lonym czasie lub przed osi'gni(ciem okre$lonego punktu
w czasie. W tabeli 4.1 opisano funkcje biblioteki standardowej j(zyka C++, które obs!u-
guj' limity czasowe, wraz z ich parametrami i typami zwracanych warto$ci. W miejsce
parametru opisanego jako
okres
nale"y przekaza% obiekt klasy
std::duration<>
, nato-
miast parametr
punkt_w_czasie
nale"y zast'pi% obiektem klasy
std::time_point<>
.
Skoro wiemy ju", jak dzia!aj' zmienne warunkowe, obiekty przysz!o$ci i obietnic
oraz opakowane zadania, czas przeanalizowa% te mechanizmy w nieco szerszym kon-
tek$cie, w szczególno$ci przyjrze% si( technikom upraszczania (za pomoc' tych mecha-
nizmów) synchronizacji operacji wykonywanych przez ró"ne w'tki.
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
4.4.
Upraszczanie kodu za pomoc$ technik synchronizowania operacji
121
Tabela 4.1.
Funkcje otrzymuj=ce limity czasowe
Klasa lub przestrzeU nazw
Funkcje
Zwracane wartoKci
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
w"tku.
std::timed_mutex
lub
std::recursive_timed_mutex
try_lock_for(okres)
try_lock_until
(punkt_w_czasie)
bool
— warto$)
true
,
je$li uda#o si* uzyska) blokad*;
w przeciwnym razie warto$)
false
std::unique_lock<Typ
ZMo)liwo!ci*Blokady
Czasowej>
unique_lock
(typ_blokowalny, okres)
unique_lock(typ_blokowalny,
punkt_w_czasie)
Nie dotyczy — funkcja
owns_lock()
wywo#ana
dla nowo skonstruowanego
obiektu zwraca warto$)
true
,
je$li uda#o si* uzyska) blokad*
(w przeciwnym razie zwraca
warto$)
false
).
try_lock_for(okres)
try_lock_until
(punkt_w_czasie)
bool
— warto$)
true
, je$li
uda#o si* uzyska) blokad*;
w przeciwnym razie warto$)
false
std::future<TypWarto!ci>
lub
std::shared_future<
TypWarto!ci>
wait_for(okres)
wait_until(punkt_w_czasie)
Je$li wyczerpano limit czasu
funkcji oczekuj"cej, zwraca
warto$)
std::future_status::timeout
;
je$li obiekt przysz#o$ci
jest gotowy, zwraca warto$)
std::future_status::ready
;
je$li przysz#o$) zawiera
odroczon" funkcj*, która
nie zosta#a jeszcze wywo#ana,
zwraca warto$)
std::future_status::deferred
.
4.4.
Upraszczanie kodu za pomoc" technik
synchronizowania operacji
Stosowanie mechanizmów synchronizacji, które opisa!em w poprzednich podrozdzia-
!ach, w roli gotowych elementów sk!adowych umo"liwia programi$cie koncentrowanie
si( na samych operacjach wymagaj'cych synchronizacji, nie na mechanice tej synchro-
nizacji. Mechanizmy synchronizacji pozwalaj' upro$ci% kod aplikacji cho%by dlatego,
"e wprowadzaj' do $wiata programowania wspó!bie"nego du"o wi(cej elementów zna-
nych z programowania funkcyjnego. Zamiast bezpo$rednio wspó!dzieli% dane pomi(dzy
w'tkami, ka"de zadanie mo"e otrzymywa% potrzebne dane, a wynik przetwarzania mo"e
by% przekazywany do wielu innych w'tków za po$rednictwem obiektów przysz!o$ci.
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
122
R
OZDZIA
4.
Synchronizacja wspó bie%nych operacji
4.4.1.
Programowanie funkcyjne przy u,yciu przysz)o-ci
Termin programowanie funkcyjne (ang. functional programming — FP) odnosi si( do
stylu programowania, w którym wynik wywo!ania funkcji zale"y wy!'cznie od para-
metrów przekazanych na jej wej$ciu. Oznacza to, "e na wynik funkcji nie ma wp!ywu
zewn(trzny stan. Opisane dzia!anie jest wi(c zgodne z matematycznym poj(ciem funk-
cji, gdzie ka"de u"ycie jednej funkcji z tymi samymi parametrami spowoduje otrzy-
manie dok!adnie takiego samego wyniku. W ten sposób dzia!a wiele matematycznych
funkcji biblioteki standardowej j(zyka 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 zewn(trznego stanu; skutki wykonywania tej funkcji ograniczaj' si( tylko do
zwracanej warto$ci.
Opisany model programowania u!atwia interpretacj( kodu, szczególnie je$li program
zawiera elementy przetwarzania wspó!bie"nego, poniewa" wiele problemów zwi'zanych
z pami(ci' wspó!dzielon' (opisanych w rozdziale 3.) w ogóle nie wyst(puje w $wiecie pro-
gramowania funkcyjnego. Skoro dane wspó!dzielone nie s' modyfikowane, nie mog' wy-
st'pi% sytuacje wy$cigów, zatem ochrona tych danych za pomoc' muteksów jest po prostu
niepotrzebna. W!a$nie prostota tego modelu powoduje, "e takie j(zyki programowania jak
Haskell
2
, gdzie wszystkie funkcje domy#lnie spe!niaj' warunek programowania funkcyj-
nego, zyskuj' coraz wi(ksz' popularno$% w$ród programistów systemów wspó!bie"nych.
Poniewa" niemal ca!y kod jest zgodny z zasadami programowania funkcyjnego, nieliczne
funkcje, które modyfikuj' wspó!dzielony stan, na tyle wyró"niaj' si( spo$ród pozosta!ych
elementów, "e mo"na bez trudu oceni% ich udzia! w ca!ej strukturze aplikacji.
Zalety programowania funkcyjnego nie ograniczaj' si( tylko do j(zyków, w których
ten model jest domy$lnym paradygmatem. J(zyk C++ !'czy w sobie wiele paradyg-
matów, zatem tak"e pisanie programów wed!ug zasad programowania funkcyjnego
jest mo"liwe w tym j(zyku. W wersji C++11 programowanie funkcyjne jest jeszcze
prostsze ni" w standardzie C++98 dzi(ki wprowadzeniu funkcji lambda (patrz cz($% A.5
dodatku A), integracji funkcji
std::bind
zaczerpni(tej z biblioteki Boost i dokumentu
TR1 oraz dodaniu automatycznego wnioskowania typów zmiennych (patrz cz($% A.7
dodatku A). Ostatnim elementem, który u!atwia programowanie funkcyjne w j(zyku
C++, s' obiekty przysz!o$ci — obiekt przysz!o$ci mo"na przekazywa% pomi(dzy
w'tkami, tak aby wynik jednej operacji móg! zale"e% od wyniku innej operacji i aby ta
zale"no$% nie wymaga a bezpo#redniego dost(pu do wspó dzielonych danych.
S
ZYBKIE SORTOWANIE W MODELU PROGRAMOWANIA FUNKCYJNEGO
Aby lepiej zrozumie% mo"liwe zastosowania przysz!o$ci w modelu programowania funk-
cyjnego, przeanalizujmy prost' implementacj( algorytmu sortowania szybkiego (ang.
quicksort
). Podstawowa koncepcja tego algorytmu jest do$% prosta — nale"y z listy
warto$ci wybra% element dziel'cy, osiowy (ang. pivot), po czym podzieli% list( na dwa
zbiory, z których jeden zawiera elementy mniejsze od elementu dziel'cego, a drugi
zawiera elementy wi(ksze od wybranego elementu. Posortowana kopia listy jest uzyski-
wana poprzez sortowanie obu podzbiorów i po!'czenie odpowiednio posortowanej listy
z!o"onej z warto$ci mniejszych od elementu dziel'cego, samego elementu dziel'cego
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 wi(kszej od elementu dziel'cego. Przyk!ad sortowania listy dziesi(ciu
liczb ca!kowitych wed!ug 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ó bie%nych operacji
Mimo "e zewn(trzny interfejs tej implementacji jest zgodny z regu!ami programowania
funkcyjnego, wewn(trzne mechanizmy zaimplementowano w „tradycyjny” sposób,
poniewa" konsekwentne stosowanie modelu funkcyjnego wymaga!oby wielu dodatko-
wych operacji kopiowania. W roli elementu dziel'cego jest wybierany pierwszy element,
który jest wyodr(bniany z listy za pomoc' funkcji
splice()
. Chocia" sortowanie na
bazie tak wybranego elementu dziel'cego mo"e nie by% optymalne (liczba operacji
porównania i wymiany mo"e by% wi(ksza, ni" to konieczne), pozosta!e operacje na
strukturze typu
std::list
b(d' wykonywane szybciej dzi(ki efektywnemu przeszu-
kiwaniu listy. Wiadomo, "e wyodr(bniony element dziel'cy musi si( znaleI% na li$cie
wynikowej, zatem jest od razu umieszczany w odpowiedniej strukturze. Poniewa"
element dziel'cy b(dzie teraz porównywany z pozosta!ymi elementami, przekazujemy
referencj( do tego elementu, aby unikn'% wielokrotnego kopiowania . Mo"emy nast(p-
nie u"y% funkcji
std::partition
do podzielenia sekwencji na warto$ci mniejsze od
elementu dziel'cego i warto$ci nie mniejsze od tego elementu . Najprostszym spo-
sobem okre$lenia kryterium podzia!u jest u"ycie funkcji lambda — aby unikn'% kopio-
wania warto$ci elementu dziel'cego, zastosowano tutaj technik( przechwytywania refe-
rencji (wi(cej informacji na temat funkcji lambda mo"na znaleI% w cz($ci A.5 dodatku A).
Funkcja
std::partition()
przetwarza przekazan' list( i zwraca iterator wskazuj'cy
pierwszy element, który nie jest mniejszy od warto$ci elementu dziel'cego. Kompletny
typ iteratora mo"e by% do$% d!ugi, zatem w powy"szym kodzie u"yto mechanizmu auto-
matycznej identyfikacji typów, aby to kompilator automatycznie okre$li! odpowiedni
typ (patrz cz($% A.7 dodatku A).
Poniewa" analizowana implementacja udost(pnia interfejs zgodny z zasadami pro-
gramowania funkcyjnego, warunkiem rekurencyjnego posortowania obu „po!ówek” listy
jest utworzenie dwóch odr(bnych list. Do tego celu mo"emy ponownie u"y% funkcji
splice()
, aby skopiowa% warto$ci z listy wej$ciowej (do elementu
divide_point
) i umie-
$ci% na nowej li$cie:
lower_part
. Reszta warto$ci pozostanie na li$cie wej$ciowej.
Obie listy mo"na nast(pnie posortowa% za pomoc' rekurencyjnych wywo!a& funkcji
sequential_quick_sort()
. U"ycie funkcji
std::move()
podczas przekazywania
list na wej$ciu rekurencyjnych wywo!a& pozwala unikn'% kopiowania tych struktur
(wyniki obu wywo!a& s' kopiowane automatycznie). I wreszcie mo"emy ponownie u"y%
funkcji
splice()
w celu uporz'dkowania list reprezentuj'cych podzbiory elementów
oryginalnej struktury. Warto$ci z listy
new_higher
trafiaj' na koniec listy wynikowej
(za element dziel'cy), natomiast warto$ci z listy
new_lower
s' umieszczane na pocz'tku
listy (przed elementem dziel'cym).
S
ZYBKIE SORTOWANIE RÓWNOLEG E W MODELU PROGRAMOWANIA FUNKCYJNEGO
Poniewa" ju" w poprzednim przyk!adzie zastosowano regu!y programowania funkcyj-
nego, konwersja tego algorytmu na wersj( równoleg!' (korzystaj'c' z obiektów przy-
sz!o$ci) 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 u"yto implementacji algorytmu sortowania szybkiego !'cz'cej obiekty przy-
sz!o$ci i model programowania funkcyjnego.
Jedn' z najwa"niejszych ró"nic dziel'cych obie wersje jest to, "e w wersji wspó!-
bie"nej cz($% listy sprzed elementu dziel'cego nie jest sortowana w bie"'cym w'tku,
tylko w dodatkowym w'tku — 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ównolegYe sortowanie szybkie z wykorzystaniem przyszYoKci
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 wi(c przy u"yciu bezpo$red-
niego wywo!ania rekurencyjnego . Rekurencyjne wywo!anie funkcji
parallel_quick_
sort()
pozwala wykorzysta% dost(pn' wspó!bie"no$% sprz(tow'. Je$li wywo!anie
funkcji
std::async()
za ka"dym razem uruchamia nowy w'tek, wystarcz' trzy poziomy
rekurencji, aby program zosta! podzielony na osiem w'tków; w przypadku dziesi(ciu
poziomów rekurencji (czyli oko!o tysi'ca elementów) program w tej formie uruchomi
1024 w'tki (o ile stosowany sprz(t poradzi sobie z tak' liczb'). W razie wykrycia zbyt
du"ej liczby uruchomionych zada& (je$li na przyk!ad liczba równolegle realizowanych
zada& przekroczy dost(pn' wspó!bie"no$% sprz(tow') biblioteka mo"e przej$% w tryb
synchronicznego uruchamiania nowych zada&. Zadania b(d' wykonywane w w'tku
wywo!uj'cym funkcj(
get()
, nie w nowym w'tku, zatem program uniknie kosztów prze-
kazywania zadania pomi(dzy w'tkami, je$li koszty tej operacji nie s' rekompensowane
przez wzrost wydajno$ci. Je$li nie przekazano wprost warto$ci
std::launch::deferred
,
uruchamianie nowego w'tku dla ka"dego zadania jest w pe!ni zgodne z za!o"eniami
implementacji
std::async
(nawet je$li prowadzi do nadsubskrypcji); podobnie je$li
nie przekazano warto$ci
std::launch::async
, najlepszym rozwi'zaniem jest synchro-
niczne wykonywanie wszystkich zada&. W przypadku stosowania biblioteki oferuj'cej
mechanizmy automatycznego skalowania warto sprawdzi% w dokumentacji, jak te mecha-
nizmy b(d' dzia!a!y w kontek$cie tego algorytmu.
Zamiast funkcji
std::async()
mogliby$my u"y% w!asnej 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ó bie%nych operacji
listing 4.14). W takim przypadku nale"a!oby utworzy% obiekt klasy
std::packaged_task
dla wyniku wywo!ania funkcji, odczyta% obiekt przysz!o$ci z obiektu zadania, uruchomi%
zadanie w odpowiednim w'tku, po czym zwróci% obiekt przysz!o$ci. Takie rozwi'za-
nie samo w sobie nie przynios!oby co prawda "adnych korzy$ci (prowadzi!oby raczej
do du"ej nadsubskrypcji), ale mo"e stanowi% punkt wyj$cia dla bardziej zaawansowa-
nych implementacji, które b(d' dodawa!y zadania do kolejki w celu przetworzenia
przez w'tki robocze dost(pne w puli. Zagadnienia zwi'zane z pulami w'tkó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' pe!n' $wiadomo$%
skutków podejmowanych dzia!a& i chc' mie% pe!n' kontrol( nad sposobem budowy
puli w'tkó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
u"yli$my bezpo$redniego wywo!ania rekurencyjnego, mo"emy u"y% funkcji
splice()
tak jak w algorytmie jednow'tkowym
. Okazuje si( jednak, "e zmienna
new_lower
zawiera obiekt klasy
std::future<std::list<T>>
, nie list(, zatem przed wywo!aniem
funkcji
splice()
musimy wywo!a% funkcj(
get()
, aby uzyska% odpowiedni' warto$% .
Wywo!anie w tej formie czeka na zako&czenie zadania wykonywanego w tle, po czym
przenosi wynik do wywo!ania funkcji
splice()
. Funkcja
get()
zwraca referencj( do
r-warto$ci wyniku, zatem lista mo"e zosta% przeniesiona (wi(cej informacji na temat
referencji do r-warto$ci i operacji przenoszenia mo"na znaleI% w cz($ci A.1.1 dodatku A).
Nawet je$li przyj'%, "e funkcja
std::async()
w optymalny sposób wykorzystuje
dost(pn' wspó!bie"no$% sprz(tow', proponowana implementacja równoleg!ego algorytmu
sortowania szybkiego wci'" nie jest optymalna. Funkcja
std::partition
realizuje co
prawda znaczn' cz($% zada& zwi'zanych z dzia!aniem tego algorytmu, ale jej wywo!anie
ma charakter typowo sekwencyjny. Czytelnicy zainteresowani mo"liwie najszybsz', rów-
noleg!' implementacj' powinni si(gn'% po odpowiedni' literatur( akademick'.
Programowanie funkcyjne nie jest jedynym paradygmatem programowania wspó!-
bie"nego eliminuj'cym problem wspó!dzielenia zmiennych danych; innym przyk!adem
takiego paradygmatu jest komunikacja procesów sekwencyjnych (ang. Communicating
Sequential Processes
— CSP)
3
, gdzie w'tki s' w za!o"eniu ca!kowicie niezale"ne i nie
3
C.A.R. Hoare, Communicating Sequential Processes, Prentice Hall, 1985. Ksi'"ka jest dost(pna 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 po$red-
nictwem kana!ów komunikacyjnych. Paradygmat CSP zastosowano w j(zyku progra-
mowania Erlang (http://www.erlang.org/) oraz w $rodowisku MPI (od ang. Message
Passing Interface
) stosowanym w systemach implementowanych w j(zykach C i C++,
które musz' gwarantowa% najwy"sz' wydajno$% (http://www.mpi-forum.org/). Po tym,
co ju" napisa!em, jestem pewien, "e wiadomo$% o mo"liwo$ci implementacji tego para-
dygmatu tak"e w j(zyku C++ nie b(dzie dla czytelnika "adnym zaskoczeniem — wystar-
czy odrobina dyscypliny. Sposób implementacji tego modelu omówi( w nast(pnym
punkcie.
4.4.2.
Synchronizacja operacji za pomoc" przesy)ania komunikatów
Koncepcja paradygmatu CSP jest prosta — nie istniej' "adne wspó!dzielone dane,
a ka"dy w'tek mo"na traktowa% jako zupe!nie niezale"ny byt. Zachowanie w'tku zale"y
wy!'cznie od komunikatów, które do niego trafiaj'. Ka"dy w'tek jest wi(c swoist'
maszyn' stanów, która po otrzymaniu komunikatu aktualizuje swój stan i która mo"e
(ale nie musi) wys!a% co najmniej jeden komunikat do pozosta!ych w'tków. Sposób prze-
twarzania komunikatu zale"y od stanu pocz'tkowego „maszyny”. Jednym ze sposobów
pisania w'tków tego typu jest stworzenie formalnego modelu i implementacja sko&-
czonej maszyny stanów, jednak istniej' te" lepsze rozwi'zania — do wyra"enia maszyny
stanów mo"na u"y% odpowiedniej struktury aplikacji. To, która metoda sprawdza si(
lepiej w danym scenariuszu, zale"y od szczegó!owych wymaga& dotycz'cych zachowa&
budowanego systemu i od umiej(tno$ci zespo!u programistów. Je$li jednak zdecydu-
jemy si( na implementacj( odr(bnych w'tków, sam podzia! na niezale"ne procesy
mo"e prowadzi% do wyeliminowania wielu komplikacji zwi'zanych ze wspó!bie"nym
przetwarzaniem danych wspó!dzielonych i tym samym u!atwi% programowanie oraz
ograniczy% liczb( b!(dów.
Procesy w pe!ni zgodne z paradygmatem CSP nie operuj' na "adnych wspó!dzie-
lonych danych, a ca!a komunikacja odbywa si( za po$rednictwem kolejek komunikatów.
Poniewa" jednak w'tki j(zyka C++ wspó!dziel' przestrze& adresow', wymuszenie
tego wymagania jest niemo"liwe. W tej sytuacji bardzo du"e znaczenie ma dyscyplina
autorów aplikacji i bibliotek, poniewa" to od nas zale"y, czy nasze w'tki b(d' si( odwo-
!ywa% do wspó!dzielonych danych. Same kolejki komunikatów oczywi$cie musz' by%
wspó!dzielone (w przeciwnym razie w'tki nie mog!yby si( komunikowa%), jednak szcze-
gó!y implementacji tych kolejek mo"na opakowa% w ramach bibliotek.
WyobraImy sobie, "e implementujemy kod dla bankomatu. Kod tego systemu musi
obs!ugiwa% interakcj( z u"ytkownikiem, czyli osob' wyp!acaj'c' gotówk(, musi komu-
nikowa% si( z systemem odpowiedniego banku oraz musi sterowa% fizycznymi urz'-
dzeniami odpowiedzialnymi za akceptacj( karty, wy$wietlanie stosownych komunika-
tów, obs!ug( klawiatury, wyp!at( pieni(dzy i zwracanie karty.
Jednym ze sposobów obs!ugi wszystkich tych zada& jest podzielenie kodu na trzy
niezale"ne w'tki: jeden obs!uguj'cy fizyczne urz'dzenia, drugi implementuj'cy logik(
samego bankomatu i trzeci odpowiedzialny za komunikacj( z bankiem. W'tki mog' si(
komunikowa% wy!'cznie poprzez przekazywanie komunikatów (nie poprzez wspó!-
dzielenie jakichkolwiek danych). Na przyk!ad w'tek obs!uguj'cy fizyczne urz'dzenia
móg!by wys!a% do w'tku logiki bankomatu komunikat o w!o"eniu karty lub naci$ni(ciu
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
128
R
OZDZIA
4.
Synchronizacja wspó bie%nych operacji
przycisku przez u"ytkownika, natomiast w'tek logiki móg!by wys!a% do w'tku obs!u-
guj'cego fizyczne urz'dzenia komunikat okre$laj'cy kwot( do wyp!acenia.
Jednym ze sposobów modelowania logiki bankomatu jest opracowanie maszyny
stanów. W ka"dym stanie w'tek oczekuje na okre$lony komunikat, który jest nast(p-
nie odpowiednio przetwarzany. W wyniku przetwarzania tego komunikatu w'tek mo"e
przej$% w nowy stan i kontynuowa% ca!y cykl. Stany sk!adaj'ce si( na t( prost' imple-
mentacj( pokazano na rysunku 4.3. W tej uproszczonej implementacji system oczekuje
na umieszczenie karty w bankomacie. Po w!o"eniu karty system czeka, a" u"ytkownik
wpisze kod PIN, naciskaj'c kolejno cyfry tego kodu. U"ytkownik mo"e usun'% ostat-
ni' wpisan' cyfr(. Po wpisaniu odpowiedniej liczby cyfr system weryfikuje kod PIN.
Je$li PIN jest nieprawid!owy, cykl dzia!ania ko&czy si( — bankomat zwraca kart( i prze-
chodzi w stan oczekiwania na wsuni(cie karty przez klienta. Je$li kod PIN jest prawi-
d!owy, system czeka na anulowanie transakcji albo na wybór kwoty do wyp!acenia.
W razie anulowania transakcji cykl pracy bankomatu ko&czy si( i urz'dzenie zwraca
kart(. Je$li klient wybra! kwot(, przed wyp!aceniem gotówki system czeka na potwier-
dzenie ze strony banku, po czym albo wyp!aca gotówk(, albo wy$wietla komunikat
„brak $rodków” i (niezale"nie od wyniku weryfikacji stanu konta) wysuwa kart(. Sys-
temy prawdziwych bankomatów s' oczywi$cie bardziej skomplikowane, jednak opisana
powy"ej maszyna stanów dobrze ilustruje istot( tego rozwi'zania.
Rysunek 4.3.
Prosty model maszyny stanów dla bankomatu
Po zaprojektowaniu maszyny stanów dla logiki bankomatu mo"emy przyst'pi% do imple-
mentacji tego rozwi'zania w formie klasy, która b(dzie definiowa!a po jednej funkcji
sk!adowej dla ka"dego stanu. Ka"da funkcja sk!adowa mo"e czeka% na okre$lony zbiór
komunikatów przychodz'cych i odpowiednio obs!ugiwa% te komunikaty (obs!uga mo"e
polega% na przechodzeniu do innego stanu). Ka"dy typ komunikatów jest reprezentowany
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
4.4.
Upraszczanie kodu za pomoc$ technik synchronizowania operacji
129
przez odr(bn' struktur(. Na listingu 4.15 pokazano fragment prostej implementacji
logiki takiego systemu, w tym g!ówn' p(tl( oraz implementacj( pierwszego stanu, w któ-
rym system oczekuje na w!o"enie 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 niezb(dne operacje zwi'zane z synchronizacj' przekazywania
komunikatów zosta!y ukryte w odpowiedniej bibliotece (implementacja tej biblioteki
zostanie pokazana w dodatku C wraz z kompletnym kodem tego przyk!adu).
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
130
R
OZDZIA
4.
Synchronizacja wspó bie%nych operacji
Jak ju" wspomnia!em, opisana tutaj implementacja jest mocno uproszczona w sto-
sunku do logiki obowi'zuj'cej w prawdziwych bankomatach, jednak przyk!ad w tej
formie wystarczy do zrozumienia stylu programowania na bazie przekazywania komu-
nikatów. Nie musimy traci% czasu na projektowanie synchronizacji i rozwi'zywanie
problemów zwi'zanych z przetwarzaniem wspó!bie"nym — wystarczy ustali%, jakie
komunikaty mog' by% odbierane i przetwarzane na poszczególnych etapach oraz które
komunikaty nale"y wysy!a%. Maszyna stanów logiki bankomatu jest przetwarzana przez
jeden w'tek; pozosta!e elementy systemu, jak interfejs !'cz'cy si( z bankiem czy interfejs
terminala, s' obs!ugiwane przez odr(bne w'tki. Ten styl projektowania oprogramowania
okre$la si( mianem modelu aktorów — w systemie istnieje wiele odr(bnych aktorów
(ka"dy dzia!a w osobnym w'tku), które wymieniaj' pomi(dzy sob' komunikaty niezb(dne
do realizacji swoich zada&. W modelu aktorów nie istnieje wspó!dzielony stan (wyj'tkiem
jest mechanizm potrzebny do bezpo$redniego przekazywania komunikatów).
Dzia!anie programu rozpoczyna si( od funkcji sk!adowej
run()
, która ustawia
stan pocz'tkowy, czyli
waiting_for_card
, po czym wielokrotnie wywo!uje funkcj(
sk!adow' reprezentuj'c' bie"'cy stan (niezale"nie od tego, który to stan). Funkcje
stanów maj' posta% prostych funkcji sk!adowych klasy
atm
. Tak"e funkcja stanu
waiting_for_card
jest do$% prosta — jej dzia!anie ogranicza si( do wys!ania komu-
nikatu do interfejsu w celu wy$wietlenia na ekranie tekstu Czekam na kart7 ; zaraz
potem funkcja rozpoczyna oczekiwanie na komunikat do obs!u"enia . Jedynym rodza-
jem komunikatów, który mo"e by% obs!ugiwany w tej cz($ci kodu, jest komunikat
card_inserted
. Do jego obs!ugi u"ywamy funkcji lambda . Na wej$ciu funkcji
handle
mo"na przekaza% dowoln' funkcj( lub dowolny obiekt funkcji, jednak najprostszym
rozwi'zaniem jest u"ycie funkcji lambda. _atwo zauwa"y%, "e wywo!anie funkcji
handle()
znalaz!o si( w !a&cuchu obejmuj'cym wywo!anie funkcji
wait()
, zatem w razie otrzy-
mania komunikatu, który nie pasuje do wskazanego typu, w'tek zignoruje ten komu-
nikat i b(dzie dalej czeka! na komunikat w!a$ciwego typu.
Sama funkcja lambda zapisuje numer konta w zmiennej sk!adowej, zeruje bie"'cy
kod PIN, wysy!a komunikat do sprz(tu odpowiedzialnego za obs!ug( interfejsu ban-
komatu, aby wy$wietli% pro$b( o podanie kodu PIN, po czym przechodzi w stan po-
bierania tego kodu. Po zako&czeniu dzia!ania przez funkcj( obs!uguj'c' komunikat
funkcja stanu zwraca sterowanie, a g!ówna p(tla programu wywo!uje funkcj( nowego
stanu .
Funkcja stanu
getting_pin
jest nieco bardziej skomplikowana, poniewa" mo"e obs!u-
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 !a&cuch
wywo!ania funkcji
wait()
obejmuje a" trzy wywo!ania funkcji
handle()
. Ka"de
wywo!anie funkcji
handle()
okre$la typ komunikatu w formie parametru szablonu, po
czym przekazuje funkcj( lambda, która otrzymuje na wej$ciu komunikat okre$lonego
typu. Poniewa" wszystkie te wywo!ania umieszczono w jednym !a&cuchu wywo!a&,
implementacja funkcji
wait()
„wie”, "e czeka na komunikat
digit_pressed
,
clear_
last_pressed
lub
cancel_pressed
. Komunikaty wszystkich innych typów b(d' (tak
jak wcze$niej) ignorowane.
W tym przypadku otrzymanie komunikatu nie musi prowadzi% do zmiany stanu.
Je$li na przyk!ad w'tek otrzyma komunikat
digit_pressed
i je$li wpisana cyfra nie b(dzie
ostatni' cyfr' kodu, wystarczy t( cyfr( dopisa% do !a&cucha
pin
. G!ówna p(tla na
listingu 4.15 ponownie wywo!a funkcj(
getting_pin()
, aby czeka% na nast(pn' cyfr(
(b'dI wyzerowa% kod PIN lub anulowa% ca!' operacj().
Opisana procedura jest zgodna ze schematem pokazanym na rysunku 4.3. Ka"dy
stan przedstawiony na tym rysunku jest implementowany przez inn' funkcj( sk!adow',
która czeka na odpowiednie komunikaty i na tej podstawie aktualizuje stan systemu.
Jak wida%, opisany styl programowania mo"e znacznie upro$ci% zadanie projekto-
wania systemu wspó!bie"nego, poniewa" ka"dy w'tek mo"na traktowa% ca!kowicie
niezale"nie od pozosta!ych. W opisanym modelu wiele w'tków ma za zadanie oddzie-
lanie zagadnie& i jako takie wymagaj' od projektanta jasnych decyzji o podziale zada&
pomi(dzy w'tki.
4.5.
Podsumowanie
Synchronizacja operacji pomi(dzy w'tkami jest wa"nym aspektem pisania aplikacji
stosuj'cej techniki przetwarzania wspó!bie"nego — w razie braku synchronizacji w'tki
dzia!a!yby ca!kowicie niezale"nie, zatem równie dobrze mog!yby mie% posta% odr(bnych
aplikacji uruchamianych w formie pewnej grupy (z racji pokrewnych zada&). W tym
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
132
R
OZDZIA
4.
Synchronizacja wspó bie%nych operacji
rozdziale omówi!em rozmaite sposoby synchronizacji operacji, w tym podstawowe
zmienne warunkowe, przysz!o$ci, obietnice i opakowywane zadania. Opisa!em te" spo-
soby rozwi'zywania problemów zwi'zanych z synchronizacj', w szczególno$ci pro-
gramowanie funkcyjne, gdzie ka"de zadanie generuje wynik wy!'cznie na podstawie
danych wej$ciowych (nie uwzgl(dnia zewn(trznego $rodowiska), oraz przekazywanie
komunikatów, gdzie komunikacja pomi(dzy w'tkami odbywa si( za po$rednictwem
asynchronicznych komunikatów (wysy!anych przy u"yciu podsystemu przekazywania
komunikatów).
Skoro omówi!em ju" wiele wysokopoziomowych rozwi'za& dost(pnych w j(zyku
C++, czas przyjrze% si( odpowiednim elementom niskopoziomowym, dzi(ki którym
opisane mechanizmy mog' funkcjonowa% — w nast(pnym rozdziale skoncentrujemy si(
na modelu pami(ci j(zyka 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 wyja$nienia komu$, 358
przegl'danie kodu, 357
pytania dotycz'ce przegl'danego kodu, 358
asynchroniczne zadanie, 104
B
bariera, 316
bariery pami(ci, Patrz ogrodzenia
biblioteki j(zyka C++, 29
ACE, 29
Boost, 29
Boost Thread Library, 30
C++ Thread Library, 30
efektywno$% klas, 30
mechanizm przysz!o$ci, 103
okres, 117
przysz!o$ci unikatowe, 103
przysz!o$ci wspó!dzielone, 103
punkt w czasie, 118
RAII, 29
standardowa, 31
typy wywo!ywalne, 36
wolne funkcje, 150
zegar, 115
blokady wiruj'ce, 221
b!'dzenie, Patrz uwi(zienie
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
dyndaj'cy wskaInik, 226
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
564
Skorowidz
E
empty(), 64, 102, 188
exchange(), 140, 143
F
fa!szywe 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 pocz'tkowa, 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
domy$lne, 377
dokumentacja, 378
wymuszanie generowania funkcji, 378
wymuszenie deklarowania konstruktora
kopiuj'cego, 378
wymuszenie generowania destruktora
wirtualnego, 378
zmiana dost(pno$ci 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
wyra"enie lambda, 386
z konstrukcj' rozpoczynaj'c', 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
niesk!adowe, 150
notify_one(), 96
now(), 116
open_connection(), 87
parallel_accumulate(), 291, 296, 329
parallel_quick_sort(), 126, 275
pocz'tkowa, 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-
ca!kowitoliczbowy>::fetch_add, 476
std::atomic<typ-
ca!kowitoliczbowy>::fetch_and, 478
std::atomic<typ-ca!kowitoliczbowy>::fetch_or,
479
std::atomic<typ-
ca!kowitoliczbowy>::fetch_sub, 477
std::atomic<typ-
ca!kowitoliczbowy>::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 w'tków, 52
identyfikatory w'tków, 52
interrupt(), 340, 342, 349
interruptible_wait(), 343, 348
interruption_point(), 341, 344, 351
is_lock_free(), 138
iteratory jednokrotnego przebiegu, 52
iteratory post(puj'ce, 52
J
j(zyk C++, 19
automatyczne okre$lanie typu zmiennej, 395
biblioteka operacji atomowych, 31
biblioteka standardowa, 31
biblioteka w'tków, 30
biblioteki, 29
efektywno$% klas, 30
frameworki aplikacji, 29
mechanizm deklarowania funkcji
jako usuni(tej, 376
mechanizm przysz!o$ci, 103
miejsce w pami(ci, 134
model pami(ci, 133
muteks, 60
obiekty, 134
obs!uga wspó!bie"no$ci, 28, 30
operacje atomowe, 137
porz'dek modyfikacji, 136
RAII, 29
referencje do r-warto$ci, 371
semantyka przenoszenia danych, 372
szablony zmiennoargumentowe, 391
paczka parametrów, 392
rozwini(cie paczki, 392
typy definiowane przez u"ytkownika, 382
inicjalizacja statyczna, 384
warstwy abstrakcji, 30
wyra"enia sta!e, 381
zastosowania, 381
wyra"enie lambda, 37
wy$cig danych, 58
zmienne lokalne w'tkó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 domy$lny, 52
konstruktor przenosz'cy, 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 pami(ci podr(cznej, 284
list_contains(), 61
load(), 140, 143
lock(), 60, 79, 80, 142
l-warto$%, 80
M
main(), 33, 36
mechanizm przysz!o$ci, 52, 102, 103
asynchroniczne zadanie, 104
obietnice, 109
oczekiwanie na wiele w'tków, 112
przysz!o$ci unikatowe, 103
przysz!o$ci wspó!dzielone, 103
wi'zanie zadania z przysz!o$ci', 106
wynik oblicze& wykonywanych w tle, 103
wy$cig danych, 112
zapisywanie wyj'tku, 111
memcmp(), 148
memcpy(), 148
model aktorów, 130
model pami(ci j(zyka C++, 133
analiza podstawowych cech strukturalnych,
134
mechanizmy przetwarzania wspó!bie"nego,
134
miejsce w pami(ci, 134
modele porz'dkowania spójnego
niesekwencyjnie, 159
niezdefiniowane zachowanie, 136
obiekty, 134
ogrodzenia, 178
operacje atomowe, 136
podzia! struktury, 135
porz'dek modyfikacji, 136
porz'dkowania pami(ci, 155
porz'dkowanie poprzez wzajemne
wykluczanie, 155, 166
operacje uzyskiwania, 166
operacje zwalniania, 166
porz'dkowanie spójne sekwencyjnie, 155, 156
porz'dkowanie z!agodzone, 155, 160
wyja$nienie porz'dkowania, 164
relacja poprzedzania, 152, 154
poprzedzanie wed!ug zale"no$ci, 173
przechodnio$%, 170
relacja wprowadzania zale"no$ci, 173
relacja synchronizacji, 152
sekwencja zwalniania, 175
wy$cig 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 w!asno$ci, 80
rekurencyjny, 90
r-warto$%, 80
stosowanie w j(zyku C++, 60
szczegó!owo$% blokady, 82
wiruj'cy, 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 przysz!o$ci, 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 obs!ug' iteracji, 214
implementacja tablicy wyszukiwania, 210
jednow'tkowa 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 w(z!em, 196
leniwa inicjalizacja, 85
lista jednokierunkowa, 194
metody zapewniania bezpiecze&stwa, 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 w!asno$ci muteksu, 80
stosowanie konstruktora, 67
struktury danych bez blokad, 220
sytuacja wy$cigu, 58
szczegó!owo$% blokady, 82
szeregowanie, 185
tablica wyszukiwania, 207
unikanie zakleszcze&, 71
wykrywanie sytuacji wy$cigu, 63
zakleszczenie, 71
zwracanie wskaInika, 67
ogrodzenia, 178
open_connection(), 87
operacje atomowe, 136, 137
funkcje niesk!adowe, 150
g!ówny szablon, 147
modele porz'dkowania spójnego
niesekwencyjnie, 159
ogrodzenia, 178
operacje dost(pne 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
porz'dkowanie pami(ci, 155
porz'dkowanie poprzez wzajemne
wykluczanie, 155, 166
operacje uzyskiwania, 166
operacje zwalniania, 166
porz'dkowanie spójne sekwencyjnie, 155, 156
porz'dkowanie z!agodzone, 155, 160
wyja$nienie porz'dkowania, 164
pozorny b!'d, 144
relacja poprzedzania, 152, 154
poprzedzanie wed!ug zale"no$ci, 173
przechodnio$%, 170
relacja wprowadzania zale"no$ci, 173
relacja synchronizacji, 152
sekwencja zwalniania, 175
rozkazy porównywania i wymiany podwójnego
s!owa, 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 przysz!o$ci, 122
rekurencyjne sortowanie, 123
równoleg!e sortowanie szybkie, 125
wnioskowanie typów zmiennych, 122
projektowanie uniwersalnej kolejki, 97
projektowanie wspó!bie"nego kodu, 269
bezpiecze&stwo wyj'tków, 291, 293, 297
algorytmy równoleg!e, 291
czynniki wp!ywaj'ce na wydajno$% kodu, 279
fa!szywe wspó!dzielenie, 284
liczba procesorów, 280
nadsubskrypcja, 280, 285
niskie wspó!zawodnictwo, 282
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
570
Skorowidz
projektowanie wspó!bie"nego kodu
ping–pong buforów, 282
prze!'czanie zada&, 285
wspó!zawodnictwo o dane, 281
wybór najlepszego algorytmu, 281
wysokie wspó!zawodnictwo, 282
zmiana elementu danych, 280
fa!szywe wspó!dzielenie, 287
!atwo$% testowania, 361
eliminacja wspó!bie"no$ci, 362
warunki struktury kodu, 361
mno"enie macierzy, 287
podzia! elementów tablicy, 287
potok, 278
praktyka, 303
bariera, 316
implementacja równoleg!ego algorytmu
wyszukiwania, 307
równoleg!a implementacja funkcji
partial_sum, 319
równoleg!a wersja funkcji std::for_each, 304
równoleg!e obliczanie sum cz($ciowych, 313
prawo Amdahla, 299
pula w'tków, 276
s'siedztwo danych, 287
skalowalno$%, 291, 298
techniki dzielenia pracy pomi(dzy w'tki, 270
dzielenie przed rozpocz(ciem przetwarzania,
271
dzielenie sekwencji zada&, 278
dzielenie wed!ug typu zadania, 276
podzia! s'siaduj'cych fragmentów danych,
272
rekurencyjne dzielenie danych, 272, 273
równoleg!y algorytm sortowania szybkiego,
273
sposób izolowania zagadnie&, 277
techniki przetwarzania równoleg!ego, 301
ukrywanie opóInie&, 300
wspó!zawodnictwo, 286
wzorce dost(pu do danych, 289
przekazywanie argumentów do funkcji w'tku, 43
konstruktor przenosz'cy, 45
kopiowane, 43
operator przypisania z przenoszeniem, 45
przenoszenie, 45
prze!'czanie kontekstu, 21
prze!'czanie zada&, 21, 22
przenoszenie w!asno$ci w'tku, 46, 47
przetwarzanie wspó!bie"ne, 29
bezpiecze&stwo, 184
definicja klasy kolejki, 190
definicja klasy stosu, 68
implementacja listy z obs!ug' iteracji, 214
implementacja tablicy wyszukiwania, 210
kolejka z mechanizmami blokowania i
oczekiwania, 203
kolejka ze szczegó!owymi blokadami, 198
mechanizmy przysz!o$ci, 102
mi(dzyw'tkowa relacja poprzedzania, 155
niechciane blokowanie, 354
oczekiwanie na zewn(trzne dane wej$ciowe,
355
uwi(zienie, 354
zakleszczenie, 354
oczekiwanie na zdarzenie, 94
stos bez blokad, 227, 250
synchronizacja operacji, 93
sytuacje wy$cigu, 355
naruszone niezmienniki, 355
problemy zwi'zane z czasem "ycia, 356
wy$cig danych, 355
tablica mieszaj'ca, 209
tablica wyszukiwania, 207
techniki lokalizacji b!(dów, 357
analiza kodu, 357
próba szczegó!owego wyja$nienia komu$, 358
pytania dotycz'ce przegl'danego kodu, 358
testowanie wspó!bie"nego kodu, 359
wspó!dzielenie danych przez w'tki, 55
wywo!anie blokuj'ce z limitem czasowym, 115
zarz'dzanie w'tkami, 36
identyfikowanie w'tków, 52
mechanizm przysz!o$ci, 52
oczekiwanie na zako&czenie w'tku, 39
oczekiwanie w razie wyst'pienia wyj'tku, 39
od!'czenie w'tku, 41
przekazywanie argumentów do funkcji w'tku,
43
przenoszenie w!asno$ci w'tku, 46
uruchamianie w'tków w tle, 42
uruchamianie w'tku, 36
w'tki demonów, 42
wybór liczby w'tków, 49
zmienna warunkowa, 95
pula w'tków, 106, 276, 324
wi'zanie zadania z przysz!o$ci', 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-warto$ci, 371
semantyka przenoszenia danych, 372
konstruktor kopiuj'cy, 374
konstruktor przenosz'cy, 374
relacja poprzedzania, 154
poprzedzanie wed!ug zale"no$ci, 173
przechodnio$%, 170
relacja wprowadzania zale"no$ci, 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
s!owa, 149
równoleg!o$%, Patrz zrównoleglanie zada&
równoleg!o$% danych, 26
run(), 130
run_pending_task(), 331, 335
r-warto$%, 80
S
s'siedztwo 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-ca!kowitoliczbowy>::fetch_add,
476
std::atomic<typ-ca!kowitoliczbowy>::fetch_and,
478
std::atomic<typ-ca!kowitoliczbowy>::fetch_or,
479
std::atomic<typ-ca!kowitoliczbowy>::fetch_sub,
477
std::atomic<typ-ca!kowitoliczbowy>::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ó!bie"nych operacji, 93
definicja klasy kolejki, 100
funkcje otrzymuj'ce limity czasowe, 121
komunikacja procesów sekwencyjnych, 126
mechanizmy przysz!o$ci, 102
obietnice, 109
oczekiwanie na wiele w'tków, 112
oczekiwanie na zdarzenie, 94
operacje atomowe, 137
porz'dek modyfikacji, 136
pozorne budzenie, 97
programowanie funkcyjne, 122
projektowanie uniwersalnej kolejki, 97
prosta kolejka komunikatów, 401
przekazywanie zada& pomi(dzy w'tkami, 107
upraszczanie kodu, 121
wi'zanie zadania z przysz!o$ci', 106
wynik oblicze& wykonywanych w tle, 103
wy$cig danych, 112
wywo!anie blokuj'ce z limitem czasowym, 115
zapisywanie wyj'tku na potrzeby przysz!o$ci,
111
zmienna warunkowa, 95
sytuacja wy$cigu, 58, 355
definicja klasy stosu, 68
przekazywanie referencji, 66
stosowanie konstruktora, 67
zwracanie wskaInika, 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 mieszaj'ca, 209
kube!ek, 209
tablica posortowana, 209
tablica wyszukiwania, 207
operacje, 208
test_and_set(), 138, 141
testowanie wspó!bie"nego kodu, 360
biblioteka podstawowych mechanizmów, 365
czynniki dotycz'ce $rodowiska testowego, 361
projektowanie struktury wielow'tkowego kodu
testowego, 366
identyfikacja odr(bnych fragmentów
poszczególnych testów, 366
przyk!ad 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ó!bie"nego kodu
testowanie wydajno$ci, 369
skalowalno$%, 369
testy si!owe, 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 wywo!ywalne, 36
U
unlock(), 60, 80, 348
update_data_for_widget, 44
uwi(zienie, 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
w'tki demonów, 42
w'tki sprz(towe, 21
wnioskowanie typów zmiennych, 122
worker_thread(), 326, 335
wskaIniki ryzyka, 233
wspó!bie"ne struktury danych, 184
aktywne oczekiwanie, 261
algorytmy blokuj'ce, 220
bezpiecze&stwo przetwarzania
wielow'tkowego, 184
blokady wiruj'ce, 221
definicja klasy kolejki, 190
definicja klasy stosu, 187
drzewo binarne, 209
implementacja listy z obs!ug' iteracji, 214
implementacja tablicy wyszukiwania, 210
jednow'tkowa implementacja kolejki, 195
kolejka bez blokad, 252
uzyskiwanie nowej referencji, 259
zwalnianie licznika zewn(trznego w(z!a, 260
zwalnianie referencji do w(z!a, 258
kolejka nieograniczona, 206
kolejka ograniczona, 206
kolejka z mechanizmami blokowania
i oczekiwania, 203
kolejka ze szczegó!owymi blokadami, 198
kolejka ze sztucznym w(z!em, 196
kolejk' z jednym producentem i jednym
konsumentem, 253
lista jednokierunkowa, 194
problem ABA, 266
projektowanie przy u"yciu blokad, 186
stos bez blokad, 227, 250
struktury bez blokad, 220, 221
eliminowanie niebezpiecznych wycieków, 228
kolejka, 252
mechanizm odzyskiwania pami(ci, 230
problem ABA, 266
stos, 227
uwi(zienie, 223
wskazówki dotycz'ce pisania struktur, 264
zalety i wady, 222
zarz'dzanie pami(ci', 228
zliczanie referencji, 242
zwalnianie w(z!ów, 229
struktury bez oczekiwania, 222
szeregowanie, 185
tablica mieszaj'ca, 209
kube!ek, 209
tablica posortowana, 209
tablica wyszukiwania, 207
wskazówki dotycz'ce projektowania, 185
wskaIniki ryzyka, 233
implementacja funkcji odzyskuj'cych w(z!y, 238
strategie odzyskiwania w(z!ów, 240
wykrywanie w(z!ów, 233
wywo!ania blokuj'ce, 220
zag!odzenie, 221
zliczanie referencji, 242
wspó!bie"no$%, 20
bezpiecze&stwo przetwarzania, 184
mechanizm przysz!o$ci, 102
modele, 22
nadsubskrypcja, 280
oczekiwanie na zdarzenie, 94
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
Skorowidz
575
operacje atomowe, 136, 137
podniesienia wydajno$ci, 26
podzia! zagadnie&, 25
projektowanie struktury danych, 184
prze!'czanie kontekstu, 21
prze!'czanie zada&, 21, 22
przyk!ad programu, 32
równoleg!o$% danych, 26
synchronizacja operacji, 93
w j(zyku C++, 28
w'tki sprz(towe, 21
wspó!bie"ne struktury danych, 184
z wieloma procesami, 23
z wieloma w'tkami, 24
zarz'dzanie w'tkami, 36
zmienna warunkowa, 95
zrównoleglanie zada&, 26
wspó!dzielenie danych przez w'tki, 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 w!asno$ci muteksu, 80
sytuacja wy$cigu, 58
szczegó!owo$% blokady, 82
wy$cigu danych, 58
zakleszczenie, 71
wspó!zawodnictwo, 286
wybór liczby w'tków, 49
nadsubskrypcja, 51
wyra"enie lambda, 37
wysokie wspó!zawodnictwo, 282
zwi(kszenie prawdopodobie&stwa, 283
wy$cig danych, 58, 112, 136, 355
niezdefiniowane zachowanie, 58
wywo!anie blokuj'ce z limitem czasowym, 115
funkcje otrzymuj'ce limity czasowe, 121
limity bezwzgl(dne, 115
maksymalny czas blokowania w'tku, 115
okres, 117
punkt w czasie, 118
wymuszanie oczekiwania na podstawie okresu,
117
zastosowanie limitu czasowego, 120
zegar, 115
Z
zaawansowane zarz'dzanie w'tkami, 323
przerywanie wykonywania w'tków, 340
monitorowanie systemu plików w tle, 350
obs!uga przerwa&, 349
oczekiwanie na zmienn', 343, 346
pozosta!e wywo!ania blokuj'ce, 348
przerywanie zada& wykonywanych w tle, 350
punkt przerwania, 341
wykrywanie przerwania, 342
pula w'tków, 324
algorytm sortowania szybkiego, 330
implementacja algorytmu sortowania
szybkiego, 332
implementacja prostej puli w'tków, 325
kolejka umo"liwiaj'ca wykradanie zada&, 336
lokalne kolejki zada&, 334
z mechanizmem oczekiwania na zadanie, 327
z mechanizmem wykradania zada&, 337
unikanie wspó!zawodnictwa w dost(pie do
kolejki, 333
w'tek roboczy, 324
wykradanie zada&, 335
zakleszczenie, 71, 354
hierarchia blokad, 75
unikanie, 71, 73
zasada jednej odpowiedzialno$ci, 277
zegar, 115
czasu rzeczywistego, 116
epoka zegara, 118
najkrótszy mo"liwy takt, 116
okres taktu, 116
stabilny, 116
zegar::now(), 116
zliczanie referencji, 242
licznik wewn(trzny, 243
licznik zewn(trzny, 243
stos bez blokad, 250
umieszczanie w(z!a na stosie bez blokad, 243
wykrywanie u"ywanych w(z!ów, 242
zdejmowanie w(z!a ze stosu bez blokad, 245
zmienna warunkowa, 95
definicja klasy kolejki, 100
oczekiwanie na spe!nienie warunku, 95
pozorne budzenie, 97
projektowanie uniwersalnej kolejki, 97
zrównoleglanie
zada&,
26
Pole
ü ksiąĪkĊ
Kup ksi
ąĪkĊ
Wyszukiwarka
Podobne podstrony:
Jezyk C i przetwarzanie wspolbiezne w akcji
Jezyk C i przetwarzanie wspolbiezne w akcji
informatyka jezyk c pierwsze starcie zbigniew koza ebook
informatyka wtyczki do wordpressa programowanie dla profesjonalistow brad williams ebook
informatyka jezyk inzynierii systemow sysml architektura i zastosowania profile uml 2 x w praktyce s
informatyka jezyk c dla mikrokontrolerow avr od podstaw do zaawansowanych aplikacji tomasz francuz e
Matura Informator Język litewski
wyklady-pwir, Studia, 6. Semestr, Przetwazanie wspolbiezne
Cwicz07KluczBD1TE1, Studia WIT - Informatyka, POB - Przetwarzanie obrazów
Cwicz06KluczBD1TE2(1), Studia WIT - Informatyka, POB - Przetwarzanie obrazów
Matura Informator Język ukrainski
lab5 Przetwarzanie wspolbiezne Nieznany
Cwicz10KluczBD1TE1, Studia WIT - Informatyka, POB - Przetwarzanie obrazów
WzorSpr, Studia WIT - Informatyka, POB - Przetwarzanie obrazów
lab 3 5 Przetwarzanie współbieżne
Matura Informator Język kaszubski
Cwicz05KluczBD1TE2, Studia WIT - Informatyka, POB - Przetwarzanie obrazów
prezentacja konrad, NAUKA, Technikum informatyczne, Język polski
więcej podobnych podstron