Wie wird conditional_wait() auf Kernel- und Hardware-/Assembly-Ebene implementiert?

Wie wird conditional_wait() auf Kernel- und Hardware-/Assembly-Ebene implementiert?


Ich verstehe, dass der Thread, der auf eine bedingte Variable wartet, die Sperre atomar freigibt und in den Ruhezustand geht, bis er durch ein bedingtes Signal von einem anderen Thread geweckt wird (wenn eine bestimmte Bedingung erfüllt ist). Nachdem es aufgewacht ist, erwirbt es die Sperre atomar wieder (irgendwie magisch) und aktualisiert es nach Bedarf und entsperrt den kritischen Abschnitt.


Es wäre großartig, wenn jemand erklären könnte, wie diese conditional_wait()-Prozedur auf Kernel- und Hardware-/Assembly-Ebene implementiert wird.


Wie wird die Sperre freigegeben und atomar wieder erlangt? Wie stellt der Kernel dies sicher?


Was heißt hier eigentlich schlafen? Bedeutet es einen Kontextwechsel zu einem anderen Prozess/Thread?


Wie wird dieser Thread während des Ruhezustands durch Signalisierung aufgeweckt? auf Kernel-Ebene implementiert und ob Hardware-spezifische Unterstützung für diese Mechanismen bereitgestellt wird?


Bearbeiten:


Es scheint, dass "futex" der Typ ist, der dieses Warte-/Signal-Zeug verwaltet. Um meine Frage einzugrenzen:
Wie wird der futex-Systemaufruf zum Warten und Benachrichtigen von Bedingungsvariablen implementiert / funktioniert auf niedriger Ebene?


Antworten:


Auf einem hohen Niveau (und da Sie diese Frage stellen, ein hohes Niveau ist das, was Sie brauchen) ist es nicht so kompliziert. Zunächst müssen Sie die Verantwortungsebenen kennen. Es gibt grundsätzlich 3 Schichten:



  • Hardwareebene - normalerweise etwas, das in einer einzigen ASM-Anweisung codiert werden kann

  • Kernel-Ebene - etwas, das der OS-Kernel tut

  • Anwendungsebene - etwas, was die Anwendung tut


Im Allgemeinen überschneiden sich diese Verantwortlichkeiten nicht – Kernel kann nicht tun, was nur Hardware tun kann, Hardware kann nicht tun, was nur Kernel tun kann. In Anbetracht dessen ist es nützlich, sich daran zu erinnern, dass nur sehr wenige Hardware darüber Bescheid weiß, wenn es um das Sperren geht. Es läuft ziemlich genau auf

hinaus

  • atomare Arithmetik - Hardware kann einen bestimmten Speicherbereich sperren (stellen Sie sicher, dass keine anderen Threads darauf zugreifen), arithmetische Operationen darauf ausführen und den Bereich entsperren. Dies kann nur mit der vom Chip nativ unterstützten Arithmetik (keine Quadratwurzeln!) und den von der Hardware nativ unterstützten Größen funktionieren

  • Speicherbarrieren oder -zäune - das heißt, eine Barriere in einen Befehlsfluss einführen, sodass, wenn die CPU Anweisungen neu ordnet oder Speicher-Caches verwendet, sie diese Zäune nicht überschreiten und der Cache frisch ist

  • Bedingtes Setzen (Compare-and-Set) – Speicherbereich auf Wert A setzen, wenn es B ist, und den Status dieser Operation melden (war er gesetzt oder nicht)


Das ist so ziemlich alles, was die CPU tun kann. Wie Sie sehen, gibt es hier keine Futex-, Mutex- oder Bedingungsvariablen. Dieses Zeug wird vom Kernel erstellt, der CPU-unterstützte Operationen zur Verfügung hat.


Schauen wir uns auf einer sehr hohen Ebene an, wie der Kernel den Futex-Aufruf implementieren könnte. Tatsächlich ist futex etwas kompliziert, da es je nach Bedarf eine Mischung aus Aufrufen auf Benutzerebene und Aufrufen auf Kernelebene ist. Schauen wir uns den „reinen“ Mutex an, der ausschließlich im Kernel-Space implementiert ist. Auf hohem Niveau wird es demonstrativ genug sein.


Wenn Mutex anfänglich erstellt wird, ordnet der Kernel ihm eine Speicherregion zu. Diese Region enthält einen Mutex-Wert, der gesperrt oder entsperrt wird. Später wird der Kernel aufgefordert, den Mutex zu sperren, er weist die CPU zunächst an, eine Speichersperre auszugeben. Ein Mutex muss als Barriere dienen, damit alles, was nach dem Abrufen (oder Freigeben) des Mutex gelesen/geschrieben wird, für den Rest der CPUs sichtbar ist. Dann verwendet es eine CPU-unterstützte Vergleichs-und-Setz-Anweisung, um den Speicherbereichswert auf 1 zu setzen, wenn er auf 0 gesetzt war. (Es gibt kompliziertere reentrante Mutexe, aber machen wir das Bild nicht komplizierter). Es wird von der CPU garantiert, dass selbst wenn mehr als ein Thread dies gleichzeitig versucht, nur einer erfolgreich sein wird. Wenn die Operation erfolgreich ist, halten wir jetzt den Mutex. Sobald der Kernel aufgefordert wird, den Mutex freizugeben, wird die Speicherregion auf 0 gesetzt (es besteht keine Notwendigkeit, dies bedingt zu tun, da wir wissen, dass wir den Mutex halten!) und eine weitere Speicherbarriere wird ausgegeben. Der Kernel aktualisiert auch den Mutex-Status in seinen Tabellen - siehe unten.


Wenn das Mutex-Sperren fehlschlägt, fügt der Kernel den Thread zu seinen Tabellen hinzu, die Threads auflisten, die auf die Freigabe eines bestimmten Mutex warten. Wenn der Mutex freigegeben wird, prüft der Kernel, welche Threads auf diesen Mutex warten, und plant (d. h. bereitet die Ausführung vor) einen von diesen (falls es mehr als einen gibt, hängt davon ab, welcher Thread geplant oder geweckt wird Vielzahl von Faktoren, im einfachsten Fall ist es einfach Zufall). Der geplante Thread beginnt mit der Ausführung, sperrt den Mutex erneut (an diesem Punkt kann er erneut fehlschlagen!) und der Lebenszyklus wird fortgesetzt.


Hoffe, es macht zumindest halbwegs Sinn :)