Friss hírek

01

Megosztás

1. A második generációs számítógépekben tranzisztorok voltak.
Igaz/Hamis

2. A végrehajtási környezet, olyan környezet, ahol a számítógép végrehajtja a programokat. Például szerver szoba, iroda, stb.
Igaz/Hamis

3. Mely folyamat állapot átmenet NINCS a nem preemptív rendszerekben?
a. futás megszakad
b. létrejön
c. esemény bekövetkezik
d. megszűnik
e. elindul
f. eseményre vár

4. Az operációs rendszer akkor függeszt fel folyamatokat, ha a rendszer túlterhelődik.
Igaz/Hamis

5. A folyamatok közötti információcsere szorosan csatolt, ha az közös tárterületen keresztül történik.
Igaz/Hamis

6. A folyamatok közötti információcsere lazán csatolt esetben csak fizikai és virtuális csatornán keresztül is történhet.
Igaz/Hamis

7. Az erőforrás használati gráfban az erőforrás használat nyila az erőforrás osztálytól a folyamathoz mutat.
Igaz/Hamis

8. Az erőforrások elvételével a holtpont megelőzhető, amikor egy P folyamatnak olyan erőforrás igénye van, amelyet más várakozó Qi folyamatok foglalnak, akkor az erőforrásokat a Qi folyamatoktól elveszik és P (futhat, leáll, elindul, várakozik) tovább, különben P (futhat, leáll, elindul, várakozik).
Igaz/Hamis

9. A körforgó ütemezési algoritmus jó, mert kiküszöböli a konvoj hatást.
Igaz/Hamis

10. Melyik két folyamat állapot közötti átmenet a középtávú ütemezés? Válasszon ki egyet vagy többet:
a. fut – várakozik
b. futásra kész – felfüggesztve futásra kész
c. várakozik – felfüggesztve várakozik
d. fut – futásra kész
e. várakozik – futásra kész

 

ZÁRTHELYI 1. ALGORITMUSOK

  1. Holtpont

I/1. Biztonságos sorozat keresés (amely alapja, hogy a folyamat csak maximális erőforrás megléte esetén fut csak le)

Adott egy rendszer, amelyben 1 erőforrás osztály van, 10 erőforrással. A rendszerben 3 folyamat (P1, P2, P3) található, amelyek az alábbi foglalásokkal F=(3, 2, 2) és maximális igényekkel M=(9, 4, 7) rendelkeznek. Ha úgy véli, hogy a rendszer biztonságos állapotban van, akkor adja meg a folyamatoknak egy biztonságos sorrendjét, különben jelölje az összeset „-„ jellel:

Biztonságos sorozat:

àà

 

  1. lépés: Elkészítem a kiindulási táblázatot a megadott adatok alapján. Szükségünk van egy Foglal, egy Max, és egy Még oszlopra. Mivel a rendszerben 3 folyamat található meg (P1, P2, P3), így 3 sorra. A foglalásokat F=(3, 2, 2) a Foglal oszlopba, a maximális igényeket M=(9, 4, 7) a Max oszlopba írom be. A Még oszlopot kitöltöm a Max és a Foglal oszlopok értékeinek különbsége alapján. Utolsó lépésként összeadom a foglalt erőforrások számát, majd megnézem, hogy hány szabad maradt a 10 erőforrásból. Ezt az értéket a Szabad sorba írom be.
FoglalMaxMég
P1396
P2242
P3275
Szabad: 3

 

  1. lépés: A szabad erőforrások száma alapján meghatározom, hogy melyik folyamat erőforrás igényét tudom maximálisan kielégíteni. A választásom a P2 folyamatra esett mivel neki még 2 szabad erőforrásra van szüksége. Ezt követően a foglalt erőforrások számát (Foglal) a maximum értékre, a kérhető erőforrások számát (Még) pedig 0 értékre állítom. Végül összeadom a foglalt erőforrásokat, és kivonom a rendszerben lévő erőforrásokat számából: 10-9=1. Az szabad erőforrások száma 1 lesz.
FoglalMaxMég
P1396
P2440
P3275
Szabad: 1

 

  1. lépés: Lefut a P2 folyamat és visszaadja az általa foglalt erőforrásokat, így a szabad erdőforrások száma 5 lesz.
FoglalMaxMég
P1396
P2
P3275
Szabad: 5

 

  1. lépés: A szabad erőforrások száma alapján újra meghatározom, hogy melyik folyamat erőforrás igényét tudom maximálisan kielégíteni. A választásom a P3 folyamatra esett mivel neki még 5 szabad erőforrásra van szüksége. Ezt követően a foglalt erőforrások számát (Foglal) a maximum értékre, a kérhető erőforrások számát (Még) pedig 0 értékre állítom. Végül összeadom a foglalt erőforrásokat, és kivonom a rendszerben lévő erőforrásokat számából: 10-10=0. Az szabad erőforrások száma 0 lesz.
FoglalMaxMég
P1396
P2
P3770
Szabad: 0

 

  1. lépés: Lefut a P3 folyamat és visszaadja az általa foglalt erőforrásokat, így a szabad erdőforrások száma 7 lesz.
FoglalMaxMég
P1396
P2
P3
Szabad: 7

 

  1. lépés: A szabad erőforrások száma alapján újra meghatározom, hogy melyik folyamat erőforrás igényét tudom maximálisan kielégíteni. A választásom a P1 folyamatra esett mivel neki még 6 szabad erőforrásra van szüksége. Ezt követően a foglalt erőforrások számát (Foglal) a maximum értékre, a kérhető erőforrások számát (Még) pedig 0 értékre állítom. Végül összeadom a foglalt erőforrásokat, és kivonom a rendszerben lévő erőforrásokat számából: 10-10=0. Az szabad erőforrások száma 0 lesz.
FoglalMaxMég
P1990
P2
P3
Szabad: 1

 

  1. lépés: Lefut a P1 folyamat és visszaadja az általa foglalt erőforrásokat, így a szabad erdőforrások száma 10 lesz.
FoglalMaxMég
P1
P2
P3
Szabad: 10

 

  1. lépés: Mivel mindegyik folyamat erőforrásigényét teljesíteni lehetett, így meg lehet határozni egy biztonságos sorozatot:
P2àP3àP1

 

I/2. Coffman algoritmus

A Coffman algoritmus segítségével állapítsa meg, hogy van-e holtpont, ha a rendszerben négy folyamatunk van (P1, P2, P3 és P4), amelyek három erőforrásosztályból már foglalnak néhány erőforrást, de továbbiakat is igényelnek a következő táblázat szerint:

FoglalKérSzabad
ABCABCABC
P1140005510
P2513202
P3103020
P4241400

 

Ha úgy véli, hogy a rendszerben nincs holtpont, akkor adja meg a folyamatoknak egy biztonságos sorozatát, különben jelölje az összeset „-„ jellel:

Biztonságos sorozat:

ààà

 

  1. lépés: Olyan folyamatot keresek, amely erőforrásigényét teljesíteni tudom a szabad erőforrások (A:5, B:1, C:0) függvényében. A választásom a P4 folyamatra esett, mivel az ő erőforrásigénye (A:4, B:0, C:0) teljesíthető.
  2. lépés: Kivonom a szabad erőforrások számából a P4 folyamat erőforrás igényét. Majd ezt követően a P4 folyamat által foglalt erőforrásokat hozzáadom a szabad erőforrásokhoz.

510 – 400 = 110, 110 + 241 = 351

Az új szabad erőforrások száma a következő: A:3, B:5, C:1

  1. lépés: A P4 által kért erőforrásokat áthelyezem a Foglal oszlopba. Mivel a P4 nem kér több erőforrást a lefutáshoz, így a P4-hez tartozó Kér oszlop mezői kihúzhatók.
