Odôvodnenie vhodnosti riešenia.

Program ako taký ma za úlohu viac vecí, ktoré by mal robiť zdanlivo paralelne. Preto sa ponúka viac možných riešení.

Prvé riešenie je rozdelit funkcionalitu do viacerých vlákien alebo procesov. Toto riešenie by sprehladnilo kód a procesy by spolu komunikovali cez zdielané médium. Avšak toto je až príliš jednoduché a preto to zadanie zakazovalo.

Druhé riešenie je aktívne čakanie na vhodnú udalosť. Toto riešenie by vyžadovalo aby program v určitých intervaloch kontroloval či nieje potreba urobiť jednu z požiadaviek. Toto riešenie má viacero nedostatkov. Prvý nedostatok je, že program po celú dobu behu požiera aktívne procesor a blokuje ostatné programy vykonávané na danom počítači. Množstvo záťaže na procesor by sa dalo zredukovať zväčšením intervalov, v ktorých kontroluje nutnosť vykonania určitej činnosti. To má však za následok to, že sa nutne zvačší časová odchylka pri zvonení budíkov. Dostávame sa teda do konfliktu požiadaviek na chod programu.

Naštastie existuje aj elegantnejšie riešenie. Toto riešenie je použite systémového volania select. Select je volanie ktoré monitoruje určitú množinu deskriptorov a ak je niektorý pripravený na zápis alebo čítanie (nás zaujíma iba čítanie), tak skončí a dalej môže program pracovať s mnoužinou deskriptorov ktoré vráti, alebo skončí po vypršaní timeout-u. Tento program používa select iba nad 1 deskriptorom a to je deskriptor STD_IN. Timeout je nastavený na najbližšiu udalosť, či už sa jedná o úder programových hodín alebo hlásenie budíka. Takto konštruovaný program netrpí na žiadnu z chýb predchádzajúceho riešenia. Nepožiera čas aktívnym čakaním na udalosť, spracúva vstup iba ak je pripravený a odchylka pri zvonení budíka je maximálne samotné zvonenie budíka + vypísanie času + spracovanie vstupu, ak sa všetky tieto udalosti stali naraz.

Určite sa dá vymyslieť veľa nevhodných riešní, ale tieto podľa mňa ako protipríklady postačujú.

Ďaľej je nutné, aby si program uchovával vedomosť o zadaných budíkoch, ktoré majú byť v budúcnosti obslúžené. Preto sa treba zamyslieť nad vhodnou dátovou štruktúrou.

Pre tento účel som zvolil haldu, ktorá je najvhodnejšia dátová štruktúra na daný účel z viacerých hladísk. Vieme, že utriediť porovnávaním n prvkov má zložitosť O(n log n). Halda má tu peknú vlastnosť, že pri pridaní alebo odobraní prvku nieje nutné znovu utriediť celú množinu n prvkov ale preusporiadať nanajvýš log n prvkov. Každé pridanie, alebo odobranie z haldy teda trvá iba logaritmicky dlho, takže ak rátame že každý prvok aj pridáme do haldy aj ho z nej vyberieme, tak dostávame zložitosť 2n log n čo patrí do O(n log n) a vieme, že rýchlejšie to už nejde. Ďalší bonus je, že operácia ktorá hľadá najvačší, alebo najmenší prvok (v našom prípade s najmenším časom) má zložitosť O(1), kedže sa stačí pozrieť iba na prvý prvok zoznamu pri implementácií do pevného zoznamu.

Toto sú hlavné nosné prvky programu a dúfam, že som presvedčil čitateľa o správnosti ich použitia.