|
|
| Line 6: |
Line 6: |
| | comment2, | | comment2, |
| | | | |
| − | = Providing a guarantee through limiting =
| + | comment2, |
| − | The idea of getting a guarantee is simple:
| |
| − | | |
| − | {{out|if any group <math>g_i</math> requires a <math>G_i</math> units of resource from <math>R</math> units available then limiting all the rest groups with <math>R - G_i</math> units provides a desired guarantee}}
| |
| − | | |
| − | For <math>N</math> groups in the system this implies solving a linear equation set to get limits <math>L_i</math> like this:
| |
| − | | |
| − | <center><math>
| |
| − | \begin{cases}
| |
| − | L_2 + L_3 + \ldots + L_N = R - G_1 \\
| |
| − | L_1 + L_3 + \ldots + L_N = R - G_2 \\
| |
| − | \ldots \\
| |
| − | L_1 + L_2 + \ldots + L_{N-1} = R - G_N \\
| |
| − | \end{cases}
| |
| − | </math></center>
| |
| − | | |
| − | In a matrix form this looks like
| |
| − | | |
| − | <center><math>
| |
| − | A L = G\;
| |
| − | </math></center>
| |
| − | | |
| − | where
| |
| − | | |
| − | <center><math>
| |
| − | A = \begin{bmatrix}
| |
| − | 0 & 1 & 1 & \cdots & 1 & 1 \\
| |
| − | 1 & 0 & 1 & \cdots & 1 & 1 \\
| |
| − | & & \cdots \\
| |
| − | 1 & 1 & 1 & \cdots & 1 & 0 \\
| |
| − | \end{bmatrix}
| |
| − | , | |
| − | L = \begin{bmatrix} L_1 \\ L_2 \\ \vdots \\ L_N \end{bmatrix}
| |
| − | ,
| |
| − | G = \begin{bmatrix} R - G_1 \\ R - G_2 \\ \vdots \\ R - G_N \end{bmatrix}
| |
| − | </math></center>
| |
| − | | |
| − | | |
| − | and thus the solution is
| |
| − | | |
| − | <center><math>
| |
| − | L = A^{-1}G\;
| |
| − | </math></center>
| |
| − | | |
| − | | |
| − | Skipping boring calculations, the reverse matrix <math>A^{-1}\;</math> is
| |
| − | | |
| − | <center><math>
| |
| − | A^{-1} = \frac {1} {N - 1} \left( A - (N - 2) E \right)
| |
| − | </math></center>
| |
| − | | |
| − | This solutions looks huge, but the <math>L</math> vector is calculated in <math>O(N)</math> time:
| |
| − |
| |
| − | <pre>
| |
| − | void calculate_limits(int N, int *g, int *l)
| |
| − | {
| |
| − | int sum;
| |
| − | int i;
| |
| − | | |
| − | if (N == 1) {
| |
| − | l[0] = R;
| |
| − | return;
| |
| − | }
| |
| − | | |
| − | sum = 0;
| |
| − | for (i = 0; i < N; i++)
| |
| − | sum += R - g[i];
| |
| − | for (i = 0; i < N; i++)
| |
| − | l[i] = (sum - (R - g[i]) - (N - 2) * (R - g[i]))/(N - 1);
| |
| − | }
| |
| − | </pre>
| |
| − | | |
| − | == Disadvantages of this approach ==
| |
| − | | |
| − | This approach has only one disadvantage: O(n) time needed to start a new container.
| |
