10 ms·

Linus Torvalds on semaphores (1999)

349 points by rainbowgarden 12y ago

wazari972 12y ago
it's surprising that Linus answers peacefully and pedagogically ! and thus it's a nice read to refresh the definition of semaphores, spinlocks and mutexes. Maybe you can edit the title and add a little [199] :-)
- Perceptes 12y ago
  He did start out by saying Peter Samuelson's CS education was bad, so there was certainly some of the infamous Linus in there.
  - rainbowgarden 12y ago
    Can you blame Linus for saying that? I can't speak with precision about 1999, but someone assumed to have a CS education should know the difference between semaphore and spinlock.
    - deleted 12y ago
      [deleted]
    - zo1 12y ago
      Whether they did or didn't know about the definitions, they should have at least looked it up to confirm before posting to the Linux Kernel Dev list or taking on Linus on the matter.
  - devnonymous 12y ago
    Erm, firstly he didn't say Peter's Samuelson's CS education was bad. He said "your CS courses were bad" and then follows up with "...(or just didn't cover much about concurrency, which is fairly common) ..." . I think, you might have been trying very hard to find some of the Linus you imagined in there.
- smcl 12y ago
  I came on here to say exactly this. Fairly or unfairly, Linus gets a lot of criticism for being pretty harsh in some situations. In discussions about this people often stick up for Linus saying that either he's joking or that the people he's addressing can take it and that he's not that way with everyone. I guess this is the first time I've ever seen this side of Linus get any sort of prominence on HN (or elsewhere).
- Intermernet 12y ago
  Like most of the media, someone being polite rarely makes headlines. Linus spends much of his time being polite and helpful on many mailing lists, but it's his outbursts that make headlines, and convince the easily convincable that he's "rude".
- forgottenpass 12y ago
  it's surprising that Linus answers peacefully and pedagogically ! No, it's not. Quit taking blogs at face value.
robert_tweed 12y ago
"Dijkstra was probably a bit heavy on drugs or something (I think the official explanation is that P and V are the first letters in some Dutch words, but I personally find the drug overdose story much more believable)." Quotes like this are why I always read what Linus has to say, regardless of whether the subject is relevant to my life in the slightest. Edit: Yes people, those Dutch words exist! I get it! I'm sure Linus was well aware of that when he made this remark. However, the point Linus was making (in a humorous way) was that like most computer scientists / mathematicians, Dijkstra was overly fond of obscure, single-letter names, which nobody ever intuitively understands. Whereas the names "up" and "down" (see the rest of Linus' quote) are far more intuitive. Personally, I would argue that "hold" and "release" convey the intent in a clearer, more abstract way.
- tomp 12y ago
  Me too. I just love this guy. Sure, some people find him insulting, but I call that "funny".
- otherusername 12y ago
  To say that a mathematician doesn't intuitively understand single-letter names would be like saying a programmer doesn't intuitively understand a keyboard. Dijkstra was a computer scientist in times where being a computer scientist meant you were basically a mathematician with a specialty. Semaphores were first introduced by him in one of his early EWDs (EWD35, http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD35.PDF http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD35.PDF). At the time of EWD35, his EWDs were non-official musings, written in Dutch, intended to be shared amongst interested colleagues and such. It's not like he was writing a scientific paper. I don't think Torvalds really meant anything much by it. He's just trying to be funny.
- drcomputer 12y ago
  > most computer scientists / mathematicians, Dijkstra was overly fond of obscure, single-letter names, which nobody ever intuitively understand If you use a word too common, it's too easy to confuse the definition of that word with the definition of its use in a different context. You must not understand the pain of reading two mathematical books and trying, with the utmost sincerity, to figure out whether the authors are actually using the words the same (such as set, relation, abstraction, object, even things like function). There's the distinct definition, and there is the contextual use, which can theoretically differ for everyone depending on the origin path of native language. You can never know if someone is altering the definition or discovering / describing something new, and they are using the wrong word. Discovering the perfect word for the concept you construct in code or math is an art.
