Thema: Konzept für periodische Events

[FlashBurn]

Das einzigste Werkzeug was ich dazu generisch in der Lage sehe ist der HPET. Der Local-APIC-Timer gibt den Event nur auf der CPU wo er läuft und ist somit zwar nutzbar aber nicht für jeden Zweck und der TSC (ebenso wie der ACPI-PMT) gibt gar keine Events ist also nur für Messung und kurzes aktives Warten (z.B. in nsleep) geeignet. Für Messungen ist der TSC natürlich perfekt weil man ihn schnell abfragen kann und weil er (Aufgrund der hohen Zählgeschwindigkeit) eine feine zeitliche Auflösung bietet, dafür bleibt das Problem das alles durcheinander gerät wenn das OS das User-Programm zwischendurch auf ne andere CPU schedult. Fürs Timing, also z.B. das Auslösen eines Event in möglichst exakt 30ms oder auch 2µs, ist der TSC eben gar nicht geeignet (er kann schlicht keine Events auslösen). Und wenn Du bei einem periodischen RTC/PIT-IRQ quasi die Nachkommastellen willst dann nimm lieber den ACPI-PMT oder den HPET, die laufen mit konstanter und verlässlicher Geschwindigkeit.

Also nochmal

Der TSC/ACPI-PMT wird nur als Counter um den aktuellen Zeitpunkt zu bestimmen genutzt.
Wenn ein ACPI-PMT oder HPET (zumindest wenn ich es denn endlich mal schaffe, den Code zu schreiben ) vorhanden ist, dann nutze ich auch keinen TSC (abgesehen von den neueren CPUs).

Der worst-case wird deutlich mehr daneben liegen, das liegt in der Natur eines General-Purpose-OS. Auch der average-case wird kaum in den einstelligen Mikrosekundenbereich (wohl noch nicht mal in den zweistelligen) vordringen, das ist eher der selten erreichte best-case.

Im Endeffekt theoresiere ich hier viel, ihr aber auch Aber so wie meine Theorie aussieht, sollte es eigentlich klappen.
Bei 250µs= 250000ns und nem P100, wo 1 Takt= 10ns und ich sage jetzt mal im Durchschnitt braucht eine Instruktion 20ns, komme ich auf 12500 Instruktionen die ausgeführt werden können in dieser Zeit. Das sollte für mehrere IRQs reichen. Ansonsten wüsste ich gerade nicht was mir noch dazwischen funken sollte (außer der SMM, aber der sollte ja eigentlich nicht lange dauern und auch nicht ständig auftreten).

DIV wirft auch ne Exception wenn das Ergebnis zu groß für ein Register ist, also z.B. bei 0x00000033_33333333 / 0x00000002 wäre das Ergebnis größer als 32Bit.

Äh, das sollte nicht passieren, da der Code den ich im Moment nutze das abfängt. Bzw. habe ich sogar Code gefunden, der schneller sein sollte als 2 divs, da ich die einzige große Division durch eine Konstante (1000) mache und da kann man irgendwie vereinfachen (richtig verstanden habe ich das nicht, aber funktionieren tut es ).

Damit wäre der PIT aber nur für relative Dinge (wie z.B. ein sleep) geeignet. Wenn Du z.B. einem Video-Player-Programm einen 24Hz Event geben möchtest damit ein Film mit 259200 Bildern bei 24fps auch ganz genau 3 Stunden läuft dann nützt Dir der PIT im One-Shot-Mode nicht viel. Für die Verwaltung der Zeitscheiben (auf einem Single-CPU-System), was ja auch relative Zeiten sind, taugt der One-Shot-PIT natürlich.

Da kommen wir halt wieder zu meinen mehreren Zeitquellen.

Alles was soweit in der Zukunft liegt, das es ab dem aktuellen Zeitpunkt größer ist (zeitlich gesehen) als ein Intervall des periodischen Timers, kommt in eine Liste die der periodische Timer verwaltet.
Dieser guckt bei jedem IRQ nach, ob ein Event getriggert werden muss was noch vor dem nächsten IRQ liegt. Ist das der Fall, wird dieses Event an den Scheduler (der aktuellen CPU, auf SMP Systemen) weitergereicht und ab da läuft das ganze dann über relative Zeiten.
Sprich der Scheduler guckt bei jedem Aufruf, wie lange es bis zum nächsten Event ist. Ist diese Zeitspanne kürzer als die Zeitscheibe die der neue Thread hat, dann wird die Zeit bis zum nächsten Event genommen. Ansonsten die Zeit für den Thread.

