Userspace M-on-N threading model implementation. Alpha release.
Hello.
I'm pleased to announce initial userspace M-on-N threading model implementation (for hackers) called NTL.
This is first alpha release, which indeed has bugs and limitations.
Userspace M-on-N threading model is based on the idea, that when signal is delivered, kernel saves all information related to previous context in stack, so it is possible to find it and replace.
M-on-N threading model compared to usual NPTL 1-on-1 model has following advantages and disadvantages:
Benefits.
1. Fast scheduling.
There is no need to cross userspace/kernelspace boundary to schedule new thread execution (just watch what happens with userspace network stack compared to kernel's one when there are a lot of syscalls performed for small packets receiving/sending).
2. Fast thread creation and destruction.
It just becomes an allocation of the structure in the userspace, no need for full creation process which is performed in clone() syscall.
3. Smaller number of cache misses.
Since there is only one process instead of several threads, cache locality is increased greatly with reduced number of misses.
Drawbacks.
1. Scheduling fairness.
Since kernel does not know about multiple threads behind given process, it can not add it appropriate number of timeslices for execution. Can be solved either by more tight collaboarion of the userspace and kernelspace schedulers or simply by increasing process' nice value.
2. All communications are performed through one kevent pipe. (TODO) All syscalls are going to be converted into non-blocking operations (including nanosleep() and the like), and keep a track of what each context performed. In practice glibc rewrite is not what I would like to do, but instead some layer on top of it will be implemented, which will convert syscalls into kevent operations, and become a rescheduling point.
3. Complex code for good SMP scalability and userspace scheduler. Not a problem. (TESTING)
SMP scalability in M-on-N threading model.
Since only kernel can schedule thread (actually not even thread or process, but its own kernel's representation, so called kernel's virtual process) to run on specified CPU, M-on-N threading model should have several real threads (for example several current POSIX threads), its number should be equal to number of real CPUs, and then library layer will schedule execution of context of different real threads, each of which in turn can run on separate CPU.
So, userspace will create new real threads when pthread_create() is called until number of them is less than number of real CPUs, each real thread in turn is a context in the global set of contexts, where fake context will be added with all subsequent pthread_create() calls, and userspace scheduler (backed by real threads) will pick up several contexts from the tree and execute them on the real CPUs.
I would be possible to use existing Linux clone() syscall, but due to complete absence of hte documentation (which is sometimes plain wrong) and ery strong encryption of glibc sources it is quite complex task.
As NPTL, M-on-N threading library uses stack rlimit for thread stack allocation.
Benchmarks.
I only ran simple benchmark of empty thread creation (its function just exits).
After I started to use atomic locks ("lock" prefix on x86) instead of semaphores, thread start/empty exec/stop was reduced down to 0.3 microseconds compared to 14 microsecods for POSIX NPTL case.
But there are problems.
First one is that I perform initial context setup through signal invokation, which is at least two syscalls. They are slow. Another one is that thread is really started only after rescheduling, which is another signal, so another two syscalls.
Third on is that there must exist different locking primitives - for signal context and for process context, which must block signals, which in turn adds additional overhead of sigprocmask() syscall.
After I fixed all above issues (actually not fixed, but confirmed that they must exist), performance reduced to 9 microseconds compared to 14 microsecods for POSIX NPTL case for empty thread creation/destruction.
(Test machine is Core Duo 2.4 Ghz (run at 3.7) with 2 GB of ram).
This can be fixed, if I would have created arch-specific getcontext()-like calls, which would be mutually transformable into signal context information (existing getcontext() and friends produces different data than signal context has at least on x86). But I can not right now, since I do not know enough x86 ABI (I learned a lot for past several days, as you can notice from this blog, but it is still even remotely not enough).
Currently M-on-N threading model uses ugly arch-specific hacks to start new threads, which actually are something remotely similar to makecontext().
So, the solution, which will rock M-on-N threading implementation is to convert or create getcontext() and friends calls which can be used with signal context information.
Another limitations are:
* x86 only (I do not have different test boxes to learn different asm)
* does not work if compiled with position-independent code support
* does not work if some functions are inlined (so -fno-inline flag)
* no support for run-time syscall substitution (to make it rescheduling point) yet
* looks like a real hack
Advantages:
* it is faster (noticebly faster)
* it is simpler
* code is not encrypted like in glibc sources
Sources and developement comments can be downloaded from NTL homepage at
http://tservice.net.ru/~s0mbre/old/?section=projects&item=threading
Archive is also attached for interested reader.
Thank you.
Signature · 1 line
Evgeniy Polyakov
P.S. I'm not subscribed to any of the above lists, please Cc: me in replies.
Signature · 1 line
Evgeniy Polyakov
Quoted 4 lines · Evgeniy Polyakov
Hello.
I'm pleased to announce initial userspace M-on-N threading model implementation (for hackers) called NTL.
If you haven't already, I suggest you look into the story of NGPT and also read the NPTL white paper (http://people.redhat.com/drepper/nptl-design.pdf) especially section 5.1 describing why they went with a 1:1 model.
Chris
Hi,
Quoted 3 lines · Evgenity, le Mon 29 Jan 2007 16:47:36 +0100, a écrit :
Userspace M-on-N threading model is based on the idea, that when signal is delivered, kernel saves all information related to previous context in stack, so it is possible to find it and replace.
You may want to have a look at some existing implementations:
- Good old `FSU Pthreads' http://moss.csc.ncsu.edu/~mueller/pthreads/
- fully POSIX-compliant `GnuPth' http://www.gnu.org/software/pth/
- server-targetted `Capriccio' www.cs.berkeley.edu/~jcondit/capriccio-sosp-2003.pdf
- efficient `ELiTE/Erlangen'
http://www4.informatik.uni-erlangen.de/Projects/FORTWIHR/ELiTE/
- and our portable, flexible, efficient `Marcel'
http://runtime.futurs.inria.fr/marcel/
Samuel
Quoted 10 lines · Chris Friesen
Quoted 4 lines · Evgeniy Polyakov
Hello.
I'm pleased to announce initial userspace M-on-N threading model implementation (for hackers) called NTL.
If you haven't already, I suggest you look into the story of NGPT and also read the NPTL white paper
(http://people.redhat.com/drepper/nptl-design.pdf) especially section 5.1 describing why they went with a 1:1 model.
Of course I read this, but it does not change anything.
NGPT had 2 times slower start time than NPTL, and NTL has 2-20 times faster than NPTL, so I think NGPT had too major problems to get it into comparison.
I described in details why and how M:N model better, and its drawbacks include all issues mentioned by Ulrich Drepper, but nevertheless its advantages are far too superiour than those which can be provided by 1:1 model.
Quoted 1 line
Chris
Signature · 1 line
Evgeniy Polyakov
Quoted 8 lines · Samuel Thibault
Hi,
Quoted 3 lines · Evgenity, le Mon 29 Jan 2007 16:47:36 +0100, a écrit :
Userspace M-on-N threading model is based on the idea, that when signal is delivered, kernel saves all information related to previous context in stack, so it is possible to find it and replace.
You may want to have a look at some existing implementations:
I saw most of them.
As far as I recall, only PTL (is not shown here) has preemptible scheduler. NTL has it too, but is based on different approach.
Quoted 10 lines
- Good old `FSU Pthreads' http://moss.csc.ncsu.edu/~mueller/pthreads/
- fully POSIX-compliant `GnuPth' http://www.gnu.org/software/pth/
- server-targetted `Capriccio' www.cs.berkeley.edu/~jcondit/capriccio-sosp-2003.pdf
- efficient `ELiTE/Erlangen'
http://www4.informatik.uni-erlangen.de/Projects/FORTWIHR/ELiTE/
- and our portable, flexible, efficient `Marcel'
http://runtime.futurs.inria.fr/marcel/Samuel
Signature · 1 line
Evgeniy Polyakov
Quoted 9 lines · Samuel Thibault
Quoted 5 lines · Evgeniy Polyakov, le Tue 30 Jan 2007 12:53:16 +0300, a écrit :
Quoted 1 line
You may want to have a look at some existing implementations:
I saw most of them.
As far as I recall, only PTL (is not shown here) has preemptible scheduler. NTL has it too, but is based on different approach.Marcel has a preemptible scheduler too, based on signals and setjmp/longjmp.
Do some documentation and benchmarks exist for that library - site seems to only described environment is was created for? How does blocking problem solved?
Quoted 1 line
Samuel
Signature · 1 line
Evgeniy Polyakov
Quoted 5 lines · Evgeniy Polyakov, le Tue 30 Jan 2007 12:53:16 +0300, a écrit :
Quoted 1 line
You may want to have a look at some existing implementations:
I saw most of them.
As far as I recall, only PTL (is not shown here) has preemptible scheduler. NTL has it too, but is based on different approach.
Marcel has a preemptible scheduler too, based on signals and setjmp/longjmp.
Samuel
Quoted 5 lines · Evgeniy Polyakov
1. Scheduling fairness.
Since kernel does not know about multiple threads behind given process, it can not add it appropriate number of timeslices for execution. Can be solved either by more tight collaboarion of the userspace and kernelspace schedulers or simply by increasing process' nice value.
nice value is only meaningful for SCHED_OTHER. How will you handle a multithreaded realtime application that uses SCHED_OTHER as well as SCHED_FIFO threads?
Lee
Quoted 10 lines · Lee Revell
Quoted 5 lines · Evgeniy Polyakov
1. Scheduling fairness.
Since kernel does not know about multiple threads behind given process, it can not add it appropriate number of timeslices for execution. Can be solved either by more tight collaboarion of the userspace and kernelspace schedulers or simply by increasing process' nice value.nice value is only meaningful for
SCHED_OTHER. How will you handle a multithreaded realtime application that usesSCHED_OTHERas well asSCHED_FIFOthreads?
Threads created inside one process obviously can not compete with RT threads created by other process. Instead process, which threads have RT priority itself should change its priority to RT to compete with other RT process. (By RT I mean any cases except SCHED_OTHER which is default).
Quoted 1 line
Lee
Signature · 1 line
Evgeniy Polyakov