Dokumentácia započtového programu

DISKRÉTNA SIMULÁCIA

Patrik Lenárt

LS 2004/05

1.1 Zadanie úlohy

Program pre diskrétnu simuláciu chodu benzínovej pumpy.

1.2 Popis problému

Program by mal užívateľovi umožnit prevádzať simuláciu benzínovej pumpy, ktorej podoba (to znamená počet jej stojanov, ich rýchlosť, škála poskytovaných služieb, vyťaženosť) je do maximálnej miery určená a modifikovateľná vstunými dátami. Výstup musí poskytovať dostatok informácií, pre zistenie jej stavu v ľubovolnom kroku simululácie.

2.1 Analýza problému

Jedným zo základných problémov je spôsob vyriešenia daného požiadavku na veľkú flexibilitu zadania, ktoré je dané obecnosťou úlohy a je taktiež jedným z hodnotiacich kritérií posudzujúcich celkovú kvalitu celej simulácie, ktorá by mala byť čo najobecnejšia a schopná spracovať čo možno najobecnejší vstup. Nie je preto vhodné aby program povoľoval na svojom vstupe len úzku skupinu „konfiguracií“ benzínovej pumpy, pretože je určený k tomu, aby poskytoval odpovedajúce data pre čo največšiu množinu možných vstupov a umožnil tak ich následné porovnanie a výber čo najlepšej konfigurácie. Previazanosť jednotlivých „komponent“ benzínovej pumpy však nie je natoľko veľká, aby tento požiadavok výrazne zkomplikoval riešenie problému. Jediné čo z neho vyplíva je nutnosť riešiť problém s využitím dynamických dátových štruktúr, čo je samozrejme prístup vhodný tiež z rady iných dôvodov. Ďalším podstatným rozhodnutím je voľba aktívnej časti dat, ktorá bude pracovať s ostatnými dátami. Je v zásade možnosť vyberať z dvoch variant.

Prvá ponecháva všetkú moc komponentám benzínovej pumpy, ktoré si vyzdvihujú požiadavky na obslúženie a následne ich plnia. Druhá varianta ponecháva riadenie simulácie práve týmto požiadavkám, ktoré samé vyzývajú vybrané komponenty k svojmu obslúženiu. Obidve voľby sú v zásade rovnocenné a žiadná neposkytuje oproti druhej nejaké výrazné výhody. Je viacmenej dielom nahody, že v tomto programe bola zvolená koncepcia druhá.

Otázku vzniku požiadaviek je možné riešiť taktiež rôznymi spôsobmi. Jedním je napríklad jej odsunutie mimo programu tým, že sa predpokláda, že postúpnosť týchto požiadavkov je priamo jeho vstupom. Ďalšia možnosť je ich náhodné generovanie na základe určitých údajov popisujúcich priemerné parametre (počet požiadaviek, ich veľkosť atď.) danej konfigurácie. Tento druhý prístup vyžaduje pre svoju realizáciu zavedenie akýchsi vnútorných hodin simulácie, keď niektoré cykly nemusia byť určené k plneniu požidaviek, ale iba k ich generovaniu v závislosti práve na týchto hodinách. Prvý prístup umožnuje obíjsť sa bez vnútorného času a iba vypočítať výsledný čas z veľkosti predom pripravených požiadaviek. V tomto programe bola použitá druhá varianta riešenia.

Posledné významé rozhodnutia sa už zaoberajú iba problémami takzvane technickejšieho rázu. Ide o to, ako zaistiť ukončenie plnenia požiadaviek a teda uvoľnenie zdroja v odpovedajúcej dobe a pritom neprerušiť na dobu plnenia prijímanie ďalších požiadaviek. Toto bolo vyriešené tak, že boli vytvorené štruktúry popisujúce ukončenie požiadavkov, ku ktorým sa pristúpuje ako ku špecifickému druhu požiadavku (ktorý je samozrejme splnený okamžite po svojom vyvolaní). S týmto riešením sa nám naskytne otázka, či máme udržiavať tito špeciálne požiadavky v pamati spoločne so skutočnými požiadávkami alebo ich reprezentovať samostatne. Z mnoha dovodov je vhodnejšie druhé riešenie. V prípade spoločnej fronty prostých a špecialnych požiadaviek by bolo napríklad zložitou otázkou ich vzájomné umiestnenie v čase (a teda vo fronte), v skutočnosti je táto otázka predmetom simulácie.

