Thema: Konzept für periodische Events

[erik.vikinger]

Hallo,

Ich hab mir das so vorgestellt. Du hast halt den PIT im periodischen Modus mit den magischen 18,2Hz = 55,4ms.

Das ist meiner persönlichen Meinung nach etwas zu grob, weniger als 100Hz würde ich nicht nehmen.

Ein Thread läuft auf CPU0 und möchte für 200ms schlafen, dann ruft er halt sleep(200000000) auf und die holt sich den aktuellen Wert des internen PIT Counters (weil ich den vorher von der zu wartenden Zeit abziehen muss) und packe den Thread in die Delta-Queue des PIT-Handlers.

Du möchtest quasi den Zählerwert vom PIT als Nachkommastellen für Deinen 18,2Hz-Software-Zähler nutzen? Interessante Idee aber ich glaube nicht das das viel nutzt genauer als auf ca. 55ms bekommst Du damit trotzdem keinen IRQ. Ich würde lieber zu einer höheren IRQ-Frequenz raten.

Jedes Mal wenn der PIT den IRQ-Handler aufruft, zieht er 55,4ms von dem 1. Thread in der Delta-Queue ab und wenn die Zeit die da rauskommt kleiner als 55,4ms ist, wird der (und alle Threads für die dies auch noch gilt) in die Sleep Queue der CPU gepackt auf welcher der IRQ-Handler gerade ausgeführt wird.

Wenn Du viele Threads am schlafen hast dann wird das schnell zu einem Problem. Ich würde lieber die absolute Zeit des Aufweckens errechnen (dafür muss man natürlich den Zeit-Counter lesen, was beim HPET ein HW-Zugriff ist) und diesen in eine sortierte Liste eintragen. Der IRQ-Handler für den periodischen PIT-IRQ inkrementiert seinen SW-Zahler und vergleicht dann diesen absoluten Ist-Zeit-Wert mit dem absoluten Soll-Zeit-Wert im vordersten Listeneintrag. Bei Gleichheit wird eine entsprechende Aktion ausgelöst. Das kann das simple Aufwecken eines Threads sein (der einfach nur ein sleep() gemacht hat) aber auch das verschicken einer Message/Signals an einen Prozess oder das setzen eines Event-Object auf das möglicherweise gerade jemand wartet der dann sofort geweckt werden muss.

Wenn ich dich richtig verstanden habe, dann meinst du das ich Probleme mit periodischen Events bekommen würde.

Ja. Solange Du den PIT nicht frei laufen lässt sondern immer mal dran "rumdrehst" bekommst Du Fehler die sich aufakkumulieren.

Das Problem was ich im Moment mit Events habe ist, ich habe noch gar keine Events auf meinem System Ich rede die ganze Zeit nur von Threads die schlafen gelegt werden.

Und wo ist Dein Problem? Wenn ein Event (oder was auch immer) nicht mehrfach sondern nur einmalig auftreten soll dann wird es eben nicht erneut in die geordnete Event-Liste eingetragen. Wo ist das Problem?

Das andere was ich noch meine ist ne Performance Counter um sagen zu können wieviel Zeit vergangen ist.

Wenn Du diese "Performance Counter" nur zu "Statistischen Zwecken", z.B. zur Anzeige in einem Taskmanager, nutzen möchtest dann solltest Du Dir da erstmal keine zu großen Sorgen machen. User-Code sollte sich von so etwas nie abhängig machen.

Ich würde spontan sagen, das ich ne Semaphore für die Events nutzen könnte (zumindest für das Sleep-Event)....

Also das klingt für mich nicht sonderlich klug da noch einen zusätzlichen Mechanismus dazwischen zu setzen. Leg den Thread, der sleep() aufgerufen hat, direkt schlafen und wecke ihn in der Event-Abhängigen Funktion, welche der PIT-IRQ-Handler beim erreichen des entsprechenden Zeitpunkts aufruft, einfach wieder auf.

Obwohl es gar nicht schlecht wäre das immer über Semaphoren zu machen. Um nochmal das Bsp mit dem Game zu bringen, wenn das Event alle 16ms die Semaphore freigibt und der Thread mal länger brauchen sollte, dann bekommt er die Semaphore ja sofort und kann gleich den nächsten Frame berechnen.

Für Spiele oder Multimediaprogramme würde ich ein Event-Object benutzen:

Code: [Auswählen]

t_handle event_object = CreateEventPeriodic(50ms); //Event-Objekt erstellen das vom System alle 50ms gesetzt wird

/// ....

while(...)
{
   WaitForEvent(event_object); //wartet bis das Event-Object gesetzt ist und tut es dann zurücksetzen, falls es bereits gesetzt ist weil die letzte Aktion den Zeitrahmen etwas gesprengt hat dann kommt ohne warten zurück
   tuWasPeriodisches(); //hier wird z.B. das nächste Bild berechnet
}

Ich habe hier einige Motherboards mit mehreren CPUs (Slot1, Sockel370, Sockel5/7, SockelA) die keinen HPET haben und die möchte ich ja auch unterstützen!

Bist Du sicher das Du Boards mit Slot1 oder Sockel5/7 und mehreren CPUs hast?

Du weißt nicht zufällig ab wann ungefähr der HPET auf neuen Boards vertreten war? Ich hab von dem Ding das erste Mal zu Core2 Zeiten gehört.

Nein, genau weiß ich das nicht aber es sollte schon einige Jahre her sein.

Als Alternative würde ich den PIT nicht betrachten, aller höchstens, und nur mit viel Bauchweh, als Notlösung.

Genau das ist er auch (aber war er das nicht von Anfang an ).

So wie fast alles bei der x86-Plattform! Hoch lebe die heilige Kuh der Kompatibilität!


Grüße
Erik

[FlashBurn]

Wenn Du viele Threads am schlafen hast dann wird das schnell zu einem Problem. Ich würde lieber die absolute Zeit des Aufweckens errechnen (dafür muss man natürlich den Zeit-Counter lesen, was beim HPET ein HW-Zugriff ist) und diesen in eine sortierte Liste eintragen. Der IRQ-Handler für den periodischen PIT-IRQ inkrementiert seinen SW-Zahler und vergleicht dann diesen absoluten Ist-Zeit-Wert mit dem absoluten Soll-Zeit-Wert im vordersten Listeneintrag. Bei Gleichheit wird eine entsprechende Aktion ausgelöst. Das kann das simple Aufwecken eines Threads sein (der einfach nur ein sleep() gemacht hat) aber auch das verschicken einer Message/Signals an einen Prozess oder das setzen eines Event-Object auf das möglicherweise gerade jemand wartet der dann sofort geweckt werden muss.

Irgendwie habe ich das Gefühl das wir aneinander vorbei reden

Wo ist jetzt der Unterschied ob du die Threads aufweckst, wenn ihre Zeit abgelaufen ist oder du sie in eine neue Queue packst?
Genauso verstehe ich nicht wo der Unterschied ist ob ich ne Zahl hab und den Thread aufwecke wenn diese Zahl bei "0" ist oder ob zwei Zahlen habe und den Thread aufwecke wenn beide gleich sind?!

Auch sollte ich vielleicht näher erläutern was ich mit einer Delta-Queue meine, denn das ist ne sortierte Liste!

Also in einer Delta-Queue stehen nicht die Absoluten Werte, sondern immer der Abstand zum Vorgänger, so dass nur im 1. Element der Liste der Absolute Wert steht.

Du möchtest quasi den Zählerwert vom PIT als Nachkommastellen für Deinen 18,2Hz-Software-Zähler nutzen? Interessante Idee aber ich glaube nicht das das viel nutzt genauer als auf ca. 55ms bekommst Du damit trotzdem keinen IRQ. Ich würde lieber zu einer höheren IRQ-Frequenz raten.

Auch hier kann ich dir nicht folgen

Also folgender Pseudo-Code:

Code: [Auswählen]

void sleep(uint64t time) {
 //Pointer auf aktuellen Thread holen
 struct thread_t *thread= threadGetCurrThread();
 //die Zeit die geschlafen werden soll + die schon seit dem letzten Tick vergangen ist speichern
 thread->sleepTime= time + (timerGetCountNSecsPerTick() - timerGetCurrCountNSecs());
 //Thread in the Sleep-Queue des Timers packen
 timerAddThread(thread)
}
Und der Code des Timer (z.B. der PIT) würde ungefähr so aussehen:

Code: [Auswählen]

void timerIRQhandler() {
 if(sleepQueue) {
  //Pointer auf das 1. Element der Queue
  struct thread_t *t= sleepQueue;
  //Zeit für einen Tick vom 1. Element abziehen
  thread->sleepTime-= timerGetCountNSecsPerTick();
  //gegebenenfalls Threads aufwecken
  while(t->sleepTime <= timerGetCountNSecsPerTick()) {
   //1. Element der Queue entfernen
   sleepQueue= queueRemoveHead(sleepQueue);
   //1. Element der Queue in die CPU Sleep-Queue packen, da müsste dann auch die Zeit die der Timer der aktuellen CPU schon verbraten haben, nochmal drauf gerechnet werden, so wie oben
   schedAddThreadSleep(t);
   //Pointer aktualisieren
   t= sleepQueue;
  }
 }
}
Und in meinem Scheduler dann ungefähr sowas:

Code: [Auswählen]

void schedHandler() {
 if(thisCPU->sleepQueue) {
  struct thread_t *t= thisCPU->sleepQueue;
  //Zeit (dauer der gerade abgelaufenen Zeitscheibe) abziehen
  t->sleepTime-= thisCPU->lastTimeSlice;
  while(t->sleepTime <= NE_KONSTANTE_WO_ES_SICH_NICHT_MEHR_LOHNT_DAS_DER_THREAD_NOCHMAL_SCHLAEFT) {
   thisCPU->sleepQueue= queueRemoveHead(thisCPU->sleepQueue);
   schedAddThreadReady(t);
   t= thisCPU->SleepQueue;
  }
 }
}
So ich hoffe ich konnte mich jetzt genauer und besser Ausdrücken

Bist Du sicher das Du Boards mit Slot1 oder Sockel5/7 und mehreren CPUs hast?

Damals aus reiner Sammelleidenschaft und heute zum Testen meines OSs Damit ich mich ja auch mit den "schönsten" Seiten der x86 Architektur rumquählen darf

Ja. Solange Du den PIT nicht frei laufen lässt sondern immer mal dran "rumdrehst" bekommst Du Fehler die sich aufakkumulieren.

Naja, das lässt sich nicht wirklich vermeiden, wenn man eh so ne "alte" Krücke hat die nur den PIT und nicht mal den APIC unterstützt

Aber mal was anderes irgendwo habe ich mal gelesen das man, auch wenn der Local-APIC deaktiviert ist, einige Sachen benutzen kann?! Muss ich direkt nochmal nach gucken ob ich dazu nochmal was finde.

Für Spiele oder Multimediaprogramme würde ich ein Event-Object benutzen:

Der Punkt ist, meine Semaphore/Futex Idee wäre aber schneller Weil du nur noch ein "lock sub dword[event],1" machst und wenn das Event gefeuert hat, dann kannst du gleich weiter machen (weil der neue Wert größer 0 ist) und wenn nicht, dann rufst du den Kernel auf und legst dich in der Semaphore "schlafen" und das Event weckt dich dann mit dem Semaphore-Code wieder auf. Also mir gefällt diese Idee Aber ich wenn du mir sagst warum dir diese Idee nicht so gefällt kann ich die Nachteile vielleicht auch erkennen. Dazu haben wir den Thread ja!

Wenn Du diese "Performance Counter" nur zu "Statistischen Zwecken", z.B. zur Anzeige in einem Taskmanager, nutzen möchtest dann solltest Du Dir da erstmal keine zu großen Sorgen machen. User-Code sollte sich von so etwas nie abhängig machen.

Ich hab halt mal nen Bsp. für ne innere Schleife bei nem Game unter Windows gesehen und da haben die es so gemacht. Also mit QeueryPerformanceCounter. Da bin ich dann ganz frech davon ausgegangen das man das unter anderen Systemen ähnlich löst. Wenn ich mich recht entsinne, sollst du unter Linux sowas mit der "Zeit" machen, die geben die, glaub ich in ms oder noch genauer an und da sollst du die beiden Werte dann vergleichen, halt was ähnliches nur nicht so genau.

[erik.vikinger]

Hallo,

Irgendwie habe ich das Gefühl das wir aneinander vorbei reden

Ja, diesen Eindruck habe ich auch.

Wo ist jetzt der Unterschied ob du die Threads aufweckst, wenn ihre Zeit abgelaufen ist oder du sie in eine neue Queue packst?

Da ist kein wirklicher Unterschied, vermute ich mal, das ist ein Implementierungsdetail Deines Schedulers was für allen anderen Code in Deinem Kernel völlig egal ist (zumindest sein sollte wenn Du guten modularen Code schreibst).

Genauso verstehe ich nicht wo der Unterschied ist ob ich ne Zahl hab und den Thread aufwecke wenn diese Zahl bei "0" ist oder ob zwei Zahlen habe und den Thread aufwecke wenn beide gleich sind?!

In Deinem Beispiel modifizierst Du immer die Werte in der Queue, das dauert länger als ein Vergleich. Den Time-Counter wirst Du auf jeden Fall zählen müssen damit Du die Systemlaufzeit u.ä. hast. Das alles fällt natürlich weg wenn der HPET da ist.
Ich habe irgendwie den Eindruck das Deine Variante recht kompliziert ist aber vielleicht erblicke ich einfach nur nicht die simple Einfachheit.

In meiner Vorstellung müsste der PIT-IRQ-Handler ungefähr so aussehen:

Code: [Auswählen]

void IRQ_PIT(void)
{
  time_counter++;  // Software-Uhr zählen
  // oder falls man mit einer anderen Zeitbasis arbeitest, wovon ich abrate, dann eben: time_counter += PIT_IRQ_PERIPODE;

  while(true)
  {
  T_TimerQueueObject* const obj = TimerQueueGetFirst();  // hole das Objekt welches als nächstes abläuft, nur ne Referenz nicht aus der Queue entfernen
  if (obj->time == time_counter)  // prüfe ob das nächste Object nun dran ist, auf Gleichheit zu prüfen reicht wenn 'time_counter' nur inkrementiert wird
   {
     switch(obj->action)
      {
        case THREAD_RESUME:  // Thread aufwecken, z.B. nach einem sleep()
          ShedulerThreadResume(obj->thread);
          break;

        case SET_EVENT:  // Event einmalig generieren
          EventSet(obj->event);
          break;

        case SET_EVENT_PERIODIC:  // Event periodisch generieren
          EventSet(obj->event);
          obj->time = ????;  // neue absolute Zeit ausrechnen (z.B. wie in meinem Ursprungspost)
          TimerQueueAdd(obj);  // Object wieder in die Timer-Queue einfügen, eventuell auch ein neues Object generieren weil das aktuelle ja gleich gelöscht wird
          break;

        case KONTEXT_SWITCH:  // den aktuellen Thread gegen einen anderen austauschen (kann hier entfallen wenn zum Kontext-Switch der Local-APIC verwendet wird)
          obj->time += SchedulerThreadSwitch();  // Sheduler wechselt in einen anderen Thread (wie und in welchen Thread ist hier egal) und gibt die Länge der neuen Zeitscheibe in Timer-Ticks zurück
          TimerQueueAdd(obj);  // Object wieder in die Timer-Queue einfügen, eventuell auch ein neues Object generieren weil das aktuelle ja gleich gelöscht wird
          break;

        default:  // sonst Fehler!
          KernelError("unbekannte Timer-Aktion");
      }
     TimerQueueKillFirst();  // vorderstes Timer-Queue-Object entfernen, wurde gerade abgearbeitet
   }
  else  // noch nicht dran : IRQ ist fertig
   { return; }

  // Schleife so lange wiederholen bis alle Objekte, deren Zeit gekommen ist, aus der Queue abgearbeitet wurden!
  }
}Der IRQ-Handler für den HPET sieht sehr ähnlich aus (so will ich das auf meiner Plattform auch machen):

Code: [Auswählen]

