DM_EP_BOUSQUET
2024-03-28
Question 1
Le but de ce Dm est de Simuler une queue G/G/k A partir du code donné dans le sujet j’ai pu apporté de nombreuse modification pour rendre cette queue G/G/k Les commentaires commençant par un “!” sont les explications des principaux changement apporté
knitr::opts_chunk$set(echo = TRUE)
# This function plot the average response time of a M/G/k queue for various scheduling disciplines.
# As input, it takes the job service times (Service), their mean value (ES) and the number of server (k)
plot_response_times <- function(Service, ES, k){
debug=0;
scheduling_disciplines = c(1:4); # 'FCFS'=1,'LCFS'=2,'RO-S'=3,'SRPT'=4
num_arrival_rates=5;
lambdas = (1/ES) * c(1:num_arrival_rates)/(num_arrival_rates+1) ;
# Matrix of average response times for all disciplines and arrival rates
R_time <- matrix(0, nrow = length(scheduling_disciplines), ncol = length(lambdas));
rownames(R_time) <- c("FCFS","LCFS","RO-S","SRPT");
colnames(R_time) <- paste("rho=", round(lambdas*ES, digits = 3), sep = "");
cnt=0;
for (lambda in lambdas)
{
cnt=cnt+1;
# Let's assume a Poisson process coming in, otherwise change the next line
Arrival= cumsum(rexp(n=N, rate = lambda)); # Arrival times
for (scheduling_discipline in scheduling_disciplines)
{
t = 0; # simulation time
Remaining = rep(N, x=NA); # Remaining service times of each job
Completion = rep(N, x=NA); # Completion time of each job
Servers = rep(NA, k) # ! initial index in remaining of the task served by each server
BusyServer = rep(NA, k) # ! Remaining time of task served by each server
AvgJobs = 0;
# CurrentTask = NA; => we use the Servers vector instead of this variable. This allow us to follow the current task in each server
NextArrival = 1;
while (TRUE) {
if (debug==1){
print("*********************");
print(Arrival);
print("*********")
print(Service);
print("**************")
print(Remaining);
}
dtA = NA;
dtC = NA;
if(length(Arrival[Arrival>t])>0) { # if an arrival exists after t
dtA = head(Arrival[Arrival>t],n=1)-t ; # time to next arrival
}
if(any(!is.na(BusyServer))) { # ! if at least on server is running a task
dtC = min(BusyServer[!is.na(BusyServer)]); # time to next completion (when the first task finish)
}
if(is.na(dtA) & is.na(dtC)) {
break;
}
dt = min(dtA,dtC,na.rm=T);
# update system variables
t = t + dt;
#
AvgJobs=AvgJobs+dt*(sum(!is.na(Remaining)) + sum(!is.na(BusyServer))); # ! we don't forget the running task by adding "sum(!is.na(BusyServer))"
#print(AvgJobs);
if (debug==1){
print(paste("Sim. time:", t));
print(paste("# of jobs arrived: ", NextArrival));
}
# Job arrival
if((NextArrival <=N) & (Arrival[NextArrival] == t)) {
Remaining[NextArrival] = Service[NextArrival];
NextArrival = NextArrival + 1;
}
for (server in 1:k){
# Job departure
#actual = Servers[server]; # initial index in Remaining of the running job in this server
if(!is.na(Servers[server])) {
BusyServer[server] = BusyServer[server] - dt ;
if(BusyServer[server] <= 0) {
# ! Current task in this server completed
actual = Servers[server];
Completion[actual] = t;
BusyServer[server] = NA;
Servers[server] = NA;
}
}
# Scheduling discipline
WaitingList=(1:NextArrival)[!is.na(Remaining)];
if(length(WaitingList)>0) {
# FCFS
if (scheduling_discipline==1){
# ! We have to check if a task is running because in the case of a G/G/k queue we supress every running task from the waiting list. Therefore the task would have been changed at each iteration if we don't have this condition
if(is.na(Servers[server])) {
Servers[server] = head(WaitingList,n=1);
actual = Servers[server];
# ! Selecting the serveur and add it to busy vector same goes for all policy
BusyServer[server] = Remaining[actual];
# ! Suppress curent task from Remaining list to avoid others serveurs to select it same goes for all policy
Remaining[actual] = NA;
}
}
# LCFS
if (scheduling_discipline==2){
# We implement the non-preemptive version of LCFS: jobs are never killed/resumed
if(is.na(Servers[server])) {
# here, a task is not running, so we find a new job to serve
Servers[server] = tail(WaitingList,n=1);
actual = Servers[server];
BusyServer[server] = Remaining[actual];
Remaining[actual] = NA;
}
}
# ROS: Random Order of Service
if (scheduling_discipline==3){
if(is.na(Servers[server])) {
# here, a task is not running, so we find a new job to serve
if (length(WaitingList)>1) {
Servers[server] = sample(WaitingList,size=1);
actual = Servers[server];
BusyServer[server] = Remaining[actual];
Remaining[actual] = NA;
} else{
Servers[server] = WaitingList;
actual = Servers[server];
BusyServer[server] = Remaining[actual];
Remaining[actual] = NA;
}
}
}
# SRPT: Shortest Remaining Processing Time
if (scheduling_discipline==4){
# ! here, a task is not running so we find a new job to serve
if(is.na(Servers[server])){
Servers[server] = which.min(Remaining);
actual = Servers[server];
BusyServer[server] = Remaining[actual];
Remaining[actual] = NA;
}
# ! here a task is still running so we check if a task with a shortest remaining time exist and if so we serve it
else{
compareshort = which.min(Remaining);
temp = BusyServer[server];
# ! we check if the shortest job of Remaining is shorter than the one currently served. we compare it that way so if the remaining time is the same for both jobs the job currently served is the one selected
if (min(compareshort, temp)!=temp){
# ! we had the job previously served to Remaining so it can be served either later or by another server
Remaining[actual]=BusyServer[server]
# ! then we serve the job newly selected
Servers[server] = compareshort;
actual = Servers[server];
BusyServer[server] = Remaining[actual];
Remaining[actual] = NA;
}
}
}
}
if (debug==1){
print(paste("Current Task = ", Servers[server]))
readline(prompt="Press [enter] to proceed")
}
}
} # while
ResponseTime = mean(Completion-Arrival); #average response time
AvgJobs=AvgJobs/(tail(Completion,n=1)-Arrival[1]);
#print(tail(Completion,n=1));
#print(Arrival[1]);
#print(Completion);
#print(tail(Completion,n=1)-Arrival[1]);
#print(AvgJobs);
# Simulation completed. Let's verify Little law: N=lambda*R
r_names=rownames(R_time)
cat(paste("Sim. ",r_names[scheduling_discipline],"(rho=",round(lambda*ES,digits = 2),") completed."));
cat(paste(" Little law verification: ", round(AvgJobs,digits = 4), "=N=lambda*R=", round(lambda*ResponseTime,digits = 4),"\n"));
R_time[scheduling_discipline,cnt]=ResponseTime;
} # loop scheduling discipline
} # loop lambda
cat("\nResponse time matrix:\n")
print(R_time)
matplot(t(R_time), type = "l", xlab="Load (lambda*E[S])", ylab="Avg Response Time", xaxt = "n", lwd = 3);
legend("topleft", legend = rownames(R_time), col=1:4, pch=1);
axis(side=1,at=1:ncol(R_time),labels=round(lambdas*ES, digits=3));
result <- list("Response_time" = R_time['FCFS',], "Load" = lambdas * ES, "colnames" = colnames(R_time));
return(result);
} # end functionAvec un echantillon assez grand on verifie globalement la loi de little pour toutes les politiques La politique SRPT est légerement plus efficaces que les autres
## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.1636 =N=lambda*R= 0.1657
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.1636 =N=lambda*R= 0.1657
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.1636 =N=lambda*R= 0.1657
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.1636 =N=lambda*R= 0.1657
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.335 =N=lambda*R= 0.3319
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.335 =N=lambda*R= 0.3319
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.335 =N=lambda*R= 0.3319
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.335 =N=lambda*R= 0.3319
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.4934 =N=lambda*R= 0.4998
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.4934 =N=lambda*R= 0.4999
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.4933 =N=lambda*R= 0.4998
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.4932 =N=lambda*R= 0.4997
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 0.6759 =N=lambda*R= 0.6713
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 0.6758 =N=lambda*R= 0.6713
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 0.676 =N=lambda*R= 0.6715
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 0.6751 =N=lambda*R= 0.6706
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 0.8642 =N=lambda*R= 0.8533
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 0.8639 =N=lambda*R= 0.8529
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 0.8648 =N=lambda*R= 0.8539
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 0.8615 =N=lambda*R= 0.8506
##
## Response time matrix:
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 0.9941252 0.9956884 0.9996940 1.007021 1.023941
## LCFS 0.9941252 0.9956884 0.9997145 1.006885 1.023507
## RO-S 0.9941252 0.9956884 0.9996031 1.007216 1.024661
## SRPT 0.9941252 0.9956884 0.9994088 1.005833 1.020721
## $Response_time
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## 0.9941252 0.9956884 0.9996940 1.0070211 1.0239415
##
## $Load
## [1] 0.1666667 0.3333333 0.5000000 0.6666667 0.8333333
##
## $colnames
## [1] "rho=0.167" "rho=0.333" "rho=0.5" "rho=0.667" "rho=0.833"Question 2
On voit des légère différence entre les différentes politiques cependant l’echantillon pris est petit et les resultats ne sont pas aussi parlant qu’au dessus
## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.2645 =N=lambda*R= 0.2887
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.2645 =N=lambda*R= 0.2887
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.2645 =N=lambda*R= 0.2887
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.2645 =N=lambda*R= 0.2887
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.4167 =N=lambda*R= 0.5773
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.4167 =N=lambda*R= 0.5773
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.4167 =N=lambda*R= 0.5773
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.4167 =N=lambda*R= 0.5773
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 1.0984 =N=lambda*R= 0.866
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 1.0984 =N=lambda*R= 0.866
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 1.0984 =N=lambda*R= 0.866
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 1.0984 =N=lambda*R= 0.866
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 1.2378 =N=lambda*R= 1.2476
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 1.194 =N=lambda*R= 1.2036
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 1.2378 =N=lambda*R= 1.2476
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 1.194 =N=lambda*R= 1.2036
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 1.033 =N=lambda*R= 1.4434
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 1.033 =N=lambda*R= 1.4434
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 1.033 =N=lambda*R= 1.4434
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 1.033 =N=lambda*R= 1.4434
##
## Response time matrix:
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 1.732028 1.732028 1.732028 1.871468 1.732028
## LCFS 1.732028 1.732028 1.732028 1.805365 1.732028
## RO-S 1.732028 1.732028 1.732028 1.871468 1.732028
## SRPT 1.732028 1.732028 1.732028 1.805365 1.732028
## $Response_time
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## 1.732028 1.732028 1.732028 1.871468 1.732028
##
## $Load
## [1] 0.1666667 0.3333333 0.5000000 0.6666667 0.8333333
##
## $colnames
## [1] "rho=0.167" "rho=0.333" "rho=0.5" "rho=0.667" "rho=0.833"Question 3
On voit que la queue G/G/k est plus efficace et plus rho est grand plus l’écart d’efficacité se fait ressentir
## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.1623 =N=lambda*R= 0.1567
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.1623 =N=lambda*R= 0.1567
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.1623 =N=lambda*R= 0.1567
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.1623 =N=lambda*R= 0.1567
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.3252 =N=lambda*R= 0.3137
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.3252 =N=lambda*R= 0.3137
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.3252 =N=lambda*R= 0.3137
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.3252 =N=lambda*R= 0.3137
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.4498 =N=lambda*R= 0.4724
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.4498 =N=lambda*R= 0.4724
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.4498 =N=lambda*R= 0.4724
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.4498 =N=lambda*R= 0.4724
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 0.627 =N=lambda*R= 0.6393
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 0.6247 =N=lambda*R= 0.637
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 0.6268 =N=lambda*R= 0.6391
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 0.6246 =N=lambda*R= 0.6369
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 0.7457 =N=lambda*R= 0.7978
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 0.7459 =N=lambda*R= 0.798
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 0.7451 =N=lambda*R= 0.7971
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 0.7448 =N=lambda*R= 0.7968
##
## Response time matrix:
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 0.9404112 0.9409573 0.9448449 0.9589715 0.9573850
## LCFS 0.9404112 0.9409573 0.9448449 0.9555432 0.9576000
## RO-S 0.9404112 0.9409573 0.9448449 0.9586365 0.9565613
## SRPT 0.9404112 0.9409573 0.9448449 0.9553322 0.9562171
## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.0575 =N=lambda*R= 0.0571
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.0577 =N=lambda*R= 0.0573
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.0577 =N=lambda*R= 0.0573
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.0551 =N=lambda*R= 0.0548
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.1168 =N=lambda*R= 0.1167
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.1184 =N=lambda*R= 0.1183
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.1174 =N=lambda*R= 0.1173
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.111 =N=lambda*R= 0.1109
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.2012 =N=lambda*R= 0.187
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.1995 =N=lambda*R= 0.1855
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.1996 =N=lambda*R= 0.1856
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.1865 =N=lambda*R= 0.1733
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 0.2623 =N=lambda*R= 0.2575
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 0.2625 =N=lambda*R= 0.2577
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 0.2617 =N=lambda*R= 0.257
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 0.2346 =N=lambda*R= 0.2303
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 0.3645 =N=lambda*R= 0.3584
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 0.3616 =N=lambda*R= 0.3555
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 0.3667 =N=lambda*R= 0.3605
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 0.3128 =N=lambda*R= 0.3076
##
## Response time matrix:
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 1.0278171 1.0504652 1.122279 1.158929 1.290225
## LCFS 1.0317164 1.0642907 1.112869 1.159714 1.279832
## RO-S 1.0317164 1.0552812 1.113438 1.156282 1.297916
## SRPT 0.9858132 0.9977143 1.039949 1.036495 1.107249
