Thema: Threads blockieren und wieder aufwecken

[FlashBurn]

Also erstmal was gibt es alles, wo ein Thread blockiert?

Mir fallen spontan ein, sleep(), semaphoreAcquire() und wait(). Die ersten beiden machen mir keine Probleme, aber letzterer. ICh weiß gar nicht ob es normalerweise unterstützt wird, das ein Thread ein warten kann bis er wieder geweckt wird? Ich wollte das für eine UserSpace-Sachen nutzen.

Um mal ein ganz einfaches Bsp. für mein eigentliches Problem zu bringen.

CPU A:
Ein Thread will die Semaphore bekommen. Also holt er sich den Lock, dekrementiert den Counter und stellt fest das er warten muss. Der Lock wird wieder freigegeben und der Thread wird blockiert.

CPU B:
Ein Thread will die Semaphore freigeben. Also holt er sich den Lock (der auf CPU A gerade freigeben wurde), inkrementiert den Counter und stellt fest das er einen Thread aufwecken muss. Der Lock wird wieder freigegeben und der Thread wird aufgeweckt (genau der von CPU A).

Problem ist nun, dass es ja passieren könnte, dass CPU B den Thread schneller aufweckt als CPU A den Thread blockieren konnte. Lösung dafür wäre auch ne Art Semaphore, nämlich das Aufwecken wäre ein Freigeben und das Blockieren ein Anfordern.

Mit meinem wait() Syscall (und dem entsprechendem resume()) könnte es nun aber passieren, dass die Aktion resume() mehrmals aufgerufen wurde und der Thread also bei mehreren wait()´s nicht blockiert.

Daher meine Frage, was wäre besser, ne Semaphore zu nutzen wo der Counter beliebig groß werden kann oder ne Semaphore zu nutzen wo der Counter max 1 werden kann?

Oder ist das totaler Schmarrn?

[bluecode]

Normalerweise werden Semaphores vollständig vom Kernel implementiert, da tritt das Problem wohl nicht auf. Was du suchst ist das was man unter Linux Futex (= Fast Userspace Mutex) nennt. Möglicherweise möchtest du dir dazu den Teil des ersten Papers auf wikipedia, in dem es um eben diese geht, anschauen. Ich hab es mir nicht durchgelesen, aber sie scheinen genau das Problem anzusprechen (ich hab aber ehrlich gesagt kein interesse da weiterzuschauen):

[...] Due to such race conditions, a lock can receive a wakeup before the waiting process had a chance to enqueue itself into the kernel wait queue. We describe below how various implementation resolved this race condition as part of the kernel service.

[FlashBurn]

Normalerweise werden Semaphores vollständig vom Kernel implementiert, da tritt das Problem wohl nicht auf.

Dumm nur das hier wir den Code dazu schreiben

Mir geht es ja genau darum, wie man das Problem entweder vermeidet oder noch besser damit umgeht.

Was du suchst ist das was man unter Linux Futex

Jap, die kenne ich, nur die Sachen mit den Race-Conditions habe ich mir noch nicht angeguckt, werde ich aber gleichmal machen.

[Jidder]

Die Funktionen mset/mclear von BSD gehen wohl auch in diese Richtung. http://docs.freebsd.org/44doc/papers/newvm.html

[FlashBurn]

Das finde ich ja gut, genau die selbe Idee (Semaphore im SharedMem für IPC) wollte ich für meine Pipe´s nutzen So schlecht kann die also nicht sein.

Trägt nur leider nix zum Thema bei Werde aber trotzdem mal gucken, ob die auch irgendwelche Race-Conditions haben und wie die gelöst wurden.

Edit::

@bluecode
Also soweit ich es verstanden und gefunden habe, machen sie genau dass, was ich in meiner Idee schon meinte. Nen Counter der bei jedem resume() erhöht wird und bei jedem wait() erniedrigt wird. So umgeht man diese Race-Condition.

OT::

Dazu habe ich mal wieder gesehen wieso ich den Linux-Kernel aus Design-Sicht nicht mag

[Jidder]

Das finde ich ja gut, genau die selbe Idee (Semaphore im SharedMem für IPC) wollte ich für meine Pipe´s nutzen So schlecht kann die also nicht sein.

