Semaphore Warteschlangen

Question

Ich erweitere die Funktionalität eines Semaphors. Ich geriet in eine Straßenblockade, als ich realisierte, dass ich die Implementierung eines tatsächlichen Semaphors nicht kannte und um sicherzustellen, dass mein Code korrekt lief, musste ich das wissen.

Ich weiß, dass ein Semaphor funktioniert, indem er Threads blockiert, die darauf warten, wenn sie sem_wait() aufrufen, und ein anderer Thread hat sie derzeit gesperrt. Der Thread wird dann blockiert und dann in eine Warteliste für diesen Semaphor eingefügt.

Meine Frage bezieht sich auf das, was auf einem sem_post() passiert. Wird der nächste Thread aus der Warteliste gezogen, als Sperrthread festgelegt und entsperrt? Oder ist das Buchungsschema komplett anders?

Danke!

Answer 1

Semaphores haben zwei Operationen:

1. P() die Semaphore zu erwerben (Sie scheinen diese sem_wait zu nennen)
2. V() die Semaphore freischalten (scheinen Sie diese sem_post zu nennen)

Semaphoren ist auch eine Ganzzahl zugeordnet, die die Anzahl gleichzeitiger Threads ist, die P() ohne Blockierung passieren dürfen. Andere Aufrufe von P() werden blockiert, bis V() aufgerufen wird, um Punkte freizugeben.

Das ist die klassische Definition eines Semaphors.

Bearbeiten: Semaphoren geben keine Garantie für die Reihenfolge. Sie müssen nicht tatsächlich eine Warteschlange oder eine andere FIFO-Struktur verwenden. Wenn nur ein Thread zu einem Zeitpunkt erlaubt ist, wenn er V() aufruft, kehrt ein anderer (möglicherweise zufälliger) Thread von seinem P() - Aufruf zurück und fährt fort.

Answer 2

Der nächste Thread zu entsperren auf sem_wait() ist, was Thread das OS entscheidet, ist der nächste in Kontext wechseln. Niemand gibt eine Garantie für die Bestellung; Dies hängt von der Scheduling-Strategie Ihres Betriebssystems ab. Es könnte der Thread sein, der am längsten von der CPU entfernt war, oder derjenige, dem die höchste "Priorität" zugewiesen wurde, oder der, der in der Vergangenheit bestimmte Ressourcennutzungsstatistiken hatte oder was auch immer.

Höchstwahrscheinlich wird Ihr aktueller Thread (der mit der Bezeichnung sem_post()) noch eine Weile weiterlaufen, bis er entweder auf Benutzereingaben zu warten beginnt, auf einem anderen Semaphor blockt oder die ihm zugewiesene Zeitscheibe verlässt. Dann wird das Betriebssystem in einem völlig unabhängigen Prozess für einen Bruchteil einer Sekunde (wahrscheinlich Firefox oder etwas) laufen, dann loslegen und den Netzwerkverkehr abwickeln, sich selbst eine Tasse Tee holen, und schließlich, wenn es sich herumspricht Wählen Sie aus, wie Sie sich fühlen, basierend auf der Vergangenheit, dass der bestimmte Thread mehr CPU- oder I/O-gebunden ist.

In vielen Betriebssystemen wird I/O-gebundenen Prozessen Priorität eingeräumt, die es schon sehr lange nicht mehr gibt. Die Theorie ist, dass neue Prozesse kurzlebig sein könnten (wenn es schon seit fünf Stunden existiert, die Chancen stehen gut, dass es in den nächsten 1ms nicht fertig wird), damit wir sie genauso gut hinter uns bringen können. I/O-gebundene Prozesse sind wahrscheinlich weiterhin I/O-gebunden, was bedeutet, dass sie wahrscheinlich die CPU kurz ausschalten, während sie auf andere Ressourcen warten. Grundsätzlich möchte das Betriebssystem den Prozess finden, den es mit ASAP möglich macht, damit es wieder seinen Tee schlürfen und Ihre Malware ausführen kann.