void IRQ_HPET(void)
{
  while(true)
  {
  T_TimerQueueObject* const obj = TimerQueueGetFirst();  // hole das Objekt welches als nächstes abläuft, nur ne Referenz nicht aus der Queue entfernen
  const uint64 time_counter = HPET->counter;  // aktuellen Time-Counter aus den HPET auslesen (richtiger HW-Lese-Zugriff in MMIO)
  if (obj->time <= time_counter)  // prüfe ob das nächste Object nun dran ist, VORSICHT: das '<=' muss natürlich auch bei einem Überlauf noch funktionieren
   {
     /* Hier ist der selbe Code wie beim PIT-IRQ-Handler,
        nur 'case KONTEXT_SWITCH' geht nicht (wenn HPET vorhanden ist dann sollten auch Local-APICs da sein),
        sicher kann man das in _eine_ extra Funktion auslagern oder man merged beide IRQ-Handler mit ein paar #ifdef...#else...#endif */
   }
  else  // noch nicht dran : IRQ ist fertig
   {
     HPET->cmp_value = obj->time;  // absolute Zeit für das nächste Object in den HPET-Comparator schreiben, damit nächster IRQ zur rechten Zeit kommt
     if (obj->time > HPET->counter)  // prüfen ob das Object nicht doch schon dran ist, dann wäre der IRQ eventuell verloren/verpasst und das darf nicht sein
      { return; }  // nächstes Object ist noch nicht dran also IRQ fertig
     // nächstes Object ist doch schon dran also Schleife doch noch mal durchlaufen
   }

  // Schleife so lange wiederholen bis alle Objekte, deren Zeit gekommen ist, aus der Queue abgearbeitet wurden!
  }
}Wenn Du so in dieser Art vorgehst kannst Du alles andere in Deinem Kernel gleich lassen nur die unterschiedlichen Zeitbasen (100Hz bis 1000Hz beim PIT oder >=10MHz beim HPET) musst Du berücksichtigen, deshalb empfehle ich im Kernel nie von einer konkreten Zeitbasis auszugehen stattdessen sollte TICKS_PER_SECOND was sinnvolles liefern. Im User-Mode gilt das erst recht. Im Kernel gibt es eigentlich nichts was von konkreten Zeitspannen abhängig ist, außer die Zeitscheiben natürlich.

Also in einer Delta-Queue stehen nicht die Absoluten Werte, sondern immer der Abstand zum Vorgänger, so dass nur im 1. Element der Liste der Absolute Wert steht.

Das klingt nach viel rechnen. Wie soll man denn da effizient was einfügen (also nicht ans Ende anhängen)? Da muss man doch vor jedem Vergleich erst mal nen Absolutwert berechnen denn man dann mit dem neuen einzufügenden Absolutwert vergleichen kann und vor allem linear durch wandern. Falls ich Dich falsch verstanden hab dann erkläre mir das mal Bitte genauer. Spätestens wenn Du mit dem HPET arbeitest benötigst Du auf jeden Fall die absoluten Zeit-Werte, denn den HPET-Counter kann man nicht (so einfach) beeinflussen. Das ist der Vorteil meiner PIT-Variante, die ist bis auf ein paar winzige Unterschiede im IRQ-Handler mit der HPET-Variante exakt identisch. Die PIT-Variante emuliert quasi den HPET, nur mit gröberer Zeiteinteilung. Nur noch GetTicks() ist unterschiedlich, läuft aber in beiden Varianten auf einen simplen Speicherlesezugriff hinaus der wohl nur recht wenig kosten sollte.

Du möchtest quasi den Zählerwert vom PIT als Nachkommastellen für Deinen 18,2Hz-Software-Zähler nutzen? Interessante Idee aber ich glaube nicht das das viel nutzt genauer als auf ca. 55ms bekommst Du damit trotzdem keinen IRQ. Ich würde lieber zu einer höheren IRQ-Frequenz raten.

Auch hier kann ich dir nicht folgen

Ich will damit sagen das Du mit dem häufigen Auslesen des PIT-Zählers trotzdem keine genaueren IRQs bekommst, Du also trotzdem auf dem 55ms-Raster hängen bleibst.

Also folgender Pseudo-Code:

Code: [Auswählen]

.........So ich hoffe ich konnte mich jetzt genauer und besser Ausdrücken

Das macht irgendwie einen komplizierten Eindruck. Vielleicht täuscht mich das, aber wenn der Scheduler das Timer-Management berücksichtigen muss dann finde ich persönlich das irgendwie ungeschickt. Außerdem scheinst Du Dich auf verschiedene HW-Timer zu verlassen, die werden 100%-tig auseinander driften, das gibt sicher viel Freude.

Ja. Solange Du den PIT nicht frei laufen lässt sondern immer mal dran "rumdrehst" bekommst Du Fehler die sich aufakkumulieren.

Naja, das lässt sich nicht wirklich vermeiden, wenn man eh so ne "alte" Krücke hat die nur den PIT und nicht mal den APIC unterstützt

Doch das geht. Genau in diese Richtung geht ja das PIT-Konzept in meinem Ursprungspost, dort wird der PIT nur zur Initialisierung angefasst und danach geht alles nur noch in Software (im PIT-IRQ-Handler, siehe oben).

Der Punkt ist, meine Semaphore/Futex Idee wäre aber schneller Weil du nur noch ein "lock sub dword[event],1" machst und wenn das Event gefeuert hat, dann kannst du gleich weiter machen (weil der neue Wert größer 0 ist) und wenn nicht, dann rufst du den Kernel auf und legst dich in der Semaphore "schlafen" und das Event weckt dich dann mit dem Semaphore-Code wieder auf.

Ich persönlich bin der Meinung das eine zusätzliche Ebene (schlafen legen und aufwecken musst Du den Thread ja trotzdem) auch zusätzliche Zeit kostet.

Ich hab halt mal nen Bsp. für ne innere Schleife bei nem Game unter Windows gesehen und da haben die es so gemacht. Also mit QeueryPerformanceCounter. Da bin ich dann ganz frech davon ausgegangen das man das unter anderen Systemen ähnlich löst. Wenn ich mich recht entsinne, sollst du unter Linux sowas mit der "Zeit" machen, die geben die, glaub ich in ms oder noch genauer an und da sollst du die beiden Werte dann vergleichen, halt was ähnliches nur nicht so genau.

Klingt nach aktivem warten, sowas sollte man nur für wirklich kurze Zeiten machen, und das mit dem ausrechnen der sleep-Zeit ist IMHO genauso ungeschickt (was macht man da mit negativen Ergebnissen).

Bist Du sicher das Du Boards mit Slot1 oder Sockel5/7 und mehreren CPUs hast?

Damals aus reiner Sammelleidenschaft und heute zum Testen meines OSs Damit ich mich ja auch mit den "schönsten" Seiten der x86 Architektur rumquählen darf

Wo hast Du denn z.B. das Board mit mehreren Sockel 5 her? Im normalen Handel gab es das bestimmt nicht. Laut http://de.wikipedia.org/wiki/Sockel_5 ist in den Sockel 5 CPUs immer ein Local-APIC drin, bei allen neueren CPUs sowieso.
Aber wenn Du so auf "rumquählen" stehst dann kann ich Dir versichern das Deine Wahl für x86 genau richtig war und sicher noch für lange Zeit bleiben wird.


Grüße
Erik

[FlashBurn]

In Deinem Beispiel modifizierst Du immer die Werte in der Queue, das dauert länger als ein Vergleich. Den Time-Counter wirst Du auf jeden Fall zählen müssen damit Du die Systemlaufzeit u.ä. hast. Das alles fällt natürlich weg wenn der HPET da ist.

Ich wusste zwar auch nicht immer was mit einer Delta-Queue anzufangen, aber so wie ich dein Wissen einschätze, habe ich eigentlich gedacht das du das Prinzip kennst.

Also bei deiner Methode, musst du doch auch den Thread in eine sortierte Queue reinpacken. Also musst du auch dort linear, ein Element nach dem Anderen durchgehen.

Ich geb dir mal folgenden Pseudo-Code:

Code: [Auswählen]

void queueAddDelta(struct thread_t *t) {
 struct thread_t *ptr= deltaQueue;

 while(ptr->next) {
  if(ptr->sleepTime >= t->sleepTime) {
   ptr->sleepTime-= t->sleepTime;
   t->next= ptr;
   t->prev= ptr->prev;
   ptr->prev= t;
   if(t->prev) {
    t->prev->next= t;
   } else {
    sleepQueue= t;
   }
   return;
  } else {
   t->sleepTime-= ptr->sleepTime;
  }
  ptr= ptr->next;
 }

 ptr->next= t;
 t->prev= ptr;
 t->next= 0;
}
Ich hoffe dieser Code (ist erstmal fehlerfrei ) und du verstehst jetzt mein Prinzip. Ich muss immer nur vom Head einer Queue einen Wert abziehen, ist also genauso effizient wie dein Vergleich. Denn ob ich einen Vergleich mache (was intern auch nur ne Subtraktion ist) oder ob ich etwas abziehen und bei den Flags dann auf 0 prüfe (was unter C leider nicht möglich ist, glaub ich jedenfalls) ist im Endeffekt das selbe!

Im Endeffekt sind unsere Systeme sich schon ähnlich nur das ich den PIT so langsam wie möglich laufen lassen möchte (bzw. ihn sogar ganz deaktivieren, wenn er nicht gebraucht wird). Wenn ich dein Konzept mit den Events nutze, dann würde ich sogar von meinem PerformanceCounter weggehen, aber eigentlich müsste das OS so eine Funktion bereitstellen und dafür war ja auch mal der TSC gedacht, bevor Intel erst hinterher festgestellt hat, das es dumm ist wenn sich die Aktualisierungsrate mit der Frequenz ändert

Das klingt nach viel rechnen. Wie soll man denn da effizient was einfügen (also nicht ans Ende anhängen)? Da muss man doch vor jedem Vergleich erst mal nen Absolutwert berechnen denn man dann mit dem neuen einzufügenden Absolutwert vergleichen kann und vor allem linear durch wandern. Falls ich Dich falsch verstanden hab dann erkläre mir das mal Bitte genauer. Spätestens wenn Du mit dem HPET arbeitest benötigst Du auf jeden Fall die absoluten Zeit-Werte, denn den HPET-Counter kann man nicht (so einfach) beeinflussen. Das ist der Vorteil meiner PIT-Variante, die ist bis auf ein paar winzige Unterschiede im IRQ-Handler mit der HPET-Variante exakt identisch. Die PIT-Variante emuliert quasi den HPET, nur mit gröberer Zeiteinteilung. Nur noch GetTicks() ist unterschiedlich, läuft aber in beiden Varianten auf einen simplen Speicherlesezugriff hinaus der wohl nur recht wenig kosten sollte.

Die Delta-Queue habe ich ja oben schon erläutert. Was ich noch nicht ganz verstehe ist, das du sachen bemängelst die bei deinem System doch genauso sind. Du hättest nur den Vorteil, das du mit absoluten Werten ne andere Struktur als ne Liste (z.B. nen RB-Tree) nehmen könntest, aber auch du musst sortiert eintragen (was in einer Liste nun mal linear ist) oder du müsstest bei jedem IRQ Aufruf die komplette Liste durch gehen, was alles andere als optimal ist.

Was das Beeinflussen des HPET-Counters betrifft. Wenn ich das alles richtig Verstanden habe, dann gibt man nun nen Comperator (einen Wert, in dem Fall nen absoluten) an und der HPET feuert dann nen IRQ wenn der Counter diesen Wert erreicht hat.
Ich würde das wieder über ne Delta-Queue lösen, einfach auf den alten Wert der schon drin steht den neuen Wert vom 1. Element der Delta-Queue drauf addieren und fertig. Ganz simpel

Ich will damit sagen das Du mit dem häufigen Auslesen des PIT-Zählers trotzdem keine genaueren IRQs bekommst, Du also trotzdem auf dem 55ms-Raster hängen bleibst.

Dann hast du leider mein Konzept immernoch nicht verstanden

Ich lese den Counter aus um zu wissen wieviel Zeit seit dem letzten PIT IRQ schon wieder vergangen ist, damit ich diese auf die Zeit, die der Thread schlafen will drauf rechnen kann. Denn der IRQ Handler vom PIT zieht immer 55,4ms ab, egal wann der Thread schlafen gelegt wurde. So sichere ich das der Thread mind. genauso lange schläft wie er das vor hat.

Um zu sichern, das ein Thread auch genauer als das 55ms Raster schlafen kann, habe ich ja eine per CPU Sleep-Queue die für alles <55ms zuständig ist und da ich da wieder mit ner Delta-Queue arbeite, ist auch mein Jitter nicht so schlimm. Denn der kann sich ja nicht immer wieder aufsummieren (jedenfalls nicht was die Sleep-Queue betrifft).

Das macht irgendwie einen komplizierten Eindruck. Vielleicht täuscht mich das, aber wenn der Scheduler das Timer-Management berücksichtigen muss dann finde ich persönlich das irgendwie ungeschickt. Außerdem scheinst Du Dich auf verschiedene HW-Timer zu verlassen, die werden 100%-tig auseinander driften, das gibt sicher viel Freude.

Wie gesagt, da der Scheduler-Timer nur für alles <55ms zuständig ist, kann eigentlich nicht viel passieren. Gerade da ein Thread mit normaler Prio bei mir 30ms als Zeitscheibe bekommt, wird der Scheduler im average-case 2mal aufgerufen und der Jitter ist dort selbst mit PIT "gerade" mal (3*832ns für lesen beim reinpacken des Threads + 5*832ns pro Scheduleraufruf= 13*832ns=) 10816ns= 10,8µs, was ich für verdammt gut für so ne alte Krücke halte Wenn du jetzt noch den APIC-Timer für den Scheduler nimmst, dann wird es noch genauer!

Das einzige Problem was ich haben werde, sind halt PCs die nur nen PIT haben, da summiert sich dann der Jitter auf, obwohl ich gerade ganz spontan mit dem Gedanken spiele in dem Fall die RTC dafür zu mißbrauchen Also das ich die RTC für´s Grobe nutze und den PIT für´s "feine", dann summiert sich mein Jitter auch nicht auf. Muss ich mal sehen ob ich das irgendwie vernünftig über mein Interface umsetzen kann.

Ich persönlich bin der Meinung das eine zusätzliche Ebene (schlafen legen und aufwecken musst Du den Thread ja trotzdem) auch zusätzliche Zeit kostet.

Ja, aber nur wenn das Event noch nicht ausgelöst wurde. Was willst du denn dann machen oder besser gesagt, wie willst du dann warten. Du musst doch den Thread auch schlafen legen (ich hätte vielleicht sagen sollen, das er so lange wartet bis er aufgeweckt wird und nicht eine bestimmte Zeit schläft).

Klingt nach aktivem warten, sowas sollte man nur für wirklich kurze Zeiten machen, und das mit dem ausrechnen der sleep-Zeit ist IMHO genauso ungeschickt (was macht man da mit negativen Ergebnissen).

Ich hab von Spieleprogrammierung keine Ahnung, obwohl mich ne 3D-Engine auch reizen würde
Ist halt das einzige was ich kenne wo dieser PerformanceCounter verwendet wurde, aber da du mich ja inzwischen von deinem Event-System überzeugt hast, kann ich das ja erstmal vergessen

Wo hast Du denn z.B. das Board mit mehreren Sockel 5 her? Im normalen Handel gab es das bestimmt nicht. Laut http://de.wikipedia.org/wiki/Sockel_5  ist in den Sockel 5 CPUs immer ein Local-APIC drin, bei allen neueren CPUs sowieso.

Da muss ich dich dann mal ganz frech nach deinem Alter fragen und wie lange du dich schon mit der OS Programmierung auf x86 beschäftigst

Denn den APIC haben die alle drin, der wird aber immer deaktiviert, Ausnahmen sind halt Dual-Sockel-Boards. Selbst bei nem Athlon XP wurde das noch meistens gemacht. Das war ein Grund warum ich mir mal nen neues Board geholt habe, weil EPOX damals gesagt hat, es bringt nur Probleme und deswegen lassen sie den APIC deaktiviert.
Aber das beste war die Begründung, der IO-APIC macht nur Probleme, da frag ich mich dann wieso der APIC nicht genutzt werden kann ohne das ein IO-APIC da ist!?

Wenn du willst mache ich dir nen Foto von dem einen Sockel5 Board was ich hier habe? Bei dem hast du sogar recht, das muss irgendeins aus nem Server sein. Denn ich habe bis heute kein Netzteil dafür und weiß erst seit dem Wochenende dass das mal nen kleiner Standard war (nen erweiterter AT).
Ein anderes ist noch bei meinen Eltern zu Hause (da ist mein großes Lager ). Das verwendet sogar die defaul Konfiguration der MPS. Sockel 7 habe ich dann auch nochmal 2 und 1 Sockel 8 Board habe ich doch total unterschlagen (alles natürlich Dual-Sockel).

Aber wenn Du so auf "rumquählen" stehst dann kann ich Dir versichern das Deine Wahl für x86 genau richtig war und sicher noch für lange Zeit bleiben wird. Wink

Darauf würde ich dir mit nem anderen Hobby von mir antworten. Andere sehen Triathlon auch nur als Quählerei an, ich sehe sowas was Herausforderung und wenn man es geschafft hat, dann kann man auch Stolz auch sich sein. Was soll ich mir denn leichte Ziele setzen?! Dann reicht es ja das neueste Spiel durch zu zocken, aber das macht nicht halb so viel Spaß, man lernt nicht so viel dabei (von der Erfahrung mal ganz abgesehen) und es gibt verdammt viele die aus auch schaffen.
Um es mal so zu sagen, OS Programmierung ist doch ne Extreme Sportart unter den Programmierern

[erik.vikinger]

Hallo,

Ich wusste zwar auch nicht immer was mit einer Delta-Queue anzufangen, aber so wie ich dein Wissen einschätze, habe ich eigentlich gedacht das du das Prinzip kennst.
Also bei deiner Methode, musst du doch auch den Thread in eine sortierte Queue reinpacken. Also musst du auch dort linear, ein Element nach dem Anderen durchgehen.

Ich denke schon das ich das Prinzip der Delta-Queue verstanden hab, aber ich bin der Meinung das die für diesen Zweck eher ungeeignet ist.
Wenn Du auf dem vordersten Element rumrechnest dann kommt auch immer ein Speicherschreibzugriff zusätzlich, gegenüber einem Vergleich, dazu. Zum prüfen, im IRQ-Handler, ob das vorderste Element nun dran ist müssen wir beide auch nur das vorderste Element anfassen (Du lesen und schreiben, ich nur lesen), das komplette durchgehen der Liste ist dafür nicht erforderlich (siehe meinen IRQ-Handler-Code). Zum beliebigen Einfügen eines neuen Elements musst Du Deine Delta-Queue in jedem Fall linear von vorne an durchlaufen bis die richtige Stelle gefunden ist, ich dagegen kann diese Liste als Baum realisieren und kann daher sehr viel schneller Einfügen. Das Entfernen des vordersten Elementes, also das Element unten links in meinem Baum, ist nur minimal komplizierter als bei Deiner Delta-Queue.

Ich weiß wovon ich schreibe, ich habe diese Baum-Variante schon mal implementiert (vor knapp 9 Jahren), in purem x86-32Bit-Assembler, mit absoluten 64Bit-Zeitwerten. Das war für ne Industrie-Maschine mit vielen Pneumatik-Zylindern, Motoren und haufenweise anderem Zeugs. Für jede Bewegung wurde ein TimeOut-Timer gestartet so das dort oft über 100 Timer (mit Laufzeiten von etwa 200ms bis etwa 3s, aber auch ein paar Timern im Stundenbereich) gleichzeitig aktiv waren. Da die meisten der Timer wieder gelöscht wurden bevor sie abgelaufen sind, da die Bewegungen ja normalerweise rechtzeitig fertig waren (anders wäre es ein Fehler gewesen), und dann wieder neue Timer gestartet wurden war das einfügen von Timern ein essenziell wichtiger Vorgang. Die gelöschten Timer wurden nicht aus dem Baum entfernt, das erschien mir zu kompliziert, (entfernt habe ich solche Timer nur wenn sie nur ein Kind haben) sondern einfach deaktiviert und wenn sie dann abgelaufen sind (dann haben die garantiert maximal nur ein Kind) einfach ohne weitere Aktion gelöscht. Zu dem Timing-System gibt es noch einen Message-Handler und einen Event-Handler welche beide auf dem Timing-System aufsetzen (für TimeOuts usw.). Auch ein kooperativer Thread-Scheduler war mit dabei, der wiederum vom Timing-System benutzt wurde. Mit diesem System bin ich auf einem K6-500MHz auf knapp 600'000 Thread-Wechsel pro Sekunde gekommen, die ungefähr 20 Threads haben auch was sinnvolles getan.

Ich geb dir mal folgenden Pseudo-Code:

Code: [Auswählen]

.......Ich hoffe dieser Code (ist erstmal fehlerfrei ) und du verstehst jetzt mein Prinzip.

Ähm, nein, leider überhaupt gar nicht.
Deinen Code hab ich ehrlich gesagt gar nicht verstanden, Bitte poste ihn noch mal mit reichlich und aussagekräftigen Kommentaren dabei. Was mich stört ist das Du da das einzufügende Element ständig modifizierst und auch das Queue-Element vor (wirklich davor? oder habe ich mich da verschaut? ) welches das neue kommt wird auch modifiziert. In meiner Variante wird nur die richtige Stelle gesucht (nur Vergleiche keine Modifikationen) und dann eingefügt (simple Pointer-Magie, so wie bei Dir), egal ob lineare sortierte Liste oder sortierter Baum, schon allein deshalb (keine zusätzlichen/verteilten Schreibzugriffe) sollte meine Variante schneller sein.

Ich muss immer nur vom Head einer Queue einen Wert abziehen,

Du meinst im IRQ-Handler?

ist also genauso effizient wie dein Vergleich. Denn ob ich einen Vergleich mache (was intern auch nur ne Subtraktion ist) oder ob ich etwas abziehen und bei den Flags dann auf 0 prüfe (was unter C leider nicht möglich ist, glaub ich jedenfalls) ist im Endeffekt das selbe!

Beim richtigen rechnen kommt eben noch der Speicherschreibzugriff dazu. Da Du einzelne Werte (viel kleiner als eine Cache-Line), quer über den RAM verteilt, modifizierst könnte das schon recht gut bremsen. Auf den Cache kannst Du dabei jedenfalls nicht zählen, der dürfte IMHO eher bremsen weil er versucht komplette Cache-Lines zu lesen und die modifizierten Cache-Lines dann wieder komplett schreiben will (oder sie im Cache liegen bleiben und dort wertvollen Platz kosten).

Im Endeffekt sind unsere Systeme sich schon ähnlich

Ja, nur das ich mit absoluten Werten arbeiten will und diese IMHO weniger (Rechen-)Arbeit machen.

nur das ich den PIT so langsam wie möglich laufen lassen möchte (bzw. ihn sogar ganz deaktivieren, wenn er nicht gebraucht wird).

Wenn Du den PIT abschalten möchtest musst Du das in GetTicks() berücksichtigen oder soll dann in Deinem OS die Zeit stehen bleiben? Wenn es Dir aufs Energiesparen ankommt würde ich eher dazu raten die PIT-Frequenz zu reduzieren, alle 100ms die CPU für ein paar Mikrosekunden aufzuwecken dürfte nur wenig Energie kosten. Wenn Du deutlich besseres Power-Management willst (was eh erst auf recht modernen CPUs und Boards geht) dann solltest Du auch den HPET voraussetzen (der braucht zum laufen fast gar nichts an Energie).

aber eigentlich müsste das OS so eine Funktion bereitstellen und dafür war ja auch mal der TSC gedacht, bevor Intel erst hinterher festgestellt hat, das es dumm ist wenn sich die Aktualisierungsrate mit der Frequenz ändert

Das der TSC von der CPU-Core-Frequenz abhängig ist finde ich gar nicht so schlecht, das macht ihn mit den anderen Performance-Monitoring-Counters (z.B. Anzahl der abgearbeiteten Befehle, nur Integer-Befehle, nur FPU-Befehle, Cache-Hits usw.) vergleichbar. Der TSC ist nur zum Messen von kleinen Zeiträumen gedacht, für präzise Langzeitmessungen gibt es ja den HPET oder die RTC.

Was ich noch nicht ganz verstehe ist, das du sachen bemängelst die bei deinem System doch genauso sind.

Ich habe bemängelt das bei der Delta-Queue mehr zu rechnen ist und das Du nicht effizient neue Elemente einfügen kannst. Das sind beides Dinge die mit absoluten Zeit-Werten nicht auftreten und das Einfügen lässt sich noch zusätzlich durch die Benutzung eines Baumes deutlich beschleunigen.

Du hättest nur den Vorteil, das du mit absoluten Werten ne andere Struktur als ne Liste (z.B. nen RB-Tree) nehmen könntest, aber auch du musst sortiert eintragen (was in einer Liste nun mal linear ist)

Absolute Zeitwerte haben den Vorteil das man diese immer beliebig miteinander Vergleichen kann (also jeden mit jeden) wogegen bei relativen Zeit-Werten immer der Bezugspunkt mit eingerechnet werden muss. Wegen der beliebigen Vergleichbarkeit der absoluten Zeitwerte muss man bei der linearen sortierten Liste auch nicht zwingenst jedes Element anfassen, da könnte man eventuell in großen Sprüngen über die Liste gehen bis man in der Nähe des gewünschten Ziels ist und dann immer feiner suchen (dazu bräuchte man natürlich einen effizienten wahlfreien Zugriff auf die Liste). Zumindest stehen mit den absoluten Zeitwerten ein menge Möglichkeiten offen, es gibt bestimmt noch was besseres als nen einfacher Baum, wogegen bei den relativen Zeitwerten der erforderliche Bezugspunkt einiges ziemlich kompliziert macht.

oder du müsstest bei jedem IRQ Aufruf die komplette Liste durch gehen, was alles andere als optimal ist.

Zumindest da sind wir uns offensichtlich einig.

Was das Beeinflussen des HPET-Counters betrifft. Wenn ich das alles richtig Verstanden habe, dann gibt man nun nen Comperator (einen Wert, in dem Fall nen absoluten) an und der HPET feuert dann nen IRQ wenn der Counter diesen Wert erreicht hat.

Exakt. Der HPET feuert nur bei Gleichheit, weshalb man mit Zeitwerten die gleich dran sind etwas aufpassen muss (aber das sollte der HPET-IRQ-Handler aus meinem letzten Post theoretisch hinbekommen).

Ich würde das wieder über ne Delta-Queue lösen, einfach auf den alten Wert der schon drin steht den neuen Wert vom 1. Element der Delta-Queue drauf addieren und fertig. Ganz simpel

Ganz simpel finde ich das nicht. Zum draufaddieren musst Du vorher lesen und das wird in einem Non-Cachable-Bereich eher langsam sein. Wenn Du zum Schluss eh absolute Werte brauchst, warum dann so viel Mühe um immer mit relativen Werten zu arbeiten?

Ich will damit sagen das Du mit dem häufigen Auslesen des PIT-Zählers trotzdem keine genaueren IRQs bekommst, Du also trotzdem auf dem 55ms-Raster hängen bleibst.

Dann hast du leider mein Konzept immernoch nicht verstanden

Ganz offensichtlich.

Ich lese den Counter aus um zu wissen wieviel Zeit seit dem letzten PIT IRQ schon wieder vergangen ist, damit ich diese auf die Zeit, die der Thread schlafen will drauf rechnen kann. Denn der IRQ Handler vom PIT zieht immer 55,4ms ab, egal wann der Thread schlafen gelegt wurde. So sichere ich das der Thread mind. genauso lange schläft wie er das vor hat.
Um zu sichern, das ein Thread auch genauer als das 55ms Raster schlafen kann, habe ich ja eine per CPU Sleep-Queue die für alles <55ms zuständig ist und da ich da wieder mit ner Delta-Queue arbeite, ist auch mein Jitter nicht so schlimm. Denn der kann sich ja nicht immer wieder aufsummieren (jedenfalls nicht was die Sleep-Queue betrifft).

Das sieht in meinen Augen irgendwie extrem Aufwendig aus. Ich verstehe nicht welchen Vorteil Du Dir von diesem Aufwand erhoffst. Das ganze kann man doch eigentlich ganz einfach und simpel Lösen.

Wie gesagt, da der Scheduler-Timer nur für alles <55ms zuständig ist,

Also ich finde es ungeschickt wenn der Scheduler was mit Timing zu tun hat. Ich persönlich bin der Meinung das der Schuler nur für die Verwaltung der Threads (und deren Zustände wie lauffähig, blockiert, schlafend usw.) und für den Kontext-Switch zuständig ist. Ein ordentlicher Scheduler, der mehrere CPUs fair + schnell über die Threads verteilt und dafür effiziente + leistungsfähige Management-Funktionen bietet, ist ansich schon kompliziert genug, da muss man nicht auch noch fremde Aufgaben mit rein packen.

Gerade da ein Thread mit normaler Prio bei mir 30ms als Zeitscheibe bekommt, wird der Scheduler im average-case 2mal aufgerufen

Auf einem normalen System dürfte kaum eine Zeitscheibe aufgebraucht werden, üblicherweise läuft ein Thread ziemlich schnell auf eine blockierende Anfrage (aus Datei lesen, ins Netzwerk senden oder auf User-Eingabe warten). Nur Threads die wirklich was zu rechnen haben werden ihre Zeitscheiben aufbrauchen. Die Länge der Zeitscheiben zu optimieren bringt IMHO nicht viel, da ist ein effizienter Kontext-Switch schon nützlicher.

und der Jitter ist dort selbst mit PIT "gerade" mal (3*832ns für lesen beim reinpacken des Threads + 5*832ns pro Scheduleraufruf= 13*832ns=) 10816ns= 10,8µs, was ich für verdammt gut für so ne alte Krücke halte Wenn du jetzt noch den APIC-Timer für den Scheduler nimmst, dann wird es noch genauer!

Von was für einen Jitter schreibst Du da eigentlich? Die exakte Länge der Zeitscheiben ist eher unkritisch, 10% hin oder her dürften da gar nichts machen. Viel wichtiger ist das wenn ein Thread mit ner hohen Priorität zum Zeitpunkt X wieder aufgeweckt werden soll dass das auch möglichst zum rechten Zeitpunkt passiert und dieser Thread dann auch einen anderen Thread mit niedrigerer Priorität verdrängen kann.

Das einzige Problem was ich haben werde, sind halt PCs die nur nen PIT haben, da summiert sich dann der Jitter auf,

Nur wenn Du den PIT nicht frei laufen lässt. In der PIT-Variante meines Ursprungsposts wird auch nichts aufakkumuliert.

obwohl ich gerade ganz spontan mit dem Gedanken spiele in dem Fall die RTC dafür zu mißbrauchen Also das ich die RTC für's Grobe nutze und den PIT für's "feine", dann summiert sich mein Jitter auch nicht auf. Muss ich mal sehen ob ich das irgendwie vernünftig über mein Interface umsetzen kann.

Mehrere unabhängige Timer (die RTC ist ja auch ein Timer) zu benutzen halte ich für keine gute Idee. Du wirst ne Menge Aufwand treiben müssen um das auch bei sehr langer Laufzeit (über Monate oder gar Jahre, oder baust Du ein OS mit konstruktiv begrenzter Laufzeit? ) synchron zu halten.
Genau deshalb stelle ich mir die Frage: Warum Kompliziert wenn es doch auch so einfach geht? Was erhoffst Du Dir davon? Wo genau siehst Du den Vorteil?
Relative Zeitwerte, mehrere unabhängige Timer und verwische Zuständigkeiten in den SW-Modulen. Klar das kann man alles realisieren aber wenn Du diesen Aufwand treiben möchtest dann erwartest Du doch auch was, ich sehe das nur eben nicht, das müsstest Du mir erklären.

Ich persönlich bin der Meinung das eine zusätzliche Ebene (schlafen legen und aufwecken musst Du den Thread ja trotzdem) auch zusätzliche Zeit kostet.

Ja, aber nur wenn das Event noch nicht ausgelöst wurde. Was willst du denn dann machen oder besser gesagt, wie willst du dann warten.

Wenn der Event noch nicht ausgelöst wurde (was sich ja einfach feststellen lässt) dann wird die aktuelle Thread-ID im Event-Object als wartend vermerkt und der Thread einfach schlafen gelegt. Wenn das Event dann irgendwann ausgelöst wird dann muss der Thread wieder geweckt werden und wenn kein Thread wartet dann eben nicht. Nur auf einem SMP-System muss man da etwas mit der Atomizität dieser Aktionen aufpassen.

(ich hätte vielleicht sagen sollen, das er so lange wartet bis er aufgeweckt wird und nicht eine bestimmte Zeit schläft)

Ja, davon bin ich ausgegangen. Wobei man als zusätzliches Feature ja noch ein optionales TimeOut einbauen kann. Meine damalige Implementierung kann das.

Da muss ich dich dann mal ganz frech nach deinem Alter fragen und wie lange du dich schon mit der OS Programmierung auf x86 beschäftigst

Das findest Du in meinem Forums-Profil und meiner Wiki-Benutzer-Seite. Wieso fragst Du das, weil ich wissen möchte wo Du so exotische Boards her hast?

Denn den APIC haben die alle drin, der wird aber immer deaktiviert,

Das wusste ich nicht das die APICs vom BIOS per Default deaktiviert werden.
Meine Erfahrung mit solchen Boards habe ich mit 4x PentiumPro 200MHz 1MB-L2-Cache unter Windows NT gemacht und ich kann Dir sagen das Windows NT verdammt schlecht skaliert hat. Das Board und die CPUs hatten zwar alle APICs aber Windows NT konnte damit nicht allzu viel anfangen. Der IO-APIC war wimre komplett deaktiviert und die Local-APICs wurden von Windows NT nur mit dem absolut notwendigsten (für SMP) benutzt.

Wenn du willst mache ich dir nen Foto von dem einen Sockel5 Board was ich hier habe?

Ja, gerne. Was haste denn für Prozies drauf? Falls Du das Board nicht in Betrieb bekommst würde ich mich dafür interessieren.

Um es mal so zu sagen, OS Programmierung ist doch ne Extreme Sportart unter den Programmierern

Full ACK!
Aber man kann den Triathlon bei normalem Wetter (leicht Bewölkt, kein Regen und kein Wind) in normaler Umgebung (Flachland) durchziehen oder, wenn man masochistisch veranlagt ist, bei extremsten Wetter (>100 l Regen pro m² und h mit Windstärke 8 ) und in unpassenster Umgebung (Gebirge).
SCNR


