I write this Post because I find the topic interesting, someone has artificial intelligence information that is used for natural functions
of the kernel, such as planning the time of the processes, deciding priorities, ... In other words, a kernel that can learn.
Artificial intelligence in the kernel?
Re: Artificial intelligence in the kernel?
In a previous post, I talked about a first order filter for calculating the times assigned to processes, in the end I implemented it, now only
I have left to obtain the best constant for the different blocking devices. What is the idea ?, try to find through a neural network
simple (Perceptron Simple) the most optimal constants during the behavior of the process. In other words, the network will learn how the processes
they follow certain patterns and she determines which is the best constant to deliver. I give you an example:
1- A process uses the keyboard, the mouse 10 times, has a life time of X and then ends for some reason.
2- The neural network takes the planned and consumed times and learns, that in these processes, it is more the time that they are maintained
sleeping, which is running, and determines a constant that allows less CPU usage.
This is just an example and I only input planned time, consumed time and filter constant but others can be used
patterns to improve the efficiency of the neural network. The output of the neural network would only be the filter constant but other
outputs that intervene in other kernel functions.
I have left to obtain the best constant for the different blocking devices. What is the idea ?, try to find through a neural network
simple (Perceptron Simple) the most optimal constants during the behavior of the process. In other words, the network will learn how the processes
they follow certain patterns and she determines which is the best constant to deliver. I give you an example:
1- A process uses the keyboard, the mouse 10 times, has a life time of X and then ends for some reason.
2- The neural network takes the planned and consumed times and learns, that in these processes, it is more the time that they are maintained
sleeping, which is running, and determines a constant that allows less CPU usage.
This is just an example and I only input planned time, consumed time and filter constant but others can be used
patterns to improve the efficiency of the neural network. The output of the neural network would only be the filter constant but other
outputs that intervene in other kernel functions.
Re: Artificial intelligence in the kernel?
I mean, you do you, and OS development is all about ignoring at least some of the received wisdom (otherwise, what's the point?) But the common solution is to treat processes that regularly time out differently from processes that often block. The latter is indicative of interactive processes, either via network or input devices. The former is indicative of batch processes. The user probably won't care about the response time of a batch process, but will care (a lot) about the response time of an interactive process. Therefore most OSes give a bonus to interactive processes, and a malus to batch processes, so that interactive processes can respond to becoming runable more quickly.
But of course, you can complicate the binary decision by putting a neural network in between there. Wait, doesn't that mean that short-lived processes get a malus because the neural net was not trained for them? That would break most UNIX like operating systems, which consist of lots of tiny processes running for a short time.
But of course, you can complicate the binary decision by putting a neural network in between there. Wait, doesn't that mean that short-lived processes get a malus because the neural net was not trained for them? That would break most UNIX like operating systems, which consist of lots of tiny processes running for a short time.
Carpe diem!
Re: Artificial intelligence in the kernel?
With the utmost respect nullplan,
The point is as follows:
The network could be trained in a certain way, as you say "the user probably won't care about the response time of a batch process, but they will (very much) care about the response time of an interactive process". Hence the importance of being able to use the consumed and planned times, I give you an example:
You have an iterative process1 (a text editor), most of the time it is blocked waiting for the user, you have a process2 that performs mathematical calculations and gives a result (it can take several minutes and you just have to wait for it to finish), although it is It is true that you rebate the short-term process because it is the one that is suspended the longest, so the question arises
What is the best time bonus? If you were the one who made the decision you would make? What priority would you give compared to others waiting for the CPU?
It is clear that the first thing you do is differentiate them by their behavior, how can you differentiate them? , you do it, because one spends most of the time blocked and the other the scheduler has to expel it for exhausting their CPU usage time.
If you knew that process1 is a text editor, that the scheduler does not know, but your neural network determines by its behavior that it is and you could treat it in an X way and thus with various processes, what advantages would it give you?
Then certain patterns are able to differentiate the processes allowing you to choose the best form of planning, if the planner learned then you could have better use of the CPU.
The point is as follows:
The network could be trained in a certain way, as you say "the user probably won't care about the response time of a batch process, but they will (very much) care about the response time of an interactive process". Hence the importance of being able to use the consumed and planned times, I give you an example:
You have an iterative process1 (a text editor), most of the time it is blocked waiting for the user, you have a process2 that performs mathematical calculations and gives a result (it can take several minutes and you just have to wait for it to finish), although it is It is true that you rebate the short-term process because it is the one that is suspended the longest, so the question arises
What is the best time bonus? If you were the one who made the decision you would make? What priority would you give compared to others waiting for the CPU?
It is clear that the first thing you do is differentiate them by their behavior, how can you differentiate them? , you do it, because one spends most of the time blocked and the other the scheduler has to expel it for exhausting their CPU usage time.
If you knew that process1 is a text editor, that the scheduler does not know, but your neural network determines by its behavior that it is and you could treat it in an X way and thus with various processes, what advantages would it give you?
Then certain patterns are able to differentiate the processes allowing you to choose the best form of planning, if the planner learned then you could have better use of the CPU.
Re: Artificial intelligence in the kernel?
Hi mkfree
I like the question, it is interesting to consider.
I'm not sure if I have missed something, but can all the work about artificial intelligence really payout?
I mean, often when you talk about scheduling one of the most impotent thing is to make the decision fast, and it is often the case that extra work will not pay out.
Do you know about exponential moving average? Just a formula which tries to predict the next CPU burst with some weight of the previous burst.
This gives that CPU bounded tasks will gets longer burst and IO bounded tasks shorter.
If a text editor waits for input, you want to make as much of the CPU bounded task as possible, hence longer CPU burst to the CPU bounded task.
If an interrupt is received the text editor gets the input and do the work, fall to sleep again (waiting for next keystroke), hence short CPU burst.
This should give a good utilization of the CPU.
I'm not sure how to optimize this? Maybe something whit the priorities, but if one wants extremely responsive interaction, should the interactive task then not just get the best priority?
I like the question, it is interesting to consider.
I'm not sure if I have missed something, but can all the work about artificial intelligence really payout?
I mean, often when you talk about scheduling one of the most impotent thing is to make the decision fast, and it is often the case that extra work will not pay out.
Do you know about exponential moving average? Just a formula which tries to predict the next CPU burst with some weight of the previous burst.
This gives that CPU bounded tasks will gets longer burst and IO bounded tasks shorter.
If a text editor waits for input, you want to make as much of the CPU bounded task as possible, hence longer CPU burst to the CPU bounded task.
If an interrupt is received the text editor gets the input and do the work, fall to sleep again (waiting for next keystroke), hence short CPU burst.
This should give a good utilization of the CPU.
I'm not sure how to optimize this? Maybe something whit the priorities, but if one wants extremely responsive interaction, should the interactive task then not just get the best priority?
Re: Artificial intelligence in the kernel?
Rhodez,
This method really sounds to me, I tell you this, in a post I published about
how to treat time with the equation of a first order filter, I even implemented it in
the kernel and it's something like what you explain to me regarding the exponential moving average
only that the weight I put it to consideration, practically the results are similar
processes that crash tend to take less time and those of higher use more time, since
they use the previous time consumed.
I was curious and I looked in several books, and I found in STALLINGS, William - Operating Systems
page 375 and I write it verbatim "..., a common technique for predicting future values
from a series of past values is to use an exponential average. "Perhaps we are talking about
same subject !.
Now he even talks about the constant going from 0 to 1 and they detail the formula, when I finished
read I realized that it already exists! If you want, look for the equation of a first order filter and
Compare it with the one in the book and you will see that it is the same.
I took it logically as the behavior of a first-order filter and it's already considered! The
Logic was very simple and practical, so I continued in search of how to get the best a.
Now the constant (0 < a <1) can perhaps be taken into account by artificial intelligence, to
vary it according to the behavior of the process, because as you know a process can go from being
interactive to non-interactive and vice versa, also the priorities can be managed according to
a behavior of the process.
Thanks for your interest in the topic
This method really sounds to me, I tell you this, in a post I published about
how to treat time with the equation of a first order filter, I even implemented it in
the kernel and it's something like what you explain to me regarding the exponential moving average
only that the weight I put it to consideration, practically the results are similar
processes that crash tend to take less time and those of higher use more time, since
they use the previous time consumed.
I was curious and I looked in several books, and I found in STALLINGS, William - Operating Systems
page 375 and I write it verbatim "..., a common technique for predicting future values
from a series of past values is to use an exponential average. "Perhaps we are talking about
same subject !.
Now he even talks about the constant going from 0 to 1 and they detail the formula, when I finished
read I realized that it already exists! If you want, look for the equation of a first order filter and
Compare it with the one in the book and you will see that it is the same.
I took it logically as the behavior of a first-order filter and it's already considered! The
Logic was very simple and practical, so I continued in search of how to get the best a.
Now the constant (0 < a <1) can perhaps be taken into account by artificial intelligence, to
vary it according to the behavior of the process, because as you know a process can go from being
interactive to non-interactive and vice versa, also the priorities can be managed according to
a behavior of the process.
Thanks for your interest in the topic
Re: Artificial intelligence in the kernel?
Ah okay, I see. Interesting. However I do not know much about Artificial intelligence and the methods in the area and how easy it is to exploit something here.mkfree wrote: Now the constant (0 < a <1) can perhaps be taken into account by artificial intelligence, to
vary it according to the behavior of the process, because as you know a process can go from being
interactive to non-interactive and vice versa, also the priorities can be managed according to
a behavior of the process.
But have you already made some tests with this?
My impression would still be that the cost overweight's the benefit, but for theoretical reasons it is still very interesting.
and of course if it can improve performance.
- Jørn
Re: Artificial intelligence in the kernel?
Interesting idea, however I can't see what benefit it would give.
First, the algorithms they mock as "AI" can be used in big data mining only. A kernel does not have big data in the first place. It's job is to provide a common high-level interface for low-level hardware and share resources in a predictable way. Using any heuristics would undermine the "predictable" goal. Users simply hate when the computers are non-deterministic. They expect that the computer gives the same results for the same input, no matter how many times they repeat that particular operation. For me, even dynamic priority value that the Linux kernel uses is a mess. And I'm not alone, that's why brainfuck scheduler was written, and became more popular than the original Linux scheduler.
Cheers,
bzt
First, the algorithms they mock as "AI" can be used in big data mining only. A kernel does not have big data in the first place. It's job is to provide a common high-level interface for low-level hardware and share resources in a predictable way. Using any heuristics would undermine the "predictable" goal. Users simply hate when the computers are non-deterministic. They expect that the computer gives the same results for the same input, no matter how many times they repeat that particular operation. For me, even dynamic priority value that the Linux kernel uses is a mess. And I'm not alone, that's why brainfuck scheduler was written, and became more popular than the original Linux scheduler.
Cheers,
bzt
Re: Artificial intelligence in the kernel?
bzt,
Artificial intelligence can be applied to programming as you wish. I give you a basic example that appears in any biliography, as a safe programmer at some point you implemented a gate and, or, ..., if you look at the simple results in a neuron you will say, I can optimize my code just by using a mathematical formula. I only put this example as a base you can find infinite texts on the subject.
AND (x1, x2) = g (x1 + x2 - 1, 5)
OR (x1, x2) = g (x1 + x2 - 0, 5)
NOT (x1) = g (-x1 + 0, 5)
g (a) = 0 if a <0
1 if a = 0
I say the same with the planner, and I hope to implement it, which would be to add the possibility of activating the planner by
artificial intelligence and with a simple neural network get the times and priorities. We are not necessarily talking about big data, but the behavior of processes over time to obtain the best form of planning. You can even have several of the forms of planning you want and depending on the context, the neural network can say to go from one to another according to what you have learned.
The benefits would be in performance, but I have yet to prove it.
Artificial intelligence can be applied to programming as you wish. I give you a basic example that appears in any biliography, as a safe programmer at some point you implemented a gate and, or, ..., if you look at the simple results in a neuron you will say, I can optimize my code just by using a mathematical formula. I only put this example as a base you can find infinite texts on the subject.
AND (x1, x2) = g (x1 + x2 - 1, 5)
OR (x1, x2) = g (x1 + x2 - 0, 5)
NOT (x1) = g (-x1 + 0, 5)
g (a) = 0 if a <0
1 if a = 0
I say the same with the planner, and I hope to implement it, which would be to add the possibility of activating the planner by
artificial intelligence and with a simple neural network get the times and priorities. We are not necessarily talking about big data, but the behavior of processes over time to obtain the best form of planning. You can even have several of the forms of planning you want and depending on the context, the neural network can say to go from one to another according to what you have learned.
The benefits would be in performance, but I have yet to prove it.
Re: Artificial intelligence in the kernel?
Okay, first things first, there's no such thing "Artificial Intelligence". It is just a buzzword used by marketing people to almost everything these days. From technical perspective the closest things are heavily statistical methods and algorithms used on big data, that's why I've mentioned that.mkfree wrote:bzt,
Artificial intelligence can be applied to programming as you wish.
The most accepted definition is that AI is a program that can pass the Turing test, however the Loebner prize made for this test was and still is criticised widely (and not without reason may I add). No real "AI" ever passed the test, but a fake chatbot (like ELIZA) could easily.
Thank you, I'm quite familiar with neural networks, I had to learn two semester at the university (and honestly I hated it. A cleverly applied and optimized minmaxsearch algorithm is always more performant and easier to use for me. Circumstances and properties by which your code measures the environment don't change in a game nor in a kernel). Interestingly neither my prof, no other serious scholar ever called a neural network an AI (but AI wasn't the buzzword back then as it is these days).mkfree wrote:I give you a basic example
Now there's a big difference optimizing your code and optimizing run-time execution by analyzing input data. I taught "proving program correctness using math" lectures at my university, I should knowmkfree wrote:I can optimize my code just by using a mathematical formula.
(if interested what that is, look here for the definition of sequence, conditional and iteration. Sorry, Hungarian only). Optimizing code using math is not as easy as you would assume. There's only 3 systems that's code have been described entirely using math (all three related to DoD and DARPA), because it is extremely hard to do, and even harder to do it right. This is the mathematical formula of a loop for example (the part when the loop's condition is evaluated to true at first, therefore the loop's body is not skipped in the first place):
If you're interested in using math for programming, try the Eiffel language, that's the closest.
This makes more sense, but don't think you can optimize your code for this, unless you allow dynamically changing your code, but then you'd be better off with evolutionary computation. I mean the properties by which you describe a "plan" is finite, and they won't change in run-time for sure, so I don't think using such complex things like NN or EC worth it at all.mkfree wrote:the behavior of processes over time to obtain the best form of planning.
I doubt using neural network for scheduling going to be performant at all, but at least there's no evidence to say otherwise either, so it is an interesting area to research.mkfree wrote:The benefits would be in performance, but I have yet to prove it.
Check out the KANN library, maybe it's useful to you. (Note: I did not wrote that lib, I've just bookmarked it because it looked like something that could be integrated into a kernel).
Cheers,
bzt
Re: Artificial intelligence in the kernel?
bzt,
I understand that you know the subject, and I thank you very much for your words, I am reviewing the library that you sent me. For now I intend something simple and
the objective of taking advantage of the advantages offered by neural networks, using 1 or 2 layers and perhaps reinforcement learning. As soon as I have something very concrete I will publish it.
The goal is not to pass the Turing test, much less try to win the Loebner contest. It is true that everyone has their vision of AI, it is a controversial topic and tends to create distractions, so I do not give any criteria regarding this.
Thank you very much for your help and courtesy.
I understand that you know the subject, and I thank you very much for your words, I am reviewing the library that you sent me. For now I intend something simple and
the objective of taking advantage of the advantages offered by neural networks, using 1 or 2 layers and perhaps reinforcement learning. As soon as I have something very concrete I will publish it.
The goal is not to pass the Turing test, much less try to win the Loebner contest. It is true that everyone has their vision of AI, it is a controversial topic and tends to create distractions, so I do not give any criteria regarding this.
Thank you very much for your help and courtesy.
Re: Artificial intelligence in the kernel?
Okay, let us know what you manage to achieve.mkfree wrote:bzt,
I understand that you know the subject, and I thank you very much for your words, I am reviewing the library that you sent me. For now I intend something simple and
the objective of taking advantage of the advantages offered by neural networks, using 1 or 2 layers and perhaps reinforcement learning. As soon as I have something very concrete I will publish it.
I've thought somkfree wrote: The goal is not to pass the Turing test, much less try to win the Loebner contest. It is true that everyone has their vision of AI, it is a controversial topic and tends to create distractions, so I do not give any criteria regarding this.
I recommend just to use the phrase "neural network" and then there'll be no confusion.You're welcome! I hope that this lib is going to be useful to you. If not, I suggest to look around, there are other CPU-only implementations. And if you're really feel up to it, you could try to integrate OpenCL or Vulkan and try a GPU based implementation (hard, but not impossible).mkfree wrote:Thank you very much for your help and courtesy.
Cheers,
bzt
Re: Artificial intelligence in the kernel?
DL has been used to estimate scheduling parameters before, for example https://www.usenix.org/conference/osdi1 ... ation/xiao has a solid number of citations. There are some papers that apply DL to classify malware. It is not inconceivable that DL or other ML techniques could be used for scheduling in an OS kernel but figuring that out is a research problem (and one that is probably not suited for this forum).
Regarding the claim "There's only 3 systems that's code have been described entirely using math" is dubious. What is a "system" here? There are correctness proofs of various computing systems, including OSes such as L4 (mostly written in constructive logics like Coq or Isabelle). Others use SMT solvers such as Z3. AFAIK proving the correctness of annotated parts of the Windows kernel is one of the main reasons why Microsoft develops Z3 (but of course these annotated parts are closed source).
Regarding the claim "There's only 3 systems that's code have been described entirely using math" is dubious. What is a "system" here? There are correctness proofs of various computing systems, including OSes such as L4 (mostly written in constructive logics like Coq or Isabelle). Others use SMT solvers such as Z3. AFAIK proving the correctness of annotated parts of the Windows kernel is one of the main reasons why Microsoft develops Z3 (but of course these annotated parts are closed source).
managarm: Microkernel-based OS capable of running a Wayland desktop (Discord: https://discord.gg/7WB6Ur3). My OS-dev projects: [mlibc: Portable C library for managarm, qword, Linux, Sigma, ...] [LAI: AML interpreter] [xbstrap: Build system for OS distributions].
Re: Artificial intelligence in the kernel?
Of course I'm talking about a system where each and every single part is proved to be correct. As soon as you load a module which is not, no matter how small that is, you can't say the system is proven correct. (The prove must be complete).Korona wrote:What is a "system" here? There are correctness proofs of various computing systems
That's what I'm talking about. Proving only parts is not enough. As soon as you load a Windows driver which wasn't proved for correctness, or an application that wasn't, then it doesn't matter if the rest was. Really serious systems has also a criteria that has to be compiled with a compiler that also was proven to be correct (I only know one system that complies with this, but only in "laboratory", it's not used in real life; or at least that's what they say because DARPA is not really communicative about it).Korona wrote:AFAIK proving the correctness of annotated parts of the Windows kernel
Maybe you do remember that fiasco when the so called "trusted" Windows almost resulted in a disaster by accidentally firing rockets with shilo doors closed. That's when Sun started to certify Solaris as a Trusted System. And just for the records, the requirements for a "Trusted System" is far less restrictive than being mathematically proven correct. The latter is the most strict verification there can be. Windows is not, and not even partially proven mathematically correct (neither is Solaris).
EDIT: I've looked it up for you: DARPA HACMS TS. It lists only two systems, L4 ("normal" and se variants) and CAmKES. It also states pretty clearly that the system is not verified, only the kernel (considering L4 is a microkernel, that's just a very very small part of the entire system). Don't get me wrong, proving correctness of a microkernel is a big thing, just pretty far from saying the entire system is proven for correctness. FYI, DARPA TS does not mention any other kernels, like Windows for example.
Cheers,
bzt
Re: Artificial intelligence in the kernel?
True, these proofs only concern small parts of the system - but in some applications these parts are enough to ensure that the application to satisfies its constraints. For example, in highly critical systems, it's common to have the crticial application running on bare metal of a dedicated core; a hardware interconnect is used to communicate with a "normal" CPU running a "real" OS. The OS performs all failable I/O while the embedded application just performs computations and drives a small subset of the peripherals (like the controls of a satelite or whatever).
Regarding the limitations: a big issue for correctness proofs is resource exhaustion. Some variants of L4 get around that by letting the user supply memory to the kernel. IIRC that's also why Microsoft's verification projects needed annotations but my memory may be off here (and I don't know if the specifics have ever been made public).
Regarding the limitations: a big issue for correctness proofs is resource exhaustion. Some variants of L4 get around that by letting the user supply memory to the kernel. IIRC that's also why Microsoft's verification projects needed annotations but my memory may be off here (and I don't know if the specifics have ever been made public).
managarm: Microkernel-based OS capable of running a Wayland desktop (Discord: https://discord.gg/7WB6Ur3). My OS-dev projects: [mlibc: Portable C library for managarm, qword, Linux, Sigma, ...] [LAI: AML interpreter] [xbstrap: Build system for OS distributions].