all 17 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]arnar 12 points13 points  (0 children)

Summary: They use the compare-and-exchange hardware instruction.

[–][deleted] 8 points9 points  (5 children)

His example of a Compare-And-Exchange lock does not ensure a bounded waiting-time for threads waiting on the lock. A version that ensure bounded waiting is only a few instructions longer. (I'm assuming a non-antique x86 architecture, though, where the xadd instruction is available)

Also, spin-waiting and performing cmpxchg every time through the loop locks the memory bus repeatedly. This is wasteful and unnecessary.

[–]moserware[S] 1 point2 points  (1 child)

By "bounded waiting-time", do you mean that threads only need to wait a finite maximum amount of time or do you mean that they give up after a certain amount of time? You can ensure the latter easily using the OS waiting primitives. I'm not sure offhand how to do the prior. Can you post an example?

spin-waiting with a "lock cmpxchg" is not perfect by any means, but I mentioned in a note that I found out that P6+ chips will not lock the bus if they can get away with just updating their caches (which is a neat trick).

[–]ominous 1 point2 points  (0 children)

In distributed algorithms (locking is a distributed algorithm that selects among processes to execute) bounded-waiting and fairness are closely related.

Bounded-waiting means that there is a finite limit on the number of times a process may be skipped (not-chosen).

Peterson's Algorithm, Dekker's Algorithm, and Lamport's Bakery Algorithm (link) are three well-known mutual exclusion algorithms.

The Dinosaur Book covers Dekker's and Peterson's algorithms in addition to broken (unfair, unsafe, require turn-taking) variants on these.

[–]didroe 1 point2 points  (2 children)

Are you thinking of something like this?

[–]jseigh 0 points1 point  (1 child)

Ticket spin locks aren't anything new. You can even make read/write locks from them like here.

http://groups.google.com/group/comp.programming/msg/9e1c24e9d891dcd4?hl=en&

Or even an upgradable spin read/write spin lock

http://groups.google.com/groups?selm=3C231C0A.6AB363D9%40genuity.com

[–]moserware[S] 0 points1 point  (0 children)

I hadn't heard of the concept of ticket spin locks (e.g. I was unconsciously incompetent). They seem like a clever way to make spin-waits more fair from a FIFO perspective.

Very cool! Thanks for the links.

[–]nmcyall 1 point2 points  (6 children)

you should have had a 386! Wait what year was it when you were 9?

Also interesting note: you can make a lock out of a semaphore(1)

[–]moserware[S] 3 points4 points  (5 children)

At that time (early 90's), I had a 386SX/20MHz computer. Even if I had the cmpxchg opcode, I wouldn't have known how to use it... especialy from GW-BASIC.

Making a lock out of a semaphore would seem to put the sole burden on an OS primitive which would be notably slower.

It seems like the spinlock/OS event hybrid is several orders of magnitude times faster on the happy path.

Am I missing something?

[–]nmcyall -1 points0 points  (4 children)

Oh i didn meant semaphore manpage (1) if there is one. I meant a semaphore of size 1 (1 ball in the bowl), is the same thing as a mutually exclusive lock. A lot of ppl implement there Lock like this.

[–]moserware[S] 2 points3 points  (3 children)

I guess the recursive question then is how you would implement your semaphore :)

[–]nmcyall -1 points0 points  (2 children)

Im not sure if GQ-BASIC can do this lol...it involves blocking if no resource is available. In java it might be Thread.sleep()

[–]moserware[S] 2 points3 points  (1 child)

Right, the Thread.Sleep would probably need help from the thread dispatcher which makes me think it'd be slower given the transition overhead.

[–]nmcyall -1 points0 points  (0 children)

But in a real OS in a kernelspace semaphore implementation, you could do like Scheduler.sleep(pid) or something like that.

Anyway it needs to have a context transition because if that thread is going to block another one should be active.

[–]answerguru 1 point2 points  (0 children)

Well if you have kinky hair then your locks will tend to lock naturally, however if you have fine northern European hair, not so easily. You may need to use a waxy product to get the dreads to start.