Jezyk C i przetwarzanie wspolbiezne w akcji

background image
background image

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ść

background image

Spis treci

Sowo wstpne .......................................................................................................................................... 11
Podzikowania .......................................................................................................................................... 13
O tej ksice .............................................................................................................................................. 15

Rozdzia 1. Witaj, wiecie wspóbienoci w C++!

19

1.1.

Czym jest wspóbieno? ........................................................................................................... 20
1.1.1. Wspóbieno w systemach komputerowych ................................................................. 20
1.1.2. Modele wspóbienoci ..................................................................................................... 22

1.2.

Dlaczego warto stosowa wspóbieno? ................................................................................. 25
1.2.1. Stosowanie wspóbienoci do podziau zagadnie ......................................................... 25
1.2.2. Stosowanie wspóbienoci do podniesienia wydajnoci ................................................. 26
1.2.3. Kiedy nie naley stosowa wspóbienoci ....................................................................... 27

1.3.

Wspóbieno i wielowtkowo w jzyku C++ .................................................................... 28
1.3.1. Historia przetwarzania wielowtkowego w jzyku C++ ................................................ 29
1.3.2. Obsuga wspóbienoci w nowym standardzie ............................................................... 30
1.3.3. Efektywno biblioteki wtków jzyka C++ .................................................................. 30
1.3.4. Mechanizmy zwizane z poszczególnymi platformami ................................................... 32

1.4. Do

dziea!

...................................................................................................................................... 32

1.4.1. „Witaj wiecie wspóbienoci” ......................................................................................... 32

1.5. Podsumowanie

.............................................................................................................................. 34

Rozdzia 2. Zarzdzanie wtkami

35

2.1. Podstawowe

zarzdzanie

wtkami

............................................................................................. 36

2.1.1 Uruchamianie

wtku .......................................................................................................... 36

2.1.2. Oczekiwanie na zakoczenie wtku .................................................................................. 39
2.1.3. Oczekiwanie w razie wystpienia wyjtku ....................................................................... 39
2.1.4. Uruchamianie wtków w tle .............................................................................................. 42

2.2. Przekazywanie

argumentów

do funkcji wtku ......................................................................... 43

2.3. Przenoszenie

wasnoci wtku .................................................................................................... 46

2.4.

Wybór liczby wtków w czasie wykonywania ........................................................................... 49

2.5. Identyfikowanie

wtków

............................................................................................................. 52

2.6. Podsumowanie

.............................................................................................................................. 54

Rozdzia 3. Wspódzielenie danych przez wtki

55

3.1.

Problemy zwizane ze wspódzieleniem danych przez wtki ................................................. 56
3.1.1. Sytuacja wycigu ................................................................................................................ 58
3.1.2. Unikanie problematycznych sytuacji wycigu .................................................................. 59

3.2. Ochrona

wspódzielonych

danych

za pomoc muteksów ........................................................ 60

3.2.1. Stosowanie muteksów w jzyku C++ ............................................................................. 60
3.2.2. Projektowanie struktury kodu z myl o ochronie wspódzielonych danych ................. 62

Kup książkę

Poleć książkę

background image

6

Spis treci

3.2.3. Wykrywanie sytuacji wycigu zwizanych z interfejsami ................................................ 63
3.2.4. Zakleszczenie: problem i rozwizanie .............................................................................. 71
3.2.5. Dodatkowe wskazówki dotyczce unikania zakleszcze ................................................. 73
3.2.6. Elastyczne blokowanie muteksów za pomoc szablonu std::unique_lock ...................... 79
3.2.7. Przenoszenie wasnoci muteksu pomidzy zasigami .................................................... 80
3.2.8. Dobór waciwej szczegóowoci blokad .......................................................................... 82

3.3.

Alternatywne mechanizmy ochrony wspódzielonych danych ................................................ 84
3.3.1. Ochrona wspódzielonych danych podczas inicjalizacji .................................................. 84
3.3.2. Ochrona rzadko aktualizowanych struktur danych .......................................................... 88
3.3.3. Blokowanie rekurencyjne .................................................................................................. 90

3.4. Podsumowanie

.............................................................................................................................. 91

Rozdzia 4. Synchronizacja wspóbienych operacji

93

4.1.

Oczekiwanie na zdarzenie lub inny warunek ........................................................................... 94
4.1.1. Oczekiwanie na spenienie warunku za pomoc zmiennych warunkowych .................. 95
4.1.2. Budowa kolejki gwarantujcej bezpieczne przetwarzanie wielowtkowe

przy uyciu zmiennych warunkowych .............................................................................. 97

4.2.

Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci ........................................... 102
4.2.1. Zwracanie wartoci przez zadania wykonywane w tle ................................................... 103
4.2.2. Wizanie zadania z przyszoci ...................................................................................... 106
4.2.3. Obietnice (szablon std::promise) ..................................................................................... 109
4.2.4. Zapisywanie wyjtku na potrzeby przyszoci ................................................................ 111
4.2.5. Oczekiwanie na wiele wtków ........................................................................................ 112

4.3. Oczekiwanie

z

limitem

czasowym

............................................................................................ 115

4.3.1. Zegary ............................................................................................................................... 115
4.3.2. Okresy ............................................................................................................................... 117
4.3.3. Punkty w czasie ................................................................................................................ 118
4.3.4. Funkcje otrzymujce limity czasowe .............................................................................. 120

4.4.

Upraszczanie kodu za pomoc technik synchronizowania operacji ..................................... 121
4.4.1. Programowanie funkcyjne przy uyciu przyszoci ....................................................... 122
4.4.2. Synchronizacja operacji za pomoc przesyania komunikatów ..................................... 127

4.5. Podsumowanie

............................................................................................................................ 131

Rozdzia 5. Model pamici jzyka C++ i operacje na typach atomowych

133

5.1.

Podstawowe elementy modelu pamici ................................................................................... 134
5.1.1. Obiekty i miejsca w pamici ............................................................................................ 134
5.1.2. Obiekty, miejsca w pamici i przetwarzanie wspóbiene ............................................ 135
5.1.3. Kolejno modyfikacji ...................................................................................................... 136

5.2.

Operacje i typy atomowe jzyka C++ .................................................................................... 137
5.2.1. Standardowe typy atomowe ............................................................................................ 138
5.2.2. Operacje na typie std::atomic_flag .................................................................................. 141
5.2.3. Operacje na typie std::atomic<bool> ............................................................................ 143
5.2.4. Operacje na typie std::atomic<T*> — arytmetyka wskaników ................................. 146
5.2.5. Operacje na standardowych atomowych typach cakowitoliczbowych ........................ 147
5.2.6. Gówny szablon klasy std::atomic<> ............................................................................. 147
5.2.7. Wolne funkcje dla operacji atomowych .......................................................................... 150

5.3.

Synchronizacja operacji i wymuszanie ich porzdku ............................................................ 151
5.3.1. Relacja synchronizacji ...................................................................................................... 152
5.3.2. Relacja poprzedzania ....................................................................................................... 154
5.3.3. Porzdkowanie pamici na potrzeby operacji atomowych ............................................ 155
5.3.4. Sekwencje zwalniania i relacja synchronizacji ............................................................... 175

Poleć książkę

Kup książkę

background image

Spis treci

7

5.3.5. Ogrodzenia ....................................................................................................................... 178
5.3.6. Porzdkowanie operacji nieatomowych za pomoc operacji atomowych ..................... 180

5.4. Podsumowanie

............................................................................................................................ 182

Rozdzia 6. Projektowanie wspóbienych struktur danych przy uyciu blokad

183

6.1.

Co oznacza projektowanie struktur danych pod ktem wspóbienoci? ............................ 184
6.1.1. Wskazówki dotyczce projektowania wspóbienych struktur danych ........................ 185

6.2.

Projektowanie wspóbienych struktur danych przy uyciu blokad .................................... 186
6.2.1. Stos gwarantujcy bezpieczestwo przetwarzania wielowtkowego

przy uyciu blokad ........................................................................................................... 187

6.2.2. Kolejka gwarantujca bezpieczestwo przetwarzania wielowtkowego

przy uyciu blokad i zmiennych warunkowych ............................................................. 190

6.2.3. Kolejka gwarantujca bezpieczestwo przetwarzania wielowtkowego

przy uyciu szczegóowych blokad i zmiennych warunkowych .................................... 194

6.3.

Projektowanie zoonych struktur danych przy uyciu blokad ............................................. 207
6.3.1. Implementacja tablicy wyszukiwania gwarantujcej bezpieczestwo

przetwarzania wielowtkowego przy uyciu blokad ...................................................... 207

6.3.2. Implementacja listy gwarantujcej bezpieczestwo przetwarzania

wielowtkowego przy uyciu blokad .............................................................................. 213

6.4. Podsumowanie

............................................................................................................................ 218

Rozdzia 7. Projektowanie wspóbienych struktur danych bez blokad

219

7.1.

Definicje i ich praktyczne znaczenie ....................................................................................... 220
7.1.1. Rodzaje nieblokujcych struktur danych ........................................................................ 220
7.1.2. Struktury danych bez blokad ........................................................................................... 221
7.1.3. Struktury danych bez oczekiwania ................................................................................. 222
7.1.4. Zalety i wady struktur danych bez blokad ...................................................................... 222

7.2.

Przykady struktur danych bez blokad .................................................................................... 223
7.2.1. Implementacja stosu gwarantujcego bezpieczestwo przetwarzania

wielowtkowego bez blokad ............................................................................................ 224

7.2.2. Eliminowanie niebezpiecznych wycieków — zarzdzanie pamici

w strukturach danych bez blokad .................................................................................... 228

7.2.3. Wykrywanie wzów, których nie mona odzyska, za pomoc wskaników ryzyka ........ 233
7.2.4. Wykrywanie uywanych wzów metod zliczania referencji .......................................... 242
7.2.5. Zmiana modelu pamici uywanego przez operacje na stosie bez blokad ................... 247
7.2.6. Implementacja kolejki gwarantujcej bezpieczestwo przetwarzania

wielowtkowego bez blokad ............................................................................................ 252

7.3.

Wskazówki dotyczce pisania struktur danych bez blokad ................................................... 264
7.3.1. Wskazówka: na etapie tworzenia prototypu naley stosowa tryb

std::memory_order_seq_cst ............................................................................................ 265

7.3.2. Wskazówka: naley uywa schematu odzyskiwania pamici bez blokad .................... 265
7.3.3 Wskazówka: naley unika problemu ABA .................................................................... 266
7.3.4. Wskazówka: naley identyfikowa ptle aktywnego oczekiwania i wykorzystywa

czas bezczynnoci na wspieranie innego wtku ............................................................. 267

7.4. Podsumowanie

............................................................................................................................ 267

Rozdzia 8. Projektowanie wspóbienego kodu

269

8.1.

Techniki dzielenia pracy pomidzy wtki ............................................................................... 270
8.1.1. Dzielenie danych pomidzy wtki przed rozpoczciem przetwarzania ....................... 271
8.1.2. Rekurencyjne dzielenie danych ...................................................................................... 272
8.1.3. Dzielenie pracy wedug typu zadania ............................................................................. 276

Poleć książkę

Kup książkę

background image

8

Spis treci

8.2.

Czynniki wpywajce na wydajno wspóbienego kodu ..................................................... 279
8.2.1. Liczba procesorów ........................................................................................................... 280
8.2.2. Wspózawodnictwo o dane i ping-pong bufora .............................................................. 281
8.2.3. Faszywe wspódzielenie ................................................................................................. 284
8.2.4. Jak blisko naley rozmieci dane? ................................................................................. 285
8.2.5. Nadsubskrypcja i zbyt intensywne przeczanie zada ................................................. 285

8.3.

Projektowanie struktur danych pod ktem wydajnoci przetwarzania wielowtkowego ..... 286
8.3.1. Podzia elementów tablicy na potrzeby zoonych operacji .......................................... 287
8.3.2. Wzorce dostpu do danych w pozostaych strukturach ................................................. 289

8.4.

Dodatkowe aspekty projektowania wspóbienych struktur danych ................................... 291
8.4.1. Bezpieczestwo wyjtków w algorytmach równolegych .............................................. 291
8.4.2. Skalowalno i prawo Amdahla ....................................................................................... 298
8.4.3. Ukrywanie opónie za pomoc wielu wtków .............................................................. 300
8.4.4. Skracanie czasu reakcji za pomoc technik przetwarzania równolegego .................... 301

8.5.

Projektowanie wspóbienego kodu w praktyce ..................................................................... 303
8.5.1. Równolega implementacja funkcji std::for_each ........................................................... 304
8.5.2. Równolega implementacja funkcji std::find .................................................................. 306
8.5.3. Równolega implementacja funkcji std::partial_sum ..................................................... 312

8.6. Podsumowanie

............................................................................................................................ 322

Rozdzia 9. Zaawansowane zarzdzanie wtkami

323

9.1. Pule

wtków

................................................................................................................................ 324

9.1.1. Najprostsza moliwa pula wtków .................................................................................. 324
9.1.2. Oczekiwanie na zadania wysyane do puli wtków ........................................................ 327
9.1.3. Zadania oczekujce na inne zadania ............................................................................... 330
9.1.4. Unikanie wspózawodnictwa w dostpie do kolejki zada ............................................ 333
9.1.5. Wykradanie zada ............................................................................................................ 335

9.2. Przerywanie

wykonywania

wtków .......................................................................................... 340

9.2.1. Uruchamianie i przerywanie innego wtku .................................................................... 340
9.2.2. Wykrywanie przerwania wtku ....................................................................................... 342
9.2.3. Przerywanie oczekiwania na zmienn warunkow ........................................................ 343
9.2.4. Przerywanie oczekiwania na zmienn typu std::condition_variable_any ..................... 346
9.2.5. Przerywanie pozostaych wywoa blokujcych ............................................................ 348
9.2.6. Obsuga przerwa ............................................................................................................ 349
9.2.7. Przerywanie zada wykonywanych w tle podczas zamykania aplikacji ........................ 350

9.3. Podsumowanie

............................................................................................................................ 352

Rozdzia 10. Testowanie i debugowanie aplikacji wielowtkowych

353

10.1. Rodzaje bdów zwizanych z przetwarzaniem wspóbienym ............................................ 354

10.1.1. Niechciane

blokowanie

............................................................................................... 354

10.1.2. Sytuacje

wycigu

......................................................................................................... 355

10.2. Techniki

lokalizacji

bdów

zwizanych

z przetwarzaniem wspóbienym ........................ 357

10.2.1.

Przegldanie kodu w celu znalezienia ewentualnych bdów .................................. 357

10.2.2.

Znajdowanie bdów zwizanych z przetwarzaniem wspóbienym

poprzez testowanie kodu ................................................................................................. 359

10.2.3.

Projektowanie kodu pod ktem atwoci testowania ................................................. 361

10.2.4.

Techniki testowania wielowtkowego kodu .............................................................. 363

10.2.5.

Projektowanie struktury wielowtkowego kodu testowego ...................................... 366

10.2.6. Testowanie

wydajnoci

wielowtkowego kodu ......................................................... 369

10.3. Podsumowanie

............................................................................................................................ 370

Poleć książkę

Kup książkę

background image

Spis treci

9

Dodatek A Krótki przegld wybranych elementów jzyka C++11

371

A.1. Referencje do r-wartoci ........................................................................................................... 371

A.1.1. Semantyka przenoszenia danych ..................................................................................... 372
A.1.2. Referencje do r-wartoci i szablony funkcji .................................................................... 375

A.2. Usunite

funkcje

......................................................................................................................... 376

A.3. Funkcje

domylne

...................................................................................................................... 377

A.4. Funkcje

constexpr

...................................................................................................................... 381

A.4.1. Wyraenia constexpr i typy definiowane przez uytkownika ........................................ 382
A.4.2. Obiekty constexpr ............................................................................................................ 385
A.4.3. Wymagania dotyczce funkcji constexpr ........................................................................ 385
A.4.4. Sowo constexpr i szablony .............................................................................................. 386

A.5. Funkcje

lambda

.......................................................................................................................... 386

A.5.1. Funkcje lambda odwoujce si do zmiennych lokalnych ............................................. 388

A.6. Szablony

zmiennoargumentowe

............................................................................................... 391

A.6.1. Rozwijanie paczki parametrów ....................................................................................... 392

A.7. Automatyczne okrelanie typu zmiennej ................................................................................. 395
A.8. Zmienne lokalne wtków ........................................................................................................... 396
A.9. Podsumowanie

............................................................................................................................ 397

Dodatek B Krótkie zestawienie bibliotek przetwarzania wspóbienego

399

Dodatek C Framework przekazywania komunikatów i kompletny przykad

implementacji systemu bankomatu

401

Dodatek D Biblioteka wtków jzyka C++

419

D.1. Nagówek

<chrono>

................................................................................................................. 419

D.1.1.

Szablon klasy std::chrono::duration ............................................................................ 420

D.1.2.

Szablon klasy std::chrono::time_point ....................................................................... 429

D.1.3. Klasa

std::chrono::system_clock

................................................................................. 431

D.1.4. Klasa

std::chrono::steady_clock

.................................................................................. 433

D.1.5.

Definicja typu std::chrono::high_resolution_clock ................................................... 435

D.2. Nagówek

<condition_variable>

............................................................................................ 435

D.2.1. Klasa

std::condition_variable

...................................................................................... 436

D.2.2. Klasa

std::condition_variable_any

.............................................................................. 444

D.3. Nagówek

<atomic>

................................................................................................................. 452

D.3.1. Definicje

typów

std::atomic_xxx

................................................................................ 454

D.3.2. Makra

ATOMIC_xxx_LOCK_FREE

........................................................................ 454

D.3.3. Makro

ATOMIC_VAR_INIT

..................................................................................... 455

D.3.4. Typ

wyliczeniowy

std::memory_order

....................................................................... 455

D.3.5. Funkcja

std::atomic_thread_fence

............................................................................. 456

D.3.6. Funkcja

std::atomic_signal_fence

.............................................................................. 457

D.3.7. Klasa

std::atomic_flag

.................................................................................................. 457

D.3.8.

Szablon klasy std::atomic ............................................................................................ 460

D.3.9. Specjalizacje

szablonu

std::atomic

............................................................................. 471

D.3.10. Specjalizacje szablonu std::atomic<typ-cakowitoliczbowy> ................................. 472

D.4. Nagówek

<future>

.................................................................................................................. 489

D.4.1.

Szablon klasy std::future ............................................................................................. 490

D.4.2.

Szablon klasy std::shared_future ................................................................................ 495

D.4.3.

Szablon klasy std::packaged_task ............................................................................... 501

D.4.4.

Szablon klasy std::promise .......................................................................................... 507

D.4.5.

Szablon funkcji std::async ........................................................................................... 513

Poleć książkę

Kup książkę

background image

10

Spis treci

D.5. Nagówek

<mutex>

.................................................................................................................. 514

D.5.1. Klasa

std::mutex

.......................................................................................................... 515

D.5.2. Klasa

std::recursive_mutex

......................................................................................... 518

D.5.3. Klasa

std::timed_mutex

............................................................................................... 520

D.5.4. Klasa

std::recursive_timed_mutex

............................................................................. 524

D.5.5.

Szablon klasy std::lock_guard ..................................................................................... 529

D.5.6.

Szablon klasy std::unique_lock ................................................................................... 530

D.5.7.

Szablon funkcji std::lock ............................................................................................. 540

D.5.8.

Szablon funkcji std::try_lock ....................................................................................... 541

D.5.9. Klasa

std::once_flag

..................................................................................................... 541

D.5.10. Szablon funkcji std::call_once .................................................................................... 542

D.6. Nagówek

<ratio>

..................................................................................................................... 543

D.6.1.

Szablon klasy std::ratio ................................................................................................ 544

D.6.2. Alias

szablonu

std::ratio_add

...................................................................................... 544

D.6.3. Alias

szablonu

std::ratio_subtract

............................................................................... 545

D.6.4. Alias

szablonu

std::ratio_multiply

.............................................................................. 545

D.6.5. Alias

szablonu

std::ratio_divide

.................................................................................. 546

D.6.6.

Szablon klasy std::ratio_equal ..................................................................................... 547

D.6.7.

Szablon klasy std::ratio_not_equal ............................................................................. 547

D.6.8.

Szablon klasy std::ratio_less ........................................................................................ 547

D.6.9.

Szablon klasy std::ratio_greater .................................................................................. 548

D.6.10. Szablon klasy std::ratio_less_equal ............................................................................ 548
D.6.11. Szablon klasy std::ratio_greater_equal ....................................................................... 548

D.7. Nagówek

<thread>

................................................................................................................. 549

D.7.1. Klasa

std::thread

.......................................................................................................... 549

D.7.2.

Przestrze nazw std::this_thread ................................................................................ 558

Materiay dodatkowe

561

Skorowidz 563

Poleć książkę

Kup książkę

background image

Synchronizacja

wspóbienych operacji

W tym rozdziale zostan omówione
nastpujce zagadnienia:

Q

oczekiwanie na zdarzenie;

Q

oczekiwanie na jednorazowe zdarzenia za pomoc
przyszoci;

Q

oczekiwanie z limitem czasowym;

Q

upraszczanie kodu za pomoc technik
synchronizowania operacji.

W poprzednim rozdziale przeanalizowalimy rozmaite sposoby ochrony danych wspó-
dzielonych przez wiele wtków. Okazuje si jednak, e w pewnych przypadkach jest
potrzebna nie tyle ochrona danych, co synchronizacja dziaa podejmowanych przez
róne wtki. Wtek moe na przykad czeka z realizacj wasnej operacji na zako-
czenie pewnego zadania przez inny wtek. Ogólnie w wielu przypadkach wtek oczeku-
jcy na okrelone zdarzenie lub spenienie pewnego warunku jest najwygodniejszym
rozwizaniem. Mimo e analogiczne rozwizanie mona zaimplementowa w formie
mechanizmu okresowego sprawdzania flagi zakoczonego zadania lub innej wartoci
zapisanej we wspódzielonych danych, taki model byby daleki od ideau. Konieczno
synchronizacji operacji wykonywanych przez róne wtki jest do typowym scena-
riuszem, zatem biblioteka standardowa jzyka C++ oferuje mechanizmy uatwiajce
obsug tego modelu, w tym zmienne warunkowe i tzw. przyszoci.