Grüße
Erik

[FlashBurn]

Wenn Du auf dem vordersten Element rumrechnest dann kommt auch immer ein Speicherschreibzugriff zusätzlich, gegenüber einem Vergleich, dazu. Zum prüfen, im IRQ-Handler, ob das vorderste Element nun dran ist müssen wir beide auch nur das vorderste Element anfassen (Du lesen und schreiben, ich nur lesen), das komplette durchgehen der Liste ist dafür nicht erforderlich (siehe meinen IRQ-Handler-Code). Zum beliebigen Einfügen eines neuen Elements musst Du Deine Delta-Queue in jedem Fall linear von vorne an durchlaufen bis die richtige Stelle gefunden ist, ich dagegen kann diese Liste als Baum realisieren und kann daher sehr viel schneller Einfügen. Das Entfernen des vordersten Elementes, also das Element unten links in meinem Baum, ist nur minimal komplizierter als bei Deiner Delta-Queue.

Also ich wüde wahrscheinlich sogar ne Delta-Queue in einen Baum packen können
Was das Entfernen betrifft, ist meine Queue klar schneller, besonders wenn der Baum immer voller wird. Denn du versaust dir da den Cache, durch die "vielen" (ein paar reichen ja) Speicherzugriffe und die "längere" (sollte eigentlich unwesentlich sein) addiert sich ja auch, wenn du doch mal einige Elemente Entfernen musst. Rein theoretisch betrachtet ist die Queue in dem Fall O(1) und der Baum O(log n).

... Mit diesem System bin ich auf einem K6-500MHz auf knapp 600'000 Thread-Wechsel pro Sekunde gekommen, die ungefähr 20 Threads haben auch was sinnvolles getan.

Die Zahl erschein mir irgendwie arg hoch. Denn das macht gerade mal 833 Takte pro Thread und so ein Thread-Wechsel kostet ja doch einiges an Zeit und Performance (oder liefen die alle in einem Adressraum?).

Deinen Code hab ich ehrlich gesagt gar nicht verstanden, Bitte poste ihn noch mal mit reichlich und aussagekräftigen Kommentaren dabei. Was mich stört ist das Du da das einzufügende Element ständig modifizierst und auch das Queue-Element vor (wirklich davor? oder habe ich mich da verschaut? ) welches das neue kommt wird auch modifiziert. In meiner Variante wird nur die richtige Stelle gesucht (nur Vergleiche keine Modifikationen) und dann eingefügt (simple Pointer-Magie, so wie bei Dir), egal ob lineare sortierte Liste oder sortierter Baum, schon allein deshalb (keine zusätzlichen/verteilten Schreibzugriffe) sollte meine Variante schneller sein.

Der "Witz" bei einer Delta-Queue ist doch, das du nur die Abstände zwischen den Elementen speicherst und nicht die direkten (absoluten) Werte. Ich weiß gar nicht mehr in welchem Zusammenhang ich das damals gelernt habe, aber kann schon sein, das es was fürs Zeitmanagement war.
Was du ja schon richtig erkannt hast, ist das deine Lösung nur ein (oder mehrere) Pointer ändern und meiner bis zu 2 Werte und ein paar Pointer, den einen Wert dafür ständig (im worst-case).
Um deine eine Frage zu beantworten, du musst den Abstand zwischen dem einzufügendem Element und dem Element danach ändern, den der Abstand zw. den beiden ist ja anders.

Code: [Auswählen]

void queueAddDelta(struct thread_t *t) {
//head der queue
struct thread_t *ptr= deltaQueue;
//so lange durch gehen, bis kein element mehr kommt oder wir unsere position gefunden haben
while(ptr->next) {
  //wenn der abstand bis zum nächsten element größer ist, als unser abstand zum vorherigen element, dann haben wir unsere position (das schließt gleich den fall ein, das wir der neue head werden)
  if(ptr->sleepTime >= t->sleepTime) {
   //abstand zum nachfolger aktualisieren
   ptr->sleepTime-= t->sleepTime;
   //ptr wird unser nachfolger
   t->next= ptr;
   //unser vorgänger ist der vorgänger von ptr
   t->prev= ptr->prev;
   //ptr´s vorgänger werden wir
   ptr->prev= t;
   //wir müssen noch den fall betrachten das wir der neue head sind oder halt mitten drin
   if(t->prev) {
    t->prev->next= t;
   } else {
    sleepQueue= t;
   }
   //fertsch, wir können endlich raus hier ;)
   return;
  } else {
   //falls wir unsere position noch nicht gefunden haben, dann müssen wir zumindest unsere zeit (den abstand sozusagen) aktualisieren
   t->sleepTime-= ptr->sleepTime;
  }
  //ab zum nächsten eintrag in der liste
  ptr= ptr->next;
}
//dummerweise sind wir das letzte (element ;) )
ptr->next= t;
t->prev= ptr;
t->next= 0;
}


Du meinst im IRQ-Handler?

Jap.

Beim richtigen rechnen kommt eben noch der Speicherschreibzugriff dazu. Da Du einzelne Werte (viel kleiner als eine Cache-Line), quer über den RAM verteilt, modifizierst könnte das schon recht gut bremsen. Auf den Cache kannst Du dabei jedenfalls nicht zählen, der dürfte IMHO eher bremsen weil er versucht komplette Cache-Lines zu lesen und die modifizierten Cache-Lines dann wieder komplett schreiben will (oder sie im Cache liegen bleiben und dort wertvollen Platz kosten).

Wie oben schon geschrieben, solltest du doch durch die "vielen" Zugriffe (bei einem Baum z.b.) auch den Cache trashen, oder? Aber ansonsten hast du recht.

Wenn Du den PIT abschalten möchtest musst Du das in GetTicks() berücksichtigen oder soll dann in Deinem OS die Zeit stehen bleiben? Wenn es Dir aufs Energiesparen ankommt würde ich eher dazu raten die PIT-Frequenz zu reduzieren, alle 100ms die CPU für ein paar Mikrosekunden aufzuwecken dürfte nur wenig Energie kosten. Wenn Du deutlich besseres Power-Management willst (was eh erst auf recht modernen CPUs und Boards geht) dann solltest Du auch den HPET voraussetzen (der braucht zum laufen fast gar nichts an Energie).

Naja, wozu brauche ich denn die Zeit noch, außer um solche Events auszuführen? Denn für die Uhr wollte ich eigentlich (also mache ich schon) die RTC nehmen, die wird einfach jede Sekunde einmal aktualisiert. Aber gerade fällt mir ein, das einige Dateisysteme die Zeit bis auf die ms genau wollen, oder?

Der TSC ist nur zum Messen von kleinen Zeiträumen gedacht, für präzise Langzeitmessungen gibt es ja den HPET oder die RTC.

Naja, die RTC ist nicht wirklich gut für sowas geeignet (meine bescheidene Meinung) und du immer mit deinem HPET Ich weiß auch das ein Auto besser ist um nach Hause zu fahren (und meistens weniger stressig), aber ich kann mir einfach keins leisten, also fahre ich Zug und mache das beste daraus

Ganz simpel finde ich das nicht. Zum draufaddieren musst Du vorher lesen und das wird in einem Non-Cachable-Bereich eher langsam sein. Wenn Du zum Schluss eh absolute Werte brauchst, warum dann so viel Mühe um immer mit relativen Werten zu arbeiten?

Macht der Gewohneit? Ich weiß es nicht, aber was ich weiß ist, das ich ein riesen Problem habe, auf SMP Systemen (ohne den netten HPET ) ne halbwegs akkurate globale Zeit zu bekommen. Wenn ich das in den Griff bekommen würde, dann kann ich auch absolute Werte nutzen.
So aber finde ich ist es einfacher, zu sagen, so jetzt soll der Thread mal so und so lange schlafen und nicht er soll bis dann schlafen!

Das sieht in meinen Augen irgendwie extrem Aufwendig aus. Ich verstehe nicht welchen Vorteil Du Dir von diesem Aufwand erhoffst. Das ganze kann man doch eigentlich ganz einfach und simpel Lösen.

Ich dachte mir halt, wenn du schon so ein schönes Thema wie die OS Programmierung machst, dann mach es auch richtig und mit richtig meine ich in dem Fall, das ich die höchste Präzision aus den gegebenen Mitteln heraus hole (ohne dabei ander Dinge negativ zu beeinflussen, wie z.B. durch ne PIT Frequenz von 1000Hz).
So weit für SMP Systeme. Für ein CPU Systeme hab ich mich halt vollkommen auf den One-Shot-Modus eingeschossen. Ich find die Idee halt toll und sehe auch die Vorteile, nur leider ist der PIT da anderer Meinung So langsam spiele ich mit dem Gedanken auf PIT only Systemen doch wieder nen periodischen Modus zu nutzen, aber damit nehme ich mir einen Vorteil und das wäre die Präzision von Events. Ich müsste halt abwiegen was schlimmer ist.

Also ich finde es ungeschickt wenn der Scheduler was mit Timing zu tun hat. Ich persönlich bin der Meinung das der Schuler nur für die Verwaltung der Threads (und deren Zustände wie lauffähig, blockiert, schlafend usw.) und für den Kontext-Switch zuständig ist. Ein ordentlicher Scheduler, der mehrere CPUs fair + schnell über die Threads verteilt und dafür effiziente + leistungsfähige Management-Funktionen bietet, ist ansich schon kompliziert genug, da muss man nicht auch noch fremde Aufgaben mit rein packen.

Naja, so wie ich das sehe hat er schon was mit Timing zu tun, denn er kümmert sich doch ohnehin darum wie lange ein Thread laufen darf! Da kann er dann auch noch Events mit einbeziehen, so dass der Thread dann halt ein wenig früher unterbrochen wird. Wirklich komplizierter wird er meiner Meinung nach deswegen nicht.
Das ist übrigenz auch ein wunderbarer Fall für relative Zeiten. Denn wenn du möglichst Präzise (was mit dem APIC auf SMP Systemen ja möglich ist) Events auslösen willst, kannst du dich nicht auf die globale Zeit verlosen, da zu ungenau und da jede CPU ihre eigene "Zeit" hat, musst du halt mir relativen Zeiten arbeiten. Um es mal so zu sagen, kann ich einfach dein Konzeot mit meinem vermischen.
Ich nutze für den PIT die globale Zeit und wecke den Thread nicht auf wenn er gleich der globalen Zeit ist, sondern ich packe ihn in die Sleep-Queue der CPU wenn er kleiner der globalen Zeit+ein Tick ist. Dann kann ich auch andere Datenstrukturen nutzen und habe auch nur noch Vergleiche.
In den Sleep-Queues der CPUs nutze ich dann wieder die Relative Zeit.

Genau deshalb stelle ich mir die Frage: Warum Kompliziert wenn es doch auch so einfach geht? Was erhoffst Du Dir davon? Wo genau siehst Du den Vorteil?
Relative Zeitwerte, mehrere unabhängige Timer und verwische Zuständigkeiten in den SW-Modulen. Klar das kann man alles realisieren aber wenn Du diesen Aufwand treiben möchtest dann erwartest Du doch auch was, ich sehe das nur eben nicht, das müsstest Du mir erklären.

Hatte ich ja oben schon beantwortet. Nur noch mal ganz kurz, höchst mögliche Präzision auf alten (wie neuen) Systemen. Wofür, ich habe keine Ahnung

Sag mir doch mal was das höchste an Präzision ist, was man in einem OS wahrscheinlich brauchen wird. Denn ich versuche ja schon mit meinem System bis auf ns runter zu gehen (beim PIT eher µs).

... Wieso fragst Du das, weil ich wissen möchte wo Du so exotische Boards her hast?

Auch, aber weil du das mit den APICs nicht wusstest.

Meine Erfahrung mit solchen Boards habe ich mit 4x PentiumPro 200MHz 1MB-L2-Cache unter Windows NT gemacht und ich kann Dir sagen das Windows NT verdammt schlecht skaliert hat. Das Board und die CPUs hatten zwar alle APICs aber Windows NT konnte damit nicht allzu viel anfangen. Der IO-APIC war wimre komplett deaktiviert und die Local-APICs wurden von Windows NT nur mit dem absolut notwendigsten (für SMP) benutzt.

Also so richtig kann ich es nicht glauben das der IO-APIC deaktiviert war. Denn das hieße ja, dass alle IRQs immer auf die selbe CPU geleitet wurden (man kann den PIC durchaus auf SMP Systemen nutzen, aber eher sehr unvorteilhaft)! Die APICs sind ja auch für SMP zwingend erforderlich!

Das mit den deaktivierten APICs ärgert mich bis heute, ich meine Athlon XP Systeme sehe ich schon als halbwegs modern an! Und wer kauft sich schon nur ein neues Board damit er sein eigenes kleines OS darauf testen kann

Ja, gerne. Was haste denn für Prozies drauf? Falls Du das Board nicht in Betrieb bekommst würde ich mich dafür interessieren.

Im Moment sind da gar keine drauf. Mir mangelt es an dem richtigen Netzteil, weil wie gesagt eine Art erweiterter AT Standard (P8 und P9 Stecker wie normal, aber zusätzlich noch nen P10 Stecker). Das Board wurde augenscheinlich auch von irgendeinem Vorbesitzer modifiziert (ich glaube um Sockel 7 CPUs laufen zu lassen, aber da irre ich mich wahrscheinlich). Wenn ich es schaffe, dann mache ich mal ein Bild.

Aber man kann den Triathlon bei normalem Wetter (leicht Bewölkt, kein Regen und kein Wind) in normaler Umgebung (Flachland) durchziehen oder, wenn man masochistisch veranlagt ist, bei extremsten Wetter (>100 l Regen pro m² und h mit Windstärke 8 ) und in unpassenster Umgebung (Gebirge). Wink
SCNR

Wer sich gerne quählt Du bist da mit deiner eigenen CPU (bzw. System) ja auch nicht weit entfernt von

[erik.vikinger]

Hallo,

Also ich wüde wahrscheinlich sogar ne Delta-Queue in einen Baum packen können

Sicher? Das kann ich mir momentan kaum vorstellen. Außerdem bleibt der Overhead das Du die relativen Zeiten immer mitrechnen musst, also zusätzliche Schreibzugriffe erzeugst.

Was das Entfernen betrifft, ist meine Queue klar schneller, besonders wenn der Baum immer voller wird.

Wieso? Ich muss Doch meinen Timer nicht suchen (und wenn wir beide suchen müssten dann wäre der Baum wieder im Vorteil). Ich muss zwar einen Pointer mehr prüfen (um zu wissen welches der beiden Kinder noch da ist, was bei einem abgelaufenen Timer eigentlich klar ist da es keine Kinder mit früherem Ablaufzeitpunkt geben kann) als in einer bidirektional verketteten Liste aber das war es auch schon.

Denn du versaust dir da den Cache, durch die "vielen" (ein paar reichen ja) Speicherzugriffe und die "längere" (sollte eigentlich unwesentlich sein) addiert sich ja auch, wenn du doch mal einige Elemente Entfernen musst. Rein theoretisch betrachtet ist die Queue in dem Fall O(1) und der Baum O(log n).

Zum entfernen muss ich maximal 2 Pointer aktualisieren. Vom zu entfernenden Element der entsprechende Kind-Pointer des Eltern-Elements und von dem maximal einem Kind-Element den Eltern-Pointer (ich hoffe ich drücke mich verständlich aus). Für den Fall dass das zu löschende Element die Wurzel ist dann muss natürlich der spezielle Wurzel-Pointer auch aktualisiert werden. Baum-Elemente die noch 2 Kinder haben lösche ich nicht sofort sondern markiere diese nur als inaktiv. Solche toten Timer fliegen automatisch raus wenn sie als nächstes dran wären. Das kostet zwar etwas Speicher aber der ist nun so knapp auch wieder nicht.

Die Zahl erschein mir irgendwie arg hoch. Denn das macht gerade mal 833 Takte pro Thread und so ein Thread-Wechsel kostet ja doch einiges an Zeit und Performance (oder liefen die alle in einem Adressraum?).

Sorry, hab ich vergessen zu erwähnen. Das waren alles Threads eines Steuerungsprogramms, die liefen alle im selben Adressraum. Der Kontext-Switch selber hat etwas mehr als 200 Takte gedauert, war ein Round-Robin-Scheduler mit 8 verschiedenen Prioritäten (wovon nur 7 ausgeführt werden, die unterste war die Sleep-Priorität).

Der "Witz" bei einer Delta-Queue ist doch, das du nur die Abstände zwischen den Elementen speicherst und nicht die direkten (absoluten) Werte.

Ich bezeichne das nicht als "Witz" sondern als "unnötigen Zusatzaufwand". Ich verstehe immer noch nicht warum Du das machst.

Was du ja schon richtig erkannt hast, ist das deine Lösung nur ein (oder mehrere) Pointer ändern und meiner bis zu 2 Werte und ein paar Pointer, den einen Wert dafür ständig (im worst-case).

Ganz recht. Du erkennst den Unterschied?

Um deine eine Frage zu beantworten,....

