Třetí série dvacátého druhého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 1. února 2010 8:00. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Zadání úloh

Hroch

Běží liška k Táboru, nese pytel zázvoru, ježek za ní utíká, že jí pytel rozpíchá … Třetí příběh se nese v duchu nejen husitských válek a sepsal ho Jan „Moskyt“ Matějka. Poslední díl seriálu o Erlangu vám přináší Michal Vaner.

Mezi stromy prosvítalo slunce. Tomáš opatrně vykoukl z lesa. Nad řekou létali ptáci a na protějším břehu nikdo nebyl. Vrátil se ke koni, přebrodil řeku a pomalu začal stoupat k Táboru.

Po ušlapané cestě se jelo pohodlně. Daleko lépe, než když se před chvílí prodíral hustým lesem. Kdyby si ho ale všimli Zikmundovi zvědové, zabili by ho, nebo alespoň … Ne, nemyslet na to. Tady už mohl být viděn, tady je vítán.

Vjel do otevřené brány a sesedl z koně. Na velkém prostranství pobíhaly děti, občas nějaká žena za domkem věšela prádlo. Klid a mír, jako by nevěděli, jakou zprávu přiváží. Strážný u brány na něj přátelsky pomrkával.

Hned se okolo něj seběhly děti a zvědavě se vyptávaly, kdo je, co veze, co jim dá … Tomáš je však nevnímal a došel až k velké kádi plné stříbrných mincí uprostřed náměstí.

Vytáhl z hlubin svého pláště hrst mincí a podával je mladíkovi u kádě. „Zde je dar od bratří z Horního Blešna. Jen se mi mezi ně zatoulala jedna falešná.“


22-3-1 Falešná mince (10 bodů)


Falešná mince se vyznačuje tím, že má odlišnou hmotnost od všech ostatních v hrsti. Jinak vypadá úplně stejně a je právě jedna v celé hrsti mincí. K dispozici máme rovnoramenné váhy. Určete, kolik vážení bude potřeba, abyste nalezli mezi N mincemi falešnou. Při jednom vážení může být na miskách libovolný počet mincí.

To by ovšem bylo příliš jednoduché. Váhy jsou totiž v celém Táboře jediné – v lékárně. Lékárník je navíc nedůvěřivý a požaduje, abyste mu předali sepsaná všechna vážení na papírku předem, on je provede, řekne vám, jak to dopadlo, a vy podle toho už musíte najít falešnou minci.

Příklad pro N=4: Lékárníkovi zadáte zvážit mince takto:

1  ---  2
1  ---  3

Pokud jsou v obou případech v rovnováze, tak je falešná 4; pokud jsou v obou případech stejně nakloněné, tak je falešná 1; konečně pokud jsou jednou v rovnováze a jednou nakloněné, tak je falešná 2, resp. 3 podle toho, které jsou nakloněné.

Falešná mince byla úspěšně oddělena, ostatní vhozeny do kádě a Tomáš vyrazil vstříc chlapíkovi, který vyšel z jednoho z domů okolo náměstí. „Buď zdráv, Prokope, přináším zprávy z Prahy.“ „Pokoj tobě, Tomáši. Pojď za mnou, ať zde nejsme rušeni.“

Oba vešli do domu, odkud Prokop před chvílí vyšel. Ženy dál věšely prádlo, nad Lužnicí létali ptáci. Obloha jako z Ladových obrázků, skoro bez mráčku, ale zdáli jako by zahřmělo. Nikdo tomu nevěnoval pozornost. Za lesem stoupal hustý černý dým, asi někdo pálil trávu. Děti na náměstí pokračovaly ve hře, kterou hrály před Tomášovým příjezdem.

Řešení


22-3-2 Dětská hra (8 bodů)


Každé dítě si vybere jedno jiné dítě. Pak se křikne „Teď!“, děti se rozprchnou po náměstí a začíná hra. Každý chytá toho, koho si vybral (plácnutím po zádech). Chycený sdělí lovci, koho si vybral on, a lovec od této chvíle loví tuto novou oběť.

