Čtení 17: Souběžnosti

#### Software v 6.005

#### cíle + předávání zpráv & sdílená paměť + procesy & vlákna+ Časové krájení+ závodní podmínky## souběžnost * souběžnost * znamená, že se děje více výpočtů současně. Souběžnost je všude v moderním programování, ať se nám to líbí nebo ne:+ Více počítačů v síti+ Více aplikací běží na jednom počítači Více procesorů v počítači (dnes často více procesorových jader na jednom čipu) Ve skutečnosti, souběžnosti, je nezbytné v moderní programování:+ weby musí zvládnout více uživatelů současně.+ Mobilní aplikace je třeba udělat některé z jejich zpracování na serverech (“v cloudu”).+ Grafická uživatelská rozhraní téměř vždy vyžadují práci na pozadí, která uživatele nepřerušuje. Například Eclipse zkompiluje kód Java, zatímco jej stále upravujete.Schopnost programovat se souběžností bude v budoucnu stále důležitá. Rychlost hodin procesoru se již nezvyšuje. Místo toho získáváme více jader s každou novou generací čipů. Takže v budoucnu, abychom dostali výpočet rychleji, budeme muset rozdělit výpočet na souběžné části.## Dva modely pro souběžné Programováníexistují dva běžné modely pro souběžné programování: * sdílená paměť* a * předávání zpráv*.

* * sdílená paměť.** V modelu sdílené paměti souběžnosti souběžné moduly interagují čtením a zápisem sdílených objektů do paměti. Další příklady modelu sdílené paměti: + a A B mohou být dva procesory (nebo procesorová jádra) ve stejném počítači, které sdílejí stejnou fyzickou paměť.+ A A B mohou být dva programy běžící na stejném počítači, které sdílejí společný souborový systém se soubory, které mohou číst a psát.+ A A B mohou být dvě vlákna ve stejném programu Java (vysvětlíme, co je vlákno níže), které sdílejí stejné objekty Java.

* * předávání zpráv.** V modelu předávání zpráv souběžné moduly interagují tím, že si navzájem posílají zprávy prostřednictvím komunikačního kanálu. Moduly odesílají zprávy a příchozí zprávy do každého modulu jsou zařazeny do fronty pro manipulaci. Příklady zahrnují:+ A A B mohou být dva počítače v síti, komunikující síťovými připojeními.+ A a B může být webový prohlížeč a webový server-otevře spojení do B, požádá o webovou stránku, a B posílá data webové stránky zpět do a.+ a a B může být instant messaging klient a server.+ A A B mohou být dva programy běžící na stejném počítači, jejichž vstup a výstup byly spojeny potrubím, jako je “ls | grep” zadaný do příkazového řádku.## Procesy, vlákna, krájení Časumodely předávání zpráv a sdílené paměti jsou o tom, jak souběžné moduly komunikují. Samotné souběžné moduly se dodávají ve dvou různých druzích: procesy a vlákna.**Proces**. Proces je instance běžícího programu, který je *izolován* od ostatních procesů na stejném počítači. Zejména má vlastní soukromou část paměti stroje.Proces abstrakce je *virtuální počítač*. Program má pocit, že má celý stroj pro sebe – jako by byl vytvořen nový počítač s čerstvou pamětí, jen aby spustil tento program.Stejně jako počítače připojené přes síť, procesy mezi nimi obvykle nesdílejí žádnou paměť. Proces nemůže vůbec přistupovat k paměti nebo objektům jiného procesu. Sdílení paměti mezi procesy je *možné* na většině operačního systému, ale vyžaduje zvláštní úsilí. Naopak, nový proces je automaticky připraven pro předávání zpráv, protože je vytvářen s standardní vstup & výstupní proudy, které jsou v Systému.ven ” a “System.in’ proudy, které jste použili v Javě.**Vlákno**. Vlákno je místo kontroly uvnitř běžícího programu. Ber to jako místo v programu, který je spuštěn, plus hromadu volání metod, které vedly k místu, na které bude nutné se vrátit.Stejně jako proces představuje virtuální počítač, abstrakce vlákna představuje *virtuální procesor*. Takže nové vlákno simuluje nový procesor uvnitř virtuálního počítače reprezentován proces. Tento nový virtuální procesor běží stejný program a sdílí stejnou paměť jako ostatní vlákna v procesu.Vlákna jsou automaticky připravena pro sdílenou paměť, protože vlákna sdílejí veškerou paměť v procesu. To vyžaduje zvláštní úsilí, aby si” vlákno-místní ” paměť, která je soukromá do jednoho vlákna. Je také nutné explicitně nastavit předávání zpráv vytvořením a použitím datových struktur fronty. Budeme mluvit o tom, jak to udělat v budoucím čtení.

