Thread Synchronization in Concurrent Systems: A Study of Dekker’s Algorithm, Peterson’s Algorithm, and Semaphore-Based Solutions

The proliferation of multi-core processors has made concurrency a central paradigm in modern software development. While concurrent execution offers significant performance benefits, it introduces the critical challenge of synchronizing access to shared resources to prevent race conditions, data corruption, and inconsistent states. This paper traces the evolution of thread synchronization solutions, beginning with the pioneering software-only mutual exclusion algorithms of Dekker and Peterson. These algorithms provided the theoretical foundation for ensuring that only one thread can execute in a critical section at a time without relying on hardware-specific instructions. The paper then explores how Dijkstra's semaphore concept extended these ideas into a more practical and powerful tool by eliminating busy waiting and providing a structured mechanism for signaling and coordination. The primary objectives are to analyze the design, properties, and limitations of Dekker's and Peterson's algorithms, demonstrate the application of semaphores to classical synchronization problems; namely the Producer-Consumer, Bounded Buffer, and Readers-Writers problems and provide a comparative analysis of their advantages and relevance in the context of modern operating systems and programming languages. The analysis concludes that while the classical algorithms are primarily of historical and educational value today, the principles they established are directly embodied in the sophisticated synchronization primitives used in contemporary systems.

Concurrency, Mutual Exclusion, Dekker's Algorithm

1. M. Herlihy and N. Shavit, The Art of Multiprocessor Programming. San Francisco, CA, USA: Morgan Kaufmann, 2012. [Google Scholar] [Crossref]

2. T. J. Dekker, "Over de sequentialiteit van procesbeschrijvingen (On the sequentiality of process descriptions)," Mathematical Centrum Amsterdam, 1965. [Google Scholar] [Crossref]

3. G. L. Peterson, "Myths about the mutual exclusion problem," Information Processing Letters, vol. 12, no. 3, pp. 115–116, Jun. 1981. [Google Scholar] [Crossref]

4. H. M. Deitel, P. J. Deitel, and D. R. Choffnes, Operating Systems, 3rd ed. Upper Saddle River, NJ, USA: Prentice Hall, 2004. [Google Scholar] [Crossref]

5. E. W. Dijkstra, "Cooperating sequential processes," Technische Hogeschool Eindhoven, 1965. [Google Scholar] [Crossref]

6. D. Dice, "Implementing fast Java monitors with relaxed locks," in Proc. JVM Research and Technology Symposium, 2001, pp. 79–90. [Google Scholar] [Crossref]

7. Intel Corporation, Intel® 64 and IA-32 Architectures Software Developer's Manual, 2023. [Google Scholar] [Crossref]

8. W. Stallings, Operating Systems: Internals and Design Principles, 9th ed. Hoboken, NJ, USA: Pearson, 2018. [Google Scholar] [Crossref]

9. M. L. Scott, Programming Language Pragmatics, 4th ed. San Francisco, CA, USA: Morgan Kaufmann, 2015. [Google Scholar] [Crossref]

10. B. Goetz et al., Java Concurrency in Practice. Boston, MA, USA: Addison-Wesley, 2006. [Google Scholar] [Crossref]

11. L. Lamport, "The mutual exclusion problem: Part I—A theory of interprocess communication," Journal of the ACM, vol. 33, no. 2, pp. 313–326, Apr. 1986. [Google Scholar] [Crossref]

12. L. Lamport, "The mutual exclusion problem: Part II—Statement and solutions," Journal of the ACM, vol. 33, no. 2, pp. 327–348, Apr. 1986. [Google Scholar] [Crossref]

13. P. Brinch Hansen, Operating System Principles. Englewood Cliffs, NJ, USA: Prentice Hall, 1973. [Google Scholar] [Crossref]

14. N. G. Leveson, "The evolution of layered synchronization," Software: Practice and Experience, vol. 16, no. 5, pp. 437–454, May 1986. [Google Scholar] [Crossref]

15. L. Nigro, F. Cicirelli, and F. Pupo, "Modeling and Analysis of Dekker-Based Mutual Exclusion Algorithms," Computers, vol. 13, no. 6, p. 133, 2024. doi: https://doi.org/10.3390/computers13060133 [Google Scholar] [Crossref]

16. O. Kode and T. Oyemade, "Analysis of Synchronization Mechanisms in Operating Systems," arXiv preprint arXiv:2409.11271, Sep. 2024. doi: https://doi.org/10.48550/arXiv.2409.11271 [Google Scholar] [Crossref]

17. L. Nigro and F. Cicirelli, "Property Assessment of Peterson’s Mutual Exclusion Algorithms," Applied Computational Intelligence, vol. 4, no. 1, pp. 66–92, Jan. 2024. doi: https://doi.org/10.3934/aci.2024005 [Google Scholar] [Crossref]

18. A. Gupta, A. Arora, and M. Kaur, "Thread Scheduling and Synchronization for Multi-Threaded Applications," Journal of Software Engineering and Simulation, vol. 10, no. 5, pp. 01–06, 2024. [Google Scholar] [Crossref]

19. J. H. Anderson and Y.-J. Kim, "Adaptive mutual exclusion with local spinning," in Proc. 14th International Symposium on Distributed Computing, 2000, pp. 1–15. [Google Scholar] [Crossref]

20. P. J. Courtois, F. Heymans, and D. L. Parnas, "Concurrent control with 'readers' and 'writers'," Communications of the ACM, vol. 14, no. 10, pp. 667–668, Oct. 1971. [Google Scholar] [Crossref]

21. M. L. Scott, Programming Language Pragmatics, 4th ed. San Francisco, CA, USA: Morgan Kaufmann, 2015. [Google Scholar] [Crossref]

22. C. A. R. Hoare, "Monitors: An operating system structuring concept," Communications of the ACM, vol. 17, no. 10, pp. 549–557, Oct. 1974. [Google Scholar] [Crossref]

23. G. Khandelwal, S. Sonwane, and S. Ware, "Concurrency and Synchronization: Detection, Reasons, Tools and Applications," International Journal of Scientific Research and Engineering Trends, vol. 10, no. 6, pp. 1–8, Nov.–Dec. 2024. [Google Scholar] [Crossref]

24. V. Sree Dharshni, V. S. Akshaya, M. Sujithra, and A. D. Chitra, "A Theory of Synchronisation Using Semaphores," International Journal of Advanced Engineering and Management (IJAEM), vol. 2, no. 9, pp. 256–263, 2020. [Google Scholar] [Crossref]

25. S. Oaks and H. Wong, Java Threads, 3rd ed. Sebastopol, CA, USA: O'Reilly Media, 2004. [Google Scholar] [Crossref]

26. M. A. Arjomandi, "A comprehensive survey of parallel mutual exclusion algorithms," ACM Computing Surveys, vol. 54, no. 9, pp. 1–33. [Google Scholar] [Crossref]

• What the Desert Fathers Teach Data Scientists: Ancient Ascetic Principles for Ethical Machine-Learning Practice
• Comparative Analysis of Some Machine Learning Algorithms for the Classification of Ransomware
• Comparative Performance Analysis of Some Priority Queue Variants in Dijkstra’s Algorithm
• Transfer Learning in Detecting E-Assessment Malpractice from a Proctored Video Recordings.
• Dual-Modal Detection of Parkinson’s Disease: A Clinical Framework and Deep Learning Approach Using NeuroParkNet