Thema: Prozessverwaltung

[DDR-RAM]

Hi,

ich hab ja schon vor ca. 3 Monaten an der Prozessverwaltung für LOST gearbeitet gehabt und plante ein Verwaltung auf Basis von sich dynamisch verändernden Prioritäten.
Das daraus nichts geworden ist, ist ne andere Sache, ich hab mir jetzt nochmal Gedanken gemacht und habe einige Fragen.

Ich umreiße ersteinmal, was ich mir im Konkreten gedacht habe:

Code: [Auswählen]

Es gibt Prozesse und Threads.
Jeder Prozess besitzt mindestens einen Thread.
Der Prozess ist die Umgebung, also der virtuelle Adressraum, bei einem Prozesswechsel muss also das Register CR3 verändert werden.
Jeder Prozess "hat" ein Objekt, das diesen repräsentiert. Mit diesem Objekt wird ein Prozess verwaltet, es beinhaltet Angabe über die Prozess ID, die Basispriorität des Prozesses, sowie die zum Prozess gehörigen Threads.
Ein Thread ist ein Faden im Prozess, der zu dessen Ausführung beiträgt.
Jeder Thread benötigt seinen eigenen Stack und seinen eigenen CPU-Status.
Auch jeder Thread "hat" ein Objekt, das diesen repräsentiert und durch den er verwaltet wird.
Dieses beinhaltet Angaben, über die Thread ID, den CPU-Status, den Zustand des Threads (aktiv/blockiert/wartend/etc.), seine Normalpriorität und seine aktuelle Priorität.
Was hat es nun mit den Prioritäten auf sich und wie wird was verwaltet?

Also, durch Normalpriorität und Basispriorität wird durch Addition dem Thread eine Maximalpriorität zugeordnet.
Bei der Verwaltung geht es um die Zuteilung der CPU-Zeit (Systeme mit mehrern Prozessoren, werden fürs erste außen vor gelassen). Die Verwaltung der CPU-Zeit erfolgt auf Thread-Basis, da sie es sind, die CPU-Zeit beanspruchen.
Alle aktiven Threads werden in einer Priority Queue (priorisierte Warteschlange) verwaltet.
Die Priorität, nach der das entschieden wird, ist die aktuelle Priorität, die sich im Laufe verändert und bei Erzeugung des Threads auf die Maximalpriorität gesetzt wird.
Die CPU-Zeit erhält immer der Thread, der in der Warteschlange ganz vorne steht.
Dieser wird der Warteschlange entnommen (und irgendwo zwischengespeichert).
Die CPU-Zeit wird zerteilt, das heißt z.b. jede 1/512 Sekunde kommt der Scheduler zum Einsatz.
Hierbei, wird die aktuelle Priorität des laufenden Threads dekrementiert (um 1 erniedrigt).
Desweiteren wird überprüft, ob nun ein anderer Thread vorne steht oder der aktuelle Thread blockiert ist.
Der Thread wird in die Liste eingefügt (oder nicht, falls blockiert).
Der neue Thread wird aus der Warteschlange genommen und falls nötig ein CR3-switch durchgeführt und der neue CPU-Status geladen.
Wenn ein Thread Priorität von 0 erreicht, wird zu den aktuellen Prioritäten der aktiven Threads die Maximalpriorität addiert, dies hat Leider einen Zeitaufwand von n * log n, da die Queue neu geformt werden muss, gibt es verbesserungsvorschläge?

So, mal bitte Verbesserungsvorschläge:
1.) Also ich würde es noch so machen, das bei aktivierung eines THread, die Quadratwurzel seiner Maximalpriorität zu seiner aktuellen priorität addiert wird.
2.) Das Zurücksetzen der Prioritäten ist sehr unschön, gibs da was besseres?

Eigentlich ist das ganze eher ne Gedankenspiel, funktioniert glaube ich irgendwie nicht ganz, entspricht auch nicht so ganz dem Sinn.

Also wenn ich dynamische Prioritäten habe, dann sollten für mich folgende Bedingungen erfüllt sein.

1) Wenn ich zwei arbeitende Threads mit der gleichen priorität habe, sollten sich diese beide ständig (das heißt immer wenn der Scheduler aktiv wird) abwechseln.
2) Wenn ich zwei arbeitende Thread habe, sollten die Zuteilungen proportional zur Priorität sein.
3) Es soll so oft wie möglich gewechselt werden (Spezialfall davon ist 1)
4) Es sollen Threads des Prozesses des aktiven Threads bevorzugt werden.

