| Grid resource management plays an important role while enabling the sharing and coordinating of resources in Grid computing environments. Generally, Grid resource management is defined as the process of discovery, coordination, allocating, scheduling and monitoring for Grid resources. Advance reservation(AR), co-reservation and co-allocation(co-scheduling) constitute the main body of Grid resource reservation system. An advance reservation is a scheduling object which reserves a group of resources for a particular timeframe for access only by a specified entity or group of entities. When the needs of a single application exceeds the capacity available in any subsystem making such a system, co-allocation, i.e., the simultaneous access to resources of possible multiple types in multiple locations and belong to multiple management domains, may be required. Co-reservation can be used to reserve multiple resources for simultaneous access while co-allocating. Based on existing research results for reservation-supporting grid resource management and scheduling, this paper investigated the reservation-supporting resource management and scheduling models for grid computing environments in the context of single machine, parallel machine and co-allocated multiple machines were used, puts forward some scheduling algorithms and analyzes their performances from the viewpoints of system utilization, scheduling makespan, response time and extension factor. This paper also developed a discrete-event driven, object-oriented open Grid simulation toolkit that supports simulation of reservation-based scheduling to allow repeatable performance evaluation under different scenarios. When multiple users or applications share a space-shared single machine in a non-preemptive way, advance reservations guarantee the availability of resources for AR jobs and at the same time partition the future timeframe into discontinuous sections and limit the allocation for non-AR jobs. This paper put forward the problem to allocate non-AR jobs into these discontinuous sections to maximize the system utilization and to minimize the total scheduling length of non-AR job and modeled this NP-hard deterministic availability-constrained scheduling problem as a variant of variable-sized bin packing (VVSBP) problem. According to the distribution of active advance reservations when scheduling online-incoming non-AR jobs, three scheduling sceneries, i.e., online, offline and scheduling with lookahead are considered and they were mapped respectively to the online, offline and bounded space bin packing of the VVSBP problem. Algorithms for classic bin packing were extended for the three versions and their worst-case and average-case performances were analyzed and simulated. EASY backfill and conservative backfill are two important parallel scheduling algorithms. The procedures to support advance reservation in these two algorithms were examined and the performance differences between the two algorithms while supporting reservation, including utilization, average slowdown and average weighted response time were examined by simulation. It is shown that EASY backfill is generally more favorable. The problem about how to support advance reservation among static and dynamic co-allocating jobs was put forward. The procedures and the performances of FCFS and EASY backfill were investigated when supporting advance reservation in both dynamic and static co-allocating environments. The effects on performance measures of FCFS and EASY backfill, including system utilization, average slowdown and average weighted response time of jobs, resulting from changing advance reservation rate, advance reservation time and the accuracy of estimated execution times of jobs were investigated with simulation. A discrete-event driven, object-oriented open Grid simulation toolkit that supports simulation of advance reservation, co-reservation, co-allocation in parallel or Grid-like computing environments was developed.
|
PDF Full Text Request