dr. Adamis Gusztáv OPERÁCIÓS RENDSZEREK PÉLDATÁR

dr. Adamis Gusztáv OPERÁCIÓS RENDSZEREK PÉLDATÁR

1

BEVEZETÉS

A Gábor Dénes Mûszaki Informatikai Fõiskola egyik alapkoncepciója a távoktatás támogatása. Ez azt igényli, hogy a hallgatókat olyan oktatási anyagokkal lássuk el, amelyek segítségével otthon, önállóan meg tudják érteni és el tudják sajátítani a tananyagot. Jelen példatárunk a Fõiskola Operációs rendszerek c. tárgyához készült. A példatár felöleli a tárgy teljes tananyagát. A példatárban alapvetõen két típusú feladat található. Az egyik típusú példa az olvasó elméleti felkészülését segíti. Ezekre a példákra hosszabb-rövidebb elméleti összefoglaló a válasz. Ezek a példák az anyag fontosabb részeire, fogalmaira kérdeznek rá, igyekezvén rávezetni az olvasót a súlyponti témakörökre. Természetesen az ilyen jellegû példákhoz közölt megoldások csak összefoglalások, részletesebb megértésükhöz nélkülözhetetlen a tankönyv [2] tanulmányozása. A példák másik csoportját a gyakorlati kérdések alkotják. Ezek keretében van mód az elméleti ismeretek alkalmazására egy-egy konkrét szituációban. Az ilyen jellegû példákhoz adott megoldások általában nem csak a "végeredményt" tartalmazzák, hanem igyekeznek megmutatni a megoldás elvét, fõbb lépéseit is. Végezetül egy jótanács a példatár használatához. Ezt a példatárat ne "tankönyvként" használjuk, azaz ne olvassuk el egyfolytában az elejétõl a végéig. Elõször mindig csak a vastag betûvel szedett kérdést nézzük meg, majd próbáljunk meg a kérdésre önállóan válaszolni. Csak ez után olvassuk el a megoldást, hogy ellenõrizzük saját válaszunk helyességét. (Természetesen vegyük figyelembe azt is, hogy egy kérdésre sokszor egynél több helyes, egymással egyenértékû válasz adható!) Ha a könyvet ilyen módon használjuk, sokkal hasznosabb segítséget fog nyújtani a felkészüléshez. Jó tanulást, sikeres felkészülést kíván A szerzõ

Budapest, 1995. december

2

PÉLDATÁR 1. Mik az operációs rendszerek fõbb funkciói? Az operációs rendszerek három fõ funkciója: - alkalmazói támogatás - alkalmazói programok - segédprogramok - rendszerszolgáltatások - operátori és munkavezérlõ parancsnyelvi rendszerek - programfejlesztési támogatás - programírás támogatása - editorok - fordítóprogramok (compiler) / interpreterek - szerkesztõprogramok (linker) - programkönyvtárak - rendszerhívások - betöltõprogramok (loader) - programok belövéséhez nyújtott támogatás - nyomkövetõprogramok ("debuggerek") - tártartalom kijelzése ("dump") - rendszeradminisztráció (magának az operációs rendszernek a mûködtetéséhez szükséges szolgáltatások) - processzorütemezés - megszakításkezelés - erõforráskezelés, szinkronizálás, idõzítés - folyamatvezérlés - tárkezelés - perifériakezelés - adatok, adatállományok kezelése - mûködési statisztikák készítése, számlázás - operátori interfész 2. Ismertesse a legfontosabb címzési módokat! Milyen magasszitû (programozási nyelv, operációs rendszer) funkciókat támogatnak? - direkt címzés - a címmezõ az operandus címét tartalmazza

3

- változók támogatása - indirekt címzés - a címmezõ annak a memóriahelynek a címét tartalmazza, ahol az operandus címe található - pointerek (mutatók) támogatása - immediate címzés - a "címmezõ" magának az operandusnak az értékét tartalmazza - konstansok támogatása - indexelt címzés - a cím a címmezõ tartalma + egy speciális, ún. indexregiszter tartalmának az összege - tömbök, rekordok kezelésének támogatása - bázisrelatív címzés - a cím a címmezõ tartalma + egy speciális, ún. bázisregiszter tartalmának az összege. A bázisregiszter tartalmazza a program kezdõcímét, az utasítás címmezõje pedig a program elejétõl való távolságot. A bázisregiszter tartalmának megváltoztatásával - a programkód változatlanul hagyása mellett a program a memóriában bárhová elhelyezhetõ. - áthelyezhetõ (relokálható) progamok támogatása - a virtuális tárkezelés (lapozás) illetve a szegmentálás támogatása - stack pointeren keresztüli címzés - az utasítás nem tartalmaz címmezõt, a címet egy speciális regiszter, az ún. stack pointer tartalma jelenti - függvényhívások támogatása - függvények paraméterátadásának támogatása 3. Mik a CISC és a RISC gépek fõbb jellemzõi? A CISC (Complex Instruction Set Computer - összetett utasításkészletû számítógép) jellemzõi: - sokfajta, bonyolult utasítás - sokfajta, bonyolult címzési mód - operációsrendszer-szolgáltatásokat támogató hardver elemek és utasítások

4

- összetett adattípusok - magasszintû programnyelvi egységek támogatása - bonyolult hardver. Értékelés: a bonyolult funkciók nagy részét igyekszik hardver úton megoldani vagy legalább támogatni. Emiatt bonyolult szerkezetû. A bonyolult szerkezetbõl fakadó nagy belsõ késleletések miatt az utasítások végrehajtási ideje (relatíve) nagy. De a hardvertámogatás miatt viszonylag könnyû (rendszer)szoftvert írni rá. Ilyen pl. az INTEL 80386-os mikroprocesszor. A RISC (Reduced Instruction Set Computer - csökkentett utasításkészletû számítógép) jellemzõi: - kevés, nagyon egyszerû, egyforma hosszú (1 órajel idõ alatt végrehajtható) utasítás - utasítások átlapolása (pipeline) egyszerûen megvalósítható - csak az abszolút szükséges memóriareferens utasítások, nagyon sok belsõ regiszter - egyszerû, gyors - emiatt olcsóbb - hardver. Értékelés: a bonyolult funkciókat szoftver úton kell megoldani, emiatt nehéz - az alacsony szintû - programozása. De az egyszerû hardver sok regiszterrel biztosítja a gyors mûködést. Ilyen például az IBM RISC 6000-es gépcsaládja. 4. Ismertesse a megszakítások elfogadásának és kiszolgálásának fõbb lépéseit! 1.,

2.,

3.,

4., 5.,

Megszakítási kérelem érkezik a központi egységhez. Ez érkezhet kívülrõl, pl. egy perifériától (hagyományos interrupt), a rendszeren belülrõl, pl. 0-val való osztás (exception - kivételes állapot) illetve a programozótól, pl. DOS-ban egy operációsrendszer-szolgáltatás hívása az INT 21H utasítással (szoftver interrupt). A központi egység a megszakítás kérelmet várakoztatja az éppen végrehajtás alatt álló utasítás végrehajtásának befejeztéig, illetve ha az adott szintû megszakítás tiltott, a tiltás befejeztéig. Amikor a központi egység elfogadja a megszakítást, elmenti a megszakított program állapotát jelzõ állapotvektort (vagy legalább annak legkritikusabb részét) a megfelelõ verembe. Automatikusan privilegizált állapot jön létre, amelyben többnyire legalább az adott szintû megszakítás letiltódik. A központi egység meghatározza a kiszolgáló eljárás címét (vagy kívülrõl a megszakítást kérõ eszköz adja be vagy - fejlettebb esetekben - a megfelelõ

5

6., 7., 8., 9.,

megszakítási vektorból a CPU veszi elõ) és elindítja a kiszolgáló eljárást, elõtte - szükség esetén - betölti a kiszolgáló eljárás induló állapotvektorát. A kiszolgáló eljárás befejezi a megszakított program állapotvektorának mentését és elvégzi a megszakítás kiszolgálási tevékenységet. Amint a megszakítás kiszolgálás túl van a kritikus szakaszon, újra engedélyezi a megszakítás elfogadáskor automatikusan letiltott megszakítási szint(ek)et. A megszakítás végén a kiszolgáló eljárás átadja a vezérlést az operációs rendszer megfelelõ (többnyire az ütemezõ) eljárásának. Az ütemezõ dönt a folytatásról, általában visszaadja a vezérlést a megszakított programnak, miután helyreállítja annak az állapotát az elmentett állapotvektorból.

