AN IMPROVED BACKFILL ALGORITHM IN CLOUD METASCHEDULER

Abstract

The contribution of this dissertation is to design and implement an improved backfill algorithm which increases the utilization of resources and take care of job priorities as well as workflow applications. Backfill Algorithm is a technique in which shorter jobs are move forward and run in parallel with the currently running job's provided sufficient resources are available for the execution of this job and the procedure should not delay the next queued job. EASY (Extensible Argonne Scheduling System) and Conservative algorithms are considered as traditional backfill algorithms which are widely used for the effective utilization of resources. Balanced Spiral Method is used to further improve the effective utilization of these resources. There are some issues related to this algorithm. First issue is Balanced Spiral Method does not consider workflow applications. Second issue is the above said algorithm does not consider the job priorities and third issue is resources are not fully utilized. In this dissertation to make Balance Spiral Method work for workflow applications a Dynamic Grouping Method is proposed which uses a DAG (Directed Acyclic Graph) structure to handle job dependencies. DAG is created based on job dependencies and from this DAG creating Dynamic Groups where jobs in (k+1)th "group are dependent on jobs in kth group and execution of jobs in kth group will finish earlier to job's in (k+l)th group . A technique which uses a Multi Queue structure instead of a single structure is proposed to handle job priorities. Here jobs are assigned to different queues based on their priority. More jobs are taken from queue with high priority jobs as compared to queue with low priority jobs to forma specific group on which our scheduling algorithm is- applied. This reduces the waiting_time of high priority jobs as well as avoids starvation of low priority jobs. For the effective utilization of resources a technique known as `Doubling run time estimations' is proposed. Doubling run time does allow shorter jobs to come forward, hence implement a SJF (Shorter Job First) like policy. Experimental results have shown that doubling run time estimations increases the resource utilization and hence increase the performance of system.