Jak mohu mít v počítači mnoho souběžných podprocesů pouze s jedním nebo dvěma procesory? Když tam jsou více vláken než procesorů, souběžnost je simulován **krájení**, což znamená, že procesor přepíná mezi závity. Obrázek vpravo ukazuje, jak mohou být tři vlákna T1, T2 a T3 časově krájena na stroji, který má pouze dva skutečné procesory. Na obrázku, čas postupuje dolů, takže nejprve jeden procesor běží vlákno T1 a druhý běží vlákno T2, a pak druhý procesor přepne na spuštění vlákna T3. Vlákno T2 se jednoduše odmlčí, až se příště rozřízne na stejném procesoru nebo jiném procesoru.Na většině systémů se Časové krájení děje nepředvídatelně a nedeterministicky, což znamená, že vlákno může být kdykoli pozastaveno nebo obnoveno.

mitx:c613ec53e92840a4a506f3062c994673 Procesy & Nitky## Sdílené Paměti ExampleLet je podívat se na příklad sdílené paměti systému. Smyslem tohoto příkladu je ukázat, že souběžné programování je těžké, protože může mít jemné chyby.

Představte si, že banka má peníze strojů, které používají sdílená paměť model, takže všechny bankomaty umí číst a psát stejný účet objekty v paměti.Pro ilustraci, co se může pokazit, ať je zjednodušit banka do jednoho účtu, s dolar rovnováhu uloženy v “rovnováha” proměnné, a dvě operace “vložit” a “výběr”, které jednoduše přidat nebo odstranit dolar: “java// předpokládejme, že všechny bankomaty sdílet jeden bankovní accountprivate static int saldo = 0;private static void vklad() { zůstatek = zůstatek + 1;}private static void odstoupit() { zůstatek = zůstatek – 1;}“Zákazníci používají hotovost, stroje, aby se transakce, jako je tento:“javadeposit(); // dát dolar inwithdraw(); // vzít zpátky`, V tomto jednoduchém příkladu, každá transakce je jen jeden dolar vkladu následuje jeden dolar odstoupení od smlouvy, takže by to mělo nechat zůstatek na účtu beze změny. Po celý den každý Bankomat v naší síti zpracovává sled transakcí vkladu/výběru.“java// každý BANKOMAT má spoustu transakcí, které// upravit rovnováhu, ale ponechat beze změny afterwardprivate static void cashMachine() { for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { vklad(); // dát dolar odstoupit(); // vzít zpátky }}“, Takže na konci dne, bez ohledu na to, kolik hotovosti stroje byly spuštěny, či jak mnoho transakcí, které jsme zpracovali, měli bychom očekávat, že zůstatek na účtu se stále rovná 0.Ale pokud spustíme tento kód, často zjistíme, že zůstatek na konci dne je *ne* 0. Pokud je současně spuštěno více než jedno volání “cashMachine ()” – řekněme na samostatných procesorech ve stejném počítači – pak “zůstatek” nemusí být na konci dne nulový. Proč ne?## InterleavingHere je jedna věc, která se může stát. Předpokládejme, že dva bankomaty, A A B, pracují současně na vkladu. Zde je návod, jak se krok vkladu() obvykle rozkládá na pokyny procesoru nízké úrovně:“get saldo (saldo=0)přidat 1 odepsat výsledek (saldo=1)“, Když a a B jsou spuštěny současně, tyto low-level instrukce interleave s sebou (někteří by dokonce být současně v jistém smyslu, ale pojďme prostě starat se o prokládání pro teď):“get saldo (saldo=0)přidat 1 zápisu zpět výsledek (saldo=1) B saldo (saldo=1) B přidat 1 B odepsat výsledek (saldo=2)“Toto prokládání je v pořádku-jsme skončili s bilanci 2, takže oba a a B úspěšně dát do dolaru. Ale co když prokládání vypadalo takto:”‘A získat zůstatek (balance=0) b získat zůstatek (balance=0) a přidat 1 B přidat 1 odepsat výsledek (balance=1) B odepsat výsledek (balance=1) “‘ zůstatek je nyní 1-A dolar byl ztracen! A a B oba číst rovnováhu ve stejnou dobu, počítačová samostatné konečné zůstatky, a pak spěchal do obchodu zpět new balance-což se nepodařilo, aby se druhý vklad na účet.## Race Conditionto je příklad stavu * * race**. Časování znamená, že správnost programu (uspokojení z postconditions a invarianty) závisí na relativní načasování událostí v souběžné výpočty a a B. Když se to stane, můžeme říci, “To je v závodu s B.”Některé interleavings událostí může být OK, v tom smyslu, že jsou v souladu s tím, co jediné, nonconcurrent proces bude vyrábět, ale i další interleavings produkovat špatné odpovědi — porušení postconditions nebo invarianty.## Vyladění kódu Nepomohevšechny tyto verze kódu bankovního účtu vykazují stejné podmínky závodu:“java// verze 1rozvoj soukromého static void vklad() { zůstatek = zůstatek + 1;}private static void odstoupit() { zůstatek = zůstatek – 1;}“`java// verze 2private static void vklad() { balance += 1;}private static void odstoupit() { balance -= 1;}“`java// verze 3private static void vklad() { ++rovnováhy;}private static void odstoupit() { –rovnováhy;}`Nemůžeš říct, jen z pohledu na kód v jazyce Java, jak procesor bude vykonávat to. Nemůžete říct, jaké budou nedělitelné operace, atomové operace. Není atomová jen proto, že je to jeden řádek Javy. Nedotýká se zůstatku pouze jednou, protože identifikátor zůstatku se vyskytuje pouze jednou v řádku. Kompilátor Java a ve skutečnosti samotný procesor nečiní žádné závazky ohledně toho, jaké operace na nízké úrovni vygeneruje z vašeho kódu. Ve skutečnosti typický moderní kompilátor Java produkuje přesně stejný kód pro všechny tři tyto verze!Klíčové ponaučení je, že při pohledu na výraz nepoznáte, zda bude v bezpečí před závodními podmínkami.

## Změna pořadí je ve skutečnosti ještě horší. Stav závodu na zůstatku bankovního účtu lze vysvětlit z hlediska různých prokládání sekvenčních operací na různých procesorech. Ale ve skutečnosti, když používáte více proměnných a více procesorů, nemůžete ani počítat se změnami těchto proměnných, které se objevují ve stejném pořadí.Zde je příklad:“javaprivate boolean připraven = false;private int odpověď = 0;// computeAnswer běží v jednom threadprivate void computeAnswer() { odpověď = 42; připraven = true;}// useAnswer běží v různých threadprivate void useAnswer() { while (!připraven) {vlákno.výnos(); } pokud (odpověď == 0) hodit novou RuntimeException (“odpověď nebyla připravena!”);} “‘Máme dvě metody, které jsou spuštěny v různých vláknech. ‘computeAnswer’ provede dlouhý výpočet a nakonec přijde s odpovědí 42, kterou vloží do proměnné odpovědi. Poté nastaví proměnnou “ready” na hodnotu true, aby signalizovala metodě běžící v druhém vlákně “useAnswer”, že odpověď je připravena k použití. Při pohledu na kód, “odpověď” je nastavena dříve, než je připraven nastavit, takže jakmile se useAnswer` vidí `ready` jako pravda, pak se zdá rozumné, že lze předpokládat, že “odpověď” bude 42, že? Příliš.Problém je v tom, že moderní kompilátory a procesory dělají spoustu věcí, aby kód urychlily. Jedna z těch věcí, je dělat dočasné kopie proměnné, jako odpověď a připraven na rychlejší úložiště (registrů nebo cache na procesoru), a práce s nimi dočasně, než se nakonec jejich ukládání zpět na své oficiální místo v paměti. Návrat do paměti může nastat v jiném pořadí, než s proměnnými bylo ve vašem kódu manipulováno. Zde je to, co by se mohlo dít pod kryty (ale vyjádřeno v syntaxi Java, aby to bylo jasné). Procesor je skutečně vytvoří dva dočasné proměnné, `tmpr ” a ” tmpa`, manipulovat pole připraven a odpověděl:“javaprivate void computeAnswer() { boolean tmpr = připraven; int tmpa = odpověď; tmpa = 42; tmpr = true; připraven = tmpr; // <– co se stane, když useAnswer() interleaves tady? // připraven je nastavena, ale odpověď není. odpověď = tmpa;}“mitx:2bf4beb7ffd5437bbbb9c782bb99b54e Podmínky Závodu## Message Passing Příklad

