This paper proposes hierarchal scheduling schemes for Grid systems: a self-discovery scheme for the resource discovery stage and an adaptive child scheduling method for the resource selection stage. In addition, we propose three rescheduling algorithms: (1) the Butterfly algorithm in order to reschedule jobs when better resources become available, (2) the Fallback algorithm in order to reschedule jobs that had their resources taken away from the Grid before the actual resource allocation, and (3) the Load-Balance algorithm in order to balance load among resources. We also propose a hybrid system to combine the proposed hierarchal schemes with the well-known peer-to-peer (P2P) principle. We compare the performance of the proposed schemes against the P2P-based Grid systems through simulation with respect to a set of predefined metrics.
Grid Scheduling Stages
Grid characteristics must be taken into account in order to perform efficient scheduling. Grid schedulers must make scheduling decisions in a very challenging environment that includes: (1) no control over the resources, since they don’t own them; (2) distributed resources; (3) a dynamic existence of resources (i.e., resources may be added or removed from the grid at any time); (4) a dynamic information collection; (5) heterogeneous resources (jobs must match appropriate resources in order to be executed as requested by the users); and (6) tentative scheduling until the allocation of actual resources (i.e., resources may be taken from the grid before a job actually uses them).
In general, grid scheduling is performed in three stages (Nabrzyski, Schopf, & Weglarz, 2004). First is the resource discovery stage, which produces a set of matched resources. Schedulers are expected to collect static information (e.g., operating systems) from local schedulers or general information systems (GIS), in order to perform job matching. In the next stage, resources are selected (i.e., resource selection stage) from the list obtained during the first stage and are expected to meet user’s imposed constraints (e.g., deadlines). Then schedulers are expected to collect dynamic information (e.g., system load) for the third stage and transfer jobs to selected resources (i.e., job execution stage).