Date: Wed, 4 Dec 1996 19:16:40 -0700 (MST) From: Terry Lambert <terry@lambert.org> To: bakul@plexuscom.com (Bakul Shah) Cc: terry@lambert.org, julian@whistle.com, cracauer@wavehh.hanse.de, nawaz921@cs.uidaho.EDU, freebsd-hackers@freebsd.org Subject: Re: clone()/rfork()/threads (Re: Inferno for FreeBSD) Message-ID: <199612050216.TAA18540@phaeton.artisoft.com> In-Reply-To: <199612042355.SAA16383@chai.plexuscom.com> from "Bakul Shah" at Dec 4, 96 06:55:30 pm
next in thread | previous in thread | raw e-mail | index | archive | help
> > If I, as the scheduler, have a "next quantum" to give away, fairness
> > dictates that I select the next process in the highest priority ready
> > to run queue to give it to.
>
> If, instead of treating a thread *as* a schedulable entity, you
> allow a set of threads to *belong to* the same schedulable entity,
> you can be fair and get around the problems you mentined. The
> kernel runs threads from the same group as long as their quantum has
> not expired and atleast one of them is runnable. When it switches
> back to the same group, it will use a FIFO scheme: the first
> runnable thread to give up the processor is the first to run.
>
> [Didn't the Thoth OS have something like this?]
>
> As an example, if threads A B and C belong to the same schedulable
> entity, then when A blocks, B gets to run provided the quantum is
> not used up. When B blocks, C will run. Now if C hogs the CPU, it
> will be kicked out at the end of the quantum. The next time this
> group is run, A will be run (if it has unblocked) since it was the
> first to give up the CPU.
>
> This way even a compute bound thread will not hog the processor
> nor will it be allowed to be unfair to threads in other groups.
It will, however, be unfair to threads within the group.
Scenario 1:
o Site provides FTP archive
o FTP forks per incoming FTP request up to N ftpd's
o each ftpd competes for one quantum with M non-FTP
processes on the system
o probability of a single ftpd making a blocking call
instead of losing quantum is P
o probability of single ftp consuming quantum and being
involuntarily switched instead of making a blocking
call is (1-P)
Clearly, for any set of X quanta available, a given ftpd will consume
X/(N+M) * P quanta units.
Scenario 2:
o Site provides FTP archive
o FTP creates thread per incoming FTP request up to
N threads
o each ftpd thread competes for quantum in the thread
group. The thread group competes for one quantum
with M non-threaded FTP processes on the system
o probability of a single ftpd thread making a blocking
call instead of losing quantum is P'
o probability of single ftp thread consuming quantum and
being involuntarily switched instead of making a blocking
call is (1-P')
The calculation in the threaded case must take into account:
P' = P - ((1/P) * 100) % 100)/100
... in other words:
1) the probability of a given thread running until it is blocked
is dependent on wheter or not it starts processing with a full
or partial quantum. If 1/P is not an integer, the probability
is reduced.
You must also consider that quantum is valued at (int)1/P'; in other
words, for every thread which can run until it blocks in any given
quantum instead of being invountarily context switched, you count
one "effective quantum".
So each thread consume X(1+M) quanta for X(1+M)*"effective quantum"
units of work per X quanta.
Unless M is less than or equal to the number of units of work, making
the process threaded using your "remaining quantum" algorithm will
unfairly penalize the threaded program for being threaded by reducing
the total number of quanta units per effective quantum (the value of
effective quantum is 1 for the non-threaded program).
For MP, mulitply "effective quantum" units of work per X quanta by
the number of CPUs.
I believe M <= "units of work per X quanta" is a special case
describing an unloaded machine running (nearly) nothing but the
threaded process.
It's unfortunate that most threading benchmarks are run in such
environments, and falsely show threading to be a win in terms of
context switch overhead vs. available quantum.
In laymans terms: "we recommend writing threaded apps so your app will
get propotionately less CPU than everybody's apps who didn't listen
to our recommendations. In addition, your apps performance will drop
off expotentially faster than those of your competitor trying to sell
into the same market, driven by the number of threads divided by
the 'effective quantum', as system load not related to only your app
goes up".
Or even more simply: "use one-quantum-per-thread-group threads to make
you look bad and your competition look good".
8-|
> The above idea can be extended to multi processors fairly easily.
> Though multi-processor schedulers that can also do realtime
> scheduling (and appropriately deal with priority inversion) are not
> easy.
Heh. "locking nodes in a directed acylic graph representing a lock
heirarchy" will address the priority inversion handily -- assuming
you compute transitive closure over the entire graph, instead of the
subelements for a single processors or kernel subsystem. This
requires that you be clere with per processor memory regions for
global objects which are scoped in per processor pools. For instance,
say I have N processors.
global lock
/
/
VM lock
/ | \
/ | \
XXX global page pool ...
/ | \
/ | \
CPU 1 CPU 2 ... CPU N page pool locks
init_page_locks( 2)
{
lock global lock IX (intention exclusive)
lock VM lock IX
lock global page pool IX
lock CPU 2 page pool lock IX
/* promise no one but CPU2, single threaded, will touch
* CPU 2 page pool...
*/
lock CPU 2 page pool lock X (exclusive)
}
alloc_page( 2) /* someone on CPU 2 wants a page...*/
{
is page pool at low water mark? {
/* Prevent other CPU's from doing same...*/
lock X global page pool
get pages from global page pool into CPU 2 page pool
/* OK for other CPU's to do same...*/
unlock X global page pool
}
return = get page from CPU 2 page pool
}
free_page( 2) /* someone on CPU is throwing a page away*/
put page in CPU 2 page pool
is page pool at high water mark? {
/* Prevent other CPU's from doing same...*/
lock X global page pool
put pages from CPU 2 page pool into global page pool
/* OK for other CPU's to do same...*/
unlock X global page pool
}
}
No need to hold a global lock or hit the bus for inter-CPU state unless
we hit the high or low water mark...
Regards,
Terry Lambert
terry@lambert.org
---
Any opinions in this posting are my own and not those of my present
or previous employers.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199612050216.TAA18540>