lightweight processes / threads
Jocelyne Farhat
>
> I am a PhD student working on threads. At the moment I am doing
> my bibliographical work on the subject and therefore searching for articles.
>
> It seems to me that most of the research in this domain was done at
> Canergie Mellon University and Washington University. I would like to know
> if there are other universities/institutes that are doing research in this
> domain and have published articles or technical reports.
>
> I am also interested in the history of threads. Somebody told me
> that it goes back to 1985.
>
> Merci beaucoup.
>
>Jocelyne.
>
>
I would like to thank all the persons who responded to my request
on threads. I have received many interesting answers. For the persons who
also manifested interest in a summary of the references I got, it follows.
The persons (in alphabetical order) who contributed are:
--------------------------------------------------------
- Hans-J. Boehm
(bo...@parc.xerox.com)
- David B. Chorlian
(dav...@panix.com)
- Didier Donsez
(don...@masi.ibp.fr)
- George W. Leach
(gle...@gte.com)
- Shigekazu INOHARA
(i...@is.s.u-tokyo.ac.jp)
- James Pinakis
(jam...@cs.uwa.edu.au)
- Keyvan Shirnia
(key...@pyra.co.uk)
- Kathy Kirman
(k...@cs.brown.edu)
- Silvano Maffeis
(maf...@ifi.unizh.ch)
- Paul McJones
(mcj...@src.dec.com)
- Marc Maathuis
(m...@chorus.fr)
- Narendra Bhandari
(nbha...@fnugget.intel.com)
- (r...@cs.washington.edu)
- Sacha Krakowiak
(krak...@imag.fr)
- Sylvain R.Y. Louboutin
(slou...@dsg.cs.tcd.ie)
- Srikant Subramaniam.
(sri...@cs.usask.ca)
- Jon E. Stroemme
( Jon.E.S...@kvatro.no)
- Tom Doeppner
(t...@cs.brown.edu)
- Eugene Walden
(wal...@ready.eng.ready.com)
- victor yodaiken
(yoda...@chelm.cs.umass.edu)
The articles that were suggested were:
---------------------------------------
Eric C. Cooper and Richard P. Draves,
"C Threads",
CMU-CS-88_154, June 1988,
Carnegie Mellon University.
## ftp: mach.cs.cmu.edu
Thomas W. Doeppner Jr.
"Threads: A System for the Support of Concurrent Programming",
Brown University,Technical Report CS-87-11,
June 16, 1987.
## ftp.cs.rit.edu:pub/techreports
Thomas W. Doeppner Jr.
"A Threads Tutorial",
Technical Report CS-87-06, March 30, 1987,
Revised December 16, 1987.
Avadis Trevanian, et. al.,
"Mach Threads and the UNIX Kernel: The Battle for Control",
USENIX Conference Proceedings, Summer 1987.
Paul R. McJones and Garret F. Swart,
"Evolving the UNIX System Interface to Support Multithreaded Programs",
USENIX Conference Proceedings, Winter 1989.
Ziya Aral, Ilya Gertner, Alan Langerman, Greg Schaffer,
James Bloom and Thomas Doeppner,
"Variable Weight Processes with Flexible Shared Resources",
USENIX Conference Proceedings, Winter 1989.
Shigekazu Inohara and Kazuhiko Kato and Takashi Masuda,
"Thread Facility Based on User/Kernel Cooperation in the {XERO}
Operating System",
Proceedings of the fifteenth IEEE International
Computer Systems and Applications Conference,IEEE Computer Society,
pages 398-405, Septembre 1991.
Shigekazu Inohara and Kazuhiko Kato and Takashi Masuda,
"{U}nstable {T}hreads' Kernel Interface for Minimizing
the Overhead of Thread Switching",
Proceedings of the 7th IEEE International Parallel Processing
Symposium, April 1993.
Yiannis Samiotakis and Karsten Schwan,
"A Thread Library for the BBN Butterfly Multiprocessor"
Ohio State University, June 1988.
Yiannis Samiotakis,
"A Thread Library for a Non Uniform Memory Access Multiprocessor"
The Ohio State University, 1989.
John E. Faust and Henry M. Levy,
"The Performance of an Object-Oriented Threads Package"
ECOOP/OOPSLA Proceedings, Octobre 1990.
F. Armand, F. Herrmann, J. Lipkis, M. Rozier
"Multi-threaded Processes in CHORUS/MiX",
In: Proc. of EUUG Spring'90 Conference, Munich, Germany,
pp 1-13, 23-27 April 1990,
CS-TR-89-37
Andrew Birrell,
"An Introduction to Programming with Threads"
DEC SRC in Palo Alto
James Pinakis,
"Remote Thread Execution",
Department of Computer Science, the University of Western Australia,
Nelland WA6009
## ftp: ftp.cs.uwa.edu.au
Accetta, M., et al.
"Mach: a new kernel foundation for UNIX development",
In Proceedings of the Summer 1986 USENIX Conference.
Apollo Computer, Inc. (now HP???)
"Concurrent Programming Support (CPS)"
Reference. Order No. 010233, June 1987.
Birrell, A., and Nelson, B.
"Implementing remote procedure calls"
ACM Transactions on Computing Systems 2, 1
Feb 1984.
Birrell, A., Guttag, J., Horning, J., and Levin, R.
"Synchronization primitives for a multiprocessor: a formal specification"
In Proceedings of the 11th Symposium on Operating System Principles
Nov 1987.
Clark, D
"The structuring of systems using up-calls"
In Proceedings of the 10th Symposium on Operating Systems Principles
December 1985.
Guttag, J., Horning, J., and Wing, J.
"The Larch family of specification languages"
IEEE Software 2, 5 ,
September 1985.
Haddon, B,
"Nested Monitor Calls",
Operating Systems Review 11, 4
October 1977.
McJones, P., and Swart, G
"Evolving the UNIX system interface to support multithreaded programs"
In Proceedings of the Winter 1989 USENIX Conference
Feb 1989.
Rovner, P
"Extending Modula-2 to build large, integrated systems"
IEEE Software 3, 6
November 1986
Saltzer, J.
"Traffic control in a multiplexed computer system",
Th., MAC-TR-30, MIT.
Tevanian, A. et al.
"Mach threads and the UNIX kernel: the battle for control",
In Proceedings of the Summer 1987 USENIX Conference ,
June 1987.
Vandevoorde, M., and Roberts, E.
"Workcrews: an abstraction for controlling parallelism",
(Contact Eric Roberts @ src.dec.com)
As for the history, many suggested origins were given:
-------------------------------------------------------
Butler W. Lampson and David D. Redell.
Experience with processes and monitors in Mesa.
Communications of the ACM, Volume 23, Number 2, February 1980.
1- >The notion of a thread, as a sequential flow of control, dates
>back to 1965, at least. Only they weren't called threads at
>that time, but processes (see e.g. Dijkstra, "Cooperating
>sequential processes", 1965). Processes interacted through
>shared variables, semaphores, etc.
2- >Then came Unix, in the early 1970's. The Unix notion of a "process" was
>a sequential thread of control PLUS a virtual address space. So >"processes",
>in the Unix sense, are quite heavyweight machines. Since they
>cannot share memory (each has its own address space), they interact
>through pipes, signals, etc). Shared memory (also a rather ponderous
>mechanism) was added much later.
>After some time, Unix users started to miss the old processes that could
>share memory. This led to the "invention" of threads: old-style
>processes that shared the address space of a Unix process. They also
>were called "lightweight", by reference to the "heavyweight" Unix processes.
>As far as I can remember, this dates back to the very late 70's or early
>80's, i.e the first "microkernels" (V-kernel, Amoeba, Chorus, the
>RIG-Accent-Mach family, etc).
3- >You might be interested in studying also the Telecom tradition for
>threads (usually called processes, but they definitely are lightweight
>threads). There are some languages defined with built-in threads,
>notably CHILL [CCITT Rec Z.200, ISO/IEC IS 9496], which trace their
>origins back to the 70's. And there are kernels for sequential
>languages. These lightweight thread systems are used by literally tens
>of thousands of programmers.
>The lack of communication between Telecom and OS researchers working
>on the same problems is sometimes unbelievable. A comparative study
>of the developments in each camp would be interesting.
4->I can tell you two commercial hardware vendors that have done extensive work
>on threads and light weight processes. One is Pyramid and the other Sequent.
>Sequent's implementation of threads goes back to 1985 (I think), whilst ours
>(Pyramid's) got implemeneted in 1988.
>You probably are aware that Sequent have a publication on their parallel
>fortran compiler and libraries. "Guide to Parallel Programming", Sequent
>Corportation 1985.
5- >Re: history of threads of control. See the discussion of co-routines
>and interrupts in Knuth Volume I (1968). The idea of multiple
>threads of control was not new then, either.
Merci encore une fois.
Jocelyne.
-----------------------------------
Jocelyne Farhat
Telecom Paris
Departement Informatique
Tel: 33-1-45-81-79-95
e-mail: far...@inf.enst.fr
-----------------------------------
James Sterbenz
>1- >The notion of a thread, as a sequential flow of control, dates
>>back to 1965, at least. Only they weren't called threads at
>>that time, but processes (see e.g. Dijkstra, "Cooperating
>>sequential processes", 1965). Processes interacted through
>>shared variables, semaphores, etc.
In fact the idea of a 2-level hierarchy equivalent to what we call today
processes and threads dates from about the same era. OS/360 and sucessors
had "jobs" using a partition, region, and later address space and lighter
weight "tasks" that ran withing a single job and address space. We even
had an internal project in the late 70's and early 80's that had lighter
weight still loci of control (the original official ACM definition of
a process) which we even called "threads"; as far as I know with no
knowledge (either way) of the current thread definition. I suspect in
poking through all the other interesting operating systems of the time
(MCP, MULTICS, SCOPE, TSS, etc.) there were other examples of "thread"
implementations.
It all comes back around...
--
James Sterbenz IBM HPCC (High Performance Computing and Communications)
472 Wheelers Farms Rd. MS93 jp...@watson.vnet.ibm.com
Milford CT 06460-1844 USA +1 203 783 4380