Druhá série dvacátého sedmého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 8. prosince 2014 8:00. Termín odevzdání CodExové úlohy je pak 9. prosince 2014 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.

Odměna série: Každému, kdo vyřeší tři libovolné úlohy na plný počet bodů, pošleme čokoládu.

Zadání úloh

Stejně jako v první sérii, i teď zavítáme k nějaké zajímavé programátorské chybě. V minulém díle jsme se potkali s chybou v GPS způsobenou dělením nulou, typické to softwarové přehlédnutí. Dnešní chyba však bude ukryta ještě hlouběji, je to na první pohled těžko tušitelné selhání v návrhu celého systému.

Podobně jako minulý příběh nás i dnešní zavede do války v Perském zálivu, tentokrát ale do města Dhahran na západním břehu Perského zálivu v Saudské Arábii. Bohužel však tato chyba bude mít mnohem temnější následky…

* * *

Bylo 25. února ráno a spojenecká základna v Dhahranu se probouzela do dalšího dne, hlídky přebíraly nové skupiny vojáků a z kantýny se začala linout vůně připálených vajíček. Svobodník George Matthews do sebe rychle naházel snídani, vajíčkům se raději vyhnul, a vydal se na hlídkovou věž vystřídat jiného strážného.

Cestou ještě podrbal svého psa, kterého měl jako pyrotechnik už mnoho let přiděleného. Dopey byl už za svých třináct let zvyklý na vojenský život na základnách, a tak jen šťastně zavrtěl ocasem, na svém řetězu doběhl k jedné z podpůrných noh blízkého přívěsu a označkoval ji.

Ilustrace: Spící kočka

„Systém za desítky miliónů a ty si ho tady budeš značkovat?“ zasmál se George a vydal se okolo přívěsu s radarem protiraketového systému Patriot dál. Systém to byl rozhodně impozantní a i díky němu si připadal v bezpečí. V bateriích v blízkosti radaru se nacházelo skoro třicet kusů protistřel, kterými systém sestřeloval blížící se irácké rakety Scud. Vždy si pro sestřel vybral tu nejvhodnější protistřelu a tu odpálil.


Teoretická úloha27-2-1 Systém Patriot (9 bodů)


Protiraketový systém Patriot má k dispozici mnoho protistřel, které může proti blížící se hrozbě odpálit. Pro jednoduchost můžeme každou protistřelu charakterizovat pomocí jejího dostřelu (kladné reálné číslo). Za normální situace (pokud neurčí lidský operátor jinak) vyšle systém protistřelu, jejíž dostřel je mediánem mezi aktuálně dostupnými protistřelami.

Medián je prvek, který by se v setříděné posloupnosti nacházel přesně uprostřed. Pokud má posloupnost sudý počet prvků (tedy uprostřed leží dva prvky), budeme v tomto případě brát ten větší z nich (protistřelu s vyšším doletem).

Protistřely se do systému i doplňují (tak, jak jsou dopravovány na základnu), a proto by od vás spojenecká armáda potřebovala vybudovat rychlou datovou strukturu podporující dva typy operací:

  1. Přidej protistřelu s doletem di do systému.
  2. Odpal protistřelu s doletem, který je mediánem mezi aktuálními dolety (výsledkem by mělo být odebrání protistřely a vrácení jejího doletu).

Lehčí variantaLehčí varianta (za 3 body): Vyřešte úlohu pro případ, kdy systém vysílá střelu s nejvyšším dostřelem.

Řešení

Už se blížil čas oběda, když se základnou rozezněly poplašné sirény. George se rychle otočil na systém Patriot. Viděl, jak se jedna z baterií protistřel natočila směrem na severovýchod, a očekával odpal. Ale vteřiny ubíhaly a nic se nedělo. Po deseti vteřinách čekání skoro v ten samý moment většině přítomných vojáků došlo, že protistřela už nevyletí, že se něco porouchalo.

George se nedíval na ostatní, ale rychle sjel po žebříku z věže a sprintem se vrhl do blízkého úkrytu. Pak dopadl irácký Scud a obloha potemněla. Byl to den, kdy opěvovaný systém Patriot selhal, a nikdo zatím nevěděl proč.

* * *

Hned, jak lehce opadl mrak sutin a prachu, začali se z různých úkrytů vynořovat více či méně zranění vojáci. Ti zázrakem nezranění a ti s lehkými zraněními se hned vrhli do odhrabávání trosek zřícených budov.


Teoretická úloha27-2-2 Prohledávání budov (10 bodů)


Po raketovém útoku stojí na základně několik poničených budov. Je nutné je všechny projít, odklidit trosky a hledat přeživší. Již se organizuje několik skupin záchranářů, ale je potřeba rozmyslet plán prohledávání.