Ich glaube ich hab das (und Deinen Queue-Add-Code) jetzt einigermaßen verstanden. Ich kann nur eben keinen Vorteil erkennen. Der Code zum einfügen eines Elementes in einen Baum ist sicher nicht umfangreicher oder komplexer, aber gerade bei vielen Elementen auf jeden Fall schneller: O(log n) < O(n/2).

solltest du doch durch die "vielen" Zugriffe (bei einem Baum z.b.) auch den Cache trashen, oder?

Wieso? Zum einfügen eines neuen Elements braucht man bei einem Baum ja weniger Zugriffe als in einer linearen Liste, deswegen nimmt man doch den Baum. Das Element das als nächstes Abläuft muss ich nicht suchen sondern ich hab immer einen extra Pointer da drauf. Das Entfernen eines beliebigen Elementes hab ich ja schon beschrieben. Bei einer linearen sortierten Liste ist das einfügen deutlich aufwändiger (lange Suche), das vorderste Element ist auch direkt über einen Pointer ansprechbar und das Entfernen ist minimal schneller als beim Baum. Aus meiner Sicht ein ganz klarer Sieg für den Baum, deswegen hab ich mich damals dafür entschieden (trotz dessen das ich den in Assembler implementieren musste). Es gibt bestimmt auch noch was besseres als nen Baum.

das einige Dateisysteme die Zeit bis auf die ms genau wollen, oder?

NTFS macht 100ns Schritte, in ext4 ist da wimre auch was ziemlich genaues drin. Auch in diesem Fall wäre der HPET ein Vorteil aber zu Not lässt Du die unteren Bits einfach auf 0. Welcher User merkt schon den Unterschied? Das klassische FAT kann nur in 2s Schritten und das hat auch immer gereicht.

aber was ich weiß ist, das ich ein riesen Problem habe, auf SMP Systemen (ohne den netten HPET ) ne halbwegs akkurate globale Zeit zu bekommen. Wenn ich das in den Griff bekommen würde, dann kann ich auch absolute Werte nutzen.

Das stimmt. Ich schreibe es nur ungerne (Du bist bestimmt schon genervt) aber ließ Dir noch mal die PIT-Variante in meinem Ursprungsport durch. Die Löst dieses Problem perfekt (egal wie viele CPUs). Das mit der hohen IRQ-Frequenz sehe ich nicht als so ernstes Problem, machen viele andere OSe ja auch so, jede Sache hat eben ihren Preis. Der einzigste echte Nachteil ist das damit die CPU nicht richtig tief schlafen kann um Energie zu sparen.

So aber finde ich ist es einfacher, zu sagen, so jetzt soll der Thread mal so und so lange schlafen und nicht er soll bis dann schlafen!

Bei der zweiten Variante musst Du in der Sleep-Funktion einmalig eine Addition ausführen, bei der ersten Variante musst Du ständig die relativen Zeiten passend hinrechnen um vernünftig Vergleichen zu können. Zusätzlich bekommst Du bei periodischen Events, mit den absoluten Zeitwerten, eine perfekte Langzeitgenauigkeit.

Ich find die Idee halt toll und sehe auch die Vorteile

Also ich sehe da keine Vorteile. Vielleicht erklärst Du mir diese mal.

Bei den absoluten Zeitwerten sehe ich noch einen Vorteil: Wenn ein IRQ kommt und dieser als Message in ein User-Mode-Prozess geleitet wird dann soll in der Message der Zeitpunt des IRQs vermerkt sein (quasi als Zeitstempel) damit der User-Mode-IRQ-Handler schauen kann wie lange die Latenz war, es könnte ja sein das ein anderer Thread mit einer höheren Priorität lief und daher der IRQ-Handler-Thread warten musste.

denn er kümmert sich doch ohnehin darum wie lange ein Thread laufen darf!

Er muss die Länge der Zeitscheiben vorgeben, aber deren Einhaltung zu kontrollieren fällt IMHO nicht in seinen Zuständigkeitsbereich. Außerdem werden Zeitscheiben wirklich nur selten aufgebraucht.
Wenn Du die Local-APICs hast dann sind diese für die Zeitscheiben zuständig ansonsten musst Du das leider mit ins normale Timing nehmen. Für andere Dinge würde ich die Local-APICs nicht nehmen. In meinen CPUs will ich was ähnliches vorsehen das dann auch mit relativen Zeiten arbeitet, einen simplen Down-Counter in welchen einfach die Zeitscheibenlänge eingetragen wird und der dann bei 0 (falls er überhaupt bis da hin kommt) einen extra Kontext-Switch-IRQ auslöst (und das zählen aufhört).

Wirklich komplizierter wird er meiner Meinung nach deswegen nicht.

Darum geht es mir gar nicht primär, sondern um die Modularität des Quell-Codes. Wenn Du das Timing über mehrere Module verteilst wirst Du Dich irgendwann später mal ziemlich ärgern darüber. Stell Dir vor Du tauscht mal den Scheduler gegen einen anderen aus, dann gibt es Teile des Timing-Systems mehrmals (in jedem Scheduler). Wartbarer Code ist IMHO was anderes.

... und da jede CPU ihre eigene "Zeit" hat ...

Wenn bei Dir jede CPU ne eigene Zeit hat dann machst Du IMHO was falsch. Bei mir wird es nur eine Zeit geben, die eine reicht mir einfach.

höchst mögliche Präzision auf alten (wie neuen) Systemen. Wofür, ich habe keine Ahnung

Genau: Wofür? Ich glaube nicht das normale Programme was genaueres als ein paar Mikrosekunden brauchen. Fürs meiste dürften auch Millisekunden völlig reichen. Programme die wirklich was genaueres brauchen (dazu gehören bestimmt keine Multimediaprogramme o.ä.) machen das sicherlich über ne extra Library welche Du dann auf Dein OS portieren musst, da braucht diese Library bestimmt eh ein paar spezielle SYSCALLs oder die Library bekommt einen eigenen Timing-Treiber mit HW-Zugriff.

Also so richtig kann ich es nicht glauben das der IO-APIC deaktiviert war.

Ich bin mir nicht sicher ob der IO-APIC vom BIOS deaktiviert wurde aber Windows NT hat den auf jeden Fall nicht benutzt. Selbst in Windows 2000 war die IO-APIC-Unterstützung noch ziemlich rudimentär.

Die APICs sind ja auch für SMP zwingend erforderlich!

Ja, gerade so das absolut nötigste hat Windows NT unterstützt. Die SMP-Unterstützung war damals auf der Alpha-Plattform deutlich besser als auf x86.

und du immer mit deinem HPET

Fühlst du Dich genervt? Sorry, aber ich bin es gewohnt mit ordentlichem Werkzeug zu arbeiten.

Ich dachte mir halt, wenn du schon so ein schönes Thema wie die OS Programmierung machst, dann mach es auch richtig

Full ACK!
Darf ich Dich daran erinnern das es noch viele andere Plattformen gibt außer x86? Die meisten dürften deutlich besser sein als x86.

Das mit den deaktivierten APICs ärgert mich bis heute, ich meine Athlon XP Systeme sehe ich schon als halbwegs modern an! Und wer kauft sich schon nur ein neues Board damit er sein eigenes kleines OS darauf testen kann

Darf ich Dich nochmal daran erinnern das es noch viele andere Plattformen gibt außer x86?

Wer sich gerne quählt Du bist da mit deiner eigenen CPU (bzw. System) ja auch nicht weit entfernt von

Also ich quäle mich wirklich nicht gerne. Und weil ich mich auch nicht gerne mit idiotischer Hardware rumärgere mache ich gleich was eigenes. Ich habe da vielleicht mehr Arbeit aber bestimmt auch einen niedrigeren Frustrationslevel.


Grüße
Erik

[FlashBurn]

Sicher? Das kann ich mir momentan kaum vorstellen. Außerdem bleibt der Overhead das Du die relativen Zeiten immer mitrechnen musst, also zusätzliche Schreibzugriffe erzeugst.

Nope, funktioniert nicht! War ein ganz großer Denkfehler von mir. Denn ich habe vorausgesetzt das ich die Abstände schon kenne, dann würde das klappen aber so nicht

Wieso? Ich muss Doch meinen Timer nicht suchen (und wenn wir beide suchen müssten dann wäre der Baum wieder im Vorteil). Ich muss zwar einen Pointer mehr prüfen (um zu wissen welches der beiden Kinder noch da ist, was bei einem abgelaufenen Timer eigentlich klar ist da es keine Kinder mit früherem Ablaufzeitpunkt geben kann) als in einer bidirektional verketteten Liste aber das war es auch schon.

Ich weiß ja nicht von was für nem Baum wir hier sprechen, aber AVL und RB müssen beim Löschen ja wieder "repariert" werden und das ist auf jeden Fall aufwendiger als bei einer Queue.

Das Element das als nächstes Abläuft muss ich nicht suchen sondern ich hab immer einen extra Pointer da drauf.

Das ist clever! Da wäre ich jetzt gar nicht so schnell drauf gekommen, aber ich hätte mir auch überlegt wie ich immer die "kleinste" Node irgendwo speichern kann.

Das stimmt. Ich schreibe es nur ungerne (Du bist bestimmt schon genervt) aber ließ Dir noch mal die PIT-Variante in meinem Ursprungsport durch. Die Löst dieses Problem perfekt (egal wie viele CPUs). Das mit der hohen IRQ-Frequenz sehe ich nicht als so ernstes Problem, machen viele andere OSe ja auch so, jede Sache hat eben ihren Preis. Der einzigste echte Nachteil ist das damit die CPU nicht richtig tief schlafen kann um Energie zu sparen.

Also erstmal du nervst nicht, ich kann sonst solche Diskussionen nicht auf so einem Niveau und über so ein Thema führen!
Gegen den PIT Timer mit einer solch hohen Frequenz habe ich grundsätzlich was! Davon wirst du mich nicht abrücken können. Und das Linux die Frequenz ihres Schedulers wieder geändert (also wieder kleiner gemacht) haben sagt mir das ich nicht so falsch liegen kann
Der Punkt welcher mih stört ist halt, ich kann den PIT auf einem SMP System nicht abschalten, egal welche Frequenz er hat und da möchte ich dann auch soviel es geht "sparen" (also im Endeffekt an Energie und CPU Zeit). Wenn der PC die meinste Zeit am nichts Tun ist, dann kostet das nur unnötig Energie und auch für diesen Fall muss geplant werden (sollte sich eventuell auf einem Laptop sehr sehr negativ auswirken!).

Also ich sehe da keine Vorteile. Vielleicht erklärst Du mir diese mal.

Präzision! Wie ich gerade in einem anderem Forum gelesen habe, macht sich da jemand gerade nen Kopf wie er die Schleife eines Games so umsetzen kann, das er auf max 60FPS kommt und somit die CPU nicht immer zu 100% auslastet. In diesem Zusammenhang meinte einer nimm einfach sleep(1) und dann ist noch rausgekommen, das sleep mindestens 15ms dauert (was ja logisch ist, da Windows nen periodischen Timer nutzt und ein Tick sind 15ms).
Und hier sage ich mir 15ms, das ist ne verdammt lange Zeit! Ich meine es gibt bestimmt genug Treiber die würden gerne wesentlich weniger warten (vielleicht irgendwo im µs Bereich) und bevor die busy-waiting machen, habe ich doch lieber eine Möglichkeit das ein Thread eine so kurze Zeit schlafen kann und in der Zeit kann die CPU schön andere Sachen machen. Das funktionier nun mal am besten mit nem One-Shot-Timer (zumal dein geliebter HPET eigentlich nur diesen Modus implementieren würde, aber aus legacy Gründen noch nen periodischen Modus hat, aber der ist optional)!
Jedes Mal wenn du weniger als 15ms (bei 400MHz sind das 6.000.000 Takte!) warten willst, müsstest du busy-waiting machen und das ganze noch als Real-Time Thread, damit du ja nicht unterbrochen wirst. Das ist ne absolute Ressourcen Verschwendung.
Desweiteren spare ich durch den One-Shot-Modus noch einige IRQs und das sollte sich ab einer Laufzeit von mehreren Stunden schon lohnen, was da gespart wird!

Darum geht es mir gar nicht primär, sondern um die Modularität des Quell-Codes. Wenn Du das Timing über mehrere Module verteilst wirst Du Dich irgendwann später mal ziemlich ärgern darüber. Stell Dir vor Du tauscht mal den Scheduler gegen einen anderen aus, dann gibt es Teile des Timing-Systems mehrmals (in jedem Scheduler). Wartbarer Code ist IMHO was anderes.

Das sehe ich ein wenig anders. Sieh es als ne Art Interface welches implementiert werden muss und wenn du sowieso den One-Shot-Modus nutzen musst (ist bei meinem Timer-Interface so vorgesehen), dann ist es auch kein Problem und Beinbruch diesen Timing-Code noch mit rein zu nehmen. Denn im Endeffekt bleibt das grobe Gerüst des Schedulers immer gleich:

Code: [Auswählen]

//berechne die Zeit die wirklich verbraucht wurde
diff= thisCPU->timerStart - timerGetCountNSecs();
//ziehe die Zeit von der Zeit ab, die der Thread hätte laufen dürfen
thisCPU->currThread->time-= diff;
//gucke ob ein Thread in der Sleep-Queue ist
if(sleepQueue) {
 //aktualisiere die Zeit des 1. Elements
 sleepQueue->sleepTime-= diff;
 //solange wie die Zeit die der Thread schlafen wollte kleiner ist als eine Konstante, weck ihn auf
 while(sleepQueue->sleepTime <= TIME_KONSTANTE) {
  //hole dir einen Pointer auf den Head der Queue
  struct thread_t *t= sleepQueue;
  //Head entfernen
  sleepQueue= queueRemoveHead(sleepQueue);
  //Thread aufwecken
  threadWakeup(t);
 }
 //hole dir die Zeit wann der nächste Thread aufgeweckt werden soll
 if(sleepQueue)
  sleepTimeNext= sleepQueue->sleepTime;
}
//hier würde jetzt der eigentliche Scheduler kommen, also berechnen welcher Thread als nächstes dran ist oder ob der gleiche Thread nochmal laufen darf usw.
//jetzt stellen wir den Timer ein
if(sleepQueue && sleepTimeNext < thisCPU->currThread->time)
 timerSetTimeSlice(sleeptime);
else
 timerSetTimeSlice(thisCPU->currThread->time);
Wenn ich sowas voraussetze, dann gibt es auch keine Probleme was die Wartbarkeit betrifft. Wenn ich es mir noch "einfacher" machen wollte, dann könnte ich den Scheduler noch weiter "auslagern" indem ich sage, dieses Grobkonzept ruft erst den eigentlichen Scheduler auf! So kann ich dann auch den Code vom Scheduler Code fernhalten!

Wenn bei Dir jede CPU ne eigene Zeit hat dann machst Du IMHO was falsch. Bei mir wird es nur eine Zeit geben, die eine reicht mir einfach.

Damit meine ich eigentlich solche Konzepte, das jeder Core extra runtergetaktet werden kann und schlafen kann, obwohl ein andere Core weiter fleißig rechnet. In dem Moment bleibt für mich auf dem Core die Zeit "stehen".

Genau: Wofür? Ich glaube nicht das normale Programme was genaueres als ein paar Mikrosekunden brauchen. Fürs meiste dürften auch Millisekunden völlig reichen. Programme die wirklich was genaueres brauchen (dazu gehören bestimmt keine Multimediaprogramme o.ä.) machen das sicherlich über ne extra Library welche Du dann auf Dein OS portieren musst, da braucht diese Library bestimmt eh ein paar spezielle SYSCALLs oder die Library bekommt einen eigenen Timing-Treiber mit HW-Zugriff.

Wieso nicht gleich zur Verfügung stellen? Wie gesagt, kann ich mir durchaus vorstellen, das einige Treiber doch ne ganz schön hohe Auflösung bei nem Timer bräuchten.
Um nochmal auf die Multimediaanwendungen zurück zu kommen und auf dein Bsp. das man es nicht merkt wenn der Film zu schnell läuft.
Also da muss ich dir ganz doll wiedersprechen. Ich habe im Moment nur unter Windows 7 sowas von Probleme mit HD Filmen, das ist nicht mehr schön und nur unter Windows 7 unter XP hatte ich die nicht. Ich merke es ganz doll wenn der Film zu schnell läuft. In diesem speziellen Fall haut irgendwas mit der Synchronisation nicht hin, denn nicht mal der Ton läuft fehlerfrei und das beste daran ist, es scheint nicht mal unbedingt ein Treiberprobelm zu sein, denn ich bekomme mit jedem Programm (WMP, VLC, MPC) andere Ergebnisse und der WMP läuft da noch am besten.
Auf meinem Desktop Rechner ist es so schlimm das ich nicht mal ne DVD vernünftig gucken kann

So aber wieder back-to-topic.

Darf ich Dich daran erinnern das es noch viele andere Plattformen gibt außer x86? Die meisten dürften deutlich besser sein als x86.