Also wenn jemand was hat, was für mich interessant sein könnte, immer her damit.

MfG
DDR-RAM

edit:
ich hab da noch ne Gute Idee gerade unter der Dusche empfangen, ich werde sie morgen posten

[DDR-RAM]

Wollt ihr nix zu sagen ne?

Also, mein neues Konzept:

Code: [Auswählen]


Als das Grundgerüst mit Threads und Prozessen habe ich oben schon beschrieben.
Aber und jetzt kommt es:
es soll zwei priorisierte Warteschlangen geben,
die eine ist gerade aktive und die andere ist die wartende.
Für die priorität eines Threads gilt jetzt, je kleiner desto besser, wie man sie sich diese errechnet, ist erstmal egal.
Sie muss aber größer 0 sein, ein Thread mit der Priorität würde bei diesem Konzept in Echtzeit laufen, das heißt der Scheduler würde ihn (sogut wie) niemals "absetzen".
Also jeder Thread erhält wieder eine dynamische Priorität, diese wächst aber und sinkt nicht, dafür werden Threads mit möglichst kleiner Priorität bevorzugt.
Es kommt immer der Thread zum Zuge, der die niedrigste dynamische Priorität hat, seine dynamische Priorität wird dadurch, aber um seine Priorität erhöht (das heißt bei niedriger Prioritätszahl, gelangt man nicht so schnell nach oben, wie mit hoher und damit kriegt man öfter die CPU).
Ist ein Thread bei einem vordefinierten Wert angelangt z.b. 256 kommt er in die wartende Warteschlange und erhält eine dynamische Priorität von 0.
Auch ein neuer Thread oder einer, der aus seiner Blockierung erwacht, kommt in die wartende Warteschlange und erhält eine dynamische Priorität von 0.
Sind in der aktiven Warteschlange keine Threads mehr enthalten, werden beide Warteschlangen vertauscht.
Kriterien für die priorisierung in den Warteschlangen, sind wie schon erwähnt die dynamische Priorität an erster stelle (kleiner ist höher) und die konstante Priorität an zweiter Stelle (auch hier kleiner ist höher).

problematisch bei diesem Modell ist, das Threads, die oft blockiert werden, wie solche, die Eingabedaten empfangen im Nachteil sind, da sie nach einer Blockierung immer wieder in der wartenden Warteliste landen.

Ein Ansatz dafür, wäre falls die Threads noch wieder auf die CPU-wartend werden, bevor die Warteschlangen vertauscht worden, sie mit der dynamischen Priorität unter der sie blockiert wurden (bzw. dem maximum ihrer damaligen dynamischen Priorität und der dynamischen Priorität, des aktuell aktiven Threads, damit sie keinen zu großen Vorteil erhalten), wieder in die Warteliste einfügt, was in den meisten Fällen bewirkt, das die Threads sofort wieder zum Zuge kommen.
Falls die Listen zwischenzeitlich gewechselt wurden, könnten sie mit einer dyn. Priorität des aktiven Threads in die aktive Liste eingefügt werden.
So kämen sie mit einer gerechten Priorität wieder ins Spiel, kämen aber sofort wieder an die Reihe.


Hört sich für mich persönlich ziehmlich gut an, hab noch keine Mängel entdeckt, vielleicht findet ihr welche.

MfG
DDR-RAM

[joachim_neu]

Eigendlich hab ich noch garnicht verstanden, wofür Threads überhaupt sein sollen. Im Eigendlichen sind die doch nix anderes als Prozesse... Bitte um Aufklärung!

[JensFZ]

Im großen und ganzen hast du recht dass Threads mit Prozessen gleichzustellen sind aber Threads sind keine kompletten Programme sondern nur teile (ggf. nur einzelne funktionen). Ein Prozess kann mehere Threads beinhalten. Ein thread ist z.B. bei spiele sehr entscheidend, wenn man z.B. die KI, die Physik und die eingaben der Spieler koordinieren muss (sollte ja alles gleichzeitig ablaufen). Somit kann man für solche Zeitkritischen Funktionen einen eigenen Thread erstellen, damit ein Synchrones arbeiten vorgetäuscht wird.

Also nochmal kurz:
Prozess = Programm (bin mir nicht ganz sicher aber beinhaltet glaube mindestens einen Thread)
Thread = Teil eines Programms

[Legend]

Der eigentliche Vorteil von Threads liegt darin das sie sich einen Addressraum teilen - dadurch kann man beim Sprung von Thread zu Thread in einem Prozess sich den Wechsel von CR3 sparen, so das es praktikabel ist ein Programm wie mein Vorposter schon gesagt hat, in mehrere Befehlsstränge zu unterteilen.

[DDR-RAM]

Im großen und ganzen hast du recht dass Threads mit Prozessen gleichzustellen sind aber Threads sind keine kompletten Programme sondern nur teile (ggf. nur einzelne funktionen). Ein Prozess kann mehere Threads beinhalten. Ein thread ist z.B. bei spiele sehr entscheidend, wenn man z.B. die KI, die Physik und die eingaben der Spieler koordinieren muss (sollte ja alles gleichzeitig ablaufen). Somit kann man für solche Zeitkritischen Funktionen einen eigenen Thread erstellen, damit ein Synchrones arbeiten vorgetäuscht wird.

Also nochmal kurz:
Prozess = Programm (bin mir nicht ganz sicher aber beinhaltet glaube mindestens einen Thread)
Thread = Teil eines Programms

Code: [Auswählen]

Es gibt Prozesse und Threads.
Jeder Prozess besitzt mindestens einen Thread.
Der Prozess ist die Umgebung, also der virtuelle Adressraum, bei einem Prozesswechsel muss also das Register CR3 verändert werden.
Jeder Prozess "hat" ein Objekt, das diesen repräsentiert. Mit diesem Objekt wird ein Prozess verwaltet, es beinhaltet Angabe über die Prozess ID, die Basispriorität des Prozesses, sowie die zum Prozess gehörigen Threads.
Ein Thread ist ein Faden im Prozess, der zu dessen Ausführung beiträgt.
Jeder Thread benötigt seinen eigenen Stack und seinen eigenen CPU-Status.
Auch jeder Thread "hat" ein Objekt, das diesen repräsentiert und durch den er verwaltet wird.


Ich stimm dir also voll und ganz zu, da ich nie etwas anderes behauptete
Bei mir ist ein Prozess kein Thread, er besitzt mindestens einen, maximal soviele, bis der (virtuelle) Speicher platzt.

Ich wollt eigentlich mehr was hören in Bezug auf das Schedulingverfahren,
falls das so in Ordnung ist, könnte ich mich nochmal daran machen, dieses für LOST zu implementieren, da Roshl meinte, dass er seinen Code für sich behält (so ähnlich jedenfalls )

MfG
DDR-RAM

[joachim_neu]

Da halte ich aber ehrlich gesagt ein Verfahren mit gleichem Adressraum (oder SharedMemory) und mehreren Prozessen (die von einem Prozess aus gestartet werden) sinnvoller, als haufenweise Threads...

[Roshl]

Wie wäre es erstmal mit einen Scheduling das einfach nur der Reihe nach durch die Prozesse switch. Damit erstmal überhaupt was da ist. Ändern kann man das später doch ohne Probleme.

[Legend]

Da halte ich aber ehrlich gesagt ein Verfahren mit gleichem Adressraum (oder SharedMemory) und mehreren Prozessen (die von einem Prozess aus gestartet werden) sinnvoller, als haufenweise Threads...

Shared Memory erspart dir nicht das wechseln von CR3!
Mehere Prozesse in einem Addressraum, das klingt nach einem Single Addressspace System, und meint was anderes.
Der Unterschied ist, das Threads sich bewusst sind das sie in einem gemeinsamen Addressraum leben, während Prozesse voreinander geschützt werden müssen.

[DarkThing]

Noch ein Beispiel für Threads:
Ein Programm bekommt Daten, verarbeitet diese und speichert sie.
Jedem der drei Schritte könnte man in einen Thread packen. Der erste Thread würde Daten lesen und zwischenspeichern. Unabhängig davon könnte der 2. Thread die Daten aus dem Buffer holen und verarbeiten. Wenn jetzt die Festplatte längere Zeit durch einen anderen Prozess blockiert wird, kann der erste Prozess die Arbeit vorrübergehend einstellen, der zweite arbeitet aber weiter die Daten ab.

--------

Threads werden aber auch von manchen Programmen selber verwaltet - ohne das der Kernel Einflus darauf hat. Das  heißt das ein normaler Prozess einen eigenen Scheduler beinhaltet um selber Threads zu schedulen. Der Kernel weiß in dem Fall gar nichts von den verschiedenen Threads.

[Legend]

Genau das ist die Idee hinter asynchronem I/O!

[joachim_neu]

Da halte ich aber ehrlich gesagt ein Verfahren mit gleichem Adressraum (oder SharedMemory) und mehreren Prozessen (die von einem Prozess aus gestartet werden) sinnvoller, als haufenweise Threads...

