DM EP
Emin Gundogan - Axel Colé
2024-01-19
Question 1
Below is a version of the G/G/k queue Comments are added to explain differences between the original G/G/1 queue and the know updated G/G/k
knitr::opts_chunk$set(echo = TRUE)
# This function plot the average response time of a M/G/1 queue for various scheduling disciplines.
# As input, it takes the job service times (Service) and their mean value (ES)
plot_response_times <- function(Service, ES, K, print=0){
debug=0;
print=print; #if 1 prints only ittle law verification
#if 2 prints plots
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
AvgJobs = 0;
CurrentTask = rep(K, x=NA); #Currrent Tasks is now an array representing all the k servers
NextArrival = 1;
while (TRUE) {
if (debug==1){
print("*********************");
print(Arrival);
print(Service);
print(Remaining);
}
dtA = NA;
dtC = rep(K, x=NA); #dtC is now an array with all remaining time to complete a job in the servers(in cureent task)
if(length(Arrival[Arrival>t])>0) { # if an arrival exists after t
dtA = head(Arrival[Arrival>t],n=1)-t ; # time to next arrival
}
for(i in 1:length(CurrentTask)){ # For every job that can be found is the servers
if(!is.na(CurrentTask[i])) { # if a task is running
dtC[i] = Remaining[CurrentTask[i]]; # time to next completion
}
}
if(is.na(dtA) & all(is.na(dtC))) { #This programs ends when there is no more arrival (dtA) and all jobs in the servers are finished(dtCs)
break;
}
dt = min(dtA,pmin(dtC),na.rm=T);
# update system variables
t = t + dt;
AvgJobs=AvgJobs+dt*sum(!is.na(Remaining));
if (debug==1){
print(paste("dt :", dt));
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;
}
# Job departure
for(i in 1:length(CurrentTask)){
if(!is.na(CurrentTask[i])) {
Remaining[CurrentTask[i]] = Remaining[CurrentTask[i]] - dt ;
if(Remaining[CurrentTask[i]] <= 0) {
# CurrentTask completed
Completion[CurrentTask[i]] = t;
Remaining[CurrentTask[i]] = NA;
CurrentTask[i] = NA;
}
}
}
# Scheduling discipline
WaitingList=(1:NextArrival)[!is.na(Remaining)];
WaitingList <- setdiff(WaitingList, CurrentTask); # Waiting List is now all jobs with a remaining time minus those already in a server
if(length(WaitingList)>0) {
# FCFS
if (scheduling_discipline==1){
for (i in 1:length(CurrentTask)) { #for each empty server
if(is.na(CurrentTask[i])){
CurrentTask[i] = head(WaitingList,n=1);
break; # only the first empty server (-> only one event at a time)
}
}
}
# LCFS
if (scheduling_discipline==2){
# We implement the non-preemptive version of LCFS: jobs are never killed/resumed
for (i in 1:length(CurrentTask)) {
if(is.na(CurrentTask[i])){
CurrentTask[i] = tail(WaitingList,n=1);
break;
}
}
}
# ROS: Random Order of Service
if (scheduling_discipline==3){
for (i in 1:length(CurrentTask)) {
if(is.na(CurrentTask[i])) { # For every empty server
# here, a task is not running, so we find a new job to serve
if (length(WaitingList)>1) {
CurrentTask[i] = sample(WaitingList,size=1);
} else{
CurrentTask[i] = WaitingList;
}
break; # Only the first empty server
}
}
}
# SRPT: Shortest Remaining Processing Time
if (scheduling_discipline==4){
for (i in 1:length(CurrentTask)){
if(is.na(CurrentTask[i])){
tab = rep(length(WaitingList)); #tab is an array of all remaining time of jobs in the waitinglist
for (j in 1:length(WaitingList)) {
tab[j] = Remaining[WaitingList[j]];
}
CurrentTask[i] = WaitingList[which.min(tab)];#the minimum remaining service tab of job in the waiting list
break; #Only the first empty server
}
}
}
}
if (debug==1){
print(paste("Current Task = ", CurrentTask))
readline(prompt="Press [enter] to proceed")
}
} # while
ResponseTime = mean(Completion-Arrival); #average response time
AvgJobs=AvgJobs/(tail(Completion,n=1)-Arrival[1]);
# Simulation completed. Let's verify Little law: N=lambda*R
r_names=rownames(R_time)
if(print == 1){
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
if(print == 2){
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));
}
return(R_time);
} # end functionQuestion 2:
We want to ensure our code is correct with 3 servers and ten arrival. To do so we are comparing each of our simulated result to the the expected result with Little’s law. Here we can observe the closeness in each of our simulation and the expected result.
knitr::opts_chunk$set(echo = FALSE)
set.seed(11); # Set seed for reproducibility
N = 10; # number of jobs to simulate;
K = 3;
mu=1;
Service=rexp(N,rate=mu); # Service times
plot_response_times(Service, 1/mu, K, 1);## 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## 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###Question 3
We are here plotting first a GGK and then a GG1 at k speed. Here, the number of server available is greater than the number of jobs coming at the same time so the response time is instataneous at first. Then it starts rising once the load is greater than the number of servers (K). On the other hand, the response time is increasing gradually as the load for the GG1 queue. Thus, the response time is better for the GGK queue ! Especially when the the load is low.
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 1.001939 1.001939 1.001939 1.001939 1.002233
## LCFS 1.001939 1.001939 1.001939 1.001939 1.002233
## RO-S 1.001939 1.001939 1.001939 1.001939 1.002233
## SRPT 1.001939 1.001939 1.001939 1.001939 1.002233
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 1.044739 1.042461 1.088275 1.098901 1.197163
## LCFS 1.044739 1.040133 1.092834 1.098398 1.199523
## RO-S 1.044739 1.040133 1.091032 1.098877 1.209000
## SRPT 1.044739 1.039104 1.084601 1.097296 1.173824###Question 4
We are plotting the ratio of the response time between FCFS GGK and FCFS GG1 at K speed. We can see the ratio decrease as the load is increasing. It is explained by the the several servers available for the GGK compared to the one and only in the GG1 queue. Indeed, as the load increases the GGK queue is able to process multiple jobs at the same time. So the response time is lower in the GGK queue.
