Date: Fri, 12 Nov 1999 00:05:42 -0800 (PST) From: Julian Elischer <julian@whistle.com> To: Michael Schuster - TSC SunOS Germany <michael.schuster@germany.sun.com> Cc: "freebsd-arch@FreeBSD.ORG" <freebsd-arch@freebsd.org> Subject: Re: Threads goals and implementation Message-ID: <Pine.BSF.4.10.9911112314520.17452-100000@current1.whistle.com> In-Reply-To: <382ABB1A.CB959F01@germany.sun.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, 11 Nov 1999, Michael Schuster - TSC SunOS Germany wrote:
> >
> > 5/ All threads in a process share the same system resources.
>
> IMO, this is a contradiction to 13/ and 9/
>
> > 6/ (contentious) Multiple theads should be bound to within the resource
> > limits of the single process (see also 13)
>
> This is implied by 5/ (I see resource limits as "resource" as well -
> "meta" resource, if you will).
>
> >
> > 9/ There exists a set of primatives that allow threads to influence the
> > in-process scheduling between themselves.
> > 9A/ e.g. 'per thread' Thread scheduling classes.
>
> scheduling class is an attribute of a thread, therefore a resource ->
> ergo contradiction to 5/ & 6/
>
> > 10/ Quick access to curthread and thread specific data.
>
> see my suggestion to 5/ below; otherwise, this belongs to implementation
> issues ("quick access").
>
> > 13/ Ability to create thread groups that can be assigned separate system
> > resource limits (e.g. priority, quantum).
>
> see my comment to 6/
>
> my suggestion:
>
> 5/ All threads in a process share the same resources by default with
> the following possible exceptions
> 5a/ the (limits for) the following resources can be set on a
> per-thread basis: priority, quantum, scheduling class.. (your favourite
> here)
> 5b/ thread-specific data such as curthread, thread stack, etc.
>
> and do away with 6/, 9/, 10/ and 13/
>
> PS: Of course, one can always argue that this is just a question of how
> you view and order information in your mind ... no contradiction here...
> --
Well you do raise some points.
here is my altered version:
1/ Multiple independent 'threads of control' within a single process
at user level. The most basic quality of threads.
2/ Ability to simultaneously schedule M threads over N Processors,
and have min(M,N) threads simultaneously executing.
2A/ ability to tune and control the above..
3/ Just because one thread blocks, doesn't mean that
the others can't keep running.
4/ All threads in a processs see the same address space (exactly).
4A/ All threads in a process share the same system resources, except cpu
which is treated specially, and some as yet unspecified thread
specific uniqifier.
5/ A process may be able to group threads into classes that have
different system priorities. These classes can not have priorities
greater than the process itself or a child could achieve, and should
be treatable by the system as a separate child process from a
scheduling point of view (including limits).
5A/ As a result threaded processes should have no more capability to
swamp a system than a regular forking process.
6/ Some well documeted scheme exists for handling signals and other
async events.
7/ Exit/shutdown protocol is well defined.
8/ The allocation of user level threads to thread groups is opaque to the
kernel.
9/ Quick access to curthread and thread specific data.
10/ A method to ask a thread blocked in the kernel to wake up and back
out (similar to present 'signals'). (see 6, 7)
---- possible userland implementation goals-----
1/ A libpthread that can be linked with libc.
2/ Libc needs to change so that library functions and system calls
used internal to the library do not use the externally visible
cancellable equivalents.
3/ see 8 above.
-------------
Meta-goals
-------------
We should keep our eyes on:
*) scalability
*) performance
*) ability to support features required by standards based threads.
*) ability to support features of those therad packages we select as
needed.
---------------------------
Implementation:
1/ User-level thread scheduler that can perform user-level thread (ULT)
context switches. The ULT that is running on a KSE is completely
opaque to the kernel.
2/ The kernel provides KSEs to a process in which ULTs may be run.
Multiple KSEs may be provided to a process in order to achieve
simultaneous SMP executions and to allow ULTs to obtain separate
system resource limits.
2A/ Some code to manage assigments of KSEs to processes and CPUs will be
needed.
3/ Kernel structures (proc, sleep queues, run queues?) will need to
change to support KSEs and multiple threads per process being
blocked in the kernel. It seems that struct proc should be analyzed
to classify components as being relevant to the process, KSEs, or
"context being blocked in the kernel".
Here are my ideas. The terminology is not fixed.
A PROCESS is the holder of all resources related to a single address
space. The SA paper liked to call this an "Address Space" but I think we
want to emphasise it's realtionship to a regular unix process.
The PROCESS may 'fork' off several SUBPROCESSES. These share the resources
of the process with the exception of their scheduling characteristics.
From a scheduling perspective they are the equivalent of child processes.
Each SUBPROCESS is allocated one or more KERNEL SCHEDULABLE ENTITIES
(KSE's). KSE' may be added to or removed from a SUBPROCESS as needed to
prevent it from involuntarily block (except when it's quantum is exceeded)(*)
The USER THREAD SCHEDULER assignes thread to KSE's and is aware of all
threads entering and exiting the kernel. It can release KSE's and handle
the case when a KSE blocks and another is provided as a replacement, It
is probably also aware when a KSE is prempted (though only when that
PROCESS is next run) (i.e. control returns to the UTS, withthe thread's
state available, rather than directly to the thread. The UTS can chose to
load that state adn keep running, or allow some other thread to run,
depending upon whether there are deadlock or similar ramifications.
KSE's from several SUBPROCESSSES may be running simultaniously in an SMP
system, but which threads are in them is decided by the UTS.
We may need to implement THREAD system calls through a different callgate
to allow the different call/return convensions.
---------------------------
Questions:
1/ Do we allow the thread system to schedule different threads when a thread
gets a pagefault? How can we be sure that the pagefault is not in the
scheduler?
---------------------------
References (posted again to provide a more complete set)
Scheduler Activations: Effective Kernel Support for the User-Level Management
of Parallelism
http://www.freebsd.org/~deischen/p95-anderson.pdf
FreeBSD-current mail archives with a 'rfork thread create' implementation
http://www.freebsd.org/cgi/getmsg.cgi?fetch=25000+30231+/usr/local/www/db/text/1999/freebsd-current/19990321.freebsd-current
LinuxThreads
http://lt.tar.com/
Adding Scheduler Activations to Mach 3.0
ftp://ftp.cs.washington.edu/tr/1992/08/UW-CSE-92-08-03.PS.Z
(* appears unreachable at the moment - JRE *)
User-Level Threads and Interprocess Communication
ftp://ftp.cs.washington.edu/tr/1993/02/UW-CSE-93-02-03.PS.Z
Tools and Techniques for Building Fast Portable Threads Packages
ftp://ftp.cs.washington.edu/tr/1993/05/UW-CSE-93-05-06.PS.Z
Efficient Support for Fine-Grain Parallelism
ftp://ftp.cs.arizona.edu/reports/1993/TR93-13a.ps
Performance Experiments for the Filaments Package
ftp://ftp.cs.arizona.edu/reports/1993/TR93-26.ps
Space-efficient Scheduling for Parallel, Multithreaded Computations
http://reports-archive.adm.cs.cmu.edu/anon/1999/CMU-CS-99-119.ps
Chorus:
ftp://ftp.chorus.fr/pub/chorus-reports/
ftp://ftp.chorus.fr/pub/chorus-reports/CS-TR-91-7.ps.Z
ftp://ftp.chorus.fr/pub/chorus-reports/CS-TR-89-37.ps.Z
MACH:
ftp://ftp.cs.cmu.edu/project/mach/doc/published/Rcs.ps
ftp://ftp.cs.cmu.edu/project/mach/doc/unpublished/sched.concur.ps
ftp://ftp.cs.cmu.edu/project/mach/doc/unpublished/threads.ps
ftp://ftp.cs.cmu.edu/project/mach/doc/published/cont_threads.ps
ftp://ftp.cs.cmu.edu/project/mach/doc/published/cmultithread.ps
DEC:
http://www.crl.research.digital.com/publications/techreports/techreports.html
http://www.digital.com/info/DTJF03/DTJF03SC.TXT
ftp://ftp.crl.research.digital.com/pub/dec/Alpha/alpha-osf1-call-std-v1_3.ps
Solaris:
http://suncom.bilkent.edu.tr/workshop/sig/threads/usenix.html
http://www.sun.com/smcc/solaris-migration/docs/courses/threadsHTML/contents.html
---------------------------
What we have at the moment:
John Birrell's excelent work on user-level threading (libc_r), based
originally on Chris provenzo's threading code has given us quite a bit of
mileage so far, but it's starting to run out of steam with new
requirements being more certain about kernel support requirements.
It is notable that we already support Linux kernel threads on FreeBSD
better than we support a native threads model. This is because we support
the 'clone' system call through our rfork() code, and that is their basis
for threading. As is common for this group of people, we have not adopted
the Linux approach because it is considered to be 'too simplistic',
assigning a separate kernel schedulable process to run each thread.
Having said that, Amancio Hasty at one stage wrote a set of threading
primitives to allow Kafe to run on FreeBSD using this scheme of threading,
and Richard Seaman has a port of the Linuxthreads code to freeBSD at his
website, http://lt.tar.com/ . This represents a useful piece of work and
though it is presently not working on -current, hopefully this will be
fixed soon. I believe there may be problems with the new signal stuff
though I have not tested it myself.
I also reference the following email in the archives:
http://www.freebsd.org/cgi/getmsg.cgi?fetch=25000+30231+/usr/local/www/db/text/1999/freebsd-current/19990321.freebsd-current
Peter dufault also has some work on scheduling that may be slightly
relevent.
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.BSF.4.10.9911112314520.17452-100000>