5. Milyen támogatást nyújtanak az operációs rendszerek a programfejlesztéshez? Az operációs rendszerek által tipikusan nyújtott programfejlesztési támogatás: - A program megírásához nyújtott támogatás: - editorok (esetleg speciális nyelvérzékeny editorok) - fordítóprogramok (compilerek) / interpreterek - programkönyvtárak - rendszerhívások (a felhasználónak nyújtott operációsrendszerszolgáltatások, pl. állománykezelés, nyomtatás stb.) - szerkesztõprogramok (linker), melyek a lefordított program és a hívott (könyvtári) szubrutinok összeszerkesztésére szolgálnak - betöltõprogramok (loader) - A programok belövéséhez nyújtott támogatás: - nyomkövetõprogramok ("debuggerek") - tártartalom kijelzése ("dump") 6. Mi az operátori parancsnyelvi rendszer? Az operátori parancsnyelvi rendszer a géptermi, futásideji események vezérlésére szolgál, a géptermi személyzet munkáját segíti. Funckóival indíthat el a kezelõszemélyzet bizonyos operációs rendszer szolgáltatásokat. A mai interaktív rendszerekben használható vezérlõnyelv is az operátori parnacsnyelv egy fajtája ("batch file-ok").

6

7. Milyen DOS parancsok szolgálnak - lemez/meghajtó váltásra: floppy egység kiválasztása, pl.: A: diszk egység kiválasztása, pl.: C: - könyvtárváltásra: CD útvonalnév, illetve speciálisan, ha az aktuális könyvtárból közvetlenül "nyíló" alkönyvtárat akarunk elérni: CD könyvtárnév - könyvtár létrehozására: MD útvonalnév\könyvtárnév illetve az aktuális könyvtárból nyíló új alkönyvtár létrehozására: MD könyvtárnév - állomány listázására: TYPE állománynév oldalanként: TYPE állománynév MORE - dátum módosítására: DATE - idõpont módosítására: TIME - tartalomjegyzék kiírására: DIR - állomány másolására: az aktuális könyvtárba: COPY fájlnév (mit) máshová: COPY fájlnév (mit) könyvtárnév (hová) - állomány átnevezésére: REN régifájlnév, újfájlnév 8. Milyen szempontok szerint osztályozhatjuk az operációs rendszereket? Az osztályzási szempontok: a., felhasználók száma (egyfelhasználós, többfelhasználós) b., a multiprogramozás foka (nem multiprogramozott/multiprogramozott) c., az elérés módja (kötegelt, interaktív (idõosztásos), valós idejû)

7

d., a hardver mérete (nagygépes, kisgépes, mikrogépes) e., a rendszer struktúrája (centralizált, elosztott, hálózati) f., a felhasználás jellege (ügyviteli, adatfeldolgozó, tranzakciós és lekérdezõ rendszerek; folyamatvezérlõ; ipari és tervezõi munkaállomások; programfejlesztõi környezet; személyi számítógépes rendszerek stb.). 9. Mik a multitasking operációs rendszerek fõbb feladatai? -

az egyes taszkok jellemzõinek nyilvántartása a processzor ütemezése taszkváltás, a taszkok állapotának mentése/helyreállítása (közös) erõforrások ütemezése tárkezelés, tárkiosztás, tárvédelem a konkurencia kezelése, kölcsönös kizárás biztosítása

- a rendszer hatásfokának vezérlése 10. Mi az ütemezés? Az ütemezés a folyamatok végrehajtási sorrendjét határozza meg, azaz azt, hogy milyen sorrendben kaphatják meg a CPU-t használatra. (Ehhez hasonlóan egyéb erõforrások használati sorrendjét az erõforrások ütemezõje határozza meg.) A magas szintû ütemezõ a rendszerbe való bejutásra (háttértárolón) váró folyamatok közül választja ki a következõt, míg az alacsony szintû ütemezõ a rendszerbe már bejutott, futásra kész folyamatok közül választja ki azt, amelyik a CPU-t használhatja a következõ idõben. Nagyobb rendszerekben e két ütemezési szint között helyezkedhet el az ún. közbensõ szintû ütemezõ, a folyamatok ütemezésének optimalizálására. 11. Mi a különbség a processz és a program között? A program valamilyen algoritmus megvalósítását szolgáló utasítások sorozata, míg a processz ennek egy konkrét lefutása. Tehát - bizonyos feltételek teljesülése esetén - ugyanazt a programot több processz is végrehajthatja egyidõben.

8

12. Milyen lehetséges állapotai lehetnek egy folyamatnak a központi egység ütemezés szempontjából? Rajzolja fel a folyamat állapotdiagramját!

ÒM

$NWtY

%HIHMH]HWW

9iUDNR]y

+ROWSRQWL

13. Milyen fõbb szolgáltatásokat nyújtanak az operációs rendszerek? 1. Az operációs rendszer tevékenységi körei szerinti csoportosítás: a. vezérlõáram-kezelés b. tárkijelölés és programbetöltés c. programszerkesztés (linkelés) d. magas szintû ütemezés (feladatok fogadása) e. mûködésoptimalizálás (közbensõ ütemezés, valós idejû kezelés) f. alrendszerek kezelése 2. Az operációs csoportosítás:

rendszer

által

nyújtott

szolgáltatás

felhasználója

szerinti

a. A felhasználók kiszolgálása: - folyamatvezérlés - program betöltés, végrehajtás - folyamat létrehozás, megszüntetés, attribútumainak beállítása - központi tár igénylése, felszabadítása - folyamatok közötti kommunikáció, szinkronizáció - nyomkövetés hibakereséskor - állományok kezelése - állományok létrehozása, megszüntetése, attribútumaik beállítása - könyvtárak létrehozása, megszüntetése, törlése - állományok megnyitása, lezárása

9

- perifériák kezelése - perifériák igénylése, lefoglalása, felszabadítása - folyamat és periféria közötti átvitel biztosítása b. A rendszer mûködtetése: - rendszerinformációk kezelése - rendszerkomponensek (folyamatok, állományok, perifériák, felhasználók, rendszeróra, stb.) állapotának lekérdezése, módosítása - rendszerstatisztikák készítése - számlázás - erõforrás gazdálkodás - erõforrás kiosztás, -kezelés, -elvétel - holtpontmentesség biztosítása - kölcsönös kizárás - védelem - a rendszer védelme a felhasználóktól - a felhasználók védelme egymástól - adott folyamat egyes részei közötti védelem c. A felhasználók és a rendszer együttmûködése: - kommunikáció - kommunikációs csatornák létrehozása, megszüntetése - üzenetek, állapotinformációk küldése, fogadása - mûveletek távoli erõforrásokon 14. Mi a fõütemezõ, az alacsony szintû és a közbensõ ütemezõ és fõbb feladataik? A fõütemezõ a rendszerbe való belépés céljából várakozó munkák közül választja ki azt a következõ munkát, melyet beenged a rendszerbe. A kiválasztott munkához elkészíti a munkavezérlõ blokkot (PCB - Process Control Block vagy TSS - Task State Segment), amelyet elhelyez a munkasorba. A fõütemezõ feladata, hogy a rendszer optimális mûködését elõsegítõ munkakeveréket készítsen, azaz hogy a kiválasztott munkák CPU és I/O igénye összességében körülbelül azonos legyen. A fõütemezõ - mûködésébõl adódóan - a kötegelt feldolgozású operációs rendszerek sajátja, de az interaktív operációs rendszerekbõl sem hiányozhat a PCB-t elkészítõ funkció. Az alacsony szintû ütemezõ (másik gyakran használt neve: diszpécser) a CPUra várakozó, futásra kész folyamatok közül választja ki azt, amelyik a következõ idõben használhatja a CPU-t. Különösen idõosztásos rendszerekben követelmény,

10

hogy mûködése gyors legyen. Ezért az alacsony szintû ütemezõ csak korlátozott számú szempont figyelembe vételével határozza meg a következõ kiválasztandó folyamatot (lokális optimum). Nagyobb rendszerekben az optimalizálás figyelembe vétele vagy nagyon lelassítaná a sebességkritikus alacsony szintû ütemezõt vagy megfelelõ sebesség megtartása mellett csak nagyon kevéssé hatékony optimalizáló algoritmust használhatnánk. Ezért szokták az (alacsony szintû) ütemezõ feladatát kettéválasztani, és az optimalizálást egy harmadik, az ún. közbensõ szintû ütemezõ segítségével megvalósítani. Ez az ütemezõ globális szempontok szerinti optimalizálást tud végezni. A folyamatok futási sebességének figyelésével detektálhatja például a kiéheztetés tényét, vagy azt, hogy ha egy folyamat aránytalanul lassan fut stb. A megbomlott egyensúlyt például a folyamatok prioritásának idõleges megváltoztatásával, sõt bizonyos folyamatok ideiglenes vagy végleges felfüggesztésével állíthatja helyre. 15. Mik az alrendszerek? Milyen tipikus szolgáltatásaik vannak? Az alrendszerek egy-egy speciális alkalmazói kör igényeit elégítik ki olymódon, hogy az adott szolgáltatás igénybevétele a felhasználók szempontjából (sokkal) egyszerûbb legyen, mint a hagyományos (alrendszer nélküli) operációs rendszer felületen keresztül. Megvalósításuk általában a következõ: a hagyományos operációs rendszer szolgáltatásokat tartalmazó réteg fölé egy, a szolgáltatásokat valamilyen felhasználói kör speciális igényeit kielégítõ módon, egyszerûen meghívni képes integrált programcsomagot készítünk. Ez azonban nem univerzális, azaz csak az adott felhasználói csoport céljaira megfelelõ. Más célok vagy egy másik alrendszer vagy közvetlenül rendszerhívások segítségével valósíthatók meg. Az alrendszerek kialakításának elõnyei: - a sokszor csak bonyolult módon elérhetõ operációs rendszeri szolgáltatásokat egyszerûen elérhetõvé teszi a felhasználó számára, így a felhasználónak nem kell ismernie az operációs rendszer részleteit, munkája ezáltal hatékonyabbá válik. - (bizonyos korlátok között) új szolgáltatások, alkalmazások megvalósításakor nem kell az operációs rendszert módosítani (vagy legfeljebb csak kis mértékben). Az alrendszerek kialakításának hátrányai: - mivel az alkalmazás és az operációs rendszer közé egy újabb szint került, ezáltal sebesség, felhasznált tármennyiség stb. szempontjából hatékonyságromlás lép

