From owner-freebsd-arch Fri Nov 12 0:20:20 1999 Delivered-To: freebsd-arch@freebsd.org Received: from ns1.yes.no (ns1.yes.no [195.204.136.10]) by hub.freebsd.org (Postfix) with ESMTP id 6792814C0B for ; Fri, 12 Nov 1999 00:20:16 -0800 (PST) (envelope-from eivind@bitbox.follo.net) Received: from bitbox.follo.net (bitbox.follo.net [195.204.143.218]) by ns1.yes.no (8.9.3/8.9.3) with ESMTP id JAA11688 for ; Fri, 12 Nov 1999 09:20:15 +0100 (CET) Received: (from eivind@localhost) by bitbox.follo.net (8.8.8/8.8.6) id JAA16510 for freebsd-arch@freebsd.org; Fri, 12 Nov 1999 09:20:14 +0100 (MET) Received: from alpo.whistle.com (alpo.whistle.com [207.76.204.38]) by hub.freebsd.org (Postfix) with ESMTP id CA67B14C0B for ; Fri, 12 Nov 1999 00:20:01 -0800 (PST) (envelope-from julian@whistle.com) Received: from current1.whiste.com (current1.whistle.com [207.76.205.22]) by alpo.whistle.com (8.9.1a/8.9.1) with ESMTP id AAA07016; Fri, 12 Nov 1999 00:05:43 -0800 (PST) Date: Fri, 12 Nov 1999 00:05:42 -0800 (PST) From: Julian Elischer To: Michael Schuster - TSC SunOS Germany Cc: "freebsd-arch@FreeBSD.ORG" Subject: Re: Threads goals and implementation In-Reply-To: <382ABB1A.CB959F01@germany.sun.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-freebsd-arch@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG 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