Resource scheduling for local computer systems with a multiaccess network

摘要

Resource scheduling maps requests to a pool of resources to optimize a combination of resource usage, response time, network congestion, and scheduling overhead. The overhead of collecting the necessary status information for the scheduler is usually high, which results in the use of outdated status information and a degradation of performance. In this paper, we study resource scheduling based on a distributed state-dependent discipline for a system of processors connected by a local multiaccess network. The scheduling problem is reduced to the identification of the extremum from a set of physically dispersed random numbers. We propose a method of utilizing the primitive operations of collision detection and broadcast in multiaccess networks to efficiently distribute status information and to identify the extremum. The optimal performance of identifying the extremum is found to be constant on the average independent of the number of contending processors. The protocol can be implemented either by minor hardware modification of existing multiaccess-network interfaces or in software.