Nachrichten

801

Lowlevel-Coding / Re: Konzept für periodische Events

« am: 22. April 2010, 23:00 »

Der PIT im One-Shot-Modus ist aber keine streng monotone Zeitquelle, also für präzises Timing definitiv unbrauchbar. Ab einer bestimmten Anforderung an Präzision geht es erst mit den HPET, dafür wurde er ja schließlich eingeführt.
Das er in vielen nicht ganz so frischen PCs nicht vorhanden ist ist mal wieder ein Grund dafür warum ich x86 Scheiße finde, so wichtige Dinge erst dann zu implementieren wenn es nicht mehr anders geht ist einfach zu typisch für diese Plattform. Deshalb will ich ja unbedingt was eigenes/besseres. Wenn man sich auf x86 festlegt muss man eben unangenehme Kompromisse eingehen, Mitleid gibt es dafür von mir auf jeden Fall nicht. grin

Ich verlang ja auch gar kein Mitleid, aber Hilfe beim Leben mit solchen Sachen
Außerdem wo bleibt der Spaß, wenn man nicht solche "netten" Probleme hätte.
Ich finde mit dem APIC kann man schon ziemlich genau timen (ich habe den Overhead zum setzen eines neuen Zählwerts des APIC Timers noch nicht getestet, aber der dürfte ziemlich gering sein).

Ich habe mir schon über legt die Zeit die fürs Lesen/Schreiben beim PIT draufgeht, einfach mit drauf zu rechnen (1. kenn ich diese Zeit genau und 2. ist mein Counter dann auch ziemlich genau!).

802

Lowlevel-Coding / Re: Konzept für periodische Events

« am: 22. April 2010, 22:38 »

...hat man mit einem 100 Hz-PIC wenigstens eine konstante, streng monotone Zeitquelle.

Bitte PIT, da ansonsten Verwirrung gestiftet wird

Tickless (One-Shot) ist besser, aber regelmäßig ist einfacher und - sofern der Overhead möglichst reduziert wird - nicht wirklich langsamer.

Naja, ob ein regelmäßiger Timer einfacher ist bezweifle ich jetzt mal. Denn das war ja ein wichtiger Grund den nicht zu nehmen. Ich meine du hast nur den PIT (oder meinet wegen noch den APIC) und um das System nicht alzu sehr zu belasten hast du ne Frequenz von 100Hz. Wie willst du ne Zeit von 35ms warten (oder 16.666...ms für 60Hz, was man dann doch öfters braucht)? Den PIT mit einer Frequenz von 1000hz zu betreiben ist bestimmt nicht sonderlich toll. Da wird der Thread ja 59mal (bei einer Laufzeit von 60ms) sinnlos unterbrochen und das dann obwohl nicht mal ein Event wartet.

Mein größtes Problem ist es halt eine Art Counter auf allen Systemen (PIT und APIC) zu bekommen. Sicher die Methode mit den Events (erik weiß wovon ich spreche) ist da besser, aber selbst da gibt es bei unschönen Zahlen doch arge Probleme. Zumal in dem Fall noch das umdenken beim Programmieren dazu kommt, aber dafür lebt ja der Programmierer

@erik

Du warst mit deiner Antwort schneller als ich

Mal abgesehen vom PIT, ist den mein Konzept Eurer Meinung nach gut?

Wenn du nur den HPET nimmst, dann ist das System gut und sollte doch etwa der One-Shot Methode gleichen, aber wenn du keinen HPET hast, find ich den periodischen Timer wie gesagt eher ungünstig.

Kontext-Switches sollte man über die enthaltenden Timer in den Local-APICs machen, so wird genau die CPU unterbrochen bei welcher auch wirklich die Zeitscheibe abgelaufen ist. Ich gehe mal von SMP als zukünftigen Normalfall aus.

Tja und ich will nunmal mein OS auch auf (oder besser vorallem darauf) alten System laufen lassen. Auch wenn die CPU nen APIC hat, ist dieser meistens deaktiviert und ich kann ihn nicht nutzen, bin also auf den PIT beschränkt und da das sogar noch für P3 Systeme zutreffen kann (welche von der Leistung her, dem ATOM entsprechen sollten, wenn nicht sogar schneller) find ich das Thema noch halbwegs aktuell.
Dann kommen noch die ganzen embedded Systems dazu, welche meist auf älterer schwächerer Hardware aufbauen (mehr brauchen die auch einfach nicht) und du hast wieder nur den doofen PIT.

