Real-time Scheduling
Real-time scheduling requires a physical time information because the scheduling should be performed very accurately.
However, in a virtual machine, tick interrupt is delivered only when it is in execution.
Thus, guest OS scheduling is performed based on tick consuming.
Namely, guest OS schedules processes based on virtual time.
In consequence, real-time scheduling is hard to be preserved in a virtual machine environment.
Compositional scheduling helps to deal with the real-time scheduling problem.
Compositional scheduling is a scheduling theory that applying composition rule to real-time scheduling of a complex system.
By the theory, multiple real-time scheduling systems can be hierarchically composed while preserving components' real-time property.
It changes the global timing problem in a real-time system into a bandwidth allocation problem;
thus, real-time property is kept by simply allocating the resource bandwidth more than the lower bound.
However, it is not directly applicable to the real systems because it does not uses tick-based bandwidth allocation.
Although it gives the lower bound of required bandwidth, in a tick-based scheduling system, the bandwidth should be translated to a number of ticks.
It could be considerable when the scheduling period is small. Note that the abstraction overhead increases as the scheduling period, in general.
So, we use the following algorithm that finds the optimal scheduling period and execution time.
It find the smallest bandwidth consuming (period, execution time) pair.