Editing
CPU Scheduler
(section)
From Linix VServer
Jump to navigation
Jump to search
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Token Bucket Examples == === Hard Limit === The simplest configuration is to just give every context an upper bound for CPU allocation. The important factor is the ratio: <center><math>\frac{R}{T} \cdot 100 = \%\mbox{ CPU allocation}</math></center> Note that this is the proportion of a ''single'' CPU in the system. So, if you have four CPUs and you want one context to get an average of one whole CPU to itself, then you would set fill-rate to 1 and interval to 4. It is advantageous to smooth operation of the algorithm to make the interval as small as possible (or much smaller than the bucket size). You can in most cases simplify the fraction, such as changing 30/100 to 3/10. === Burst time === To penalize processes after a certain amount of ''burst time'', i.e. putting them on the hold queue, you can use the maximum size S of the bucket and the minimum number of tokens M to ''hold'' processes. Consider a context with a limit of 1/2 of CPU time, a bucket of 15000 tokens and a minimum of 2500 tokens. Given that your scheduler runs at 1000Hz, processes that have used the CPU for 30 seconds will be put on hold for 5 seconds. The following formula can be used to calculate S and M, using ''B'' as burst time and ''H'' as hold time: <center><math>M = \mbox{Hz} \cdot H \cdot \frac{R}{T}</math></center> <center><math>S = \mbox{Hz} \cdot B (1 - \frac{R}{T})</math></center> === Guarantees === A guarantee is nearly the same as a pure hard limit, except that you must not allocate more than 100% CPU time to all contexts. In other words, if you have ''N'' contexts and give each one a guarantee of more than 1/N CPU time, it would result in more CPU time needed than physically available, which cannot work out. The important factor here is the sum of all ratios: <center><math>\sum_{i=1}^N \frac{R_i}{T_i} \le 1</math></center> === Fair Share === The fair share configuration is similar to guarantees, except that if the CPU is idle, a context can allocate more CPU time than its guarantee/limit. The scheduler and bucket configuration was extended in Linux-VServer 2.1.1 to allow fair share scheduling and is also know as ''IDLE time''. Consider a configuration with 5 contexts each limited to 1/5 of CPU time, where two of these contexts run CPU intensive processes and the rest is idle. Given that each context may only allocate 1/5 of CPU time, 3/5 of CPU time are wasted since 3 contexts are idle. To distribute the wasted CPU time ''fair'' among contexts that could need it, you can configure an allocation ratio for R/T during idle times, namely ''R2''/''T2''. To calculate the cpu distribution for context ''k'' the following formula is used: <center><math>\left ( \frac{C \cdot \frac{R2_k}{T2_k}}{\sum_{i=1}^N \frac{R2_i}{T2_i}} + \frac{R_k}{T_k} \right ) \cdot 100 = \%\mbox{ CPU allocation}</math></center> where ''C'' is the idle CPU time, 3/5 in our example. Consider a R2/T2 ratio of 1/2 for the first guest and 1/4 for the second. This would result in: <center><math>\left ( \frac{\frac{3}{5} \cdot \frac{1}{2}}{\frac{1}{2} + \frac{1}{4}} + \frac{1}{5} \right ) \cdot 100 = 60\%\mbox{ CPU allocation for context 1}</math></center> <center><math>\left ( \frac{\frac{3}{5} \cdot \frac{1}{4}}{\frac{1}{2} + \frac{1}{4}} + \frac{1}{5} \right ) \cdot 100 = 40\%\mbox{ CPU allocation for context 2}</math></center> If the idle time ratio is the same for all contexts, the formula can be simplified: <center><math>\left ( C \cdot \frac{1}{N} + \frac{R_k}{T_k} \right ) \cdot 100 = \%\mbox{ CPU allocation}</math></center> Therefore, if 3 of the above 5 contexts would run, i.e. <math>C = \frac{2}{5}, N = 3</math>, it would result in the expted 33% split: <center><math>\left ( \frac{2}{5} \cdot \frac{1}{3} + \frac{1}{5} \right ) \cdot 100 \approx 33\%\mbox{ CPU allocation}</math></center> [[Category:Theory]]
Summary:
Please note that all contributions to Linix VServer may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see
Linix VServer:Copyrights
for details).
Do not submit copyrighted work without permission!
Cancel
Editing help
(opens in new window)
Navigation menu
Page actions
Page
Discussion
Read
Edit
History
Page actions
Page
Discussion
More
Tools
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
About
Overview
Paper
News
Developers
Donations
Search
Getting Started
Downloads
FAQs
Documentation
Support
Participate
How to participate
Report a Bug
Communicate
Teams/Projects
Hall of Fame
Resources
Archives
Recent Wiki Changes
Pastebin
Related Projects
VServer Hosting
Happy VServer Users
Tools
What links here
Related changes
Special pages
Page information