Zvědavá tetka Bětka před jednou hrou zjistila od všech dětí, koho chytají, a dlouze se zamýšlela nad tím, co se stane, když dítě zjistí, že má chytat samo sebe. To by nás zajímalo také a k tomu se hodí samozřejmě vědět, kolik dětí může do takové situace dospět.

Například pro skupinu 4 dětí, kde si první vybere druhého, druhý třetího, třetí čtvrtého a čtvrtý prvního, mohou do tohoto stavu dospět všechny čtyři děti.

Naopak pro jinou skupinu 4 dětí, kde první chytá druhého, druhý třetího, třetí prvního a čtvrtý také prvního, snadno zjistíme, že čtvrtý nikdy sebe sama chytat nebude.

Vymyslete algoritmus, který tento počet na základě informací tetky Bětky určí.

Jedno z dětí se právě začalo zuřivě bít do zad a křičet „Já, já, já!“, když Tomáš s Prokopem v družném hovoru vyšli ven z domu.

Přešli přes náměstí až ke bráně. Prokop řekl cosi strážnému, ten hned vstal a spěšně kamsi odešel. Vedle seděl zarostlý muž, který až do této chvíle hrál karty s vrátným. „Petře, čeká tě dlouhá cesta. Pozdravíš bratry v Rokycanech a sdělíš jim …“

Kurýr Petr vstal a odešel do stáje. Strážný se vrátil k bráně s malým chlapcem, ten vyběhl ven. Pomalu začali přicházet různí lidé, vraceli se domů, do bezpečí za táborskou palisádu.

Petr se po chvíli vrátil i s osedlaným koněm, nabral do měchu vodu, přehodil přes sebe plášť, nasedl na koně a odjel, strážný za ním zavřel bránu. Tomáš a Prokop ho chvíli sledovali, jak přebrodil Lužnici a vydal se směrem na Orlík, pak se vrátili do Prokopova domku.

Řešení


22-3-3 Kurýrní služba (13 bodů)


Mezi husitskými městy předávají zprávy kurýři. Každý kurýr přepravuje zprávy pouze ze svého domovského města do jednoho jiného. Opačným směrem je považován za nedůvěryhodného. Nevadí však, když je zpráva poslána postupně přes několik kurýrů (např. zprávu z Tábora do Chlumce odveze táborský kurýr do Prahy, kde ji předá jinému, který ji odveze do Chlumce).

Vymyslete algoritmus, jehož vstupem bude seznam všech kurýrů ve všech městech a který zjistí, jestli mezi každými dvěma městy lze přepravit zprávu alespoň jedním směrem. Stačí tedy, když existuje jednosměrná cesta.

Příklad: Pro města Tábor (T), Praha (P) a Rokycany (R) a kurýry TP, PR lze přepravit mezi každou dvojicí měst zprávu alespoň jedním směrem. Pro stejnou trojici měst, ale kurýry TP a RP nelze přepravit zprávu z Tábora do Rokycan ani naopak.

„Poplach! Hradečtí za řekou, poplach!“ ozvalo se najednou a dosud klidné náměstí jako by ožilo. Děti utekly domů, po náměstí pobíhali poloozbrojení muži. Mířili do zbrojnice. Atmosféra houstla.

Za dřevěnou palisádou se pomalu objevovali další strážní. Ozbrojeni okovanými cepy a krátkými meči byli téměř neporazitelní. Z dálky se pomalu blížilo dunění.

Prokop a Tomáš vyšli z domku a přešli náměstí. Prokop v plné zbroji, dlouhý meč a štít. Tomáš měl krátký meč, aby mu při jízdě na koni nepřekážel, ale někde ztratil rukavice. Stavili se tedy ve zbrojnici. Prokop zašel do malé temné místnosti a po chvíli se vrátil s náručí plnou rukavic. Hrály všemi barvami, až se zdálo, že Tomáš nenajde levou a pravou stejné barvy.

