n:m threads considered good (was RE: SCO: "thread creation is abo ut a thousand times faster than on native Linux")

From: Marty Fouts (marty@dotcast.com)
Date: Fri Aug 25 2000 - 11:22:17 EST

There are good reasons for using "lots" of threads in an application:
one-thread-per-task programming models simplify program design and make
certain programs much easier to write/modify/maintain, most notably some GUI

There are good reasons for keeping the number of "kernel threads" (ie
seperately schedulable threads of control) used by an application "small",
most notably that maximum thread utilization efficiency tends to happen when
the number of kernel threads is approximately equal to the number of
available processors + k where k is an overhead number and is usually near

There are two effective models that try to balance those requirements. If
the underlying system doesn't support n:m threading, then thread pools are
used. Thread pools are a compromise, since they are (slightly) harder to
program than one-thread-per-task models, and expose some stalling issues,
such as blocking system calls. An underlying n:m implementation can make
one-thread-per-task efficient, but has interesting scheduling problems.
(One that I tried to get the community to call "silly-waiting" in the 80s,
is the most common reason for poor implementation.)

I don't know the N:M implementation in Solaris, but the existence of a poor
implementation only proves that there is a poor implementation, not that the
problem is unsolvable. A fairly reasonable, and very straightforward n:m
implementation that solved the silly-waiting and related problems was done
by Cray in the X/MP version of Unicos in the 80s. A similar system was
described in the literature, IIRC, by Brian Bershad, and others, under the
name of Scheduler Activations. The upshot of schedular activations is that
kernel scheduling needs to be slightly aware of library-level thread
scheduling to cooperate in avoiding situations such as a thread that holds a
lock being preempted so that a thread waiting for the lock can spin on it.
(That's silly waiting for those who care.)

It turns out that you have problems like 'silly waiting' in your
implementation whether you use all kernel threads or an n:m thread model,
because the kernel has to be made syncrhonization primitive aware in order
to avoid silly waiting, but you don't want to have to make kernel calls for
synchronization because of the overhead.

The problem with Pthread / signal semantics is that we (The Posix 1003.4 et
cetera folks) tried to impose a multithreaded model on a programming
language / operating system core that were inherently
signals/errno/blocking-system-calls make it difficult to reproduce "un*x"
semantics and remain multithreads; but we took a stab at making it possible.
Other threading models used on "un*x" systems take the more draconian (and
probably wiser) step of saying "you don't get those semantics any more, if
you use the thread model".

My own opinion is that the Pthread spec can be made to work reasonably well
under Linux, and that I'd like to see it done using a scheduler-activation
or similar N:M approach that doesn't work too hard at giving Un*x signalling
semantics to multithreaded applications. (No I'm not volunteering to do the
patch -- I understand the problem but not the Linux kernel details well
enough to do a good job.)

The alternative, of course, would be for the Linux Standard folks to follow
kernel developer leads in specifiying an equivalent set of functionality --
threads, after all, come with the burden of synchronization, and a good
thread library should have a set of synchronization primatives, preferably
something lighter weight than SYSV system calls.

While it would probably be possible to specify a better set of semantics and
cleaner interfaces specific to Linux, doing so would lead to increased
complexity in interacting with the maintainers of the C libraries and other
thread-sensitive facilities -- and someone would end up doing a pthread
layer for it anyway.


-----Original Message-----
From: Theodore Y. Ts'o [mailto:tytso@MIT.EDU]
Sent: Thursday, August 24, 2000 12:17 PM
To: Mark Kettenis
Cc: torlvalds@transmeta.com; linux-kernel@vger.kernel.org;
Subject: Re: SCO: "thread creation is about a thousand times faster than
on native Linux"


   On the issue of 1:1 versus 1:many:

   * The consesus on comp.programming.threads seems to be that 1:1 is
     preferable over 1:many. It seems to be too difficult to get the
     1:many right, and the Solaris' two-level library seems to have
     considerable problems. That's why there is an additional 1:1
     library in Solaris 8.

Heh. Part of the reason why Posix threads has such broken semantics is
because the standards committee wanted to make 1:many implementations
possible. That's why the signal semantics are so.... interesting.

My understanding is that there are some broken applications out there
(which unfortunately include Java) which require a n:m threads
implementations, because they think it's amusing to create (in some
caes) hundreds of thousands of threads, and a 1:1: model simply falls
over in the face of such a (unreasonable?) number of threds.
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

This archive was generated by hypermail 2b29 : Thu Aug 31 2000 - 21:00:16 EST