|
Home > Archive > Unix Shell > November 2006 > Name of the scheduler process/daemon?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Name of the scheduler process/daemon?
|
|
| Olumide 2006-11-14, 7:24 pm |
| What's the scheduler process/daemon called on UNIX and UNIX-like
systems?
Thanks,
- Olumide
| |
| Olumide 2006-11-14, 7:24 pm |
| > What's the scheduler process/daemon called on UNIX and UNIX-like
> systems?
I mean the name of the CPU scheduler.
| |
| Olumide 2006-11-14, 7:24 pm |
|
Olumide wrote:[vbcol=seagreen]
This is fast turning into a monologue :-D , but I need to add that I'm
aware that the process 0, commonly known as the swapper, is sometimes
called the scheduler, but it seems to me that the swapper is a memory
management deamon, and not the CPU scheduler. Or does the swapper
perform both tasks?
Thanks.
- Olumide
| |
| Bill Marcum 2006-11-14, 7:24 pm |
| ["Followup-To:" header set to comp.unix.shell.]
On 14 Nov 2006 14:56:27 -0800, Olumide
<50295@web.de> wrote:
>
> I mean the name of the CPU scheduler.
>
The scheduler is built into the kernel.
--
does your DRESSING ROOM have enough ASPARAGUS?
| |
| Random832 2006-11-14, 7:24 pm |
| 2006-11-14 <1163544870.077732.133710@b28g2000cwb.googlegroups.com>,
Olumide wrote:
> What's the scheduler process/daemon called on UNIX and UNIX-like
> systems?
On many systems, it's called "unix" or "vmunix" - on linux systems it's
called "vmlinux" or "vmlinuz". on mac os x, it's called "mach_kernel".
| |
| Olumide 2006-11-14, 7:24 pm |
|
Bill Marcum wrote:
> ...
> The scheduler is built into the kernel.
So, its a OS routine, but within the context of which process does the
scheduler normally run? Interrupt handlers? (they too will require an
existing context to be efficient), or is it that the scheduler routine
is run whenever the a process enters the kernel or is about to leave
it? :-S
- Olumide
| |
| Olumide 2006-11-14, 7:24 pm |
| Bill Marcum wrote:
> ...
> The scheduler is built into the kernel.
So, its a OS routine, but within the context of which process does the
scheduler normally run?
Interrupt handlers? (they too will require an existing context to be
efficient), or is it that the scheduler routine is run whenever the a
process enters the kernel or is about to leave
it? :-S
- Olumide
| |
| Olumide 2006-11-14, 7:24 pm |
|
Random832 wrote:
> 2006-11-14 <1163544870.077732.133710@b28g2000cwb.googlegroups.com>,
> Olumide wrote:
>
> On many systems, it's called "unix" or "vmunix" - on linux systems it's
> called "vmlinux" or "vmlinuz". on mac os x, it's called "mach_kernel".
Isn't vmlinuz/vmlinux the name of the executable that contains the
Linux kernel?
(See http://en.wikipedia.org/wiki/Vmlinux)
| |
| Random832 2006-11-14, 7:24 pm |
| 2006-11-14 <1163547932.122990.221270@m7g2000cwm.googlegroups.com>,
Olumide wrote:
>
> Bill Marcum wrote:
>
> So, its a OS routine, but within the context of which process does the
> scheduler normally run? Interrupt handlers? (they too will require an
> existing context to be efficient), or is it that the scheduler routine
> is run whenever the a process enters the kernel or is about to leave
> it? :-S
I think that the scheduler is something that is called by a timer
interrupt. In that case, it would run, I believe, in the 'context' of
the previous process, like any interrupt handler.
Now, obviously, if a process makes a system call and has to wait
(block), the next ready process will be given control immediately.
| |
| Random832 2006-11-14, 7:24 pm |
| 2006-11-14 <1163548383.432032.214430@i42g2000cwa.googlegroups.com>,
Olumide wrote:
>
> Random832 wrote:
>
> Isn't vmlinuz/vmlinux the name of the executable that contains the
> Linux kernel?
That was rather my point. Incidentally, this discussion probably doesn't
belong in comp.unix.shell - followups set.
| |
| Garry Tittle 2006-11-14, 7:24 pm |
| Olumide wrote:
> Random832 wrote:
>
>
>
> Isn't vmlinuz/vmlinux the name of the executable that contains the
> Linux kernel?
> (See http://en.wikipedia.org/wiki/Vmlinux)
>
One last attempt to answer this question:
Consider your brain. It is booted and running at all times, even when
you are sleeping. You can't see it running, but surely it must be. If
you talk, swim, read, eat, and more, those are peripheral tasks that
have a process that we can see. We don't/can't see your brain function
while you do these.
The UNIX developers realized that some folks really shouldn't be given
the keys to the car. So, the kernel boots and sits in kernel memory.
It does whatever it is asked to do with no thanks required.
Think about it for a moment. On the face of the Earth, there is at
least one dummy who would try to stop the scheduler if he could; this is
much like those that climb Mount Everest just because it is there.
Accept that the kernel is present, running, and does not need anyone's
assistance. When you do a "ps" command, you are allowed to see some of
what it is doing for you.
..
..
| |
| Olumide 2006-11-15, 1:30 am |
|
Garry Tittle wrote:
> One last attempt to answer this question:
>
> Consider your brain. It is booted and running at all times, even when
> you are sleeping. You can't see it running, but surely it must be. If
> you talk, swim, read, eat, and more, those are peripheral tasks that
> have a process that we can see. We don't/can't see your brain function
> while you do these.
>
> The UNIX developers realized that some folks really shouldn't be given
> the keys to the car. So, the kernel boots and sits in kernel memory.
> It does whatever it is asked to do with no thanks required.
>
> Think about it for a moment. On the face of the Earth, there is at
> least one dummy who would try to stop the scheduler if he could; this is
> much like those that climb Mount Everest just because it is there.
>
> Accept that the kernel is present, running, and does not need anyone's
> assistance. When you do a "ps" command, you are allowed to see some of
> what it is doing for you.
> .
> .
In that case, someone ought to shut down comp.unix.internals
| |
| Kaz Kylheku 2006-11-15, 1:30 am |
| Olumide wrote:
> What's the scheduler process/daemon called on UNIX and UNIX-like
> systems?
The scheduler is a function in the kernel. A scheduling decision occurs
when that function is run. It is always run in the context of some
process, either voluntarily (the process invokes the scheduler as a
service, either directly, or implicitly as part of some other action
such as I/O) or involuntarily (a hardware interrupt occurs in the
middle of the process, and the handler decides that a scheduling
decision should be made, and invokes the scheduler).
The scheduler function parks the current task into a suspended state,
remembering all of the information needed to resume the task. It then
chooses a new task from anong the runnable ones and changes context to
it. To the resumed task, it then "magically" appears as if it just
returned from the original call it made to the scheduler.
On SMP systems, the scheduler can be called by any processor, and
chooses a process that will execute next on that same processor.
It simply doesn't make much sense to implement the scheduler as a
daemon. How would that work? The daemon would be suspended in a run
queue while another task runs. When it would come to make a scheduling
decision to run a different task, how would the scheduler task be
activated? A scheduler is needed to activate a task. How can it
activate itself if it is suspended?
However, long-term schedulers for running batch jobs are implemented as
daemons. The prime example of that is the cron daemon, which schedules
programs to run at specified times, on behalf of specified users.
| |
| Kaz Kylheku 2006-11-15, 1:30 am |
|
Olumide wrote:
> Bill Marcum wrote:
>
> So, its a OS routine, but within the context of which process does the
> scheduler normally run?
Within any process context that is used to invoke it.
> Interrupt handlers? (they too will require an
> existing context to be efficient), or is it that the scheduler routine
Interrupt handlers borrow the context of whatever they interrupted.
There are typically special rules for calling the scheduler from an
interrupt; for instance, it might only be allowed when returning from
the topmost interrupt nesting level. (Remember, interrupt handlers may
be interrupted!)
Not all interrupts call for a scheduling decision. A timer interrupt
might decrement the time quantum of the task which is running on the
same processor that is handling the interrupt. Only when that quantum
reaches zero will the interrupt will set a "scheduling decision
needed!" flag. As the kernel is returning from the outer-most nesting
level of interrupt handling, it can check the flag and call the
scheduler. The scheduler can park the current task and pick another
one. When the return from the kernel is executed, it will go to the
newly dispatched task, which will think that it just returned from the
original system call or event which interrupted it.
So in this indirect way, an interrupt service routine can request that
the scheduler be run, even though it's not allowed to actually make
that call directly itself.
On Linux for instance, a panic error message will result if the
scheduler is called from an interrupt handler. This typically happens
when someone mistakenly writes an handler which calls code that might
sleep: non-atomic memory allocation, blocking IPC, acquisition of
``long'' locks, etc.
| |
| Olumide 2006-11-15, 1:20 pm |
| Kaz Kylheku wrote:
> Olumide wrote:
> ...
> It simply doesn't make much sense to implement the scheduler as a
> daemon. How would that work? The daemon would be suspended in a run
> queue while another task runs. When it would come to make a scheduling
> decision to run a different task, how would the scheduler task be
> activated? A scheduler is needed to activate a task. How can it
> activate itself if it is suspended?
>
> However, long-term schedulers for running batch jobs are implemented as
> daemons. The prime example of that is the cron daemon, which schedules
> programs to run at specified times, on behalf of specified users.
'Makes sense. Thank you Kaz.
| |
| Olumide 2006-11-15, 1:20 pm |
| Kaz Kylheku wrote:
> The scheduler is a function in the kernel. A scheduling decision occurs
> when that function is run. It is always run in the context of some
> process, either voluntarily (the process invokes the scheduler as a
> service, either directly, or implicitly as part of some other action
> such as I/O) or involuntarily (a hardware interrupt occurs in the
> middle of the process, and the handler decides that a scheduling
> decision should be made, and invokes the scheduler).
'Just wondering. In what context of which process does do interrupts
(often) run?
Postscript:
My original question was inspired an OS text which claims that on some
UNIX-like OSs, the scheduler is implemented as kernel level processes
which is run between other processes. If I recall correctly, the text
even went as far as claiming that this process is the idle process. I
no longer think this is true, because how and why would a scheduler
need to run in an endless loop as the idle process does, if it did, it
would be hard to make this idling scheduler process give up the CPU ...
| |
| Olumide 2006-11-16, 1:30 am |
| Olumide wrote:
> Postscript:
> My original question was inspired an OS text which claims that on some
> UNIX-like OSs, the scheduler is implemented as kernel level processes
> which is run between other processes. If I recall correctly, the text
> even went as far as claiming that this process is the idle process. ...
Aha ... the text is, Operating Systems Principles by Lubomir F. Bic,
and Alan C. Shaw (ISBN 0-13-122455-7, Prentice Hall, 2003), page 149:
Quote:
"... UNIX is an example of a system where the scheduler (dispatcher) is
a separate process. It runs every other time, i.e., between any two
processes. It also serves as the "dummy" or idle process which runs
when no other process is ready ..."
Which version of UNIX does this, I'll like to know.
| |
| Michael Quinlivan 2006-11-16, 7:29 am |
|
Olumide wrote:
> Olumide wrote:
>
> Aha ... the text is, Operating Systems Principles by Lubomir F. Bic,
> and Alan C. Shaw (ISBN 0-13-122455-7, Prentice Hall, 2003), page 149:
>
> Quote:
> "... UNIX is an example of a system where the scheduler (dispatcher) is
> a separate process. It runs every other time, i.e., between any two
> processes. It also serves as the "dummy" or idle process which runs
> when no other process is ready ..."
>
> Which version of UNIX does this, I'll like to know.
I don't understand how this could possibly work. The scheduler
schedules processes. So who schedules the scheduler (which is a
process). At some point (in a truly preemptive system), the scheduler
must be activated by a hardware clock interrupt, in order to maintain
the quanta of time allocated to a process.
MQ
| |
| Bruce Barnett 2006-11-16, 7:29 am |
| "Michael Quinlivan" <michaelquinlivan@gmail.com> writes:
> I don't understand how this could possibly work. The scheduler
> schedules processes. So who schedules the scheduler (which is a
> process). At some point (in a truly preemptive system), the scheduler
> must be activated by a hardware clock interrupt, in order to maintain
> the quanta of time allocated to a process.
It might be that the scheduler has a special UID that is never swapped out.
I vaguely recall special low-ID processes in early Unix systems.
Does this sound familiar for the UID numbers?
0 - Scheduler
1 - Init
2 - Sync
I can check my old UNIX internals book Monday.
--
Sending unsolicited commercial e-mail to this account incurs a fee of
$500 per message, and acknowledges the legality of this contract.
| |
| Random832 2006-11-16, 7:29 am |
| 2006-11-16 <yek1wo3mx4n.fsf@grymoire.com>,
Bruce Barnett wrote:
> "Michael Quinlivan" <michaelquinlivan@gmail.com> writes:
>
>
> It might be that the scheduler has a special UID that is never swapped out.
>
> I vaguely recall special low-ID processes in early Unix systems.
> Does this sound familiar for the UID numbers?
I assume you mean PID
> 0 - Scheduler
> 1 - Init
> 2 - Sync
I've never heard of a pid 0. init and syncd are userspace processes (all
syncd does is call sync() over and over, it doesn't actually do any of
the actual work of sync'ing.)
> I can check my old UNIX internals book Monday.
| |
| Casper H.S. Dik 2006-11-16, 1:17 pm |
| Random832 <random@random.yi.org> writes:
>I've never heard of a pid 0. init and syncd are userspace processes (all
>syncd does is call sync() over and over, it doesn't actually do any of
>the actual work of sync'ing.)
Solaris (and presumably SysVr4) has a process 0 called "sched".
But as far as I know, it's merely a place holder for kernel threads
and have nothing to do with scheduling proper.
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
| |
| Olumide 2006-11-16, 1:17 pm |
|
Michael Quinlivan wrote:
> Olumide wrote:
>
> I don't understand how this could possibly work. The scheduler
> schedules processes. So who schedules the scheduler (which is a
> process). At some point (in a truly preemptive system), the scheduler
> must be activated by a hardware clock interrupt, in order to maintain
> the quanta of time allocated to a process.
I suppose the scheduler will have to be woken up when:
- The currently running process terminates
- The currently running process blocks
- The currently running process forks
- An interrupt occours
- The clock interrupt occours
At least this is what the text suggests (I'd quote it again, but I
don't have the book here). This seems workable, provided the scheduler
process is never swapped out -- I think.
| |
| Olumide 2006-11-16, 1:17 pm |
| Casper H. S. Dik wrote:
> Random832 <random@random.yi.org> writes:
>
>
> Solaris (and presumably SysVr4) has a process 0 called "sched".
>
> But as far as I know, it's merely a place holder for kernel threads
> and have nothing to do with scheduling proper.
'Just speculating, but couldn't the scheduler (and the interrupt
handler) be one of such kernel threads? Oh well ...
| |
| Barry Margolin 2006-11-17, 1:25 am |
| In article <1163674583.723276.128540@h54g2000cwb.googlegroups.com>,
"Michael Quinlivan" <michaelquinlivan@gmail.com> wrote:
> Olumide wrote:
>
> I don't understand how this could possibly work. The scheduler
> schedules processes. So who schedules the scheduler (which is a
> process). At some point (in a truly preemptive system), the scheduler
> must be activated by a hardware clock interrupt, in order to maintain
> the quanta of time allocated to a process.
I think what's actually going on is that it's the scheduler's job to
decide which process should be scheduled, while it's still the kernel's
job to actually load the selected process onto the CPU. The kernel
still needs to treat the scheduler process specially, since it gets
loaded automatically whenever it's necessary to make a scheduling
decision, or when there are no runnable processes.
--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
| |
| Kaz Kylheku 2006-11-17, 7:30 am |
| Olumide wrote:
> Olumide wrote:
>
> Aha ... the text is, Operating Systems Principles by Lubomir F. Bic,
> and Alan C. Shaw (ISBN 0-13-122455-7, Prentice Hall, 2003), page 149:
> Quote:
> "... UNIX is an example of a system where the scheduler (dispatcher) is
> a separate process. It runs every other time, i.e., between any two
> processes. It also serves as the "dummy" or idle process which runs
> when no other process is ready ..."
>
> Which version of UNIX does this, I'll like to know.
As anyone writing an OS textbook should know by now that these days,
Unix isn't an operating system but the name of a specification for the
features of a family of operating systems. Its name is no longer
written in upper case either.
The Unix specification does not stipulate the internal workings of the
scheduler. So, strictly speaking, it is not possible to write a correct
sentence which asserts that the Unix scheduler is this way or that way.
You can only make such factual statements about a Unix implementation.
I suspect that what they describe isn't a common implementation
technique. But yes, it is certainly possible.
You see, a scheduler is not needed in order to implement task
switching. It's possible for a task to context switch to another
specific task. A scheduler just does this in a more fancy way: it
executes an algorithm to decide from among a set of tasks. You could
take all those pieces out of a scheduler and hack it down to a
"context_switch(old_task, new_task)" routine, where the new task is
somehow determined externally. Some multithreading systems are based
on such explicit "coroutine" switching.
So yes indeed, a scheduling function could be split up into a small
context switching stub and a scheduling task. The job of the stub is
simply to context switch to the scheduling task which has a well-known
identity in the system (and like the idle task, there would be one of
these per processor: every processor knows how to locate /its/
suspended scheduler task).
Now the scheduling task is activated. Inside that task, the scheduling
dispatch appears as a magic return from the context switch function.
The scheduler ran that function the last time it chose a process to
run, by context switching to it. Now it is returning from that function
and has to choose another process from among the runnable ones:
scheduler_task_function()
{
for (;;) {
task next = choose_next(all_runnable);
context_switch(self, next);
}
}
Now the entire body of the loop runs to completion; the scheduler task
cannot be preempted. That would be disastrous, because only the
scheduler can determine the next task to run. If the scheduler can't be
preempted, then this problem can't happen. The scheduler can't block on
anything. (It's starting to sound like the idle task, isn't it!)
And so the schedule function reduces to this logic:
schedule_function()
{
context_switch(self, scheduler_task[current_cpu]);
}
In other words, ``deactivate the current task and dispatch the
scheduler.'' The scheduler then returns from the context_switch()
function call, and returns to the top of the loop, where it calls
choose_next() to pick the next process to run.
It should be obvious that the scheduler_task_function can actually
double as the idle task also. The idle task runs when no other tasks
are runnable (or when all runnable tasks are already running on other
CPU's). When the idle task is the only runnable task, what does it
do? It is the only element in the "all_runnable" set and so the
choose_next function, guess what, returns the idle task itself. The
idle task thus calls context_switch(self, self) which is a noop, and so
it immediately returns to the top of the loop.
How is the CPU wrestled away from the idle task? Simple; some interrupt
goes off, and marks a task as runnable. For instance, some I/O
completes, and the completion interrupt wakes up a blocked process. The
idle/scheduler task is somewhere in the middle of executing
choose_next(), context_switch() or the body of its loop. Eventually it
will enter the choose_next() function again and find that the set now
contains itself as well as another task. Since the newly runnable task
has a higher priority than the idle task (as all tasks do) the
choose_next() function will pick that task, and the scheduler will
context switch to it.
A possible thing about this implementation is that because the job of
scheduling is attached to its own process, information can be gathered
about it quite readily. It can be shown in the list of processes, along
with how much time is being spent in it instantaneously and
cumulatively. When clock tick interrupts happen, they can update the
process times of the scheduler just as any other task, allowing it to
be profiled easily.
| |
| Kaz Kylheku 2006-11-17, 7:30 am |
| Olumide wrote:
> Olumide wrote:
>
> Aha ... the text is, Operating Systems Principles by Lubomir F. Bic,
> and Alan C. Shaw (ISBN 0-13-122455-7, Prentice Hall, 2003), page 149:
> Quote:
> "... UNIX is an example of a system where the scheduler (dispatcher) is
> a separate process. It runs every other time, i.e., between any two
> processes. It also serves as the "dummy" or idle process which runs
> when no other process is ready ..."
>
> Which version of UNIX does this, I'll like to know.
As anyone writing an OS textbook should know by now that these days,
Unix isn't an operating system but the name of a specification for the
features of a family of operating systems.
The Unix specification does not stipulate the internal workings of the
scheduler. So, strictly speaking, it is not possible to write a correct
sentence which asserts that the Unix scheduler is this way or that way.
You can only make such factual statements about a Unix implementation.
I suspect that what they describe isn't a common implementation
technique. But yes, it is certainly possible.
You see, a scheduler is not needed in order to implement task
switching. It's possible for a task to context switch to another
specific task. A scheduler just does this in a more fancy way: it
executes an algorithm to decide from among a set of tasks. You could
take all those pieces out of a scheduler and hack it down to a
"context_switch(old_task, new_task)" routine, where the new task is
somehow determined externally. Some multithreading systems are based
on such explicit "coroutine" switching.
So yes indeed, a scheduling function could be split up into a small
context switching stub and a scheduling task. The job of the stub is
simply to context switch to the scheduling task which has a well-known
identity in the system (and like the idle task, there would be one of
these per processor: every processor knows how to locate /its/
suspended scheduler task).
Now the scheduling task is activated. Inside that task, the scheduling
dispatch appears as a magic return from the context switch function.
The scheduler ran that function the last time it chose a process to
run, by context switching to it. Now it is returning from that function
and has to choose another process from among the runnable ones:
scheduler_task_function()
{
for (;;) {
task next = choose_next(all_runnable);
context_switch(self, next);
}
}
Now the entire body of the loop runs to completion; the scheduler task
cannot be preempted. That would be disastrous, because only the
scheduler can determine the next task to run. If the scheduler can't be
preempted, then this problem can't happen. The scheduler can't block on
anything. (It's starting to sound like the idle task, isn't it!)
And so the schedule function reduces to this logic:
schedule_function()
{
context_switch(self, scheduler_task[current_cpu]);
}
In other words, ``deactivate the current task and dispatch the
scheduler.'' The scheduler then returns from the context_switch()
function call, and returns to the top of the loop, where it calls
choose_next() to pick the next process to run.
It should be obvious that the scheduler_task_function can actually
double as the idle task also. The idle task runs when no other tasks
are runnable (or when all runnable tasks are already running on other
CPU's). When the idle task is the only runnable task, what does it
do? It is the only element in the "all_runnable" set and so the
choose_next function, guess what, returns the idle task itself. The
idle task thus calls context_switch(self, self) which is a noop, and so
it immediately returns to the top of the loop.
How is the CPU wrestled away from the idle task? Simple; some interrupt
goes off, and marks a task as runnable. For instance, some I/O
completes, and the completion interrupt wakes up a blocked process. The
idle/scheduler task is somewhere in the middle of executing
choose_next(), context_switch() or the body of its loop. Eventually it
will enter the choose_next() function again and find that the set now
contains itself as well as another task. Since the newly runnable task
has a higher priority than the idle task (as all tasks do) the
choose_next() function will pick that task, and the scheduler will
context switch to it.
A possible thing about this implementation is that because the job of
scheduling is attached to its own process, information can be gathered
about it quite readily. It can be shown in the list of processes, along
with how much time is being spent in it instantaneously and
cumulatively. When clock tick interrupts happen, they can update the
process times of the scheduler just as any other task, allowing it to
be profiled easily.
| |
| Old Man 2006-11-17, 1:22 pm |
| Kaz Kylheku wrote:
> Olumide wrote:
>
>
>
>
>
> As anyone writing an OS textbook should know by now that these days,
> Unix isn't an operating system but the name of a specification for the
> features of a family of operating systems.
>
> The Unix specification does not stipulate the internal workings of the
> scheduler. So, strictly speaking, it is not possible to write a correct
> sentence which asserts that the Unix scheduler is this way or that way.
> You can only make such factual statements about a Unix implementation.
>
> I suspect that what they describe isn't a common implementation
> technique. But yes, it is certainly possible.
>
> You see, a scheduler is not needed in order to implement task
> switching. It's possible for a task to context switch to another
> specific task. A scheduler just does this in a more fancy way: it
> executes an algorithm to decide from among a set of tasks. You could
> take all those pieces out of a scheduler and hack it down to a
> "context_switch(old_task, new_task)" routine, where the new task is
> somehow determined externally. Some multithreading systems are based
> on such explicit "coroutine" switching.
>
> So yes indeed, a scheduling function could be split up into a small
> context switching stub and a scheduling task. The job of the stub is
> simply to context switch to the scheduling task which has a well-known
> identity in the system (and like the idle task, there would be one of
> these per processor: every processor knows how to locate /its/
> suspended scheduler task).
>
> Now the scheduling task is activated. Inside that task, the scheduling
> dispatch appears as a magic return from the context switch function.
> The scheduler ran that function the last time it chose a process to
> run, by context switching to it. Now it is returning from that function
> and has to choose another process from among the runnable ones:
>
> scheduler_task_function()
> {
> for (;;) {
> task next = choose_next(all_runnable);
> context_switch(self, next);
> }
> }
>
> Now the entire body of the loop runs to completion; the scheduler task
> cannot be preempted. That would be disastrous, because only the
> scheduler can determine the next task to run. If the scheduler can't be
> preempted, then this problem can't happen. The scheduler can't block on
> anything. (It's starting to sound like the idle task, isn't it!)
>
> And so the schedule function reduces to this logic:
>
> schedule_function()
> {
> context_switch(self, scheduler_task[current_cpu]);
> }
>
> In other words, ``deactivate the current task and dispatch the
> scheduler.'' The scheduler then returns from the context_switch()
> function call, and returns to the top of the loop, where it calls
> choose_next() to pick the next process to run.
>
> It should be obvious that the scheduler_task_function can actually
> double as the idle task also. The idle task runs when no other tasks
> are runnable (or when all runnable tasks are already running on other
> CPU's). When the idle task is the only runnable task, what does it
> do? It is the only element in the "all_runnable" set and so the
> choose_next function, guess what, returns the idle task itself. The
> idle task thus calls context_switch(self, self) which is a noop, and so
> it immediately returns to the top of the loop.
>
> How is the CPU wrestled away from the idle task? Simple; some interrupt
> goes off, and marks a task as runnable. For instance, some I/O
> completes, and the completion interrupt wakes up a blocked process. The
> idle/scheduler task is somewhere in the middle of executing
> choose_next(), context_switch() or the body of its loop. Eventually it
> will enter the choose_next() function again and find that the set now
> contains itself as well as another task. Since the newly runnable task
> has a higher priority than the idle task (as all tasks do) the
> choose_next() function will pick that task, and the scheduler will
> context switch to it.
>
> A possible thing about this implementation is that because the job of
> scheduling is attached to its own process, information can be gathered
> about it quite readily. It can be shown in the list of processes, along
> with how much time is being spent in it instantaneously and
> cumulatively. When clock tick interrupts happen, they can update the
> process times of the scheduler just as any other task, allowing it to
> be profiled easily.
>
It seems that the concepts of the run queue, wait queue, the priority,
the "nice" factor, and above all, the OS "tick" (usually 1/100th or
1/60th of a second) has been totally ignored for the sake of astute
conversation. Based upon everything in the queues, a job goes on the
run queue for a "tick", then it goes off, of course, that is based upon
the calculations returned from the priorities and the nice guy gets more
time concepts.
Old Man
| |
| Kaz Kylheku 2006-11-17, 7:23 pm |
| Old Man wrote:
> conversation. Based upon everything in the queues, a job goes on the
> run queue for a "tick", then it goes off
Only if its time quantum is just one tick.
| |
| Philippe Amarenco 2006-11-27, 1:18 pm |
| "Olumide" <50295@web.de> writes:
> Casper H. S. Dik wrote:
>
> 'Just speculating, but couldn't the scheduler (and the interrupt
> handler) be one of such kernel threads? Oh well ...
what you have to realize is that a kernel actually implements 2
virtual machines:
- 1 called Virtual Memory that virtualize memory ressources and
conceptually allows you to do a "new RAM;" (as C++'s new a RAM an
object)
- 1 called multithreading that virtualze the execution ressources and
conceptually allows you to do a "new CPU;"
- a unix process is a pair (cpu, ram).
at any point of time, a processor runs only 1 process and the
sequencer is here to switch between processes (cpu and ram). The
scheduler only decides which is next.
so in fact, from a hardware point of view, a processor only runs 1
process, it is just the kernel that virtualize ressources to
user-space part of the virtual process.
interrupts are only directed to the process seen by hardware, the only
that is piloted by your kernel (your virual machines). when interrupts
are caught, they can be conceptually redirected by software to a
thread but this is only a part of the virtualization job of the
kernel.
As a consequence, all functions that are part of the kernel (the
virtualizer) cannot be part of a (virutal) process. it would be a
chicken-and-egg problem.
as for the scheduler (the algo that decides which is next, not the
sequencer), it could theorically be separate process which always runs
and has the highest priority but the performance impact would be far
too high so it is also part of the kernel.
--
Philippe Amarenco, aka Phix
epita 2007 - GISTR - ACU - EpX
|
|
|
|
|