Oprendszerek gyakorló feladatok kidolgozásai

Számolósak

Feladat leírása

Egy rendszerben 3 üres memóriakeret (A, B és C) van, és egy olyan "legrégebben nem használt" (Least Recently Used, LRU) lapcsere működik, amely csak egyetlen biten (pl. a "használt" jelzéssel) tárolja a használati gyakoriságot.

Egyforma gyakoriság esetén a FIFO algoritmus alapján dönt.

Írja le, melyik keretbe tölt be a lapot a kernel az alábbi laphivatkozások esetén!

Hivatkozási sorrend: 1, 2, 3, 3, 5, 2, 4, 3, 1, 2

Jelölés:
  • "-" : nem volt laphiba
  • "*" : a kérés nem szolgálható ki (a következő lép a rendszer)

Megoldás - Lap:Keret párok

Hivatkozás Betöltés
1 A
2 B
3 C
3 -
5 A
2 -
4 C
3 A
1 B
2 C
Mivel LRU, meg kell nézni, hogy mit hivatkoztak a legrégebben (a - is hivatkozás) (Innen a legrégebbit fogjuk használni, ami a legnagyobb számmal rendelkezik):
Keret 1 2 3 3 5 2 4 3 1 2
A 1 2 3 3 1 2 3 1 2 3
B - 1 2 2 3 1 2 3 1 2
C - - 1 1 2 3 1 2 3 1

Módosítsa úgy az algoritmust, hogy használja a tárba fagyasztás technikáját is!

A fagyasztás maximális időtartama behozás után 3 lapkérés. Fagyasztás tekintetében a lapbehozás lépését nem tekintjük hivatkozásnak.

Hogyan fut le így az algoritmus?

Hivatkozási sorrend: 1, 2, 3, 3, 5, 2, 4, 3, 1, 2

Megoldás - Lap:Keret párok + Fagyasztás

Hivatkozás Betöltés
1 A
2 B
3 C
3 -
5 A
2 -
4 C
3 B
1 A
2 *
Mivel LRU, meg kell nézni, hogy mit hivatkoztak a legrégebben (a - is hivatkozás, de nincs fagyasztás, mert max időtartama 3, így nem lehet, hogy 5-ig fagyasszuk mondjuk) (Innen a legrégebbit fogjuk használni, ami a legnagyobb számmal rendelkezik) A tárba fagyasztás azt jelenti, hogy a behivatkozás UTÁN X lépésnél nem lehet a keretbe új dolgot rakni, így mondjuk a 2. legrégebbi-be történik az olvasás, ha az 1. még fagyott állapotban van) A : utáni az, hogy még hány körig fagyott, a 0, hogy használható (egy körbe ha 0 akkor már abba lehet használni):
Keret 1 2 3 3 5 2 4 3 1 2
A 1:f 2:3 3:2 3:1 1:f 2:3 3:2 3:1 1:f 1:3
B - 1:f 2:3 2:2 3:1 1:0 2:0 1:f 2:3 2:2
C - - 1:f 1:3 2:2 3:1 1:f 2:3 3:2 3:1

Feladat leírása

Egy beágyazott operációs rendszerben az ütemezőnek két típusú feladat végrehajtását kell támogatnia:

  1. Valósidejű taszkok
  2. Eseménykezelő taszkok

A valósidejű taszkok végrehajtása fontosabb (prioritás = 1), és mivel nagyon hamar lefutnak, ezért nem szakítjuk meg azokat. Ezen taszkok esetén cél a taszkok várakozási idejének minimalizálása.

A kevésbé fontos (prioritás = 0) eseménykezelő taszkok futását 2 időegység után mindenképpen megszakítjuk. Nem teszünk közöttük különbséget a fontosságuk tekintetében. Ezen taszkok esetén az eseményre adott választidejűket szeretnénk alacsony értéken tartani.

A rendszerbe az alább látható taszkok érkeznek.

Milyen sorrendben kerülnek futó állapotba? Egy taszkot több helyre is behúzhat, ha szükséges.

Lefutási sorrend:

Sorrend:

[0,0,4]
[1,2,1]
[1,2,2]
[0,1,1]
[0,2,2]
[0,0,4]
Taszkok: [prioritás, érkezési idő, löketidő]

Elérhető taszkok:

Prioritás Érkezési idő Löketidő
1 2 2
1 2 1
0 1 1
0 0 4
0 2 2

Magyarázat:

Prioritás alapján az 1-es taszk mindíg előbbre kerül. Előszőr a 0,0,4-es taszk fut 2 időszeletet, mivel nem jön be más, így megszakad azután az időosztás miatt. Utána bejön az 1,2,1. Ezt 1 ideig futtatjuk. Utána jön az 1,2,2. Közbe bejött az 0,1,1, de ezt azért várakoztatjuk mert még a 0,0,4-nek nem járt le a 2 időszelete utána meg jött prios taszk. A 2 priós taszk után futtatni kezdjük a 0,1,1-et, utána a 0,2,2-t. Majd utólag a 0,0,4 jön. Azért jön utoljára mert ő az 1. körben már megkapta a 2 időszeletét és a taszkok az 1. körbe jöttek be.

Egy kétprocesszoros rendszer legrövidebb hátralevő löketidejű (shortest remaining time first, SRTF) ütemezőt használ globális terheledelosztással.

A feladat az alábba taszkok ütemezésének bemutatása és a körülfordulási idők kiszámítása. Használja a kiadott feladatmegoldó-lapot az ütemezés futtatásához!

Beérkező taszkok (név|érkezési idő, löketidő):

A[0,4]

B[0,6]

C[1,4]

D[3,3]

E[6,3]

Egy taszk a rendszerbe érkezését követő első időcsoportban futhat először (ha az ütemező kiválasztja). A taszkok bármelyik végrehajtó egységen futhatnak, de a 2. CPU csak akkor kap terhelést, amennyiben az 1. már foglalt. Egy futó állapotban levő taszk megszakítható.

Ütemezési táblázat

t (idő) Érkező Ütem rendezve CPU1 CPU2
0 A4,B6 A4,B6 A B
1 C4 A3,C4,B5 A C
2 - A2,C3,B5 A C
3 D3 A1,C2,D3,B5 A C
4 - C1,D3,B5 D C
5 - D2,B5 D B
6 E3 D1,E3,B4 D E
7 - E2,B4 B E
8 - E1,B3 B E
9 - B2 B -
10 - B1 B -

Körülfordulási idők számítása

Taszk Érkezési idő Befejezési idő Körülfordulási idő
A 0 3 4
B 0 10 11
C 1 4 4
D 3 4 4
E 6 8 3

Megjegyzés: Körülfordulási idő = Befejezési idő - Érkezési idő (+1 ha még bejövetelkor elkezdődhet)