Teď se pojďme podívat na zprávy-absolvování přístup na náš bankovní účet příklad.Nyní jsou nejen moduly bankomatů, ale účty jsou také moduly. Moduly interagují tím, že si navzájem posílají zprávy. Příchozí požadavky jsou umístěny ve frontě, které mají být zpracovány jeden po druhém. Odesílatel nepřestává pracovat při čekání na odpověď na jeho žádost. Zpracovává více požadavků z vlastní fronty. Odpověď na jeho žádost se nakonec vrátí jako další zpráva.Předávání zpráv bohužel nevylučuje možnost závodních podmínek. Předpokládejme, že každý účet podporuje operace “získat zůstatek” a “vybrat” s odpovídajícími zprávami. Dva uživatelé, u bankomatu A A B, se snaží vybrat Dolar ze stejného účtu. Budou kontrolovat rovnováhu jako první, aby se ujistil, že nikdy vybrat více, než účet drží, protože přečerpání vyvolat velké bankovní sankce:“get-balanceif rovnováhu >= 1 pak se stáhnout 1“problém je opět prokládání, ale tentokrát prokládání *zprávy* odeslané na bankovní účet, spíše než *návod* popraven a a B. Pokud účet začíná s dollar v to, pak to, co prokládání zpráv bude blázen a a B, mysleli si, že mohou oba stáhnout dolaru, čímž přečerpání účtu?Jednou z lekcí je, že musíte pečlivě zvolit operace modelu předávání zpráv. `výběr-pokud-dostatečných-prostředků “by byl lepší operací než jen “výběr”.## Souběžnost je těžké testovat a Laditpokud jsme vás nepřesvědčili, že souběžnost je složitá, tady je to nejhorší. Je velmi těžké zjistit závodní podmínky pomocí testování. A i když test našel chybu, může být velmi obtížné ji lokalizovat do části programu, která ji způsobuje.Chyby souběžnosti vykazují velmi špatnou Reprodukovatelnost. Je těžké, aby se staly stejným způsobem dvakrát. Prokládání instrukcí nebo zpráv závisí na relativním načasování událostí, které jsou silně ovlivněny prostředím. Zpoždění může být způsobeno jinými běžícími programy, jiným síťovým provozem,rozhodnutím o plánování operačního systému, změnami rychlosti hodin procesoru atd. Pokaždé, když spustíte program obsahující podmínku závodu, můžete získat odlišné chování. Tyto druhy chyb se **heisenbugs**, které jsou nedeterministické a těžko reprodukovat, jako protiklad k “bohrbug”, které se objeví opakovaně, kdykoliv se podíváte na to. Téměř všechny chyby v sekvenčním programování jsou bohrbugy.Heisenbug může dokonce zmizet, když se pokusíte podívat na to s ‘println’ nebo ‘debugger’` Důvodem je, že tisk a ladění jsou mnohem pomalejší než jiné operace, často 100-1000x pomalejší, že dramaticky mění načasování operací a prokládání. Takže vložení jednoduchého tiskového prohlášení do Kašmíru():“javaprivate static void cashMachine() { for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { vklad(); // dát dolar odstoupit(); // vzít zpátky Systému.mimo.println (zůstatek); / / způsobí, že chyba zmizí! }}“`…a najednou je zůstatek vždy 0, jak je požadováno, a zdá se, že chyba zmizí. Ale je to jen maskované, ne opravdu opravené. Změna načasování někde jinde v programu může náhle způsobit, že se chyba vrátí.Souběžnost je těžké napravit. Součástí tohoto čtení je trochu vás vyděsit. V příštích několika čteních uvidíme principiální způsoby, jak navrhnout souběžné programy tak, aby byly bezpečnější před těmito druhy chyb.mitx:704b9c4db3c6487c9f1549956af8bfc8 Testování Souběžnosti## Shrnutí+ Souběžnosti: více výpočtů současně spuštěných+ Sdílené paměti & message-passing paradigmata+ Procesy & threads + Proces je jako virtuální počítač; vlákno je jako virtuální procesor+ podmínky Závodu + Při správnost výsledku (postconditions a invarianty) závisí na relativní načasování eventsThese nápady připojit na naše tři klíčové vlastnosti dobrého software většinou ve špatné způsoby. Souběžnost je nutná, ale způsobuje vážné problémy s korektností. Budeme pracovat na odstranění těchto problémů v příštích několika čtení.+ * * Bezpečné před chybami.** Souběžnost chyby jsou některé z nejtěžších chyb najít a opravit, a vyžadují pečlivý design, aby se zabránilo.+ * * Snadno pochopitelné.** Předpovídání toho, jak souběžný kód může prokládat s jiným souběžným kódem, je pro programátory velmi obtížné. Nejlepší je navrhnout tak, aby o tom programátoři nemuseli přemýšlet. + * * Připraven ke změně.** Zde není nijak zvlášť relevantní.