Programozás | Programozás-elmélet » Légrádi - Fordítóprogramok, compilerek

Fordítóprogramok 1. A fordítóprogramok felépítése, az egyes funkcionális részek részletes feladatai Compiler: olyan fordítóprogram, melynél alapvetõen különválik a fordítási és a futtatási idõ. Az ilyen eszköz általában magasszintû nyelveket fordít gépi kódra. Forrásnyelvű prg Compiler tárgyprg Assembler: olyan compiler, amely jellemzõen assembly (a gépi kód szimbólikus megfelelõit tartalmazó) kódot fordít közvetlenül gépi kódra. Assembly Compiler tárgyprg Compiler felépítése: COMPILER: (forrásnyelvű prg)⇒(tárgykód, hibák) INPUT HANDLER: (forrásnyelvű prg)⇒(karaktersorozat) OUTPUT HANDLER: (forrásnyelvű prg, hibák)⇒(lista) SOURCE HANDLER: (forrásnyelvű prg, hibák)⇒(karaktersorozat, lista) CODE HANDLER: (tárgykód)⇒(tárgyprg) 2. A programok fordítása és a futtatása közti különbség, a fordító és értelmező programok működésének eltérései. Fordítóprogram: valamely programozási nyelv

forrásnyelvü programjának (source) tárgykóddá (object) alakítására szolgáló, általában szoftver megvalósítású eszköz. Fordítási idõ: az az idõ, ameddig a fordítóprogram a fent említett transzformációt elvégzi. Futási ideje. idõ: a már lefordított kód végrehajtásának Compiler: olyan fordítóprogram, melynél alapvetõen különválik a fordítási és a futási idõ. Az ilyen eszköz általában magasszintû nyelveket fordít gépi kódra Interpreter: olyan szoftvereszköz, mely a fordítási és futtatási idõt nem választja ketté. jellemzõ módon bizonyos egységek (pl. egy utasítás, vagy egy sornyi utasítás) valamilyen közbensõ kódra fordítása után, az elkészült kódot már le is képes futtani. Hibrid rendszer: mind a compiler, mind az interpreter tulajdonságok megtalálhatók benne. A forrásprogramok fordítása két, egymástól jól elkülöníthetõ egységbõl tevõdik össze, az analízis (felbontás, elemzés),

illetve a szintézis (létrehozás, felépítés) részbõl. Analízis fázis részei Lexikális elemzés: a forrásprogramot kisebb részekre (tokenekre, szimbólumokra) szabdaljuk, daraboljuk, mely részek elválasztójelek (space, tab, újsor, stb.) között találhatók, valamint ezenfelül a forrásból a felesleges dolgokat - pl. megjegyzéseket, "space" karaktereket eltávolítjuk. A szimbólumok elõfordulását, s ha kell az értékét a szimbólumtáblába feljegyezzük. Szintaktikus elemzés: a lexikális elemzõtõl kapott szimbólumsorozatot egyeztetjük a nyelvtani szabályokkal, hogy kiderüljön az, hogy a forrásnyelvû program megfelel -e az adott nyelv definíciójának. Szemantikus elemzés: a szintaktikusan elemzett programot ellenõrzi, hogy a formai szabályoknak megfelel -e. Ilyen formai szabály pl változók tipusának egyeztetése az értékadás két oldalán, mûveletek eredményének ellenõrzése (pl. sztinghez ne adjunk lebegõpontos

értéket). Szintézis fázis Kódgenerálás: az elõzõekben leírt módon elemzett program alapján futásképes (vagy további adminisztráció után futásképessé tehetõ) kód elõállítása. Kódoptimalizálás: a kódgenerátor által készített kód optimalizálása, pl. sebességének növelése, vagy hoszszának csökkentése kódátalakítással Konkurens programozás 1. Programok párhuzamos futtatásának elve, feltételei A párhuzamos programfutás olyan programrészek (látszólag) egyidejű, „átlapolt” végrehajtását jelenti, amelyek közös feladatot oldanak meg, ezért egymástól nem függetlenek. Vele szemben a multiprogramozás teljesen független programrészek átlapolt végrehajtását jelenti; amit elsősorban oprdsz-ek használnak, az erőforrások jobb kihasználása végett (CPU és B/K igényes feladatok váltogatott végrehajtásakor). A párhuzamos végrehajtás fogalmának pontosabb jelentése: nem sorrendi, műveleti sorrendiséget nem

