GGk_scheduling_disciplines
Rémi Del Medico
2024-03-31
Question 1:
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), the number of server (k) and the debug we want (0=no debug, 1=full debug and 2=debug of FCFS with highest lambda)
plot_response_times <- 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 = "");
infoPrinted = 0;
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);
NextArrival = 1;
while (TRUE) {
if (debug==1 | (debug ==2 & lambda==lambdas[num_arrival_rates] & scheduling_discipline==1)){
print("******************************************************************************************************");
if (infoPrinted == 0) { # We only print the arrival and service times once
cat("Arrival: "); print(Arrival);
cat("Service: "); print(Service);
infoPrinted = 1;
}
cat("Remaining: "); print(Remaining);
cat("Completion: "); print(Completion);
}
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
}
# We update dtC to be the shortest time until completion
for (i in 1:length(CurrentTask)) {
if(!is.na(CurrentTask[i])) { # if a task is running
if (is.na(dtC)) {
dtC = Remaining[CurrentTask[i]]; # time to next completion
} else if (dtC > Remaining[CurrentTask[i]]) {
dtC = Remaining[CurrentTask[i]]; # time to next completion
}
}
}
# no more arrival / completion
if(is.na(dtA) & is.na(dtC)) {
break;
}
# Next event
dt = min(dtA,dtC,na.rm=T);
# update system variables
t = t + dt;
AvgJobs=AvgJobs+dt*sum(!is.na(Remaining));
if (debug==1 | (debug ==2 & lambda==lambdas[num_arrival_rates] & scheduling_discipline==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
for (i in 1:length(CurrentTask)) {
if(!is.na(CurrentTask[i])) {
Remaining[CurrentTask[i]] = Remaining[CurrentTask[i]] - dt ;
if(Remaining[CurrentTask[i]] <= 0) { # Remove finished task
# CurrentTask completed
Completion[CurrentTask[i]] = t;
Remaining[CurrentTask[i]] = NA;
CurrentTask[i] = NA;
}
}
}
# Scheduling discipline
WaitingList=(1:NextArrival)[!is.na(Remaining)];
# We only take the jobs waiting not the one being processed
for (i in CurrentTask) {
if (!is.na(i)) {
WaitingList <- WaitingList[WaitingList != i];
}
}
if(length(WaitingList)>0) {
# FCFS
if (scheduling_discipline==1){
for (i in 1:length(CurrentTask)) {
if (is.na(CurrentTask[i])) {
CurrentTask[i] = head(WaitingList, n=1);
break;
}
}
}
# LCFS
if (scheduling_discipline==2){
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])) {
# 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;
}
}
}
# SRPT: Shortest Remaining Processing Time
if (scheduling_discipline==4){
for (i in 1:length(CurrentTask)) {
if(is.na(CurrentTask[i])) {
if (length(CurrentTask[!is.na(CurrentTask)]) > 0) { # If at least one task is being processed
tab = Remaining;
tab[CurrentTask[!is.na(CurrentTask)]] <- NA; # Set the service times of tasks currently being processed to NA
CurrentTask[i] = which.min(tab); # Take the task with the minimal remaining time
break;
} else {
CurrentTask[i] = which.min(Remaining);
break;
}
}
}
}
}
if (debug==1 | (debug ==2 & lambda==lambdas[num_arrival_rates] & scheduling_discipline==1)){
for (i in 1:length(CurrentTask)) {
print(paste("Current Task = ", CurrentTask[i]))
}
if (debug==1) {
readline(prompt="Press [enter] to proceed")
}
}
} # while
if (debug != 2) {
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
if (debug != 2) {
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));
}
return (R_time)
} # end functionQuestion 2:
To verify that the execution is correct we observe the simulation over an execution using k = 3, N = 10 and the FCFS scheduling discipline:
knitr::opts_chunk$set(echo = FALSE)
set.seed(11); # Set seed for reproducibility
N = 10; # number of jobs to simulate;
k = 3; # number of servers
mu=1;
Service=rexp(N,rate=mu/k); # Service times
plot_response_times(Service, 1/mu, k, 2);## [1] "******************************************************************************************************"
## Arrival: [1] 0.6350583 6.0219460 7.8460552 8.0548722 10.2816795 11.8768878
## [7] 13.4711646 15.9174554 16.8163547 17.2756400
## Service: [1] 2.40643907 20.97892994 0.06365024 12.61116786 7.39012740 2.55914165
## [7] 0.25622089 3.84913335 1.40392496 0.44211433
## Remaining: [1] NA NA NA NA NA NA NA NA NA NA
## Completion: [1] NA NA NA NA NA NA NA NA NA NA
## [1] "Sim. time: 0.635058255493641"
## [1] "# of jobs arrived: 1"
## [1] "Current Task = 1"
## [1] "Current Task = NA"
## [1] "Current Task = NA"
## [1] "******************************************************************************************************"
## Remaining: [1] 2.406439 NA NA NA NA NA NA NA
## [9] NA NA
## Completion: [1] NA NA NA NA NA NA NA NA NA NA
## [1] "Sim. time: 3.0414973278201"
## [1] "# of jobs arrived: 2"
## [1] "Current Task = NA"
## [1] "Current Task = NA"
## [1] "Current Task = NA"
## [1] "******************************************************************************************************"
## Remaining: [1] NA NA NA NA NA NA NA NA NA NA
## Completion: [1] 3.041497 NA NA NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 6.02194598370303"
## [1] "# of jobs arrived: 2"
## [1] "Current Task = 2"
## [1] "Current Task = NA"
## [1] "Current Task = NA"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 20.97893 NA NA NA NA NA NA
## [9] NA NA
## Completion: [1] 3.041497 NA NA NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 7.84605523825728"
## [1] "# of jobs arrived: 3"
## [1] "Current Task = 2"
## [1] "Current Task = 3"
## [1] "Current Task = NA"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 19.15482068 0.06365024 NA NA NA
## [7] NA NA NA NA
## Completion: [1] 3.041497 NA NA NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 7.9097054761193"
## [1] "# of jobs arrived: 4"
## [1] "Current Task = 2"
## [1] "Current Task = NA"
## [1] "Current Task = NA"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 19.09117 NA NA NA NA NA NA
## [9] NA NA
## Completion: [1] 3.041497 NA 7.909705 NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 8.05487217989855"
## [1] "# of jobs arrived: 4"
## [1] "Current Task = 2"
## [1] "Current Task = 4"
## [1] "Current Task = NA"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 18.94600 NA 12.61117 NA NA NA NA
## [9] NA NA
## Completion: [1] 3.041497 NA 7.909705 NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 10.2816795317229"
## [1] "# of jobs arrived: 5"
## [1] "Current Task = 2"
## [1] "Current Task = 4"
## [1] "Current Task = 5"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 16.719196 NA 10.384361 7.390127 NA NA
## [8] NA NA NA
## Completion: [1] 3.041497 NA 7.909705 NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 11.8768877838939"
## [1] "# of jobs arrived: 6"
## [1] "Current Task = 2"
## [1] "Current Task = 4"
## [1] "Current Task = 5"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 15.123988 NA 8.789152 5.794919 2.559142 NA
## [8] NA NA NA
## Completion: [1] 3.041497 NA 7.909705 NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 13.4711646479251"
## [1] "# of jobs arrived: 7"
## [1] "Current Task = 2"
## [1] "Current Task = 4"
## [1] "Current Task = 5"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 13.5297113 NA 7.1948754 4.2006423 2.5591417
## [7] 0.2562209 NA NA NA
## Completion: [1] 3.041497 NA 7.909705 NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 15.9174554448194"
## [1] "# of jobs arrived: 8"
## [1] "Current Task = 2"
## [1] "Current Task = 4"
## [1] "Current Task = 5"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 11.0834205 NA 4.7485846 1.7543515 2.5591417
## [7] 0.2562209 3.8491334 NA NA
## Completion: [1] 3.041497 NA 7.909705 NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 16.816354745538"
## [1] "# of jobs arrived: 9"
## [1] "Current Task = 2"
## [1] "Current Task = 4"
## [1] "Current Task = 5"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 10.1845212 NA 3.8496853 0.8554522 2.5591417
## [7] 0.2562209 3.8491334 1.4039250 NA
## Completion: [1] 3.041497 NA 7.909705 NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 17.2756400021771"
## [1] "# of jobs arrived: 10"
## [1] "Current Task = 2"
## [1] "Current Task = 4"
## [1] "Current Task = 5"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 9.7252359 NA 3.3904000 0.3961669 2.5591417 0.2562209
## [8] 3.8491334 1.4039250 0.4421143
## Completion: [1] 3.041497 NA 7.909705 NA NA NA NA NA
## [9] NA NA
## [1] "Sim. time: 17.6718069350065"
## [1] "# of jobs arrived: 11"
## [1] "Current Task = 2"
## [1] "Current Task = 4"
## [1] "Current Task = 6"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 9.3290690 NA 2.9942331 NA 2.5591417 0.2562209
## [8] 3.8491334 1.4039250 0.4421143
## Completion: [1] 3.041497 NA 7.909705 NA 17.671807 NA NA
## [8] NA NA NA
## [1] "Sim. time: 20.2309485866077"
## [1] "# of jobs arrived: 11"
## [1] "Current Task = 2"
## [1] "Current Task = 4"
## [1] "Current Task = 7"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 6.7699273 NA 0.4350915 NA NA 0.2562209
## [8] 3.8491334 1.4039250 0.4421143
## Completion: [1] 3.041497 NA 7.909705 NA 17.671807 20.230949 NA
## [8] NA NA NA
## [1] "Sim. time: 20.4871694742372"
## [1] "# of jobs arrived: 11"
## [1] "Current Task = 2"
## [1] "Current Task = 4"
## [1] "Current Task = 8"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 6.5137064 NA 0.1788706 NA NA NA
## [8] 3.8491334 1.4039250 0.4421143
## Completion: [1] 3.041497 NA 7.909705 NA 17.671807 20.230949 20.487169
## [8] NA NA NA
## [1] "Sim. time: 20.6660400388185"
## [1] "# of jobs arrived: 11"
## [1] "Current Task = 2"
## [1] "Current Task = 9"
## [1] "Current Task = 8"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 6.3348359 NA NA NA NA NA
## [8] 3.6702628 1.4039250 0.4421143
## Completion: [1] 3.041497 NA 7.909705 20.666040 17.671807 20.230949 20.487169
## [8] NA NA NA
## [1] "Sim. time: 22.0699649952706"
## [1] "# of jobs arrived: 11"
## [1] "Current Task = 2"
## [1] "Current Task = 10"
## [1] "Current Task = 8"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 4.9309109 NA NA NA NA NA
## [8] 2.2663378 NA 0.4421143
## Completion: [1] 3.041497 NA 7.909705 20.666040 17.671807 20.230949 20.487169
## [8] NA 22.069965 NA
## [1] "Sim. time: 22.5120793242361"
## [1] "# of jobs arrived: 11"
## [1] "Current Task = 2"
## [1] "Current Task = NA"
## [1] "Current Task = 8"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 4.488797 NA NA NA NA NA 1.824224
## [9] NA NA
## Completion: [1] 3.041497 NA 7.909705 20.666040 17.671807 20.230949 20.487169
## [8] NA 22.069965 22.512079
## [1] "Sim. time: 24.3363028277244"
## [1] "# of jobs arrived: 11"
## [1] "Current Task = 2"
## [1] "Current Task = NA"
## [1] "Current Task = NA"
## [1] "******************************************************************************************************"
## Remaining: [1] NA 2.664573 NA NA NA NA NA NA
## [9] NA NA
## Completion: [1] 3.041497 NA 7.909705 20.666040 17.671807 20.230949 20.487169
## [8] 24.336303 22.069965 22.512079
## [1] "Sim. time: 27.0008759230539"
## [1] "# of jobs arrived: 11"
## [1] "Current Task = NA"
## [1] "Current Task = NA"
## [1] "Current Task = NA"
## [1] "******************************************************************************************************"
## Remaining: [1] NA NA NA NA NA NA NA NA NA NA
## Completion: [1] 3.041497 27.000876 7.909705 20.666040 17.671807 20.230949 20.487169
## [8] 24.336303 22.069965 22.512079## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 0 0 0 0 0
## LCFS 0 0 0 0 0
## RO-S 0 0 0 0 0
## SRPT 0 0 0 0 0We can clearly see that during the execution the 3 servers are being used, and that the task entering a server is always the oldest one (which is expected using a FCFS scheduling).
Question 3:
We now want to compare a G/G/k queue with a G/G/1 queue having a server k times faster:
## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.1654 =N=lambda*R= 0.1688
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.1654 =N=lambda*R= 0.1688
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.1654 =N=lambda*R= 0.1688
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.1654 =N=lambda*R= 0.1688
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.346 =N=lambda*R= 0.3389
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.346 =N=lambda*R= 0.339
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.346 =N=lambda*R= 0.339
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.346 =N=lambda*R= 0.3389
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.4952 =N=lambda*R= 0.5098
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.4949 =N=lambda*R= 0.5095
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.4954 =N=lambda*R= 0.51
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.4948 =N=lambda*R= 0.5094
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 0.6543 =N=lambda*R= 0.6824
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 0.6538 =N=lambda*R= 0.6818
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 0.6541 =N=lambda*R= 0.6821
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 0.6538 =N=lambda*R= 0.6818
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 0.8923 =N=lambda*R= 0.8712
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 0.8935 =N=lambda*R= 0.8724
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 0.8954 =N=lambda*R= 0.8743
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 0.8876 =N=lambda*R= 0.8667
##
## Response time matrix:
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 1.013012 1.016820 1.019578 1.023529 1.045497
## LCFS 1.013012 1.016991 1.019023 1.022676 1.046899
## RO-S 1.013012 1.016944 1.020046 1.023162 1.049124
## SRPT 1.013012 1.016820 1.018857 1.022657 1.040010
## Sim. FCFS (rho= 0.17 ) completed. Little law verification: 0.0598 =N=lambda*R= 0.0588
## Sim. LCFS (rho= 0.17 ) completed. Little law verification: 0.0598 =N=lambda*R= 0.0588
## Sim. RO-S (rho= 0.17 ) completed. Little law verification: 0.0598 =N=lambda*R= 0.0588
## Sim. SRPT (rho= 0.17 ) completed. Little law verification: 0.0598 =N=lambda*R= 0.0588
## Sim. FCFS (rho= 0.33 ) completed. Little law verification: 0.125 =N=lambda*R= 0.1264
## Sim. LCFS (rho= 0.33 ) completed. Little law verification: 0.1244 =N=lambda*R= 0.1258
## Sim. RO-S (rho= 0.33 ) completed. Little law verification: 0.1248 =N=lambda*R= 0.1263
## Sim. SRPT (rho= 0.33 ) completed. Little law verification: 0.1242 =N=lambda*R= 0.1257
## Sim. FCFS (rho= 0.5 ) completed. Little law verification: 0.2034 =N=lambda*R= 0.2006
## Sim. LCFS (rho= 0.5 ) completed. Little law verification: 0.2027 =N=lambda*R= 0.2
## Sim. RO-S (rho= 0.5 ) completed. Little law verification: 0.2032 =N=lambda*R= 0.2004
## Sim. SRPT (rho= 0.5 ) completed. Little law verification: 0.2008 =N=lambda*R= 0.1981
## Sim. FCFS (rho= 0.67 ) completed. Little law verification: 0.285 =N=lambda*R= 0.2862
## Sim. LCFS (rho= 0.67 ) completed. Little law verification: 0.2888 =N=lambda*R= 0.29
## Sim. RO-S (rho= 0.67 ) completed. Little law verification: 0.286 =N=lambda*R= 0.2872
## Sim. SRPT (rho= 0.67 ) completed. Little law verification: 0.279 =N=lambda*R= 0.2801
## Sim. FCFS (rho= 0.83 ) completed. Little law verification: 0.3954 =N=lambda*R= 0.3908
## Sim. LCFS (rho= 0.83 ) completed. Little law verification: 0.3947 =N=lambda*R= 0.3901
## Sim. RO-S (rho= 0.83 ) completed. Little law verification: 0.3949 =N=lambda*R= 0.3903
## Sim. SRPT (rho= 0.83 ) completed. Little law verification: 0.3793 =N=lambda*R= 0.3748
##
## Response time matrix:
## rho=0.167 rho=0.333 rho=0.5 rho=0.667 rho=0.833
## FCFS 1.058524 1.137958 1.203478 1.287892 1.406847
## LCFS 1.058634 1.132543 1.199778 1.305192 1.404295
## RO-S 1.058582 1.136691 1.202209 1.292253 1.405021
## SRPT 1.058466 1.131260 1.188422 1.260669 1.349458
We can see that the G/G/k queue (first graph) is in average faster than the G/G/1 queue k times faster (second graph) using the FCFS discipline. That is probably due to the load on the server indeed if the load is too high where in the G/G/1 queue the jobs n will have to wait for the n-1 jobs to finish where with the G/G/k queue a job will have to wait less. So we can think that when the load increases the ratio decreases as the G/G/1 became worse.
###Question 4:
Let’s verify that by ploting the values:
As expected when the load increases the ratio decreases, meaning that the G/G/1 queue becomes worse and worse compared to the G/G/k queue.