2.2 Popis datových štruktúr

Zpôsob reprezentácie dát má v tejto úlohe nesmierný vplyv na jej celkové riešenie a dá sa taktiež takmer povedať, že je to jej najpodstatnejšia časť.

V programe sú obsiahlo používané premenné objektového typu. Hojne sa pracuje taktiež s dynamickými štruktúrami.

Celkovú konfiguráciu celej benzínovej pumpy popisujú premenné následujúcich typov :

tSluzba – reprezentuje jednu konkrétnu službu poskytovanú benzínovou pumpou (napríklad tankovanie nafty, umývanie auta atď.). Mimo iného nesie informáciu o počte požiadavkov na poskytnutie tejto služby, o ich veľkosti a ďalšie. Jej súčasťou je tiež jednoznačné identifikačné číslo.

tZdroj – reprezentuje nejakú komponentu benzínovej pumpy, nejakú jej súčasť poskytujúcu službu určenú svojím identifikačným číslom. Práve tieto komponenty, tieto zdroje sú súčasťou systému zpracuvavajúceho príchodzie požiadavky.

tSluzby – zoznam poskytovaných služieb, odvodený zo vstupného súboru

tZdroje – zoznam využiteľných zdrojov, odvodený zo vstupného súboru

Následuje popis typov premenných, reprezentujúcich požiadavky na poskytnutie služieb alebo z nich nejak odvodených :

tPoziadavok – reprezentuje požiadavok na poskytnutie nejakej služby určenej príslušným identifikačným čislom.

tKoniec – reprezentuje pseudopožiadavok na ukončenie obsluhy požiadavkov. Odvodený z požiadavku po jeho vyzdvihnutí zaniká jeho splnením. Nesie čas splnenia prislušného požiadavku. Určený k tomu aby predal komponente pracujúcej na obslužení požiadavkov signál k uvoľneniu.

tPoziadavky – fronta požiadavkov čakajúcich na vyzdvihnutie a splenenie, umožnuje plnenie požiadavkov mimo poradia (pokiaľ nie sú pre predchadzajúce požiadavky voľné zdroje).

tKonce – fronta preudopožiadavkov zariaďujúcich uvoľnenie zdroja v správnom čase, zoradená práve podľa týchto časov

Typ ktorý zastrešuje všetky predchádzajúce:

tPumpa – obsahuje jak položky popisujúce konfiguráciu pumpy (služby, komponenty), tak položky nesúce informáciu o momentálnom stave simulácie (požiadavky, pseudopožiadavky).

2.3 Popis algoritmu

Po inicializácii všetkých patričných hodnot sa opakuje cyklus vykonávajúci všetko podstatné. Každý prechod týmto cyklom reprezentuje skok o určitý časový úsek vpred.

V prvej fáze cyklu sa prejde fronta požiadavkov. Tie z nich, ktoré môžu byť obslúžené sú obslúžené. To, že je nejaký zdroj vhodný pre obslúženie určitého požiadavku sa pozná podľa identifikačného čísla odpovedajúcej služby, ktorá je súčasťou obidvoch zúčastnených štruktúr. Obslúžený požiadavok je vybraný z fronty požiadavkov a zároveň je vytvorený odpovedajúci pseudopožiadavok, ktorý umožní uvoľnenie zdroja v správnom čase a ktorý je zaradený podľa svojho časového určenia do fronty pseudopožiadavkov.

V následujúcej části sa odoberú z počiatku fronty pseudopožiadavkov všetky prvky, ktorých čas určenia je menší ako čas aktuálny. Uvoľnia sa prislušné zdroje a tým sú definitívne vyriešené požiadavky, ktoré inicializovali ich vznik.

Na záver prebehne generovanie nových požiadavkov a ich vloženie do fronty.

Čas je zvýšený a cyklus začína nanovo (samozrejme len ak nie je splnená ukončovacia podmienka).

3.1 Popis vstupného súboru

Vstupný súbor môže obsahovať komentáre začínajúce znakom „#”. Je rozdelený na niekoľko sekcií, z nich každej predchádza špecialne slovo na samostatnom riadku. Následujúce riadky sú zložené z polí oddelených dvojbodkami. Niektoré sekcie sa môžu vyskytovať aj viackrát.

