	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Yoshihide Igarashi Articles by Yasuaki Nishitani

1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99)

Speedup of Lockout-Free Mutual Exclusion Algorithms

Fremantle, Australia

June 23-June 25

ISBN: 0-7695-0231-8

	ASCII Text	x
	Yoshihide Igarashi, Yasuaki Nishitani, "Speedup of Lockout-Free Mutual Exclusion Algorithms," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 172, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999.

	BibTex	x
	@article{ 10.1109/ISPAN.1999.778935, author = {Yoshihide Igarashi and Yasuaki Nishitani}, title = {Speedup of Lockout-Free Mutual Exclusion Algorithms}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {1999}, issn = {1087-4089}, pages = {172}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778935}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - Speedup of Lockout-Free Mutual Exclusion Algorithms SN - 1087-4089 SP EP A1 - Yoshihide Igarashi, A1 - Yasuaki Nishitani, PY - 1999 KW - asynchronous processes KW - concurrent computation KW - distributed systems KW - lockout-freedom KW - mutual exclusion KW - shared memory VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Yoshihide Igarashi, Gunma University

Yasuaki Nishitani, Gunma University

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778935

We propose three lockout-free mutual exclusion algorithms for the asynchronous multi-writer/reader shared memory model. The first two algorithms are modifications of the $n$-process algorithm by Peterson, and the third algorithm is a modification of the tournament algorithm by Peterson and Fischer. The correctness and efficiency of these modified algorithms are shown. By these modifications we can speed up the original algorithms. The running times for the trying regions of the first algorithm and the second algorithm are (2n-3)c+O(n^3l) and (n-1)c+O(n^3l), respectively, where $n$ is the number of processes, l is an upper bound on the time between successive two steps, and c is is an upper bound on the time that any user spends in the critical region. The running time for the trying region of the third algorithm is (n-1)c+O(nl).

Index Terms:

asynchronous processes, concurrent computation, distributed systems, lockout-freedom, mutual exclusion, shared memory

Citation:

Yoshihide Igarashi, Yasuaki Nishitani, "Speedup of Lockout-Free Mutual Exclusion Algorithms," ispan, pp.172, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.