11

fel (bár ha figyelembe vesszük, hogy különben az alrendszer funkcióinak nagy részét magába az alkalmazásba kellett volna integrálni, ez a veszteség általában nem túl számottevõ). Tipikus alrendszerek az univerzális operációs rendszerek esetében a programfejlesztõi alrendszerek. Ezek legfontosabb szolgáltatásai: - (nyelvspecifikus vagy mésnéven szintaxisvezérelt) editorok - fordítók és/vagy interpreterek - szerkesztõk (linker) - betöltõk (loader) - hibakeresési támogatás (debugger) stb. Egy másik, tipikus, manapság egyre növekvõ jelentõségû alrendszer az adatbázis-kezelési alrendszer. 16. Ismertesse az operációs rendszerek héjszerkezetét! Az operációs rendszerek felépítésekor - elsõsorban védelmi okokból - szükség van a hierarchikus struktúrálásra. Ez azt jelenti, hogy az operációs rendszer szolgáltatásait ún. rétegekbe szervezzük. Egy réteg rutinjai csak a közvetlenül alatta levõ réteg rutinjait használhatják, de csak egy jól meghatározott interfészen keresztül. Vagyis egy adott réteg elemi mûveleteket nyújt a felette levõ rétegnek, vagy másképpen nézve, egy felsõbb réteg bõvíti, komplexebbé teszi egy alatta lévõ réteg szolgáltatásait. Az egyes rétegek önmagukban is több funkciót tartalmazhatnak, az egyes rétegeken belüli struktúrálódásra szolgálnak a modulok, amelyek a rétegen belül egy-egy jól körülhatárolható feladat(csoport)ot valósítanak meg. E modulok szintén jól definiált interfészeken keresztül - használhatják egymás szolgáltatásait. A rétegek kialakításakor meg kell oldani az adatelrejtést is, azaz hogy egy réteg adatstruktúrája (táblázatok, változók stb.) csak a rétegen belülrõl legyen elérhetõ, alulról illetve fölülrõl ne. Egy tipikus rétegzõdést tükröz a következõ ábra: 3. szint 2. szint 1. szint 0. szint A kernel a 0. és az

Alkalmazói szint Parancsértelmezõ szint I/O szint Rendszerhívások szintje 1. szint együttese.

17. Mi a rendszermag (kernel) ?

12

A rendszermag az operációs rendszer réteg felsõbb szintjeibõl intenzíven használt közös rutinokat tartalmazza. Ez nem egy összefüggõ algoritmusú program, hanem egy olyan szubrutin- és adattáblázat-együttes, amely együttesen képes a rendszermag szolgáltatásait nyújtani. A rendszermag tipikus funkciói: - a hardverben nem létezõ, gyakran használt utasítások megvalósításai (lebegõpontos aritmetikai mûveletek stb.) - megszakításkezelés - folyamatok állapotainak vezérlése, követése - folyamatszinkronizáció - a védelmi rendszer mûködtetése - erõforrás-kezelés - ütemezések (CPU, perifériák) - eseménystatisztika, eseménykezelés - rendszerkönyvtárak, rendszertáblák kezelése - kölcsönös kizárást megvalósító algoritmusok (szemafor kezelés, P és V primitívek)

18. Mi az erõforrás-kezelés? Milyen típusú erõforrásokat ismerünk? Az erõforrás-kezelés során az operációs rendszer gondoskodik a számítógéprendszer erõforrásainak (a futó folyamatok igényei alapján történõ) elosztásáról, ezek védett használatáról, illetve az erõforrások használatáért vívott versenyhelyzetek kezelésérõl. Az erõforrás-kezelés két fontos célja: a számítógéprendszer mûködését gazdaságossá tenni valamilyen szempont szerint elkerülni a holtponthelyzetek kialakulását és/vagy detektálni és felszámolni a kialakuló holtponthelyzeteket. A rendszer erõforrásait többféle szempont szerint osztályozhatjuk: I. - hardver erõforrások; Pl.: a központi processzor, memóriák, input/output csatornák és perifériák stb.

13

Ezek az erõforrások általában a technikai fejlõdés következtében egyre gyorsabbá és olcsóbbá válnak, ezért maximális kihasználtságuk manapság egyre kevésbé fontos követelmény. - szoftver erõforrások; Pl.: a különbözõ programok, adatállományok stb. Ezek ára a hardverhez képest egyre nõ, ezért hatékony kihasználtságuk egyre inkább elõtérbe kerül. II. - a számítógéprendszerben meglévõ "hagyományos", a felhasználók igényeit kielégítõ erõforrások, pl. nyomtatók, szövegszerkesztõ programok, stb. - az operációs rendszer által létrehozott, magának a számítógéprendszernek a mûködését lehetõvé tevõ, illetve elõsegítõ erõforrások, pl. lapok a virtuális tárkezelésnél, fájl leíró táblák, stb. III. - elvehetõ erõforrások; Pl. operatív tár (tartalma a háttértárolóra menthetõ) folyamatok felfüggesztése esetén (pl. holtponthelyzet kialakulása miatt); az adott erõforrás használata a folyamat újraindításakor a felfüggesztéskori állapotából folytatódhat - nem elvehetõ erõforrások; Pl. nyomtatók. Ha egy processz ilyen erõforrást használ, célszerû megvárni, míg a használatot befejezi (ha ez lehetséges), mert újbóli vagy más általi használata esetén elõzõleg alaphelyzetbe kell hozni. 19. Mi a holtpont? Milyen feltételrendszer teljesülése esetén alakulhat ki? Milyen holtpontkezelési stratégiákat ismer? A holtpont az a jelenség, amikor a számítógéprendszerben a folyamatok egy egynél több elemû halmaza egy olyan eseményre vár (erõforrás felszabadítás), amelyet csak a halmaz valamelyik eleme válthatna ki, de erre nincs lehetõség. A holtpont kialakulásának feltételei: 1. Vannak olyan erõforrások, amelyek egyidejûleg csak egy folyamat által haszálhatók. 2. A folyamatok várakozás közben lekötve tarthatnak erõforrásokat. 3. A várakozó folyamatok által lefoglalva tartott erõforrások erõszakkal nem vehetõk el ("rablás" nincs). 4. A rendszerben ciklikus várakozás van, azaz például az elsõ folyamat olyan erõforrásra vár, amit a második folyamat foglal, a második olyanra vár, amit a harmadik foglal stb., míg az utolsó olyanra vár, amit az elsõ folyamat tart lefoglalva.

14

A holtponthelyzet kialakulása a fenti négy feltétel EGYIDEJÛ teljesülése esetén lehetséges. A holtpontkezelésnek két alapvetõ módja van. 1. A holtpont lehetõségének elkerülése, megelõzése: 1.1. Ha egy folyamat várakozik, nem köthet le erõforrást: 1.1.1. Statikus lefoglalási stratégia: egy folyamat csak akkor indulhat, ha minden szükséges erõforrást megszerzett 1.1.2. Egy folyamat csak akkor igényelhet újabb erõforrást, ha nincs lekötött erõforrása Hátrány: kiéheztetés, rossz erõforrás kihasználtság 1.2. Ha egy várakozó folyamatnak nem elégíthetõ ki az erõforrás igénye: 1.2.1. Az összes eddig lekötött erõforrását fel kell szabadítania 1.2.2. Más, várakozó folyamattól "elrabolhatja" a szükséges erõforrást. A két módszer hátránya: nem mûködik nem elvehetõ erõforrások esetében (pl. nyomtató). 1.3. A ciklikus várakozás kizárása: 1.3.1. Minden erõforráshoz egy (a többitõl különbözõ) sorszámot rendelünk, és a folyamatok az erõforrásokat csak azok sorszámai szerint növekvõ sorrendjében igényelhetik, vagy másképen megfogalmazva, ha egy folyamat egy bizonyos sorszámú erõforrást igényel, elõtte fel kell szabadítania az összes általa lefoglalt, az igényeltnél nagyobb sorszámú erõforrást. Hátrány: csökken a rendszer áteresztõképessége 1.3.2. Az operációs rendszer csak akkor engedi meg új erõforrások lefoglalását, ha ennek teljesítése után a rendszer ún. biztonságos állapotban marad, azaz olyan állapotban, hogy az igények valamilyen sorrendben ki legyenek elégíthetõk. Hátrány: olyan pluszinformáció szükséges (hogy egy folyamat egy erõforrásból maximálisan hányat igényel), mely sokszor nem tudható elõre, illetve az algoritmus bonyolultsága. 2. A már kialakult holtponthelyzet felismerése és megszüntetése (esetleg speciális, holtpontfelismerõ és holtpontból való felélesztést szolgáló alrendszerek használatával): 2.1. Holtpontfelismerés - folyamatos adatgyûjtés az erõforrások szétosztásáról és a ki nem elégített igényekrõl

