preemptive multi-tasking version of linux kernel?
Roger Reynolds
I was wondering if anybody has come up with a kernel hack that would
allow for "premptive multi-tasking". It seems to me that with a few
well placed hacks to the scheduler, one should be able to guarantee
that the highest priority task that is runnable is always the one that
is running.
I dunno, just a quick thought. Anybody else going down this road?
Thanks,
r...@rogerware.com
Atarax
I believe that Linux already does this, and has since 0.00pl0... (if you mean
preemptive to be requiring tasks to give up time, rather than assuming tasks
know how to give up time)
--
ata...@eznet.net ----/\/\/---- Resist,
-----|(------ Don't Capacitate!
Finger ata...@eznet.net for instructions on how to log on to Hydroxyzine, my
PGP key, and my disclaimer for this message.
===============================================================================
D. Duke Smith
multitasking decades ago. It only started being called "preemptive"
when B Gates started peddling his toy "multitasking" "OS"'s. Non-
preemptive "real" multitasking is more useful in realtime or embedded
systems where there are no "users" in the time-sharing sense.
In such systems, each task runs to completion or until it decides to
rest. Obviously this can only work when there is an overall
architecture and cooperation protocol, ie: 1 "user". These things
generally drive controller cards & so forth.
Preemptive in the Unix MT world simply means the OS, which can
always "preempt" a task (even in Windows), preempts the currently
running task on behalf of another task which
has convinced it that it should
get the cpu, like when a higher-priority task which has been waiting
on input gets its data.
A historical note - Unix used to be called "multiprocessing" because
multiple processes shared the processor, and there was a big debate
about allegedly significant differences between IBM OS/360/VS[12]/MVS
"multitasking" and Unix "multiprocessing". These guys stopped Pi__ing
on each others' shoes when multiple processor machines came along
and they needed a name for what they do. So they stopped fighting
and decided there were no significant differences .... Bet you were
waiting to hear about this histrivia.
Tim Smith
>Preemptive in the Unix MT world simply means the OS, which can
>always "preempt" a task (even in Windows), preempts the currently
>running task on behalf of another task which
>has convinced it that it should
>get the cpu, like when a higher-priority task which has been waiting
>on input gets its data.
Not quite. Most Unixes only preempt when the lower priority task is
in or going to return to user mode. If task A is in the kernel, and
task B, which has higher priority, wakes up because of an interrupt,
task B does not run until A sleeps or gets ready to leave the kernel.
Perhaps the first poster was asking if anyone was considering doing a
kernel that would preempt tasks even if they are in kernel mode?
--Tim Smith
Duncan P Simpson
SMP doe the same reason: to allow pre-empotion in kernel mode you need
mutex stuff in the kernel. Linux (and many other kernels) rely on not
being pre-empted in kernel code to make sure changes that have to be
atomic are atomic; on multi-processor systems or systems where kernel
code can be interupted you need mutex to prevent race conditions
leaving the kernel in an incosistent state.
--
Duncan (-:
"software industry, the: unique industry where the supply of substandard
goods is legal and you can charge extra for fixing the problems"
H. Peter Anvin
By author: t...@u.washington.edu (Tim Smith)
In newsgroup: comp.os.linux.misc
>
> Not quite. Most Unixes only preempt when the lower priority task is
> in or going to return to user mode. If task A is in the kernel, and
> task B, which has higher priority, wakes up because of an interrupt,
> task B does not run until A sleeps or gets ready to leave the kernel.
>
> Perhaps the first poster was asking if anyone was considering doing a
> kernel that would preempt tasks even if they are in kernel mode?
>
This is true, even for Linux. Processes in kernel mode are
multitasked cooperatively. However, it isn't the lossage it may sound
like, as the kernel will reschedule any process as soon as it attempts
to do I/O which is not immediately available, and there is
(theoretically) no way a process could make the kernel hog the CPU for
it. Bill's toy doesn't do either. In user mode, of course, Linux is
completely preemptive.
Allowing preemption of kernel mode processes would be of benefit in
real-time applications, as a process could get scheduled with a
ridiculously high priority (SCHED_FIFO?) which would indicate that one
that process is runnable, it demands immediate attention.
/hpa
--
PGP public key available - finger h...@yggdrasil.com
"The earth is but one country, and mankind its citizens." -- Baha'u'llah
Joel Katz
>D. Duke Smith <lrna...@ix.netcom.com> wrote:
>>Preemptive in the Unix MT world simply means the OS, which can
>>always "preempt" a task (even in Windows), preempts the currently
>>running task on behalf of another task which
>>has convinced it that it should
>>get the cpu, like when a higher-priority task which has been waiting
>>on input gets its data.
>Not quite. Most Unixes only preempt when the lower priority task is
>in or going to return to user mode. If task A is in the kernel, and
>task B, which has higher priority, wakes up because of an interrupt,
>task B does not run until A sleeps or gets ready to leave the kernel.
>Perhaps the first poster was asking if anyone was considering doing a
>kernel that would preempt tasks even if they are in kernel mode?
Can't be. Tasks in kernel state always have a higher priority
that tasks in user states. ("Higher" being used in its usual sense, not
numerically higher)
--
Joel Katz -- Stim...@Panix.COM Finger for PGP 2.6 Key
Information on Objectivism, Atheism, the 8031/8051 Microcontrollers, Linux
and more is available at "http:www.panix.com/~stimpson/".
ian_...@acm.org
>>In user mode, of course, Linux is
>>completely preemptive.
>>
This is not exactly true. Linux adjusts the priority of tasks that
have been running for some time to give lower priority tasks a
chance to run occasionally ahead of high-priority tasks.
In my application, I would like strict priority execution order.
For example: I have two tasks, one parsing input from a broadcast
network and one spooling output to a printer. The parser has higher
priority because I want it to run ahead of the print spooler
whenever it has something to do. I WANT the print spooling to
pause if the network is very busy because I cannot afford to miss
any incoming data.
Does anyone have a library of different schedulers for different
operating environments?
Ian.
H. Peter Anvin
By author: ian_...@ACM.ORG
In newsgroup: comp.os.linux.misc
>
> >>In user mode, of course, Linux is
> >>completely preemptive.
>
> This is not exactly true. Linux adjusts the priority of tasks that
> have been running for some time to give lower priority tasks a
> chance to run occasionally ahead of high-priority tasks.
>
The scheduling policy has nothing to do with the issue of preemptive
or nonpreemptiveness. Although I do agree that control over
scheduling policy in Linux (POSIX.4?) would be good.
Svante Gellerstam
says...
>
>In article <3rseek$s...@shell1.best.com>, pe...@best.com (Roger Reynolds)
>
>>Here's a question that somebody must surely have thought of by now..
>>
>>I was wondering if anybody has come up with a kernel hack that would
>>allow for "premptive multi-tasking".
>
>
>>It seems to me that with a few
>>well placed hacks to the scheduler, one should be able to guarantee
>>that the highest priority task that is runnable is always the one that
>>is running.
>
starvation,
>just for one thing.
>
>pjm.
As many Amiga users will testify, preemtive multitasking is not so bad
_if the apps are written for it_. Preemtive & busy wait is a no-no. But
correctly designed it works very well. The new POSIX scheduling code
might also be worth taking a look at. It will provide this functionality
to the linux kernel.
/svante
Bouwmeester
Peter Moulder <rei...@netspace.net.au> wrote:
>In article <3rseek$s...@shell1.best.com>, pe...@best.com (Roger Reynolds) wrote:
>
>>Here's a question that somebody must surely have thought of by now..
>>
>>I was wondering if anybody has come up with a kernel hack that would
>>allow for "premptive multi-tasking".
>
>Linux always has done pre-emptive multitasking.
Question: since when is the Linux kernel pre-emptive? Traditional Unix
kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
to do so (by calling schedule()).
It should be noted that it is quite difficult to make the kernel pre-emptive:
lots and lots of data structures have to be protected by locks. Currently,
the LUMP-project and the Viper-project are involved in making the Linux
kernel pre-emptible and suitable for multiprocessor applications. Alan Cox
is working on the boot code, whereas I (together with someone else) am
working on kernel threads (already implemented) and kernel pre-emption.
>>It seems to me that with a few
>>well placed hacks to the scheduler, one should be able to guarantee
>>that the highest priority task that is runnable is always the one that
>>is running.
>
>I wouldn't want such a scheduling algorithm. It would lead to starvation,
>just for one thing.
Depends: in real-time systems such behaviour *IS* desirable. However, most
tasks in Linux (would) run in timesharing mode anyway. Furtermore,
starvation is usually caused by the problem of priority inversion and
hidden scheduling problems: tasks with low priority have allocated resources
are pre-empted by tasks with middle priority. They both block tasks with
high priority also requesting for the same resources now allocated by the
tasks with low priority.
A carefull design is required to avoid such problems and usually requires
the use of priority inheritance protocols or, even better, priority ceiling
protocols (these also avoid deadlocks).
Regards,
Leon.
Yonik Seeley
>>>
>>>I was wondering if anybody has come up with a kernel hack that would
>>>allow for "premptive multi-tasking".
>>
>>Linux always has done pre-emptive multitasking.
>
>Question: since when is the Linux kernel pre-emptive? Traditional Unix
>kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
>to do so (by calling schedule()).
We should really be careful not to mislead new/potential linuxers
that may not have a strong OS background. The most common usage of
"preemptive multitasking" is taken to mean that there is that more
than one process (user process) may run at a time, and that these
processes do not have to voluntarily give up control because they
get preempted.
Saying that Linux is "not pre-emptive" may lead some people to
believe that user processes are cooperatively multi-tasked, which is
false of course.
- Yonik
L. Donovan Heinz
>>>I was wondering if anybody has come up with a kernel hack that would
>>>allow for "premptive multi-tasking".
>>
>>Linux always has done pre-emptive multitasking.
>>
>>>well placed hacks to the scheduler, one should be able to guarantee
>>>that the highest priority task that is runnable is always the one
that
>>>is running.
>>
>>I wouldn't want such a scheduling algorithm. It would lead to
>starvation,
>>just for one thing.
>>
>
>As many Amiga users will testify, preemtive multitasking is not so bad
>_if the apps are written for it_. Preemtive & busy wait is a no-no.
But
>correctly designed it works very well. The new POSIX scheduling code
>might also be worth taking a look at. It will provide this
functionality
>to the linux kernel.
>
>/svante
>
Different scheduling algorithms are good for different purposes. I
could see a sysgen-time option of scheduler algorithms. What do you
think?
--
*****************************************************************************
The U. S. Constitution is not a perfect document; it has its flaws....
But it's a lot better than what we have now.
ldh...@ix.netcom.com
*****************************************************************************
Erik Corry
: In article <reiter-1906...@203.12.52.22>, rei...@netspace.net.au
: says...
: >
: >In article <3rseek$s...@shell1.best.com>, pe...@best.com (Roger Reynolds)
: wrote:
: >
: >>Here's a question that somebody must surely have thought of by now..
: >>
: >>I was wondering if anybody has come up with a kernel hack that would
: >>allow for "premptive multi-tasking".
: >
: >Linux always has done pre-emptive multitasking.
: >
: >>It seems to me that with a few
: >>well placed hacks to the scheduler, one should be able to guarantee
: >>that the highest priority task that is runnable is always the one that
: >>is running.
: >
: >I wouldn't want such a scheduling algorithm. It would lead to
: starvation,
: >just for one thing.
: >
: >pjm.
: As many Amiga users will testify, preemtive multitasking is not so bad
: _if the apps are written for it_. Preemtive & busy wait is a no-no. But
: correctly designed it works very well. The new POSIX scheduling code
: might also be worth taking a look at. It will provide this functionality
: to the linux kernel.
This sort of thing is catered for in the Posix.4 standard (the real
time extensions for Unix-like OSs). You don't want this to apply to
normal processes, as it's too risky, leads to starvation etc. For
example if a process with a higher priority than the X server goes
into an endless loop, you will have difficulty sending a ^C to it.
With the Posix.4 standard there are 'real-time' process priorities
above the usual ones for processes that really need it. Only apps that
are written for it should be run at a real-time process priority.
See the excellent O'Reilly book by Bill Gallmeister on the subject.
I seem to remember that someone uploaded some patches for real time
process priorities, but I can't find a reference to this anymore. Also
hal...@iitb.fhg.de (Ralf Haller) and k...@iitb.fhg.de (Harald Kirsch)
recently uploaded 'mlock', a patch for Posix.4 memory locking to
sunsite. This would also be a prerequisite for what you want since there
is no point having the highest priority real-time process waiting for
virtual memory to be paged in from disk.
Markus Kuhn seems to be interested in Posix.4 for Linux. His email address
is msk...@cip.informatik.uni-erlangen.de.
Posix.4 is now called IEEE 1003.1b-1993.
--
Erik Corry, Freiburg, Germany, +49 761 406637 er...@kroete2.freinet.de
Christopher B. Browne
Michael van Elst <mle...@comma.rhein.de> wrote:
>Bach p.258:
>
>"The scheduler algorithms described above were designed for use in
>a time-sharing environment and are inappropriate in a real-time
>environment, because they cannot guarantee that the kernel can schedule
>a particular process within a fixed limit. Another impediment to the
>support of real-time processing is that the kernel is nonpreemptive;
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>the kernel cannot schedule a real-time process in user mode if it
>is currently executing another process in kernel mode, unless
>major changes are made. Currently, system programmers must insert
>real-time processes into the kernel to achieve real-time response..."
I suppose that this is probably the sort of point at which it
may make sense to start thinking about having more than two
rings of control on the system (e.g. - "root"/kernel and "user"),
and heading to finer levels of granularity.
It's quite common for there to be processes that provide services
for all users. lpd would be a good example of this. Because it
has to service everyone, it generally has to have some parts
executing as root. Which has the highly unfortunate problem that
any bugs in lpd can corrupt the rest of the kernel.
- I had this very problem under OSF/1 not too long ago when I
attempted to upgrade lpd. It started spawning lpd processes
like *crazy* (hundreds of 'em) and was dragging down the system
until I killed it off.
- A fax system (again under OSF/1) has to run as root in order
to service all users on the system. (In theory that's optional,
but the software needs to be root anyways.)
Supposing part of it runs away and starts dumping into a file
on the root partition, (happened the other week :-( ) it can quite
happily fill / completely. Breaking anything else that might need
to access the root partition.
The common theme is that these systems have a need for system-wide
permissions, but could use some limitations as well.
Having 3 rings would be a useful notion in this case:
Ring 0: Kernel Services
Ring 1: System-wide services
Ring 2: User-level services
No doubt there can be an abstraction made somewhere that allows
us to run most of a "ring 1" system at user level, with occasional
forays into the "kernel level." But it would be rather nice to
actually have the three levels of privilege.
The three levels would simplify the issues described in the
previous posts; as the kernel services become a smaller set
of software, it becomes easier to apply things such as
preemptive scheduling. Or at least it appears so to me.
Linux meets Multics?
--
Christopher Browne - Email:<cbb...@io.org>, WWW:<http://www.io.org/~cbbrown/>
"I believe OS/2 is destined to be the most important operating system,
and possibly program, of all time." -- Bill Gates
Dave Barr
Ah, I just love the net. Where people will use any excuse to start
an argument and show off their knowledge, including changing
the subject.
We're of course talking about two different things here.
The statement "Linux always has done pre-emptive multitasking" is
entirely true.
>Traditional Unix
>kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
>to do so (by calling schedule()).
Well, that statment is misleading. The kernel schedules a new
task only when it calls schedule(). But we're not talking about
how the kernel schedules itself, we're talking about how the kernel
schedules tasks.
Yes, several projects including those interested in SMP are involved
in making a pre-emptible _kernel_. However Linux (and all other
non-real-time Unixes) does pre-emptive multitasking.
--Dave
Michael van Elst
>}Question: since when is the Linux kernel pre-emptive? Traditional Unix
>}kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
>}to do so (by calling schedule()).
>You are probably confusing real-time scheduling....
Nope. A preemptive kernel is important for real-time scheduling but
the implications go much farther.
>UNIX is and always has been pre-emptive.
As soon as a process runs in the kernel it cannot be preempted.
Preemption just takes place in user mode.
>Hopefully I'm not confusing anyone with facts here :-)
Bach p.258:
"The scheduler algorithms described above were designed for use in
a time-sharing environment and are inappropriate in a real-time
environment, because they cannot guarantee that the kernel can schedule
a particular process within a fixed limit. Another impediment to the
support of real-time processing is that the kernel is nonpreemptive;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
the kernel cannot schedule a real-time process in user mode if it
is currently executing another process in kernel mode, unless
major changes are made. Currently, system programmers must insert
real-time processes into the kernel to achieve real-time response..."
Regards,
--
Michael van Elst
Internet: mle...@mpifr-bonn.mpg.de mle...@serpens.rhein.de
"A potential Snark may lurk in every tree."
Stuart Lynne
Bouwmeester <bouw...@dutian.twi.tudelft.nl> wrote:
}In article <reiter-1906...@203.12.52.22>,
}Peter Moulder <rei...@netspace.net.au> wrote:
}>
}>>Here's a question that somebody must surely have thought of by now..
}>>
}>>I was wondering if anybody has come up with a kernel hack that would
}>>allow for "premptive multi-tasking".
}>
}
}kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
}to do so (by calling schedule()).
You are probably confusing real-time scheduling....
UNIX is and always has been pre-emptive.
To quote from The Design of the UNIX Operating System by Maurice J. Bach,
the first sentence of the first paragraph of Chapter 8, Processing
Scheduling and Time...
On a time sharing system, the kernel allocates the CUP to a process
for a period of time called a time slice or time quantum, preempts
the process and schedules another when the time slice expires, and
reschedules the process to continue execution at a later time.
and further on, section 8.1 Process Scheduling...
The scheduler on the UNIX system belongs to the general class of
operating system schedulers know as round robin with multilevel
feedback, meaning that the kernel allocates the CPU to a process for
a time quantum, preempts a process that exceeds its time quantum and
feeds it back into one of several priority queues.
Hopefully I'm not confusing anyone with facts here :-)
--
Stuart Lynne <s...@wimsey.com> 604-933-1000 <http://www.wimsey.com>
PGP Fingerprint: 28 E2 A0 15 99 62 9A 00 88 EC A3 EE 2D 1C 15 68
Emmanuel Charpentier
: kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
: to do so (by calling schedule()).
Ooooh, poor boy ! You've just flunked Operating Systems 101 ... Let's get back
to basics : "See Spot. See Spot run. Run, Spot, Run !" ...
[What I mean is that you *really* should learn how to read. ]
You're confusing preemptive systems and realtime systems, which are not only
quite different but also incompatible (at least with one processor). Please
go do your homework. Thanks.
--
Emmanuel Charpentier
char...@bacbuc.frmug.fr.net
Brian Hurt
>Question: since when is the Linux kernel pre-emptive? Traditional Unix
>kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
>to do so (by calling schedule()).
Oy vey.
1) Go read Tannebaum (if you haven't already). Pre-emptive multitasking is
defined to mean "a running process may be pre-empted at any time to run
another process". In otherwords- a process doesn't when or if it will be
pre-empted- nor should it care. The process's entire state (memory,
registers, code, open files, etc.) is saved, and restarted later (after
pre-empting another process). A process can, on a pre-emptive multitasking
OS, voluntarily give up the CPU ("block") by calling schedule() (or an
equivelent). Systems which only task switch when the running processes
calls schedule() are called "cooperative multitasking".
The Mac and MS-Windows are cooperative multitasking, Linux, and Unix in
general, are (and always have been) preemptive multitasking.
>It should be noted that it is quite difficult to make the kernel pre-emptive:
>lots and lots of data structures have to be protected by locks. Currently,
>the LUMP-project and the Viper-project are involved in making the Linux
>kernel pre-emptible and suitable for multiprocessor applications. Alan Cox
>is working on the boot code, whereas I (together with someone else) am
>working on kernel threads (already implemented) and kernel pre-emption.
I think you are confusing multi-tasking with multi-processing, in which
there are several different CPUs cooperating within one computer.
Linux is not (yet) multi-processing capable, in this you are correct.
The original idea with multi-_tasking_ was to make one CPU look like
several much slower CPUs, each of which is running a single process.
>Depends: in real-time systems such behaviour *IS* desirable. However, most
>tasks in Linux (would) run in timesharing mode anyway. Furtermore,
>starvation is usually caused by the problem of priority inversion and
>hidden scheduling problems: tasks with low priority have allocated resources
>are pre-empted by tasks with middle priority. They both block tasks with
>high priority also requesting for the same resources now allocated by the
>tasks with low priority.
This is one of the (few) advatages coopertive multitasking has over
pre-emptive multitasking. In a pre-emptive system, you are never sure
how long a given program or sub-program is going to take to run, as
you are never sure when the CPU might get stolen out from under you
to run some other process. So long as you avoid calling schedule(),
in a cooperative MT OS, you're safe.
I'm not sure how much "need" there is for Linux to be real-time. Adding
real-time causes a lot of philosophical and techinical problems to raise
thier ugly heads (some of which you have mentioned).
Brian Hurt.
Albert Cahalan
B> ... one of the (few) advatages coopertive multitasking has over
B> pre-emptive multitasking. In a pre-emptive system, you are never
B> sure how long a given program or sub-program is going to take to
B> run, as you are never sure when the CPU might get stolen out from
B> under you to run some other process. So long as you avoid calling
B> schedule(), in a cooperative MT OS, you're safe.
If you need to have a block of time interrupted only by interrupts,
can you get that block of time by calling schedule() just before the
critical code? I think it would work if time slices have uniform
size: after schedule() returns, a time slice has _just started_, right?
--
Albert Cahalan
alb...@ccs.neu.edu
Erik Corry
: bouw...@dutian.twi.tudelft.nl (Bouwmeester) writes:
: >Question: since when is the Linux kernel pre-emptive? Traditional Unix
: >kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
: >to do so (by calling schedule()).
: Oy vey.
: 1) Go read Tannebaum (if you haven't already). Pre-emptive multitasking is
Tanenbaum
: defined to mean "a running process may be pre-empted at any time to run
: another process". In otherwords- a process doesn't when or if it will be
But in Unix a process can be in user mode or in kernel mode at any one
time. In kernel mode the process is not preempted in a traditional Unix
kernel like Linux.
: pre-empted- nor should it care. The process's entire state (memory,
: registers, code, open files, etc.) is saved, and restarted later (after
: pre-empting another process). A process can, on a pre-emptive multitasking
: OS, voluntarily give up the CPU ("block") by calling schedule() (or an
: equivelent). Systems which only task switch when the running processes
: calls schedule() are called "cooperative multitasking".
Perhaps you could say that Linux is preempting in user mode, but not in
kernel mode.
: The Mac and MS-Windows are cooperative multitasking, Linux, and Unix in
: general, are (and always have been) preemptive multitasking.
: >It should be noted that it is quite difficult to make the kernel pre-emptive:
: >lots and lots of data structures have to be protected by locks. Currently,
: >the LUMP-project and the Viper-project are involved in making the Linux
: >kernel pre-emptible and suitable for multiprocessor applications. Alan Cox
: >is working on the boot code, whereas I (together with someone else) am
: >working on kernel threads (already implemented) and kernel pre-emption.
:
: I think you are confusing multi-tasking with multi-processing, in which
: there are several different CPUs cooperating within one computer.
: Linux is not (yet) multi-processing capable, in this you are correct.
: The original idea with multi-_tasking_ was to make one CPU look like
: several much slower CPUs, each of which is running a single process.
Since he is actually working on the project, you are pretty arrogant
to presume he has merely forgotten to read Tanenbaum.
You are confused. The requirements to make a kernel multi-processor
capable are mostly the same as those required to make it fully
preemptable. This is because in both cases you cannot assume that only
one process is in kernel mode at the same time.
: >Depends: in real-time systems such behaviour *IS* desirable. However, most
: >tasks in Linux (would) run in timesharing mode anyway. Furtermore,
: >starvation is usually caused by the problem of priority inversion and
: >hidden scheduling problems: tasks with low priority have allocated resources
: >are pre-empted by tasks with middle priority. They both block tasks with
: >high priority also requesting for the same resources now allocated by the
: >tasks with low priority.
:
: This is one of the (few) advatages coopertive multitasking has over
: pre-emptive multitasking. In a pre-emptive system, you are never sure
: how long a given program or sub-program is going to take to run, as
: you are never sure when the CPU might get stolen out from under you
: to run some other process. So long as you avoid calling schedule(),
: in a cooperative MT OS, you're safe.
A fully preemptable OS with real-time process priorities acheives a similar
effect.
: I'm not sure how much "need" there is for Linux to be real-time. Adding
: real-time causes a lot of philosophical and techinical problems to raise
: thier ugly heads (some of which you have mentioned).
A lot of the features in Posix.4 look very useful, even to a general-
purpose Unix. As you note, there are advantages to being able to prevent
interruptions to a process.
Hamish Marson
: : Question: since when is the Linux kernel pre-emptive? Traditional Unix
: : kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
: : to do so (by calling schedule()).
: Ooooh, poor boy ! You've just flunked Operating Systems 101 ... Let's get back
: to basics : "See Spot. See Spot run. Run, Spot, Run !" ...
: [What I mean is that you *really* should learn how to read. ]
: You're confusing preemptive systems and realtime systems, which are not only
: quite different but also incompatible (at least with one processor). Please
: go do your homework. Thanks.
Perhaps you should learn to read... What the quote says is perfectly true.
The Linux kernel is not pre-emptive. I read that as saying once a process
is executing in the kernel, it can only be re-scheduled when it wants to
(ie when the kernel says i'm going to sleep now, whether for IO or some
other reason).
Also, I take exception to the statement about pre-emptive and real-time
being incompatible. In a multitasking operating system (Pick one), if
the system is not pre-empting then it CAN'T be real-time. Otherwise a
process could get the CPU and hog it, thus denying your real-time process
of its CPU, and hence not being real-time any more. For an example of
a pre-emptive real-time OS look at QNX. I don't know of any OS's that
are non-preemptive and claiing to be real-time (And multitasking, I can
concieve that a system might be single tasking, and non-premptive, real-time,
but again I don't know of any that make this claim).
--
======================================================================
| Hamish Marson |
| Systems Programmer & News Manager ne...@news.waikato.ac.nz|
| Computer Services | INTERNET h.ma...@waikato.ac.nz |
| University of Waikato | PHONE +64 7 8562889 xt 8181 |
| New Zealand | FAX +64 7 8384066 |
===========Disclaimer :- Remember. You heard it here first.===========
Brian Hurt
>If you need to have a block of time interrupted only by interrupts,
>can you get that block of time by calling schedule() just before the
>critical code? I think it would work if time slices have uniform
>size: after schedule() returns, a time slice has _just started_, right?
Not nessecarily- first off, someone else might have called schedule(), and
the OS might have decided to slip you into the time remaining in the block
(Though I would assume a nice OS would also let you have the next block as
well- what does linux do?). Second- you never know how much time the
"other interrupts" are going to take. I seem to remember some posting
that said that data transfer to an IDE drive (not using DMA) took like
90% of the CPU time. If you block happens to get scheduled during some
heavy accessing of an IDE drve, 90% of your time just vanished. This is
another little problem with realtime processes (do with simply disallow
accessing block devices while they are running?)
Brian Hurt
Michael van Elst
>bouw...@dutian.twi.tudelft.nl (Bouwmeester) writes:
>>Question: since when is the Linux kernel pre-emptive? Traditional Unix
>>kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
>>to do so (by calling schedule()).
>1) Go read Tannebaum (if you haven't already). Pre-emptive multitasking is
>defined to mean "a running process may be pre-empted at any time to run
>another process".
>The Mac and MS-Windows are cooperative multitasking, Linux, and Unix in
>general, are (and always have been) preemptive multitasking.
But not all the time. A process in kernel mode is _not_ preempted.
>The original idea with multi-_tasking_ was to make one CPU look like
>several much slower CPUs, each of which is running a single process.
Indeed. However, as soon as you start several communicating tasks
you need a method to arbitrate access to shared data. The kernel data
is inherently shared by all processes. The arbitration method used is
to forbid preemption of tasks in kernel mode and to voluntarily give
up the CPU (with schedule() or similar) only when the kernel data is in
a consistent state.
A premptive _kernel_ would need locking of data structures.
>to run some other process. So long as you avoid calling schedule(),
>in a cooperative MT OS, you're safe.
That's what the Linux kernel uses to be safe. The kernel is fortunately
well-behaved and does not hog the CPU for a long time.
>I'm not sure how much "need" there is for Linux to be real-time.
Well, it helps for tasks that need real-time :) But a preemptive
kernel is good for non-real-time processes too.
Brian Hurt
>But not all the time. A process in kernel mode is _not_ preempted.
Granted. Is there much of a difference between making the kernel pre-
emptable (as is needed for realtime programming) and making it
reinterent (for multi-processing)?
>Indeed. However, as soon as you start several communicating tasks
>you need a method to arbitrate access to shared data. The kernel data
>is inherently shared by all processes. The arbitration method used is
>to forbid preemption of tasks in kernel mode and to voluntarily give
>up the CPU (with schedule() or similar) only when the kernel data is in
>a consistent state.
In a monolithic kernel on a uniprocessor machine, you simply never
interrupt the kernel- in this regards, the kernel is "special".
>A premptive _kernel_ would need locking of data structures.
So would a reentrant one.
>>I'm not sure how much "need" there is for Linux to be real-time.
>Well, it helps for tasks that need real-time :) But a preemptive
>kernel is good for non-real-time processes too.
I see a need for reentrant kernels for symetric multi-processors. What
other uses are there for full realtime capability, other than for
realtime processes?
Brian Hurt
Ken Bass
Emmanuel Charpentier <char...@bacbuc.frmug.fr.net> wrote:
>[What I mean is that you *really* should learn how to read. ]
>
>You're confusing preemptive systems and realtime systems, which are not only
>quite different but also incompatible (at least with one processor). Please
>go do your homework. Thanks.
Actually I think the confusion here is between pre-emption in the
user space versus the kernal space.
John F. Reeves
< all previous arguments deleted>
Hey Guys,
I've never seen an argument go on so long without a single solid
answer to the original question! I understand operating systems,
more or less, as far as I understand, Linux and Unix are both
pre-emptive. Meaning user processes have a fixed time quantum and,
they either finish running in their time Q and give up the CPU,
use up their time Q and are preempted by the kernel, or voluntarily
give up the CPU before finishing their time Q. Is this correct?
If not, then what is the answer to this whole argument.
Also, I'm kind of foggy on how you guys have been defining user
process in kernel mode. Does this mean a user process has made
a system call to the kernel? As far as I know, a user process
can still be preempted while doing this because it's state is
saved. Even though it's made a system call, it's still a user
process and the kernel can still preempt it.
Now I'm not saying this IS what happens, this is just a question
for you Kernel Gurus out there. I hope that I don't get two
opposite answers to this that are both convinced they are right
like in most of the previous replies to this posting.
Just my two cents.
Frank
Lex Spoon
[ section of message actually having to do with preemption deleted ]
: I suppose that this is probably the sort of point at which it
: may make sense to start thinking about having more than two
: rings of control on the system (e.g. - "root"/kernel and "user"),
: and heading to finer levels of granularity.
: It's quite common for there to be processes that provide services
: for all users. lpd would be a good example of this. Because it
: has to service everyone, it generally has to have some parts
: executing as root. Which has the highly unfortunate problem that
: any bugs in lpd can corrupt the rest of the kernel.
: - I had this very problem under OSF/1 not too long ago when I
: attempted to upgrade lpd. It started spawning lpd processes
: like *crazy* (hundreds of 'em) and was dragging down the system
: until I killed it off.
: - A fax system (again under OSF/1) has to run as root in order
: to service all users on the system. (In theory that's optional,
: but the software needs to be root anyways.)
For examples like these, the support is already here. Make lpd
setgid to "lp", and then make the lpd files writable by
group lp. Then if lpd screws up, you only lose the
print spooling system....
Lex
Cees de Groot
Christopher B. Browne <cbb...@io.org> wrote:
>The common theme is that these systems have a need for system-wide
>permissions, but could use some limitations as well.
>
>Having 3 rings would be a useful notion in this case:
>Ring 0: Kernel Services
>Ring 1: System-wide services
>Ring 2: User-level services
>
kernel, especially all kinds of ideas people are having (a relational
file system, a standard set of graphics drivers, ...). Currently, the
kernel is blowing up without upper limits (0.97 -> 1.3 was an increase
from 200k to 2.2Mb), I think we should strive to make it smaller. Having
an intermediate level could give us the breathing space we need, and I
think it wouldn't be _that_ hard to implement it (AFAIK the whole thing
is carefully explained in the 80386 books).
For people who don't know it, VMS implements four rings (Kernel, Executive,
Supervisor and User; the latter two are user-level and needed to protect
DCL from running images); you can jump to inner rings with CMKRNL and
CMEXEC system calls (they take a funcpointer as argument), you pop-up
back with a return. I never really analyzed it, but I guess that large
parts of networking, system-wide services, and maybe even parts of
device drivers are working on this intermediate level. It probably is
one of the reasons the system is so stable...
BTW: I guess the AXP has multiple rings, how'bout the other processors
everybody is porting to ?
--
Cees de Groot, OpenLink Software <c...@openlink.co.uk>
PGP26ui: 14 C4 B3 B6 97 7F CA 4F FC 7D E8 B1 AB 25 03 19 [Key on servers]
<A HREF=http://www.decus.de/people/de_groot/bio.html>Click</A>
-- Programmir c'est mourir un peu
Andreas Fluegge
It's very interesting to read your comments about multitasking and
multithreading. Because I'm new here there are some questions:
1) Is there a faq about your previous discusions?
2) Who is working on the different projects and what is their state?
3) Would the development of such a kernel lead to new Linux (a complete
different 'incompatible' version) or is it possible to implement it as
a kernel option?
Andreas.
--------------------------------------------------------------------------
Andreas Fluegge AFLU...@TERRA-I.RHEIN-RUHR.DE
Gelsenkirchen / Germany
--------------------------------------------------------------------------
## CrossPoint v3.02 ##
Michael van Elst
>You're confusing preemptive systems and realtime systems
Preemptive scheduling and real-time scheduling are independent.
Michael van Elst
>being incompatible. In a multitasking operating system (Pick one), if
>the system is not pre-empting then it CAN'T be real-time. Otherwise a
>process could get the CPU and hog it, thus denying your real-time process
>of its CPU, and hence not being real-time any more.
That depends on what programs are allowed. A system can still be real-time
if you can enforce a maximum run-time of each process before it goes back
to sleep or is removed (e.g., the compiler could do this)
Some real-time systems prefer this approach. Of course it's not adequate
for a workstation.
Michael van Elst
>mle...@comma.rhein.de (Michael van Elst) writes:
>>But not all the time. A process in kernel mode is _not_ preempted.
>Granted. Is there much of a difference between making the kernel pre-
>emptable (as is needed for realtime programming) and making it
>reinterent (for multi-processing)?
Well, a preemtable kernel can easily be transformed into a multi-processor
kernel (assuming "multi-processor" means SMP or something close). But there
are other approaches for multi-processors that go beyond a preemptable
kernel. But since a preemptable kernel is a good idea it is usually
implemented with anything else to support multi-processors.
>In a monolithic kernel on a uniprocessor machine, you simply never
>interrupt the kernel- in this regards, the kernel is "special".
No. You could preempt any task and use semaphores to protect the
data structures. This works even with a monolithic kernel and on
uniprocessor machines.
>>A premptive _kernel_ would need locking of data structures.
>So would a reentrant one.
I think reentrancy is necessary for a preemptive kernel.
>>Well, it helps for tasks that need real-time :) But a preemptive
>>kernel is good for non-real-time processes too.
>I see a need for reentrant kernels for symetric multi-processors. What
>other uses are there for full realtime capability, other than for
>realtime processes?
Well, there is real-time and real-time :) Think about a network server
that has to answer requests. Each request needs a system call (or two).
The time necessary for the system call depends on the time another
process spends in the kernel. This could be long if you think about
buffer cache operations or PIO drivers or a console driver that scrolls
a framebuffer. A preemptable kernel (with smart data structures that
try to avoid locking operations) could handle the network service much
faster.
Of course you can add lots of buffering to avoid this kernel bottleneck.
But that just moves the latencies to a different layer.
Mr A. Aloto
>< all previous arguments deleted>
>
>Hey Guys,
>
>I've never seen an argument go on so long without a single solid
>answer to the original question! I understand operating systems,
>more or less, as far as I understand, Linux and Unix are both
>pre-emptive. Meaning user processes have a fixed time quantum and,
>they either finish running in their time Q and give up the CPU,
>use up their time Q and are preempted by the kernel, or voluntarily
>give up the CPU before finishing their time Q. Is this correct?
>If not, then what is the answer to this whole argument.
>
Yes it is correct.
And please can we end this thread here.
I suggest in future that those who do not know about a subject,
do not start spooling confusing threads about a subject on which
they have little or no understanding.
"pre-emptive multitasking" is by definition exactly what unix is
all about, and thus LINUX.
allister
Mikolaj Habryn
>Christopher B. Browne (cbb...@io.org) wrote:
[snip]
>: - A fax system (again under OSF/1) has to run as root in order
>: to service all users on the system. (In theory that's optional,
>: but the software needs to be root anyways.)
>For examples like these, the support is already here. Make lpd
>setgid to "lp", and then make the lpd files writable by
>group lp. Then if lpd screws up, you only lose the
>print spooling system....
Yeah - i did this on my linux box. I ripped out all the suid root
stuff, stripped down my group and passwd files as far as possible, then
reinstalled everything that needed privs from scratch. It is a pain.
While you can do it, it generally requires manoeuvres such as adding
specific uids into the requisite groups in /etc/group and tweaking
the source to call initgroups().
It's not really worth the effort. With a fully dynamic hierarchical
security system, it would be a breeze. Then again, writing it into the
kernel probably wouldn't be. Time to find a middle ground :) SUID/SGID
just isn't good enough any more.
* * Mikolaj J. Habryn
dic...@tartarus.uwa.edu.au
* "I'm just another sniper on the information super-highway."
PGP Public key available by finger
* #include <standard-disclaimer.h>
Emmanuel Charpentier
: Emmanuel Charpentier (char...@bacbuc.frmug.fr.net) wrote:
: : : Question: since when is the Linux kernel pre-emptive? Traditional Unix
: : : kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
: : : to do so (by calling schedule()).
: : Ooooh, poor boy ! You've just flunked Operating Systems 101 ... Let's get back
: : to basics : "See Spot. See Spot run. Run, Spot, Run !" ...
: : [What I mean is that you *really* should learn how to read. ]
: : You're confusing preemptive systems and realtime systems, which are not only
: : quite different but also incompatible (at least with one processor). Please
: : go do your homework. Thanks.
: Perhaps you should learn to read... What the quote says is perfectly true.
: The Linux kernel is not pre-emptive. I read that as saying once a process
: is executing in the kernel, it can only be re-scheduled when it wants to
: (ie when the kernel says i'm going to sleep now, whether for IO or some
: other reason).
Dear sir,
As any user of any human language, you are free to redefine any word of the
said language to mean whatever you want to mean. For example, you can redefine
"white" to mean what other people call black and vice versa, as long as you
remain internally consistent.
However, in the process, you'll lose the ability to use these words as a
communication tools with others users of the aforementioned language.
When you redefine "preemption" as you did, you are trying to get back to an
etymological meaning of preemption. It just happens that this meaning is not
the common-use meaning. See any good basic textbook on operating systems.
Furthermore, to get more specifically at what you say about a process running
"in the kernel" (in kernel mode ?), it turns out that it is not the case :
how do you think that interrupts are managed ? Hmmm ?
: Also, I take exception to the statement about pre-emptive and real-time
: being incompatible. In a multitasking operating system (Pick one), if
: the system is not pre-empting then it CAN'T be real-time. Otherwise a
: process could get the CPU and hog it, thus denying your real-time process
: of its CPU, and hence not being real-time any more. For an example of
: a pre-emptive real-time OS look at QNX. I don't know of any OS's that
: are non-preemptive and claiing to be real-time (And multitasking, I can
: concieve that a system might be single tasking, and non-premptive, real-time,
: but again I don't know of any that make this claim).
Again a problem of definitions : a realtime OS is usually defined as one that
allows to put explicit, finite upper bounds to the time necessary to have
a process to react to an oputer event. It can be formally shown that, in order
to comply fully with this definition, you need either a fixed hardcoded
scheduling algorithm with at most a severely limited set of priority
adjustments, or a multiprocessor hardware, with one processor and a process
per information input *plus* processors and process devoted to IPC. Looks
more like electrical engineering than "usual" informatics.
--
Emmanuel Charpentier
char...@bacbuc.frmug.fr.net
Louis-D. Dubeau
CdG> In article <3sil1j$6...@ionews.io.org>, Christopher B. Browne
CdG> <cbb...@io.org> wrote:
>> The common theme is that these systems have a need for
>> system-wide permissions, but could use some limitations as
>> well.
>>
>> Having 3 rings would be a useful notion in this case: Ring 0:
>> Kernel Services Ring 1: System-wide services Ring 2: User-level
>> services
>>
CdG> I agree 100%. An intermediate ring could keep lots of stuff
CdG> out of the kernel, especially all kinds of ideas people are
CdG> having (a relational file system, a standard set of graphics
CdG> drivers, ...). Currently, the kernel is blowing up without
CdG> upper limits (0.97 -> 1.3 was an increase from 200k to
CdG> 2.2Mb), I think we should strive to make it smaller. Having
CdG> an intermediate level could give us the breathing space we
CdG> need, and I think it wouldn't be _that_ hard to implement it
CdG> (AFAIK the whole thing is carefully explained in the 80386
CdG> books).
For this purpose rings are unnecessary. A microkernel/multiserver
architecture like Mach+the Hurd is quite enough. This architecture
uses a supervisor/user protection model but most of the OS runs in
user mode. The last version of Mach I've seen has the device drivers
in kernel but other microkernels have proved that it is possible to
remove them from the kernel to run them in user mode. (Mach 4.0 is
evolving toward this.)
CdG> BTW: I guess the AXP has multiple rings, how'bout the other
CdG> processors everybody is porting to ?
Not all processors support multiple rings. This is one reason not to
use them.
ldd
Felix von Leitner
>kernel (assuming "multi-processor" means SMP or something close).
I hope that, when you read this sentence again, you realize this is
wrong !
Preemption has nothing to do with reentrance. The other way around ! A
reentrant kernel is preemptable, and a reentrant kernel can do SMP, but
a preemptable kernel can not automatically.
>But there are other approaches for multi-processors that go beyond a
>preemptable kernel.
???
>But since a preemptable kernel is a good idea it is usually implemented
>with anything else to support multi-processors.
Why is a preemptable kernel a good idea ? I'm perfectly happy with my
Linux, I don't know what you want ! Are you afraid that your neighbour
can say Windoze 95 has preemptive multitasking and Linux has not ?
>>In a monolithic kernel on a uniprocessor machine, you simply never
>>interrupt the kernel- in this regards, the kernel is "special".
>No. You could preempt any task and use semaphores to protect the
>data structures. This works even with a monolithic kernel and on
>uniprocessor machines.
?! Look at this :
Situation: Task a and b do file I/O
Scenario 1: Non-preemptive multitasking.
Task a makes a request, when the system is in a stable state, task b
is activated and can do a request, too.
Scenario 2: Preemptive multitasking.
Task a makes a request, which is interrupted. A semaphore is created
and initialized. Task b is activated, the semaphore is checked, Linux
finds that task b has to wait until task a is done, task b is put into
the queue of the semaphore. Then Linux switches back to task a.
When task a is done, the semaphore is cleared, task a is deactivated,
task b is activated, the old semaphore is deleted, a new semaphore is
created. The kernel notes somewhere that the file system is busy with
task b. Task b is interrupted, the whole towabunga again.
You see - not only you don't gain anything, you actually have tons of
overhead for managing stuff.
>>>A premptive _kernel_ would need locking of data structures.
>>So would a reentrant one.
>I think reentrancy is necessary for a preemptive kernel.
Bullshit.
>>>Well, it helps for tasks that need real-time :) But a preemptive
>>>kernel is good for non-real-time processes too.
>>I see a need for reentrant kernels for symetric multi-processors. What
>>other uses are there for full realtime capability, other than for
>>realtime processes?
>Well, there is real-time and real-time :) Think about a network server
>that has to answer requests. Each request needs a system call (or two).
>The time necessary for the system call depends on the time another
>process spends in the kernel. This could be long if you think about
>buffer cache operations or PIO drivers or a console driver that scrolls
>a framebuffer. A preemptable kernel (with smart data structures that
>try to avoid locking operations) could handle the network service much
>faster.
Huh ? Of course NOT ! You are just designing a system where background
activity is more important than video I/O ! Since you can't scroll the
console "in the background", you lose not only time with the overhead
you just created, you also lose time saving kernel data structure you
normally would not have to save, so you lose memory, too. And you gain
- NOTHING !
All you real-time weenies out there cry for real-time stuff and have no
idea what to do with it once it's there ! This is complete crap !
Nobody in the world needs real-time extensions in Linux ! Obviously the
marketroids have had a good harvest among the Linux users.
If your system is too slow to answer requests real-time, real-time
system extensions don't buy you anything, except that they waste memory
and clock cycles maintaining lists.
>Of course you can add lots of buffering to avoid this kernel bottleneck.
What bottleneck ? You want fast network response ? You got it !
Network response is limited by the network congestion and the disk I/O
speed, which is limited by the number of paging jobs you run. If you
want a fast network response, don't compile the kernel on that machine.
>But that just moves the latencies to a different layer.
Huh ? Seriously - You sure can spill out tons of marketing slang here,
but you didn't say anything useful IMHO.
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
"If you can, help others. If you can't, at least don't hurt others."
--the Dalai Lama
Erik Corry
: < all previous arguments deleted>
: Hey Guys,
: [Already answered question deleted]
: Also, I'm kind of foggy on how you guys have been defining user
: process in kernel mode. Does this mean a user process has made
: a system call to the kernel? As far as I know, a user process
: can still be preempted while doing this because it's state is
: saved. Even though it's made a system call, it's still a user
: process and the kernel can still preempt it.
When you do a system call, your process simply carries on running
in kernel mode. The kernel is not a process, it is more like a mode
for all processes. Of course, there is only one kernel address
space for all processes, whereas each process has its own user
address space.
Most of the confusion on this thread comes from people misunderstanding
each others' terminology, and being too quick to assume that the others
are stupid.
andrew ross
: Brian Hurt (bh...@subzero.winternet.com) wrote:
: : bouw...@dutian.twi.tudelft.nl (Bouwmeester) writes:
: : >Question: since when is the Linux kernel pre-emptive? Traditional Unix
: : >kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
: : >to do so (by calling schedule()).
: : Oy vey.
: : 1) Go read Tannebaum (if you haven't already). Pre-emptive multitasking is
: Tanenbaum
: : defined to mean "a running process may be pre-empted at any time to run
: : another process". In otherwords- a process doesn't when or if it will be
: But in Unix a process can be in user mode or in kernel mode at any one
: time. In kernel mode the process is not preempted in a traditional Unix
: kernel like Linux.
This is getting out of hand. People who generally know what they are
talking about (and therefore _should_ know better) are getting into a
ridiculous flame war here.
The word "preemptive" is being used in two sublty different ways by
the two camps. First, it is used to refer to the fact that user
programs do not get control over how much processor time they get
(other than nicing themselves) and can be arbitrarily "pre-empted"
during timer interrupts, etc... This is the traditional definition of
a "preemptive" OS, used to distinguish it from a "cooperative"
scheduler (Windows/Mac -- where a program gets to keep the CPU until
it explicitly releases it).
There is also the issue of how the kernel schedules itself. Under
linux (and most traditional Unix kernels) when a process is executing
in kernel mode, it cannot be preempted. It has to wait for the kernel
code to exit before the CPU can be given to another process. So long
as the kernel code doesn't (and it _shouldn't_) contain any long
loops, this isn't a problem 99% of the time, as very little of the CPU
time is actually spent in the kernel (you can find out roughly how
much by running 'top'). It _is_ an issue, though, with real time
applications which _need_ to be able to get the CPU at specific times,
even if another process is in the kernel.
The problems inherent in implementing kernel preemption (that more
than one process may be "in the kernel" at any point in time) are very
similar to those with designing symmetric multiprocessing systems,
where several process may be (really) in the kernel at once.
My own opinions: I think the term "preemptive OS" should be used to
refer to systems that do preemptive scheduling. Linux is one of
these. I would suggest the term "preemptible kernel" to indicate that
both user and kernel-mode operation may be preempted.
Andy Ross
ajr...@fas.harvard.edu
Albert Cahalan
>> You're confusing preemptive systems and realtime systems, which are not
>> only quite different but also incompatible (at least with one
>> processor). Please go do your homework. Thanks.
K> Actually I think the confusion here is between pre-emption
K> in the user space versus the kernal space.
I think this is why:
1: user program running in user mode, as itself, not calling kernel
2: kernel doing kernel things
3: program "in kernel mode" or kernel "servicing program's syscall"
4: interrupt handler
For number 3, I prefer to say that the kernel is running on behalf
of the user process. Many (traditional?) people prefer to say that
the user process in running in kernel mode.
Some traditions are awful, like the "text segment" full of binary data.
--
Albert Cahalan
alb...@ccs.neu.edu
Daniel Veillard
|> >Having 3 rings would be a useful notion in this case:
|> >Ring 0: Kernel Services
|> >Ring 1: System-wide services
|> >Ring 2: User-level services
|> >
|> kernel, especially all kinds of ideas people are having (a relational
|> file system, a standard set of graphics drivers, ...). Currently, the
|> kernel is blowing up without upper limits (0.97 -> 1.3 was an increase
|> from 200k to 2.2Mb), I think we should strive to make it smaller. Having
|> an intermediate level could give us the breathing space we need, and I
|> think it wouldn't be _that_ hard to implement it (AFAIK the whole thing
|> is carefully explained in the 80386 books).
I support this idea. Most of the kernel code is in fact devices driver.
IMHO, keeping them in an intermediate protection ring has a LOT of
advantages :
- allow to implement dynamic module loading without full kernel
access, this way it would be possible to implement module loading
for a restricted set of users, without root privileges.
- protect kernel internals from a device driver or module crash, if
properly designed. It can help a lot when developping FS ou drivers
since you don't need to reboot. It also improve dramatically the
whole system stability and ability to recover from failure, if a driver
crash, just restart it and have a look at the error available from
the kernel :-) .
Basically it's most of the ideas behind the notion of micro-kernel. There
is so many papers around describing in details all the benefits of such
a separation (and so few smart implementation, the usual "Computer Science"
problem ! :-)).
|> For people who don't know it, VMS implements four rings (Kernel, Executive,
|> Supervisor and User; the latter two are user-level and needed to protect
|> DCL from running images); you can jump to inner rings with CMKRNL and
|> CMEXEC system calls (they take a funcpointer as argument), you pop-up
|> back with a return. I never really analyzed it, but I guess that large
|> parts of networking, system-wide services, and maybe even parts of
|> device drivers are working on this intermediate level. It probably is
|> one of the reasons the system is so stable...
|>
|> BTW: I guess the AXP has multiple rings, how'bout the other processors
|> everybody is porting to ?
Most of the new chips have at least the three ring capability, this is at
least true for Alphas and R4x00 chips, don't know for Power[2,PC] and Sparc
but this should be available.
Daniel
Daniel Veillard : | Bull-IMAG Systems | You should give me a chance
Daniel....@imag.fr | Centre Equation | This can't be the end
Tel : (33) 76 63 48 40 | 2 ave. de Vignates | I'm still loving you
Fax : (33) 76 54 76 15 | 38610 GIERES FRANCE| Scorpions
Home: (33) 76 63 05 86 | http://aroe.imag.fr/veillard/veillard.html
L'erreur est humaine mais un veritable desastre necessite un ordinateur
Erik Corry
: Some traditions are awful, like the "text segment" full of binary data.
Or like saying binary when you mean machine code.
Erik Corry
: >Well, a preemtable kernel can easily be transformed into a multi-processor
: >kernel (assuming "multi-processor" means SMP or something close).
: I hope that, when you read this sentence again, you realize this is
: wrong !
: Preemption has nothing to do with reentrance. The other way around ! A
: reentrant kernel is preemptable, and a reentrant kernel can do SMP, but
: a preemptable kernel can not automatically.
Could you explain in more detail how you would make a kernel preemptable
without making it reentrant. If you mean that the kernel calls schedule()
fairly often - that is not a preemtable kernel. The kernel is not being
preempted at random points. A kernel that calls schedule now and then
will not achieve the same low reaction time that a really preemptable
kernel will.
: >But since a preemptable kernel is a good idea it is usually implemented
: >with anything else to support multi-processors.
: Why is a preemptable kernel a good idea ? I'm perfectly happy with my
: Linux, I don't know what you want ! Are you afraid that your neighbour
: can say Windoze 95 has preemptive multitasking and Linux has not ?
I think it is taking linux advocacy a little far when it becomes Linux
1.2 advocacy, and even suggestions for improvement are taken as attacks
on Linux.
Windows 95 almost certainly does not have a preemptable kernel. We should
aim a little higher.
: >>In a monolithic kernel on a uniprocessor machine, you simply never
: >>interrupt the kernel- in this regards, the kernel is "special".
: >No. You could preempt any task and use semaphores to protect the
: >data structures. This works even with a monolithic kernel and on
: >uniprocessor machines.
: ?! Look at this :
: Situation: Task a and b do file I/O
: Scenario 1: Non-preemptive multitasking.
: Task a makes a request, when the system is in a stable state, task b
: is activated and can do a request, too.
: Scenario 2: Preemptive multitasking.
: Task a makes a request, which is interrupted. A semaphore is created
: and initialized. Task b is activated, the semaphore is checked, Linux
: finds that task b has to wait until task a is done [etc...]
: You see - not only you don't gain anything, you actually have tons of
: overhead for managing stuff.
The point was that monolithic or not monolithic is a separate question
to the question of whether the kernel is interruptible. Your 'answer'
has nothing to do with that point.
You claim that nothing is gained, but this is merely because in your
example processes a and b both need the same resource. In this case
there is nothing you can do about it, you are simply going to have
to wait. But if the processes do not need the same resource then
process b can get priority over process a. In a non-preemptable
kernel there is only one resource: the kernel. Two processes cannot
use the kernel at the same time. With locks you can structure the
resource locking more finely.
: >>>A premptive _kernel_ would need locking of data structures.
: >>So would a reentrant one.
: >I think reentrancy is necessary for a preemptive kernel.
: Bullshit.
See above. For any real reentrancy this seems to me to be true. Having
calls to schedule() in the kernel code does not count as preemtable.
: >>>Well, it helps for tasks that need real-time :) But a preemptive
: >>>kernel is good for non-real-time processes too.
: >>I see a need for reentrant kernels for symetric multi-processors. What
: >>other uses are there for full realtime capability, other than for
: >>realtime processes?
: >Well, there is real-time and real-time :) Think about a network server
: >that has to answer requests. Each request needs a system call (or two).
: >The time necessary for the system call depends on the time another
: >process spends in the kernel. This could be long if you think about
: >buffer cache operations or PIO drivers or a console driver that scrolls
: >a framebuffer. A preemptable kernel (with smart data structures that
: >try to avoid locking operations) could handle the network service much
: >faster.
: Huh ? Of course NOT ! You are just designing a system where background
: activity is more important than video I/O ! Since you can't scroll the
: console "in the background", you lose not only time with the overhead
: you just created, you also lose time saving kernel data structure you
: normally would not have to save, so you lose memory, too. And you gain
: - NOTHING !
Without a preemptable kernel there is no way to prioritise the network
above the screen IO. Once the screen IO has started it will carry on
until it has finished. There is no way to stop it because the screen
IO code is in the kernel and therefor uninterruptible.
Suppose you use a network protocol which requires responses to
certain events within a certain time. Using a non-preemptable
kernel, you cannot guarantee a response time for the network code.
You either have to buy a smart network card that handles part of
the protocol on the card, or you use another protocol.
: All you real-time weenies out there cry for real-time stuff and have no
: idea what to do with it once it's there ! This is complete crap !
: Nobody in the world needs real-time extensions in Linux ! Obviously the
: marketroids have had a good harvest among the Linux users.
Not only do some people need it, it comes more or less for free with the
multiprocessor changes. As you admitted above. You really should calm
down before posting.
An example of a program that needs real-time response is a program
for a Class 1 fax modem. It is impossibly to write a reliable Class 1
fax modem that works under high system load on a conventional Unix
system. This is not because the system 'simply isn't fast enough', it
is because the system is not able to prioritise the fax software
to the point where it can make the timing guarantees it needs to.
This is why mgetty+sendfax does not support Class 1 fax modems.
Last I heard, the people who were implementing reentrancy and
multiprocessor capability to Linux were planning to do it in
such a way that you could compile it out if you didn't like it.
: [more raving deleted]
Michael van Elst
>BTW: I guess the AXP has multiple rings, how'bout the other processors
>everybody is porting to ?
Other processors just have two levels: user mode and supervisor mode.
Any higher structuring can be done in software or can be avoided altogether.
Michael van Elst
>pre-emptive. Meaning user processes have a fixed time quantum and,
>they either finish running in their time Q and give up the CPU,
>use up their time Q and are preempted by the kernel, or voluntarily
>give up the CPU before finishing their time Q. Is this correct?
>If not, then what is the answer to this whole argument.
It is not exactly correct. When the process is in kernel mode
at the end of the time slice it is _not_ preempted.
>Also, I'm kind of foggy on how you guys have been defining user
>process in kernel mode. Does this mean a user process has made
>a system call to the kernel?
Yes.
>As far as I know, a user process
>can still be preempted while doing this because it's state is
>saved. Even though it's made a system call, it's still a user
>process and the kernel can still preempt it.
That's a misconception. There is no magical 'kernel' that
operates outside of all processes. So while a process is
executing a system call it _is_ the kernel and it is not
preempted because the kernel needs to keep the kernel data
structures consistent.
Michael van Elst
>>Well, a preemtable kernel can easily be transformed into a multi-processor
>>kernel (assuming "multi-processor" means SMP or something close).
>I hope that, when you read this sentence again, you realize this is
>wrong !
But why ?
>Preemption has nothing to do with reentrance.
Well, preemption _without_ reentrance is pretty difficult. You would
need to lock the kernel for other tasks so that only tasks in user mode
could preempt the kernel. I don't think that his makes sense.
>The other way around ! A
>reentrant kernel is preemptable, and a reentrant kernel can do SMP, but
>a preemptable kernel can not automatically.
That is definitely correct. But there is no truly 'reentrant' kernel.
You always share data between threads that needs to be locked for
accesses.
>>But there are other approaches for multi-processors that go beyond a
>>preemptable kernel.
>???
You can create distributed data structures that are synchronized by
some kind of message protocol. Each instance of the "kernel" then runs
within its own context.
>Why is a preemptable kernel a good idea ?
Because it avoids the kernel bottleneck.
>I'm perfectly happy with my Linux, I don't know what you want !
Oh.. you could be perfectly happy with Linux. Such bottlenecks
aren't that visible if your machine is fast enough.
>Are you afraid that your neighbour
>can say Windoze 95 has preemptive multitasking and Linux has not ?
I don't use Windoze in any incarnation and, frankly, I don't use
Linux that much either. My systems run AmigaOS and NetBSD. Of course,
NetBSD has the same 'problem' as Linux.
>You see - not only you don't gain anything, you actually have tons of
>overhead for managing stuff.
Not really. The semaphores are created and initialized _once_. And
checking semaphores is a fast operation.
But the basic error your made is to use a case where both processes
need _the same_ kernel structures. Think about one that does file I/O
and one that does network I/O. Both can happen concurrently without
waiting for any semaphores (assuming a clean/separated design of both
I/O systems).
>>>>A premptive _kernel_ would need locking of data structures.
>>>So would a reentrant one.
>>I think reentrancy is necessary for a preemptive kernel.
>Bullshit.
Well, maybe not strictly 'necessary'. But you avoid lots of problems.
>Huh ? Of course NOT ! You are just designing a system where background
>activity is more important than video I/O !
But why ? This doesn't affect the scheduler. A preemptive kernel can
preempt the networking process as much as the video I/O process.
>normally would not have to save, so you lose memory, too. And you gain
>- NOTHING !
I gain efficiency and throughput because I removed the kernel bottleneck.
Well, the bottleneck is now splitted over a larger set of data structures
that can become a smaller bottleneck themselves.
>All you real-time weenies out there cry for real-time stuff and have no
>idea what to do with it once it's there ! This is complete crap !
Thanks for your open-minded opinions.
>Nobody in the world needs real-time extensions in Linux !
Then I probably qualify as 'Nobody'.
>If your system is too slow to answer requests real-time
This assumes that 'real-time' and 'fast' are synonymous.
>What bottleneck ?
I think I explained that. Any text-book on multitasking will probably
do the same.
>You want fast network response ? You got it !
I want fast and precise scheduling of threads.
>Network response is limited by the network congestion and the disk I/O
>speed, which is limited by the number of paging jobs you run. If you
>want a fast network response, don't compile the kernel on that machine.
Connect your machine to a 1Gbps link and talk again about 'network congestion'.
>>But that just moves the latencies to a different layer.
>Huh ? Seriously - You sure can spill out tons of marketing slang here,
>but you didn't say anything useful IMHO.
I don't think that technical terms like 'latency' and '(software) layer'
have anything to do with marketing slang.
I don't have anything to do with marketing anyway.
Fred R. Goldstein
>For people who don't know it, VMS implements four rings (Kernel, Executive,
>Supervisor and User; the latter two are user-level and needed to protect
>DCL from running images); you can jump to inner rings with CMKRNL and
>CMEXEC system calls (they take a funcpointer as argument), you pop-up
>back with a return. I never really analyzed it, but I guess that large
>parts of networking, system-wide services, and maybe even parts of
>device drivers are working on this intermediate level. It probably is
>one of the reasons the system is so stable...
>BTW: I guess the AXP has multiple rings, how'bout the other processors
>everybody is porting to ?
I think AXP is actually two levels in hardware. One level is normally hidden
from the user, runs very special microcode (PALcode, I think), and creates a
"personality" for the chip. The other level uses the PALcode calls to
simulate whatever the OS wants. Thus for VMS, it creates 4 levels of
protection, while Unix uses fewer.
Agreed that there's too much in "kernel".
Fred R. Goldstein k1io fgold...@bbn.com
Bolt Beranek & Newman Inc., Cambridge MA USA +1 617 873 3850
Opinions are mine alone; sharing requires permission.
Jim Finnis
Erik Corry <er...@kroete2.freinet.de> wrote:
>: Some traditions are awful, like the "text segment" full of binary data.
>
>Or like saying binary when you mean machine code.
>
Incidentally, what does BSS stand for? I know what it means -
uninitialised data segment - but what the hell do the letters stand for?
Jim
Louis-D. Dubeau
>> For this purpose rings are unnecessary. A
>> microkernel/multiserver architecture like Mach+the Hurd is
>> quite enough. This architecture uses a supervisor/user
>> protection model but most of the OS runs in user mode. The
>> last version of Mach I've seen has the device drivers in kernel
>> but other microkernels have proved that it is possible to
>> remove them from the kernel to run them in user mode. (Mach
>> 4.0 is evolving toward this.)
FvL> Hey, one moment, AFAIK there has never been a microkernel
FvL> architecture that was as fast as a monolithic architecture.
FvL> Besides that - moving things from the kernel does not save
FvL> memory ! The opposite is true ! You need more memory for
FvL> the communications code and the message passing overhead eats
FvL> time, too.
If you have a modular OS with modules that are loadable on demand, you
save memory. One of the posters in this thread complained he had a
2Mb kernel, I guess that not everything in this kernel is used all the
time. Also, I don't know if numbers are available for QNX but this is
one _fast_ mk. Remember also that not only a mk architecture removes
the need for protection rings but also adds flexibility and fault
tolerance to a system (if well used).
>> Not all processors support multiple rings. This is one reason
>> not to use them.
FvL> I'm not convinced we don't need multiple rings. Multiple
FvL> rings can reduce the message passing overhead and add
FvL> security, since disk drivers, for example, don't have to be
FvL> ring 0.
With a mk/multiserver architecture the disk driver can run in user
mode. I don't know if thread migration has been implemented yet in
Mach 4 but this is one thing that reduces communication overhead _a
lot_. (Thread migration is the process of moving thread between
tasks.)
ldd
Thomas Koenig
>Hey, one moment, AFAIK there has never been a microkernel architecture
>that was as fast as a monolithic architecture.
Take a look at QNX one day. It's a microkernel (10 k ;-) based,
'hard' realtime operating system.
If you want hard realtime capabilities in an industrial environment,
going microkernel makes a lot of sense:
- You want a preemptible kernel with fixed response time; anything
that's big and complicated and makes analysis harder should be
avoided.
- For embedded systems, you want easy scalability; removing
unneeded parts is as easy as not starting a particular server.
Of course, there's additional overhead involved in message passing, etc.
However, this overhead need not be large compared to other factors;
a slightly cleaner design, which a microkernel architecture lends itself
to, might be enough to offset this advantage.
I'm reminded of a story which I read on alt.folklore.computers not so
long ago. You may know the IBM VM operating system, which splits up the
machine into different virtual machines, emulating each one.
The people who wrote this OS were acutely aware that every cycle spent
in emulation was wasted, so they optimized it (efficiency and shortening
the execution path became quite an obsession; apparently, readability of
the resulting code wasn't too good, but it was fast).
The result was that you could run VS/1, a production operating system,
under VM by pretending to the VS/1 system that it ran in real storage,
and letting VM handle all the paging, FASTER than running VS/1 on
the bare metal. The highly optimized paging algorithms of VM were
more than enough to overcompensate for the average 10% overhead spent
in emulated supervisor mode.
>I'm not convinced we don't need multiple rings. Multiple rings can
>reduce the message passing overhead and add security, since disk
>drivers, for example, don't have to be ring 0.
I think OS/2 does this, but I'm not really sure what this buys for the
kernel. Isn't there additional overhead in passing data read from
a device driver in ring 1 to the kernel in ring 0 to the user
in ring 3? I admit I've never studied this issue.
Also, what processors have multiple rings? The Alpha probably has them
(I believe VMS uses four rings, though what for I can't imagine),
the 68k doesn't, ...
--
Thomas Koenig, Thomas...@ciw.uni-karlsruhe.de, ig...@dkauni2.bitnet.
The joy of engineering is to find a straight line on a double
logarithmic diagram.
Michael van Elst
>When you redefine "preemption" as you did, you are trying to get back to an
>etymological meaning of preemption. It just happens that this meaning is not
>the common-use meaning. See any good basic textbook on operating systems.
Any good textbook defines the UNIX-Kernel es non-preemptive.
Of course this might be different from the "common" meaning.. whoever
that "common" is.
Anyway, since you have a different meaning of the word it doesn't make
sense to discuss this topic any further.
Peter Moulder
<lei...@inf.fu-berlin.de> wrote:
> >I think reentrancy is necessary for a preemptive kernel.
>
> Bullshit.
(Let's take "preemptive" above to apply to kernel mode, not just user
mode. We might as well avoid that confusion again.)
Process A makes system call _foo().
Before _foo() has completed, it is preempted, and control goes to process B.
Process B also makes the system call _foo().
The possibility of _foo() being preempted and control passing to another
instance of _foo() requires _foo() to be reentrant.
Therefore a "preemptive kernel" (according to the definition I use above)
must also be reentrant.
(Thanks Erik Corry for addressing the rest of the article.)
pjm.
Redestination REAL Soon Now
| Incidentally, what does BSS stand for? I know what it means -
| uninitialised data segment - but what the hell do the letters stand for?
Block Starting Symbol, though it has been a long time and my
memory might not be completely intact . . .
Cees de Groot
Louis-D. Dubeau <l...@step.polymtl.ca> wrote:
>
>For this purpose rings are unnecessary. A microkernel/multiserver
>architecture like Mach+the Hurd is quite enough. This architecture
>uses a supervisor/user protection model but most of the OS runs in
>user mode. The last version of Mach I've seen has the device drivers
>in kernel but other microkernels have proved that it is possible to
>remove them from the kernel to run them in user mode. (Mach 4.0 is
>evolving toward this.)
>
we can about rewrite the system from scratch. An extra ring would give
the same effect, without much of the hassle (IMHO).
--
Cees de Groot, OpenLink Software <c...@openlink.co.uk>
PGP26ui: 14 C4 B3 B6 97 7F CA 4F FC 7D E8 B1 AB 25 03 19 [Key on servers]
<A HREF=http://www.decus.de/people/de_groot/bio.html>Click</A>
-- Programmir c'est mourir un peu
Cees de Groot
Thomas Koenig <Thomas...@ciw.uni-karlsruhe.de> wrote:
>(I believe VMS uses four rings, though what for I can't imagine),
>the 68k doesn't, ...
It does: Kernel and Executive may be clear (these are the standard inner
rings), but then things get VMS specific: DCL, the CLI under VMS, always
is `there' in a session. When it needs an executable to perform a task
(probably while the user asked for it), it loads the image, but in a outer
ring (the User rings are Supervisor and User). This protects DCL from
the image, and the system from having to create new processes all of the
time.
At least, that's how I understood it :-).
Felix von Leitner
>In <3sp2ts$e...@fu-berlin.de> Felix von Leitner <lei...@inf.fu-berlin.de> writes:
>>>Well, a preemtable kernel can easily be transformed into a multi-processor
>>>kernel (assuming "multi-processor" means SMP or something close).
>>I hope that, when you read this sentence again, you realize this is
>>wrong !
>But why ?
Because I can kludge together a preemptable Linux kernel that is NOT
easity transformed into a SMP kernel.
>>Preemption has nothing to do with reentrance.
>Well, preemption _without_ reentrance is pretty difficult.
It's the other way around. If you are reentrant, then you can be
made preemptable easily.
>You would need to lock the kernel for other tasks so that only tasks in
>user mode could preempt the kernel. I don't think that his makes sense.
??? A preemptable kernel does not need to be reentrant !
>>The other way around ! A reentrant kernel is preemptable, and a
>>reentrant kernel can do SMP, but a preemptable kernel can not
>>automatically.
>That is definitely correct. But there is no truly 'reentrant' kernel.
>You always share data between threads that needs to be locked for
>accesses.
You tell me there cannot be a reentrant kernel ? How do you explain me
that there exist SMP kernels ? Like Solaris ?
>>>But there are other approaches for multi-processors that go beyond a
>>>preemptable kernel.
>You can create distributed data structures that are synchronized by
>some kind of message protocol. Each instance of the "kernel" then runs
>within its own context.
Let's get this straight now. This is reentrance ! This is exactly what
we mean when we say a kernel is "reentrant". An operation can be called
several times at a time. That there has to be some synchronisation is
unquestioned.
>>Why is a preemptable kernel a good idea ?
>Because it avoids the kernel bottleneck.
What kernel bottleneck ?
>>I'm perfectly happy with my Linux, I don't know what you want !
>Oh.. you could be perfectly happy with Linux. Such bottlenecks
>aren't that visible if your machine is fast enough.
My machine is not fast enough. No machine is ever fast enough.
>>Are you afraid that your neighbour can say Windoze 95 has preemptive
>>multitasking and Linux has not ?
>I don't use Windoze in any incarnation and, frankly, I don't use
>Linux that much either. My systems run AmigaOS and NetBSD. Of course,
>NetBSD has the same 'problem' as Linux.
You people will all be disappointed when you have a real-time Linux.
>>You see - not only you don't gain anything, you actually have tons of
>>overhead for managing stuff.
>Not really. The semaphores are created and initialized _once_. And
>checking semaphores is a fast operation.
But it's not a necessity, so it's unneeded overhead. If you have
millions of small kernel calls and you add this overhead, you *will*
notice the slowdown if you compare both Linuxen.
>But the basic error your made is to use a case where both processes
>need _the same_ kernel structures. Think about one that does file I/O
>and one that does network I/O. Both can happen concurrently without
>waiting for any semaphores (assuming a clean/separated design of both
>I/O systems).
Without *waiting*, yes. But you still have the - basically unnecessary
- semaphore operations there. Linux already supports asynchronous disk
and network I/O if your network devices support it. What is your
problem ?
>>Huh ? Of course NOT ! You are just designing a system where background
>>activity is more important than video I/O !
>But why ? This doesn't affect the scheduler. A preemptive kernel can
>preempt the networking process as much as the video I/O process.
But why should it ? Both already run asynchronously if your network and
disk adapters support other things as polled I/O.
>>normally would not have to save, so you lose memory, too. And you gain
>>- NOTHING !
>I gain efficiency and throughput because I removed the kernel bottleneck.
>Well, the bottleneck is now splitted over a larger set of data structures
>that can become a smaller bottleneck themselves.
There IS not kernel bottleneck. Look, if you actually waited for the
file system to write to disk, there would be a bottleneck. But it's
this way. You issue your file system read operation and your task is
put asleep until the data has been read. You issue your disk write
operation, it's put into the disk cache, and is written to disk
asynchronously. There *IS* *NO* bottleneck. Trust me.
>>All you real-time weenies out there cry for real-time stuff and have no
>>idea what to do with it once it's there ! This is complete crap !
>Thanks for your open-minded opinions.
Hehe, well, normally I would not have a problem with this. If you want,
you can work with a real-time Linux. But in the case, I'll lose
performance, too, because I will be forced to use a real-time Linux,
too, and take the full overhead, too.
>>Nobody in the world needs real-time extensions in Linux !
>Then I probably qualify as 'Nobody'.
Ah, you need them ? What for ?
"Mommy, I have a real-time system now !"
"I'm SOOO proud of you, Michael !"
>>What bottleneck ?
>I think I explained that. Any text-book on multitasking will probably
>do the same.
No problem. You show me a bottleneck, and I pay you one beer if you
visit me in Berlin, OK ? With "show" I mean "demonstrate", not "point
to some text book".
>>You want fast network response ? You got it !
>I want fast and precise scheduling of threads.
What for ? Interrupts and buffering should be enough for you !
>>Network response is limited by the network congestion and the disk I/O
>>speed, which is limited by the number of paging jobs you run. If you
>>want a fast network response, don't compile the kernel on that machine.
>Connect your machine to a 1Gbps link and talk again about 'network congestion'.
No problem, you pay me the 1Gbps link, and we'll see further ;)
As demonstrated on the Linux congress here in Berlin, a Pentium-90 was
barely able to do 150 Mbps, when DEDICATED. So again, it's not the busy
machine but the slow hardware that limits your performance.
>>>But that just moves the latencies to a different layer.
>>Huh ? Seriously - You sure can spill out tons of marketing slang here,
>>but you didn't say anything useful IMHO.
>I don't think that technical terms like 'latency' and '(software) layer'
>have anything to do with marketing slang.
>I don't have anything to do with marketing anyway.
I meant the whole tone of your message, not this particular one. I
still think you did not demonstrate your claims, you just point to
"every good text book should show you".
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
Any programming language is at its best before it is implemented and used.
Felix von Leitner
>In <3sofda$1...@beth.bacbuc.fdn.fr> char...@bacbuc.frmug.fr.net (Emmanuel Charpentier) writes:
>>When you redefine "preemption" as you did, you are trying to get back to an
>>etymological meaning of preemption. It just happens that this meaning is not
>>the common-use meaning. See any good basic textbook on operating systems.
>Any good textbook defines the UNIX-Kernel es non-preemptive.
Halt, wait a minute, a textbook that defines the UNIX kernel as
non-preemptive is no good ;) The original AT&T UNIX kernel was
non-preemptive, but there are a number of clones. As far as I know,
most are still non-preemptive, but some OSes offer preemptiveness.
>Of course this might be different from the "common" meaning.. whoever
>that "common" is.
>Anyway, since you have a different meaning of the word it doesn't make
>sense to discuss this topic any further.
You are right. Let's stop this discussion.
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
Even if you do learn to speak correct English, whom are you going to
speak it to?
--Clarence Darrow
Michael van Elst
>Incidentally, what does BSS stand for?
Block storage section.
Felix von Leitner
>> Bullshit.
>(Let's take "preemptive" above to apply to kernel mode, not just user
>mode. We might as well avoid that confusion again.)
>Process A makes system call _foo().
>Before _foo() has completed, it is preempted, and control goes to process B.
>Process B also makes the system call _foo().
>The possibility of _foo() being preempted and control passing to another
>instance of _foo() requires _foo() to be reentrant.
Yes, but that is not a requirement for a preemptive kernel.
"Preemptive" does not mean that you can execute the preempted kernel call
again, it just means you can interrupt a kernel call. Being able to
execute an interrupted system call again is called "reentrancy".
>Therefore a "preemptive kernel" (according to the definition I use above)
>must also be reentrant.
No.
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
Crime and Punishment LITE(tm)
--by Fyodor Dostoevski
A man sends a nasty letter to a pawnbroker, but later
feels guilty and apologizes.
Rajat Datta
Michael van Elst <mle...@comma.rhein.de> wrote:
>In <3sn8pn$2...@tricbbs.tricbbs.fn.sub.org> c...@tricbbs.tricbbs.fn.sub.org (Cees de Groot) writes:
>
>>BTW: I guess the AXP has multiple rings, how'bout the other processors
>>everybody is porting to ?
>
>Any higher structuring can be done in software or can be avoided altogether.
>
>--
> Michael van Elst
>
>Internet: mle...@mpifr-bonn.mpg.de mle...@serpens.rhein.de
> "A potential Snark may lurk in every tree."
The x86 processors have four rings, with ring 0 being the most priviledged.
I know of a few operating systems that use 3 rings, Unix systems use 2 rings,
and don't know of any that uses all four.
rajat
Michael van Elst
>>Well, preemption _without_ reentrance is pretty difficult.
>It's the other way around. If you are reentrant, then you can be
>made preemptable easily.
Do you notice that this is exactly the same statement ?
>>You would need to lock the kernel for other tasks so that only tasks in
>>user mode could preempt the kernel. I don't think that his makes sense.
>??? A preemptable kernel does not need to be reentrant !
Try to get your arguments straight.
>You tell me there cannot be a reentrant kernel ? How do you explain me
>that there exist SMP kernels ? Like Solaris ?
Reentrancy means that you can enter a function while another thread
just executes that function.
You can't do this everywhere. As soon as you have to access data structures
that are shared you have to prevent concurrent threads to access these
structures. These functions are therefore not reentrant.
>Let's get this straight now. This is reentrance ! This is exactly what
>we mean when we say a kernel is "reentrant".
It is not. You can get a large portion of reentrancy with shared data.
You just lock them when you access them intead of locking the kernel
as a whole.
>>>Why is a preemptable kernel a good idea ?
>>Because it avoids the kernel bottleneck.
>What kernel bottleneck ?
Only one thread can access kernel structures at a time... in UNIX/Linux.
>My machine is not fast enough. No machine is ever fast enough.
Is that an argument ? If yes then I can tell you that you see the
kernel bottleneck.
>You people will all be disappointed when you have a real-time Linux.
But why ?
>But it's not a necessity, so it's unneeded overhead.
It's necessary to get a preemptive kernel.
>If you have
>millions of small kernel calls and you add this overhead, you *will*
>notice the slowdown if you compare both Linuxen.
Or even a speedup. Total throughput is of course reduced if your CPU
is the bottleneck, but existing systems show that the overhead is
rather small. On the other hand you can gain much in terms of I/O
and communication.
>Without *waiting*, yes. But you still have the - basically unnecessary
>- semaphore operations there.
Isn't that better than *waiting* for the kernel to schedule a process ?
>Linux already supports asynchronous disk
>and network I/O if your network devices support it. What is your
>problem ?
I don't have a problem.
>But why should it ? Both already run asynchronously if your network and
>disk adapters support other things as polled I/O.
Running 'asynchronously' is completely off-topic.
>There IS not kernel bottleneck.
*sigh*. Do us a favour and read some text-books...
>Look, if you actually waited for the
>file system to write to disk, there would be a bottleneck.
If you actually waited for the kernel to be unlocked (== the current
thread leaving the kernel) there would be a bottleneck.
It is basically the same. You wait for a resource.
>asynchronously. There *IS* *NO* bottleneck. Trust me.
You seem to have a problem with the language.
>Ah, you need them ? What for ?
>"Mommy, I have a real-time system now !"
>"I'm SOOO proud of you, Michael !"
What a pure asshole you are...
>>I want fast and precise scheduling of threads.
>What for ? Interrupts and buffering should be enough for you !
Maybe for you. 640k RAM is good enough for you.
>As demonstrated on the Linux congress here in Berlin, a Pentium-90 was
>barely able to do 150 Mbps, when DEDICATED. So again, it's not the busy
>machine but the slow hardware that limits your performance.
In that case you have no network congestion... so it is NOT the limit.
A limit can be the locking of the kernel.
Michael van Elst
>Halt, wait a minute, a textbook that defines the UNIX kernel as
>non-preemptive is no good ;)
Oh.. it is good, it has something to do with reality.
>The original AT&T UNIX kernel was
>non-preemptive, but there are a number of clones.
That's not UNIX.
Michael Shields
Mikolaj Habryn <dic...@tartarus.uwa.edu.au> wrote:
> Yeah - i did this on my linux box. I ripped out all the suid root
> stuff, stripped down my group and passwd files as far as possible, then
> reinstalled everything that needed privs from scratch. It is a pain.
> While you can do it, it generally requires manoeuvres such as adding
> specific uids into the requisite groups in /etc/group and tweaking
> the source to call initgroups().
>
> It's not really worth the effort.
It's called "least privilege", and it's something your distribution
maker should have done in the first place. It's not really that hard
to administer once set up.
--
Shields.
Felix von Leitner
>In <3sv33r$s...@fu-berlin.de> Felix von Leitner <lei...@inf.fu-berlin.de> writes:
>>>Well, preemption _without_ reentrance is pretty difficult.
>>It's the other way around. If you are reentrant, then you can be
>>made preemptable easily.
>Do you notice that this is exactly the same statement ?
It's not.
An example: climbing a mountain without a spoon is difficult. That does
not make climbing a mountain with a spoon easy.
>>>You would need to lock the kernel for other tasks so that only tasks in
>>>user mode could preempt the kernel. I don't think that his makes sense.
>>??? A preemptable kernel does not need to be reentrant !
>Try to get your arguments straight.
They are straight. If you don't understand something, please say what
it is, and I'll try to elaborate.
>>You tell me there cannot be a reentrant kernel ? How do you explain me
>>that there exist SMP kernels ? Like Solaris ?
>Reentrancy means that you can enter a function while another thread
>just executes that function.
>You can't do this everywhere. As soon as you have to access data structures
>that are shared you have to prevent concurrent threads to access these
>structures. These functions are therefore not reentrant.
No. You can let them enter the kernel, when they try to enter the
critical region, suspend them until the other thread lifts the lock and
then switch back.
>>Let's get this straight now. This is reentrance ! This is exactly what
>>we mean when we say a kernel is "reentrant".
>It is not. You can get a large portion of reentrancy with shared data.
>You just lock them when you access them intead of locking the kernel
>as a whole.
Look, we can talk for hours (in fact, we do) and don't come to a
conclusion when we don't agree on the definitions. My definition of
reentrancy is: "can be entered more than once". My definition of
preemptable is "can be interrupted", which does not necessarily mean it
can be entered more than once. What you say here is not a contradiction
to what I said. So please get your definitions straight before
following up.
>>>>Why is a preemptable kernel a good idea ?
>>>Because it avoids the kernel bottleneck.
>>What kernel bottleneck ?
>Only one thread can access kernel structures at a time... in UNIX/Linux.
Since there is no way that another thread can even TRY to access the
kernel structures at a time, there is no need to add overhead to permit
that.
>>My machine is not fast enough. No machine is ever fast enough.
>Is that an argument ? If yes then I can tell you that you see the
>kernel bottleneck.
That was just a little joke to show that your argument (which you did
not quote here) was invalid. There is no kernel bottleneck because my
machine is slow.
>>You people will all be disappointed when you have a real-time Linux.
>But why ?
Because it adds another layer of overhead which takes time and gives you
effectively nothing.
>>But it's not a necessity, so it's unneeded overhead.
>It's necessary to get a preemptive kernel.
No. It is not. You always quote some mysterious kernel bottleneck
which is simply not there. It is *not* necessary to have a preemptive
kernel, so it's not necessary to add that overhead.
>>If you have
>>millions of small kernel calls and you add this overhead, you *will*
>>notice the slowdown if you compare both Linuxen.
>Or even a speedup. Total throughput is of course reduced if your CPU
>is the bottleneck, but existing systems show that the overhead is
>rather small. On the other hand you can gain much in terms of I/O
>and communication.
That argumentation would be correct if disk I/O was done synchronously,
which it isn't. In fact, not only is the disk I/O not done
synchronously, the printer I/O, the serial I/O, the network I/O, all of
these are done interrupt driven and not synchronously, so there is no
throughput to gain by doing things asynchronous.
>>Without *waiting*, yes. But you still have the - basically unnecessary
>>- semaphore operations there.
>Isn't that better than *waiting* for the kernel to schedule a process ?
You don't wait for the kernel. Who is waiting for what kernel in your
opinion ? When the urgent I/O request you seem to be constructing your
argumentation on comes, the kernel handles the interrupt, so in a sense,
the kernel is already preemptable.
Possibility 1. You want to transmit 10 megabytes over a serial link. You
want to achieve that no characters are dropped. So the kernel has a
buffer with the next 2k to be sent and the interrupt handler can send
the next character. The situation is that the data generating task does
not *need* to be run as soon as the device is ready to send the next few
characters, because we can buffer the data before the device is ready.
Possibility 2. You want to receive 10 megabytes over a serial link. You
want to achieve that no characters are lost. So the kernel has a buffer
which can hold 2k and when the serial device signals that a new
character has arrived, the kernel does not need to activate the task
that waits for the data, it can queue them in a buffer. So no chars get
dropped.
Possibility 3. You want to receive chars and send the answer directly
afterwards. You can build a kernel driver that answers real-time. Now
we have some very wise guys saying that the driver may not answer
real-time because the next interrupt might occur. Now if this was true,
we would not have been able to answer the requests quickly enough with
any other method. If you don't understand this: Waking up the process
that waits for the device takes more time that having the kernel handle
the requests.
>>Linux already supports asynchronous disk
>>and network I/O if your network devices support it. What is your
>>problem ?
>I don't have a problem.
Fine ! So what are we discussing about when you don't have a problem
with Linux as it is now ? The whole thread consist of me and people
having the problem that they want a reentrant kernel.
>>But why should it ? Both already run asynchronously if your network and
>>disk adapters support other things as polled I/O.
>Running 'asynchronously' is completely off-topic.
No, since that's the only thing that could be sped up by having a
reentrant kernel !
>>There IS not kernel bottleneck.
>*sigh*. Do us a favour and read some text-books...
I should read a text book ? Which do you want me to cite of to prove
that I read a few ? I'd say that *you* should read some text books.
First you claim that we need a reentrant kernel but are not able to
give reasons other than "speed up because we avoid the kernel
bottleneck". Let me say it again. There is no kernel bottleneck.
In case you didn't get it: there is no kernel bottleneck.
Oh, you have reading problems ? Then let me repeat that.
THERE IS NO KERNEL BOTTLENECK.
>>Look, if you actually waited for the
>>file system to write to disk, there would be a bottleneck.
>If you actually waited for the kernel to be unlocked (== the current
>thread leaving the kernel) there would be a bottleneck.
But since we don't have threads interrupting processes in the kernel, we
don't have kernel locking, and thus we don't have a bottleneck.
>It is basically the same. You wait for a resource.
Who waits for what resource ? Please give one example. Just one.
Please ? Pretty-please ? With raspberries on top ?
>>asynchronously. There *IS* *NO* bottleneck. Trust me.
>You seem to have a problem with the language.
Maybe I do. I can't prove the opposite. But that has nothing to do
with the fact that there is no kernel bottleneck.
>>Ah, you need them ? What for ?
>>"Mommy, I have a real-time system now !"
>>"I'm SOOO proud of you, Michael !"
>What a pure asshole you are...
At least you think I'm a pure one. Mhh, who was that who said I had a
problem with the language ? You seem to know more words than I do.
>>>I want fast and precise scheduling of threads.
>>What for ? Interrupts and buffering should be enough for you !
>Maybe for you. 640k RAM is good enough for you.
I can work with 640k RAM. So what ? What does this have to do with the
fact that kernel locking does not give you more performance, since it's
overhead and it's not necessary ? You were not able to give a single
example that proves your point. You seem to believe that claiming a
thing over and over again makes it more valid. This is not true.
>>As demonstrated on the Linux congress here in Berlin, a Pentium-90 was
>>barely able to do 150 Mbps, when DEDICATED. So again, it's not the busy
>>machine but the slow hardware that limits your performance.
>In that case you have no network congestion... so it is NOT the limit.
>A limit can be the locking of the kernel.
Yes, kernel locking can limit your performance, that's exactly what I
was saying all the time. Finally we came to an agreement. Wonderful.
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
I remember when legal used to mean lawful, now it means some
kind of loophole.
--Leo Kessler
Felix von Leitner
>In <3sv3c0$s...@fu-berlin.de> Felix von Leitner <lei...@inf.fu-berlin.de> writes:
>>Halt, wait a minute, a textbook that defines the UNIX kernel as
>>non-preemptive is no good ;)
>Oh.. it is good, it has something to do with reality.
It's not good since there is not "the UNIX kernel". There are several
UNIX versions, which were until now all non-preemptive. But UNIX is not
defined to be non-preemptive. There is no divine power keeping UNIX
from being preemptive. Although I am trying to ;)
>>The original AT&T UNIX kernel was
>>non-preemptive, but there are a number of clones.
>That's not UNIX.
Yes. So ?
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
Hardware:
The parts of a computer system that can be kicked.
Michael van Elst
>They are straight. If you don't understand something, please say what
>it is, and I'll try to elaborate.
How kind of you. Could it be that you have problems to understand something ?
>>You can't do this everywhere. As soon as you have to access data structures
>>that are shared you have to prevent concurrent threads to access these
>>structures. These functions are therefore not reentrant.
>No. You can let them enter the kernel, when they try to enter the
>critical region, suspend them until the other thread lifts the lock and
>then switch back.
Please note that I did not make a statement about a kernel or critical
regions. I made a statement about reentrancy.
>Look, we can talk for hours (in fact, we do) and don't come to a
>conclusion when we don't agree on the definitions.
>From the discussion I see that you are the one with the different
definitions.
>My definition of
>reentrancy is: "can be entered more than once". My definition of
>preemptable is "can be interrupted", which does not necessarily mean it
>can be entered more than once.
Preemptable does not mean: "can be interrupted". Close to everything
can be interrupted but you still cannot schedule another thread.
Scheduling another thread however would let the new thread enter the
same function.
>Since there is no way that another thread can even TRY to access the
>kernel structures at a time,
As a matter of fact it is possible that multiple threads access
kernel structures. Every thread does. But it requires explicit
action of the kernel to allow other threads to run.
>That was just a little joke to show that your argument (which you did
>not quote here) was invalid. There is no kernel bottleneck because my
>machine is slow.
That was not my argument. A slow machine can make the kernel bottleneck
visible. A fast machine can have this bottleneck but still be fast enough
for the input from a specific setup.
>Because it adds another layer of overhead which takes time and gives you
>effectively nothing.
Tell that all those people that USE real-time systems.
>>>But it's not a necessity, so it's unneeded overhead.
>>It's necessary to get a preemptive kernel.
>No. It is not.
It is NOT necessary to add this overhead to get a preemptive kernel ?
>You always quote some mysterious kernel bottleneck
>which is simply not there.
Try to look up the definition of "bottleneck".
>It is *not* necessary to have a preemptive
>kernel, so it's not necessary to add that overhead.
It is not necessary to use a computer, so it's not necessary
to add that overhead.
>That argumentation would be correct if disk I/O was done synchronously,
>which it isn't.
Please. This has nothing to do with synchronous disk I/O.
>these are done interrupt driven and not synchronously, so there is no
>throughput to gain by doing things asynchronous.
Check your logic.
>You don't wait for the kernel.
The task does wait for the kernel. If it would be waiting it would be
running. It is not running. Fullstop.
>Who is waiting for what kernel in your
>opinion ? When the urgent I/O request you seem to be constructing your
>argumentation on comes, the kernel handles the interrupt, so in a sense,
>the kernel is already preemptable.
The interrupt can do what ? Handle protocols of a user process ?
>Possibility 1. You want to transmit 10 megabytes over a serial link. You
>want to achieve that no characters are dropped.
>Possibility 2. You want to receive 10 megabytes over a serial link. You
>want to achieve that no characters are lost.
>Possibility 3. You want to receive chars and send the answer directly
>afterwards. You can build a kernel driver that answers real-time.
The answer is: YOU MUST BUILD A KERNEL DRIVER that answers real-time.
>any other method. If you don't understand this: Waking up the process
>that waits for the device takes more time that having the kernel handle
>the requests.
_If_ the kernel can handle the request. Are you going to put arbitrary
software into your kernel ?
>Fine ! So what are we discussing about when you don't have a problem
>with Linux as it is now ?
We are discussing a misunderstanding of yours.
>No, since that's the only thing that could be sped up by having a
>reentrant kernel !
Asynchronous I/O is something that can be sped up by having a
rentrant kernel. Yes, right, correct.
> THERE IS NO KERNEL BOTTLENECK.
Define Bottleneck.
Have a look how requests of tasks are handled by the kernel.
Now look _when_ the kernel is able to handle requests.
There is a limit to _when_ it can handle requests.
This limits the number of requests that can be handled in a time.
Compare that with the definition of bottleneck.
>But since we don't have threads interrupting processes in the kernel, we
>don't have kernel locking, and thus we don't have a bottleneck.
Of course you have kernel locking. As soon as a thread is using
the kernel it is blocked for all other threads.
>Who waits for what resource ?
Interrupt wants to wake up a user process. This is defered if another
process is executing in kernel mode. The first process _waits_ for
the _resource_ "kernel".
>Please ? Pretty-please ? With raspberries on top ?
Another one of your kind answers.
>Maybe I do. I can't prove the opposite. But that has nothing to do
>with the fact that there is no kernel bottleneck.
Read above.
>At least you think I'm a pure one. Mhh, who was that who said I had a
>problem with the language ? You seem to know more words than I do.
Doesn't change the fact that you insulted me.
>overhead and it's not necessary ? You were not able to give a single
>example that proves your point.
You didn't listen.
>Yes, kernel locking can limit your performance, that's exactly what I
>was saying all the time. Finally we came to an agreement. Wonderful.
You didn't say this. You are misunderstanding. I said "kernel locking",
that means: locking the whole kernel, inhibiting other threads to
use the kernel, not being able to schedule other tasks to use the kernel.
This is not a matter of overhead, it is a matter of locking resources
that aren't used.
A reentrant kernel would lock data structures when needed to maximize
concurrency, even in the kernel.
Geert Uytterhoeven
|>
|> I have been told in mail that a UNIX FAQ says that it actually
|> stands for Block Started by Symbol, and may have roots in
|> Fortran. Just thought I would pass the info along.
The book `Design of the BSD 4.3 Operating System' (the book with the devil)
says that BSS means `Block Started by Symbol'.
Greetings,
Geert
--
Geert Uytterhoeven Geert.Uyt...@cs.kuleuven.ac.be
Wavelets, Linux/68k on Amiga,... http://www.cs.kuleuven.ac.be/~geert/
Department of Computer Science -- Katholieke Universiteit Leuven -- Belgium
Hiro Sugawara
>pe...@best.com (Roger Reynolds) wrote:
>>Here's a question that somebody must surely have thought of by now..
>>
>>I was wondering if anybody has come up with a kernel hack that would
>>allow for "premptive multi-tasking". It seems to me that with a few
>>well placed hacks to the scheduler, one should be able to guarantee
>>that the highest priority task that is runnable is always the one that
>>is running.
>>
>>I dunno, just a quick thought. Anybody else going down this road?
>>
>
>I believe that Linux already does this, and has since 0.00pl0... (if you mean
>preemptive to be requiring tasks to give up time, rather than assuming tasks
>know how to give up time)
I have not read the original posting, but I guess it asked whether Linux
*kernel* is preemptable. If so, and Linux kernel is not actually preembtable,
I doubt that it could be easily done just by "patching," unless the
original kernel was designed with a high degree of preemptability and
reentrancy in mind.
Normal Unix kernels are not preempltable: If a lower priority
tasks is running in kernel mode (i.e., executing system call) and a
higher priority task becomes ready by an event such as an interrupt,
the higher priority task cannot run until the lower priority task
relinquishes CPU by suspending itself or exits kernel mode to user
mode. This is acceptable in time-sharing environments such as Unix,
but not in real-time environments--sometimes fatally unacceptable.
I know of only two fully preemptable Unix-compatible real-time kernels:
Venix and LynxOS. Venix was made by Venturecom, a Mass. company, by patching
SVR3 kernel and runs only on 386. LynxOS was written from scrath using no
AT&T code and runs on x86, 68040, uSPARC, and PPC. LynxOS, made and marketed
by Lynx Real-Time Systems in San Jose, is often confused with Linux
and Lynx WWW brouser by a number of people, resulting the news group
"comp.os.lynx" contaminated with postings from those stupid people.
hiro
--
Hiro Sugawara hsug...@us.oracle.com +1(415)506-9336
Oracle Corporation MPP Development
500 Oracle Parkway, Box 659107, Redwood Shores, CA 94065 USA
Redestination REAL Soon Now
Reagan Blundell
"Is Not!"
"Is Too!"
"Is NOT!"
arguments?
--
Reagan Blundell Phone: +61-7 405 5764 (work)
System Operations +61-15 657 366 (mobile)
rea...@opennet.net.au Fax: +61-7 405 5759
These are my opinions, and not necesarily the opinions of my employer.
Eric Jacquino
>
> non-preemptive, but there are a number of clones. As far as I know,
> most are still non-preemptive, but some OSes offer preemptiveness.
>
We are saying Linux (and most Unix kernel) doesn't have a preemptive __kernel__..
It is not the same to say Linux is not a preemptive system !
A system with a preemptive kernel is a system where processes can be preempted
even when in kernel mode..
In Linux for example, a process can be preempted only when in user mode or
when in kernel mode when waiting for an event (I/O, semaphore ..).
The process will call implicitely (*) a kernel call like sleep() or something like that in this case to be put in waiting queue.
(*) In fact the process when in user mode doesn't make himself the sleep() call which is reserved to the kernel mode but when the kernel make some systems calls, behind this
system call can make himself the sleep() kernel call..
In preemptive kernel, the processes can be preempted in kernel mode at almost any moment even if they don't call sleep() or something like that.
In fact, the problem is that the kernel must be made reentrant (except for some code
portions that enable() disable() interrupt to protect data structures integrity.. : theses sequences are called masked (for interrupt) sequences)
Preemptive kernel is the angular stone of many real time systems because they are
by nature deterministics (the granularity is the longest masqued sequence in the kernel) for example Solaris is of this sort.
The other way to make real time systems is to built it on non preemptive micro kernel with very short kernel sequence (eg : mach 2.0..). This is the non-monolithic approch.
-------------------------------------------------------------------
Name : JACQUINOT
First_Name : Eric
Room_Number : A2043
Phone_Number : 73360
Date : 09/02/95
Status : Working
Mail_Address : jacquino
Station_Name : c2s16
Station_Type : SparcStation ELC
Personnal_Phone :
-------------------------------------------------------------------
Mark M. Thiehatten
: In article <3sht67$m...@comma.rhein.de> mle...@comma.rhein.de (Michael van Elst) writes:
: >In <3sggvb$t...@wolfe.wimsey.com> s...@whiskey.wimsey.com (Stuart Lynne) writes:
: >
: >
: >As soon as a process runs in the kernel it cannot be preempted.
: >Preemption just takes place in user mode.
: >
: The kernel must NOT be preempted!
Yes, it should be!
Just not always and in every place.
: What if you preempt the buffer routine
: for serial ops? DATA IS LOST! What if you preempt the disk between seek
: and write? VERY POSSIBLE data corruption! What if you preempt the interrupt
: routines? HIGHLY unreliable operation! SOMEBODY HAS to be in charge!
Some low-level routines should not be preempted, but that doesn't mean
nothing in the kernel can be preempted!
: Check ANY computer, and you will find that the low level routines are NEVER
: preempted! BTW some routines are HIGHLY time dependant. Two accesses must
: be made in sequence within a given time. Failure to do so means it will be
: unreliable or simply not work.
Indeed, low-level routines are not interrupted, but what about the file-system
code, just to name an example. It can safely be interrupted. So can most of the
higher level routines now in the kernel. And, btw, the low-level routines should
be as short as possible, and the real work should be done on a level that allows
preemption.
Please, please, If you want to start screaming about things you don't know
enough about to say something sensible go to some other newsgroup.
Oh, and about wether or not it should be added to the linux kernel,
Lets just make it a set of patches, so who wants it can use it and
the rest won't have to worry that it might influence their performance.
Mark.
--
--
Left is the right way to go.
Nothing of the above is my opinion, nor is it the opinion of anybody else.
Any resemblance to an actual persons opinions is purely coincidental and
not intentional.
Stephen Knilans
>In article <3sduhf$t...@mo6.rc.tudelft.nl>,
>Bouwmeester <bouw...@dutian.twi.tudelft.nl> wrote:
>>In article <reiter-1906...@203.12.52.22>,
>>Peter Moulder <rei...@netspace.net.au> wrote:
>>>Linux always has done pre-emptive multitasking.
>>
>>Question: since when is the Linux kernel pre-emptive?
>
>>Traditional Unix
>>kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
>>to do so (by calling schedule()).
>
And what does "pre-emptive strike" mean? Pre-emptive means, with respect to
a multi tasking O/S, that a regularly scheduled interuppt is used to switch
tasks! Thus, CICS and the older MS/WINDOWS products are NOT pre-emptive.
They use a given routine to provide task switching and thus allow ONE
process to hog the WHOLE machine!
VMS, UNIX, and the newer MS/WINDOWS products ARE pre-emptive! If a program
simply does a loop with NO intervening routine, the processes WILL be switched!
If you HAD to call schedule to cause preempting, you would defeat the major
benefits of pre-emptive multitasking!
Steve
Stephen Knilans
>In <3sggvb$t...@wolfe.wimsey.com> s...@whiskey.wimsey.com (Stuart Lynne) writes:
>
>
>As soon as a process runs in the kernel it cannot be preempted.
>Preemption just takes place in user mode.
>
and write? VERY POSSIBLE data corruption! What if you preempt the interrupt
routines? HIGHLY unreliable operation! SOMEBODY HAS to be in charge!
If, in a company, everyone had EQUAL priority and actions had to be started
IMMEDIATELY upon request, it is likely NOTHING would ever get done! It is
the SAME thing with a computer!
Check ANY computer, and you will find that the low level routines are NEVER
preempted! BTW some routines are HIGHLY time dependant. Two accesses must
be made in sequence within a given time. Failure to do so means it will be
unreliable or simply not work.
What if, for example, a network request came in as a prior one was being
processed on the same card? The data from the first one would be CORRUPTED!
The trick is to disable interrupts(check it out, all computers have that
instruction, if they ever allow them!), and get the process over with ASAP!
Steve
Michael van Elst
>Cant you guys come up with something better than the
>"Is Not!"
>"Is Too!"
>"Is NOT!"
>arguments?
As soon as arguments are replaced by insults there is little chance.
"Just say NO" - How many people follow that advice ?
Regards,
Michael van Elst
>>>Traditional Unix
>>>kernel are *ALL* non-pre-emptive. A task is only pre-empted when it allows
>>>to do so (by calling schedule()).
>They use a given routine to provide task switching and thus allow ONE
>process to hog the WHOLE machine!
Indeed.
>VMS, UNIX, and the newer MS/WINDOWS products ARE pre-emptive! If a program
>simply does a loop with NO intervening routine, the processes WILL be switched!
>If you HAD to call schedule to cause preempting, you would defeat the major
>benefits of pre-emptive multitasking!
The point is that UNIX does not preempt tasks always. If a task executes
a kernel function (syscall) it is not preempted but has to voluntarily
give up the CPU (with schedule() or derived functions) or it has to
leave the kernel.
This is important when too much time is spent in kernel functions to
answer requests in time. Many machines are fast enough so that you
do not see this effect. It becomes an issue if communication is a big
part of the application.
Michael van Elst
>>As soon as a process runs in the kernel it cannot be preempted.
>>Preemption just takes place in user mode.
>>
>The kernel must NOT be preempted!
The current kernel can't be preempted.
>What if you preempt the buffer routine for serial ops? DATA IS LOST!
>What if you preempt the disk between seek and write? VERY POSSIBLE
>data corruption! What if you preempt the interrupt
>routines? HIGHLY unreliable operation! SOMEBODY HAS to be in charge!
Indeed. If you just allow preemption in the current kernel design then
nothing would work. The solution is to lock data structures (or use
a manager task, but that's probably too far away from a UNIX kernel).
>Check ANY computer, and you will find that the low level routines are NEVER
>preempted!
Yes, but how low-level ? The UNIX kernel is big enough to be split into
parts (logically) that can work concurrently. It is possible to let one
task run filesystem code, another one network code, another one memory
allocation and so on. You can divide even finer. The lowest level is then
probably an access to a data structure that has to be atomic.
>BTW some routines are HIGHLY time dependant. Two accesses must
>be made in sequence within a given time.
Yes, but what about an access to the disk controller and one to the
network card ? Can these be exchanged in time ?
>What if, for example, a network request came in as a prior one was being
>processed on the same card? The data from the first one would be CORRUPTED!
No. You would halt all tasks that attempt to access the network card
(or rather the network data structures involved).
Of course you could forbid task switching generally: that's ultimatively bad.
You can forbid task switching while kernel functions are executing: reasonable.
You could also forbid task switching just to guarantee atomic functions: best.
>The trick is to disable interrupts(check it out, all computers have that
>instruction, if they ever allow them!), and get the process over with ASAP!
Oh no. Disabling interrupts is the worst thing. Even the UNIX kernel
avoids it wherever possible. Disabling interrupts would even forbid
the kernel to handle communication in time.
young a t
Jim Finnis <wh...@elf.dircon.co.uk> wrote:
>In article <DAut...@kroete2.freinet.de>,
>Erik Corry <er...@kroete2.freinet.de> wrote:
>>: Some traditions are awful, like the "text segment" full of binary data.
>>Or like saying binary when you mean machine code.
>Incidentally, what does BSS stand for? I know what it means -
>uninitialised data segment - but what the hell do the letters stand for?
BSS = Block Starts with Symbol (an old SAP pseudo-op on the 704.)
It just labels a block of data with a name, but nothing is put into
the block.
--
A.T.Young a...@mintaka.sdsu.edu
Astronomy Department
San Diego State University
San Diego CA 92182-0540
Emmanuel Charpentier
: In <3slfa3$1q...@thebes.waikato.ac.nz> hamish@hamish (Hamish Marson) writes:
: >being incompatible. In a multitasking operating system (Pick one), if
: >the system is not pre-empting then it CAN'T be real-time. Otherwise a
: >process could get the CPU and hog it, thus denying your real-time process
: >of its CPU, and hence not being real-time any more.
: That depends on what programs are allowed. A system can still be real-time
: if you can enforce a maximum run-time of each process before it goes back
: to sleep or is removed (e.g., the compiler could do this)
!!!!!!!!!!!!!! Yikes !
This is the very same problem as the "stopping problem" (i. e. will a given
Turing machine ever stop ?). This problem has been demonstrated unsolvable
by a Turing machine, therefore by any conceivable computer. Basics of
logical foudations of informatics, again ...
--
Emmanuel Charpentier
char...@bacbuc.frmug.fr.net
Felix von Leitner
>>>As soon as a process runs in the kernel it cannot be preempted.
>>>Preemption just takes place in user mode.
>>The kernel must NOT be preempted!
>The current kernel can't be preempted.
In fact, it IS preempted, by interrupts serviced by the kernel.
>>What if you preempt the buffer routine for serial ops? DATA IS LOST!
>>What if you preempt the disk between seek and write? VERY POSSIBLE
>>data corruption! What if you preempt the interrupt
>>routines? HIGHLY unreliable operation! SOMEBODY HAS to be in charge!
>Indeed. If you just allow preemption in the current kernel design then
>nothing would work. The solution is to lock data structures (or use
>a manager task, but that's probably too far away from a UNIX kernel).
That's not the solution. A manager task is in fact the greatest evil of
all times. If you think we need a preemptable kernel, go ahead ! Write
one ! And then show me that it is any good. I doubt it. And you doubt
it too, since, as you demonstrate here daily, you are one of the
greatest experts of multitasking and multithreading¸ preemptiveness and
reentrancy, you obviously MUST have the knowledge to write such a
kernel, but you do not just do it. Instead, you waste you time with us
lowly unknowing dimwits, trying to talk us into doing it.
I claim: You will demonstrate clearly that a preemptable kernel is not
only a waste of time, memory and CPU cycles for a single processor
machine, it will show a massive slowdown compared to a buffering kernel.
>>Check ANY computer, and you will find that the low level routines are NEVER
>>preempted!
>Yes, but how low-level ? The UNIX kernel is big enough to be split into
>parts (logically) that can work concurrently.
No, they can't work concurrently if you have only one CPU, and as long
as you don't have multiprocessing, even multiple processors won't help.
>It is possible to let one
>task run filesystem code, another one network code, another one memory
>allocation and so on.
... slowing down the whole bunch because of task management that would
be unnecessary without theoreticians like you. Look, you never tried
it. You just come and tell everybody this would be absolutely the
greatest thing in the world.
OS/2 does what you want. Go and switch to OS/2. Let us stay with the
efficient kernel we have.
>You can divide even finer. The lowest level is then
>probably an access to a data structure that has to be atomic.
Wow. Wonderful. Cool !
And ? What do you gain ? Even more overhead, because the kernel is
busy locking and unlocking data structures instead of doing some work.
>>BTW some routines are HIGHLY time dependant. Two accesses must
>>be made in sequence within a given time.
>Yes, but what about an access to the disk controller and one to the
>network card ? Can these be exchanged in time ?
They are already asynchronous. How often do I have to state that until
you believe me or look into the kernel sources ?
>>What if, for example, a network request came in as a prior one was being
>>processed on the same card? The data from the first one would be CORRUPTED!
>No. You would halt all tasks that attempt to access the network card
>(or rather the network data structures involved).
? Let's make a role-play.
I am the network card, you are the kernel.
I interrupt you. Some NFS client wants to open /tmp/blah.
What do you do ? You halt all other network tasks ? OK, there is none.
Now ? You suspend everything in favour of the NFS daemon.
Wow, the NFS daemon is activated, reads the UDP packet.
Before it is done, I interrupt you again. Another UDP packet from
another client came. What do you do now ? You stated above that you
halt the NFS daemon ?! Who is going to process the UDP packet now ?
>Of course you could forbid task switching generally: that's ultimatively bad.
Who wants to forbid task switching ?
>You can forbid task switching while kernel functions are executing: reasonable.
Not only resonable. Fast, easy, safe, time and space efficient, and you
avoid strange race conditions.
>You could also forbid task switching just to guarantee atomic functions: best.
You claimed that 1000 times now. Pleas demonstrate it to us. Bring me
a hacked Linux kernel, I will try it, and send you the results back.
But please, don't be disappointed that you wasted all those months.
>>The trick is to disable interrupts(check it out, all computers have that
>>instruction, if they ever allow them!), and get the process over with ASAP!
>Oh no. Disabling interrupts is the worst thing.
Did you know that interrupts are disabled implicitly when an interrupt
handler is called ?
>Disabling interrupts would even forbid the kernel to handle
>communication in time.
Not THAT again !
Please prove your point, don't just claim this and that.
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
"New versions happen." --Larry Wall
Felix von Leitner
>> This is the very same problem as the "stopping problem" (i. e. will a given
>> Turing machine ever stop ?). This problem has been demonstrated unsolvable
>> by a Turing machine, therefore by any conceivable computer. Basics of
>> logical foudations of informatics, again ...
> This is true only if self-modifying code is allowed. If the code is
>static, then the compiler can trace all possible paths of execution and
>insert sleep/halt/etc. instructions to make sure that there is no
>executable path greater than a specified length.
... slowing down the compile time by, say, 80%, and the execution time
of a given program by, say, 40% ? Oh, that's OK. We get wonderful
things ! For example, ... uh ... mhh ...
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
Fertility is hereditary. If your parents
didn't have any children, neither will you.
Christopher B. Browne
Timothy L. Nali <tn...@andrew.cmu.edu> wrote:
>Excerpts from netnews.comp.os.linux.development.system: 4-Jul-95 Re:
>preemptive multi-taskin.. by Emmanuel Charpentier@bac
>> Turing machine ever stop ?). This problem has been demonstrated unsolvable
>> by a Turing machine, therefore by any conceivable computer. Basics of
>> logical foudations of informatics, again ...
>
> This is true only if self-modifying code is allowed. If the code is
>static, then the compiler can trace all possible paths of execution and
>insert sleep/halt/etc. instructions to make sure that there is no
>executable path greater than a specified length.
>
>can still determine whether it will sleep every x seconds or not. The
>halting problem doesn't apply here since the process is never run. The
>compiler can do a static analysis of the code.
Turing's problem *does not assume* that you are using self-modifying
code.
Waving one's hands untheoretically, it should be pretty clear that
self-modifying code makes the problem *look* harder. That neither
makes it so, nor does it mean that non-self-modifying code does not
suffer from the Halting Problem.
If I put a loop into a program that depends on parameters that are
modified in *other processes,* that's certainly a place where
static analysis will fail. If I put a loop in that is sufficiently
complex that your analyzer can't handle it, then your analysis
will fail. And it won't have to be a terribly complex loop to
do the job.
If this were possible, I would think that Apple would have
spent a few million dollars developing such a compiler to prevent
all possible bugs. Programmers still have to be careful, so
evidently they didn't.
Computing theory may be a nasty course to take, and evidently
people who need it don't take it...
--
Christopher Browne - Email:<cbb...@io.org>, WWW:<http://www.io.org/~cbbrown/>
Windows 95 Alpha - Unlike Windows 3.1 users, they at least have the relief of
knowing it's not a production "Operating System"
Felix von Leitner
>In article <3sv5tn$1...@fu-berlin.de> Felix von Leitner <lei...@inf.fu-berlin.de> writes:
>>>> >I think reentrancy is necessary for a preemptive kernel.
>>
>> Yes, but that is not a requirement for a preemptive kernel.
>>"Preemptive" does not mean that you can execute the preempted kernel call
>>again, it just means you can interrupt a kernel call. Being able to
>>execute an interrupted system call again is called "reentrancy".
>>
>>>Therefore a "preemptive kernel" (according to the definition I use above)
>>>must also be reentrant.
>>
>>No.
>>
>>Felix
>If the kernel is FULLY premptable, which as I said it CAN'T, then each routine
>could be interrupted.
In fact, each routine *can* be interrupted. The interrupt handler just
can't call non-reentrant kernel routines.
The kernel is fully preemptable.
>If that happened, the interruppter COULD call the same routine.
You didn't get it. Being able to preempt something does not mean you
can also call it again ! DOS is preemptable, but not reentrant, for
example.
>Hence, it MUST use reentrant code!
No. If you want reentrancy, the code must be reentrant. If you want
preemptability, the code must be preemptable.
>Frankly, the overhead for such a system could be ENORMOUS!
Yes.
>It is my understanding that a variable that stops the task switcher upon
>using a library command would satisfy most of your requests.
Then your code is not preemptable any longer. You just made the
"kernel" smaller.
>Why not simply do it?
Hey, just do it, then you'll see why nobody did it before.
>It ought to be CHILDSPLAY!
Hey, no problem, dude, just show us what a KEWL C0D3R you are and do it.
It's all trivial, you know.
>The taskswitcher is probably easy to understand, and one command could
>be added to the library that ties in as many already do.
No prob, dude.
The point is that you don't want to halt the kernel.
>It would be ironic. Such a command would DISABLE the preempting that the
>original poster of this thread claimed was never there!
You actually got the point now !
>BTW I'd do it myself, but I am happy with the current system. I think it is
>better or equal, over all, to any system I have been on.
Equal? Equal to what?
Frankly, Linux has some problems. The scheduler is quite crappy. You
should try to work on an HP workstation once. The CPU is quite
powerful, that's true, but the scheduler is very advanced. You always
get the impression that the machine is not burdened.
Solaris has a good scheduler, too.
I thought about writing a new scheduler, but I was told that there
already are people writing a new scheduler.
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
IT is VERY IMPORTANT not to SPELL every OTHER word in UPPER CASE.
A Myles
>In article <DAut...@kroete2.freinet.de>,
>Erik Corry <er...@kroete2.freinet.de> wrote:
>>: Some traditions are awful, like the "text segment" full of binary data.
>>
>>Or like saying binary when you mean machine code.
>>
>Incidentally, what does BSS stand for? I know what it means -
>uninitialised data segment - but what the hell do the letters stand for?
>Jim
Block Started by Symbol, I think. I believe it comes from some old
IBM Fortran compiler or assembler.
Andy
Timothy L. Nali
preemptive multi-taskin.. by Emmanuel Charpentier@bac
> Michael van Elst (mle...@comma.rhein.de) wrote:
>
> : >being incompatible. In a multitasking operating system (Pick one), if
> : >the system is not pre-empting then it CAN'T be real-time. Otherwise a
> : >process could get the CPU and hog it, thus denying your real-time process
> : >of its CPU, and hence not being real-time any more.
>
> : That depends on what programs are allowed. A system can still be real-time
> : if you can enforce a maximum run-time of each process before it goes back
> : to sleep or is removed (e.g., the compiler could do this)
>
> !!!!!!!!!!!!!! Yikes !
>
> Turing machine ever stop ?). This problem has been demonstrated unsolvable
> by a Turing machine, therefore by any conceivable computer. Basics of
> logical foudations of informatics, again ...
This is true only if self-modifying code is allowed. If the code is
static, then the compiler can trace all possible paths of execution and
insert sleep/halt/etc. instructions to make sure that there is no
executable path greater than a specified length.
Assuming static code, even if the process never halts when run, you
can still determine whether it will sleep every x seconds or not. The
halting problem doesn't apply here since the process is never run. The
compiler can do a static analysis of the code.
Now, what if self modifying code is allowed?
Assuming the code can modify itself, if the process halts for all
possible combinations of inputs, then we can make sure the process
sleeps every x cycles. We can simply construct instruction traces for
all possible input combinations and search for sequences that run longer
than x seconds without sleeping and modify things accordingly. This is,
of course, VERY theoretical (i.e. not very damn practical).
Now what if self modifying code is allowed but the process doesn't halt?
In this case, it is impossible to prove that process p will never
run for more than x cycles without sleeping. The comipler can't
guarntee anything.
SO what does all this mean? The original problem was whether a
compiler could guarntee that a program that it compiled would run for no
more than x cycles without sleeping. Although the Halting problem
dictates that is impossible for the compiler to guarntee this for all
programs it compiles, the compiler can at least theoretically do it for
a large subset of all possible programs, namely those that do not have
self-modifying code or those that always halt in finite time.
In the real world, however, such processing would be expensive. It
would probably be much easier/faster to have a pre-emptive system.
_____________________________________________________________________________
Tim Nali \ "We are the music makers, and we are the dreamers of
tn...@andrew.cmu.edu \ the dreams" -Willy Wonka and the Chocolate Factory
Stephen Knilans
>>> >I think reentrancy is necessary for a preemptive kernel.
>
> Yes, but that is not a requirement for a preemptive kernel.
>"Preemptive" does not mean that you can execute the preempted kernel call
>again, it just means you can interrupt a kernel call. Being able to
>execute an interrupted system call again is called "reentrancy".
>
>>Therefore a "preemptive kernel" (according to the definition I use above)
>>must also be reentrant.
>
>No.
>
>Felix
If the kernel is FULLY premptable, which as I said it CAN'T, then each routine
could be interrupted. If that happened, the interruppter COULD call the same
routine. Failure of that routine to be reentrant would cause an improperly
initialized routine upon the call being satisfied! Hence, it MUST use
reentrant code! Frankly, the overhead for such a system could be ENORMOUS!
It is my understanding that a variable that stops the task switcher upon
using a library command would satisfy most of your requests. Why not simply
do it? It ought to be CHILDSPLAY! The taskswitcher is probably easy to
understand, and one command could be added to the library that ties in as
many already do.
It would be ironic. Such a command would DISABLE the preempting that the
original poster of this thread claimed was never there!
Stephen Knilans
Stephen Knilans
>In <stephenkD...@netcom.com> step...@netcom.com (Stephen Knilans) writes:
>
>
>>instruction, if they ever allow them!), and get the process over with ASAP!
>
>Oh no. Disabling interrupts is the worst thing. Even the UNIX kernel
>avoids it wherever possible. Disabling interrupts would even forbid
>the kernel to handle communication in time.
We really don't disagree on much, if any, of the other stuff you mentioned, when
taken as a whole. As for this? It was OBVIOUS, so I didn't bother really
stating it. The thought IS implied, however, by "get the process over with
ASAP". I should have added "and then reenable interrupts".
My point is that there is a VITAL reason for this! I saw round about code in
the 6502, and found it had a REASON! EVEN NOPS which waste time! With the
80486 and pentium, some code is added that makes the 386 SLOWER, but the others
FASTER! Likewise, the enable/disable interrupt functions serve an important
purpose, even if some doubt it.
Stephen Knilans
>In <3sna1h$m...@colossus.csl.mtu.edu> jfre...@mtu.edu (John F. Reeves) writes:
>
>That's a misconception. There is no magical 'kernel' that
>operates outside of all processes. So while a process is
>executing a system call it _is_ the kernel and it is not
>preempted because the kernel needs to keep the kernel data
>structures consistent.
>
>Regards,
>--
> Michael van Elst
AMEN to that LAST statement! I have been trying to tell a few people the SAME
thing. It is the lowest level of logic, and should be readily understood, but
some think you can interrupt interrupts till next month with NO ill effects.
BTW I once wrote a "REAL TIME" application, that wouldn't have been able to work
reliably on ANY multi tasking computer. It had to control 8 stepper motors
individually in sequence, but together in harmony. A difference in order, or
a delay of a few milliseconds, would have made it worthless! Heck, I remember
the time dependant programs I had to write on the APPLE II. The APPLE II uses
a 6502 processor. It has a 16 bit data bus, but ALL registers, INCLUDING the
address register, are 8 bit! Since the eightbit address registers are cascaded,
you may NEVER know that. Some may have had the APPLE II, adn NEVER knew it!
Just try writting a sound program, for example, and you quickly see the problem!
The infinitesimal delay caused by switching the registers causes distortion
whenever it crosses a 256 byte(8 bit) boundary! This is really no different
from an interrupt for a buffering routine on a multitasking machine.
Today, that program can be replaced by a chip to offload the work, like
SCSI devices do with THEIR work.
BTW The current definition of "REAL TIME" here seems a bit hazy. The way it
was originally related to me was that it was a system that would do something
at a PRECISE time. Hence, that chip could be told to give a motor a 1ms pulse
every 2ms for 3 minutes, and it would do PRECISELY that. If you tell a
multitasking system to do something at 4:30, it might not do it until 4:35!
Steve
Michael van Elst
>: That depends on what programs are allowed. A system can still be real-time
>: if you can enforce a maximum run-time of each process before it goes back
>: to sleep or is removed (e.g., the compiler could do this)
>!!!!!!!!!!!!!! Yikes !
>This is the very same problem as the "stopping problem" (i. e. will a given
>Turing machine ever stop ?). This problem has been demonstrated unsolvable
>by a Turing machine, therefore by any conceivable computer. Basics of
>logical foudations of informatics, again ...
Indeed. The assumption however is that the programs are arbitrary Turing
machines which might not hold. :)
You could restrict yourself to "primitiv recursive functions" (at least
that's how we called it). "while" considered harmful. :)
Regards,
--
Michael van Elst
Internet: mle...@mpifr-bonn.mpg.de mle...@serpens.rhein.de
Michael van Elst
> This is true only if self-modifying code is allowed. If the code is
>static, then the compiler can trace all possible paths of execution and
>insert sleep/halt/etc. instructions to make sure that there is no
>executable path greater than a specified length.
You are right.. I wasn't even thinking about this possibility. But
you might end with much more calls to schedule than necessary.
> In the real world, however, such processing would be expensive. It
>would probably be much easier/faster to have a pre-emptive system.
Yes, but there are systems that rely on limited languages. This is easier
to do than to verify a preemptive system.
Michael van Elst
>Waving one's hands untheoretically, it should be pretty clear that
>self-modifying code makes the problem *look* harder.
Indeed. You can write an interpreter for the machine that does not
use self-modifying code.
>That neither
>makes it so, nor does it mean that non-self-modifying code does not
>suffer from the Halting Problem.
Yes. But the halting problem assumes arbitrary code. Lets say the
compiler put a call to the scheduler after every instruction. This
ensures that the process does not run longer than the slowest
instruction.
>If I put a loop into a program that depends on parameters that are
>modified in *other processes,* that's certainly a place where
>static analysis will fail.
Fortunately we do not have to solve the halting-problem. We just
have to detect all possible loops which is possible with static
analysis.
Michael van Elst
>>The current kernel can't be preempted.
>In fact, it IS preempted, by interrupts serviced by the kernel.
Obviously it is preempted by interrupts. Obviously that's not what
we were talking about.
>>nothing would work. The solution is to lock data structures (or use
>>a manager task, but that's probably too far away from a UNIX kernel).
>That's not the solution. A manager task is in fact the greatest evil of
>all times.
It's a very modern solution. It usually suffers from overhead and
thus it is often just a thread of a larger task.
>Instead, you waste you time with us
>lowly unknowing dimwits, trying to talk us into doing it.
Don't speak for others.. they might not agree...
BTW, I am not talking anyone into doing something. At least not here.
>I claim: You will demonstrate clearly that a preemptable kernel is not
>only a waste of time, memory and CPU cycles for a single processor
>machine, it will show a massive slowdown compared to a buffering kernel.
Compared to ? Why do you think that a preemptive kernel would not
use buffering where applicable ?
>No, they can't work concurrently if you have only one CPU, and as long
>as you don't have multiprocessing, even multiple processors won't help.
Please try to understand what other people write.
"Concurrently" means that the tasks can be scheduled (and you might not
have an idea what task is running at a time).
It also means that on a multi-processor the tasks can be executed really
a the same time.
>... slowing down the whole bunch because of task management that would
>be unnecessary without theoreticians like you.
I am using a system that is quite fast. Thanks.
>Look, you never tried it.
I never tried a preemptive UNIX kernel.
>OS/2 does what you want. Go and switch to OS/2. Let us stay with the
>efficient kernel we have.
That would preclude that I buy a PC first.
>>probably an access to a data structure that has to be atomic.
>Wow. Wonderful. Cool !
Thanks for insulting me and others...
>And ? What do you gain ? Even more overhead, because the kernel is
>busy locking and unlocking data structures instead of doing some work.
Why would it be busy ? Most operations can work undisturbed, you just
lock at some entry points, the same as locking at _one_ entry point now.
But now you have more locking points, the propability of collisions is
reduced and the time a resource is locked is reduced too. That's why
it is faster.
>>Yes, but what about an access to the disk controller and one to the
>>network card ? Can these be exchanged in time ?
>They are already asynchronous. How often do I have to state that until
>you believe me or look into the kernel sources ?
How often do I have to tell you to read what others write ? The existing
kernel can only do one thing: access the disk controller or access the
network card.
>Before it is done, I interrupt you again. Another UDP packet from
>another client came. What do you do now ? You stated above that you
>halt the NFS daemon ?! Who is going to process the UDP packet now ?
I stated that ?
>>Of course you could forbid task switching generally: that's ultimatively bad.
>Who wants to forbid task switching ?
Noone. It just would be a solution to the problem.
>>You can forbid task switching while kernel functions are executing: reasonable.
>Not only resonable. Fast, easy, safe, time and space efficient, and you
>avoid strange race conditions.
Yes. But maybe not as fast as wanted. I'm not sure why it would avoid
strange race conditions more than any other locking protocol.
>>You could also forbid task switching just to guarantee atomic functions: best.
>You claimed that 1000 times now. Pleas demonstrate it to us. Bring me
>a hacked Linux kernel,
I am against "hacked" Linux kernels.
>>Oh no. Disabling interrupts is the worst thing.
>Did you know that interrupts are disabled implicitly when an interrupt
>handler is called ?
Not all interrupts.
>>Disabling interrupts would even forbid the kernel to handle
>>communication in time.
>Not THAT again !
It is something different. If you disable interrupts you even forbid
to service requests in an interrupt handler, no buffering kernel
will help you now. Instead you need buffering in the hardware.
Michael van Elst
>... slowing down the compile time by, say, 80%, and the execution time
>of a given program by, say, 40% ? Oh, that's OK. We get wonderful
>things ! For example, ... uh ... mhh ...
You did not understand that this is a theoretical example. That's
why you start insulting again.
Well, sometimes you would even prefer this method but that's unlikely
if you want to program a workstation.
Michael van Elst
>The kernel is fully preemptable.
We are talking about preemption by the scheduler.
>You didn't get it. Being able to preempt something does not mean you
>can also call it again !
If you talk about _tasks_ that are _scheduled_ this does mean the
same thing unless you limit other tasks ability to call the kernel.
Paul D. Smith
%% Felix von Leitner <lei...@inf.fu-berlin.de> writes:
fvl> Frankly, Linux has some problems. The scheduler is quite
fvl> crappy.
fvl> I thought about writing a new scheduler, but I was told that
fvl> there already are people writing a new scheduler.
Schedulers are extremely tricky: they're similar to malloc libraries in
that it's rare that one scheduler can work well for all styles of
system usage.
When I worked at Data General there was a parameter you could set in the
kernel build for DG/UX to specify whether you were working on a
"workstation" (primarily single-user where perceived user response time
was paramount) or a "server" (multi-user system where efficiency and
equal sharing of time slice was most important)... this parameter would
affect various other kernel params that would cause the scheduler
(probably among other things) to work better for that type of system.
FWIW :)
--
-------------------------------------------------------------------------------
Paul D. Smith <psm...@baynetworks.com> Network Management Development
Senior Software Engineer Bay Networks, Inc.
-----------------------------------------------==<http://www.baynetworks.com/>-
"Please remain calm...I may be mad, but I am a professional." --Mad Scientist
-------------------------------------------------------------------------------
These are my opinions--Bay Networks takes no responsibility for them.
Felix von Leitner
>>>a manager task, but that's probably too far away from a UNIX kernel).
>>That's not the solution. A manager task is in fact the greatest evil of
>>all times.
>It's a very modern solution. It usually suffers from overhead and
>thus it is often just a thread of a larger task.
Oh, it suffers from overhead, you say ? This obviously makes it *very*
different from your other suggestions ... ;*}
>>Instead, you waste you time with us
>>lowly unknowing dimwits, trying to talk us into doing it.
>Don't speak for others.. they might not agree...
>BTW, I am not talking anyone into doing something. At least not here.
You are not ? You mean, you waste weeks posting here saying "we need a
reentrant kernel" and you don't want anybody to implement it ? Why ?
>>I claim: You will demonstrate clearly that a preemptable kernel is not
>>only a waste of time, memory and CPU cycles for a single processor
>>machine, it will show a massive slowdown compared to a buffering kernel.
>Compared to ? Why do you think that a preemptive kernel would not
>use buffering where applicable ?
Because there is no situation where buffering is *not* applicable. So
there is at least one situation where you will slow the kernel down it
you modify it to be preemptive. Please go ahead.
>>No, they can't work concurrently if you have only one CPU, and as long
>>as you don't have multiprocessing, even multiple processors won't help.
>Please try to understand what other people write.
Please state correctly what you mean and don't complain that I
understand what you write instead of what you meant.
>"Concurrently" means that the tasks can be scheduled (and you might not
>have an idea what task is running at a time).
con-cur-rent \-'ker-ent, -'ke-rent\ adj
[ME, fr. MF & L; MF, fr. L concurrent-, concurrens, prp. of concurrere]
(14c)
1: operating or occurring at the same time
2a: CONVERGENT; specif : meeting or intersecting in a point
2b: running parallel
Sorry.
>>... slowing down the whole bunch because of task management that would
>>be unnecessary without theoreticians like you.
>I am using a system that is quite fast. Thanks.
Wonderful. So maybe one person will not notice the immense slowdown:
You.
>>Look, you never tried it.
>I never tried a preemptive UNIX kernel.
So please go ahead and try one. Then you'll hopefully no longer want to
change the Linux kernel.
>>OS/2 does what you want. Go and switch to OS/2. Let us stay with the
>>efficient kernel we have.
>That would preclude that I buy a PC first.
You mean you don't have a PC but you are talking about the Linux kernel
with us ? You mean you want us to slow down the Linux kernel and you
are not even using it ? Oh, now I understand your motives, you are an
IRIX user and are jealous of Linux' speed and now you think you found a
way to slow Linux down ;)))
>>>probably an access to a data structure that has to be atomic.
>>Wow. Wonderful. Cool !
>Thanks for insulting me and others...
Insulting ? I did not insult anybody.
>>And ? What do you gain ? Even more overhead, because the kernel is
>>busy locking and unlocking data structures instead of doing some work.
>Why would it be busy ?
You mean the CPU can do all the management without being busy sometimes?
Hey, you seem to be a magician ! Cool ! Please implement it ! I'm
very interested in seeing your code !
>Most operations can work undisturbed, you just
>lock at some entry points, the same as locking at _one_ entry point now.
>But now you have more locking points, the propability of collisions is
>reduced and the time a resource is locked is reduced too. That's why
>it is faster.
Again, this has never been demonstrated before, and if you think you can
do it, please go ahead. I claim the kernel is faster now than your
kernel will be. Go ahead and prove me wrong.
>>>Yes, but what about an access to the disk controller and one to the
>>>network card ? Can these be exchanged in time ?
>>They are already asynchronous. How often do I have to state that until
>>you believe me or look into the kernel sources ?
>How often do I have to tell you to read what others write ? The existing
>kernel can only do one thing: access the disk controller or access the
>network card.
Because others wrote it (which they didn't) this need not be right. In
fact, it isn't.
>>Before it is done, I interrupt you again. Another UDP packet from
>>another client came. What do you do now ? You stated above that you
>>halt the NFS daemon ?! Who is going to process the UDP packet now ?
>I stated that ?
Yes. If you had quoted the lines I quoted to prove this point, you'd
see yourself.
>>>You can forbid task switching while kernel functions are executing: reasonable.
>>Not only resonable. Fast, easy, safe, time and space efficient, and you
>>avoid strange race conditions.
>Yes. But maybe not as fast as wanted. I'm not sure why it would avoid
>strange race conditions more than any other locking protocol.
Why don't you just stop claiming this and ultimately prove all of us
stupid and wrong. Just go ahead and show me ONE kernel which showed a
speed-up on a single processor machine.
>>>You could also forbid task switching just to guarantee atomic functions: best.
>>You claimed that 1000 times now. Pleas demonstrate it to us. Bring me
>>a hacked Linux kernel,
>I am against "hacked" Linux kernels.
That's what you want from us all the time ! Oh, if you want to, you can
spend as much time as you want changing the kernel the way you described
here time after time.
>>>Oh no. Disabling interrupts is the worst thing.
>>Did you know that interrupts are disabled implicitly when an interrupt
>>handler is called ?
>Not all interrupts.
So what ?
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
A conference is a gathering of important people who singly can
do nothing but together can decide that nothing can be done.
--Fred Allen
Felix von Leitner
>We are talking about preemption by the scheduler.
>>You didn't get it. Being able to preempt something does not mean you
>>can also call it again !
>If you talk about _tasks_ that are _scheduled_ this does mean the
>same thing unless you limit other tasks ability to call the kernel.
Oh, sure, if *YOU* talk about tasks that are scheduled, all the words
mean something different. No problem. Since you are a known expert on
this topic, wen you and the literature differ, you are right.
So please accept my apologies if I ever assumed that the literature was
right. So sorry.
Felix
--------====### legal notice ###====-------------------------------------------
Microsoft Network is prohibited from redistributing this work in any form, in
whole or in part. License to distribute this post is available to Microsoft
for $499. Posting without permission constitutes an agreement to these terms.
--
"... an initial underscore already conveys strong feelings of
magicalness to a C programmer."
-- Larry Wall in <1992Nov9.1...@netlabs.com>