Good processor management = fast allocation+efficient scheduling

Fast and efficient processor allocation and job scheduling algorithms are essential components of a multi-user multicomputer operating system. In this paper, we propose two novel processor management schemes which meet such demands for mesh-connected multicomputers. A stack-based allocation algorithm that can locate a free sub-mesh for a job very quickly using simple coordinate calculation and spatial subtraction is proposed. Simulation results show that the stack-based allocation algorithm outperforms all the existing allocation policies in terms of allocation overhead while delivering competitive performance. Another technique, called group scheduling, schedules jobs in such a way that the jobs belonging to the same group do not block each other. The groups are scheduled in an FCFS order to prevent starvation. This simple but efficient scheduling policy reduces the response time significantly by minimizing the queueing delay for the jobs in the same group. These two schemes, when used together can provide faster service to users with very little overhead.