Im Wiki-Artikel über den HPET ist ein Link auf die Spec enthalten. Da drin ist erklärt wie man den HPET in den ACPI-Tabellen findet, zum betreiben benötigt man kein ACPI.

Das klingt doch sehr toll! Ich habe das Dokument zum HPET zwar schon, aber beim schnellen überfliegen konnte ich nichts finden, in welchen Tabellen das drin stehen soll, aber ich werds mir noch mal angucken!

Um nochmal auf deine periodischen Events zurück zu kommen. Ich würde diese trotzdem auf Basis eines One-Shot-Timers umsetzen. Also wenn es abgelaufen ist, den Event auslösen und wieder an die richtige Position in der Queue, aber der Timer sollte nur ausgelöst werden, wenn auch wirklich ein Event ausgelöst werden soll. Denn wie gesagt, gerade bei nem PC der gerade nichts macht (und das macht er bekanntlich am meisten ) wäre mir der Overhead eines periodischen Timers einfach zu groß!

Edit::

@erik

Ich bin inzwischen echt am Überlegen, ob ich mein Konzeot mit dem Counter (um ganz geringe Zeiten zu "überbrücken") zugunsten eines periodischen Events zu ersetzen. Nur weiß ich halt nicht wie ich die eigentlich Events umsetzen soll. Ich meine wenn ich ne einfache Schleife mache, die mir mit Hilfe eines Counters sagen wir 2µs wartet, wie soll ich das dann mit nem Event machen. Ich finde es halt umständlich auf irgendein Event zu warten (weil ich halt nicht weiß, wie ich es umsetzen soll).

803

Lowlevel-Coding / Re: Konzept für periodische Events

« am: 22. April 2010, 21:22 »

Um es mal kurz zu machen, ich bin eher für einen One-Shot-Timer.

Der Linux-Kernel hatte mal den Timer (unter anderem zuständig für den Scheduler) auf 1000Hz=1ms gestellt und die sind ganz schnell wieder zurück gerudert. Einmal wegen des höheren Stromverbrauchs. Denn der Timer läuft auch, wenn der PC eigentlich gar nichts zu tun hat.

Dann kommt noch der ganze Overhead für einen IRQ, alle 1ms!!!, dazu. Das ist nicht gerade wenig.

Zumal man nicht alle Probleme mit so einem Timer erschlagen kann. Was ist mit den Events die weniger als 1ms (was ich als CPU so ziemlich lange finde) "warten" wollen?

Ich habe das in meinem OS, wie gesagt, über den One-Shot Modus gelöst. Hat den Vorteil, das wenn der Computer nichts macht, auch kein Timer einen IRQ feuert (es sei denn es ist ein Event was ausgelöst werden will). Desweiteren hat der laufende Thread so effektiv mehr Zeit. Selbst wenn man jetzt nicht den PIT auch noch für den Scheduler nutzt, sondern den APIC, dann wird der Thread alle 1ms unterbrochen. Wenn man dann auch noch den APIC periodisch nutzt und sagen wir mal der feuert alle 10ms und der Thread darf 60ms laufen, dann wird er nochmals zusätzlich alle 10ms unterbrochen.

Ich behaupte mal das dieser Overhead größer ist, als die Zeit dir benötigt wird um den Timer im One-Shot-Modus zu betreiben. Ich weiß das gerade der PIT sehr sehr sehr langsam ist, aber selbst das sollte sich mit der Zeit rechnen.

Der HPET ist natürlich eine sehr feine Sache, aber halt nicht auf allen PCs verfügbar. Gut, wer anfängt ein OS zu programmieren, der sollte vielleicht auf "Altlasten" wie den PIT verzichten, aber das wift sogar Athlon XP Systeme mit raus (ich hatte selbst so eins, wo der APIC deaktiviert war). Ich programmiere aber halt auch für alte System, wo es nur den PIT gibt. Meine Lösung muss das also auch beinhalten. Wenn ich dann auch mal die Möglichkeit habe den HPET zu testen (habe nur einen PC wo der ist, auf meinem Laptop bin ich mir nicht sicher), aber wenn ich mich recht entsinne, braucht man dafür ACPI (nicht nur das parsen statischer Tabellen, sondern ausführen von deren Sprache) und das sollte für fast alle Hobby-OSs wegfallen.

