A re-entrant algorithm that enables multiple concurrent critical sections with possible recursion
Original Publication Date: 2009-Jul-15
Included in the Prior Art Database: 2009-Jul-15
The "Bakery algorithm" is a known method to achieve a critical section in code (i.e. an area of code that must not be executed concurrently by multiple processes in a distributed application). This article presents is a description of several improvements to the bakery algorithm supporting various types of multiple independant synchronizations.
In distributed applications involving several processes running concurrently and using shared resources there is a frequent need for a "critical section".
section (termed CS for short here) is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one process. Some synchronization mechanism is required at the entry and exit of the CS to ensure exclusive use.
The problem of an algorithm for CS synchronization is an old one and there are several known algorithms for it. These include:
In addition to these - there are also several known algorithms that employ commonly available hardware synchronization resources for achieving critical sections. For example see PowerPC-Book II Appendix B.
We assume here a usage methodology of calling a reentrant function EnterCriticalSection and ExitCriticalSection at the entry and exit to the critical sections respectively. This is different from another possible methodology of coding the algorithms for entry and exit directly around the CS code. The use of functions is obviously more efficient in code size and maintainability.
The problems with the known solutions when used as entry/exit functions are:
Disjoint critical sections:
There may be several different critical sections each of which requires exclusive entry into itself but they do not need to be mutually exclusive among themselves - i.e. different threads may occupy different critical sections simultaneously but may not occupy the same critical section simultaneously. We term such critical sections here "disjoint critical sections".
For example there may be one critical section for using a single printing device and another critical section for writing to a shared file. If a function for CS entry/exit is written directly based on known algorithms - this would cause over synchronization (i.e. bar different threads from entering the different critical sections). This would degrade performance.
Recursive critical section:
There are cases where a process while still inside a CS would like to re-entrantly use the same CS for some sub-actions.
For example assume there is a critical section for accessing any printer. Suppose the procedure for sending a file to a printer is written as a recursive function - for example because in some case the procedure may decide in addition to the main printing action to send the file to a "copy" printer.
Possible solutions could include to rewrite the procedure so that it does not use recursion or to enter/exit the CS before/after making the first call to the procedure. However, these solutions may be inconvenient for the programmer.
Critical section code that employs hardware synchronization algorithm...