Řešení


22-3-4 Rukavice (10 bodů)


V malé temné místnosti jsou dvě truhly a tma. V jedné z truhel jsou jen levé rukavice, ve druhé jen pravé. Bezpečně víme, kolik rukavic které barvy je ve které truhle. Prokop jednou náhodně vytáhne L levých rukavic a P pravých rukavic. Nalezněte algoritmus, který najde L a P taková, aby součet L+P (celkový počet přinesených rukavic) byl co nejmenší, ale aby si Tomáš mohl vybrat pravou a levou rukavici stejné barvy.

Prokop jich ale přinesl dostatek, takže po chvíli Tomáš odcházel spokojen se dvěma hnědými rukavicemi.

Hradečtí vybíhali z lesa. Z palisády trčela kopí jak bodliny ježka, která jim znesnadňovala přístup až k ní. Táborští ale zjevně toužili po pořádné bitevní vřavě. Přelézali palisádu a bili se s hradeckými hlava nehlava.

Tomáš natáhl rukavice, vzal do ruky meč a nelítostně šermoval hned se dvěma hradeckými. Jednoho z nich odrazil, až se skutálel ze svahu dolů, druhý měl dosti tuhý kořínek, ale i ten nakonec padl. A hned se na něj vrhl další. Ještě že se skrčil. Taková příležitost k seku do nohou se jen tak nenaskytne!

Zvládl už asi deset hradeckých, když se k němu rozběhli najednou tři. Nevěděl, kam dřív skočit. Tu se otevřela brána a vyjely z ní dva vozy naložené shnilými mokrými kůly, které táborští vyměnili při poslední opravě palisády. Hradečtí nestíhali uhýbat a Tomáš měl konečně zase chvíli klid …

* * *

Slunce se klonilo k západu, když se ozvalo trojí táhlé zatroubení. Hradečtí už byli dávno zpátky za řekou a utíkali rozprášeni přes pole pryč. Tomáš s Prokopem přes sebe přehodili pláště, dřevěné meče schovali pod ně, z Prokopova domu vytáhli batohy a vydali se spolu s většinou ostatních táboritů na nejbližší železniční zastávku.

Přijíždějící vlak měl na sobě reklamu, kterou ještě nikdy neviděli. Na modrém pozadí byly nakresleny žluté puntíky propojené žlutými čarami.

Řešení


22-3-5 Reklama (15 bodů)


Ve čtvercové síti je nakresleno N bodů. Potřebujeme je pokrýt co nejméně plochými lomenými čarami.

Plochá lomená čára vypadá tak, že žádný z jejích úseků nesvírá s osou x větší úhel než 45° a lze nakreslit jedním tahem zleva doprava (tužka se pohybuje jen vpravo).

Na vstupu dostanete N bodů zadaných jejich celočíselnými souřadnicemi (xi,yi). Jako výstup vypište minimální počet potřebných plochých lomených čar.

Příklad

Příklad:

Pro 6 bodů se souřadnicemi (1,6), (10,8), (1,5), (2,20), (4,4), (6,2) potřebujeme 3 ploché lomené čáry na jejich pokrytí.

Bodování:

  • max. 15 bodů: řešení rychlé při 1 ≤ N ≤ 100000
  • max. 12 bodů: řešení rychlé při 1 ≤ N ≤ 1000
  • max. 10 bodů: řešení rychlé při 1 ≤ N ≤ 100

Nastoupili do vlaku a vzájemně si vyměňovali zážitky. Kdo koho potkal, vypátral nebo nevypátral, kdo spadl do potoka nebo uskakoval před jedoucím vozem plným shnilých klád.

Ostatní odjeli auty. Dřevěný Tábor tady zůstane, za měsíc v něm bude dětský tábor. Všechno ostatní uklidili, přece po nich nezůstane nepořádek.