Ich weiß, leider. Denn erstmal sind mir diese zu teuer (ich wäre an ARM und PowerPC interessiert). Dann ist die Situation auf der ARM Plattform nicht wirklich besser. Denn da müsste ich ja für jedes Board bzw. jedes SoC meinen Kernel anpassen, das wäre für mich schon fast wie ne neue Architektur, dann kommen noch die verschiedenen BEfehlssätze dazu.
Was aber alle Argumente schlägt ist einfach die Verbreitung. Warum sollte ich mich mit einer Architektur befassen, die ich in meinem Umfeld gar nicht zu Gesicht bekomme?
Einen Punkt für ARM gibt es aber noch, ich hoffe auf immer mehr Handys mit Android oder nem anderen Linux, so dass man vielleicht irgendwann mal sein eigenen OS auf nem Handy laufen lassen kann. Daran wäre ich wirklich sehr interessiert!

[erik.vikinger]

Hallo,

Ich weiß ja nicht von was für nem Baum wir hier sprechen,

Mit den Fachbegriffen dazu bin ich nicht vertraut. Jedes Element enthält einen Timer (mit absoluten Zeitpunkt) und 3 Pointer, einen für Parent und 2 für die Kinder. An Kind A kommen alle kleineren Zeitpunkte und an Kind B kommt alles was größer oder gleich ist.

aber AVL und RB müssen beim Löschen ja wieder "repariert" werden und das ist auf jeden Fall aufwendiger als bei einer Queue.

Eben deshalb lösche ich nur Elemente aus dem Baum die nur ein (oder gar kein) Kind haben. Das kostet zwar etwas Speicher aber erspart mir komplizierte Umbaumaßnahmen im Baum. Da der Baum in den Maschinen, für die er ursprünglich programmiert wurde, eh ständig komplett umgewürfelt wird (die meisten Timer hatten Laufzeiten von unter 10 Sekunden) hab ich mir jegliche Optimierungsbemühungen zur Laufzeit gleich ganz gespart.

Das Element das als nächstes Abläuft muss ich nicht suchen sondern ich hab immer einen extra Pointer da drauf.

Das ist clever!

Is ja auch von mir.
Ne, das war einfach logisch, wenn ein Timer abläuft dann ist als nächstes einer seiner unmittelbaren Nachbarn dran und da spare ich mir natürlich das ewige neu suchen.

aber ich hätte mir auch überlegt wie ich immer die "kleinste" Node irgendwo speichern kann.

Eben, da wärst Du bestimmt auch zügig drauf gekommen, das ist einfach zu nahe liegend.

Also erstmal du nervst nicht, ich kann sonst solche Diskussionen nicht auf so einem Niveau und über so ein Thema führen!

Gegen den PIT Timer mit einer solch hohen Frequenz habe ich grundsätzlich was!

Was genau? Mal vom verwehrten CPU-Tiefschlaf abgesehen. Und bis Du Dich ordentlichem Powermanagement bei x86 widmen kannst wirst Du erst mal einen dicken Haufen anderer Probleme lösen müssen, der Energieverbrauch ist IMHO nicht Dein dringenstes Problem.

Davon wirst du mich nicht abrücken können.

Ich will Dich gar nicht verrücken, ich will Dich so lange mit guten Argumenten locken bis Du von ganz alleine kommst.
Oder Du mir bessere Gegenargumente bringst.

Und das Linux die Frequenz ihres Schedulers wieder geändert (also wieder kleiner gemacht) haben sagt mir das ich nicht so falsch liegen kann

Ich weiß es nicht genau aber ich vermute dass das Powermanagement da ein wichtiges Ziel war. Das Linux auf den meisten Laptops eine kürzere Akku-Laufzeit erreicht als Windows ist sicher ein wichtiges Argument dafür (und leider auch heute noch die Regel).

Der Punkt welcher mih stört ist halt, ich kann den PIT auf einem SMP System nicht abschalten, egal welche Frequenz er hat und da möchte ich dann auch soviel es geht "sparen" (also im Endeffekt an Energie und CPU Zeit). Wenn der PC die meinste Zeit am nichts Tun ist, dann kostet das nur unnötig Energie und auch für diesen Fall muss geplant werden (sollte sich eventuell auf einem Laptop sehr sehr negativ auswirken!).

Die Last, welcher ein 1000Hz IRQ generiert, ist meiner Meinung nach nicht so hoch, sollte auf einer modernen CPU unter 0,1% betragen, und bei SMP trifft das ja auch nur eine CPU. Warum sollte man den PIT bei SMP nicht abschalten können? Wenn Du ihn nicht brauchst, z.B. wenn keine Timer aktiv sind oder der HPET da ist, dann kann man den PIT auch abschalten. Für die Zeitscheiben stehen Dir bei SMP ja garantiert die Local-APICs bereit.

Also ich sehe da keine Vorteile. Vielleicht erklärst Du mir diese mal.

Präzision!

Aber gerade die wirst Du mit dem PIT-One-Shot-Modus sicher nicht erreichen. Nach 1'080'000 Bildern, bei 60 fps, werden damit bestimmt nicht genau 5 Stunden vergangen sein. Außerdem ist das Beispiel schon vom Konzept her falsch, wenn die GraKa ein neues Bild will dann soll sie doch bitte einen IRQ auslösen.

Ich meine es gibt bestimmt genug Treiber die würden gerne wesentlich weniger warten (vielleicht irgendwo im µs Bereich)

Zu welchem Zweck? Die x86-Plattform ist zwar ziemlicher Schrott aber das man, wie auf nen C64, mal 2 NOPs nimmt um irgendeiner HW-Peripherie-Komponente ne Mikrosekunde Bedenkzeit zu geben um die letzten Daten zu schlucken, ist längst vorbei. Heutige Hardware hat FIFOs, kann IRQs auslösen oder holt sich die nötigen Daten selber (im eigenen Tempo) aus dem Speicher.

(zumal dein geliebter HPET eigentlich nur diesen Modus implementieren würde, aber aus legacy Gründen noch nen periodischen Modus hat, aber der ist optional)

Nein, der HPET läuft immer, außerdem hat er mehrere Comparatoren und damit mindestens einen Multi-Shot-Mode. Der monoton laufende Counter ist ja gerade der Unterschied zum PIT-One-Shot-Mode. Vom dem Moment an wo der PIT einen IRQ auslöst bis er dann endlich wieder läuft, mit der nächsten Zeitspanne, vergeht immer etwas Zeit, vor allem ist diese Zeit nicht konstant oder vorhersehbar. Für wirklich präzise Dinge (ich meine damit Langzeitgenauigkeit) ist der PIT-One-Shot-Mode nicht geeignet.

Desweiteren spare ich durch den One-Shot-Modus noch einige IRQs und das sollte sich ab einer Laufzeit von mehreren Stunden schon lohnen, was da gespart wird!

Klar sparst Du damit etwas CPU-Leistung ein, verlierst dafür aber auch die einzigste Möglichkeit auf ne präzise monotone Zeitquelle.

Damit meine ich eigentlich solche Konzepte, das jeder Core extra runtergetaktet werden kann und schlafen kann, obwohl ein andere Core weiter fleißig rechnet. In dem Moment bleibt für mich auf dem Core die Zeit "stehen".

Also wenn ich Abends ins Bett gehe, schlafe und Morgens wieder aufwache dann ist die Zeit doch auch nicht stehen geblieben. Leider! Die Messung der absoluten Laufzeit Deines Systems darf nicht von irgend einer CPU abhängen.

Wie gesagt, kann ich mir durchaus vorstellen, das einige Treiber doch ne ganz schön hohe Auflösung bei nem Timer bräuchten.

Wofür? Der Treiber hat doch seine Hardware zur Verfügung, für die er zuständig ist, und kann dort auch IRQs bestellen wenn er auf einen längeren Vorgang warten muss. Auf moderner Hardware ist es übrigens gute Sitte gleich mehrere Jobs abzuliefern damit nicht zu viele IRQs anfallen.

Ich merke es ganz doll wenn der Film zu schnell läuft. In diesem speziellen Fall haut irgendwas mit der Synchronisation nicht hin, denn nicht mal der Ton läuft fehlerfrei und das beste daran ist,

Ich kann die Situation auf Deinem PC nicht beurteilen aber das klingt nicht nach mal 2 ms längerer Framedauer oder ähnlichen Kleinigkeiten. Außerdem hört man Ton-Aussetzer und Asynchronitäten sehr deutlich, das Ohr hat eine deutlich feinere zeitliche Auflösung als das Auge.

Darf ich Dich daran erinnern das es noch viele andere Plattformen gibt außer x86? Die meisten dürften deutlich besser sein als x86.

Ich weiß, leider.

Dann ist ja gut.

Denn erstmal sind mir diese zu teuer (ich wäre an ARM und PowerPC interessiert).

Klar kostet ein gutes Eval-Board etwas Geld aber wo da die Schmerzgrenze ist muss jeder selbst entscheiden. Meine Entwicklung mit mehreren FPGAs wird ganz sicher auch einiges an Geld verschlingen. Die TTL-Variante von Svenska ist aber auch nicht gerade preiswert. Ein echtes Hobby kostet eben auch mal Geld.

Dann ist die Situation auf der ARM Plattform nicht wirklich besser. Denn da müsste ich ja für jedes Board bzw. jedes SoC meinen Kernel anpassen, das wäre für mich schon fast wie ne neue Architektur,

Nein, das löst man über so genannte "Board-Specific-Packages" die dem Kernel, in Form von Treibern u.ä., die jeweilige Hardware des Boards zur Verfügung stellen. So lange die CPU die selbe ist bleibt der Aufwand sehr in Grenzen.

dann kommen noch die verschiedenen BEfehlssätze dazu.

Ja das wird bei ARM wohl ein echtes Problem werden, auf der anderen Seite sollte das ein guter Compiler nahezu komplett verbergen.

Was aber alle Argumente schlägt ist einfach die Verbreitung. Warum sollte ich mich mit einer Architektur befassen, die ich in meinem Umfeld gar nicht zu Gesicht bekomme?

Ich wette Du hast in Deiner unmittelbaren Umgebung mehr ARM und MIPS CPUs als x86. Denke mal an DVD-Player, Handy, Drucker und all die anderen elektronischen Spielzeuge in unserem Alltag. x86 ist das tatsächliche Nischenprodukt!

Einen Punkt für ARM gibt es aber noch, ich hoffe auf immer mehr Handys mit Android oder nem anderen Linux, so dass man vielleicht irgendwann mal sein eigenen OS auf nem Handy laufen lassen kann. Daran wäre ich wirklich sehr interessiert!

Ja darauf hoffe ich auch, vor allem darauf das diese Systeme ohne Abschottungsmechanismen kommen, das ist mir als mündigen Verbraucher sehr wichtig weshalb ich auch keine Apple-Produkte kaufe.


Grüße
Erik

[kevin]

aber AVL und RB müssen beim Löschen ja wieder "repariert" werden und das ist auf jeden Fall aufwendiger als bei einer Queue.

Eben deshalb lösche ich nur Elemente aus dem Baum die nur ein (oder gar kein) Kind haben. Das kostet zwar etwas Speicher aber erspart mir komplizierte Umbaumaßnahmen im Baum.

Entartet dir der Baum nicht ziemlich leicht in eine Liste, wenn du komplett auf das Ausgleichen verzichtest? Was natürlich den Vorteil hätte, dass du dann ständig nur ein Kind hast und ohne weiteres löschen kannst, aber ich glaube, das war trotzdem nicht ganz, was du im Sinn hattest.

[erik.vikinger]

Hallo,

Entartet dir der Baum nicht ziemlich leicht in eine Liste, wenn du komplett auf das Ausgleichen verzichtest?

Ein bisschen bestimmt. Da der Baum, in der damaligen Maschine, eh jede Minute fast komplett abgearbeitet wurde und die Zeiten ziemlich gut verteilt waren bin ich davon ausgegangen das sich so ein extra Aufwand gar nicht lohnt. Ich muss aber auch ehrlich sagen das ich von solchen Bäumen quasi keine Ahnung hab. Ich hab damals etwas gesucht ob ich einen kleinen Algorithmus finde der bei jedem Einfügen und Löschen den Baum ein klein wenig optimiert aber ich hab nichts gefunden was mich überzeugt hätte, nur Algorithmen die den Baum als ganzes durchoptimieren und ausbalancieren. Ich hatte auch mal vor den Baum zu Laufzeit zu vermessen aber ihr kennt das Problem vielleicht: wenn ein Programm(teil) einmal fehlerfrei läuft dann bekommt man vom Chef keine Zeit mehr um noch Details nachjustieren zu können. Zumindest hatte ich eine Funktion die den Baum sehr gründlich auf Fehlerfreiheit prüft.


Es freut mich zumindest das dieser Thread tatsächlich noch von anderen gelesen wird obwohl er doch schon sooooooo lange Beiträge enthält.


Grüße
Erik

[kevin]

Überfliegen trifft es besser, um ihn gründlich durchzulesen sind mir die Beiträge tatsächlich zu lang.

Gerade dass der Baum ständig abgearbeitet wird, führt doch aber dazu, dass tendenziell immer links Knoten rausfliegen und immer rechts neue dazukommen, oder? Für mich sieht das wirklich wie die perfekte Ausgangssituation für einen Baum aus, der in eine Liste entarten möchte. Insofern frage ich mich, ob du nicht genauso gut rauskommen würdest und dir noch ein bisschen Komplexität sparst, wenn du gleich eine Liste nimmst.

Dieses "komplette" Ausbalancieren klingt zwar aufwendig, aber bei jeder Einfüge/Lösch-Operation machst du pro Knoten auf dem Weg zwischen dem eingefügten/gelöschten Knoten und der Wurzel maximal eine Operation; im Durchschnitt dürfte es einiges weniger sein. Das ist also eigentlich jedesmal nur ein bisschen optimieren - aber wenn man das konsequent macht, bleibt der Baum trotzdem als ganzes ausbalanciert.

Ob es sich in diesem speziellen Fall lohnt, einen Baum zu nehmen, musst du selbst wissen, aber zumindest ein unbalancierter Baum kommt mir nicht sinnvoll vor.

[erik.vikinger]

Hallo,

Gerade dass der Baum ständig abgearbeitet wird, führt doch aber dazu, dass tendenziell immer links Knoten rausfliegen und immer rechts neue dazukommen, oder?

Im Prinzip hast Du recht. Da die Timerlaufzeiten, die in den Baum kommen, alle unterschiedlich sind wird der Baum, zumindest auf der damaligen Maschine, nicht allzu linear. Die Check-Funktion hat auch die Ebene des tiefsten Elements im Baum ausgegeben und der war nie tiefer als die Hälfte des Baums. Wie schon geschrieben, zu einer genaueren Analyse bin ich leider nicht gekommen. Falls ich dieses System in mein OS übernehme werde ich aber bestimmt mal deutlich genauer hinschauen. Versprochen.
Zumindest bietet der komplexere Code die potentielle Möglichkeit das es nicht auf eine lineare Liste hinausläuft.

Dieses "komplette" Ausbalancieren klingt zwar aufwendig, aber bei jeder Einfüge/Lösch-Operation machst du pro Knoten auf dem Weg zwischen dem eingefügten/gelöschten Knoten und der Wurzel maximal eine Operation; im Durchschnitt dürfte es einiges weniger sein. Das ist also eigentlich jedesmal nur ein bisschen optimieren - aber wenn man das konsequent macht, bleibt der Baum trotzdem als ganzes ausbalanciert.

Klingt sinnvoll, kommt auf meine ToDo-Liste. Die Frage ist halt wie sinnvoll es wirklich ist einen Baumabschnitt zu optimieren der als nächstes abläuft.

Ob es sich in diesem speziellen Fall lohnt, einen Baum zu nehmen, musst du selbst wissen, aber zumindest ein unbalancierter Baum kommt mir nicht sinnvoll vor.

Ich denke es hat sich damals gelohnt, ob es sich auch bei einem klassischen General-Purpose-OS lohnt kann ich nicht wirklich beurteilen aber ich vermute das der Baum immer noch zumindest etwas besser als eine lineare Liste ist.


Grüße
Erik

[kevin]

Da die Timerlaufzeiten, die in den Baum kommen, alle unterschiedlich sind wird der Baum, zumindest auf der damaligen Maschine, nicht allzu linear. Die Check-Funktion hat auch die Ebene des tiefsten Elements im Baum ausgegeben und der war nie tiefer als die Hälfte des Baums.

Eine Höhe von n/2 ist aber schon ganz schön groß. Ein richtig ausbalancierter Baum kommt immerhin auf log(n).

Ich kann im Moment auch nicht richtig abschätzen, wie viele Knoten durchschnittlich im Baum sein werden (wahrscheinlich hätte ich eure Posts dazu mehr als nur überfliegen müssen ) - aber ich vermute entweder n ist groß genug, dass zwischen n/2 und log(n) ein nennenswerter Unterschied ist, oder es sind so wenige Knoten, dass eine Liste auch nicht wesentlich langsamer wäre.

