1 Overview In this project, you are going to build a “discrete-time event simulator” (see site below) for a number of CPU scheduling algorithms on a single CPU system. The goal of this project is to...

1 answer below »

1 Overview


In this project, you are going to build a “discrete-time event simulator” (see site below) for a number of CPU scheduling algorithms on a single CPU system. The goal of this project is to compare and assess the impact of different scheduling algorithms on different performance metrics, and across multiple workloads.


https://en.wikipedia.org/wiki/Discrete-event_simulation


1.1 CPU Scheduling Algorithms
We are going to implement the following CPU scheduling algorithms that we learned in class: 1. First-Come First-Served (FCFS) [non-preemptive]
2. Shortest Remaining Time First (SRTF) [preemptive by comparison of run time left]
3. Round Robin, with different quantum values (RR) [preemptive by quantum]


1.2 Performance Metrics
We are interested in computing the following metrics, for each experiment: • The average turnaround time
• The total throughput (number of processes done per unit time)
• The CPU utilization
• The average number of processes (queue length) in the ready queue Note: There is a relationship between:
- average queue length n,
- average arrival time λ (in processes/second), and


- average waiting time for a single process W (in seconds): n = λW.


This relationship allows computing any of these quantities from the other two.


2 The Simulator


A discrete-time event simulation 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 time can directly jump to the occurrence time of the next event, which is called next-event time progression.


Your simulator needs to generate a list of CPU-bound processes (no I/O happens for them). For each process, we need to generate its arrival time and its requested service time (or burst time). We can assume that processes arrive with an average rate λ that follows a Poisson process (hence exponential inter-arrival times). We will vary λ to simulate different loads. The service times are generated according to an exponential distribution (more detail below).


The simulator should stop after handling 10,000 processes to completion (without stopping the arrival of new processes), then it should output the statistics (i.e., the metrics above).


Events (e.g., process arrival, process completion, time-slice occurrence) that occur cause the simulator to update its current state (e.g., CPU busy/idle, number of processes in the ready queue, etc.). To keep track and handle events in the right order, we keep events in a priority list (called the “Events List”) that describes the future events and is kept sorted by the time of each event.


The simulator keeps a clock that represents the current system time, which takes the time from the event at the head of the Events List. Notice that when an event is handled at its assigned time, one or more future events may be added to the Events List. For example, when a process gets serviced by the CPU, another process can start executing (if one is waiting in the “Process Ready Queue”) and under FCFS, we know exactly when this process would finish, so we can schedule a completion event in the future and place it in the Events List. Notice that time hops between events, so you will need to update your simulator clock accordingly.


The simulator must take a few command-line arguments. The first one is to indicate the scheduling algorithm, a 1 through 3 value based on the list above. Also, it should take other arguments such as the average arrival rate, the average service time, and the quantum interval (for RR). Running the simulator with no arguments should display the arguments usage.


Each scheduler will need to maintain a queue (the “Process Ready Queue”) for the ready processes that are waiting for the CPU. A scheduler will select a process to run next based on the scheduling policy. Clearly, this queue should not be confused with the simulation’s Events List that is used to hold events to be handled in the future.


3 The Runs


We will vary the average arrival rate, λ, of processes from 1 process per second to 30 processes per second (based on a Poisson distribution). The service time is chosen according to an exponential distribution with an average service time of 0.06 sec.


For each value of λ, we need to compare the performance of each scheduler, based on the metrics above. It is recommended that you write a simple batch file (script) that would run those experiments and put the results in a file (that you can later import into a spreadsheet to plot the values).


Example script (assume your program is called sim and it creates the output file sim.data):


