Changes

Jump to: navigation, search

Containers/Guarantees for resources

1,836 bytes removed, 09:48, 20 May 2011
Providing a guarantee through limiting
comment2,
= Providing a guarantee through limiting =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}comment2,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.
Anonymous user

Navigation menu