Ich muss meine Aussage leider relativieren. Nach kurzem Googeln scheint es so, dass das in dem Umfang nie im offiziellen Kernel eingeführt wurde.

Das Zitat von der Seite (Section 2.2) wollte ich ursprünglich noch in meinem Post unterbringen:

In all the above examples, there appears to be a race condition. Between the time that the process finds that a semaphore is locked, and the time that it manages to call the system to sleep on the semaphore another process may unlock the semaphore and issue a wakeup call. Luckily the race can be avoided. The insight that is critical is that the process and the kernel agree on the physical byte of memory that is being used for the semaphore. The system call to put a process to sleep takes a pointer to the desired semaphore as its argument so that once inside the kernel, the kernel can repeat the test-and-set. If the lock has cleared (and possibly the wakeup issued) between the time that the process did the test-and-set and eventually got into the sleep request system call, then the kernel immediately resumes the process rather than putting it to sleep. Thus the only problem to solve is how the kernel interlocks between testing a semaphore and going to sleep; this problem has already been solved on existing systems.

[FlashBurn]

Ich muss meine Aussage leider relativieren. Nach kurzem Googeln scheint es so, dass das in dem Umfang nie im offiziellen Kernel eingeführt wurde.

Im Linux-Kernel ist es drin und ich musste jetzt feststellen, dass die Futex´s doch auch für inter-process-communication genutzt werden und nicht nur für intra.

[Svenska]

Das Problem sollte eigentlich nicht auftreten, wenn der Scheduler selbst weiß, wenn ein Thread auf ein Lock wartet und ihn unblockt, wenn das Lock gerade frei ist. Sollte sich zwischenzeitlich jemand anders bereits das Lock wieder gekrallt haben, kann der gerade geweckte Thread das Lock nicht bekommen und geht halt weiterschlafen.

Allerdings kann ich nicht einschätzen, wieviel Performanceverlust das mit sich bringt, wenn der Scheduler anfängt, Lock-Variablen zu inspizieren...

Vielleicht schreib ich aber auch komplett am Problem vorbei, weiß ich nicht.

[FlashBurn]

@svenska

Ganz allgemein ist das Problem, wie geht man damit um, dass ein Thread blockiert und bevor er das erfolgreich abschließen kann, wird er von einem anderen Thread aufgeweckt. Da müssen keine Locks im Spiel sein.

[Svenska]

Naja, ein Thread ist blockiert oder er ist nicht blockiert... dazwischen sollte es keine halben Zustände geben. Schlafen tut ein Thread erst, wenn er vollständig eingeschlafen ist, nicht vorher.

Der Rückgabewert der Aufweckfunktion sollte das wiederspiegeln. Wenn der aufweckende Thread weiß, dass der andere Thread eigentlich hätte schlafen müssen, dann kann er das Wecken ja später nochmal probieren und so den Deadlock vermeiden.

[FlashBurn]

Wenn der aufweckende Thread weiß, dass der andere Thread eigentlich hätte schlafen müssen, dann kann er das Wecken ja später nochmal probieren und so den Deadlock vermeiden.

Das würde bei mir dann heißen das ich im Kernel so lange probiere den Thread aufzuwecken bis das geklappt hat (weil sowas überlässt man nicht dem User, zumal es dann noch unperformanter wird). Glaubst du wirklich dass das eine gute Idee ist?

Ich denke mit meinem Counter bin ich ganz gut dabei (entspricht auch in etwa der Lösung von Linux und co). Die Frage die ich mir da dann stelle ist halt, sollte man es zulassen das der Counter nen größeren Wert als 1 annimmt oder nicht?

Wie sollte man eigentlich entscheiden ob ein Thread A ein Thread B aufwecken darf?

[Svenska]

Wenn du einen Thread fünfmal aufweckst, dann geht der die nächsten fünf Male nicht mehr schlafen. Ist (mehrfaches) präventiv-wecken sinnvoll?

Ist es überhaupt sinnvoll, einen Thread aufzuwecken, der garnicht schläft? Um den Deadlock zu vermeiden, reicht ja ein einzelner erneuter Weckversuch, nachdem der betroffene Thread garantiert einmal dran gewesen ist (und die Möglichkeit hatte, endgültig einzuschlafen). Du sollst den Kernel nicht endlos auf den Schlaf eines Userspace-Threads warten lassen.

Außerdem im Fall der Race Condition fällt mir jedenfalls kein Grund ein, warum ein grundloses Aufwecken sinnvoll sein sollte.

[FlashBurn]

Ist (mehrfaches) präventiv-wecken sinnvoll?

Das ist ja meine Frage

Ist es überhaupt sinnvoll, einen Thread aufzuwecken, der garnicht schläft?

Es kann eben den Fall geben das Thread A den wait Syscall (aus welchem Grund auch immer) macht und bevor dieser ausgeführt werden kann kommt der Scheduler und Thread B ist dran, Thread A soll laut Thread´s B infos auf das Aufwecken warten. Thread B erledigt seine Sachen und weckt Thread A auf, dieser schläft noch gar nicht und ein resume() ist in meiner Welt immer erfolgreich (hat keinen Rückgabewert) und damit ist die Sache für Thread B auch beendet. Thread A kommt wieder auf die CPU und legt sich endlich schlafen, dumm nur das es wohl für immer sein wird

Das Problem existiert durchaus, deswegen mussten sich ja auch die Linuxer Gedanken darüber machen.

Um den Deadlock zu vermeiden, reicht ja ein einzelner erneuter Weckversuch, nachdem der betroffene Thread garantiert einmal dran gewesen ist (und die Möglichkeit hatte, endgültig einzuschlafen).

Was ist, wenn der Thread aber eine so niedrige Priorität hat das er ne Weile nicht mehr dran kommt bzw. eventuell gar nicht mehr, weil der andere Thread ne höhere Priorität hat?

Dann hätten wir da auch noch die Sache damit das man damit ja mehrmals in den Kernel muss, für einen Syscall der eigentlich immer klappen sollte.

Außerdem im Fall der Race Condition fällt mir jedenfalls kein Grund ein, warum ein grundloses Aufwecken sinnvoll sein sollte.

Ich bin mir nicht sicher ob ich verstanden habe was du damit meinst, aber mit meinem Counter würde der Thread B den Counter von Thread A erhöhen (resume() für Thread A) und wenn Thread A wieder an der Reihe ist (also den wait() Syscall ausführt), dann würde er nicht blockieren, sondern gleich wieder zurück gehen.

[erik.vikinger]

Hallo FlashBurn,


hier zeigt sich IMHO ein weiteres Problem mit Deinen Problemlösungsstrategien. Das bedingungslose wait() ist offensichtlich nicht geeignet Dein Problem zu lösen. Warum schaust Du Dich nicht nach Alternativen um?

Ich würde hierfür Events vorschlagen. In meiner (naiven) Welt hat ein Event (der natürlich im Kernel implementiert sein muss) 2 Syscalls: event_trigger(handle) und event_wait(handle,timeout) und einen internen Zähler der Null (niemand wartet), positiv (ein oder mehrere Threads warten) oder negativ (es wurde ein oder mehrmals getriggert ohne das jemand gewartet hat) sein kann. Beim event_wait() wird der Zähler inkrementiert (falls er >=0 ist) und der Thread hinten an eine geordnete Liste angehängt (und natürlich dem Scheduler entzogen da er ja nun blockiert ist), bei negativem Zähler wird dieser auch inkrementiert aber der Thread wird nicht blockiert (da hiermit nur ein vorangegangenes Trigger abgeholt wird). Das event_trigger() dekrementiert immer den Zähler und prüft dann ob dieser vorher größer 0 war, falls ja wird der vorderste Thread aus der Liste aufgeweckt (und natürlich auch entfernt) da die Liste bei einem Zähler >0 nie leer sein kann. Da beide Syscalls atomar arbeiten kann es auch keine Race-Conditions o.ä. geben. Als zusätzliches Feature kommt beim event_wait() noch das TimeOut hinzu (welches genau diesen Thread wieder aus der Blockierung befreien kann, dabei muss natürlich auch der Zähler dekrementiert und dieser Thread korrekt aus der Liste entfernt werden) welches IMHO sehr sinnvoll ist und dann könnte man noch überlegen ob man die Liste nicht noch nach den Prioritäten der wartenden Threads sortiert damit immer zuerst die mit der höchsten Priorität geweckt werden (das ist aber kein triviales Feature weil es hier u.U. dazu kommen kann das Threads mit niedriger Priorität permanent nach hinten verdrängt werden und so total verhungern). Der einzigste Nachteil dieser Methode ist das Du für so eine User-Mode-Semaphore immer zusätzlich einen zugehörigen Event im Kernel einrichten musst aber das dürfte wohl verschmerzbar sein.