deleted 12y ago
[deleted]
PhantomGremlin 12y ago
Link is to a collection of Linus's comments, from between 1999 and 2008, about how to efficiently implement mutex and semaphores in the Linux kernel. Linus is the BDFL of the Linux kernel, and he obviously needs to think about the big picture. And yet in these comments he gets into nitty-gritty assembly language. I love it when a big picture guy also sweats the details.
deleted 12y ago
[deleted]
Animats 12y ago
Here's Dijkstra's original paper on P and V (in Dutch), from about 1963. http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD35.html http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EW... Here is a implementation of P and V, the original counted semaphore primitives, from 1972. http://www.fourmilab.ch/documents/univac/fang/ http://www.fourmilab.ch/documents/univac/fang/ This is UNIVAC 1108 assembly code. Along with P and V is the code for bounded buffers, with the operations "PUT" and "GET". Bounded buffers are what Go calls "channels". Note how simple they are if you have P and V. That code even works on multiprocessors. There's one semaphore for "queue full" and one for "queue empty". PUT does a P on "queue full", puts on an item, and does a V on "queue empty". GET does a P on "queue empty", takes off an item, and does a V on "queue full". It's very simple. That's the real use case for P and V. Linus' note indicates that in 1999 he didn't know this. (I didn't write those primitives, but I've used that code, and once ported it to a Pascal compiler I adapted to handle concurrency.) This stuff was all well understood four decades ago. Much of it was forgotten outside the mainframe world, because threads and multiprocessors didn't make it to microprocessors for several more decades. UNIX, for a long time, had very primitive synchronization primitives. Early UNIX didn't have threads, and even after it got threads, it took years before the locking primitives settled down. The DOS/Windows world didn't get them until Windows NT, circa 1993. It's been amusing to me to see bounded buffers resurface in Go. They're quite useful, and I've been using them in concurrent programs for many years.
- roel_v 12y ago
  For those wondering, P comes from 'Passering', roughly translated 'pass' (as a noun), and V from 'Vrijgave' ('release'). Apparently somehow this terminology comes from train systems but there's not a lot of context on that etymology. As an aside, this paper (it's actually the transcription of a lecture) has some great metaphors that explain problems with concurrence and issues with synchronisation. At the risk of losing much of the nuances, he essentially illustrates the synchronisation using the example of a teacher who needs to find a pupil in a class. When pupils are free to choose a seat, she needs to scan all seats when she is looking for a particular pupil; but when at the same time pupils are free to change seats as she's scanning, there is no guarantee that she will ever find the pupil she's looking for as he might run from the back of the class to the front as soon as she's done scanning the front.
jgrahamc 12y ago
For those that care why Dijskstra used P() and V(): P for Passering; V for Vrijgave (release)
- barrystaes 12y ago
  Thanks. Fun quote FTA: "" They originally had operations called "P()" and "V()", but nobody ever remembers whether P() was down() or up(), so nobody uses those names any more. Dijkstra was probably a bit heavy on drugs or something (I think the official explanation is that P and V are the first letters in some Dutch words, but I personally find the drug overdose story much more believable). ""
CmonDev 12y ago
Love vintage concurrency techniques :).
- sz4kerto 12y ago
  There's nothing vintage about them. Understanding these is crucial to understand how and why modern concurrency tools work. As I noted above in another comment, the issues that need mutexes or semaphores have never went away, only you might not realize that they're there. And please, don't come up with async/await, callback/continuation, node.js' async stuff. They are not a replacement for mutual exclusion, etc.
  - icebraining 12y ago
    Vintage doesn't mean obsolete.
    - twic 12y ago
      Vintage means "from a particularly good year, the like of which we have not seen for some time". Seems about right for an invention of EWD's.
- sigjuice 12y ago
  Are there concurrency techniques that aren't vintage?
  - richm44 12y ago
    How about hardware transactional memory like the new TSX instructions in the haswell chips.
