Priority-Based Scheduling for Dependent Processes Using Random Selection of Resource Holders

摘要

Modern operating systems support execution of cooperating processes. Interactions among these cooperating processes often result in dependencies in which a given process cannot continue executing until one or more other processes complete their tasks. Priority-based schedulers for these dependent processes suffer from the priority inversion problem where a high priority process is blocked on a resource that is held by a lower priority process. In this paper, we introduce a new priority-based scheduling approach that takes both process dependencies and dynamic priorities into account. We have developed a new algorithm for selecting the resource holders that should be given the chance to execute in order to release their respective resources. This algorithm is based on random selection of the resource holder in order to reduce overhead processing of the scheduler. Typically, selecting the process that can release a held resource is a difficult problem and needs some kind of prediction mechanism to determine which process to select. However, the proposed algorithm for selecting the resource holder eliminates the need for such prediction mechanisms, which leads to a dramatic reduction in processing overhead. An analytical model of the average waiting time in the ready queue of the proposed scheduler is developed. We simulated the proposed scheduler and compared its results both with the results of the analytical model and the results of SWAP as a similar scheduler. Simulation results show that the proposed scheduler has low overhead processing and superior performance, especially in the case of high loaded systems.