Ütemezési algoritmus

A HupWiki-ből...

Tartalomjegyzék

Processz ütemezők

Az ütemező működését meghatározó algoritmus. Multiprogramozott operációs rendszerek alapjának a CPU-ütemezés tekinthető. A rövidtávú ütemezés feladata annak eldöntése, hogy a processzort melyik futásra kész folyamat kaphatja meg.

A rövidtávú ütemezők két fő csoportba sorolhatók:

  • Preemptív: ha az operációs rendszer elveheti a futás jogát az éppen futó folyamattól, azt "futásra kész" állapotúvá teheti, és a CPU-t egy másik folyamatnak adhatja, azaz egy másik folyamatot indíthat el
  • Nem preemptív: ha az operációs rendszer nem veheti el a futás jogát a folyamattól, azaz a futó folyamat addig birtokolja a CPU-t, amíg egy általa kiadott utasítás hatására állapotot nem vált. Azaz csak maga a folyamat válthatja ki az új ütemezést. Például a folyamat befejeződik, vagy erőforrásra, eseményre várakozik, esetleg önként lemond a futás jogáról.

Mostanság már mindegyik általános célú operációs rendszer preemptív ütemezővel rendelkezik.

A mai korszerű ütemezők az ún. O(1) ütemezést valósítják meg. Ilyen algoritmus szerint működik a 2.6-os Linux kernel processz ütemezője, amelynek a kifejlesztése a magyar származású, a Red Hat alkalmazásában álló Molnár Ingo nevéhez fűződik.

Szintén az O(1) algoritmus alapján működik a FreeBSD-ben a jelenleg nem alapértelmezett ütemezőként jelenlevő ULE ütemező is. Az ULE Jeff Robertson nevéhez fűződik.

I/O ütemezők

Linux I/O ütemezők

  • jelenleg elérhető ütemezők:
    • deadline: megpróbálja minimalizálni a "seek"-eket, miközben gondoskodik arról, hogy ne várakozzon kérés tovább, mint egy megadott időperiódus
    • anticipatory: megáll azután, hogy befejezte az olvasási műveletet, feltételezve, hogy egy másik közeli olvasási kérés felbukkan hamarosan
    • CFQ ("completely fair queueing"): megpróbálja egyenlő részre felosztani a rendelkezésre álló I/O sávszélességet a processzek között
    • noop: elsősorban olyan eszközökhöz készült (memória-alapú eszközök) amelyek nem igazán profitálnak az előzőekben felsorolt ütemező logikákból
  • váltás az ütemezők közt:
    • a kernel boot paramétereit kell kiegészíteni, pld. egy "elevator=cfq"-val
    • futás közben átállításra példa: 'echo cfq > /sys/block/hda/queue/scheduler'

A szócikkhez kapcsolódó szakirodalom

  • Kóczy A., Kondorosi K.: "Operációs rendszerek mérnöki megközelítésben" (ISBN 963-545-250-0)
Személyes eszközök