A Performance Evaluation on Classic Mutual Exclusion Algorithms for Exploring Feasibility of Practical Application


KIPS Transactions on Computer and Communication Systems, Vol. 6, No. 12, pp. 469-478, Dec. 2017
10.3745/KTCCS.2017.6.12.469,   PDF Download:
Keywords: Mutual Exclusion, Dekker's Algorithm, Peterson's Algorithm, POSIX Thread, WIN32 Thread, Java Monitor
Abstract

The mutual exclusion is originally based on the theory of race condition prevention in symmetric multi-processor operating systems. But recently, due to the generalization of multi-core processors, its application range has been rapidly shifted to parallel processing application domain. POSIX thread, WIN32 thread, and Java thread, which are typical parallel processing application development environments, provide a unique mutual exclusion mechanism for each of them. Applications that are very sensitive to performance in these environments may want to reduce the burden of mutual exclusion, even at some cost, such as inconvenience of coding. In this study, we implement Dekker's and Peterson's algorithm in the form of busy-wait and processor-yield in various platforms, and compare the performance of them with the built-in mutual exclusion mechanisms to evaluate the usability of the classic algorithms. The analysis result shows that Dekker's algorithm of processor-yield type is superior to the built-in mechanisms in POSIX and WIN32 thread environments at least 2 times and up to 70 times, and confirms that the practicality of the algorithm is sufficient.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
H. Lee and K. Kwon, "A Performance Evaluation on Classic Mutual Exclusion Algorithms for Exploring Feasibility of Practical Application," KIPS Transactions on Computer and Communication Systems, vol. 6, no. 12, pp. 469-478, 2017. DOI: 10.3745/KTCCS.2017.6.12.469.

[ACM Style]
Hyung-Bong Lee and Ki-Hyeon Kwon. 2017. A Performance Evaluation on Classic Mutual Exclusion Algorithms for Exploring Feasibility of Practical Application. KIPS Transactions on Computer and Communication Systems, 6, 12, (2017), 469-478. DOI: 10.3745/KTCCS.2017.6.12.469.