12. Číselné soustavy, binární číselná soustava. Kódování informací, binární váhový kód, kódování záporných čísel. Standardní jednoduché datové typy s pevnou a s pohyblivou řádovou tečkou. Základní strukturované datové typy (pole, rekord apod.). Paměť počítače, adresa, uložení základních datových typů v paměti počítače.
Číselné soustavy Každou hodnotu lze reprezentovat různými způsoby. V historii se používali jako počítadla ruce a proto první číselné soustavy měli základ pět a deset. Dnes se v běžném životě nejvíce používá soustava o základu deset, takzvaná Arabská (vymyšlena ale byla v Indii). Tato soustava používá číslice 0..9, přičemž poloha číslice určuje jeho váhu - tím je možné vyjádřit i čísla větší než deset. Číslo v desítkové soustavě můžeme obecně rozepsat takto: Příklad: 156,2 = 1 x 100 + 5 x 10 + 6 x 1 + 2 x 0,1 Počítače mohou z principu pracovat s libovolnou číselnou soustavou. Protože je však nejjednodušší a nejspolehlivější rozlišovat pouze dva stavy nějaké fyzikální veličiny, používá soustava o základu dva. Tyto dva stavy se mohou nazývat různě: 0–1 lež – pravda logická 0 – logická 1 V reálném světě se pracuje nejčastěji s napětím. Buňce, která nese takovou informaci, říkáme jeden bit. Protože zápis čísel v soustavě o základu dva je pro člověka nepřehledný, používají se ve výpočetní technice ještě soustavy o základu osm a šestnáct. Mezi těmito soustavami a dvojkovou soustavou lze totiž snadno převádět a pro člověka jsou čísla v těchto soustavách mnohem „představitelnější“. Pro některé speciální případy lze používat i jiné typy číselných systémů. Např. pomocí číselné soustavy s faktoriály, kde každá pozice má váhu n!, lze velmi přesně pracovat s racionálními čísly. V určitých případech potřebujeme předem vědět, kolik platných míst (N) budeme potřebovat k vyjádření nějaké hodnoty (X) v různých číselných soustavách. Výpočet provedeme pomocí logaritmu o základu, který odpovídá základu soustavy: Pro dekadickou soustavu: N = [ log10 X ] + 1 Pro binární soustavu: N = [ log2 X ] + 1 Pro hexadecimální soustavu: N = [ log16 X ] + 1 Výsledek zaokrouhlujeme na celé číslo směrem dolů.
Binární číselná soustava ● ●
používá pouze dva symboly: 0 a 1 nejjednodušší soustava
Převod z dvojkové soustavy do dekadické číslo ve dvojkové soustavě:
př:
tedy:
Tento postup je velmi rychlý a lze ho provádět pro malý počet míst i přímo z hlavy. Stačí si pamatovat mocniny dvojky (= váhy pozic).
Převod z dekadické soustavy do dvojkové Matematické odvození postupu: Napíšeme si rovnici, kde na levé straně je zadaná hodnota v desítkové soustavě a na pravé straně je obecně rozepsané číslo ve dvojkové soustavě. Př:
Toto je jedna rovnice o mnoha neznámých. Abychom jí mohli vyřešit, musíme jí rozdělit na rovnice pro jednotlivé proměnné. To provedeme tak, že celou rovnici vydělíme číslem 2:
Výsledek poté rozdělíme na celou část a část za desetinou čárkou. Desetinná část: V tomto okamžiku již můžeme přímo napsat, že koeficient a0 = 0. Celá část:
Se zbytkem rovnice opakujeme tento postup až do doby, kdy na levé straně zůstane 0. V tomto okamžiku máme vypočteny všechny koeficienty.
Tento postup je poněkud zdlouhavý, proto se používá jeho rychlejší varianta. Dělíme desítkové číslo
celočíselně dvěma a opisujeme zbytky. Příklad: 132 : 2 = 66 : 2 = 33 : 2 = 16 : 2 = 8 : 2 = 4 : 2 = 2 : 2 = 1 : 2 = 0 zbytek: 0 0 1 0 0 0 0 1 a0 a1 a2 a3 a4 a5 a6 a7
Dělíme do té doby, dokud výsledek není nula a zbytky opisujeme křížem (od a7 do a0). Desetinou část čísla převádíme obdobně. Pouze používáme pro řešení rovnice místo dělení násobení. Př:
Stejně jako u převodu celé části lze postup zrychlit. Př: 0,25 x 2 = 0,5 x 2 = 1 (-1) 0 x 2 = 0 0 1 a-1 a-2
Jako výsledek opisujeme celé části výsledku po násobení dvěma. V našem případě je tedy výsledek po zaokrouhlení: 0,25 = 0,012
Rozvoj necelé části může být i neukončený (periodický nebo neperiodický). V tomto případě musíme rozvoj zkrátit (zaokrouhlit) a dochází tak k zaokrouhlovací chybě. Př: 0,22 x 2 = 0,44 x 2 = 0,88 x 2 = 1,76 (-1) 0,76 x 2 = 1,52 (-1) 0,52 x 2 = 1,04 (-1) 0,04 x 2 = 0,08 … 0 0 1 1 1 0 0,22 = 0,001110002
S čísly ve dvojkové soustavě lze přímo počítat obdobně, jako s čísly v desítkové soustavě.
Binární váhový kód Binární kód je způsob uložení informace v počítači definovaný jako konečný počet bitů, z nichž každý může nabývat právě jednu ze dvou hodnot (obvykle označených 0 nebo 1). Pro snadnější zápis uložených hodnot (čísel) se dnes převážně používá byte (bajt) s délkou slova osm bitů. Pro výpočet hodnoty binárního zápisu se používá binární soustava.
Kódování záporných čísel Pro zápis záporných čísel ve dvojkové soustavě můžeme použít znaménko mínus stejně, jako v desítkové soustavě. Pro kódování znaménka v počítačích se proto používají tyto metody: ●
Vyhrazení jednoho bitu pro znaménko, další bity zůstávají pro binární váhový kód absolutní hodnoty (např. mantisa u typů s pohyblivou řádovou čárkou) ● Přičtení konstanty (např. exponent u typů s pohyblivou řádovou čárkou) ● Pomocí dvojkového doplňku (např. celočíselné typy ve vyšších programovacích jazycích)
Dvojkový doplněk Doplňkem se rozumí rozdíl kapacity soustavy (tj. 2 n, kde n je počet bitů v binárním vyjádření) a absolutní hodnoty čísla. Rozsah čísel, které tímto způsobem lze vyjádřit, je pak ( - 2 n-1 ) až ( 2 n-1 – 1 ). Např. Pomocí osmi bitů tak lze vyjádřit čísla v rozsahu –128 .. +127 . Interpretace záporných čísel pomocí dvojkového doplňku umožňuje, na rozdíl od ostatních způsobů, přímo provádět sčítání a odečítání. Zároveň lze také přímo zjistit znaménko, protože nejvyšší bit u záporných čísel je vždy jedna. Postup pro převod absolutní hodnoty na záporné číslo pomocí dvojkového doplňku je následující: ● doplníme dvojkové vyjádření absolutní hodnoty zleva nulami na požadovaný počet bitů ● provedeme negaci všech bitů ● k výsledné hodnotě přičteme binárně hodnotu jedna Alternativní postup: ● doplníme dvojkové vyjádření absolutní hodnoty zleva nulami na požadovaný počet bitů ● zprava opíšeme všechny nuly až k první jedničce (včetně), další bity negujeme př: -46 46 = 001011102 Nejprve převedeme desítkovou absolutní hodnotu a doplníme nulami zleva na osm bitů 110100012 Znegujeme výsledek 110100102 Přičteme k výsledku jedničku Výsledek: -46 = 110100102
Standardní jednoduché datové typy ● s pevnou řádovou tečkou ● neznaménkové ●byte (8b) ●word (16b) ●Dword (32b) ●Char (8b) ● znaménkové ●shortInt (8b) ●integer (16b) ●longint (32b) ● s plovoucí řádovou tečkou ● single (32b) ● double, real (64b) ● extended (80b)
Datové typy s pevnou řádovou tečkou Jsou to nejjednodušší celočíselné typy, pomocí kterých lze vyjadřovat celá čísla. Můžeme je dále rozdělit na znaménkové a neznaménkové. Rozsah hodnot, které pomocí nich lze vyjádřit je dán jejich velikostí v pamětí (počtem bitů). Typ Byte Word Dword ShortInt Integer LongInt Char
Rozsah 0 .. 255 0 .. 65535 0 .. 2 32 –1 -128 .. 127 -32768 .. 32767 -2 32 .. 2 32 -1 0..255 – odkaz do ASCII tabulky
Datové typy s plovoucí řádovou tečkou Abychom mohli pracovat s reálnými čísly ve dvojkové soustavě, můžeme využít stejný přístup, jako v desítkové. To znamená, že si číslo převedeme do dvojkové soustavy a případně ještě do normalizovaného tvaru. Př: Převeďte číslo 2,1345 x 10 2 do dvojkové soustavy v normalizovaném tvaru. Řešení: Nejprve si převedeme desítkové číslo z normalizovaného tvaru do tvaru, který je vhodný pro převod do dvojkové soustavy (to je tvar bez exponentu). Provedeme převod celé i desetinné části a nakonec přepíšeme výsledek do normalizovaného tvaru ve dvojkové soustavě (přidáme exponent tak, aby před desetinou čárkou bylo pouze číslo 1). 2,1234 x 10 3 = 2123,4 = 100001001011,0110011002 = 1,000010010110110011002 x 2 11 Pokud už máme reálné číslo ve dvojkové soustavě v normalizovaném tvaru, můžeme se zabývat problémem jak ho uložit do paměti počítače. Ve skutečnosti totiž musíme uložit tři různé informace – znaménko, absolutní hodnotu a exponent. Musíme si zvolit způsob kódování znaménka u exponentu, počet bitů u exponentu a počet bitů na vlastní číslo (mantisu). Tím určíme rozsah a přesnost čísel, která můžeme takto kódovat. Je zřejmé, že možností je velmi mnoho. Ve vyšších programovacích jazycích se používají hlavně tyto tři datové typy: Single, Double (někdy se označuje jako Real), Extended. Datový typ Single Pro zápis reálného čísla v tomto datovém typu se využívá celkem 32 bitů. Jeden bit je znaménko, osm bitů je vyhrazeno pro exponent a 23 bitů pro mantisu. Mantisa je absolutní hodnota reálného čísla v normalizovaném tvaru, ale zapisuje se bez první jedničky. V normalizovaném tvaru totiž
binární číslo vždy začíná jedničkou, pak je desetinná čárka a pak následuje zbytek absolutní hodnoty. Proto je zbytečné první jedničku před desetinou čárkou zapisovat. S – znaménko, 1=mínus E – exponent, kóduje se přičtením konstanty 127, takže rozsah exponentů je –127 až +128 M – mantisa, absolutní hodnota čísla, zapisuje se bez první jedničky Zpětně pak dostaneme reálné číslo dosazením do vzorce: (-1) S x 2 E - 127 x ( 1,M )
Postup pro vytvoření 32-bitové konstrukce: 1. Vyjádřit absolutní hodnotu daného čísla X v binární soustavě (odděleně zjistit binární vyjádření celé a necelé části, potom obě části oddělit řádovou tečkou) 2. Řádovou tečku posunout za první jedničku zleva. Z počtu pozic, o které se tečka v zápisu posouvá, určit hodnotu EXPONENTU: Žádný posun e = 0 Posun vpravo e <0 Posun vlevo e > 0 3. Určit obsah pole S: X >=0 S=0 X < 0 S=1 4. Určit obsah pole E: Vyjádřit hodnotu e+127 binárním váhovým kódováním (jako typ Byte) 5. Určit obsah pole M: bity, které zůstaly po posunutí řádové tečky vpravo od ní. Příklad: Uložte do paměti číslo –0,0625 ve formátu datového typu Single. Řešení: Nejprve převedeme absolutní hodnotu do dvojkové soustavy. 0,0625 = 0,00012 Poté přepíšeme výsledek do normalizovaného tvaru posunem desetinné čárky. 0,00012 = 1,02 x 2 -4 Obsah pole S je 1, protože číslo je záporné. Obsah pole E je binárně vyjádřený exponent, ke kterému přičteme konstantu 127. E = -4 + 127 = 124 = 011110112 Mantisu získáme opsáním absolutní hodnoty bez první jedničky, takže to jsou v tomto případě samé nuly.
Rekonstrukce číselné hodnoty: 1. 32-bitovou strukturu rozdělit na pole S (1 bit), E (8), M (23) 2. Sestavit zápis . 1. ...., ve kterém za řádovou tečkou jsou bity z pole M. 3. Číselně interpretovat obsah pole E (binární váhový kód). Zmenšením získané hodnoty o 127 určit hodnotu e. V zápisu posunout řádovou tečku o e pozic. (Pro e>0 se tečka posouvá směrem vlevo). 4. Zápis v binární soustavě převést do dekadické soustavy (binární váhový kód) 5. Doplnit znaménko podle bitu v poli S. (S=1 . číslo je záporné) př: S=0 E = 100000102 = 129 M = 10010012
Výsledek je pak: 2 130 - 127 x 1,10010012 = 2 3 x 1,10010012 = 1100,10012 = 12,5625
vyjímky: ● ●
Pokud S = 0, E = 0 a M = 0 : hodnota čísla je nula Pokud E = -127 : EXP se bere jako –126 a absolutní hodnota se nebere ve tvaru (1,M) ale
(0,M) ●
Pokud E = 128 : hodnota čísla je nekonečno, M musí být 0. Jiné hodnoty M jsou neplatné. Exponent Mantisa Velikost MIN MAX Přesnost
Single
8b
23b
32b
1,4E-45
3,4E38
6-7 míst
Double
11b
52b
64b
5,0E-324
17,E308
15-16 míst
Extended
15b
63b
80b
3,4E-4932
1,1E4932
18-19 míst
Strukturované datové typy Datový typ obsahuje jeden nebo více prvků. Říkáme, že je homogenní, jsou-li prvky stejného typu. Pole sdružuje daný počet prvků (čísel, textových řetězců, … ) o stejné velikosti. K jednotlivým prvkům pole se přistupuje pomocí jejich indexu (celého čísla, označujícího pořadí prvku). Velikost pole zůstavá při běhu programu neměnná (některé programovací jazyky toto omezení nekladou, zvětšení pole je ale časově náročná operace). Řetězec Počet znaků řetězce definuje délku textového řetězce. Textový řetězec může být prázdný (obsahuje 0 znaků řetězce). Typy ● ● ●
konstantní – neměnný obsah (generovaný při překladu programu) staticky alokovaný pamětový prostor pro řetězec – řetězec má omezenou max. Délku dynamicky alokovaný pamětový prostor pro řetězec – řetězec má max. délku omezenou jen velikostí volné paměti Záznam Tento datový typ se skládá z určitého počtu položek, které mohou být různého typu. každá položka má přiděleno jméno, neboli identifikátor položky, pomocí něhož se provádí výběr položky. Výčtový typ (enum) programátorem definovaný typ, např. pro barvu karet.
Paměť Společná pro data i program (viz. Von Neumann) ● Slouží k uchování dat ● je potřeba ● prostor pro uložení dat (paměťové buňky) ● nástroj na přístup (adresa, sběrnice) ● každá buňka má svou adresu Operační paměť je volatilní (nestálá) vnitřní elektronická paměť číslicového počítače typu RWMRAM, určená pro dočasné uložení zpracovávaných dat a spouštěného programového kódu. Tato paměť má obvykle rychlejší přístup než vnější paměť (např. pevný disk). Tuto paměť může procesor adresovat přímo, pomocí podpory ve své instrukční síti. Strojové instrukce jsou
adresovány pomocí instrukčního ukazatele a k datům se obvykle přistupuje pomocí adresace prvku paměti hodnotou uloženou v registru procesoru nebo je adresa dat součástí strojové instrukce. Operační paměť je spojena s procesorem pomocí sběrnice, obvykle se mezi procesor a operační paměť vkládá rychlá vyrovnávací paměť typu cache, neboli paměť, která je přímo přístupná procesoru. Jedná se o nepostradatelný fyzický prostředek, který je spravován jednou z hlavních části operačního systému. Operační paměť je určená pro uchovávání kódu programů respektive procesů spolu s mezivýsledky a výsledky jejich činnosti. Zrovna tak je v operační paměti uchováván stav dalších prostředků a základní datové struktury jádra. Vezmeme-li v potaz adresování operační paměti, lze zjednodušeně paměť chápat jako souvislý prostor paměťových buněk o nějaké velikosti. Tyto buňky jsou pak lineárně adresovány adresami pevné délky. Je-li operační paměť reprezentována pamětí s přímým přístupem, označujeme adresový prostor jako fyzický adresový prostor (FAP). Velikost tohoto prostoru je omezena buď fyzickou velikostí paměťových modulů a nebo velikostí adresy tj. adresa o velikosti n bitů umožňuje adresovat 2 na ntou paměťových míst. Jednodušší procesory podporují adresovat pouze paměť s přímým přístupem, tedy adresovat pouze fyzický adresový prostor. V dnešní době velká část procesorů umožňuje adresovat i logické adresové prostory. Jedná se o tzv. virtualizaci paměti respektive jde o neomezený počet logických adresových prostorů.
Adresa ● ● ● ● ● ● ● ●
Adresa = číslo, pořadí paměťové buňky Udává se nejčastěji v šestnáctkové soustavě (např. adresa 2F9 je buňka na 761. pozici) Adresový prostor = rozsah adres Adresový prostor procesoru: rozsah adres, na které dokáže přistupovat procesor Např. 8bitový procesor neumí pracovat s 16bit. Adresou Paměti většího rozsahu (disky apod.): Děleny do segmentů; stránek a dalších celků Adresa je kombinací určení segmentu a adresy buňky
Uložení základních datových typů v paměti počítače Pro zjednodušení budeme o paměti uvažovat jako tabulce, která má na každém řádku osmibitové číslo. Adresa 0 je nahoře a každý další řádek má adresu o 1 vyšší. Překladače vyšších programovacích jazyků ukládají proměnně postupně do paměti v pořadí, jak jsou deklarovány. Proměnné, které mají velikost jeden bajt (Byte, Char) je situace jednoduchá. Více bajtové proměnné se ukládají do paměti postupně od nejméně významného bajtu.
Př typ single:
13. Programátorský model procesoru, instrukce, instrukční soubor, symbolická adresa, operace v registrech, s pamětí, I/O operace. Sekvence instrukcí, algoritmizace základních úloh v jazyku symbolických adres. Časování programu, podprogramy, přerušení. Programátorský model procesoru
Uvnitř procesoru se nachází: řadič instrukcí – dekóduje instrukci na vstupu a provede potřebné operace ALU – Aritmeticko-logická jednotka, ta provádí vlastní výpočty Univerzální použitelné registry R0..R7 – slouží jako rychlá paměť pro výpočty Akumulátor = registr A – speciální registr, jediný možný operand některých instrukcí Registr PSW (Program State Word) – tento registr obsahuje stav procesoru používat z tohoto registru pouze dva bity, a to bit C (Carry) který je v jedničce pokud poslední matematická operace skončila přetečením a bit Z (Zero) který je v jedničce pokud aktuální obsah akumulátoru je 0 Registr DPTR (Data Pointer) – slouží pro nepřímé adresování v datové paměti, je šestnáctibitový ale přistupujeme k němu osmibitově pomocí registrů DPL a DPH Registr SP (Stack Pointer) – slouží jako ukazatel na vrchol zásobníku Registr PC (Program Counter) – tento registr obsahuje adresu aktuálně vykonávané instrukce
Instrukce Strojová instrukce je v informatice označení elementární operace procesoru, který je součástí počítače. Strojová instrukce je základní jednotkou strojového kódu. Každý typ procesoru má vlastní sadu strojových instrukcí, kterou je schopen přímo vykonávat. Jednotlivé instrukce jsou uloženy za sebou v programové paměti. Každá instrukce se v paměti skládá z operačního kódu a operandů. V reálném mikroprocesoru může zápis instrukce v paměti zabírat různé množství paměťových buněk. Instrukce, která nemá žádné operandy, zabere pouze jednu buňku. Naopak instrukce, která například ukládá konstantu do nějakého registru, zabere tři buňky.
Typy instrukcí : Přesunové - Přesunové slouží ke kopírování dat v paměti. Tyto instrukce mají typicky mnemoniku MOV (z angl. move - přesun), případně LD nebo ST (load, store). Prakticky vždy mají dva operandy - zdrojový a cílový, kdy hodnota uložená ve zdrojovém operandu je uložena do cílového operandu. MOV A, R0 – přesune do A hodnotu v R0 Aritmeticko-logické - Aritmeticko-logické instrukce slouží k vykonávání aritmetických nebo logických operací. V podstatě jde o to, že se zdrojovými operandy se provede určitá matematická operace, jejíž výsledek je uložen do cílového operandu. Velmi častý je případ, kdy jeden ze zdrojových operandů slouží současně jako cílový. To znamená, že např. instrukce add r0, r1 nejprve sečte hodnoty registrů r0 a r1, přičemž výsledek uloží do registru r0. Typickými funkcemi aritmetickou-logických instrukcí jsou sčítání (ADD), odečítání (SUB), porovnávání (CMP), bitové logické součty (OR) a logické součiny (AND), bitové posuny a rotace. ANL A, R0 – provede logický součin akumulátoru s obsahem registru R0 Řídící - Tyto instrukce mění buď tok programu, nebo způsob, jakým procesor funguje. Základní řídící instrukcí je instrukce skoku (typicky má mnemoniku JMP), která říká, že vykonávání programu nepokračuje následující instrukcí, ale instrukcí která je uložena na adrese definované operandem instrukce JMP. LOOP: INC A OUT 0AAH JMP LOOP
Přehled instrukcí:
Instrukční soubor Další rozdělení mikrokontrolérů je podle použitého instrukčního souboru. V oblasti jednočipových počítačů se běžně používají instrukční soubory typu CISC, RISC. CISC označuje procesor s „komplexním instrukčním souborem“. Procesor podporuje mnoho formátů a druhů instrukcí. Na jednu stranu to znamená úsporu místa v programové paměti (vyšší hustotu kódu), na druhé straně to však znamená komplikovanější dekodér instrukcí ve vlastním mikrokontroléru a pomalejší zpracování instrukcí. RISC označuje procesor s redukovaným instrukčním souborem. Základní myšlenkou je omezení počtu a zjednodušení kódování instrukcí, což vede ke zjednodušení instrukčního dekodéru. Hlavní výhodou tohto přístupu je rychlost a jednoduchost, na stejné ploše čipu může být místo 16bitového procesoru CISC 32bitový procesor RISC. Nevýhodou je, že pro zakódování instrukce je potřeba více místa, někdy musíme použít dvě instrukce místo jedné, takže klesá hustota kódu. (ARM, ATMEL) Symbolická adresa
Operační kód instrukce je v paměti samozřejmě uložen jako číslo. Instrukcí sice procesor nemá mnoho (jednočipové mikroprocesory mají řádově okolo 100 různých instrukcí), ale stejně je pro člověka nepředstavitelné, že by znal všechny jejich operační kódy zpaměti a pamatoval si jejich význam. Navíc by si musel pamatovat i kódy jednotlivých operandů a v případě skoků by musel při každé změně programu přepočítat adresy instrukcí v paměti. Takový program by se nejen obtížně psal, ale i četl a ladil. Proto se procesory neprogramují přímo ve strojovém kódu ale v takzvaném jazyce symbolických adres (JSA), který se někdy (nesprávně) označuje jako assembler. V tomto jazyce je každé instrukci přiřazena tzv. mnemonická zkratka. Stejně tak jsou zavedeny jednoduchá jména pro registry procesoru místo jejich čísel. Také je možné používat v takovém programu symbolická návěstí pro označení místa, kam ukazuje instrukce skoku. Program napsaný v jazyce symbolických adres je pak nutné přeložit pomocí překladače assembleru do strojového kódu. Překladač nahradí jména instrukcí, registrů a návěstí konkrétními čísly a poskládá instrukce za sebe do paměti procesoru. Toto je triviální úloha, která nám ale přináší obrovský komfort při psaní programů na úrovni jednotlivých instrukcí.
Operace v registrech Výměna obsahů mezi registry R0 a R1: mov A, R0 mov R2, A mov A, R1 mov R0, A mov A, R2 mov R1, A K tomuto je potřeba využít pomocný registr R2, protože výměna je realizována přes zásobník. Oprace v paměti Do paměti na adresu AAh vložit hodnotu 123: mov A, #123 mov 0AAh, A Do paměti na adresu AAAAh vložit hodnotu 123: mov A, #123 mov DPTR, #0AAAAH mov @DPTR, A
I/O operace IN in A, Adresa8 – instrukce zkopíruje data s adresou vstupního portu do akumulátoru Vstupní porty nemají vlastnost registru. Jejich obsah je v každém okamžiku dán děním mimo počítač. Instrukce „in“ jednorázově zkopíruje obsah portu do akumulátoru. OUT out Adresa8, A – instrukce zkopíruje osmibitová data z akumulátoru na vybraný port Výstupní porty mají vlastnost registru. Jejich obsah je dán posledním provedením instrukce „out“. Algoritmizace
Časování (z PHS x51) Časovač (Timer) - počítá strojové takty Čítač počítá impulzy vnějšího signálu (měří jeho kmitočet). Časovač čítá pevný kmitočet, který je obvykle odvozen od hodinového signálu mikropočítače. 8051 obsahuje dva čítače/časovače, které mohou mít délku až 16 bitů. Obsah čítačů časovačů je dostupný pomocí registrů THx nebo Tlx. X je konkrétní číslo časovače/čítače. THx je horní bajt a TLx je dolní bajt. Každý čítač nebo časovač s dá nastavit do 4 režimů. Pro řízení časovačů/čítačů se používají registry TMOD a TCON. TMOD Tento registr umožňuje volit režim obou časovačů/čítačů a není bitově adresovatelný.
bit 7
bit 6
bit 5
bit 4
bit 3
bit 2
bit 1
G
C/T
M1
M0
G
C/T
M1
bit 0
M0
G - volí způsob hradlování čítače (tedy kdy jsou impulzy čítačem uvažovány) G=0 čítač/časovač je řízen pouze programově (bitem TRx v registru TCON) G=1 čítač/časovač je řízen programově i obvodově (vstupem) C/T - (Counter/Timer) volí, zda čítač/časovač pracuje jako čítač nebo časovač. C/ =0 pracuje jako časovač, v tom případě jsou brány hodiny z vnitřního zdroje odvozeny jako 1/12 hodinového kmitočtu mikrořadiče C/ =1 pracuje jako čítač, hodinový vstup je na vývodu Tx. Maximální kmitočet je 1/24 hodinového kmitočtu mikrořadiče. TCON Bity registru TCON slouží pro programové spouštění časovačů nebo pro indikaci přetečí a jsou bitově adresovatelné.
bit 7
bit 6
bit 5
bit 4
bit 3
bit 2
bit 1
bit 0
TF1
TR1
TF0
TR0
IE1
IT1
IE0
IT0
TF1 – indikace přetečení čítače/časovače 1, při přetečení je automaticky nastaven, po vstupu do obsluhy přerušení je automaticky vynulován. TF0 – to samé jako ^ akorát pro čítač/časovač 0 TR1 – spuštění čítače/časovače 1 TR0 - spuštění čítače/časovače 0 Podprogramy Podobně jako při skoku se při volání podprogramu předává řízení instrukci na jiném místě programu. Na rozdíl od skoku se ale předpokládá návrat do místa, odkud byl podprogram
volán. Proto je nutné nejprve uložit adresu aktuální instrukce (registr PC – Program Counter) a pak teprve provést skok. Na konci podprogramu se tato adresa opět vyzvedne a program pokračuje na původním místě, odkud byl podprogram volán. K tomuto slouží instrukce CALL a RET.
Přerušení Přerušení je v informatice metoda pro asynchronní obsluhu událostí, kdy procesor přeruší vykonávání sledu instrukcí, vykoná obsluhu přerušení a pak pokračuje v předchozí činnosti. Původně přerušení sloužilo k obsluze hardwarových zařízení, které tak signalizovaly potřebu obsloužit Později byla přidána vnitřní přerušení, která vyvolává sám procesor, který tak oznamuje chyby vzniklé při provádění strojových instrukcí a synchronní softwarová přerušení vyvolávaná speciální strojovou instrukcí, která se obvykle používají pro vyvolání služeb operačního systému. Obsluha přerušení : Přijde-li do procesoru signalizace přerušení, je v případě, že obsluha přerušení je povolena, nejprve dokončena právě rozpracovaná strojová instrukce. Pak je na zásobník uložena adresa následující strojové instrukce, která by měla být zpracována, kdyby k přerušení nedošlo. Pak je podle tabulky přerušení vyvolána obsluha přerušení, která obslouží
událost, kterou přerušení vyvolalo. Obsluha přerušení je zodpovědná za to, aby na jeho konci byl uveden stav procesoru do stavu jako na jejím začátku, aby výpočet přerušené úlohy nebyl ovlivněn, což se z důvodu vyšší rychlosti obvykle dělá softwarově (některé procesory umožňují uložit svůj stav pomocí speciální strojové instrukce). Na konci obsluhy přerušení je umístěna instrukce návratu (RET, někdy speciální IRET), která vyzvedne ze zásobníku návratovou adresu a tak způsobí, že z této adresy bude vyzvednuta následující strojová instrukce. Přerušená úloha tak až na zpoždění nepozná, že proběhla obsluha přerušení. Tabulka přerušení umožňuje, aby procesor mohl rozlišit více různých přerušení (rozlišených čísly), ke každému vyvolat odpovídající obsluhu přerušení (podprogram) a aby šlo jednotlivé obsluhy umístit na libovolná místa v paměti. Obsluha přerušení je obvykle uložena v ovladači, který spolu s novým hardwarovým zařízením do operačního systému instalujeme.
Typy: Vnější přerušení Vnější přerušení (též hardwarové přerušení) je označováno podle toho, že přichází ze vstupněvýstupních zařízení (tj. z pohledu procesoru přicházejí z vnějšku). Vstupně-výstupní zařízení tak má možnost si asynchronně vyžádat pozornost procesoru a zajistit tak svoji obsluhu ve chvíli, kdy to právě potřebuje bez ohledu na právě zpracovávanou úlohu. Vnější přerušení jsou do procesoru doručována prostřednictvím řadiče přerušení, což je specializovaný obvod, který umožňuje stanovit prioritu jednotlivým přerušením, rozdělovat je mezi různé procesory a další související akce. Vnitřní přerušení Vnitřní přerušení vyvolává sám procesor, který tak signalizuje problémy při zpracování strojových instrukcí a umožňuje operačnímu systému na tyto události nejvhodnějším způsobem zareagovat. Jedná se například o pokus dělení nulou, porušení ochrany paměti, nepřítomnost matematického koprocesoru, výpadek stránky a podobně. Softwarové přerušení Softwarové přerušení je speciální strojová instrukce (obvykle je jich v procesoru k dispozici několik, procesory Intel mapují všechna přerušení na softwarová přerušení). Tento typ přerušení je na rozdíl od druhých dvou typů synchronní, je tedy vyvoláno zcela záměrně umístěním příslušné strojové instrukce přímo do prováděného programu. Jedná se o podobný způsob, jako vyvolání klasickému podprogramu (podprogramem je zde ISR uvnitř operačního systému), avšak procesor se může zachovat jinak. Instrukce softwarového přerušení se proto využívá pro vyvolání služeb operačního systému z běžícího procesu (tzv. systémové volání).
Uživatelská úloha tak sice nemůže skočit do prostoru jádra operačního systému, ale může k tomu využít softwarové přerušení (kterých je omezené množství a vstupní body lze snadno kontrolovat). Při využití privilegovaného režimu může softwarové přerušení aktivovat privilegovaný stav.
14. Vyšší programovací jazyky (Java, C, C# apod.). Struktura programu, implementace příkazů a datových typů. Práce se soubory, operace vstupu a výstupu. Algoritmizace základních úloh, třídění, vyhledávání, porovnání algoritmů. (Perutka) Je to programovací jazyk s větší mírou abstrakce. Vyšší abstrakcí je míněno přiblížení zápisu zdrojového kódu programu v daném programovacím jazyce k tomu, jak problémy zpracovává svým myšlením člově !k. Nižší programovací jazyk se naopak svým zápisem přibližuje tomu, jak po technické stránce pracuje počítač (resp. jeho procesor). Vyšší programovací jazyky by měly být člověku lépe srozumitelné, než nižší programovací jazyky, čímž by měl být jednodušší vlastní vývoj programů. Programy zapsané ve vyšších jazycích jsou obvykle kratší a lépe čitelné, než zápis v nižších programovacích jazycích. Tím by měly šetřit čas programátora a zmenšit pravděpodobnost výskytu programátorských chyb. Ve vyšších programovacích jazycích je možné používat prvky přirozeného jazyka. Struktura zdrojového kódu je u vyšších programovacích jazyků logická. Další výhodou vyšších programovacích jazyků je jejich přenositelnost. Programy po malých (někdy i žádných) úpravách mohou běžet na různých počítačových platformách. Nevýhodou vyšších programovacích jazyků je fakt, že počítače umí přímo zpracovávat kód zapsaný v nejnižších programovacích jazycích (tzv. Jazyk symbolických adres). Proto musejí být programy zapsané ve vyšších programovacích jazycích překládány překladačem (kompilátorem) do nižších jazyků. Do skupiny vyšších programovacích jazyků patří v podstatě všechny programovací jazyky kromě Jazyka symbolických adres (často nesprávně označován jako Assembler) a strojového kódu.
Java Objektově orientovaný programovací jazyk. Jeden z nejpoužívanějších programovacích jazyků na světě. Díky své přenositelnosti je používán pro programy, které mají pracovat na různých systémech počínaje čipovými kartami (platforma JavaCard), přes mobilní telefony a různá zabudovaná zařízení (platforma Java ME), aplikace pro desktopové počítače (platforma Java SE) až po rozsáhlé distribuované systémy pracující na řadě spolupracujících počítačů rozprostřené po celém světě (platforma Java EE). Tyto technologie se jako celek nazývají platforma Java. Dne 8. května 2007 Sun uvolnil zdrojové kódy Javy (cca 2,5 miliónů řádků kódu) a Java bude dále vyvíjena jako open source. Vlastnosti: jednoduchý – jeho syntaxe je zjednodušenou (a drobně upravenou) verzí syntaxe jazyka C a C++. Odpadla většina konstrukcí, které způsobovaly programátorům problémy a na druhou stranu přibyla řada užitečných rozšíření. objektově orientovaný – s výjimkou osmi primitivních datových typů jsou všechny ostatní datové typy objektové.
distribuovaný – je navržen pro podporu aplikací v síti (podporuje různé úrovně síťového spojení, práce se vzdálenými soubory, umožňuje vytvářet distribuované klientské aplikace a servery). interpretovaný – místo skutečného strojového kódu se vytváří pouze tzv. mezikód (bajtkód). Tento formát je nezávislý na architektuře počítače nebo zařízení. Program pak může pracovat na libovolném počítači nebo zařízení, který má k dispozici interpret Javy, tzv. virtuální stroj Javy - Java Virtual Machine (JVM). V pozdějších verzích Javy nebyl mezikód přímo interpretován, ale před prvním svým provedením dynamicky zkompilován do strojového kódu daného počítače (tzv. just in time compilation - JIT). Tato vlastnost zásadním způsobem zrychlila provádění programů v Javě ale výrazně zpomalila start programů. V současnosti se převážně používají technologie zvané HotSpot compiler, které mezikód zpočátku interpretují a na základě statistik získaných z této interpretace později provedou překlad často používaných částí do strojového kódu včetně dalších dynamických optimalizací (jako je např. inlining krátkých metod atp.). robustní – je určen pro psaní vysoce spolehlivého softwaru – z tohoto důvodu neumožňuje některé programátorské konstrukce, které bývají častou příčinou chyb (např. správa paměti, příkaz goto, používání ukazatelů). Používá tzv. silnou typovou kontrolu – veškeré používané proměnné musí mít definovaný svůj datový typ. generační správa paměti – správa paměti je realizována pomocí automatického Garbage collectoru který automaticky vyhledává již nepoužívané části paměti a uvolňuje je pro další použití. To bylo v prvních verzích opět příčinou pomalejšího běhu programů. V posledních verzích běhových prostředí je díky novým algoritmům pro garbage collection a tzv. generační správě paměti (paměť je rozdělena na více částí, v každé se používá jiný algoritmus pro garbage collection a objekty jsou mezi těmito částmi přesunovány podle délky svého života) tento problém ze značné části eliminován. bezpečný – má vlastnosti, které chrání počítač v síťovém prostředí, na kterém je program zpracováván, před nebezpečnými operacemi nebo napadením vlastního operačního systému nepřátelským kódem. nezávislý na architektuře – vytvořená aplikace běží na libovolném operačním systému nebo libovolné architektuře. Ke spuštění programu je potřeba pouze to, aby byl na dané platformě instalován správný virtuální stroj. Podle konkrétní platformy se může přizpůsobit vzhled a chování aplikace. přenositelný – vedle zmíněné nezávislosti na architektuře je jazyk nezávislý i co se týká vlastností základních datových typů (je například explicitně určena vlastnost a velikost každého z primitivních datových typů). Přenositelností se však myslí pouze přenášení v rámci jedné platformy Javy (např. J2SE). Při přenášení mezi platformami Javy je třeba dát pozor na to, že platforma určená pro jednodušší zařízení nemusí podporovat všechny funkce dostupné na platformě pro složitější zařízení a kromě toho může definovat některé vlastní třídy doplňující nějakou speciální funkčnost nebo nahrazující třídy vyšší platformy, které jsou pro nižší platformu příliš komplikované. výkonný – přestože se jedná o jazyk interpretovaný, není ztráta výkonu významná, neboť překladače pracují v režimu „právě včas“ a do strojového kódu se překládá jen ten kód, který je opravdu zapotřebí.
víceúlohový – podporuje zpracování vícevláknových aplikací dynamický – Java byla navržena pro nasazení ve vyvíjejícím se prostředí. Knihovna může být dynamicky za chodu rozšiřována o nové třídy a funkce, a to jak z externích zdrojů, tak vlastním programem. elegantní – velice pěkně se v něm pracuje, je snadno čitelný (např. i pro publikaci algoritmů), přímo vyžaduje ošetření výjimek a typovou kontrolu.
C Počátkem 70. let 20. století jej vyvinuli Ken Thompson a Dennis Ritchie pro potřeby operačního systému Unix. V současné době je to jeden z nejpopulárnějších jazyků, zřejmě nejčastější pro psaní systémového softwaru, ale velmi rozšířený i pro aplikace. C je nízkoúrovňový, kompilovaný, relativně minimalistický programovací jazyk. Je dostatečně mocný na většinu systémového programování (ovladače a jádro OS), přičemž zbytek lze dořešit tzv. inline assemblerem, tedy metodou zápisu assembleru přímo do kódu. Zdrojový kód C je přitom mnohem čitelnější než assembler, je jednodušší ho zapsat a navíc je snáze přenositelný na jiné architektury. Proto jsou často operační systémy, překladače, knihovny a interpretry vysokoúrovňových jazyků implementovány právě v C. Mnoho dalších moderních programovacích jazyků přebírá způsob zápisu (neboli syntaxi) z jazyka C, například Java, Perl a PHP. Ukládání dat je v C řešeno třemi základními způsoby: statickou alokací paměti (při překladu), automatickou alokací paměti na zásobníku a dynamickou alokací na haldě (heap) pomocí knihovních funkcí. Jazyk disponuje jen minimální abstrakcí nad alokací: s pamětí se pracuje přes datový typ zvaný ukazatel, který drží odkaz na paměťový prostor daného typu proměnné, ale je na něm možné provádět aritmetické operace (tyto operace ale neoperují s ukazateli přímo na úrovni jednotlivých bajtů, nýbrž přihlíží k velikosti datového typu, na který ukazují – existují ale také ukazatele typu void *, které mohou odkazovat na jakýkoliv typ dat uložený v paměti.). Ukazatele tedy existují nezávisle na proměnných, na které odkazují, a je na odpovědnosti programátora, aby neukazovaly na paměť nealokovanou. Ukazatele jsou velmi mocným nástrojem, protože C jazyk povoluje ukazatele nejen na data, ale i na funkce. Současně jsou ukazatele z hlediska přenositelnosti a rizika zhroucení programu při jejich nesprávném použití Achillovou patou jazyka. Na druhou stranu programátor má plnou zodpovědnost za alokaci paměti, není zde tedy závislost na automatickém dealokátoru paměti (garbage collector). Jazyky Java a C#, oba odvozené od C, používají méně univerzální způsob odkazování alokovaných proměnných, který snižuje pravděpodobnost chyby v programu. Jazyk C++, původně rozšíření jazyka C, ovšem zodpovědnost programátora za alokaci zachoval. Datové typy: char - Používá se pro znaky int - Používá se pro celá čísla float - Používá se pro desetinné číslo s plovoucí řádovou čárkou double - Používá se pro desetinné číslo s plovoucí řádovou čárkou s dvojnásobnou přesností void - Používá se pokud nepotřebujeme žádnou hodnotu (např. u funkcí) Řídící příkazy Řídící příkazy určují průběh zpracovávání programu. Jako takové tvoří páteř programů.
if - Příkaz if je jedním z příkazů jazyka C pro větvení programu (někdy nazývané také jako podmíněné příkazy). Jeho činnost je určena výsledkem testu podmínky, která je vyhodnocena jako pravdivá, nebo nepravdivá. Jednoduše řečeno, podmíněné činí rozhodnutí na základě vyhodnocení nějaké podmínky. if - else - K příkazu if můžete přidat else. Pokud tak učiníte, tak programu řeknete, co má dělat, i pokud bude podmínka nepravdivá. switch - Příkaz switch slouží k výběru jedné z několika větví programu, která se má provést v závislosti na nějaké celočíselné hodnotě. Podle hodnoty celočíselného výrazu se vybere jedna z větví case. Příkaz break na konci každé větve není povinný, ale pokud tam není, začne se po skončení větve provádět další větev v pořadí bez ohledu na hodnotu výrazu. Chceme-li tedy pro každou hodnotu provádět jedinou větev, je break nutný na konci každé větve kromě poslední. Větev default (je-li přítomna) se vykoná v případě, že hodnota výrazu není rovna ani jedné z hodnot uvedených za příkazy case. for - Příkaz cyklu for je jedním ze tří příkazů cyklu v jazyku C. Umožňuje opakovat jeden, nebo více příkazů. Cyklus for je mnohými programátory v jazyku C považován za jeho nejpružnější příkaz. Cyklus for se používá pro zadaný počet opakování příkazu, nebo bloku příkazu. while - Cyklus while je cyklus s podmínkou na začátku. Napřed se testuje podmínka, je-li platná, pak se provede tělo cyklu a znovu se testuje podmínka. Není-li platná, program pokračuje za cyklem. Není-li tedy podmínka platná při prvním příchodu na cyklus, neprovede se cyklus ani jednou. do-while - Cyklus do-while je cyklus s podmínkou na konci. Napřed se provede tělo cyklu, pak se testuje podmínka. Je-li platná, cyklus se provede znovu. Není-li platná, program pokračuje za cyklem. Tento cyklus se tedy provede vždy nejméně jednou. break a continue - Příkaz break slouží k okamžitému opuštění cyklu, bez ohledu na platnost podmínky. Příkaz continue slouží ke skoku na konec cyklu a znovu testování podmínky (v cyklu for skočí na inkrementaci, pak se znovu testuje podmínka, v cyklech while a do-while skočí na test podmínky).
C++ xC++ je objektově orientovaný programovací jazyk, který vyvinul Bjarne Stroustrup a další v Bellových laboratořích AT&T rozšířením jazyka C. C++ podporuje několik programovacích stylů (paradigmat) jako je procedurální programování, objektově orientované programování a generické programování, není tedy jazykem čistě objektovým. V současné době patří C++ mezi nejrozšířenější programovací jazyky. Jazyk C je až na několik jasně definovaných výjimek podmnožinou C++. Jak uvádí Bjarne Stroustrup, všechny programy uvedené ve slavné učebnici jazyka C The C Programming Language od Briana W. Kernighana a Dennise M. Ritchieho jsou zároveň programy v C++.
C# vysokoúrovňový objektově orientovaný programovací jazyk vyvinutý firmou Microsoft zároveň s platformou .NET Framework, později schválený standardizačními komisemi ECMA (ECMA-334) a ISO (ISO/IEC 23270). Microsoft založil C# na jazycích C++ a Java (a je tedy nepřímým potomkem jazyka C, ze kterého čerpá syntaxi). Vlastnosti:
V C# neexistuje vícenásobná dědičnost - to znamená, že každá třída může být potomkem pouze jedné třídy. Toto rozhodnutí bylo přijato, aby se předešlo komplikacím a přílišné složitosti, která je spojena s vícenásobnou dědičností. Třída může implementovat libovolný počet rozhraní. Neexistují žádné globální proměnné a metody. Všechny funkce a metody musí být deklarovány uvnitř tříd. Náhradou za ně jsou statické metody a proměnné veřejných tříd. V Objektově orientovaném programování se z důvodu dodržení principu zapouzdření často používá vzor, kdy k datovým atributům třídy lze zvenčí přistupovat pouze nepřímo a to pomocí dvou metod get (accessor) a set (mutator). V C# lze místo toho definovat tzv. Property, která zvenčí stále funguje jako datový atribut, ale uvnitř Property si můžeme definovat get a set metody. Výhodou je jednodušší práce s datovým atributem při zachování principu zapouzdření. C# je typově bezpečnější než C++. Jediné výchozí implicitní konverze jsou takové, které jsou považovány za bezpečné jako rozšiřování Integerů (např. z 32 bitového na 64 bitový) nebo konverze z odvozeného typu na typ rodičovský. Neexistuje implicitní konverze z typu Integer na Boolean, ani mezi výčtovým typem enum a typem Integer. C# neobsahuje a ani nepotřebuje dopřednou deklaraci - není důležité pořadí deklarace metod. Jazyk C# je case sensitive - to znamená, že rozlišuje mezi velkými a malými písmeny . Identifikátory "hodnota" a "Hodnota" tedy nejsou na rozdíl od VB.NET ekvivalentní. Common Type System je unifikovaný typový systém, používaný všemi jazyky pod .NET Framework, tedy i jazykem C# (dále například VB.NET). Všechny typy, včetně primitivních datových typů jako je Integer, jsou potomky třídy System.Object a dědí od ní i všechny její metody jako například ToString().
Vstup a výstup C Vstup a výstup v jazyce C je v informatice řešen souborem knihovních funkcí ze standardní knihovny jazyka C (libc, glibc a podobně), jejíž prototypy jsou deklarovány v hlavičkovém souboru <stdio.h>. Programovací jazyk C při operacích vstupu a výstupu využívá proudy bytů a nerozlišuje mezi vstupními a výstupními zařízeními, rourami a soubory, přičemž definuje standardní proudy (stdin, stdout a stderr). Proudy Na rozdíl od některých dřívějších programovacích jazyků, nemá jazyk C přímou podporu pro přímý přístup k datům souborů. Pro čtení uprostřed souboru musí programátor nejprve vytvořit proud, ve kterém pak pomocí funkce fseek nastaví ukazatel do místa v souboru, ze kterého následně bude číst nebo zapisovat. Použití proudů pro práci se soubory bylo zpopularizováno operačním systémem UNIX, který byl vyvíjen ve stejné době, jako programovací jazyk C. Celá řada moderních operačních systémů proudy z unixových systémů zdědila stejně, jako je mnoho programovacích jazyků zdědilo z jazyka C (např. PHP). Též do standardních knihoven jazyka C++ se promítají proudy (tzv. iostream). Otevírání souboru Soubor je otevírán použitím funkce fopen, která vrací I/O proud. Ten je připojen k danému souboru nebo jinému blokovému zařízení umožňujícímu operace čtení a zápis. V případě, že funkce selže, vrací nulový ukazatel (NULL). Související knihovní funkce freopen vykonává stejnou operaci, avšak nejprve zavře otevřený proud, který je uveden jako doplňující parametr. I/O proud je definován takto:
Funkce fopen je wrapper, který na vyšší úrovni obaluje jednoduché systémové volání open jádra unixového operačního systému. Stejným způsobem jako fopen pracuje i funkce fclose, která poskytuje obálku pro systémové volání jádra close. Struktura FILE jazyka C se velmi často shoduje se souborovými deskriptory používanými v unixových systémech. V POSIXu je definována funkce fdopen, která inicializuje I/O proud z existujícího deskriptoru, přestože deskriptory jsou čistě unixová záležitost a nejsou obsaženy ve standardech jazyka C. Parametr mode, který využívají funkce fopen nebo freopen, musí být řetězec začínající jednou z následujících sekvencí či jejich kombinací:
Označení „b“ znamená binární. Standardy jazyka C poskytují dva typy souborů – textové a binární, ačkoli operační systém nemusí být schopen je rozlišovat. Textový soubor V režimu textového souboru je text uspořádán v řádcích, jejichž konce jsou označeny znakem nového řádku (zkratka EOL). Unixové systémy označují nový řádek znakem LF, zatímco DOS a Microsoft Windows používají kombinaci CR/LF. Při čtení z textového souboru je obvykle mapována sekvence EOL na znak LF, což slouží ke zjednodušení zpracování v programu. V případě, že je textový soubor zapisován, převádí se před vlastním zápisem EOL automaticky na znaky, které daný operační systém používá. Binární soubor V režimu binárního souboru je obsah souboru čten a zapisován operačním systémem bez úprav (obsah je doručen programu bez automatického převodu, tzv. přímý přístup, anglicky raw). Znak „+“ (režim aktualizace)
Když je soubor otevřen v režimu aktualizace (znak „+“ na druhé nebo třetí pozici), může být na daném proudu použito čtení i zápis, avšak je-li po operaci zápisu nemůže být volána funkce čtení bez toho, aby mezi nimi byla volána funkce fflush nebo funkce pro změnu pozice ukazatele (fseek, fsetpos nebo rewind). Stejně tak čtení nemůže být následováno zápisem bez toho, aby mezi nimi byla též volána funkce pro změnu pozice ukazatele. Automatické vytvoření souboru
Pokud při volání funkce otevření souboru v režimu zápisu nebo připojení za konec souboru požadované jméno neexistuje, pokusí se funkce soubor požadovaného jména vytvořit. Pokud operace selže, vrací se hodnotu NULL. Uzavření proudu Funkce fclose pracuje pouze s jedním argumentem, a to s ukazatelem na souborovou strukturu proudu určeného k zavření. Po zavření se uvolní paměť vyhrazená pro strukturu FILE * a vyprázdní se vyrovnávací paměť. Bez opětovného otevření proudu již není práce se souborem možná. Počet otevřených souborů je omezen, proto jestliže se souborem nebudeme již
pracovat, měli bychom jej uzavřít. Pokud proud neuzavřeme pomocí příkazu, uzavře se sám po ukončení programu.
Ostatní jazyky Všechny ostatní, dnes používané jazyky vycházejí z C takže to je přibližně stejné. V jazyce java je např třída File atd.
Algoritmizace základních úloh Řadící algorytmy Selection sort (zkráceně Selectsort) je jednoduchý algoritmus uspořádávání s časovou složitostí O(N^2). Pro svou jednoduchou implementaci a nízký overhead bývá často používán pro uspořádávání malých množství dat. Princip 1. Najdeme prvek s nejmenší hodnotou v posloupnosti dat 2. Zaměníme ho s prvkem na první pozici 3. Na první pozici se nyní nachází správný prvek, zbytek posloupnosti se uspořádá opakováním těchto kroků pro zbylých n-1 prvků, dokud je n > 1 Implementace C:
Diagram
Insertion sort je jednoduchý řadicí algoritmus založený na porovnávání. Algoritmus Insert Sort pracuje tak, že prochází prvky postupně a každý další nesetříděný prvek zařadí na správné místo do již setříděné posloupnosti. Je to jeden z nejrychlejších algoritmů s kvadratickou časovou složitostí. Je asymptoticky pomalejší než pokročilé algoritmy jako třeba quicksort nebo mergesort, ale zato má jiné výhody: - jednoduchá implementace - efektivní na malých množinách - efektivní na částečně seřazených množinách (běží v čase O(N + d), kde d je počet transpozic prvků množiny) - efektivnější než většina ostatních O(N^2) algoritmů (selection sort, bubble sort), průměrný čas je N^2/4 a v nejlepším případě je dokonce lineární - řadí stabilně (nemění vzájemné pořadí prvků se stejnými klíči) - vyžaduje pouze O(1) paměti (kromě vlastního vstupu) - je to online algoritmus, dokáže řadit data tak, jak přicházejí na vstupu Ipmlementace:
Diagram
Bubble sort (též řazení záměnou) je implementačně jednoduchý řadicí algoritmus. Algoritmus opakovaně prochází seznam, přičemž porovnává každé dva sousedící prvky, a pokud nejsou ve správném pořadí, prohodí je. Porovnávání prvků běží do té doby, dokud není seznam seřazený. Pro praktické účely je neefektivní, využívá se hlavně pro výukové účely či v nenáročných aplikacích. Algoritmus je univerzální (pracuje na základě porovnávání dvojic prvků), pracuje lokálně (nevyžaduje pomocnou paměť), je stabilní (prvkům se stejným klíčem nemění vzájemnou polohu), patří mezi přirozené řadicí algoritmy (částečně seřazený seznam zpracuje rychleji než neseřazený). Průměrná i nejhorší asymptotická složitost bubble sortu je O(n^2). Tento algoritmus řazení je jedním z nejpomalejších, oproti jiným algoritmům se stejnou složitostí vyžaduje velké množství zápisů do paměti a tím neefektivně pracuje s cache procesoru. Výhody X nevýhody Bublinkové řazení je z hlediska naprogramování nejjednodušším algoritmem pro třídění. Výhodou rovněž je, že je stabilní, tzn. nemění pozici prvků které při porovnávání vyhodnoceny jako ekvivalentní. Bublinkové třídění je jeden z mála třídících algoritmů, kterému stačí sekvenční přístup k datům (algoritmus nepotřebuje ve tříděné posloupnosti provádět žádné skoky). V minulosti se proto používal ke třídění dat na páskových médiích, dnes jej lze s výhodou použít například při třídění jednosměrně zřetězeného spojového seznamu. Bublinkové třídění se používá například pro výuku programování, nebo pro třídění malých polí, nebo polí která jsou již částečně setříděna. Vzhledem k vysokému výkonu současných počítačů může mít "malé" pole i několik tisíc prvků, avšak pro třídění opravdu velkých polí je "bubblesort" naprosto nevhodný. Pokud trvá setřídění např. 10 prvků dlouhého pole jednotku času, pak při bublinkovém třídění 1000 prvků spotřebujeme 10000 jednotek času, zatímco při použití kvalitního algoritmu pouze 200 jednotek času. Implementace:
Diagram:
Quicksort neboli rychlé (rekurzivní) řazení do tříd je jeden z nejrychlejších známých algoritmů řazení založených na porovnávání prvků. Jeho průměrná časová složitost je pro algoritmy této skupiny nejlepší možná (O(N log N)), v nejhorším případě (kterému se ale v praxi jde obvykle vyhnout) je však jeho časová náročnost O(N²). Další výhodou algoritmu je jeho jednoduchost. Základní myšlenkou quicksortu je rozdělení řazené posloupnosti čísel na dvě přibližně stejné části (quicksort patří mezi algoritmy typu rozděl a panuj). V jedné části jsou čísla větší a ve druhé menší, než nějaká zvolená hodnota (nazývaná pivot). Pokud je tato hodnota zvolena dobře, jsou obě části přibližně stejně velké. Pokud budou obě části samostatně seřazeny, je seřazené i celé pole. Obě části se pak rekurzivně řadí stejným postupem. Největším problémem celého algoritmu je volba pivota. Pokud se daří volit číslo blízké mediánu řazené části pole, je algoritmus skutečně velmi rychlý. V opačném případě se jeho časová složitost blíží O(N^2). Přirozenou metodou na získání pivota se pak jeví volit za pivot medián. Hledání mediánu (a obecně k-tého prvku) v posloupnosti běží v lineárním čase k počtu prvků, tím dostaneme složitost O(Nlog2N) v nejhorším případě. Nicméně tato implementace není příliš rychlá z důvodu vysokých konstant schovaných v O notaci. Proto existuje velké množství alternativních způsobů, které se snaží efektivně vybrat pivota co nejbližšího mediánu. Zde je seznam některých metod: První prvek – popřípadě kterákoli jiná fixní pozice. Velmi nevýkonná především na částečně seřazených množinách. Náhodný prvek – často používaná metoda. Lze dokázat, že pokud je pozice pivotu skutečně náhodná, algoritmus poběží v O(N log N)). Skutečně náhodná čísla generují ale pouze hardwarové generátory, které nemusí dodávat data dostatečně rychle. V praxi mnohdy stačí použít pseudonáhodný algoritmus. Metoda mediánu tří – případně pěti, či libovolné jiné konstanty. Pomocí pseudonáhodného algoritmu (používají se i fixní pozice) se vybere X prvků z množiny, ze kterých se použitím některého primitivního řadicího algoritmu najde medián a ten je zvolen za pivota. Přestože Quicksort nemá zaručenou časovou složitost O(N log2 N)), reálné aplikace a testy ukazují, že na pseudonáhodných datech je vůbec nejrychlejší ze všech obecných řadicích algoritmů (tedy i rychlejší než Heapsort a Mergesort, které jsou formálně rychlejší). Maximální časová náročnost O(N²) ho však diskvalifikuje pro použití v kritických aplikacích. Výhody X nevýhody: Jak již bylo zmíněno, tento algoritmus je ve většině běžných případů nejrychlejší, což může být při řazení rozsáhlých posloupností hlavním požadavkem. Obecně je nestabilní. Může být upraven tak, aby byl stabilní, avšak na to je potřeba dodatečná paměť. Rychlost výpočtu je většinou vynikající, avšak tento algoritmus vyžaduje více než jiné pečlivou implementaci. Zde uvedená základní rekurzivní verze algoritmu (tj. bez sofistikovanějšího výběru pivota a bez modifikace proti přetečení zásobníku), může být pro nasazení v praxi naprosto nevhodná. Základní quicksort je nejpomaleší při třídění již setříděných nebo převážně setříděných polí. Vzhledem k tomu že nejde o stabilní řadící algoritmus a vzhledem k nutnosti obcházet jeho nedostatky mohou být knihovní funkce pro quicksort na různých systémech a v různých knihovnách implementovány různým způsobem. To znamená, že při zavolání knihovní
funkce nebude pole setříděno vždy stejně, což je potenciálním zdrojem problémů s přenositelností software. Navíc na slabším hardware (například u jednoduchých embedded systémů) nebo při třídění velkých polí může prostoduchá implementace quicksortu vést dokonce i k přeplnění zásobníku a pádu systému. Je třeba si uvědomit, že zde uvedený algoritmus pouze demonstruje funkční princip quicksortu. Jde o rekurzivní algoritmus a každé rekurzivní voládní spotřebovává paměť zásobníku, která bývá u embedded procesorů často omezená. Tento problém se nemusí při ladění projevit, protože množství spotřebované paměti závisí na tříděných datech. Navzdory výše zmíněným problémům jde v drtivé většině případů o nejrychlejší známý univerzální algoritmus pro třídění polí v operační paměti počítače. Ne však nejsnadněji použitelný. Implementace C:
Diagram:
Merge sort je řadicí algoritmus, jehož průměrná i nejhorší možná časová složitost je (O(N log N)). Algoritmus je velmi dobrým příkladem programátorské metody rozděl a panuj. Algoritmus pracuje následovně: 1) Rozdělí neseřazenou množinu dat na dvě podmnožiny o přibližně stejné velikosti 2) Seřadí obě podmnožiny 3) Spojí seřazené podmnožiny do jedné seřazené množiny Algoritmus vytvořil v roce 1945 John von Neumann. Výhody X nevýhody Velkou nevýhodou oproti algoritmům stejné rychlostní třídy (např. heapsort) je, že Mergesort pro svou práci potřebuje navíc pole o velikosti N. Existuje sice i modifikace Mergesortu, která toto pole nepotřebuje, ale její implementace je velmi složitá a kvůli vysoké režii i pomalá. Kromě toho je Mergesort ve většině případů pomalejší než quicksort nebo heapsort. Na druhou stranu je Mergesort stabilní řadicí algoritmus, lépe se paralelizuje a má vyšší výkon na sekvenčních médiích s nižší přístupovou dobou. Velkou výhodou proti quicksortu je, že čas potřebný pro třídění je téměř nezávislý na počátečním řazení tříděné posloupnosti. Vyšší spotřeba paměti není tak velkým problémem jak se může na první pohled zdát, protože při třídění nemusíme manipulovat přímo s položkami tříděného pole, ale pouze s polem indexů, které v paměti většinou zabírá mnohem méně místa. Při použití více polí indexů můžeme mít pole setříděné "současně" podle více kritérií. V mnoha implementacích programovacích jazyků je Mergesort implicitním řadicím algoritmem (v Perlu 5.8, v Javě nebo v GNU C Library). Implementace:
Diagram:
Heapsort neboli řazení haldou je jeden z nejlepších obecných algoritmů řazení, založených na porovnávání prvků. Byť je v průměru o něco pomalejší než dobře napsaný quicksort, je jeho zaručená časová náročnost O(N log N) a dokáže řadit data na původním místě (má pouze konstantní nároky na paměť). Heapsort není stabilní řadící algoritmus. Základní myšlenkou tohoto kroku je využití datové struktury označované jako halda (angl. heap). Tato struktura umí velmi efektivně provést operaci vložení prvku a operaci výběr největšího prvku. Proto lze pomocí haldy seřadit dodaná data od největšího k nejmenšímu prostě pomocí jejich vložení do haldy a následného postupného vybírání největšího prvku. V praxi lze haldu vystavět přímo ve vstupním poli tím způsobem, že jsou následovníci prvku n uloženi do prvků 2n a 2n+1 (při indexování od jedničky), a také následné vybírání prvků lze provádět pouhým přeuspořádáváním dat v tomto poli. Pro oba kroky je využit pomocný algoritmus, který v čase O(log(n)) dokáže prodloužit haldu zpředu o jeden prvek. Přesněji řečeno - pokud všechny prvky s indexy L+1 až R (včetně krajních prvků) splňují pravidla haldy, po provedení pomocného algoritmu budou splňovat podmínky haldy prvky s indexy L až R. Je dobré si uvědomit, že prvky s indexy (N/2+1 až N) splňují pravidla haldy automaticky - není je s čím porovnávat. První krok haldového řazení spočívá v postupném prodlužování haldy z rozsahu (N/2 až N) na (1 až N). Po provedení N/2 kroků je halda vytvořena. Halda, která splňuje popsané podmínky, má na vrcholu (index 1) prvek s největší hodnotou. Ve druhém kroku haldového řazení se tento prvek vymění za poslední prvek pole. Tak se na konec pole dostane největší prvek (tím je zařazen na správné místo) ale prvkem, přesunutým z konce pole dojde k porušení pravidel haldy. Je třeba spustit pomocný algoritmus, tentokrát pro prvky s indexy (1 až N-1). Výše zmíněný postup se opakuje pro stále se zmenšující haldu. Při každém kroku je na vrcholu haldy největší ze zbývajících prvků, a ten je výměnou s posledním prvkem této menší haldy zařazen na správné pořadí v poli.
Vyhledávání Binární vyhledávání (nebo také metoda půlení intervalu) je vyhledávací algoritmus na nalezení zadané hodnoty v uspořádaném seznamu pomocí zkracování seznamu o polovinu v každém kroku. Binární vyhledávání najde medián, porovná s hledanou hodnotou a na základě výsledku porovnání se rozhodne o pokračování v horní nebo dolní části seznamu a rekurzivně pokračuje od začátku. Binární vyhledávání je algoritmus s logaritmickou časovou složitostí O(log n). Přesněji, je potřeba 1 + log2N iterací na získání výsledku. Je značně rychlejší než lineární vyhledávání, které má časovou složitost O(n). Nicméně vyžaduje, aby data byla setříděna, je tudíž vhodný jen pro určitou množinu problémů. Dá se vyjádřit rekurzivně i iterativně; ve většině programovacích jazyků je však rekurzivní zápis mnohem elegantnější. Iterativní varianta algoritmu je však (díky absenci režie související s voláním funkcí) mírně rychlejší. Binární vyhledávání je příkladem algoritmu typu rozděl a panuj. Rekurzivní implementace Python:
Implementace cyklem Python:
Lineární vyhledávání (také známé jako sekvenční vyhledávání) je vyhledávací algoritmus vhodný na nalezení určité hodnoty v seznamu. Funguje na principu procházení všech prvků seznamu. Lineární vyhledávání má časovou složitost O(N). V případě náhodného rozložení je průměrně potřeba N/2 porovnání. Nejlepší případ nastane tehdy, když se hledaná hodnota nachází na prvním místě v seznamu, v tomto případě je potřeba pouze jedno porovnání. Nejhorší případ nastane tehdy, když se hodnota v seznamu vůbec nevyskytuje; v tom případě je potřeba N porovnání. Výhodou lineárního vyhledávání, oproti efektivnějším algoritmům jako například binární vyhledávání, je možnost použití i na neuspořádaných seznamech. Implementace Python:
Porovnání
Vyhledávací algoritmy Binární vyhledávání
Lineární vyhledávání
Pro neuspořádaný seznam
ne
ano
Složitost
O(log n)
O(N)
15. Organizace paměti programu ve vyšším programovacím jazyce, základní části paměti a jejich význam. Referenční typy. Datový typ ukazatel. Rezervování a uvolňování paměti. Statické a dynamické přidělování paměti. Dynamické datové struktury, vytvoření, základní operace Virtuální paměť Virtuální paměť byla zavedena pro zjednodušení práce s pamětí u jednotlivých aplikací především pak s ohledem na multitasking a zabezpečení pamětí mezi jednotlivými aplikacemi. Aplikace si myslí, že mají k dispozici celý adresní prostor, ale o alokaci paměti se stará OS.
Virtuální paměť může být alokována jako stránka (page) s konstantní velikostí umožňující rychlejší práci s rozměrnými daty, ale části stránky mohou zůstat nevyužité nebo jako segment s proměnlivou velikostí, mají lepší využití fyzické paměti, ale mohou zvyšovat její fragmentaci. Další výhodou virtuální paměti je fakt, že se celá ani nemusí vejít do operační paměti, nepotřebné úseky (použité jinou neaktivní aplikací) je možné uložit na disk, odtud i tolik otravné swapování, pokud přepínáme mezi aplikacemi s vyšší paměťovou náročností.
Virtuální paměť a Windows (pro zajímavost až nebudete mít o čem mluvit, je to ze zkušenosti)
Operační systém Windows používá funkce spojené s virtuální pamětí pro bezpečnou výměnu dat mezi aplikacemi či knihovnami. Některé API funkce vyžadují použití speciálních alokačních mechanismů, případně označení místa paměti jako sdíleného, aby zabezpečili dobrou funkčnost a bezpečnost určitých datových operací. Tato funkčnost však nebyla uspokojivě vyřešena, ve Windows 9x prakticky správně nefungovala, bylo možné přepsat libovolnou adresu a při vývoji aplikací se nezřídka stávalo, že se GDI najednou rozhodlo kreslit texty nakřivo, protože mu někdo přepsal jeho chráněné místo v paměti. Pokrokem pak byly Windows verze 5 (2000 a XP), jisté stránky paměti už jsou úspěšně zamčené a nedají se jednoduše poškodit, funguje i lepší správa paměti a její uvolňování při (násilném) ukončení aplikace. Další pokrok přišel s Windows Vista (verze 6) a s ním i technologie UAC, především pak při práci s COM objekty, zatímco objekty (objekty je v tomto smyslu myšlena aplikace + jí alokované COM objekty a rozhraní, např. pomocí ActiveX s GUID) běžící ve standardním uživatelském režimu mohou mezi sebou vyměňovat data a t i ve smyslu statických konstant. Například máme-li funkci, která jako svůj návratový parametr vrací string (PChar), pak nyní vše bude fungovat pořádku, pokud ale totéž budu požadovat po elevovaném objektu (běžicím v administrátorském režimu), výsledek bude chybný, systém nepovolí použití paměti programu elevované části kódu, stejně tak nefungují ani funkce drag&drop a další. Pro správnou funkčnost je nutné předat elevovanému objektu pointer, který má vyplnit (nejlépe ještě pomocí funkce VirtualAlloc, případně GlobalAlloc, aby bylo zaručeno, že oblast bude sdílena oběma procesy), jelikož elevovaný objekt má přístup do všech nižších částí a může tedy operaci úspěšně provést. Aby nebylo vše ještě tak jednoduché, tak se nám do cesty staví tokeny, které aplikace musí mít pro přístup do určitých systémových funkcí atd.
Paměť programu Je vyobrazen standardní model používaný ve Windows, u jiných OS se může lišit. Odtud i rozsah virtuální paměti 0-0x7fffffff -> 2 GB na proces.
Text Paměť programu (instrukce). Obsahuje vlastní kód a konstanty. OS označena jako jen pro čtení (ve Windows lze měnit pomoci funkcí s virtuální pamětí). Data Inicializované (během kompilace) statické a globální proměnné. BSS Neinicializované (během kompilace) statické a globální proměnné. Heap Dynamicky alokovaná data. Stack Lokální data procedur (alokována po callu, proto nemůžeme mít velké členské proměnné, pozor především na buffery při komunikaci a pole, mohou způsobit přetečení stacku).
Stack navíc slouží k předávání parametrů funkcí a ukládání návratových adres při callu. Předávání parametrů se navíc řídí volacími konvencemi: ● cdecl – standardní konvence používaná většinou C kompilátorů. Parametry jsou pushnuty do stacku v pořadí zprava doleva, návratový parametr je v EAX registru, pokud je návratový parametr float, nachází se v fp0 registru. Volající je zodpovědný za vyčištění stacku.
●
●
●
●
pascal – používaná Windows 3.x, Borland Delphi 1.x. Obráceně k cdecl používá pořadí zleva doprava a volaná funkce je zodpovědná za vyčištění stacku (musí odpopovat až na návratovou adresu). stdcall – standardní konvence používaná Windows 32 API a .NET Frameworku. Parametry pushnuty na stack zprava doleva, návratová hodnota v EAX, volaná funkce je zodpovědná za vyčištění stacku. fastcall – různá interpretace. Microsoft nebo GCC předává první dva parametry (zleva doprava) v ECX a EDX, zbylé jsou pushnuty do stacku zprava doleva. Borland tři argumenty do registrů EAX, ECX a EDX, zbylé jsou pushnuty do stacku, vše zleva doprava (také nazývána register). safecall – využívá Borldand Delphi při volání COM objektu (jejich rozhraní) pro automatické vytváření výjimek z návratového parametru HResult daného objektu, pokud dojde k selhání.
Ještě druhý obrázek obsazení paměti - je z přednášek z PJC:
Další sekce spustitelného souboru (méně podstatné): ● Reloc – Udržuje tabulku relokací (relokace je použita během dynamického připojovaní externích knihoven). ● Rsrc – Resource soubory (.RES). ● CRT – Používané Microsoftem pro volání konstruktorů statických tříd apod. před voláním WinMain. ● Idata – Obsahuje informace o funkcích a datech importovaných z jiných knihoven. ● Edata – Obsahuje informace o funkcích a datech exportovaných z aktuálního spustitelného souboru.
● ●
Tls – Definuje data, která mají mít kopii pro každé vlákno zvlášť (nejsou tedy přítomny v data ani BSS). Rdata – Obsahuje dodatečné informace o souboru a pro ladění.
Alokace paměti ● Jméno proměnné je symbolická adresa paměťového prostoru, kde je proměnná uložena ● Statická x Dynamická alokace Statická alokace ● Můžeme použít pokud známe předem paměťové nároky našeho programu ● Překladač alokuje paměť se spuštěním programu ● Statická alokace je poměrně účinná ● neleze ji použít např. u rekurzivních funkcí, kde je třeba alokovat vždy nový blok paměti dynamicky dle počtu volání ● Statická alokace – datová oblast paměti ● Globální proměnné pouze statická alokace Dynamické přidělování paměti Dynamická paměť je alokována na heapu (C – malloc, Pascal – GetMem) a musíme dbát na její opětovnou dealokaci (C – free, Pascal – FreeMem) jinak způsobíme tzv. memory leak. Navíc je veškerá paměť uvolněna při konci programu, ale dobrý programátor si ji vždy sám dealokuje. Pamět nemá symbolickou adresu a přistupuje se k ní pomocí ukazatele (pointeru). Přidělení paměti v C ● pomocí volání funkce malloc() ● parametr je typu unsiged int a udává počet Bytů, které se mají alokovat ● vrací pointer typu void na právě alokovanou paměť (na první prvek alokované paměti) ● vrací NULL pokud není dost místa v paměti
Uvolňování paměti v C ● Je vhodné paměť uvolnit hned jak jí nebudeme potřebovat ● funkce free() ● parametr typu void ukazuje na začátek bloku co se má uvolnit ● POZOR free nemění hodnotu parametru ● Tedy třeba jen ručně nastavit na NULL free((void *)p_c); p_c = NULL; Zásobník (je v otázce 16, ale zde aspoň nějaké základní info) ● Pro uložení parametrů funkcí a lokálních proměnných definovaných ve funkcích ● po skončení běhu funkce se proměnné této funkce v zásobníku uvolní ● při dalším volání se znovu založí, tedy nelze takto předávat hodnoty mezi funkcemi
Garbage collector Programátor sám nedealokuje dynamickou paměť, namísto toho pouze smaže (vynuluje) nebo přealokuje ukazatele, systém (případně framework) při nedostatku místa v paměti (nebo i v pravidelných časových intervalech, případně tehdy, není-li procesor zaneprázdněn) provede kontrolu pointerů, pokud zjistí, že nějaké místo v heapu je neobsazené, jeho obsah automaticky uvolní (v případě objektu jej napřed zruší). Používá Java nebo Microsoft .NET Framework (Visual C++, Visual C#, Visual Basic, ale i Delphi v. 8 podporující .NET). Referenční datové typy (platí pro Javu, a asi i C# a Python - kdo ví ať doplní :+) Referenční datové typy jsou objekty a pole. Hodnota referenční proměnné je odkaz (reference) do paměti na místo, kde je objekt (nebo pole) uložen. V jiných programovacích jazycích se používá pro tento účel pointerů (ukazatelů do paměti), v Javě se přímo s pamětí nepracuje, místo pointerů se používají referenční proměnné. Typ null je prázdná hodnota pro referenční typy a znamená, že chybí odkaz na objekt resp. pole. Jelikož referenční proměnná obsahuje pouze odkaz na objekt, nikoli objekt samotný, přiřazením její hodnoty jiné proměnné se přiřadí opět pouze reference na původní objekt, nikoli jeho samotná data tak, jak to bylo u primitivních datových typů. Porovnejte přiřazení v následujícím příkladu:
Referenční model Deklarace proměnné – přidělení paměti pro uchování reference (odkazu, ukazatele), deklarací proměnné ještě není alokována paměť pro hodnotu příslušného typu, rozumnou číselnou hodnotu reference neumíme získat: Scanner sc; Přidělení paměti v jazyce Java zajistíme operátorem new – použití závisí na konkrétním referenčním typu – zda se jedná o pole nebo třídu: sc = new Scanner(System.in); Typ ukazatel /pointer ● Ukazatel je základním stavebním kamenem dynamických datových struktur v jazycích jako C nebo Pascal.
● ● ● ● ● ●
Nezavádí se deklarací v deklarační části programu, ale pomocí speciálního příkazu v těle programu. Ukazatel v sobě uchovává adresu prvku v operační paměti počítače. Adresa, kterou ukazatel obsahuje, může ukazovat do libovolné části operační paměti. Konkrétní typ ukazatele je určen dle datového typu dynamické proměnné, na kterou ukazatel ukazuje. Každý nový ukazatel tedy slouží jedné dynamické proměnné. Poznámka: http://dl.dropbox.com/u/17987360/15c.pdf - zde přednáška z předmětu PJC věnující se pointerům v jazyce C
Dynamické struktury ● Dynamicky alokovaná pole ● Zřetězené pointery – struktura (rekord) která obsahuje ukazatel na následující prvek ● Objekty – každý objekt zabírá nějaké místo v paměti, alokuje se při vytvoření a dealokuje při zrušení. ● Kolekce – speciální typ objektu umožňující kombinaci funkcí jako dynamického pole a zřetězených pointerů, často umožňuje využití iterátorů a dalších složitějších operací ● String – zálečí na dané implementaci jazyka. V Object pascalu (Delphi, FreePascal při použití direktivy huge strings překladače) je to varianta dynamického pole, vytvořená aby byla kompatibilní s typem PChar Windows API, klasický Pascal (nebo OP bez výše zmíněné direktivy nebo jako typ ShortString) definuje stringy o maximální velikosti 255 bytů, přičemž na pozici 0 se nachází jeho délka. C využívá stringů jako dynamicky alokovaných polí, ale práce s nimi je oproti Pascalu složitější. C++ umožňuje implementovat stringy pomocí tříd CString (MFC nebo CLR) ● Poznámka: http://dl.dropbox.com/u/17987360/15f.pdf - zde přednáška z ADA věnující se ADT (jaké jsou, k čemu se hodí a jaké jsou nad nimi operace, příklady implementací)
16. Členění programu v jazyce vyšší úrovně. Metody, funkce, procedury, makra. Parametry metod, procedur a funkcí a způsoby jejich předávání. Globální a lokální proměnné. Rekurze a její použití. Rekurzivní a nerekurzivní realizace vybraných algoritmů. Využití zásobníku programu. Členění programu Vyšší (problémově orientované) programovací jazyky jsou podstatně srozumitelnější, struktura jejich zdrojových kódů je logická, nejsou závislé na strojových principech počítače. Do strojového kódu se převádějí kompilátorem (případně se rovnou spouštějí interpretrem). V praxi je vyšší programovací jazyk vše, co není jazyk symbolických adres, to znamená: C/C++/C#, Java, Pascal, Basic, Prolog, Lisp, Algol, Fortran,… Často se uvádí, že jazyk C je jakýmsi přechodem mezi vyššími a nižšími jazyky, má však blíže k vyšším. Metody, funkce, procedury Procedury a funkce tvoří posloupnosti instrukcí, které potřebujeme v programu provádět na různých souborech dat nebo na různých místech programu. Procedura nebo funkce může být po deklaraci použita kdekoli v následujícím textu bloku programu. Rozdíl mezi procedurou a funkcí je v tom, že funkce vrací hodnotu a může se použít přímo ve výrazech. Procedura se vyvolá příkazem volání procedury ke splnění jedné nebo více operací. Procedury a funkce umožňují vnořovat přídavné bloky do hlavního programového bloku. Každá deklarace procedury nebo funkce má hlavičku, po které následuje blok příkazů. Procedura se aktivuje příkazem volání procedury, funkce se aktivuje vyhodnocením výrazu, který obsahuje její volání. Za identifikátorem procedury nebo funkce může následovat seznam parametrů, uzavřený v kulatých závorkách. Každý parametr v seznamu má své místo, kterému odpovídá příslušný typ. Zdrojový text programu je ukončen tělem hlavního programu. Tělo hlavního programu se musí uvést vždy jako poslední. Mezi část deklarace proměnných a tělo hlavního programu lze vložit libovolné množství deklarací procedur a funkcí v jakémkoli pořadí. Musí se však dodržovat zásada, že cokoli použijeme, musí být deklarováno, jinak dojde k chybě během překladu. Procedura nebo funkce může mít své vlastní interní datové typy, proměnné i své vlastní procedury a funkce. Veškeré prvky deklarované uvnitř procedury nebo funkce mají lokální charakter, tzn., že je lze využít pouze uvnitř procedury nebo funkce, ve které jsou deklarovány. Deklarace, které jsou uvedeny v hlavním programu, mají globální charakter. Metoda - funkce uvnitř objektu Procedura - funkce, která nevrací hodnotu Funkce - klasická funkce, která vrací hodnotu (return) Makra Makra jsou ve většině jazyků zvláštní konstrukce, které definují způsob přepisu jednoho výrazu na výraz jiný. Umožňují tak často se opakující vzor programu označit jedním symbolickým názvem. Programátor v programu používá tyto symbolické názvy a před samotným překladem jsou tato symbolická jména nahrazena skutečným kódem. Tato fáze se nazývá expanze maker. Mnoho jazyků podporuje i parametrizaci maker, takže „volání'' makra mnohdy vypadá podobně
jako volání funkce. Na rozdíl od volání funkce však dochází k expanzi makra při překladu, a v době běhu programu tudíž k žádné „aktivaci“ makra nedochází. Příklad - makro nepřijímá argumenty #define PI 3.14159
Příklad - makro přijímá parametr #define NASOBEK(a,b) ((a)*(b))
Parametry V hlavičce deklarace procedury nebo funkce můžeme definovat seznam formálních parametrů. Každý parametr deklarovaný v seznamu je lokální v deklarované proceduře nebo funkci. Uvnitř bloku procedury nebo funkce je možné se na něj odvolávat jeho identifikátorem. Typy parametrů: · Formální - ty se objevují v deklaraci procedury nebo funkce. · Skutečné - jsou to parametry, které se uvádějí při volání procedury nebo funkce. Musí odpovídat svým datovým typem parametrům, definovaným v podprogramu a jejich počet musí být stejný s počtem, který jsme v podprogramu definovali. Metoda samozřejmě nemusí mít žádný vstupní parametr, pokud ano styl zápisu je následující : návratový typ jméno metody ( arg1, arg2, …, argn ) { // zde se nachází kód } Klasicky se po předání parametru do funkce, vytvoří ve funkci nová lokální proměnná, která se zde modifikuje, ale nedochází ke změně vnější proměnné. V jazyce C lze předávat parametr pomocí ukazatele (pointeru), tím se modifikuje proměnná na předané adrese (tudíž vnější proměnná). Totu problematiku řeší i C# pomocí ref a out viz (ppt): http://www.google.cz/url?sa=t&source=web&cd=4&ved=0CDMQFjAD&url=http%3A%2F%2Foa kostelec.cz%2Fmaterialy%2Finformatika%2FProgramovani%2FC%2520passing%2520paramet ersA.pps&rct=j&q=predavani%20parametru%20metod&ei=k3vsTaDsM4jGQbUqfzkDA&usg=AFQjCNF5rPCulYK4W5i12DmFLHRZjIxQhw&sig2=yvjWaFOV4zXFaaNzDg0 qgw Předávání volání hodnotou (call by value) volající provede vyhodnocení výrazu který je zadán jako argument funkce a výslednou hodnotu předá do volané funkce volání odkazem (call by reference) volající předá v argumentu funkce ukazatel nebo referenci na proměnou. Funkce může obsah této proměnné nejen číst, ale i modifikovat její obsah (viz vedlejší účinek). Často se pole jako argument funkce předává pomocí volání odkazem Globální a lokální proměnné
Podle směrnic základní klasifikace proměnných dělíme proměnné na lokální a globální. Každá proměnná, která je definována uvnitř jisté funkce, je vůči této funkci lokální proměnnou. Naproti tomu definiční příkaz vytvářející globální proměnnou se nachází mimo tělo jakýchkoliv funkcí. Rozdíly mezi globální a lokální proměnnou Život globální proměnné je totožný s dobou běhu programu. Globální proměnná žije déle než lokální proměnná. Globální proměnná smí být sdílena napříč více funkcemi, ovšem je nutno zabránit situacím, kdy by hodnota globální proměnné mohla být nepatřičně modifikována. Životní cyklus lokální proměnné je ohraničen životním cyklem funkce, v níž je lokální proměnná situována. Vzhledem k tomu, že lokální proměnná žije pouze v rámci jedné funkce, nemůže být sdílena více funkcemi. Je proto možné, aby byly v různých funkcích definovány lokální proměnné se shodným identifikátorem. To znamená, že kdybychom kromě hlavní funkce main měli ještě jednu funkci F, tak v tělech obou zmíněných funkcí by se mohl vyskytovat definiční příkaz int o;, jenž by zakládal celočíselnou proměnnou o. Proč používat lokální a globální proměnné Z pohledu začátečníka se může zdát používání globálních proměnných velmi výhodné. Jednoduše přece uvedeme jméno proměnné, které je známé ve všech místech programu. Zdánlivá jednoduchost však může věci později zkomplikovat: ● Při zvětšování programu používáme čím dál víc jmen a začnou se nám špatně vymýšlet. Pokud chceme jméno proměnné později změnit, musíme je měnit na mnoha různých místech. ● Pokud jazyk umožňuje práci s lokálními proměnnými, pak obvykle existence lokální proměnné zamaskuje existenci stejnojmenné globální. Při čtení zdrojového textu si vůbec nemusíme všimnout toho, že je stejnojmenná lokální proměnná již definována. A najednou se program začne chovat jinak, než bychom čekali. ● Použitím jména globální proměnné někde v kódu vytváříme obtížně kontrolovatelnou vazbu na zbytek systému. Nejde jen o to, že existuje vazba na globálně pojmenovanou proměnnou, ale jejím prostřednictvím se najednou ovlivňuje činnost všech ostatních částí kódu, které s globální proměnnou pracují. Jinými slovy, někdy je velmi obtížné zajistit, aby v globální proměnné byla uložena právě ta hodnota, která tam má být uložena. Zdánlivě nevinná změna obsahu, provedená v jednom místě, může neočekávaným způsobem ovlivnit činnost jiných částí aplikace. Rekurze a její použití V oblasti matematiky pojem rekurze chápeme jako definování objektu pomocí volání sebe sama. Využívá se například pro definici přirozených čísel, stromových struktur a některých funkcí. V programování rekurze představuje opakované vnořené volání stejné funkce (podprogramu), v takovém případě se hovoří o rekurzivní funkci. Nedílnou součástí rekurzivní funkce musí být ukončující podmínka určující, kdy se má vnořování zastavit. Jelikož bývá nejčastějším zdrojem chyb, je třeba ji navrhnout dostatečně robustním způsobem a prověřit veškeré možné stavy.
Pro uplatnění rekurzivních algoritmů je zapotřebí, aby programovací jazyk umožňoval volání podprogramu ještě před ukončením jeho předchozího volání. Po každém kroku volání sebe sama musí dojít ke zjednodušení problému. Pokud nenastane koncová situace, provede se rekurzivní krok. Každý algoritmus využívající rekurzi lze přepsat do nerekurzivního tvaru při použití zásobníku nebo jiné paměťové struktury. Základní rozdělení rekurzí Rekurzivní chování může být různé v závislosti na tom, kolik podprogramů se jí účastní. Rozlišujeme dva základní typy dělení: · Přímá rekurze nastává, pokud podprogram volá přímo sám sebe. · Nepřímá (vzájemná) rekurze je situace, kdy vzájemné volání podprogramů vytvoří „kruh“. Např. v příkazové části funkce A je volána funkce B, ve funkci B voláme funkci C, která volá funkci A. Další dělení rekurzí · Lineární rekurze nastává, pokud podprogram při vykonávání svého úkolu volá sama sebe pouze jednou. Vytváří se takto lineární struktura postupně volaných podprogramů. · Stromová rekurze nastává, pokud se funkce nebo procedura v rámci jednoho vykonání svého úkolu vyvolá vícekrát. Vzniklou strukturu je možné znázornit jako strom. Pro dvě volání v jednom průchodu vzniká binární strom, pro tři ternární strom, atd. Při kombinaci zmíněných typů rekurze lze docílit velmi komplikovaných struktur. Je třeba připomenout, že již z charakteru takovéhoto volání podprogramů nelze docílit jiné, než symetrické struktury. Paměť & hloubka rekurze Každé nové volání rekurzivní funkce znamená nové vytvoření lokálních proměnných (aniž by se uvolnily proměnné z předchozího volání, neboť ještě neskončilo). Při hlubší rekurzi se může stát, že program vyčerpá kapacitu zásobníku (operační paměť), nebude mít volnou paměť a skončí chybou. Abychom mohli algoritmus označit za rekurzivní, musí splňovat následující pravidla: 1.Musí být definována podmínka pro ukončení algoritmu. 2.V každém kroku rekurze musí dojít ke zjednodušení problému. 3.V algoritmu se nejprve musí ověřit, zda nenastala koncová situace. Když ne, provede se rekurzivní krok. Příklady rekurze Typickým příkladem přirozeně rekurzivního algoritmu je průchod stromem: void ProjdiStrom(uzel x) { unsigned int i = 0; while (i < x.count) { ProjdiStrom(x.children[i]); i++; } ZpracujUzel(x); // zde jsou prováděny operace s daty uloženými v daném uzlu
} Pro zpracování celého stromu voláme na počátku proceduru s počátečním parametrem kořenový uzel. Procedura rekurzivně volá sebe sama pro potomky aktuálního uzlu (tedy pro podstromy daného stromu), dokud nedosáhne k uzlům, které nemají žádné potomky (uzly bez potomků jsou nazývány „listy“). Při vykonání určité operace se všemi soubory v adresářové struktuře na pevném disku je možné použít rekurzi, neboť na každý nalezený podadresář lze automaticky zavolat stejnou funkci. Faktoriál : public static int factorialRek(int number){ if(number < 0) throw new IllegalArgumentException("zaporny argument"); if(number == 0 || number == 1) return 1; return number * factorialRek(number - 1); } QuickSort Ukázkou vhodného užití rekurze je třídící algoritmus QuickSort. Jedná se jeden z nejrychlejších a zároveň i jednodušších algoritmů řazení. Princip spočívá v rozdělení posloupnosti čísel do dvou oblastí. Do jedné umístíme menší čísla než nějaká náhodně zvolená hodnota (nazýváme ji pivot) a do druhé větší. Při vhodném zvolení pivotu jsou obě oblasti přibližně stejně velké. V momentě, kdy jsou seřazeny obě části, je seřazená i celá posloupnost. Obě části se rekurzivně řadí stejným postupem, dokud nebudou mít jednotlivé úseky pouze jeden člen. static void QuickSort(ref int[] array, long VLEVO, long VPRAVO){ int PIVOT = array[((VLEVO + VPRAVO)/2)]; long L = VLEVO; long P = VPRAVO; do { while (array[L-1] < PIVOT) { L++;} while (PIVOT < array[P-1]) { P--;} if(L <= P){ // prohození čísel int TMP = array[L-1]; array[L-1] = array[P-1]; array[P-1] = TMP; L++; P--; } }while(!(L > P)); if (VLEVO < P){ QuickSort(ref array, VLEVO, P); }// rekurzivní volání if (L < VPRAVO){ QuickSort(ref array, L, VPRAVO); } // rekurzivní volání }
Použití zásobníku Zásobník (stack) je v informatice abstraktní datový typ, používá se pro dočasné ukládání dat. Pro zásobník je charakteristický způsob manipulace s daty - data uložena jako poslední budou čtena jako první. Proto se používá také výraz LIFO z anglického "Last In - First Out". Pro manipulaci s uloženými datovými položkami se udržuje tzv. ukazatel zásobníku, který udává relativní adresu poslední přidané položky, tzv. vrchol zásobníku. Obsahem zásobníku mohou být jakékoli datové struktury. Může být realizován jak programovými prostředky, tak i elektronickými obvody. Nejznámější aplikací zásobníku je vnitřní zásobník realizovaný procesorem, do něhož jsou ukládány návratové adresy a příznaky stavu procesoru při přerušeních a skocích do podprogramů. Při návratu z podprogramu je z vrcholu zásobníku vyjmuta návratová adresa a zpracování pokračuje od přerušeného místa. Tento zásobník může být čistě v procesoru, nebo se fyzicky nachází v paměti a procesor obsahuje pouze podporu jeho používání. Ve většině případů (včetně procesorů architektury i386) je možné na zásobník v paměti s podporou procesoru ukládat libovolné informace, což se využívá především k ukládání parametrů funkcí a jejich lokálních proměnných. Zásobník, ať už hardwarový nebo softwarový (emulovaný) je klíčovou datovou strukturou používanou v programování při realizaci rekurzivních algoritmů. Implementace zásobníku Pro implementaci zásobníku jako abstraktního datového typu jsou zapotřebí tato primitiva: 1. inicializace zásobníku (create) 2. přidání položky na vrchol zásobníku (push), test plnosti zásobníku (is_full) 3. odebrání položky z vrcholu zásobníku (pop), test prázdnosti zásobníku (is_empty) Zásobník lze realizovat buď polem, nebo spojovým seznamem: class IntZasobnik { private Prvek vrchol; private class Prvek { int klic; Prvek dalsi; Prvek (int klic, Prvek dalsi) { this.klic = klic; this.dalsi = dalsi; } }
IntZasobnik() { vrchol = null; } boolean jePrazdny() { return (vrchol == null); } void push(int klic) { vrchol = new Prvek(klic, vrchol); } int pop() { int v = vrchol.klic; vrchol = vrchol.dalsi; return v; } } Třída zásobník obsahuje podtřídu Prvek. Samozřejmě třída Prvek může být vytvořena samostatně, tak jak jsem to x-krát dělali :-).
17. Objektově orientované programování, význam a základní principy, struktura programu. Zapouzdření, data metody, správa přístupu. Dědičnost, polymorfismus, pozdní vazba. Abstraktní třídy, rozhraní jako abstraktní datová struktura. Kompatibilita typů. Hierarchie tříd. Genericita a její využití. Výjimky, jejich využití a ošetření. OOP Základním paradigmatem OOP je snaha modelovat při řešení úloh principy reálného světa v počítači pokud možno jedna ku jedné. V praktickém životě otevíráme dveře pořád stejně, bez ohledu na to, zda jsou dřevěné nebo laminované, zda mají kukátko, bezpečnostní vložku nebo řetízek navíc. Stejně tak se můžeme dívat na televizi, přepínat programy a docela dobře ji ovládat, přesto že nevíme vůbec nic o principech jejího fungování. Analogicky při vývoji složitých informačních systémů mohou vývojáři používat již vytvořené komponenty, podle potřeby si je trochu upravit nebo je používat jako stavebnici pro sestavování důmyslnějších a složitějších objektů. Třída je základním obecným pojmem klasifikace, jak při návrhu uspořádávát informace do smysluplné entity. Základním pojmem je objekt, instance třídy, jako konkrétní případ realizace předpisu. Objekt si „pamatuje“ svůj stav (v podobě dat čili atributů) a zveřejněním některých svých operací (nazývaných metody) poskytuje rozhraní, jak s ním pracovat. Při používání objektu nás zajímá, jaké operace (služby) poskytuje, ale ne, jakým způsobem to provádí - to je princip zapouzdření. Jestli to provádí sám nebo využije služeb jiných objektů, je celkem jedno. Vlastní implementaci pak můžeme změnit, aniž by se to dotklo všech, kteří objekt používají. Třída = předpis, jak bude objekt “vypadat” Objekt = konkrétní instance třídy Základní koncepce OOP: ● Objekty – jednotlivé prvky modelované reality (jak data, tak související funkčnost) jsou v programu seskupeny do entit, nazývaných objekty. Objekty si pamatují svůj stav a navenek poskytují operace (přístupné jako metody pro volání). ● Abstrakce – programátor, potažmo program, který vytváří, může abstrahovat od některých detailů práce jednotlivých objektů. Každý objekt pracuje jako černá skříňka, která dokáže provádět určené činnosti a komunikovat s okolím, aniž by vyžadovala znalost způsobu, kterým vnitřně pracuje. ● Zapouzdření – zaručuje, že objekt nemůže přímo přistupovat k „vnitřnostem“ jiných objektů, což by mohlo vést k nekonzistenci. Každý objekt navenek zpřístupňuje rozhraní, pomocí kterého (a nijak jinak) se s objektem pracuje. ● Skládání – Objekt může obsahovat jiné objekty. ● Delegování – Objekt může využívat služeb jiných objektů tak, že je požádá o provedení operace. ● Dědičnost – objekty jsou organizovány stromovým způsobem, kdy objekty nějakého druhu mohou dědit z jiného druhu objektů, čímž přebírají jejich schopnosti, ke kterým pouze přidávají svoje vlastní rozšíření. Tato myšlenka se obvykle implementuje pomocí
rozdělení objektů do tříd, přičemž každý objekt je instancí nějaké třídy. Každá třída pak může dědit od jiné třídy (v některých programovacích jazycích i z několika jiných tříd). ● Polymorfismus – odkazovaný objekt se chová podle toho, jaké třídy je instancí. Pokud několik objektů poskytuje stejné rozhraní, pracuje se s nimi stejným způsobem, ale jejich konkrétní chování se liší podle implementace. U polymorfismu podmíněného dědičností to znamená, že na místo, kde je očekávána instance nějaké třídy, můžeme dosadit i instanci libovolné její podtřídy, neboť rozhraní třídy je podmnožinou rozhraní podtřídy. U polymorfismu nepodmíněného dědičností je dostačující, jestliže se rozhraní (nebo jejich požadované části) u různých tříd shodují, pak jsou vzájemně polymorfní. Zapouzdření Zapouzdření v objektech znamená, že k obsahu objektu se nedostane nikdo jiný, než sám vlastník. Navenek se objekt projeví jen svým rozhraním (operacemi, metodami) a komunikačním protokolem. S daty lze pracovat pouze prostřednictvím obalujících funkcí (metod), zároveň se v rámci obalující metody může kontrolovat validita argumentu, konzistence vnitřního stavu před změnou a lze nastavovat více vnitřních atributů zároveň. Uživatel třídy není zatěžován vnitřní logikou. Příklad: class Bod{ private int x; private int y; public void SetX(int x){ this.x = x; } public int GetX(){ return this.x; } } klasickým příkladem je použití tzv. SETrů a GETrů. Nyní se ostatní dostanou k privátním proměnným pouze přes tyto zapouzdřující metody. Není potřeba vědět jak to metoda uvnitř objektu udělá. Samozřejmě je možné přetížit metodu SetX a předat ji parametr například String. Poté bude v metodě ohlídána výjimka, zda došlo ke korektnímu přetypování Stringu na int -> kontrola validity. Vlastností zapouzdření je, že ve třídách můžeme jak u členských proměnných, tak i u metod nastavit přístupová práva - můžeme omezit přístup k metodám a proměnným kupříkladu jen na kód samotných tříd. Pokud bychom chtěli dodržovat OOP do posledního puntíku, neměly by být proměnné vůbec přístupné a veškerá práce s nimi by měla být realizována přes metody.
Práva (java):
Existují čtyři druhy práv: private, protected, package-access a public. Lze je nastavit jak na metody třídy tak na atributy. private - k položkám lze přistupovat pouze pouze ze třídy kde byly deklarovány protected - k položkám mohou přistupovat kromě vlastní třídy ještě třídy ve stejném balíčku a třídy odvozené public - k položkám je přístup možný odkudkoliv package - k položkám mají přístup třídy uvnitř balíčku - pro komunikaci uvnitř balíčku Dědičnost Dědičnost nám umožňuje třídy zařadit do hierarchické struktury, stejně jako je to v reálném světě. Vezměme si zase nějaký pěkný příklad - třeba auto. Auto může být určitě třídou. Mělo by své členské proměnné jako značku či SPZ a také své metody jako jet někam či natankovat. Auta však můžeme dále dělit do dalších kategorií - nákladní auta, sportovní auta atd. Každá z těchto skupin by ovšem klidně mohla být rovněž třídou. Ta by měla určitě stejné vlastnosti a metody jako třída Auto, ale zároveň by přidávala i svá specifika. Tak u nákladního auta by to mohla být vlastnost nosnost a u sportovního třeba zrychlení. A nakonec Auto je určitě zase podskupina třídy dopravních prostředků. Tuto hierarchii můžeme vytvářet i v OOP. Můžeme totiž vytvářet nové třídy odvozením od jiných. Tyto odvozené třídy jsou pak potomkem původní třídy a dědí jeho členské proměnné a metody. S tímto je spjata i hiearchie tříd. Polymorfizmus Polymorfismus nám dává do rukou silný nástroj, který je spjatý s dedičností. Jde v něm o to, že při překladu nemusí být ještě známo, když v programu voláme metody, které třídě budou patřit a teprve za běhu se rozhodne o tom, které to budou. Nejlépe bude, když si to ukážeme na konkrétním příkladu.
V polymorfizmu platí že potomek může zastoupit předka. Pokud vytvoříme pole předků (Tvarů), můžeme do něj vložit jakéhokoliv potomka (Kruh, Ctverec, Trojuhlenik). V poli se poté může volat Tvar[i].vykresli() metoda se bude chovat až podle konkrétní instance - pozdní vazba. Abstraktní třída
Přímo podle abstraktní třídy, na rozdíl od klasické (neabstraktní) třídy, nemůžeme vytvářet objekty, instance. ● Abstraktní třída má definované (deklarované i implementované) jen některé své metody, které se rozdědí společné všem potomkům. ● Neimplementované (abstraktní) metody, se v odděděných třídách, potomcích abstraktní třídy, mohou lišit. Dán je pouze předpis požadovaných metod, jejich deklarace: Jejich názvy, počty a typy předávaných vstupů (argumentů) a návratové typy metod. Lze tedy říci, že se jedná o šablonu pro vytváření specifické skupiny tříd. Rozhraní Rozhraní (interface) je množina metod, která může být implementována třídou. Interface pouze popisuje metody, jejich vlastní implementace však neobsahuje. V Javě na rozdíl od jiných programovacích jazyků (například C++) nemůže třída dědit od více tříd najednou (neexistuje vícenásobná dědičnost). Každá třída však může implementovat libovolný počet rozhraní, do jisté míry tedy rozhraní vícenásobnou dědičnost nahrazují. Implementace rozhraní není na hierarchii tříd nijak vázána a nevzniká z ní vztah dědičnosti. Rozdíly - abstraktní může mít definované tělo metody, interface ne interface pouze říká, že třída bude splňovat to a to (neříká jak) více : http://www.kai.tul.cz/~kopetschke/java/PG2-JavaRozhrani2.pdf Kompatibilita typů Typová kompatibilita je vyžadována především mezi operandy některých operací. Dva typy jsou kompatibilní, je-li splněn některý z následujících předpokladů: ● typy jsou identické ● oba typy jsou reálné ● oba typy jsou celočíselné ● jeden typ je podintervalem druhého ● oba typy jsou intervaly s identickými hostitelskými typy ● oba typy jsou množinové, s kompatibilními bázovými typy ● oba typy jsou pole znaků se stejným počtem prvků ● jeden typ je řetězec a druhý řetězec, pole znaků nebo znak ● jeden z typů je netypový ukazatel a druhý libovolný ukazatel nebo jsou oba typy ukazatele s identickými bázovými typy (jen za nastavené direktivy {$T+}) ● oba typy jsou procedurální, se stejným typem výsledku, stejným počtem parametrů a vzájemně identickými typy parametrů To bylo hodně obecný :-). Co si pamatuju já, tak platí předešlé, plus podlě mě třeba Špánek bude chtít slyšet právě implementaci rozhraní do nějaké třídy, aby splňovala typovou kompatibilitu pro použítí jiné třídy. Genericita Základní myšlenkou, která se skrývá za pojmem generické programování, je rozdělení kódu programu na algoritmus a datové typy takovým způsobem, aby bylo možné zápis kódu algoritmu chápat jako obecný, bez ohledu nad jakými datovými typy pracuje. Konkrétní kód algoritmu se z něj stává dosazením datového typu.
Generické programování má následující cíle: ● Poskytnout programátorovi způsob, jak vyjádřit algoritmy s minimální závislostí na použitých datových strukturách. ● Poskytnout programátorovi způsob, jak vyjádřit datové struktury s minimální závislostí na algoritmech. ● Poskytnout programátorovi možnost implementovat algoritmy co nejobecněji, aniž by při přechodu ke konkrétním typům došlo ke ztrátě efektivity. ● V případě, že zcela obecná forma algoritmu je v některých speciálních případech neefektivní nebo není použitelná, dát programátorovi možnost tyto speciální případy implementovat zvlášť. ● V případě, že obecná datová struktura pro jisté speciální případy nevyhovuje, poskytnout programátorovi možnost implementovat tyto speciální případy zvlášť. ● V případě, že k řešení určitého problému existuje několik rovnocenných algoritmů, poskytnout programátorovi možnost implementovat je všechny a dát tak uživateli na vybranou podle dalších kritérií. V jazyce Java (od verze 5) – můžeme vytvořit vlastní třídu, která bude pracovat s hodnotami zadaného typu a tento typ bude specifikován při deklaraci třídy class MojeTrida
{ T hodnota; public MojeTrida (T t)} hodnota = t; }
public T getHodnota(){ return hodnota; } } Využití - kolekce jazyka Java objektů jako hodnot typu Object ● do kolekce je poté vložen libovolný objekt ● při práci s prvku je nutné je přetypovat na příslušný typ Genericita ● umožňuje vytvářet kolekce objektů konkrétního typu - typ je specifikován při deklaraci a vytváření instance ● obdobně lze vytvářet seznamy Výjimky Pomocí mechanismu výjimek můžeme lépe reagovat na chybové a nestandardní stavy běhu programu. Místo toho, abyste po každém vykonaném příkazu kontrolovali chyby, které mohou nastat, umístíte ošetření chyb celého bloku kódu na jedno místo.
Výjimky v Javě jsou objekty, které jsou potomky objektu java.lang.Throwable. Tato třída má dvě podtřídy java.lang.Error a java.lang.Exception (pro obě se používá společný název výjimky). Pokud v programu dojde k výjimečnému stavu, vznikne objekt výjimky a program může na tuto výjimku reagovat, odchytit ji. Ošetření výjimek Výjimky se ošetřují pomocí konstrukce try-catch-finally. Blok za klíčovým slovem tryobsahuje nebezpečný kód, ve kterém může dojít k výjimce. Za ním následuje žádný nebo více bloků catch, ve kterých jsou ošetřeny jednotlivé typy výjimek, které mohou nastat v bloku try. Nepovinný blok finally obsahuje kód, který je vždy spuštěn nezávisle na tom, jak dopadl blok try (zda proběhl bezchybně či skončil výjimkou).
try { // nebezpečný blok kódu, v němž mohou nastat výjimky } catch (NejakaVyjimka1 nv1) { // zde se ošetří výjimky typu NejakaVyjimka1 // a jeho podtypu } catch (NejakaVyjimka2 nv2) { // zde se ošetří výjimky typu NejakaVyjimka2 // a jeho podtypu } finally { // tento kód se provede vždy po opuštění klausule try }
Při vstupu do bloku try se příkazy vykonávají v pořadí, ve kterým jsou zapsány. Pokud vše proběhne bezchybně, je po bloku try spuštěn případný blok finally. Pokud v průběhu bloku try nastane výjimka, přeruší se jeho vykonávání. Pokud některá klausule catch ošetřuje daný typ výjimky, spustí se blok kódu první takové. Nakonec se spustí blokfinally, pokud je přítomen. Za klíčovým slovem catch následuje v kulatých závorkách typ výjimky a jméno proměnné, která na ni bude odkazovat. Tato klausule odchytává pouze výjimky tohoto typu a jeho podtypů. Proměnná odkazující na výjimku je platná pouze v daném bloku catch. Deklarace výjimek Je nutné, aby každá metoda, která může způsobit výjimku, ji buď odchytila nebo specifikovala, že tuto výjimku způsobuje. Používá se k tomu klíčové slovo throws v deklaraci metody:
public void nactiSoubor() throws IOException { // kód, který může způsobit výjimku typu java.io.IOException // (nebo jejího podtypu), ale tuto výjimku neodchytává
}
Není nutné ošetřovat ani deklarovat výjimky (pod)typu java.lang.Error anijava.lang.RuntimeException, protože je může potenciálně vyvolat každá metoda a měly by vést k přerušení programu. Vlastní výjimky Pomocí klíčového slova throw můžeme vyvolávat také své vlastní výjimky (nebo standardní výjimky). Vlastní výjimku definujeme jako objekt dědící od objektu java.lang.Throwablenebo nějakého jeho podobjektu:
public class MojeVyjimka extends java.lang.Exception { public MojeVyjimka() { super(); } public MojeVyjimka(String a) { super(a); } }
throw new MojeVyjimka("Nastala MojeVyjimka"); // parametr konstruktoru // se stane zprávou, kterou lze získat metodou getMessage()
18. Tvorba aplikací v prostředí konzole a MS Windows. Vývojová prostředí. Programátorské rozhraní operačního systému. Pokročilejší programátorské techniky jako zpracování zpráv, programování threadů, synchronizace procesů. Nevím, zda tohle je to, co chtějí, ale nepřišel jsem na jiný význam této části otázky !!! Konzole → Basic, Pascal , C, C++ → je zpravidla jednoduchý počítačový program na
úrovni řetězců znaků, který nevyužívá grafické rozhraní. Dřívější verze operačních systému, které kompletně neměly grafické rozhraní využívaly jenom konzolové aplikace. Je to v podstatě příkazový řádek, který je upravený pro potřeby daného programu. MS Windows → GUI aplikace ( s pomocí Windows API (viz dále)) -->C++, java, C#, .NET framework, ..
Odsud by to mělo být OK Vývojová prostředí Vývojové prostředí (zkratka IDE, anglicky Integrated Development Environment) je software usnadňující práci programátorů, většinou zaměřené na jeden konkrétní programovací jazyk. Obsahuje editor zdrojového kódu, kompilátor, případně interpret a většinou také debugger. Některé obsahují systém pro rychlý vývoj aplikací (zvaný RAD), který slouží pro vizuální návrh grafického uživatelského rozhraní. Pokud se jedná o nástroj pro objektově orientované programování, může obsahovat také object browser. Historie IDE se stala nezbytnými v době, kdy se programy začaly vyvíjet přes konzoli nebo terminál. Jazyk Dartmouth BASIC byl prvním, který byl vyvinut s IDE (a byl také prvním, který byl navržen pro použití na konzoli nebo terminálu). Vývojové prostředí tohoto jazyka (část z Dartmouth Time Sharing System) bylo založeno na příkazech, a proto nevypadalo jako dnes používaná grafická IDE. Přesto integrovalo editaci, správu souborů, překlad, ladění a vykonávání stejně jako moderní IDE. Maestro I je produkt firmy Softlab Munich a byl prvním integrovaným vývojovým prostředím pro software (1975). Maestro I byl po celém světě instalován pro 22 000 programátorů. Do roku 1989 existovalo například ve Spolkové republice Německo šest tisíc instalací. Maestro I byl pravděpodobně světovou jedničkou v tomto oboru v sedmdesátých a osmdesátých letech. Dnes můžeme najít jednu z posledních instalací Maestro I v Arlington Museum of Information Technology. Jedno z prvních IDE s plug-in konceptem byl software s názvem Softbench. V roce 1995 časopis Computerwoche napsal, že používání IDE nebylo vývojáři dobře přijato z důvodu omezování jejich kreativity.
Vizuální programování V poslední době se zvyšuje zájem o vizuální programování (nezaměňovat s Visual Basic nebo Visual C++). Vizuální IDE umožňují uživateli vytvářet nové aplikace přemístěním programovacích stavebních bloků nebo uzlů a vytvořením vývojových diagramů nebo blokových schémat, které jsou dále přeloženy. Tyto diagramy bývají často založeny na UML (Unified Modeling Language). Toto rozhraní získalo oblibu s příchodem systému Lego Mindstorms a je aktivně používáno řadou společností, které tak chtějí těžit ze schopností prohlížečů, jako například těch vytvořených v Mozille. KTechlab podporuje programování pomocí vývojových diagramů a je populárním vývojovým prostředím a simulátorem pro vývoj aplikací pro mikropočítače. Vizuální programování se také zasloužilo o rozšíření distribuovaného programování. Max, jeden z prvních softwarů pro vizuální programování, byl navržen podle analogového syntezátoru a byl v osmdesátých letech používán pro tvorbu hudebních aplikací. Dalším z průkopníků byl Prograph, původně navržený pro Macintosh a založený na principu datového toku. Grafické vývojové prostředí Grape je používáno pro programování stavebnicových robotů qfix. Tento přístup je také používán u specializovaných softwarů, jako například Openlab, kde koncový uživatel požaduje maximální flexibilitu bez nutnosti dlouhého osvojování znalostí, jako je tomu u jiných programovacích jazyků. Vizuální programování zastupuje v oblasti open source prostředí Mindscript, které poskytuje rozšířené funkce pro šifrování, propojení s databázemi atd. Podpora programovacích jazyků Některá IDE podporují více jazyků, jako například Eclipse nebo Netbeans, oboje vytvořené v Javě, nebo MonoDevelop, vytvořený v C#. Podpora pro alternativní jazyky je často poskytována prostřednictvím pluginů, které mohou být instalovány současně na stejném IDE. Například Eclipse a Netbeans mají pluginy pro C/C++, Python, Ruby, nebo PHP a některé další jazyky. Programátorské rozhraní operačního systému API (zkratka pro Application Programming Interface) označuje v informatice rozhraní pro programování aplikací. Tento termín používá softwarové inženýrství. Jde o sbírku procedur, funkcí či tříd nějaké knihovny (ale třeba i jiného programu nebo jádra operačního systému), které může programátor využívat. API určuje, jakým způsobem se funkce knihovny volají ze zdrojového kódu programu. Rozhraní, které se vytváří při kompilaci a je využíváno při běhu programu, se nazývá ABI.
API operačních systémů
V současné době jsou nejrozšířenější dva standardy API OS: POSIX (IEEE) a Win32 (Microsoft). Rozhraní POSIX bylo vytvořeno pro standardizaci unixových operačních systémů, rozhraní Windows API reprezentuje rozhraní pro systém s mikrojádrem (absence systémových volání). Vlastnosti API je abstrakce, která definuje a popisuje rozhraní pro interakci s řadou funkcí, používaných součástí softwarového systému. Software, který poskytuje funkce popsané API říká, že je implementován v API. API může být: obecné – jedná se o úplný soubor rozhraní API, který je zasílán v knihovnách programovacího jazyka (např. Standard Template Library v C ++ nebo Java API) konkrétní – chce řešit konkrétní problémy, jako jsou Mapy Google nebo Java API for XML Web Services jazykově závislé – to znamená, že je k dispozici pouze v daném programovacím jazyce, pomocí syntaxí a základních prvků tohoto jazyka, aby API bylo vhodné pro použití v této souvislosti jazykově nezávislé – to znamená, že lze volat z několika programovacích jazyků, což je žádoucí vlastnost pro službu orientovanou v API, která není vázána na daný proces nebo systém, a může být poskytnuta jako RPC nebo Webová služba Například internetové stránky, které uživatelům umožňují hledání místních restaurací je schopna si převzít vrstvu z Google Maps, protože Google Maps API to umožňuje. Google Maps API kontroluje, jaké informace třetí síť může chytit, a co lze s nimi udělat. „API“ může být používán k odkazování na kompletní rozhraní, jednu funkci, nebo dokonce na soubor více API poskytovaných organizací. Proto je rozsah výzkumu obvykle určen osobou nebo dokumentem, který sděluje informace. Implementace Standard POSIX definuje API, které pokrývá širokou škálu běžně používaných funkcí a umožňuje je používat na mnoha různých systémech (typicky unixové systémy – Linux, Mac OS X, různé BSD systémy atd.). Použití toho API však vyžaduje na každé platformě danou aplikaci znovu přeložit (překompilovat). Kompatibilní API však umožňuje naprogramovat jeden zdrojový kód tak, aby beze změn fungoval na libovolném systému implementujícím toto API. Přenositelnost je výhodná jak pro tvůrce software (již existující produkt lze snadno přenést na jinou platformu), tak pro uživatele (mohou instalovat starší software na své novější systémy bez nutnosti zakoupení upgrade), i když to často vyžaduje přenášet i doplňující knihovny. Microsoft pro vytvoření zpětné kompatibility Windows API (Win32, tj. pro možnost běhu starších aplikací na novějších verzích systému Windows) poskytuje možnost nastavit specifický „režim kompatibility“. Apple zastává v tomto ohledu méně vstřícný postoj, což mu poskytuje větší svobodu při vývoji aplikací za cenu označení starších programů jako „zastaralých“. Mezi unixovými operačními systémy existuje mnoho příbuzných, ale navzájem nekompatibilních operačních systémů, přestože běží na společné technické platformě (zejména IBM PC kompatibilní systémy). Bylo zde mnoho pokusů o standardizaci API tak, aby výrobci software mohli šířit jedinou binární formu aplikace pro všechny tyto systémy, avšak do dnešního dne se žádný z nich nesetkal s větším úspěchem. Existuje projekt LSB (Linux Standard Base) pro
platformu Linux a BSD (FreeBSD, NetBSD, OpenBSD), který by mohl zaručit různé úrovně kompatibility API a zajistit zpětnou kompatibilitu (pro programy napsané pro starší verze, které běží na novějších distribucích systému) a multiplatformní kompatibilitu (umožňuje spuštění kódu určeného pro jinou platformu bez nutnosti rekompilace).
Pokročilejší programátorské techniky ● ● ●
Zpracování zpráv (zpracování vyjímek, událostí) vlákna a jejich synchronizace synchronizace procesů
Zpracování zpráv Strukturovaná obsluha výjimek Jazyk Java, podobně jako např. C++, využívá pro ošetření výjimek metodu strukturované obsluhy. To znamená, že programátor může pro konkrétní úsek programu specifikovat, jakým způsobem se má konkrétní typ výjimky ošetřit. V případě, že výjimka nastane, vyhledá se vždy nejbližší nadřazený blok, ve kterém je výjimka ošetřena. Výjimky jsou v jazyce Java reprezentovány jako objekty; tyto objekty jsou instancemi tříd odvozených obecně od třídy Throwable se dvěma podtřídami Error a Exception. Každá z těchto podtříd odpovídá jedné skupině výjimek. V první skupině jsou výjimky, jejichž výskyt představuje vážný problém v činnosti aplikace a které by programátor neměl zachycovat. Druhou skupinu tvoří výjimky, jejichž ošetření má smysl - jde například o výjimky jako pokus o otevření neexistujícího souboru, chybný formát čísla apod. Do této skupiny by měly patřit také veškeré výjimky definované uživatelem. Zvláštní podtřídu třídy Exception tvoří třída RuntimeException, která zahrnuje veškeré ošetřitelné výjimky vyvolané samotným systémem. Události
Události představují v jazyku C# cestu, která umožňuje třídě upozornit jinou třídu nebo třídy, že v ní došlo k něčemu zajímavému, na což by mohla tato třída respektive třídy určitým způsobem zareagovat. Časté použití můžeme nalézt v implementaci grafických uživatelských prostředí pro upozornění, že uživatel provedl nějakou akci, na níž by mohla být implementována reakce. Samozřejmě to není jediné možné použití události. Události se hodí všude tam, kde je potřeba upozornit okolí na to, že se v objektu respektive třídě došlo k nějaké změně stavu. Pro definici metod, které mohou být použity pro reakci na vzniklou událost slouží delegáty,
Obsluha událostí
Pokud chceme nastalou událost nějaké instance třídy obsloužit, musíme nějakou třídu učinit takzvaným předplatitelem události. Zvenčí, lze k události třídy nebo její instance přistoupit jako ke členu, ale použití tohoto členu je velmi omezené. Jediné co je .NET frameworkem dovoleno s členy typu událost provést je přidání instance delegáta do seznamu delegátů pro její obsluhu nebo naopak instancí delegáta z tohoto seznamu vyjmout. K přidání instance delegáta slouží operátor += a k jeho vyjmutí operátor -= .
Vlákna a jejich synchronizace
== multithreading neboli paralelní běh dvou či více částí programu. Demonstrováno v jazyce JAVA (obecně platí s menšími uprávami v každém programovacím jazyce, který podporuje vlákna) Každé vlákno v Javě je instancí třídy Thread (z balíku java.lang) nebo jejího potomka. Tato třída definuje základní metody jako je spuštění, zastavení a ukončení vlákna. Jednoduché vlákno se naprogramuje tak, že se vytvoří potomek třídy Thread, který definuje metodu: public void run() obsahující kód, který bude prováděn paralelně. Spuštění vlákna se provede zavoláním metody start()(metoda run() se přímo nevolá). Rozhraní Runnable (z balíku java.lang) obsahuje pouze deklaraci metody: public void run(); Třída pomocí tohoto rozhraní může definovat jádro vlákna, metodu run(), přičemž sama nemusí být potomkem třídy Thread. To je užitečné zejména v případě, že: ● program bude potřebovat pouze jedno další vlákno (kromě hlavního programu) - je zbytečné vytvářet kvůli jedné instanci vlákna třídu, ● daná třída je potomkem nějaké třídy (případ appletu) a potřebuje mít vlastnosti vlákna.
Ze života vlákna Každé vlákno se v daném okamžiku nachází v právě jednom z těchto stavů:
●
Nové vlákno (new thread) - je stav, kdy je vlákno vytvořeno, ale ještě nebylo spuštěno (nejsou ještě alokovány systémové prostředky vlákna).
●
"Běhuschopný" stav (runnable) - je stav po spuštění metodou start(). V tomto stavu se může nacházet více spuštěných vláken, z nichž ale jen jedno je (na počítači s jedním procesorem) právěběžící.
●
"Neběhuschopný" stav (not ○ ○ ○ ○
●
runnable) - do tohoto stavu se vlákno dostane, pokud:
je uspáno metodou sleep(), je "odstaveno" metodou suspend(), čeká v metodě wait() čeká na vstupní/výstupní zařízení.
Mrtvé vlákno (dead
thread) - je stav po ukončení metody run() nebo po zavolání
metody stop(). Přechody mezi jednotlivými stavy znázorňuje obrázek:
Synchronizace Potřeba synchronizace vzniká všude tam, kde je možné (avšak nepřípustné) používat současně zařízení (např. automat na kávu) nebo sdílet společná data (např. skripta na analýzu). U automatu je nutné synchronizovat přístup lidí, neboť se nesmí stát, aby po vhození mince byl člověk odstrčen jiným "uživatelem", který by pak obdržel kýžený nápoj. Podobně skripta nemůže číst více studentů současně, jinak by při obracení jedné stránky opačným směrem došlo brzy k jejich destrukci.
Synchronizace kritických sekcí
Vyloučení současného běhu kritických sekcí lze provést například pomocí tzv. monitorů. Monitor se obecně skládá z dat a funkcí (metod) jako zámků (locks) nad daty. V Javě má každý objekt vlastní jedinečný monitor. Při vstupu do synchronizované kritické sekce vlákno získá monitor (zámek je uzamčen) a po jejím opuštění vlákno monitor uvolní (zámek je odemčen). Po získání monitoru jedním vláknem nemůže jiné vlákno zahájit provádění žádné synchronizované kritické sekce náležící k témuž monitoru (vlákno, které monitor vlastní, ano - monitory jsou reentrantní). Synchronizovanou kritickou sekcí v Javě může být blok nebo metoda. Synchronizovaná metoda se v programu označí modifikátorem synchronized. Každá synchronizovaná sekce je vždy provedena jako nedělitelný (atomický) celek, bez možnosti přerušení.
Synchronizace procesu Semafor je v informatice široce používané synchronizační primitivum, které obsahuje celočíselný čítač. Semafor se využívá zejména jako ochrana proti souběhu tím, že chrání přístup do kritické sekce, k čemuž používá dvojici operací V (up) a P (down). Je tak zobecněním instrukce TSL, která používá proměnnou typu boolean. Semafory poprvé popsal holandský informatik Edsger Dijkstra v roce 1965. Implementace Implementace semaforu je založena na atomických operacích V (verhogen, též označováno jako up) a P (proberen, též označováno jako down). Operace down otestuje stav čítače a v případě že je nulový, zahájí čekání. Je-li nenulový, je čítač snížen o jedničku a vstup do kritické sekce je povolen. Při výstupu z kritické sekce je vyvolána operace up, která odblokuje vstup do kritické sekce pro další (čekající) proces. Čítač je možné si představit jako omezení počtu procesů, které mohou zároveň vstoupit do kritické sekce nebo například jako počitadlo volných prostředků. Tato implementace neodstraňuje problém aktivního čekání. [editovat]Odstranění aktivního čekání V případě, že je při vyvolání operace down čítač nulový, je nutné volající proces zablokovat. Čekání je implementováno jako nekonečná smyčka (tzv. aktivní čekání), která může být přerušena pouze vnějším zásahem jiného procesu do počitadla pomocí volání operace up. Neustálé testování stavu proměnné je možné nahradit pomocí fronty čekajících procesů.[1] Proces je místo aktivního čekání (tj. neustálého kontrolování stavu proměnné) zařazen do fronty, ve které je uspán. Funkce up je rozšířena o průchod touto frontou, kdy je kromě zvýšení počitadla aktivován pouze proces, který je ve frontě první. Tento proces sníží počitadlo a vstoupí do kritické sekce. Ostatní procesy dále čekají v uspaném stavu.
19. Operační systém, vysvětlení pojmu, typy, poskytované funkce. Správa procesů v operačním systému, vztah programu a procesu, životní cyklus procesu. Operační systém – vysvětlení pojmu Operační systém je v informatice základní programové vybavení počítače, které je zavedeno do paměti počítače při jeho startu a zůstává v činnosti až do jeho vypnutí. Skládá se z jádra (kernel) a pomocných systémových nástrojů. Hlavním úkolem operačního systému je zajistit uživateli možnost ovládat počítač, vytvořit pro procesy stabilní aplikační rozhraní (API) a přidělovat jim systémové zdroje. Operační systém je velmi komplexní software, jehož vývoj je mnohem složitější a náročnější, než vývoj obyčejných programů. Operační systém – typy (verze) Nejpoužívanějším druhem je OS určený pro pracovní stanice, druhou významnou skupinou je skupina serverových OS. Máme ovšem i speciální OS určené třeba pro velmi výkonné počítače anebo pro ruční počítače. OS pro počítače: UNIX - Je používán na strojích různého výpočetního výkonu od mikroprocesorů po střediskové počítače, a na počítačích architektur různých výrobců. Jedná se o nejstarší OS, který je dnes běžně používán. ● má jednoduché uživatelské rozhraní, jehož síla poskytuje uživateli služby, které potřebuje. ● nabízí prostředky umožňující budování komplexních programů z jednodušších. ● používá hierachický systém souborů, který dovoluje jednoduchou údržbu a efektivní implementaci. ● používá konzistentní formát souborů, posloupnost slabik, zjednodušující psaní aplikačních programů. ● poskytuje jednoduché konzistentní rozhraní periferních zařízení. ● je víceuživatelský (multiuser) systém; každý uživatel může vykonávat více procesů současně (multitasking). ● ukrývá před uživatelem architekturu počítače, takže zjednodušuje psaní programů provozovaných na různých implementacích technických prostředků. UNIX má několik variant. Liší se od sebe především výrobcem (komerční větev, univerzitní větev) a určením, kde a k jakým účelům má být použit (Linux je verze pro počítače typu PC). V současnosti je UNIX především využíván jako Internetový server (asi 40% celého Internetu). MS-DOS je operační systém firmy Microsoft, je to první operační systém určený pro jednoduchou obsluhu a byl klíčový pro obecné rozšíření PC Windows 95 - Prý plně 32–bitový OS podporující preemptivní multitasking (žádný aplikační program nemůže ohrozit běh OS, jelikož OS přiděluje veškeré výpočetní prostředky). Základem ovládání OS je práce s myší, příjemné pro uživatele aplikačního softwaru, ale zcela nevyhovující pro výkon správy počítače.
Windows 98 - Nástupce systému Windows 95. Neobsahuje žádné podstatné vylepšení, pouze radikálně mění uživatelské rozhraní, kde pracovní plochou je Internet Explorer. Pevné začlenění Internet Exploreru do nového OS vyústilo k soudní žalobě na firmu Microsoft . I přes to, že při prezentaci nového OS došlo k těžké havárii systému, přímo pod rukama Bila Gatese, mělo uvedení na trh v polovině roku 1998 velký komerční úspěch. Nejspíše se Windows 98 stanou na přelomu tisíciletí dominantním operačním systémem ve světě. Windows NT - Operační systém Windows NT verze 4 je dodáván buď ve verzi workstation (pro procovní stanici) nebo ve verzi server. Uživatelské rozhraní je velmi podobné jako má systém Windows 95. Ovšem vzhledem ke svým UNIXovým základům je systém daleko bezpečnější a spolehlivější (z této řady vychází i Windows XP, Vista, 7). Macintosh OS - Firma Apple pro svoje počítače dodává svůj vlastní operační systém, který uživateli připomíná vzhledm i chováním systém OS/2. Základem práce je nestarat se o to, jaký hardware je připojen, jak ho nastavit, ale vzít do ruky myš a pracovat. Novell - Firma Novell v současnosti produkuje řadu pěti síťových operačních systémů. Jedná se o, na DOSu založeném systému peer-to-peer, Personal NetWare: ● maximální počet 1000 uzlů na jeden server ● podpora globálních zdrojů, globálního pojmenování ● podpora komprese souborů na disku ● lepší prostředky bezpečnosti včetně auditingu síťových aktivit ● rozšířené možnosti síťové správy ● podpora odložení částí souborového systému (HCSS) na vysokokapacitních médiích ● podpora migrace dat při přechodu z nižších verzí NetWare OS pro mobilní systémy: ● Symbian OS - nejrozšířenější OS pro mobilní telefony, především Nokia. ● Rim BlackBerry OS - OS mobilních zařízení Blackberry. ● iPhone OS - systém mobilních telefonů iPhone a přehrávačů iPod Touch, založený na Mac OS X firmy Apple. ● Windows Mobile - OS firmy Microsoft ● Android - vyvinutý firmou Google, založený na Linuxu, nyní spravovaný Open Handset Alliance. ● Linux - platformy založené na Linuxovském jádře. ● Palm webOS - OS firmy Palm Inc. ● bada - operační systém pro mobilní telefony firmy Samsung. ● Maemo - platforma firmy Nokia založená na operačním systému Debian. OS pro servery - Wndows NT, Server 2003, Server 2008. Server 2011, UNIX (BSD, LINUX), např. distribuce: UBUNTU, FreeBSD, OpenBSD, Mandriva, atd. ● ●
jednouživatelské jednoúlohové (single-user single-task) např. CP/M, MS-DOS;s podporou operačního systému běží pouze jedna aplikace jednouživatelské víceúlohové (single-user multi-task) např. Windows 95, Windows 98; jeden uživatel může mít současně spuštěno více aplikací
●
víceuživatelské víceúlohové (multi-user multi-task) např. UNIX, Linux; umožňují zpracovávat požadavky více uživatelů současně systémy s reálným časem (real time) – zejména pro řízení technologických proces
Operační systém – typy (jádra) Operační systém se skládá z jádra a pomocných systémových nástrojů. Jádro je zavedeno do operační paměti při startu (bootování) počítače a je mu předáno řízení. U pokročilých operačních systémů jádro nikdy neztrácí kontrolu nad počítačem a po celou dobu jeho běhu koordinuje činnost ostatních běžících procesů. Označení kernel pochází z angličtiny, kde označuje jádro pecky, zrno nebo ztvrdlou dužinu ovoce. Hlavní úkol jádra spočívá v přidělovaní paměti a času procesoru (či procesorů) programům, ovládání zařízení počítače (pomocí ovladačů) a abstrakci funkcí (aby bylo např. možné načítat soubory z pevného disku a z jednotky CD-ROM stejným příkazem). Pro zajištění bezpečnosti operačního systému je nutné, aby procesor podporoval dva módy činnosti: omezený pro aplikace a privilegovaný (se speciálními strojovými instrukcemi) pro jádro. Privilegovanému módu se proto někdy říká kernel mód. ● ● ●
monolitické jádro – jádro je jedním funkčním celkem mikrojádro – jádro je velmi malé a všechny oddělitelné části pracují samostatně jako běžné procesy hybridní jádro – kombinuje vlastnosti monolitického jádra i mikrojádra Operační systém – poskytované funkce
Operační systém plní tři základní funkce: 1. ovládání počítače – umožňuje uživateli spouštět programy, předávat jim vstupy a získávat jejich výstupy s výsledky 2. abstrakce hardware – vytváří rozhraní pro programy, které abstrahuje ovládání hardware a dalších funkcí do snadno použitelných funkcí (API) 3. správa prostředků – přiděluje a odebírá procesům systémové prostředky počítače Ovládání počítače - Při definici operačního systému se obvykle omezuje ovládání počítače na schopnost spustit program, předat mu vstupní data a umožnit výstup výsledků na výstupní zařízení. Někdy je však pojem operační systém rozšířen i na grafické uživatelské rozhraní, což může být z důvodů marketingových, ale i problému nejasné hranice mezi operačním systémem a aplikacemi. U systémů, které disponují jediným grafickým rozhraním (Microsoft Windows, Symbian OS, …) je často grafické rozhraní zahrnováno do operačního systému. U systémů, kde je uživatelské rozhraní možné vytvořit několika nezávislými způsoby nebo různými aplikacemi, je běžné nepovažovat ho za součást systému.
Abstrakce hardware - Operační systém skrývá detaily ovládání jednotlivých zařízení v počítači (tzv. hardware) a definuje standardní rozhraní pro volání systémových služeb[1] tak, že vytváří abstraktní vrstvu s jednoduchými funkcemi (tzv. API), které využívají programátoři aplikací. Tím nejen zjednodušuje programátorům vytváření programů, ale umožňuje programům pracovat i se zařízeními, které v době vzniku programu neexistovaly (například z hlediska programátora není rozdíl mezi otevřením souboru na pevném disku, CD, DVD, flash, síťovém disku nebo Blu-ray). Někdy je uvnitř operačního systému vytvářena podobná abstraktní mezivrstva, která usnadňuje programování ovladačů jednotlivých zařízení . Správa zdrojů - Operační systém přiděluje spuštěným programům systémové prostředky (operační paměť, procesor, pevný disk, vstupně-výstupní zařízení). V případě potřeby může operační systém procesům přidělené prostředky násilně odebrat (preempce). Operační systém využívá schopnosti procesoru k ochraně sebe samého, ale i k oddělení pracovního prostoru jednotlivých procesů. Správa procesů Moderní operační systémy umožňují spustit zároveň více procesů což nazýváme multitasking. Pokud je v počítači méně procesorů, než je běžících procesů, musejí se procesy na procesorech střídat, což označujeme jako změnu kontextu. Změna kontextu je operace, při níž multitaskingový operační systém přepíná řízení mezi procesy. Při tom se ukládá a načítá aktuální stav procesoru. Tento děj se u moderních procesorů opakuje mnohokrát za sekundu. Změny kontextu jsou obvykle výpočetně intenzivní a hodně plánované a operační systémy jsou k tomu optimalizované. Změnou kontextu můžeme myslet změnu kontextu registrů, vláken, úloh a procesů. Ke které změně kontextu dojde, záleží na procesoru nebo operačním systému.
Nepreemptivní (kooperativní) multitasking Nepreemptivní multitasking vyžaduje aktivní spoluúčast běžících úloh. Každá úloha je povinna dostatečně často systémovým voláním předat řízení zpět operačnímu systému, který díky tomu může spustit jinou úlohu, která se po chvíli opět dobrovolně vzdá procesoru atd. Výhodou řešení je jednodušší implementace operačního systému. Podstatnou nevýhodou je skutečnost, že chybně naprogramovaná úloha, která nevrátí řízení zpět operačnímu systému, způsobí úplné zastavení systému i ostatních úloh.(Windows 95, 98) Preemptivní multitasking V preemptivním multitaskingu o přidělování a odebírání procesoru jednotlivým úlohám plně rozhoduje operační systém. V pravidelných intervalech (typicky zhruba 100× až 1000×
za sekundu) přeruší provádění běžícího programu, vyhodnotí aktuální situaci (které úlohy žádají o přidělení procesoru, jejich priority atd.) a nechá běžet buď opět úlohu, kterou přerušil, nebo jinou úlohu, která má zájem o přidělení procesoru. I v preemptivním multitaskingu však může úloha dobrovolně požádat o přepnutí kontextu a vzdát se zbytku svého kvanta (úloha takzvaně „usne“ nebo se zablokuje provedením pomalé vstupně-výstupní operace, jako je například čtení dat z pevného disku). Výhodou tohoto řešení je, že nedochází k „zatuhnutí“ počítače, neboť i v případě, že se úloha zacyklí, odebere operační systém pomocí časovače dané úloze řízení a přidělí procesor jiné úloze. Nevýhodou je složitější implementace operačního systému a nutnost hardwarové podpory v procesoru počítače (viz privilegovaný režim). (Windows NT, unixové systémy)
Program, proces Počítačový program je v informatice postup operací, který popisuje realizaci dané úlohy. Počítačový program může být vytvořen programátorem zápisem algoritmu v nějakém programovacím jazyce. Zapsaný program může být v počítači prováděn interpretem nebo může být pomocí překladače nejprve přeložen do strojového kódu a teprve pak přímo prováděn mikroprocesorem. Proces je v informatice název pro spuštěný počítačový program. Proces je umístěn v operační paměti počítače v podobě sledu strojových instrukcí vykonávaných procesorem. Obsahuje nejen kód vykonávaného programu, ale i dynamicky měnící se data, která proces zpracovává. Jeden program může v počítači běžet jako více procesů s různými daty (například vícekrát spuštěný webový prohlížeč zobrazující různé stránky). Správu procesů vykonává operační systém, který zajišťuje jejich oddělený běh, přiděluje jim systémové prostředky počítače a umožňuje uživateli procesy spravovat. Životní cyklus procesu Životní cyklus procesu probíhá podle diagramu stavových přechodů. U několika soupeřících procesů je zařazení k běhu řízeno pravidly: časová kvanta, priorita, či bez možnosti přerušení. Přepínání procesů je značně časově náročné a může vyhovovat jen pro toleranci událostí s dlouhou latencí. ● ● ● ●
proces je vytvořen buď příkazem uživatele (u terminálu), nebo na žádost operačního systému o provedení služby, či na žádost jiného procesu (rodiče) „vytvořený“ proces je ve stavu „připravený“ – připravený k vykonání a čeká pouze na přidělení procesoru spuštěním procesu, na základě plánovacího algoritmu přechází proces do stavu „běžící“ „běžící“ proces může být ukončen normálně, tj. byl celý proveden, nebo násilně ukončen uživatelem, provedením chybné strojové instrukce, chybou vstupně–výstupní zařízení, porušením ochrany paměti, nebo na žádost rodiče apod.
● ●
„běžící“ proces může být po vypršením časového limitu pro jeho běh (uplynutí maximální časového kvanta) převeden do stavu „připravený“ „běžící“ proces může být jen jeden, máme-li jen jeden procesor, kdežto ve stavu „připravený“ může být více procesů zařazených do fronty nebo jiné datové struktury, kterou využívá plánovací algoritmus
Základní stavy procesů - Následující stavy procesů se vyskytují ve všech víceúlohových systémech: ● ● ● ●
●
vytvořený (created) – proces je vytvořen buď příkazem uživatele (u terminálu), nebo na žádost operačního systému o provedení služby, či na žádost jiného procesu (rodiče) připravený (ready) nebo čekající (waiting) – připravený pro vstup do stavu běžící, čeká pouze na přidělení procesoru běžící (running) – procesu je přidělen procesor a právě se provádí příslušné programy blokovaný (blocked) – proces je převeden do tohoto stavu v případě, kdy čeká na dokončení nějaké vstupně–výstupní operace, případně na skončení jiného procesu, uvolnění zdroje, synchronizační primitivum a podobně ukončený (terminated) – proces skončil