Ansonsten bleibt nur noch zu sagen das wenn man einen Lock üblicherweise so lange benötigt das es sich für die wartenden Threads lohnt sich schlafen zu legen (was ja auch CPU-Zeit kostet) das es dann wohl meistens geschickter ist gleich eine Semaphore zu benutzen die komplett vom Kernel verwaltet wird. Für recht kurze Locks wartet man doch üblicherweise per PAUSE so das die von Dir beschriebenen Probleme eh nicht auftreten.


Grüße
Erik

[Svenska]

Ist es überhaupt sinnvoll, einen Thread aufzuwecken, der garnicht schläft?

Es kann eben den Fall geben das Thread A den wait Syscall (aus welchem Grund auch immer) macht und bevor dieser ausgeführt werden kann...

Das ist der Fall der Race-Condition: A geht schlafen, B weckt ihn gleichzeitig wieder auf, Wettlauf.

Ich frage, ob es einen sinnvollen Grund gibt, ein wakeup() for einem wait() zu machen. Nicht gleichzeitig, sondern irgendwann früher. Ich sehe keinen, deswegen habe ich da auch kein Problem.

Um den Deadlock zu vermeiden, reicht ja ein einzelner erneuter Weckversuch, nachdem der betroffene Thread garantiert einmal dran gewesen ist (und die Möglichkeit hatte, endgültig einzuschlafen).

Was ist, wenn der Thread aber eine so niedrige Priorität hat das er ne Weile nicht mehr dran kommt bzw. eventuell gar nicht mehr, weil der andere Thread ne höhere Priorität hat?

Wenn dein Scheduler einen niedriger priorisierten Thread verhungern lässt, Pech gehabt. Sowas macht man nicht.

Ich bin mir nicht sicher ob ich verstanden habe was du damit meinst, aber mit meinem Counter würde der Thread B den Counter von Thread A erhöhen (resume() für Thread A) und wenn Thread A wieder an der Reihe ist (also den wait() Syscall ausführt), dann würde er nicht blockieren, sondern gleich wieder zurück gehen.

Also präventives Wecken. Naja, wenn du das für sinnvoll erachtest, dann implementier es.

Eriks Variante hat auch was für sich, erlaubt aber auch das präventive Wecken.

Gruß,
Svenska

[FlashBurn]

Das bedingungslose wait() ist offensichtlich nicht geeignet Dein Problem zu lösen. Warum schaust Du Dich nicht nach Alternativen um?

Es geht darum auch nen Futex zu implementieren bzw. dem User die Möglichkeit zu geben was eigenes auf basis von wait() und resume() zu entwickeln und vorallem geht es darum nicht für jede Aktion in den Kernel zu müssen.

In meiner (naiven) Welt hat ein Event (der natürlich im Kernel implementiert sein muss) ...

Sorry, schon mal schlecht Ich muss für jede Aktion in den Kernel ohne das es nötig wäre. Erfüllt leider nicht die Anforderungen. Um es nochmal zu sagen, ich habe Anforderungen und die müssen erfüllt werden.
Wenn ein Kunde ein Auto will, kannst du ihm doch nicht einfach nen Flugzeug hinstellen (du kannst schon, aber hast einen Kunden weniger ).

Wieso gehst du den unkonventionellen Weg (du machst es genau umgekehrt wie bei einer Semaphore) und nutzt nicht ne Semaphore dafür. Die gibt es schon und du musst nix neues erfinden was es schon gibt