Slunce již bylo dávno pod horizontem. Praha svítila do dáli pouličním osvětlením, když Tomáš s Prokopem vystupovali na hlavním nádraží. Vešli do metra, v Holešovicích přestoupili a cestou od zastávky autobusu 112 na kolej přemýšleli, kolik času zase stráví ve výtahu, než dojedou až tam, kde bydlí.

Řešení


22-3-6 Kolejní výtahy (10 bodů)


V přízemí před výtahem stojí N kolejníků, kolej má K pater. Každý kolejník má své cílové patro – kde bydlí – a ochotu (inverzní veličinu k lenosti), která určuje, kolik pater je ochoten dojít poté, co vystoupí z výtahu. Výtah přijede, všichni kolejníci se do něj nastřádají.

Napište program, který dostane na vstupu seznam kolejníků s jejich cílovými patry a ochotami a který vypíše na výstup minimální počet pater, ve kterých je potřeba zastavit, aby byli všichni kolejníci uspokojeni. Jak počet pater, tak cílová patra a ochoty jsou nezáporná celá čísla.

Tato úloha je praktická a řeší se ve vyhodnocovacím systému CodEx. Pokud jste zatím žádnou praktickou úlohu neřešili, přečtěte si stručný úvod.

A tak skončila další dřevárna, oblíbená to víkendová zábava některých členů Bratrstva, jako Tomáše a Prokopa.

Řešení


22-3-7 Pavouci internetu (12 bodů)


Pavouci dělají sítě. A také přežijí téměř cokoliv, protože mají každý orgán alespoň dvakrát a když o jeden přijdou, s jedním si chvíli vystačí a druhý po čase zase doroste.

V dnešním, posledním díle Erlangového seriálu se takovými pavouky necháme trochu inspirovat.

Pojmenované procesy

Když chceme, aby dva procesy komunikovaly, musí alespoň jeden z nich znát PID toho druhého. To je ale nepohodlné, protože by ty procesy nemohly vznikat nezávisle na sobě.

Erlang nás od tohoto problému zachrání tím, že nám dovoluje procesy pojmenovávat. Slouží k tomu funkce register, která přebírá jméno (které je reprezentováno atomem – tedy slovem začínajícím malým písmenem) a PID:

register(udrzbar, spawn(sprava, udrzuj,
                       [budova1, budova2]))

Poté můžeme používat tento atom v místě, kde bychom potřebovali PID procesu. Napíšeme prostě něco takového:

udrzbar ! {oprava,
    "Potřebuji opravit záchod, nesplachuje."}

Více počítačů

A nyní se dostáváme k tomu zajímavému. Máme více počítačů a chceme, aby různé kusy kódu běžely na různých počítačích. Než se však pustíme do vlastního programování, je třeba provést trochu nastavení.

Oprávnění

Při použití unixového systému je veškeré nastavení jednoduché. Vytvoříme soubor .erlang.cookie s oprávněním 0400 (čtení jen majitelem, nikdo jiný nesmí nic) a uložíme do něj jeden řádek obsahující nějaké heslo. Tento soubor poté umístíme na všechny počítače, kde náš program poběží (tím, že budou mít stejné heslo, budou počítače vědět, že si mají navzájem věřit, je to princip společného tajemství).

$ cat >.erlang.cookie
heslo
$ chmod 0400 .erlang.cookie

Při použití Windows je to malinko složitější. Domovský adresář je ten, který je nastavený v proměnné prostředí HOME, takže je potřeba zjistit, který to je, a případně tuto proměnnou na nějakou hodnotu nastavit. Pro ty, kteří nevědí, kde takovou věc najít, nachází se v  Tento počítač Vlastnosti záložka Upřesnit tlačítko Proměnné prostředí. Pokud nevíte, kde hledat Tento počítač, otevřete si Ovládací panely Systém.

Komunikace