Also um es zusammen zu fassen, meine Argumente dagegen wären der Overhead, Events < 1ms sind nicht möglich und der HPET ist dann doch etwas zu neu und (hier lasse ich mich gerne korregieren, dann kann ich nämlich auch endlich anfangen diesen zu programmieren) man braucht eine laufende (Interpreter) ACPI Umgebung.

804

Lowlevel-Coding / Re: spinlocks

« am: 22. April 2010, 20:59 »

Deine extrem kurze Reaktionszeit auf meine Postings finde ich jedenfalls etwas beängstigend. wink

Du schreibst aber auch meistens dann wenn ich mal wieder vor dem Rechner sitze

805

OS-Design / Re: Kernelparts in Modulen unterbringen

« am: 22. April 2010, 16:45 »

Ich kram den Thread einfach mal wieder aus. Ich bin mir nicht sicher ob ich verstanden habe was Du (=ChristianF) meinst, aber ich mache in meinem Kernel folgendes.

Ich habe bestimmte Sachen in "Module" gesteckt (z.b. PMM, IRQs usw.). Diese "Module" implementieren ein bestimmtes Interface. Mein Loader linkt dann all diese "Module" mit dem "Kernel-Modul" zusammen. So weit so sinnlos

Was will ich aber damit erreichen?!

Der Punkt ist, ich kann/will erst zur Laufzeit wissen ob der PC z.b. nen LAPIC hat oder nen IO-APIC usw. Was ich jetzt nicht will ist das der Code für diese ganze Hardware mit dem Kernel geladen wird und ich dann halt zur Laufzeit nur ein paar Funktionspointer umhänge (1. indirekte Aufrufe und 2. bleibt der Code ja im Speicher = Overhead).

Mein Kernel liegt mit samt seinen Modulen in einem Tar-Archive und der Loader guckt halt auf was für Hardware er läuft und linkt dann die entsprechenden Module zusammen und die "nutzlosen" Module können wieder freigegeben werden. So habe ich z.b. 3 verschieden PMMs, habe bei bestimmten Sachen unterschiedlichen Code für SMP und ein CPU Systeme und ich habe 2 verschiedene Module für IRQs (PIC und IO-APIC) und 2 (jedenfalls noch) verschiedene Scheduler (einmal SMP und einmal 1 CPU).

Wenn du sowas meintest, dann ja ist möglich und auch nicht wirklich sinnlos.

Drauf gekommen bin ich eigentlich darüber, dass ich es möglich machen wollte das der Kernel zur Laufzeit gepatcht werden kann und dafür brauche ich halt die ganzen Link Infos, aber das war mir dann nachher doch zu komplex und ich habe dann den schon vorhandenen Code einfach dafür genutzt.

806

Lowlevel-Coding / Re: Schedulingstrategien

« am: 21. April 2010, 22:07 »

Für jede Priorität eine eigene Queue geht nur wenn es nicht zu viele Prioritäten gibt, ansonsten müsste man die eine Queue sortieren also beim Eintragen abgelaufener Threads diese an die richtige Stelle packen.

Ich habe 32 Prios (31 normale, 1 Realtime), dann noch eine Queue wo alle Threads drin sind die nur laufen sollen wenn nichts los ist und halt den klassischen Idlethread.
Nur mal um ein Bsp. zu haben. Mit 32 Prios kann man die Organisation ganz schnell und komfortabel machen (auf 32bit CPUs, auf 64bit CPUs sogar bis 64 Prios). Du nimmst einfach ne Bitmap in der "gesetzt" heißt in der Queue ist mind. 1 Thread. Du machst also einfach nen "bts eax,[bitmap]" und schon hast du in eax die höchste Prio in der ein Thread bereit steht. Das ist genau das Verfahren was damals im Linux O(1)-Scheduler verwendet wurde und ich fands gut und habs übernommen

Damit kann ich die Zeit die die Queues für andere CPUs gesperrt sind, minimieren. Ich habe dann noch 2 (mehr fallen mir grad nicht ein) andere Sachen damit es möglichst selten vorkommt das mehrere CPUs gleichzeitg auf die Queues zugreifen wollen. Das alles funktioniert noch einiger Maßen optimal auf heutigen CPUs (8 Cores), aber bei viel mehr dürfte auch dieser Algo ziemlich ineffizient werden, weil dann die Wahrscheinlichkeit steigt das mehrere CPUs auf die Queue wollen (obwohl ich das warten bis 30-40 Instruktion (wahrscheinlich eher weniger)) ausgeführt sind, jetzt nicht sonderlich lange finde. Auf 16 CPUs hochgerechnet (15 CPUs (die erste muss ja nicht warten) * 40Instruktionen * 2Takte pro Instruktion (worst-case)) macht das 1200Takte, bei 2GHz sind das 600ns die die letzte CPU warten muss, die zweite müsste in dem Fall 40ns warten. Ich weiß jetzt nicht wieviel Takte es dauert bis etwas aus dem RAM geladen wurde, aber es waren glaub ich etwas über 100. Also das sollte noch gehen. Vorallem kommt hinzu, selbst wenn dieser Fall eintreten sollte, dann dürfte er so schnell nicht wieder auftreten, weil es unwahrscheinlich ist (bei einer Zeitscheibe von 1ms) das irgendwelche Threads zur selben Zeit fertig werden (ich ignorier jetzt mal ganz stur, das die Threads ja auch abgeben können ).

Ansonsten kann ich erik nur zustimmen.

Was ich vielleicht noch sage, jetzt muss nur noch jemand kommen der es schafft einen Algo zu entwerfen, der Queues für jede CPU hat und das ganze rechnen welcher Thread auf welcher CPU läuft, sollte in max 1200Takten passieren. Dann wären die Algos eventuell ca. gleich (da bin ich mir grad nicht sicher, denn das Entscheiden, welcher Thread auf welcher CPU, dürfte öfter passieren als der worst-case bei meinem Algo).

807

Lowlevel-Coding / Re: spinlocks

« am: 21. April 2010, 20:32 »

Wenn Du denn PIT immer wieder manuell anlaufen lässt dann geht das natürlich nach hinten los. Du brauchst zwingenst eine gleichmäßige und monotone Zeitquelle (der Counter im HPET ist da genau das richtige) ansonsten kann man damit nichts genaues timen (und die SW-Uhr geht auch noch falsch).

Es ist besser das alles in einem neuen Thread zu besprechen, sonst wird meine Antwort zu lang und zu Off!

Okay, ich bemühe mich das zeitnah zu schaffen, zur Zeit ist das leider nicht einfach bei mir. sad

Kein Prob, ich hab im Mom auch nicht so viel Zeit.

808

Lowlevel-Coding / Re: kontrolliert zurück in den 16bit-Modus

« am: 18. April 2010, 20:32 »

FreakyPenguin hat es offensichtlich auch probiert (für seinen SMP-Code) und es muss wohl funktioniert haben.

Ohne diesen Code gesehen zu haben sage ich mal nein. Du hast mich wahrscheinlich falsch verstanden.

Du kannst wunderbar Labels definieren und diese dann woanders benutzen, aber was du nicht kannst ist, Label innerhalb des 16bit Codes benutzen, die der Linker auflösen muss, dann bekommst du irgendeine Fehlermeldung von wegen das er bei 32bit ELF keine 16bit Offset auflösen kann.

Ich meine konkret:

Code: [Auswählen]

RMode:
;16bit Code Anfang
 code
 call FOO
 code
;16bit Code Ende
RModeEnd:
Irgendwo in deinem C Code kannst du "RMode" und "RModeEnd" benutzen, aber er Linker kann die externe Adresse von "FOO" nicht auflösen, da er 16Bit Adressen/Offsets in einer 32bit ELF Datei nicht kann/will.

809

Lowlevel-Coding / Re: kontrolliert zurück in den 16bit-Modus

« am: 18. April 2010, 19:53 »

...(du hast ja m.E. auf die Frage zum Linken geantwortet).

Auch. Aber eigentlich mehr wie du es hinbekommst ohne dich verrenken zu müssen. Das wichtigste und schwierigste ist halt in den RMode und wieder zurück in den PMode zu kommen. Wie man den Code dann in eine Objektdatei bekommt ist relativ einfach (und ich finde weiterhin am einfachsten, wenn man es über eine Assemblerobjektdatei löst, aber jedem das Seine).