gsg 12y ago
If you haven't already, follow the 'index' link (to http://yarchive.net/comp/index.html http://yarchive.net/comp/index.html) and bookmark that. Some very worthwhile reading there.
- trentnelson 12y ago
  That whole site is fascinating, I just lost like 2 hours of my life. Late 90s threads about TLB strategies from @sgi.com e-mail addresses? F&$% me, I could read that sort of stuff all day. (I started http://www.snakebite.org http://www.snakebite.org, for reference.)
fleitz 12y ago
This is why I LOVE reading what Linus has to say, it's all very practical, and pretty much ignores theory, because he has actual evidence to support his claims.
xyzzyz 12y ago
Ah, semaphores. I recall in my operating systems course we had to implement some simple concurrency patterns using semaphores as an exercise -- for instance synchronize a group of processes so that idle processes gather into groups of N, and when a group is ready, N-1 threads of the group does TaskX(), and 1 thread does TaskY(), and when they're done, they go back to the pool. Then we implemented the same using usual mutexes and condition variables. I encourage everyone to do that, to see how one of the approaches is much more complicated than the other. Linus says that almost all practical uses of semaphores is when they are just used as mutexes, and rightly so -- implementing concurrency patterns based only on semaphores is a total pain.
- exDM69 12y ago
  > Linus says that almost all practical uses of semaphores is when they are just used as mutexes, and rightly so -- implementing concurrency patterns based only on semaphores is a total pain. Semaphores are not very good in practical programming but they're still valuable as a mental model and reasoning about algorithms. It is a lot easier to prove by induction that an algorithm implemented with semaphores works than it is to deal with mutexes and conditions in a formal proof. So semaphores are very useful in theoretical work, mutexes and conditions are more useful in practice.
pwelch 12y ago
That was a pretty interesting read. Random question, does anyone know what some more active newsgroups lists are today or has it all slowed down?
FoloX 12y ago
Linus absolutely a semaphore genius.
caf 12y ago
The possible future improvement that Linus mentions here: For example, the per-VM memory management semaphore could very usefully be a blocking read-write lock, but without heavy thread contention a mutex semaphore is basically equivalent. has actually come to pass: the mm_struct is now protected by struct rw_semaphore mmap_sem.
esaym 12y ago
Man every time I read linux kernel stuff I want to join the dev team. Kernel development sounds awesome/fun. But I can never seem to make time.
WallWextra 12y ago
Semaphores are basically unused in the kernel these days, abandoned in favor of mutexes. I really recommend reading kernel/locking/mutex.c. You can learn a lot about the details of low-level synchronization, and it's also just a really impressive piece of ruthlessly-optimised code. Tricks like reading the lock's 'owner' field without any sort of synchronization, to decide whether to spin on the lock or to sleep.
- julenx 12y ago
  For the sake of completeness: https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/kernel/locking/mutex.c https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux....
herf 12y ago
The "benchmarks game" has a thread ring benchmark which can compare conditions/mutexes/semaphores, because for some applications they're interchangeable: 4-thread x64: mutex (480s): http://benchmarksgame.alioth.debian.org/u64q/program.php?test=threadring&lang=gcc&id=1 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... sem_wait (476s): http://benchmarksgame.alioth.debian.org/u64q/program.php?test=threadring&lang=gcc&id=2 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... cond_wait (271s - runs single-threaded?) http://benchmarksgame.alioth.debian.org/u64q/program.php?test=threadring&lang=gcc&id=3 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... 1-thread x86: mutex (136s): http://benchmarksgame.alioth.debian.org/u32/program.php?test=threadring&lang=gcc&id=1 http://benchmarksgame.alioth.debian.org/u32/program.php?test... sem_wait (131s): http://benchmarksgame.alioth.debian.org/u32/program.php?test=threadring&lang=gcc&id=2 http://benchmarksgame.alioth.debian.org/u32/program.php?test... cond_wait (156s): http://benchmarksgame.alioth.debian.org/u32/program.php?test=threadring&lang=gcc&id=3 http://benchmarksgame.alioth.debian.org/u32/program.php?test...
knutsonbradacnl 12y ago
Coming from embedded systems and MCU RTOS development, mutexes and semaphores are the name of the game.
haileyr 12y ago
nice
ww520 12y ago
Semaphore and spinlock sure are different. People rarely use spinlock in user mode programs since there are better synchronizing mechanisms in user mode than busy waiting with spinlock. However, in kernel mode program spinlock is invaluable since it's the only synchronizing mechanism that works in any interrupt level.
PinguTS 12y ago
Nice read, but still some misconceptions and misunderstandings. If I am in a multiprocessor design, where each processor runs completely independent from each other and there is no central organizational unit like a central OS, like in many embedded designs, there is no such thing as a spinlock. A semaphore is also not used for sending processes to sleep. Linus explanation makes sense, speaking only about a single OS, which may is comprised of multiple processors. But makes no sense at all for real multi-processor designs. I don't blame him for his narrow view, more his professors that he never experienced real embedded design. I have worked in the past with multi-processors designs, where one processor was using one OS, like OS9, and the other processor had no OS at all running. Both processors where exchanging data via a dual ported RAM. So basically both processes where competing for the same resource. But even than, using a semaphore does not prevent race-conditions. Even then it is very tricky to use them. Because dual ported RAM allowed real concurrent access to the same resource. In summary, the semaphore definition is the more broad definition where 2 (or more) processes are competing for a single resource. The naming convention within Linux is more specific for this requirements. The "invented" spinlock is just a renamed version for a fast semaphore, AFAIK. Even a mutex is just a special case of a semaphore.
- AnimalMuppet 12y ago
  You're blaming Linus for not building something that can synchronize with another processor that isn't running Linux? That seems like it is well outside the scope of Linux's intent. (Linux will get you synchronization if both processors are running Linux as one image, but a processor running no OS? Why do you expect the Linux processor to be able to synchronize with that? I'd expect you to have to implement your own synchronization there, since the other processor is completely outside of Linux's control.)
- caretcaret 12y ago
  You should realize that the post was written in 1999.
  - PinguTS 12y ago
    And I have done my work on this back around 1997/1998 as part of my diploma thesis.
asimpletune 12y ago
Semaphores make a lot more sense if you know their literal translation of the Spanish word "semaforo", which is a "signal". It's also used in Spanish to describe a traffic light.
- darylteo 12y ago
  I thought it got its name from the Semaphore Flag Signalling System. http://www.anbg.gov.au/flags/semaphore.html http://www.anbg.gov.au/flags/semaphore.html
michaelsbradley 12y ago
There's a free book available on the subject of semaphores: The Little Book of Semaphores by Allen Downey http://greenteapress.com/semaphores/ http://greenteapress.com/semaphores/
darylteo 12y ago
Wow I remember some of this class from my OS course 10 years after this was written. We were just told about mutexes, but I never knew that it stood for Mutual Exclusion. (I did correctly intuit that a mutex was simply a specific use case of semaphore though so I'm happy and managed to pass the course in the end :D)

349 points by rainbowgarden 12y ago

it's surprising that Linus answers peacefully and pedagogically ! and thus it's a nice read to refresh the definition of semaphores, spinlocks and mutexes. Maybe you can edit the title and add a little [199] :-)

Perceptes 12y ago
He did start out by saying Peter Samuelson's CS education was bad, so there was certainly some of the infamous Linus in there.
- rainbowgarden 12y ago
  Can you blame Linus for saying that? I can't speak with precision about 1999, but someone assumed to have a CS education should know the difference between semaphore and spinlock.
  - deleted 12y ago
    [deleted]
  - zo1 12y ago
    Whether they did or didn't know about the definitions, they should have at least looked it up to confirm before posting to the Linux Kernel Dev list or taking on Linus on the matter.
- devnonymous 12y ago
  Erm, firstly he didn't say Peter's Samuelson's CS education was bad. He said "your CS courses were bad" and then follows up with "...(or just didn't cover much about concurrency, which is fairly common) ..." . I think, you might have been trying very hard to find some of the Linus you imagined in there.
