Mi az a "Teljesen Korrekt Ütemező"?

Kernel

Linus nemrég beolvasztotta a 2.6.23-as (egyelőre -rc állapotban levő) mainline kernelbe a Molnár Ingo-féle "Completely Fair Scheduler" (CFS) névre hallgató processz ütemezőt, lecserélve a meglevő, a 2.5-ös fejlesztői kernel során bemutatkozott, szintén Molnár Ingo által fejlesztett O(1) algoritmussal dolgozó scheduler-t. De vajon miért kellett cserélni? Mi a különbség az O(1) elven működő, bonyolult heurisztikkákkal operáló (még) meglevő ütemező és az egyszerű, de annál igazságosabb elven működő, új CFS közt? A válasz közérthető nyelven itt.

( selli | 2007. 08. 05., v – 11:36 )

Nekem valahogy nem derult ki hogy a CFS hogy veszi figyelembe a nice level-t. Vagy mar az sincs?

Nekem ez a post tetszett a legjobban:
"On Mon, 16 Jul 2007, Roman Zippel wrote:
>
> To illustrate the problem a little different: a task with a nice level -20
> got around 700% more cpu time (or 8 times more), now it gets 8500% more
> cpu time (or 86.7 times more).

Ingo, that _does_ sound excessive.

How about trying a much less aggressive nice-level (and preferably linear,
not exponential)?

Linus"

Lehet, hogy jobban utána kellene olvasnom, de állítólag a régihez képest egyszerűbb a kód, mégis:
Torvalds úgy tette a kernelbe, hogy -ezek szerint- nem igazán értette meg :)

Bíztató.

> Lehet, hogy jobban utána kellene olvasnom, de állítólag a régihez képest egyszerűbb a kód, mégis:
> Torvalds úgy tette a kernelbe, hogy -ezek szerint- nem igazán értette meg :)
Most mar csak az a kerdes, hogy a regit ertette-e? :)

York.

------
"Nyugi! Minden a legnagyobb rendben csúszik ki a kezeim közül..."

( horvatha | 2007. 08. 05., v – 12:03 )

Ha már az egyik ütemezőt "O(1)"-nek hívják, akkor
az ordó-jelöléssel milyen bonyolultságú a CFS?
Jól értem, hogy "O(n)", azaz a CFS a processzek
számával arányos futásidőt igényel?

Ha igen, az nem tűnik vészesnek (gondolom én,
aki ilyesmit sose programozott). Nyilván tesztelték,
mi történik igen nagy számú processz esetén is és
nem vészes a CFS saját műveletigénye a mai procikon.

Amatőr kérdés a profikhoz: a CFS jobb lett volna vajon
azokon a hardvereken is, amik az O(1) ütemező
bevezetésekor voltak általánosak? Vagy ott még a
CFS (vélhetően) nagyobb műveletigénye zavaróbb
lett volna?

http://lwn.net/Articles/230574/

"There are a number of interesting aspects to CFS. To begin with, it does away with the arrays of run queues altogether. Instead, the CFS works with a single red-black tree to track all processes which are in a runnable state. The process which pops up at the leftmost node of the tree is the one which is most entitled to run at any given time."

Ez akkor tényleg megmagyarázza a sok vitát a CFS körül. Így boot-kor kell mindenkinek eldönenie, hogy milyen ütemezőt szeretne, és minden process bele van kényszerítve ebbe a sémába.

Összehasonlításképpen Solarison nagyszerűen megférnek egymás mellett a különböző ütemezési osztályok: time share/interactive, fair-share, fixed priority, system, real-time és az interruptok.

erröl is szólt az egyik vita, az egyik hosszú threadben az lkml-en, hogy legyen e a kernelben boot-time-kor választható ütemező, de Linus(?) azt mondta, hogy nem lesz és kész.

lehet, hogy erre gondolt

Nekem mindig igazam van, ha nem, akkor nincs igazam, szoval megint igazam van hogy nincs igazam.

debian 4.0 - linux-2.6.22.1-pancs1-wifi1 - 2.6.22.1 kernel madwifivel itt

Konkrétan mihez? Tudomásom szerint egy, azaz egy darab CPU (vagy ha úgy tetszik processz) ütemezője volt ( 2.6.23-rc1-ig az O(1) ) / van (2.6.23-rc1 után a CFS) a Linux kernelnek. Így nincs mik közt választani. Sem futási, sem boot időben, se fordítási időben. Ezért nem értettem a mondatot. Lehet, hogy én tudom rosszul, ezért kértem a kollégát, hogy fejtse ki, hogy mire is gondol.

--
trey @ gépház

Elegge flexibilis cucc, gyakorlatilag sajat kis scripteket injektalhatsz a kernelbe, es es a scriptjeiden mulik, hogy mit figyelsz meg vagy eppen mit modositasz. (Pl kernel funkciok viszsateresi ertekeit atirhatod a scripteddel, ha eppen ahhoz van kedved).

Ja es ehhez nem kell kernelt forgatnod (gyariban van), s ezt on-the-fly mukodes kozben megteheted.

Ezt csak megerősíthetem, én már ebédeltem vele együtt sok éve az Üllői úti Bécsi Szelet vendéglőben. :) Amire te gondolsz, az az Iringó név, az valóban női.

--
Sokan nincsenek tudatában annak, / hogy egyszer mindenki meghal. / Akik ráébrednek erre, / azonnal abbahagyják az ellenségeskedést.

Hú, ez tényleg erős érv.

Én teljesen meg voltam róla győződve, hogy nő, mivel úgy emlékszem, valami 5 éve olvastam, talán pont itt a HUP-on, hogy milyen nagyszerű, hogy van ilyen tehetséges kernel hackerünk, aki ráadásul nő. Természetesen a Google-n most semmit sem találtam a fentieket alátámasztandó. :-(

Jó, hogy kiderült, hogy mi az igazság (akkor ezt vehetjük 100%-nak?), mert az O(1) ütemező még sehol sem volt, amikor én már tanítottam, hogy "Ingó az ELTE fiatal női oktatója, aki a Red Hat-nél is dolgozik". Kár, ezek szerint sok embert félreinformáltam. :-(

Egyébként a Google arról sem mond semmit, hogy az Ingó név férfi vagy nő. Egyáltalán nem is találtam sehol ilyen keresztnevet, semmilyen utónévkönyvben...

És még valami. Nem mentegetőzésként, de látom, mások is félrenyúltak ilyesmiben:

http://epa.oszk.hu/00300/00384/00021/18.html

Ingo Schulze pedig egyáltalán nem néz ki nőiesen:

http://de.wikipedia.org/wiki/Bild:Ingo_Schulz-004.jpg

Azt hiszem, most már meggyőződtem magam is a dolgokról. Köszi. :-)