[FlashBurn]

Ich denke es hat sich damals gelohnt, ob es sich auch bei einem klassischen General-Purpose-OS lohnt kann ich nicht wirklich beurteilen aber ich vermute das der Baum immer noch zumindest etwas besser als eine lineare Liste ist.

Dazu müsste man mal konkret gucken, was für Zeiten so "geschlafen" werden. Denn wenn du davon ausgehst, das jedes neue Event was in den Baum kommt später endet als das davor, würde sich ein ausbalanzierter Baum schon lohnen.

Die Last, welcher ein 1000Hz IRQ generiert, ist meiner Meinung nach nicht so hoch, sollte auf einer modernen CPU unter 0,1% betragen, und bei SMP trifft das ja auch nur eine CPU. Warum sollte man den PIT bei SMP nicht abschalten können? Wenn Du ihn nicht brauchst, z.B. wenn keine Timer aktiv sind oder der HPET da ist, dann kann man den PIT auch abschalten. Für die Zeitscheiben stehen Dir bei SMP ja garantiert die Local-APICs bereit.

Ich muss doch aber auch an alte Systeme denken, wenn ich schon ne mindest Voraussetzung von nem Pentium habe, dann will ich auch das mein OS da vernünftig läuft und da machen sich 1000 IRQs doch sehr bemerkbar (vorallem wenn ich da an den worst-case mit nem Dual-P75 System denke ).

Aber gerade die wirst Du mit dem PIT-One-Shot-Modus sicher nicht erreichen. Nach 1'080'000 Bildern, bei 60 fps, werden damit bestimmt nicht genau 5 Stunden vergangen sein. Außerdem ist das Beispiel schon vom Konzept her falsch, wenn die GraKa ein neues Bild will dann soll sie doch bitte einen IRQ auslösen.

Da haben wir dann wieder aneinander vorbei geredet

Also wir sprechen jetzt erstmal nur von SMP Systemen und da brauche ich den PIT (oder halt den HPET so weit vorhanden) als globale Zeit! Und da nutze ich ihn ja auch im periodischen Modus, aber halt mit den 18,2Hz. Auf SMP Systemen nutze ich dann den APIC für die Scheduler der CPUs und die laufen im One-Shot Modus, weil da ist der Fehler nicht wichtig, der durch das neu Schreiben des Counter auftritt (zumal er da sowieso minimal sein sollte!). Alle Timer die <55,4ms warten, kommen in die Sleep-Queue einer CPU und dadurch das ich diese dort mit relativen Zeiten reinpacke ist halt auch der Jitter, der sich aufsummieren würde, egal. In der Sleep-Queue vom PIT (oder halt HPET) kommen alle Timer >55,4ms und dort nutze ich dann absolute Zeiten (wegen der von dir schon genannten Vorteile).

Jetzt zu den Single-CPU Systemen. Dort wo ich nur den PIT habe (also keinen APIC, was leider bis zu Athlon XP passieren kann), habe ich mir überlegt die RTC im periodischen Modus zu nutzen (z.B. dachte ich an nen Tick von 62,5ms) und da kommen dann wieder alle Timer mit ner Zeit >62,5ms rein und dort würde ich dann den PIT im One-Shot-Modus nutzen und da ist es dann ja wieder egal wie groß der Jitter, weil er sich nicht aufaddieren kann, da ja nur Timer mit ner Zeit <62,5ms da rein kommen. Ansonsten ist das Prinzip das gleiche.

Nein, der HPET läuft immer, außerdem hat er mehrere Comparatoren und damit mindestens einen Multi-Shot-Mode. Der monoton laufende Counter ist ja gerade der Unterschied zum PIT-One-Shot-Mode. Vom dem Moment an wo der PIT einen IRQ auslöst bis er dann endlich wieder läuft, mit der nächsten Zeitspanne, vergeht immer etwas Zeit, vor allem ist diese Zeit nicht konstant oder vorhersehbar. Für wirklich präzise Dinge (ich meine damit Langzeitgenauigkeit) ist der PIT-One-Shot-Mode nicht geeignet.

Was du mit den Comparatoren meinst ist im Endeffekt nen One-Shot-Modus. Der IRQ wird nur gefeuert wenn das Event erreicht ist und es liegt nicht unbedingt immer die selbe Zeit zwischen den IRQs, es werden also keine sinnlosen IRQs gefeuert, wo du nur nen Counter inkrementierst und sonst nichts machts, weil kein Event gefeuert werden muss.

Also wenn ich Abends ins Bett gehe, schlafe und Morgens wieder aufwache dann ist die Zeit doch auch nicht stehen geblieben. Leider! Wink Die Messung der absoluten Laufzeit Deines Systems darf nicht von irgend einer CPU abhängen.

Auch hier wieder hast du mich wahrscheinlich falsch verstanden. Das Problem auf SMP Systemen ist, das du nicht auf jeder CPU nen Counter haben kannst (auf meinem sowieso nicht, zwecks One-Shot und meinem speziellen idle System) und dann sagen kannst du nutzt den Counter jeder CPU als globale Zeit. Wenn ich von globaler Zeit rede meine ich die absolute Zeit die in der Realität vergangen ist, aber die Counter der CPUs driften irgendwann auseinander, genauso wie die TSCs. Deswegen brauche ich halt auf nem SMP System ne globale Zeit (in dem Fall über den PIT).

Ich wette Du hast in Deiner unmittelbaren Umgebung mehr ARM und MIPS CPUs als x86. Denke mal an DVD-Player, Handy, Drucker und all die anderen elektronischen Spielzeuge in unserem Alltag. x86 ist das tatsächliche Nischenprodukt!

Da muss ich dich in meinem Fall wohl leider enttäuschen (zumindest wenn wir von meiner Wohnung reden ). Denn da können andere CPUs nicht mit meiner Sammlung an Boards und CPUs mithalten Und andere Sachen habe ich nicht großartig (nicht mal nen DVD-Player ).

Ich kann im Moment auch nicht richtig abschätzen, wie viele Knoten durchschnittlich im Baum sein werden (wahrscheinlich hätte ich eure Posts dazu mehr als nur überfliegen müssen Wink) - aber ich vermute entweder n ist groß genug, dass zwischen n/2 und log(n) ein nennenswerter Unterschied ist, oder es sind so wenige Knoten, dass eine Liste auch nicht wesentlich langsamer wäre.

Das ist ja im Endeffekt genau das Problem! Wie willst du das vorher wissen? Das geht nicht auf nem OS wo Programme laufen können, die nicht nur du geschrieben hast. Du kannst ja nicht wissen auf was für nette Ideen die Leute so kommen und dann hast du mit einmal ne Queue die 1000 und mehr Einträge hat und da würde sich dann nen ausbalanzierter Baum besser machen (ich seh ein meine Delta-Queue ist da mist )!

[kevin]

Dazu müsste man mal konkret gucken, was für Zeiten so "geschlafen" werden. Denn wenn du davon ausgehst, das jedes neue Event was in den Baum kommt später endet als das davor, würde sich ein ausbalanzierter Baum schon lohnen.

Ich glaube nicht, dass das der Fall ist. Aber wenn es so wäre, wäre ein Baum jedenfalls definitv das falsche Mittel, dann würdest du eine einfache Queue wollen. Ein Baum lohnt sich nur dann, wenn du auch wirklich Suchen musst, am besten mit gleichverteilter Wahrscheinlichkeit, wo im Baum du das gesuchte Element tatsächlich findest.

Ich gehe davon aus, dass das bei der Timergeschichte der Fall ist, so dass sich ein balancierter Baum vielleicht tatsächlich lohnen könnte.

Das ist ja im Endeffekt genau das Problem! Wie willst du das vorher wissen? Das geht nicht auf nem OS wo Programme laufen können, die nicht nur du geschrieben hast. Du kannst ja nicht wissen auf was für nette Ideen die Leute so kommen und dann hast du mit einmal ne Queue die 1000 und mehr Einträge hat und da würde sich dann nen ausbalanzierter Baum besser machen (ich seh ein meine Delta-Queue ist da mist )!

Wie auch immer - einen unbalancierten Baum halte ich für Blödsinn, egal welchen der Fälle du dir raussuchst.

[FlashBurn]

Aber wenn es so wäre, wäre ein Baum jedenfalls definitv das falsche Mittel, dann würdest du eine einfache Queue wollen.

Denkfehler meinerseits. Denn dann könntest du ja immer am Ende Anfangen zu suchen und das dürfte in dem Fall wesentlich schneller sein.

[erik.vikinger]

Hallo,


erstmal möchte ich mich für mein langes Delay entschuldigen, mein PC hat massiv gestreikt. Wer mir sein unendliches Mitleid bekunden möchte darf das gerne hier oder hier tun.

Ein Baum lohnt sich nur dann, wenn du auch wirklich Suchen musst, am besten mit gleichverteilter Wahrscheinlichkeit, wo im Baum du das gesuchte Element tatsächlich findest.
Ich gehe davon aus, dass das bei der Timergeschichte der Fall ist, so dass sich ein balancierter Baum vielleicht tatsächlich lohnen könnte.

Ganz meine Meinung. Deshalb hab ich das ja damals auch gemacht, nur leider nicht zu Ende gebracht.

Wie auch immer - einen unbalancierten Baum halte ich für Blödsinn,

Auch da kann ich Dir nur zustimmen, auch wenn ich persönlich der Meinung bin das selbst ein nicht ganz optimaler Baum immer noch besser als eine lineare Liste ist.
Ich hab mir mal den AVL-Baum etwas näher angesehen und der schein mir recht geeignet und auch nicht zu komplex zu sein. Die B-Bäume machen auf mich keinen so guten Eindruck weil die Nodes ziemlich komplex sind und außerdem der eigentliche Inhalt zwischen den Nodes wechseln kann und noch eine zusätzliche Indirektion finde ich eher ungünstig, die B-Bäume sind wohl wirklich eher für Daten geeignet die lange Zugriffszeiten haben so das die komplexeren Baum-Nodes nicht so ins Gewicht fallen.

Ich muss doch aber auch an alte Systeme denken, wenn ich schon ne mindest Voraussetzung von nem Pentium habe, dann will ich auch das mein OS da vernünftig läuft und da machen sich 1000 IRQs doch sehr bemerkbar (vorallem wenn ich da an den worst-case mit nem Dual-P75 System denke ).

Dann nimmst Du eben nur 100Hz oder gar 50Hz, das kannst Du doch beim OS-Start dynamisch festlegen. Bei einem Dual-CPU-System ist das Problem doch auch nur halb so schlimm, es belastet ja nur eine CPU.

Da haben wir dann wieder aneinander vorbei geredet

Was meinst Du den dann mit Präzision? Die Laufzeit eines sleep(0815) dürfte kaum auf die Micro-Sekunde genau interessieren, schließlich sagt ja auch der Standard das ein sleep länger dauern darf. Für ein präzises nsleep() sehe ich keinen Bedarf, so alte Hardware wirst Du doch hoffentlich nicht mehr in Deinen PCs haben.

Also wir sprechen jetzt erstmal nur von SMP Systemen und da brauche ich den PIT (oder halt den HPET so weit vorhanden) als globale Zeit! Und da nutze ich ihn ja auch im periodischen Modus, aber halt mit den 18,2Hz. Auf SMP Systemen nutze ich dann den APIC für die Scheduler der CPUs und die laufen im One-Shot Modus, weil da ist der Fehler nicht wichtig, der durch das neu Schreiben des Counter auftritt (zumal er da sowieso minimal sein sollte!).

Ja, das klingt doch schon mal gut.

Alle Timer die <55,4ms warten, kommen in die Sleep-Queue einer CPU und dadurch das ich diese dort mit relativen Zeiten reinpacke ist halt auch der Jitter, der sich aufsummieren würde, egal.

Wenn Du einen Timer mit absoluten Ablaufzeitpunkt als relative Zeit in den Local-APIC-Timer eintragen willst dann benötigst Du eine Bezugszeit, also die aktuelle Ist-Zeit, möglichst in der selben Präzision. Was machst Du in der Situation wenn Du einen Timer mit 60ms hast und gleichzeitig ein neuer Thread laufen soll, dann wirst Du bestimmt erstmal die Zeitscheibenlänge (55,4ms) in den Local-APIC-Timer eintragen, wenn dann der Thread die Zeitscheibe nach etwa 20ms abgeben möchte (was ja nun wirklich nicht unwahrscheinlich ist) dann hat der Timer nur noch 40 ms übrig, trägst Du dann diesen in den Local-APIC-Timer ein und startest einen anderen Thread? Wenn ja, was ist wenn dieser Thread auch vorzeitig seine Zeitscheibe abgibt? Wie bestimmst Du dann wie viel Zeit er von seiner Zeitscheibe aufgebraucht hat, schließlich wurde ja nicht die Zeitscheibenlänge in den Local-APIC-Timer reingeladen? Dieses vermischen unterschiedlicher Dinge erscheint mir irgendwie ungeschickt.

In der Sleep-Queue vom PIT (oder halt HPET) kommen alle Timer >55,4ms und dort nutze ich dann absolute Zeiten (wegen der von dir schon genannten Vorteile).

Jetzt zu den Single-CPU Systemen. Dort wo ich nur den PIT habe (also keinen APIC, was leider bis zu Athlon XP passieren kann), habe ich mir überlegt die RTC im periodischen Modus zu nutzen (z.B. dachte ich an nen Tick von 62,5ms) und da kommen dann wieder alle Timer mit ner Zeit >62,5ms rein und dort würde ich dann den PIT im One-Shot-Modus nutzen und da ist es dann ja wieder egal wie groß der Jitter, weil er sich nicht aufaddieren kann, da ja nur Timer mit ner Zeit <62,5ms da rein kommen. Ansonsten ist das Prinzip das gleiche.

Kann der RTC periodische IRQs generieren?
Außerdem verstehe ich noch nicht wie du einen absoluten Timer und einen relativen Timer synchron halten willst. Ich denke dass das ziemlich Arbeit werden könnte. Also ich würde das nicht freiwillig versuchen.

Also wenn ich Abends ins Bett gehe, schlafe und Morgens wieder aufwache dann ist die Zeit doch auch nicht stehen geblieben. Leider! Wink Die Messung der absoluten Laufzeit Deines Systems darf nicht von irgend einer CPU abhängen.

Auch hier wieder hast du mich wahrscheinlich falsch verstanden. Das Problem auf SMP Systemen ist, das du nicht auf jeder CPU nen Counter haben kannst (auf meinem sowieso nicht, zwecks One-Shot und meinem speziellen idle System) und dann sagen kannst du nutzt den Counter jeder CPU als globale Zeit. Wenn ich von globaler Zeit rede meine ich die absolute Zeit die in der Realität vergangen ist, aber die Counter der CPUs driften irgendwann auseinander, genauso wie die TSCs. Deswegen brauche ich halt auf nem SMP System ne globale Zeit (in dem Fall über den PIT).

Also brauchst Du für die globale Zeit eine einzelne Instanz nimmst (ob PIT oder HPET ist erstmal egal) dann gibt es doch auch kein Problem, ein Lesezugriff sollte schließlich immer möglich sein. Die CPU-Lokalen-Timer sind für sowas prinzipiell nicht geeignet, eben weil man die CPUs auch mal schlafen legen will.

Da muss ich dich in meinem Fall wohl leider enttäuschen (zumindest wenn wir von meiner Wohnung reden ).

Okay, aber Deine Wohnung ist offensichtlich nicht der Normal-Fall. Über die gesamte Erde betrachtet ist x86 definitiv ein Nischenprodukt.


Grüße
Erik

[FlashBurn]

Auch da kann ich Dir nur zustimmen, auch wenn ich persönlich der Meinung bin das selbst ein nicht ganz optimaler Baum immer noch besser als eine lineare Liste ist.
Ich hab mir mal den AVL-Baum etwas näher angesehen und der schein mir recht geeignet und auch nicht zu komplex zu sein. Die B-Bäume machen auf mich keinen so guten Eindruck weil die Nodes ziemlich komplex sind und außerdem der eigentliche Inhalt zwischen den Nodes wechseln kann und noch eine zusätzliche Indirektion finde ich eher ungünstig, die B-Bäume sind wohl wirklich eher für Daten geeignet die lange Zugriffszeiten haben so das die komplexeren Baum-Nodes nicht so ins Gewicht fallen.

Ich bin ein Fan vom AVL-Baum, aber in dem Fall von einer Sleep-Queue muss ich dann auch zugeben, dass ein RB-Baum wahrscheinlich die bessere Wahl wäre. Denn in dem ist das Löschen schneller.

Was meinst Du den dann mit Präzision? Die Laufzeit eines sleep(0815) dürfte kaum auf die Micro-Sekunde genau interessieren, schließlich sagt ja auch der Standard das ein sleep länger dauern darf. Für ein präzises nsleep() sehe ich keinen Bedarf, so alte Hardware wirst Du doch hoffentlich nicht mehr in Deinen PCs haben.