15

- a holtponti helyzetet ezen adatokból detektálni képes algoritmus ismételt futtatása Hátrány: bonyolult, sok idõt felemésztõ algoritmusok 2.2. Holtpontból való felélesztés 2.2.1. A holtponti helyzetben lévõ folyamatokat - vagy azok egy megfelelõ részét - felszámoljuk Hátrány: az elvégzett munka (egy része) kárbaveszik, nagy károkozást jelenthet. 2.2.2. A holtponti helyzetben lévõ folyamatok (egy részétõl) erõforrásokat rabolunk Hátrány: az elvégzett munka egy része kárbaveszik el nem vehetõ erõforrások elrablása esetén, illetve ezeket az erõforrásokat más folyamatnak való átadás elõtt alaphelyzetbe kell hozni. 20. Mi a rendszer biztonságos illetve nem biztonságos állapota? Egy rendszer (holtpont kialakulás lehetõségének a szempontjából) biztonságos, ha minden folyamat erõforrás igényét ki lehet elégíteni valamilyen sorrendben, a ciklikus várakozás veszélye nélkül. Ha ez nem lehetséges, akkor a rendszer nem biztonságos állapotban van. Ez azt jelenti, hogy ilyenkor holtponti helyzet kialakulHAT. 21. Milyen fontosabb processzorütemezési stratégiákat ismer? Jellemezze röviden mûködésüket! Milyen elõnyös illetve hátrányos oldalai vannak az egyes módszereknek? 1. Elõbb jött - elõbb fut (First Come First Served - FCFS) A folyamatok érkezési sorrendjükben kapják meg a processzort. Elõny: egyszerû megvalósítás (egy FIFO sor) Hátrány: - a folyamatok átlagos várakozási ideje nagymértékben függ a folyamatok érkezési sorrendjétõl. Egy hosszú folyamat sokáig várakoztatja az összes utána érkezõ folyamatot (lassú kamion effektus), ezáltal az átlagos várakozási idõ nagyon nagy lehet. - csorda hatás: nagy CPU igényû folyamat sokáig használja a CPU-t, az összes többi várakozik, az I/O sorok/processzorok kihasználatlanok.

16

2. A legrövidebb elõnyben (Shortest Job First - SJF) A CPU-t egy folyamat befejezõdése után a legrövidebb CPU igényû várakozó folyamatnak adjuk oda (ha több ilyen van, azok közül az FCFS technikával választunk). Elõny: a legjobb az átlagos várakozási idõ szempontjából Hátrány: - KIÉHEZTETÉS! - tudni kell a CPU igény nagyságát (ez nem mindig mondható meg elõre): - kötegelt rendszereknél (ált. itt használják) programozói becslés - idõosztásos rendszereknél matematikai statisztikai becslés 3. Prioritásos módszerek Minden folyamathoz egy prioritási értéket rendelünk, és a CPU-t a legmagasabb prioritású folyamat kapja meg (ha több ilyen van, FCFS szerint választunk). A prioritás lehet külsõ (pl. a folyamat fontosságától függõ) illetve belsõ (az operációs rendszer által meghatározott pl. az erõforrás igény alapján). Elõny: a prioritásokkal sokféle szempont érvényesíthetõ Hátrány: KIÉHEZTETÉS! A kiéheztetés megszüntetése: - "öregedés" (a folyamatok prioritását adott idõ eltelte után növeljük vagy csökkentjük - fõleg belsõ prioritású rendszerekben használt megoldás) - biztosítjuk, hogy adott (nagy) idõközönként az alacsony prioritású folyamatok is használhassák egy (kis) idõre a CPU-t, még akkor is, ha vannak várakozó magas prioritású folyamatok is (fõleg külsõ prioritású rendszerekben használt megoldás). 4. Körben járás (Round Robin - RR) A folyamatokat egy zárt körbe szervezzük, és minden egyes folyamat egy elõre rögzített maximális idõre (idõszelet - time slice) megkapja a processzort, majd vesszük a kör következõ folyamatát. Az interaktív rendszerek tipikusan ezt az ütemezési stratégiát használják. Kombinálható prioritások bevezetésével is, ilyenkor minden prioritási szintnek "saját köre" van. Elõny: egyszerû algoritmus; nincs kiéheztetés Hátrány: a folyamatok megszakításakor állapotukat el kell menteni (környezetváltás - context switching). Ez jelentõs idõt vesz igénybe és jelentõs plusz erõforrásokat igényel.

17

A 2. és 3. pont alatt felsorolt algoritmusok mindegyikének megvan a preemptív (kizárásos) és nem preemptív formája. A preemptív forma annyiban különbözik az ismertetett nem preemptív formáktól, hogy ha egy rövidebb (SJF esetén) illetve magasabb prioritású (prioritásos algoritmus esetén) folyamat érkezik, akkor az MEGSZAKÍTJA a futó folyamatot. A preempció elõnye: kisebb átlagos várakozást biztosít illetve a fontosabb folyamatokat jobban preferálja. Hátránya: megszakításkor környezetváltásra van szükség. 22. Egy rendszer az alábbi erõforrásokkal gazdálkodik: E1: 240 példány E2: 36 példány E3: 8 példány A rendszerben levõ processzek: P1, P2, P3, P4. Biztonságos-e holtpontmentesség szempontjából a következõ állapot?

P1 P2 P3 P4

E1 53 0 46 127

Foglal E2 E3 14 4 5 1 17 0 0 1

Maximális igény E1 E2 E3 67 15 5 13 5 3 107 27 5 132 25 4

A maximális igényt leíró mátrixból kivonva a pillanatnyilag lefoglalt erõforrások mátrixát kapjuk meg a folyamatok által igényelt erõforrások mátrixát, azaz:

P1 P2 P3 P4

E1 14 13 61 5

Igény E2 1 0 10 25

E3 1 2 5 3

A pillanatnyilag lefoglalt erõforrásokat tartalmazó mátrix oszlopait összeadva és az eredményt az összerõforrás-számból kivonva megkapjuk a pillanatnyilag szabad erõforrások számát:

18

E1=240-(53+0+46+127)=240-226=14 E2=36-(14+5+17+0)=36-36=0 E3=8-(4+1+0+1)=8-6=2 Ebbõl látszik, hogy a szabad erõforrásokból (14,0,2) kielégíthetjük P2 (13,0,2) igényét. P2 lefutása után felszabadítja az általa lefoglalt erõforrásokat (0,5,1) is. Ezt hozzáadva az eredetileg szabad erõforrások számához (14,0,2), kapjuk a szabad erõforrások új számát: (14,5,3). Ebbõl kielégíthetõ P1 igénye, amely lefutása után a szabad erõforrások új száma (14,5,3)+(53,14,4)=(67,19,7) lesz. Ebbõl kielégíthetõ P3 igénye, amely lefutása után a szabad erõforrások új száma (67,19,7)+(46,17,0)=(113,36,7) lesz, amelybõl kielégíthetõ P4 igénye. Vagyis a folyamatok erõforrás igénye P2, P1, P3, P4 sorrendben kielégíthetõ, tehát a rendszer holtpontmentesség szempontjából BIZTONSÁGOS. 23. Határozza meg az alábbi terhelés esetén az átlagos várakozási idõ értékét a következõ CPU ütemezési algoritmusok mellett: a. FCFS (elõbb jött - elõbb fut) b. SJF (legrövidebb elõször) c. Round-Robin (idõszelet 10 egység) processz érkezési idõ (futásra kész sorba) P1 0 P2 8 P3 12 P4 20

CPU igény 15 7 26 10

a. FCFS: Ennél a módszernél a folyamatok érkezési sorrendben kapják meg a processzor használati jogát. A várakozási idõ értelemszerûen a kezdési idõpont és az érkezési idõpont különbsége.

19

proc. P1 P2 P3 P4

érkezési idõ 0 8 12 20

CPU igény 15 7 26 10

kezdési befejezési idõpont 0 15 15 22 22 48 48 58

várakozási idõ (kezd. - érk.) 0 7 10 28 ---45