Ansonsten bleibt nur noch zu sagen das wenn man einen Lock üblicherweise so lange benötigt das es sich für die wartenden Threads lohnt sich schlafen zu legen (was ja auch CPU-Zeit kostet) das es dann wohl meistens geschickter ist gleich eine Semaphore zu benutzen die komplett vom Kernel verwaltet wird. Für recht kurze Locks wartet man doch üblicherweise per PAUSE so das die von Dir beschriebenen Probleme eh nicht auftreten.

Ich weiß aber selbst zur Laufzeit nicht wie lange ich solch einen Lock halten werden, was also machen? Du bist doch auch nicht fürs Kopieren, aber wertvolle Zeit beim Spinnen verbraten?!

Spinlocks im UserSpace sind weder fair noch skalieren sie gut (dann kommt noch das nötige Locking des Speicherbuses dazu), sicher um nur 2 Variablen zu ändern funktioniert das, aber sobald ich entweder nicht sagen kann wie lange der Lock gehalten wird oder die Zeitspanne lange wird, ist ne Semaphore besser. Bekommt man allerdings meistens den Lock, lohnt es sich das man sich das in den Kernel Gehen sparen kann.

Ich frage, ob es einen sinnvollen Grund gibt, ein wakeup() for einem wait() zu machen. Nicht gleichzeitig, sondern irgendwann früher. Ich sehe keinen, deswegen habe ich da auch kein Problem.

Mir fällt kein Sinnvoller Grund ein, ein wakeup() vor einem wait() zu machen. Es kann aber mehr oder weniger Zeitgleich bzw ungünstig (wie schon mehrmals beschrieben) passieren und da hat man dann ne Race-Condition und das muss man ja irgendwie ausmerzen. Dazu halt der Counter und er ist halt einfacher zu implementieren wenn ich viele wakeup()´s vor einem wait() zulassen. Ansonsten müsste ich irgendwie gucken das er nie größer als 1 wird. Kann man wahrscheinlich per cmpxchg machen, bin mir gerade nicht sicher wie ich das genau machen könnte.

Die andere Frage ist dann, würde es denn Probleme geben, wenn man viele wakeup()´s vor einem wait() machen kann? Auch hat sich noch keiner dazu geäußert wie man es am besten löst das nicht jeder Thread jeden x-beliebigen Thread aufwecken kann. Alzu komplexe Rechte-Verwaltung wollte ich eigentlich nicht im Kernel haben.

[erik.vikinger]

Hallo,

Eriks Variante hat auch was für sich

Na klar, meine Ideen sind (fast) immer gut!
Vor allem möchte ich diese Events auch gleich noch vom Kernel automagisch periodisch triggern lassen können (das Konzept hatte ich ja schon mal vorgestellt) dann habe ich einen simplen Mechanismus mit dem man viele tolle Sachen machen kann.

erlaubt aber auch das präventive Wecken.

Genau darum geht es ja. Wenn Du merkst das Du eine Ressource nicht bekommst und dann eben warten möchtest dann kann dazwischen immer mal der Scheduler zuschlagen (dem User-Mode zu erlauben die INTs abzuschalten ist auf gewöhnlichen Plattformen keine gute Idee), von daher kann es eben passieren das erst geweckt wird und dann der Versuch kommt zu schlafen. Entweder man hat so eine Funktionalität oder man muss das immer atomisch machen und das geht meistens nur im Kernel und erfordert damit grundsätzlich mindestens einen Syscall und den möchte man ja wegen der lieben Performance vermeiden.

Sorry, schon mal schlecht Ich muss für jede Aktion in den Kernel ohne das es nötig wäre. Erfüllt leider nicht die Anforderungen....

Ich fürchte Du hast mich missverstanden. Ich meine Du sollst anstatt Deinem wait()/resume() mein event_wait()/event_trigger() zusammen mit Deiner User-Mode-Semaphore benutzen. Da musst Du genau so oft in den Kernel wie mit Deiner Idee nur das Du das Problem mit den Race-Conditions grundsätzlich nicht bekommst.
Übrigens müsstest Du mit Deiner Implementierung auch eine Liste mit den blockierten Threads pflegen damit derjenige der die Semaphore momentan hat auch weiß wen er wecken muss, und wenn Du diese Semaphore z.B. innerhalb von Shared-Memory einrichtest damit diese von mehreren Prozessen benutzt werden kann dann muss auch diese Liste komplett im Shared-Memory liegen (damit jeder eintragen/austragen kann) und dafür möchte in kein malloc bauen müssen (irgendwo her müssen ja die neuen Listen-Elemente kommen). Hast Du dafür schon eine gute Lösung?

