A space- and time-efficient local-spin spin lock. (Q1853104)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A space- and time-efficient local-spin spin lock. |
scientific article; zbMATH DE number 1856442
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A space- and time-efficient local-spin spin lock. |
scientific article; zbMATH DE number 1856442 |
Statements
A space- and time-efficient local-spin spin lock. (English)
0 references
21 January 2003
0 references
A simple code transformation is presented that reduces the space complexity of Yang and Anderson's local-spin mutual exclusion algorithm. In both the original and the transformed algorithm, only atomic read and write instructions are used; each process generates \(\Theta(\log N)\) remote memory references per lock request, where \(N\) is the number of processes. The transformed algorithm uses \(\Theta(N)\) distinct variables, which is clearly optimal.
0 references
Mutual exclusion
0 references
Local spinning
0 references
Read/write atomicity
0 references
Shared-memory systems
0 references
Space complexity
0 references
Algorithms
0 references
