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

Celý leták, který posíláme také papírově, v PDF.

• Termín série: 1. června 2015 8:00
• Termín CodExové úlohy: 2. června 2015 8:00
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Každému, kdo z úloh této série získá alespoň 42 bodů, pošleme čokoládu.

Zadání úloh

• 27-5-1: Šíření poplašné zprávy
• 27-5-2: Survivalisté
• 27-5-3: Čekání na poště
• 27-5-4: Školení zaměstnanců
• 27-5-5: Kniha přání a stížností
• 27-5-6: Autobazar
• 27-5-7: Shellová automatizace

27-5-1 Šíření poplašné zprávy (10 bodů)

Firma, ve které pracuje Karlova matka v Anglii, má spoustu kanceláří a místností v jedné velké budově.

Jednou za čas tam testují poplašný systém. Z centrály mohou zavolat telefonem naráz do dvou kanceláří poplašnou zprávu „Hoří, všichni rychle opusťte budovu!“. Nato z daných kanceláří vyběhnou zaměstnanci do všech sousedních kanceláří a tam jim předají tuto zprávu. Všichni doběhnou ve stejném okamžiku, tomu celému můžeme říkat třeba jeden takt. V dalším taktu i z těchto kanceláří vyběhnou zaměstnanci do všech sousedních kanceláří, ve kterých se ještě o zprávě nedozvěděli, a tak dál.

Při poplachu se ale smějí používat pouze chodby a schodiště označené symbolem zeleného utíkajícího panáčka, to jsou ty, které vedou k únikovému východu. Tyto chodby tvoří neorientovaný strom.

Nás by zajímalo, do kterých dvou kanceláří máme zavolat, aby se zpráva rozšířila co nejrychleji po celé budově.

Řešení

27-5-2 Survivalisté (12 bodů)

Tito lidé (říká se jim survivalisté) si v supermarketu nakoupili velké zásoby trvanlivých potravin, aby v následující krizi přežili co nejdéle. Teď si krátí čas při čekání na autobus tím, že si navzájem ukazují, co si kdo koupil. Postávají v hloučcích, podávají si konzervy, balíčky nebo lahve, a ochutnávají.

Žádný z nich ale nechce podat svou věc úplně každému. Například jsou mezi nimi lidé, kteří se neznají, kteří odmítli ochutnat nabízenou věc nebo patří k jiné skupině, než k té, se kterou budou trávit konec světa v bunkru a následně obnovovat lidskou populaci. Takoví lidé se spolu nebaví a věci si nepůjčují. Survivalisty tedy můžeme popsat orientovaným grafem, z každého survivalisty vede hrana do těch, kterým je ochoten věc podat.

Teď každý člověk vytáhne z tašky jednu věc a předá ji někomu jinému, aby ji ochutnal. Zároveň ale chce, aby někdo jiný podal nějakou věc jemu. Na vás je, abyste rozhodli, zda je toto možné.

Například survivalisté na následujícím obrázku si takto věci předávat nemohou. Pokud bychom však přidali hranu E →D, už by předávání mohlo proběhnout.

Řešení

27-5-3 Čekání na poště (9 bodů)

Když je na poště tolik lidí, že není snadné poznat, kde fronta začíná a kde končí nebo kdo je za kým na řadě, rozmístí na podlahu sloupky a natáhnou mezi nimi pásku. Na začátku a na konci fronty je samozřejmě mezera, kterou se prochází, ale pro jednoduchost si představme, že i tam je páska, i když pomyslná. Sloupky a páska tak tvoří mnohoúhelník, který neprotíná sám sebe. Lidé čekají uvnitř tohoto mnohoúhelníka.

Váš program dostane na vstupu rozmístění sloupků, tedy N bodů v rovině (nebudou tvořit přímku). Na vás je, abyste z nich vytvořili mnohoúhelník, který neprotíná sám sebe.

Formát vstupu: Na prvním řádku dostanete číslo N, tedy počet bodů. Poté následuje N řádků, kde na každém bude mezerou oddělená x-ová a y-ová souřadnice jednoho bodu. Pro všechny vstupy platí 3 ≤ N ≤ 250 000, 0 ≤ x, y ≤ 1 000 000.

Formát výstupu: Výstupem programu bude jediný řádek obsahující čísla bodů oddělená mezerami seřazená podle výskytu na obvodu mnohoúhelníka. Body jsou číslované od nuly podle pořadí na vstupu.

Pozor, výstup nemusí být jednoznačně určený (vypište libovolný korektní).

6
0 0
2 0
1 2
1 1
0 1
2 1

0 4 2 5 1 3

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

Řešení

27-5-4 Školení zaměstnanců (10 bodů)

Pošta, jako každá firma, má hierarchickou strukturu zaměstnanců, a tato struktura tvoří strom.

Manažeři ze školícího oddělení čas od času vysílají některé zaměstnance na speciální školení, kde se naučí, jak se vypořádat s určitými situacemi, které někdy mohou nastat, ale nejsou tak obvyklé, aby školení využil každý zaměstnanec. Navíc zjistili, že pro zaměstnance je jednodušší se nové věci dozvídat od svých kolegů než se ptát úplně cizího odborníka. A počítají i s tím, že vyškolení se budou chlubit novými znalostmi kolegům, a tak se informace snadno rozšíří po celé firmě.

Konkrétně si řekli, že by bylo dobré, aby se každý zaměstnanec mohl obrátit k vyškolenému zaměstnanci, který prošel například týdenním kurzem razítkování dopisů, přes méně než K spolupracovníků. To znamená, že každý vrchol stromu musí ležet do vzdálenosti K od nějakého zaměstnance, který prošel školením.

Na vás je, abyste pro zadaný strom a číslo K vybrali co nejméně vrcholů tak, aby každý vrchol stromu ležel do vzdálenosti K od jednoho z vybraných vrcholů.

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í

27-5-5 Kniha přání a stížností (12 bodů)

Jistý pan Václav šel na poštu pro důchod. Byl velice rozladěn, že pošťačkám tak dlouho trvá poslat nějakou složenku a mezitím neobsluhují ostatní zákazníky, že si vyžádal knihu přání a stížností a napsal tam hodně dlouhý text o tom, co si o nich myslí a kam s těmi službami mají zalézt. A nepoužíval přitom nijak slušná slova.

Na vás je, abyste jeho text zkultivovali. Jinými slovy, váš program dostane seznam zakázaných slov, která by se v této situaci neměla používat (slovo je posloupnost symbolů z nějaké abecedy), a vstupní text (to je vlastně také slovo, jen obvykle trochu delší). Máte ze vstupního textu vymazat všechna zakázaná slova (to znamená podslova ze vstupního textu, která jsou zakázanými slovy), ale ani písmenko navíc!

A pozor, tím, že vymažete zakázané slovo, může vzniknout jiné zakázané slovo. To musíte vymazat také. Máte ale zaručeno, že žádné zakázané slovo není prefixem ani suffixem jiného zakázaného slova. Pokud nastane více možností mazání, vymažte to slovo, které končí dříve.

Vstupní text: aaaaaabbbbbbc
Zakázaná slova: aaaaaaa, ab

c

Řešení

27-5-6 Autobazar (10 bodů)

Autobazar, to je jedna dlouhá, dlouhá řada aut. Modré, červené, červené, černé, zelené, fialové, červené…Karel si vzpomněl na hru, kterou někdy hrají děti v autě. Každý počítá jednu svou barvu aut, která potkávají, a kdo jich má nejvíc, vyhraje.

Karla by zajímalo, zda je v autobazaru nějaká barva v nadpoloviční většině, aby s ní tu hru vyhrál proti komukoliv.

V tomhle autobazaru je ale těch barev hodně, taková červená s oranžovým víkem kufru je něco jiného než červená s rezatým nárazníkem. Barvami byste nemohli indexovat paměť počítače.

A těch aut je ještě víc. Takové dlouhé číslo, které udává počet aut, by se vám také nikam nevešlo. Jinými slovy máte k dispozici jenom konstantně mnoho paměti. Můžete ale (i víckrát) procházet řadu aut a dívat se, jakou mají barvu.

Popište postup, jak zjistit, zda je v posloupnosti barev délky N alespoň N/2 výskytů nějaké barvy. Použít smíte ale jen konstantní paměť a lineární čas.

Řešení

Bohužel, měli zavřeno. Cedulky s cenami dával na auta člověk a ten tu chybu odhalil dřív, než nějaké auto prodali. Jejich program totiž měl nějaká kritéria, jak určovat ceny aut. A tím prvním byla doba od poslední technické kontroly. On věděl, že je rok 2000, ale myslel si, že technická prošla krátce po roce 1900, a tak ta stará auta doporučoval prodat za pár korun.

Poté ještě Karlově stoleté prababičce přišla pozvánka na kojeneckou prohlídku, tím byl konec s problémem roku 2000. S programátorskými chybami ale bohužel konec jenom tak nebude. Chyby dělají lidé, ne zlomyslné počítače, a lidskou chybu nemůžete úplně vyloučit, dokud z programování nevyloučíte lidský faktor.

Důležité je se z chyb poučit. K podobnému problému by mohlo v budoucnu dojít ještě jednou. Mnohé programy používají znaménkový 32-bitový typ, který reprezentuje čas jako počet vteřin od 1. 1. 1970, a ten přeteče 19. ledna 2038. Ale pokud do té doby začnou používat 64-bitový typ, přesouvá se problém do roku 292 277 026 596.

To ale neznamená, že nemáte řešit KSP. S chutí do toho!

Příběh vyprávěl

Dominik Macháček

27-5-7 Shellová automatizace (15 bodů)

Poslední díl letošního seriálu o UNIXu a jeho příkazovém řádku se ponese v duchu automatizace úkonů a lepšího provázání našich skriptů se systémem. Ukážeme si třeba, jak lze spustit stejný příkaz na všech souborech nějakého typu, jak v nějakém složitějším procesu zpracování dat (nebo třeba kompilace programů) zpracovávat jen to, co ovlivní změněné soubory, a také jak například zajistit, aby déle běžící skript po sobě uklidil, pokud se ho rozhodneme ukončit v průběhu práce.

Všechno to jsou drobné pomůcky, které nám krásně zapadnou do všeho ostatního, co jsme se přes rok naučili, a pomohou vám ještě lépe využívat sílu shellu. Pokud se tedy nebojíte, račte vstoupit.

Hledání souborů

V minulých dílech jsme vám ukázali, jak třeba pomocí wildcardů vybrat všechny soubory v aktuální složce s příponou .pdf. To pomocí nich umíme jednoduše, horší to ale začíná být ve chvíli, kdy chceme prohledat rekurzivně třeba i všechny podsložky včetně jejich podsložek a tak dále.

Asi by se dal napsat nějaký skript, který by si nechal vypsat příkazem ls všechny složky a na nich by se zavolal znova, ale existuje mnohem snadnější řešení. Zkuste si třeba ve svém domovském adresáři spustit příkaz find.

.
./poznamky.txt
./Obrazky
./Obrazky/Kevin.jpg
./Obrazky/Sara.jpg
./Obrazky/Petr.jpg
./Reseni
./Reseni/KSP
./Reseni/KSP/27-5-7.pdf
...

Jak vidíte, find vám vypsal úplně všechny složky a soubory ležící ve stromě souborů pod aktuálním umístěním. Pokud mu totiž nezadáme, jakou složku má prohledávat, tak použije aktuální adresář . (a také ho vypíše jako první prohledaný a připojí ve výpisu před všechny nalezené složky a soubory). Kdybychom ve stejném umístění spustili třeba příkaz find Reseni, výpis by pak vypadal takto:

Reseni
Reseni/KSP
Reseni/KSP/27-5-7.pdf

To je pěkné, na takovýto výstup bychom už mohli použít třeba příkaz grep a vyfiltrovat z něj s trochou práce třeba jen PDF soubory. Ale find to umí sám a ještě spoustu věcí navíc (Dokonce může být vnější filtrování pomocí grepu výrazně pomalejší, protože se mezi těmito dvěma příkazy musí přenést skrz rouru velké množství dat.).

Než se pustíme do dalšího experimentování, tak se na příkaz find podíváme i se všemi jeho skupinami parametrů:

find <kde hledat> <kritéria> <prováděný příkaz>

• První skupina je asi jasná, určuje místo, kde má find začít své prohledávání. Je možné předat i více umístění, find je prohledá všechna. Pokud není žádné umístění zadané, tak se použije aktuální adresář ., jak jsme ukázali výše.
• Druhá skupina parametrů nastavuje různá kritéria omezující výběr souborů a složek. Pokud není nic nastaveno, nefiltruje se nic a vypisují se všechny nalezené složky a soubory. Tím se budeme zabývat vzápětí.
• Třetí skupina parametrů určuje, co se má pak s nalezenými názvy souborů a složek dít. Pokud nezvolíme žádnou akci sami, tak find použije akci -print a vše jen vypíše na výstup. Můžete si zkusit ho s touto akcí na konci jeho seznamu parametrů spustit.

Mezi další jeho akce patří pak třeba formátovaný výpis nebo spuštění nějakého příkazu. Tomu se budeme věnovat po kritériích výběru.

Mocnější find

Co kdyby nás zajímaly všechny README soubory třeba ve složce /etc? V tu chvíli nám stačí použít kritérium -name a spustit příkaz:

find /etc -name README 2>/dev/null

Protože složka /etc obsahuje pravděpodobně několik podsložek, na jejichž čtení nebudeme mít práva, může nám find vynadat několika chybovými hláškami (jednou za každou nepřístupnou složku). Aby se nám výstup mezi těmito hláškami neztratil, je dobré vzpomenout si na minulé díly seriálu a chybový výstup „odfiltrovat“ jeho přesměrováním do /dev/null, jak jsme v příkladu výše rovnou udělali.

Můžete dokonce použít i shellové wildcardy ke specifikování názvu. Jen pozor na to, že wildcardy se musí dostat až k findu, nesmí je tedy zpracovat už samotný shell a tedy je nutné je buď escapovat, nebo zabalit do uvozovek:

find -name "*.pdf"

Pokud by vám nestačily shellové wildcardy, je možné podobným způsobem použít i regulární výrazy, ale už s jiným přepínačem. Následující příkaz najde všechny PDF soubory začínající od písmene a:

find -regex ".*/a[^/]*\.pdf"

Mezi další zajímavá kritéria patří například specifikace typu souboru pomocí přepínače -type (-type d je složka, -type f běžný soubor, více v manuálové stránce). Velmi pěkné je také filtrování podle toho, kdy byl soubor naposledy modifikovaný. Viz následující příklady:

