یک ​امتیاز دهی تطبیقی الگوریتم زمان بندی شغلی برای محاسبات شبکه

When human culture advances, current problems in science and engineering become more complicated and need more computing power to tackle and analyze. A supercomputer is not the only choice for solving complex problems any more as a result of the speed-up of personal computers and networks. Grid technology, which connects a number of personal computer clusters with high speed networks, can achieve the same computing power as a supercomputer does, also with a lower cost. However, grid is a heterogeneous system. Scheduling independent tasks on it is more complicated. In order to utilize the power of grid completely, we need an efficient job scheduling algorithm to assign jobs to resources in a grid. In this paper, we propose an Adaptive Scoring Job Scheduling algorithm (ASJS) for the grid environment. Compared to other methods, it can decrease the completion time of submitted jobs, which may compose of computing-intensive jobs and data-intensive jobs.

When science and technology advance, the problems encountered become more complicated and need more computing power. In contrast to the traditional notion of using supercomputers, grid computing is proposed. Distributed computing supports resource sharing. Parallel computing supports computing power. Grid computing aims to harness the power of both distributed computing and parallel computing. The goal of grid computing is to aggregate idle resources on the Internet such as Central Processing Unit (CPU) cycles and storage spaces to facilitate utilization. The Search for Extra-Terrestrial Intelligence (SETI) experiment [31] is an early application of grids. The data Trans-Atlantic Grid project (TAG) [32] constructs a large-scale intercontinental grid testbed which focuses on issues of advanced networking and interoperability between these intercontinental grid domains, hence extending the capabilities of each and enhancing the worldwide program of grid development. In implementation, Globus Toolkit [33] is an open source and a fundamental enabling technology for grid. The latest version of Globus Toolkit is Globus Toolkit 5.2.0. Grid can achieve the same level of computing power as a supercomputer does, but at a much reduced cost. Grid is like a virtual supercomputer. However, we need to consider about many conditions such as network status and resource status because the members of grid are connected by networks. Grid is also a heterogeneous system. Scheduling independent tasks on it is more complicated. In order to utilize the power of grid computing completely, we need an efficient job scheduling algorithm to assign jobs to resources. This paper focuses on the efficient job scheduling considering the completion time of jobs in a grid environment. General task scheduling is an NP-Complete problem [17] and is an integral part of parallel and distributed computing [11]. How to schedule task in a grid environment efficiently is a new challenge because grid is a distributed and heterogeneous system. To shorten completion time and enhance the system throughput is the purpose of a job scheduling algorithm. Because the status of grid environment may change at any time, the traditional job scheduling algorithm, e.g. “First Come Fist Serve” (FCFS), “Fist Come Last Serve” (FCLS), etc., may not adapt to the dynamic grid environment well. This paper proposes a new framework and scheduling algorithm to decrease job’s completion time in a grid environment. Computing intensive jobs and data intensive jobs are handled differently, reflecting the real time grid situations. We assign a new job to a resource depending on the result in the past job scheduling. We select the most appropriate resource for the current job. Local update and global update are used to get the newest status of resources in Grid environment. According to the local update and global update results, we can schedule jobs more dynamically and appropriately. A new gauge structure for the current situation and a new job scheduling algorithm is proposed. The algorithm is called Adaptive Scoring Job Scheduling (ASJS) algorithm. We compare ASJS with Ant Colony Optimization (ACO) [21], Most Fit Task First scheduling algorithm (MFTF) [18] method and random selection method in the experiments. According to the results of experiments, ASJS is capable of decreasing the completion time of jobs better than other job scheduling algorithms mentioned above. In recent years cloud computing has become an important part of computer systems [1] and [2]. Its centralized data center approach is different from grid computing approach. Its transaction based processing is also different from the batch processing of grids. That is, scheduling for thousands of processors in a data center is basically focused on response time and load balance. Scheduling algorithms for grid computing may not be able to be directly applied. However, when performing backup or load distributing between data centers, our scheduling algorithm could be a very useful reference [8]. The remainder of this paper is organized as follows. Section 2 gives an overview of previous work about job scheduling in grid environment. Section 3 introduces the framework and job scheduling algorithm we propose. The implementation and experiments are given in Section 4. Finally, Section 5 concludes the paper and proposes some future work.

In this paper, we propose an adaptive scoring method to schedule jobs in grid environment. ASJS selects the fittest resource to execute a job according to the status of resources. Local and global update rules are applied to get the newest status of each resource. Local update rule updates the status of the resource and cluster which are selected to execute the job after assigning the job and the Job Scheduler uses the newest information to assign the next job. Global update rule updates the status of each resource and cluster after a job is completed by a resource. It supplies the Job Scheduler the newest information of all resources and clusters such that the Job Scheduler can select the fittest resource for the next job. The experimental results show that ASJS is capable of decreasing completion time of jobs and the performance of ASJS is better than other methods. In the future, we will apply ASJS to real grid applications. This paper focuses on job scheduling. We will modify ASJS to consider division of file and the replica strategy in data-intensive jobs. Jobs are independent in this paper, but they may have some precedence relations in real-life situation. We will study and improve ASJS for such kinds of jobs in the future.