Slashdot Mirror
Linux 2.6 Multithreading Advances
chromatic writes "Jerry Cooperstein has just written an excellent article explaining the competing threading implementations in the upcoming 2.6 kernel for the O'Reilly Network."
← Back to Stories (view on slashdot.org)
Sigh, I'll do your web searching for you.
Basically, while Linus was incommunicado sailing across the ocean, someone got jumpy and suggested 3.0 should be the next step.
It might be more likely that it proceeds through 2.10 and higher before going to 3, though. Just to confuse the people who think version numbers are floating-point.
Many coders are disinclined to use threads, because they don't necessarily improve code speed.
Whether or not multithreading will accelerate any particular program has to be determined case-by-case. And for most software, the deciding factor should be whether threads will simplify development and correctness (theoretically they can, but lots of developers don't understand threads and use them wrong).
My company has some realtime networked game for which threading was an impediment. Both the rate/duration of screen refreshs and network transmissions were low enough so they didn't usually interfere with each other in the same thread. But using thread-safe versions of standard library functions was degrading every other part of the program with constant locking/unlocking.
So nonthreaded was faster. (Maybe cleverer people could've made special thread-unsafe alternative functions to use in contexts where we know inter-thread race conditions won't occur. But munging around with 2 standard libraries in one program is riskier than we'd like to deal with)
While Quake 1 was developed on NEXT, the target platform at that time would have been DOS, so multithreading would be a bit of a problem...
As to further licencees of the engine, revamping the engine to use multithreading was probably not a very high priority in making a game.
On the other hand, for someone writing an engine from scratch is a different matter.
-- Silhouette
In terms of software archeology, there is an important intermediate ancestor.
Quake's original networking was meant for LANs only- the fact that it was even barely playable over the internet suprised the authors.
idsoftware soon released QuakeWorld free to Quake owners. It used the same interface and most of the graphics resources as Quake, so its arguably not a different program. But it came as a separate executable, with many Quake features removed (like monsters). And most importantly, the networking code was entirely re-written.
It is that code that QuakeII and successors derived from.
From what I understand NGPT is mainly a user space thing. Why not go with the 1:1 one in the kernel (NPTL or whatever), just have a libpthread.so (NPTL runtime) and libpthread-mn.so (NGPT). From a programmer's standpoint, when I say pthread_create() I want to know exactly what that does: with NPTL I know what happens. With NGPT I don't. Also, the old rule of "Don't pay for what you don't use" applies. If I'm going to have just, say, four threads, those four threads are going to run better as four kernel threads as opposed to 2 LWP's dynamically mapped between 4 CPU contexts.
But, again, I might want to write a server of some sort which handles hundreds of thousands of connections at once, but 99% are idle at any given time and the other 1% require some nontrivial processing sometimes and/or a long stream of data to be sent without prejudicing the other 99%. Now, for ANY 1:1 threading system, I can't just create x * 10^5 threads because the overhead would be colossal. But equally so, implementing this with poll() is going to be horrid, and if the amount of processing done on a connection is nontrivial and/or DoS'able, there's going to be tons of hairy context management code in there, until lo and behold you end up with a 1:N or M:N scheduling implementation yourself. NGPT could be very useful as a portable userspace library here, as these people have implemented an efficient M:N scheduler under GPL, something that hasn't existed before and could be very useful. I think these libraries might be much more complimentary than the article makes out.
I can easily imagine that one of them might be more efficient for gigantic numbers of threads that don't individually do much, or maybe one might be more efficient for very large numbers of processors, but I don't know jack about the issues involved, so I'm just talking out my ass. (Hello! I'd like to "ass" you a few questions!)
So, someone who knows... Are these threading systems good for different things? And would it really be that hard to make them both come with the kernel?
"You're right," Fisheye says. "I should have set it on 'whip' or 'chop.'"
I really don't understand where people get that ridiculous idea.
Half-Life was mostly based off Quake1. The network protocol and prediction code was taken from QuakeWorld. Some small Quake2 functionality was merged later on.
The initial release of Half-Life was approximatly 65% Quake1, 15% QuakeWorld, 5% Quake2 and 15% Original(Not including the bastardisation of the code into MFC/C++).
And yes, people from Valve have confirmed the base was Quake1, not (as some people continue to claim, and I really wish I knew where the rumor started) Quake2.
Also, the percentages are based off some reverse engineering work I done a while ago when I was playing with making a compatible Linux clone of Half-Life.
(FYI, I took the Quake1 engine.. added Half-Life map loading and rendering within about three hours... Half-Life model support took about four days, and adding a mini-WINE dll loader for the gameplay code took about a week. I gave up on the project when it came down to having to keep it up-to-date with Valves patches)
- Ender
Founder, http://www.quakesrc.org/
Project Leader, http://www.scummvm.org/
I don't understand this all that well myself, but I did just read the whitepaper linked to in the article written by Ingo Molnar and Ulrich Drepper. From the looks of things, NGPT's M:N model will cause a lot more problems because of the difficulty of getting the two schedulers (userspace and kernelspace) to dance well together.
/proc directory when a process has tons of threads.
By sticking with the 1:1 solution that's currently used in the kernel and the NPTL model, there's really only the kernel scheduler to worry about, making things run a lot more smoothly generally. I'd imagine latency being a big issue with M:N (I'm pretty sure that it was mentioned in the whitepaper). I haven't read the other side of the issue, but I think that pretty graph in the O'Reilly article says it all performance-wise.
There are other issues though, like getting full POSIX compliance with signal handling. The 1:1 model apparently makes signal handling much more difficult (I don't know anything about the POSIX signaling model, but there's a paper about it on Drepper's homepage that could probably shed some light on the subject if you were so inclined. There are other issues in the current thread model that have to be dealt with in a new 1:1 model (and are) such as a messy
From the whitepaper, it seems that the development of the O(1) scheduler was meant to facilitate the new thread model they've developed, which I hadn't thought about before even though it makes sense. There's still some issues to work through, but both models look promising. If the signal handling issues can be resolved it looks like from the article that NPTL's model will win on sheer performance.
As for making them both come with the kernel, that's really really difficult, since this stuff touches on some major pieces of the kernel like signal handling. The same way you're only going to get one scheduler and VM subsystem, you're only going to get one threading model. You're able to patch your own tree to your heart's content, but as per a default install, there can be only one.
"I may not have morals, but I have standards."
Wheren't we going to go straight to 3.0?
I don't think the 2.6 vs. 3.0 debate is over yet. But it seems to be quiet right now. I think the discussion will live up when the release date starts getting close about a year from now. And I even think there will be discussion after the release, because the version number come as a complete surprise to some people. And I will not try to guess how much doubt will be in Linus mind once he actually wants to release the thing.
But if you want to be unambigious when talking about it, you should call it 2.6. If it turns out not to be the case everybody will know that it was indeed 3.0 you were talking about. But if you talk about 3.0 already now, and it turns out to be called 2.6, then 3.0 might be something else released in the future.
Do you care about the security of your wireless mouse?
Troll! ;)
---
(And yes, Mike Abrash did WinQuake, not Carmack)
/^[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}$/i
has a nice article about the state of threading on Linux. See the Sept. 27th Weekly Edition.
scheduler does not immediately respond to priority changes
thread-specific storage access is slow
There is a well known effect in multi-threaded programming called priority inversion that can cause deadlocks when a low-priority thread has acquired a resource that a high priority thread is waiting for, but a medium priority thread keeps the low priority thread from beeing executed and so the medium priority thread effectively gets more cycles than the high priority thread.
One way to overcome this problem is to use priority ceiling locks where the priority of a thread is boosted to a ceiling value when it acquires a lock. Unfortunately I found that changing the priority of a thread for a short interval does not have any effect at all with the current 2.4.x standard pthreads implementation.
The second problem I ecountered is that accessing thread-specific storage with pthread_getspecific() takes 100-200 processor cycles on 1 Ghz PIII, which makes this common approach to overcome hotspots almost as slow as locking.
Does anyone know if any of these issues are adressed by the new implementations ?
p.
Without order, nothing can exist. Without chaos, nothing can be created.
Many coders are disinclined to use threads, because they don't necessarily improve code speed.
Further there are a number of examples where writing a single threaded application has definitive benefits. For example applications where deadlocks or race conditions would be an integral problem in a multithreaded implementation whilst a single thread has none of these problems.
"The first thing to do when you find yourself in a hole is stop digging."
I don't see how someone can say that "kernel thread scheduling" is slower than "user thread scheduling". Whatever algorithms pthreads library is using could also be used by a kernel process scheduler and offer the same benefits for daemons that fork() a lot of processes. Indeed, most of the time threads are not used to take advantage of multiple processors. Instead they are used in place of multiple processes with some shared memory that handle multiple requests at once. If they could be re-written to really be multiple processes with some shared memory, the resulting application will be simplier and possibly more stable/secure because only some portions would need to worry about concurrent access. Conceptually, there is no reason why kernel code shouldn't use virtual memory, start system-use processes/threads, load shared libraries and so on. Or why "user" code shouldn't handle IRQs, call internal kernel functions or run in CPU supervisor code. Some tasks demand a certain programming model. For example, one would hope that a disk IRQ handler doesn't use virtual memory. But there is no need to place artificial restrictions to the point that multi-level schedulers and duplicated code are needed to run a nice Java web server.
Someone should start a site that covers long term issues, rather than the week by week stuff I've found on the web... or maybe someone has, and I'm just too out of the loop....
KernelTrap.
ex$$
Mostly because the was unix VMs are designed is much more efficient at multiple process programs than windows is. Windows started doing threads long before smp was all that common. They did it because multi process was slow as hell. But for 90% of tasks it worked just fine in linux. And its not like linux is just now moving to a thread model. Its just making the existing one (which worked well until you scale to many many threads) a bit better. And by better I don't mean similar to windows performance, I mean similar to solaris (which has threading from the gods).
Try lwn.net. They have a weekly overview of the kernel status. Since they moved to a subscription model, you have to pay to see the latest news, but previous weeks can be viewed for free.
"Just like Communism, GNU/HURD will never take off."
More realistically, like communism GNU/HURD is a great idea in theory, but the only available example right now is run by fascist lunatics and doesn't work...
AC because I'm too cruel
Debugging multithreaded programs in Linux is a complete bitch. As the article mentioned, the core dump only has the stack of the thread that caused the fault. Yes, I know any competant multithreaded programmer uses log files extensively in debugging such code but any additional tool helps. Either of these LinuxThreads replacements would be a major improvement. I just hope the major distros roll in either package in their next release.
I bet the 1:1 package would have finer-grained context switching, though. M:N models tend to switch thread contexts only during I/O or blocking system calls. With finer-grained thread switching you tend to expose more bugs in multithreaded code, which is a very good thing. But I suppose even in an M:N model you could always set M=N to acheive similar results.
Regarding thread specific data access: If your LinuxThreads library uses floating stacks (for ix86 this means it has been built with --enable-kernel=2.4 and for i686) it already will be faster.
For other TLS enhancements take a look at http://people.redhat.com/drepper/tls.pdf.
I am not well-versed in the world of Linux, ( have my own allegiances but am being drawn to it more and more. Reading the article, it felt very clear to me that Linux will prevail (with a nod to William Faulkner's Nobel speech).
Consider a few quotes from the article:
Perhaps others have already pointed this out, but I am newly impressed with the universal nature of Linux. The power of an operating system that *everyone* is interested in improving, and has the opportunity to improve, is awesome. Yes, Microsoft has tremendous resources, and very earnest, good-willed, brilliant people. But to improve Microsoft's kernels, you have to work for Microsoft. That means switching the kid's schools, moving to Redmond, etc. etc. On the other hand, everyone from IBM to HP to some kid in, say, Finland, can add a good idea to Linux. When the kernel's threads implementation is a topic for conversation at conferences, with multiple independent teams coming up with their best ideas, Linux is sure to win in the long run.
I'm struck by the parallels to my own field of scientific research: Yes, the large multinational companies have made tremendous contributions in materials science, seminconductors, and biotech. They work on the "closed-source", or perhaps "BSD" model of development. But it is the "GPL"-like process of peer-reviewed, openly shared, and collaborative academic science that has truly prevailed.
four nine eighteen twenty-7 thirty-nine forty-7 fiftyeight sixty-nine seventy-9 eighty-8 one-hundred-and-nine one-twenty
Correctly programming threads is hard, so they should only be used when necessary. Many of the things that can be done with threads can be done more safely with fork() and/or select(). Since Windows lacks the former and has a broken version of the latter, Windows programmers tend to use threads when Unix programmers would use an alternative.
Regarding changing of priorities, I think that with SCHED_OTHER the priority is beeing automatically modified by the scheduler to distibute cycles in a more fair fashion.
I tried both SCHED_RR and SCHED_FIFO and changing priorities basically works, but it seemed to me that changing priorities did not have an immediate effect as required to implement priority ceiling locks.
For example, when boosting the priority of a thread to the ceiling priority, and the thread is the only one with this priority, I expect it to run without beeing preempted by anyone before the priority is lowered or the process blocks. On the other hand, when lowering the priority, I expect a higher prio thread to be executed immediately. I would also expect the order of unblocking threads is correctly adjusted when their priority was changed while suspended.
However, it seems that priority changes do not much affect the actual timeslice or the unblocking order, but I did not have the means to find out what exactly happens; using a debugger is outright impossible with fine-grained multi threaded programs.
Is it possible that some system thread needs to run inbetween to do some housekeeping ? Do you have any hints about the scheduler's inner workings ?
Thank you
p.
Without order, nothing can exist. Without chaos, nothing can be created.
That's a common myth. In fact, there are some kinds of deadlock that do go away, but there are also some kinds that merely change their shape. For example, the need to lock a data structure to guarantee consistent updates goes away, and so do deadlocks related to locking multiple data structures. OTOH, resource-contention deadlocks don't go away. You might still have two "tasks" contending for resources A and B, except that in the non-threaded model the tasks might be chained event handlers for some sort of state machine instead of threads. If task1 tries to get A then B, and task2 tries to get B then A, then task1's "B_READY" and task2's "A_READY" events will never fire and you're still deadlocked. Sure, you can solve it by requiring that resources be taken in order, but you can do that with threads too; the problem's solvable, but isn't solved by some kind of single-threading magic.
I've written several articles on this topic for my website in the past. In case anyone's interested...
Slashdot - News for Herds. Stuff that Splatters.
You poor Unix guys are struggling through something we all went through years ago -- learning how to think more sophisticated than a single thread of control correctly.
What the heck does altering the structure of a thread *library* have to do with application-level thread programming? What are you talking about?
May we never see th
While it's great that Linux has excellent multithreading support, it's a shame, however, that many programmers do not take advantage of multi-threading in their programs.
Multi-threading is an easy way to cut down response latency in programs and produce a responsive UI. Unfortunately, it also has many drawbacks -- it can actually be slower (due to having to maintain a bunch of locks...you're usually only better off with threads if you have a very few), and it's one of the very best ways to introduce very hard to debug bugs.
I do think that a lot of GTK programmers, at least, block the UI when they'd be better off creating a single thread to handle UI issues and hand this data off to the core program. Also, when doing I/O that doesn't affect the rest of the program heavily, it can be more straightforward to use threads -- if you have multiple TCP connections running, it can be worthwhile to use a thread for each.
There are a not insignificant number of libraries that are non-reentrant, and have issues with threads. Xlib, gtk+1 (dunno about 2), etc.
Threading is just a paradigm. Just about anything you can manage to pull off with threading you can pull off without threading. The question is just which is cleaner in your case -- worrying about the interactions of multiple threads, or having more complex event handlers in a single-threaded program.
The other problem is that UNIX has a good fork() multi-process model, so a lot of times when a Windows programmer would have to use threads, a UNIX programmer can get away with fork().
So you only really want to use threads when:
* you have a number of tasks, each of which operates mostly independently
* when these tasks *do* need to affect each other, they do so with *large* amounts of data (so the traditional process model doesn't get as good performance).
* You have more CPU-bound "tasks" than CPUs, so you derive a benefit from avoiding context switching that characterizes the fork() model.
* you are using reentrant libraries in everything that the threads must use.
May we never see th
has built-in language support and features for threads, it is becomming almost second nature to think in terms of threads. What a wonderful language!
This is partly a matter of taste, but I dislike languages that are excessively large. That is, when given the choice between implementing a feature in the language itself or in the standard libraries (which are built in, or at least interfaced via, the same language) you should try to use the language you already have.
Academics prefers this because it follows principles like Occam's Razor and MDL (minimum description length, an artificial intelligence related term for program quality).
This simplifies your language definition, but transfers some complexity to your library documentation- which is optional reading for learning the language. And it makes the language more extensible in the future. The classic example that C++ advocates pick on is Java's String class. Two Java Strings support the "+" operator to concatenate them as a special language feature. But 3rd party library developers cannot support "+" with their own Objects, like complex numbers or string-like series of non-character data.
The same argument can be applied (with much more complexity and opportunity for disagreement or plain old error) to the question of including threading support native in the language, rather than as an external library. Language-supporters may say "The language natively provides the CPU's logical, arithmetic, and memory management operations. Threads are just as fundamental, and should go there too". The Library guys respond "No useful program lacks logic,arith,and memory. But we've gotten by fine for decades without threads. They're OPTIONAL. And not all OSes support threads- you want to make them incompatible with your language then?"
It goes back and forth, but winds up with a pro-Library argument backed up by programming language theory- language support for threads offers no more expressive power than library support, so they should be kept in the standard libraries. So C/C++ adopted this approach (or rather, C++ kept the C approach as it had been justified).
It sounds great to theorists, who think that even C++'s 4 styles of parentheses are redundant and excessive compared to what's used in Lisp. But outside of conceptual language design, there's a large practical problem which has retarded the performance of C++ programs to this day: backwards compatibility. Specifically, compatibility of new source code with old linkers. (This problem applied somewhat to the acceptance of other compiled languages besides C++)
To get any acceptance, new versions of C++ needed to be compatibile with user's existing C libraries. And to reduce the workload of C++ compiler developers, they made C++ compilers fit into the C workflow (compile, compile... & link) as directly as possible.
But that undermines one big assumption of the "provide important features IN the language, not AS the language" crowd- the assumption that the compiler is very, very good. Their quality metric ignored the ease of the compiler making good binary code from your source- as long as the language has the ability to express their intent compactly and unambiguously they're happy- but that intent may not be clear if the computer isn't looking at the whole program.
A compiler can make global optimizations if it considers the whole program at once, avoiding the function-call overhead of using external functions for core features. But the C developement processs- only giving the compiler small sections of code at once, and then depending on a separate program to link them together- means that the compiler simply can't make the best choices, burdened with incomplete information. (Today, we sometimes have smarter linkers which support more function inlining and const propagation, but they're a poorer solution than using compilers all the way through).
So, this lack of super-good compilers is why pulling more features into a language definition has been helpful, even though plenty of CS graduate theses say it shouldn't be so.
I don't think C/C++ is a good language either- except to implement other languages in! (Where "other languages" may include all the graphics, networking, compression, and other low-level code that Ada95 programs access via C bindings). And to make the academics most happy, that language should be Lisp or ML, which can then be used to write any other compiler/interpreter you might wish.
There are other valid reasons why C++ is still heavily used, but they're mostly shortsighted and based in legacy compatibility ("We've always written desktop applications that way!")
While it's great that Linux has excellent multithreading support, it's a shame, however, that many programmers do not take advantage of multi-threading in their programs.
What a load of crap. There are plenty on threaded applications for linux. The problem is that all these inexperienced threads-every-fucking-where-programmers" that Java spawned fail to understand that threading is NOT the solution for everything.
Besides in unix style coding few tings are as common as forking about, which in many cases is the what people also do with java all the time. Real single memory space cloned processes (i.e. threads) have less uses than people actually think.
The worst example of this was the Quake I source code, which was used for many games, including Half-Life. The code was not multi-threaded, and the network code sat idle while everything else drew -- adding about 20ms of lag, unless you cut the frame rate down to about 15 or so.
If you'd EVER actually used threads in linux, you'd know that if there are busy threads you would still get to run atmost once in 20ms and even more likely far less seldom.
It's easy to try out even. Write a code that preforms usleep(1) or sched_yields() every now and then and checks how long that takes. Especially try out the case by putting few totally separate processes in the back ground doing while(1); loops. There's your 20ms and way more...
When quake 1 was written the 20 ms lag was concidered NOTHING. At that time online gaming was limited to mainly xpilot and muds. It started the boots and naturally the demands changed, too. THUS ID wrote the Quake World client which was quite different.
Besides a brutal fact always is that single thread process can be made faster than _ANY_ multithreaded approach, although it's often quite difficult. Moreover, threading is never chosen as an approach due to performance, but rather because it simplifies the structure in some cases.
Given the amount of optimization already present in Quake 1, I feel quite safe saying that lack of threads in Dos had jack to do with Quake 1 being single threaded.
1 Earth is warming, 2 It's us, 3 it's royally bad, 4 we need to take action NOW
There aren't really any incompatibilities with older code, so you don't need to go to a new kernel version like you would if you broke anything.
In one of the discussions with Linus on this issue he said there was a planned change that broke something but it wouldn't be in for this version. Because that would warrant a major version change of its own, he didn't want to go from 2.5 to 3.0 then from 3.3 or something to 4.0, he'd rather go from 2.9(or so) to 3.0, and avoid the version inflation.
I agree. There's no stigma in having a product numbered 1.x or 2.x, it simply means you got it right early on, without needing to break old applications too often.
The change in thinking for this is argued in this Sun Whitepaper , and this FAQ .
If one believes the Sun guys have a clue, you can take this as a vote in favor of 1:1.
IMO, anyone who runs more than about 4*NCPUS threads in a program is an idiot; the benchmarks on 10^5 threads are absurd and irrelevant.
Once you run a reasonable number of threads, you can be quickly driven to internal queueing of work from thread to thread; and by the time you have done that, you may already have reached a point of state abstraction that lets you run event driven in a very small number of threads, approaching NCPUs as the lower useful limit. Putting all your state in per-thread storage or on the thread stack is a sign of weak state abstraction.
-dB
"It if was easy to do, we'd find someone cheaper than you to do it."
This is only a factor with a poor multithreaded design. By contrast, single-threaded programs always fail to take advantage of multiple processors, no matter how well they're designed otherwise.
Slashdot - News for Herds. Stuff that Splatters.
A well-designed multi-threaded implemention will organize its thread usage in such a way that under light load and/or on a single processor it will not have significantly more context switches than a single-threaded equivalent. Under such conditions it will exhibit the same performance characteristics as that single-threaded version, and yet it will also be able to take advantage of inherent parallelism and multiple processors when they exist. Been there.
Bad multithreaded implementations schedule so many computationally active threads that TSE switches are inevitable. Bad multithreaded implementations force two context switches per request as work is handed off between "listener" and "worker" threads. Bad multithreaded implementations do lots of stupid things, but not all multithreaded implementations are bad. The main overhead involved in running a well-designed multithreaded program on a uniprocessor is not context switches but locking, and that will be buried in the noise. Done that.
A handful of extra context switches per second and a fraction of a percent of extra locking overhead are a small price to pay for multiprocessor scalability.
Trivial, but stupid. You really will context-switch yourself to death that way, as every occasion where you need to coordinate between processes generates at least one IPC and every IPC generates at least one context switch (usually two or more)...and those are complete process/address-space switches, not relatively lightweight thread switches. That's how to build a really slow application.
No, it doesn't. There's simply no comparison between the speed of using the same memory - often the same cache on the same processor, if you do things right - and shipping stuff across the network...any network, and I was working on 1.6Gb/s full-duplex 2us app-to-app round-trip interconnects five years ago. Writing software to run efficiently on even the best-provisioned loosely-coupled system is even more difficult than writing a good multithreaded program. That's why people only bother for the most regularly decomposable problems with very high compute-to-communicate ratios.
Using separate processes instead of threads on a single machine might allow your other processes to stay alive if one dies, but your application will almost certainly be just as dead. The causal dependencies don't go away just because you're using processes instead of threads. In many ways having the entire application go down is better, because at least then it can be restarted. When I used to work in high availability, a hung node was considered much worse than a crash, and the same applies to indefinite waits when part of a complex application craps out.
Slashdot - News for Herds. Stuff that Splatters.