Átlagos várakozási idõ: 45/4=11,25 b. SJF: Ennél a módszernél meg kell vizsgálni, hogy egy folyamat befejezésekor a várakozó folyamatok közül melyik a legrövidebb, és az kapja meg a processzor használati jogát. Tehát itt az érkezési és a végrehajtási sorrend különbözõ lehet! proc. P1 P2 P3 P4

érk. idõ 0 8 12 20

CPU igény 15 7 26 10

kezd. befej. idõpont 0 15 15 22 32 58 22 32

vár. idõ 0 7 20 2

befejezéskor váró proc-k P2(7), P3(26)P2 P3(26), P4(10) P3(26) P3

következõ legrövidebb P4 -

---29 Átlagos várakozási idõ: 29/4=7,25 c. Round Robin: Ennél a módszernél egy folyamatot az idõszelet letelte után felfüggesztünk és a várakozási sor végére rakjuk be. A táblázatban csillaggal jelöltük meg a korábban felfüggesztett folyamatok ismételt futását és ilyenkor az érkezési idõpont oszlopában zárójelben a felfüggesztés idejét adtuk meg.

20

proc. P1 P2 P1* P3 P4 P3* P3*

érk. idõ 0 8 (10) 12 20 (42) (52)

CPU igény 15 7 5 26 10 16 6

kezd. befej. idõpont 0 10 10 17 17 22 22 32 32 42 42 52 52 58

maradék igény 5 0 0 16 0 6 0

vár. idõ 0 2 7 10 12 10 0

befejezéskor a váró proc-k sorrendje P2, P1 P1, P3 P3, P4 P4, P3 P3 P3 -

---41 Átlagos várakozási idõ: 41/4=10,25 (Megjegyzés: az átlagos várakozási idõ mindig a folyamatok összes várakozási ideje osztva a folyamatok darabszámával.)

24. Mi a virtuális tárkezelés? A felhasználó által kiadott memória címek egy háttértáron (virtuális tárban) levõ címeknek felelnek meg, és e címtartománynak csak bizonyos részei találhatóak meg az operatív memóriában. A módszer elõnyei: - a multiprogramozott rendszerekben ha a folyamatoknak csak egy-egy részét tároljuk az operatív memóriában, akkor több folyamatot futtathatunk párhuzamosan. - ma már a (mikro)processzorok címtartománya (is) olyan nagy, hogy ekkora operatív memóriát nem tudunk (nem akarunk) kiépíteni. A virtuális tárkezeléssel elérhetõ, hogy viszonylag kis méretû operatív tároló használata esetén is a felhasználó úgy lássa, mintha egy teljes címtartomány méretû operatív tárat használna. A virtuális tárkezelés leggyakrabban használt formája a lapszervezésû virtuális tár. Ilyenkor a virtuális tárat és az operatív tárat is felosztjuk egyforma méretû egységekre, lapokra, és az operatív memóriában egy laptáblát hozunk létre. Ez a laptábla tartalmazza majd azt, hogy az adott lap az operatív tárban van-e vagy sem, illetve, hogy ha bent van, akkor mi a lap kezdõcíme az operatív tárban (valamint egyéb vezérlõ biteket.) A processzor által kiadott logikai (virtuális) címet logikailag két részre osztjuk, a felsõ rész kiválaszt egy bejegyzést a laptáblából, itt megtaláljuk a lap operatív tárbeli kezdõcímét és ehhez adjuk hozzá a cím második

21

felét, az úgynevezett (lapon belüli) eltolást. Ez az összeg jelenti a keresett memóriahely címét az operatív tárolóban. A címszámítás gyorsítására az utoljára használt néhány lap címét tartalmazó asszociatív tárat szoktak használni.

LOGIKAI CÍM Lapszám Lapon belüli eltolás OPERATÍV MEMÓRIA LAPTÁBLA Kezdõcím

Vezérlés

+

FIZIKAI CÍM

25. Mi a laphiba? Virtuális tárkezelés használata esetén elõfordulhat, hogy a processzor által kiadott címet tartalmazó lap nincs bent az operatív memóriában. Ezt hívjuk laphibának. Kezelése: 1., Ellenõrizzük, hogy a kiadott címet az adott folyamat használhatja-e. 2., A kérdéses lapot be kell olvasni az operatív tárolóba (természetesen ez azzal járhat, hogy elõtte egy bent lévõ lapot ki kell vinnünk a háttertárba), majd módosítani kell laptáblát. 3., Meg kell ismételni annak az utasítsának a végrehajtását, amelynél a laphiba fellépett.

22

26. Milyen lapozási stratégiákat ismer? Ismertesse röviden õket! Milyen elõnyös és hátrányos tulajdonságaik vannak? a, FIFO (elõbb be - elõbb ki) A behozott lapok számait egy FIFO tárban tároljuk. Laphiba esetén a FIFO sor elején álló (azaz a legrégebben behozott) lapot visszük ki, és az újonnan behozott lap sorszámát a FIFO sor végére írjuk. Elõny: - egyszerû Hátrány: - sok laphibát generál, hiszen elképzelhetõ, hogy egy lapot már régen behoztunk, de még mindig használjuk. Ez tipikusan igaz a magát az operációs rendszert tartalmazó lapokra, amelyeket az algoritmus állandóan "kilapoz". b, OPT (optimális) Az új lapot mindig annak a lapnak a helyére hozzuk be, amelyre a legkésõbb fogunk (újra)hivatkozni. Elõny: - ez adja a minimális laphibaszámot Hátrány: - a gyakorlatban megvalósíthatatlan, mivel nem lehet elõre tudni a lapokra való hivatkozások sorrendjét. Ezért csak az egyéb statégiák jóságának vizsgálatához referenciaként használják. c., LRU (legrégebben használt) Az új lapot mindig annak a helyére hozzuk be, amelyre a legrégebben hivatkoztunk (amelyet a legrégebben használtunk). Az algoritmus alapja a lokalitási elv megfordítása, azaz ha egy lapot már régóta nem használunk, akkor nagy valószínûséggel nem lesz rá szükség a késõbbiekben sem. Elõny: - viszonylag jól közelíti az optimális módszert Hátrány: - kiegészítõ hardvert igényel és lassú d., Second chance (második esély) Ennél a stratégiánál minden lapon van egy hivatkozás bit is, amelyet 1-be állítunk minden alkalommal, ha a lapra hivatkozunk. (Figyelem: ez igény szerinti lapozásnál azt jelenti, hogy amikor behozzuk a lapot, ezt a bitet rögtön 1-be állítjuk, hiszen azért hozzuk be a lapot, mert hivatkozunk rá!) Lapcsere esetén azt a lapot kell kicserélnünk, amelyik a legrégebben van bent (FIFO), de ha a FIFO módszerrel meghatározott lap hivatkozás bitje=1, akkor a lapot 0 értékû hivatkozás bittel betesszük a FIFO végére. (Azaz csak 0 hivatkozás bitû lapot cserélhetünk le.)

23

27. Miért van szükség tárvédelemre? Tárvédelemre elsõsorban a következõ okok miatt van szükség: a., Az operációs rendszer védelme a felhasználói programoktól (illetve az operjcáiós rendszer rétegeinek védelme egymástól). Megoldás: prioritási szintek bevezetése, az adott területet csak egy legalább adott prioritási szinttel rendelkezõ folyamat használhatja. b., A folyamaton belüli logikai egységek védelme. Megoldás: szegmentálás; kódstack- és adatszegmensek definiálása. Minden egyes utasítás végrehajtásakor (hardver úton) ellenõrizzük, hogy az utasítás operandusa tényleg az adott utasításnak megfelelõ típusú szegmensen belül található-e meg. c., A folyamatok védelme egymástól. Megoldás: szegmentálás. Minden egyes folyamat saját szegmensleíró táblával rendelkezik és csak azokat a szegmeseket érheti el, amelyek szerepelnek a táblájában. A fentieken túlmenõen szükség van arra is, hogy kijelöljük, hogy egy folyamat az általa elért tárterületeket hogyan használhatja (csak olvasható vagy írhatóolvasható; csak futtatható vagy futtatható-olvasható, stb.). 28. Hogyan vesz részt a szegmentálás a védelemben? 1.,

A folyamat különbözõ logikai egységeit védi egymástól. Például definiálhatunk egy-egy kód- illetve stackszegmenst valamint egy vagy több adatszegmenst. Amikor egy-egy utasítást végrehajtunk, ellenõrizzük, hogy az az utasítás az adott típusú szegmensben dolgozik-e (pl. ugrás-kódszegmens, mûveletvégzésadatszegmens, PUSH/POP-stackszegmens), illetve, hogy az utasításban lévõ cím ténylegesen benne van-e a szegmens kezdete és hossza által meghatározott memóriaterületen. Így elkerülhetõk azok a tipikus programhibák, mint például, hogy a stack túlcsordul és felülírja a progamot, egy rossz ugrási cím miatt adatokat értelmezünk utasításnak, vagy fordítva: rossz operanduscím esetén felülírunk utasításokat.