Ich denke ein wenig Pseudocode hilft hier weiter:

Code: [Auswählen]

uint64t diff= timeNow - timeStarted;
uint32t nextEventTime= -1; //ich weiß theoretisch falsch, aber ich wollte halt die größte unsigned Zahl haben und das ist so kürzer

if(eventQueue) {
  eventQueue->time-= diff;

  while(eventQueue->time == 0) {
    threadWakeup(eventQueue);
    eventQueue= eventQueue->next;
  }

  nextEventTime= eventQueue->time;
}

//hier kommt dann der eigentlich Scheduler

if(nextEventTime < threadTimeslice)
  timerSetTimeslice(nextEventTime);
else
  timerSetTimeslice(threadTimeslice);

timeStarted= timerGetNow();


Trotzdem wüste ich gerne was Du mit "One-Shot-Scheduler" meinst.

Damit meine ich "nur" das du keinen periodischen Timer nutzt, sondern nen One-Shot-Timer. Damit will ich mir die ständigen IRQs sparen (dafür wird es dann leider auf SMP System ein wenig "langsamer", zwecks IRQs an alle CPUs.

Wieso sollten die TSCs nicht mehr auseinander driften, gerade auf den modernen CPUs können alle CPU-Kerne ihre Taktfrequenz unabhängig und dynamisch ändern (bei den aktuellen Core i? eventuell sogar ganz ohne aktives zutun von OS oder BIOS). Und selbst bei den aller ersten Pentium-Pro Systemen war es nicht verboten CPUs mit unterschiedlichem Core-Takt auf ein Board zu stecken solange der Front-Side-BUS-Takt identisch war. Wie will man sowas synchronisieren? Von den ganzen physikalische Phänomenen wie schwankenden Temperaturen usw. mal ganz abgesehen. Stell Dir mal ein Dual-Sockel Core i7 System vor bei dem einer der beiden CPU-Lüfter leicht verschmutzt ist (in einem privaten PC sicher nicht auszuschließen) und der Turbo-Boost-Controller der betreffenden CPU alle ihre Kerne nicht ganz bis an die maximale Frequenz ran lässt (weil das CPU-Die am Temperatur-Limit ist). Dann hast Du 4 CPU-Kerne mit z.B. 2,6GHz und 4 mit 2,0GHz. Wie will man sowas synchronisieren?
Das synchronisieren der TSCs ist völliger Blödsinn, um die als Stoppuhr zu benutzen braucht man sie nicht zu synchronisieren.

Wie ich schon geschrieben habe, wird auf neueren CPUs ein konstanter TSC, sogar auf allen Kernen garantiert. Der ist ab Core2 nicht mehr an die CPU Frequenz gebunden!
Um dann nochmal auf die Variante mit den unterschiedlichen CPUs zu kommen. Den Fall betrachte ich erst gar nicht! 1. ist das ganze dann kein SMP- sondern ein AMP-System und die paar Systeme die es eventuell gibt, um die kümmere ich mich nicht! Mir ist durchaus klar, das ich nicht jedes System unterstützen kann, dafür wäre der Aufwand viel zu groß, genauso wie die Einschränkungen. Zumal Intel damals (zu Pentium Zeiten) schon gesagt hat, das sie nicht garantieren das solche Kombinationen laufen. Die wollten sogar das du 2 CPUs mit dem selben Stepping (und das ist bis heute in den Köpfen der Leute drin) nimmst. Das haben die sogar noch zu P3 Zeiten gesagt.
In dem Sinne gibt es offiziell gar keine AMP-Systeme auf der x86 Architektur.

Um nochmal was klarzustellen.
Ihr "werft" mir immer vor, den TSC für generisches (wie ihr es so schön nennt) Timing zu nehmen. Das stimmt so nicht. Im Endeffekt nutze (wenn ich ihn überhaupt nutze) ich ihn nur für relative und kurze Zeiten (also genau dafür wofür er gemacht wurde). Über das Intervall (also die Länge) lässt sich jetzt streiten, aber ansonsten nutze ich den TSC eben nicht für langfristige Zeiten.

Der Vorteil bei meinem System ist doch, das ich nen periodischen Timer habe, der nur eine Auflösung von 55ms Intervallen (am Bsp. des PIT) hat. Das ist natürlich viel zu grob. Für die "Nachkommestellen" (wie du es nennst) nutze ich dann den TSC.
Passiert mit dem TSC irgendwelcher Blödsinn (aus welchen Gründen auch immer) für 4ms (oder so), dann ist das ab dem nächsten periodischen IRQ wieder egal, ab diesem (so fern nicht wieder was mit dem TSC passiert) Zeitpunkt ist das "Timing" mit dem TSC wieder in Ordnung! Ich schleppe also keine Fehler mit.

[FlashBurn]

Um nochmal auf meine Rumrechnerei zurück zu kommen (zwecks der Performance).

Ich habe es jetzt nur mal auf nem AMD K6-200, nem dual Celeron 400 und Qemu getestet.

Also auf dem K6 ist "div" schneller als eine Version ohne Division, auf dem Celeron 400 (der genauso lange braucht wie der K6 ) ist die Version ohne Division geringfügig schneller und in Qemu ist die Version ohne Division um den Faktor 6 schneller.

Erstmal bin ich überrascht, das der K6 genauso schnell (trotz der halben Taktrate) ist wie der Celeron. Das nächste ist, das ich bei meinem "div" bleibe, da es auf den CPUs wo es drauf ankommt, schneller ist.

Desweiteren reden wir hier von ca. 40 Takten und ich denke, die sind zu verschmerzen!

[erik.vikinger]

Hallo,


ich hab mir noch mal die letzten paar Beiträge durchgelesen und blicke ehrlich gesagt gar nicht mehr welche HW-Kombinationen Du eigentlich unterstützen möchtest und wie die SW sich dann jeweils verhalten soll. Ich habe eher den (subjektiven) Eindruck das Du in jedem Satz immer gleich von mehreren HW-Kombinationen schreibst. Ich bin ziemlich verwirrt.

Am besten wäre es wenn Du die einzelnen HW-Kombinationen (vielleicht nicht alle aber zumindest einige) mal konkret (unabhängig voneinander) beschreibst, erklärst nach welchen Kriterien die jeweils selektiert werden und dann mit ein paar Beispielen jeweils das Verhalten von periodischen/einmaligen langen/kurzen Events beschreibst, ohne Dich dabei auf andere Kombinationen zu beziehen. Ich weiß dass das etwas Arbeit ist aber keiner hier kann in Deinen Kopf reinsehen und vielleicht gibt Dir das auch selber etwas mehr Klarheit. Anhand verschiedener konkreter Beispiele können wir dann auch mal überlegen welche Genauigkeit (best/average/worst-cases) damit ungefähr jeweils möglich sein sollte.


Zum TSC bin ich ebenfalls etwas verwirrt. Meinst Du wirklich das Intel garantiert das der TSC in allen Kernen (auf dem selben Die oder im gesamten System?) synchron ist? Klar kann man alle Kerne auf einem Die auf den selben Zähler lesend zugreifen lassen aber wenn die Kerne mit unterschiedlichen Taktraten laufen und der TSC noch mal nen anderen Takt hat (welchen eigentlich?) dann kommt es doch zu Jitter und anderen Phänomenen (nebst den Latenzen beim Überführen der Zählerwerte in eine andere Takt-Domäne). Wenn der TSC nicht mehr mit der selben Frequenz wie der eigentliche CPU-Kern läuft dann ist er doch für kurze (taktgenaue) Performancemessungen kleiner Code-Abschnitte kaum noch zu gebrauchen, gerade die enge Kopplung dieses Zählers an die tatsächliche Arbeitsgeschwindigkeit der CPU macht ihn dafür so interessant. Im Prinzip hätte Intel den TSC mit diesem Schritt zu einem weiteren globalen Zähler degradiert (davon gibt es doch nun schon mehr als genug). Wenn man schon so einen globalen Zähler möchte dann hätte Intel dafür besser einen neuen erstellen sollen anstatt den TSC seines besonderen Alleinstellungsmerkmales zu berauben.


Grüße
Erik

[FlashBurn]

Also gut fangen wir mit dem Minimum an.

Der PC unterstützt kein ACPI und hat keinen APIC.

Für die periodische Zeitquelle nehme ich die RTC und für meinen Scheduler den PIT.

Der RTC wird auf ein Intervall von 62,5ms gestellt (sprich alle 62,5ms wird ein IRQ ausgelöst).

Was wichtig ist, ein Event was (zeitlich gesehen) >= 62,5ms in der Zukunft liegt kommt in die Event-Queue der RTC und ein Event < 62,5ms kommt in die Event-Queue des Schedulers.

(Ich beschreibe erstmal ein einmaliges Event (z.B. ein Sleep))

Innerhalb des IRQ-Codes wird ein Counter um 62500000ns erhöht. Desweiteren wird in der Event-Queue (dort wo alle Events drin sind; hier wird mit absoluten Zeiten gearbeitet) geguckt ob das 1. Event (sprich das was als nächstes kommt) innerhalb einer Zeit < 62,5ms ausgelöst werden muss. Ist das nicht der Fall braucht nichts gemacht zu werden und der IRQ ist fertig.
Ist da aber ein Event was innerhalb einer Zeit < 62,5ms ausgelöst werden muss, wird es aus dieser Queue entfernt und wird an den Scheduler "weitergereicht".
Der Scheduler packt das Event in seine Event-Queue (das ist ne andere als die von der RTC!). Als Zeit wird ab jetzt die relative Zeit genommen (sprich wie lange noch bis das Event auszulösen ist). Auf diese wird die Zeit drauf gerechnet wie lange seit dem letzten Scheduleraufruf vergangen ist (macht die Rechnung nachher einfacher).
Dann macht der Scheduler sein "scheduler-Ding" (es wird ein neuer Thread ausgewählt, der an der Reihe ist).
Da ich einen One-Shot-Scheduler (was so viel heißt das der Scheduler (und damit auch der IRQ) erst wieder aufgerufen wird, wenn der Thread seine Zeitscheibe verbraucht hat oder der Thread abgegeben möchte) implementiert habe, wird nun geguckt was von der Zeit her "kleiner" ist. Also ob das nächste Event zeitiger passiert oder das Ende des Threads.
Der PIT wird dann auf den jeweiligen Wert gesetzt und dieser Wert wird gespeichert (damit ich ihn beim nächsten Scheduler-Aufruf nutzen kann).
Jedes Mal wenn der IRQ des Schedulers aufgerufen wird (also der PIT einen IRQ auslöst oder der Thread den Scheduler aufruft) wird der Counter des PITs ausgelesen und es wird die Differenz zwischen dem ausgelesenen Wert und dem gespeicherten Wert ausgerechnet (um die Zeit zu berechnen die vergangen ist).
Diese Differenz wird dann vom 1. Eintrag in der Event-Queue abgezogen. Ist der Wert gleich "0" oder zu klein (da habe ich noch keinen Wert festgelegt, aber z.B. < 4µs) wird das Event ausgelöst (und aus der Liste gelöscht).

(Jetzt kommen wir zu den periodischen Events, die habe ich noch nicht implementiert, da ich noch nicht alles fertig gedacht habe)

Der Unterschied zu den einmaligen Events ist, das ich soviele Events in die Event-Queue (>= 0; die Event-Queue des Schedulers) packe das genau 1 Event >= 62,5ms in der Zukunft liegt.
Warum will ich das so machen?
Die Genauigkeit des Schedulers ist natürlich bescheiden und damit bekomme ich, gerade bei periodischen Events, keine vernünftige langzeit Genauigkeit hin.
Um diesen Umstand zu kaschieren will ich immer genau 1 Event in der Queue der RTC haben, denn diese hat eine sehr gute langzeit Genauigkeit.
Ist dann der Zeitpunkt erreicht, dass das Event (welches in der Event-Queue der RTC steht) an den Scheduler weitergegeben werden muss, dann packe ich wieder soviele Events in die Queue, das genau 1 in der Queue der RTC "landet".

Im Moment nutze ich für die "simulation" periodischer Events noch viele einmalige Events. Das wird noch "schöner" gemacht (irgendwie ).

Das hört sich jetzt alles erstmal komplizierter an als es eigentlich ist. Denn der Code ist eigentlich gar nicht so kompliziert (dank dessen das ich "nur" ein Interface implementiere).

Zum TSC bin ich ebenfalls etwas verwirrt. Meinst Du wirklich das Intel garantiert das der TSC in allen Kernen (auf dem selben Die oder im gesamten System?) synchron ist? Klar kann man alle Kerne auf einem Die auf den selben Zähler lesend zugreifen lassen aber wenn die Kerne mit unterschiedlichen Taktraten laufen und der TSC noch mal nen anderen Takt hat (welchen eigentlich?) dann kommt es doch zu Jitter und anderen Phänomenen (nebst den Latenzen beim Überführen der Zählerwerte in eine andere Takt-Domäne). Wenn der TSC nicht mehr mit der selben Frequenz wie der eigentliche CPU-Kern läuft dann ist er doch für kurze (taktgenaue) Performancemessungen kleiner Code-Abschnitte kaum noch zu gebrauchen, gerade die enge Kopplung dieses Zählers an die tatsächliche Arbeitsgeschwindigkeit der CPU macht ihn dafür so interessant. Im Prinzip hätte Intel den TSC mit diesem Schritt zu einem weiteren globalen Zähler degradiert (davon gibt es doch nun schon mehr als genug). Wenn man schon so einen globalen Zähler möchte dann hätte Intel dafür besser einen neuen erstellen sollen anstatt den TSC seines besonderen Alleinstellungsmerkmales zu berauben.

Also auf dem gleichen Sockel garantiert das Intel auf jeden Fall. Was sie jetzt geändert haben ist, dass sie nicht mehr sagen an welchen Taktgeber der TSC geknüpft ist. Aber meistens wohl die höchste Taktfrequenz mit der die CPU gestartet wird.

Ich bin mir nicht sicher, aber ich glaube das sie sagen, das die Frequenz mind. der höchsten CPU-Frequenz entspricht. Damit kann man doch sehr gut leben.

Dies wurde vorallem auf Grund von MS und Linux so gemacht (da es halt keinen verlässlichen hoch präzisen Counter gab).

Ich finde es so auch besser, macht dir (als OS Programmierer) das Leben leichter. Vorallem ist so ein Counter möglich der auch noch performant umgesetzt werden kann (komplett im Usermode).

[Svenska]

Ich hab mir das jetzt nicht mehr durchgelesen.

Allerdings habe ich nach dem letzten Kernel-Update mir die Kernelmessages vom Bootvorgang angeschaut:
"Marking TSC unstable due to TSC halts in idle".

Sowohl auf meinem Core2 Duo, als auch auf dem VIA C7.

Gruß,
Svenska

[FlashBurn]

Erstmal willkommen zurück aus dem Urlaub.

Also das der VIA C7 keinen konstanten TSC unterstützt habe ich eigentlich erwartet, aber was mit dem Core2Duo ist weiß ich auch nicht.
Eine schnelle Suche per Google hat mich nur soweit gebracht, das es wohl was mit tieferen Schlafmodi (<=C2) zu tun hat und da beeinflusst das mein System nicht und selbst wenn, dann muss ich halt die Anforderungen für den TSC höher setzen.

Ich müsste direkt mal nachgucken wie lange es dauert aus einem Schlafmodi <= C2 wieder raus zukommen, bzw. wie groß die Zeitspanne ist da rein und wieder raus zukommen.

[Svenska]

Was ich damit nur anmerken wollte, ist, dass der TSC grundsätzlich als "nicht zuverlässig" zu bewerten ist, was meine Ursprungsaussage war. Umkehrschluss heißt, dass die Zeitmessung im Bereich des TSC ungenau ist (was deinem Grundgedanken widerspricht) oder du eine Whitelist über CPUs führen musst, bei denen der TSC stabil ist.

Ich vermute, eine Whitelist wäre kürzer als eine Blacklist. Einen Pentium III Coppermine (Family 6, Model 8, Stepping 10) markiert Linux nicht als "unstable TSC", meinen Core2 Duo T5500 (Family 6, Model 15, Stepping 6) und meinen VIA C7 (Family 6, Model 13, Stepping 0) jedoch schon. Andere Systeme habe ich nicht zum Testen hier.

Hoffe, es hilft dir weiter. Urlaub war herrlich, jetzt kommt der letzte Prüfungshaufen.

Gruß,
Svenska

[FlashBurn]

Was ich damit nur anmerken wollte, ist, dass der TSC grundsätzlich als "nicht zuverlässig" zu bewerten ist, was meine Ursprungsaussage war. Umkehrschluss heißt, dass die Zeitmessung im Bereich des TSC ungenau ist (was deinem Grundgedanken widerspricht) oder du eine Whitelist über CPUs führen musst, bei denen der TSC stabil ist.

Wenn dann wollte ich das sowieso über eine "Whitelist" machen. Interessant das es auf nem P3 noch funktioniert, aber auf nem P3-M leider nicht.

Einen Pentium III Coppermine (Family 6, Model 8, Stepping 10) markiert Linux nicht als "unstable TSC", meinen Core2 Duo T5500 (Family 6, Model 15, Stepping 6) und meinen VIA C7 (Family 6, Model 13, Stepping 0) jedoch schon.

Laut nem Wikipedia-Artikel (nicht das ich dem 100%ig vertraue) steht das dein Core2 Duo eigentlich schon solch einen konstanten TSC haben müsste und laut dem was ich auf die schnelle bei Google gefunden habe, funktioniert der TSC schon, halt nur nicht mehr wenn du in einen Schlafmodi <= C2 gehst und da ist ja der PC schon fast aus

Ich werd dazu mal die Intel Manuels befragen.