FoglalKérSzabad
ABCABCABC
P1140005351
P2513202
P3103020
P4400

 

  1. lépés: Újra megvizsgálom, hogy tudok-e találni olyan folyamatot, amely erőforrásigényét teljesíteni tudom a szabad erőforrások (A:3, B:5, C:1) függvényében. A választásom a P3 folyamatra esett, mivel az ő erőforrásigénye (A:0, B:2, C:0) teljesíthető.
  2. lépés: Kivonom a szabad erőforrások számából a P3 folyamat erőforrás igényét. Majd ezt követően a P3 folyamat által foglalt erőforrásokat hozzáadom a szabad erőforrásokhoz.

351 – 020 = 331, 331 + 103 = 434

Az új szabad erőforrások száma a következő: A:4, B:3, C:4

  1. lépés: A P3 által kért erőforrásokat áthelyezem a Foglal oszlopba. Mivel a P3 nem kér több erőforrást a lefutáshoz, így a P3-hez tartozó Kér oszlop mezői kihúzhatók.
FoglalKérSzabad
ABCABCABC
P1140005434
P2513202
P3020
P4400

 

  1. lépés: Újra megvizsgálom, hogy tudok-e találni olyan folyamatot, amely erőforrásigényét teljesíteni tudom a szabad erőforrások (A:4, B:3, C:4) függvényében. A választásom a P2 folyamatra esett, mivel az ő erőforrásigénye (A:2, B:0, C:2) teljesíthető.
  2. lépés: Kivonom a szabad erőforrások számából a P2 folyamat erőforrás igényét. Majd ezt követően a P2 folyamat által foglalt erőforrásokat hozzáadom a szabad erőforrásokhoz.

434 – 202 = 232, 232 + 513 = 745

Az új szabad erőforrások száma a következő: A:7, B:4, C:5

  1. lépés: A P2 által kért erőforrásokat áthelyezem a Foglal oszlopba. Mivel a P2 nem kér több erőforrást a lefutáshoz, így a P2-hez tartozó Kér oszlop mezői kihúzhatók.
FoglalKérSzabad
ABCABCABC
P1140005745
P2202
P3020
P4400

 

  1. lépés: Újra megvizsgálom, hogy tudok-e találni olyan folyamatot, amely erőforrásigényét teljesíteni tudom a szabad erőforrások (A:7, B:4, C:5) függvényében. A választásom a P1 folyamatra esett, mivel az ő erőforrásigénye (A:0, B:0, C:5) teljesíthető.
  2. lépés: Kivonom a szabad erőforrások számából a P1 folyamat erőforrás igényét. Majd ezt követően a P1 folyamat által foglalt erőforrásokat hozzáadom a szabad erőforrásokhoz.

745 – 005 = 740, 740 + 140 = 880

Az új szabad erőforrások száma a következő: A:8, B:8, C:0

  1. lépés: A P1 által kért erőforrásokat áthelyezem a Foglal oszlopba. Mivel a P1 nem kér több erőforrást a lefutáshoz, így a P1-hez tartozó Kér oszlop mezői kihúzhatók.
FoglalKérSzabad
ABCABCABC
P1005880
P2202
P3020
P4400

 

  1. lépés: Mivel mindegyik folyamat erőforrásigényét teljesíteni lehetett, így meg lehet határozni egy biztonságos sorozatot:
P4àP3àP2àP1

 

  1. Ütemezés

II/1. Legrégebben várakozó (First Come First Served, FCFS)

Adott öt folyamat P=(1, 2, 3, 4, 5), amelyeknek futásideje C=(1, 2, 6, 5, 3). A folyamatok T=(2, 4, 5, 0, 8) időpontban kerülnek futásra kész állapotba. A rendszerben legrégebben várakozó (FCFS) CPU ütemezés működik.

Adja meg a folyamatok ütemezését:

àààà

 

  1. lépés: Elkészítem a kiindulási táblázatot a megadott adatok alapján. A folyamatokat az 1. oszlopba, a folyamatok futásra állapotainak idejét (T) a 2. oszlopba, még a futási időt (C) a harmadik oszlopba írom be.
