Dans quelle mesure les sémaphores Java sont-ils garantis d'être déterministes ?

Question

Le (Oracle) javadoc pour Semaphore.release() inclut :

Si des threads essaient d'acquérir un permis, alors l'un est sélectionné et reçoit le permis qui vient d'être relâché.

S'agit-il d'une promesse ferme ? Cela implique que si le thread A attend dans acquire() et que le thread B fait ceci :

sem.release()
sem.acquire()

Alors le release() devrait passer le contrôle à A et B sera bloqué dans acquire(). Si ce sont les seuls deux threads qui peuvent détenir le sémaphore et que l'affirmation de la documentation est formellement vraie, alors il s'agit d'un processus complètement déterministe : Ensuite, A aura le permis et B sera bloqué.

Mais ce n'est pas vrai, ou du moins cela me semble ainsi. Je n'ai pas inclus d'exemple de code complet ici car je cherche simplement une confirmation que :

Les conditions de course s'appliquent : Même si le thread A attend le permis, lorsqu'il est libéré, il peut être immédiatement ré-acquis par le thread B, laissant le thread A toujours bloqué.

Il s'agit de sémaphores "équitables" si cela fait une différence, et je travaille en kotlin.

Answer 1

Dans les commentaires sur la question Slaw a souligné quelque chose d'autre de la documentation:

Lorsque la justice est définie comme vraie, le sémaphore garantit que les threads appelant l'une des méthodes d'acquisition sont sélectionnés pour obtenir des permis dans l'ordre dans lequel leur appel de ces méthodes a été traité (premier entré, premier sorti; FIFO). Notez que l'ordonnancement FIFO s'applique nécessairement à des points d'exécution spécifiques au sein de ces méthodes. Donc, il est possible qu'un thread appelle acquire avant un autre, mais atteigne le point d'ordonnancement après l'autre, et de même au retour de la méthode.

Le point ici est que acquire() est une fonction interruptible avec un début et une fin. À un moment donné pendant son exception, le thread appelant sécurise une place dans la file d'attente d'équité, mais quand cela se produit par rapport à un autre thread accédant simultanément à la même fonction est encore indéterminé. Appelez ce point X et considérez deux threads, dont l'un détient le sémaphore. À un moment donné, un autre thread appelle:

   sem.acquire()

Il n'y a aucune garantie que l'ordonnanceur ne mettra pas le thread en attente à l'intérieur de acquire() avant que le point X ne soit atteint. Si le thread propriétaire fait alors ceci (il pourrait s'agir, par exemple, d'un point de contrôle de synchronisation ou d'un contrôle de barrière):

   sem.release()
   sem.acquire()

Il pourrait simplement libérer et acquérir le sémaphore sans être acquis par un autre thread même si ce thread a déjà entrepris acquire.

L'injection de Thread.sleep() ou yield() entre les appels fonctionne souvent, mais ce n'est pas une garantie. Pour créer un tel point de contrôle avec cette garantie, vous avez besoin de deux verrous/sémaphores pour un échange:

• Le thread propriétaire détient semA.
• Le thread client peut prendre semB puis attendre sur semA.
• Le propriétaire peut libérer semA puis attendre sur semB, ce qui bloquera si un autre thread attend vraiment semA en détenant semB, garantissant ainsi que semA peut maintenant être acquis par le client.
• Lorsque le client a terminé, il libère semB, puis semA.
• Lorsque le propriétaire est libéré de l'attente sur semB, il peut acquérir semA et libérer semB.

Si ces éléments sont correctement encapsulés, ce mécanisme est très solide.