Jedna skupina záchranářů může projít buď jednu budovu od přízemí do nejvyššího patra, nebo může naopak projít i-té patro v každé budově. Každé patro v každé budově je nutné prohledat alespoň jednou, vícenásobné prohledání nám nevadí.

Dostanete seznam budov a jejich počty pater. Rozmyslete, jak je všechny prohledat s co nejmenším počtem záchranných týmů.

Například pro výšky (5,2,4,1,2) stačí čtyři záchranné týmy, jak je vidět na následujícím obrázku:

Řešení

Už několik hodin pomáhal George vytahovat z trosek oběti. Většina z nich to přežije, ale už objevili i pár takových, kteří tolik štěstí neměli. Právě rozebírali pozůstatky po kantýně v centru základny, když pod troskami spatřil známou věc – lesklý obojek.

Rychle odházel stranou několik kovových nosníků a sevřel v náručí psí tělo. Dopey vypadal, že jen spí, ale nebylo tomu tak. Na George náhle dolehly události několika posledních hodin plnou silou, a tak se jen posadil na trosky a několik minut jenom hleděl do dáli.

„Třináct let a čtyřicet dva dní, pane,“ řekl důstojníkovi, který se u něj objevil, a pak ještě dodal: „Tolik mu bylo.“ „To je mi líto Matthewsi, ale teď sem potřebujeme rychle dostat nějaké jeřáby, aby nám pomohly s odklízením trosek.“ George odložil tělo Dopeyho opatrně ke stěně, osušil slzy a vrhl se na hordu map na plánovacím stole.


Praktická CodExová úloha27-2-3 Průjezd jeřábu (10 bodů)


Potřebujeme dostat autojeřáb z jednoho konce města Dhahran na druhý, aby pomohl s odklízením trosek na vojenské základně. Stavební firma sídlící na druhém okraji města je ochotná půjčit jakýkoliv ze svých jeřábů. My bychom chtěli k troskám dostat co největší jeřáb, ale čím větší, tím také vyšší – a ulice Dhahranu jsou prošpikované nízko zavěšenými elektrickými dráty.

Ilustrace: Jeřáb Na vstupu máme mapu města zadanou jako síť ulic a křižovatek. Ulice jsou obousměrné, ale pro každou ulici máme údaj, jaké nejvyšší vozidlo jí ještě může bezpečně projet. Mapa města tedy představuje ohodnocený graf.

Navíc dostaneme ještě dvě označené křižovatky, sídlo firmy a vojenskou základnu. Najděte cestu mezi těmito dvěma místy, kterou může projet co nejvyšší jeřáb.

Tato úloha je praktická a řeší se ve vyhodnocovacím systému CodEx. Přesný formát vstupu a výstupu, povolené jazyky a další technické informace jsou uvedeny v CodExu přímo u úlohy.

Řešení

Konečně se jim povedlo všechny vyprostit, a také znovu zabezpečit základnu. Konečný účet byl 28 mrtvých spojeneckých vojáků a jeden pes k tomu. Zraněných bylo několik desítek. Všem také vrtalo hlavou, proč systém Patriot ani nevystřelil. Na to přijel hledat odpověď i vyšetřovací tým, který dorazil ještě toho dne večer.

Přesuneme se teď v příběhu od svobodníka Matthewse, který sehrál důležitou roli při záchranných operacích, k poručíkovi Blairovi, vedoucímu vyšetřovacího týmu.

Poručík Blair začal ihned shánět všechny informace o selhání. Protiraketový systém fungoval tak, že radar kontinuálně snímal celou oblast. Ve chvíli, kdy zachytil blížící se raketu Scud, přepnul se do přesnějšího módu, omezil snímání jen na oblast, ve které se raketa nacházela, a tím zpřesnil zaměření před odpálením protistřely.

Podle očitých svědků radar něco zaregistroval a připravil jednu z baterií protistřel na odpal. K samotnému odpalu ale již nedošlo. První věcí, kterou vyšetřovací tým potřeboval, bylo stáhnout družicové snímky oblasti z okamžiku vypálení Scudu. Zhruba každých deset sekund snímkovala americká družice oblast Íráku a čas startu rakety a její trajektorie by mohly pomoci s objasněním, co se vlastně stalo.

Problémem, se kterým se ale vyšetřovací tým musel nějak poprat, bylo to, že rychlost místního připojení k družicové informační síti byla příliš pomalá – dostačovalo k předávání běžných zpráv, ale na stáhnutí mnoha kompletních snímků z družic již ne. Naštěstí si Američané již před časem pro podobné věci vypracovali postup.


Teoretická úloha27-2-4 Stahování map (12 bodů)