Das eigentlich größte Problem (vorallem am Linken) ist, dass man keine Symbole benutzen darf (die vom Linker aufgelöst werden müssen), während man 16bit Code schreibt, denn das Mixen von 16bit und 32bit Offsets kann der Linker nicht (ich habs probiert ).

@bluecode

Ich denke mal wir haben aneinander vorbei geredet. Du meinst das Linken und ich wie man den Code schreibt.

810

Lowlevel-Coding / Re: Schedulingstrategien

« am: 18. April 2010, 17:55 »

Das klingt alles prioritätsfrei, da du alle Threads, die gerade lauffähig sind, in einem Round Robin auch ausführst. Erst die Ready-, dann die Run-Queue, eventuell ein Tausch, wieder von vorne. Sind beide leer => Idle.

Das könnte daran liegen, dass ich die hälfte vergessen habe

Mit Queue meine ich in dem Fall ein Array (mit 32 Einträgen => 32 Prioritäten). Zu jeder Queue gehört eine Bitmap damit ich weiß in welche Prio mind. 1 Thread ist. Das dürfte so ziemlich dem alten O(1) Scheduler von Linux entsprechen, ich fand das Konzept nicht schlecht und habe es mal ganz frech übernommen

ch redete ursprünglich von Prozessen. Tasks sind Prozesse in diesem Sinne, Threads auch. Mir ist schon klar, wozu Multithreading gut ist. Ob man Threads grundsätzlich sinnvoll findet, ist eine andere Frage.

Will man auch in Zukunft auch für aktuelle Systeme entwickeln, sollte man sich ganz schnell mit Multithreading anfreunden. Denn die Entwicklung geht in Richtung immer mehr Cores, aber dafür langsamer. Ohne Multithreading kommst du spätestens dann (obwohl das heute auch schon so ist) nicht sehr weit.

811

Lowlevel-Coding / Re: kontrolliert zurück in den 16bit-Modus

« am: 18. April 2010, 17:05 »

Das ganze hat mit Assembler herzlich wenig zu tun. Das einzige Problem mit 16Bit und C/C++ ist wohl eher einen Compiler zu finden, der das unterstützt.

Wieso hat das ganze nichts mit Assembler zu tun? Alleine schon um in den RMode aus dem PMode zurück zu springen brauchst du Assembler, weil der Compiler weder das CR0 Register noch nen Sprung den du dafür brauchst kennt! Also brauchst du sehr wohl Assembler und willst du dann noch nen BIOS Interrupt aufrufen musst du bestimmte Register mit einem bestimmten Inhalt füllen (Assembler) und du musst den Interrupt aufrufen (Assembler).

Also Mode Wechsel sind immer mit Assembler verbunden (selbst wenn du es nur über Inline-Assembler machst, bleibt es Assembler)!

Edit::

Selbst in dem Patch den du ansprichst sieht man eindeutig das es über Assembler gelöst wurde, denn die Datei mit dem Code heißt trampoline.S, was eine Assemblerdatei ist. Man bekommt GCC dazu 16bit Code zu generieren (bzw. GAS) nur funktioniert das nicht so richtig.

812

Lowlevel-Coding / Re: Schedulingstrategien

« am: 18. April 2010, 16:59 »

Auch Tasks. Oder auch Threads, genaueres ist Definitionsfrage.

Ich sag jetzt mal du bist genau in die "Falle" gelaufen die ich dir stellen wollte

Wenn du jetzt nämlich sagst das du einen Task (und damit verstehe ich dann sämtliche Threads des Tasks) möglichst lange auf einer CPU laufen lassen möchtest, wozu dann Multithreading? Dann kannst du dir den ganzen Quatsch auch sparen, denn Multithreading kann nur effektiv sein, wenn die Threads wirklich parallel laufen und nicht nur scheinbar parallel!

Wenn eine CPU wartet und die andere CPU noch Aufgaben zu erledigen hat, kann man die ja verschieben. Man weist also einer CPU ihre Prozesse zu und wenn sich die Aufteilung als schlecht erweist, wird nachträglich geändert. Das sollte auch recht sinnvoll skalieren.

