How to write a spinlock without using CAS

views:

119

answers:

How to write a spinlock without using CAS

Following on from a discussion which got going in the comments of this question.

How would one go about writing a Spinlock without CAS operations?

As the other question states:

The memory ordering model is such that writes will be atomic (if two concurrent threads write a memory location at the same time, the result will be one or the other). The platform will not support atomic compare-and-set operations.

+2 A:

Wikipedia's article on spinlock says you'll have to use an algorithm like Peterson's algortihm, which uses another flag to indicate which process's turn it is to enter the critical section (if desired).

Stephen Denne 2010-05-02 21:11:10

It looks like this requires one variable declaration per thread? The question this was inspired by required thousands of threads, and an unknown number of them. Which means that this probably isn't a viable solution :(

Martin 2010-05-02 21:16:56

True. Additionally, the threads would need to know which atomically writeable flag was theirs, which is essentially what the original question is trying to determine. Are there systems that do not provide threads with an identity, such as a combination of the identity of whatever created the thread, and a serial from that creator?

Stephen Denne 2010-05-02 21:40:36

I'm going to accept this, it seems like there aren't any other ways to do this.

Martin 2010-05-04 12:52:05

@Martin: the default stacksize for a thread is 1MB. You would ptobably have to lower that to accommodate 1k threads, but even then 1 flag/thread won't be the deal breaker.

Henk Holterman 2010-05-04 21:26:21

Well 1 flag per thread sets a hard upper limit on the number of threads, the original question implied that there was an unspecified number of threads (possibly being created/destroyed all the time).

Martin 2010-05-04 21:39:31

ansaurus

tags:

views:

answers:

How to write a spinlock without using CAS

related questions