Přes pomalé připojení potřebujeme přenést několik snímků o rozměrech R×S políček. Každý snímek můžeme přenést buď samostatně nezávisle na ostatních, pak nás jeho přenesení stojí R · S času, nebo jako diferenci od jiného, již přeneseného snímku. V takovém případě se přenášejí jen rozdílná políčka, ale je nutné počítat s režií přenosu W navíc (například proto, že nestačí jen přenést hodnotu na políčku, ale musíme ještě udat jeho souřadnice, tedy posíláme tři čísla namísto jednoho).

Konkrétně, pokud bychom chtěli snímek Ai přenést jako diferenci oproti již přenesenému snímku AjDij by nám vyjadřovalo počet rozdílných políček obou snímků, pak by náklady na přenos Ai byly Dij · W.

Na vstupu dostanete počet snímků N, jejich rozměry R a S, režii přenosu W a pak všech N snímků. Vaším cílem bude uspořádat snímky v nějakém pořadí a u každého zvolit, jestli se má přenášet celý, či jako diference od nějakého zvoleného snímku, aby celkové náklady na přenos byly nejmenší možné.

Při řešení úlohy předpokládejte N ≤ 500, R, S ≤ 20.

Lehčí variantaLehčí varianta (za 4 body): Řešte stejnou úlohu, ovšem s omezením N = 3.

Řešení

„Tohle je všechno správně…“ vzdychl jeden z techniků po prohlédnutí stažených družicových snímků. „Scud přilétl skoro přímo doprostřed zorného pole Patriotu, takže ho musel detekovat. Baterie protistřel se také aktivovala, ale pak už od řídícího systému nedostala finální zaměření a pokyn k odpalu.“

„Dobře. Zkuste se podívat na jakákoliv hlášení související s chybami a údržbou systému Patriot za poslední dva měsíce,“ rozkázal poručík jednomu z desátníků. „My zatím zkusíme prozkoumat instrukční sadu, jestli není chyba v ní,“ dodal ke zbytku týmu.


Praktická opendata úloha27-2-5 Nejdelší příkaz (12 bodů)


Nervovým centrem každého systému Patriot je řídící počítač s několikanásobnou zálohou. Při zkoumání důvodů problému již technici vyloučili fyzické selhání počítačů, a tak padl jejich zrak na software.

Při programování se používá specifický programovací jazyk, ve kterém se jednotlivé příkazy skládají z posloupnosti klíčových slov. Každý příkaz může začít libovolným klíčovým slovem, ale každé navazující klíčové slovo může vzniknout jen vložením jednoho písmene do předchozího (posloupnost UA,DUA,DUHA,DUCHA je korektní, ale posloupnosti DUA,DUCHA ani DUA,DUHA,DUHY již ne).

Techniky by zajímalo, jaký nejdelší příkaz (co do počtu klíčových slov) lze v jazyce sestavit a jestli náhodou touto délkou nepřekročí délku vestavěného příkazového zásobníku, a nemůže tak způsobit systémové selhání.

Toto je praktická open-data úloha. V odevzdávacím systému si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: První řádek obsahuje počet klíčových slov, na dalších řádcích jsou uvedena jednotlivá klíčová slova. Slova se mohou opakovat.

Formát výstupu: První řádek obsahuje délku nejdelšího příkazu, na dalších řádcích jsou vyjmenována klíčová slova tohoto příkazu. Pokud je nejdelších příkazů více, vypište libovolný z nich.

Ukázkový vstup:
6
abc
aba
aa
b
bc
dacb
Ukázkový výstup:
3
b
bc
abc

Řešení

„Program se zdá v pořádku, budeme si tedy muset ušpinit ruce,“ řekl znaveně poručík a odvedl svůj tým techniků ven k lehce poškozenému radaru. „Zkusíme zjistit, jestli jsou všechny části systému na svých místech a komunikují spolu.“

„Ale pane, to bude hrozně moc práce, rozebrat to a prověřit každý kabel nám bude trvat dny!“ „Máte snad lepší nápad?“ zeptal se Blair. Mladý desátník se chvíli zamyslel, pak odběhl dovnitř, vytáhl ven jeden z počítačů a přinesl kupu propojovacích kabelů.

Ilustrace: Hrocha s kufrem

„Můžeme zkusit do jednotlivých uzlů systému vysílat signály a sledovat, za jak dlouho se dostanou do jiných. To by nám mělo dát odpověď na to, jestli jsou spoje v pořádku.“


Teoretická úloha27-2-6 Testování odezvy (14 bodů)


Technici naměřili na propojeném počítačovém systému, sestávajícím z N uzlů, jak dlouho trvá signálu dostat se z každého uzlu do každého jiného. Systém je tvořený propojenými dráty, a vyslané signály tak mohou volně procházet skrz celou síť, jen jim překonání každého drátu trvá určitý čas.