Um es nochmal zu sagen, ich habe Anforderungen und die müssen erfüllt werden.

Ganz recht, aber genau das leisten Dein wait()/resume() eben nicht zuverlässig.

Die andere Frage ist dann, würde es denn Probleme geben, wenn man viele wakeup()´s vor einem wait() machen kann?

Der Punkt ist das man sowas sicher nicht absichtlich macht aber das es eben trotzdem mal passieren kann und daher muss das System mit solchen Situationen sinnvoll umgehen können. Bei einem einfachen und unspezifischen wait()/resume() macht es aber IMHO keinen Sinn vorauseilende Resumes zu queuen. Mir fällt für wait()/resume() auch gar keine sinnvolle Verwendung ein, andere unbedingte Blockierungen als sleep() soll es bei meinem OS auch nicht geben. Wenn ein Thread auf ein bestimmtes Ereignis, wie das Freiwerden eines Locks, warten will dann muss er auch eine spezifische Blockierung benutzen um auch gezielt geweckt werden zu können (dazu benötigt man dann auch nicht die ID des blockierten Threads sondern nur den Event-Mechanismus so das sich auch keine Probleme mit den Zugriffsrechten ergeben selbst wenn das über mehrere Prozesse hinweg benutzt wird).

Auch hat sich noch keiner dazu geäußert wie man es am besten löst das nicht jeder Thread jeden x-beliebigen Thread aufwecken kann.

Das würde ich grundsätzlich nur innerhalb eines Prozesses erlauben. Die einzigste Ausnahme würde ich für Prozesse mit root-Rechten machen, sonst kannst Du z.B. keinen anständigen Task-Manager (sowas wie den "Process Explorer" von den Windows Sysinternals, schade das es ein Tool in der Qualität nicht für Linux gibt) programmieren. Eine komplexe Rechte-Verwaltung möchte ich auch nicht im Kernel haben, die möchte ich persönlich lieber im User-Mode haben.


Grüße
Erik

[FlashBurn]

Da musst Du genau so oft in den Kernel wie mit Deiner Idee nur das Du das Problem mit den Race-Conditions grundsätzlich nicht bekommst.

Ich fürchte wir reden aneinander vorbei, mal wieder

Auf der einen Seite möchte ich wait()/resume() anbieten, die arbeiten mit den selben Thread-Variablen (Status-Flags und halt der Counter für die Waits) wie meine Semaphoren im Kernel (es geht ja auch bei einer Semaphore darum das ein Thread wartet, da kann diese Situation auch auftreten, wenn auch wesentlich unwahrscheinlicher).

Allgemein wollte ich halt wissen wie man damit umgeht das ein resume() vor einem wait() ankommen kann und das geht auch bei einer Semaphore im Kernel (wenn auch verdammt unwahrscheinlich bei einem nicht unterbrechbaren Kernel), vorallem bei einem der unterbrechbar ist.

Wenn das Problem gelöst ist, habe ich gleichzeitig das wait()/resume() aus dem UserSpace gelöst, da es die selben Thread-Variablen nutzt. Auch muss ich bei einer Futex (auch wenn da eine Semaphore im Kernel dahinter steckt) genau das selbe Problem lösen.

Übrigens müsstest Du mit Deiner Implementierung auch eine Liste mit den blockierten Threads pflegen damit derjenige der die Semaphore momentan hat auch weiß wen er wecken muss, und wenn Du diese Semaphore z.B. innerhalb von Shared-Memory einrichtest damit diese von mehreren Prozessen benutzt werden kann dann muss auch diese Liste komplett im Shared-Memory liegen (damit jeder eintragen/austragen kann) und dafür möchte in kein malloc bauen müssen (irgendwo her müssen ja die neuen Listen-Elemente kommen). Hast Du dafür schon eine gute Lösung?