kívánó. Az adatfeldolgozás eredménye nem változna, ha a párhuzamos utasítás-csoportokat a processzor(ok) eltérő sorrendben hajtaná(k) végre. Természetesen nem minden feladat párhuzamosítható. Ha tehát párhuzamosított programrészeket újra futtatunk, megváltozhat a műveletek végrehajtási sorrendje; az sem biztos, hogy a programozó által elkövetett hibák megismétlődnek. Emiatt a párhuzamos programozás során bonyolult hibakeresésre kell felkészülni; ráadásul a párhuzamos programozást támogató programnyelvek erősen gépfüggőek. Szálak: az egyetlen processzoron végrehajtandó – vagyis a nem párhuzamosítható – utasításcsoportokat elemi utasításfonalnak, szálnak nevezik (thread). Egy-egy ilyen szál pl. előállíthat más és más perifériára kimenő adatokat, vagy feldolgozhat más és más forrásból származó adatokat. Természetes tehát, hogy a szálak végrehajtásának sorrendje nem befolyásolja a végeredményt. A

szálon belül azonban az utasítások végrehajtási sorrendje meg van szabva. 2. Programok szinkronizációja, és ezek típusai Szimultán adatfeldolgozás (együttes, adatpárhuzamos feldolgozás): közös programot futtat több processzor, egymással összehangoltan (szinkronban), de eltérő adatokkal. Az ilyen, általában SIMD elvű számítógépben minden processzor külön helyi (privát) tárrészben tartja saját adatait és közös tárrészben az utasításokat. Egy szimultán adatfeldolgozás célja a sebesség növelése, az egyprocesszoros feldolgozáshoz képest. Konkurrens adatfeldolgozás (vetélkedő, multiproceszszoros, funkcionálisan párhuzamos feldolgozás): eltérő feladatú részprogramokat futtat több processzor (aszinkron módon, de párhuzamosan). Bár a feldolgozott adatok eltérők, a processzorok közös erőforrásért versengenek (pl puffer-területért) Az ilyen, MIMD elvű számítógépekben mind az adatok, mind az utasítások

elkülönített tárhelyekben vannak. A konkurrens adatfeldolgozás célja a részprogramok közti együttműködés megvalósítása. Ez különösen hasznos a gyártási folyamatokat irányító számítógépekben, vagy a termelést és a fogyasztást elemző-szimuláló közgazdasági számításokban. Folyamatok szinkronizációja alatt a folyamatok szinkron soros, vagy szinkron párhuzamos ütemezését értjük. A szinkronizáció célja egy vagy több folyamat utasításcsoportjainak, programrészeinek időzített végrehajtása. Olyan folyamatokról van szó, amelyek közös objektumon osztoznak (pl. szignálkezelő eljáráson), ugyanattól az erőforrástól várnak megszakításkérést, vagy szignált. Emiatt kölcsönösen hatniuk kell egymásra, jelzéseket kell küldeniük és fogadniuk: kommunikálniuk kell Folyamatközi kommunikáció (IPC = InterProcess Communication): az IPC-nek két fő módja van. A partnerfolyamatok mindkettőben a saját PID–jukkal

azonosítják magukat - szorosan csatolt rendszerben közös tárrészt használnak: változókat, szemafort, osztott adatszegmenst. - lazán csatolt rendszerben IPC-re az oprdsz által továbbított üzeneteket kell használni. Az üzenetek csak közvetve, egy „postafiókon” keresztül jutnak el a címzett folyamathoz. A SZINKRONIZÁCIÓ TÍPUSAI A szinkronizációnak 3 fő típusa van. Az első kettő szinkron soros, a harmadik szinkron párhuzamos ütemezéssel valósítható meg. Kölcsönös kizárás: a kölcsönös kizáráson alapuló szinkronizációra van szükség a leggyakrabban: pl. akkor, amikor egy soros elérésű perifériát (pl nyomtatót) több folyamat is használni kíván Lényege a nevében van: amikor az egyik folyamat fut, akkor a másik nem futhat és fordítva. A kölcsönös kizárás fogalmának leggyakoribb értelmezése az, hogy bizonyos programrészeket (folyamatokat) csak egymás után szabad beütemezni, egyidőben csakis egyiküket.

Végrehajtásuk sorrendje azonban nincs megszabva, többféle lehet Precedencia: ez a sorrendi típusú szinkronizáció pl. akkor fordul elő, amikor másolni kell egy állományt: előtte kell befejeztetni minden író-olvasó folyamatot. Precedencia során tehát bizonyos programrészeket (folyamatokat) – hasonlóan a kölcsönös kizáráshoz- csakis egymás után szabad beütemezni, sőt, még a végrehajtásuk sorrendjét is meg kell szabni. Randevú: az egyidejű típusú szinkronizáció fordul elő pl. akkor, amikor egy folyamat olvasni szeretne egy közös tárrészből (adatszegmensből, pufferből), de az üres, mert egy másik folyamat még nem termelt bele adatot. Megfordítva, a termelő folyamat készen állna arra, hogy írjon a közös tárrészbe, de az éppen teli van, mert a fogyasztó folyamat még nem igényelt ki belőle egy korábban beleírt adatot. A randevú közvetlen kommunikációt jelent a résztvevő folyamatok között. Szinkron párhuzamos

ütemezéssel valósítható meg. Lényege, hogy a kommunikáló folyamatok bizonyos programrészei bevárják egymást: arra várnak, hogy a folytatáshoz adatot kapjanak a másik programrésztől. Az adatszolgáltatás előtt és után azonban a folyamatok felváltva, tetszőleges sorrendben, párhuzamosan is futhatnak. 3. A kritikus szakasz A közös erőforrásra hivatkozó utasításcsoportok, kódszegmensek neve kritikus szakasz (kritikus szekció). Konkurrens folyamatoknak –erőforrásigényeik egyeztetése céljából– értesíteniük kell egymást arról, hogy valamelyikük belépett-e már egy kritikus szakaszba, vagy éppen belépni készül oda. Emiatt a szinkronizáció úgy tekinthető, mint a folyamatközi kommunikáció (IPC) speciális esete. Ha ugyanis az utasítás-csoportok között nem lehetne biztosítani a kritikus szakasz programkódjával szemben támasztott követelményeket: Kölcsönös kizárás: a kritikus programrészek egyidejű végrehajtása

nemcsak a kölcsönös kizáráson alapuló szinkronizáció során tilos, de a precedencia és a randevú típusú szinkronizálás esetén sem engedhető meg. Véges időn belüli beléptetés: ezzel a követelménnyel a következőket lehet elérni: a. „előrehaladást” a legelső igénylő folyamat számára, ha a kritikus szakasz üres (még nem lépett be egyetlen folyamat sem). b. az „éhezés” elkerülését (mind az író, mind az olvasó folyamatok számára), ha nem üres a kritikus szakasz. c. a „holtpont” elkerülését, amit pl az idézhet elő, hogy egy nagy prioritású folyamat futása kedvéért az ütemező feltartóztat egy kisebb prioritású folyamatot; ha viszont ez utóbbi korábban már belépett a kritikus szakaszba, akkor a nagyobb prioritású folyamat hasztalan várná, hogy ő is beléphessen oda. Korlátozott számú ismételt beléptetés: ez a követelmény a további igénylők érdekét szolgálja, hiszen köztük lehetnek kisebb

