Scheduling between threads of a same process - Linux

This is a discussion on Scheduling between threads of a same process - Linux ; > > 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, ...

+ Reply to Thread
Page 2 of 2 FirstFirst 1 2
Results 21 to 37 of 37

Thread: Scheduling between threads of a same process

  1. Re: Scheduling between threads of a same process

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

  2. Re: Scheduling between threads of a same process

    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.

  3. Re: Scheduling between threads of a same process


    > 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

  4. Re: Scheduling between threads of a same process

    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.

  5. Re: Scheduling between threads of a same process

    Rainer Weikusat writes:

    [...]

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


    s/9/8 :-(

  6. Re: Scheduling between threads of a same process


    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

  7. Re: Scheduling between threads of a same process

    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

  8. Re: Scheduling between threads of a same process

    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

  9. Re: Scheduling between threads of a same process

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


  10. Re: Scheduling between threads of a same process

    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

  11. Re: Scheduling between threads of a same process

    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

  12. Re: Scheduling between threads of a same process

    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

  13. Re: Scheduling between threads of a same process

    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


  14. Re: Scheduling between threads of a same process

    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]

  15. Re: Scheduling between threads of a same process

    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

  16. Re: Scheduling between threads of a same process

    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


  17. Re: Scheduling between threads of a same process

    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.

+ Reply to Thread
Page 2 of 2 FirstFirst 1 2