find -mtime 7    # Modifikace v posledním týdnu
find -mmin 10    # Modifikace v posledních 10min

Další možné filtrování je například podle vlastníka nebo podle přístupových práv. Dokonce umí hledat i podle čísla inode, a tedy lze použít k nalezení všech hardlinků na konkrétní soubor (hardlinky jsme zmiňovali ve třetím díle seriálu). Další užitečný přepínač, který sice není standardizovaný, ale Linuxová verze ho podporuje, je -maxdepth 2 omezující hloubku prohledávání.

Závěrem povídání o findu se zmíníme o dalších možných akcích. S defaultní akcí -print jsme se už potkali, ta vytiskne nalezené soubory oddělené znakem nového řádku. Kdybychom očekávali, že se nám může ve filesystému objevit soubor se znakem nového řádku v názvu, mohla by se nám hodit akce -print0, která jednotlivé soubory na výstupu odděluje nulovým bajtem.

Další akce je třeba -delete, které nalezené soubory smaže, -printf, které zvládá tisknout formátovaný výstup, nebo -exec, které spustí daný příkaz pro všechny nalezené soubory. Na jejich použití a na více vyhledávacích kritérií se podívejte do manuálové stránky, zde ukážeme jen jednoduché příklady:

# Otevření všech HTML stránek ve Firefoxu:
find -name "*.html" -exec firefox '{}' \;
# Přidání přípony .txt všem souborům:
find -exec mv {} {}.txt \;

Konstrukce příkazu pomocí xargs

Jak padlo výše, tak find umí spouštět pro každý nalezený soubor nějaký příkaz, ale dělá to bohužel pro každý soubor samostatně. Pokud bychom například chtěli všechny takto nalezené soubory smazat, někam zkopírovat, nebo přidat do společného archivu, bude to zbytečně pomalé nebo komplikované.

Tento problém ale řeší příkaz xargs. Ten v podstatě dělá to, že vezme svůj standardní vstup (který může přijít třeba od příkazu find skrz rouru) a použije ho jako argumenty pro zadaný příkaz (tento příkaz samozřejmě musí podporovat proměnlivý počet argumentů).

Smazání všech PDF souborů třeba můžeme v kombinaci s příkazem find udělat takto:

find -name "*.pdf" | xargs rm
find -name "*.pdf" -print0 | xargs -0 rm

Argumenty jsou připojené na konec zadaného příkazu a ten je vykonán. Druhý řádek je bezpečnější, pokud by se nám v názvech souborů vyskytovaly mezery nebo znaky nového řádku, ale jinak dělá úplně to samé. Prostě jen find i xargs přepneme do módu oddělování null-bytem, o kterém z minulých dílů víme, že se v názvu souboru vyskytnout nemůže.

Možná vás ale napadla otázka: Co když nechceme argumenty připojit na konec konstruovaného příkazu? Co když, třeba jako u příkazu cp chceme jako poslední argument mít název složky, do které chceme zkopírovat nalezené soubory?

V takovou chvíli využijeme přepínače -I, kterým příkazu xargs nastavíme výraz, jež pak bude v konstruovaném příkazu nahrazen argumenty. Tradičně se používá výraz {}, ale není problém použít cokoliv jiného. Dva příkazy níže jsou tedy ekvivalentní:

find -name "*.pdf" | xargs -I {} cp {} ~/backup/
find -name "*.pdf" | xargs -I F cp F ~/backup/

Závěrem povíme, že xargs předává argumenty příkazu najednou, pokud jich není moc. Samotný systém má totiž jistá omezení a třeba spuštění příkazu rm * ve složce obsahující příliš mnoho (třeba milióny) souborů už vám neprojde. Příkaz xargs ale tato omezení zná a rozsekává příkazy po správně velkých blocích. Pokud tedy neprojde příkaz výše, stačí spustit find | xargs rm, xargs sám spustí několik příkazů rm a každému předá jen zvládnutelný počet argumentů.

Pokud si nejsme jisti počtem argumentů, které dostaneme na vstupu, a nechceme příkaz spouštět pro nulový počet argumentů, můžeme příkazu xargs přidat parametr -r říkající „naprázdno nedělej nic“.

Úkol 1 [1b]

Spočtěte počet řádek ve všech souborech s příponou .txt ležících přímo v aktuálním adresáři nebo v jeho podadresářích (do libovolné hloubky). Výstupem by mělo být jediné číslo.

Úkol 2 [2b]

Najděte všechny prázdné podadresáře aktuálního adresáře (do libovolné hloubky).

Úkol 3 [2b]

Změňte všem souborům v aktuálním adresáři (nebo jeho podadresářích do libovolné hloubky) s příponou .tvuj příponu na .muj. Myslete i na to, že se v názvech mohou objevit podivné znaky.

Procesy a paralelizace