Z provedeného měření jsme dostali čtvercovou matici A o rozměrech N×N. Vaším úkolem je sestrojit ohodnocený strom o N vrcholech, v němž vzdálenost mezi vrcholem i a vrcholem j odpovídá hodnotě Aij, nebo říct, že žádný takový strom neexistuje.

Například pro matici

abcde
a011512
b102613
c120613
d56607
e12131370

je výsledkem následující strom:

Naopak si snadno rozmyslíte, že pro matici

abc
a012
b1010
c2100

řešení neexistuje.

Lehčí variantaLehčí varianta (za 6 bodů): Řešte úlohu s předpokladem, že strom, kterému matice odpovídá, je neohodnocený (tj. každá jeho hrana má jednotkovou délku).

Řešení

Když vyšetřovací tým vyloučil softwarové selhání i nefunkčnost radaru, začali být skutečně bezradní. Vtom ale do místnosti vešel desátník, kterého Blair poslal zkoumat stará hlášení, a nesl v ruce desky s jednou zprávou. Bez vysvětlení je podal poručíkovi a Blairovy oči se rozšířily, když mu došlo, co právě objevili.

Byla to zpráva z jedné izraelské základny stará asi dva týdny. Naměřili tam, že po osmi hodinách provozu se střed zaměřovací oblasti Patriotu při přesnějším módu odchýlil o zhruba dvacet procent od místa, kde se reálně nacházela sledovaná střela. Taková odchylka ještě systému nevadila, ale zpráva uváděla, že se tím začal zabývat výrobce protiraketového systému.

Rychlé prolistování skrz hlášení z místní základny odhalilo to, že v tomto případě byl systém Patriot v nepřetržitém provozu skoro 100 hodin – a to už vadilo.

Interně si totiž Patriot počítal čas od svého spuštění jako celé číslo, ale při výpočtu dráhy střely a odhadu místa, kam by měl zaměřit přesnější režim sledování, si rychlost cíle a čas přepočítával do 24-bitového čísla s plovoucí desetinnou čárkou. A jelikož bylo po 100 hodinách provozu číslo udávající čas již příliš veliké, převod do floatu a následný výpočet vyústil v odchylku zaměření skoro 600 metrů.

Systém Patriot tak správně zaregistroval blížící se Scud, připravil protistřelu k odpalu a přepnul se do přesnějšího módu. Kvůli špatnému výpočtu však útočící střelu v přesnějším módu již neviděl, zkrátka proto, že se díval na špatné místo. Co systém nevidí, to nemůže sestřelit, a tak ani nebyla odpálena žádná protistřela.

Nejvíce ironické na celém incidentu je to, že softwarová oprava Patriotu, na které firma pracovala již od izraelského hlášení, dorazila do Dhahranu o den později. Dorazit o den dříve, tato katastrofa by se vůbec stát nemusela…

Příběh pro vás převyprávěl

Jirka Setnička


Seriálová úloha27-2-7 Shellové skripty (12 bodů)


V minulém dílu jste se naučili pár základních příkazů shellu. Víte, jak vypadá adresářová struktura systému, a umíte si trochu hrát se soubory. Po přečtení tohoto dílu seriálu byste měli být schopni použít shell jako plnohodnotný programovací jazyk. Naučíte se vytvořit skript, používat proměnné a podobné věci.

Skripty

Možná víte, že programovací jazyky se dají rozdělit na kompilované a interpretované. Programem v interpretovaném jazyce je samotný zdrojový kód, který si interpret přečte a provede. A protože je shell mocný nástroj, umí sloužit jako interpretovaný jazyk.

Skript je tedy obyčejný textový soubor, který obsahuje příkazy pro shell. Otevřete si svůj oblíbený editor a v něm třeba soubor skript.sh. Koncovka souboru není rozhodně nutná, název souboru je informací jen pro uživatele. Do něj můžete napsat třeba toto:

echo "Jsi v adresáři:"
pwd

Věřím, že poznáte, co skript dělá. Pokud ne, můžete ho zkusit spustit:

hroch@ksp:~$ bash skript.sh
Jsi v adresáři:
/home/hroch

Takto spustíme nový shell. Pokud dáme shellu jako první poziční argument existující soubor, spustí jej. To je pěkné, ale není to „program“. Aby šlo skript spouštět samostatně, musíte ještě pár věcí zařídit.

Minule jsme si říkali, že soubory mají nějaká práva. Podrobnější rozepsání očekávejte v príštích dílech, dnes jen krátce. Každý soubor má různá práva pro svého vlastníka, skupinu a ostatní. Tři základní práva jsou Read, Write a eXecute, neboli čtení, zápis a spuštění. Aby byl shell ochoten soubor spustit, musíte mít právo spuštění a samozřejmě čtení.

