| Today, The Internet technology is developing with high speed. User'srequirements for sharing resources are not only in the area of transmitdata, but also in using the resources that are distributed andheterogeneous. The application of Grid technology makes it possiblefor people to choose distributed and heterogeneous resources. Gridtechnology can organize isomerism resources crunodes to make avirtual system which can accept user's application, schedule and maptasks to Long Distance recourses. This virtual system affords a clearand high efficient environment to users. Because the special attributesof Grid, such as: dynamic, isomerism and distribution, we shouldchoose different scheduling strategy for different Grid system in orderto gain minimum executing time and load balance. We also want oursystem has transportability and extensibility.The Computing Grid shares distributed recourses. In ComputingGrid environment, computing recourses belong to virtual organizationsthat are located in different places. So the problem of load imbalanceor resources invalidated is inevitable. Large scale scheduling is a NPCompleted Problem, however, we have not found a better method toresolve it although we have used P algorithm for small scalescheduling already. Traditional methods for tasks scheduling andresources management are not fit for distributed systems, especially tothese high throughput distributed systems. In consideration of theownership and location of resources, we can not only use one methodto allocate resources. In this case, we have to find a general andefficient scheduling algorithm as soon as possible.Based on these basic requirements above, we presented alaminated resources management system. The user submitsapplications which are described with ClassAds to user-interface, andthen the interface transmits this task to Task Management Agency(TMA). TMA will record this submission. At this point, the user'ssubmission is completed. Then TMA will create a match tableaccording to resources circumstance that provided by predict recordstable.The steps as follow:Resources prediction model submits a junior resources recordstable which records the using circumstance of resources in nexttime quantum to SA, and then the table is waiting for retrieval.Scheduling program retrieves the junior resources records tableaccording to the attributes of tasks in Task Queue, and thencreates a final resources match table.SA transmits the final resources match table to TMA.TMA will map the tasks to Grid resources based on the finalresources match table. The tasks will be transmitted to local orlong distance Globus Gatekeeper by tasks submission service.Finally, Globus actuates Job manager, and then the Jobmanager will submit the executing result of tasks to a certainplace that determined by Grid. The tasks executing condition willtransmit to SA at the same time.Users can monitor the executing conditions of tasks at any time byusing the monitor service that supplied by our system.We choose Min-Min algorithm as a matching strategy. The purposeof using Min-Min algorithm is that we want to gain the shortestexecuting time by the mechanism which we allocate tasks to theresources that can execute tasks earliest and fastest. First, wecompute one task's executing time on each machine, and gain the IDof the machine that has the earliest and the fastest executing time. Weallocate this machine to this task, and update the Ready Time of themachine, and then delete the task from Task Queue. Repeat thisprocedure until all the tasks have their machines. In general, if thereare two tasks completing the same machine, we will allocate thismachine to the one which can update the Ready Time to minimum. Inthis way, we can gain a minimum Makepan of all the tasks.In view of the dynamic property of Grid, resource failure maybehappens when tasks execute on long distances resources. However,resources failure does not main that the resource loses its computingability completely. It maybe just loses part of computing ability in acertain period. At this point, we need a criterion to determine whetherthe tasks that execute on the failure machine should be migrated to anew machine. For this reason, we update Min-Min algorithm. We set athrottle to measure whether the tasks should be migrated under theresource failure condition in future when we schedule the tasks withMin-Min algorithm. If the resource failure is emerging, the executingtime of tasks under the new condition will be recomputed. The taskswill be migrated to new machines if it is benefit for finishing time of thewhole tasks. This update algorithm has dynamic property and faulttolerance property which accord with the purpose of Grid.In the future, we suppose to use different algorithm to schedule tasksunder different granularity conditions, and perfect our Self-AdaptiveTasks Scheduling System. |