prioritásúak is, mint az első belépő prioritása. Emiatt ennek a követelménynek a teljesítése programozástechnikailag igen nehéz. Hibamentesség: tranzakciók –pl. távoli helyfoglalások– rendszerösszeomlás utáni helyreállításához a kritikus szakaszba lépés előtt menteni kell az osztott változók értékeit. 4. Szemaforok és alkalmazásuk lehetőségei Információ-feldolgozás: számítógépes erőforrásoknak nevezünk minden olyan SW-elemet és programozható HWeszközt, amely adatfeldolgozásban vesz részt, információ-átalakításhoz szükséges. Az oprdsz is adatfeldolgozást végez; számára ugyanis egy folyamat indítása, futtatása, megállítása jelenti az adatfeldolgozást. A Neumann-elvű számítógépek oprdsz-e minden folyamatot adatnak tekint: megkülönbözteti az alkalmazói- és rendszerfolyamatok kód-, adat- és veremterületét, létrehozza és mozgatja őket a memóriában, sőt, megjeleníti őket a CPU számára, amikor

átadja nekik a vezérlést. Ütemezés: a vezérlés átadása előtt a rendszerSW az, amelynek garantálnia kell az igényelt erőforrások használatát az adatfeldolgozó folyamat számára. Minden folyamatnak valamilyen vezérlési elv által megszabott ütemben , sorrendben kell futnia. Az oprdsz-nek is van beépített vezérlési elve: a folyamatok erőforrásigénye. Minthogy az erőforrások végesek, a folyamatoknak versengeniük kell egymással, és egy rendszerSW-re van szükségük, hogy az eldöntse, melyiküknek biztosítson erőforrást és meddig. Az oprdsz ütemezője a többi folyamatot addig sorba állítja és várakoztatja. Osztott és osztatlan erőforrások: egy osztott erőforrás gyakorlatilag párhuzamosan érhető el: különféle részeit több folyamat használhatja, szinte egyszerre vagy felváltva. Ilyen pl a CPU (többprocesszoros rendszerben), a memória, egy több felhasználó által osztott olvasásra megnyitott állomány, a mágneslemezek, vagy

egy ablakrendszerű képernyő. Ezzel szemben egyszerre mindig csak egy folyamat számára érhető el, ezért osztatlan erőforrás pl. a CPU (egyprocesszoros rendszerben) és általában soros elérésű perifériák: a nyomtató, a mágnesszalag, a terminál, vagy az aktív alkalmazásablak egy ablakrendszerű képernyőn (ez utóbbit csak az előtérfolyamat használhatja). Osztatlan erőforrás egy sín topológiájú helyi hálózat koax kábele is SZEMAFOROK ALKALMAZÁSÁNAK MÓDJAI Oszthatatlan műveletek: szorosan csatolt folyamatok – pl. kódmegosztásos szülő-, gyermek- vagy testvérfolyamatok- un oszthatatlan művelettel módosíthatnak egy közös adatot, melynek változótípusa a programnyelvbe épített szemafor. Ha ez a változó hozzá van rendelve egy kritikus szakaszhoz, akkor a neve privát szemafor. A kritikus szakaszt a szemafor vasúti vágánynak tekinti, amelyre különféle irányokból közeledhetnek vonatok (folyamatok), de egyszerre csak egyiküket