W tym rozdziale omówi techniki oczekiwania na zdarzenia przy uyciu zmiennych

warunkowych oraz sposoby upraszczania synchronizacji operacji za pomoc przyszoci.

Poleć książkę

Kup książkę

background image

94

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

4.1.

Oczekiwanie na zdarzenie lub inny warunek

Przypumy, e podróujemy nocnym pocigiem. Jednym ze sposobów zagwaranto-
wania, e wysidziemy na waciwej stacji, jest unikanie snu i sprawdzanie wszystkich
stacji, na których zatrzymuje si nasz pocig. W ten sposób nie przegapimy naszej stacji,
jednak po dotarciu na miejsce bdziemy bardzo zmczeni. Alternatywnym rozwiza-
niem jest sprawdzenie rozkadu jazdy pod ktem godziny przyjazdu, ustawienie budzika
z pewnym wyprzedzeniem wzgldem tej godziny i pójcie spa. To rozwizanie jest
do bezpieczne — nie przegapimy naszej stacji, ale jeli pocig si spóni, wstaniemy
zbyt wczenie. Nie mona te wykluczy sytuacji, w której wyczerpi si baterie
w budziku — w takim przypadku moemy zaspa i przegapi swoj stacj. Idealnym
rozwizaniem byaby moliwo pójcia spa i skorzystania z pomocy czego (lub kogo),
co obudzioby nas bezporednio przed osigniciem stacji docelowej.

Jaki to ma zwizek z wtkami? Jeli jeden wtek czeka, a inny wtek zakoczy jakie

zadanie, ma do wyboru kilka moliwych rozwiza. Po pierwsze, moe stale spraw-
dza odpowiedni flag we wspódzielonych danych (chronionych przez muteks); flaga
zostanie ustawiona przez drugi wtek w momencie zakoczenia zadania. Takie rozwi-
zanie jest nieefektywne z dwóch powodów: wtek, który wielokrotnie sprawdza wspo-
mnian flag, zajmuje cenny czas procesora, a muteks zablokowany przez oczekujcy
wtek nie jest dostpny dla adnego innego wtku. Oba te czynniki dziaaj na nieko-
rzy oczekujcego wtku, poniewa ten wtek zajmuje zasoby potrzebne take do
dziaania wtku, na który czeka, co opónia wykonanie zadania i ustawienie odpowied-
niej flagi. Sytuacja przypomina unikanie snu przez ca podró pocigiem i prowadze-
nie rozmowy z maszynist — maszynista zajty rozmow musi prowadzi pocig nieco
wolniej, zatem póniej dotrzemy na swoj stacj. Podobnie wtek oczekujcy zajmuje
zasoby, które mogyby by uywane przez pozostae wtki w systemie, przez co czas
oczekiwania moe by duszy, ni to konieczne.

Druga opcja polega na przechodzeniu wtku oczekujcego w stan upienia na

krótkie momenty i okresowym wykonywaniu testów za pomoc funkcji

std::this_

´

thread::sleep_for()

(patrz punkt 4.3):

bool flag;
std::mutex m;

void wait_for_flag()
{
std::unique_lock<std::mutex> lk(m);
while(!flag)
{
lk.unlock();

Odblokowuje muteks

std::this_thread::sleep_for(std::chrono::milliseconds(100));

Czeka 100 ms

lk.lock();

Ponownie blokuje muteks

}
}

Wywoanie funkcji w ptli odblokowuje muteks przed przejciem w stan upienia
i ponownie blokuje ten muteks po wyjciu z tego stanu — dziki temu drugi wtek
ma szanse uzyskania dostpu do flagi i jej ustawienia.

Opisane rozwizanie jest o tyle dobre, e upiony wtek nie zajmuje bezproduk-

tywnie czasu procesora. Warto jednak pamita, e dobór waciwego czasu upienia

Poleć książkę

Kup książkę

background image

4.1.

Oczekiwanie na zdarzenie lub inny warunek

95

jest do trudny. Zbyt krótki czas przebywania w tym stanie spowoduje, e wtek bdzie
traci czas procesora na zbyt czste testy; zbyt dugi czas upienia bdzie oznacza, e
wtek bdzie przebywa w tym stanie nawet po zakoczeniu zadania, na które oczekuje,
zatem opónienie w dziaaniu wtku oczekujcego bdzie zbyt due. Takie „zaspanie”
wtku rzadko ma bezporedni wpyw na wynik operacji wykonywanych przez program,
ale ju w przypadku szybkiej gry moe powodowa pominicie niektórych klatek
animacji, a w przypadku aplikacji czasu rzeczywistego moe oznacza pominicie
przydziau czasu procesora.

Trzecim, najlepszym rozwizaniem jest uycie gotowych elementów biblioteki stan-

dardowej jzyka C++ umoliwiajcych oczekiwanie na okrelone zdarzenie. Najprost-
szym mechanizmem oczekiwania na zdarzenie generowane przez inny wtek (na przy-
kad zdarzenie polegajce na umieszczeniu dodatkowego zadania w potoku) jest tzw.
zmienna warunkowa. Zmienna warunkowa jest powizana z pewnym zdarzeniem lub
warunkiem oraz co najmniej jednym wtkiem, który czeka na spenienie tego warunku.
Wtek, który odkrywa, e warunek jest speniony, moe powiadomi pozostae wtki
oczekujce na t zmienn warunkow, aby je obudzi i umoliwi im dalsze przetwarzanie.

4.1.1.

Oczekiwanie na spenienie warunku
za pomoc zmiennych warunkowych

Biblioteka standardowa jzyka C++ udostpnia dwie implementacje mechanizmu
zmiennych warunkowych w formie klas

std::condition_variable

i

std::condition_

´

variable_any

. Obie klasy zostay zadeklarowane w pliku nagówkowym

<condition_

´

variable>

. W obu przypadkach zapewnienie waciwej synchronizacji wymaga uy-

cia muteksu — pierwsza klasa jest przystosowana tylko do obsugi muteksów typu

std::mutex

, natomiast druga klasa obsuguje wszystkie rodzaje muteksów speniajcych

pewien minimalny zbiór kryteriów (std przyrostek

_any

). Poniewa klasa

std::condition_

´

variable_any

jest bardziej uniwersalna, z jej stosowaniem wi si dodatkowe

koszty w wymiarze wielkoci, wydajnoci i zasobów systemu operacyjnego. Jeli wic
nie potrzebujemy dodatkowej elastycznoci, powinnimy stosowa klas

std::condition_

´

variable

.

Jak naleaoby uy klasy

std::condition_variable

do obsugi przykadu opisanego

na pocztku tego podrozdziau — jak sprawi, e wtek oczekujcy na wykonanie jakie-
go zadania bdzie upiony do momentu, w którym bd dostpne dane do przetwo-
rzenia? Na listingu 4.1 pokazano przykad kodu implementujcego odpowiednie roz-
wizanie przy uyciu zmiennej warunkowej.

Listing 4.1. Oczekiwanie na dane do przetworzenia za pomoc klasy
std::condition_variable

std::mutex mut;
std::queue<data_chunk> data_queue;
std::condition_variable data_cond;

void data_preparation_thread()
{
while(more_data_to_prepare())
{
data_chunk const data=prepare_data();

Poleć książkę

Kup książkę

background image

96

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

std::lock_guard<std::mutex> lk(mut);
data_queue.push(data);
data_cond.notify_one();
}
}

void data_processing_thread()
{
while(true)
{
std::unique_lock<std::mutex> lk(mut);
data_cond.wait(
lk,[]{return !data_queue.empty();});
data_chunk data=data_queue.front();
data_queue.pop();
lk.unlock();
process(data);
if(is_last_chunk(data))
break;
}
}

Na pocztku kodu zdefiniowano kolejk , która bdzie uywana do przekazywania
danych pomidzy dwoma wtkami. Kiedy dane s gotowe do przetworzenia, wtek,
który je przygotowa, blokuje muteks chronicy kolejk za pomoc klasy

std::lock_

´

guard

i umieszcza nowe dane w kolejce . Wtek wywouje nastpnie funkcj ska-

dow

notify_one()

dla obiektu klasy

std::condition_variable

, aby powiadomi ocze-

kujcy wtek (jeli taki istnieje) o dostpnoci nowych danych .

W tym modelu drug stron komunikacji jest wtek przetwarzajcy te dane. Wtek

przetwarzajcy najpierw blokuje muteks, jednak tym razem uyto do tego celu klasy

std::unique_lock

zamiast klasy

std::lock_guard

— przyczyny tej decyzji zostan

wyjanione za chwil. Wtek wywouje nastpnie funkcj

wait()

dla obiektu klasy

std::condition_variable

. Na wejciu tego wywoania wtek przekazuje obiekt blokady

i funkcj lambda reprezentujc warunek, który musi zosta speniony przed przyst-
pieniem do dalszego przetwarzania . Funkcje lambda to stosunkowo nowy element
(wprowadzony w standardzie C++11), który umoliwia pisanie funkcji anonimowych
w ramach innych wyrae. Wspomniane rozwizanie wprost idealnie nadaje si do
wskazywania predykatów w wywoaniach takich funkcji biblioteki standardowej jak

wait()

. W tym przypadku prosta funkcja lambda

[]{return !data_queue.empty();}

sprawdza, czy struktura reprezentowana przez zmienn

data_queue

nie jest pusta, tj.

czy kolejka zawiera jakie dane gotowe do przetworzenia. Funkcje lambda zostan szcze-
góowo omówione w czci A.5 dodatku A.

Implementacja funkcji

wait()

sprawdza warunek (wywoujc przekazan funkcj

lambda), po czym zwraca sterowanie, jeli ten warunek jest speniony (jeli funkcja
lambda zwrócia warto

true

). Jeli warunek nie jest speniony (jeli funkcja lambda

zwrócia warto

false

), funkcja

wait()

odblokowuje muteks i wprowadza biecy wtek

w stan blokady (oczekiwania). Kiedy zmienna warunkowa jest powiadamiana za pomoc
funkcji

notify_one()

wywoanej przez wtek przygotowujcy dane, wtek oczekujcy jest

budzony (odblokowywany), ponownie uzyskuje blokad muteksu i jeszcze raz sprawdza
warunek. Jeli warunek dalszego przetwarzania jest speniony, funkcja

wait()

zwraca

Poleć książkę

Kup książkę

background image

4.1.

Oczekiwanie na zdarzenie lub inny warunek

97

sterowanie z zachowaniem blokady muteksu. Jeli warunek nie jest speniony, wtek
odblokowuje muteks i ponownie przechodzi w stan oczekiwania. Wanie dlatego w przy-
kadzie naleao uy klasy

std::unique_lock

zamiast klasy

std::lock_guard

— wtek

oczekujcy musi odblokowa muteks na czas oczekiwania i zablokowa go ponownie
po otrzymaniu powiadomienia, a klasa

std::lock_guard

nie zapewnia takiej elastycz-

noci. Gdyby muteks pozosta zablokowany przez cay czas upienia tego wtku, wtek
przygotowujcy dane nie mógby zablokowa tego muteksu i doda elementu do kolejki,
zatem warunek budzenia wtku oczekujcego nigdy nie zostaby speniony.

Na listingu 4.1 uyem prostej funkcji lambda , która sprawdza, czy struktura

kolejki nie jest pusta. Okazuje si, e w tej roli równie dobrze mona by uy dowolnej
funkcji lub obiektu wywoywalnego. Jeli programista dysponuje ju funkcj spraw-
dzajc odpowiedni warunek (funkcja moe oczywicie by nieporównanie bardziej
zoona ni prosty test z powyszego przykadu), moe przekaza t funkcj bezpo-
rednio na wejciu funkcji

wait()

, bez koniecznoci opakowywania jej w ramach wyra-

enia lambda. Po wywoaniu funkcji

wait()

zmienna warunkowa moe sprawdzi

wskazany warunek na wiele rónych sposobów, jednak podczas tego testu muteks
zawsze jest zablokowany, a funkcja

wait()

natychmiast zwraca sterowanie, pod warun-

kiem e przekazana funkcja sprawdzajca ten warunek zwrócia warto

true

. Jeli

wtek oczekujcy ponownie uzyskuje muteks i sprawdza warunek, mimo e nie otrzy-
ma powiadomienia od innego wtku i jego dziaania nie s bezporedni odpowiedzi
na takie powiadomienie, mamy do czynienia z tzw. pozornym budzeniem (ang. spu-
rious wake
). Poniewa optymalna liczba i czstotliwo takich pozornych budze s
z definicji trudne do oszacowania, funkcja sprawdzajca prawdziwo warunku nie
powinna powodowa adnych skutków ubocznych. Gdyby ta funkcja powodowaa skutki
uboczne, programista musiaby przygotowa swój kod na wielokrotne wystpowanie
tych skutków przed spenieniem warunku.

Moliwo odblokowania obiektu klasy

std::unique_lock

nie jest uywana tylko

dla wywoania funkcji

wait()

— analogiczne rozwizanie zastosowalimy po uzyskaniu

danych do przetworzenia, ale przed przystpieniem do waciwego przetwarzania .
Przetwarzanie danych moe by czasochonn operacj, a jak wiemy z rozdziau 3.,
utrzymywanie blokady muteksu duej, ni to konieczne, nie jest dobrym rozwizaniem.

Stosowanie struktury kolejki do przekazywania danych pomidzy wtkami (jak na

listingu 4.1) jest do typowym rozwizaniem. Jeli projekt aplikacji jest waciwy,
synchronizacja powinna dotyczy samej kolejki, co znacznie ogranicza liczb poten-
cjalnych problemów i problematycznych sytuacji wycigu. Spróbujmy wic wyodrb-
ni z listingu 4.1 uniwersaln kolejk gwarantujc bezpieczne przetwarzanie wielo-
wtkowe.

4.1.2.

Budowa kolejki gwarantujcej bezpieczne przetwarzanie
wielowtkowe przy uyciu zmiennych warunkowych

Przed przystpieniem do projektowania uniwersalnej kolejki warto powici kilka
minut analizie operacji, które trzeba bdzie zaimplementowa dla tej struktury danych
(podobnie jak w przypadku stosu gwarantujcego bezpieczestwo przetwarzania wielo-
wtkowego z punktu 3.2.3). Przyjrzyjmy si kontenerowi

std::queue<>

dostpnemu

w bibliotece standardowej jzyka C++ (patrz listing 4.2), który bdzie stanowi punkt
wyjcia dla naszej implementacji.

Poleć książkę

Kup książkę

background image

98

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

Listing 4.2. Interfejs kontenera std::queue

template <class T, class Container = std::deque<T> >
class queue {
public:
explicit queue(const Container&);
explicit queue(Container&& = Container());

template <class Alloc> explicit queue(const Alloc&);
template <class Alloc> queue(const Container&, const Alloc&);
template <class Alloc> queue(Container&&, const Alloc&);
template <class Alloc> queue(queue&&, const Alloc&);

void swap(queue& q);

bool empty() const;
size_type size() const;

T& front();
const T& front() const;
T& back();
const T& back() const;

void push(const T& x);
void push(T&& x);
void pop();
template <class... Args> void emplace(Args&&... args);
};

Jeli pominiemy operacje konstruowania, przypisywania i wymiany, pozostan nam
zaledwie trzy grupy operacji: operacje zwracajce stan caej kolejki (

empty()

i

size()

),

operacje zwracajce pojedyncze elementy kolejki (

front()

i

back()

) oraz operacje

modyfikujce kolejk (

push()

,

pop()

i

emplace()

). Mamy wic do czynienia z sytuacj

analogiczn do tej opisanej w punkcie 3.2.3 (gdzie omawialimy struktur stosu), zatem
opisany interfejs jest naraony na te same problemy zwizane z sytuacjami wycigów.
W tym przypadku naley poczy funkcje

front()

i

pop()

w jedno wywoanie, tak jak

wczeniej poczylimy funkcje

top()

i

pop()

dla struktury stosu. Warto jeszcze zwróci

uwag na pewien nowy element w kodzie z listingu 4.1 — podczas uywania kolejki
do przekazywania danych pomidzy wtkami wtek docelowy zwykle musi czeka na
te dane. Warto wic zaimplementowa funkcj

pop()

w dwóch wersjach — pierwsza

funkcja,

try_pop()

, próbuje pobra warto z kolejki, ale zawsze zwraca sterowanie

bezporednio po wywoaniu, nawet jeli kolejka nie zawieraa adnej wartoci (wtedy
funkcja sygnalizuje bd); druga funkcja,

wait_and_pop()

, czeka na pojawienie si

w kolejce wartoci do pobrania. Po wprowadzeniu zmian zgodnie ze schematem opi-
sanym ju przy okazji przykadu stosu interfejs struktury kolejki powinien wyglda
tak jak na listingu 4.3.

Listing 4.3. Interfejs struktury danych threadsafe_queue

#include <memory>

Dla typu std::shared_ptr

template<typename T>
class threadsafe_queue

Poleć książkę

Kup książkę

background image

4.1.

Oczekiwanie na zdarzenie lub inny warunek

99

{
public:
threadsafe_queue();
threadsafe_queue(const threadsafe_queue&);
threadsafe_queue& operator=(
const threadsafe_queue&) = delete;

Dla uproszczenia wyklucza moliwo

przypisywania

void push(T new_value);

bool try_pop(T& value);
std::shared_ptr<T> try_pop();

void wait_and_pop(T& value);
std::shared_ptr<T> wait_and_pop();

bool empty() const;
};

Podobnie jak w przypadku stosu, na listingu 4.3 usunito konstruktory i operator
przypisania, aby uproci analizowany kod. Tak jak wczeniej, take tym razem funk-
cje

try_pop()

i

wait_for_pop()

wystpuj w dwóch wersjach. Pierwsza przeciona

wersja funkcji

try_pop()

zapisuje pobran warto we wskazywanej zmiennej, tak

aby mona byo uy tej wartoci w roli statusu; funkcja zwraca warto

true

, jeli

uzyskaa jak warto — w przeciwnym razie funkcja zwraca warto

false

(patrz

cz A.2 dodatku A). Druga przeciona wersja nie moe dziaa w ten sam spo-
sób, poniewa natychmiast zwraca uzyskan warto. Jeli jednak funkcja nie uzyskaa
adnej wartoci, moe zwróci wskanik równy

NULL

.

Jaki to ma zwizek z listingiem 4.1? Okazuje si, e moemy wyodrbni kod funkcji

push()

i

wait_and_pop()

z tamtego listingu i na tej podstawie przygotowa now imple-

mentacj (patrz listing 4.4).

Listing 4.4. Funkcje push() i wait_and_pop() wyodrbnione z listingu 4.1

#include <queue>
#include <mutex>
#include <condition_variable>

template<typename T>
class threadsafe_queue
{
private:
std::mutex mut;
std::queue<T> data_queue;
std::condition_variable data_cond;
public:
void push(T new_value)
{
std::lock_guard<std::mutex> lk(mut);
data_queue.push(new_value);
data_cond.notify_one();
}

void wait_and_pop(T& value)
{

Poleć książkę

Kup książkę

background image

100

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

std::unique_lock<std::mutex> lk(mut);
data_cond.wait(lk,[this]{return !data_queue.empty();});
value=data_queue.front();
data_queue.pop();
}
};

threadsafe_queue<data_chunk> data_queue;

void data_preparation_thread()
{
while(more_data_to_prepare())
{
data_chunk const data=prepare_data();
data_queue.push(data);
}
}

void data_processing_thread()
{
while(true)
{
data_chunk data;
data_queue.wait_and_pop(data);
process(data);
if(is_last_chunk(data))
break;
}
}

Muteks i zmienna warunkowa s teraz elementami skadowymi obiektu klasy

threadsafe_

´

queue

, zatem nie jest potrzebne stosowanie odrbnych zmiennych , a wywoanie

funkcji

push()

nie wymaga zewntrznych mechanizmów synchronizacji . Jak wida,

take funkcja

wait_and_pop()

uwzgldnia stan zmiennej warunkowej .

Napisanie drugiej wersji przecionej funkcji

wait_and_pop()

nie stanowi adnego

problemu; take pozostae funkcje mona niemal skopiowa z przykadu stosu pokaza-
nego na listingu 3.5. Ostateczn wersj implementacji kolejki pokazano na listingu 4.5.

Listing 4.5. Kompletna definicja klasy kolejki gwarantujcej bezpieczestwo
przetwarzania wielowtkowego (dziki uyciu zmiennych warunkowych)

#include <queue>
#include <memory>
#include <mutex>
#include <condition_variable>