Mit Präzision meine ich z.B. das ein Thread alle 40ms ein Bild berechnet und es dann ausgibt. Wenn ich jetzt nen periodischen Timer von 15ms habe, dann kann der Fehler zw 5ms und 20ms liegen, was ich schon arg ungenau finde. Ich sag mal der Grund ist doch erstmal egal wozu ich die Präzision brauche, das kann ich auch gar nicht wissen, aber ich hätte sie gerne. Das Prinzip läuft auf eine Diskussion der Art 64KiB RAM sind genug hinaus

Um auf die alte Hardware zurück zu kommen. Du möchtest doch sicher das dein OS so schnell wie möglich startet und dem APIC sollte man schon ne gewisse Zeit geben damit er deine Befehle ausführen kann (konkret meine ich das Starten der APs) und wenn du dann jedes Mal als kleinste mögliche Wartezeit 15ms hast summiert sich das schnell zu einer sehr langen Zeit auf. Ich weiß nicht ob du jetzt genau wissen möchtest wie lange man wo warten sollte, aber wenn du es wissen möchtest, dann gucke ich nach und schreibe es noch!

Wenn Du einen Timer mit absoluten Ablaufzeitpunkt als relative Zeit in den Local-APIC-Timer eintragen willst dann benötigst Du eine Bezugszeit, also die aktuelle Ist-Zeit, möglichst in der selben Präzision. Was machst Du in der Situation wenn Du einen Timer mit 60ms hast und gleichzeitig ein neuer Thread laufen soll, dann wirst Du bestimmt erstmal die Zeitscheibenlänge (55,4ms) in den Local-APIC-Timer eintragen, wenn dann der Thread die Zeitscheibe nach etwa 20ms abgeben möchte (was ja nun wirklich nicht unwahrscheinlich ist) dann hat der Timer nur noch 40 ms übrig, trägst Du dann diesen in den Local-APIC-Timer ein und startest einen anderen Thread? Wenn ja, was ist wenn dieser Thread auch vorzeitig seine Zeitscheibe abgibt? Wie bestimmst Du dann wie viel Zeit er von seiner Zeitscheibe aufgebraucht hat, schließlich wurde ja nicht die Zeitscheibenlänge in den Local-APIC-Timer reingeladen? Dieses vermischen unterschiedlicher Dinge erscheint mir irgendwie ungeschickt.

Dein Bsp. ist erstmal ungeeignet, da der Thread ja erstmal in die Queue des PIT gehen würde, da er >55,4ms schlafen möchte.
Ich speichere wie gesagt immer die Zeit ab die ich in den APIC geschrieben habe und jedes Mal wenn der Scheduler aufgerufen wird (ob die Zeitscheibe nun aufgebraucht wurde oder der Thread abgegeben hat) berechne ich die Differenz zwischen der Zeit die ich eingetragen habe und der Zeit die noch übrig ist (kannst du ganz einfach machen, in dem du den Counter ausliest und mit der Zeit eines Ticks multiplizierst). Diese nutze ich dann zum rechnen.
Der Sinn hinter einem One-Shot-Timer ist, dass dieser nur feuert, wenn die Zeit die eingetragen wurde abgelaufen ist. Also ja ich trage genau die Zeit in den APIC ein die ein Thread laufen darf (oder halt die Zeit bis zu dem nächsten Thread der aufgeweckt werden muss, je nach dem was "kleiner" ist).

Praktisch sowas:

Code: [Auswählen]

timeNextThread= currThread->prio * NETTE_KONSTANTE;
sleepNext= sleepQueue->sleepTime;

if(sleepNext < timeNextThread)
 timeSet= apicSetTimeSlice(sleepNext);
else
 timeSet= apicSetTimeSlice(timeNextThread);


Kann der RTC periodische IRQs generieren?
Außerdem verstehe ich noch nicht wie du einen absoluten Timer und einen relativen Timer synchron halten willst. Ich denke dass das ziemlich Arbeit werden könnte. Also ich würde das nicht freiwillig versuchen.

Also ja die RTC hat nen periodischen Modus aber immer nur 2er Potenzen als Frequenz.
Der Trick ist, dass ich die beiden Timer nicht synchron halten muss! Ich arbeite doch nur bei dem periodischen Timer mit absoluten Zeit und bei dem One-Shot-Timer arbeite ich mit relativen Zeiten.
Bei relativen Zeiten kann es mir doch egal sein, wie der Timer "aus dem Ruder läuft". Ich nutze dort keine Counter um die absolute Zeit zu verfolgen, sondern mich interessiert es nur, ab einem gewissen Zeitpunkt bis zu einem gewissen Zeitpunkt die Zeit so genau wie möglich zu erfassen und wenn der Timer in der Zeit 1ms ungenau ist, naund! Immernoch besser als was ich mit einem periodischen Timer erreichen kann.

Okay, aber Deine Wohnung ist offensichtlich nicht der Normal-Fall. Über die gesamte Erde betrachtet ist x86 definitiv ein Nischenprodukt.

Das habe ich schon verstanden und ist mir bekannt, aber ich dachte wir sind uns schon einig das wir ein OS für einen "normalen" PC schreiben! Denn was interessieren mich DVD-Player oder eingebettete Systeme in Autos oder Mikrowellen oder Hifi-Anlagen? Die PCs an denen wir arbeiten/spielen/gucken sind in der Mehrzahl x86er!
Ich würde mich sehr freuen auch nen potenten ARM-PC zu sehen, aber das ist leider noch nicht der Fall (und bezahlbar sollte er sein). Wenn es darum geht einen PC als User (damit meine ich nen normalen Menschen) zum Internet surfen, Dokumente schreiben, spiele Spielen und Filme gucken zu benutzen, dann sind alle anderen Architekturen Nischenprodukte! Ob das gut und schön ist, sei mal dahin gestellt!

[erik.vikinger]

Hallo,

Ich bin ein Fan vom AVL-Baum, aber in dem Fall von einer Sleep-Queue muss ich dann auch zugeben, dass ein RB-Baum wahrscheinlich die bessere Wahl wäre. Denn in dem ist das Löschen schneller.

Ich kenne mich damit (noch) gar nicht aus, meine Meinung basiert nur auf den Artikeln in der Wikipedia. Löschen betrachte ich nicht als komplexe Notwendigkeit, wenn ein Element 2 Kinder hat dann wird es eben nicht gelöscht sondern nur deaktiviert. Ein abgelaufener Timer kann prinzipiell maximal nur 1 Kind haben und ist damit garantiert immer mit wenig Aufwand zu löschen. Das kostet zwar etwas Speicher und macht den Baum minimal umfangreicher aber ich denke der gesparte Aufwand, Elemente mit 2 Kindern zu löschen und anschließend noch den Baum auszubalancieren, rechtfertigt das. Wirklich genau kann man das natürlich erst sagen wenn man beides probiert hat.

Mit Präzision meine ich z.B. das ein Thread alle 40ms ein Bild berechnet und es dann ausgibt.

Gerade das wird mit dem PIT-One-Shot-Modus nicht klappen weil ja der PIT immer wieder neu zeitaufwändig konfiguriert werden muss. Nach genau 360000 Bildern wird mit der PIT-One-Shot-Methode sicher etwas mehr Zeit als ganz exakt 4 Stunden vergangen sein. Wenn Du das anders siehst dann erkläre mir das bitte mal genauer.

Wenn ich jetzt nen periodischen Timer von 15ms habe, dann kann der Fehler zw 5ms und 20ms liegen, was ich schon arg ungenau finde.

Bei einer PIT-Periode von 15ms dürfte der Jitter für ein 25Hz-Timer zwischen 0ms und 10ms liegen. Wie Du da auf 20ms kommst verstehe ich nicht. Außerdem könnte man die PIT-Frequenz ja anstatt auf 66,6666Hz auch auf 50Hz legen, mit einer 20ms PIT-Periode wirst Du der 40ms Frame-Periode bestimmt besser gerecht. Eventuell ist eine variable PIT-Frequenz, die je nach vorhandenen Timern, CPU-Last oder Energie-Spar-Wünschen angepasst wird, doch die beste Lösung für ein PIT-Only-System.

... aber ich hätte sie gerne. Das Prinzip läuft auf eine Diskussion der Art 64KiB RAM sind genug hinaus

Schon klar, ich verstehe das Du Präzision willst, geht mir genau so. Aber Du solltest erst mal klar definieren was Du unter Präzision verstehst. Willst Du das ein Film mit 216048 Frames bei 24fps genau 2:30:02 geht oder was möchtest Du?

Du möchtest doch sicher das dein OS so schnell wie möglich startet

Aber klar doch.
Genau deshalb will ich auf meiner Plattform kein BIOS o.ä., ein fest eingebauter Initial-Loader selektiert das gewünschte OS-Image im Plattform-Flash und startet es. Mein Micro-Kernel-OS initialisiert allen normalen RAM, ein paar Basis-Komponenten wie HPET u.ä. und als letztes alle CPUs und läuft dann los (es ist ab da voll einsatzfähig). Erst die User-Mode-Personality scannt anschließend den PCI(-Express)-Bus und aktiviert die gefundene HW bzw. startet die zugehörigen Treiber-Prozesse und führt dann ein Init-Script o.ä. aus. Ich hoffe damit in weniger als 10s vom Einschalten bis zu einer funktionierenden Shell (welche von der normalen HDD gestartet wurde) zu kommen. Mit einer SSD-HDD und spartanischer HW (also nur 1 mal SATA und 1 mal RS232 für Konsole) sind bestimmt auch weniger als 5s möglich. Ich hab schon verschiedene speziell angepasste Linuxe gesehen die einen graphischen Desktop in 3 bis 4 Sekunden hinbekommen, allerdings nicht auf x86 sondern auf ARM, MIPS und PowerPC. Eine einfache Shell ist da in weniger als 1 Sekunde einsatzbereit.

und dem APIC sollte man schon ne gewisse Zeit geben damit er deine Befehle ausführen kann (konkret meine ich das Starten der APs)

Echt? Ich bin geschockt! Das hätte ich im 20 Jahrhundert der x86-Plattform nicht mehr zugetraut das es noch HW gibt die so lange Bedenkzeit nur für sich selbst braucht. Die APICs haben doch keine nennenswerten externen Abhängigkeiten, wofür benötigen die mal einfach so Zeit? Kannst Du nicht alle APs gleichzeitig aktivieren?

und wenn du dann jedes Mal als kleinste mögliche Wartezeit 15ms hast summiert sich das schnell zu einer sehr langen Zeit auf.

Das kann ich natürlich nachvollziehen. Führst Du während der OS-Kernel-Initialisierung solche Wartezeiten über die selben Mechanismen wie für die User-Mode-Prozesse aus? Vielleicht lassen sich in dieser Zeit, wo ja noch keine User-Mode-Prozesse laufen, ein paar Dinge etwas anders handhaben.

Ich weiß nicht ob du jetzt genau wissen möchtest wie lange man wo warten sollte ...

Ne lass mal, ich bin wirklich geschockt das es sowas immer noch gibt. Ich dachte die Ära der C64 und ähnlicher Hardware-Komponenten ist längst vorbei.

da der Thread ja erstmal in die Queue des PIT gehen würde, da er >55,4ms schlafen möchte.

Davon bin ich auch ausgegangen. Es ging mir um den Teil wo die Restzeit kleiner als diese 55,4ms wird.

Ich speichere wie gesagt immer die Zeit ab die ich in den APIC geschrieben habe und jedes Mal wenn der Scheduler aufgerufen wird (ob die Zeitscheibe nun aufgebraucht wurde oder der Thread abgegeben hat) berechne ich die Differenz zwischen der Zeit die ich eingetragen habe und der Zeit die noch übrig ist (kannst du ganz einfach machen, in dem du den Counter ausliest und mit der Zeit eines Ticks multiplizierst). Diese nutze ich dann zum rechnen.

Das klingt für mich viel aufwändiger als es IMHO eigentlich nötig wäre. Du schreibst in den Local-APIC-Timer ja 2 verschieden Dinge rein, das finde ich persönlich verwirrend und möglicherweise etwas fehleranfällig. Was ist wenn kein APIC vorhanden ist?

Der Sinn hinter einem One-Shot-Timer ist, dass dieser nur feuert, wenn die Zeit die eingetragen wurde abgelaufen ist.

Das ist klar. Das man damit CPU-Last und Energie sparen kann ist auch klar. Beim HPET ist das auch wunderbar nutzbar weil dort ja der eigentliche Counter kontinuierlich monoton durchläuft. Beim PIT im One-Shot-Mode ist genau das nicht der Fall was bedeutet das keine vernünftige präzise Zeitquelle zur Verfügung steht (vom RTC mal abgesehen, aber ob das ne gute Idee ist wage ich zu bezweifeln).

Der Trick ist, dass ich die beiden Timer nicht synchron halten muss! Ich arbeite doch nur bei dem periodischen Timer mit absoluten Zeit und bei dem One-Shot-Timer arbeite ich mit relativen Zeiten.

Auch das erscheint mir unnötig kompliziert. Außerdem gibt es dann eine 2 Klassengesellschaft bei den Timern: solche die kürzer sind als diese 55,4ms und recht genau laufen und jene die länger als 55,4ms laufen und auf ein 55,4ms-Raster gedrückt werden (also wohl mindestens 110,8ms). Wie willst Du eigentlich den Startzeitpunkt eines Timers ermitteln (also den Moment wo z.B. ein sleep(20) aufgerufen wurde) um zu ermitteln ob er noch vor dem nächsten 55,4ms-Tick abläuft oder erst danach. Wenn Du nur diese 55,4ms-Ticks hast dann hast Du auch keine genauere absolute Zeitbasis, kannst also den Timer-Start auch nur auf 55,4ms genau bestimmen. Oder hab ich was übersehen? Oder war das die Idee mit dem auslesen des aktuellen PIT-Zählerwertes und diesen quasi als zusätzliche Genauigkeit (das meinte ich mit dem Nachkomma-Bits) zu benutzen?

aber ich dachte wir sind uns schon einig das wir ein OS für einen "normalen" PC schreiben!

Ne, also ich auf jeden Fall nicht. Den Stress tue ich mir nicht an. Vor gut 7 Jahren hatte ich mal mit dem Gedanken gespielt einen eigenen DOS-Extender, der auch ohne DOS starten können sollte, zu programmieren und mich in diesem Zusammenhang auch mal etwas mit der x86-Plattform (und nicht nur mit den x86-CPUs) beschäftigt. Ich bin dann nach einem guten halben Jahr zu dem Schluss gekommen dass das doch nichts für mich ist. Ich bin dann erstmal auf die FPGA-Programmierung gekommen und hab daher vor einiger Zeit die Idee entwickelt gleich selber ne komplette Plattform aufzubauen. Ohne all die Macken die ich in meiner Berufspraxis (und auch in privaten Projekten) mit den zur Zeit existierenden Plattformen immer wieder mal erlebe, damit will ich nicht sagen das es keine ordentlichen Plattformen gibt.

Die PCs an denen wir arbeiten/spielen/gucken sind in der Mehrzahl x86er!

Darf ich Dich an die vielen Smart-Phones erinnern? Es gibt einiges an tollen Nicht-x86-Systemen die für die normalen PC-Arbeiten absolut geeignet sind, z.B. verschiedene NetBooks mit ARM- oder MIPS-Innenleben. Das Problem, welches die Hersteller von einer aktiven Vermarktung abhält, ist einfach das kein Windows (und oft auch kein Flash) drauf läuft. Ich persönlich betrachte beides eher als Vorteil und nicht als Nachteil und hoffe das Android ein Erfolg wird und damit dann die Windows-Pflicht, die viele Hersteller empfinden, deutlich reduziert wird. Mit der Abkehr von Windows kann dann auch eine Abkehr von x86 erfolgen, ich denke beides wird langsam aber sicher an Bedeutung verlieren aber wohl auch nicht ganz verschwinden.

Ich würde mich sehr freuen auch nen potenten ARM-PC zu sehen, aber das ist leider noch nicht der Fall (und bezahlbar sollte er sein). Wenn es darum geht einen PC als User (damit meine ich nen normalen Menschen) zum Internet surfen, Dokumente schreiben, spiele Spielen und Filme gucken zu benutzen

Hast Du schon was vom iPad gehört? Die Restriktionen, die Apple künstlich einbaut, finde ich zwar ganz und gar nicht toll (deswegen werde ich wohl nie ein iPad besitzen) aber die Hardware als solche ist schon ziemlich gut (von ein paar fehlenden Schnittstellen abgesehen, die aber gewiss ganz leicht zu integrieren wären). Für ein paar Euro mehr wäre sicher auch Dual-Core und ordentlich RAM möglich, die nötigen Komponenten gibt es jedenfalls. Was der ARM-Plattform fehlt ist der Schritt in Richtung 64Bit. Das haben MIPS und PowerPC schon lange (schon vor x86) und erfolgreich (beide waren schon im High-Performance-Computing vertreten) erledigt und würden sich daher auch für dicke PCs empfehlen. Man darf also gespannt sein was die Zukunft so bringt.


Grüße
Erik