188025. lajstromszámú szabadalom • Eljárás és berendezés egynél több, egyidőben jelentkező, különböző kéréserősségű, szekvenciális végrehajtást kívánó műveleti igény időoptimális kielégítésére
1 188 025 2 egység kimeneteire, kimenetei pedig vezérlő D vezetékkötegen és időzítő T vezetékkötegen keresztül a 14 kiszolgáló egység bemeneteire csatlakoznak. (7. ábra) A találmány tárgya eljárás és berendezés egynél több, egyidőben jelentkező, különböző kéréserősségű, szekvenciális végrehajtást kívánó műveleti igény időoptimális kielégítésére. Mint ismeretes, programvezéreit műveletek mikroprogramozott végrehajtása (számítógépek bitslice-os, vagy emulált megvalósítása), megadott sorrend (prioritás) szerint végrehajtandó műveleti igények szekvenciális lekérdezése, illetve végrehajtása (pl. busz vagy egyéb hardware erőforrások optimális időbeni elosztása az igénylők között), illetve egyéb hardware jellegű feladatok megoldása során igen gyakran felmerül a feladat, hogy különböző kéréserősségű (prioritású), N számú igényt minimális ráfordítással elégítsünk ki. A fent vázolt feladat hagyományosan az 1. ábrán látható folyamatábra által vázolt általános módon oldható meg. Mint látható, ennél a módszernél, mielőtt az 1, 2, ... N igénynek megfelelő művelet elvégzését elkezdenénk, egy lekérdezési művelettel meg kell győződnünk róla, hogy az adott végrehajtási ciklusban a végrehajtáskor éppen soron lévő műveleteknek megfelelő igény egyáltalán fennáll-e, a művelet végrehajtására ugyanis egyébként nem kerül sor. Ha a folyamatábra például egy mikroprogram utasítás végrehajtását, vagy egy számítógép periféria kiszolgálását reprezentálja, ezek a lekérdezések idő- és tárolóigényesek. Nyilvánvaló, hogy az 1. ábra szerinti folyamatnak a t = t„ időpontban jelentkező max. N db lehetséges kombinációnak megfelelően 2N lefolyása lehetséges. Ha a lehetséges 2N változatból az igények jelentkezésének időpontját követően azonnal sikerül az igények adott kombinációjának megfelelőt kiválasztani, ezek az időigényes lekérdezések a továbbiakban elmaradnak, a folyamat elágaztatást sikerül egy lépésben, a folyamat kezdetekor elvégezni. A probléma megoldásának ezt a második, elvileg lehetséges változatát a 2. ábra szemlélteti. A 2. ábrán látható, hogy ebben az esetben a t = t0 időpontban jelentkezett műveleti igények kiszolgálása egyetlen lépésben történik. Ez a módszer az 1. ábra szerinti eljárásnál fellépő időveszteségeket kiküszöböli, mert a t = t0 időpontban jelentkezett igénykombinációknak megfelelő műveletek egy lépésben történő kiszolgálása azt jelenti, hogy a nemlétezö igények lekérdezése feleslegessé válik. Ez a tény önmagában időoptimális végrehajtást tesz lehetővé, még akkor is, ha egynél több igény esetén, az egyes igények kiszolgálását egy adott feladatnál végül is egymás után következő (szekvenciális) lépésekben kell kiszolgálni. A 2. ábra szerinti módszernek igen nagy hátránya, hogy az összesen 2N-féle lehetséges végrehajtási variáns egy lépésben történő megkülönböztetése igen nehézkes, és ha a folyamatábra egy mikroprogram futását reprezentálja, a 2N-féle változat egymástól független megvalósítása egyben 2N számú, egymástól gyakorlatilag független szubrutin megírását jelenti. A módszer így rendkívül tárolóigényes, és nagy értékű N esetén a fentebb említett nehézségeket is figyelembe véve, gyakorlatilag nem alkalmazható. A fenti két, hagyományos megoldási módszer időviszonyainak jobb áttekintése céljából kövessük nyomon a fenti megoldások idődiagramjait. Az 1. ábra szerinti megoldás idődiagramját a 3. ábra, a 2 ábra szerinti megoldás idődiagramját a 4. ábra szemlélteti. Tekintsük először a 3. ábrát! Látható, hogy az Iu I2,..., IN igények mintavételezése a t = t„ időpontban történik. Ha egy In igény a t = t0-At és t = t0 időpontok között fennáll, az S mintavételező impulzus hatására eltárolásra keiül, és a t = t0 időpontot követően megjelenik az \ jel, az I„ igény eltárolt megfelelője. Látható, hogy az In igény kiszolgálást jelentő Tn művelet végrehajtására az I„ igény lekérdezését követően csak akkor kerül sor, ha a lekérdezés eredménye az volt, hogy az I„ igény fennáll. Az I,, I2...,In,...,IN igények lekérdezése azonban minden esetben megtörténik, és ez időveszteséget jelent. Igen fontos megjegyezni, hogy ha az 1. ábra ismertetése során tett feltételezéssel élünk, és az idődiagramon is egy mikroprogram futását ábrázoljuk, akkor a mintavételezés és eltárolás egyetlen impulzus hatására, hardware úton megy végbe, míg az IB tárolt igények lekérdezése és a megfelelő M műveletek végrehajtása a mikroprogram egy megfelelő utasítássorozatának végrehajtásával történik, és így az idődiagram időarányaiból következőnél lényegesen hosszabb időt vesz igénybe. A 4. ábrán a 2. ábra szerinti másik lehetséges, hagyományos megoldási változat idődiagramját láthatjuk. A 4. ábrán az It, I2,...,IN igények mintavételezése a 2. ábra idődiagramjának megfelelően történik. Látható azonban, hogy itt az igények lekérdezése egyetlen lépésben történik, és ez az egyetlen elágazás megfelelő áramköri elrendezés segítségével hardware úton megvalósítható. Ez a 3. ábrához képest, azon túl, hogy itt N-szeri lekérdezés helyett csak 1-szeri elágaztatás szükséges, további időmegtakarítást eredményez. A 4. ábra szerinti megoldásnál, végeredményben az I,, I2,.. .,IN igények m-edik kombinációjának megfelelő Fm műveletsor végrehajtására úgy kerül sor, hogy az egyes igényeknek megfelelő Mj, M2,...,MN műveletek végrehajtása szünet nélkül, egymás után kerül sorra. Ez azonban azt jelenti, hogy az Mj, M2,...,MN műveletek fizikailag az Ilt...IN igények 2N kombinációjának megfelelő számban kell megvalósítani, ami nagyszámú N esetén gyakorlatilag lehetetlen. A találmány célja egy olyan megoldás kialakítása, amely a fenti problémákat maradéktalanul megoldja. A találmánnyal megoldandó feladat ennek megfelelően egy olyan eljárás és berendezés kialakítása, amely lehetővé teszi, hogy-a prioritási sorrendbe rendezett I1( I2,...,IN igények kiszolgálását végző M t, M2..., MN műveleteket (a műveletek végrehajtását végző szubrutinokat) csak egyszer kelljen fizikailag megvalósítani;- 5 10 15 20 25 30 35 40 45 50 55 60 65 2