ÉrkezikCPU-idő
P121
P232
P346
P405
P583

 

  1. lépés: Az algoritmus alapja, hogy az a folyamat lesz leghamarabb kiszolgálva, amelyik leghamarabb érkezett meg futásra kész állapotba. Érkezési sorrendben a folyamatok ütemezése a következő:
P4àP1àP2àP3àP5

 

II/2. Körbeforgó (Round Robin, RR)

Adott négy folyamat P=(1, 2, 3, 4), amelyeknek futásideje C=(3, 6, 2, 5). A folyamatok T=(1, 3, 0, 5) időpontban kerülnek futásra kész állapotba. A rendszerben körforgó (RR) CPU ütemezés működik, az időszelet hossza 3 ms.

Adja meg a folyamatok ütemezését:

ààààààà

(Ha valamelyik helyre már nincs mit ütemezni, akkor jelölje “-” jellel!)

  1. lépés: Elkészítem a kiindulási táblázatot a megadott adatok alapján. A folyamatokat az 1. oszlopba, a folyamatok futásra állapotainak idejét (T) a 2. oszlopba, még a futási időt (C) a harmadik oszlopba írom be.
ÉrkezikCPU-időIndulVégeVár
P113
P236
P302
P455

 

  1. lépés: Megkeresem a legkorábban érkező folyamatot (P3), majd az érkezési idejét, beírom az Indul oszlop megfelelő helyére. Mivel a P3 folyamat CPU-ideje (2) kisebb, mint az időszelet hossza (3), így az indulási időhöz hozzáadom a CPU-időt, majd ezt az értéket a Vége oszlop megfelelő sorába írom be. Végül, mivel a folyamatnak nem kellett várakoznia, így a Vár oszlop megfelelő sorába a 0 értéket írom be.
ÉrkezikCPU-időIndulVégeVár
P113
P236
P302020
P455

 

  1. lépés: Megkeresem a következő legkorábban érkező folyamatot (P1), majd az indulási idejének megadom az előző folyamat (P3) végzési idejét. Mivel a P1 folyamat CPU-ideje (3) megegyezik az időszelet hosszával (3), így az indulási időhöz hozzáadom a CPU-időt, majd ezt az értéket (5) a Vége oszlop megfelelő sorába írom be. Végül, mivel a P1 folyamat az 1. időszeletben érkezett, de csak a 2. időszeletben indult, így 1 időszeletet kellett várnia. Ezt az értéket a Vár oszlop megfelelő helyére írom be.
ÉrkezikCPU-időIndulVégeVár
P113251
P236
P302020
P455

 

  1. lépés: Megkeresem a következő legkorábban érkező folyamatot (P2), majd az indulási idejének megadom az előző folyamat (P1) végzési idejét. Mivel a P2 folyamat CPU-ideje (6) nagyobb, mint az időszelet hossza (3), így az indulási időhöz (5) hozzáadom az időszelet hosszát (3), majd ezt az értéket (8) írom be a végzési időnek. Ezt követően létrehozok egy új P2 folyamatot, amelynek érkezési ideje, az előző végzési ideje (8), a CPU-ideje pedig az eredeti CPU-idő és az időszelet különbsége (6-3=3). Végül, mivel a P2 folyamat a 3. időszeletben érkezett, de csak az 5. időszeletben indult el, így 2 időszeletet kellett várnia. Ezt az értéket a Vár oszlop megfelelő helyére írom be.
ÉrkezikCPU-időIndulVégeVár
P113251
P236582
P302020
P455
P283

 

  1. lépés: Megkeresem a következő legkorábban érkező folyamatot (P4), majd az indulási idejének megadom az előző folyamat (P2) végzési idejét. Mivel a P4 folyamat CPU-ideje (5) nagyobb, mint az időszelet hossza (3), így az indulási időhöz (8) hozzáadom az időszelet hosszát (3), majd ezt az értéket (11) írom be a végzési időnek. Ezt követően létrehozok egy új P4 folyamatot, amelynek érkezési ideje, az előző végzési ideje (11), a CPU-ideje pedig az eredeti CPU-idő és az időszelet különbsége (5-3=2). Végül, mivel a P4 folyamat az 5. időszeletben érkezett, de csak a 8. időszeletben indult el, így 3 időszeletet kellett várnia. Ezt az értéket a Vár oszlop megfelelő helyére írom be.