2.,

A folyamatok memóriaterületeinek más folyamatoktól való védelme (megteremtve viszont az esetleges közös adatterületek kialakításának lehetõségét). Minden egyes folyamat saját szegmensleíró táblával rendelkezik, amely csak azon szegmensek címeit tartalamzza, amelyeket az adott folyamat használhat. A folyamat csak olyan címeket adhat ki, melyek ezeken a szegmenseken belül vannak, és ezt ellenõrizzük. Így nincs mód arra, hogy egy

24

folyamat véletlenül vagy szándékosan más folyamat számára fenntartott helyre írjon. Viszont sokszor szükség van arra, hogy több folyamat együttmûködhessen. Ez a lehetõség úgy teremthetõ meg, hogy bizonyos (a közös területeket tartalmazó) szegmenseket az együttmûködni kívánó összes folyamat szegmenstáblájába felvesszük. 29. Mi a vergõdés és megelõzési módja? A vergõdés mutiprogramozott számítógéprendszerek esetén az a jelenség, amikor egy folyamat több idõt tölt lapozással, mint saját "hasznos" tevékenységével. A jelenség oka az, hogy a folyamat a szükségesnél kevesebb lapkerettel rendelkezik az operatív memóriában. A vergõdés megelõzési módjai: a.,

b.,

c.,

lokális lapkiosztási algoritmus használata: Ez azt jelenti, hogy minden folyamat rögzített darabszámú kerettel gazdálkodhat (nem tud más folyamatoktól lapokat elvenni). Ezáltal, ha egy folyamat vergõdés állapotába kerül, attól a többi még (viszonylag) zavartalanul lefuthat. munkahalmaz vagy kritikus halmaz: A munkahalmaz kialakíthatósága a lokalitás elvén alapul, azaz ha egy folyamat egy adott címtartományt (azaz lapkészletet) használ, akkor nagy valószínûséggel a következõkben is ezt fogja használni. Ez a munkahalmaz viszonylag lassan változik (akár maguk a lapok, akár a munkahalmazt alkotó lapok darabszáma). Az operációs rendszer olyan lapozási stratégiát követ, hogy minden egyes folyamatnak igyekszik állandóan benntartani a munkahalmazát. Hátránya: bonyolult szoftvert és hardvert igényel. laphiba gyakoriság figyelése: Figyeljük, hogy egy folyamatban idõegységenként hány laphiba lépett fel. Ha ez az érték meghalad egy elõre rögzített maximumot, akkor a folyamatnak a szükségesnél kevesebb kerete van. Ha lehetséges, adunk neki még egyet, ha nem, felfüggesztjük a folyamatot átmenetileg. Viszont, ha egy elõre rögzített minimumnál kisebb a laphibák száma, a folyamatnak túl sok kerete van, ezért ilyenkor elveszünk tõle egyet.

25

30. Hogyan találunk meg egy adatblokkot lemezen? A mágneses háttértárak szervezési elve általában a következõ: A lemezeket koncentrikus körökre (sáv vagy pálya - track) osztjuk. Merevlemezes egységeknél, ahol általában több lemez helyezkedik el egymás alatt, az egymás alatti sávok összességét cilindernek hívjuk. Más esetekben lehetséges, hogy a lemez mindkét oldalára írunk. A sávok további egységekre, az úgynevezett szektorokra vannak osztva. A 0. szektor helyzetét egy referencia- vagy más néven indexlyuk jelzi. Az egyes szektorok között üres helyek (gap) találhatók. Minden pálya illeve szektor elején egy azonosító bitsorozat áll, amelyet a formattálás során a formattáló program ír fel. Az adatblokkok az egyes szektorokban helyezkednek el. Az adatblokkok méretétõl függõen lehetséges, hogy egy adatblokk = egy szektor, egy adatblokk < egy szektor illetve egy adatblokk > egy szektor. Az, hogy az egyes állományokhoz tartozó adatterületek hogyan helyezkednek el a lemezen, nagymértékben függ az alkalmazott háttértér kiosztási stratégiától (lásd 32. kérdés). 31. Milyen katalógusszerkezeteket (könyvtárszerkezeteket) ismer? a.,

b.,

c.,

kétszintû katalógus Minden felhasználónak saját katalógusa van (ezek neveit tartalmazza a felsõ szintû katalógus). E saját katalógusokban helyezhetik el a felhasználók saját állományaikat. Ezen kívül van egy "rendszerkatalógus", ahol a közös használatú állományok találhatók meg. Értékelés: túlságosan egyszerû, merev fa struktúrájú katalógus Az a., módszer továbbfejlesztése. A felsõ szintû ("gyökér") katalógusban állományok mellett újabb katalógusok találhatók, majd ezekben a katalógusokban szintén állományok és újabb katalógusok vannak és így tovább. Értékelés: elég flexibilis, gyakran használt megoldás. ciklusmentes gráf A b., módszer továbbfejlesztése. Ha egy állomány több katalógusban is szerepel, a több másolatonak az egyes katalógusokban külön-külön való tárolása helyett az adott állományból csak egy példányt tárolunk és a megfelelõ katalógusokban speciális bejegyésekkel, az ún. kapcsolatokkal (linkekkel) mutatunk e közös példányra.

26

Értékelés: nagyon flexibilis, többfelhasználós rendszerekben közös adatterületek kialakítását kifejezetten támogatja, helytakarékos, bár a vezérlése bonyolultabb. 32. Milyen háttértér-kiosztási stratégiákat ismer? Ismertesse röviden õket! Milyen elõnyös és hátrányos tulajdonságaik vannak? a.,

b.,

c.,

folytonos Minden állomány egymás után álló blokkok sorozatát foglalja el a lemezen. A katalógusba a blokk kezdõcímét és az elfoglalt blokkok számát kell felvenni. Elõny: szekvenciális és véletlen elérésû állományokhoz is jó Hátrány:- bonyolult algoritmusok a megfelelõ méretû szabad terület megkeresére (elsõ illeszkedõ - first fit; legjobban illeszkedõ - best fit; legnagyobb hely - largest hole). - külsõ elaprozódás lép fel (a szabad terület egy idõ után sok haszálhatatlan kis részre esik szét). Kezelése: idõnkénti tömörítés - lassú! - probléma az állományok bõvítése: - át kell másolni - lassú - nagyobb helyet foglalunk le, mint ami szükséges, de egyrészt nem biztos, hogy késõbb tényleg bõvítjük az állományt, ekkor ez felesleges helypazarlás, illetve másrészt nincs arra garancia, hogy bõvítéskor a lefoglalt nagyobb hely tényleg elég nagy-e. láncolt Minden állomány blokkok láncolt listája, azaz minden blokk végén van egy pointer, mely a következõ blokkra mutat. A katalógus az elsõ és az utolsó blokk címét tartalmazza. Elõny: - a szabad helyek aprózódása nem jelentkezik - nem probléma az állomány bõvítése Hátrány: - csak szekvenciális állományokra jó - sebezhetõ; ha egy pointer elveszik, elvész az állomány egész hátralévõ része, hiszen ahhoz, hogy egy adott blokkot megtaláljunk, az elsõ blokktól kiindulva végig kell tudni menni a keresett blokkig a pointerek segítségével. indexelt A b., verzió módosítása oly módon, hogy a pointereket egy külön indextáblában tároljuk. Az indexblokk i. eleme az állomány i. blokkjára mutat. Elõny: - nem csak szekvenciális állományokra jó - ez a legflexibilisebb megoldás

27

Hátrány: - az indexblokkok kezelése: - nem biztos, hogy az indexblokk belefér egy blokkba (hosszú állományok esetén), ilyenkor a megoldás az indexblokkok láncolt listája - ha a fizikai blokkméret sokkal nagyobb, mint az indexek elhelyezéshez szükséges terület - belsõ elaprózódás lép fel (kis méretû állományoknál). 33. Ismertessen legalább három lemezes háttértár ütemezési stratégiát! Melyik ezek közül a legoptimálisabb? FCFS (elõbb jött - elõbb szolgálják ki) A kérelmek egy FIFO sorba kerülnek, és mindig a FIFO elejérõl vesszük a következõ kiszolgálandót. - A legrosszabb hatásfokú a fejmozgás szempontjából. SSTF (a legközelebbi elõnyben) Mindig azt az igényt elégítjük ki, amelyhez a fej éppen a legközelebb van. - A kiéheztetés veszélye miatt (a fej jelenlegi állásától "messze" lehet, hogy soha sem jut el) használhatatlan. SCAN (pásztázó) A fej a két végállása között folyamatosan ingázik és kielégíti az éppen aktuális pályára vonatkozó azon igényeket, amelyek a pásztázás kezdetekor már fennálltak. (Azaz a kiszolgálás közben érkezõ új igényeket csak a következõ "körben" szolgálja ki, így kerüli el a kiéheztetést.) - Jó algoritmus, de a lemez szélein lévõ állományokat ritkábban szolgálja ki. N-SCAN (N lépéses pásztázó) Egy irányba mozogva csak maximum N darab igényt elégítünk ki minden pályán. - Az átlagos várakozási idõ körülbelül ugyanaz mint a SCAN-é, de a szórása kisebb. C(ircular)-SCAN (Egyirányú pásztázó) A kérések kiszolgálása mindig csak az egyik irányú fejmozgásnál történik. Elkerüli még a szélsõ pályák háttérbe szorítását is. 34. Mit nevezünk konkurens folyamatoknak? Konkurens folyamatoknak az egymással (elvileg) párhuzamosan futtatható folyamatokat nevezzük. A konkurens folyamatokat egymásrahatásuk szempontjából a következõképpen osztályozhatjuk. - Független folyamatok: sem közös erõforrás, sem adatcsere nem kapcsolja õket össze, nincs semmi közük egymáshoz. Csak multiprocesszoros rendszerekben

