The idea to use a tournament to implement N-thread mutual exclusion has been around for a long time. It is already carefully described by J.L.W. Kessels in Acta Informatica 17 (1982) 135-141. A N-thread tournament algorithm based on Peterson's 2-thread algorithm can have a throughput comparable with the hardware assisted MCS algorithm, see Buhr-Dice-Hesselink in Concurrency Computat.: Pract. Exper. 27 (2015) 651-701. I have recently underpinned this experimental result with an estimate of the concurrent complexity of tournament algorithms. A paper is in preparation. A preliminary PVS proof script is available. Also available is a separate proof script about Peterson's two-thread algorithm.
Comments and questions are welcome.
Back to my home page.
Last modified: 8 August 2016.