Distributed Process Scheduling Algorithm
Hi, I am given a task to design a distributed process scheduling algorithm. Current distributed OS are patch work over the linux kernels, that is, they are responsible for load balancing through process migration but the scheduling is taken care by the single machine linux kernels. My task is to make the scheduling algorithm itself as distributed. That is a scheduler itself makes a decision whether to migrate a task or to keep the task in the current system. I need some design aspects of how to achieve it. Another thing which I want to know is that whether this job is possible for a kernel newbie like me. Need urgent help. Nitin
On Mon, Feb 15, 2016 at 09:35:28PM +0530, Nitin Varyani wrote:
Hi,
Hi Nitin,
I am given a task to design a distributed process scheduling algorithm. Current distributed OS are patch work over the linux kernels, that is, they are responsible for load balancing through process migration but the scheduling is taken care by the single machine linux kernels.
Hmm, are you talking about HPC clusters or other large machines here? I'm not familiar with this, so a few references to existing designs would be appreciated.
My task is to make the scheduling algorithm itself as distributed.
Apart from my comment below, it sounds like a really interesting project. Is this a research-project or something commercial?
That is a scheduler itself makes a decision whether to migrate a task or to keep the task in the current system. I need some design aspects of how to achieve it. Another thing which I want to know is that whether this job is possible for a kernel newbie like me. Need urgent help. Nitin
Uhm, ok. I think this is _way_ outside the scope of Kernelnewbies, and it is definitely not a newbie project. If you are really serious about this, I'd start with listing all the different elements you need to share and then an initial idea as to how to share those between individual systems. I have an inkling that you'll find out quite fast as to why the current kernel does not support this out of the box. -- Henrik Austad
No doubt it is really interesting. It is a research project. The project is related to HPC clusters. I am as of now planning only to make the process scheduling algorithm distributed. Linux has already implemented SMP using Completely Fair Scheduler and I was thinking was of extending it for distributed systems. Two things need to be added to it: 1) Sending process context via network 2) Maintaining a table at each node which stores the load of each remote node. This table will be used to make a decision whether to send a process context along the network or not. Thanks for your kind help. On Mon, Feb 15, 2016 at 10:22 PM, Henrik Austad <henrik@austad.us> wrote:
On Mon, Feb 15, 2016 at 09:35:28PM +0530, Nitin Varyani wrote:
Hi,
Hi Nitin,
I am given a task to design a distributed process scheduling algorithm. Current distributed OS are patch work over the linux kernels, that is, they are responsible for load balancing through process migration but the scheduling is taken care by the single machine linux kernels.
Hmm, are you talking about HPC clusters or other large machines here? I'm not familiar with this, so a few references to existing designs would be appreciated.
My task is to make the scheduling algorithm itself as distributed.
Apart from my comment below, it sounds like a really interesting project. Is this a research-project or something commercial?
That is a scheduler itself makes a decision whether to migrate a task or to keep the task in the current system. I need some design aspects of how to achieve it. Another thing which I want to know is that whether this job is possible for a kernel newbie like me. Need urgent help. Nitin
Uhm, ok. I think this is _way_ outside the scope of Kernelnewbies, and it is definitely not a newbie project.
If you are really serious about this, I'd start with listing all the different elements you need to share and then an initial idea as to how to share those between individual systems. I have an inkling that you'll find out quite fast as to why the current kernel does not support this out of the box.
-- Henrik Austad
On Tue, 16 Feb 2016 10:18:26 +0530, Nitin Varyani said:
1) Sending process context via network
Note that this is a non-trivial issue by itself. At a *minimum*, you'll need all the checkpoint-restart code. Plus, if the process has any open TCP connections, *those* have to be migrated without causing a security problem. Good luck on figuring out how to properly route packets in this case - consider 4 nodes 10.0.0.1 through 10.0.0.4, you migrate a process from 10.0.0.1 to 10.0.0.3, How do you make sure *that process*'s packets go to 0.3 while all other packets still go to 0.1. Also, consider the impact this may have on iptables, if there is a state=RELATED,CONNECTED on 0.1 - that info needs to be relayed to 0.3 as well. For bonus points, what's the most efficient way to transfer a large process image (say 500M, or even a bloated Firefox at 3.5G), without causing timeouts while copying the image? I hope your research project is *really* well funded - you're going to need a *lot* of people (Hint - find out how many people work on VMWare - that should give you a rough idea)
On Tue, 16 Feb 2016 00:13:34 -0500 Valdis.Kletnieks@vt.edu wrote:
On Tue, 16 Feb 2016 10:18:26 +0530, Nitin Varyani said:
1) Sending process context via network
Note that this is a non-trivial issue by itself. At a *minimum*, you'll need all the checkpoint-restart code. Plus, if the process has any open TCP connections, *those* have to be migrated without causing a security problem. Good luck on figuring out how to properly route packets in this case - consider 4 nodes 10.0.0.1 through 10.0.0.4, you migrate a process from 10.0.0.1 to 10.0.0.3, How do you make sure *that process*'s packets go to 0.3 while all other packets still go to 0.1. Also, consider the impact this may have on iptables, if there is a state=RELATED,CONNECTED on 0.1 - that info needs to be relayed to 0.3 as well.
For bonus points, what's the most efficient way to transfer a large process image (say 500M, or even a bloated Firefox at 3.5G), without causing timeouts while copying the image?
I hope your research project is *really* well funded - you're going to need a *lot* of people (Hint - find out how many people work on VMWare - that should give you a rough idea)
I wouldn't see things that dark. Also this is an interesting puzzle. To migrate processes I would pick an already existing solution. Like there is for container. So every process should be, if possible, in a container. To migrate them efficiently without having some distributed shared memory, you might want to look at userfaultfd. So now back to the scheduling, I do not think that every node should keep track of every process on every other node, as this would mean a massive need for communication and hurt scalability. So either you would implement something like work stealing or go for a central entity like mesos. Which could do process/job/container scheduling for you. There are now two pitfalls which are hard enough on their own: - interprocess communication between two process with something different than a socket in such an case you would probably need to merge the two distinct containers - dedicated hardware Dominik
According to my project requirement, I need a distributed algorithm so mesos will not work. But work stealing is the best bargain. It will save communication costs. Thankyou. Can you please elaborate on the last part of your reply? On Tue, Feb 16, 2016 at 2:12 PM, Dominik Dingel <dingel@linux.vnet.ibm.com> wrote:
On Tue, 16 Feb 2016 00:13:34 -0500 Valdis.Kletnieks@vt.edu wrote:
On Tue, 16 Feb 2016 10:18:26 +0530, Nitin Varyani said:
1) Sending process context via network
Note that this is a non-trivial issue by itself. At a *minimum*, you'll need all the checkpoint-restart code. Plus, if the process has any open TCP connections, *those* have to be migrated without causing a security problem. Good luck on figuring out how to properly route packets in this case - consider 4 nodes 10.0.0.1 through 10.0.0.4, you migrate a process from 10.0.0.1 to 10.0.0.3, How do you make sure *that process*'s packets go to 0.3 while all other packets still go to 0.1. Also, consider the impact this may have on iptables, if there is a state=RELATED,CONNECTED on 0.1 - that info needs to be relayed to 0.3 as well.
For bonus points, what's the most efficient way to transfer a large process image (say 500M, or even a bloated Firefox at 3.5G), without causing timeouts while copying the image?
I hope your research project is *really* well funded - you're going to need a *lot* of people (Hint - find out how many people work on VMWare - that should give you a rough idea)
I wouldn't see things that dark. Also this is an interesting puzzle.
To migrate processes I would pick an already existing solution. Like there is for container. So every process should be, if possible, in a container. To migrate them efficiently without having some distributed shared memory, you might want to look at userfaultfd.
So now back to the scheduling, I do not think that every node should keep track of every process on every other node, as this would mean a massive need for communication and hurt scalability. So either you would implement something like work stealing or go for a central entity like mesos. Which could do process/job/container scheduling for you.
There are now two pitfalls which are hard enough on their own: - interprocess communication between two process with something different than a socket in such an case you would probably need to merge the two distinct containers
- dedicated hardware
Dominik
The essence of the discussion is that : We can run each process in a container and migrate the container itself. Migration can be done based on work stealing. As far as communication between processes in different containers is concerned, can't we use sockets? On Tue, Feb 16, 2016 at 3:16 PM, Nitin Varyani <varyani.nitin1@gmail.com> wrote:
According to my project requirement, I need a distributed algorithm so mesos will not work. But work stealing is the best bargain. It will save communication costs. Thankyou. Can you please elaborate on the last part of your reply?
On Tue, Feb 16, 2016 at 2:12 PM, Dominik Dingel <dingel@linux.vnet.ibm.com
wrote:
On Tue, 16 Feb 2016 00:13:34 -0500 Valdis.Kletnieks@vt.edu wrote:
On Tue, 16 Feb 2016 10:18:26 +0530, Nitin Varyani said:
1) Sending process context via network
Note that this is a non-trivial issue by itself. At a *minimum*, you'll need all the checkpoint-restart code. Plus, if the process has any open TCP connections, *those* have to be migrated without causing a security problem. Good luck on figuring out how to properly route packets in this case - consider 4 nodes 10.0.0.1 through 10.0.0.4, you migrate a process from 10.0.0.1 to 10.0.0.3, How do you make sure *that process*'s packets go to 0.3 while all other packets still go to 0.1. Also, consider the impact this may have on iptables, if there is a state=RELATED,CONNECTED on 0.1 - that info needs to be relayed to 0.3 as well.
For bonus points, what's the most efficient way to transfer a large process image (say 500M, or even a bloated Firefox at 3.5G), without causing timeouts while copying the image?
I hope your research project is *really* well funded - you're going to need a *lot* of people (Hint - find out how many people work on VMWare - that should give you a rough idea)
I wouldn't see things that dark. Also this is an interesting puzzle.
To migrate processes I would pick an already existing solution. Like there is for container. So every process should be, if possible, in a container. To migrate them efficiently without having some distributed shared memory, you might want to look at userfaultfd.
So now back to the scheduling, I do not think that every node should keep track of every process on every other node, as this would mean a massive need for communication and hurt scalability. So either you would implement something like work stealing or go for a central entity like mesos. Which could do process/job/container scheduling for you.
There are now two pitfalls which are hard enough on their own: - interprocess communication between two process with something different than a socket in such an case you would probably need to merge the two distinct containers
- dedicated hardware
Dominik
On Tue, 16 Feb 2016 16:13:25 +0530 Nitin Varyani <varyani.nitin1@gmail.com> wrote: It is common practice to shorten your answers to mailinglists.
The essence of the discussion is that :
We can run each process in a container and migrate the container itself. Migration can be done based on work stealing. As far as communication between processes in different containers is concerned, can't we use sockets?
Migration can be done based on work stealing sounds misleading. Maybe something like: Nodes might apply the work stealing pattern by migrating the workload, encapsulated in the container. That would be the idea, if that actually works and how it would perform is up to that experiment ;). That is for new applications possible, but there may be "legacy" applications which rely on communication methods like shared memory, and pipes. If this ends in an research paper I would like to read it. Dominik
On Tue, 16 Feb 2016 09:42:52 +0100, Dominik Dingel said:
I wouldn't see things that dark. Also this is an interesting puzzle.
Just pointing out *very real* issues that will require solution, unless you add strict bounds like "cannot be using network connections". Heck, even open files get interesting. How do you ensure that the file descriptor returned by mkstemp() remains valid? (The *really* ugly case is programs that do a mkstemp() and then unlink() the result, confident that the kernel will clean up when the process exits, as there is no longer a file system object to reference.... Of course, if you say "no network connections" and "no open files", the problem gets a lot easier - but also quickly devolving into a master's thesis research project rather than anything useful.... Bottom line: Don't even *think* about changing the scheduler etc until you have a functional way to actually move the process. Doesn't matter if you use a kvm approach, or containers, or whatever - if you can't do the migrate, you can't even *test* your code that decides which process to migrate.....
if you say "no network connections" and "no open files", the problem gets a lot easier - but also quickly devolving into a master's thesis research project rather than anything useful.... Actually it is a master's thesis research project as of now. I am ready to boil down to the most basic implementation of distributed linux kernel. Assume there is no network connection and no open files. We can drop even more assumptions if it becomes complicated. Once this basic implementation is successful, we can go ahead with a more complicated version. The next task is to integrate the migration code in the linux kernel. What is the most easy way of implementing it. On Tue, Feb 16, 2016 at 10:05 PM, <Valdis.Kletnieks@vt.edu> wrote:
On Tue, 16 Feb 2016 09:42:52 +0100, Dominik Dingel said:
I wouldn't see things that dark. Also this is an interesting puzzle.
Just pointing out *very real* issues that will require solution, unless you add strict bounds like "cannot be using network connections".
Heck, even open files get interesting. How do you ensure that the file descriptor returned by mkstemp() remains valid? (The *really* ugly case is programs that do a mkstemp() and then unlink() the result, confident that the kernel will clean up when the process exits, as there is no longer a file system object to reference....
Of course, if you say "no network connections" and "no open files", the problem gets a lot easier - but also quickly devolving into a master's thesis research project rather than anything useful....
Bottom line: Don't even *think* about changing the scheduler etc until you have a functional way to actually move the process. Doesn't matter if you use a kvm approach, or containers, or whatever - if you can't do the migrate, you can't even *test* your code that decides which process to migrate.....
On Wed, 17 Feb 2016 10:21:35 +0530, Nitin Varyani said:
Actually it is a master's thesis research project as of now. I am ready to boil down to the most basic implementation of distributed linux kernel. Assume there is no network connection and no open files. We can drop even more assumptions if it becomes complicated. Once this basic implementation is successful, we can go ahead with a more complicated version. The next task is to integrate the migration code in the linux kernel. What is the most easy way of implementing it.
If you get it to where you can migrate a process on command controlled by a userspace process, the scheduler part will be trivial. And note that the choice of which process to migrate where is sufficiently "policy" that it belongs in userspace - see how cgroups and containers are kernel mechanisms that are controlled by userspace. You want to follow that model if you intend for this to be upstreamed rather than just another dead master's thesis.
On 2/17/16 1:10 AM, Valdis.Kletnieks@vt.edu wrote:
On Wed, 17 Feb 2016 10:21:35 +0530, Nitin Varyani said:
Actually it is a master's thesis research project as of now. I am ready to boil down to the most basic implementation of distributed linux kernel. Assume there is no network connection and no open files. We can drop even more assumptions if it becomes complicated. Once this basic implementation is successful, we can go ahead with a more complicated version. The next task is to integrate the migration code in the linux kernel. What is the most easy way of implementing it. If you get it to where you can migrate a process on command controlled by a userspace process, the scheduler part will be trivial.
If you want some ideas about distributed process scheduling, you might want to explore how Erlang's run-time works - it's all about massive concurrency and scheduling processes (well, really light-weight processes) across multiple cores. If you google "distributed process scheduling erlang" you'll also find some work about process scheduling across clusters, particularly for gaming environments. How much might be applicable in a linux kernel environment is unclear - but, then, it's your research project. Miles Fidelman In theory, there is no difference between theory and practice. In practice, there is. .... Yogi Berra
Having got some clarity of what I have to do, I want to now proceed for a step by step development. What all I know about linux kernels is a theoretical understanding of its various components (from the book of Robert Love) but as far as practical is concerned, I know the following things: 1) Linking modules dynamically to kernel at run time ( outside source tree and inside source tree) 2) Adding system calls Rather than trying to go blind folded in getting practical experience of linux programming, I want to gain experience only in relation to my task of creating a distributed process scheduler. What all things should I try to work with to understand the kernel CFS scheduler well? Please provide sufficient literature for the practical work. Also what is the best place to learn about implementing linux containers? On Wed, Feb 17, 2016 at 11:40 AM, <Valdis.Kletnieks@vt.edu> wrote:
On Wed, 17 Feb 2016 10:21:35 +0530, Nitin Varyani said:
Actually it is a master's thesis research project as of now. I am ready to boil down to the most basic implementation of distributed linux kernel. Assume there is no network connection and no open files. We can drop even more assumptions if it becomes complicated. Once this basic implementation is successful, we can go ahead with a more complicated version. The next task is to integrate the migration code in the linux kernel. What is the most easy way of implementing it.
If you get it to where you can migrate a process on command controlled by a userspace process, the scheduler part will be trivial.
And note that the choice of which process to migrate where is sufficiently "policy" that it belongs in userspace - see how cgroups and containers are kernel mechanisms that are controlled by userspace. You want to follow that model if you intend for this to be upstreamed rather than just another dead master's thesis.
On Wed, Feb 17, 2016 at 04:05:17PM +0530, Nitin Varyani wrote:
Rather than trying to go blind folded in getting practical experience of linux programming, I want to gain experience only in relation to my task of creating a distributed process scheduler. What all things should I try to work with to understand the kernel CFS scheduler well? Please provide sufficient literature for the practical work. Also what is the best place to learn about implementing linux containers?
Why are you asking other people to do your research work for you? That's pretty rude, does your professor know this is what you are doing? greg k-h
@ Greg: Since I am very new to the field, with the huge task in hand and a short time span of 3 months given for this project, I am looking for specific directions from the linux experts to work on. As far as efforts are concerned, I am taking out hours together to research into this area. I do not mind telling this to my professor. Still, I am always looking for improvement. I will try to put more endeavor and seek as less help as possible. I hope you will not mind my reply. Thanks. On Wed, Feb 17, 2016 at 9:02 PM, Greg KH <greg@kroah.com> wrote:
On Wed, Feb 17, 2016 at 04:05:17PM +0530, Nitin Varyani wrote:
Rather than trying to go blind folded in getting practical experience of linux programming, I want to gain experience only in relation to my task of creating a distributed process scheduler. What all things should I try to work with to understand the kernel CFS scheduler well? Please provide sufficient literature for the practical work. Also what is the best place to learn about implementing linux containers?
Why are you asking other people to do your research work for you? That's pretty rude, does your professor know this is what you are doing?
greg k-h
On Thu, Feb 18, 2016 at 11:35 AM, Nitin Varyani <varyani.nitin1@gmail.com> wrote:
@ Greg: Since I am very new to the field, with the huge task in hand and a short time span of 3 months given for this project, I am looking for specific directions from the linux experts to work on. As far as efforts are concerned, I am taking out hours together to research into this area. I do not mind telling this to my professor. Still, I am always looking for improvement. I will try to put more endeavor and seek as less help as possible. I hope you will not mind my reply. Thanks.
On Wed, Feb 17, 2016 at 9:02 PM, Greg KH <greg@kroah.com> wrote:
On Wed, Feb 17, 2016 at 04:05:17PM +0530, Nitin Varyani wrote:
Rather than trying to go blind folded in getting practical experience of linux programming, I want to gain experience only in relation to my task of creating a distributed process scheduler. What all things should I try to work with to understand the kernel CFS scheduler well? Please provide sufficient literature for the practical work. Also what is the best place to learn about implementing linux containers?
Why are you asking other people to do your research work for you? That's pretty rude, does your professor know this is what you are doing?
greg k-h
Dear Nitin Again, please don't top post :) That's considered rude too, at least here :) I can't speak on behalf of Greg, but I guess the basic idea of why people gather in this mailing list is to share ideas and discuss, but not giving very specific guidance. If that's the goal, this list would be named "kernel mentoring", don't you agree? :) So, if we follow this "discussion area" rule, I can give you ideas: - maybe your scope of work is too wide. Try to be more specific. 3 months time span is very short compared to what you're going to do (IIUC). As other already pointed, maybe you can piggy back on Erlang project and enhance their work instead? - do you have solid background of kernel programming, especially related to scheduler? if not, try to get a grasp quickly using code navigator e.g cscope or lxr.linux.no and play around with the code first. It might give direct experience on how code works and at the same time how kernel build mechanism work Hope it helps.... -- regards, Mulyadi Santosa Freelance Linux trainer and consultant blog: the-hydra.blogspot.com training: mulyaditraining.blogspot.com
On Thu, Feb 18, 2016 at 10:05:40AM +0530, Nitin Varyani wrote:
@ Greg: Since I am very new to the field, with the huge task in hand and a short time span of 3 months given for this project,
3 months? That's way too short, this is a multi-year/decade type research project. You can barely write a "simple" kernel driver in 3 months start to finish unless you _really_ know what you are doing. I suggest get a new professor / advisor, this one doesn't seem to realize the scope of the work involved :) good luck! greg k-h
On Thu, Feb 18, 2016 at 09:06:05PM -0800, Greg KH wrote:
On Thu, Feb 18, 2016 at 10:05:40AM +0530, Nitin Varyani wrote:
@ Greg: Since I am very new to the field, with the huge task in hand and a short time span of 3 months given for this project,
Are you formally trained froma university? I'm just asking because I know that many core coders don't even have a college background in comp sci. So I'm just curious as to the path you took. Reuvain
3 months? That's way too short, this is a multi-year/decade type research project. You can barely write a "simple" kernel driver in 3 months start to finish unless you _really_ know what you are doing.
I suggest get a new professor / advisor, this one doesn't seem to realize the scope of the work involved :)
good luck!
greg k-h
_______________________________________________ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
-- So many immigrant groups have swept through our town that Brooklyn, like Atlantis, reaches mythological proportions in the mind of the world - RI Safir 1998 http://www.mrbrklyn.com DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002 http://www.nylxs.com - Leadership Development in Free Software http://www2.mrbrklyn.com/resources - Unpublished Archive http://www.coinhangout.com - coins! http://www.brooklyn-living.com Being so tracked is for FARM ANIMALS and and extermination camps, but incompatible with living as a free human being. -RI Safir 2013
participants (8)
-
Dominik Dingel -
Greg KH -
Henrik Austad -
Miles Fidelman -
Mulyadi Santosa -
Nitin Varyani -
Ruben Safir -
Valdis.Kletnieks＠vt.edu