Containers/Guarantees for resources

This page describes how guarantees for resources can be implemented.

comment4,

Providing a guarantee through limiting

The idea of getting a guarantee is simple:

if any group $g_{i}$ requires a $G_{i}$ units of resource from $R$ units available then limiting all the rest groups with $R-G_{i}$ units provides a desired guarantee

For $N$ groups in the system this implies solving a linear equation set to get limits $L_{i}$ like this:

${\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}}$

In a matrix form this looks like

$AL=G\;$

where

$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}}$

and thus the solution is

$L=A^{-1}G\;$

Skipping boring calculations, the reverse matrix $A^{-1}\;$ is

$A^{-1}={\frac {1}{N-1}}\left(A-(N-2)E\right)$

This solutions looks huge, but the $L$ vector is calculated in $O(N)$ time:

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);
}

Disadvantages of this approach

This approach has only one disadvantage: O(n) time needed to start a new container.