template<typename T>
class threadsafe_queue
{
private:
mutable std::mutex mut;

Muteks musi by modyfikowalny

std::queue<T> data_queue;
std::condition_variable data_cond;
public:
threadsafe_queue()
{}

Poleć książkę

Kup książkę

background image

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ę

background image

102

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

Mimo e

empty()

jest sta funkcj skadow i mimo e parametr

other

konstruktora

kopiujcego jest sta referencj, pozostae wtki mog dysponowa niestaymi refe-
rencjami do tego obiektu i wywoywa funkcje skadowe zmieniajce jego stan, zatem
blokowanie muteksu wci jest konieczne. Poniewa blokowanie muteksu jest operacj
zmieniajc stan obiektu, obiekt muteksu naley oznaczy jako modyfikowalny (ang.
mutable) , tak aby mona byo blokowa ten muteks w ciele funkcji

empty()

i kon-

struktora kopiujcego.

Zmienne warunkowe s przydatne take w sytuacji, w której wiele wtków czeka na

to samo zdarzenie. Jeli celem stosowania wtków jest dzielenie obcienia i jeli tylko
jeden wtek powinien reagowa na powiadomienie, mona zastosowa dokadnie tak
sam struktur jak ta z listingu 4.1 — wystarczy uruchomi wiele instancji wtku prze-
twarzajcego dane. Po przygotowaniu nowych danych wywoanie funkcji

notify_one()

spowoduje, e jeden z wtków aktualnie wykonujcych funkcj

wait()

sprawdzi waru-

nek. Poniewa do struktury

data_queue

wanie dodano nowe dane, funkcja

wait()

zwróci sterowanie. Nie wiadomo, do którego wtku trafi powiadomienie ani nawet czy
istnieje wtek oczekujcy na to powiadomienie (nie mona przecie wykluczy, e
wszystkie wtki w danej chwili przetwarzaj swoje dane).

Warto te pamita o moliwoci oczekiwania na to samo zdarzenie przez wiele

wtków, z których kady musi zareagowa na powiadomienie. Opisany scenariusz moe
mie zwizek z inicjalizacj wspódzielonych danych, gdzie wszystkie wtki przetwa-
rzajce operuj na tych samych danych i musz czeka albo na ich inicjalizacj (w takim
przypadku istniej lepsze mechanizmy — patrz punkt 3.3.1 w rozdziale 3.), albo na ich
aktualizacj (na przykad w ramach okresowej, wielokrotnej inicjalizacji). W opisanych
przypadkach wtek przygotowujcy dane moe wywoa funkcj skadow

notify_all()

dla zmiennej warunkowej (zamiast funkcji

notify_one()

). Jak nietrudno si domyli,

funkcja powoduje, e wszystkie wtki aktualnie wykonujce funkcj

wait()

sprawdz

warunek, na który czekaj.

Jeli wtek wywoujcy w zaoeniu ma oczekiwa na dane zdarzenie tylko raz, czyli

jeli po spenieniu warunku wtek nie bdzie ponownie czeka na t sam zmienn
warunkow, by moe warto zastosowa inny mechanizm synchronizacji ni zmienna
warunkowa. Zmienne warunkowe s szczególnie nieefektywne w sytuacji, gdy warun-
kiem, na który oczekuj wtki, jest dostpno okrelonego elementu danych. W takim
przypadku lepszym rozwizaniem jest uycie mechanizmu przyszoci.

4.2.

Oczekiwanie na jednorazowe zdarzenia
za pomoc przyszoci

Przypumy, e planujemy podró samolotem. Po przyjedzie na lotnisko i przejciu
rozmaitych procedur wci musimy czeka na komunikat dotyczcy gotowoci naszego
samolotu na przyjcie pasaerów (zdarza si, e pasaerowie musz czeka wiele godzin).
Moemy oczywicie znale sposób, aby ten czas min nieco szybciej (moemy na
przykad czyta ksik, przeglda strony internetowe lub uda si na posiek do
drogiej lotniskowej kawiarni), jednak niezalenie od sposobu spdzania czasu czekamy
na jedno — sygna wzywajcy do udania si na pokad samolotu. Co wicej, interesu-
jcy nas lot odbdzie si tylko raz, zatem przy okazji nastpnego wyjazdu na wakacje
bdziemy czekali na inny lot.

Poleć książkę

Kup książkę

background image

4.2.

Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci

103

Twórcy biblioteki standardowej jzyka C++ rozwizali problem jednorazowych

zdarze za pomoc mechanizmu nazwanego przyszoci (ang. future). Wtek, który
musi czeka na okrelone jednorazowe zdarzenie, powinien uzyska przyszo repre-
zentujc to zdarzenie. Wtek oczekujcy na t przyszo moe nastpnie okresowo
sprawdza, czy odpowiednie zdarzenie nie nastpio (tak jak pasaerowie co jaki czas
zerkaj na tablic odlotów), i jednoczenie pomidzy tymi testami wykonywa inne
zadanie (spoywa drogi deser w lotniskowej kawiarni). Alternatywnym rozwizaniem
jest wykonywanie innego zadania do momentu, w którym dalsze dziaanie nie jest mo-
liwe bez okrelonego zdarzenia, i przejcie w stan gotowoci na przyszo. Przyszo
moe, ale nie musi by powizana z danymi (tak jak tablica odlotów moe wskazywa
rkawy prowadzce do waciwych samolotów). Po wystpieniu zdarzenia (po osigni-
ciu gotowoci przez przyszo) nie jest moliwe wyzerowanie tej przyszoci.

W bibliotece standardowej jzyka C++ istniej dwa rodzaje przyszoci zaimple-

mentowane w formie dwóch szablonów klas zadeklarowanych w nagówku biblioteki

<future>

: przyszoci unikatowe (

std::future<>

) oraz przyszoci wspódzielone (

std::

´

shared_future<>

). Wymienione klasy opracowano na bazie typów

std::unique_ptr

i

std::shared_ptr

. Obiekt typu

std::future

jest jedyn instancj odwoujc si do

powizanego zdarzenia, natomiast do jednego zdarzenia moe si odwoywa wiele
instancji typu

std::shared_future

. W drugim przypadku wszystkie instancje s gotowe

jednoczenie i wszystkie mog uzyskiwa dostp do dowolnych danych powizanych
z danym zdarzeniem. Wanie z myl o powizanych danych zaprojektowano te szablony
klas — tak jak w przypadku szablonów

std::unique_ptr

i

std::shared_ptr

, parametry

szablonów

std::future<>

i

std::shared_future<>

reprezentuj wanie typy powizanych

danych. W razie braku powizanych danych naley stosowa nastpujce specjalizacje
tych szablonów:

std:future<void>

i

std::shared_future<void>.

Mimo e przyszoci

su do komunikacji pomidzy wtkami, same obiekty przyszoci nie oferuj mecha-
nizmów synchronizowanego dostpu. Jeli wiele wtków potrzebuje dostpu do jednego
obiektu przyszoci, naley chroni ten dostp za pomoc muteksu lub innego mecha-
nizmu synchronizacji (patrz rozdzia 3.). Jak napisz w punkcie 4.2.5 w dalszej czci
tego podrozdziau, wiele wtków moe uzyskiwa dostp do wasnej kopii obiektu typu

std::shared_future<>

bez koniecznoci dodatkowej synchronizacji, nawet jeli wszystkie

te kopie odwouj si do tego samego asynchronicznego wyniku.

Najprostszym przykadem jednorazowego zdarzenia jest wynik oblicze wykonywa-

nych w tle. Ju w rozdziale 2. napisaem, e klasa

std::thread

nie udostpnia prostych

mechanizmów zwracania wartoci wynikowych dla tego rodzaju zada, i zapowiedzia-
em wprowadzenie odpowiednich rozwiza w rozdziale 4. przy okazji omawiania przy-
szoci — czas zapozna si z tymi rozwizaniami.

4.2.1.

Zwracanie wartoci przez zadania wykonywane w tle

Przypumy, e nasza aplikacja wykonuje czasochonne obliczenia, które ostatecznie
pozwol uzyska oczekiwany wynik. Zaómy, e warto wynikowa nie jest potrzebna
na tym etapie dziaania programu. By moe udao nam si wymyli sposób poszu-
kiwania odpowiedzi na pytanie o ycie, wszechwiat i ca reszt stawiane w ksikach

Poleć książkę

Kup książkę

background image

104

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

Douglasa Adamsa

1

. Moglibymy oczywicie uruchomi nowy wtek, który wykona

niezbdne obliczenia, jednak takie rozwizanie wizaoby si z koniecznoci przeka-
zania wyników z powrotem do wtku gównego, poniewa klasa

std::thread

nie oferuje

alternatywnego mechanizmu zwracania wartoci wynikowych. W takim przypadku
sporym uatwieniem jest uycie szablonu funkcji

std::async

(zadeklarowanego w pliku

nagówkowym

<future>

).

Asynchroniczne zadanie, którego wynik nie jest potrzebny na biecym etapie dzia-

ania programu, mona rozpocz za pomoc funkcji

std::async

. Zamiast zwracania

obiektu klasy

std::thread

, który umoliwi oczekiwanie na zakoczenie danego wtku,

funkcja

std::async

zwraca obiekt klasy

std::future

, który w przyszoci bdzie zawiera

warto wynikow. W miejscu, w którym aplikacja bdzie potrzebowaa tej wartoci,
naley wywoa funkcj

get()

dla obiektu przyszoci — wywoanie tej funkcji zablo-

kuje wykonywanie biecego wtku do momentu osignicia gotowoci przez przy-
szo, po czym zwróci uzyskan warto. Prosty przykad uycia tych elementów poka-
zano na listingu 4.6.

Listing 4.6. Przykad uycia szablonu klasy std::future do uzyskania wartoci
wynikowej asynchronicznego zadania

#include <future>
#include <iostream>

int find_the_answer_to_ltuae();
void do_other_stuff();
int main()
{
std::future<int> the_answer=std::async(find_the_answer_to_ltuae);
do_other_stuff();
std::cout<<"Odpowied brzmi "<<the_answer.get()<<std::endl;
}

Szablon funkcji

std::async

umoliwia przekazywanie dodatkowych argumentów na

wejciu wywoywanej funkcji — wystarczy doda te argumenty do wywoania (podob-
nie jak w przypadku klasy

std::thread

). Jeli pierwszy argument reprezentuje wskanik

do funkcji skadowej, drugi argument zawiera obiekt, dla którego ma zosta wywoana
ta funkcja skadowa (bezporednio, za porednictwem wskanika lub poprzez opako-
wanie

std::ref

), a pozostae argumenty s przekazywane na wejciu tej funkcji skado-

wej. W przeciwnym razie drugi i kolejne argumenty s przekazywane na wejciu funkcji
skadowej lub wywoywalnego obiektu wskazanego za porednictwem pierwszego argu-
mentu. Tak jak w przypadku klasy

std::thread

, jeli argumenty maj posta r-wartoci,

zostan utworzone kopie poprzez przeniesienie oryginalnych wartoci. Dziki temu
moemy stosowa typy oferujce tylko moliwo przenoszenia zarówno w roli obiektów
funkcji, jak i w roli argumentów. Przykad takiego rozwizania pokazano na listingu 4.7.

1

W ksice Autostopem przez Galaktyk zbudowano komputer Deep Thought, który mia odpowiedzie
na pytanie o ycie, wszechwiat i ca reszt. Odpowiedzi na to pytanie bya liczba 42.

Poleć książkę

Kup książkę

background image

4.2.

Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci

105

Listing 4.7. Przekazywanie argumentów na wejciu funkcji wtku std::async

#include <string>
#include <future>

struct X
{
void foo(int,std::string const&);
std::string bar(std::string const&);
};
X x;
auto f1=std::async(&X::foo,&x,42,"witaj");
auto f2=std::async(&X::bar,x,"egnaj");
struct Y
{
double operator()(double);
};
Y y;
auto f3=std::async(Y(),3.141);
auto f4=std::async(std::ref(y),2.718);

Wywouje y(2.718)

X baz(X&);
std::async(baz,std::ref(x));

Wywouje baz(x)

class move_only
{
public:
move_only();
move_only(move_only&&)
move_only(move_only const&) = delete;
move_only& operator=(move_only&&);
move_only& operator=(move_only const&) = delete;

void operator()();
};
auto f5=std::async(move_only());

Domylnie to od stosowanej implementacji zaley, czy funkcja

std::async

uruchamia

nowy wtek, czy wskazane zadanie bdzie wykonywane w sposób synchroniczny (wów-
czas biecy wtek bdzie czeka na osignicie gotowoci przez przyszo). W wikszo-
ci przypadków standardowe rozwizanie jest wystarczajce, jednak programista moe
wybra waciwy tryb za pomoc dodatkowego parametru funkcji

std::async

przeka-

zywanego przed funkcj do wywoania. Wspomniany parametr typu

std::launch

moe

mie albo warto

std::launch::deferred

(wówczas wywoanie funkcji jest odkadane

do momentu wywoania funkcji

wait()

lub

get()

dla danej przyszoci), albo warto

std::

´

launch::async

(wówczas funkcja musi by wykonywana w odrbnym wtku), albo

warto

std::launch::deferred | std::launch::async

(wówczas decyzja naley do

implementacji). Ostatnia opcja jest stosowana w roli wartoci domylnej. Jeli wywo-
anie funkcji jest odkadane na przyszo, moe nigdy nie nastpi. Na przykad:

auto f6=std::async(std::launch::async,Y(),1.2);

Wykonywane w nowym wtku

auto f7=std::async(std::launch::deferred,baz,std::ref(x));
auto f8=std::async(
std::launch::deferred | std::launch::async,
baz,std::ref(x));
auto f9=std::async(baz,std::ref(x));
f7.wait();

Wywoanie odroczonej funkcji

Wywouje p->foo(42,"witaj"),
gdzie p jest reprezentowane przez &x

Wywouje tmpx.bar("egnaj"),
gdzie tmpx jest kopi x

Wywouje tmpy(3.141), gdzie tmpy
jest tworzone za pomoc konstruktora
przenoszcego Y()

Wywouje tmp(), gdzie tmp jest konstruowany
na podstawie wywoania std::move(move_only())

Wykonywane w ramach
funkcji wait() lub get()

Wybór
implementacji

Poleć książkę

Kup książkę

background image

106

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

Jak si przekonasz w dalszej czci tego rozdziau (i ponownie w rozdziale 8.), funkcja

std::async

uatwia dzielenie algorytmów na wspóbienie wykonywane zadania. Oka-

zuje si jednak, e nie jest to jedyny sposób kojarzenia obiektu typu

std::future

z zada-

niem — alternatywnym rozwizaniem jest opakowanie zadania w ramach instancji
szablonu klasy

std::packaged_task<>

lub napisanie kodu bezporednio ustawiajcego

wartoci za pomoc szablonu klasy

std::promise<>

. Szablon klasy

std::packaged_task

jest abstrakcj wyszego poziomu (w porównaniu z szablonem

std::promise

), zatem

wanie ten szablon omówimy jako pierwszy.

4.2.2.

Wizanie zadania z przyszoci

Szablon klasy

std::packaged_task<>

wie przyszo z funkcj lub wywoywalnym

obiektem. W momencie wywoania obiektu typu

std::packaged_task<>

wywoana zostaje

powizana funkcja lub wywoywalny obiekt, a sama przyszo przechodzi w stan goto-
woci
(warto wynikowa zostaje umieszczona w powizanych danych). Opisan struktur
mona wykorzysta w roli elementu skadowego podczas budowy puli wtków (patrz
rozdzia 9.) lub dowolnego innego schematu zarzdzania zadaniami polegajcego na
przykad na wykonywaniu kadego zadania w osobnym wtku lub sekwencyjnym wyko-
nywaniu zada w jednym wtku dziaajcym w tle. Jeli jedn wiksz operacj mona
podzieli na wiele autonomicznych podzada, kade z tych podzada mona opakowa
w ramach obiektu klasy

std::packaged_task<>

, aby nastpnie przekaza ten obiekt do

mechanizmu szeregowania zada lub do puli wtków. W ten sposób mona skutecznie
ukry szczegóy zwizane z poszczególnymi zadaniami — mechanizm szeregowania zada
operuje na obiektach klasy

std::packaged_task<>

, nie na poszczególnych funkcjach.

Parametr szablonu klasy

std::packaged_task<>

reprezentuje sygnatur funkcji —

na przykad dla funkcji, która nie otrzymuje adnych parametrów i nie zwraca wartoci,
naleaoby uy sygnatury

void()

, natomiast dla funkcji otrzymujcej niesta refe-

rencj do wartoci typu

std::string

i wskanik do wartoci typu

double

oraz zwraca-

jcej warto typu

int

naleaoby uy sygnatury

int(std::string&,double*)

. Podczas

konstruowania obiektu klasy

std::packaged_task

naley przekaza funkcj (lub wywo-

ywalny obiekt) otrzymujc na wejciu wskazane parametry i zwracajc typ, który
mona przekonwertowa na wskazany typ danych. Dokadne dopasowanie typów nie
jest wymagane — istnieje moliwo skonstruowania obiektu klasy

std::packaged_task

´

<double(double)>

na podstawie funkcji otrzymujcej na wejciu warto typu

int

i zwracajcej warto typu

float

, poniewa wymienione typy mog by automatycznie

konwertowane.

Typ wartoci zwracanych przez wskazan funkcj identyfikuje typ zwracany przez

funkcj skadow

get_future()

konstruowanego obiektu klasy

std::future<>

, nato-

miast lista argumentów zdefiniowana w ramach sygnatury funkcji jest uywana do
wyznaczania sygnatury operatora wywoania funkcji zadania reprezentowanego przez
ten obiekt. Przykad czciowej definicji klasy

std::packaged_task<std::string(std::

´

vector<char>*,int)>

pokazano na listingu 4.8.

Instancja klasy

std::packaged_task

jest obiektem wywoywalnym i jako taka moe

by opakowana w ramach obiektu klasy

std::function

, przekazana do obiektu kla-

sy

std::thread

w roli funkcji wtku, przekazana do dowolnej innej funkcji oczekujcej

wywoywalnego obiektu, a nawet bezporednio wywoana. W momencie wywoania

Poleć książkę

Kup książkę

background image

4.2.

Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci

107

Listing 4.8. Czciowa definicja specjalizacji szablonu klasy
std::packaged_task<>

template<>
class packaged_task<std::string(std::vector<char>*,int)>
{
public:
template<typename Callable>
explicit packaged_task(Callable&& f);
std::future<std::string> get_future();
void operator()(std::vector<char>*,int);
};

obiektu klasy

std::packaged_task

jako obiektu funkcji argumenty przekazane na wejciu

operatora wywoania s przekazywane do opakowanej funkcji, a zwracana warto jest
zapisywana jako asynchroniczny wynik w obiekcie typu

std::future

(obiekt mona

nastpnie uzyska za pomoc funkcji

get_future()

). Oznacza to, e moemy opakowa

zadanie w obiekcie klasy

std::packaged_task

i uzyska przyszo przed przekazaniem

tego obiektu do miejsca, gdzie zostanie wywoany. W momencie, w którym program
bdzie potrzebowa wyniku, wystarczy poczeka na osignicie gotowoci przez t przy-
szo. Praktyczny przykad takiego rozwizania opisano w nastpnym podpunkcie.

P

RZEKAZYWANIE ZADA POMIDZY WTKAMI

Wiele frameworków graficznego interfejsu uytkownika wymaga, aby aktualizacje tego
interfejsu byy wykonywane przez okrelone wtki. Oznacza to, e jeli jaki inny wtek
musi zaktualizowa graficzny interfejs uytkownika, powinien wysa komunikat do
waciwego wtku, aby wyznaczony wtek wykona to zadanie w jego imieniu. Szablon
klasy

std::packaged_task

oferuje odpowiednie rozwizania bez koniecznoci stosowania

niestandardowych komunikatów dla kadego zadania zwizanego z dziaaniem graficz-
nego interfejsu uytkownika (patrz listing 4.9).

Listing 4.9. Uruchamianie kodu w wtku graficznego interfejsu uytkownika
za pomoc szablonu klasy std::packaged_task

#include <deque>
#include <mutex>
#include <future>
#include <thread>
#include <utility>

std::mutex m;
std::deque<std::packaged_task<void()> > tasks;

bool gui_shutdown_message_received();
void get_and_process_gui_message();

void gui_thread()
{
while(!gui_shutdown_message_received())
{
get_and_process_gui_message();
std::packaged_task<void()> task;
{

Poleć książkę

Kup książkę

background image

108

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

std::lock_guard<std::mutex> lk(m);
if(tasks.empty())
continue;
task=std::move(tasks.front());
tasks.pop_front();
}
task();
}
}

std::thread gui_bg_thread(gui_thread);

template<typename Func>
std::future<void> post_task_for_gui_thread(Func f)
{
std::packaged_task<void()> task(f);
std::future<void> res=task.get_future();
std::lock_guard<std::mutex> lk(m);
tasks.push_back(std::move(task));
return res;
}

Powyszy kod jest bardzo prosty: wtek graficznego interfejsu uytkownika dziaa
w ptli do momentu otrzymania komunikatu sygnalizujcego konieczno zamknicia
tego interfejsu . W ciele tej ptli wtek sprawdza komunikaty dotyczce graficznego
interfejsu uytkownika (na przykad tego, e uytkownik klikn jaki element inter-
fejsu) oraz ewentualne zadania w kolejce zada. Jeli kolejka nie zawiera adnych zada

, wtek przechodzi do nastpnej iteracji ptli; w przeciwnym razie wtek odczytuje

zadanie z kolejki , zwalnia blokad tej kolejki, po czym uruchamia to zadanie .
W momencie zakoczenia zadania powizana z nim przyszo przechodzi w stan
gotowoci.

Umieszczenie zadania w kolejce jest równie proste: nowe, opakowane zadanie jest

tworzone na podstawie wskazanej funkcji , przyszo jest uzyskiwana z obiektu zada-
nia za pomoc funkcji skadowej

get_future()

i wreszcie zadanie jest umieszczane

na licie przed zwróceniem przyszoci do kodu wywoujcego . Kod, który wysya
komunikat do wtku interfejsu uytkownika, moe albo poczeka na przyszo (jeli
wykonanie zadania jest niezbdne do dalszego dziaania), albo porzuci t przyszo
(jeli nie potrzebuje wyniku przetwarzania).

W tym przykadzie uylimy do reprezentacji zada klasy

std::packaged_task

´

<void()>

. Klasa opakowuje funkcj (lub inny obiekt wywoywalny), która nie otrzy-

muje adnych parametrów i zwraca

void

(jeli wskazana funkcja zwraca inn warto,

wynik zostanie porzucony). W tym przypadku zastosowano najprostsze moliwe zada-
nie, jednak (jak ju wiemy) szablon klasy

std::packaged_task

moe by równie dobrze

stosowany w implementacjach bardziej zoonych rozwiza — wystarczy w roli para-
metru szablonu uy innej sygnatury funkcji, zmieni typ zwracanych wartoci (a wic
take typ danych przechowywanych w ramach stanu przyszoci) i zmieni typy argu-
mentów operatora wywoania funkcji. Przedstawiony przykad mona by atwo rozsze-
rzy o moliwo przekazywania argumentów do zada, które maj by wykonywane
przez wtek graficznego interfejsu uytkownika, i zwracania wartoci w ramach obiektu
typu

std::future

(zamiast samego sygnau o zakoczeniu zadania).

Poleć książkę

Kup książkę

background image

4.2.

Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci

109

Co naley zrobi z zadaniami, których nie mona wyrazi w formie prostych wywo-

a funkcji, i zadaniami, których wyniki mog pochodzi z wielu rónych miejsc? Obsuga
takich przypadków wymaga jeszcze innego sposobu tworzenia przyszoci — bezpo-
redniego ustawiania wartoci za pomoc szablonu

std::promise

.

4.2.3.

Obietnice (szablon std::promise)

Programici pracujcy nad aplikacjami, które musz obsugiwa wiele pocze sie-
ciowych, czsto ulegaj pokusie obsugi kadego poczenia w osobnym wtku, ponie-
wa takie rozwizanie uatwia zrozumienie i zaimplementowanie mechanizmów komu-
nikacji sieciowej. Takie rozwizanie sprawdza si w przypadku niewielkiej liczby
pocze (a wic take niewielkiej liczby wtków). Okazuje si jednak, e w razie
wzrostu liczby pocze opisany model staje si nieefektywny, poniewa dua liczba
wtków zajmuje zbyt wiele zasobów systemu operacyjnego, a czste przeczanie
kontekstu (jeli liczba wtków przekracza wspóbieno sprztow) ma negatywny
wpyw na wydajno aplikacji. W skrajnych przypadkach aplikacja uruchamiajca duo
nowych wtków moe wyczerpa zasoby systemu operacyjnego przed osigniciem limitu
pocze sieciowych. Wanie dlatego nawet w aplikacjach obsugujcych bardzo duo
pocze sieciowych stosuje si stosunkowo niewiele wtków (czasem tylko jeden
wtek) odpowiedzialnych za obsug tych pocze, zatem kady wtek musi obsugi-
wa wiele pocze jednoczenie.

Przeanalizujmy przykad wtku obsugujcego poczenia. Pakiety danych przy-

chodz za porednictwem rónych pocze w przypadkowej kolejnoci; podobnie
pakiety danych przeznaczone do wysania s kolejkowane w przypadkowej kolejnoci.
W wielu przypadkach pozostae elementy aplikacji bd oczekiway albo na wysanie
danych, albo na otrzymanie nowego pakietu danych za porednictwem okrelonego po-
czenia sieciowego.

Szablon klasy

std::promise<T>

umoliwia ustawienie wartoci (typu

T

), któr w przy-

szoci bdzie mona odczyta za porednictwem powizanego obiektu klasy

std::

´

future<T>

. Para klas

std::promise

i

std::future

to jeden z mechanizmów umoli-

wiajcych implementacj interesujcego nas rozwizania — wtek oczekujcy moe
wstrzyma dziaanie w oczekiwaniu na przyszo, natomiast wtek udostpniajcy
dane moe uy obiektu obietnicy do ustawienia powizanej wartoci, tak aby odpo-
wiednia przyszo przesza w stan gotowoci.

Obiekt klasy

std::future

powizany z danym obiektem klasy

std::promise

mona

uzyska za pomoc funkcji skadowej

get_future()

, a wic tak samo jak w przypadku

obiektu klasy

std::packaged_task

. W momencie ustawienia wartoci obiektu obietnicy

(za pomoc funkcji skadowej

set_value()

) obiekt przyszoci przechodzi w stan goto-

woci i jako taki moe zosta uyty do pobrania zapisanej wartoci. Jeli nastpi znisz-
czenie obiektu klasy

std::promise

bez wczeniejszego ustawienia wartoci, zamiast

oczekiwanej wartoci zostanie ustawiony stosowny wyjtek. Sposób przekazywania wyjt-
ków pomidzy wtkami zostanie opisany w punkcie 4.2.4.

Na listingu 4.10 pokazano przykad kodu wtku, który przetwarza poczenia w opi-

sany powyej sposób. W prezentowanym przykadzie uylimy pary klas

std::promise

´

<bool>

i

std::future<bool>

do identyfikacji udanej transmisji bloku danych wycho-

dzcych; warto powizana z obiektem przyszoci ma posta prostej flagi sukcesu

Poleć książkę

Kup książkę

background image

110

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

lub niepowodzenia. W przypadku pakietów przychodzcych funkcj danych powiza-
nych z obiektem przyszoci peni waciwa tre tych pakietów.

Listing 4.10. Obsuga wielu pocze w jednym wtku przy uyciu obiektów obietnic

#include <future>

void process_connections(connection_set& connections)
{
while(!done(connections))
{
for(connection_iterator
connection=connections.begin(),end=connections.end();
connection!=end;
++connection)
{
if(connection->has_incoming_data())
{
data_packet data=connection->incoming();
std::promise<payload_type>& p=
connection->get_promise(data.id);
p.set_value(data.payload);
}
if(connection->has_outgoing_data())
{
outgoing_packet data=
connection->top_of_outgoing_queue();
connection->send(data.payload);
data.promise.set_value(true);
}
}
}
}

Funkcja

process_connections()

wykonuje ptl do momentu, w którym funkcja

done()

zwróci warto

true

. W kadej iteracji tej ptli kod aplikacji sprawdza kolejno kade

poczenie

i pobiera dane przychodzce (jeli istniej) lub wysya kolejkowane

dane wychodzce . Zakadamy, e pakiet przychodzcy zawiera jaki identyfikator i wa-
ciwe dane. Identyfikator jest odwzorowywany na odpowiedni obiekt klasy

std::promise

(na przykad metod odnajdywania w kontenerze asocjacyjnym) , natomiast warto
jest przypisywana do ciaa pakietu. W przypadku pakietów wychodzcych zastosowa-
no mechanizm kolejki pakietów oczekujcych na wysanie — program sprawdza stan
kolejki i wysya ewentualne pakiety dla danego poczenia. Po wysaniu pakietu w obiek-
cie obietnicy powizanym z tymi danymi wychodzcymi jest ustawiana warto

true

,

która oznacza pomyln transmisj danych . Zgodno opisanego modelu z rzeczy-
wistymi protokoami komunikacji sieciowej zaley tylko od tych protokoów. Struktura
na bazie obietnicy i przyszoci nie pasuje co prawda do kadego scenariusza, ale pod
wieloma wzgldami przypomina model asynchronicznych operacji wejcia-wyjcia sto-
sowany w niektórych systemach operacyjnych.

W dotychczas prezentowanym kodzie cakowicie ignorowalimy problem wyjt-

ków. Wyobraenie wiata, w którym wszystko dziaa, jak naley, jest by moe kuszce,
ale nie ma wiele wspólnego z rzeczywistoci. Nie mona wykluczy, e dysk zostanie

Poleć książkę

Kup książkę

background image

4.2.

Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci

111

zapeniony, e program nie bdzie móg znale potrzebnych danych, e nastpi awa-
ria poczenia sieciowego lub e w wyniku bdu nie bdzie dostpna baza danych.
Jeli operacja wykonywana w jednym wtku potrzebuje do dziaania wyniku innego
wtku, warto uwzgldni moliwo zasygnalizowania bdu w formie wyjtku — zaka-
danie, e w kodzie stosujcym obiekty klasy

std::packaged_task

czy

std::promise

wszystko zawsze bdzie dziaao prawidowo, byoby zbyt optymistyczne. Biblioteka
standardowa jzyka C++ oferuje wygodne mechanizmy obsugi wyjtków w tego rodzaju
scenariuszach i umoliwia zapisywanie wyjtków w ramach wyników powizanych z tymi
obiektami.

4.2.4.

Zapisywanie wyjtku na potrzeby przyszoci

Przeanalizujmy nastpujcy fragment kodu. Jeli na wejciu funkcji

square_root()

prze-

kaemy warto

-1

, zgoszony zostanie wyjtek (to on trafi do kodu wywoujcego t

funkcj):

double square_root(double x)
{
if(x<0)
{
throw std::out_of_range(“x<0”);
}
return sqrt(x);
}

Przypumy teraz, e zamiast wywoa funkcj

square_root()

w biecym wtku, jak

w poniszym wierszu:

double y=square_root(-1);

uyjemy wywoania asynchronicznego w nastpujcej formie:

std::future<double> f=std::async(square_root,-1);
double y=f.get();

Idealnym rozwizaniem byoby zapewnienie dokadnie takiego samego zachowania
jak w przypadku kodu jednowtkowego — skoro zmiennej

y

w obu przypadkach jest

przypisywany wynik funkcji, wtek wywoujcy funkcj

f.get()

powinien mie dostp

take do ewentualnych wyjtków (tak jak odpowiedni kod jednowtkowy).

Okazuje si, e wanie tak dziaa prezentowane rozwizanie: jeli funkcja

square_

´

root

wywoana za porednictwem funkcji

std::async

zgosi jaki wyjtek, wyjtek

ten zostanie zapisany w obiekcie przyszoci (w miejscu dla wartoci wynikowej), przy-
szo przejdzie w stan gotowoci, a funkcja

get()

spowoduje ponowne zgoszenie zapi-

sanego wyjtku. (Uwaga: standard jzyka C++ nie okrela, czy ponowne zgoszenie
dotyczy oryginalnego obiektu wyjtku, czy jego kopii; róne kompilatory i biblioteki
stosuj w tym wzgldzie odmienne rozwizania). To samo dotyczy funkcji opakowanej
w ramach obiektu klasy

std::packaged_task

— jeli po wywoaniu zadania opakowana

funkcja zgosi jaki wyjtek, wyjtek jest zapisywany w obiekcie przyszoci zamiast
waciwego wyniku. Aby ponownie zgosi ten wyjtek, wystarczy wywoa funkcj

get()

.

Szablon klasy

std::promise

oferuje oczywicie analogiczne rozwizanie, które wymaga

bezporedniego wywoania funkcji. Aby zapisa wyjtek zamiast wartoci wynikowej,
wystarczy wywoa funkcj skadow

set_exception()

zamiast funkcji

set_value()

.

Poleć książkę

Kup książkę

background image

112

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

Wspomniana funkcja jest zwykle stosowana w bloku

catch

odpowiedzialnym za obsug

wyjtku zgoszonego w trakcie dziaania algorytmu — wyjtek jest umieszczany w obiek-
cie obietnicy:

extern std::promise<double> some_promise;

try
{
some_promise.set_value(calculate_value());
}
catch(...)
{
some_promise.set_exception(std::current_exception());
}

W powyszym kodzie uyto funkcji

std::current_exception()

do pobrania zgoszonego

wyjtku; alternatywnym rozwizaniem byoby wywoanie funkcji

std::copy_exception()

w celu zapisania nowego wyjtku bez jego bezporedniego zgaszania:

some_promise.set_exception(std::copy_exception(std::logic_error("foo ")));

Opisane rozwizanie jest nieporównanie bardziej czytelne ni stosowanie bloku

try

-

catch

,

jeli tylko potencjalny wyjtek jest znany z wyprzedzeniem. W ten sposób mona nie
tylko uproci kod, ale te uatwi optymalizacj tego kodu przez kompilator.

Innym sposobem zapisywania wyjtku w przyszoci jest zniszczenie obiektu klasy

std::promise

lub

std::packaged_task

powizanego z obiektem przyszoci bez uprzed-

niego wywoania funkcji ustawiajcej (w przypadku obiektu obietnicy) lub uruchomie-
nia opakowanego zadania. Jeli obiekt przyszoci nie bdzie gotowy, w obu przypadkach
destruktor klasy

std::promise

lub

std::packaged_task

zapisze w powizanym stanie

wyjtek typu

std::future_error

z kodem bdu

std::future_errc::broken_promise

.

Tworzc przyszo, zapowiadamy (skadamy obietnic), e udostpnimy jak warto
lub jaki wyjtek; zniszczenie róda tej wartoci lub tego wyjtku bez uprzedniego
dostarczenia zapowiedzianego zasobu amie t obietnic. Gdyby w opisanym przypadku
kompilator niczego nie zapisa w obiekcie przyszoci, wtki oczekujce mogyby czeka
w nieskoczono.

Do tej pory we wszystkich przykadach stosowaem szablon klasy

std::future

.

Warto jednak pamita o pewnych ograniczeniach szablonu

std::future

, w tym o mo-

liwoci oczekiwania na wynik przez zaledwie jeden wtek. W razie koniecznoci zaim-
plementowania modelu, w którym na jedno zdarzenie bdzie oczekiwao wiele wtków,
naley uy raczej szablonu klasy

std::shared_future

.

4.2.5.

Oczekiwanie na wiele wtków

Mimo e szablon klasy

std::future

obsuguje wszystkie mechanizmy synchronizacji

potrzebne do przesyania danych pomidzy wtkami, wywoania funkcji skadowych
okrelonego obiektu klasy

std::future

nie s synchronizowane z wywoaniami funkcji

pozostaych obiektów tej klasy. Jeli wiele wtków uzyskuje dostp do jednego obiektu
klasy

std::future

bez stosowania dodatkowych mechanizmów synchronizacji, aplika-

cja jest naraona na wycig danych i niezdefiniowane zachowania. Problem wynika
z projektu tego rozwizania — szablon klasy

std::future

modeluje unikatow wasno

asynchronicznego wyniku, a jednorazowy charakter funkcji

get()

i tak wyklucza sens

Poleć książkę

Kup książkę

background image

4.2.

Oczekiwanie na jednorazowe zdarzenia za pomoc przyszoci

113

wspóbienego dostpu. Skoro po pierwszym wywoaniu funkcji

get()

nie mona ju

pobra adnych danych, z natury rzeczy dane mog by pobrane tylko przez jeden wtek.

Jeli jednak projekt naszej aplikacji wspóbienej wymaga, aby wiele wtków mogo

czeka na to samo zdarzenie, nie wszystko stracone — wystarczy uy szablonu klasy

std::shared_future

. O ile szablon klasy

std::future

oferuje tylko moliwo przeno-

szenia, zatem wasno przyszoci mona przenosi pomidzy rónymi obiektami, ale
tylko jeden obiekt moe si jednoczenie odwoywa do jednego asynchronicznego
wyniku, o tyle szablon klasy

std::shared_future

oferuje moliwo kopiowania, zatem

moe istnie wiele obiektów odwoujcych si do tego samego stanu.

W przypadku szablonu

std::shared_future

funkcje skadowe wywoywane dla poje-

dynczego obiektu wci nie s synchronizowane, zatem warunkiem unikania wycigów
danych w zwizku z dostpem do tego samego obiektu z poziomu wielu wtków jest
ochrona tego dostpu za pomoc blokady. Najlepszym sposobem jest kopiowanie tego
obiektu, tak aby kady wtek uzyskiwa dostp do wasnej kopii. Dostp do wspódzie-
lonego, asynchronicznego stanu z poziomu wielu wtków jest bezpieczny, jeli tylko
kady z tych wtków uzyskuje dostp do stanu za porednictwem wasnego obiektu
klasy

std::shared_future

. Przykad takiego rozwizania pokazano na rysunku 4.1.

Rysunek 4.1.

Uycie

wielu obiektów klasy
std::shared_future
w celu uniknicia
wycigów danych

Jednym z moliwych zastosowa szablonu klasy

std::shared_future

jest implementa-

cja równolegego wykonywania jakiej operacji w modelu zblionym do zoonego
arkusza kalkulacyjnego, gdzie kada komórka zawiera warto, która moe by uywana

Poleć książkę

Kup książkę

background image

114

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

we wzorach w wielu pozostaych komórkach. Wzory potrzebne do obliczania wyników
w komórkach zalenych mog uywa obiektu klasy

std::shared_future

podczas odwo-

ywania si do pierwszej komórki. Jeli wzory we wszystkich komórkach bd prze-
twarzane równolegle, zadania odwoujce si do gotowych wartoci zostan zrealizo-
wane natychmiast, natomiast zadania zalene od innych, jeszcze przetwarzanych komórek
bd musiay poczeka na osignicie gotowoci przez tamte komórki. Takie rozwi-
zanie umoliwia maksymalne wykorzystanie dostpnej wspóbienoci sprztowej.

Obiekty klasy

std::shared_future

, które wskazuj pewien asynchroniczny stan, s

konstruowane na podstawie obiektów klasy

std::future

odwoujcych si do tego stanu.

Poniewa obiekty klasy

std::future

nie wspódziel wasnoci tego asynchronicznego

stanu z adnymi innymi obiektami, wasno naley przenie do obiektu klasy

std::

´

shared_future

za pomoc funkcji

std::move

, pozostawiajc oryginalny obiekt klasy

std::future

z pustym stanem (jak w przypadku uycia konstruktora domylnego):

std::promise<int> p;
std::future<int> f(p.get_future());
assert(f.valid());

Przyszo f jest prawidowa

std::shared_future<int> sf(std::move(f));
assert(!f.valid());

Przyszo f ju nie jest prawidowa

assert(sf.valid());

Przyszo sf jest teraz prawidowa

Obiekt przyszoci

f

jest pocztkowo prawidowy , poniewa odwouje si do asyn-

chronicznego stanu obietnicy

p

, jednak po przeniesieniu tego stanu do obiektu

sf

to

obiekt

sf

jest prawidowy , natomiast obiekt

f

jest ju nieprawidowy .

Jak w przypadku wszystkich obiektów z moliwoci przenoszenia, przeniesienie

wasnoci jest wykonywane automatycznie dla r-wartoci, zatem moemy skonstruowa
obiekt klasy

std::shared_future

bezporednio na podstawie wartoci zwróconej przez

funkcj skadow

get_future()

obiektu klasy

std::promise

:

std::promise<std::string> p;
std::shared_future<std::string> sf(p.get_future());

Automatyczne

przeniesienie wasnoci

W powyszym kodzie wasno jest przenoszona automatycznie — obiekt klasy

std::

´

shared_future<>

jest konstruowany na podstawie r-wartoci typu

std::future<std::

´

string>

.

Szablon klasy

std::future

oferuje jeszcze inne rozwizanie uatwiajce stosowanie

obiektów klasy

std::shared_future

przy uyciu nowego mechanizmu automatycznego

okrelania typu zmiennej na podstawie inicjalizatora (patrz cz A.6 dodatku A). Sza-
blon klasy

std::future

definiuje funkcj skadow

share()

, która tworzy nowy obiekt

klasy

std::shared_future

i bezporednio przenosi wasno do tego obiektu. Uycie tego

rozwizania moe nam oszczdzi sporo pisania i znacznie uatwia modyfikowanie kodu:

std::promise< std::map< SomeIndexType, SomeDataType, SomeComparator,
SomeAllocator>::iterator> p;
auto sf=p.get_future().share();

W tym przypadku typ zmiennej

sf

jest identyfikowany jako

std::shared_future<

std::map< SomeIndexType, SomeDataType, SomeComparator, SomeAllocator>::iterator>

,

czyli konstrukcja, której wielokrotne stosowanie w kodzie byoby do kopotliwe.

Poleć książkę

Kup książkę

background image

4.3.

Oczekiwanie z limitem czasowym

115

W razie zmiany komparatora lub alokatora wystarczy zmodyfikowa typ obiektu obiet-
nicy; typ obiektu przyszoci zostanie automatycznie zaktualizowany i dostosowany do
tej zmiany.

W pewnych przypadkach dobrym rozwizaniem jest ograniczanie maksymalnego

czasu oczekiwania na zdarzenie (z uwagi na ograniczony czas dziaania okrelonej sekcji
kodu lub ze wzgldu na istnienie innych wanych zada, którymi dany wtek moe si
zaj, jeli oczekiwane zdarzenie nie wystpi odpowiednio wczenie). Z myl o takich
przypadkach wiele funkcji oczekiwania oferuje wersje z moliwoci okrelenia limitu
czasowego.

4.3.

Oczekiwanie z limitem czasowym

Wszystkie wywoania blokujce, które stosowalimy w dotychczasowych przykadach,
blokoway wykonywanie wtków przez nieokrelony czas, tj. do momentu wystpienia
oczekiwanego zdarzenia. W wielu przypadkach takie rozwizanie jest wystarczajce,
jednak w niektórych sytuacjach lepszym wyjciem jest okrelenie maksymalnego czasu
oczekiwania. Stosowanie takich limitów czasowych moe mie na celu potwierdzenie
prawidowego dziaania aplikacji (w formie komunikatu dla uytkownika lub innego
procesu) lub przerwanie oczekiwania, jeli na przykad uytkownik klikn przycisk
Anuluj.

Istniej dwa rodzaje limitów czasowych stosowanych dla operacji blokujcych: limity

okrelajce maksymalny czas blokowania wtku (na przykad 30 milisekund) oraz limity
bezwzgldne, gdzie oczekiwanie nie moe trwa duej ni do okrelonego punktu
w czasie (na przykad do godziny 17:30:15.045987023 dnia 30 listopada 2012 roku).
Wikszo funkcji oczekujcych wystpuje w wersjach obsugujcych obie formy limi-
tów czasowych. Wersje obsugujce wzgldne limity czasowe (okrelajce czas trwania
operacji) s oznaczane przyrostkiem

_for

, natomiast bezwzgldne limity czasowe ozna-

cza si przyrostkiem

_until

.

Na przykad klasa

std::condition_variable

definiuje dwie przecione wersje funk-

cji skadowej

wait_for()

i dwie przecione wersje funkcji skadowej

wait_until()

,

czyli odpowiedniki obu wersji funkcji

wait()

uzupenione o obsug wzgldnych i bez-

wzgldnych limitów czasowych — pierwsza wersja czeka na sygna, upynicie limitu
czasowego lub bezporednie budzenie; druga wersja w momencie budzenia sprawdza
przekazany predykat i zwraca sterowanie, pod warunkiem e albo ten predykat jest
prawdziwy (w wyniku sygnau umieszczonego w zmiennej warunkowej), albo osignito
limit czasowy.

Zanim przeanalizujemy szczegóowe aspekty stosowania funkcji uwzgldniajcych

limity czasowe, warto powici chwil na omówienie sposobu okrelania czasu w jzyku
C++, w tym dostpnych zegarów.

4.3.1.

Zegary

W kontekcie elementów biblioteki standardowej jzyka C++ zegar jest dla programu
ródem informacji o biecej godzinie. W szczególnoci zegar jest klas udostpnia-
jc cztery odrbne informacje:

Poleć książkę

Kup książkę

background image

116

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

Q

bieca godzina;

Q

typ wartoci uywanych do reprezentowania godzin uzyskiwanych z obiektu
zegara;

Q

okres reprezentowany przez jeden takt zegara;

Q

to, czy takty zegara maj sta dugo, czyli moliwo traktowania zegara
jako stabilnego.

Biec godzin reprezentowan przez zegar mona uzyska, wywoujc statyczn funk-
cj skadow

now()

klasy zegara; na przykad funkcja

std::chrono::system_clock::now()

zwróci biec godzin reprezentowan przez zegar systemowy. Typ punktów w czasie
dla poszczególnych zegarów jest reprezentowany przez skadow definicj typu

time_

´

point

, zatem kada funkcja

zegar::now()

zwraca warto typu

zegar::time_point

.

Okres taktu zegara jest wyraany w formie uamka sekundy reprezentowanego

przez skadow definicj typu

period

— w przypadku zegara wykonujcego 25 taktów

w cigu sekundy

period

definiuje typ

std::ratio<1,25>

, natomiast w przypadku zegara

wykonujcego jeden takt na 2,5 sekundy skadowa

period

definiuje typ

std::ratio<5,2>

.

Jeli okrelenie okresu taktu nie jest moliwe do momentu uruchomienia programu
lub jeli ten okres moe si zmienia w czasie dziaania aplikacji, okres mona zdefi-
niowa w formie redniego czasu trwania taktu, najkrótszego moliwego taktu lub innej
wartoci przewidzianej przez twórców biblioteki. Nie mona jednak zakada, e obser-
wowany okres taktu zegara podczas jednej próby uruchomienia programu bdzie odpo-
wiada rzeczywistemu okresowi danego zegara.

Jeli takty zegara maj sta czstotliwo (niezalenie od tego, czy ta czstotli-

wo pasuje do przyjtego okresu) i jeli nie moemy zmieni dugoci taktu, mamy do
czynienia z tzw. stabilnym zegarem (ang. steady clock). Skadowa statyczna

is_steady

klasy stabilnego zegara ma warto

true

(w przypadku niestabilnego zegara ta sama ska-

dowa ma warto

false

). Zegar systemowy (reprezentowany przez klas

std::chrono::

´

system_clock

) zwykle nie jest stabilny, poniewa mona dostosowywa jego czsto-

tliwo (nawet jeli zmiany czstotliwoci s wprowadzane automatycznie z uwzgld-
nieniem przesuni wzgldem zegara lokalnego). Kada taka zmiana moe spowodo-
wa, e wywoanie funkcji

now()

zwróci warto wczeniejsz ni zwrócona przez

poprzednie wywoanie tej funkcji, co oczywicie narusza wymaganie staej czstotli-
woci zegara (i dugoci taktu). Jak si za chwil przekonasz, stabilne zegary s szcze-
gólnie przydatne podczas oblicze z uwzgldnieniem limitów czasowych — z myl
o tych i podobnych zastosowaniach twórcy biblioteki standardowej udostpnili taki
zegar w formie klasy

std::chrono::steady_clock

. Biblioteka standardowa jzyka C++

zawiera te inne klasy zegarów: wspomnian wczeniej klas

std::chrono::system_clock

,

która reprezentuje zegar „czasu rzeczywistego” w danym systemie i która udostpnia
funkcj konwersji punktów w czasie na i z wartoci typu

time_t

, oraz klas

std::

´

chrono::high_resolution_clock

, która zapewnia najkrótszy moliwy takt zegara (a wic

take najwysz moliw czstotliwo) sporód wszystkich zegarów tej biblioteki.
Drugi z zegarów mona wykorzysta w roli punktu wyjcia dla definicji alternatyw-
nych rozwiza. Wymienione zegary zdefiniowano (wraz z pozostaymi elementami
zwizanymi z obsug czasu) w pliku nagówkowym

<chrono>

.

Zanim przystpimy do omawiania metod reprezentowania punktów w czasie, warto

powici chwil analizie technik reprezentowania okresów.

Poleć książkę

Kup książkę

background image

4.3.

Oczekiwanie z limitem czasowym

117

4.3.2.

Okresy

Okres (czas trwania) to najprostszy aspekt obsugi czasu. Okres zaimplementowano
w szablonie klasy

std::chrono::duration<>

(wszystkie elementy jzyka C++ zwizane

z obsug czasu i uywane przez bibliotek wtków nale do przestrzeni nazw

std::

´

chrono

). Pierwszy parametr tego szablonu okrela typ reprezentacji (na przykad

int

,

long

lub

double

); drugi parametr jest uamkiem okrelajcym liczb sekund repre-

zentowanych przez jednostk okresu. Na przykad liczba minut przechowywana w war-
toci typu

short

jest reprezentowana przez klas

std::chrono::duration<short,std::

´

ratio<60,1>>

, poniewa minuta skada si z 60 sekund. Liczba milisekund prze-

chowywanych w wartoci typu

double

jest reprezentowana przez klas

std::chrono::

´

duration<double,std::ratio<1,1000>>

, poniewa kada milisekunda trwa jedn

tysiczn cz sekundy.

Biblioteka standardowa oferuje zbiór predefiniowanych definicji typów w prze-

strzeni nazw

std::chrono

dla rónych okresów (wyraanych w nanosekundach, mikro-

sekundach, milisekundach, sekundach, minutach i godzinach). Wszystkie te definicje
stosuj na tyle elastyczne typy cakowitoliczbowe, e mog reprezentowa na przykad
okresy ponad 500-letnie w wybranych jednostkach czasu. Przestrze nazw zawiera
take definicje typów dla rzdów wielkoci ukadu SI: od

std::atto

(10

–18

) do

std::exa

(10

18

) (i wicej, jeli tylko dana platforma obsuguje 128-bitowe typy cakowitoliczbowe).

Za pomoc tych typów mona operowa na niestandardowych okresach, na przykad
klasa

std::duration<double,std::centi>

obsuguje liczb setnych czci sekundy repre-

zentowanych przez liczb typu

double

.

Konwersja pomidzy okresami jest wykonywana automatycznie, pod warunkiem

e nie wymaga obcicia wartoci ródowej — oznacza to, e konwersja godzin na
sekundy jest moliwa, ale ju konwersja sekund na godziny nie zostanie wykonana auto-
matycznie. Konwersj mona te wykona jawnie za pomoc funkcji

std::chrono::

´

duration_cast<>

:

std::chrono::milliseconds ms(54802);
std::chrono::seconds s=
std::chrono::duration_cast<std::chrono::seconds>(ms);

Poniewa wynik jest obcinany (nie zaokrglany), zmienna

s

bdzie zawieraa warto 54.

Okresy obsuguj dziaania arytmetyczne, zatem moemy dodawa i odejmowa

okresy, aby otrzymywa nowe okresy, bd mnoy lub dzieli okresy przez stae wybra-
nego typu danych (czyli pierwszego parametru szablonu klasy). Oznacza to, e wyraenie

5*seconds(1)

ma tak sam warto jak wyraenia

seconds(5)

i

minutes(1) – seconds(55)

.

Liczb jednostek skadajcych si na dany okres mona uzyska za pomoc funkcji
skadowej

count()

. Oznacza to, e wywoanie

std::chrono::milliseconds(1234).count()

zwróci warto

1234

.

Wymuszanie oczekiwania na podstawie okresu (czasu trwania) wymaga stosowania

instancji typu

std::chrono::duration<>

. Moemy na przykad spowodowa, e czas

oczekiwania na gotowo obiektu przyszoci wyniesie 35 milisekund:

std::future<int> f=std::async(some_task);
if(f.wait_for(std::chrono::milliseconds(35))==std::future_status::ready)
do_something_with(f.get());

Poleć książkę

Kup książkę

background image

118

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

Wszystkie funkcje oczekiwania zwracaj status okrelajcy, czy koniec oczekiwania
wynika z wyczerpania limitu czasowego, czy z wystpienia zdarzenia, na które czeka
dany wtek. W tym przypadku wtek czeka na przyszo, zatem funkcja zwraca warto

std::future_status::timeout

w przypadku wyczerpania limitu czasowego; warto

std::future_status::ready

, jeli przyszo jest gotowa; lub warto

std::future_

´

status::deferred

, jeli zadanie przyszoci zostao odoone na póniej. Czas ocze-

kiwania okresowego jest mierzony przy uyciu stabilnego, wewntrznego zegara biblio-
teki, zatem 35 milisekund oznacza wanie 35 milisekund, nawet jeli w czasie oczekiwa-
nia zegar systemowy zostanie przestawiony (w przód lub w ty). Nie mona oczywicie
zapomina o kaprysach systemu szeregowania zada i o zrónicowanej precyzji zega-
rów systemów operacyjnych, które mog spowodowa, e rzeczywisty czas dzielcy
wywoanie funkcji

wait()

od zwrócenia sterowania bdzie duo duszy ni 35 ms.

Skoro potrafimy ju stosowa okresy, moemy przej do analizy modelu punktów

w czasie.

4.3.3.

Punkty w czasie

Punkt w czasie jest reprezentowany przez instancj szablonu klasy

std::chrono::

´

time_point<>

. Pierwszy parametr tego szablonu wskazuje zegar, natomiast drugi para-

metr okrela jednostki miary (w tej roli naley uy specjalizacji szablonu klasy

std::chrono::duration<>

). Warto punktu w czasie reprezentuje czas (w formie wielo-

krotnoci wskazanego okresu) od konkretnego punktu w czasie nazywanego epok zegara.
Epoka zegara jest prost waciwoci, która jednak nie jest bezporednio dostpna
ani wprost definiowana przez standard jzyka C++. Do najczciej stosowanych
epok naley pónoc 1 stycznia 1970 roku i moment uruchomienia komputera, na którym
dziaa dana aplikacja. Zegary mog stosowa jedn epok lub róne, niezalene epoki.
Jeli dwa zegary stosuj t sam epok, definicja typu

time_point

w klasie jednego zegara

moe wskazywa drug klas jako typ zegara powizanego z dan definicj

time_point

.

Mimo e nie mona bezporednio uzyska epoki, mamy do dyspozycji funkcj

time_

´

since_epoch()

, któr moemy wywoa dla danej instancji typu

time_point

. Funkcja

skadowa

time_since_epoch()

zwraca warto okresu reprezentujc czas od epoki zegara

do okrelonego punktu w czasie.

Punkt w czasie mona zdefiniowa na przykad w formie obiektu klasy

std::chrono::

´

time_point<std::chrono::system_clock, std::chrono::minutes>

. Tak skonstruowany

obiekt zawiera czas wzgldem zegara systemowego, tyle e mierzony w minutach (nie
wedug standardowej precyzji zegara systemowego, czyli sekund lub czci sekundy).

Na obiektach klasy

std::chrono::time_point<>

mona wykonywa operacje doda-

wania i odejmowania okresów, których wynikiem s nowe punkty w czasie. Oznacza
to, e na przykad w wyniku dodawania

std::chrono::high_resolution_clock::now()

+ std::chrono::nanoseconds(500)

otrzymamy punkt w czasie, który nastpi za 500

nanosekund (liczc od teraz). Wyraenia tego typu s przydatne podczas obliczania
bezwzgldnego limitu czasowego w sytuacji, gdy maksymalny czas wykonywania bloku
kodu jest znany z wyprzedzeniem. Takie rozwizanie wymaga jednak wielu wywoa
funkcji oczekujcych lub funkcji poprzedzajcych funkcj oczekujc i zaliczanych do
bloku, który podlega ograniczeniu czasowemu.

Poleć książkę

Kup książkę

background image

4.3.

Oczekiwanie z limitem czasowym

119

Istnieje te moliwo odjcia jednego punktu w czasie od innego, pod warunkiem

e oba punkty bazuj na tym samym zegarze. Wynikiem tej operacji jest okres, który
reprezentuje czas dzielcy oba punkty. W ten sposób mona na przykad sprawdza czas
wykonywania bloków kodu:

auto start=std::chrono::high_resolution_clock::now();
do_something();
auto stop=std::chrono::high_resolution_clock::now();
std::cout<<”Wykonanie funkcji do_something() zajo “
<<std::chrono::duration<double,std::chrono::seconds>(stop-start).count()
<<” sekund.”<<std::endl;

Parametr zegara szablonu klasy

std::chrono::time_point<>

decyduje nie tylko o epoce.

W przypadku przekazania punktu w czasie na wejciu funkcji oczekujcej, która sto-
suje bezwzgldny limit czasowy, wybrany zegar bdzie uywany do mierzenia czasu.
Warto pamita o moliwoci zmiany wskaza zegara i o tym, e funkcja oczekujca
nie zwróci sterowania do momentu, w którym funkcja

now()

tego zegara nie zwróci

wartoci póniejszej od wskazanego limitu czasowego. Jeli zegar zostanie przesta-
wiony w przód, czny czas oczekiwania moe by krótszy (w porównaniu z czasem
mierzonym przez stabilny zegar); a jeli zegar zostanie cofnity, czny czas oczekiwa-
nia zostanie wyduony.

Jak nietrudno odgadn, punkty w czasie s uywane w wersjach funkcji oczekuj-

cych z przyrostkiem

_until

. Typowym zastosowaniem tego rozwizania jest wyznacza-

nie przesunicia wzgldem godziny zwracanej przez wywoanie

jaki-zegar

::now()

w wybranym punkcie programu. Punkty powizane z zegarem systemowym mona
uzyskiwa, konwertujc instancje typu

time_t

za pomoc statycznej funkcji skadowej

std::chrono::system_clock::to_time_point()

. Jeli na przykad maksymalny czas ocze-

kiwania na zdarzenie powizane ze zmienn warunkow wynosi 500 milisekund, mona
zastosowa konstrukcj podobn do tej z listingu 4.11.

Listing 4.11. Oczekiwanie na zmienn warunkow z uwzgldnieniem limitu
czasowego

#include <condition_variable>
#include <mutex>
#include <chrono>

std::condition_variable cv;
bool done;
std::mutex m;

bool wait_loop()
{
auto const timeout= std::chrono::steady_clock::now()+
std::chrono::milliseconds(500);
std::unique_lock<std::mutex> lk(m);
while(!done)
{
if(cv.wait_until(lk,timeout)==std::cv_status::timeout)
break;
}
return done;
}

Poleć książkę

Kup książkę

background image

120

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

Rozwizanie z listingu 4.11 jest zalecanym sposobem oczekiwania na zmienne warun-
kowe z uwzgldnieniem limitu czasowego w sytuacji, gdy funkcja oczekujca nie
otrzymuje na wejciu adnego predykatu. Maksymalny czas wykonywania ptli jest
ograniczony. Jak napisaem w punkcie 4.1.1, jeli nie stosujemy dodatkowego predy-
katu, operowanie na zmiennych warunkowych wymaga uycia ptli, która obsuguje
nietypowe sposoby budzenia wtku. W przypadku wywoania funkcji

wait_for()

w ciele

ptli moe si zdarzy, e warunek wznowienia dziaania zostanie speniony bezpored-
nio przed upywem limitu czasowego, a w nastpnej iteracji czas oczekiwania bdzie
liczony od pocztku. Taka sytuacja moe mie miejsce wielokrotnie, zatem czny czas
oczekiwania byby nieograniczony.

Skoro dysponujemy ju podstawowymi narzdziami umoliwiajcymi stosowanie

limitów czasowych, pora omówi funkcje, w których mona uywa tych limitów.

4.3.4.

Funkcje otrzymujce limity czasowe

Najprostszym zastosowaniem limitu czasowego jest dodanie opónienia do przetwarza-
nia okrelonego wtku, tak aby ten wtek nie zajmowa czasu procesora (potrzebnego
innym wtkom) w czasie, gdy nie wykonuje adnych wartociowych zada. Przykad
takiego rozwizania opisaem w podrozdziale 4.1, gdzie kod wielokrotnie sprawdza
stan flagi gotowoci w ptli. Do opóniania dziaania (usypiania) wtków su funkcje

std::this_thread::sleep_ for()

i

std::this_thread::sleep_until()

. Obie funkcje

dziaaj jak proste budziki — wtek jest usypiany albo na okrelony okres (za pomoc
funkcji

sleep_for()

), albo do wskazanego punktu w czasie (za pomoc funkcji

sleep_

´

until()

). W przykadowych rozwizaniach z podrozdziau 4.1 naleaoby uy funkcji

sleep_for()

, poniewa w przypadku okresowo wykonywanych operacji wtek powi-

nien by wstrzymywany na pewien czas (nie do okrelonego punktu w czasie). Funkcja

sleep_until()

umoliwia planowanie budzenia wtku w okrelonym punkcie w czasie.

Funkcja

sleep_until()

moe wic suy na przykad do uruchamiania procedury two-

rzenia kopii zapasowej o pónocy, drukowania listy pac o 6 rano lub wstrzymywania
wtku do momentu wywietlenia nastpnej klatki podczas odtwarzania zapisu wideo.

Usypianie wtku to oczywicie nie jedyne zastosowanie limitów czasowych — jak

ju wspomniaem, limity tego typu mona stosowa cznie ze zmiennymi warunko-
wymi i przyszociami. Istnieje nawet moliwo stosowania limitów czasowych pod-
czas prób uzyskania blokady muteksu, jeli tylko uyty muteks obsuguje takie dziaa-
nie. Standardowe muteksy typów

std::mutex

i

std::recursive_mutex

nie obsuguj

limitów czasowych dla operacji blokowania, ale ju muteksy typów

std::timed_mutex

i

std::recursive_timed_mutex

dopuszczaj takie dziaanie. Oba te typy udostpniaj

funkcje skadowe

try_lock_for()

i

try_lock_until()

, które próbuj uzyska blokad

muteksu odpowiednio w okrelonym czasie lub przed osigniciem okrelonego punktu
w czasie. W tabeli 4.1 opisano funkcje biblioteki standardowej jzyka C++, które obsu-
guj limity czasowe, wraz z ich parametrami i typami zwracanych wartoci. W miejsce
parametru opisanego jako

okres

naley przekaza obiekt klasy

std::duration<>

, nato-

miast parametr

punkt_w_czasie

naley zastpi obiektem klasy

std::time_point<>

.

Skoro wiemy ju, jak dziaaj zmienne warunkowe, obiekty przyszoci i obietnic

oraz opakowane zadania, czas przeanalizowa te mechanizmy w nieco szerszym kon-
tekcie, w szczególnoci przyjrze si technikom upraszczania (za pomoc tych mecha-
nizmów) synchronizacji operacji wykonywanych przez róne wtki.

Poleć książkę

Kup książkę

background image

4.4.

Upraszczanie kodu za pomoc technik synchronizowania operacji

121

Tabela 4.1.

Funkcje otrzymujce limity czasowe

Klasa lub przestrze nazw

Funkcje

Zwracane wartoci

Przestrze nazw

std::this_thread

sleep_for(okres)

sleep_until(punkt_w_czasie)

Nie dotyczy

std::condition_variable

lub

std::condition_variable_any

wait_for(blokada, okres)

wait_until(blokada,
punkt_w_czasie

)

std::cv_status::timeout

lub

std::cv_status::no_timeout

wait_for(blokada, okres,
predykat

)

wait_until(blokada,
punkt_w_czasie

, predykat)

bool

— warto zwrócona

przez

predykat

po obudzeniu

wtku.

std::timed_mutex

lub

std::recursive_timed_mutex

try_lock_for(okres)

try_lock_until

´

(punkt_w_czasie)

bool

— warto

true

,

jeli udao si uzyska blokad;
w przeciwnym razie warto

false

std::unique_lock<Typ

´

ZMoliwociBlokady

´

Czasowej

>

unique_lock

´

(typ_blokowalny, okres)

unique_lock(typ_blokowalny,
punkt_w_czasie

)

Nie dotyczy — funkcja

owns_lock()

wywoana

dla nowo skonstruowanego
obiektu zwraca warto

true

,

jeli udao si uzyska blokad
(w przeciwnym razie zwraca
warto

false

).

try_lock_for(okres)

try_lock_until

´

(punkt_w_czasie)

bool

— warto

true

, jeli

udao si uzyska blokad;
w przeciwnym razie warto

false

std::future<TypWartoci>

lub

std::shared_future<

´

TypWartoci

>

wait_for(okres)

wait_until(punkt_w_czasie)

Jeli wyczerpano limit czasu
funkcji oczekujcej, zwraca
warto

std::future_status::timeout

;

jeli obiekt przyszoci
jest gotowy, zwraca warto

std::future_status::ready

;

jeli przyszo zawiera
odroczon funkcj, która
nie zostaa jeszcze wywoana,
zwraca warto

std::future_status::deferred

.

4.4.

Upraszczanie kodu za pomoc technik
synchronizowania operacji

Stosowanie mechanizmów synchronizacji, które opisaem w poprzednich podrozdzia-
ach, w roli gotowych elementów skadowych umoliwia programicie koncentrowanie
si na samych operacjach wymagajcych synchronizacji, nie na mechanice tej synchro-
nizacji. Mechanizmy synchronizacji pozwalaj uproci kod aplikacji choby dlatego,
e wprowadzaj do wiata programowania wspóbienego duo wicej elementów zna-
nych z programowania funkcyjnego. Zamiast bezporednio wspódzieli dane pomidzy
wtkami, kade zadanie moe otrzymywa potrzebne dane, a wynik przetwarzania moe
by przekazywany do wielu innych wtków za porednictwem obiektów przyszoci.

Poleć książkę

Kup książkę

background image

122

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

4.4.1.

Programowanie funkcyjne przy uyciu przyszoci

Termin programowanie funkcyjne (ang. functional programming — FP) odnosi si do
stylu programowania, w którym wynik wywoania funkcji zaley wycznie od para-
metrów przekazanych na jej wejciu. Oznacza to, e na wynik funkcji nie ma wpywu
zewntrzny stan. Opisane dziaanie jest wic zgodne z matematycznym pojciem funk-
cji, gdzie kade uycie jednej funkcji z tymi samymi parametrami spowoduje otrzy-
manie dokadnie takiego samego wyniku. W ten sposób dziaa wiele matematycznych
funkcji biblioteki standardowej jzyka C++, jak

sin

,

cos

czy

sqrt

, oraz prostych ope-

racji na typach podstawowych, jak

3+3

,

6*9

czy

1.3/4.7

. Typowa funkcja nie modyfi-

kuje zewntrznego stanu; skutki wykonywania tej funkcji ograniczaj si tylko do
zwracanej wartoci.

Opisany model programowania uatwia interpretacj kodu, szczególnie jeli program

zawiera elementy przetwarzania wspóbienego, poniewa wiele problemów zwizanych
z pamici wspódzielon (opisanych w rozdziale 3.) w ogóle nie wystpuje w wiecie pro-
gramowania funkcyjnego. Skoro dane wspódzielone nie s modyfikowane, nie mog wy-
stpi sytuacje wycigów, zatem ochrona tych danych za pomoc muteksów jest po prostu
niepotrzebna. Wanie prostota tego modelu powoduje, e takie jzyki programowania jak
Haskell

2

, gdzie wszystkie funkcje domylnie speniaj warunek programowania funkcyj-

nego, zyskuj coraz wiksz popularno wród programistów systemów wspóbienych.
Poniewa niemal cay kod jest zgodny z zasadami programowania funkcyjnego, nieliczne
funkcje, które modyfikuj wspódzielony stan, na tyle wyróniaj si sporód pozostaych
elementów, e mona bez trudu oceni ich udzia w caej strukturze aplikacji.

Zalety programowania funkcyjnego nie ograniczaj si tylko do jzyków, w których

ten model jest domylnym paradygmatem. Jzyk C++ czy w sobie wiele paradyg-
matów, zatem take pisanie programów wedug zasad programowania funkcyjnego
jest moliwe w tym jzyku. W wersji C++11 programowanie funkcyjne jest jeszcze
prostsze ni w standardzie C++98 dziki wprowadzeniu funkcji lambda (patrz cz A.5
dodatku A), integracji funkcji

std::bind

zaczerpnitej z biblioteki Boost i dokumentu

TR1 oraz dodaniu automatycznego wnioskowania typów zmiennych (patrz cz A.7
dodatku A). Ostatnim elementem, który uatwia programowanie funkcyjne w jzyku
C++, s obiekty przyszoci — obiekt przyszoci mona przekazywa pomidzy
wtkami, tak aby wynik jednej operacji móg zalee od wyniku innej operacji i aby ta
zaleno nie wymagaa bezporedniego dostpu do wspódzielonych danych.

S

ZYBKIE SORTOWANIE W MODELU PROGRAMOWANIA FUNKCYJNEGO

Aby lepiej zrozumie moliwe zastosowania przyszoci w modelu programowania funk-
cyjnego, przeanalizujmy prost implementacj algorytmu sortowania szybkiego (ang.
quicksort). Podstawowa koncepcja tego algorytmu jest do prosta — naley z listy
wartoci wybra element dzielcy, osiowy (ang. pivot), po czym podzieli list na dwa
zbiory, z których jeden zawiera elementy mniejsze od elementu dzielcego, a drugi
zawiera elementy wiksze od wybranego elementu. Posortowana kopia listy jest uzyski-
wana poprzez sortowanie obu podzbiorów i poczenie odpowiednio posortowanej listy
zoonej z wartoci mniejszych od elementu dzielcego, samego elementu dzielcego

2

Patrz http://www.haskell.org/.

Poleć książkę

Kup książkę

background image

4.4.

Upraszczanie kodu za pomoc technik synchronizowania operacji

123

i posortowanej listy wikszej od elementu dzielcego. Przykad sortowania listy dziesiciu
liczb cakowitych wedug opisanego schematu pokazano na rysunku 4.2. Na listingu 4.12
pokazano sekwencyjn implementacj tego algorytmu opracowan zgodnie z zasadami
programowania funkcyjnego; funkcja

sequential_quick_sort()

otrzymuje list i zwraca

jej posortowan kopi przez warto (zamiast sortowa list przekazan przez referen-
cj, jak w przypadku funkcji

std::sort()

).

Rysunek 4.2.

Rekurencyjne sortowanie w modelu programowania funkcyjnego

Listing 4.12. Sekwencyjna implementacja algorytmu sortowania szybkiego

template<typename T>
std::list<T> sequential_quick_sort(std::list<T> input)
{
if(input.empty())
{
return input;
}
std::list<T> result;
result.splice(result.begin(),input,input.begin());
T const& pivot=*result.begin();

auto divide_point=std::partition(input.begin(),input.end(),
[&](T const& t){return t<pivot;});

std::list<T> lower_part;
lower_part.splice(lower_part.end(),input,input.begin(),
divide_point);

auto new_lower(
sequential_quick_sort(std::move(lower_part)));
auto new_higher(
sequential_quick_sort(std::move(input)));

result.splice(result.end(),new_higher);
result.splice(result.begin(),new_lower);
return result;
}

Poleć książkę

Kup książkę

background image

124

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

Mimo e zewntrzny interfejs tej implementacji jest zgodny z reguami programowania
funkcyjnego, wewntrzne mechanizmy zaimplementowano w „tradycyjny” sposób,
poniewa konsekwentne stosowanie modelu funkcyjnego wymagaoby wielu dodatko-
wych operacji kopiowania. W roli elementu dzielcego jest wybierany pierwszy element,
który jest wyodrbniany z listy za pomoc funkcji

splice()

. Chocia sortowanie na

bazie tak wybranego elementu dzielcego moe nie by optymalne (liczba operacji
porównania i wymiany moe by wiksza, ni to konieczne), pozostae operacje na
strukturze typu

std::list

bd wykonywane szybciej dziki efektywnemu przeszu-

kiwaniu listy. Wiadomo, e wyodrbniony element dzielcy musi si znale na licie
wynikowej, zatem jest od razu umieszczany w odpowiedniej strukturze. Poniewa
element dzielcy bdzie teraz porównywany z pozostaymi elementami, przekazujemy
referencj do tego elementu, aby unikn wielokrotnego kopiowania . Moemy nastp-
nie uy funkcji

std::partition

do podzielenia sekwencji na wartoci mniejsze od

elementu dzielcego i wartoci nie mniejsze od tego elementu . Najprostszym spo-
sobem okrelenia kryterium podziau jest uycie funkcji lambda — aby unikn kopio-
wania wartoci elementu dzielcego, zastosowano tutaj technik przechwytywania refe-
rencji (wicej informacji na temat funkcji lambda mona znale w czci A.5 dodatku A).

Funkcja

std::partition()

przetwarza przekazan list i zwraca iterator wskazujcy

pierwszy element, który nie jest mniejszy od wartoci elementu dzielcego. Kompletny
typ iteratora moe by do dugi, zatem w powyszym kodzie uyto mechanizmu auto-
matycznej identyfikacji typów, aby to kompilator automatycznie okreli odpowiedni
typ (patrz cz A.7 dodatku A).

Poniewa analizowana implementacja udostpnia interfejs zgodny z zasadami pro-

gramowania funkcyjnego, warunkiem rekurencyjnego posortowania obu „poówek” listy
jest utworzenie dwóch odrbnych list. Do tego celu moemy ponownie uy funkcji

splice()

, aby skopiowa wartoci z listy wejciowej (do elementu

divide_point

) i umie-

ci na nowej licie:

lower_part

. Reszta wartoci pozostanie na licie wejciowej.

Obie listy mona nastpnie posortowa za pomoc rekurencyjnych wywoa funkcji

sequential_quick_sort()

. Uycie funkcji

std::move()

podczas przekazywania

list na wejciu rekurencyjnych wywoa pozwala unikn kopiowania tych struktur
(wyniki obu wywoa s kopiowane automatycznie). I wreszcie moemy ponownie uy
funkcji

splice()

w celu uporzdkowania list reprezentujcych podzbiory elementów

oryginalnej struktury. Wartoci z listy

new_higher

trafiaj na koniec listy wynikowej

(za element dzielcy), natomiast wartoci z listy

new_lower

s umieszczane na pocztku

listy (przed elementem dzielcym).

S

ZYBKIE SORTOWANIE RÓWNOLEGE W MODELU PROGRAMOWANIA FUNKCYJNEGO

Poniewa ju w poprzednim przykadzie zastosowano reguy programowania funkcyj-
nego, konwersja tego algorytmu na wersj równoleg (korzystajc z obiektów przy-
szoci) nie jest specjalnie trudna (patrz listing 4.13). Zbiór operacji jest taki sam jak
w poprzedniej wersji, tyle e teraz cz tych operacji jest wykonywana równolegle.
W tej wersji uyto implementacji algorytmu sortowania szybkiego czcej obiekty przy-
szoci i model programowania funkcyjnego.

Jedn z najwaniejszych rónic dzielcych obie wersje jest to, e w wersji wspó-

bienej cz listy sprzed elementu dzielcego nie jest sortowana w biecym wtku,
tylko w dodatkowym wtku — w tym celu zastosowano funkcj

std::async()

. Druga

Poleć książkę

Kup książkę

background image

4.4.

Upraszczanie kodu za pomoc technik synchronizowania operacji

125

Listing 4.13. Równolege sortowanie szybkie z wykorzystaniem przyszoci

template<typename T>
std::list<T> parallel_quick_sort(std::list<T> input)
{
if(input.empty())
{
return input;
}
std::list<T> result;
result.splice(result.begin(),input,input.begin());
T const& pivot=*result.begin();

auto divide_point=std::partition(input.begin(),input.end(),
[&](T const& t){return t<pivot;});

std::list<T> lower_part;
lower_part.splice(lower_part.end(),input,input.begin(),
divide_point);

std::future<std::list<T> > new_lower(
std::async(&parallel_quick_sort<T>,std::move(lower_part)));

auto new_higher(
parallel_quick_sort(std::move(input)));

result.splice(result.end(),new_higher);
result.splice(result.begin(),new_lower.get());
return result;
}

cz listy jest sortowana tak jak w poprzedniej wersji, a wic przy uyciu bezpored-
niego wywoania rekurencyjnego . Rekurencyjne wywoanie funkcji

parallel_quick_

´

sort()

pozwala wykorzysta dostpn wspóbieno sprztow. Jeli wywoanie

funkcji

std::async()

za kadym razem uruchamia nowy wtek, wystarcz trzy poziomy

rekurencji, aby program zosta podzielony na osiem wtków; w przypadku dziesiciu
poziomów rekurencji (czyli okoo tysica elementów) program w tej formie uruchomi
1024 wtki (o ile stosowany sprzt poradzi sobie z tak liczb). W razie wykrycia zbyt
duej liczby uruchomionych zada (jeli na przykad liczba równolegle realizowanych
zada przekroczy dostpn wspóbieno sprztow) biblioteka moe przej w tryb
synchronicznego uruchamiania nowych zada. Zadania bd wykonywane w wtku
wywoujcym funkcj

get()

, nie w nowym wtku, zatem program uniknie kosztów prze-

kazywania zadania pomidzy wtkami, jeli koszty tej operacji nie s rekompensowane
przez wzrost wydajnoci. Jeli nie przekazano wprost wartoci

std::launch::deferred

,

uruchamianie nowego wtku dla kadego zadania jest w peni zgodne z zaoeniami
implementacji

std::async

(nawet jeli prowadzi do nadsubskrypcji); podobnie jeli

nie przekazano wartoci

std::launch::async

, najlepszym rozwizaniem jest synchro-

niczne wykonywanie wszystkich zada. W przypadku stosowania biblioteki oferujcej
mechanizmy automatycznego skalowania warto sprawdzi w dokumentacji, jak te mecha-
nizmy bd dziaay w kontekcie tego algorytmu.

Zamiast funkcji

std::async()

moglibymy uy wasnej funkcji

spawn_task()

w roli

prostego opakowania szablonu klasy

std::packaged_task

i klasy

std::thread

(patrz

Poleć książkę

Kup książkę

background image

126

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

listing 4.14). W takim przypadku naleaoby utworzy obiekt klasy

std::packaged_task

dla wyniku wywoania funkcji, odczyta obiekt przyszoci z obiektu zadania, uruchomi
zadanie w odpowiednim wtku, po czym zwróci obiekt przyszoci. Takie rozwiza-
nie samo w sobie nie przyniosoby co prawda adnych korzyci (prowadzioby raczej
do duej nadsubskrypcji), ale moe stanowi punkt wyjcia dla bardziej zaawansowa-
nych implementacji, które bd dodaway zadania do kolejki w celu przetworzenia
przez wtki robocze dostpne w puli. Zagadnienia zwizane z pulami wtków zostan
omówione w rozdziale 9. Wybór tego kierunku (zamiast stosowania funkcji

std::async

)

jest uzasadniony tylko w przypadku programistów, którzy maj pen wiadomo
skutków podejmowanych dziaa i chc mie pen kontrol nad sposobem budowy
puli wtków i wykonywania zada.

Listing 4.14. Prosta implementacja funkcji spawn_task

template<typename F,typename A>
std::future<std::result_of<F(A&&)>::type>
spawn_task(F&& f,A&& a)
{
typedef std::result_of<F(A&&)>::type result_type;
std::packaged_task<result_type(A&&)>
task(std::move(f)));
std::future<result_type> res(task.get_future());
std::thread t(std::move(task),std::move(a));
t.detach();
return res;
}

Wrómy teraz do funkcji

parallel_quick_sort()

. Poniewa do uzyskania listy

new_higher

uylimy bezporedniego wywoania rekurencyjnego, moemy uy funkcji

splice()

tak jak w algorytmie jednowtkowym . Okazuje si jednak, e zmienna

new_lower

zawiera obiekt klasy

std::future<std::list<T>>

, nie list, zatem przed wywoaniem

funkcji

splice()

musimy wywoa funkcj

get()

, aby uzyska odpowiedni warto .

Wywoanie w tej formie czeka na zakoczenie zadania wykonywanego w tle, po czym
przenosi wynik do wywoania funkcji

splice()

. Funkcja

get()

zwraca referencj do

r-wartoci wyniku, zatem lista moe zosta przeniesiona (wicej informacji na temat
referencji do r-wartoci i operacji przenoszenia mona znale w czci A.1.1 dodatku A).

Nawet jeli przyj, e funkcja

std::async()

w optymalny sposób wykorzystuje

dostpn wspóbieno sprztow, proponowana implementacja równolegego algorytmu
sortowania szybkiego wci nie jest optymalna. Funkcja

std::partition

realizuje co

prawda znaczn cz zada zwizanych z dziaaniem tego algorytmu, ale jej wywoanie
ma charakter typowo sekwencyjny. Czytelnicy zainteresowani moliwie najszybsz, rów-
noleg implementacj powinni sign po odpowiedni literatur akademick.