Pokud jste si na práci v terminálu trochu zvykli a spouštěli jste ve větším množství i nějaké déle běžící programy, možná vás napadlo, že by bylo dobré pouštět je paralelně – nemuseli byste tak čekat, až předchozí skončí. Operační systém samozřejmě umí pouštět víc příkazů, zatím jsme si ale pořádně neukázali, jak na to v shellu.

Dosud jsme se setkali s rourou. Pokud příkazy oddělíme |, shell je spustí současně a správně na sebe napojí jejich vstupy a výstupy. (Detaily si můžete přečíst ve čtvrtém dílu seriálu.) Další příkaz z našeho skriptu ovšem shell vykoná, až když všechny propojené rourou skončí.

Procesy v popředí i na pozadí

Pokud by se však úloha běžící na pozadí rozhodla číst ze vstupu, má problém. Na terminál je už připojený standardní vstup shellu, případně vstup nějaké jiné úlohy běžící v popředí. Úloha na pozadí proto bude zastavena, dokud ji znovu nepustíme.

Pozastavenou úlohu můžeme spustit na popředí pomocí vestavěného příkazu shellu fg (foreground), či na pozadí bg (background). Pokud byla úloha pozastavena, protože chce číst ze vstupu, jejím spuštěním na pozadí ji okamžitě pozastavíme znovu. Příkaz bg ale má stále své využití. I úlohy běžící v popředí totiž můžeme z terminálu snadno pozastavit. Většinou stačí zmáčknout Ctrl+Z. Hned si vysvětlíme, jakým způsobem toto pozastavování funguje.

Připomeňme si ještě, co dalšího o UNIXových procesech víme. Letmo jsme se s nimi seznámili ve druhém díle. Pověděli jsme si, že systém si pro každý proces pamatuje jeho identifikační číslo PID, stav, seznam otevřených souborů, uživatele, s jehož právy běží, a mnoho dalších informací. Seznam všech běžících procesů dostaneme příkazem ps ax. Tyto znalosti využijeme v další části.

Pokud bychom chtěli počkat na dokončení některého procesu běžícího na pozadí, poslouží nám k tomu interní příkaz wait PID. Pokud žádný parametr nedostane, počká jednoduše na všechny podprocesy.

Signály a meziprocesová komunikace

Signál si můžeme představit jako takové malé šťouchnutí. Procesy si je mohou mezi sebou navzájem posílat a tím si vlastně předávat informace. Rozhodně to není způsob, kterým byste chtěli přenášet kilobyty dat (natož více). Signály slouží spíš k upozorňování na asynchronní události. Na běžném dnešním Linuxu jich najdeme 64, na OpenBSD jen 32.

Každý signál má své jméno a číslo. Pozor na to, že různé operační systémy mohou mít přiřazení čísel signálů různé.

A k čemu se signály hodí? Například při vypínání počítače by bylo dobré dát všem programům vědět, že se mají vypnout a případně uložit rozdělanou práci. K tomu se používá signál SIGTERM. Pokud by na to program nereagoval a nechtěl se vypnout, můžeme jeho činnost ukončit natvrdo signálem SIGKILL.

Podobně existují také signály SIGTSTP a SIGSTOP, které způsobí zastavení běžícího procesu a naopak SIGCONT, pro opětovné spuštění. SIGTSTP pošleme procesu právě pomocí stisku Ctrl+Z. Naopak Ctrl+C posílá SIGINT.

Za zmínku stojí ještě SIGHUP a SIGCHLD. Kdykoli nějaký proces skončí, je na to upozorněn jeho rodič signálem SIGCHLD. Stejné upozornění přijde i v případě, že je synovský proces pozastaven, případně znovu spuštěn. SIGHUP má hned několik významů. Tento signál obdrží programy, pokud jim zavřeme terminál, ve kterém běží. Většina aplikací se proto ukončí. U daemonů, programů určených k tomu, aby běžely na pozadí a s člověkem nekomunikovaly pomocí terminálu, SIGHUP obyčejně způsobí znovunačtení konfigurace z konfiguračních souborů.

Chceme-li procesu poslat signál, stačí z shellu zavolat kill [-signál] PID. Pro označení signálu můžeme použít jak číslo, tak název. Pokud signál nespecifikujeme, posílá se SIGTERM. Jako identifikátor procesu můžeme zvolit i -1. Potom je daný signál poslaný úplně všem procesům, kterým můžeme nějaký signál poslat. Signály totiž můžeme posílat pouze svým vlastním procesům. (Jenom root má výjimku a umí signalizovat všem.)

Signály mají za sebou bouřlivou historii a jejich význam se průběžně trochu měnil. Například někdy narazíme na to, že signály nezačínají na SIG. Máme pak INT, TERM, TSTP,…Pokud by vás zajímaly detaily, podívejte se do manuálových stránek man 7 signal. V zásadě můžeme signály dělit podle toho, jestli proces ukončí, ukončí a vytvoří obraz jeho paměti (tzv. core dump), pozastaví, znovu spustí, případně jestli jsou ignorovány a nedělají nic.