Chceme dosáhnout toho, že na různých počítačích běží různý kód, a uděláme to tak, že si na každém z nich pustíme interpretr Erlangu. Pokud se nedostává počítačů, tak je možné na jednom počítači pustit více interpretrů (pokud chceme testovat komunikaci 5 počítačů a máme jen jeden, tak na něm prostě pustíme 5 interpretrů).

Aby mezi sebou mohly interpretry komunikovat, musíme mít způsob, jak je adresovat. Adresa je podobná e-mailové a má tvar jmeno@pocitac. Část pocitac je jednoduchá – to je jméno počítače na lokální síti (ne, že by nešlo zařídit, aby spolu komunikovaly Erlangy na různých sítích, ale my si to ulehčíme). A část jmeno mu poskytneme při zapnutí. Předpokládejme, že tedy máme počítač zvaný hroch a chceme na něm pustit interpretr, který nazveme testovaci (tedy, adresa tohoto interpretru bude testovaci@hroch):

erl -sname testovaci

Posílání zpráv

PID obsahuje i identifikaci interpretru, ve kterém proces běží. To znamená, že pokud dostaneme PID jako parametr, máme ho v proměnné, je výsledkem funkce nebo podobně, nemusíme se vůbec starat o to, jestli proces běží u nás, nebo někde jinde. Zprávu mu odešleme úplně obvyklým způsobem a Erlang se o doručení postará.

Jediné, co je třeba prozkoumat, je posílání zprávy procesu registrovanému v jiném interpretru. Potom jako cíl zprávy uvedeme dvojici {proces, interpretr}. Tedy, kdyby náš údržbář byl registrovaný na vrátnici, hlásili bychom mu závady takto:

{udrzbar, vratnice@budova} !
          {oprava, "Potřebuji opravit záchod."}

To, kde je proces registrovaný, neříká vůbec nic o tom, kde vlastně běží. Registrování procesu je jen uložení PID do „globálního úložiště“.

Spouštění procesů

Pokud použijeme spawn tak, jak jsme jej až dosud používali, proces se spustí v aktuálním interpretru. Pokud bychom chtěli spustit proces v jiném interpretru, tak bychom přidali na začátek parametrů funkce spawn adresu interpretru, kde se má spustit. Samozřejmě, tento interpretr už musí běžet a musí mít k dispozici kód, který se má spouštět.

Vezměme si tedy příklad z minulého dílu, kde jsme měli producenta a konzumenta. Malinko si ho upravíme:

-module(spojeni).
-export([vypocet/0, registrovany_vyrobce/0,
                       vyrob/0, spotrebuj/1]).
-import(zpracovani).
 
vyrob() ->
  Data = zpracovani:vyrob(),
  receive
    {chciData, Pid} ->
      Pid ! data, Data,
      vyrob();
    konec -> ok
   end.
 
registrovany_vyrobce() ->
  register(vyrobce, self()),
  vyrob().
 
spotrebuj(Vyrobce) ->
  Vyrobce ! {chciData, self()},
  receive {data, Data} ->
    case zpracovani:spotrebuj(Data) of
      dalsi -> spotrebuj(Vyrobce);
      konec -> Vyrobce ! konec
    end;
  end.
 
vypocet() ->
  spawn(vyrobce@hroch, spojeni,
                   registrovany_vyrobce, []),
  spawn(spojeni, spotrebitel,
                   [{vyrobce, vyrobce@hroch}]).

Čím se liší od minulé verze? Jednak, výrobce se registruje, abychom nemuseli chytat jeho PID (i když, zrovna v tomto případě z toho žádná výhoda neplyne, jen jsme si ukázali syntaxi). Ale co je hlavní, výrobce je vzdáleně puštěn v interpretru vyrobce@hroch, zatímco spotřebitel nám běží lokálně. Pokud by lokální interpretr neběžel na počítači hroch, ale někde jinde, tak by pracovaly oba počítače – jeden vyráběl, druhý spotřebovával. A o přenos dat mezi nimi by se staral Erlang bez naší pomoci.

