Priority-based scheduling for dependent processes using random selection of resource holders

Tarek Helmy*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)181-189
Number of pages9
JournalComputer Systems Science and Engineering
Volume28
Issue number3
StatePublished - May 2013

Keywords

  • Priority-based scheduling
  • Process dependency
  • Random selection
  • Resource holder

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Priority-based scheduling for dependent processes using random selection of resource holders'. Together they form a unique fingerprint.

Cite this