Congruence in virtualization

<behavioral congruence within virtualization>

In a virtualization environment, task execution is difficult to be analyzed. Since virtualization layer hides all the physical operations and exposes only a small subset of hardware, the actual physical behavior under the virtualization layer can be largely different from the observed behavior over the virtualization layer. For example, all task execution within a guest OS is based on the virtual time of the guest OS; however, the actual execution with physical time is differently presented, and real-time applications would miss physical deadlines, which makes difficult to incorporate real-time OSs within virtualization.

To present behavioral equivalence within virtualization, event serialization is definitely not enough. Even though events occurs consecutively in the same order, it cannot catch the timeliness of the execution. Timed automata or timed Petri-net tried to address timely execution; however, they also have limitations with respect to the state space. Since they project all the execution behavior to every time instants, the state space increases as much as the execution time. This makes difficult to analyze behavior deterministically since the halting problem is a well-known decidability problem, which is NP-hard. Namely, those timed analysis techniques are too complex, hence they are not directly applicable in scalable virtualization system.

To address timeliness within virtualization, I think, we can use the notion of real-time schedulability. Within a virtualization system, physical execution of a task is determined by the hypervisor instead of a guest OS, so a guest OS cannot impose task execution at a specific physical time instant. Namely, timeliness is difficult to define with a single time instant. Instead, we focus on the execution within a time duration. If a task is executed in a physically timely manner, then it should be executed not too late. Schedulability guarantees that tasks within a system meet deadlines, which means tasks are executed ‘not-too-late’.

In traditional real-time scheduling theory, schedulability tests are defined with a task set and scheduling algorithm. Schedulability tests determine whether all tasks can complete their execution within respective deadlines through the algorithm. For example, if tasks in the set are periodic, and the summation of their utilization is not more than 100%, then all tasks are schedulable with EDF (i.e. EDF schedulable).

In a virtualization system, schedulability of a task is difficult to define since scheduling is performed at two different levels. At first, inter-VM scheduling (or VCPU scheduling) is performed at the virtualization layer (inside a hypervisor). Secondly, intra-VM scheduling (or task scheduling) is separately performed over the virtualization layer (inside the guest OS). Inter-VM scheduling is performed by the hypervisor that doesn’t have any task information inside a guest OS. Instead of scheduling each tasks within guest OSs, the hypervisor simply schedules VCPUs that are given to each virtual machine. To schedule VCPU, each VCPU requires scheduling a parameter that represents all the execution of a guest OS.

Intra-VM schedulability is not easily determined because task execution is determined not only by task set and intra-VM scheduling algorithm, but also by inter-VM scheduling parameter of the guest OS, and inter-VM scheduling algorithm. This
Inter-VM schedulability can be easily determined provided that the scheduling parameters are given.