smcl 12y ago
I came on here to say exactly this. Fairly or unfairly, Linus gets a lot of criticism for being pretty harsh in some situations. In discussions about this people often stick up for Linus saying that either he's joking or that the people he's addressing can take it and that he's not that way with everyone. I guess this is the first time I've ever seen this side of Linus get any sort of prominence on HN (or elsewhere).
Intermernet 12y ago
Like most of the media, someone being polite rarely makes headlines. Linus spends much of his time being polite and helpful on many mailing lists, but it's his outbursts that make headlines, and convince the easily convincable that he's "rude".
forgottenpass 12y ago
it's surprising that Linus answers peacefully and pedagogically ! No, it's not. Quit taking blogs at face value.

robert_tweed 12y ago

"Dijkstra was probably a bit heavy on drugs or something (I think the official explanation is that P and V are the first letters in some Dutch words, but I personally find the drug overdose story much more believable)." Quotes like this are why I always read what Linus has to say, regardless of whether the subject is relevant to my life in the slightest. Edit: Yes people, those Dutch words exist! I get it! I'm sure Linus was well aware of that when he made this remark. However, the point Linus was making (in a humorous way) was that like most computer scientists / mathematicians, Dijkstra was overly fond of obscure, single-letter names, which nobody ever intuitively understands. Whereas the names "up" and "down" (see the rest of Linus' quote) are far more intuitive. Personally, I would argue that "hold" and "release" convey the intent in a clearer, more abstract way.

tomp 12y ago
Me too. I just love this guy. Sure, some people find him insulting, but I call that "funny".
otherusername 12y ago
To say that a mathematician doesn't intuitively understand single-letter names would be like saying a programmer doesn't intuitively understand a keyboard. Dijkstra was a computer scientist in times where being a computer scientist meant you were basically a mathematician with a specialty. Semaphores were first introduced by him in one of his early EWDs (EWD35, http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD35.PDF http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD35.PDF). At the time of EWD35, his EWDs were non-official musings, written in Dutch, intended to be shared amongst interested colleagues and such. It's not like he was writing a scientific paper. I don't think Torvalds really meant anything much by it. He's just trying to be funny.
drcomputer 12y ago
> most computer scientists / mathematicians, Dijkstra was overly fond of obscure, single-letter names, which nobody ever intuitively understand If you use a word too common, it's too easy to confuse the definition of that word with the definition of its use in a different context. You must not understand the pain of reading two mathematical books and trying, with the utmost sincerity, to figure out whether the authors are actually using the words the same (such as set, relation, abstraction, object, even things like function). There's the distinct definition, and there is the contextual use, which can theoretically differ for everyone depending on the origin path of native language. You can never know if someone is altering the definition or discovering / describing something new, and they are using the wrong word. Discovering the perfect word for the concept you construct in code or math is an art.

deleted 12y ago

[deleted]

PhantomGremlin 12y ago

Link is to a collection of Linus's comments, from between 1999 and 2008, about how to efficiently implement mutex and semaphores in the Linux kernel. Linus is the BDFL of the Linux kernel, and he obviously needs to think about the big picture. And yet in these comments he gets into nitty-gritty assembly language. I love it when a big picture guy also sweats the details.

deleted 12y ago

[deleted]

Animats 12y ago

Here's Dijkstra's original paper on P and V (in Dutch), from about 1963. http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD35.html http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EW... Here is a implementation of P and V, the original counted semaphore primitives, from 1972. http://www.fourmilab.ch/documents/univac/fang/ http://www.fourmilab.ch/documents/univac/fang/ This is UNIVAC 1108 assembly code. Along with P and V is the code for bounded buffers, with the operations "PUT" and "GET". Bounded buffers are what Go calls "channels". Note how simple they are if you have P and V. That code even works on multiprocessors. There's one semaphore for "queue full" and one for "queue empty". PUT does a P on "queue full", puts on an item, and does a V on "queue empty". GET does a P on "queue empty", takes off an item, and does a V on "queue full". It's very simple. That's the real use case for P and V. Linus' note indicates that in 1999 he didn't know this. (I didn't write those primitives, but I've used that code, and once ported it to a Pascal compiler I adapted to handle concurrency.) This stuff was all well understood four decades ago. Much of it was forgotten outside the mainframe world, because threads and multiprocessors didn't make it to microprocessors for several more decades. UNIX, for a long time, had very primitive synchronization primitives. Early UNIX didn't have threads, and even after it got threads, it took years before the locking primitives settled down. The DOS/Windows world didn't get them until Windows NT, circa 1993. It's been amusing to me to see bounded buffers resurface in Go. They're quite useful, and I've been using them in concurrent programs for many years.

roel_v 12y ago
For those wondering, P comes from 'Passering', roughly translated 'pass' (as a noun), and V from 'Vrijgave' ('release'). Apparently somehow this terminology comes from train systems but there's not a lot of context on that etymology. As an aside, this paper (it's actually the transcription of a lecture) has some great metaphors that explain problems with concurrence and issues with synchronisation. At the risk of losing much of the nuances, he essentially illustrates the synchronisation using the example of a teacher who needs to find a pupil in a class. When pupils are free to choose a seat, she needs to scan all seats when she is looking for a particular pupil; but when at the same time pupils are free to change seats as she's scanning, there is no guarantee that she will ever find the pupil she's looking for as he might run from the back of the class to the front as soon as she's done scanning the front.

jgrahamc 12y ago

For those that care why Dijskstra used P() and V(): P for Passering; V for Vrijgave (release)

barrystaes 12y ago
Thanks. Fun quote FTA: "" They originally had operations called "P()" and "V()", but nobody ever remembers whether P() was down() or up(), so nobody uses those names any more. Dijkstra was probably a bit heavy on drugs or something (I think the official explanation is that P and V are the first letters in some Dutch words, but I personally find the drug overdose story much more believable). ""

CmonDev 12y ago

Love vintage concurrency techniques :).

sz4kerto 12y ago
There's nothing vintage about them. Understanding these is crucial to understand how and why modern concurrency tools work. As I noted above in another comment, the issues that need mutexes or semaphores have never went away, only you might not realize that they're there. And please, don't come up with async/await, callback/continuation, node.js' async stuff. They are not a replacement for mutual exclusion, etc.
- icebraining 12y ago
  Vintage doesn't mean obsolete.
  - twic 12y ago
    Vintage means "from a particularly good year, the like of which we have not seen for some time". Seems about right for an invention of EWD's.
sigjuice 12y ago
Are there concurrency techniques that aren't vintage?
- richm44 12y ago
  How about hardware transactional memory like the new TSX instructions in the haswell chips.

gsg 12y ago

If you haven't already, follow the 'index' link (to http://yarchive.net/comp/index.html http://yarchive.net/comp/index.html) and bookmark that. Some very worthwhile reading there.

trentnelson 12y ago
That whole site is fascinating, I just lost like 2 hours of my life. Late 90s threads about TLB strategies from @sgi.com e-mail addresses? F&$% me, I could read that sort of stuff all day. (I started http://www.snakebite.org http://www.snakebite.org, for reference.)

fleitz 12y ago

This is why I LOVE reading what Linus has to say, it's all very practical, and pretty much ignores theory, because he has actual evidence to support his claims.

xyzzyz 12y ago

Ah, semaphores. I recall in my operating systems course we had to implement some simple concurrency patterns using semaphores as an exercise -- for instance synchronize a group of processes so that idle processes gather into groups of N, and when a group is ready, N-1 threads of the group does TaskX(), and 1 thread does TaskY(), and when they're done, they go back to the pool. Then we implemented the same using usual mutexes and condition variables. I encourage everyone to do that, to see how one of the approaches is much more complicated than the other. Linus says that almost all practical uses of semaphores is when they are just used as mutexes, and rightly so -- implementing concurrency patterns based only on semaphores is a total pain.

exDM69 12y ago
> Linus says that almost all practical uses of semaphores is when they are just used as mutexes, and rightly so -- implementing concurrency patterns based only on semaphores is a total pain. Semaphores are not very good in practical programming but they're still valuable as a mental model and reasoning about algorithms. It is a lot easier to prove by induction that an algorithm implemented with semaphores works than it is to deal with mutexes and conditions in a formal proof. So semaphores are very useful in theoretical work, mutexes and conditions are more useful in practice.

pwelch 12y ago

That was a pretty interesting read. Random question, does anyone know what some more active newsgroups lists are today or has it all slowed down?

FoloX 12y ago

Linus absolutely a semaphore genius.

caf 12y ago

The possible future improvement that Linus mentions here: For example, the per-VM memory management semaphore could very usefully be a blocking read-write lock, but without heavy thread contention a mutex semaphore is basically equivalent. has actually come to pass: the mm_struct is now protected by struct rw_semaphore mmap_sem.

esaym 12y ago

Man every time I read linux kernel stuff I want to join the dev team. Kernel development sounds awesome/fun. But I can never seem to make time.

WallWextra 12y ago

Semaphores are basically unused in the kernel these days, abandoned in favor of mutexes. I really recommend reading kernel/locking/mutex.c. You can learn a lot about the details of low-level synchronization, and it's also just a really impressive piece of ruthlessly-optimised code. Tricks like reading the lock's 'owner' field without any sort of synchronization, to decide whether to spin on the lock or to sleep.

julenx 12y ago
For the sake of completeness: https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/kernel/locking/mutex.c https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux....

herf 12y ago

The "benchmarks game" has a thread ring benchmark which can compare conditions/mutexes/semaphores, because for some applications they're interchangeable: 4-thread x64: mutex (480s): http://benchmarksgame.alioth.debian.org/u64q/program.php?test=threadring&lang=gcc&id=1 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... sem_wait (476s): http://benchmarksgame.alioth.debian.org/u64q/program.php?test=threadring&lang=gcc&id=2 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... cond_wait (271s - runs single-threaded?) http://benchmarksgame.alioth.debian.org/u64q/program.php?test=threadring&lang=gcc&id=3 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... 1-thread x86: mutex (136s): http://benchmarksgame.alioth.debian.org/u32/program.php?test=threadring&lang=gcc&id=1 http://benchmarksgame.alioth.debian.org/u32/program.php?test... sem_wait (131s): http://benchmarksgame.alioth.debian.org/u32/program.php?test=threadring&lang=gcc&id=2 http://benchmarksgame.alioth.debian.org/u32/program.php?test... cond_wait (156s): http://benchmarksgame.alioth.debian.org/u32/program.php?test=threadring&lang=gcc&id=3 http://benchmarksgame.alioth.debian.org/u32/program.php?test...

knutsonbradacnl 12y ago

Coming from embedded systems and MCU RTOS development, mutexes and semaphores are the name of the game.

haileyr 12y ago

nice

ww520 12y ago

Semaphore and spinlock sure are different. People rarely use spinlock in user mode programs since there are better synchronizing mechanisms in user mode than busy waiting with spinlock. However, in kernel mode program spinlock is invaluable since it's the only synchronizing mechanism that works in any interrupt level.

PinguTS 12y ago

Nice read, but still some misconceptions and misunderstandings. If I am in a multiprocessor design, where each processor runs completely independent from each other and there is no central organizational unit like a central OS, like in many embedded designs, there is no such thing as a spinlock. A semaphore is also not used for sending processes to sleep. Linus explanation makes sense, speaking only about a single OS, which may is comprised of multiple processors. But makes no sense at all for real multi-processor designs. I don't blame him for his narrow view, more his professors that he never experienced real embedded design. I have worked in the past with multi-processors designs, where one processor was using one OS, like OS9, and the other processor had no OS at all running. Both processors where exchanging data via a dual ported RAM. So basically both processes where competing for the same resource. But even than, using a semaphore does not prevent race-conditions. Even then it is very tricky to use them. Because dual ported RAM allowed real concurrent access to the same resource. In summary, the semaphore definition is the more broad definition where 2 (or more) processes are competing for a single resource. The naming convention within Linux is more specific for this requirements. The "invented" spinlock is just a renamed version for a fast semaphore, AFAIK. Even a mutex is just a special case of a semaphore.

AnimalMuppet 12y ago
You're blaming Linus for not building something that can synchronize with another processor that isn't running Linux? That seems like it is well outside the scope of Linux's intent. (Linux will get you synchronization if both processors are running Linux as one image, but a processor running no OS? Why do you expect the Linux processor to be able to synchronize with that? I'd expect you to have to implement your own synchronization there, since the other processor is completely outside of Linux's control.)
caretcaret 12y ago
You should realize that the post was written in 1999.
- PinguTS 12y ago
  And I have done my work on this back around 1997/1998 as part of my diploma thesis.

asimpletune 12y ago

Semaphores make a lot more sense if you know their literal translation of the Spanish word "semaforo", which is a "signal". It's also used in Spanish to describe a traffic light.

darylteo 12y ago
I thought it got its name from the Semaphore Flag Signalling System. http://www.anbg.gov.au/flags/semaphore.html http://www.anbg.gov.au/flags/semaphore.html

michaelsbradley 12y ago

There's a free book available on the subject of semaphores: The Little Book of Semaphores by Allen Downey http://greenteapress.com/semaphores/ http://greenteapress.com/semaphores/

darylteo 12y ago

Wow I remember some of this class from my OS course 10 years after this was written. We were just told about mutexes, but I never knew that it stood for Mutual Exclusion. (I did correctly intuit that a mutex was simply a specific use case of semaphore though so I'm happy and managed to pass the course in the end :D)