Na změnu práv souboru použijte příkaz chmod. V prvním argumentu lze říct o jaká práva jde, dalšími jsou pak změněné soubory. Následující příklad učiní náš skript spustitelným:

hroch@ksp:~$ ls -l skript.sh
-rw-r--r-- hroch ksp 29 1. říj 12:00 skript.sh
hroch@ksp:~$ chmod +x skript.sh
hroch@ksp:~$ ls -l skript.sh
-rwxr-xr-x hroch ksp 29 1. říj 12:00 skript.sh

Ještě musíme říct systému, čím že to má skript spustit. Doplňte tuto konstrukci na první řádek souboru:

#!/bin/bash
Za normálních okolností značí mříž (#) na začátku řádku komentář, spolu s vykřičníkem na prvním řádku ale říká, jaký program se má spustit k interpretaci daného souboru. Takto už systém ví, že má použít program /bin/bash, tedy bash.

Při psaní příkazu v shellu jsme zatím první slovo na řádku označovali jako příkaz. Není to ale úplně pravda – prvním slovem je název souboru nebo interní příkaz shellu. Shell má několik adresářů, ve kterých programy hledá, pokud nejsou zadány s cestou. Jedním z nich je určitě /bin, takže když napíšete jen „bash“, shell si domyslí /bin/ a spustí /bin/bash.

Pokud ale dáte na začátek řádky soubor i s adresou, shell si nic domýšlet nebude a zadaný soubor prostě spustí (pokud je spustitelný).

hroch@ksp:~$ /home/hroch/skript.sh

Možná si vzpomenete na všudypřítomný adresář . (tečka). Teď si ukážeme, k čemu se dá využít. Pokud byste se pokusili spustit jen příkaz

hroch@ksp:~$ skript.sh
tak se asi nic nestane. Většina shellů z bezpečnostních důvodů nehledá spustitelné soubory v aktuálním adresáři. Je tedy nutné shellu zadat plnou cestu k souboru – no a abychom nemuseli psát celou cestu, použijeme adresář tečka. Ten totiž odkazuje na adresář, ve kterém je umístěn. Můžeme toho využít i zde:
hroch@ksp:~$ ./skript.sh
Ilustrace: Hroch

Procesy

Na chvilku odbočíme od skriptování k samotnému UNIXu. Jistě jste si všimli, že v systému může běžet více programů současně. Dokonce můžete spustit jeden program dvakrát, třeba s jinými parametry. Jak tohle systém dělá?

Každý běžící program je zabalen do struktury, které říkáme proces. V ní najdeme například PID (Process ID, identifikátor procesu). To je nějaké číslo, unikátní pro každý běžící proces. Jakmile dojdou volná PID, systém vám již nedovolí další proces spustit.

Dále si proces pamatuje uživatele, pod kterým běží, stav, ve kterém se nachází, PID svého otce nebo třeba terminál, ke kterému je připojen.

Jak se ale takový proces vytváří? Předně, vyrobit „čistý“ proces není možné. To udělá při startu systému jádro, které spustí program init. Nadále se procesy můžou jen kopírovat.

Takové operaci se říká fork a můžete si ji představit jako rozdvojení. Před zavoláním systémového volání fork jste měli jeden proces, po něm máte dva. Úplně stejné, až na PID. Jednomu zůstane a stává se rodičovským procesem, ten druhý má PID nové a stává se synem.

Pro vypsání procesů můžete použít příkaz ps. Jeho parametry nejsou dané normou, ale něco jako ps ax by mělo vypsat všechny procesy běžící v systému.

Dalším systémovým voláním je exec, kterým se ukončí váš program a nahradí se jiným. Například, pokud v terminálu spustíte program, váš shell provede fork. Tím vznikne kopie shellu, která vzápětí zavolá exec na váš program.

Každý uživatelský proces má tedy svého otce. Může od něj dostat nějaké informace, třeba v paměti před forkem. Zpět je to ale složitější. Dokud oba běží, existují prostředky meziprocesové komunikace. Jak ale oznámit otci „Je mi líto, chyba, končím?“

Když proces ukončí svůj běh, není okamžitě vymazán. Místo toho mu jádro vystaví úmrtní list a čeká, než si ho jeho otec vyzvedne. Pokud mezitím skončil také otec, vyzvedne si ho init. Pokud otec běží, ale na svého syna zapomněl, bude syn čekat v paměti navěky. Operaci vyzvednutí můžete najít jako systémové volání wait.

Součastí ukončeného procesu je návratová hodnota. To je jednobajtové číslo (0–255) a jeho interpretace je čistě na otci. Můžete si předávat klidně výsledek nějaké operace, ale k tomu je jeden bajt docela málo. Místo toho se návratová hodnota používá pro signalizaci úspěchu nebo chyby. V UNIXovém prostředí je zvykem, že nula značí úspěch, nenula nějakou chybu.

Proměnné

Když už máme za sebou spuštění prvního skriptu, můžeme se podívat na jeho obsah. Na každém řádku leží příkaz se svými přepínači a argumenty. Jednotlivé příkazy může oddělovat také středník. Jako příkaz může sloužit i shellový skript.

Opravdová legrace začne až s proměnnými. Shell má proměnné z různých důvodů pouze typu řetězec. Nelze s nimi provádět nic zázračného, lze do nich jen zapsat hodnotu nebo naopak proměnnou expandovat (nahradit, použít, …). Tyto dvě operace ale stačí ke všem myslitelným potřebám.

prom=ksp
echo $prom

Na prvním řádku jsme do proměnné prom přiřadili „ksp“. Důležité je, že před rovnítkem není mezera – podle toho shell pozná, že chceme přiřadit do proměnné a ne spustit příkaz prom. Všimněte si také, že součástí názvu proměnné není znak $.

Na druhém potom spouštíme příkaz echo. Znak $ říká „vlož sem proměnnou“. Shell nejprve vyhledá odpovídající proměnnou a vloží ji na dané místo ještě před spuštěním příkazu.

Tomuto procesu se říká expanze a popíšeme si jej přesněji. Na začátku má shell řádku, která mu byla zadána. Tu rozdělí poprvé na slova, posloupnosti nebílých znaků, případně části ohraničené uvozovkami. Poté provede nahrazení složených závorek {} a tildy ~ (viz minulý díl). Pak přijdou na řadu proměnné. Bash nabízí spoustu rozšíření expanze proměnných, odvážným doporučuji podívat se do manuálu. Neexistující proměnné jsou prázdné řetězce.

Ilustrace: Chip

Další krok expanze si popíšeme podrobněji. Často se hodí si někam schovat výstup nějakého příkazu. Už to umíte se soubory. Bez souborů to lze s použitím jedné z těchto dvou konstrukcí pro substituci výstupu:

cas=`date`
cas=$(date)
Zpětný apostrof (backtick) je kratší a používanější zápis, má ale několik nevýhod. Ty se projeví zejména pokud plánujete volání zanořit, jako v následujícím, trochu umělém, příkladě:
cas=`date +\`cat format-\\\`date +%Y\\\`\``
cas=$(date +$(cat format-$(date +%Y)))
Ten nejprve zjistí, jaký je rok, poté přečte soubor, např. format-2014, a jeho obsah použije jako formátovací řetězec pro příkaz date. Zpětné apostrofy se musí escapovat, a escapovací lomítka na druhé úrovni také. Kolik zpětných lomítek musíte použít v třetí úrovni?

V dalším postupu expanze se jednotlivé shelly liší. Společné je jen další rozdělení výsledků předchozích expanzí na slova. Na to pozor, kdekoli použijete proměnnou, její obsah se znovu rozdělí. Pokud chcete použít obsah proměnné jako jeden argument, je potřeba zapsat ji jako "$prom", nestačí jen $prom.

Následně proběhne vyhodnocení wildcardů a odstranění escapovacích zpětných lomítek. Až na konci tohoto procesu shell vezme první slovo, spustí jej a předá zbylá slova jako argumenty.

Ilustrace: Žonglující hroch

Teď už si můžeme říct pořádně, jaký je rozdíl mezi použitím uvozovek ", apostrofů ' a ničeho. Pokud napíšete text jen tak, použijí se všechny expanze. V uvozovkách se ztrácí význam všech speciálních znaků vyjma $, ` a \, takže se použijí jen expanze proměnných a substituce výstupu. V apostrofech nemá speciální význam vůbec nic, dokonce ani zpětné lomítko. Napsat apostrof do literálu v apostrofech tedy nelze.

echo 'Napsat apostrof ('\'') není snadné.'

