FreeBSD fejlesztő a CFS és SD ütemezőkről

Kernel

Jeff Robertson, a FreeBSD ütemező guruja - aki évek óta dolgozik az ULE (újabban ULE2) ütemezőjén, amelynek célja, hogy lecserélje a 4BSD ütemezőt - szemügyre vette, hogy merre halad a Linux kernel e téren. Belenézett a Con Kolivas-féle SD ütemezőbe és a Molnár Ingo-féle CFS-be is. A véleménye elolvasható a blogjában.

( gabrielakos v | 2007. 08. 06., h – 22:26 )

Na ilyen se volt meg hogy elsonek szolok hozza valamihez :)

Szal az a velemenyem, hogy sajna Ingo nem talalta fel a nagy csodat, hanem egy csomot egyszerusitett, cserebe kisse rosszabb lett a kod hatasfoka. O(log n) azert neha sokkal rosszabb bir lenni mint O(n). Igazi szerver benchmarkok kellenenek, desktop nem erdekel... :)

--
Gabriel Akos

( eax | 2007. 08. 06., h – 22:53 )

s/O(n)/O(1)/, nem? A log n-t jobban szeretjuk, mint a linearisat, szerintem.

--
Fontos feladatot soha ne bizz olyan gepre, amit egyedul is fel tudsz emelni!

( turul16 v | 2007. 08. 07., k – 13:54 )

"I'm curious to see if they find the increased algorithm complexity will show up on many profiles. You can imagine that when dealing with hundreds or thousands of running threads the cache misses when walking log n could be quite expensive."

Hát én nem volnék ennyire peszimista.

Ha jol emlékszem n=15 nél ez az algoritmus gyorsabb mint a régi O(1), szerintem elég fura egy nem n függő algoritmusra bízni az ütemzést.

Az n csak CPU ra várakozó processek száma, én egy csomó S betűt szoktam látni a top, ezek álltalában kevesen vannak.

Ha jol emlékszem egy cache miss kb. 120 óra jelbe kerülhet, ha nincs közbe semmi amit csinálhat a rendszer ez is elég peszimista. 64(8*8) Burst reading elején derül ki a miss, akkor a következő hasonló olvasás végéig kell kb. ennyit várni.

log_2(16)=4 legyen sok(16) várakozó process, és mondjuk gonosz módon 1000Hz cumóval játszunk másodpercenként 1000 szer lefutatva az algoritmust, Akkor is max ~500 * 1000 orajelet bukunk -e miatt.

Szerveren nem szokás 1000 Hz -vel játszani sokal inkább javasolt 100 vagy 250 körüli.
Kurva magas esélyel I/O wait miatti várakozás még mindig nagyságrandekkel sulyosabb, cache -böl is akkor van jó esélye kikrülnie a dolognak, ha nagy adatmozgatás történt, ami egy jó alkalmazásnál i/o müveletkor gyakori, és nem a processen belüli (számítás nélküli) adattologatáskor.

De, ha valki nagyon parázik a cahche missek miatt, ujabban már remek prefetch utasítások vannak :), amik cacheben való tovább tartást is kérhetik AFIK.

Molnár Ingo -nak van hup accountja ? kiváncsi lennék ő mit mond ezekröl.

( bra | 2007. 08. 08., sze – 10:01 )

"ütemező guru"... Hát nem is tudom, nekem eddig nem éppen ezt a benyomást keltette.

Szerintem a guru szó nem feltétlenül a szakmai tudásra, sokkal inkább valakinek a valamiben betöltött vezetői státuszára vonatkozik (legalábbis én ilyen értelmeben szoktam használni, lehet, hogy rosszul?). Mivel Robertson nyomja a FreeBSD-nél ezt az ütemező témát, megkockáztattam neki a guru jelzőt.

--
trey @ gépház

Jó, ne ragozzuk. :)

Nem célzok rá, egész egyszerűen valamiért az volt a benyomásom, hogy más -az eddigi munkájuk alapján általam profinak ítélt- committerekhez képest gyengébb képességű :).
Ha megpróbálom felidézni az okokat, ezek jutnak eszembe:
- elég sokat görcsölt az ULE-val, és sok probléma elő is jött vele
- mindezek ellenére a mai napig nem vagyok róla meggyőződve, hogy tényleg megérte (bár az ULE 2 azért lehet, hogy ezen javít)
- nekem olyan durrbele embernek tűnt az ULE kapcsán, azaz néha nagy elánnal belevetette magát a dologba, majd sokáig szinte semmi és most megint...

Az idő majd megválaszolja, hogy a mostani megoldása tényleg jobb-e.

van motiváció, a linux-nál elkezdtek ott mozgolódni (Kolivas ~2003, de nem biztos) akkora freebsd-nél miért nem tegyen rá, hogy jobb legyen

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

Már van ULE 3.0 is , a shed_smp lett átnevezve.

A listákon sok jót írnak , meglássuk ezt a 7-es FreeBSD-t.

link

ULE 3.0: Fine grain scheduler locking and affinity improvements. This has
been in development for over 6 months as SCHED_SMP.
- Implement one spin lock per thread-queue. Threads assigned to a
run-queue point to this lock via td_lock.
- Improve the facility for assigning threads to CPUs now that sched_lock
contention no longer dominates scheduling decisions on larger SMP
machines.
- Re-write idle time stealing in an attempt to make it less damaging to
general performance. This is still disabled by default. See
kern.sched.steal_idle.
- Call the long-term load balancer from a callout rather than sched_clock()
so there are no locks held. This is disabled by default. See
kern.sched.balance.
- Parameterize many scheduling decisions via sysctls. Try to document
these via sysctl descriptions.
- General structural and naming cleanups.
- Document each function with comments.

Tested by: current@ amd64, x86, UP, SMP.
Approved by: re

Üdv
Godot