Adaptive Task Allocation in a Distributed Workstation Environment

Abstract

A distributed workstation environment often displays extremes of very busy hosts and correspondingly idle hosts. By more evenly distributing processing load among these machines we achieve better average task turnaround and make more effective use of resources. Such load sharing can be categorized into three scheme types. In static task allocation, each host is assigned a subset of task types regardless of system load. Dynamic allocation uses this load information to dynamically assign tasks to lightly loaded hosts. Finally, adaptive task allocation matches task resource requirements to host resource availability. As background to this work, we describe task resource use and host resource availability in a typical distributed workstation environment. Remote execution in such an environment requires careful management so as to emulate local execution. We describe the options available when designing both a remote execution environment and the accompanying load sharing service. Several examples are described emphasizing the results of these design decisions. STARS is a task allocation facility supporting dynamic load sharing based on host statistics. It is built around a remote execution mechanism and a distributed information service DRUMS. This service collects and distributes both host information and task execution information. DRUMS is designed to achieve a high level of availability, to have minimum impact on the host systems, to adjust its processing capacity in response to changing demand, and to be easy to manage. Replication is used for both availability and performance. Adaptive task allocation requires the prediction of task resource usage. We accomplish this using a classification hierarchy borrowed from the field of AI. Three new construction techniques are demonstrated which provide significantly better prediction than that based on average resource use by task or standard classification. The adaptive allocation scheme employs resource usage feedback from remote task execution to derive better allocation rules. The predicted resource usage for a task is matched against the resources available on each host to find the best match. We show that in high load situations, adaptive task allocation performs better than either random or dynamic allocation.