Důležitý je rozsah platnosti proměnných. Každá proměnná, kterou ve skriptu máte, je viditelná jen a pouze pro váš skript. Nepřežije konec skriptu a nepředá se do vnořených spuštěných příkazů. To druhé lze změnit tzv. exportem proměnné.

Pomocí interního příkazu export prom zařídíte, že obsah proměnné prom bude dostupný i v programech, které spustíte zevnitř vašeho skriptu.

Naopak, proměnné z „vnějšku“ budou dostupné jako tzv. proměnné prostředí. V shellových skriptech se jejich obsah dostane do vnitřních proměnných, např. v C se k nim dá přistoupit pomocí funkce getenv.

V souvislosti s rozsahem platosti proměnných se hodí příkaz source, který provede vložení. Pokud nějaký skript zavoláte, dostanete z něj pouze výstup a návratovou hodnotu – není způsob, jak by mohl předat obsah proměnných. Pokud jej ale vložíte, spustí se jeho obsah ve stejném procesu. Má tedy přístup ke všem proměnným vašeho programu a obráceně.

K nahlédnutí do proměnných prostředí se dá použít příkaz env. Pokud chcete spatřit i neexportované proměnné, pomůže interní příkaz set.

Dále má shell spoustu magických proměnných:

  • $0 obsahuje název skriptu tak, jak byl volán
  • $1$9 poziční argumenty
  • $# počet argumentů
  • $* a $@ všechny argumenty (rozdíl níže)
  • $$ identifikátor procesu shellu
  • $IFS znaky používané pro oddělení slov v konečné fázi expanze

