It’s high time now that I start coding for my BTP so as to arrive at some result by the next month. However, I am yet to resolve all the analytical issues related to my problem. The biggest of my worries being a mathematical bound over the under-allocation that a task could suffer when scheduled using the algorithm I am working on.
Let me start from the beginning. I have taken up as my BTech project the topic of scheduling tasks on multi-processor system. PPC alloted me to Mr. Arnab Sarkar (Arnab da I call him). I have been working with him for the past few months to arrive at an optimised solution to our problem.
The problem that we are tackling is that there exists an algorithm called ER-Fair which schedules tasks proportionately on a multi-processor system. Arnab da in his research improved the time complexity by using frames. He divided the time into frames, of equal sizes and then alloted the tasks to these frames. Inside the frame, ER-Fair scheduling can be used to arrive at fair scheduling. The drawback was that ER-Fair requires a higher time complexity than a simple Round Robin algorithm. So the motivation was to replace the ER-Fair algorithm by an O(1) round robin algorithm without compromising on the fairness.
VTRR is one such algorithm. But then I was not able to derive any mathematical bounds for the maximum under-allocation that a task can suffer when scheduled using the VTRR algorithm, and by definition VTRR does not guarentee against under-allocation. So we could be losing fairness if we used just the VTRR algorithm. One pathological case where this happens is when there are 4 tasks to be scheduled and they have weights of 9, 1, 1, 1. The VTRR algo then schedules Task A, B, C, D and only then returns back to again schedule A. But by this time A has been under-allocated. Now consider a system where there are many more tasks than just 4, this boundary case implies a huge deviation from the required fairness.
We found a way around this by using groups within frames. Tasks are divided into groups on the basis of their shares. This ensures that all tasks of similar weights are put into the same group, therby avoiding the occurance of any case as mentioned above. The weight of the group would be the combined weight of all the tasks. To the external scheduler, a group would appear as a single task which needs to be scheduled. Since we shall be creating fixed number of groups, using ER-Fair algorithm for scheduling the groups should take only O(1) time.
The tasks within a single group can be scheduled using VTRR algorithm. But I met with the smae problem once again, that of deriving the bounds for the under-allocation. This very evening though, Arnab da found another interesting algorithm. It is a slight modification of the VTRR algorithm and performs better in the same complexity range. This one works with ensuring that the error (defined as the amount of work received less what the task should have been serviced) never exceeds 1. If it does, then either the first or the next task is selected on the basis of which task has lesser error. Being a simple round robin algorithm, it is O(1) and easier to implement than the VTRR. Also I have managed to come up with a few equations to bound the under-allocation. I am not getting my hopes high yet, not until Arnab da checks it and finds it right.
Also we met PPC today. It was mostly Arnab da and him discussing the problem and the solution, I was just a third person observer. PPC said the idea is good and told me to come up with some analytical result as to what would be the optimal way of putting the tasks into groups. Also, he said if we code the algorithm and if the observation of under-allocations vs. number of groups comes out as a rectangular hyperbola, dipping quickly as the number of groups increases, then it could be a successful experiment. The reason is that if the number of groups is 1, then the system is equivalent to VTRR which does not have bounded under-allocation, and if the number of groups equals the number of tasks, then the system is effectively being scheduled using just the ER-Fair algorithm which is not O(1). So if we can show that the idea of a few groups can schedule the system in O(1), it’ll be successful work.
Popularity: 1% [?]
Related posts:
