Containers/Guarantees for resources - Revision history

Kir: Protected "Containers/Guarantees for resources" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))

2011-05-23T12:43:48Z

Protected "Containers/Guarantees for resources" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))

Kir: Reverted edits by 188.163.68.72 (Talk) to last revision by Kir

2011-05-23T12:43:31Z

Reverted edits by 188.163.68.72 (Talk) to last revision by Kir

188.163.68.72: /* Providing a guarantee through limiting */

2011-05-23T12:41:27Z

‎Providing a guarantee through limiting

188.163.68.72: /* How to guarantee a guarantee */

2011-05-23T12:36:23Z

‎How to guarantee a guarantee

Kir: Reverted edits by 188.163.104.220 (Talk) to last revision by Kir

2011-05-20T10:29:39Z

Reverted edits by 188.163.104.220 (Talk) to last revision by Kir

188.163.104.220: HGgycptlmeZf

2011-05-20T10:02:50Z

HGgycptlmeZf

188.163.104.220: ZbHQKqUwYgcflxtG

2011-05-20T09:58:04Z

ZbHQKqUwYgcflxtG

188.163.104.220: wOUtVgxYFpsB

2011-05-20T09:53:12Z

wOUtVgxYFpsB

188.163.104.220: /* Providing a guarantee through limiting */

2011-05-20T09:48:01Z

‎Providing a guarantee through limiting

188.163.104.220: /* How to guarantee a guarantee */

2011-05-20T09:43:08Z

‎How to guarantee a guarantee

@@ Line 4: / Line 4: @@
 This page describes how guarantees for resources can be implemented.
-comment4,
+= How to guarantee a guarantee =
-comment5,
+The first way has the followong disadvantages:

← Older revision		Revision as of 12:41, 23 May 2011
Line 6:		Line 6:
	comment4,		comment4,

−	~~= Providing a guarantee through limiting =~~	+	comment5,
−	~~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.~~

@@ Line 4: / Line 4: @@
 This page describes how guarantees for resources can be implemented.
-= How to guarantee a guarantee =
+comment4,
 = Providing a guarantee through limiting =

← Older revision		Revision as of 10:29, 20 May 2011
Line 1:		Line 1:
−	~~comment6~~,	+	[[Category:UBC]]
		+	[[Category:Containers]]
		+
		+	This page describes how guarantees for resources can be implemented.
		+
		+	= How to guarantee a guarantee =
		+	It's not obvious at the first glance, but ''there are only two ways of how a guarantee can be provided'':
		+	# reserve desired amount in advance
		+	# limit consumers to keep some amount free
		+
		+	The first way has the followong disadvantages:
		+	; Reservation is impossible for certain resources
		+	: such as CPU time, disk or network bandwidth and similar can not be just reserved as their amount instantly increases;
		+
		+	; Reserved amount is essentially a limit, but much more strict
		+	: cutting off X megabytes from RAM implies that all the rest groups are limited in their RAM consumption;
		+
		+	; Reservation reduces containers density
		+	: if one wants to run some identical containers, each requiring 100Mb on 1Gb system, reservations can be done for only 10 containers, and starting the 11th is impossible.
		+
		+	On the other hand, ''limiting'' of containers can provide guarantees for them as well.
		+
		+	= 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}
		+	,
		+	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.

← Older revision		Revision as of 10:02, 20 May 2011
Line 1:		Line 1:
−	~~comment2~~,	+	comment6,

← Older revision	Revision as of 12:43, 23 May 2011
(No difference)

← Older revision		Revision as of 09:58, 20 May 2011
Line 1:		Line 1:
−	~~comment3~~,	+	comment2,

← Older revision		Revision as of 09:53, 20 May 2011
Line 1:		Line 1:
−	~~[[Category:UBC]]~~	+	comment3,
−	~~[[Category:Containers]]~~
−
−	~~This page describes how guarantees for resources can be implemented.~~
−
−	~~comment2,~~
−
−	~~comment2~~,

← Older revision		Revision as of 09:48, 20 May 2011
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.~~