U většiny signálů si proces může výchozí chování přenastavit. Jedinou výjimkou jsou SIGKILL a SIGSTOP – ty vždy znamenají to samé. Díky tomu jde každý proces ukončit, případně zastavit. Typicky chceme některé signály ignorovat, nebo odchytit vlastní funkcí. Pokud pak náš proces obdrží signál, operační systém přeruší aktuálně vykonávanou práci a spustí naši funkci. Signály můžeme odchytávat i v shellu.

Číháme na signál

Úkol 4 [3b]

Napište skript, který vám pomůže se smysluplným využitím dnešních vícejádrových počítačů naplno. Váš skript dostane jediný parametr N. Na standardním vstupu pak bude číst podobně jako shell příkazy a bude je spouštět. Řádky by však měl provádět paralelně. Vždy se smí provádět nejvýše N řádek současně.

Proč /proc?

Aby nebylo nutné vytvářet pro zjištění všech možných informací specializovaná systémová volání, vznikl v Linuxu virtuální filesystém /proc. V proc najdeme pro každý spuštěný proces adresář s celou řadou zajímavých souborů. Například v /proc/PID/fd najdeme jako symlinky seznam všech souborů otevřených daným programem. Podrobnosti najdete v manuálu man 5 proc.

Úkol 5 [2b]

Napište malou náhradu programu ps ax. Na výstupu vašeho skriptu by se měl objevit o každém procesu jeho PID, nějaký identifikátor uživatele, příkaz i se všemi jeho parametry a alespoň jeden další údaj podle vašeho výběru. Můžete si vybrat cokoli, co se vám bude zdát aspoň trochu zajímavé či užitečné. Všechna potřebná data čtěte přímo z /proc.

Make – základy

Poslední velký pomocník, kterého si letos ukážeme, je příkaz make. Ten se stará o automatizaci procesu nějaké kompilace, překladu nebo třeba jen zpracování dat. Většinou je řízen souborem s názvem Makefile (všimněte si velkého prvního písmena) v adresáři, kde make zavoláme.

A co že přesně umí? Základem celého procesu je, že se make pokouší splnit nějaké v Makefile definované cíle, což většinou znamená vyrobit nějaké soubory. Pokud Makefile zjistí, že požadovaný cíl ještě neexistuje, zkusí ho podle pravidel uvedených v Makefile vyrobit. Pravidla pro výrobu cíle se v něm zapisují odsazená tabulátorem pod názvem cíle. Takový jednoduchý Makefile tedy může vypadat takto:

datum.txt:
	echo Datum: > datum.txt
	date >> datum.txt

Pokud tedy ve složce s tímto Makefile zavoláme příkaz make datum.txt, tak se provedou příkazy definované výše a vznikne nám tento soubor. Pokud ale zkusíme teď stejný příkaz zavolat znova, tak se už nic neprovede – make už totiž vidí, že je tento cíl splněn (soubor existuje) a že tedy není potřeba nic vyrábět.

Make a závislosti a virtuální cíle

Nejsilnější zbraní, kterou ale make disponuje, jsou závislosti. Dá se prohlásit, že cíl závisí na určitých souborech, například že vyráběný soubor se statistikou závisí na zdrojových datech měření. Když je pak make požádán o splnění nějakého cíle, tak se nejdříve pokusí splnit všechny závislosti.

Pro každou závislost se podívá, jestli neexistuje stejně pojmenovaný cíl, a zkusí ho také splnit. Takto může rekurzivně postupovat prakticky do neomezené hloubky.

Poté, co má nějaký cíl splněné všechny své závislosti, tak se make ještě rozhodne, jestli je nutné provádět i tělo tohoto cíle. Pokud soubor stejného jména, jako je jméno cíle, ještě neexistuje, není proč váhat a tělo se provede. Pokud ale takový soubor už existuje, je to zajímavější. Pak se make podívá na časy modifikace všech souborů, na kterých aktuální cíl závisí, a porovná je s časem modifikace již existujícího souboru.

Když zjistí, že již existující soubor je novější než všechny jeho závislosti, tak není potřeba dělat nic. Pokud se ale nějaká závislost změnila od doby jeho vytvoření (tedy je alespoň jedna závislost s novějším časem modifikace, než má již existující soubor), tak se tělo cíle provede.

Abychom si to ukázali na příkladě, tak uvažujme následující Makefile používaný ke generování seznamu kapitol a nějakých statistik ze sepisované knížky:

all: kapitoly.txt statistika.txt

kapitoly: knizka.txt
	grep "^Kapitola:" <knizka.txt >kapitoly

statistika.txt: knizka.txt kapitoly
	echo Počet řádků > statistika.txt
	wc -l knizka.txt >> statistika.txt
	echo Počet kapitol >> statistika.txt
	wc -l kapitoly >> statistika.txt

clean:
	rm -f statistika.txt
	rm -f kapitoly

.PHONY: all clean

