Projet_EP_MACHENAUD
Florian MACHENAUD
2023-03-23
Step 0 : Preliminaries
1.
Pour que l’ordonnanceur soit stable, il faut que le temps moyen de réponse soit fini.
Ici, on a une queue M/M/1, mais avec quelque chose de légèrement différent. On doit prendre en compte l’impact du temps de test \(\sigma\) sur le taux de service moyen \(\mu\).
On a alors, avec \(\mu = \frac{1}{1-\sigma}\):
\(E[T] = \frac {1}{\frac{1}{\sigma} -\lambda * N}\)
Donc pour que le temps de réponse soit fini, il faut que \(\frac{1}{\sigma} > \lambda * N\) , et ce pour tout \(\sigma\), d’où \(1 > \lambda * N * \sigma\)
2.
On va calculer chaque point séparément :
Waiting time : \(\frac{1}{\mu - \lambda}\) Service time : \(\sigma\)
D’où le temps de temps d’attente moyen qui est égal à la somme des deux temps ci dessus. On a donc un temps d’attente moyen égal à \(\frac{1}{\mu - \lambda} + \sigma\)
3.
On connait \(Y = X_m\) D’où \(E[X^p | Y_\sigma = X_m] =\)
\((p = 1) : X_m * P_{{X_m},{X_m}}(\sigma) + X_M * P_{{X_M},{X_M}}(\sigma)\) \((p = 2) : X_m^2 * P_{{X_m},{X_m}}(\sigma) + X_M^2 * P_{{X_M},{X_M}}(\sigma)\)
Step 1 : Code Writing
#knitr::opts_chunk$set(echo = TRUE)
LB_random <- function(N,K,mu,InterArrival,JobSize) {
WaitingTime=rep(0,K);
WaitingTimeCum=rep(0,K);
for (n in 1:N) #for each job
{
# Dispatching decision of RANDOM
U = sample(x=1:K,1);
for (k in 1:K) #for each server
{
# Update the waiting time of server k (Lindley's recursion)
WaitingTime[k] = max(WaitingTime[k] + ifelse(U==k,1,0)*JobSize[n]/mu[k] - InterArrival[n],0);
}
WaitingTimeCum[U] = WaitingTimeCum[U]+WaitingTime[U];
}
return(sum(WaitingTimeCum)/N);
}
LB_SITAc <- function(N,K,mu,InterArrival,JobSize,c,xm) {
WaitingTime=rep(0,K);
WaitingTimeCum=rep(0,K);
for (n in 1:N) #for each job
{
# Dispatching decision of SITA-c
k_win=sample(x=(c+1):K);
if(JobSize[n]==xm)
{
# job n is short
k_win=sample(x=1:c);
}
for (k in 1:K) #for each server
{
# Update the waiting time of server k (Lindley's recursion)
WaitingTime[k]=max(WaitingTime[k]+ifelse(k_win==k,1,0)*JobSize[n]/mu[k_win]-InterArrival[n],0);
}
WaitingTimeCum[k_win] = WaitingTimeCum[k_win]+WaitingTime[k_win];
}
return(sum(WaitingTimeCum)/N);
}
LB_SITAc_2 <- function(N,K,mu,InterArrival,JobSize,c,xm, p_matrix) {
WaitingTime = rep(0,K)
WaitingTimeCum = rep(0,K)
for (n in 1:N){
k_win = sample(x = (c+1):K)
xm_pred = p_matrix[1][1] + p_matrix[2][1]
if (xm_pred > runif(1)){
k_win = sample(x = 1:c)
}
for (k in 1:K){
WaitingTime[k] = max(WaitingTime[k] + ifelse(k_win == k,1,0) * JobSize[n] / mu[k_win] - InterArrival[n],0)
}
WaitingTimeCum[k_win] = WaitingTimeCum[k_win] + WaitingTime[k_win]
}
return(sum(WaitingTimeCum) / N)
}
################################################################################
N=10; # number of jobs to simulate
K=10; # number of servers
sigma = 1
mu = rep(sigma,N)
#mu = sample(x=1:1, K, replace = TRUE); # service rates
set.seed(69); # Set seed for reproducibility
beta=1;
xM=1e6;
xm=1;
JobSize=sample(c(xm,xM),N,replace=T,prob=c(1/xM^beta,1- 1/xM^beta)); # Job sizes
EX=xm*(1/xM^beta) + xM*(1/xM^beta); # Expected value of job sizes
B=10;
xdata=(0.5:(B-0.5))/B;
p_time = 0.1
P_xm_xm = (1 - exp(-10 * p_time)) * (1/xM^beta - 0.001) + 0.001
P_xm_xM = 1/xM^beta - P_xm_xm
P_xM_xM = (1 - exp(-p_time)) * (1/xM^beta - 0.001) + 0.001
P_xM_xm = 1/xM^beta - P_xM_xM
p_matrix = c(
c(P_xm_xm, P_xm_xM),
c(P_xM_xm, P_xM_xM)
)
W_RANDOM=rep(0,length(xdata));
#W_RR=rep(0,length(xdata));
#W_LLd=rep(0,length(xdata));
W_SITAc = rep(0,length(xdata))
W_SITAc_2 = rep(0,length(xdata))
cnt=1;
for (rho in xdata)
{
# For stability
lambda=K * rho/EX; #"overall arrival rate"<"overall service rate"=(mu[1]+...+ mu[K])/EX
InterArrival = rexp(n=N, rate = lambda); # Inter-arrival times
c = floor(K/2)
#W_RANDOM[cnt]=LB_random(N,K,mu,InterArrival,JobSize);
#W_RR[cnt]=LB_RR(N,K,mu,InterArrival,JobSize);
#W_LLd[cnt]=LB_LLd(N,K,mu,InterArrival,JobSize,2);
W_SITAc[cnt] = LB_SITAc(N,K,mu,InterArrival,JobSize,c,xm)
W_SITAc_2[cnt] = LB_SITAc_2(N, K, mu, InterArrival, JobSize, c, xm, p_matrix)
print(paste("Waiting Times with rho =",format(round(rho, 2), nsmall = 2),"and K =",K))
print(paste("Random: ", W_RANDOM[cnt]))
EX2 = xm * xm * (1 - 1 / xM ^ beta) + xM ^ (2 - beta)
W = (0.5 * lambda / N) * EX2 / (1 - rho)
#print(paste("RR: ", W_RR[cnt]))
#print(paste("LL-d: ", W_LLd[cnt]))
EX2=xm*xm*(1-1/xM^beta) + xM^(2-beta);
W=(0.5*lambda/K)*EX2/(1-rho);
print(paste("Random (Theory): ", W))
print(paste("SITA-c (exact): ", W_SITAc[cnt]))
print(paste("SITA-c (w/ prediction):", W_SITAc_2[cnt]))
cnt = cnt + 1
cat("\n")
}## [1] "Waiting Times with rho = 0.05 and K = 10"
## [1] "Random: 0"
## [1] "Random (Theory): 26315.7894736579"
## [1] "SITA-c (exact): 27499939.2681941"
## [1] "SITA-c (w/ prediction): 27499939.2681941"
##
## [1] "Waiting Times with rho = 0.15 and K = 10"
## [1] "Random: 0"
## [1] "Random (Theory): 88235.2941175588"
## [1] "SITA-c (exact): 27499981.8969947"
## [1] "SITA-c (w/ prediction): 27499981.8969947"
##
## [1] "Waiting Times with rho = 0.25 and K = 10"
## [1] "Random: 0"
## [1] "Random (Theory): 166666.6666665"
## [1] "SITA-c (exact): 27499988.9518684"
## [1] "SITA-c (w/ prediction): 27499988.9518684"
##
## [1] "Waiting Times with rho = 0.35 and K = 10"
## [1] "Random: 0"
## [1] "Random (Theory): 269230.7692305"
## [1] "SITA-c (exact): 27499993.3683845"
## [1] "SITA-c (w/ prediction): 27499993.3683845"
##
## [1] "Waiting Times with rho = 0.45 and K = 10"
## [1] "Random: 0"
## [1] "Random (Theory): 409090.9090905"
## [1] "SITA-c (exact): 27499993.7375111"
## [1] "SITA-c (w/ prediction): 27499993.7375111"
##
## [1] "Waiting Times with rho = 0.55 and K = 10"
## [1] "Random: 0"
## [1] "Random (Theory): 611111.1111105"
## [1] "SITA-c (exact): 27499993.2432329"
## [1] "SITA-c (w/ prediction): 27499993.2432329"
##
## [1] "Waiting Times with rho = 0.65 and K = 10"
## [1] "Random: 0"
## [1] "Random (Theory): 928571.4285705"
## [1] "SITA-c (exact): 27499997.29008"
## [1] "SITA-c (w/ prediction): 27499997.29008"
##
## [1] "Waiting Times with rho = 0.75 and K = 10"
## [1] "Random: 0"
## [1] "Random (Theory): 1499999.9999985"
## [1] "SITA-c (exact): 27499997.2933433"
## [1] "SITA-c (w/ prediction): 27499997.2933433"
##
## [1] "Waiting Times with rho = 0.85 and K = 10"
## [1] "Random: 0"
## [1] "Random (Theory): 2833333.3333305"
## [1] "SITA-c (exact): 27499994.6364263"
## [1] "SITA-c (w/ prediction): 27499994.6364263"
##
## [1] "Waiting Times with rho = 0.95 and K = 10"
## [1] "Random: 0"
## [1] "Random (Theory): 9499999.99999049"
## [1] "SITA-c (exact): 27499997.8265182"
## [1] "SITA-c (w/ prediction): 27499997.8265182" length(xdata)## [1] 10 xdata## [1] 0.05 0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85 0.95 length(W_RANDOM)## [1] 10 plot(xdata, W_RANDOM, xlim=c(0,1), ylim = c(0, max( W_SITAc, W_SITAc_2)*1.5), type="o", col="blue", pch="o", lty=1, ylab="",xlab="rho", main=paste("Average Waiting Times - K=",K))
points(xdata, W_SITAc, col="red", pch="*")
lines(xdata, W_SITAc, col="red",lty=2)
points(xdata, W_SITAc_2, col="dark red", pch="*")
lines(xdata, W_SITAc_2, col="dark red",lty=2)
legend("topleft",legend=c("RANDOM","SITAc(origin)","SITAc(prediction)"), col=c("blue","red","dark red"), pch=c("o","*","+"),lty=c(1,2,3), ncol=1)