$* a $@ jsou obě zkratkou za vypsání všech pozičních argumentů, jen se každá chová jinak podle uvozovek:

$*, $@ $1 $2 $3
"$@" "$1" "$2" "$3"
"$*" "$1c$2c$3", kde c je první znak IFS

Výchozí hodnota proměnné IFS (z angl. Internal Field Separator) je mezera, tabulátor a nový řádek. Díky tomu se chová dělení na slova před expanzí stejně jako po ní. IFS ale můžete změnit a tím si upravit chování některých příkazů k obrazu svému – nebo taky způsobit divné chování shellu.

Řídící struktury

Shell samozřejmě poskytuje běžné řídící struktury jako podmínky a cykly. Způsob, jakým to dělá, je ale poněkud… nezvyklý.

Začněme podmínkou. Její syntax je:

if cmd; then ...; else ...; fi
Část else je nepovinná. Důležitý poznatek – shell nemá nic jako číselnou, natožpak logickou proměnnou. Nemá tedy ani nic jako výraz v podmínce. Místo toho se větev then provede tehdy, když byl příkaz cmd úspěšný, neboli vrátil nulu. Ještě jednou pro jistotu – za if se píše příkaz.

Velmi důležitý je příkaz test, který umožňuje porovnávat svoje parametry, a to dokonce i v číselném kontextu. Užitečný je jeho manuál, určitě se do něj podívejte (man test). Pár používaných testů:

neprázdnost: test -n "$prom"
řetězce: test "$USER" = "hroch"
čísla a = b: test "$$" -eq 1
      a ≥ b: test "$a" -ge "$b"
existence souboru: test -f "$file"
          adresáře: test -d "$file"

Příkaz test ale v mnoha zdrojových kódech nenajdete. Existuje na něj totiž alias, který vypadá přirozeněji – příkaz [. Pokud ale test voláte tímto jménem, musí být jeho posledním argumentem ].

if [ "$i" -ge "$j" ]
Z principu fungování podmínky a příkazu test je nutné všechny části oddělit mezerou. Nezapomeňte na uvozovky okolo proměnných – bez nich to sice zpravidla bude fungovat, ale jinak, než byste chtěli. Příkaz test je většinou jak samostatný program, tak interní příkaz shellu, to aby se kvůli každé podmínce nemusel spouštět další proces.

Syntaxe cyklů je v jistém smyslu podobná.

while cmd; do ...; done
Opět, cyklus se opakuje, dokud příkaz cmd vrací nulovou návratovou hodnotu. Místo negace existuje cyklus until. Pokud byste chtěli něco jako do-while, ten se v shellu dělá těžko.

Zajímavější je cyklus for. Neprve ukázka:

for i in 1 2 3 4 5; do ...; done
Cyklus iteruje přes seznam argumentů, které do proměnné postupně dosazuje. Může se to zdát nepraktické, ale vzpomeňte, co všechno umí shell udělat při expanzi.

Pokud vynecháte in a seznam slov za ním, bude for iterovat přes poziční argumenty.

Úkol 1 [2b]

Vypište názvy těch souborů v pracovním adresáři, které jsou prázdné.

Další užitečnou konstrukcí je něco, co připomíná switch z klasických programovacích jazyků. Protože ale shell pracuje jen s texty, umožňuje vybírat mezi variantami podle tvaru řetězce:

case "vstup" in
	vzor) ... ;;
	vzor1|vzor2) ... ;;
	[a-z]) ... ;;
	*) ... ;;
esac

Shell postupně zkouší, jestli vstup neodpovídá některému ze vzorů, a vybere první splňující větev. Vzory jsou klasické shellové wildcardy. Je možno jich uvést více, jako na druhém řádku, a vzájemně je oddělit svislou čarou.

