Design and evaluation of processor management techniques in parallel and distributed computing environments
Chita R. Das, Byung S. Yoo · 1998
Processor management in multiuser, multicomputer operating systems plays a crucial role in obtaining high system performance. A processor management scheme consists of two components: processor allocation and job scheduling. A processor allocation algorithm locates and assigns free sub-systems to requesting jobs. A job scheduler is concerned with selecting the next job to be executed. The objective of this research is to design and evaluate efficient allocation and scheduling-schemes with low complexity for meshes and k-ary n-cubes. First, a very first and efficient allocation algorithm is proposed for mesh-connected multicomputers. This algorithm, which can be implemented efficiently using a stack, is the fastest submesh allocation scheme reported so far in the literature. Second, a set of scheduling alternatives are developed for meshes. Two of the proposed scheduling algorithms change the order in which jobs are executed to reduce queueing delay. Third, a multiprogramming technique is developed to execute jobs allocated to different virtual meshes in a time-sharing fashion. A novel technique to simulate a torus architecture with a mesh by using the multiprogramming technique is also introduced. Next, a new allocation scheme that scales down the size of a job, when an attempt to allocate the job fails, is proposed. This scheme not only reduces external fragmentation but also can serve as an ideal allocation algorithm for fault-tolerant mesh systems. It is shown that all these schemes can improve the system performance significantly compared to conventional FCFS scheduling. Next, a unified processor management technique for k-ary n-cubes is proposed. Using multiprogramming of jobs, this technique can support different types of jobs efficiently and can out-perform all the existing schemes. Two very fast allocation algorithms are also developed to minimize the allocation overhead. Finally, an analytical model, based on a multiple-server queueing model, is introduced for mesh systems. This technique combines simulation and analytical modeling to analyze the performance of mesh-connected multicomputers without including high computational overhead.