期刊名称：International Journal of Grid and Distributed Computing
印刷版ISSN：2005-4262
出版年度：2011
卷号：4
期号：2
页码：Grid-Computing
出版社：SERSC
摘要：A Computational grid is highly useful computing infrastructure that enables effective access of resources to perform high performance computing wherein job management, efficient resource utilization are key grid service issues. To make grid environment greatly useful, an optimized scheduling system is essential as computational grid is often heterogeneous with complex environment. This complexity raises difficulties in gathering the load information of computational resources as well as coping up with user needs specifically when users dealt with jobs. Other existing fact of grid computing is that it is best known for handling batch job rather than interactive job submission. Interactive Job submission is useful in situations when a job requires human intervention to control the job result. This research paper tries to satisfy the requirements of the user by developing user driven scheduler. We have developed a scheduler here after referred as NGSched compatible with Globus and hence provides user on-demand and interactive access to grid resources. It adopts novel approach for scheduling multiple jobs by giving privileges of resource selection to the user. The proposed and implemented algorithm also satisfies the deadlines given by the user for job execution on the selected resources and balances the load on grid nodes. The proposed heuristic also calculates the share of each resource according to capability to handle load. Since this scheduler is user centric, it facilitates the user to monitor the job, cancel the job, schedule on selected resources, suspend and resume the job. Results obtained proved that our innovative algorithm is better and efficient.
关键词：Grid Computing; Resource Selection; Optimized Load balancing; Interactive ;Job Submission ;1.;Introduction ;Grid Computing is concerned with coordinated resource sharing and problem solving in ;dynamic; multi-institutional virtual organizations. The coordination between multiple ;administrative domains leads to complexity & heterogeneity in grid environment. The ;resources that Grid computing is attempting to integrate are varied. The most common ;resource is computing cycles provided by the processors of the machines on the grid. The ;processors can vary in speed; architecture; software platform; and other associated factors; ;such as memory; storage; and connectivity[1].They also can be of different types like ;supercomputers; workstations; databases; storages; networks; software; and special ;instruments; advanced display devices; cache; CPU cycle and so on. Amongst these; resource ;as CPU cycles is considered by NGSched for provisioning; job execution and balancing the ;load. The Grid also includes coordinated problem solving;which is beyond simple client–;server paradigm; leading to more challenges for handling jobs[2]. Users who are the resource ;consumers adopt the strategy of solving their problems at low cost within a required ; var currentpos;timer; function initialize() { timer=setInterval("scrollwindow()";10);} function sc(){clearInterval(timer); }function scrollwindow() { currentpos=document.body.scrollTop; window.scroll(0;++currentpos); if (currentpos != document.body.scrollTop) sc();} document.onmousedown=scdocument.ondblclick=initializeInternational Journal;of ;Grid and Distributed Computing;Vol. 4;No. ;2; ;June;2011;2 ;timeframe [17]. The resource providers adopt the strategy of obtaining best possible return on ;their investment while trying to maximize their resource utilization and hence efficient ;scheduling mechanisms plays key role. ;An organization can lease selected resources to solve large computation problems. ;Resources owned by various administrative organizations can be shared under locally defined ;policies satisfying the criteria defined and adopted by user as well as resource owners. ;Harnessing unused CPU cycles can give huge benefits to corporations and provide cost ;benefits too[3]. To achieve the promising potentials of computational Grids; an effective and ;efficient scheduling strategy is defined and implemented as stated further in this paper. If a set ;of standalone jobs are to be executed with no interdependencies; then a specialized scheduler ;may not be required. However; if it is desired to reserve a specific resource or to ensure that ;different jobs within the application run concurrently (for instance; if they require inter-;process communication); then a job scheduler should be used to coordinate the execution of ;the jobs[4]. Prioritizing user and his expectations in the form of deadline achievement for ;completion of jobs and opportunity for resource selection for deployment of jobs are handled ;by our user centric scheduler. These tasks are done by algorithm by balancing the ;computational cycles load in the grid environment. ;2.;Related Works ;A set of algorithms has been designed by researchers to identify best resources and ;schedule Jobs to heterogeneous computing systems. Scheduling algorithm employed in [6] ;describes the mean load based on task predictive execution time as heuristic information to ;obtain an initial scheduling strategy and then reduce the load of the machine with higher-load ;at the fastest speed. Min-min algorithm [14] starts with a set of all unmapped Jobs. The ;completion time for each job on each machine is calculated. The machine that has the ;minimum completion time for each job is selected. Then the job with the overall minimum ;completion time is selected and mapped to the machine. Again; this process is repeated with ;the remaining unmapped Jobs.Min-min[13] begins with a set of all unmapped Jobs. The ;completion time for each job on each machine is calculated. The machine that has the ;minimum completion time for each job is selected. From the set; the algorithm maps the job ;with the overall maximum completion time to the machine. Again the above process is ;repeated with the remaining unmapped Jobs. Similar to Min-min; Max-min also considers all ;unmapped Jobs at a time. [7] contributes with the mean of all machines completion time is ;taken. The machine whose completion time is greater than the mean value is selected. The ;tasks allocated to the selected machines are reallocated to the machines whose completion ;time is less than the mean value. Scheduling is a process that maps and manages execution of ;inter-dependent tasks on distributed resources. Scheduling algorithm implemented by [9] ;provides distinct functionalities; such as dynamic workflow planning and just-in-time ;scheduling in a grid environment. Serve On Time algorithm proposed in [11] is based on the ;idea of combining all the dynamic multi tasks so that all the tasks will obtain the rights to be ;served as soon as possible The highly effective dispatch strategy or algorithm may fully use ;the processing ability of the grid system; and then enhances application procedure ;performance. [22] Proposes workflow based scheduling algorithm. Workflow is concerned ;with the automation of procedures; whereby files and other data are passed between ;participants according to a defined set of rules in order to achieve an overall goal. Developers ;of Nimrod-G broker[15] claimed that this is the only system that supports resource allocation ;and application scheduling algorithms driven by users. quality of service requirements. ;Paper[10] describes Genetic algorithm which uses the GA.s searching technique to find a
