| View previous topic :: View next topic |
| Author |
Message |
Michael Schnell
Guest
|
 Posted: Wed May 28, 2008 2:56 am Post subject: Re: Scheduling between threads of a same process |
 |
|
| Quote: | I was under the impression that switching threads and processes _under
linux_ were equivalent. Perhaps you could point me at something that says
otherwise?
|
Maybe:
http://www-128.ibm.com/developerworks/linux/library/l-threading.html?ca=dgr-lnxw07LinuxThreadsAndNPTL
-Michael |
|
| |
|
 Back to top |
Michael Schnell
Guest
|
| Posted: Wed May 28, 2008 3:54 pm Post subject: Re: Scheduling between threads of a same process |
|
|
| Quote: |
To maximize this benefit, Linux tries to schedule threads that share a
VM "in a row". That is, if it has threads A1 and A2 from process A and
threads B1 and B2 from process B, it will try to schedule "A1 A2 B1
B2" over "A1 B1 A2 B2".
|
Sounds like a good point, but I did not hear about this, yet. Where did
you read that ?
Anyway this affects only the scheduling sequence and not the count of
time slices given to the "scheduling entities". I'm quite sure that this
is not related to the memory mapping. Bit with NTPL support, the
scheduler of the Linux Kernel _does_ have a concept of threads that are
grouped as processes and now acts according to the time slice scheduling
concept the Posix specification requires. That was not possible with the
"old" "Linux-Thread" method (each thread is a Kernel process), but was
done (if necessary) by an additional user space scheduler in a special
version of the pthread library.
-Michael |
|
| |
|
| Back to top |
Rainer Weikusat
Guest
|
| Posted: Wed May 28, 2008 4:35 pm Post subject: Re: Scheduling between threads of a same process |
|
|
Michael Schnell <mschnell_at_lumino_dot_de@gmx.com> writes:
| Quote: | To maximize this benefit, Linux tries to schedule threads that share a
VM "in a row". That is, if it has threads A1 and A2 from process A and
threads B1 and B2 from process B, it will try to schedule "A1 A2 B1
B2" over "A1 B1 A2 B2".
Sounds like a good point, but I did not hear about this, yet. Where
did you read that ?
|
Is there are particular reason why you keep posting 'trash about
threads' into this group?
| Quote: | Anyway this affects only the scheduling sequence and not the count of
time slices given to the "scheduling entities". I'm quite sure that
this is not related to the memory mapping. Bit with NTPL support, the
scheduler of the Linux Kernel _does_ have a concept of threads that
are grouped as processes and now acts according to the time slice
scheduling concept the Posix specification requires.
|
POSIX (or, more correctly, SUS) specifies exactly nothing about
SCHED_OTHER (it is implementation defined) and doesn't contain the
term 'timeslice' anywhere in the text. Apart from that, since 2.6, the
kernel has a concept of 'thread groups', composed of multiple related
kernel tasks, with an associated thread group id that serves as
'process id' for a multi-threaded process. This enable the POSIX
signalling model to be implemented.
| Quote: | That was not possible with the "old" "Linux-Thread" method (each
thread is a Kernel process),
|
There is no such thing as 'a kernel process' (and there never
was). The kernel schedules tasks (struct task_struct) and these tasks
may or may not share certain ressources with other tasks. And this
hasn't changed since 'clone' was invented.
| Quote: | but was done (if necessary) by an additional user space
scheduler in a special version of the pthread library.
|
No threading implementation for Linux distributed together with glibc,
ie LinuxThreads and NPTL, has ever had a 'userspace
scheduler'. Linux-pthread support is and always was a 1:1
implementation. |
|
| |
|
| Back to top |
David Schwartz
Guest
|
| Posted: Wed May 28, 2008 4:36 pm Post subject: Re: Scheduling between threads of a same process |
|
|
Michael Schnell wrote:
| Quote: | To maximize this benefit, Linux tries to schedule threads that share a
VM "in a row". That is, if it has threads A1 and A2 from process A and
threads B1 and B2 from process B, it will try to schedule "A1 A2 B1
B2" over "A1 B1 A2 B2".
Sounds like a good point, but I did not hear about this, yet. Where did
you read that ?
|
From following the development. However, I'm not sure this
optimization is present in the CFS scheduler.
| Quote: | Anyway this affects only the scheduling sequence and not the count of
time slices given to the "scheduling entities".
|
Correct.
| Quote: | I'm quite sure that this
is not related to the memory mapping.
|
It used to be, I'm not sure that it is now. In the LinuxThreads days,
the kernel had no idea if threads were part of the same process, it
only knew that they shared a vm.
| Quote: | Bit with NTPL support, the
scheduler of the Linux Kernel _does_ have a concept of threads that are
grouped as processes and now acts according to the time slice scheduling
concept the Posix specification requires.
|
I'm not sure what time slice scheduling you think the POSIX
specification requires, but I'm pretty sure that whatever you are
thinking is not true.
| Quote: | That was not possible with the
"old" "Linux-Thread" method (each thread is a Kernel process), but was
done (if necessary) by an additional user space scheduler in a special
version of the pthread library.
|
Again, I'm not sure what you are talking about, but I'm pretty sure
that it's not true.
DS |
|
| |
|
| Back to top |
Michael Schnell
Guest
|
| Posted: Wed May 28, 2008 7:30 pm Post subject: Re: Scheduling between threads of a same process |
|
|
| Quote: | Is there are particular reason why you keep posting 'trash about
threads' into this group?
|
I just answered to a thread message
| Quote: | 'process id' for a multi-threaded process. This enable the POSIX
signalling model to be implemented.
|
Time slice assignment seems to be affected, too. A little googeling came
up with
http://kaciula.ro/2007/11/28/posix-threads-unleashed/
| Quote: |
No threading implementation for Linux distributed together with glibc,
ie LinuxThreads and NPTL, has ever had a 'userspace
scheduler'. Linux-pthread support is and always was a 1:1
implementation.
|
I don't know the name of such library But the article above talks of
this, too.
-Michael |
|
| |
|
| Back to top |
Rainer Weikusat
Guest
|
| Posted: Wed May 28, 2008 8:15 pm Post subject: Re: Scheduling between threads of a same process |
|
|
Michael Schnell <mschnell_at_lumino_dot_de@gmx.com> writes:
| Quote: | Is there are particular reason why you keep posting 'trash about
threads' into this group?
I just answered to a thread message
|
The point was that you 'answer' had nothing in common with reality,
which happened to be true for most of your previous postings (eg the
O(1) scheduler is the original Linux 2.6 scheduler and it was
replaced with the CFS scheduler in 2.6.23), insofar I read them.
| Quote: | 'process id' for a multi-threaded process. This enable the POSIX
signalling model to be implemented.
Time slice assignment seems to be affected, too. A little googeling
came up with
http://kaciula.ro/2007/11/28/posix-threads-unleashed/
|
You original claim was that SUS would specify 'something' regarding
timeslices which it doesn't. The 'contention scopes' are an artefact
of M:N threading, eg the default Solaris implementation up to and
including Solaris 9, where 'm' userlevel threads are bound to 'n' LWPs
(light-weight processes scheduled by the kernel). A thread which has
its own LWP bound to it competes with all other LWPs for the system
CPU (contention scope system), one that doesn't competes with other
threads in the same process for a LWP (contention scope process).
The common Linux pthread implementations implement 1:1 threading,
hence, only 'contention scope system'. The random Romanian web page
you cite as 'supporting' even explicitly states this:
Well, NPTL creates all threads with the default scope
PTHREAD_SCOPE_SYSTEM, so we can have multiple threads from the
same process running simultaneously on a multiprocessor
system. In fact, you can't change the scope to
PTHREAD_SCOPE_PROCESS even if you wanted (try
pthread_attr_setscope()).
| Quote: | No threading implementation for Linux distributed together with
glibc, ie LinuxThreads and NPTL, has ever had a 'userspace
scheduler'. Linux-pthread support is and always was a 1:1
implementation.
I don't know the name of such library
|
No such library has ever been part of a Linux pthreads-implementation
being part of glibc. |
|
| |
|
| Back to top |
Rainer Weikusat
Guest
|
| Posted: Wed May 28, 2008 8:16 pm Post subject: Re: Scheduling between threads of a same process |
|
|
Rainer Weikusat <rweikusat@mssgmbh.com> writes:
[...]
| Quote: | eg the default Solaris implementation up to and
including Solaris 9,
|
s/9/8  |
|
| |
|
| Back to top |
David Schwartz
Guest
|
| Posted: Wed May 28, 2008 11:02 pm Post subject: Re: Scheduling between threads of a same process |
|
|
On May 28, 2:28 pm, Michael Schnell
<mschnell_at_bschnell_dot...@aol.com> wrote:
| Quote: | David Schwartz wrote:
Again, I'm not sure what you are talking about, but I'm pretty sure
that it's not true.
Maybe. I did not do my own investigationes on that issue. I got this
impression from following a discussion at the time when NPTL was
introduced. It was about user space scheduling now not being necessary
any more to overcome the incompatibility to Posix threads which could
not be provided with Linux threads.
|
That's still not enough information for me to figure out what you're
thinking of. There were a few incompatabilities with POSIX in
LinuxThreads that NTPL fixed, but I don't know of any involving
scheduling. I just looked at several "LinuxThreads versus NPTL" pages
and none of them mention any changes involving scheduling.
DS |
|
| |
|
| Back to top |
Michael Schnell
Guest
|
| Posted: Thu May 29, 2008 2:28 am Post subject: Re: Scheduling between threads of a same process |
|
|
David Schwartz wrote:
| Quote: | Again, I'm not sure what you are talking about, but I'm pretty sure
that it's not true.
|
Maybe. I did not do my own investigationes on that issue. I got this
impression from following a discussion at the time when NPTL was
introduced. It was about user space scheduling now not being necessary
any more to overcome the incompatibility to Posix threads which could
not be provided with Linux threads.
-Michael |
|
| |
|
| Back to top |
Jim Jackson
Guest
|
| Posted: Thu May 29, 2008 10:20 am Post subject: Re: Scheduling between threads of a same process |
|
|
| Quote: | Al things being equal, the tpc server is more efficient since its
context switches are cheaper.
I was under the impression that switching threads and processes _under
linux_ were equivalent. Perhaps you could point me at something that says
otherwise?
Okay, let's phrase things precisely. All the kernel is ever does is
switch between two kernel scheduling entities. The two cases we are
comparing is one where the KSEs share a vm (which would happen if they
were threads from the same process) and one where the KSEs do not
share a vm (which would happen if they were threads from different
processes).
If the threads share a vm, the OS does not have to change the memory
map. This means no TLB flushes. It also means the TLB cache entries
will still be valid and usable and new entries will not fault in.
To maximize this benefit, Linux tries to schedule threads that share a
VM "in a row". That is, if it has threads A1 and A2 from process A and
threads B1 and B2 from process B, it will try to schedule "A1 A2 B1
B2" over "A1 B1 A2 B2".
Unfortunately, it is very hard to follow discussions on this subject
because people are often not precise in their terminology. I try to be
very precise and use "thread" to mean a POSIX thread, "process" to
mean all the threads that share a particular virtual memory view, and
"kse" to mean what the kernel schedules. Unfortunately, kernel
programmers often use the term "process" to mean a KSE, which
typically corresponds to only a single thread in a multi-threaded
process.
|
Your precision is much appreciated, as is the explanation, which matched
what I understood. But I had under estimated the cost of changing the
memory map on a schedule. Have you any pointers to those costs? Any
timings? |
|
| |
|
| Back to top |
Juergen Beisert
Guest
|
| Posted: Thu May 29, 2008 3:57 pm Post subject: Re: Scheduling between threads of a same process |
|
|
Jim Jackson wrote:
| Quote: | Al things being equal, the tpc server is more efficient since its
context switches are cheaper.
I was under the impression that switching threads and processes _under
linux_ were equivalent. Perhaps you could point me at something that
says otherwise?
Okay, let's phrase things precisely. All the kernel is ever does is
switch between two kernel scheduling entities. The two cases we are
comparing is one where the KSEs share a vm (which would happen if they
were threads from the same process) and one where the KSEs do not
share a vm (which would happen if they were threads from different
processes).
If the threads share a vm, the OS does not have to change the memory
map. This means no TLB flushes. It also means the TLB cache entries
will still be valid and usable and new entries will not fault in.
To maximize this benefit, Linux tries to schedule threads that share a
VM "in a row". That is, if it has threads A1 and A2 from process A and
threads B1 and B2 from process B, it will try to schedule "A1 A2 B1
B2" over "A1 B1 A2 B2".
Unfortunately, it is very hard to follow discussions on this subject
because people are often not precise in their terminology. I try to be
very precise and use "thread" to mean a POSIX thread, "process" to
mean all the threads that share a particular virtual memory view, and
"kse" to mean what the kernel schedules. Unfortunately, kernel
programmers often use the term "process" to mean a KSE, which
typically corresponds to only a single thread in a multi-threaded
process.
Your precision is much appreciated, as is the explanation, which matched
what I understood. But I had under estimated the cost of changing the
memory map on a schedule. Have you any pointers to those costs? Any
timings?
|
For example ARM (here PXA family): Switching between threads: ~100us,
between processes: 550us. But ARM is very special here (cache at the
virtual address bus, needs flush on vm change).
JB |
|
| |
|
| Back to top |
Rainer Weikusat
Guest
|
| Posted: Thu May 29, 2008 4:09 pm Post subject: Re: Scheduling between threads of a same process |
|
|
Michael Schnell <mschnell_at_bschnell_dot_de@aol.com> writes:
| Quote: | David Schwartz wrote:
Again, I'm not sure what you are talking about, but I'm pretty sure
that it's not true.
Maybe. I did not do my own investigationes on that issue. I got this
impression from following a discussion at the time when NPTL was
introduced. It was about user space scheduling now not being necessary
any more to overcome the incompatibility to Posix threads which could
not be provided with Linux threads.
|
No matter how many times you repeat this particular piece of
disinformation, it will not become less wrong: No mainstream
Linux-pthread-implementation has ever had a userspace
scheduler. 'scheduling contention scopes' for threads are defined by
SUS in order to support 1:m threading, n:m threading and 1:1
threading, cf
Conforming implementations shall support the
PTHREAD_SCOPE_PROCESS scheduling contention scope, the
PTHREAD_SCOPE_SYSTEM scheduling contention scope, or both.
Linux-pthreads has always been an 1:1-implementation and has
consequently never supported anything except PTHREAD_SCOPE_SYSTEM.
Design goals for NPTL and the deficiencies in LinuxThreads it intends
to fix can be found in the original NPTL-paper:
http://people.redhat.com/drepper/nptl-design.pdf |
|
| |
|
| Back to top |
karthikbalaguru
Guest
|
| Posted: Thu May 29, 2008 6:33 pm Post subject: Re: Scheduling between threads of a same process |
|
|
On May 23, 4:03 am, David Schwartz <dav...@webmaster.com> wrote:
| Quote: | On May 21, 10:17 pm, Michael Schnell
mschnell_at_bschnell_dot...@aol.com> wrote:
Why should an implementation that uses two processes get twice as much
CPU time as an implementation that uses two threads? That would
unfairly bias one type of implementation over another.
AFAIK, the scheduler does not know about processes and threads, unless
NPTL ("native Posix threads") is activated in the Kernel (available as
of 2.6.??). Thus it seems logical that - given equal priority - without
NPTL, all thread of all processes get the same count of time slices.
With NPTL the threads are grouped and scheduled appropriately (all
processes get the same count of time slices).
No. In fact, with or without NPTL, all threads get the same count of
time slices assuming the same priority.
What you are suggesting would be a disaster, and no sane scheduler
would work that way. Consider two web servers running on the machine,
one uses a process per client and one uses a thread per client, each
have 100 clients. Why should the ppc server get 100 times the CPU of
the tpc server?
Al things being equal, the tpc server is more efficient since its
context switches are cheaper. If anything, the scheduler should reward
the more efficient server, not punish it.
|
But, Interestingly, i came across the below info from
internet which talks about sharing of the CPU among
themselves and which inturn is determined by the
scheduling policy and the thread's priority.
PTHREAD_SCOPE_PROCESS -
All threads of a process that have a scope of
PTHREAD_SCOPE_PROCESS will be grouped together
and this group of threads contents for the CPU. If there is
a process with 4 PTHREAD_SCOPE_PROCESS threads
and 4 PTHREAD_SCOPE_SYSTEM threds, then each of
the PTHREAD_SCOPE_SYSTEM threads will get a fifth
of the CPU and the other 4 PTHREAD_SCOPE_PROCESS
threads will share the remaing fifth of the CPU. How the
PTHREAD_SCOPE_PROCESS threads share their fifth
of the CPU among themselves is determined by the
scheduling policy and the thread's priority.
Any ideas about this ?
Thx in advans,
Karthik Balaguru |
|
| |
|
| Back to top |
David Schwartz
Guest
|
| Posted: Thu May 29, 2008 7:04 pm Post subject: Re: Scheduling between threads of a same process |
|
|
On May 29, 11:33 am, karthikbalaguru <karthikbalagur...@gmail.com>
wrote:
| Quote: | PTHREAD_SCOPE_PROCESS -
All threads of a process that have a scope of
PTHREAD_SCOPE_PROCESS will be grouped together
and this group of threads contents for the CPU. If there is
a process with 4 PTHREAD_SCOPE_PROCESS threads
and 4 PTHREAD_SCOPE_SYSTEM threds, then each of
the PTHREAD_SCOPE_SYSTEM threads will get a fifth
of the CPU and the other 4 PTHREAD_SCOPE_PROCESS
threads will share the remaing fifth of the CPU. How the
PTHREAD_SCOPE_PROCESS threads share their fifth
of the CPU among themselves is determined by the
scheduling policy and the thread's priority.
Any ideas about this ?
|
There might be some platform for which this is sort of true
(Solaris?), but Linux is not such a platform. I know of no platform
where it's literally true -- at best it's a gross oversimplification.
DS |
|
| |
|
| Back to top |
karthikbalaguru
Guest
|
| Posted: Fri May 30, 2008 2:47 am Post subject: Re: Scheduling between threads of a same process |
|
|
On May 30, 12:04 am, David Schwartz <dav...@webmaster.com> wrote:
| Quote: | On May 29, 11:33 am, karthikbalaguru <karthikbalagur...@gmail.com
wrote:
PTHREAD_SCOPE_PROCESS -
All threads of a process that have a scope of
PTHREAD_SCOPE_PROCESS will be grouped together
and this group of threads contents for the CPU. If there is
a process with 4 PTHREAD_SCOPE_PROCESS threads
and 4 PTHREAD_SCOPE_SYSTEM threds, then each of
the PTHREAD_SCOPE_SYSTEM threads will get a fifth
of the CPU and the other 4 PTHREAD_SCOPE_PROCESS
threads will share the remaing fifth of the CPU. How the
PTHREAD_SCOPE_PROCESS threads share their fifth
of the CPU among themselves is determined by the
scheduling policy and the thread's priority.
Any ideas about this ?
There might be some platform for which this is sort of true
(Solaris?), but Linux is not such a platform. I know of no platform
where it's literally true -- at best it's a gross oversimplification.
|
But, I got that info from the below link ->
http://www.net.t-labs.tu-berlin.de/~gregor/tools/pthread-scheduling.html
Any ideas ?
Thx in advans,
Karthik Balaguru |
|
| |
|
| Back to top |
|