Jetzt kommen wir zur anderen Seite. Der Counter der Futex ist im SharedMem also genau 4byte. Im Kernel wird dann ne ganz normale Semaphore benutzt, die als ID die physische Adresse des Counters der Futex hat.
Unter Linux wird das sogar so dynamisch gemacht, dass erst wenn ein Thread warten muss, eine Liste erstellt wird. Ich bin mir noch nicht sicher ob ich das auch so machen will, aber da der Thread ja höchstwahrscheinlich eh warten muss, kann man die Zeit auch vernachlässigen.

Das würde ich grundsätzlich nur innerhalb eines Prozesses erlauben. Die einzigste Ausnahme würde ich für Prozesse mit root-Rechten machen, sonst kannst Du z.B. keinen anständigen Task-Manager (sowas wie den "Process Explorer" von den Windows Sysinternals, schade das es ein Tool in der Qualität nicht für Linux gibt) programmieren. Eine komplexe Rechte-Verwaltung möchte ich auch nicht im Kernel haben, die möchte ich persönlich lieber im User-Mode haben.

Schön das wir uns da einig sind

Allerdings ist die Rechte-Sache eigentlich wieder nen eigenes Thema wert. Ich werde also fürs erste resume() nur auf Threads im selben Task zulassen. Gut das ich das transparent zu dem resume() im Kernel machen kann (indem der Syscall das überprüft und kein resume() aufgerufen wird.

Also nochmal ganz genau. Eine Futex ist nur ein Counter im UserSpace. Der Thread der den Wert des Counters ändert entscheidet auch ob er in den Kernel geht (zum Warten oder um einen anderen Thread aufzuwecken) oder nicht. Im Kernel wird nur eine Liste mit wartenden Threads verwaltet.
Wer mir jetzt mit Sicherheitsproblemen kommen möchte, die gleichen haben alle Synchonizationsprimitiven. Denn der Thread muss diese ja nicht nutzen um auf die Daten (lesend oder schreibend) zu zugreifen.
Man stelle sich nur vor ein Thread wartet auf Daten in einer Semaphore im Kernel, aber der andere Thread denkt sich, nee heute nicht und weckt den wartenden Thread halt einfach nicht auf. Dieses Problem ist mMn nicht zu lösen, solange jemand auf etwas wartet.

[erik.vikinger]

Hallo,

Ich fürchte wir reden aneinander vorbei, mal wieder

Dann musst Du mir noch mal genau erklären was Du eigentlich konkret vor hast. Ich hatte Dich so verstanden das Du eine Semaphore im User-Mode hast und falls die jemand haben will aber nicht bekommt das dieser dann einfach schläft bis er vom aktuellen Besitzer geweckt wird (wenn dieser die Semaphore frei gibt). Genau das würde meine Idee auf jeden Fall besser lösen als ein simples unspezifisches wait()/resume().

Auf der einen Seite möchte ich wait()/resume() anbieten, die arbeiten mit den selben Thread-Variablen (Status-Flags und halt der Counter für die Waits) wie meine Semaphoren im Kernel (es geht ja auch bei einer Semaphore darum das ein Thread wartet, da kann diese Situation auch auftreten, wenn auch wesentlich unwahrscheinlicher).

Also wenn Dein wait()/resume() doch mehr machen als nur schlafen legen und aufwecken dann hättest Du das von Anfang an mit dazu schreiben müssen. Im Kernel sollte es grundsätzlich keine Race-Conditions geben weil dort das Prüfen ob die gewünschte Ressource frei ist und das Blockieren (inklusive anhängen an eine Liste) immer atomisch ablaufen kann, so dass das Aufwecken immer konsistent sieht ob und wenn ja welcher Thread wartet. Selbst bei einem unterbrechbaren Kernel kann man ja extra für diesen Vorgang die INTs abschalten (bzw. die resume()/wait()-Syscalls schalten die INTs erst gar nicht frei).

Der Counter der Futex ist im SharedMem also genau 4byte. Im Kernel wird dann ne ganz normale Semaphore benutzt....

Aha, das ist jetzt aber was ganz anderes als am Anfang dieses Threads, oder hab ich da was übersehen? Wir sollten uns erst mal einigen über was wir eigentlich diskutieren wollen.

Wer mir jetzt mit Sicherheitsproblemen kommen möchte ....

Keine Angst, damit komme ich Dir nicht, diese Probleme sind auch mit meinen Events vorhanden (u.a. deswegen hallte ich das TimeOut-Parameter beim event_wait()-syscall für so wichtig).


Grüße
Erik

[FlashBurn]

Dann musst Du mir noch mal genau erklären was Du eigentlich konkret vor hast.

Ziel dieses Thema´s war es eine Lösung für die weiter oben oft beschriebene Race-Condition zu finden, was ich ja auch in Form des Counters (fairerweise reicht der eigentlich nicht) habe.

Also nochmal, am Bsp. einer Semaphore im Kernel (die Ints sind aus). CPU A Thread 1 bekommt den Lock für die Semaphore dekrementiert den Counter und stellt fest das er warten muss, packt sich an das Ende der Warteliste, gibt den Lock wieder frei und ruft wait() auf.
CPU B Thread 2 bekommt den Lock genau nach CPU A, inkrementiert den Counter und stellt fest das er jemanden wecken muss, holt den ersten Thread aus der Liste (dummerweise ist das Thread 1) und macht für diesen Thread ein resume().

Jetzt mal in Code-Form:

Code: [Auswählen]

void
Sem::acquire()
{
    m_Lock.acquire();
   
    if(likely(Atomic::subTestNeg(&m_Count,1))) {
        Thread* t= Thread::getCurrThread();
       
        m_Threads.addTail(t);
       
        m_Lock.release();
       
        t->wait();
    } else {
        m_Lock.release();
    }
}

void
Sem::release()
{
    m_Lock.acquire();
   
    if(likely(Atomic::addTestNegZero(&m_Count,1))) {   
        Thread* t= m_Threads.removeHead();
       
        m_Lock.release();
       
        t->resume();
    } else {
        m_Lock.release();
    }
}

wait() und resume() sehen so aus:

Code: [Auswählen]

void
Thread::wait()
{
    if(likely(Atomic::subTestNeg(&m_WaitStatus,1))) {
        m_Status= THREAD_STS_WANTS_WAITING;
       
        Scheduler::reschedule();
    }
}

void
Thread::resume()
{
    if(likely(Atomic::addTestZero(&m_WaitStatus,1)))
        Scheduler::addThread(this);
}

Ich gehe mal davon aus, dass Thread 1 auf jeden Fall das Dekrementieren seines m_WaitStatus vor dem resume() von Thread 2 schafft (anders rum wäre auch gar kein Problem).
Das Problem taucht da auf, wo die resume() Funktion Scheduler::addThread(this) aufruft und der Thread noch gar nicht durch den Scheduler durch ist. Das kann jetzt zu Problemen führen. Was ich so gelöst habe, dass diese Funktion den Thread nur hinzufügt, wenn er einen "vernünftigen" Status hat (wozu THREAD_WANTS_WAIT nicht dazu gehört).
Bevor mein Scheduler den Thread wirklich in den THREAD_STS_WAITING Status versetzt, überprüft er nocheinmal m_WaitStatus und ob das Warten wirklich nötig ist.

Könnte es da jetzt noch eine Race-Condition geben? Vorallem wenn man bedenkt, das wir in Richtung jeder Kern hat seine eigene Frequenz gehen und damit auch Code der eigentlich erst später erreicht werden sollte, zeitgleich mit anderem Code erreicht werden kann.

Aha, das ist jetzt aber was ganz anderes als am Anfang dieses Threads, oder hab ich da was übersehen?

Naja, es läuft alles auf obige Situation hinaus, nur um diese geht es mir im Endeffekt. Denn wenn ich das im Griff habe, ist das andere auch kein Problem mehr.

u.a. deswegen hallte ich das TimeOut-Parameter beim event_wait()-syscall für so wichtig

Wenn wir mein Race-Condition Problem geklärt haben, würde ich gerne wissen, wie man sowas vernünftig umsetzt. Ich habe da gar keine Idee, aber sowas wird ja doch ab und zu verwendet. (Gibt es bei einer Pipe unter Linux auch so nen Timeout?)