Semaphores, Are They Really Like Traffic Signals?

• Carlos M. Tobar PUC-Campinas
• Juan M. Adán-Coello PUC-Campinas
• Ricardo Luís de Freitas PUC-Campinas

Abstract

Semaphores are software mechanisms designed to synchronize processes. The name seems to recall a traffic signal but diversely from the original idea behind them, different implementations can be found in popular Operating Systems as well as different definitions in the most adopted introductory books. Due to these differences, care is necessary in knowing if an implementation of semaphores is compatible with the definition found in the adopted book, otherwise could become confused to students. This article presents and compares semaphores definitions and implementations, rescuing three types of them. It is a warning to teachers on semaphore semantics and implementations, considering that they are usually used by applications programmers where kernel mechanisms cannot be used.

References

Apple (2009) “Perl Programmers Reference Guide”. [link], January.

Apt, K. R. (2002) “Edsger Wybe Dijkstra (1930–2002): A Portrait of a Genius (Obituary)”, Formal Aspects of Computing, n. 14, p. 92–98.

Deitel, H. M. (1984) An Introduction to Operating Systems, Addison-Wesley.

Deitel, H. M.; Deitel, P. J.; Choffnes, D. R. (2004) Operating Systems (3rd Ed.), Prentice Hall.

Dijkstra, E. W. (1968) “The structure of the “THE”-multiprogramming system”, CACM, v. 11, n. 5, p. 341 – 346.

Dijkstra, E. W. (1971) “Hierarchical Ordering of Sequential Processes”. Acta Informática, v. 1, n. 2, p. 115-138.

Dustan, N.; Fris, I. (1995) “Process Scheduling and UNIX Semaphores”. Software-Practice and Experience, v. 25, n. 10, p. 1141-1153. DOI: 10.1002/spe.4380251005

Lewis, B.; Berg, D. (1998) Multithreaded Programming with PThreads. Sun Microsystems Press.

Microsoft (2008) “.NET Framework Developer's Guide”. [link], September.

Milenkovic, M. (1992) Operating Systems, Concepts and Design (2nd Ed.), McGraw-Hill International Editions.

Posix (2004) “Portable Operating Systems and Interface for Unix”, IEEE Standard 1003. 2004 ed. [link], February.

Reek, K. A. (2002) “The Well-Tempered Semaphore: Theme with Variations”. ACM SIGSE Bulletin, March, p. 356-359.

Silberschatz, A.; Galvin, P. B.; Gagne, G. (2004) Operating System Concepts (7th Ed.), Wiley.

Stallings, W. (2004) Operating Systems: Internals and Design Principles (5th Ed.), Prentice Hall.

Stark, E. W. (1982) “Semaphore primitives and starvation-free mutual exclusion”. Journal of the ACM (JACM), v. 29, n. 4, p. 1049-1072.

Tanenbaum, A. S. (2008) Modern Operating Systems (3rd Ed.), Prentice Hall.

Tanenbaum, A. S.; Woodhull A. S. (2006) Operating Systems Design and Implementation (3rd Ed.), Prentice Hall.

THOCP. (2008) “The History of Computing Project”. [link], November.