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.

Does mobile phones give more freedom to people?

Small essay for writing practice

Recently mobile phones are widely used by a lot of people. Although there is a controversy, I think mobile phones have provided more freedom to people. There are two specific reasons why I think mobile phones give more freedom.

First, mobile phones free people’s communication from a fixed physical location. Even though a telephone enables a person to communicate with another at distance, the person has to be at a specific location that the telephone is installed. On the contrary, with mobile phone, one can make or receive phone call while moving places. Thus, people can work more efficiently overcoming the limitation of physical location. For example, important business decision can be made in a car, or urgent meeting can be arranged in an airplane.

Second, using a mobile phone, one can put/get useful information to/from Internet with respect to a location in a timely manner because recent mobile phones provide location-free Internet connection. For example, navigation service in your mobile phone helps you to find the shortest or the least congested path to the destination when you are traveling a new place. Besides, you can post a movie clip during a travel to Internet through a mobile phone. The media is immediately shared among people who are connected to Internet, and it provides more realistic information. So, people don’t need to rely upon the mass media such as newspaper or news broadcast. This implies that mobile phone serves as a new media service platform, and enables people to freely distribute useful information without the help of mass media.

In conclusion, mobile phones have been developed for free communication in terms of location, and helps people to work more efficiently. Furthermore, it frees people from the limitations of current mass media. Personal news or useful local information can be easily shared with the help of recent mobile phones.

Game-theoretic approach vol. 3

To testify the assumption, we measure fairness and latency satisfaction. With the current credit scheduler, we run two domains: dom1 and dom2. dom1 has both I/O and CPU load, and dom2 has only CPU workload. By changing the CPU workload (0, 20, 40, 60, 80 and 100%), we observe the characteristics of the scheduler. Fairness is measured by the throughput (amount of work done during unit time), and latency is measured by the percentage of missed deadlines.

Air way plan

Itinerary:

From Incheon to Paris,
From Paris to Wien,
From Wien to Incheon

Vienna
to meet opera or classical music

I had not been to concerts for a long time
This year, anna-sophie has come to Korea, but I couldn’t go
Sorry for my un-attendance

Wish to meet magic flute at vienna

Game-theoretic approach vol. 2

Cont. from prev. Game-theoretic. article

A real-time virtual machine(VM) requires a strictly time-bounded I/O latency, and a non-real-time VM demands a guarantee for fair utilization for physical resources. I/O latency can be reduced by prioritization and preemption; fair utilization requires accurate accounting and compensation for lost execution time.

We define inter-VM scheduling game to determine how both VMs can be scheduled with satisfied. To define a pay-off function, we measure how much the domain is unsatisfied with scheduling.

To measure the unsatisfaction for the I/O latency, we can use statistical information. An example can be the probability of deadline miss. i.e. A domain is more unsatisfactory if the domain misses the more deadlines. Another example measure is the expectation for the latency over the deadlines. i.e. E[Min{(Latency - deadline),0}] can measure how the real-time domain is unsatisfactory. On the other hand, Jain’s fairness can be used for measuring how the non-real-time is unsatisfactory.

So, now we can provide a parametric unsatisfaction for scheduling with respect to I/O latency and CPU fairness. The key control parameter in the credit scheduler is the BOOST mechanism since it controls the temporal priority of a domain. If a domain is boosted, it can quickly run a task, so that the task meets the deadline. If I/O domains are not boosted, the credit scheduler will achieve fairness by giving the equivalent CPU time for all the domains.

We want to control the scheduler so that it can flexibly adjust latency or fairness levels. To control the CPU fairness or I/O latency level, BOOST can be flexibly controlled. If a domain wants to have a I/O latency with strict time bound, then it has to be boosted always, and it can handle events within a deadline. If a domain demands a strict fairness, (i.e. don’t want to get penalty by another domain) the boost has to be applied only when it doesn’t break the fairness.

We can find an optimal scheduler that boosts a domain with a probability in order to meet the required fairness as well as latency. Boost probability p_i decides how often the domain i is boosted. For current credit scheduler, CPU fairness is preserved, and applies boost for domains that have enough remaining credit. So, a latency sensitive domain have penalty; particularly when it has I/O and CPU mixed workload. Unfortunately, a real-world domain usually has CPU-I/O mixed workload; thus, it takes penalty with regard to latency. If a domain has CPU-intensive task, the domain is not boosted when the CPU-intensive task is running.

Game-theoretic approach on latency-bandwidth trade-off

This is a tech. article, so you can skip this if you are not interested in computer systems or systems virtualization.

Recently, I had an interesting observation on Xen-scheduler. Xen uses the credit scheduler, by default. You can refer the credit scheduler at other papers, articles, etc. (So, I will skip to explain this) Xen’s credit scheduler has been designed to preserve fairness among CPU-bound guest domains. This results in bad latency for time-sensitive applications (or domains). For mobile virtual machines that require real-time facilities, it is a critical problem. To support real-time, I/O latency has to be time-bounded, which is difficult with the current credit scheduler and split driver.

Keep it simple.

The first article on this blog.

This blog will include personal misc things and tech spots that I am focusing

Making a footprint on this site requires me a lot continuous effort and care

So, I try to focus on a few things enough to keep this work simple

Let us watch this out, the evolution of the site and me
...