Jako první jste si asi všimli podivných cílů all a clean. Oba jsou to takzvané virtuální cíle, tedy jim neodpovídají žádné skutečně vytvářené soubory, ale slouží pro speciální účely. Aby make nebyl zmaten, kdyby se přece jen objevily soubory tohoto jména, tak mu to raději sdělíme mírně magickou formulí .PHONY: na konci ukázky – ta zajistí to, že make bude stejně se jmenující soubory ignorovat a vyjmenované cíle brát vždy jako virtuální a vždy se provedou jejich těla, jako by soubory neexistovaly.

Nyní můžeme spustit příkazy make all pro výrobu všeho, na čem cíl all závisí, nebo make clean pro odstranění pracovních souborů. Cíl all je navíc uveden jako první proto, že když zavoláme jen make bez cíle, provede se první cíl.

Když jsme teď ukázali pár nových triků, pojďme se vrátit k závislostem. Řekněme, že jsme už provedli make all a máme tedy v adresáři všechny tři soubory. Když teď zavoláme make kapitoly nebo make statistika.txt, tak se nic nestane. Při volání make statistika.txt se sice make rekurzivně zavolá na splnění cíle kapitoly, ale protože ten nevygeneruje žádný novější soubor, tak se neprovede ani tělo cíle statistika.txt.

Pokud ale nejdříve změníme obsah souboru knizka.txt, začne to být mnohem zajímavější. Po opětovném zavolání make statistika.txt se make znovu pokusí obstarat všechny jeho závislosti. Pro soubor knizka.txt žádný cíl nemá a tedy ho bere tak, jak je, ale pro cíl kapitoly cíl existuje a tak se ho pokusí rekurzivně splnit.

Při plnění cíle kapitoly zjistí, že jsou závislosti novější, než je vygenerovaný soubor, a tedy spustí tělo příkazu kapitoly a vygeneruje tak nový soubor. Cíl statistika.txt pak zjistí, že dokonce obě jeho závislosti (soubory knizka.txt i kapitoly) jsou novější, než vygenerovaný soubor, a proto taky spustí své tělo a vygeneruje nový obsah souboru statistika.txt.

Zde je vidět, že make vždy dělá jen tu nejmenší nutnou práci, spouští jen těla těch cílů, jejichž zdroje, na kterých závisí, se změnily. U malého projektu je nám to asi jedno, ale kdybychom třeba make používali k překladu Linuxového jádra a provedli jsme změnu jen v jednom zdrojovém souboru, budeme rádi, že make během několika málo sekund přegeneruje jen to, co potřebuje, a nemusíme tak čekat dlouhé minuty, než by se provedlo přegenerování úplně všeho, i když to nebylo potřeba.

Make a speciální proměnné

Možná vám přijde, že třeba přejmenovat soubor se statistikami v příkladu výše by bylo docela pracné a máte pravdu. Znamenalo by to na spoustě míst přepsat jeho název na něco jiného, hlavně v těle cíle, jež ho vyrábí. Na to má ale make docela pěknou léčbu v podobě speciálních proměnných.

V tělech cílů se dají používat třeba tyto tři základní:

• $@ zastupuje název cíle (jméno vytvářeného souboru)
• $< zastupuje název první závislosti
• $^ zastupuje názvy všech závislostí

Klíčové cíle z dřívější ukázky by se tak daly přepsat třeba takto:

kapitoly: knizka.txt
	grep "^Kapitola:" < $< > $@

statistika.txt: knizka.txt kapitoly
	echo Počet řádků > $@
	wc -l knizka.txt >> $@
	echo Počet kapitol >> $@
	wc -l kapitoly >> $@

Velmi mocným nástrojem je také konstruování obecných cílů. Pokud bychom třeba chtěli mít obecná pravidla, která nám pro každý textový soubor (třeba pro každou knížku, kterou jako úspěšní spisovatelé sepisujeme) vygeneruje statistiku jako výše, můžeme k tomu právě tyto obecné cíle využít.

Obecný cíl vytvoříme tak, že v jeho názvu použijeme zástupnou část reprezentovanou znakem %. Za tu pak make při hledání cílů může doplnit cokoliv chce, ale zástupný znak můžeme použít jen na jednom místě v názvu cíle (nelze například vytvořit cíl KSP-%-5-%.pdf). Můžeme jej pak ale libovolně používat v závislostech (lze tak třeba vyjádřit, že libovolný přeložený program závisí na svém zdrojáku v jazyce C a podobně).

Když zástupný znak použijeme, tak se nám pak pro použití v těle cíle přidává ještě jedna speciální proměnná:

• $* obsahuje to, co se dosadilo za zástupný znak %

Hlavní část tohoto obecného Makefile by tedy mohla vypadat třeba takto:

%-kapitoly: %.txt
	grep "^Kapitola:" < $< > $@

%-stat.txt: %.txt %-kapitoly
	echo Počet řádků > $@
	wc -l $*.txt >> $@
	echo Počet kapitol >> $@
	wc -l $*-kapitoly >> $@