Genau mit diesem Verschieben, habe ich so meine Probleme! Erstmal hast du da wie gesagt das Problem, das du in dem Moment wo du mit der Queue einer anderen CPU rumspielst, diese durch einen Lock schützen musst und das dann diese CPU warten muss (wenn sie gerade im Scheduler ist) bis du den Lock wieder freigibst. Dann kommt auch noch der ganze Aufwand um die Threads hin und her zu schieben und die richtige CPU zu finden dazu. Ich behaupte jetzt das dieser ganze Overhead meine eine globale Queue effizienter erscheinen lässt (ohne das theoretisch und praktisch beweisen zu können, ist nur mein Eindruck).

Eventuell sollte man den Scheduler mit einer gewissen Weitsicht ausstatten und selbst auf eine CPU festpinnen, so dass er die CPU-Zuteilung zentral regeln kann (und zwar so, dass er bereits die zukünftigen Zeitscheiben verteilt). Das benachteiligt interaktive Prozesse allerdings stark, so dass die Hauptqueue bevorzugt abgearbeitet werden muss; sie sollte aber die meiste Zeit leer oder sehr kurz sein (Prozesse, die ihre Zeitscheibe nicht aufbrauchen, brauchen meist die folgenden Zeitscheiben auch nicht).

Das musst du mir genauer erklären. Ich meine der Scheduler muss in dem Sinne auf jeder CPU laufen, zumindest um einen Thread, dessen Zeitscheibe abgelaufen ist, wieder in die Queue zu packen und einen neuen raus zu holen. Das einzigste was ich jetzt darunter noch verstehen würde, ist das man den Scheduler der die ganze rechnerei übernimmt welcher Thread auf welcher CPU laufen soll auf eine CPU gepinnt wird und die Scheduler auf den eigentlichen Arbeits CPUs nur noch mit ihrer eigenen Queue arbeiten (was sich aber meiner Meinung nach erst wirklich bei sehr vielen CPUs lohnt).

Prioritätsinversion kannst du vermeiden, indem du beispielsweise für jeden Durchlauf der hohen Prioritätsqueue (mind.) einen Eintrag der niederen Priorität ausführst und so ein Verhungern vermeidest. Solange du aber keine tausende Prozesse auf deinem System laufenlassen möchtest, die alle verschiedene Prioritäten haben, bleibt es ein relativ seltenes Ereignis.

Dieses oder ein ähnliches Prinzip verwendet glaub ich auch der Haiku-Scheduler.

Solch ein verhungern gibt es in meinem (momentanen) Scheduler nicht, weil ...

Ich habe ne Ready- und ne Run-Queue, ein neuer Thread kommt immer aus der Ready-Queue, ist seine Zeitscheibe aufgebraucht kommt er in die Run-Queue, ist die Ready-Queue leer, wird geguckt ob in der Run-Queue Threads drin sind, ist das der Fall werden die beiden Queues vertauscht und der Spaß geht wieder von Vorne los. Sind beide Queues leer, wird meine Idle-Queue durchgelaufen, ist auch diese leer, wird der Idle-Thread genommen (was bei mir besonders effizient abläuft).

813

Lowlevel-Coding / Re: kontrolliert zurück in den 16bit-Modus

« am: 18. April 2010, 16:42 »

Deswegen musst du das ganze ja in Assembler machen, dem ist es herzlich egal ob er nun die 16bit Variante oder die 32bit Variante von dem Opcode codieren soll und da ich das ganze nur in meinem Loader verwende bin ich auch immer unter der 1MiB Grenze.

Das ganze sieht dann in etwa so aus:

Code: [Auswählen]

use32
code
...
Sprung in den RMode
use16
.rmode:
code
Sprung in den PMode
use32
.pmode:
Der Linker sieht dann ganz normal eine Elf-Objektdatei und weiß gar nicht das da auch 16bit Code drin ist.

814

Lowlevel-Coding / Re: Schedulingstrategien

« am: 18. April 2010, 08:49 »

elegant wäre es schon, je CPU eine Queue zu haben.

Ich weiß, ich habe halt nur noch keinen Algorithmus gefunden der mir zusagt

Wichtig ist es, möglichst lange den einzelnen Prozess auf einer CPU ausführen zu lassen, wenn du ständig die CPUs wechselst, verlierst du die Cache-Inhalte.

Ich würde jetzt erstmal wissen wollen, was du unter einem Prozess verstehst.