ÉrkezikCPU-időIndulVégeVár
P113251
P236582
P302020
P4558113
P283
P4112

 

  1. lépés: Megkeresem a következő legkorábban érkező folyamatot (P2), majd az indulási idejének megadom az előző folyamat (P4) végzési idejét. Mivel a P2 folyamat CPU-ideje (3) megegyezik az időszelet hosszával (3), így az indulási időhöz hozzáadom a CPU-időt, majd ezt az értéket (14) a Vége oszlop megfelelő sorába írom be. Végül, mivel a P2 folyamat az 8. időszeletben érkezett, de csak a 12. időszeletben indult, így 4 időszeletet kellett várnia. Ezt az értéket a Vár oszlop megfelelő helyére írom be.
ÉrkezikCPU-időIndulVégeVár
P113251
P236582
P302020
P4558113
P28311143
P4112

 

  1. lépés: Megkeresem a következő legkorábban érkező folyamatot (P4), majd az indulási idejének megadom az előző folyamat (P2) végzési idejét. Mivel a P4 folyamat CPU-ideje (2) kisebb, mint az időszelet hossza (3), így az indulási időhöz hozzáadom a CPU-időt, majd ezt az értéket (16) a Vége oszlop megfelelő sorába írom be. Végül, mivel a P4 folyamat a 12. időszeletben érkezett, de csak a 15. időszeletben indult, így 3 időszeletet kellett várnia. Ezt az értéket a Vár oszlop megfelelő helyére írom be.
ÉrkezikCPU-időIndulVégeVár
P113251
P236582
P302020
P4558113
P28311143
P411214163

 

  1. lépés: Indulási idők növekvő sorendje alapján meghatározható a folyamatok ütemezése:
P3àP1àP2àP4àP2àP4àà

 

II/3. Prioritásos

Adott öt folyamat P=(1, 2, 3, 4, 5), amelyeknek futásideje C=(3, 6, 2, 1, 3), prioritása pedig Prioritas=(5, 4, 2, 3, 1). A folyamatok T=0 időpontban kerülnek futásra kész állapotba.

  1. lépés: Elkészítem a kiindulási táblázatot a megadott adatok alapján. A folyamatokat az 1. oszlopba, a folyamatok futásra állapotainak idejét (T) a 2. oszlopba, még a futási időt (C) a harmadik oszlopba írom be.
CPU-időPrioritás
P115
P224
P362
P453
P531

 

  1. lépés: Mivel minden folyamat a 0. időegységben kerül futásra kész állapotba, így az algoritmusnál a prioritás értéke a mérvadó. Minél kisebb a prioritás annál hamarabb kerül beütemezésre a folyamat. Prioritási sorrendben a folyamatok ütemezése a következő:
P5àP3àP4àP2àP1

 

II/4. Legrövidebb hátralévő idejű (Shortest Remaining Time First, SRTF)

Adott négy folyamat P=(1, 2, 3, 4), amelyeknek futásideje C=(4, 5, 7, 1). A folyamatok T=(5, 2, 4, 0) időpontban kerülnek futásra kész állapotba. A rendszerben a legrövidebb hátralévő idejű (Shortest Remaining Time First – SRTF) CPU ütemezés működik.

Adja meg a folyamatok ütemezését:

ààààààà

(Megjegyzés: ha egy döntés után ugyanaz a folyamat folytatódik, akkor azt újból fel kell venni! Ha valamelyik hely már nincs mit ütemezni, akkor jelölje “-” jellel!)

  1. lépés: Elkészítem a kiindulási táblázatot a megadott adatok alapján. A folyamatokat az 1. oszlopba, a folyamatok futásra állapotainak idejét (T) a 2. oszlopba, még a futási időt (C) a harmadik oszlopba írom be.
