User: Password:
Subscribe / Log in / New account

Ticket spinlocks

Ticket spinlocks

Posted Feb 7, 2008 21:10 UTC (Thu) by jengelh (subscriber, #33263)
Parent article: Ticket spinlocks

>That raises the maximum system size to 65536 processors - who could ever want more than that?


(Log in to post comments)

Ticket spinlocks

Posted Feb 7, 2008 23:01 UTC (Thu) by brianomahoney (guest, #6206) [Link]

While I suspect it will be a little while before tightly clustered
systems begin to feel this limitation, history is littered with 
_this_should_be_enough_ comments however the algorithm obviously
extends to u_64 (next|current) with little extra cost and that will surely 

Ticket spinlocks

Posted Feb 8, 2008 6:51 UTC (Fri) by zlynx (subscriber, #2285) [Link]

Right, no one could ever need more than 4G processor cores. :)

Ticket spinlocks

Posted Feb 8, 2008 10:43 UTC (Fri) by rvfh (subscriber, #31018) [Link]

I think you missed the ironical reference to Bill Gates' alleged comment "640K of memory
should be enough for anybody." :)

Bill Gates claims this is a urban legend though.


Posted Feb 8, 2008 19:04 UTC (Fri) by jd (guest, #26381) [Link]

The more sophisticated the spinlock allocation mechanism, the greater the overheads. Simply having a wide enough table (and it can be as wide as the UPID mechanism) would be fast, but costly on memory. Spinlocks are also not going to be under equal demand. Perhaps spinlocks can be created with a given ticket width (to reflect expected demand) or have the ticket width grow once a high water mark is exceeded (to reflect actual demand).

There's also the problem of what to do if a maximum of N processes can control something. Do you allocate N spinlocks? That ruins any quality of service you're trying to attain. Or if a process has claimed one spinlock, do you bar it from reclaiming it (or claiming one of the other N) until some sort of fair service guarantee has been achieved?

There seem to be many semi-independent problems involved here, with spinlocks ending up used for 1:1, 1:N, M:1 and M:N situations. in practice, some of these may never really apply, but even if one of the other options applies once, you've a candidate for leading the Department of Headaches.

Do we need smarter spinlocks? Something on top of "dumb" spinlocks to add any extra capabilities? Something that divides the problem-space up such that smarter spinlocks aren't needed? Big spinlocks, such that they can stay as they are and survive in more generalized situations?


Posted Feb 9, 2008 14:09 UTC (Sat) by willy (subscriber, #9762) [Link]

For N processes, you would use a semaphore initialised to N, not a spinlock.  If you wanted N
cpus to be able to do something, then I guess we could introduce a counting spinlock, similar
to a semaphore.  But we've not needed one yet, and I doubt we will.

We have many things implemented on top of spinlocks -- the BKL, semaphores, mutexes, rwlocks,
rwsems and the late and unlamented brwlock (obsoleted by RCU).  Then there's specialised
beasts such as bitlocks and seqlocks.

Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds