Round robin techniques is one of the most popular scheduling algorithms but the problem with that is more context switches, more waiting time. And yes the response time is good in this case.
But what if we can have different time slices for different processes?
And are there any good modifications to the basic RR algorithm which applies to Distributed/ Parallel computing scenario.
Any suggestion in this regard will be very helpful.
Edit:
The scheduling should be done on the below environment
Online System with symmetric processing stations.
throughput, response time,
And approximate schedule
The reason something like Round Robin is excellent for Parallel computing is because round-robin is great for load balancing if the tasks are around the same lengths. That being said, maybe considering a weighted variation of the scheduling problem is useful to identify and research. Also it depends on what type of scheduling you are doing. Time splicing is great if the tasks are offline (that is, we already have all the tasks determined) and this will do great ideally in a parallel environment. If the tasks are online (are added and removed in real time) then it becomes a little more difficult. Also, we have to consider what you exactly need to minimize in your scheduling. Is it just the deadline? The load of the parallel machines? The makespan?
You may see what I am getting at. Scheduling is a very "general" term. Round robin has been around so long because it is very easy to implement and often is easier to translate into things such as hardware via table lookups. Unless you specify what exactly you want from your scheduling algorithm, it isn't clear what would be the "better" approach.
If you are looking to minimize the deadline, ask yourself the following questions:
-How do I want to minimize it? Minimize the makespan? Minimize load?
-What kind of parallel machines? Identical (homogeneous)? Unrelated?
-Optimal or approximate schedule lengths?
Depending on these three questions you can be dealing with a very easy problem which round robin (in an online environment) works pretty well, or with a very computationally intensive problem (i.e., makespan problem on identical, or even unrelated parallel machines is known to be NP-hard).
Some of my suggestions should be enough to help, but it may be useful for this question to specify your problem more clearly. The machine type is very important in scheduling.
If you want to manage different time slices for different processes, you can have a look to the virtual processor scheduling model. A modern version of this idea can be found with the MLQ (Multi Level Queue) scheduling algorithm where you can manage the different queues with differents quantum. Each quantum can also be dynamically computed according to several parameters (CPU load, number of processes in each queue, etc...).
Fair channel access can be obtained by Round Robin scheduling algorithm at mac layer but does it support real-time traffic?
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms