http://www.linux-vserver.org/api.php?action=feedcontributions&user=80.248.178.79&feedformat=atomLinux-VServer - User contributions [en]2024-03-28T16:17:43ZUser contributionsMediaWiki 1.20.2http://www.linux-vserver.org/CPU_SchedulerCPU Scheduler2008-03-29T11:47:00Z<p>80.248.178.79: /* Token Bucket Extension */</p>
<hr />
<div>== Overview of Processes and Threads ==<br />
<br />
It is important to have a decent understanding of both processes and <br />
threads before learning about schedulers.<br />
<br />
=== Programs and Processes ===<br />
<br />
A program is a combination of instructions and data put together to <br />
perform a task when executed. A process is an instance of a program <br />
(what one might call a "running" program). An analogy is that programs <br />
are like classes in languages like C++ and Java, and processes are <br />
like objects (instantiated instances of classes). Processes are an <br />
abstraction created to embody the state of a program during its <br />
execution. This means keeping track of the data that is associated <br />
with a thread or threads of execution, which includes variables, <br />
hardware state (e.g. registers and the program counter, etc...), and <br />
the contents of an address space.<br />
<br />
=== Threads ===<br />
<br />
A process can have multiple threads of execution that work together to <br />
accomplish its goals. These threads of execution are aptly named <br />
threads. A kernel must keep track of each thread's stack and hardware <br />
state, or whatever is necessary to track a single flow of execution <br />
within a process. Usually threads share address spaces, but they do <br />
not have to (often they merely overlap). It is important to remember <br />
that only one thread may be executing on a CPU at any given time, <br />
which is basically the reason kernels have CPU schedulers. An example <br />
of multiple threads within a process can be found in most web <br />
browsers. Usually at least one thread exists to handle user interface <br />
events (like stopping a page load), one thread exists to handle <br />
network transactions, and one thread exists to render web pages.<br />
<br />
== Scheduling in Linux ==<br />
<br />
Multitasking kernels (like Linux) allow more than one process to exist <br />
at any given time, and furthermore each process is allowed to run as <br />
if it were the only process on the system. Processes do not need to be <br />
aware of any other processes unless they are explicitly designed to <br />
be. This makes programs easier to develop, maintain, and port. Though <br />
each CPU in a system can execute only one thread within a process at a <br />
time, many threads from many processes appear to be executing at the <br />
same time. This is because threads are scheduled to run for very short <br />
periods of time and then other threads are given a chance to run. A <br />
kernel's scheduler enforces a thread scheduling policy, including <br />
when, for how long, and in some cases where (on Symmetric <br />
Multiprocessing (SMP) systems) threads can execute. Normally the <br />
scheduler runs in its own thread, which is woken up by a timer <br />
interrupt. Otherwise it is invoked via a system call or another kernel <br />
thread that wishes to yield the CPU. A thread will be allowed to <br />
execute for a certain amount of time, then a context switch to the <br />
scheduler thread will occur, followed by another context switch to a <br />
thread of the scheduler's choice. This cycle continues, and in this <br />
way a certain policy for CPU usage is carried out.<br />
<br />
== Token Bucket Extension ==<br />
<br />
While the basic idea of Linux-VServer is a peaceful coexistence of all<br />
contexts, sharing the common resources in a respectful way, it is<br />
sometimes useful to control the resource distribution for resource hungry<br />
processes.<br />
<br />
The basic principle of a Token Bucket is not very new. It is given here<br />
as an example for the Hard CPU Limit. The same principle also applies<br />
to scheduler priorities, network bandwidth limitation and resource<br />
control in general.<br />
<br />
The Linux-VServer scheduler uses this mechanism in the following way: consider a<br />
bucket of a certain size ''S'' which is filled with a specified amount of tokens ''R''<br />
every interval ''T'', when the bucket is "full" - excess tokens are spilled.<br />
At each timer tick, a running process (here running means actually needing<br />
the CPU as opposed to "running" as in "existing") consumes exactly one token from the<br />
bucket, unless the bucket is empty, in which case the process is put on a<br />
hold queue until the bucket has been refilled with a minimum ''M'' of tokens.<br />
The process is then rescheduled.<br />
<br />
A major advantage of a Token Bucket is that a certain amount of tokens can<br />
be accumulated in times of quiescence, which later can be used to burst when<br />
resources are required. <br />
<br />
Where a per-process Token Bucket would allow for a CPU resource limitation<br />
of a single process, a Context Token Bucket allows to control the CPU usage<br />
of all confined processes.<br />
<br />
Another approach, which is also implemented, is to use the current fill<br />
level of the bucket to adjust the process priority, thus reducing the<br />
priority of processes belonging to excessive contexts.<br />
<br />
== Token Bucket Examples ==<br />
<br />
=== Hard Limit ===<br />
<br />
The simplest configuration is to just give every context an upper bound for<br />
CPU allocation. The important factor is the ratio:<br />
<br />
<br />
<center><math>\frac{R}{T} \cdot 100 = \%\mbox{ CPU allocation}</math></center><br />
<br />
<br />
Note that this is the proportion of a ''single'' CPU in the system. So,<br />
if you have four CPUs and you want one context to get an average of one whole<br />
CPU to itself, then you would set fill-rate to 1 and interval to 4.<br />
<br />
It is advantageous to smooth operation of the algorithm to make the interval<br />
as small as possible (or much smaller than the bucket size). You can in most<br />
cases simplify the fraction, such as changing 30/100 to 3/10.<br />
<br />
=== Burst time ===<br />
<br />
To penalize processes after a certain amount of ''burst time'', i.e. putting them<br />
on the hold queue, you can use the maximum size S of the bucket and the minimum<br />
number of tokens M to ''hold'' processes.<br />
<br />
Consider a context with a limit of 1/2 of CPU time, a bucket of 15000 tokens and<br />
a minimum of 2500 tokens. Given that your scheduler runs at 1000Hz, processes that<br />
have used the CPU for 30 seconds will be put on hold for 5 seconds. The following<br />
formula can be used to calculate S and M, using ''B'' as burst time and ''H'' as<br />
hold time:<br />
<br />
<br />
<center><math>M = \mbox{Hz} \cdot H \cdot \frac{R}{T}</math></center><br />
<br />
<br />
<center><math>S = \mbox{Hz} \cdot B (1 - \frac{R}{T})</math></center><br />
<br />
=== Guarantees ===<br />
<br />
A guarantee is nearly the same as a pure hard limit, except that you must not<br />
allocate more than 100% CPU time to all contexts. In other words, if you have<br />
''N'' contexts and give each one a guarantee of more than 1/N CPU time, it would result in<br />
more CPU time needed than physically available, which cannot work out. The<br />
important factor here is the sum of all ratios:<br />
<br />
<br />
<center><math>\sum_{i=1}^N \frac{R_i}{T_i} \le 1</math></center><br />
<br />
<br />
=== Fair Share ===<br />
<br />
The fair share configuration is similar to guarantees, except that if the CPU is idle<br />
a context can allocate more CPU time than its guarantee/limit. The scheduler and<br />
bucket configuration was extended in Linux-VServer 2.1.1 to allow fair share<br />
scheduling and is also know as ''IDLE time''.<br />
<br />
Consider a configuration with 5 contexts each limited to 1/5 of CPU time, where<br />
two of these contexts run CPU intensive processes and the rest is idle. Given<br />
that each context may only allocate 1/5 of CPU time, 3/5 of CPU time are wasted<br />
since 3 contexts are idle.<br />
<br />
To distribute the wasted CPU time ''fair'' among contexts that could need it, you<br />
can configure an allocation ratio for R/T during idle times, namely ''R2''/''T2''. To<br />
calculate the cpu distribution for context ''k'' the following formula is used:<br />
<br />
<br />
<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><br />
<br />
<br />
where ''C'' is the idle CPU time, 3/5 in our example. Consider a R2/T2 ratio of 1/2 for<br />
the first guest and 1/4 for the second. This would result in:<br />
<br />
<br />
<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><br />
<br />
<br />
<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><br />
<br />
<br />
If the idle time ratio is the same for all contexts, the formula can be simplified:<br />
<br />
<br />
<center><math>\left ( C \cdot \frac{1}{N} + \frac{R_k}{T_k} \right ) \cdot 100 = \%\mbox{ CPU allocation}</math></center><br />
<br />
<br />
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:<br />
<br />
<br />
<center><math>\left ( \frac{2}{5} \cdot \frac{1}{3} + \frac{1}{5} \right ) \cdot 100 \approx 33\%\mbox{ CPU allocation}</math></center></div>80.248.178.79