A Fast and Efficient Processor Management Scheme for k-ary n-cubes1

Job scheduling and processor allocation are two key components of processor management technique in a multiprocessor operating system. We propose a fast and efficient processor management technique, called virtual cube (VC), fork-aryn-cubes in this paper. The proposed scheme supports spatial allocation of jobs to the virtual cubes of the system and multiprograms the virtual cubes in a round-robin fashion. The objective here is to reduce job waiting time and fragmentation. The VC scheme uses a fast subcube allocation algorithm called enhancedk-ary buddy. A novel approach, called paging, is proposed for fast submesh allocation. When used with the first fit algorithm, the paging scheme is shown to be extremely fast and efficient compared to other contemporary submesh allocation algorithms fork-aryn-cubes. We also study the impact of page size on performance and illustrate a methodology to compute optimal page size. Simulation results show that the VC scheme with its multiprogramming capability can boost system performance considerably and outperforms all existing policies while incurring minimal run-time overhead.