ÉrkezikCPU-időIndulVégeVár
P154
P225
P347
P401

 

  1. lépés: Megkeresem a legkorábban érkező folyamatot (P4), majd az érkezési idejét, beírom az Indul oszlop megfelelő helyére. Mivel futás közben nem érkezik új folyamat, így a végzési idő egyenlő lesz a P4 folyamat CPU-idejével (1).
ÉrkezikCPU-időIndulVégeVár
P154
P225
P347
P401010

 

  1. lépés: Megkeresem a legkorábban érkező folyamatot (P2), majd az érkezési idejét (2), beírom az Indul oszlop megfelelő helyére, mivel a P4 folyamat már hamarabb befejeződött. Mivel a CPU-idő 5, így egészen a 7. időszeletig tartana a folyamat. Azonban a 4. időszeletben futásra kész állapotba került a P3 folyamat is. Ekkor meg kell vizsgálni, hogy melyik folyamatnak kisebb a szükséges CPU-ideje a 4. időszeletben. Mivel a P2 folyamatnak 3, a P3 folyamatnak pedig 7 a CPU-ideje, így a P2 folyamat folytatódhat tovább. (Ezt jelezni kell a megoldásban úgy, hogy újra leírom a P2 folyamatot.) Az 5. időszeletben azonban futásra kész lesz a P1 folyamat is. Ekkor meg kell vizsgálni, hogy melyik folyamatnak kisebb a szükséges CPU-ideje az 5. időszeletben. Mivel a P2 folyamatnak 2, a P1 folyamatnak pedig 4 a CPU-ideje, így a P2 folyamat folytatódhat tovább. (Ezt jelezni kell a megoldásban úgy, hogy újra leírom a P2 folyamatot.) Ezt követően már nem lesz új folyamat, amely futásra kész áll, így a P2 végzési ideje az érkezési és CPU-idő összege lesz (2+5=7). Végül mivel nem kellett várakoznia, így a 0 értéket kell beírni a Vár oszlop megfelelő oszlopába.
ÉrkezikCPU-időIndulVégeVár
P154
P225270
P347
P401010

 

  1. lépés: Mivel a 7. időlépésben vagyok, így meg kell néznem, hogy vannak-e olyan folyamatok, amelyek futásra készen állnak. Ilyen a P1 és a P3 is. Mivel a P1-nek a kisebb a CPU ideje, így őt fogom következőnek beütemezni. P1 indulási ideje meg fog egyezni az előző folyamat (P2) végzési idejével (7). P1 végzési ideje pedig az indulási idő és a CPU-idő összege lesz (7+4=11). Várakozás idő szempontjából az 5. időszeletben kellett volna indulnia, azonban csak a 7. időszeletben tudott, így a várakozási idő 2 lesz.
ÉrkezikCPU-időIndulVégeVár
P1547112
P225270
P347
P401010

 

  1. lépés: Végül az utolsó folyamatot (P3) is beütemezem. P3 indulási ideje meg fog egyezni az előző folyamat (P1) végzési idejével (11). P3 végzési ideje pedig az indulási idő és a CPU-idő összege lesz (11+7=18). Várakozás idő szempontjából az 4. időszeletben kellett volna indulnia, azonban csak a 11. időszeletben tudott, így a várakozási idő 7 lesz.
ÉrkezikCPU-időIndulVégeVár
P1547112
P225270
P34711187
P401010

 

  1. lépés Folyamatok ütemezésének meghatározása az indulási idők és a folyamatok megállásának és újraindulásának jelölésével.
P4àP2àP2àP2àP1àP3àà

 

Megjegyzés az algoritmus használatához: Ha egy döntés miatt egy folyamat nem folytatódhat tovább, akkor azt újra fel kell venni a folyamatok közé úgy, hogy a végzési idő lesz az új érkezési idő, a megmaradt CPU-idő pedig az új CPU-idő lesz.