RE: thread rant [semi-OT]
just an aside on asynchronous i/o: concurrency by asychronous I/O actually predates concurrency via thread-like models, and goes back to the earliest OS-precursors. Early work on thread-like concurrency models were, in part, a response to the difficulties inherent in getting asynchronous I/O right, and so now the pendulum is swinging back. A pedantic nit: the basic Un*x I/O model, with syncrhronous interfaces predates Un*x networking by some time. I woudl make the case that the people who grafted Un*x networking (most notably sockets) onto Un*x didn't really understand the I/O model, and crafted cruft, that just happened to have a few usable features, one being a sort-of way of sometimes getting asynchrony. Prior to posix, by the way, there were any number of Un*x variants that asynchronous I/o models, supporting any number of i/o completion notification models, buffering schemes and (lack of) cancellation semantics. My personal favorite was the variant in the Cray-2 Unicos; my personal least favorite was Intergraph's Clix. Marty -Original Message- From: Dan Maas [mailto:[EMAIL PROTECTED]] Sent: Friday, September 01, 2000 11:50 PM To: [EMAIL PROTECTED] Subject: Re: thread rant [semi-OT] [...] Can we do better? Yes, thanks to various programming techniques that allow us to keep more of the system busy. The most important bottleneck is probably the network - it makes no sense for our server to wait while a slow client takes its time acknowledging our packets. By using standard UNIX multiplexed I/O (select()/poll()), we can send buffers of data to the kernel just when space becomes available in the outgoing queue; we can also accept client requests piecemeal, as the individual packets flow in. And while we're waiting for packets from one client, we can be processing another client's request. The improved program performs better since it keeps the CPU and network busy at the same time. However, it will be more difficult to write, since we have to maintain the connection state manually, rather than implicitly on the call stack. So now the server handles many clients at once, and it gracefully handles slow clients. Can we do even better? Yes, let's look at the next bottleneck - disk I/O. If a client asks for a file that's not in memory, the whole server will come to a halt while it read()s the data in. But the SCSI/IDE controller is smart enough to handle this alone; why not let the CPU and network take care of other clients while the disk does its work? How do we go about doing this? Well, it's UNIX, right? We talk to disk files the same way we talk to network sockets, so let's just select()/poll() on the disk files too, and everything will be dandy... (Unfortunately we can't do that - the designers of UNIX made a huge mistake and decided against implementing non-blocking disk I/O as they had with network I/O. Big booboo. For that reason, it was impossible to do concurrent disk I/O until the POSIX Asynchronous I/O standard came along. So we go learn this whole bloated API, in the process finding out that we can no longer use select()/poll(), and must switch to POSIX RT signals - sigwaitinfo() - to control our server***). After the dust has settled, we can now keep the CPU, network card, and the disk busy all the time -- so our server is even faster. [...] - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] Please read the FAQ at http://www.tux.org/lkml/
Re: thread rant [semi-OT]
On Sat, 2 Sep 2000, J. Dow wrote: > Dan, another thing to consider with multithreading is that it is a way > to avoid "convoy" effects if there is a nice priority mechanism for > first in first out messaging. [...] yep, this is a frequent problem at the level of the kernel. We fixed such a (longtime) performance bug just a couple of weeks ago in the TCP-accept logic. We are using FIFO in most places where multiple contexts are waiting. But is 'shared everything multithreading' the natural solution for this? Nope, that statement is misleading. 'Multi-contexting' is the solution. Those contexts can be 'shared-everything threads' or 'isolated processes' as well. Ingo - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] Please read the FAQ at http://www.tux.org/lkml/
Re: thread rant [semi-OT]
> In summary, when "multithreading" floats into your mind, think
> "concurrency." Think very carefully about how you might simultaneously
> exploit all of the independent resources in your computer. Due to the long
> and complex history of OS development, a different API is usually required
> to communicate with each device. (e.g. old-school UNIX has always handled
> non-blocking network I/O with select(), but non-blocking disk I/O is
rather
> new and must be done with AIO or threads; and don't even ask about
> asynchronous access to the graphics card =).
Dan, another thing to consider with multithreading is that it is a way to
avoid "convoy" effects if there is a nice priority mechanism for first in
first out messaging. Until NT crufted in its IO Completion model it was
highly prone to either starvation or convoy problems with certain problems.
If you fired off reads on several interfaces which all experienced about the
same problem the first on in the array searched by the multiple object
wait function was more likely to get serviced than the others. The initial
solution reordered the list each pass through the wait. IO Completion
actually added in first in first out messaging for all the messages
reaching that particular wait for io completion call. This made a VERY
measureable improvement in performance overall. You can run into
the same problems with psuedo-threading in state machines with
polling loops only it's a whole lot uglier. (Been there, done that, kicked
myself, bought the teeshirt in disgrace, and retreated to a proper
solution.)
(Heh, incidentally I was rather surprised by the time I hit NT tasking
to discover its array based message handling. I was used to the
FIFO message queueing on AmigaDOS that it enjoyed from day
zero. So I wrote as if I had that on NT I learned the hard way.)
{^_^}
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
Please read the FAQ at http://www.tux.org/lkml/
Re: thread rant [semi-OT]
> All portability issues aside, if one is writing an application in > Linux that one would be tempted to make multithreaded for > whatever reason, what would be the better Linux way of doing > things? Let's go back to basics. Look inside your computer. See what's there: 1) one (or more) CPUs 2) some RAM 3) a PCI bus, containing: 4) -- a SCSI/IDE controller 5) -- a network card 6) -- a graphics card These are all the parts of your computer that are smart enough to accomplish some amount of work on their own. The SCSI or IDE controller can read data from disk without bothering any other components. The network card can send and receive packets fairly autonomously. Each CPU in an SMP system operates nearly independently. An ideal application could have all of these devices doing useful work at the same time. When people think of "multithreading," often they are just looking for a way to extract more concurrency from their machine. You want all these independent parts to be working on your task simultaneously. There are many different mechanisms for achieveing this. Here we go... A naively-written "server" program (eg a web server) might be coded like so: * Read configuration file - all other work stops while data is fetched from disk * Parse configuration file - all other work stops while CPU/RAM work on parsing the file * Wait for a network connection - all other work stops while waiting for incoming packets * Read request from client - all other work stops while waiting for incoming packets * Process request - all other work stops while CPU/RAM figure out what to do - all other work stops while disk fetches requested file * Write reply to client - all other work stops until final buffer transmitted I've phrased the descriptions to emphasize that only one resource is being used at once - the rest of the system sits twiddling its thumbs until the one device in question finishes its task. Can we do better? Yes, thanks to various programming techniques that allow us to keep more of the system busy. The most important bottleneck is probably the network - it makes no sense for our server to wait while a slow client takes its time acknowledging our packets. By using standard UNIX multiplexed I/O (select()/poll()), we can send buffers of data to the kernel just when space becomes available in the outgoing queue; we can also accept client requests piecemeal, as the individual packets flow in. And while we're waiting for packets from one client, we can be processing another client's request. The improved program performs better since it keeps the CPU and network busy at the same time. However, it will be more difficult to write, since we have to maintain the connection state manually, rather than implicitly on the call stack. So now the server handles many clients at once, and it gracefully handles slow clients. Can we do even better? Yes, let's look at the next bottleneck - disk I/O. If a client asks for a file that's not in memory, the whole server will come to a halt while it read()s the data in. But the SCSI/IDE controller is smart enough to handle this alone; why not let the CPU and network take care of other clients while the disk does its work? How do we go about doing this? Well, it's UNIX, right? We talk to disk files the same way we talk to network sockets, so let's just select()/poll() on the disk files too, and everything will be dandy... (Unfortunately we can't do that - the designers of UNIX made a huge mistake and decided against implementing non-blocking disk I/O as they had with network I/O. Big booboo. For that reason, it was impossible to do concurrent disk I/O until the POSIX Asynchronous I/O standard came along. So we go learn this whole bloated API, in the process finding out that we can no longer use select()/poll(), and must switch to POSIX RT signals - sigwaitinfo() - to control our server***). After the dust has settled, we can now keep the CPU, network card, and the disk busy all the time -- so our server is even faster. Notice that our program has been made heavily concurrent, and I haven't even used the word "thread" yet! Let's take it one step further. Packets and buffers are now coming in and out so quickly that the CPU is sweating just handling all the I/O. But say we have one or three more CPU's sitting there idle - how can we get them going, too? We need to run multiple request handlers at once. Conventional multithreading is *one* possible way to accomplish this; it's rather brute-force, since the threads share all their memory, sockets, etc. (and full VM sharing doesn't scale optimally, since interrupts must be sent to all the CPUs when the memory layout changes). Lots of UNIX servers run multiple *processes*- the "sub-servers" might not share anything, or they might file cache or request queue. If we were brave, we'd think carefully about what resources really should be shared between the sub-servers, and then implement it manually
RE: thread rant [semi-OT]
just an aside on asynchronous i/o: concurrency by asychronous I/O actually predates concurrency via thread-like models, and goes back to the earliest OS-precursors. Early work on thread-like concurrency models were, in part, a response to the difficulties inherent in getting asynchronous I/O right, and so now the pendulum is swinging back. A pedantic nit: the basic Un*x I/O model, with syncrhronous interfaces predates Un*x networking by some time. I woudl make the case that the people who grafted Un*x networking (most notably sockets) onto Un*x didn't really understand the I/O model, and crafted cruft, that just happened to have a few usable features, one being a sort-of way of sometimes getting asynchrony. Prior to posix, by the way, there were any number of Un*x variants that asynchronous I/o models, supporting any number of i/o completion notification models, buffering schemes and (lack of) cancellation semantics. My personal favorite was the variant in the Cray-2 Unicos; my personal least favorite was Intergraph's Clix. Marty -Original Message- From: Dan Maas [mailto:[EMAIL PROTECTED]] Sent: Friday, September 01, 2000 11:50 PM To: [EMAIL PROTECTED] Subject: Re: thread rant [semi-OT] [...] Can we do better? Yes, thanks to various programming techniques that allow us to keep more of the system busy. The most important bottleneck is probably the network - it makes no sense for our server to wait while a slow client takes its time acknowledging our packets. By using standard UNIX multiplexed I/O (select()/poll()), we can send buffers of data to the kernel just when space becomes available in the outgoing queue; we can also accept client requests piecemeal, as the individual packets flow in. And while we're waiting for packets from one client, we can be processing another client's request. The improved program performs better since it keeps the CPU and network busy at the same time. However, it will be more difficult to write, since we have to maintain the connection state manually, rather than implicitly on the call stack. So now the server handles many clients at once, and it gracefully handles slow clients. Can we do even better? Yes, let's look at the next bottleneck - disk I/O. If a client asks for a file that's not in memory, the whole server will come to a halt while it read()s the data in. But the SCSI/IDE controller is smart enough to handle this alone; why not let the CPU and network take care of other clients while the disk does its work? How do we go about doing this? Well, it's UNIX, right? We talk to disk files the same way we talk to network sockets, so let's just select()/poll() on the disk files too, and everything will be dandy... (Unfortunately we can't do that - the designers of UNIX made a huge mistake and decided against implementing non-blocking disk I/O as they had with network I/O. Big booboo. For that reason, it was impossible to do concurrent disk I/O until the POSIX Asynchronous I/O standard came along. So we go learn this whole bloated API, in the process finding out that we can no longer use select()/poll(), and must switch to POSIX RT signals - sigwaitinfo() - to control our server***). After the dust has settled, we can now keep the CPU, network card, and the disk busy all the time -- so our server is even faster. [...] - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] Please read the FAQ at http://www.tux.org/lkml/