#!/bin/bash
rm sim.data
for ((i = 1; i



./sim 1 $i 0.06 0.01

cp sim.data /data/sim-1-$i-001.data done


NOTICE:
The “sim” program called in the above script has the following four arguments:




  • First: the scheduling algorithm number (1 to 3),




  • Second: the number of processes per second as the arrival rate,




  • Third: the average burst time for processes,




  • Fourth: the quantum value (used for RR only).


    This example bash script will run the simulator using FCFS (indicated by the value 1 in the first argument) for 30 different values of λ, using 0.06 as the average service time and a quantum value of 0.01 (which is ignored in other algorithms, except in Round Robin). Then, the script will move the sim.data file to a safe place for later use.


    With the Round Robin algorithm, a fourth argument is supplied to indicate the quantum value to be used. Use 2 different values of quantum: 0.01 and 0.2 (i.e., make two different runs). Remember, if a process finishes before its quantum expires, the CPU should be scheduled for the next process right away.







program2-nmlwzgcc.c program2-kkxtstbw.key program2data-530niv5b.numbers
Answered 2 days AfterOct 30, 2021

Answer To: 1 Overview In this project, you are going to build a “discrete-time event simulator” (see site...

Ayush answered on Nov 02 2021
120 Votes
Discrete-Time_Event_Simulator-master/a.csv
Lambda, CPU Utilization, Avg Turnaround, Avg Queuesize, System Throughput,
e,c,d
2,0,0,0,
3,0,0,0,
4,0,0,0,
5,0,0,0,
6,0,0,0,
7,0,0,0,
8,0,0,0,
9,0,0,0,
10,0,0,0,
11,0,0,0,
12,0,0,0,
13,0,0,0,
14,0,0,0,
15,0,0,0,
16,0,0,0,
17,0,0,0,
18,0,0,0,
19,0,0,0,
20,0,0,0,
21,0,0,0,
22,0,0,0,
23,0,0,0,
24,0,0,0,
25,0,0,0,
26,0,0,0,
27,0,0,0,
28,0,0,0,
29,0,0,0,
30,0,0,0
Discrete-Time_Event_Simulator-master/ErrorFile.csv
Lambda, Avg Service Time, Quantum, CPU Utilization, Avg Turnaround, Avg Queuesize, System Throughput,
1,0,0,0,0,0,0,
2,0,0,0,0,0,0,
3,0,0,0,0,0,0,
4,0,0,0,0,0,0,
5,0,0,0,0,0,0,
6,0,0,0,0,0,0,
7,0,0,0,0,0,0,
8,0,0,0,0,0,0,
9,0,0,0,0,0,0,
10,0,0,0,0,0,0,
11,0,0,0,0,0,0,
12,0,0,0,0,0,0,
13,0,0,0,0,0,0,
14,0,0,0,0,0,0,
15,0,0,0,0,0,0,
16,0,0,0,0,0,0,
17,0,0,0,0,0,0,
18,0,0,0,0,0,0,
19,0,0,0,0,0,0,
20,0,0,0,0,0,0,
21,0,0,0,0,0,0,
22,0,0,0,0,0,0,
23,0,0,0,0,0,0,
24,0,0,0,0,0,0,
25,0,0,0,0,0,0,
26,0,0,0,0,0,0,
27,0,0,0,0,0,0,
28,0,0,0,0,0,0,
29,0,0,0,0,0,0,
30,0,0,0,0,0,0
Discrete-Time_Event_Simulator-master/FirstComeFirstServe with graphs.xlsx
FirstComeFirstServe
        Lambda         Avg Service Time         Quantum         CPU Utilization         Avg Turnaround         Avg Queuesize         System Throughput
        1        0.06        0.01        5.903971818        0.0635235732        0.0034        0.9853682345
        2        0.06        0.01        11.9629003747        0.0689440901        0.0188        1.9791817121
        3        0.06        0.01        17.5949808586        0.0709571437        0.0392        3.0009052016
        4        0.06        0.01        24.0693561355        0.0793294382        0.0805        3.9998449981
        5        0.06        0.01        29.4552984919        0.083545379        0.1193        4.9357955318
        6        0.06        0.01        35.9717334529        0.0925889397        0.2002        6.0844797576
        7        0.06        0.01        42.3902255403        0.1057320936        0.3179        7.0051031303
        8        0.06        0.01        47.7734742803        0.1120243494        0.4022        7.9996332663
        9        0.06        0.01        53.7501175996        0.133077455        0.6503        8.9484596044
        10        0.06        0.01        59.6550814907        0.1465045429        0.8691        10.0671665236
        11        0.06        0.01        66.3867980302        0.1731341786        1.2472        11.0362812608
        12        0.06        0.01        71.653432628        0.1962231628        1.6007        11.8851388634
        13        0.06        0.01        78.2570440963        0.2861329152        2.9924        13.1309592247
        14        0.06        0.01        86.3743762856        0.4103791633        4.8852        14.1480324268
        15        0.06        0.01        90.315288069        0.6860038363        9.4492        14.9352660907
        16        0.06        0.01        93.1633144173        0.8117303028        11.9445        15.7498987338
        17        0.06        0.01        97.8824995622        2.1234735386        34.5062        16.7355569589
        18        0.06        0.01        99.7779748071        20.0487438455        356.4763        16.8033983181
        19        0.06        0.01        99.9578602134        38.9195776535        735.1644        16.4913404629
        20        0.06        0.01        99.8975672529        49.215450566        981.1022        16.796298045
        21        0.06        0.01        99.9746761244        62.1422349039        1322.1493        16.7476899787
        22        0.06        0.01        99.8989440628        74.3274343078        1610.2974        16.3796315244
        23        0.06        0.01        99.9302964024        77.8746772949        1808.5764        16.8687259951
        24        0.06        0.01        99.96740318        95.4286307769        2276.1953        16.3577463098
        25        0.06        0.01        99.9947085893        90.8385459914        2268.4241        16.8476558833
        26        0.06        0.01        99.9944896125        111.7165713879        2907.0128        16.6184870909
        27        0.06        0.01        99.9903087883        116.401731605        3201.9718        16.5749945783
        28        0.06        0.01        99.9856892994        125.2045482022        3471.2126        16.6466940548
        29        0.06        0.01        99.9878075843        130.8316679129        3763.4932        16.5083591163
        30        0.06        0.01        99.9832062375        137.0800008351        4129.9267        16.5343019798
FCFS - CPU Utilization
CPU Utilization    5.9039718179909997    11.962900374673699    17.594980858575401    24.069356135509899    29.455298491934101    35.971733452871902    42.390225540318198    47.773474280281398    53.7501175996059    59.655081490679002    66.386798030224199    71.653432627953904    78.257044096340493    86.374376285612698    90.315288069003401    93.163314417267301    97.8824995621639    99.777974807059294    99.957860213403706    99.897567252853705    99.974676124419005    99.898944062764201    99.930296402419501    99.967403180036001    99.994708589303102    99.994489612473004    99.990308788273296    99.985689299439898    99.987807584305799    99.983206237523106    
FCFS - Avg Turnaround
Avg Turnaround    6.3523573245361301E-2    6.89440901364652E-2    7.0957143672240999E-2    7.9329438183369502E-2    8.3545379024053498E-2    9.2588939653505301E-2    0.10573209361387401    0.11202434939350001    0.13307745495272499    0.14650454293385201    0.173134178598573    0.19622316278237401    0.28613291520906198    0.41037916329209201    0.68600383628790895    0.81173030278151703    2.1234735385537702    20.048743845542202    38.919577653502103    49.215450566046101    62.1422349038628    74.327434307820496    77.874677294913795    95.428630776904996    90.8385459913586    111.71657138787    116.401731605013    125.20454820224499    130.83166791291899    137.08000083508699    
FCFS - Avg Queuesize
Avg Queuesize    3.3999999999999998E-3    1.8800000000000001E-2    3.9199999999999999E-2    8.0500000000000002E-2    0.1193    0.20019999999999999    0.31790000000000002    0.4022    0.65029999999999999    0.86909999999999998    1.2472000000000001    1.6007    2.9923999999999999    4.8852000000000002    9.4491999999999994    11.9445    34.5062    356.47629999999998    735.1644    981.10220000000004    1322.1493    1610.2973999999999    1808.5763999999999    2276.1952999999999    2268.4241000000002    2907.0128    3201.9717999999998    3471.2125999999998    3763.4931999999999    4129.9267    
FCFS - System Throughput
System Throughput    0.98536823454386402    1.9791817120550199    3.0009052015814901    3.9998449981469699    4.93579553182132    6.0844797575717902    7.0051031303111699    7.9996332662827996    8.9484596044345697    10.067166523637299    11.0362812607724    11.8851388634143    13.1309592247414    14.148032426801199    14.9352660907489    15.749898733849699    16.735556958887901    16.803398318101799    16.491340462928299    16.796298045005098    16.747689978697998    16.3796315243778    16.868725995118201    16.357746309815699    16.8476558833319    16.6184870909319    16.574994578282499    16.646694054776699    16.508359116250201    16.534301979821699    
Discrete-Time_Event_Simulator-master/FirstComeFirstServe.csv
Lambda, Avg Service Time, Quantum, CPU Utilization, Avg Turnaround, Avg Queuesize, System Throughput,
1,0.06,0.01,5.903971817991006,0.06352357324536133,0.0034,0.9853682345438644
2,0.06,0.01,11.962900374673708,0.06894409013646527,0.0188,1.9791817120550297
3,0.06,0.01,17.594980858575415,0.07095714367224101,0.0392,3.0009052015814905
4,0.06,0.01,24.069356135509956,0.07932943818336956,0.0805,3.9998449981469757
5,0.06,0.01,29.45529849193415,0.0835453790240535,0.1193,4.935795531821324
6,0.06,0.01,35.97173345287197,0.09258893965350538,0.2002,6.0844797575717955
7,0.06,0.01,42.390225540318276,0.1057320936138749,0.3179,7.005103130311177
8,0.06,0.01,47.77347428028147,0.11202434939350037,0.4022,7.999633266282803
9,0.06,0.01,53.75011759960592,0.13307745495272594,0.6503,8.94845960443457
10,0.06,0.01,59.65508149067904,0.14650454293385218,0.8691,10.067166523637372
11,0.06,0.01,66.38679803022426,0.173134178598573,1.2472,11.036281260772466
12,0.06,0.01,71.65343262795399,0.1962231627823745,1.6007,11.88513886341435
13,0.06,0.01,78.25704409634052,0.2861329152090621,2.9924,13.130959224741476
14,0.06,0.01,86.3743762856127,0.4103791632920927,4.8852,14.148032426801272
15,0.06,0.01,90.31528806900343,0.6860038362879092,9.4492,14.935266090748904
16,0.06,0.01,93.1633144172673,0.8117303027815171,11.9445,15.749898733849749
17,0.06,0.01,97.88249956216397,2.1234735385537795,34.5062,16.735556958887962
18,0.06,0.01,99.77797480705937,20.048743845542212,356.4763,16.80339831810183
19,0.06,0.01,99.95786021340373,38.91957765350212,735.1644,16.4913404629283
20,0.06,0.01,99.89756725285375,49.21545056604617,981.1022,16.796298045005162
21,0.06,0.01,99.97467612441909,62.14223490386281,1322.1493,16.747689978698084
22,0.06,0.01,99.89894406276429,74.32743430782051,1610.2974,16.37963152437785
23,0.06,0.01,99.93029640241959,77.87467729491384,1808.5764,16.86872599511829
24,0.06,0.01,99.96740318003602,95.42863077690507,2276.1953,16.357746309815752
25,0.06,0.01,99.99470858930317,90.83854599135864,2268.4241,16.847655883331942
26,0.06,0.01,99.99448961247303,111.71657138787062,2907.0128,16.61848709093198
27,0.06,0.01,99.99030878827335,116.40173160501381,3201.9718,16.574994578282517
28,0.06,0.01,99.98568929943998,125.20454820224549,3471.2126,16.646694054776724
29,0.06,0.01,99.98780758430583,130.83166791291927,3763.4932,16.508359116250293
30,0.06,0.01,99.98320623752319,137.08000083508733,4129.9267,16.53430197982177
Discrete-Time_Event_Simulator-master/HighestResponseRatioNext with graphs.xlsx
HighestResponseRatioNext
        Lambda         Avg Service Time         Quantum         CPU Utilization         Avg Turnaround         Avg Queuesize         System Throughput
        1        0.06        0.01        5.9333514027        0.0635143238        0.0649        0.9947139618
        2        0.06        0.01        11.9321618274        0.0675633687        0.1307        2.0005552806
        3        0.06        0.01        18.0887308454        0.0715907133        0.2221        3.0435135592
        4        0.06        0.01        23.9896845011        0.0764179192        0.3021        4.0117364962
        5        0.06        0.01        29.7959457124        0.0805409114        0.3998        5.0167981707
        6        0.06        0.01        36.1664450833        0.0897085759        0.5423        6.0561701267
        7        0.06        0.01        42.1090233436        0.0971505408        0.6922        6.9499735148
        8        0.06        0.01        47.9416538436        0.1024193418        0.8303        8.0240806198
        9        0.06        0.01        54.3489343524        0.115706073        1.0391        8.949688346
        10        0.06        0.01        61.1300839618        0.1284871485        1.29        10.1600382306
        11        0.06        0.01        66.0962487321        0.148673595        1.6354        10.9178499453
        12        0.06        0.01        73.1635958821        0.1700677183        2.0734        12.0902475292
        13        0.06        0.01        78.5253987534        0.1850712197        2.3906        12.9510453603
        14        0.06        0.01        83.7904992752        0.2560975059        3.5545        13.8981294578
        15        0.06        0.01        92.5846125817        0.611191175        9.3574        15.1489816646
        16        0.06        0.01        96.2741490833        0.6407478617        10.118        15.9114425675
        17        0.06        0.01        99.9868113724        3.8235905586        65.339        16.8213842992
        18        0.06        0.01        99.9300686376        13.1787753582        254.1778        17.5328188235
        19        0.06        0.01        99.9504610819        14.0255213244        276.0614        18.002340123
        20        0.06        0.01        99.9780007634        19.9195878416        435.4965        18.4720750896
        21        0.06        0.01        99.9624288391        23.5487598098        559.1717        18.8656718652
        22        0.06        0.01        99.9599882334        27.3181986879        670.9998        19.1863909297
        23        0.06        0.01        99.9831680568        29.9107391716        836.0918        19.9180772705
        24        0.06        0.01        99.9814382074        31.9856405625        936.5047        20.1377318383
        25        0.06        0.01        99.9645166261        32.5259264469        1037.5358        21.0440161769
        26        0.06        0.01        99.9953928523        34.2891379405        1134.0795        21.5682450461
        27        0.06        0.01        99.9490601641        34.0053279632        1163.4787        21.7204376322
        28        0.06        0.01        99.9697346702        36.0444093402        1357.8031        22.4084044142
        29        0.06        0.01        99.9878114249        35.2622157217        1389.9317        22.7773091821
        30        0.06        0.01        99.9636109441        36.5579650419        1455.0905        22.9315332741
HRRN - CPU Utilization
CPU Utilization    5.9333514026812004    11.9321618274285    18.0887308454225    23.9896845010921    29.7959457124322    36.1664450833308    42.109023343581399    47.941653843640402    54.348934352404399    61.130083961789097    66.096248732138406    73.163595882050402    78.525398753400097    83.790499275239796    92.5846125817001    96.2741490833466    99.986811372424896    99.930068637649796    99.950461081855806    99.978000763438203    99.962428839094898    99.959988233436604    99.983168056777302    99.981438207350294    99.964516626082002    99.995392852281896    99.949060164144797    99.969734670211594    99.987811424933    99.963610944142502    
HRRN - Avg Turnaround
Avg Turnaround    6.3514323813944298E-2    6.7563368702262205E-2    7.1590713317687807E-2    7.6417919236235005E-2    8.0540911409716101E-2    8.9708575908701196E-2    9.7150540843232797E-2    0.102419341790025    0.11570607299286    0.128487148481122    0.14867359499024099    0.17006771827449299    0.185071219674456    0.25609750592984198    0.61119117496046604    0.64074786168245201    3.8235905585879499    13.1787753582219    14.025521324354701    19.919587841625301    23.5487598098021    27.3181986879265    29.910739171561101    31.985640562522899    32.525926446900797    34.289137940458502    34.0053279631761    36.044409340244997    35.262215721729298    36.557965041942197    
HRRN - Avg Queuesize
Avg Queuesize    6.4899999999999999E-2    0.13070000000000001    0.22209999999999999    0.30209999999999998    0.39979999999999999    0.5423    0.69220000000000004    0.83030000000000004    1.0390999999999999    1.29    1.6354    2.0733999999999999    2.3906000000000001    3.5545    9.3574000000000002    10.118    65.338999999999999    254.17779999999999    276.06139999999999    435.49650000000003    559.17169999999999    670.99980000000005    836.09180000000003    936.50469999999996    1037.5358000000001    1134.0795000000001    1163.4786999999999    1357.8031000000001    1389.9317000000001    1455.0905    
HRRN - System Throughput
System Throughput    0.994713961833261    2.0005552806065001    3.0435135592349698    4.01173649615437    5.0167981706936402    6.0561701267107297    6.9499735147876898    8.0240806198253694    8.9496883459538505    10.1600382305907    10.9178499453028    12.0902475291733    12.951045360284001    13.8981294577904    15.148981664613    15.911442567464199    16.8213842992329    17.532818823547199    18.0023401229803    18.4720750896279    18.8656718652115    19.186390929708001    19.9180772705257    20.137731838348099    21.044016176936299    21.568245046115599    21.720437632158301    22.4084044142216    22.777309182099501    22.9315332741436    
Discrete-Time_Event_Simulator-master/HighestResponseRatioNext.csv
Lambda, Avg Service Time, Quantum, CPU Utilization, Avg Turnaround, Avg Queuesize, System Throughput,
1,0.06,0.01,6.015825929628368,0.06381640155866816,0.0676,0.9962059780688269
2,0.06,0.01,11.949717544621716,0.06659561643762466,0.1327,2.018225706762477
3,0.06,0.01,18.672183182580177,0.07413314220352846,0.2365,3.0689204016592795
4,0.06,0.01,24.259155416355533,0.07915271367108014,0.3273,3.991180659343463
5,0.06,0.01,30.627720810889247,0.08475410728032669,0.422,5.0272605562457136
6,0.06,0.01,35.92687135826326,0.08823414247449375,0.5167,5.985023890756575
7,0.06,0.01,42.227450091631134,0.09695658123237685,0.7106,7.062736589968077
8,0.06,0.01,48.12376137882951,0.10848461104404897,0.8693,7.854321738194799
9,0.06,0.01,54.99144948003604,0.11589800118433652,1.0526,9.173419210807092
10,0.06,0.01,60.81115659526685,0.12872157788800068,1.2873,10.01061575782006
11,0.06,0.01,65.09284598490889,0.13907249328712454,1.5106,10.866313920867967
12,0.06,0.01,71.83948711179553,0.15249906123028745,1.841,12.182623235235319
13,0.06,0.01,78.09352147924201,0.21519271843359047,2.8016,12.909038352793825
14,0.06,0.01,82.46477512230335,0.2297987510779809,3.1232,13.607767046998477
15,0.06,0.01,87.21205189369817,0.2850013395012456,4.2025,14.76382843415817
16,0.06,0.01,91.92704097382814,0.42260572656392,6.6637,15.6783372114461
17,0.06,0.01,99.98261952698678,5.049326126520991,86.0749,16.84191060468186
18,0.06,0.01,99.97773354441274,13.857709848721372,261.7504,17.257340164185326
19,0.06,0.01,99.98050759353185,12.832849034736718,258.7293,17.808637259797067
20,0.06,0.01,99.92936660213942,19.942479466152015,433.0946,18.28697452952715
21,0.06,0.01,99.98697936092101,25.90210825162307,609.9556,18.801481254163548
22,0.06,0.01,99.9919420483384,26.631383375194645,664.5675,19.239282960038782
23,0.06,0.01,99.94835929769424,28.35378972920081,761.7249,19.661675345906776
24,0.06,0.01,99.99746057347048,32.28739179667786,971.7098,20.435078207743803
25,0.06,0.01,99.97617126559365,33.55793421678408,1040.7809,20.596342120876095
26,0.06,0.01,99.99792573121249,33.275869380428546,1071.5388,21.249881709236398
27,0.06,0.01,99.99353167482704,35.71019481474007,1248.9503,21.84009934986702
28,0.06,0.01,99.9867614530359,35.58517496024894,1336.9122,22.283803556079448
29,0.06,0.01,99.98391776334523,36.39695187241099,1410.7361,22.81915833910428
30,0.06,0.01,99.99320148699395,36.64644562478843,1503.9174,23.130374568176574
Discrete-Time_Event_Simulator-master/modules.py
import numpy as np
import random as rn
import csv
import time
from subprocess import call
from multiprocessing import Queue
from Queue import Empty
from Queue import PriorityQueue
from collections import deque
import heapq
# Test input values functions ###
def isValueBetweenOneAndFour(num):
    return True if (1 <= num <= 4) else False
def isValueBetweenZeroAndThousand(num):
    return True if (0.0 < num < 1000.0) else False
def isValueBetweenOneAndThousand(num):
    return True if (1.0 <= num < 1000.0) else False
def cleanInitialInputScheduleAlgorithm(scheduleAlgorithm):
    try:
        assert (isValueBetweenOneAndFour(int(scheduleAlgorithm))), "scheduleAlgorithm value should be an integer between 1 and 4"
    except:
        print("\nINPUT RANGE ERROR: \nscheduleAlgorithm selection should be an integer between 1 and 4\n")
        print("These are available options for Scheduling Algorthims:\n")
        print("1 - First Come First Serve")
        print("2 - Shortest Time Remaining First")
        print("3 - Highest Response Ratio Next")
        print("4 - Round Robin\n")
        while True:
            scheduleAlgorithm = raw_input('Number between 1 and 4: ')
            try:
                scheduleAlgorithm = int(scheduleAlgorithm)
            except:
                print("\nPlease input a number")
                continue
            if (isValueBetweenOneAndFour(scheduleAlgorithm)):
                print("\nInput accepted :)\n")
                break
            else:
                print("\nNumber must be between 1 and 4")
    return int(scheduleAlgorithm)
def cleanInitialInputLmdaValues(num):
    try:
        assert (isValueBetweenOneAndThousand(float(num))), "Lambda value should be a float bigger than 1 and smaller than 1000"
    except:
        print("\nINPUT RANGE ERROR: \n Lambda selection should be a float bigger than 1 and smaller than 1000\n")
        while True:
            num = raw_input('Number bigger than 1 and smaller than 1000: ')
            try:
                num = float(num)
            except:
                print("\nPlease input a number")
                continue
            if (isValueBetweenOneAndThousand(num)):
                print("\nInput accepted :)\n")
                break
            else:
                print("\nNumber must be bigger than 1 and smaller than 1000")
    return float(num)
def cleanInitialInputFloatValues(num, name):
    try:
        assert (isValueBetweenZeroAndThousand(float(num))), name + " value should be a float bigger than 0 and smaller than 1000"
    except:
        print("\nINPUT RANGE ERROR: \n" + name + " selection should be a float bigger than 0 and smaller than 1000\n")
        while True:
            num = raw_input('Number bigger than 0 and smaller than 1000: ')
            try:
                num = float(num)
            except:
                print("\nPlease input a number")
                continue
            if (isValueBetweenZeroAndThousand(num)):
                print("\nInput accepted :)\n")
                break
            else:
                print("\nNumber must be bigger than 0 and smaller than 1000")
    return float(num)
# End of test input values functions ###
def poissonStep(num):
    randomUniform = rn.uniform(0, 1)
    while(randomUniform == 0 or randomUniform == 1):
        randomUniform = rn.uniform(0, 1)
    poissonValue = (np.log(randomUniform))/(-num) # x = (-1/lmbda)*ln(y) or (-Ts)*ln(y)
    # print("Poisson Value: " + str(poissonValue))
    return poissonValue
def poissonStep2(num):
    return np.random.poisson(num)
class Process:
    def __init__(self, params):
        self.id = params.get('id')
        self.arrivalTime = params.get('arrivalTime')
        self.serviceTime = params.get('serviceTime')
        self.remainingTime = params.get('serviceTime')
        self.completionTime = 0
def createProcess(params):
    processParams = {
        "id" : params.get("id"),
        "arrivalTime" : float(params.get("clock") + poissonStep(params.get("lmbda"))),
        "serviceTime" : float(poissonStep(params.get("mu")))
    }
    # print("arrivalTime " + str(processParams.get("arrivalTime")))
    # print("serviceTime " + str(processParams.get("serviceTime")))
    return Process(processParams)
class Event:
    def __init__(self, params):
        self.type = params.get('type')
        self.time = params.get('time')
        self.process = params.get('process')
def createArrivalEvent(processParams):
    newProcess = createProcess(processParams)
    eventParams = {
        "type" : "ARR",
        "time" : newProcess.arrivalTime,
        "process" : newProcess
    }
    return Event(eventParams)
def createDepartureEvent(process, time):
    eventParams = {
        "type" : "DEP",
        "time" : time,
        "process" : process
    }
    return Event(eventParams)
def createRoundRobinEvent(process, time):
    eventParams = {
        "type" : "RR",
        "time" : time,
        "process" : process
    }
    return Event(eventParams)
class RecordedData:
    def __init__(self, params):
        self.CPU_time = params.get('CPU_time')
        self.turnaround = params.get('turnaround')
        self.queueSize = params.get('queueSize')
        #self.throughput = params.get('throughput')
def newRecordedData(process, clock, queueSize):
    recordedDataParams = {
        "CPU_time" : process.serviceTime,
        "turnaround" : clock - process.arrivalTime,
        "queueSize" : queueSize
    }
    # print("\n\nArrival: " + str(process.arrivalTime))
    # print("Clock: " + str(clock))
    # print("Turnaround: " + str(recordedDataParams.get("turnaround")))
    return RecordedData(recordedDataParams)
def interpretData(recordedDataList, processParams, numSamples):
    totalCPU_UtilizationTime = 0
    sumOfAllTurnaroundTimes = 0
    sumOfAllQueueSizes = 0
    totalThroughput = 0
    for data in recordedDataList:
        # print("CPU: " + str(data.CPU_time))
        # print("Turn: " + str(data.turnaround))
        # print("Queue: " + str(data.queueSize))
        totalCPU_UtilizationTime += data.CPU_time
        sumOfAllTurnaroundTimes += data.turnaround
        sumOfAllQueueSizes += data.queueSize
    print("totalCPU_UtilizationTime: " + str(totalCPU_UtilizationTime))
    print("sumOfAllTurnaroundTimes: " + str(sumOfAllTurnaroundTimes))
    print("sumOfAllQueueSizes: " + str(sumOfAllQueueSizes))
    print("CPU_IddleTime: " + str(processParams.get("CPU_IddleTime")))
    clock = processParams.get("clock")
    # CPU_Utilization = float(100*totalCPU_UtilizationTime/clock)
    CPU_Utilization = 100*(clock - processParams.get("CPU_IddleTime"))/clock
    avgTurnaroundTime = float(sumOfAllTurnaroundTimes/numSamples)
    avgQueueSize = float(sumOfAllQueueSizes/numSamples)
    systemThroughput = float(numSamples/clock)
    avgServiceTime = processParams.get("avgServiceTime")
    roundRobinQuantum = processParams.get("roundRobinQuantum")
    lmbda = processParams.get("lmbda")
    csvParams = {
        "CPU_Utilization": CPU_Utilization,
        "avgTurnaroundTime": avgTurnaroundTime,
        "avgQueueSize": avgQueueSize,
        "systemThroughput" :systemThroughput,
        "avgServiceTime": avgServiceTime,
        "quantum": roundRobinQuantum,
        "line": int(lmbda)
    }
    return csvParams
def recordToCSV(params, dataType):
    # Following section records data to appropriate row in corresponding excel file
    excelList = []
    fileName = ''
    if(dataType == 1):
        fileName = 'FirstComeFirstServe.csv'
    elif(dataType == 2):
        fileName = 'ShortestTimeRemainingFirst.csv'
    elif(dataType == 3):
        fileName = 'HighestResponseRatioNext.csv'
    elif(dataType == 4):
        if(params.get("quantum") == .01):
            fileName = 'RoundRobin.csv'
        else:
            fileName = 'RoundRobin2.csv'
    else:
        fileName = 'ErrorFile.csv'
    # Read all data from the csv file.
    with open(fileName, 'rb') as b:
        excelFile = csv.reader(b)
        excelList.extend(excelFile)
    line = params.get("line")
    lmbda = line
    avgServiceTime = params.get("avgServiceTime")
    quantum = params.get("quantum")
    CPU_Utilization = params.get("CPU_Utilization")
    avgTurnaroundTime = params.get("avgTurnaroundTime")
    avgQueueSize = params.get("avgQueueSize")
    systemThroughput = params.get("systemThroughput")
    # data to override in the format {line_num_to_override:data_to_write}.
    # Lambda, Avg Service Time, Quantum, CPU Utilization, Avg Turnaround, Avg Queuesize, System Throughput,
    line_to_override = {line:[lmbda, avgServiceTime, quantum, CPU_Utilization, avgTurnaroundTime, avgQueueSize, systemThroughput]}
    # Write data to the csv file and replace the lines in the line_to_override dict.
    with open(fileName, 'wb') as b:
        writer = csv.writer(b)
        for line, row in enumerate(excelList):
            data = line_to_override.get(line, row)
            writer.writerow(data)
def removeDepartures_PriorityQueue(priority_Queue):
    queueObjectsList = []
    while(priority_Queue.empty() != True):
        queueObjectsList.append(priority_Queue.get()[1])
    for queueObject in queueObjectsList:
        if queueObject.type == "ARR":
            priority_Queue.put((queueObject.time, queueObject))
    return priority_Queue
def getShortestRemainingTime(processList):
    organizedBySRTFQueue = PriorityQueue()
    for process in processList:
        organizedBySRTFQueue.put((process.remainingTime, process))
    highestPriorityProcess = organizedBySRTFQueue.get()[1]
    processList.remove(highestPriorityProcess)
    return highestPriorityProcess
def getHighestResponseRatio(processList, clock):
    # organizedByHRRNQueue = PriorityQueue()
    # for process in processList:
    #     waiting = clock - process.arrivalTime
    #     responseRatio = -1*((waiting/process.serviceTime) + 1)
    #     organizedByHRRNQueue.put((responseRatio, process))
    # highestPriorityProcess = organizedByHRRNQueue.get()[1]
    HighestResponseRatio = 0
    highestPriorityProcess = None
    for process in processList:
        waiting = clock - process.arrivalTime
        responseRatio = ((waiting/process.serviceTime) + 1)
        if(responseRatio > HighestResponseRatio):
            HighestResponseRatio = responseRatio
            highestPriorityProcess = process
    return highestPriorityProcess
def FCFS_Samples(processParams, numSamples):
    # Create appropriate data structures for FCFS
    FCFS_Queue = deque()
    event_PriorityQueue = PriorityQueue()
    # Create process counter to test end condition
    processCounter = 0
    # Queue Size to keep track of size of FCFS Queue
    queueSize = 0
    # To keep track of CPU being utilized
    CPU_iddle = 1
    lastCPU_UtilizationTime = 0
    totalCPU_IdleTime = 0
    # To store simulated information
    recordedDataList = []
    # If process takes more than 5 minutes, it will terminate
    timeout = time.time() + 60*5
    # Create first process and place it as an arrival at time 0 in event_PriorityQueue
    arrivalEvent = createArrivalEvent(processParams)
    processParams["id"] += 1
    event_PriorityQueue.put((arrivalEvent.time, arrivalEvent))
    while(processCounter < numSamples and time.time() < timeout):
        currentEvent = event_PriorityQueue.get()[1]
        clock = currentEvent.time
        currentProcess = currentEvent.process
        # print("clock:" + str(clock))
        # print("processCounter: " + str(processCounter))
        # print("Queue Size: " + str(queueSize))
        if(currentEvent.type == "ARR"):
            if(CPU_iddle == 1):
                CPU_iddle = 0
                totalCPU_IdleTime += clock - lastCPU_UtilizationTime
                departureEvent = createDepartureEvent(currentProcess, clock + currentProcess.serviceTime)
                event_PriorityQueue.put((departureEvent.time, departureEvent))
            else:
                queueSize += 1
                FCFS_Queue.appendleft(currentProcess)
            # Create a new process to arrive
            processParams.update({'clock': clock})
            arrivalEvent = createArrivalEvent(processParams)
            processParams["id"] += 1
            event_PriorityQueue.put((arrivalEvent.time, arrivalEvent))
        elif(currentEvent.type == "DEP"):
            if(len(FCFS_Queue) == 0):
                CPU_iddle = 1
                lastCPU_UtilizationTime = clock
            else:
                queueSize -= 1
                queuedProcess = FCFS_Queue.pop()
                departureEvent = createDepartureEvent(queuedProcess, clock + queuedProcess.serviceTime)
                event_PriorityQueue.put((departureEvent.time, departureEvent))
            # Record the data and add one to the process counter end condition
            recordedDataList.append(newRecordedData(currentProcess, clock, queueSize))
            processCounter += 1
    # Update clock to final value
    if(event_PriorityQueue.empty() == False):
        finalEvent = event_PriorityQueue.get()[1]
        clock = finalEvent.time + finalEvent.process.serviceTime
        processParams.update({'clock': clock})
    processParams.update({'CPU_IddleTime': totalCPU_IdleTime})
    return recordedDataList
def SRTF_Samples(processParams, numSamples):
    # Create appropriate data structures for SRTF
    processList = []
    event_PriorityQueue = PriorityQueue()
    # Create process counter to test end condition
    processCounter = 0
    # To keep track of CPU being utilized
    CPU_iddle = 1
    lastCPU_UtilizationTime = 0
    totalCPU_IdleTime = 0
    # To keep track of previous event times since SRTF is preemptive
    runningProcessStartTime = 0
    nextDepartureTime = 0
    runningProcess = []
    # To store simulated information
    recordedDataList = []
    # If process takes more than 5 minutes, it will terminate
    timeout = time.time() + 60*5
    # Create first process and place it as an arrival at time 0 in event_PriorityQueue
    arrivalEvent = createArrivalEvent(processParams)
    processParams["id"] += 1
    event_PriorityQueue.put((arrivalEvent.time, arrivalEvent))
    while(processCounter < numSamples and time.time() < timeout):
        currentEvent = event_PriorityQueue.get()[1]
        clock = currentEvent.time
        currentProcess = currentEvent.process
        if(currentEvent.type == "ARR"):
            # Add the current process to the list of considered processes that will be tested
            processList.append(currentProcess)
            # If CPU is iddle, run the process and create a departure event based on its service time
            if(CPU_iddle == 1):
                CPU_iddle = 0
                totalCPU_IdleTime += clock - lastCPU_UtilizationTime
                departureEvent = createDepartureEvent(currentProcess, clock + currentProcess.serviceTime)
                event_PriorityQueue.put((departureEvent.time, departureEvent))
                nextDepartureTime = clock + currentProcess.serviceTime
                runningProcess = currentProcess
                runningProcessStartTime = clock
            else:
                # If CPU is not iddle we need to check if this process should be running instead of the current one
                # otherwise place it in the process list
                if(nextDepartureTime > currentProcess.remainingTime + clock):
                    for processObject in processList:
                        if(processObject == runningProcess):
                            processObject.serviceTime -= clock - runningProcessStartTime
                    nextDepartureTime = clock + currentProcess.serviceTime
                    runningProcess = currentProcess
                    runningProcessStartTime = clock
                    event_PriorityQueue = removeDepartures_PriorityQueue(event_PriorityQueue)
                    departureEvent = createDepartureEvent(currentProcess, clock + currentProcess.serviceTime)
                    event_PriorityQueue.put((departureEvent.time, departureEvent))
                else:
                    pass
            # Create a new process to arrive
            processParams.update({'clock': clock})
            arrivalEvent = createArrivalEvent(processParams)
            processParams["id"] += 1
            event_PriorityQueue.put((arrivalEvent.time, arrivalEvent))
        elif(currentEvent.type == "DEP"):
            #processList.remove(currentProcess)
            for processObject in processList:
                        if(processObject == runningProcess):
                            processList.remove(processObject)
            if not processList:
                CPU_iddle = 1
                lastCPU_UtilizationTime = clock
                # Create a ridiculous departure time so that it gets overiden when a new process arrives
                nextDepartureTime = 1000000 + clock
                runningProcess = None
                runningProcessStartTime = 1000000 + clock
            else:
                queuedProcess = getShortestRemainingTime(processList)
                departureEvent = createDepartureEvent(queuedProcess, clock + queuedProcess.serviceTime)
                event_PriorityQueue.put((departureEvent.time, departureEvent))
                nextDepartureTime = departureEvent.time
                runningProcess = departureEvent
                runningProcessStartTime = clock
            # Record the data and add one to the process counter end condition
            recordedDataList.append(newRecordedData(currentProcess, clock, len(processList)))
            processCounter += 1
    # Update clock to final value
    if(event_PriorityQueue.empty() == False):
        finalEvent = event_PriorityQueue.get()[1]
        clock = finalEvent.time + finalEvent.process.serviceTime
        processParams.update({'clock': clock})
    processParams.update({'CPU_IddleTime': totalCPU_IdleTime})
    return recordedDataList
def HRRN_Samples(processParams, numSamples):
    # Create appropriate data structures for HRRN
    processList = []
    event_PriorityQueue = PriorityQueue()
    # Create process counter to test end condition
    processCounter = 0
    # To keep track of CPU being utilized
    CPU_iddle = 1
    lastCPU_UtilizationTime = 0
    totalCPU_IdleTime = 0
    # To keep track of running process
    runningProcess = None
    # To store simulated information
    recordedDataList = []
    # If process takes more than 20 minutes, it will terminate
    timeout = time.time() + 60*20
    # Create first process and place it as an arrival at time 0 in event_PriorityQueue
    arrivalEvent = createArrivalEvent(processParams)
    processParams["id"] += 1
    event_PriorityQueue.put((arrivalEvent.time, arrivalEvent))
    while(processCounter < numSamples and time.time() < timeout):
        currentEvent = event_PriorityQueue.get()[1]
        clock = currentEvent.time
        currentProcess = currentEvent.process
        if(currentEvent.type == "ARR"):
            # Add the current process to the list of considered processes that will be...
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Have files?