12142019 hw12
CS 237: Homework 12: DiscreteEvent Simulation of Queueing System
Due date: PDF file due Wednesday December 11th 11:59PM in GradeScope
Homeworks may be handed in late up to noon Sunday 1215 with no penalty. There will be possible questions on the final exam about this homework, as well as the previous one.
Please complete this notebook by filling in solutions where indicated. Be sure to Run All from the Cell menu before submitting.
You may use ordinary ASCII text to write your solutions, or preferably Latex. A nice introduction to Latex in Jupyter notebooks may be found here: http:datablog.udacity.composts201610latexprimer http:data blog.udacity.composts201610latexprimer
As with previous homeworks, just upload a PDF file of this notebook. Instructions for converting to PDF may be found on the class web page right under the link for homework 1.
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
128
12142019 hw12
General Instructions
In this homework we will simulate a simple system consisting of a single queue and a single server:
Although this is a very broad idea, we will focus on simulating a ready queue which holds tasks waiting for the CPU.
How should we approach this simulation? Previously, we did almost all of our simulations using discrete time steps:
for k in rangenumtrials:you can think of this as one trial every ti
me step k
….
However, it is very unrealistic to model queues using such a technique, since most queues exist in an environment when tasks are independent, asynchronous, and arrive at a random time which is best modeled as a real number, not an integer. We will assume a Poisson arrival process, so we can model the interarrival time using an exponential distribution.
It is also the case that the service time the amount of time the task will take in the CPU will be modeled as a real number, and in fact, experiments show that the exponential distribution is also a good model for the service times.
But now, because we can no longer use a for loop to model time in our simulation, we will have to use a very different approach, which we describe in the rest of this section.
DiscreteEvent Simulation
As an overview, I can not do better than the beginning of the Wikipedia article:
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
228
12142019 hw12
The essential components of a DES are the following:
Clock: A variable keeping track of the current time in seconds a float. This most important thing to understand about the clock is that it is not like the counter in a for loop, counting off the seconds; rather, the main loop performs one event per iteration, and the clock keeps track of the time elapsed, skipping ahead from one event time stamp to the next. In general, the time interval between events will not be constant.
Events List: This is an ordered list of events, each with a code telling what is the kind of action to take, and a time stamp for when the event is to occur, and any other information needed for the event. At each iteration of the main loop, the next event will be removed and the action taken. The usual data structure for this list is a priority queue implemented as a minheap.
State Transitions in the DES
The simulation will go through various changes in configuration or state transitions during execution. In some DESs, the number of states is so large, you would literally write the code with a big loop to determine what state the simulation will go to next. For us, there are really only 3 states, and the simulation code doesnt strictly adhere to this diagram; however, it may be useful for understanding what is happening:
In the field of simulation, a discreteevent simulation DES models the operation of a system as a discrete sequence of events in time. Each event occurs at a particular instant in time and marks a change of state in the system. Between consecutive events, no change in the system is assumed to occur; thus the simulation can directly jump in time from one event to the next. This contrasts with continuous simulation in which the simulation continuously tracks the system dynamics over time. Instead of being eventbased, this is called an activitybased simulation; time is broken up into small time slices and the system state is updated according to the set of activities happening in the time slice. Because discreteevent simulations do not have to simulate every time slice, they can typically run much faster than the corresponding continuous simulation. Another alternative to eventbased simulation is processbased simulation. In this approach, each activity in a system corresponds to a separate process, where a process is typically simulated by a thread in the simulation program. In this case, the discrete events, which are generated by threads, would cause other threads to sleep, wake, and update the system state.
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
328
12142019 hw12
Data Structures for the DES An event will be represented by a triple
eventtime, eventtype, task
The eventtype is an integer code with the following meanings:
0arrival event, a task arrives in the queue: 0, arrivaltime, task1finish event, a task
Data Structures for the DES An event will be represented by a triple
eventtime, eventtype, task
The eventtype is an integer code with the following meanings:
0arrival event, a task arrives in the queue: 0, arrivaltime,
1finish event, a task finishes service and leaves the CPU 1, finish time,
Tasks are represented by a list
arrivaltime, servicetime, queuewaittime ,
The queue wait time will be initialized to 0, and updated when a task leaves the queue and starts service.
The events list will be implemented by a heap, using the Python heapq library see this https:docs.python.org2libraryheapq.html link for details, including examples of how to use it on tuples; the two functions used are:
heapq.heappushheap, itemPush the value item onto the heap just a list, ma
intaining the heap ordering.
heapq.heappopheapPop and return the smallest item from the heap, maintain
ing the heap ordering.
e smallest
If the heap is empty, IndexError is raised. To access th
item without popping it, use heap0.
The Task Queue will also use a heap, ordered in two different ways:
FIFO FirstInFirstOut, First come first served: The default and simplest implementation; the heap is ordered by arrival time;
SJF ShortestJobFirst: An implementation which often increases throughput; the heap is ordered by service time, shortest time first.
Other details of the simulation:
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
428
12142019 hw12
An initial list of tasks will be generated before the simulation begins, and the simulation will run until all tasks have been processed.
Arrival of tasks will follow a Poisson distribution with rate parameter lamarrivals per unit time, but expressed by an exponential Exp lamwhich will give the interarrival time; by successively adding the interarrival times we arrive at the arrival times which increase throughout the simulation.
The service time of tasks follows a exponential distribution Exp beta, where beta1mean service time ; we can think of beta as the rate at which tasks need the CPU or the rate at which tasks finish and leave the system;
In order to simulate various kinds of loads on the system, it is only necessary to investigate the relationship between lam and beta , in particular when:
We will be very interested in watching what happens to the system as we change this relationship, as the
lam beta : Tasks finish and depart at a faster rate then they arrive; such a system is underloaded;
lam beta : Arrival and departure mean rates are equally matched; and
lam beta : Tasks arrive faster than they can be served; such a system is overloaded.
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
528
12142019 hw12
A pseudocode version of the algorithm used to run the simulation is as fol
lows:
numtasks104
currenttime0
meanarrivalrate100
tasklist
queue
Create an array of numtasks arrival tasks with exponentiallydistributed interarr
ival times and service times;
the mean of the service times will be varied see below.
Note that the interarrival time need to be added to the last arrival time, to
create an increasing sequence
of time stamps for arrival events.
whileevents list is nonempty
egetnextevent
clocktime stamp of e
if e is an arrival event
insert the task into the queue, following the queue discipline being used
FIFO or SJF
elsemust be a finish event
if the queue is nonempty
that task,
remove the task at the head of the queue and create a finish event for
with time stamp and queue wait time as shown in boldface here:
currenttimeservicetime, 1,arrivaltime, service ti me, currenttimearrivaltime
Print out the statistics.
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
628
12142019 hw12
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
728
12142019 hw12
In 1:
Imports potentially used for this lab
import matplotlib.pyplot as pltnormal plotting
import math
from random import seed, random, uniform, randint import numpy as np
import scipy.signalused to smooth graphs
from collections import Counter
matplotlib inline
Calculating permutations and combinations efficiently
def PN,K: res1
for i in rangeK: resN
NN1 return res
def CN,K: ifKN2:
KNK
X1K1
for row in range1,NK1: Xrow2
for col in rangerow1,K1: XcolXcolXcol1
return XK
Useful code from lab 01
This function takes a list of outcomes and a list of probabilities and
draws a chart of the probability distribution.
def drawdistributionRx, fx, titleProbability Distribution for X: plt.figurefigsize8, 4 plt.barRx,fx,width1.0,edgecolorblack plt.ylabelProbability
plt.xlabelOutcomes if Rx1Rx030:
ticksrangeRx0,Rx11
plt.xticksticks, ticks
plt.titletitle
plt.show
This function takes a list of outcomes, calculates a histogram, and
then draws the empirical frequency distribution.
def showdistributionoutcomes, titleEmpirical Probability Distribution: numtrialslenoutcomes
Rxrange intminoutcomes, intmaxoutcomes1
freqsCounteroutcomes
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
828
12142019
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse 928
hw12
fxfreqsinumtrials for i in Rx drawdistributionRx, fx, titletitle
def round4x:
return roundx0.00000000001,4
def round4listL:
returnround4x for x in L
12142019 hw12
In 2:
Two kinds of queues
import heapq arrivalevent0
finishevent1
def tasktostringtask:
return strtask0, round4task1,round4task2
class FIFOQueue:
def initself:
self.items def isEmptyself:
return self.items def enqueueself, item:
self.items.insert0,item def dequeueself:
return self.items.pop def sizeself:
return lenself.items
def showself:
if self.isEmpty:
return emptyn ret
for k in rangelenself.items1,1,1:
retnttasktostringself.itemsk
return retn
class SJFQueue:
def initself:
self.heap def isEmptyself:
return self.heap
def enqueueself, item:
wrap the task in a tuple so can be heap ordered tupitem1,item
heapq.heappushself.heap, tup
def dequeueself:
return heapq.heappopself.heap1
def sizeself:
return lenself.heap
def showself:
if self.isEmpty:
return emptyn ret
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
1028
12142019
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse 1128
hw12
for k in rangelenself.heap:
retnttasktostringself.heapk1
return retn
def eventtostringevent:
if event1arrivalevent:
returnstrround4event0, arrival, tasktostringe vent2
else:
returnstrround4event0, finish, tasktostringev
ent2
class EventQueue:
def initself:
self.heap def isEmptyself:
return self.heap def enqueueself, item:
heapq.heappushself.heap, item def dequeueself:
return heapq.heappopself.heap def sizeself:
return lenself.heap
def showself:
if self.isEmpty:
return emptyn ret
for k in rangelenself.heap:
retnteventtostringself.heapk
return retn
12142019 hw12
Testing the queues
printnNote: printouts of queues and heaps are with head or min value at to p;
printremember that heaps are not in decreasing order but heap ordered.n
printFIFO
QFIFOQueue
Q.enqueue0,.5,.4,0
Q.enqueue1,.1,.2,0
Q.enqueue2,.2,.3,0
printQ.size
printQ.isEmpty
printQ.show
printQ.dequeue
printQ.dequeue
printQ.size
printQ.isEmpty
print
printSJF
Q2SJFQueue
Q2.enqueue0,.5,.4,0
Q2.enqueue1,.1,.2,0
Q2.enqueue2,.2,.3,0
printQ2.size
printQ2.isEmpty
printQ2.show
printQ2.dequeue
printQ2.dequeue
printQ2.size
printQ2.isEmpty
print
printEvent
HEventQueue H.enqueue61,0,0,61,3,4 H.enqueue9,1,1,9,3,4 H.enqueue1,0,2,1,3,4 H.enqueue19,0,3,19,3,4 H.enqueue0,0,4,0,3,4 H.enqueue99,0,5,99,3,4 printH.size printH.isEmpty printH.show
while not H.isEmpty:
printeventtostringH.dequeue
printH.size
printH.isEmpty
printH.show
In 3:
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
1228
12142019 hw12
Note: printouts of queues and heaps are with head or min value at top;
remember that heaps are not in decreasing order but heap ordered.
FIFO 3 False
0, 0.5, 0.4, 0
1, 0.1, 0.2, 0
1
False
SJF
3 False
1, 0.1, 0.2, 0
2, 0.2, 0.3, 0
1
False
Event 6 False
0.0, arrival, 4, 0.0, 3.0
1.0, arrival, 2, 1.0, 3.0
9.0, finish, 1, 9.0, 3.0
19.0, arrival, 3, 19.0, 3.0
61.0, arrival, 0, 61.0, 3.0
99.0, arrival, 5, 99.0, 3.0
0
True empty
0, 0.5, 0.4
1, 0.1, 0.2
2, 0.2, 0.3
1, 0.1, 0.2
0, 0.5, 0.4
2, 0.2, 0.3
0.0, arrival, 4, 0.0, 3.0
1.0, arrival, 2, 1.0, 3.0
9.0, finish, 1, 9.0, 3.0
61.0, arrival, 0, 61.0, 3.0
19.0, arrival, 3, 19.0, 3.0
99.0, arrival, 5, 99.0, 3.0
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
1328
12142019 hw12
In 4:
codes for event types
arrivalevent0
finishevent1
def runtasks, queuediscipline, traceFalse:
clock0current time in the simulation
if queuedisciplineFIFO: taskqueueFIFOQueue
else:
printusing SJF taskqueueSJFQueue
eventlistEventQueue for k in rangelentasks:
eventlist.enqueue tasksk0,arrivalevent,tasksk finishedtasksFIFOQueue
CPUempty list indicates CPU is idle
if trace:
printnExecution Trace
printnNote: printouts of queues and heaps are with head or min valu
e at top;
printremember that heaps are not in decreasing order but heap ordere
d.n
whilenot eventlist.isEmpty:
if trace: printn
printnClock: strround4clock printnEvents: eventlist.show printTask queue: strtaskqueue.show if CPU ! :
printCPU processing task tasktostringCPU else:
printCPU idle
printnFinished tasks: strfinishedtasks.show
get the next event
nexteventeventlist.dequeue if trace:
print
if trace:
printnNext Event: nteventtostringnextevent
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
1428
12142019
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse 1528
hw12
update the clock to this events time
clocknextevent0
arrival event
if nextevent1arrivalevent:
if CPU:Q and CPU both empty, no wait, inse
rt finish event
if trace:
printnCPU and task queue both empty, task goes directly
to CPU, create finish event.
tasknextevent2
arrivaltimetask0
servicetimetask1
task2clockarrivaltime
finishtimeclockservicetime
eventlist.enqueue finishtime, finishevent, task
CPUtask
else: taskqueue.enqueuenextevent2 if trace:
printnCPU busy, insert arriving task in task queue.
finish event, so put task in list of finished tasks and get next tas
k from queue if exists
else: finishedtasks.enqueuenextevent2 if trace:
printnTask in CPU finishes. CPU
if not taskqueue.isEmpty: if trace:
finish event.
printnDequeue next task and start to run in CPU, create
tasktaskqueue.dequeue
arrivaltimetask0
servicetimetask1
task2clockarrivaltime
finishtimeclockservicetime
eventlist.enqueue finishtime, finishevent, task
CPUtask
elif trace:
printnTask queue empty, CPU becomes idle.
if trace:
printnAll tasks complete, simulation ends.
printnFinished tasks: strfinishedtasks.show print
n
tasks
while not finishedtasks.isEmpty:
tasks.appendfinishedtasks.dequeue return tasks
queuewaittime
queuewaittime
12142019 hw12
In 5:
this prints out GANNT charts and charts for CPU
utilization, queue length, and queue length distribution.
def analyzeResultstask,showChartsTrue,showStatsTrue:
Determine various parameters and means
numTaskslentask
totalTimetask10task11task12
meanServiceTimenp.meantaskk1 for k in rangelentask meanInterarrivalTimetask10lentask
meanWaitTimenp.meantaskk2 for k in rangelentask cpuUtilizationsumtaskk1 for k in rangelentasktotalTime
increment0.001 stats
Xnp.arange0,totalTime,increment if showCharts:
Print GANTT Chart
figplt.figurefigsize15,10 fig.subplotsadjusthspace.5 ax1fig.addsubplot311 plt.yticksrangelentask plt.ylim0.5,lentask plt.titleGANNT Chart plt.ylabelTask Number plt.xlabelTime sec
if lentask50: lw1
elif lentask20: lw2
elif lentask10: lw3
else:
lw4
use to create charts and collect
for k in rangelentask:
arrivaltaskk0
beginservicearrivaltaskk2
endservicebeginservicetaskk1
plt.hlinesk, arrival, beginservice, colorC0,linestyledotte
d,linewidthlw
plt.hlinesk, beginservice, endservice, colorC0,linestyleso
lid,linewidthlw
Print CPU Utilization Chart
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
1628
12142019
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse 1728
hw12
Ynp.zeroslenX
for k in rangelentask:
arrivaltaskk0
beginservicearrivaltaskk2
endservicebeginservicetaskk1
for x in np.arangebeginservice,endservice,increment:
Yintxincrement1
Yscipy.signal.medfiltY
Y10
fig.addsubplot312,sharexax1 plt.yticksrangelentask plt.titleCPU Utilization plt.ylabelUsage plt.xlabelTime sec plt.ylim0.15,1.2 plt.plotX,Y
Plot Queue length over time
Y1np.zeroslenX
for k in rangelentask:
arrivaltaskk0
beginservicearrivaltaskk2
for x in np.arangearrival,beginservice,increment:
Y1intxincrement1
Y1scipy.signal.medfiltY1
Y110
if showCharts:
maxLengthintmaxY1
fig.addsubplot313,sharexax1 plt.yticksrangemaxLength1 plt.titleQueue Length Over Time plt.ylabelQueue Length plt.xlabelTime sec plt.ylim0.5,maxLength 0.5 plt.plotX,Y1
plt.show
showdistributionY1,titleDistribution of Queue Lengths
maxQueueLengthmaxY1
meanQueueLengthnp.meanY1
stdQueueLengthnp.stdY1
if showStats:
12142019
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse 1828
hw12
Problem Zero
Nothing to hand in here, but you need to understand how tasks are represented, and how they proceed through the system before you can do the probability problems to follow.
Each task is represented by a list
arrivaltime, servicetime, queuewaittime ,
where the list of tasks is given in order of arrival time, and the last parameter is 0 it will be filled in by the simulation and the resulting list returned by the simulation.
Play around with these examples, including changing the parameters to try different queue disciplines FIFO or Shortest Job First, and exhaustive tracing of the simulation. When you are comfortable with the framework, continue with the rest of the problems.
printnNumber of Tasks:tstrnumTasks
printTotal Time:ttstrround4totalTime
printMean Interarrival Time:tstrround4meanInterarrivalTime printMean Wait Time:ttstrround4meanWaitTime
printMean Service Time:tstrround4meanServiceTime printCPU Utilization:tstrround4cpuUtilization printMaximum queue length:tstrround4maxQueueLength printMean queue length:tstrround4meanQueueLength printStd of queue length:tstrround4stdQueueLength
return numTasks,totalTime,meanInterarrivalTime,meanWaitTime, meanServiceTime,cpuUtilization,
maxQueueLength,meanQueueLength,stdQueueLength
12142019 hw12
tasklist11, 1, 0,
3, 2, 0,
e
4, 1, 0
tasklist21, 4, 0, een FIFO and SJF
Basic example
FIFO vs SJF will not make a difference her
This example will show the difference betw
In FIFO, tasks executed as they arrive ta
In SJF, tasks will be executed in order
A more complicated example!
Will also behave differently under FIFO an
sks 0,1,2,3
2, 5, 0,
3, 2, 0,
6, 3, 0
tasklist30.1, 0.1, 0,
d SJF
0.3, 0.4, 0,
0.5, 0.2, 0,
0.6, 0.3, 0,
0.8, 0.2, 0
tasklist40,2,0, 1.1,3,0, 3.4,4,0, 3.45,3,0, 5,3.23,0,6.2,2.9,0
,6.4,2.32,0, 9.99,1.2,0, 10.3,3.4,0, 12.8,3.9,0, 15.2,3.4,0,
15.67,2.43,0,17.01,2.8,0,18.8,2.2,0,20.1,2.99,0,21.7,5.34,0,
24.4,2.2,0
taskstasklist1 taskstasklist2 taskstasklist3 taskstasklist4
run the simulation with the given task list
the second parameters gives the queue discipline, either FIFO or SJF
the third parameter controls whether an exhaustive trace is done of the simu
lation
finishedruntasks,FIFO,False finishedruntasks,SJF,False ng
finishedruntasks,FIFO,True finishedruntasks,SJF,True
printfinished
use shortest job first scheduli
exhaustive tracing
Analyze the results, printing out various charts, and return relevant statis
tics
statsanalyzeResultsfinished
statsnumTasks,totalTime,meanInterarrivalTime,meanWaitTime,meanServiceTim
e,
cpuUtilization,maxQueueLength,meanQueueLength,stdQueueLength
In 6:
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
1928
12142019 hw12
Number of Tasks:3
Total Time: 6.0
Mean Interarrival Time: 1.3333
Mean Wait Time:
Mean Service Time:
CPU Utilization:
Maximum queue length:
Mean queue length:
Std of queue length:
0.3333
1.3333
0.6667
1.0
0.1667
0.3727
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
2028
12142019 hw12
Problem One
A Give a task list ans1 which will produce the following Gannt Chart using FIFO:
B Give a task list ans2 which will produce the following Gannt Chart using SJF:
Hint: All arrival times and service requests will be integers.
In 137:
ans1a your answer here
statsanalyzeResultsrunans1a,FIFO,False ans1b your answer here
statsanalyzeResultsrunans1a,SJF,False
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
2128
12142019 hw12
Problem Two: Generating a Task List
Now we are going to generate a list of tasks following an Exponential Distribution for both the interarrival time and the service time. This is a very common assumption when doing these kind of queueing simulations. As described above, we will let
lamthe mean arrival rate of tasks in the system, and beta0.1mean service rate requested by tasks
but only lam will be changed during the simulation, from below 10 underload to above 10 overload. Recall that tasks are represented by a list
arrivaltime, servicetime, queuewaittime ,
where the last component is initialized to 0, and set during the simulation. From the list of completed tasks, it is possible to generate all the statistics discussed above this will already be done for you in the code.
We will use the scipy.stats function expon.rvsscale to generate the random variates for the interarrival times of tasks, and also for the service times of tasks.
This Python function uses scalethe mean of the distribution as a parameter, so you have to be careful, since it is the exact opposite of the way these distributions are described in the literature:
If you are interested in generating exponential variates with mean beta , then you call expon.rvsscalebeta , but
If you are interested in interarrival times of a Poisson process with arrival rate of lam arrivals per unit time, then you would call expon.rvsscale1lam .
Part A:
Complete the following to generate a list of tasks to input into the system, and then run the simulation and observe the results.
Hint: Dont forget that the interarrival times have to be added together to get the succession of actual arrival times.
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
2228
12142019 hw12
from scipy.stats import expon
def getTaskListnumtasks,lam,beta: time0
tasks
Your code here return tasks
parameters for the simulation
numtasks20
lam10mean arrival rate of tasks in the systemthis is the only p arameter we will change
beta0.1mean service time of arriving tasksdo not change this param eter
statsanalyzeResultsrungetTaskListnumtasks,lam,beta,FIFO,False
In 138:
Part B
Run the same simulation, but with the arrival rate set much lower than 10, say at 5.
In:
Part C
Now run the simulation with lam20. In:
Part D
Now I would like you to also generate the same simulations, but using SJF no need to give them all, just run them, and to run these various times to get a feel for how they behave, and then answer the following in a sentence or two:
When the lam10, the arrival rate and departure rate are evenly matching, and we might expect that the system could deal with all the requests. But is this case? Look at your results and answer this question: When the rates are evenly matched, do the results look more like the overloaded case or the underloaded case? Does using FIFO vs SJF change this?
Hint: dont worry about being too precise, I just want you to think about the issue a bit after observing the simulations.
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
2328
12142019 hw12
Answer:
Problem Three
Now we are going to run multiple trials of our simulation with different values of lam, and graph and analyze the results. In this problem, we will see the effect of changing lam by graphing three different result values against
lam . Part A
Complete the following code template to graph the CPU Utilization against lam and observe that this increases to the overload point and then remains close to 1.0.
In 139:
You may find the following useful:
numTasksresults0
totalTimeresults1
meanInterarrivalTimeresults2
meanWaitTimeresults3
meanServiceTimeresults4
cpuUtilizationresults5
maxQueueLengthresults6
meanQueueLengthresults7
stdQueueLengthresults8
Plot the statistic at resultsnumStat against the sequence of lam values in
lams
schedule is FIFO or SJF and titl is for the plot
def plotStatnumStat,numTasks,lams,beta,schedule,titl:
for each lam in lams, run the simulation and collect the statistic resul
tsnumStat in a list,
then plot these against lams to see the effect of arrival rate on this s
tatistic
pass
numTasks200
lamslistnp.arange5,20,0.2 s problem
beta0.1
not change this parameter
the different values of lam to use in thi
mean service time of arriving tasksdo
plotStat5,numTasks,lams,beta,scheduleFIFO,titlMean CPU Utilization vs A
rrival Rate
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
2428
12142019 hw12
Part B
Now plot these parameters vs the arrival rate using FIFO:
Mean Wait Time Mean Queue Length Std of Queue Length
and answer the following question: How do these behave as they exceed the overload point? Do changes happen at the overload point or before?
I am just looking for general observations, nothing too deep, just a couple of sentences of what you observe.
In:
Answer to B:
Problem Four
Now the question that might occur to you is: What would happen if we use SJF in the previous problem?
Compared with FIFO, SJF scheduling provides a shorter mean wait time meaning, as a whole, jobs spend less time in the system but may suffer from starvation long jobs may wait a very long time.
We will only look at
CPU Utilization Mean Queue Length Std Queue Length
Part A
Repeat the experiment of the previous problem, but using FIFO and SJF and only for the three statistics just given. I would like you to plot FIFO and SJF on the same graph, in order to compare.
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
2528
12142019 hw12
def plotStatistics2numTasks,lams,beta:Your code here
pass
numTasks200
lamslistnp.arange5,15,0.2 s problem
beta0.1
the different values of lam to use in thi
mean service time of arriving tasksdo
not change this parameter
plotStatistics2numTasks,lams,beta
In 140:
Part B
Answer the following question: Describe what you see and what effect the SJF queue discipline has on these statistics. Do they both behave the same with regard to overload?
Hint: The CPU Utilization graph will look a little odd, and you may think you have a bug! Try graphing each curve separately and then together and you will understand what is going on.
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
2628
12142019 hw12
Problem Five
In this problem we are going to investigate Littles Law, which is described concisely in Wikipedia as follows:
In queueing theory, a discipline within the mathematical theory of probability, Littles law is a theorem by John Little which states that the longterm average number of customers in a stationary i.e., not overloaded system is equal to the longterm average effective arrival rate multiplied by the average time that a customer spends in the system. Expressed algebraically the law is
Translating this into our parameters, and noting that the CPU utilization is the mean number of tasks in the CPU, this is equivalent to the following:
mean queue lengthCPU utilizationMean queue wait timemean service ti
memean interarrival time
The importance of Littles Law is that it holds under a wide variety of different distributions, queueing disciplines, number of queues and servers, etc.
We are going to do the same experiment, but only plot the ratio of the left side of the equation with the right side, i.e.,
littlesratiomean queue lengthCPU utilization Mean queue wait time
mean service timemean interarrival time
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
2728
L
WL
W
12142019 hw12
numTasks,totalTime,meanInterarrivalTime,meanWaitTime,meanServiceTime,
cpuUtilization,maxQueueLength,meanQueueLength,stdQueueLength
numTasksresults0
totalTimeresults1
meanInterarrivalTimeresults2
meanWaitTimeresults3
meanServiceTimeresults4
cpuUtilizationresults5
maxQueueLengthresults6
meanQueueLengthresults7
stdQueueLengthresults8
def plotStatistics3numTasks,lams,beta:Your code here
pass
numTasks500
lamslistnp.arange5,15,0.1 s problem
beta0.1
the different values of lam to use in thi
mean service time of arriving tasksdo
not change this parameter
plotStatistics3numTasks,lams,beta
In 141:
http:localhost:8888nbconverthtmlDownloadshw12.ipynb?downloadfalse
2828
Reviews
There are no reviews yet.