Shared Memory erspart dir nicht das wechseln von CR3!
Mehere Prozesse in einem Addressraum, das klingt nach einem Single Addressspace System, und meint was anderes.
Der Unterschied ist, das Threads sich bewusst sind das sie in einem gemeinsamen Addressraum leben, während Prozesse voreinander geschützt werden müssen.

Natürlich. So ist es auch. Aber es können sich ja auch einfach Prozesse (dann mit "Abstimmung" über IPC) zusammenklinken. Oder eben gleich im Adressraum gestartet werden (müssen sie aber nicht). Das ist dann wie ein Thread und jeder ist sich bewusst, dass es einer ist.  

[Legend]

Damit haste Threads bestenfalls neu erfunden!
Und Prozesse welche sich Addressräume teilen und welche die sie sich nicht teilen, wie es auch bei Linux ist, wenn Threads vom Kernel verwaltet werden, was dort im wesentlich per "fork" ohne neuen Addressraum passiert.
Sinn würde das noch machen wenn Prozesse die nichts voneinander wissen in gemeinsame Räume gepackt würden - dafür bräuchte man aber ne sichere Sprache.
Von daher finde ich die Aufteilung in Threads und Prozesse sehr viel übersichtlicher, dann sehe ich in der Prozessliste z.B. nur einen Apache und nicht seine 50 Worker "Threads".

[DDR-RAM]

Marktführer windoof hat Threads und Prozesse,
ich bin daran gewöhnt, dieses Konzept ist ziehmlich gut, sehr kompliziert ist es auch nicht.
Ich dachte es würde sich von selbst verstehen, das wir Threads und Prozesse haben.
Mein eigentliches Anliegen, war wie gesagt die Frage, ob dieses Schedulingverfahren gut oder schlecht ist bzw. was ist gut, was ist schlecht.

MfG
DDR-RAM

[Legend]

Ich muss ganz ehrlich sagen, das Fehlen von Absätzen hält mich etwas vom lesen ab!

[DDR-RAM]

Da sind Absätze

[Legend]

Ich glaube du brauchst ein paar Queues mehr.
z.B. eine niedrig priorisierte Queue, eine hochpriorisierte Queue, und eine normale Queue. Innerhalb einer Queue kannste dann probieren mit einer dynamischen Priorität (wobei ich bei denen immer sehr vorsichtig bin) etwas gerecht zu verteilen, aber sobald ein Prozess in der hochpriorisierten Queue Zeit braucht, kommt dieser sofort zum Zuge.

[DDR-RAM]

Hm, also eigentlich wollte ich nicht, dass höherpriorisierte Threads niedrigerpriorisierte komplett abwürgen, sondern nur häufiger als andere an die CPU kommen.

Falls ein hochpriosierter Thread gerade aus seiner Blockierung erwacht bekommt er die CPU ja (in den meisten Fällen) sofort.

Beispiel 2 Threads, einer Prio 2, der andere Prio 4.
beide sind sagen wir mal bei 0 und erstmal arbeiten beide sagen wir Zeitscheiben lang.
Dann haben beide Prio 20, der mit Prio zwei war 10 mal, der andere 5 mal dran.
Thread mit prio 2 wird kurz blockiert.
Thread mit prio 4 kommt ran, liegt bei 24.
Thread mit prio 2 wird wieder entblockiert und kommt sofort an die CPU.

auch zum Thema aber nicht auf Legend antwortend:
Bei Synchronisationsmechanismen (Semaphore, Mutex, CriticalSection) sollte, falls ein Thread mit niedriger Prio einen mit hoher Prio blockiert, der mit niedriger vorübergehend in seiner Priorität gesenkt (also schneller abgearbeitet) werden.
Ich werd für LOST bald ein Kernel-Modell vorlegen.

MfG
DDR-RAM

[Legend]

Wenn du einen Microkernel hast, ist es evtl. sogar sehr wichtig das es hochpriorisierte Threads geben kann die andere abwürgen können, denn die Kommunikation mit der Hardware ist durchaus zeitkritisch.
Das ist dann aber ein Spezialfall für Treiber.

Was das andere geht, das grosse Problem der Prioritätsinversion. Jo, da hilft wohl nur entweder nicht reinlaufen oder aber schnell abarbeiten.

[DDR-RAM]

Das widerspricht aber dem Microkernelkonzept aber, da durch vollständige Blockierung anderer Threads die Stabilität des Systems extrem gesenkt wird

MfG
DDR-RAM