The Little Book of Semaphores is a free (in both senses of the word) textbook that introduces the principles of synchronization for concurrent programming.
In most computer science curricula, synchronization is a module in an Operating Systems class. OS textbooks present a standard set of problems with a standard set of solutions, but most students don't get a good understanding of the material or the ability to solve similar problems.
The approach of this book is to identify patterns that are useful for a variety of synchronization problems and then show how they can be assembled into solutions. After each problem, the book offers a hint before showing a solution, giving students a better chance of discovering solutions on their own.
The book covers the classical problems, including "Readers-writers", "Producer-consumer", and "Dining Philosophers". In addition, it collects a number of not-so-classical problems, some written by the author and some by other teachers and textbook writers. Readers are invited to create and submit new problems.
The process of writing large parallel programs is complicated by the need to specify both the parallel behaviour of the program and the algorithm that is to be used to compute its result.
JoCaml is Objective Caml plus (&) the join calculus, that is, OCaml extended for concurrent and distributed programming. The new JoCaml is a re-implementation of the now unmaintained JoCaml by Fabrice Le Fessant. With respect to this previous implementation, main changes are: * Numerous syntax changes, we believe the new syntax to be cleaner. * Disparition of mobility features, sacrified for the sake of OCaml compatibility. * Much better compatibility with Objective Caml. o Source compatibility is about 99%, there are three new keywords (def, reply and spawn) ; or and & should definitely not be used as boolean operators. o Binary compatibility for matching versions.
concurrent paradigm, namely functional programming extended with threads and ports, which I call multi-agent dataflow programming. * The declarative concurrent subset (no ports) has no race conditions and can be programmed like a functional language. The basic concept is dataflow synchronization of single-assignment variables. A useful data structure is the stream, a list with dataflow tail used as a communication channel. * Nondeterminism can be added exactly where needed and minimally, by using ports - a named stream to which any thread can send. * All functional building blocks are concurrency patterns. Map, fold, filter, etc., are all useful for building concurrent programs. * Concurrent systems can be configured in any order and concurrently with actual use of the system. * Designing concurrent programs is any declarative part of the program can be put in own thread, loosening the coupling between system's parts * The paradigm is easily extended
This is an Erlang solution to "The Santa Claus problem", % as discussed by Simon Peyton Jones (with a Haskell solution using % Software Transactional Memory) in "Beautiful code". % He quotes J.A.Trono "A new exercise in concurrency", SIGCSE 26:8-10, 1994.
With the advent of multi-core processors concurrent programming is becoming indispensable. Scala's primary concurrency construct is actors. Actors are basically concurrent processes that communicate by exchanging messages. Actors can also be seen as a form of active objects where invoking a method corresponds to sending a message. The Scala Actors library provides both asynchronous and synchronous message sends (the latter are implemented by exchanging several asynchronous messages). Moreover, actors may communicate using futures where requests are handled asynchronously, but return a representation (the future) that allows to await the reply. This tutorial is mainly designed as a walk-through of several complete example programs Our first example consists of two actors that exchange a bunch of messages and then terminate. The first actor sends "ping" messages to the second actor, which in turn sends "pong" messages back (for each received "ping" message one "pong" message).
Dynamic Networks Everything I described so far is common to CSP (Communicating Sequential Processes) and the Actor model. Here’s what makes actors more general: Connections between actors are dynamic. Unlike processes in CSP, actors may establish communication channels dynamically. They may pass messages containing references to actors (or mailboxes). They can then send messages to those actors. Here’s a Scala example: receive { case (name: String, actor: Actor) => actor ! lookup(name) } The original message is a tuple combining a string and an actor object. The receiver sends the result of lookup(name) to the actor it has just learned about. Thus a new communication channel between the receiver and the unknown actor can be established at runtime. (In Kilim the same is possible by passing mailboxes via messages.)
J. Protze, M. Schulz, D. Ahn, und M. Müller. Proceedings of the 27th International Symposium on High-Performance Parallel and Distributed Computing, Seite 144--155. ACM, (2018)
V. Raychev, M. Vechev, und M. Sridharan. Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages &\#38; Applications, Seite 151--166. ACM, (2013)
J. Reppy, C. Russo, und Y. Xiao. Proceedings of the 14th ACM SIGPLAN international conference on Functional programming, Seite 257--268. New York, NY, USA, ACM, (August 2009)
C. Reynolds. SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, Seite 25--34. New York, NY, USA, ACM, (1987)
C. Ritson, und J. Simpson. Communicating Process Architectures 2008, Volume 66 von Concurrent Systems Engineering Series, Seite 293--307. Amsterdam, The Netherlands, IOS Press, (September 2008)
J. Roemer, K. Genc, und M. Bond. Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, Seite 374--389. ACM, (2018)
L. Salucci, D. Bonetta, S. Marr, und W. Binder. Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Seite 40:1--40:2. ACM, (März 2016)
H. Schippers, T. Van Cutsem, S. Marr, M. Haupt, und R. Hirschfeld. Proceedings of the Fourth Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS), Seite 4--9. ACM, (06.07.2009)
M. Scott, T. LeBlanc, und B. Marsh. PPOPP '90: Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, Seite 70--78. New York, NY, USA, ACM, (1990)
G. Steele, Jr., D. Lea, und C. Flood. Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, Seite 453--472. ACM, (2014)
H. Sun, D. Bonetta, F. Schiavio, und W. Binder. Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization, Seite 61--72. IEEE Press, (2019)
J. Swalens, J. De Koster, und W. De Meuter. 30th European Conference on Object-Oriented Programming (ECOOP 2016), Volume 56 von Leibniz International Proceedings in Informatics (LIPIcs), Seite 23:1--23:28. Dagstuhl, Germany, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, (2016)
J. Swalens, J. De Koster, und W. De Meuter. Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control - AGERE 2018, Seite 33--43. ACM, (November 2018)
J. Swalens, S. Marr, J. De Koster, und T. Van Cutsem. Proceedings of the Workshop on Programming Language Approaches to Concurrency and communication-cEntric Software (PLACES), Volume 155 von PLACES '14, Seite 54--60. (April 2014)
M. Talupur, und M. Tuttle. FMCAD '08: Proceedings of the 2008 International Conference on Formal Methods in Computer-Aided Design, Seite 1--8. Piscataway, NJ, USA, IEEE Press, (2008)
S. Tasharofi, P. Dinges, und R. Johnson. ECOOP 2013 – Object-Oriented Programming, Volume 7920 von Lecture Notes in Computer Science, Seite 302-326. Springer Berlin Heidelberg, (2013)
S. Tasharofi, R. Karmani, S. Lauterburg, A. Legay, D. Marinov, und G. Agha. Formal Techniques for Distributed Systems: Joint 14th IFIP WG 6.1 International Conference, FMOODS 2012 and 32nd IFIP WG 6.1 International Conference, FORTE 2012, Stockholm, Sweden, June 13-16, 2012. Proceedings, Seite 219--234. Springer, (2012)
S. Tasharofi, M. Pradel, Y. Lin, und R. Johnson. 2013 28th IEEE/ACM International Conference on Automated Software Engineering, Seite 114-124. (November 2013)
S. Tasiran, A. Sezgin, und S. Quadeer. Design and Validation of Concurrent Systems, 09361, Dagstuhl, Germany, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, (2010)
T. Tu, X. Liu, L. Song, und Y. Zhang. Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS \textquotesingle19, ACM, (2019)
D. Ungar, und S. Adams. Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion, Seite 19--26. New York, NY, USA, ACM, (2010)
T. Usui, R. Behrends, J. Evans, und Y. Smaragdakis. Parallel Architectures and Compilation Techniques, 2009. PACT '09. 18th International Conference on, Seite 3--14. (September 2009)
R. Utterback, K. Agrawal, J. Fineman, und I. Lee. Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, Seite 83--94. ACM, (2016)
R. von Behren, J. Condit, und E. Brewer. Proceedings of the 9th conference on Hot Topics in Operating Systems - Volume 9, Seite 4. Berkeley, CA, USA, USENIX Association, (2003)
J. Wang, W. Dou, Y. Gao, C. Gao, F. Qin, K. Yin, und J. Wei. Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering, Seite 520--531. IEEE Press, (2017)
P. Welch, und F. Barnes. Communicating Sequential Processes. The First 25 Years, Volume 3525 von Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 10.1007/11423348_10.(April 2005)
C. Wirth, H. Prähofer, und R. Schatz. Visualizing Software for Understanding and Analysis, 6th IEEE International Workshop on, Seite 1--4. (September 2011)
D. Wu, L. Chen, Y. Zhou, und B. Xu. 2015 ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM), Seite 1-10. (Oktober 2015)
A. Yoga, S. Nagarakatte, und A. Gupta. Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, Seite 833--845. ACM, (2016)
M. Zhang, J. Huang, M. Cao, und M. Bond. Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Seite 97--108. ACM, (2015)
J. Zhou, X. Xiao, und C. Zhang. Proceedings of the 34th International Conference on Software Engineering, Seite 892--902. Piscataway, NJ, USA, IEEE Press, (2012)