szabad beengedni a kritikus szakaszba. Minden folyamatnak a szemafor módosításával kell jeleznie - belépési szándékát (még a kritikus szakasz végrehajtása előtt): a szemaforokat kezelő egyik rendszerrutinban, az un. monitorban pl. ezt segíti a wait (PID-várólista) nevű oszthatatlan művelet (rendszerhívás) - kilépését a kritikus szakaszból; ezt segíti pl. a signal(várólista) nevű oszthatatlan művelet (rendszerhívás). Oszthatatlan művelet az olyan utasítás-sorozat vagy gépi kódú utasítás, melynek eredményét nem befolyásolja, ha végrehajtása közben az ütemezőnek még munkaváltást is végre kell hajtania. Pl az Intel 80486 összes LOCK prefixű utasítása oszthatatlan, hiszen lefoglalja a rendszersínt. Egyetlen gépi kódú utasítás használata azonban nem elég ahhoz, hogy korlátozható legyen az ismételt beléptetések száma A szemafor definíciója: a szemafor az oprdsz globális változója, a kritikus szakasz kezelésének

eszköze, a folyamatok szinkronizálásának régi, struktúrálatlan, de legáltalánosabb módszere. 3-féle típusa van: - logikai (másnéven bináris): ilyen pl. az Intel 80486 bináris szemafortáblát vizsgáló utasítása a BTS (Bit Test and Set) vagy a BSR (Bit Scan Reserve) - integer (másnéven számláló): ilyen típusú szemafor számlálja egy olvasó folyamat számára az adatpuffer telítettségét, vagy egy író folyamat számára a puffer üres helyeit - összetett (record vagy queue típusú, másnéven várólistás) Szemafort létrehozni a UNIX-ban pl. a semget() rendszerhívással lehet Oszthatatlan szemaforműveletek: a szemafornak, mint változónak midig van kezdőértéke, és csak két oszthatatlan művelet végezhető vele. A szabályos kezdőértékadást a szülőfolyamatnak kell végrehajtania, pl. a következőképpen: While (Szem <>kezdő) Do If (Szem<>kezdő) Then V(Szem) Else P(Szem); A kritikus szakaszba történő belépés előtt

meghívandó az un. P() eljárás Ennek a primitívként lefutó rendszerhívásnak a lényege a következő: Procedure P(var S:integer); angolul wait Begin While (S>=0) Do aktív üresjárat Dec(S); End; A P() eljárás aktív üresjáratát (busy-waiting, livelock) ki kell küszöbölni, hogy ne sajátíthassa ki a CPU-t. Ennek érdekében a hívó folyamatnak összetett szemafort kell igényelnie és a P()-nek kérnie kell a saját –és a hívó- feltartóztatását. Ennek érdekében egy recordban közölnie kell a hívó folyamat PID-ját is, a szemafor azonosítója mellett. A PID ezzel felkerül az összetett szemafor várólistájára A kritikus szakasz elhagyását jelző V() eljárás lényege a következő: Procedure V(var S:integer) angolul signal() Begin Inc(S); End; A V() eljárás szabad jelzésűre állítja a szemafort, a kritikus szakaszhoz érkező többi folyamat számára. Várólistás szemafor esetén a V()-nek még ki kell választania a várólistára

került folyamatok (PID-jai) közül azt, amelyiket majd az ütemezőnek futásra kész állapotba kell hoznia. A konkurrens programvégrehajtás kezdetét a C nyelvekben a fork kulcsszó (szétágazás rendszerhívás) jelzi, a konkurrens programvégrehajtás végét padig a join (csatlakozás), ill. a wait (veszteglés) A fork() rendszerhívás visszatérési értéke a szülőben létrehozott gyermekfolyamat PID-ja, a gyermekben viszont 0. A struktúrálatlanság miatt a szülőben elég könnyű megfeledkezni a wait()-ről, a gyermekben pedig az exit()-ről. Maga a megoldás azonban minden szinkronizáció-típushoz használható. Konkurrens Pascal-ban a Dijkstrától eredő parbegin és parend kulcsszavak között kell felsorolni a párhuzamosítandó utasításokat (külön szálnak számít minden begin-end közé írt utasításcsoport). 5. Erőforrások védelme, módszerei Az állományműveletek korlátozása nagyban függ az oprdsz-től. Osztatlan perifériák