Erlang je, i když se to nezdá, kompilovaný jazyk. Kompiluje se příkazem c(jmenomodulu). Toto vytvoří soubor obsahující bytecode pro interpretr (tou jsou ty podivné .beam soubory, které se při pokusech začnou povalovat po okolí). Tedy, pro použití modulu není c potřeba, pokud už .beam existuje, stačí se na něj jen odkázat. Proto, pokud chceme pouštět nějaký kus kódu na vzdáleném počítači, tak na něj stačí nakopírovat vzniklé .beam soubory.

Robustnost, spolehlivost

Co se stane v případě, že výrobce v našem případě bude dělit nulou a umře? Nebo v případě, že máme, podobně jako Cimrman, jako domácího mazlíčka slepici a ona dostane skvělý nápad nám klovnout do síťového kabelu?

Potřebujeme takové situace nějak ošetřit. Ne, že by Erlang dokázal zabránit přirozenému chování slepic, ale naučíme se na vzniklé situace reagovat.

Výsledek procesu

Každý proces jednou skončí, ale může skončit různými způsoby. Tyto způsoby se dělí do dvou skupin – normální konec a abnormální. Normální znamená, že je všechno v pořádku, abnormální obvykle znamená, že se něco pokazilo či nedopadlo, jak mělo.

Prvním způsobem je, když proces jednoduše doběhne na konec – všechny funkce skončí. To způsobí normální konec.

Druhý způsob je, když dojde k nějaké běhové chybě – dělíme nulou, počítač, kde proces běžel, odnese voda, zavoláme funkci, která neexistuje, a podobně. To samozřejmě způsobí abnormální konec.

Nebo může proces zavolat příkaz exit. Ten způsobí, že proces skončí (okamžitě, ne třeba až doběhne funkce). Přebírá jeden parametr – výsledek procesu. Pokud je jím atom normal, pak se jedná o normální konec, v opačném případě je to abnormální konec.

Známí

Procesy v Erlangu mohou navazovat jakési známosti. K tomu slouží příkaz link(PID), který spojí aktuální proces s předaným v obousměrnou známost (aktuální zná PID a PID zná aktuální). Podobná funkce je spawn_link, jež funguje stejně jako spawn, ale navíc ještě seznámí starý proces s tím nově vzniklým.

Pokud některý náš známý proces skončí, pošle se nám o tom zpráva. Ve výchozím nastavení jsou normální konce ignorovány a abnormální způsobí, že skončíme také (abnormálně).

Již toto by stačilo na zařízení, aby, když umře některá část provázaného systému, bez které se nedá obejít, tak zbývající části „nehnily“, ale skončily také.

Řízení reakcí

Pokud by nám způsob „mor“ nevyhovoval, můžeme si změnit, co se stane, když nějaký známý skončí. To se udělá příkazem:

process_flag(trap_exit, true)

V takovém případě nám při skončení známého přijde obvyklá zpráva ve tvaru:

{'EXIT', PID_mrtvoly, Duvod}

Duvod bude to, co dostal exit, případně nějaké zdůvodnění, proč proces spadl. V případě, že vše bylo v pořádku, tak to bude normal.

Tuto zprávu si můžeme vybrat z fronty a známého třeba restartovat, nahlásit správci, prohlásit úlohu za neřešitelnou, či cokoliv jiného.

Netrpělivost

Normálně, pokud použijeme receive, tak čeká, dokud nějaká zpráva nepřijde. Můžeme však říct, že chceme čekat nejvýše nějakou dobu, a to tak, že jako poslední možnost dáme after jakdlouhocekat. Čas je uveden v milisekundách. Toto je tedy kód, který by čekal na autobus, ale nejvýše 5 minut:

cekej() -> receive
  {autobus, Pid} -> autobus ! {nastup, self()};
  after 300000 -> jdi_pesky()
end.

Ukázky

