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.
Thursday, April 28, 2011
Wednesday, April 27, 2011
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.
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
...
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
...
Subscribe to:
Posts (Atom)