Programowanie funkcyjne nie jest jedynym paradygmatem programowania wspó-

bienego eliminujcym problem wspódzielenia zmiennych danych; innym przykadem
takiego paradygmatu jest komunikacja procesów sekwencyjnych (ang. Communicating
Sequential Processes
CSP)

3

, gdzie wtki s w zaoeniu cakowicie niezalene i nie

3

C.A.R. Hoare, Communicating Sequential Processes, Prentice Hall, 1985. Ksika jest dostpna za darmo
pod adresem http://www.usingcsp.com/cspbook.pdf.

Poleć książkę

Kup książkę

background image

4.4.

Upraszczanie kodu za pomoc technik synchronizowania operacji

127

operuj na wspódzielonych danych — zamiast tego wymieniaj komunikaty za pored-
nictwem kanaów komunikacyjnych. Paradygmat CSP zastosowano w jzyku progra-
mowania Erlang (http://www.erlang.org/) oraz w rodowisku MPI (od ang. Message
Passing Interface
) stosowanym w systemach implementowanych w jzykach C i C++,
które musz gwarantowa najwysz wydajno (http://www.mpi-forum.org/). Po tym,
co ju napisaem, jestem pewien, e wiadomo o moliwoci implementacji tego para-
dygmatu take w jzyku C++ nie bdzie dla czytelnika adnym zaskoczeniem — wystar-
czy odrobina dyscypliny. Sposób implementacji tego modelu omówi w nastpnym
punkcie.

4.4.2.

Synchronizacja operacji za pomoc przesyania komunikatów

Koncepcja paradygmatu CSP jest prosta — nie istniej adne wspódzielone dane,
a kady wtek mona traktowa jako zupenie niezaleny byt. Zachowanie wtku zaley
wycznie od komunikatów, które do niego trafiaj. Kady wtek jest wic swoist
maszyn stanów, która po otrzymaniu komunikatu aktualizuje swój stan i która moe
(ale nie musi) wysa co najmniej jeden komunikat do pozostaych wtków. Sposób prze-
twarzania komunikatu zaley od stanu pocztkowego „maszyny”. Jednym ze sposobów
pisania wtków tego typu jest stworzenie formalnego modelu i implementacja sko-
czonej maszyny stanów, jednak istniej te lepsze rozwizania — do wyraenia maszyny
stanów mona uy odpowiedniej struktury aplikacji. To, która metoda sprawdza si
lepiej w danym scenariuszu, zaley od szczegóowych wymaga dotyczcych zachowa
budowanego systemu i od umiejtnoci zespou programistów. Jeli jednak zdecydu-
jemy si na implementacj odrbnych wtków, sam podzia na niezalene procesy
moe prowadzi do wyeliminowania wielu komplikacji zwizanych ze wspóbienym
przetwarzaniem danych wspódzielonych i tym samym uatwi programowanie oraz
ograniczy liczb bdów.

Procesy w peni zgodne z paradygmatem CSP nie operuj na adnych wspódzie-

lonych danych, a caa komunikacja odbywa si za porednictwem kolejek komunikatów.
Poniewa jednak wtki jzyka C++ wspódziel przestrze adresow, wymuszenie
tego wymagania jest niemoliwe. W tej sytuacji bardzo due znaczenie ma dyscyplina
autorów aplikacji i bibliotek, poniewa to od nas zaley, czy nasze wtki bd si odwo-
ywa do wspódzielonych danych. Same kolejki komunikatów oczywicie musz by
wspódzielone (w przeciwnym razie wtki nie mogyby si komunikowa), jednak szcze-
góy implementacji tych kolejek mona opakowa w ramach bibliotek.

Wyobramy sobie, e implementujemy kod dla bankomatu. Kod tego systemu musi

obsugiwa interakcj z uytkownikiem, czyli osob wypacajc gotówk, musi komu-
nikowa si z systemem odpowiedniego banku oraz musi sterowa fizycznymi urz-
dzeniami odpowiedzialnymi za akceptacj karty, wywietlanie stosownych komunika-
tów, obsug klawiatury, wypat pienidzy i zwracanie karty.

Jednym ze sposobów obsugi wszystkich tych zada jest podzielenie kodu na trzy

niezalene wtki: jeden obsugujcy fizyczne urzdzenia, drugi implementujcy logik
samego bankomatu i trzeci odpowiedzialny za komunikacj z bankiem. Wtki mog si
komunikowa wycznie poprzez przekazywanie komunikatów (nie poprzez wspó-
dzielenie jakichkolwiek danych). Na przykad wtek obsugujcy fizyczne urzdzenia
mógby wysa do wtku logiki bankomatu komunikat o woeniu karty lub naciniciu

Poleć książkę

Kup książkę

background image

128

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

przycisku przez uytkownika, natomiast wtek logiki mógby wysa do wtku obsu-
gujcego fizyczne urzdzenia komunikat okrelajcy kwot do wypacenia.

Jednym ze sposobów modelowania logiki bankomatu jest opracowanie maszyny

stanów. W kadym stanie wtek oczekuje na okrelony komunikat, który jest nastp-
nie odpowiednio przetwarzany. W wyniku przetwarzania tego komunikatu wtek moe
przej w nowy stan i kontynuowa cay cykl. Stany skadajce si na t prost imple-
mentacj pokazano na rysunku 4.3. W tej uproszczonej implementacji system oczekuje
na umieszczenie karty w bankomacie. Po woeniu karty system czeka, a uytkownik
wpisze kod PIN, naciskajc kolejno cyfry tego kodu. Uytkownik moe usun ostat-
ni wpisan cyfr. Po wpisaniu odpowiedniej liczby cyfr system weryfikuje kod PIN.
Jeli PIN jest nieprawidowy, cykl dziaania koczy si — bankomat zwraca kart i prze-
chodzi w stan oczekiwania na wsunicie karty przez klienta. Jeli kod PIN jest prawi-
dowy, system czeka na anulowanie transakcji albo na wybór kwoty do wypacenia.
W razie anulowania transakcji cykl pracy bankomatu koczy si i urzdzenie zwraca
kart. Jeli klient wybra kwot, przed wypaceniem gotówki system czeka na potwier-
dzenie ze strony banku, po czym albo wypaca gotówk, albo wywietla komunikat
„brak rodków” i (niezalenie od wyniku weryfikacji stanu konta) wysuwa kart. Sys-
temy prawdziwych bankomatów s oczywicie bardziej skomplikowane, jednak opisana
powyej maszyna stanów dobrze ilustruje istot tego rozwizania.

Rysunek 4.3.

Prosty model maszyny stanów dla bankomatu

Po zaprojektowaniu maszyny stanów dla logiki bankomatu moemy przystpi do imple-
mentacji tego rozwizania w formie klasy, która bdzie definiowaa po jednej funkcji
skadowej dla kadego stanu. Kada funkcja skadowa moe czeka na okrelony zbiór
komunikatów przychodzcych i odpowiednio obsugiwa te komunikaty (obsuga moe
polega na przechodzeniu do innego stanu). Kady typ komunikatów jest reprezentowany

Poleć książkę

Kup książkę

background image

4.4.

Upraszczanie kodu za pomoc technik synchronizowania operacji

129

przez odrbn struktur. Na listingu 4.15 pokazano fragment prostej implementacji
logiki takiego systemu, w tym gówn ptl oraz implementacj pierwszego stanu, w któ-
rym system oczekuje na woenie karty.

Listing 4.15. Prosta implementacja klasy logiki systemu bankomatu

struct card_inserted
{
std::string account;
};
class atm
{
messaging::receiver incoming;
messaging::sender bank;
messaging::sender interface_hardware;
void (atm::*state)();

std::string account;
std::string pin;

void waiting_for_card()
{
interface_hardware.send(display_enter_card());
incoming.wait()
.handle<card_inserted>(
[&](card_inserted const& msg)
{
account=msg.account;
pin="";
interface_hardware.send(display_enter_pin());
state=&atm::getting_pin;
}
);
}
void getting_pin();
public:
void run()
{
state=&atm::waiting_for_card;
try
{
for(;;)
{
(this->*state)();
}
}
catch(messaging::close_queue const&)
{
}
}
};

Jak wida, wszystkie niezbdne operacje zwizane z synchronizacj przekazywania
komunikatów zostay ukryte w odpowiedniej bibliotece (implementacja tej biblioteki
zostanie pokazana w dodatku C wraz z kompletnym kodem tego przykadu).

Poleć książkę

Kup książkę

background image

130

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

Jak ju wspomniaem, opisana tutaj implementacja jest mocno uproszczona w sto-

sunku do logiki obowizujcej w prawdziwych bankomatach, jednak przykad w tej
formie wystarczy do zrozumienia stylu programowania na bazie przekazywania komu-
nikatów. Nie musimy traci czasu na projektowanie synchronizacji i rozwizywanie
problemów zwizanych z przetwarzaniem wspóbienym — wystarczy ustali, jakie
komunikaty mog by odbierane i przetwarzane na poszczególnych etapach oraz które
komunikaty naley wysya. Maszyna stanów logiki bankomatu jest przetwarzana przez
jeden wtek; pozostae elementy systemu, jak interfejs czcy si z bankiem czy interfejs
terminala, s obsugiwane przez odrbne wtki. Ten styl projektowania oprogramowania
okrela si mianem modelu aktorów — w systemie istnieje wiele odrbnych aktorów
(kady dziaa w osobnym wtku), które wymieniaj pomidzy sob komunikaty niezbdne
do realizacji swoich zada. W modelu aktorów nie istnieje wspódzielony stan (wyjtkiem
jest mechanizm potrzebny do bezporedniego przekazywania komunikatów).

Dziaanie programu rozpoczyna si od funkcji skadowej

run()

, która ustawia

stan pocztkowy, czyli

waiting_for_card

, po czym wielokrotnie wywouje funkcj

skadow reprezentujc biecy stan (niezalenie od tego, który to stan). Funkcje
stanów maj posta prostych funkcji skadowych klasy

atm

. Take funkcja stanu

waiting_for_card

jest do prosta — jej dziaanie ogranicza si do wysania komu-

nikatu do interfejsu w celu wywietlenia na ekranie tekstu Czekam na kart ; zaraz
potem funkcja rozpoczyna oczekiwanie na komunikat do obsuenia . Jedynym rodza-
jem komunikatów, który moe by obsugiwany w tej czci kodu, jest komunikat

card_inserted

. Do jego obsugi uywamy funkcji lambda . Na wejciu funkcji

handle

mona przekaza dowoln funkcj lub dowolny obiekt funkcji, jednak najprostszym
rozwizaniem jest uycie funkcji lambda. atwo zauway, e wywoanie funkcji

handle()

znalazo si w acuchu obejmujcym wywoanie funkcji

wait()

, zatem w razie otrzy-

mania komunikatu, który nie pasuje do wskazanego typu, wtek zignoruje ten komu-
nikat i bdzie dalej czeka na komunikat waciwego typu.

Sama funkcja lambda zapisuje numer konta w zmiennej skadowej, zeruje biecy

kod PIN, wysya komunikat do sprztu odpowiedzialnego za obsug interfejsu ban-
komatu, aby wywietli prob o podanie kodu PIN, po czym przechodzi w stan po-
bierania tego kodu. Po zakoczeniu dziaania przez funkcj obsugujc komunikat
funkcja stanu zwraca sterowanie, a gówna ptla programu wywouje funkcj nowego
stanu .

Funkcja stanu

getting_pin

jest nieco bardziej skomplikowana, poniewa moe obsu-

giwa trzy róne typy komunikatów (patrz rysunek 4.3). Kod tej funkcji pokazano na
listingu 4.16.

Listing 4.16. Funkcja stanu getting_pin na potrzeby prostej implementacji systemu
bankomatu

void atm::getting_pin()
{
incoming.wait()
.handle<digit_pressed>(
[&](digit_pressed const& msg)
{
unsigned const pin_length=4;
pin+=msg.digit;
if(pin.length()==pin_length)

Poleć książkę

Kup książkę

background image

4.5.

Podsumowanie

131

{
bank.send(verify_pin(account,pin,incoming));
state=&atm::verifying_pin;
}
}
)
.handle<clear_last_pressed>(
[&](clear_last_pressed const& msg)
{
if(!pin.empty())
{
pin.resize(pin.length()-1);
}
}
)
.handle<cancel_pressed>(
[&](cancel_pressed const& msg)
{
state=&atm::done_processing;
}
);
}

Tym razem funkcja musi przetwarza trzy róne typy komunikatów, zatem acuch
wywoania funkcji

wait()

obejmuje a trzy wywoania funkcji

handle()

. Kade

wywoanie funkcji

handle()

okrela typ komunikatu w formie parametru szablonu, po

czym przekazuje funkcj lambda, która otrzymuje na wejciu komunikat okrelonego
typu. Poniewa wszystkie te wywoania umieszczono w jednym acuchu wywoa,
implementacja funkcji

wait()

„wie”, e czeka na komunikat

digit_pressed

,

clear_

´

last_pressed

lub

cancel_pressed

. Komunikaty wszystkich innych typów bd (tak

jak wczeniej) ignorowane.

W tym przypadku otrzymanie komunikatu nie musi prowadzi do zmiany stanu.

Jeli na przykad wtek otrzyma komunikat

digit_pressed

i jeli wpisana cyfra nie bdzie

ostatni cyfr kodu, wystarczy t cyfr dopisa do acucha

pin

. Gówna ptla na

listingu 4.15 ponownie wywoa funkcj

getting_pin()

, aby czeka na nastpn cyfr

(bd wyzerowa kod PIN lub anulowa ca operacj).

Opisana procedura jest zgodna ze schematem pokazanym na rysunku 4.3. Kady

stan przedstawiony na tym rysunku jest implementowany przez inn funkcj skadow,
która czeka na odpowiednie komunikaty i na tej podstawie aktualizuje stan systemu.

Jak wida, opisany styl programowania moe znacznie uproci zadanie projekto-

wania systemu wspóbienego, poniewa kady wtek mona traktowa cakowicie
niezalenie od pozostaych. W opisanym modelu wiele wtków ma za zadanie oddzie-
lanie zagadnie i jako takie wymagaj od projektanta jasnych decyzji o podziale zada
pomidzy wtki.

4.5.

Podsumowanie

Synchronizacja operacji pomidzy wtkami jest wanym aspektem pisania aplikacji
stosujcej techniki przetwarzania wspóbienego — w razie braku synchronizacji wtki
dziaayby cakowicie niezalenie, zatem równie dobrze mogyby mie posta odrbnych
aplikacji uruchamianych w formie pewnej grupy (z racji pokrewnych zada). W tym

Poleć książkę

Kup książkę

background image

132

R

OZDZIA

4.

Synchronizacja wspóbienych operacji

rozdziale omówiem rozmaite sposoby synchronizacji operacji, w tym podstawowe
zmienne warunkowe, przyszoci, obietnice i opakowywane zadania. Opisaem te spo-
soby rozwizywania problemów zwizanych z synchronizacj, w szczególnoci pro-
gramowanie funkcyjne, gdzie kade zadanie generuje wynik wycznie na podstawie
danych wejciowych (nie uwzgldnia zewntrznego rodowiska), oraz przekazywanie
komunikatów, gdzie komunikacja pomidzy wtkami odbywa si za porednictwem
asynchronicznych komunikatów (wysyanych przy uyciu podsystemu przekazywania
komunikatów).

Skoro omówiem ju wiele wysokopoziomowych rozwiza dostpnych w jzyku

C++, czas przyjrze si odpowiednim elementom niskopoziomowym, dziki którym
opisane mechanizmy mog funkcjonowa — w nastpnym rozdziale skoncentrujemy si
na modelu pamici jzyka C++ i operacjach atomowych.

Poleć książkę

Kup książkę

background image

Skorowidz

A

accumulate_block, 293, 294
add_to_list(), 61
add_to_reclaim_list(), 239
aktywne oczekiwanie, 261
algorytm sortowania szybkiego, 330
analiza kodu, 357

próba szczegóowego wyjanienia komu, 358
przegldanie kodu, 357
pytania dotyczce przegldanego kodu, 358

asynchroniczne zadanie, 104

B

bariera, 316
bariery pamici, Patrz ogrodzenia
biblioteki jzyka C++, 29

ACE, 29
Boost, 29
Boost Thread Library, 30
C++ Thread Library, 30
efektywno klas, 30
mechanizm przyszoci, 103
okres, 117
przyszoci unikatowe, 103
przyszoci wspódzielone, 103
punkt w czasie, 118
RAII, 29
standardowa, 31
typy wywoywalne, 36

wolne funkcje, 150
zegar, 115

blokady wirujce, 221
bdzenie, Patrz uwizienie
Boost Thread Library, 30
buffer, 44

C

C++ Thread Library, 30
clear(), 138, 141
compare_exchange_strong(), 140, 144, 236, 248,

263

compare_exchange_weak(), 140, 144, 225, 247

D

data.push(), 188
data_cond.notify_one(), 191
definicja klasy stosu, 68
delete_nodes_with_no_hazards(), 238, 240
detach(), 38, 42
dispatch(), 405
do_something(), 63
do_sort(), 275, 333
done(), 110
Double-Checked Locking, 85
drzewo binarne, 209
dyndajcy wskanik, 226

Poleć książkę

Kup książkę

background image

564

Skorowidz

E

empty(), 64, 102, 188
exchange(), 140, 143

F

faszywe wspódzielenie, 284, 287
fetch_add(), 140, 146, 249
fetch_and(), 147
fetch_or(), 140, 147
fetch_sub(), 146, 176
fetch_xor(), 147
find_entry_for(), 212
find_first_if(), 217
for_each(), 213, 216
frameworki aplikacji, 29

MFC, 29

free_external_counter(), 260
front(), 98
funkcja lambda, 122
funkcja pocztkowa, 33
funkcje

accumulate_block, 293, 294
add_to_list(), 61
add_to_reclaim_list(), 239
clear(), 138, 141
compare_exchange_strong(), 140, 144, 236,

248, 263

compare_exchange_weak(), 140, 144, 225, 247
constexpr, 381

wymagania, 385

data.push(), 188
data_cond.notify_one(), 191
delete_nodes_with_no_hazards(), 238, 240
detach(), 38, 42
dispatch(), 405
do_something(), 63
do_sort(), 275, 333
domylne, 377

dokumentacja, 378
wymuszanie generowania funkcji, 378
wymuszenie deklarowania konstruktora

kopiujcego, 378

wymuszenie generowania destruktora

wirtualnego, 378

zmiana dostpnoci funkcji, 378

done(), 110
empty(), 64, 102, 188
exchange(), 140, 143
fetch_add(), 140, 146, 249

fetch_and(), 147
fetch_or(), 140, 147
fetch_sub(), 146, 176
fetch_xor(), 147
find_entry_for(), 212
find_first_if(), 217
foo<int&>(), 375
for_each(), 213, 216
free_external_counter(), 260
front(), 98
get(), 125
get_event(), 301
get_future(), 106, 114
get_hazard_pointer_for_current_thread(), 234,

236

get_id(), 52
get_lock(), 80
get_tail(), 200
getting_pin(), 130
handle(), 130, 407
head.get(), 197
hello(), 33
interrupt(), 340, 342, 349
interruptible_wait(), 343, 348
interruption_point(), 341, 344, 351
is_lock_free(), 138
joinable(), 295
lambda, 386

wyraenie lambda, 386
z konstrukcj rozpoczynajc, 388

list_contains(), 61
load(), 140, 143
lock(), 60, 79, 80, 142
main(), 33, 36
memcmp(), 148
memcpy(), 148
my_thread, 37
my_x.do_lengthy_work(), 45
native_handle(), 32
nieskadowe, 150
notify_one(), 96
now(), 116
open_connection(), 87
parallel_accumulate(), 291, 296, 329
parallel_quick_sort(), 126, 275
pocztkowa, 33
pop(), 64, 188, 226, 228, 235, 245, 247, 254,

257, 261

pop_head(), 205
pop_task_from_other_thread_queue(), 339
process(), 82, 301

Poleć książkę

Kup książkę

background image

Skorowidz

565

process_connections(), 110
process_data(), 81
push(), 64, 100, 191, 197, 201, 225, 229, 247,

254, 255, 261, 337

push_front(), 216
reclaim_later(), 236, 238, 239
remove_if(), 217
run(), 130
run_pending_task(), 331, 335
send_data(), 87
sequential_quick_sort(), 124
set(), 343
set_condition_variable(), 344
set_exception(), 111
set_new_tail(), 264
share(), 114
size(), 64
sleep_for(), 120
sleep_until(), 120
some_function, 47
spawn_task(), 125
splice(), 124
square_root(), 111
std::accumulate, 49
std::async(), 104, 125, 273, 281, 297
std::atomic_compare_exchange_strong, 469
std::atomic_compare_exchange_strong_explicit,

469

std::atomic_compare_exchange_weak, 470
std::atomic_compare_exchange_weak_explicit,

471

std::atomic_exchange, 467
std::atomic_exchange_explicit, 467
std::atomic_fetch_add, 476, 486
std::atomic_fetch_add_explicit, 476, 486
std::atomic_fetch_and, 478
std::atomic_fetch_and_explicit, 479
std::atomic_fetch_or, 479
std::atomic_fetch_or_explicit, 480
std::atomic_fetch_sub, 477, 487
std::atomic_fetch_sub_explicit, 478, 487
std::atomic_fetch_xor, 480
std::atomic_fetch_xor_explicit, 481
std::atomic_flag_clear, 459
std::atomic_flag_clear_explicit, 460
std::atomic_flag_test_and_set, 459
std::atomic_flag_test_and_set_explicit, 459
std::atomic_flag::clear, 459
std::atomic_flag::test_and_set, 458
std::atomic_init, 463
std::atomic_is_lock_free, 464

std::atomic_load, 465
std::atomic_load_explicit, 465
std::atomic_signal_fence(), 457
std::atomic_store, 466
std::atomic_store_explicit, 466
std::atomic_thread_fence(), 456
std::atomic<t*>::fetch_add, 486
std::atomic<t*>::fetch_sub, 487
std::atomic<typ-

cakowitoliczbowy>::fetch_add, 476

std::atomic<typ-

cakowitoliczbowy>::fetch_and, 478

std::atomic<typ-cakowitoliczbowy>::fetch_or,

479

std::atomic<typ-

cakowitoliczbowy>::fetch_sub, 477

std::atomic<typ-

cakowitoliczbowy>::fetch_xor, 480

std::atomic::compare_exchange_strong, 468
std::atomic::compare_exchange_weak, 469
std::atomic::exchange, 467
std::atomic::is_lock_free, 464
std::atomic::load, 464
std::atomic::store, 466
std::bind(), 45, 333
std::call_once, 86
std::chrono::duration_cast, 428
std::chrono::duration::count, 423
std::chrono::duration::max, 426
std::chrono::duration::min, 426
std::chrono::duration::zero, 425
std::chrono::steady_clock::now, 434
std::chrono::system_clock::from_time_t, 433
std::chrono::system_clock::now, 432
std::chrono::system_clock::to_time_t, 433
std::chrono::time_point::max, 431
std::chrono::time_point::min, 431
std::chrono::time_point::time_since_epoch, 430
std::condition_variable_any::notify_all, 446
std::condition_variable_any::notify_one, 446
std::condition_variable_any::wait, 447
std::condition_variable_any::wait_for, 448
std::condition_variable_any::wait_until, 450
std::condition_variable::notify_all, 437
std::condition_variable::notify_one, 437
std::condition_variable::wait, 344, 438
std::condition_variable::wait_for, 439
std::condition_variable::wait_until, 441
std::copy_exception(), 112
std::current_exception(), 112
std::find, 306

Poleć książkę

Kup książkę

background image

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ę

background image

Skorowidz

567

G

get(), 125
get_event(), 301
get_future(), 106, 114
get_hazard_pointer_for_current_thread(), 234, 236
get_id(), 52
get_lock(), 80
get_tail(), 200
getting_pin(), 130

H

handle(), 130, 407
head.get(), 197
hello(), 33

I

identyfikowanie wtków, 52

identyfikatory wtków, 52

interrupt(), 340, 342, 349
interruptible_wait(), 343, 348
interruption_point(), 341, 344, 351
is_lock_free(), 138
iteratory jednokrotnego przebiegu, 52
iteratory postpujce, 52

J

jzyk C++, 19

automatyczne okrelanie typu zmiennej, 395
biblioteka operacji atomowych, 31
biblioteka standardowa, 31
biblioteka wtków, 30
biblioteki, 29
efektywno klas, 30
frameworki aplikacji, 29
mechanizm deklarowania funkcji

jako usunitej, 376

mechanizm przyszoci, 103
miejsce w pamici, 134
model pamici, 133
muteks, 60
obiekty, 134
obsuga wspóbienoci, 28, 30
operacje atomowe, 137
porzdek modyfikacji, 136
RAII, 29
referencje do r-wartoci, 371

semantyka przenoszenia danych, 372

szablony zmiennoargumentowe, 391

paczka parametrów, 392
rozwinicie paczki, 392

typy definiowane przez uytkownika, 382

inicjalizacja statyczna, 384

warstwy abstrakcji, 30
wyraenia stae, 381

zastosowania, 381

wyraenie lambda, 37
wycig danych, 58
zmienne lokalne wtków, 396

join(), 39
joinable(), 295

K

klasy

dispatcher, 404
receiver, 403
scoped_thread, 48
sender, 402
std::thread, 36
std::atomic_flag, 457
std::chrono::high_resolution_clock, 116
std::chrono::steady_clock, 116, 433
std::chrono::system_clock, 116, 431
std::condition_variable, 95, 436
std::condition_variable_any, 95, 444
std::future<>, 103
std::mutex, 60, 515
std::once_flag, 541
std::recursive_mutex, 90, 517
std::recursive_timed_mutex, 524
std::shared_future<>, 103
std::thread, 549
std::thread::id, 550
std::timed_mutex, 520
thread_guard, 48
thread_pool, 331

komunikacja procesów sekwencyjnych, 126, 127

maszyna stanów, 127, 128
model aktorów, 130
model maszyny stanów, 128

konstruktor domylny, 52
konstruktor przenoszcy, 45
kontenery

std::map<>, 207
std::multimap<>, 207
std::queue<>, 97
std::stack, 64, 66
std::unordered_map<>, 207
std::unordered_multimap<>, 207

Poleć książkę

Kup książkę

background image

568

Skorowidz

L

leniwa inicjalizacja, 85
linie pamici podrcznej, 284
list_contains(), 61
load(), 140, 143
lock(), 60, 79, 80, 142
l-warto, 80

M

main(), 33, 36
mechanizm przyszoci, 52, 102, 103

asynchroniczne zadanie, 104
obietnice, 109
oczekiwanie na wiele wtków, 112
przyszoci unikatowe, 103
przyszoci wspódzielone, 103
wizanie zadania z przyszoci, 106
wynik oblicze wykonywanych w tle, 103
wycig danych, 112
zapisywanie wyjtku, 111

memcmp(), 148
memcpy(), 148
model aktorów, 130
model pamici jzyka C++, 133

analiza podstawowych cech strukturalnych,

134

mechanizmy przetwarzania wspóbienego,

134

miejsce w pamici, 134
modele porzdkowania spójnego

niesekwencyjnie, 159

niezdefiniowane zachowanie, 136
obiekty, 134
ogrodzenia, 178
operacje atomowe, 136
podzia struktury, 135
porzdek modyfikacji, 136
porzdkowania pamici, 155
porzdkowanie poprzez wzajemne

wykluczanie, 155, 166

operacje uzyskiwania, 166
operacje zwalniania, 166

porzdkowanie spójne sekwencyjnie, 155, 156
porzdkowanie zagodzone, 155, 160

wyjanienie porzdkowania, 164

relacja poprzedzania, 152, 154

poprzedzanie wedug zalenoci, 173
przechodnio, 170
relacja wprowadzania zalenoci, 173

relacja synchronizacji, 152

sekwencja zwalniania, 175

wycig danych, 136

muteks, 59, 60, 220

blokowanie, 60
blokowanie rekurencyjne, 90
czytelników-pisarzy, 88
elastyczne blokowanie, 79
hierarchiczny, 77
l-warto, 80
niezdefiniowane zachowanie, 90
ochrona listy, 61
odblokowywanie, 60
przenoszenie wasnoci, 80
rekurencyjny, 90
r-warto, 80
stosowanie w jzyku C++, 60
szczegóowo blokady, 82
wirujcy, 142
zakleszczenie, 71

my_thread, 37
my_thread.detach(), 39
my_thread.join(), 39
my_x.do_lengthy_work(), 45

N

nadsubskrypcja, 51, 280, 285
native_handle(), 32
niezdefiniowane zachowanie, 58, 86, 90, 136
niezmienniki, 56, 355
niskie wspózawodnictwo, 282
notify_one(), 96
now(), 116

O

obiekty przyszoci, 122
ochrona wspódzielonych danych, 56

blokowanie rekurencyjne, 90
definicja klasy kolejki, 100, 190
definicja klasy stosu, 68, 187
Double-Checked Locking, 85
elastyczne blokowanie muteksu, 79
hierarchia blokad, 75
implementacja listy z obsug iteracji, 214
implementacja tablicy wyszukiwania, 210
jednowtkowa implementacja kolejki, 195
kolejka z mechanizmami blokowania i

oczekiwania, 203

kolejka ze szczegóowymi blokadami, 198

Poleć książkę

Kup książkę

background image

Skorowidz

569

kolejka ze sztucznym wzem, 196
leniwa inicjalizacja, 85
lista jednokierunkowa, 194
metody zapewniania bezpieczestwa, 185
muteks, 59, 60
muteks czytelników-pisarzy, 88
niezdefiniowane zachowanie, 58
niezmienniki, 56
ochrona listy, 61
pami transakcyjna, 59
programowanie bez blokad, 59
przekazywanie referencji, 66
przenoszenie wasnoci muteksu, 80
stosowanie konstruktora, 67
struktury danych bez blokad, 220
sytuacja wycigu, 58
szczegóowo blokady, 82
szeregowanie, 185
tablica wyszukiwania, 207
unikanie zakleszcze, 71
wykrywanie sytuacji wycigu, 63
zakleszczenie, 71
zwracanie wskanika, 67

ogrodzenia, 178
open_connection(), 87
operacje atomowe, 136, 137

funkcje nieskadowe, 150
gówny szablon, 147
modele porzdkowania spójnego

niesekwencyjnie, 159

ogrodzenia, 178
operacje dostpne dla typów atomowych, 149
operacje adowania (odczytu), 140, 143
operacje odczyt-modyfikacja-zapis, 140, 141, 143,
operacje porównania-wymiany, 144
operacje wymiany i dodania, 146
operacje zapisu, 140, 141, 143
porównywanie bitowe, 148
porzdkowanie pamici, 155
porzdkowanie poprzez wzajemne

wykluczanie, 155, 166

operacje uzyskiwania, 166
operacje zwalniania, 166

porzdkowanie spójne sekwencyjnie, 155, 156
porzdkowanie zagodzone, 155, 160

wyjanienie porzdkowania, 164

pozorny bd, 144
relacja poprzedzania, 152, 154

poprzedzanie wedug zalenoci, 173
przechodnio, 170
relacja wprowadzania zalenoci, 173

relacja synchronizacji, 152

sekwencja zwalniania, 175

rozkazy porównywania i wymiany podwójnego

sowa, 149

sekwencja zwalniania zasobów, 147
standardowe definicje typów atomowych, 139
standardowe typy atomowe, 138
stos bez blokad, 250
tworzenie typów niestandardowych, 147
wolne funkcje, 150

operator przypisania z przenoszeniem, 45

P

pami transakcyjna, 59
paradygmat CSP, Patrz komunikacja procesów

sekwencyjnych

parallel_accumulate(), 291, 296, 329
parallel_quick_sort(), 126, 275
ping-pong buforów, 282
podzia zagadnie, 25
pop(), 64, 188, 226, 228, 235, 245, 247, 254, 257,

261

pop_head(), 205
pop_task_from_other_thread_queue(), 339
porównywanie bitowe, 148
potok, 278
pozorne budzenie, 97
prawo Amdahla, 299
problem ABA, 266
process(), 82, 301
process_connections(), 110
process_data(), 81
procesy demonów, 42
programowanie bez blokad, 59
programowanie funkcyjne, 122

algorytm sortowania szybkiego, 122
funkcja lambda, 122
obiekty przyszoci, 122
rekurencyjne sortowanie, 123
równolege sortowanie szybkie, 125
wnioskowanie typów zmiennych, 122

projektowanie uniwersalnej kolejki, 97
projektowanie wspóbienego kodu, 269

bezpieczestwo wyjtków, 291, 293, 297

algorytmy równolege, 291

czynniki wpywajce na wydajno kodu, 279

faszywe wspódzielenie, 284
liczba procesorów, 280
nadsubskrypcja, 280, 285
niskie wspózawodnictwo, 282

Poleć książkę

Kup książkę

background image

570

Skorowidz

projektowanie wspóbienego kodu

ping–pong buforów, 282
przeczanie zada, 285
wspózawodnictwo o dane, 281
wybór najlepszego algorytmu, 281
wysokie wspózawodnictwo, 282
zmiana elementu danych, 280

faszywe wspódzielenie, 287
atwo testowania, 361

eliminacja wspóbienoci, 362
warunki struktury kodu, 361

mnoenie macierzy, 287
podzia elementów tablicy, 287
potok, 278
praktyka, 303

bariera, 316
implementacja równolegego algorytmu

wyszukiwania, 307

równolega implementacja funkcji

partial_sum, 319

równolega wersja funkcji std::for_each, 304
równolege obliczanie sum czciowych, 313

prawo Amdahla, 299
pula wtków, 276
ssiedztwo danych, 287
skalowalno, 291, 298
techniki dzielenia pracy pomidzy wtki, 270

dzielenie przed rozpoczciem przetwarzania,

271

dzielenie sekwencji zada, 278
dzielenie wedug typu zadania, 276
podzia ssiadujcych fragmentów danych,

272

rekurencyjne dzielenie danych, 272, 273
równolegy algorytm sortowania szybkiego,

273

sposób izolowania zagadnie, 277

techniki przetwarzania równolegego, 301
ukrywanie opónie, 300
wspózawodnictwo, 286
wzorce dostpu do danych, 289

przekazywanie argumentów do funkcji wtku, 43

konstruktor przenoszcy, 45
kopiowane, 43
operator przypisania z przenoszeniem, 45
przenoszenie, 45

przeczanie kontekstu, 21
przeczanie zada, 21, 22
przenoszenie wasnoci wtku, 46, 47
przetwarzanie wspóbiene, 29

bezpieczestwo, 184

definicja klasy kolejki, 190
definicja klasy stosu, 68
implementacja listy z obsug iteracji, 214
implementacja tablicy wyszukiwania, 210
kolejka z mechanizmami blokowania i

oczekiwania, 203

kolejka ze szczegóowymi blokadami, 198
mechanizmy przyszoci, 102
midzywtkowa relacja poprzedzania, 155
niechciane blokowanie, 354

oczekiwanie na zewntrzne dane wejciowe,

355

uwizienie, 354
zakleszczenie, 354

oczekiwanie na zdarzenie, 94
stos bez blokad, 227, 250
synchronizacja operacji, 93
sytuacje wycigu, 355

naruszone niezmienniki, 355
problemy zwizane z czasem ycia, 356
wycig danych, 355

tablica mieszajca, 209
tablica wyszukiwania, 207
techniki lokalizacji bdów, 357

analiza kodu, 357
próba szczegóowego wyjanienia komu, 358
pytania dotyczce przegldanego kodu, 358
testowanie wspóbienego kodu, 359

wspódzielenie danych przez wtki, 55
wywoanie blokujce z limitem czasowym, 115
zarzdzanie wtkami, 36

identyfikowanie wtków, 52
mechanizm przyszoci, 52
oczekiwanie na zakoczenie wtku, 39
oczekiwanie w razie wystpienia wyjtku, 39
odczenie wtku, 41
przekazywanie argumentów do funkcji wtku,

43

przenoszenie wasnoci wtku, 46
uruchamianie wtków w tle, 42
uruchamianie wtku, 36
wtki demonów, 42
wybór liczby wtków, 49

zmienna warunkowa, 95

pula wtków, 106, 276, 324

wizanie zadania z przyszoci, 106

push(), 64, 100, 191, 197, 201, 225, 229, 247, 254,

255, 261, 337

push_front(), 216

Poleć książkę

Kup książkę

background image

Skorowidz

571

R

RAII, 29
reclaim_later(), 236, 238, 239
referencje do r-wartoci, 371

semantyka przenoszenia danych, 372

konstruktor kopiujcy, 374
konstruktor przenoszcy, 374

relacja poprzedzania, 154

poprzedzanie wedug zalenoci, 173
przechodnio, 170
relacja wprowadzania zalenoci, 173

relacja synchronizacji, 152

sekwencja zwalniania, 175

remove_if(), 217
Resource Acquisition Is Initialization, Patrz RAII
RIAA, 40
rozkazy porównywania i wymiany podwójnego

sowa, 149

równolego, Patrz zrównoleglanie zada
równolego danych, 26
run(), 130
run_pending_task(), 331, 335
r-warto, 80

S

ssiedztwo danych, 287
scoped_thread, 48
sekwencja zwalniania, 175
send_data(), 87
sequential_quick_sort(), 124
set(), 343
set_condition_variable(), 344
set_exception(), 111
set_new_tail(), 264
share(), 114
size(), 64
skalowalno, 298, 369
sleep_for(), 120
sleep_until(), 120
some_function, 47
spawn_task(), 125
splice(), 124
square_root(), 111
std::accumulate, 49
std::async, 104, 125, 273, 281, 297, 513
std::atomic, 138, 140, 147, 460
std::atomic_compare_exchange_strong, 469
std::atomic_compare_exchange_strong_explicit,

469

std::atomic_compare_exchange_weak, 470
std::atomic_compare_exchange_weak_explicit, 471
std::atomic_exchange, 467
std::atomic_exchange_explicit, 467
std::atomic_fetch_add, 476, 486
std::atomic_fetch_add_explicit, 476, 486
std::atomic_fetch_and, 478
std::atomic_fetch_and_explicit, 479
std::atomic_fetch_or, 479
std::atomic_fetch_or_explicit, 480
std::atomic_fetch_sub, 477, 487
std::atomic_fetch_sub_explicit, 478, 487
std::atomic_fetch_xor, 480
std::atomic_fetch_xor_explicit, 481
std::atomic_flag, 138, 141, 457
std::atomic_flag_clear, 459
std::atomic_flag_clear_explicit, 460
std::atomic_flag_test_and_set, 459
std::atomic_flag_test_and_set_explicit, 459
std::atomic_flag::clear, 459
std::atomic_flag::test_and_set, 458
std::atomic_init, 463
std::atomic_is_lock_free, 464
std::atomic_load, 465
std::atomic_load_explicit, 465
std::atomic_signal_fence(), 457
std::atomic_store, 466
std::atomic_store_explicit, 466
std::atomic_thread_fence(), 456
std::atomic<bool>, 143
std::atomic<int>, 147
std::atomic<T*>, 146
std::atomic<t*>::fetch_add, 486
std::atomic<t*>::fetch_sub, 487
std::atomic<typ-cakowitoliczbowy>::fetch_add,

476

std::atomic<typ-cakowitoliczbowy>::fetch_and,

478

std::atomic<typ-cakowitoliczbowy>::fetch_or,

479

std::atomic<typ-cakowitoliczbowy>::fetch_sub,

477

std::atomic<typ-cakowitoliczbowy>::fetch_xor,

480

std::atomic<unsigned long long>, 147
std::atomic::compare_exchange_strong, 468
std::atomic::compare_exchange_weak, 469
std::atomic::exchange, 467
std::atomic::is_lock_free, 464
std::atomic::load, 464
std::atomic::store, 466

Poleć książkę

Kup książkę

background image

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ę

background image

Skorowidz

573

std::thread, 43, 549
std::thread::detach, 557
std::thread::get_id, 558
std::thread::hardware_concurrency, 49, 273, 276,

280, 324, 558

std::thread::id, 550
std::thread::join, 557
std::thread::joinable, 556
std::thread::native_handle, 553
std::thread::swap, 556
std::timed_mutex, 520
std::timed_mutex::lock, 521
std::timed_mutex::try_lock, 522
std::timed_mutex::try_lock_for, 522
std::timed_mutex::try_lock_until, 523
std::timed_mutex::unlock, 524
std::try_lock, 541
std::unique_lock, 79, 80, 530
std::unique_lock::lock, 536
std::unique_lock::mutex, 539
std::unique_lock::operator, 539
std::unique_lock::owns_lock, 539
std::unique_lock::release, 539
std::unique_lock::swap, 535, 536
std::unique_lock::try_lock, 536
std::unique_lock::try_lock_for, 537
std::unique_lock::try_lock_until, 538
std::unique_lock::unlock, 537
std::unordered_map<>, 207
std::unordered_multimap<>, 207
store(), 140, 143, 177
submit(), 326, 329, 335
swap(), 64
synchronizacja wspóbienych operacji, 93

definicja klasy kolejki, 100
funkcje otrzymujce limity czasowe, 121
komunikacja procesów sekwencyjnych, 126
mechanizmy przyszoci, 102
obietnice, 109
oczekiwanie na wiele wtków, 112
oczekiwanie na zdarzenie, 94
operacje atomowe, 137
porzdek modyfikacji, 136
pozorne budzenie, 97
programowanie funkcyjne, 122
projektowanie uniwersalnej kolejki, 97
prosta kolejka komunikatów, 401
przekazywanie zada pomidzy wtkami, 107
upraszczanie kodu, 121
wizanie zadania z przyszoci, 106

wynik oblicze wykonywanych w tle, 103
wycig danych, 112
wywoanie blokujce z limitem czasowym, 115
zapisywanie wyjtku na potrzeby przyszoci,

111

zmienna warunkowa, 95

sytuacja wycigu, 58, 355

definicja klasy stosu, 68
przekazywanie referencji, 66
stosowanie konstruktora, 67
zwracanie wskanika, 67

szablon klasy

std::atomic, 138, 140, 147, 460
std::chrono::duration, 117, 420
std::chrono::time_point, 118, 429
std::future, 103, 109, 112, 490
std::lock_guard, 60, 528
std::packaged_task, 106, 391, 501
std::promise, 109, 507
std::ratio, 421, 544
std::ratio_equal, 546
std::ratio_greater, 548
std::ratio_greater_equal, 548
std::ratio_less, 547
std::ratio_less_equal, 548
std::ratio_not_equal, 547
std::shared_future, 103, 113, 495
std::unique_lock, 79, 80, 530
TemplateDispatcher, 405

szczegóowo blokady, 82
szeregowanie, 185

T

tablica mieszajca, 209

kubeek, 209

tablica posortowana, 209
tablica wyszukiwania, 207

operacje, 208

test_and_set(), 138, 141
testowanie wspóbienego kodu, 360

biblioteka podstawowych mechanizmów, 365
czynniki dotyczce rodowiska testowego, 361
projektowanie struktury wielowtkowego kodu

testowego, 366

identyfikacja odrbnych fragmentów

poszczególnych testów, 366

przykad testu dla struktury kolejki, 367

scenariusze testowania kolejki, 360
testowanie symulowanych kombinacji, 364

wady, 365

Poleć książkę

Kup książkę

background image

574

Skorowidz

testowanie wspóbienego kodu

testowanie wydajnoci, 369

skalowalno, 369

testy siowe, 363

wady, 364

thread_a(), 76
thread_b(), 76
thread_guard, 48
thread_pool, 331
time_since_epoch(), 118
top(), 64
try_lock(), 76, 80
try_lock_for(), 120
try_lock_until(), 120
try_pop(), 98, 191, 197, 200, 202, 337
try_reclaim(), 230
try_steal(), 337
try-catch, 40
typy wywoywalne, 36

U

unlock(), 60, 80, 348
update_data_for_widget, 44
uwizienie, 223, 354

V

void(), 106

W

wait(), 96, 102, 318, 344, 348, 403
wait_and_dispatch(), 405, 407
wait_and_pop(), 98, 191, 202, 204
wait_for(), 115, 120, 344
wait_for_data(), 205
wait_until(), 115
warstwy abstrakcji, 30
wtki demonów, 42
wtki sprztowe, 21
wnioskowanie typów zmiennych, 122
worker_thread(), 326, 335
wskaniki ryzyka, 233
wspóbiene struktury danych, 184

aktywne oczekiwanie, 261
algorytmy blokujce, 220
bezpieczestwo przetwarzania

wielowtkowego, 184

blokady wirujce, 221
definicja klasy kolejki, 190
definicja klasy stosu, 187

drzewo binarne, 209
implementacja listy z obsug iteracji, 214
implementacja tablicy wyszukiwania, 210
jednowtkowa implementacja kolejki, 195
kolejka bez blokad, 252

uzyskiwanie nowej referencji, 259
zwalnianie licznika zewntrznego wza, 260
zwalnianie referencji do wza, 258

kolejka nieograniczona, 206
kolejka ograniczona, 206
kolejka z mechanizmami blokowania

i oczekiwania, 203

kolejka ze szczegóowymi blokadami, 198
kolejka ze sztucznym wzem, 196
kolejk z jednym producentem i jednym

konsumentem, 253

lista jednokierunkowa, 194
problem ABA, 266
projektowanie przy uyciu blokad, 186
stos bez blokad, 227, 250
struktury bez blokad, 220, 221

eliminowanie niebezpiecznych wycieków, 228
kolejka, 252
mechanizm odzyskiwania pamici, 230
problem ABA, 266
stos, 227
uwizienie, 223
wskazówki dotyczce pisania struktur, 264
zalety i wady, 222
zarzdzanie pamici, 228
zliczanie referencji, 242
zwalnianie wzów, 229

struktury bez oczekiwania, 222
szeregowanie, 185
tablica mieszajca, 209

kubeek, 209

tablica posortowana, 209
tablica wyszukiwania, 207
wskazówki dotyczce projektowania, 185
wskaniki ryzyka, 233

implementacja funkcji odzyskujcych wzy, 238
strategie odzyskiwania wzów, 240
wykrywanie wzów, 233

wywoania blokujce, 220
zagodzenie, 221
zliczanie referencji, 242

wspóbieno, 20

bezpieczestwo przetwarzania, 184
mechanizm przyszoci, 102
modele, 22
nadsubskrypcja, 280
oczekiwanie na zdarzenie, 94

Poleć książkę

Kup książkę

background image

Skorowidz

575

operacje atomowe, 136, 137
podniesienia wydajnoci, 26
podzia zagadnie, 25
projektowanie struktury danych, 184
przeczanie kontekstu, 21
przeczanie zada, 21, 22
przykad programu, 32
równolego danych, 26
synchronizacja operacji, 93
w jzyku C++, 28
wtki sprztowe, 21
wspóbiene struktury danych, 184
z wieloma procesami, 23
z wieloma wtkami, 24
zarzdzanie wtkami, 36
zmienna warunkowa, 95
zrównoleglanie zada, 26

wspódzielenie danych przez wtki, 55

blokowanie rekurencyjne, 90
definicja klasy stosu, 68
Double-Checked Locking, 85
elastyczne blokowanie muteksu, 79
leniwa inicjalizacja, 85
lista dwukierunkowa, 56
muteks, 59
niezmienniki, 56
ochrona danych za pomoc muteksów, 60
pami transakcyjna, 59
problemy, 56
programowanie bez blokad, 59
przenoszenie wasnoci muteksu, 80
sytuacja wycigu, 58
szczegóowo blokady, 82
wycigu danych, 58
zakleszczenie, 71

wspózawodnictwo, 286
wybór liczby wtków, 49

nadsubskrypcja, 51

wyraenie lambda, 37
wysokie wspózawodnictwo, 282

zwikszenie prawdopodobiestwa, 283

wycig danych, 58, 112, 136, 355

niezdefiniowane zachowanie, 58

wywoanie blokujce z limitem czasowym, 115

funkcje otrzymujce limity czasowe, 121
limity bezwzgldne, 115
maksymalny czas blokowania wtku, 115
okres, 117
punkt w czasie, 118
wymuszanie oczekiwania na podstawie okresu,

117

zastosowanie limitu czasowego, 120
zegar, 115

Z

zaawansowane zarzdzanie wtkami, 323

przerywanie wykonywania wtków, 340

monitorowanie systemu plików w tle, 350
obsuga przerwa, 349
oczekiwanie na zmienn, 343, 346
pozostae wywoania blokujce, 348
przerywanie zada wykonywanych w tle, 350
punkt przerwania, 341
wykrywanie przerwania, 342

pula wtków, 324

algorytm sortowania szybkiego, 330
implementacja algorytmu sortowania

szybkiego, 332

implementacja prostej puli wtków, 325
kolejka umoliwiajca wykradanie zada, 336
lokalne kolejki zada, 334
z mechanizmem oczekiwania na zadanie, 327
z mechanizmem wykradania zada, 337
unikanie wspózawodnictwa w dostpie do

kolejki, 333

wtek roboczy, 324
wykradanie zada, 335

zakleszczenie, 71, 354

hierarchia blokad, 75
unikanie, 71, 73

zasada jednej odpowiedzialnoci, 277
zegar, 115

czasu rzeczywistego, 116
epoka zegara, 118
najkrótszy moliwy takt, 116
okres taktu, 116
stabilny, 116

zegar::now(), 116
zliczanie referencji, 242

licznik wewntrzny, 243
licznik zewntrzny, 243
stos bez blokad, 250
umieszczanie wza na stosie bez blokad, 243
wykrywanie uywanych wzów, 242
zdejmowanie wza ze stosu bez blokad, 245

zmienna warunkowa, 95

definicja klasy kolejki, 100
oczekiwanie na spenienie warunku, 95
pozorne budzenie, 97
projektowanie uniwersalnej kolejki, 97

zrównoleglanie

zada,

26

Poleć książkę

Kup książkę

background image

576

Skorowidz

Poleć książkę

Kup książkę

background image
background image

Wyszukiwarka

Podobne podstrony:
informatyka jezyk c i przetwarzanie wspolbiezne w akcji anthony williams ebook
Jezyk C i przetwarzanie wspolbiezne w akcji
wyklady-pwir, Studia, 6. Semestr, Przetwazanie wspolbiezne
lab5 Przetwarzanie wspolbiezne Nieznany
lab 3 5 Przetwarzanie współbieżne
wyklady-pwir, Studia, 6. Semestr, Przetwazanie wspolbiezne
lab2 Przetwarzanie współbieżne
lab105 Przetwarzanie współbieżne
Przetwarzanie współbieżne
lab1 Przetwarzanie współbieżne
lab5 Przetwarzanie współbieżne
wyklady-pwir, Studia, 6. Semestr, Przetwazanie wspolbiezne
Prezentacja 2 analiza akcji zadania dla studentow
przetworniki indukcyjne
Prop aut W9 Ses cyfr Przetworniki fotoelektryczne
Przetworstwo produktow rolniczych
MLEKO I PRZETWORY MLECZNE (2)

więcej podobnych podstron