Náš spotřebitel potřebuje výrobce, bez něho nemůže fungovat. Takže bychom ho napsali asi takto:

bezpecny_spotrebitel(Vyrobce) ->
  link(Vyrobce),
  spotrebuj(Vyrobce).

Pokud umře výrobce, umře i spotřebitel. Dále, výrobce, pokud po něm nikdo dlouho nebude nic chtít, tak skončí (zřejmě něco nefunguje, protože si ho pustil a neposílá požadavky):

bezpecny_vyrobce() ->
  Data = zpracovani:vyrob(),
  receive
    {chciData, Pid} ->
      Pid ! data, Data,
      bezpecny_vyrobce();
    konec -> ok;
    after 10000 -> exit(timeout)
  end.

Nakonec si pořídíme ještě jeden proces, který na tyto dva bude dohlížet. Pokud se cokoliv nepovede (některý proces skončí a nebude to normální konec), tak celou operaci zkusí znovu.

hlidej(0) -> ok;
hlidej(Zbyva) -> receive
  {'EXIT', _, normal} -> hlidej(Zbyva - 1);
  {'EXIT', _, _} -> spawn(spojeni,
                       bezpecny_start, [])
end.
 
bezpecny_start() ->
  process_flag(trap_exit, true),
  Vyrobce = spawn_link(vyrobce@hroch, spojeni,
                       bezpecny_vyrobce, []),
  spawn_link(spojeni, bezpecny_spotrebitel,
                       [Vyrobce]),
  hlidej(2).

Napřed si nastavíme, že chceme dostávat zprávy o koncích známých, a poté pustíme dva procesy. Nakonec je necháme hlídat, když některý skončí normálně, odečteme si, kolik jich zbývá. Až žádný zbývat nebude, vše skončilo dobře. Pokud některý z nich skončí s chybou, celé to pustíme znovu, ale v novém procesu – druhý v té době může ještě existovat a za chvíli skončí s chybou, takže bychom dostali hlášku i o jeho smrti – ale to bychom už hlídali nový pokus a mysleli bychom si, že skončil špatně ten.

Úložka

Chceme něco, co bude rozdělovat práci mezi stroje. Budeme mít 3 druhy strojů – pracující (na těch se bude provádět práce), klienti (ti budou požadovat provedení nějaké práce) a servery, které budou práci rozdělovat. V zásadě něco podobného, jako úložka Centrum práce v minulém díle.

Bude několik modulů. Jeden modul (client) bude obsahovat funkci na zadání práce. Až práce skončí, bude nám výsledek funkce doručen jako zpráva. Druhý, prace se bude pouštět na pracujících strojích, třetí server na serverech. A v modulu nastaveni budou adresy serverů, ke kterým se mohou klienti a pracující připojovat. Pracující smí dělat maximálně jednu činnost v daný okamžik a nesmí se stát, že by někde práce čekala, pokud je některý pracující volný.

Samozřejmě nám jde o to, aby nám systém přežíval i v případě výpadků. Takže, co je potřeba zařídit:

  • Když vypadne klient, tak přežít.[3 body]
  • Když spadne vyhodnocování práce, pracující musí přežít a zaslat zprávu o chybě. Stejně tak, pokud práce bude trvat delší dobu, než nějakou stanovenou (pravděpodobně je zacyklená), tak je třeba ji ukončit a poslat zprávu o chybě.[3 body]
  • Když vypadne pracující, tak přežít a práci přidělit nějakému jinému pracujícímu na udělání. Tedy, když vypadne pracující, tak by to klient vůbec neměl poznat. [3 body]
  • Když vypadne některý ze serverů, tak se zařídit tak, aby zbytek systému přežil, daly se dál zadávat nové úkoly a stávající práce byla dokončená a výsledky doručeny. [3 body]

V každém z těchto případů můžete předpokládat, že z každé skupiny strojů ještě nějaké zbyly, tedy nestane se, že by vypadly všechny servery.

Řešení