An Analysis of Partially Clairvoyant Scheduling

Real-time scheduling problems confront two issues not addressed by traditional scheduling models, viz., parameter variability and the existence of complex relationships constraining the executions of jobs. Accordingly, modeling becomes crucial in the specification of scheduling problems in such systems. In this paper, we analyze scheduling algorithms in Partially Clairvoyant Real-time scheduling systems and present a new dual-based algorithm for the feasibility problem in the case of strict relative constraints. We also study the problem of online dispatching in Partially Clairvoyant systems and show that the complexity of dispatching is logarithmically related to the complexity of the schedulability problem.