Mein Vorschlag wäre eine große Queue pro Priorität, und zusätzlich noch eine Queue je CPU, um gewisse Prozesse auf dieser CPU festhalten zu können (bzw. auch einen Prozess von einer CPU auf eine andere verschieben zu können).

In gewisser Weise habe ich das schon, mir fehlt nur noch die Queue per CPU. Nur bin ich noch von dem einen Prozess auf einer CPU "festpinnen" nicht so richtig überzeugt. Ich wüsste jetzt spontan nicht mal wofür das gut sein sollte.

Damit kannst du neu entstehende Prozesse der CPU zuteilen, die gerade frei ist, und wenn eine CPU frei geworden ist, holst du dir aus dem Aufgabenpool den nächsten Prozess. Wenn ein Prozess blockt, wird er in den gemeinsamen Pool geschoben, wenn er seine Zeitscheibe aufgebraucht hat, landet er wieder in der CPU-eigenen Queue.

Klingt erstmal nicht schlecht, aber dadurch könnte es auch passieren das eine CPU 2 Threads hat und ne andere gar keine, weil die 2 Threads immer ihre Zeitscheibe aufbrauchen. In dem Moment wär es also besser wenn einer der beiden Threads in die globale Queue geschoben wird und dann die CPU die gar keine hat sich diesen nehmen kann. Wo wir wieder bei meinem ein Queue System wären, was in dem Moment wahrscheinlich effektiver wäre. Genauso hast du da die selben Problem die ich auch schon mit nur einer Queue habe (das andere CPUs eventuell warten müssen bis sie auf die globale Queue zugreifen können).

Auf einem normalen System haben die meisten Prozesse die gleiche Priorität, und viele verschiedene Prioritäten gibt es auch nicht (mein Hostlinux: boinc* hat 39, der Kernel hat RT, udev 16 und der Rest 20 ==> 4 verschiedene). Die Prioritätsinversion kann damit nur selten auftreten.

soweit ich weiß hat Linux 256(??) Prioritäten (-127 bis 128). Auch verwendet er (wie ich) dynamische Prioritäten (war so als ich das letzte mal geguckt habe), wird also durchaus verschiedene Prios geben. Vorallem auf meinem OS (so wie es mir momentan vorschwebt) wird es unterschiedliche geben (im Bereich von 10 bis 20) und ich würde auch diesen "seltenen" Fall gerne vermeiden. Außerdem kann ich ja vorher nicht wissen was für Programme mit welchen Prios auf meinem System laufen.

Du merkst schon, ist ein schwieriges Thema für mich

815

Lowlevel-Coding / Re: Schedulingstrategien

« am: 17. April 2010, 23:37 »

Das ist immer das erste was ich höre und damit habe ich ein Problem. Denn soweit ich mir das vorstellen kann gibt es nur genauso viele oder sogar mehr Probleme!

Einmal musst du ja irgendwie in die Queues einfügen können, also kann es an der Stelle schonmal passieren das du gerade in einer Queue was einfügst (von einer anderen CPU aus) und die CPU der die Queue gehört möchte den nächsten Thread aus dieser Queue haben, also muss die CPU warten. Toll das mache ich schon mit meiner einen Queue, also schonmal nen Minuspunkt (ich lasse mich hier aber gerne eines besseren belehren).

Dann kommt mein klassisches Bsp. CPU0 hat gerade nen Thread mit Prio 30 am Laufen und der nächste Thread hat Prio 28. Auf CPU1 läuft gerade ein Thread mit Prio 29 und der nächste hat die Prio 27. Während der Thread auf CPU0 noch viel Zeit hat und läuft, kommt auf CPU1 der Scheduler und lässt den Thread mit Prio 27 laufen, aber eigentlich müsste der Thread mit der Prio 28 laufen, der er wichtiger ist, aber er ist ja in der Queue auf der anderen CPU (nämlich CPU0). Also ist das nicht mehr sehr gerecht, um es gerecht zu machen müsste man nen ganz schönen Aufwand betreiben und da glaube ich ist mein Algo mit nur einer Queue noch am Besten.

Aber wie gesagt ich lasse mich gerne eines besseren belehren!

816

Lowlevel-Coding / Re: kontrolliert zurück in den 16bit-Modus

« am: 17. April 2010, 23:31 »

