Ugrás a tartalomhoz

Operációs rendszerek

Dr. Fazekas Gábor (2011)

Kempelen Farkas Hallgatói Információs Központ

Ütemezési stratégiák

Ütemezési stratégiák

Döntési helyzetek, módok:

  • Nem beavatkozó (nem preemptív)

    • – a processzus maga mond le a CPU-ról (futó állapotból várakozó állapotba kerül

    • –I/O eseményre vár

    • – vagy megáll

  • Beavatkozó (preemptív)

    • – egy futó processzust az operációs rendszer megszakít és készenlétei állapotba helyez, vagy várakozó állapotból készenléti állapotba küld

    • – jobb szolgáltatást tesz lehetővé, hiszen egy processzus sem sajátíthatja ki a CPU-t túl sok ideig

Igénybejelentési sorrend szerinti kiszolgálás- First come first served (FCFS):

  • minden processzus a készenléti sorba kerül

  • mikor az aktuális processzus végrehajtási megszűnik, a készenléti sorban legrégebb óta váró processzus lesz kiválasztva végrehajtásra

  • egy rövid processzus túl sokáig várhat végrehajtása előtt...

  • az átlagos várakozási idő nagyon szórhat! (konvoj hatás)

Körleosztásos - Round Robin:

  • beavatkozás egy óra alapján: minden processzus sorban egy meghatározott ideig (q) használhatja a CPU-t (q = 10-100 millisec.)

  • egyenlő időközönként óramegszakítás generálódik

  • megszakítás esetén az éppen futó processzus a készenléti sorba kerül és a következő processzus kerül futó állapotba

  • n processzus esetén a várakozási idő: (n-1)/q

Rövidebb igény először - Shortest Process Next:

  • nem preemptív ütemezés

  • a legkisebb várható processzorfoglalási idővel rendelkező processzus kerül kiválasztásra

  • hosszabb processzusok háttérbe szorulhatnak, éhezés!

  • ha a megjósolt feldolgozási idő nem helyes, az operációs rendszer megszakíthatja a processzust (preemptív ütemezés)

  • elméletileg minimalizálja az átlagos várakozási időt

Rövidebb megmaradó idő- shortest remaining time next:

  • a rövidebb igény először preemptív változata

  • a feldolgozási idő becslése szükséges

Magasabb válaszarány először:

  • a legnagyobb R=(w+s)/s arányú processzus választása következőnek (w: proceszorra való várakozással töltött idő; s: várható kiszolgálási idő )

Visszacsatolt ütemezés - Feedback Scheduling

  • a hosszabban futó processzusok „büntetése”