SHARE
TWEET

Untitled

a guest Jul 16th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """
  2. CPU Scheduling
  3. CSCI 4210 OPSYS
  4. Summer 2019
  5. """
  6.  
  7. import sys
  8. from classes.config import Config
  9. from classes.process import Process
  10. from classes.state import State
  11. from classes.random_class import Rand48
  12. from copy import deepcopy
  13. import math
  14.  
  15. def initialize_processes():
  16.     rand48_obj = Rand48(Config.instance._seed)
  17.     rand48_obj.srand(Config.instance._seed)
  18.     processes = list()
  19.     alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  20.     n_processes = Config.instance._nProcesses
  21.     for i in range(n_processes):
  22.         process = Process(alpha[i], rand48_obj)
  23.         processes.append(process)
  24.     return processes
  25.  
  26.  
  27. def accept_new_process(alg, time, time_str, state, process, output):
  28.     state.place_ready(process)
  29.     if state.running == '':
  30.         process.context_switch = Config.instance._contextSwitchDuration//2 - 1
  31.  
  32.     output += time_str
  33.     if time == 9:
  34.         x = 0
  35.     if alg == "SRT" or alg == "SJF":
  36.         state.ready.sort(key=lambda x: (x.tau[min(x.burst_index, len(x.tau)- 1)] - x.burst_elapsed, x._id))
  37.  
  38.     runningProcess = state.get_process(state.running)  
  39.     if alg == "SRT" and runningProcess != None and max(process.tau[process.burst_index] - process.burst_elapsed, -2) <= \
  40.                 max(runningProcess.tau[runningProcess.burst_index - 1] - runningProcess.burst_elapsed, -2):
  41.         output += "(tau " + str(process.tau[process.burst_index]) + "ms) arrived; preempting {:s} {:s}\n" \
  42.             .format(str(runningProcess), state.getReadyQ())
  43.         #output += time_str + "now preempting\n"
  44.         state.preemption(process, False)
  45.         state.ready[0].context_switch = Config.instance._contextSwitchDuration - 1
  46.         runningProcess.context_switch = Config.instance._contextSwitchDuration // 2 - 1
  47.         runningProcess.time_remaining = runningProcess.burst_time
  48.  
  49.         runningProcess.resetBurstCounters(rsElapsed=False)
  50.         if runningProcess.burst_elapsed == -1:
  51.            runningProcess.burst_elapsed = 0
  52.     elif alg == "SRT" or alg == "SJF":
  53.         output += "(tau " + str(process.tau[process.burst_index]) + "ms) arrived; added to ready queue {:s}\n" \
  54.             .format(state.getReadyQ())
  55.     else:
  56.         output += "arrived; added to ready queue {:s}\n".format(state.getReadyQ())
  57.     # TODO add contextswitch
  58.     return output
  59.  
  60.  
  61. def handle_context_switch(alg, time, time_str, state, process, output):
  62.  
  63.     if process.context_switch == 0:
  64.         process.resetContextSwitch()
  65.         if process.status == "ready":
  66.             state.switches += 1
  67.             process.CPU_time += 1
  68.             #output += time_str + "In ready within handle_context_switch for {:s}\n".format(str(process))
  69.             process.burst_time = process.bursts[min(process.burst_index, len(process.tau)- 1)].actual_burst_time
  70.  
  71.             if process.burst_elapsed == -1:
  72.                 if alg == "SRT":
  73.                     process.burst_index += 1
  74.                 if process.burst_index == process.n_bursts:
  75.                     return (output, False)
  76.             if alg != "SRT":
  77.                 process.burst_index += 1
  78.  
  79.             if (alg == "RR" or alg == "SRT") and process.time_remaining != -1:
  80.                 process.burst_time = process.time_remaining
  81.                 process.time_remaining = -1
  82.                 #process.burst_index -= 1
  83.             if (alg == "SRT" or alg == "SJF") and process.burst_index < len(process.tau):
  84.                 state.ready.sort(key=lambda x: (x.tau[min(x.burst_index, len(x.tau)- 1)] - x.burst_elapsed, x._id))
  85.             process.start_burst = time              # a marker indicating the current time (to determine total allocated time for burst)
  86.             #output += time_str + "now preempting\n"
  87.  
  88.             #print(str(time) + " " + str(state.getReadyQ()) + str(process))
  89.             state.preemption(process, True)
  90.  
  91.             output += time_str
  92.             if (alg == "SRT" or alg == "SJF") and process.burst_index <= process.n_bursts:
  93.                 output += "(tau " + str(process.tau[process.burst_index - 1]) + "ms) "
  94.  
  95.             output += "started using the CPU "
  96.  
  97.             if (alg == "SRT") and process.burst_index <= process.n_bursts:
  98.                 output += "with {:d}ms burst remaining {:s}\n".format(process.burst_time, state.getReadyQ())
  99.             else:
  100.                 output += "for {:d}ms burst {:s}\n".format(process.burst_time, state.getReadyQ())
  101.  
  102.             if len(state.ready) > 0:
  103.                 first_proc = state.ready[0]
  104.                 first_proc_index = first_proc.burst_index if first_proc.burst_elapsed == -1 else first_proc.burst_index - 1
  105.                 #first_proc_index = first_proc.burst_index
  106.                 #print("{:s}: {:d}".format(str(first_proc), max(first_proc.tau[first_proc_index] - first_proc.burst_elapsed, -2)))
  107.                 #print("{:s}: {:d}\n".format(str(process), max(process.tau[process.burst_index] - process.burst_elapsed, -2)))
  108.                 if alg == "SRT" and max(first_proc.tau[first_proc_index] - first_proc.burst_elapsed, -2) <= \
  109.                         max(process.tau[process.burst_index] - process.burst_elapsed, -2) and \
  110.                         first_proc.burst_index < first_proc.n_bursts:
  111.  
  112.                     output += "time {:d}ms: Process {:s} (tau {:d}ms) will preempt {:s} {:s}\n"\
  113.                         .format(time, str(first_proc), first_proc.tau[first_proc_index], str(process), state.getReadyQ())
  114.                     output += "{:s}: tau: {:d} elapsed: {:d} actual: {:d}\n{:s}: tau: {:d} elapsed: {:d} actual: {:d}\n".format(str(first_proc), first_proc.tau[first_proc_index ], first_proc.burst_elapsed, \
  115.                         first_proc.bursts[first_proc_index ].actual_burst_time, str(process), process.tau[process.burst_index], process.burst_elapsed, process.bursts[process.burst_index].actual_burst_time)
  116.                     first_proc.context_switch = Config.instance._contextSwitchDuration - 1
  117.                     process.context_switch = Config.instance._contextSwitchDuration//2 - 1
  118.                     process.time_remaining = process.burst_time
  119.                     process.resetBurstCounters(rsElapsed=False)
  120.                     if process.burst_elapsed == -1:
  121.                         process.burst_elapsed = 0
  122.  
  123.  
  124.         elif process.status == "running":
  125.             if (alg == "RR" or alg == "SRT") and process.time_remaining != -1:
  126.                 state.preemption(None, False)
  127.             else:
  128.                 state.place_blocked(state.get_process(state.running))
  129.     elif process.context_switch > 0:
  130.         process.context_switch -= 1
  131.         return (None, True)
  132.  
  133.     return (output, False)
  134.  
  135. def print_list(l):
  136.     output = "["
  137.     for i in range(len(l)):
  138.         output += str(l[i]) + ", "
  139.     output += "]"
  140.     return output
  141.  
  142. def do_burst(alg, time, time_str, time_slice, state, process, output, terminated_processes):
  143.     process.CPU_time += 1
  144.     if time == 42:
  145.         x = 12
  146.     if process.burst_time == 0 or (time - process.start_burst) == time_slice:
  147.         if alg == "RR":
  148.             if time - process.start_burst == time_slice and len(state.ready) == 0:
  149.                 output += "time {:d}ms: Time slice expired; no preemption because ready queue is empty {:s}\n"\
  150.                     .format(time, state.getReadyQ())
  151.                 process.burst_time -= 1
  152.                 return (output, True)
  153.             elif time - process.start_burst == time_slice and process.burst_time != 0:
  154.                 time_remaining = process.bursts[process.burst_index - 1].actual_burst_time - time_slice
  155.                 output += time_str + "Time slice expired; process {:s} preempted with {:d}ms to go {:s}\n"\
  156.                     .format(str(process), time_remaining, state.getReadyQ())
  157.                 process.time_remaining = time_remaining
  158.                 process.context_switch = Config.instance._contextSwitchDuration//2 - 1
  159.                 if state.ready[0] in state.processes_run:
  160.                     state.ready[0].context_switch = Config.instance._contextSwitchDuration - 1
  161.                 else:
  162.                     state.ready[0].context_switch = Config.instance._contextSwitchDuration - 1
  163.                 process.resetBurstCounters(rsElapsed=True)
  164.                 process.burst_index -= 1
  165.                 return (output, True)
  166.  
  167.         remaining_bursts = len(process.bursts) - process.burst_index
  168.         if process.burst_index == len(process.bursts):
  169.             terminated_processes.append(process)
  170.             output += time_str + "terminated {:s}\n".format(state.getReadyQ())
  171.             state.running = ''
  172.             if len(state.ready) > 0:
  173.                 state.ready[0].context_switch = Config.instance._contextSwitchDuration-1
  174.             '''state.turnaround += float(process.CPU_time/process.n_bursts)
  175.             state.wait_time += float((process.CPU_time-process.totalBurstTime())/process.n_bursts)'''
  176.             return (output, True)
  177.  
  178.         process.start_io = time
  179.         process.io_time = process.bursts[process.burst_index - 1].io_burst_time
  180.         process.resetBurstCounters(rsElapsed=True)
  181.         if len(state.ready) > 0:
  182.             #output += "processes_run == " + print_list(state.processes_run) + "\n"
  183.             state.ready[0].context_switch = Config.instance._contextSwitchDuration - 1
  184.             process.context_switch = Config.instance._contextSwitchDuration // 2
  185.             #output += ("set the context switch of {:s} to {:d}\n".format(str(state.ready[0]), state.ready[0].context_switch))
  186.         else:
  187.             process.context_switch = Config.instance._contextSwitchDuration//2
  188.  
  189.         burstWord = "bursts" if remaining_bursts > 1 else "burst"
  190.  
  191.         output += time_str
  192.  
  193.         if alg == "SRT" or alg == "SJF":
  194.             output += "(tau " + str(process.tau[process.burst_index - 1]) + "ms) "
  195.  
  196.         output += "completed a CPU burst; {:d} {:s} to go {:s}\n"\
  197.             .format(remaining_bursts, burstWord, state.getReadyQ())
  198.  
  199.         if alg == "SRT" or alg == "SJF":
  200.             output += "time {:d}ms: Recalculated tau = {:d}ms for process {:s} {:s}\n" \
  201.                 .format(time, process.tau[process.burst_index], str(process), state.getReadyQ())
  202.         output += time_str + "switching out of CPU; will block on I/O until time {:d}ms {:s}\n"\
  203.             .format(process.io_time + time + process.context_switch, state.getReadyQ())
  204.         runningProcess = state.get_process(state.running)
  205.         # if runningProcess:
  206.         #     state.place_blocked(state.get_process(state.running))
  207.         process.time_remaining = -1
  208.     elif alg == "RR":
  209.         if process.burst_time > 0 and (time - process.start_burst) != time_slice:
  210.             process.burst_time -= 1
  211.             return (None, True)
  212.  
  213.     elif process.burst_time > 0:
  214.         process.burst_time -= 1
  215.         process.burst_elapsed += 1
  216.         return (None, True)
  217.  
  218.     return (output, False)
  219.  
  220.  
  221. def do_IO_burst(alg, time, time_str, state, process, output):
  222.     if process.io_time == 0:
  223.         state.place_ready(process)
  224.         process.resetIOCounters()
  225.         if time == 92:
  226.             print("here")
  227.         runningProcess = state.get_process(state.running)
  228.        
  229.         if runningProcess:
  230.             output += "{:d}\n".format(max(process.tau[process.burst_index] - process.burst_elapsed, -2));
  231.             output += "{:d}\n".format(max(runningProcess.tau[runningProcess.burst_index-1] - runningProcess.burst_elapsed, -2));
  232.        
  233.         if time == 1159:
  234.             x = 2
  235.  
  236.         if alg == "SRT" and runningProcess != None and max(process.tau[process.burst_index] - process.burst_elapsed, -2) <= \
  237.                 max(runningProcess.tau[runningProcess.burst_index-1] - runningProcess.burst_elapsed, -2):
  238.             output += time_str + "(tau " + str(process.tau[process.burst_index]) + "ms) completed I/O; preempting {:s} {:s}\n" \
  239.                 .format(str(runningProcess), state.getReadyQ())
  240.             output += "{:s}: tau: {:d} elapsed: {:d} actual: {:d}\n{:s}: tau: {:d} elapsed: {:d} actual: {:d}\n".format(str(process), process.tau[process.burst_index], process.burst_elapsed, \
  241.                 process.bursts[process.burst_index].actual_burst_time, str(runningProcess), runningProcess.tau[runningProcess.burst_index-1], runningProcess.burst_elapsed, runningProcess.bursts[runningProcess.burst_index-1].actual_burst_time)
  242.             state.ready[0].context_switch = Config.instance._contextSwitchDuration - 1
  243.             runningProcess.context_switch = Config.instance._contextSwitchDuration//2 - 1
  244.             runningProcess.time_remaining = runningProcess.burst_time + 1
  245.             runningProcess.resetBurstCounters(rsElapsed=False)
  246.             if runningProcess.burst_elapsed == -1:
  247.                 runningProcess.burst_elapsed = 0
  248.         else:
  249.             if alg == "SRT" or alg == "SJF":
  250.                 output += time_str + "(tau " + str(process.tau[process.burst_index]) + "ms) completed I/O; added to ready queue {:s}\n" \
  251.                     .format(state.getReadyQ())
  252.                 if (runningProcess != None):
  253.                     x = 0
  254.                     #output += "{:s}: tau: {:d} elapsed: {:d} actual: {:d}\n{:s}: tau: {:d} elapsed: {:d} actual: {:d}\n".format(str(process), process.tau[process.burst_index], process.burst_elapsed, \
  255.                 #process.bursts[process.burst_index].actual_burst_time, str(runningProcess), runningProcess.tau[runningProcess.burst_index - 1], runningProcess.burst_elapsed, runningProcess.bursts[runningProcess.burst_index-1].actual_burst_time)
  256.             else:
  257.                 output += time_str +  "completed I/O; added to ready queue {:s}\n".format(state.getReadyQ())
  258.  
  259.             if state.running == '' and state.ready[0] == process:
  260.                 state.ready[0].context_switch = Config.instance._contextSwitchDuration//2 - 1
  261.  
  262.     else:
  263.         process.io_time -= 1
  264.  
  265.     return (output, True)
  266.  
  267.  
  268. def run_algorithm(alg, state, time, time_slice):
  269.     terminated_processes = list()
  270.     output = ""
  271.     state.processes.sort()
  272.     sorted_processes = state.processes
  273.     #print(sorted_processes)
  274.     for process in sorted_processes:
  275.         if(process.status == "ready"):
  276.             process.CPU_time += 1
  277.  
  278.     for process in sorted_processes:
  279.         state.processes_run.append(process)
  280.         time_str = "time {:d}ms: Process {:s} ".format(time, str(process))
  281.         # Preemption for RR
  282.         if process.context_switch != -1:
  283.             returnTuple = handle_context_switch(alg, time, time_str, state, process, output)
  284.            
  285.             # If there's anything to append to output, do so
  286.             if returnTuple[0] != None:
  287.                 output += returnTuple[0]
  288.                    
  289.             # If context switch ongoing, then continue
  290.             if returnTuple[1]:
  291.                 continue
  292.     state.processes_run.clear()
  293.  
  294.     for process in sorted_processes:
  295.         state.processes_run.append(process)
  296.         if process.context_switch <= 0:
  297.             time_str = "time {:d}ms: Process {:s} ".format(time, str(process))
  298.             # Do a CPU Burst/Set up IO Burst
  299.             if process.burst_time != -1:
  300.                 if(time > 678 and time < 685):
  301.                     print("burst", process.burst_time)
  302.                 returnTuple = do_burst(alg, time, time_str, time_slice, state, process, output, terminated_processes)
  303.  
  304.                 if returnTuple[0] != None:
  305.                     output += returnTuple[0]
  306.  
  307.                 if returnTuple[1]:
  308.                     continue
  309.     state.processes_run.clear()
  310.  
  311.     for process in sorted_processes:
  312.         state.processes_run.append(process)
  313.         if process.context_switch <= 0:
  314.             time_str = "time {:d}ms: Process {:s} ".format(time, str(process))
  315.             # Do an IO Burst
  316.             if process.io_time != -1:
  317.                 output = do_IO_burst(alg, time, time_str, state, process, output)[0]
  318.                 continue
  319.     state.processes_run.clear()
  320.  
  321.     for process in sorted_processes:
  322.         state.processes_run.append(process)
  323.         time_str = "time {:d}ms: Process {:s} ".format(time, str(process))
  324.         # Process arrival
  325.         if process.arrival_time == time:
  326.             output += accept_new_process(alg, time, time_str, state, process, output)
  327.     state.processes_run.clear()
  328.  
  329.     for process in terminated_processes:
  330.         state.remove_process(process)
  331.     return output
  332.  
  333.  
  334. def RR(state, time, time_slice):
  335.     return run_algorithm("RR", state, time, time_slice)
  336.  
  337. def FCFS(state, time):
  338.     return run_algorithm("FCFS", state, time, 1000000)
  339.  
  340. def SJF(state, time):
  341.     return run_algorithm("SJF", state, time, -999999)
  342.  
  343. def SRT(state, time):
  344.     return run_algorithm("SRT", state, time, -999999)
  345.  
  346.  
  347. def wrapperAlgo(processes, header, tHeader):
  348.     FCFS_state = State(deepcopy(processes))
  349.     SJF_state = State(deepcopy(processes))
  350.     SRT_state = State(deepcopy(processes))
  351.     RR_state = State(deepcopy(processes))
  352.     time = 0
  353.     FCFS_output = header + "time {:d}ms: Simulator started for FCFS {:s}\n".format(time,FCFS_state.getReadyQ())
  354.     SJF_output = tHeader + "time {:d}ms: Simulator started for SJF {:s}\n".format(time,SJF_state.getReadyQ())
  355.     SRT_output = tHeader + "time {:d}ms: Simulator started for SRT {:s}\n".format(time,SRT_state.getReadyQ())
  356.     RR_output = header + "time {:d}ms: Simulator started for RR {:s}\n".format(time,RR_state.getReadyQ())
  357.     #while len(FCFS_state) > 0 and len(SJF_state) > 0 and len(SRT_state) > 0 and len(RR_state) > 0:
  358.  
  359.     while len(FCFS_state) > 0 and len(RR_state) > 0 and time != 50000:
  360.         if time == 7425:
  361.             x = "yes"
  362.         FCFS_output += FCFS(FCFS_state, time)
  363.         #SJF_output += SJF(SJF_state, time)
  364.         #SRT_output += SRT(SRT_state, time)
  365.         #RR_output += RR(RR_state, time, Config.instance._timeSliceRR)
  366.         time += 1
  367.        
  368.     time+=1
  369.     RR_output += "time {:d}ms: Simulator ended for RR {:s}\n".format(time,RR_state.getReadyQ())
  370.     FCFS_output += "time {:d}ms: Simulator ended for FCFS {:s}\n".format(time,FCFS_state.getReadyQ())
  371.     SRT_output += "time {:d}ms: Simulator ended for SRT {:s}\n".format(time,SRT_state.getReadyQ())
  372.     SJF_output += "time {:d}ms: Simulator ended for SJF {:s}\n".format(time,SJF_state.getReadyQ())
  373.    
  374.     print(FCFS_output)
  375.     print(SJF_output)
  376.     print(SRT_output)
  377.     print(RR_output)
  378.  
  379.  
  380. if __name__ == "__main__":
  381.     # Instantiate a singleton Config with unpacked sys.argv, and
  382.     # prevent python/python3 from being considered an argument
  383.     if sys.argv[0] in ["python", "python3"]:
  384.         Config(*sys.argv[2:])
  385.     else:
  386.         Config(*sys.argv[1:])
  387.    
  388.     # Debug print config
  389.     # print(Config.instance)
  390.     processes = initialize_processes()
  391.     header = ""
  392.     tHeader = ""
  393.     for p in processes:
  394.         header +=  "Process {:s} [NEW] (arrival time {:d} ms) {:d} CPU bursts\n".format(str(p),p.arrival_time,p.n_bursts)
  395.         tHeader += "Process {:s} [NEW] (arrival time {:d} ms) {:d} CPU bursts (tau {:.0f}ms)\n".format(str(p),p.arrival_time,p.n_bursts,1/Config.instance._lambdaValue)
  396.        
  397.     wrapperAlgo(processes, header, tHeader)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top