Ve vzorech můžete použít většinu expanzí (proměnné, ", wildcardy, …). Každou větev musíte ukončit jedním z operátorů ;; a ;&. První jmenovaný ukončí zpracovávání case, tedy již nespustí žádnou větev, kdežto po druhém bude shell pokračovat v porovnávání. Expanze vzorů probíhá až těsně před porovnáním.

Protože pravá zavírací závorka rozbíjí jednoduché zvýrazňování syntaxe, je možno v dnešních shellech před vzor napsat nepovinnou závorku do páru.

Na co nesmíme zapomenout, jsou operátory && a ||, můžeme číst jako and a or. Používají se místo oddělovačů příkazů, tedy tam, kde byste použili rouru nebo středník.

Podstatné je, že se vyhodnocují zkráceně. To znamená, máme-li seznam příkazů spojených &&, spouštějí se po sobě a první, který vrátí nenulu, sekvenci ukončí. Naopak, posloupnost příkazů spojených || ukončí první úspěšný příkaz.

Dají se využít k příjemnému podmínění vykonání příkazů:

[ -f soubor ] && ...
mkdir .lock || exit

Zejména druhý příklad si zapamatujte, mkdir vrátí nulu tehdy a jen tehdy, pokud adresář neexistoval a podařilo se ho vytvořit (znovu připomínáme, že ve světě UNIXu značí nulová návratová hodnota úspěch). Dá se tedy dobře použít jako virtuální zámek.

Pokud byste potřebovali návratovou hodnotu příkazu negovat, můzete tak učinit připsáním ! před příkaz. Vykřičník a příkaz ale musí být dvě oddělená slova, musí mezi nimi být mezera.

Úkol 2 [3b]

Napište skript, který vypíše všechny své argumenty v opačném pořadí, než v jakém je dostal.

Složený příkaz

Kdekoli, kde je možno spustit jeden příkaz, je možno místo toho použít příkaz složený. Příklad použití:

{
	echo "Soubor 1:"
	cat s1
} >s2
Zde se výstup celého složeného příkazu zapíše do souboru s2. Možná jste viděli i použití s kulatými závorkami místo složených. S těmi se vnitřní příkazy spustí v tzv. subshellu. V subshellu se spustí příkaz i pokud do něj nebo z něj vede roura, pokud je spuštěn ve zpětných apostrofech nebo pokud jej spouštíte na pozadí.

To znamená, že shell provede fork, a obsah závorek provede v synovském procesu. Přesměrování vstupů a výstupů tedy provádíte na nové instanci shellu. V subshellu nelze nijak ovlivnit prostředí shellu otcovského, všechny proměnné jsou lokální pro subshell. V kontextu subshellu obsahuje proměnná $$ id procesu otcovského shellu, přestože jde o jiný proces.

Vstup

Do proměnné lze snadno vložit obsah souboru, ale jak do ní přečíst vstup? Na to je k dispozici příkaz read.
echo prvni druha | {
	read prom1 prom2
	echo "prom1: $prom1"
	echo "prom2: $prom2"
}

read přečte řádek ze standardního vstupu, rozdělí jej na slova podle IFS, první slovo vloží do první proměnné, druhé do druhé a tak dále.

Pokud je méně slov na vstupu než proměnných, zbylé proměnné se vyprázdní. Pokud je tomu naopak, do poslední se uloží celý zbytek řádku bez oddělovačů na konci.

Úkol 3 [1b]

Poslední příklad by bez složených závorek jen tak nefungoval. Proč je musíme použít?

Úkol 4 [3b]

Pro každého uživatele z /etc/passwd vyrobte v aktuálním adresáři soubor, jehož název bude odpovídat uživatelskému jménu daného uživatele. Obsahem tohoto souboru budiž uživatelův výchozí shell. O struktuře /etc/passwd se dočtete v manuálu, man 5 passwd.

Úkol 5 [3b]

Napište skript, který bude zpracovávat textový log příchodů na velké setkání KSP. Řádky obsahují akce (prichod/odchod), pohlaví (M/F) a pak jméno (jednoslovné nebo i víceslovné), oddělené mezerou. Úkolem skriptu bude načíst tento soubor a každý řádek vypsat hezky ve tvaru „Prisla Jana Novakova“, „Odesel Petr“ a podobně. Dávejte pozor na správný tvar prvního slova podle pohlaví.

Závěr

Abychom si připomněli a ujasnili, jaké věci jsme se dnes naučili a jaké můžete použít v řešení jednotlivých úkolů, zde je jejich přehled:

  • Psaní a spouštění skriptů (adresář tečka)
  • Vytváření a život procesů v UNIXu (fork, exec, PID)
  • Proměnné (proměnné pro argumenty, $IFS)
  • Řídící struktury (if, else, while, for, case)
  • Příkaz test a &&||
  • Složené příkazy a read.

V dalším pokračování se můžete těšit na některé pokročilejší UNIXové příkazy, jež vám umožní třeba třídit a filtrovat velká data jen pár stisky kláves. Doufáme, že nám zachováte přízeň i nadále.

Ondra Hlavatý

Řešení