Teď můžeme volat třeba make detektivka-stat.txt nebo třeba make roman-stat.txt a stačí nám jen, aby detektivka.txt a roman.txt existovaly.

Někdy se nám dokonce může hodit mít nějaké obecné pravidlo a pak pro jednotlivé soubory přidávat závislosti navíc. Pokud uvedeme jen hlavičku cíle bez těla obsahujícího příkazy, tak se pro tento konkrétní cíl jen přidají závislosti. Třeba příklad níže má pro soubory prvni.txt i druhy.txt definovaný stejný příkaz, ale díky speciálním proměnným se pro každý zpracuje jiný zdrojový soubor:

%.txt:
	grep "body" <$< >$@

prvni.txt: KSP_serie1.txt
druhy.txt: KSP_serie2.txt

Poslední věcí, kterou ve spojení s příkazem make zmíníme, je definování a použití vlastních konstant. V podstatě to jsou proměnné, ale doporučujeme vám používat je skutečně jako konstanty (tedy do každé přiřadit pouze jednou), jinak se to celé zamotává. Typické použití je třeba v Makefile pro překlad zdrojáků jazyka C, kde se jednou globálně nastaví všechny přepínače kompilátoru, a pak se používají. Hodnotu v proměnné použijete zapsáním ${nazev_promenne}.

Ukázkový Makefile využívající definované proměnné, speciální proměnné i obecné cíle vidíte níže. Používá se jak verze ${promenna}, tak i verze $(promenna).

PROG=mujprogram
OBJS=mujprogram.o knihovna.o

CFLAGS=-Wall -c
LDFLAGS=-lm -lpthread
CC=gcc

%.o: %.c
	${CC} ${CFLAGS} -o $@ $<

${PROG}: ${OBJS}
	${CC} ${LDFLAGS} -o $@ $^

K tomu ještě dodejme to, že make zpřístupňuje i proměnné prostředí (tedy proměnné ze shellu). Tak si třeba v shellu můžeme nastavit proměnnou, která nám ovlivní prováděné příkazy. Když make žádnou definovanou proměnnou daného jména nenajde (ani interní, ani v prostředí), dosadí místo ní prázdný řetězec.

Úkol 6 [2b]

Představte si, že máte tři zdrojové soubory dat: A.data, B.data a C.data. Dále máte program generuj <vstupy>, kterému jako parametry můžete předhodit libovolný počet vstupních souborů a on na svůj standardní výstup vypíše nějaký vygenerovaný obsah. Ten by se měl ukládat do souborů, které budeme označovat jako A, AB a podobně (podle jejich vstupů).

Pak máte tři finální soubory, které se vytvářejí obdobným příkazem finalizuj <vstupy> (opět vezme libovolně mnoho vstupních souborů a vygenerovaný obsah vypíše na svůj standardní výstup). Soubor FIN1 se vytváří ze souborů A, AB a B, soubor FIN2 ze souborů BC a C a soubor FINAL ze souborů A, AB, B, BC a C.

Sepište Makefile, který bude odpovídat těmto závislostem (zkuste co nejvíce pravidel nějak šikovně seskupit), a pak se zamyslete (a odpovězte), co vše se přegeneruje, když postupně provedeme následující příkazy:

make FINAL
make FIN1
touch A.data  # změníme soubor A.data
make FIN2
touch C.data  # změníme soubor C.data
make FIN1

Úkol 7 [3b]

V KSPčku používáme make i na překlad zdrojáků v TeXu. Ale když chceme někde použít automaticky generované obsahy, nastává problém – TeX totiž generuje soubor s obsahem během generování svého výstupu, a je tak potřeba často spustit první překlad TeXu „naprázdno“ a teprve při druhém překladu použít již vygenerovaný soubor s obsahem, který se vloží na správné místo zdrojáku.

Protože se soubor s obsahem (označme ho toc) vkládá do zdrojáku (tex) a z něj se pak generuje pdf soubor, měly by závislosti být toc ← tex ← pdf. Jenže čas změny toc souboru se změní vždy s překladem nového pdf a tedy vzniká vlastně cyklus.

Zkuste vymyslet řešení a sepsat základní Makefile, který bude toto řešení ilustrovat. Může se vám hodit třeba příkaz diff.

Závěr

Dnes jste se dozvěděli další kousky velké skládačky o UNIXu a jeho příkazovém řádku. Pověděli jsme si o příkazech find a xargs, podívali se na zpracování signálů a obsah /proc a nakonec jsme si ukázali mocného pomocníka v podobě příkazu make.

Existuje ještě spousta kousků této skládačky, o kterých jsme neměli čas se zmínit, ale doufáme, že jsme vám poskytli aspoň to, co jsme považovali za základ, a pomohli vám třeba k tomu, abyste se o UNIX začali zabývat sami. Děkujeme, že jste s námi a s naším seriálem přes celý rok vydrželi. :-)

Jirka Setnička & Jenda Hadrava

Řešení