Za slovom „SLUZBY“ následuje popis poskytovaných služieb. Prvé pole určuje jednoznačný kód služby, druhé a tretie minimálnu a maximálnu veľkosť požiadavkov naňu (v stotinách jednotky), vo štvrtom poli je priemerná doba medzi dvoma výskytmi požiadavku na službu. Vo štvrtom je stonásobok ceny za jednotku. Následuje slovný popis a jednotka veľkosti požiadavku.

Slovo ZDROJE1 začína sekciu s popisom zdrojov, ktoré plnia požiadavky závislé na ich rozsahu (tankovanie nafty...). V prvom poli je identifikačné číslo zdroja, v druhom identifikačné číslo poskytovanej služby, v tretiom rychlosť zdroja v stotinách jednotky za sekundu, v štvrtom slovný popis zdroja.

Sekcia s popisom zdrojov, ktoré plnia požiadavky nezávisle na ich rozsahu (umývanie auta v umývačke) predchádza slovo „ZDROJE2“. Prvé pole obsahuje identifikačné číslo zdroja, druhé identifikačné číslo príslušnej služby, tretie dobu potrebnú k splneniu požiadavku, štvrté slovný popis zdroja.

Akémukoľvek popisu zdroja musí predchádzať popis služby, ktorú plní.

Všetky identifikačné čísla môžu mať hodnoty len z intervalu celých čísel a to 0-255.

Posledná sekcia sa začína slovom „RIADENIE“. Význam riadku tejto sekcie závisí na hodnote prvého poľa. Po 0 následuje číslo udávajúce dobu trvania simulácie v sekundách, po čísle 1 číslo udávajúce dobu trvania v počte splnených požiadavkov (obom týmto hodnotám program vyhovie len približne), po 2 následuje hodnota udávajúca veľkosť kroku programu v sekundách, po 3 hodnota pre generátor náhodných čísel.

Kdekoľvek sa v súbore môže objaviť riadok obsahujúci iba slovo „INTERAKT“, čo značí, že bude použitý interaktívni režim a sekcia riadenia bude ignorována (až na riadok s veľkosťou kroku).

3.2 Popis výstupného súboru

Začiatok zpracovávania nejakého požiadavku je indikovaný výstupom slova „ZAC“ nasledovaného údajom o požiadavku, podobne je tomu aj s koncom spracovávania požiadavku, úvodné slovo je „KON“. Za časťou v ktorej sa striedajú tieto dva typy výstupov a ktoré reprezentuje vlastná simulácia je uvedená súhrnná tržba zo všetkých požiadavkov, nasledována výpisom služieb, ktoré sa prevádzali v dobe ukončenia simulácie, a začínajú slovom „VYKONAVA SA“. Za slovami „CAKA NA VYKONANIE“ následuje výpis fronty v dobe ukončenia simulácie.

3.3 Popis interaktivného režimu

Príkazy (môžu byť zapísané jak veľkými tak malými písmenamy):

H – help

P – zmena množiny služieb považovaných príkazmi A,F,C za platné, služby sú popísané zoznamom identifikačných kódov oddelených čiarkami nesledujúcich po medzere za príkazom, pri prázdnom zozname sa nastavia všetky služby, implicitne sú taktiež nastavene všetky.

R – zmena množiny zdrojov považovaných príkazmy U,K za platné, služby sú popísané zoznamom identifikačných kódov oddelených čiarkami nasledujúcich po medzere za príkazom, pri prázdnom zozname sa nastavia všetky služby implicitne sú taktiež nastavené všetky.

A – prevedenie počtu platných akcií určených (približne) číslom nasledujúcim za príkazom po medzere.

V – postup vpred o počet sekúnd určený (približne) číslom nasledujúcim za príkazom po medzere.

U – uvoľnenie platných zdrojov

K – výpis akcií práve prevádzaných platnými zdrojmi

C – vymazanie všetkých požiadavkov na platné služby z fronty

F – výpis všetkých požiadavkov na platné služby

Z – výpis všetkých zdrojov

S – výpis všetkých služieb

T – výpis aktuálneho času

Q – ukončenie programu

3.4 Uživateľská příručka

Program môže byť spustený so žiadným až dvoma parametrami. Prvý parameter určuje vstupný súbor, druhý súbor výstupný. Nie je druhý parameter zadaný použije sa štandardný výstup, nie je zadaný ani prvý parameter je vstupom súbor bka.inp.