From owner-freebsd-arch Wed Nov 10 16:40:50 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 D5F1F14E76 for ; Wed, 10 Nov 1999 16:40:29 -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 BAA16699 for ; Thu, 11 Nov 1999 01:40:26 +0100 (CET) Received: (from eivind@localhost) by bitbox.follo.net (8.8.8/8.8.6) id BAA09384 for freebsd-arch@freebsd.org; Thu, 11 Nov 1999 01:40:26 +0100 (MET) Received: from plunger.gdeb.com (plunger.gdeb.com [153.11.11.3]) by hub.freebsd.org (Postfix) with ESMTP id 05A8314E76 for ; Wed, 10 Nov 1999 16:39:56 -0800 (PST) (envelope-from eischen@vigrid.com) Received: from orion.caen.gdeb.com ([153.11.109.11]) by plunger.gdeb.com with ESMTP id TAA00805; Wed, 10 Nov 1999 19:35:06 -0500 (EST) Received: from vigrid.com (clcrtr [153.11.109.129]) by orion.caen.gdeb.com (8.9.3/8.9.3) with ESMTP id TAA59008; Wed, 10 Nov 1999 19:37:29 -0500 (EST) (envelope-from eischen@vigrid.com) Message-ID: <382A0FC9.DDF8228F@vigrid.com> Date: Wed, 10 Nov 1999 19:37:29 -0500 From: "Daniel M. Eischen" X-Mailer: Mozilla 4.51 [en] (X11; U; FreeBSD 3.2-STABLE i386) X-Accept-Language: en MIME-Version: 1.0 To: Julian Elischer Cc: freebsd-arch@freebsd.org Subject: Threads goals and implementation References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-freebsd-arch@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG Julian wanted an updated set of goals and to start defining the implementation details that are becoming clear. -------------------------------------------------------------- 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). 5/ All threads in a process share the same system resources. 6/ (contentious) Multiple theads should be bound to within the resource limits of the single process (see also 13) 7/ Some well documeted scheme exists for handling signals and other async events. 8/ Exit/shutdown protocol is well defined. 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. 10/ Quick access to curthread and thread specific data. 11/ A method to ask a thread blocked in the kernel to wake up and back out (similar to present 'signals'). 12/ Processorr affinity for threads. 13/ Ability to create thread groups that can be assigned separate system resource limits (e.g. priority, quantum). ---- 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. ------------- 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". --------------------------- 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 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