[lkml]   [2003]   [Sep]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectUse of AI for process scheduling
I just got back from vacation and have 3278 list messages to sift
through. (Yay.) I wouldn't be surprised, therefore, if others were
already discussing this, but I've been thinking of some ideas over the
past week that we may be helpful for the advancement of intelligent
process scheduling.

To begin with, let's consider the parts of an intelligent system:

1) Inputs (ie. properties and behaviors of processes)
2) Heuristics
3) Outputs (ie. dynamic priorities, etc.)

Up to this point, the interactive scheduler has been designed in a very
expert-system-like manner. Human experts observe behaviors and define
heuristics. Ultimately, we do want a solid set of heuristics that are
coded in C, and that's what the current development process has been
working directly toward.

The progress has been slow, and there have been a lot of false starts
and tangents which have been discarded. This is all how development
works, and it's important to explore all possibilities. But what I
would like to propose is that we work on a way to accelerate that
process, and that is to make use of machine learning. We move from
expert systems to artificial intelligence, because the heuristics are
determined by the machine and are therefore dynamic.

Basically, we need to write and install into the kernel an AI engine
which uses user feedback about the "feel" of the system to adjust
heuristics dynamically. For instance, if the user sees that the system
is misbehaving, they can pause the system in the kernel debugger,
examine process priorities, and indicate what "outputs" from the AI
engine are wrong. It then learns from that. Heuristics can be tweaked
until things run as desired. At that point, scheduler developers trade
emails in the AI heuristic language.

Obviously, this AI engine will be slow and add a huge amount of
processing overhead. The idea is to determine what the heuristics are,
and then to release a kernel, recode the heuristics in C.

We have a number of options for what kinds of AI engines we use. A
neural net is something that's relatively easy to train, but beyond a
certain level of complexity, it's impossible to make much sense out of
the weights. Genetic algorithms are probably out of the question.

The ideal situation would be to have a rule processor that uses a script
language of sorts (lots of if-thens with some math, etc.) to compute on
inputs and produce directives to the scheduler (dynamic priorities, but
perhaps more) -- but what would produce the script? How do you turn
user feedback automatically into better rules? But at the very least,
it could speed up development by making scheduler behavior dynamically
programmable. If a priority inversion occurs and you stop the kernel to
examine it, the AI engine could report to you what combination of rules
were used to cause that condition. You then dynamically change the
rules and observe the effects.

I have huge gaps in my knowledge of AI, so I'm hoping some LKML members
who are experts on this will engage in this discussion.

I think use of AI could be applied to the development of MANY parts of
the kernel. Obviously, the I/O scheduler could benefit. But what about
intelligently dealing with failure conditions?

Maybe AI could be useful in a running kernel, at least as an observer.
I read an article about self-correcting systems in space craft. There
is the logic of the system, and then there is an AI model of it. When
some component fails to operate properly or the system behaves in an
unexpected manner, the "model" finds a way to work around the problem.
This kind of redundancy in a kernel being debugged could be invaluable.
In a deployment kernel, it could exist at a reduced level of

Another freaky idea is that large parts of the kernel could be rewritten
in the heuristic language and interpreted during debugging and then
compiled for release.

Also, some logic which is not computationally intensive could be always
interpreted because the size of the interpretor plus the size of the
pcode would be smaller than the size of the object code for the compiled
version. This would not be for performance-critical logic in a deployed

Ok, I know I'm going too far. Right now, the best application would be
the process scheduler, but we should start thinking about ways of making
the system "self aware" and "self correcting" so that when the model
observes the logic to misbehave, detailed information can be produced
for debugging purposes.

Naturally, I am interested in contributing to this, but some of what I
will have to learn to participate will come out of ensuing discussions.
I have a lot to learn, but I think if these ideas are valuable, others
who already know enough will start to do something with them.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:48    [W:0.160 / U:30.212 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site