lefoglalása: egy osztatlan periféria használatba vételét jelezni kell a többi igénylő folyamatnak is. Erre szolgál többek között egy perifériához rendelhető rendszerváltozó, az un szemafor Ennek kezdőértékét az adott periféria lefoglalása/felszabadítása esetén az oprdsz eggyel növeli/csökkenti Ha az eredmény 0, akkor az osztatlan periféria szabad, egyébként a szemafor számlálhatja foglalási igényeket, amiket a különféle folyamatok jelentettek be. Sürgősségük szerint ezeket az ütemező sorba is állíthatja. Ilyenkor jó, ha az oprdsz automatikusan tudja változtatni a folyamatok prioritását, nehogy a szemafornál való várakoztatásuk a végtelenségig tartson, kiéheztetéssé fajuljon. Web-programozás 1. Mi a hipertext, s milyen tulajdonságai vannak? Miben különbözik pl egy átlagos szövegtől, vagy dokumentumtól? Hipertext (hypertext): olyan - célszerûségbõl elektronikus formában adott - "dokumentum", melynek

részei (oldalai) között nem a "rákövetkezés" reláció értelmezett feltétlenül, mint mondjuk egy nyomtatott könyv esetén, hanem az egyik rész után akár több "következõ" lap is lehet, sõt, nem kell feltétlenül, hogy a "lapok" fizikailag egy helyen legyenek, lehetnek nagy távolságokban is (pl. a hálózaton) 2. Milyen hipertext-leíró nyelveket ismer? Melyik az Interneten legjobban elterjedt? Dokumentum leírónyelv: olyan eszköz, melynek segítségével egy adott dokumentum formai, és tartalmi tulajdonságai is leírhatók, pl. egy szöveg betûinek tulajdonságai (pl Times CE, dõlt, 12 pontos méretû) Az ilyen módon adott dokumentum tartalmaz mind formai leíró információt (ezeket a dolgokat pl. a HTML-ben "tag" néven nevezik), mind pedig azt a szöveget, amit tulajdonképpen leírunk az elõbbiekkel. Jelenleg az Interneten a HTML dokumentum-leírónyelvvel készített infomáció talán a legelterjedtebb

(népszerûbb nevén "web-lap", vagy "hompédzs"). HTML: leírónyelv (HyperText Markup Language), mely nevébõl adódóan hipertext – típusú információk kezelését teszi lehetõvé. Alapvetõen statikus megoldásokat támogat Az ilyen dokumentumok szervereken tárolódnak, s megjelenítésüket a kliensek (böngészõk) végzik. Elemkészlete adott, nem bõvíthetõ a felhasználói által XML: (eXtensible Markup Language) olyan dokumentum leírónyelv, mely rendelkezik azzal a tulajdonsággal, hogy újabb leíró elemeket is lehet vele létrehozni, tehát akár a használói által is kiegészíthetõ nyelvi elemekkel (ez pl. a HTML-ben nincsen!) 3. Mi jellemzi a kliens-szerver nyök-hátrányok)? architektúrát új (Elő- Kliens-szerver architektúra: olyan elosztott rendszer, melyben bizonyos funkciók gépekhez társítottak, pl. file-tárolás, nyomtatás vezérlést egy un szerverre bíznak A kiszolgálái igények a szerver felé az un.

kliensek felõl érkeznek Szerver: olyan számítógép, mely erõforrásokban gazdag (pl. sok memóriával, és/vagy sok, és nagykapacitású háttértárral rendelkezik). Jellemzõ felhasználási területe napjainkban web-szerver Kliens: olyan - önállóan is használható - számítógép, melynek segítségével a szerverektõl igényelhetõk szolgáltatások. Jellemzõ felhasználási területe napjainkban pl web-böngészõ (browser) Előnye: - elosztott rdsz Hátránya: - a kommunikációhoz kell egy kliens és egy szerver is + megbízható hálózat - ha a szerver meghibásodik, akkor annyi az egésznek