Ich hab von C aus ne Funktion callBIOS(uint32t *eax, uint32t *ebx, ...) wo du halt Pointer auf die Register (Vars dafür) übergibst. Diese dienen als Eingabe und gleichzeitig als Ausgabe, als Rückgabewert der Funktion habe ich uint32t und gebe die Flags zurück (ist gerade bei BIOS Funktionen wichtig).

Die Funktion habe ich in Assembler geschrieben, zusammengefasst springe ich zurück in den RMode hole die Register vom Stack, rufe den BIOS Int auf, ist dieser fertig packe ich die Register und die Flags wieder auf den Stack und springe zurück in den PMode.

Es ist halt wichtig das du nicht am PIT und nicht am PIC rumspielst solange du sowas machen willst (obwohl ich den PIT solange ich im PMode von meinem eigenem Handler aufrufen lasse).

Wenn du willst könnte ich dir auch den Code als (schlecht kommentiertes) Bsp. geben.

817

Lowlevel-Coding / Re: spinlocks

« am: 17. April 2010, 08:59 »

Wo genau hast Du bedenken? Soll ich dazu einen neuen Thread aufmachen?

Ein neuer Thread wäre nicht schlecht zu dem Thema (hatte ich zwar schon in einem anderem Board, aber neue Ideen sind immer willkommen). Mein Lieblingsbeispiel für Bedenken ist der PIT, weil der Zugriff alleine schon langsam ist (pro Zugriff in/out 838ns Verzögerung) und dann kann es durch das Ausschalten von den Ints auch noch zu einer zusätzlichen Verzögerung kommen und dadurch das ich den Timer (welchen ich auch immer nutze) im One-Shot-Modus benutze, kommen bei mir pro Scheduler Aufruf 5 Zugriffe (3x out, 2x in) auf den Timer (was beim PIT alleine schon ne Verzögerung von 4190ns ~ 4µs macht, pro Scheduleraufruf!). Ich bin da gerne offen für Vorschläge zur Verbesserung (gibt nur Beschränkungen die es erschweren).

Beim Zusammenfassen von Lesezugriffen, was man dann wohl eher mit "Read-Ahead" umschreiben dürfte, stelle ich mir vor das zwar auch immer gleich ganze Cache-Lines gelesen werden und nachvolgende Lesebefehle sich gegebenenfalls auch daraus bedienen (so das nach außen nur ein Lesebefehl sichtbar ist) aber diese Cache-Lines nicht in den normalen Cache kommen, um dort länger zu bleiben, sondern in den kleinen Mini-Cache, um dort möglichst bald wieder zu verschwinden.

Mit "Read-Ahead" kann ich schon mehr anfangen (und sowas haben wir ja auch in neueren CPUs). Ich weiß nicht, aber reicht nicht der Prefetcher?

818

Lowlevel-Coding / Re: kontrolliert zurück in den 16bit-Modus

« am: 16. April 2010, 19:03 »

Ich hätte mich besser ausdrücken sollen. Ich springe zurück in den RMode, calle den BIOS-Code und springe zurück in den PMode. So muss ich meinen Loader nicht komplett in ASM coden (was ich vorher gemacht habe) und es macht die Sache halt wesentlich einfacher.

819

Lowlevel-Coding / Schedulingstrategien

« am: 16. April 2010, 18:51 »

So nun mal zu einem interessanten Thema

Richtig interessant sind die ja erst auf Multi-CPU Systemen.

Ich nutze im Moment noch eine Queue wo sich alle CPUs bedienen. Ich weiß das es durchaus zu Engpäßen kommen kann, aber ich habe halt noch keine bessere Strategie gefunden mit der ich leben kann (und welche ich verstehe, das ist Voraussetzung).

Ich würde also gerne mal hören was ihr so für Strategien auf 1-CPU oder Multi-CPU System nutzen würdet/nutzt.

820

Lowlevel-Coding / Re: kontrolliert zurück in den 16bit-Modus

« am: 16. April 2010, 18:47 »

Falls ich mal meinen Senf dazugeben darf. Am besten macht sich das wenn man sowas komplett in Assembler schreibt und dann in z.B. NASM nur den Modus angibt (z.b. use16 und use32). Ich habe genau sowas genutzt um in meinem Loader auch aufs BIOS zugreifen zukönnen und trotzdem alles schön in 32bit C-Code zu schreiben.