Process scheduling vs. Thread scheduling
Ramesh Shankar
In the process scheduling model (pre-multithreaded systems), process
priority (in the time sharing class) depends on its CPU usage. The
usual approach is to favour I/O bound processes as opposed to CPU
bound processes to provide better interactive response.
However, with the multi-threaded Operating Systems, a process can have
more than one thread. I am curious to know the scheduling policies
used to handle the case where a process has 10 threads and another
process has 1 thread. Assuming all the threads are doing the same
"thing," I would expect process 2's thread to run after (for argument
sake) all the threads of process 1 have run.
Basically, is each thread in a process considered independently for
priority calculations or does the usage of 1 thread in a process
affect the priorities of other threads in a process as well? I hope
my question is clear ;-)).
Any ideas on common OSes like SunOS/Solaris, NT etc?
Thanks,
S.R.
-------------------------------------------------------------------------
Ramesh Shankar (S. Ramesh)
Novell Inc.,
Provo, UT
All opinions are my own. I don't speak for Novell Inc.
-------------------------------------------------------------------------
Bryan O'Sullivan
r> Basically, is each thread in a process considered independently for
r> priority calculations or does the usage of 1 thread in a process
r> affect the priorities of other threads in a process as well?
The answer to this question varies, depending on the operating system
in question. Rather than repeat answers that have already been made
to this question, I will point you at the FAQ for the newsgroup
comp.programming.threads:
http://www.serpentine.com/~bos/threads-faq
<b
--
Let us pray:
What a Great System. b...@eng.sun.com
Please Do Not Crash. b...@serpentine.com
^G^IP@P6 http://www.serpentine.com/~bos
Jerry Leichter
| In the process scheduling model (pre-multithreaded systems), process
| priority (in the time sharing class) depends on its CPU usage. The
| usual approach is to favour I/O bound processes as opposed to CPU
| bound processes to provide better interactive response.
|
| However, with the multi-threaded Operating Systems, a process can have
| more than one thread. I am curious to know the scheduling policies
| used to handle the case where a process has 10 threads and another
| process has 1 thread.... Basically, is each thread in a process
| considered independently for priority calculations or does the usage
| of 1 thread in a process affect the priorities of other threads in a
| process as well?
The first thing to keep in mind is that there are, and will almost
certainly continue to be, both user-level and kernel-level threads. In
the basic scheme, user-level threads only exist within a single process.
It's the process that the OS schedules, and the OS doesn't really care
how that process chooses to divide itself up internally. So in a pure
user-level thread implementation, all threads share the "CPU share"
alloted to their single "owning" process. A process with 10 threads
gets the same CPU time as one with 1 thread, assuming all other things
that influence scheduling are equal.
Conversely, in a basic kernel-level thread scheme, the unit of
scheduling becomes the thread, not the process. The kernel schedules
threads pretty much independently of each other. Under such a regime, a
process that splits itself up into 10 threads could potentially get 10
times the CPU that a conservative process that only uses 1 thread would
get.
Some systems - Solaris is an example - combine the two ideas. A process
contains some number of user-level threads, which in turn are executed
by some potentially smaller number of kernel-level threads. (If there
is exactly one kernel-level thread associated with the process, you're
back to the user-level thread model. If there are exactly as many
kernel-level as user-level threads, you get the basic kernel thread
model. In between, you get stuff, well, in between.) As best I can
recall, the kernel-level threads continue to be scheduled independently.
To help control things, you could set limits on the number of kernel-
level threads a user is allowed to have. That way, he can structure his
code as he likes with large numbers of user-level threads, but the
impact his program has on the system is limited.
In theory, you could look at all the kernel-level threads associated
with a process, sum up their CPU time (or whatever), and use that to
influence the priority of all of them. This is expensive, and it's not
clear how much it gains you.
Note that if you're worrying about people deliberately abusing the
system by creating many threads so that they get more than their fair
share of CPU time: They've been able to do that by creating multiple
*processes* for years. In fact, on any system with shared memory (mmap
or equivalent), it's possible without too much effort to get essentially
the kernel-thread programming model out of multiple processes sharing
memory. I know of no OS that tries to keep track of multiple processes
used by a single user for influencing priorities. Perhaps some of the
mainframe OS's have dealt with this in some way. (VMS has a larger-
scale grouping than the process, the "job". It's vaguely like a process
group in Unix. Some quotas are enforced on all the processes within a
job, combined. However, priorities are calculated on a process-at-a-
time basis.)
-- Jerry
George Ball
Ramesh Shankar wrote:
>
> In the process scheduling model (pre-multithreaded systems), process
> priority (in the time sharing class) depends on its CPU usage. The
> usual approach is to favour I/O bound processes as opposed to CPU
> bound processes to provide better interactive response.
>
> However, with the multi-threaded Operating Systems, a process can have
> more than one thread. I am curious to know the scheduling policies
> used to handle the case where a process has 10 threads and another
> process has 1 thread. Assuming all the threads are doing the same
> "thing," I would expect process 2's thread to run after (for argument
> sake) all the threads of process 1 have run.
>
> Basically, is each thread in a process considered independently for
> priority calculations or does the usage of 1 thread in a process
> affect the priorities of other threads in a process as well? I hope
> my question is clear ;-)).
>
> Any ideas on common OSes like SunOS/Solaris, NT etc?
>
In Solaris, each (kernel) thread is considered to be independent by the
sceduling subsystem. Each kernel thread has its own priority, calculated
without any reference to other threads in the same process.
Threads belong to a scheduling class, which determines the properties of
the thread from a scheduling point of view. For example the timesharing
class imposes similar disciplines as the "traditional" Unix model where
I/O bound jobs are favoured and CPU bound jobs penalised. The real-time
class allows threads to have a high, fixed priority and to preempt
kernel activities if necessary.
Essentially the process becomes a container object for the system
resources(memory, files, IPC descriptors etc) used by a collection of
threads.
Since most applications in Solaris anyway are still single threaded, the
default behaviour of all of this is the same as it was in earlier
versions of SunOS. But the model gives more flexibility and "offers much
better scalability to Multi CPU systems..."
Hope this helps
George
Charles A. Jolley
In article <5eaej0$h...@darkstar.ucsc.edu>, RSha...@Novell.COM (Ramesh
Shankar) wrote:
>
> However, with the multi-threaded Operating Systems, a process can have
> more than one thread. I am curious to know the scheduling policies
> used to handle the case where a process has 10 threads and another
> process has 1 thread. Assuming all the threads are doing the same
> "thing," I would expect process 2's thread to run after (for argument
> sake) all the threads of process 1 have run.
By a multithreaded OS, I'm assuming that you mean one in which
multithreading is supported by the OS kernal rather than it being
implemented on a per process basis. Usually, kernal-based threads do
schedule threads of a single process together. This is neccessary to keep
the threads "lightweight."
>
> Basically, is each thread in a process considered independently for
> priority calculations or does the usage of 1 thread in a process
> affect the priorities of other threads in a process as well?
This depends on the OS. In the kernal in development here at Solomon, the
addition of a new thread will affect the scheduling of other threads only
if enough threads are scheduled to use the computer's full processor time.
-Charles
=================================================
Charles A. Jolley
Chief Technology Officer
Solomon Technologies, Inc.
-------------------------------------------------
EM: charle...@usa.net
-------------------------------------------------
Your trusted source for technology advising.
=================================================
***Opinions expressed here are my own***
Mencik Pavel
jhklhjkhkOn 18 Feb 1997, Jerry Leichter wrote:
>
> | In the process scheduling model (pre-multithreaded systems), process
> | priority (in the time sharing class) depends on its CPU usage. The
> | usual approach is to favour I/O bound processes as opposed to CPU
> | bound processes to provide better interactive response.
> |
> | However, with the multi-threaded Operating Systems, a process can have
> | more than one thread. I am curious to know the scheduling policies
> | used to handle the case where a process has 10 threads and another
> | process has 1 thread.... Basically, is each thread in a process
> | considered independently for priority calculations or does the usage
> | of 1 thread in a process affect the priorities of other threads in a
> | process as well?
>
Jonathan Shapiro
In article <5ecmsj$s...@darkstar.ucsc.edu>, Jerry Leichter <leic...@smarts.com> writes:
> Conversely, in a basic kernel-level thread scheme, the unit of
> scheduling becomes the thread, not the process. The kernel schedules
> threads pretty much independently of each other. Under such a regime, a
> process that splits itself up into 10 threads could potentially get 10
> times the CPU that a conservative process that only uses 1 thread would
> get.
Some kernel thread schedulers actually do make some
attempt to "gang" the threads together in order to avoid
flushing the TLB when possible. Otherwise, this is a fair
description.
> Note that if you're worrying about people deliberately abusing the
> system by creating many threads so that they get more than their fair
> share of CPU time...
This is one reason why priorities are a bad model, and why the
authority to claim a part of the CPU needs to be an explicitly
authorized and managed resource. If you only have authority over
10% of the CPU, I shouldn't care how many threads you run in your 10%.
If your interested in exploring this further, have a look at Cliff
Mercer's paper on "Processor Capacity Reserves" (try your local search
engine), and also a look at the EROS object reference, locatable via
the EROS home page:
http://www.cis.upenn.edu/~eros
Jonathan Shapiro
University of Pennsylvania
Ramesh Shankar
On 18 Feb 1997 16:55:10 GMT, "Bryan O'Sullivan" <b...@serpentine.com>
wrote:
>
>r> Basically, is each thread in a process considered independently for
>r> priority calculations or does the usage of 1 thread in a process
>r> affect the priorities of other threads in a process as well?
>
>The answer to this question varies, depending on the operating system
>in question. Rather than repeat answers that have already been made
>to this question, I will point you at the FAQ for the newsgroup
>comp.programming.threads:
>
Actually, the question that I am asking is NOT in the FAQ. The
question was, "Does the CPU usage of one LWP in a process influence
the priority of another LWP in a process?" Uresh Vahalia's book
mentions about a "Fair Share Scheduler." This scheme uses a "share"
for a process and ensures that each share group (which may consist of
a single process, all processes of a user, all processes in a login
session and so on) is alloted a predictable amount of processing time,
independent of the total load on the system.
The question is, is there any OS which implements this scheme, what
are the pros and cons of this? Any pointers to info. on such
implementation?
I know that Windows NT tweaks the base priority associated with a
process to ensure that LWPs (threads in Win NT) associated with a
foreground application get higher priority overall compared to the
LWPs associate with a background application.
I hope my question has been better framed now ;-))
S.R.
-------------------------------------------------------------------------
Ramesh Shankar E-mail: RSha...@Novell.COM
Novell Inc.
Provo, UT, USA
All opinions expressed are my own. I don't speak on behalf of Novell
-------------------------------------------------------------------------
Carl Waldspurger
On 24 Feb 1997 03:20:09 GMT, RSha...@Novell.COM (Ramesh Shankar) writes:
> The question is, is there any OS which implements this scheme, what
> are the pros and cons of this? Any pointers to info. on such
> implementation?
There has been a fair amount of recent work on share-based scheduling,
including papers that appear in the proceedings of both the first and
second OSDI conferences.
My own papers (and Ph.D. thesis) on proportional-share resource
management, which include descriptions of prototype implementations
and references to many other relevant publications, are available via
the web at: <http://www.research.digital.com/SRC/scheduling/papers/caw/>.
Carl Waldspurger
Digital Systems Research Center
http://www.research.digital.com/SRC/personal/caw/
Prashant J. Shenoy
In article <5er1d9$i...@darkstar.ucsc.edu>,
Ramesh Shankar <RSha...@Novell.COM> wrote:
>
>The question is, is there any OS which implements this scheme, what
>are the pros and cons of this? Any pointers to info. on such
>implementation?
>
Hi: You may also want to look at the work done by our group on
fair CPU scheduling. The scheduling algorithm and its prototype
implementation in Solaris are described in the paper :
Pawan Goyal, Xingang Guo, and Harrick M. Vin. "A Hierarchical CPU
Scheduler for Multimedia Operating Systems"
In the proceedings of Second Usenix Symposium on Operating
System Design and Implementation, 1996. Online version is available from
http://www.cs.utexas.edu/users/dmcl
Prashant.
Jonathan Shapiro
In article <5er1d9$i...@darkstar.ucsc.edu>, RSha...@Novell.COM (Ramesh Shankar) writes:
> The
> question was, "Does the CPU usage of one LWP in a process influence
> the priority of another LWP in a process?" Uresh Vahalia's book
> mentions about a "Fair Share Scheduler."
The "Fair Share" scheduler predates kernel-implemented threads. Very
few real implementations of this policy were done. To be consistent
with the intent, the behavior of one LWP can *effectively* degrade another
by using up the share. As a secondary decision, one might choose to
build a gang-scheduler, in which all threads in process X were run before
threads in process Y. Gang schedulers reduce page fault overhead.
In summary, the "fair share" ideas would need to be restated to cover
kernel-scheduled threads, and there are a variety of reasonable approaches.
shap
k