Michael Schnell writes:
>> 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?

> 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.

> 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.

> 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.

> Is there are particular reason why you keep posting 'trash about
> threads' into this group?

I just answered to a thread message

> '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/

>
> 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

Michael Schnell writes:
>> 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.

>> '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()).

>> 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.

Rainer Weikusat writes:

[...]

> eg the default Solaris implementation up to and
> including Solaris 9,

s/9/8 :-(

Michael Schnell wrote:

> > 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.

> Anyway this affects only the scheduling sequence and not the count of
> time slices given to the "scheduling entities".

Correct.

> 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.

> 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.

> 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

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.

-Michael

On May 28, 2:28*pm, Michael Schnell
wrote:

> 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

> > > 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?

Jim Jackson wrote:

>> > > 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

Michael Schnell writes:
> 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

On May 23, 4:03*am, David Schwartz wrote:
> On May 21, 10:17*pm, Michael Schnell
>
> 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

On May 29, 11:33*am, karthikbalaguru
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.

DS

On May 30, 12:04*am, David Schwartz wrote:
> On May 29, 11:33*am, karthikbalaguru
> 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/~...cheduling.html

Any ideas ?

Thx in advans,
Karthik Balaguru

karthikbalaguru writes:

[...]

>> > 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 ->

,----
| The nptl implementation [...] uses a 1:1 thread model.
|
| [...]
|
| Therefor only the supported scope is PTHREAD_SCOPE_SYSTEM.
`----
(section 5)

NB: I have purposely removed the author's uninformed opinion about 1:1
threading from the quoted text.

BTW, this is the code which implements pthread_attr_setscope in glibc
2.3.6:

int
__pthread_attr_setscope (attr, scope)
pthread_attr_t *attr;
int scope;
{
struct pthread_attr *iattr;

assert (sizeof (*attr) >= sizeof (struct pthread_attr));
iattr = (struct pthread_attr *) attr;

/* Catch invalid values. */
switch (scope)
{
case PTHREAD_SCOPE_SYSTEM:
iattr->flags &= ~ATTR_FLAG_SCOPEPROCESS;
break;

case PTHREAD_SCOPE_PROCESS:
return ENOTSUP;

default:
return EINVAL;
}

return 0;
}
[note that this is GPL-code, meaning you may not just copy
it into your assortment of BSD-derived trash]

In article ,
jj@franjam.org.uk (Jim Jackson) wrote:
> I was under the impression that switching threads and processes _under
> linux_ were equivalent. Perhaps you could point me at something that says
> otherwise?

If you'd like to measure this, it is actually fairly easy to do, at
least for the case of compute-bound threads and/or processes, being
preempted by the OS, purely with user-mode code.

Basically, you create some shared memory, and use that to store two
things: a timestamp, and an ID that identifies the thread or process
that wrote the timestamp. Your threads and processes run a loop that
looks something like this pseudocode:

1 while ( true ) {
2 while ( id in shared memory == my id )
3 write current time to timestamp in shared memory
4 other_id = id from shared memory
5 other_ts = timestamp from shared memory
6 write invalid id to shared memory
7 if ( other_id is a valid id ) {
8 record context switch took current time - other_ts
9 }
10 write our id to shared memory
11 write current time to timestamp in shared memory
12 }

The idea is that you sit in the loop at 2 until you lose the CPU to
another measurement process. When you get it back, the id will not
match, and you reach line 4. The timestamp in shared memory contains
the time the other process lost the CPU. You've just got it back. So,
we take the difference as the switch time.

This won't always be right, because the system may have run other
processes between the two measurement processes. What you see is that
you get a variety of switch times. However, there will be a minimum,
and you have a lot of these processes or threads going, you'll hit that
minimum a lot. That's the case where the system does preempt one of
your measurement processes and next runs another one of yours.

--
--Tim Smith

Juergen Beisert wrote:

> > 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).

I'm sure you are right, but hadn't realised the context switch figures
were that high, even on an ARM. Are those timings with the newer CFS?

Rainer Weikusat wrote:
> Michael Schnell writes:
> > 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.

Except Gnu Pth which is a portable user space pthreads library, and
as such can be considered as sufficiently mainstream under Linux.

A N:M thread implementation has been developed by IBM for Linux, but
has been abandoned for performance reasons. Similarly such a library has
been introduced for Solaris and for FreeBSD (and NetBSD i think) under
the name KSE, but has been deprecated for performance reasons. In theory
the N:M stuff should allow for better performance at the expense of more
complexity, in practice it seems that complexity is the only result
which is really achieved. However i beleive that commercial N:M
implementations had been developed and were in wide use for IBM AIX
and Digital Unix.

> '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:

Deficiencies in the original LinuxThreads were numerous and in
particular non conformance with standard pthreads. The present
implementation by Ulrich Drepper is both conformant and of good
performance. The present 1:1 implementation for FreeBSD by David Xu
has similar performance.

>
> http://people.redhat.com/drepper/nptl-design.pdf

--

Michel TALON

talon@lpthe.jussieu.fr (Michel Talon) writes:
> Rainer Weikusat wrote:
>> Michael Schnell writes:
>> > 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.
>
> Except Gnu Pth which is a portable user space pthreads library, and
> as such can be considered as sufficiently mainstream under Linux.

.... and except one million of other library implementations (eg Java
'GreenThreads') which can trivially be found on the internet. That's
why I wrote 'distributed with glibc' in an earlier posting.

> A N:M thread implementation has been developed by IBM for Linux, but
> has been abandoned for performance reasons.

That would have been NGPT (Next Generation POSIX Threading Library).

> Similarly such a library has been introduced for Solaris and for
> FreeBSD (and NetBSD i think) under the name KSE, but has been
> deprecated for performance reasons.

The standard Solaris pthreads-library up to Solaris 8 was a M:N
implementation which was deprecated in favor of a 1:1 implementation
lowith Solaris 9. The new library was already available as an option for
8.

Jim Jackson wrote:

> Juergen Beisert wrote:
>
>> > 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).
>
> I'm sure you are right, but hadn't realised the context switch figures
> were that high, even on an ARM. Are those timings with the newer CFS?

On ARM its a hardware restriction. CFS cannot change anything here. We
measured it with an RT preempt kernel.

JB