28

fordulhatnak elõ. (Egyprocesszoros rendszerben, ha más nem is, de a CPU mindig közös erõforrás, melyért a folyamatok versenyeznek.) - Aszinkron folyamatok: esetenkénti szinkronizáció, kooperáció, illetve közös erõforrásért való versengés fennáll köztük: - erõforrásokért versengõ (de egyébként egymástól független) folyamatok - kooperáló folyamatok (kooperáció és versengés együttesen jellemzi õket). 35. Mi a precedenciagráf, a fork/join illetve a parbein/parend utasításpár? A konkurens folyamatokban is lehetnek olyan utasítások (vagy utasításcsoportok), melyek végrehajtása meg kell, hogy elõzze más utasítások (vagy utasításcsoportok) végrehajtását. A lehetséges párhuzamosítások, illetve sorrendi kötöttségek szemléletes ábrázolására szolgál a prcedenciagráf, mely egy irányított, ciklusmentes gráf. A gráf csomópontjai utasítások, míg, ha egy csomópontból él vezet egy másik csomópontba, akkor ez jelenti azt, hogy az elsõ csomópont utaításának végrehajtása meg kell, hogy elõzze a második csomópontét. Ha egy csomópontból egynél több él indul ki, akkor ez jelenti azt, hogy az élek mentén lévõ csomópontok utasításai párhuzamosíthatók. Míg, ha egy csomópontba egynél több él fut be, akkor ez azt jelenti, hogy az - eddig - párhuzamosan futó tevékenységeket szinkronizálni kell, azaz a csomópontban szereplõ utaítást csak azután lehet végrehajtani, ha minden bevezetõ ág tevékenysége végetért. A precedenciagráfok szemléletesek, de közvetlenül programozásra nem használhatók fel. Megoldás: a., fork/join utasítások bevezetése - a "fork címke" utasítás: a végrehajtás két párhuzamos ágra szakad, az egyik ág következõ utasítása a fork utasítást követõ utasítás, míg a másik ágé a címkénél található. - a "join számláló" utasítás: a számláló által mutatott darabszámú ág egyesítése. Mûködése: minden ág befejzõdése eggyel csökkenti a számláló értékét, és a join után következõ utasítás végrehajtása csak akkor kezdõdhet el, ha a számláló eléri a nulla értéket (minden ág befejezõdik). A fork/join utasításokkal tetszés szerinti precedenciagráf leírható, de a program strukturálatlan, a címkék és a goto utasítások miatt áttekinthetlen lesz.

29

b., parbegin/parend utasítások bevezetése A parbegin/parend utasítások között egymással párhuzamosan végrehajtható utasításokat sorolhatunk fel. A parbegin/parend utasításokkal készült program strukturált, áttekinthetõ, goto utasítás mentes lesz, de csak önmagukban ezekkel az utasításokkal nem írható le minden precedenciagráf. Megoldás: alkalmasan megválasztott szemaforok és az õket kezelõ P (letiltás) és V (engedélyezés) primitívek bevezetése. Ezen kiegészítésekkel minden precedenciagráf kezelhetõ és az elkészült program áttekinthetõ, goto mentes lesz. 36. Mi a kritikus szekció, a szemafor és a P illetve V primitív? A párhuzamosan végrehajtható folyamatokban is lehetnek olyan részek, melyek párhuzamos végrehajtása hibát okozhat. Ezeket a részeket nevezzük kritikus szekcióknak. Biztosítani kell, hogy a kritikus szekcióhoz tartozó utasítások oszthatatlanul (azaz más folyamatok által meg nem szakítható módon) hajtódjanak végre. Megoldás: rendeljünk minden kritikus szekcióhoz egy, a kritikus szekcióba való belépést engedélyezõ jelzõt, egy ún. szemafort. Egy folyamat csak akkor léphet be az adott kritikus szekcióba, ha a hozzá tartozó szemfort szabadnak találja. A szemafor állítására szolgáló két oszthatatlan mûvelet a P és V primitív. A P primitív lefoglalja (azaz tilosra állítja), míg a V primitív felszabadítja (azaz szabadra állítja) a szemafort. 37. Ismertesse a P és V primitívek mûködését egy termelõ/fogyasztó probléma megoldására! A termelõ/fogyasztó probléma: két folyamat egy közös memóriaterületen (postaláda) kommunikál egymással. A termelõ üzenetet (levelet) tesz be a postaládába, míg a fogyaszó azt kiveszi onnan. A feladat megoldásához 3 szemafor szükséges: 1., SEMA:

2., TELE:

a kölcsönös kizárást valósítja meg, tehát, hogy amíg az egyik folyamat használja a postaládát, a másik folyamatnak várakoznia kell. A SEMA szemafor két értéket vehet fel: SZABAD = 1, FOGLALT = 0; Kezdeti értéke SZABAD. a postaládában lévõ tele borítékok (azaz üzenetek) számát határozza meg. Értéke 0 és a postaláda kapacitását meghatározó

30

MAX érték között változhat. Kezdeti értéke: 0. Ha a TELE = 0. ez jelzi a fogyasztó folyamatnak, hogy nincs levél (üzenet) a postaládában. 3., ÜRES: a postaládában levõ üres helyek száma. Értéke 0 és MAX között változhat. Kezdeti értéke: MAX. Ha ÜRES = 0, ez jelzi a termelõ folyamatnak, hogy a postaláda tele van, tehát újabb üzenet oda nem tehetõ be. A megoldáshoz a P és V primitívek azon megvalósítása használható, melyben P (a lefoglaló primitív) eggyel csökkenti, míg a V (a felszabadító primitív) eggyel növeli a szemafor értékét.

SEMA termelõ folyamat

postaláda TELE

fogyasztó folyamat

ÜRES

A termelõ folyamat programja: P (ÜRES)

- egy üres hely lefoglalása, az üres helyek számának eggyel való csökkentése P (SEMA) - a postaláda használati jogának megszerzése, a postaláda lefoglalása a levél beírása a postaládába V (SEMA) - a postaláda felszabadítása V (TELE) - a tele borítékok számának eggyel való növelése

31

A fogyasztó folyamat programja: P (TELE)

- egy tele boríték lefoglalása, a tele borítékok számának csökkentése P (SEMA) - a postaláda használati jogának megszerzése, a postaláda lefoglalása egy levél kiolvasása a postaládából V (SEMA) - a postaláda felszabadítása V (ÜRES) - az üres helyek számának eggyel való növelése 38. Milyen operációsrendszer-támogatást nyújt az Intel 80386-os processzor? A legfontosabbak operációsrendszer-támogatási formák: - a strukturált tárkezelés támogatása:

-

-

-

-

- virtuális tárkezelés támogatása - kétszintû laptáblán alapuló címzés - címszámítást gyorsító egység (TLB) szegmentálás: - lokális, globális és interrupt szegmensleíró táblák támogatása - címszámítást gyorsító szegmensregiszterek a védelem támogatása: - prioritások (4 szintû) - a hardver bizonyos regiszterei illetve utasításai csak bizonyos prioritási szintû folyamatok számára elérhetõek (rendszerregiszterek ill. privilegizált utasítások). - tárvédelmi jogosultságok - szegmentálás az idõosztásos multiprogramozás támogatása: - környezetváltás hardver támogatása (a környezetválás EGY assembly utasítás) - a task állapot szegmens (TSS; kb. azonos a máshol használt PCB-vel) adattípus assembly szintû bevezetése a megszakítások, rendszerhívások támogatása: - különféle típusú megszakítás lehetõsége (hardver, szoftver, kivételes állapot) - interrupt vektortábla, néhány fontos interrupt definiálása - különbözõ típusú megszakításkezelõ eljárások

32

