G/G/k
Clément Dehosse, Bastien Lambert, Alexis Noel
2024-03-24
Question 1 :
# This function plot the average response time of a G/G/K queue for various scheduling disciplines.
# As input, it takes the job service times (Service) and their mean value (ES)
#You can choose between different debug prints : - debug = 0 => no debug
# - debug = 1 => lite debug
# - debug = 2 => lots of debug
plot_response_times_GGK <- function(Service, ES, k, debug){
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 = "");
result=NA;
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) {
if(debug>0){
print("CHANGING SCHEDULING DISCIPLINE");
}
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
CurrentTask = rep(NA,k); # Tasks being served on each server
AvgJobs = 0;
NextArrival = 1;
while (TRUE) {
if (debug>0){
print("*********************");
print("Arrival : ");
print(Arrival);
print("\n");
print("Service : ");
print(Service);
print("\n");
print("Remaining : ");
print(Remaining);
print("Current Tasks = ");
print(CurrentTask);
readline(prompt="Press [enter] to proceed")
}
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(CurrentTask))) { # if a task is running
dtC = min(Remaining[CurrentTask[!is.na(CurrentTask)]]); # time to next completion
}
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));
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;
}
# Job departure
if (any(!is.na(CurrentTask))) {
if(debug>1){
print("##################");
print("Departure");
print("Current Tasks : ");
print(CurrentTask);
print("Remaining before update : ");
print(Remaining);
print("Completion before update : ");
print(Completion);
}
for (i in CurrentTask[!is.na(CurrentTask)]) {
Remaining[i] = Remaining[i] - dt
if (Remaining[i] <= 0) {
if(debug>1){
print("Job completed : ");
print(i);
}
Completion[i] <- t
Remaining[i] <- NA
CurrentTask[which(CurrentTask == i)] <- NA
}
}
}
# Scheduling discipline
# List of jobs waiting to be served.
# We consider only jobs that have not been completed yet and are not being served by any server
WaitingList <- setdiff(which(!is.na(Remaining)), CurrentTask[!is.na(CurrentTask)])
IdleServers <- which(is.na(CurrentTask))
if(length(WaitingList)>0 & length(IdleServers)>0) {
jobs_to_assign = min(length(IdleServers),length(WaitingList));
if(debug>1){
print("Average jobs : ")
print(AvgJobs);
print("jobs_to_assign = ");
print(jobs_to_assign);
print("IdleServers = ");
print(IdleServers);
print("WaitingList = ");
print(WaitingList);
print("Current tasks before scheduling : ");
print(CurrentTask);
}
# We are putting the jobs from the waiting list into idle servers
# We don't take into account the time to dispatch the data.
# FCFS
if (scheduling_discipline == 1) { # FCFS
CurrentTask[IdleServers[1:jobs_to_assign]] <- head(WaitingList, n = jobs_to_assign)
} else if (scheduling_discipline == 2) { # LCFS
# We implement the non-preemptive version of LCFS: jobs are never killed/resumed
CurrentTask[IdleServers[1:jobs_to_assign]] <- tail(WaitingList, n = jobs_to_assign)
} else if (scheduling_discipline == 3) { # RO-S
# here, a task is not running, so we find a new job to serve
if(length(WaitingList)==1){
CurrentTask[IdleServers[1:jobs_to_assign]] <- WaitingList[1];
} else {
CurrentTask[IdleServers[1:jobs_to_assign]] <- sample(WaitingList, size = jobs_to_assign);
}
} else if (scheduling_discipline == 4) { # SRPT
# here, a task is not running, so we find a new job to serve
CurrentTask[IdleServers[1:jobs_to_assign]] <- WaitingList[order(Remaining[WaitingList])[1:jobs_to_assign]]
}
}
if (debug>1){
print("Current Tasks = ");
print(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)
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)
return(R_time)
} # end functionQuestion 2 :
plot_response_time_GGK_display <- function(Service, ES, k) {
num_arrival_rates = 5;
lambdas = (1 / ES) * c(1:num_arrival_rates) / (num_arrival_rates + 1);
result_GGK <- plot_response_times_GGK(Service, ES, k, 0)
matplot(t(result_GGK), type = "l", xlab="Load (lambda*E[S])", ylab="Avg Response Time", xaxt = "n", lwd = 3);
legend("topleft", legend = rownames(result_GGK), col=1:4, pch=1);
axis(side=1,at=1:ncol(result_GGK),labels=round(lambdas*ES, digits=3));
}set.seed(11); # Set seed for reproducibility
N = 10; # number of jobs to simulate;
mu=1;
k= 3; # number of servers
Service=rexp(N,rate=mu); # Service times
plot_response_time_GGK_display(Service, 1/mu,k);## 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
Question 3 :
plot_comparaison_between_GG5_GG1 <- function(Service, ES, k) {
num_arrival_rates = 5;
lambdas = (1 / ES) * c(1:num_arrival_rates) / (num_arrival_rates + 1);
result_GGK <- plot_response_times_GGK(Service, ES, k, 0)
# Average response times for G/G/1/FCFS queue with a server that operates at speed k
Service_scaled <- Service / k; # Scale the service times to represent a faster server
ES_scaled <- ES / k; # Scale the mean service time accordingly
#R_time_GG1 <- plot_response_times_GGk(Service_scaled, ES_scaled, 1, scheduling_discipline = 1, debug = 0);
result_GG1 <- plot_response_times_GGK(Service_scaled, ES_scaled, 1, 0)
par(mfrow=c(1,2))
matplot(t(result_GGK), type = "l", xlab="Load (lambda*E[S])", ylab="Avg Response Time (GGK)", xaxt = "n", lwd = 3);
legend("topleft", legend = rownames(result_GGK), col=1:4, pch=1);
axis(side=1,at=1:ncol(result_GGK),labels=round(lambdas*ES, digits=3));
matplot(t(result_GG1), type = "l", xlab="Load (lambda*E[S])", ylab="Avg Response Time (GG1 5*fast)", xaxt = "n", lwd = 3);
legend("topleft", legend = rownames(result_GG1), col=1:4, pch=1);
axis(side=1,at=1:ncol(result_GG1),labels=round(lambdas*ES, digits=3));
par(mfrow=c(1,1))
}set.seed(11);
N = 1e3;
mu = 1;
k = 5;
Service = rexp(N, rate = mu);
plot_comparaison_between_GG5_GG1(Service, 1/mu, k);## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
##
## Response time matrix:
## 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
## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.2084 =N=lambda*R= 0.202
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.2114 =N=lambda*R= 0.2048
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.2102 =N=lambda*R= 0.2036
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.2067 =N=lambda*R= 0.2003
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.4605 =N=lambda*R= 0.4818
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.4557 =N=lambda*R= 0.4768
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.4638 =N=lambda*R= 0.4853
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.4309 =N=lambda*R= 0.4509
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.9641 =N=lambda*R= 0.9534
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.9545 =N=lambda*R= 0.9439
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.9636 =N=lambda*R= 0.953
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.836 =N=lambda*R= 0.8267
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 1.7499 =N=lambda*R= 1.8323
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 1.7924 =N=lambda*R= 1.8761
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 1.7602 =N=lambda*R= 1.8405
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 1.3189 =N=lambda*R= 1.3792
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 3.8431 =N=lambda*R= 3.9415
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 3.9047 =N=lambda*R= 4.0047
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 3.8618 =N=lambda*R= 3.9606
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 2.3121 =N=lambda*R= 2.3713
##
## Response time matrix:
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 0.2424237 0.2890600 0.3813760 0.5496760 0.9459615
## LCFS 0.2457996 0.2860787 0.3775638 0.5628388 0.9611163
## RO-S 0.2443608 0.2911620 0.3811936 0.5521441 0.9505490
## SRPT 0.2403863 0.2705117 0.3306852 0.4137600 0.5691156
plot_response_time_ratio <- function(Service, ES, k) {
num_arrival_rates = 5;
lambdas = (1 / ES) * c(1:num_arrival_rates) / (num_arrival_rates + 1);
# Average response times for G/G/k/FCFS queue
#R_time_GGk <- plot_response_times_GGk(Service, ES, k, scheduling_discipline = 1, debug = 0);
result_GGK <- plot_response_times_GGK(Service, ES, k, 0)
# Average response times for G/G/1/FCFS queue with a server that operates at speed k
Service_scaled <- Service / k; # Scale the service times to represent a faster server
ES_scaled <- ES / k; # Scale the mean service time accordingly
#R_time_GG1 <- plot_response_times_GGk(Service_scaled, ES_scaled, 1, scheduling_discipline = 1, debug = 0);
result_GG1 <- plot_response_times_GGK(Service_scaled, ES_scaled, 1, 0)
response_times_GGK_FCFS <- result_GGK[1, ]
response_times_GG1_FCFS <- result_GG1[1, ]
# Compute the ratio of average response times
#ratio <- R_time_GGk / R_time_GG1;
ratio_FCFS <- response_times_GG1_FCFS / response_times_GGK_FCFS
# Plot the ratio as a function of the load (lambda * ES)
plot(lambdas * ES, ratio_FCFS, type = "l", xlab = "Load (lambda * E[S])", ylab = "Response Time Ratio (GG1 / GGK)", lwd = 3);
}set.seed(11);
N = 1e3;
mu = 1;
k = 5;
Service = rexp(N, rate = mu);
plot_response_time_ratio(Service, 1/mu, k);## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
##
## Response time matrix:
## 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
## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.2084 =N=lambda*R= 0.202
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.2114 =N=lambda*R= 0.2048
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.2102 =N=lambda*R= 0.2036
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.2067 =N=lambda*R= 0.2003
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.4605 =N=lambda*R= 0.4818
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.4557 =N=lambda*R= 0.4768
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.4638 =N=lambda*R= 0.4853
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.4309 =N=lambda*R= 0.4509
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.9641 =N=lambda*R= 0.9534
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.9545 =N=lambda*R= 0.9439
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.9636 =N=lambda*R= 0.953
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.836 =N=lambda*R= 0.8267
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 1.7499 =N=lambda*R= 1.8323
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 1.7924 =N=lambda*R= 1.8761
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 1.7602 =N=lambda*R= 1.8405
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 1.3189 =N=lambda*R= 1.3792
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 3.8431 =N=lambda*R= 3.9415
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 3.9047 =N=lambda*R= 4.0047
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 3.8618 =N=lambda*R= 3.9606
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 2.3121 =N=lambda*R= 2.3713
##
## Response time matrix:
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 0.2424237 0.2890600 0.3813760 0.5496760 0.9459615
## LCFS 0.2457996 0.2860787 0.3775638 0.5628388 0.9611163
## RO-S 0.2443608 0.2911620 0.3811936 0.5521441 0.9505490
## SRPT 0.2403863 0.2705117 0.3306852 0.4137600 0.5691156
The GG1/GGK ratio increases as a function of load because the average response time of GG1 increases faster than that of GGK as a function of load. This is because GG1 has a single server that can become a bottleneck when the load is high, whereas GGK has several servers that can share the workload.
In a G/G/1 system, when the load is low, the single server can process requests quickly and the average response time is low. However, when the load increases, the single server can become a bottleneck and the average response time can increase rapidly.
In a G/G/k system, when the load is low, there may be idle servers and the average response time may be higher than in a G/G/1 system. However, as the load increases, servers may share the workload and the average response time may increase more slowly than in a G/G/1 system.
Question 4:
plot_response_time_ratio2 <- function(Service, ES, k) {
num_arrival_rates = 5;
lambdas = (1 / ES) * c(1:num_arrival_rates) / (num_arrival_rates + 1);
# Average response times for G/G/k/FCFS queue
#R_time_GGk <- plot_response_times_GGk(Service, ES, k, scheduling_discipline = 1, debug = 0);
result_GGK <- plot_response_times_GGK(Service, ES, k, 0)
# Average response times for G/G/1/FCFS queue with a server that operates at speed k
Service_scaled <- Service / k; # Scale the service times to represent a faster server
ES_scaled <- ES / k; # Scale the mean service time accordingly
#R_time_GG1 <- plot_response_times_GGk(Service_scaled, ES_scaled, 1, scheduling_discipline = 1, debug = 0);
result_GG1 <- plot_response_times_GGK(Service_scaled, ES_scaled, 1, 0)
response_times_GGK_FCFS <- result_GGK[1, ]
response_times_GG1_FCFS <- result_GG1[1, ]
# Compute the ratio of average response times
ratio_FCFS <- response_times_GG1_FCFS / response_times_GGK_FCFS
limit_load_index <- which.max(lambdas * ES < 1);
limit_ratio <- ratio_FCFS[limit_load_index];
# Print the limit value
cat("Limit of the response time ratio as the load approaches one from below: ", limit_ratio, "\n");
print(limit_ratio);
# Plot the response time ratio
plot(lambdas * ES, ratio_FCFS, type = "l", xlab = "Load (lambda * E[S])", ylab = "Response Time Ratio (GG1 / GGK)", lwd = 3);
}set.seed(11);
N = 1e3;
mu = 1;
k = 5;
Service = rexp(N, rate = mu);
plot_response_time_ratio2(Service, 1/mu, k);## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.1699 =N=lambda*R= 0.167
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.3343 =N=lambda*R= 0.334
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.5122 =N=lambda*R= 0.501
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 0.6642 =N=lambda*R= 0.668
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 0.8764 =N=lambda*R= 0.8352
##
## Response time matrix:
## 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
## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.2084 =N=lambda*R= 0.202
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.2114 =N=lambda*R= 0.2048
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.2102 =N=lambda*R= 0.2036
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.2067 =N=lambda*R= 0.2003
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.4605 =N=lambda*R= 0.4818
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.4557 =N=lambda*R= 0.4768
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.4638 =N=lambda*R= 0.4853
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.4309 =N=lambda*R= 0.4509
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.9641 =N=lambda*R= 0.9534
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.9545 =N=lambda*R= 0.9439
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.9636 =N=lambda*R= 0.953
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.836 =N=lambda*R= 0.8267
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 1.7499 =N=lambda*R= 1.8323
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 1.7924 =N=lambda*R= 1.8761
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 1.7602 =N=lambda*R= 1.8405
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 1.3189 =N=lambda*R= 1.3792
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 3.8431 =N=lambda*R= 3.9415
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 3.9047 =N=lambda*R= 4.0047
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 3.8618 =N=lambda*R= 3.9606
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 2.3121 =N=lambda*R= 2.3713
##
## Response time matrix:
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 0.2424237 0.2890600 0.3813760 0.5496760 0.9459615
## LCFS 0.2457996 0.2860787 0.3775638 0.5628388 0.9611163
## RO-S 0.2443608 0.2911620 0.3811936 0.5521441 0.9505490
## SRPT 0.2403863 0.2705117 0.3306852 0.4137600 0.5691156
## Limit of the response time ratio as the load approaches one from below: 0.2419545
## rho=0.167
## 0.2419545
We definitely think that the ratio is in favor of the GG1 queue at a low load because the messages are treated quicker than the GGk. This effect is reduced when we increase the load and will tend to 1 when the load reaches 1.