- a megszakításkezelõ eljárás ellenõrzött hívása, paraméter átadása, prioritási szint idõleges módosítása (kapuk - gate) - a programfejlesztõ alrendszer támogatása: - nyomkövetõ programok ("debuggerek") hardver támogatása - töréspont elhelyezési támogatás - lépésenkénti programvégrehajtás 39. Igény szerinti lapozásnál a lapokra az alábbi sorrendben hivatkoznak: 76546732676512567652 Határozza meg a laphibák számát a. a FIFO b. az optimális (OPT) c. az LRU d. a second chance (második esély) lapváltási stratégiák mellett, ha a memóriában 4 lapnyi hely van (4 frame)! Írja le a laphibák meghatározásának menetét is! a. A FIFO stratégiánál azt a lapot kell lecserélni, amelyiket a legrégebben hoztuk be. 7 6 7 7 - 6 - - A laphibák

5 4 6 7 3 2 6 7 6 5 1 2 5 6 7 6 5 2 7 7 3 3 3 3 5 5 5 5 7 7 6 6 6 2 2 2 2 1 1 1 1 5 5 5 5 5 6 6 6 6 2 2 2 2 - 4 4 4 4 7 7 7 7 6 6 6 száma: 4+10.

b. Az OPT stratégiánál azt a lapot kell lecserélni, amelyik a legkésõbb kell majd. 7 6 7 7 - 6 - - A laphibák

5 4 6 7 3 2 6 7 6 5 1 2 5 6 7 6 5 2 7 7 7 7 1 7 6 6 6 6 6 6 5 5 5 5 5 5 - 4 3 2 2 2 száma: 4+4.

33

c. Az LRU stratégiánál azt a lapot kell lecserélni, amelyiket a legrégebben használtuk. 7 6 7 7 - 6 - - A laphibák

5 4 6 7 3 7 7 7 6 6 6 5 5 3 - 4 4 száma:4+6.

2 6 7 6 5 1 2 5 6 7 6 5 2 7 7 7 2 2 6 6 6 6 6 3 5 5 5 5 2 2 1 1 7

d. A második esély stratégiánál minden lapon van egy hivatkozás bit is, amelyet 1-be állítunk minden alkalommal, ha a lapra hivatkozunk. (Figyelem: ez igény szerinti lapozásnál azt jelenti, hogy amikor behozzuk a lapot, ezt a bitet rögtön 1-be állítjuk, hiszen azért hozzuk be a lapot, mert hivatkozunk rá!) Lapcsere esetén azt a lapot kell kicserélnünk, amelyik a legrégebben van bent (FIFO), de ha a FIFO módszerrel meghatározott lap hivatkozás bitje=1, akkor a lapot 0 értékû hivatkozás bittel betesszük a FIFO végére. (Azaz csak 0 hivatkozás bitû lapot cserélhetünk le.) Az alábbi példában a laphiba eseteket - a fentiektõl eltérõen - *gal jelezzük. 7* 7,1 ----------

6* 7,1 6,1 -------

5* 7,1 6,1 5,1 ----

1* 5,1 1,1 6,0 7,0

4* 6 7 7,1 6,1 5,1 4,1

2* 5,1 1,1 2,1 7,0

5 5,1 1,1 2,1 7,0

6* 5,1 1,1 2,1 6,1

3* 7,0 6,1 5,1 4,1 7* 5,0 1,1 2,1 6,1

7,0 6,0 5,1 4,1

5,0 1,0 2,1 6,1

7,0 6,0 5,0 4,1

5,0 1,0 2,1 6,1

7,0 6,0 5,0 4,0

5,0 1,0 2,0 6,0

3,1 6,0 5,0 4,0

2* 3,1 2,1 5,0 4,0

6* 3,1 2,1 6,1 4,0

7,1 1,0 2,0 6,0

6 7,1 1,0 2,0 6,1

5* 7,1 5,1 2,0 6,1

7* 6 3,1 2,1 6,1 7,1

5* 3,0 2,1 6,1 7,1

3,0 2,0 6,1 7,1

3,0 2,0 6,0 7,1

3,0 2,0 6,0 7,0

. 5,1 2,0 6,0 7,0

2 . 7,1 5,1 2,1 6,1

A laphibák száma: 4+10. Figyeljük meg, hogy mindegyik lapozási algoritmus esetében, amíg az operatív memória meg nem telik, minden egyes új lapra történõ hivatkozás laphibával jár. Az ezen (jelen példában az elsõ 4) felüli laphibaszám jellemzi valójában az adott algoritmus jóságát. Ezért adtuk meg minden esetben a laphibák

34

számát összeg formájában, külön felüntetve a "kötelezõ" és az algoritmust jellemzõ laphibaszámot. 40. Valósítsa meg a következõ precedenciagráfot a. fork/join b. parbegin/parend utasítások segítségével!

U1

U3

U2

U4

U5

U6

U7

U8

a.

L2: L3:

L1: L4:

c1:=c2:=2; U1; fork L1; U2; fork L2; U4; goto L3; U5; join c1; U7; goto L4; U3; U6; join c2; U8;

35

b.

U1; parbegin begin U2; parbegin U4; U5; parend; U7; end; begin U3; U6; end; parend; U8;

41. Valósítsa meg a következõ precedenciagráfot a. fork/join b. parbegin/parend utasítások segítségével!

U1

U2

U3

U4

U5

a. A problémát most az okozza, hogy az U1 utasítás után a gráf három ágra szakad, míg a fork utasítással csak kétfelé való elágaztatás lehetséges. Megoldás: két fork utasítás használata. Az elsõvel a gráfot kétfelé ágaztatjuk, míg a másodikkal az egyik ágat (a mi megoldásunkban az elsõt) bontjuk további két részre. Figyeljük

36

meg azt is, hogy mivel az U5 utasítás elõtt 3 ág találkozik, a join utasítás c számlálójának kezdetben 3-as értéket adunk!

L2: L1: L3:

c:=3; U1; fork L1; fork L2; U2; goto L3; U3; goto L3; U4; join c; U5;

b. A parbegin/parend használatakor semmilyen probléma nem merül fel: U1; parbegin U2; U3; U4; parend; U5; 42. Adott a következõ fork/join leírású programrészlet: c1:=c2:=c3:=2; U1; fork L1; U7; fork L3; U8; goto L4; L1: U2; fork L3; U3; L2: join c1; U4; goto L4; L3: join c2; U6; goto L2; L4: join c3; U5;

37

a. Mely utasítások hajthatók végre az U3 utasítással párhuzamosan? Indokolja! b. Rajzolja fel a precedenciagráfot! c. Valósítsa meg ugyanezt a programot parbegin/parend utasításokkal is! b. A precedenciagráf:

U1

U7

U8

U2

U6

U3

U4

U5

a. A gráfból leolvashatóan U3-mal párhuzamosan a vele "megelõzõ" illetve "követõ" kapcsolatban nem álló utasítások, azaz az U6, illetve az U7(!) és az U8(!) hajtható végre. c. Az adott precedenciagráf parbegin/parend utasításokkal közvetlenül nem valósítható meg (hiszen az U1 után szétváló két ág egynél több helyen, az U6-nál és az U5-nél is egyesül), be kell vezetnünk a megfelelõ vezérlõ szemaforokat is. A szemaforokat berajzoltuk a precedenciagráfba:

38

U1 s2

s7 U7

U2 s67

s8 U8

s62

s3

U6

U3 s46

s43

s58 U4 s54 U5

Magyarázat: például az s2 szemafor az U2 utasítás elvégzését engedélyezi, az s43 szemafor az U4 elvégzését az U3 elvégzése után, míg az s46 az U4 elvégzését engedélyezi az U6 elvégzése után stb. A parbegin/parend program a berajzolt szemaforokkal: parbegin begin begin begin begin begin begin begin begin parend;

U1; V(s7); V(s2); end; P(s7); U7; V(s8); V(s67); end; P(s2); U2; V(s62); V(s3); end; P(s8); U8; V(s58); end; P(s67); P(s62); U6; V(s46); end; P(s3); U3; V(s43); end; P(s46); P(s43); U4; V(s54); end; P(s58); P(s54); U5; end;

39

Magyarázat: például a begin P(s46); P(s43); U4; V(s54); end; sor jelentése: Az s46 szemafor segítségével megvárjuk, míg az U4 utasítást engedélyezzük az U6 elvégzése után, illetve az s43 szemafor segítségével megvárjuk, míg az U4 utasítást engedélyezzük az U3 elvégzése után. Ha mind a két feltétel teljesül, elvégezhetjük az U4 utasítást, majd ezután az s54 szemafor szabadra állításával engedélyezzük az U5 utasítás elvégzését, stb.

40

IRODALOMJEGYZÉK

[1]

James L. Peterson - Abraham Silberschatz: Operating System Concepts - 2nd edition Addison-Wesley, 1985. ISBN 0-201-06079-5

[2]

Bakos Tamás - Zsadányi Pál: Operációs rendszerek Gábor Dénes Mûszaki Informatikai Fõiskola, ISBN 963 577 098 7

[3]

Kiss István - dr. Kondorosi Károly: Operációs rendszerek Mûegyetemi Kiadó, 1992.

[4]

Intel Microprocessor and Peripheral Handbook Intel Corporation, 1989. ISBN1-55512-041-5

41