[Python-ro] PROIECT PYTHON
Cornelia Silvia Micoroiu
corina.upb.fils at gmail.com
Mon May 18 21:12:15 CEST 2015
Buna seara. Am de facut un proiect in Python legat de Shortest First Job
Preemtive and non-Preemptive. Ideea este ca totul imi iese bine pana la
partea cu trasarea graficului in care sa arat cum se comporta CPU-ul. Si nu
ma descurc deloc. Am luat matplolib pip si alte biblioteci specifice
graficelor in python. Multumesc
Micoroiu Cornelia
-------------- partea urm��toare --------------
Un ata��ament HTML a fost eliminat
URL: <http://mail.python.org/pipermail/python-ro/attachments/20150518/5234b1be/attachment-0001.html>
-------------- partea urm��toare --------------
# cpu.py
class CPU(object):
def __init__(self, id, proc = None):
self.curr_proc = proc
self.id = id
self.finish_time = 0
self.utilization_time = 0
self.num_procs = 0
self.free = lambda: True if self.curr_proc is None else False
-------------- partea urm��toare --------------
# nonpreemptiveSJF.py
from processes import *
from cpu import *
from copy import deepcopy
import random
# Shortest Job First algorithm without preemption
def sjfNoPreemption(processes,num_cpus):
print "===== Running Non-preemptive SJF. ====="
cpus = [CPU(i) for i in xrange(num_cpus)]
ready_q = processes
ready_q.sort(key=lambda proc: proc.burst_times[0])
reentry_q = []
completed_procs = []
time = 0
complete = 0
num_bound_process = 0
ran_cpus = []
for item in processes:
if isinstance(item,BoundProcess):
num_bound_process+=1
while complete < num_bound_process:
# Find any free cpu's and give them a process to execute if possible
i = 0
while i < len(cpus):
if cpus[i].curr_proc is None and len(ready_q) > 0:
cpus[i].curr_proc = ready_q.pop(0)
i+=1
# Count the number of free cpu's
temp_count = 0
for c in cpus:
if c.curr_proc is None:
temp_count+=1
# Check if everything is in the reentry_q
if len(ready_q) == 0 and temp_count == num_cpus:
time = minArrivalTime(reentry_q)
i = 0
while i < len(reentry_q):
if reentry_q[i].reentry_time <= time:
temp = reentry_q.pop(i)
temp.wait_time += time-temp.reentry_time
ready_q.append(temp)
continue
i+=1
ready_q.sort(key=lambda proc: proc.burst_times[0])
continue
# Loop through the cpu's and execute each process for the cpus
ran_cpus = []
while len(cpus) > 0:
# Determine the shortest process in any of the cpu's
# The minTimeRemaining function actually pops the cpu from the list
cpu_min = minTimeRemaining(cpus)
if cpu_min.curr_proc is None:
ran_cpus.append(cpu_min)
continue
proc = deepcopy(cpu_min.curr_proc)
exec_time = proc.burst_times.pop(0)
cpu_min.curr_proc = None
cpu_min.utilization_time+=exec_time
# Update the time info
updateWaitTime(ready_q, exec_time)
updateTurnaroundTime(ready_q, exec_time)
updateBurstTimesInCPUs(cpus, exec_time)
proc.turnaround_time += exec_time
time += exec_time
# Print results
printBurstCompletion(proc,time)
# Add the current process to the reentry_q
if isinstance(proc,InteractiveProcess):
proc.num_bursts+=1
proc.updateTurnaround()
proc.updateWait()
proc.genNewBurstTime()
proc.reentry_time = random.randint(1000,4500)+time
reentry_q.append(proc)
else:
proc.updateTurnaround()
proc.updateWait()
if len(proc.burst_times) == 0:
complete += 1
completed_procs.append(proc)
else:
proc.reentry_time = random.randint(1000,4500)+time
reentry_q.append(proc)
i=0
while i < len(reentry_q):
if reentry_q[i].reentry_time <= time:
temp = reentry_q.pop(i)
temp.wait_time += time-temp.reentry_time
ready_q.append(temp)
continue
i+=1
ready_q.sort(key=lambda proc: proc.burst_times[0])
# Check if another process can be added to the current cpu
if len(ready_q) != 0:
cpu_min.curr_proc = ready_q.pop(0)
# No matter what append the cpu that just finished to the ran_cpus list
ran_cpus.append(cpu_min)
if complete < num_bound_process:
cpus = ran_cpus
if len(cpus) == 0:
break
if len(ready_q) == 0:
time = minArrivalTime(reentry_q)
i = 0
while i < len(reentry_q):
if reentry_q[i].reentry_time <= time:
temp = reentry_q.pop(i)
temp.wait_time += time-temp.reentry_time
ready_q.append(temp)
continue
i+=1
ready_q.sort(key=lambda proc: proc.burst_times[0])
for item in reentry_q:
completed_procs.append(item)
for item in ready_q:
completed_procs.append(item)
for c in ran_cpus:
if c.curr_proc is None:
continue
else:
completed_procs.append(c.curr_proc)
print "===== Non-preemptive SJF completed. ====="
completed_procs.sort(key=lambda proc: proc.id)
interactive_procs = [cpu.curr_proc for cpu in cpus if not cpu.curr_proc is None]
interactive_procs.extend([proc for proc in ready_q])
interactive_procs.extend([proc for proc in reentry_q])
all_cpus = cpus.extend(ran_cpus)
return completed_procs, interactive_procs, cpus, time
# Find the minimum amount of time remaining for all the cpu's. This assumes
# that the minimum exists.
def minTimeRemaining(cpus):
min_curr_burst = 10000
min_cpu = None
for cpu in cpus:
if cpu.curr_proc is None:
continue
else:
if cpu.curr_proc.burst_times[0] < min_curr_burst:
min_curr_burst = cpu.curr_proc.burst_times[0]
if min_curr_burst == 10000:
return cpus.pop(0)
# Find the process with the minimum burst time
for cpu in cpus:
if cpu.curr_proc is None:
continue
else:
if cpu.curr_proc.burst_times[0] == min_curr_burst:
# Find, remove from the list of cpu's, and return the cpu with
# the least amount of time remaining on it's current process
min_cpu = cpus.pop(cpus.index(cpu))
break
return min_cpu
# Find the minimum arrival time of the elements in the reentry_q
def minArrivalTime(reentry_q):
min_arrive = 0
for item in reentry_q:
if min_arrive == 0:
min_arrive = item.reentry_time
elif item.reentry_time < min_arrive:
min_arrive = item.reentry_time
return min_arrive
# Subtract the amount of time elapsed from the processes in the CPU's
# and update turnaround times for those processes
def updateBurstTimesInCPUs(cpus, elapsed_time):
for c in cpus:
if c.curr_proc is None:
continue
else:
if c.curr_proc.burst_times[0] < elapsed_time:
c.curr_proc.turnaround_time += c.curr_proc.burst_times[0]
c.curr_proc.burst_times[0] = 0
c.utilization_time+=c.curr_proc.burst_times[0]
else:
c.curr_proc.turnaround_time += elapsed_time
c.curr_proc.burst_times[0] -= elapsed_time
c.utilization_time+=elapsed_time
# Updates the turnaround_time of everything in the queue.
def updateTurnaroundTime(ready_q, t):
for proc in ready_q:
proc.turnaround_time += t
# Update the total wait time and wait time
def updateWaitTime(procs, wait_time):
for proc in procs:
proc.wait_time += wait_time
proc.updateWait()
# Print that the burst was completed
def printBurstCompletion(proc, t):
proc_type = "CPU-bound" if isinstance(proc, BoundProcess) else "Interactive"
print ("[time {0}ms] {1} process ID {2} CPU burst done "
"(turnaround time {3}ms, total wait time {4}ms)").format(t, proc_type,
proc.id, proc.turnaround_time, proc.total_wait_time)
-------------- partea urm��toare --------------
# Learn about API authentication here: https://plot.ly/python/getting-started
# Find your api_key here: https://plot.ly/settings/api
import plotly.plotly as py
#import plotly as py
from plotly.graph_objs import *
#from py.graph_objs import *
trace1 = Bar(
x=['giraffes', 'orangutans', 'monkeys'],
y=[20, 14, 23],
name='SF Zoo'
)
trace2 = Bar(
x=['giraffes', 'orangutans', 'monkeys'],
y=[12, 18, 29],
name='LA Zoo'
)
data = Data([trace1, trace2])
layout = Layout(
barmode='group'
)
fig = Figure(data=data, layout=layout)
plot_url = py.plot(fig, filename='grouped-bar')
-------------- partea urm��toare --------------
# preemptive_priority.py
from processes import *
from collections import deque
from cpu import CPU
import random
import sys
CONTEXT_SWITCH_TIME = 2
MAX_PRIORITY = 4
AGING_VALUE = 1200
MAX_TIME = 9999999
def preemptivePriority(procs, num_cpus, context_switch_time):
print "===== Running Preemptive Priority with FCFS. ====="
ready_q = deque(sorted(procs, reverse=True))
queue_order = len(ready_q)
completed_procs = []
time = 0
exec_time = 0
reentry_q = deque([])
curr_proc = None
cpu_list = [CPU(n) for n in xrange(1, num_cpus+1)]
for proc in ready_q:
printProcessEnteredReadyQueue(proc, time)
# Set the age times for each process in the ready queue
for proc in ready_q:
set_age_times(proc)
# Enter main while loop
while not terminateSimulation(ready_q, cpu_list, reentry_q):
# Sort the reentry and ready queues
reentry_q = deque(sorted(reentry_q))
ready_q = deque(sorted(ready_q, reverse=True))
# Find the CPU that will finish bursting next, including
# CPUs that have no processes running
next_available_cpu = cpu_list[0]
min_finish_time = cpu_list[0].finish_time
for cpu in cpu_list:
if cpu.finish_time < min_finish_time:
next_available_cpu = cpu
min_finish_time = cpu.finish_time
# This next block determines what action will be run next, be it filling
# an empty CPU, a process getting preemptive by another with a higher
# priority, a process aging, etc. It does not yet execute the action,
# it simply determines which action will come next
# Create a dummy next_action tuple
next_action = (MAX_TIME, "filler")
if len(ready_q) > 0:
proc = ready_q[0]
for cpu in cpu_list:
if not cpu.curr_proc:
# If there are processes in the ready queue and there is an
# empty CPU, then fill it without any time delay
next_action = (time, "fill-cpu", cpu, proc)
break
elif proc > cpu.curr_proc and proc.id != cpu.curr_proc.id:
# If there is a process in the ready queue that should preempt
# a process in the CPUs, then run the preemption without any
# time delay
next_action = (time, "preempt", cpu, proc)
elif cpu.finish_time < next_action[0]:
# If a process finishes bursting normally, then switch it out
# with a process from the ready queue after bursting
next_action = (cpu.finish_time, "switch", cpu, proc)
for proc in ready_q:
if len(proc.age_times) > 0 and proc.age_times[0] <= next_action[0]:
# If a process will age before anything else happens, then
# increment the priority of the process
next_action = (proc.age_times[0], "age", proc)
else:
# Determine the next CPU to finish bursting that is actually running
# a process burst
min_finish_time = MAX_TIME
next_running_cpu = None
for cpu in cpu_list:
if cpu.curr_proc and cpu.finish_time < min_finish_time:
min_finish_time = cpu.finish_time
next_running_cpu = cpu
if next_running_cpu and next_running_cpu.finish_time < next_action[0]:
# If there is a CPU running something and it will finish bursting before
# any other action, then have it end its burst
next_action = (next_running_cpu.finish_time, "burst-end", next_running_cpu)
if len(reentry_q) > 0:
if reentry_q[0][0] < next_action[0]:
# If a process will enter the ready queue before any other action, then
# add it to the ready queue
next_action = (reentry_q[0][0], "ready", reentry_q[0][1])
# For bookkeeping purposes, store the time before executing anything
# then increment the time appropriately
old_time = time
time = next_action[0]
if time < old_time:
time = old_time
# Update the turnaround and wait times of the two queues
updateTurnaroundTime(ready_q, time - old_time)
updateWaitTime(ready_q, time - old_time)
# If a burst ends without getting replaced
if next_action[1] == "burst-end":
# Context switch with a no-op
printContextSwitch(next_action[2].curr_proc, None, time)
time += context_switch_time
# Prepare the old process to be added to the reentry queue
proc = next_action[2].curr_proc
proc.burst_times.pop()
proc.num_bursts += 1
proc.total_turnaround_time += time - old_time
proc.turnaround_time += time - old_time
# If the old process was a bound process
if isinstance(proc, BoundProcess):
if len(proc.burst_times) > 0:
# If it has another burst then print the burst completion and
# update the correct values
printBurstCompletion(proc, time)
proc.updateTurnaround()
proc.updateWait()
# Append it back to the reentry queue
reentry_q.append((time + random.randint(1200,3200), proc))
else:
# If there are no more bursts left then print the termination
# and update the correct values
printProcessTermination(proc, time)
proc.updateTurnaround()
proc.updateWait()
# Append it to the list of completed processes
completed_procs.append(proc)
else:
# If the process is not a bound process it is interactive
# in which case update values and append it back onto the
# reentry queue
printBurstCompletion(proc, time)
proc.updateTurnaround()
proc.updateWait()
proc.burst_times.append(random.randint(20,200))
reentry_q.append((time + random.randint(1000,4500), proc))
# Update the time values in the CPUs and ready queue
for cpu in cpu_list:
if cpu.curr_proc:
cpu.utilization_time += time-old_time
cpu.curr_proc.turnaround_time += time-old_time
updateTurnaroundTime(ready_q, context_switch_time)
# Reset the CPU to a state without any processes running
next_action[2].curr_proc = None
next_action[2].finish_time = time
# If a process is to be preempted by one from the ready queue
elif next_action[1] == "preempt":
# Decrement the burst time of the old process accordingly
proc = next_action[2].curr_proc
proc.burst_times[-1] -= next_action[2].utilization_time
# Run the context switch
printContextSwitch(next_action[2].curr_proc, proc, time)
time += context_switch_time
updateTurnaroundTime(ready_q, context_switch_time)
# Prepare the process for entry back into the ready queue
proc.ready_time = time
set_age_times(proc)
# Replace the old process with the new one
printProcessEnteredReadyQueue(proc, time)
ready_q.append(proc)
new_proc = ready_q.popleft()
next_action[2].curr_proc = new_proc
next_action[2].finish_time = time + new_proc.burst_times[-1]
# Update the times appropriately
for cpu in cpu_list:
if cpu.curr_proc:
cpu.utilization_time += (time-old_time)
cpu.curr_proc.turnaround_time += time-old_time
# If a new process is to enter the ready queue
elif next_action[1] == "ready":
# Prepare the process to enter the ready queue and remove it
# from the reentry queue. Then add it to the ready queue
next_action[2].ready_time = time
set_age_times(next_action[2])
reentry_q.popleft()
printProcessEnteredReadyQueue(next_action[2], time)
ready_q.append(next_action[2])
# Update times appropriately
for cpu in cpu_list:
if cpu.curr_proc:
cpu.utilization_time += (time-old_time)
cpu.curr_proc.turnaround_time += time-old_time
# If a process ages
elif next_action[1] == "age":
# Decrement its priority
next_action[2].priority -= 1
# Remove its first age time and print the message
next_action[2].age_times.pop(0)
printProcessAged(next_action[2], time)
# Update times appropriately
for cpu in cpu_list:
if cpu.curr_proc:
cpu.utilization_time += (time-old_time)
cpu.curr_proc.turnaround_time += time-old_time
# If a process is added to an empty CPU
elif next_action[1] == "fill-cpu":
# Pop it from the ready queue and update the CPU's attributes
next_action[2].curr_proc = ready_q.popleft()
next_action[2].finish_time = time + next_action[2].curr_proc.burst_times[-1]
# If a process has finished bursting and must be switched out for another
# process
elif next_action[1] == "switch":
# Pop the next process from the ready queue
next_proc = ready_q.popleft()
printContextSwitch(next_action[2].curr_proc, next_proc, time)
time += context_switch_time
# Prepare the old process to get added back onto the reentry queue
proc = next_action[2].curr_proc
proc.burst_times.pop()
proc.num_bursts += 1
proc.total_turnaround_time += time - old_time
proc.turnaround_time += time - old_time
# If the old process was a bound process
if isinstance(proc, BoundProcess):
if len(proc.burst_times) > 0:
# If it has another burst then print the burst completion and
# update the correct values
printBurstCompletion(proc, time)
proc.updateTurnaround()
proc.updateWait()
# Append it back to the reentry queue
reentry_q.append((time + random.randint(1200,3200), proc))
else:
# If there are no more bursts left then print the termination
# and update the correct values
printProcessTermination(proc, time)
proc.updateTurnaround()
proc.updateWait()
# Append it to the list of completed processes
completed_procs.append(proc)
else:
# If the process is not a bound process it is interactive
# in which case update values and append it back onto the
# reentry queue
printBurstCompletion(proc, time)
proc.updateTurnaround()
proc.updateWait()
proc.burst_times.append(random.randint(20,200))
reentry_q.append((time + random.randint(1000,4500), proc))
# Update the time values in the CPUs and the ready queue
for cpu in cpu_list:
if cpu.curr_proc:
cpu.utilization_time += (time-old_time)
cpu.curr_proc.turnaround_time += time-old_time
updateTurnaroundTime(ready_q, context_switch_time)
# Replace the old process with the new one and update values
# accordingly
next_action[2].curr_proc = next_proc
next_action[2].finish_time = time + next_proc.burst_times[-1]
print "===== Preemptive Priority completed. ====="
interactive_procs = [cpu.curr_proc for cpu in cpu_list if not cpu.curr_proc is None]
interactive_procs.extend([proc[1] for proc in ready_q])
interactive_procs.extend([proc[1] for proc in reentry_q])
return completed_procs, interactive_procs, cpu_list, time
def set_age_times(proc):
proc.age_times = []
for i in range(1,proc.priority+1):
proc.age_times.append(proc.ready_time + i*AGING_VALUE)
# Updates the turnaround_time of everything in the queue.
def updateTurnaroundTime(ready_q, t):
for proc in ready_q:
proc.turnaround_time += t
# Updates the wait_time of everything in the queue.
def updateWaitTime(procs, wait_time):
for proc in procs:
proc.wait_time += wait_time
def printContextSwitch(proc_curr, proc_next, t):
if not proc_next:
print ("[time {0}ms] Context switch (swapping out process ID {1} "
"for None)").format(t, proc_curr.id)
else:
print ("[time {0}ms] Context switch (swapping out process ID {1} "
"for process ID {2})").format(t, proc_curr.id, proc_next.id)
def printBurstCompletion(proc, t):
proc_type = "CPU-bound" if isinstance(proc, BoundProcess) else "Interactive"
print ("[time {0}ms] {1} process ID {2} CPU burst done "
"(turnaround time {3}ms, total wait time {4}ms)").format(t, proc_type,
proc.id, proc.turnaround_time, proc.wait_time)
def printProcessTermination(proc, t):
proc_type = "CPU-bound" if isinstance(proc, BoundProcess) else "Interactive"
print ("[time {0}ms] {1} process ID {2} terminated (avg turnaround "
"time {3:.3f}ms, avg total wait time {4:.3f}ms)").format(t, proc_type,
proc.id, proc.avg_turnaround, proc.avg_wait)
def printProcessEnteredReadyQueue(proc, t):
proc_type = "CPU-bound" if isinstance(proc, BoundProcess) else "Interactive"
print ("[time {0}ms] {1} process ID {2} entered ready queue "
"(requires {3}ms CPU time; priority {4})").format(t, proc_type,
proc.id, proc.burst_times[-1], proc.priority)
def printProcessAged(proc, t):
proc_type = "CPU-bound" if isinstance(proc, BoundProcess) else "Interactive"
print ("[time {0}ms] Increased priority of {1} process ID {2}"
" to {3} due to aging").format(t, proc_type, proc.id, proc.priority)
# Checks for at least one BoundProcess in the ready queue, reentry queue, or CPU
# processes. If it finds one, then the simulation is not terminated.
def terminateSimulation(ready_q, cpu_list, reentry_q):
for x in ready_q:
if isinstance(x, BoundProcess):
return False
for x in cpu_list:
if isinstance(x.curr_proc, BoundProcess):
return False
for x in reentry_q:
if isinstance(x[1], BoundProcess):
return False
return True
-------------- partea urm��toare --------------
# preemptiveSJF.py
from processes import *
from cpu import *
from copy import deepcopy
import random
# Shortest Job First algorithm with preemption
def sjfPreemption(processes, num_cpus):
print "===== Running Preemptive SJF. ====="
num_processes = len(processes)
cpus = [CPU(i) for i in xrange(num_cpus)]
ready_q = processes
ready_q.sort(key=lambda proc: proc.burst_times[0])
reentry_q = []
completed_procs = []
time = 0
complete = 0
num_bound_process = 0
ran_cpus = []
for item in processes:
if isinstance(item,BoundProcess):
num_bound_process+=1
while complete < num_bound_process:
# Find any free cpu's and give them a process to execute if possible
i = 0
while i < len(cpus):
if cpus[i].curr_proc is None and len(ready_q) > 0:
cpus[i].curr_proc = ready_q.pop(0)
i+=1
# Count the number of free cpu's
temp_count = 0
for c in cpus:
if c.curr_proc is None:
temp_count+=1
# Check if everything is in the reentry_q
if len(ready_q) == 0 and temp_count == num_cpus:
time = minArrivalTime(reentry_q)
i = 0
while i < len(reentry_q):
if reentry_q[i].reentry_time <= time:
temp = reentry_q.pop(i)
temp.wait_time += time-temp.reentry_time
ready_q.append(temp)
continue
i+=1
ready_q.sort(key=lambda proc: proc.burst_times[0])
continue
# Loop through the cpu's and execute each process for the cpus
ran_cpus = []
while len(cpus) > 0:
# Determine the shortest process in any of the cpu's
# The minTimeRemaining function actually pops the cpu from the list
cpu_min = minTimeRemaining(cpus)
if cpu_min.curr_proc is None:
ran_cpus.append(cpu_min)
continue
if num_cpus < num_processes:
i = 0
while i < len(reentry_q):
if reentry_q[i].reentry_time < time+cpu_min.curr_proc.burst_times[0]:
if reentry_q[i].burst_times[0] < (time+cpu_min.curr_proc.burst_times[0]-reentry_q[i].burst_times[0]):
temp = reentry_q.pop(i)
cpu_min.curr_proc.burst_times[0]-=temp.reentry_time-time
cpu_min.utilization_time+=temp.reentry_time-time
updateBurstTimesInCPUs(cpus, temp.reentry_time-time)
for c in cpus:
if c.curr_proc is None:
continue
else:
c.curr_proc.turnaround_time += temp.reentry_time-time+2
updateTurnaroundTime(ready_q,temp.reentry_time-time+2)
updateWaitTime(ready_q,temp.reentry_time-time)
time+=temp.reentry_time-time+2
printContextSwitch(cpu_min.curr_proc,temp,time)
ready_q.append(cpu_min.curr_proc)
cpu_min.curr_proc = temp
break
i+=1
ready_q.sort(key=lambda proc: proc.burst_times[0])
proc = deepcopy(cpu_min.curr_proc)
exec_time = proc.burst_times.pop(0)
cpu_min.curr_proc = None
cpu_min.utilization_time+=exec_time
# Update the time info
updateWaitTime(ready_q, exec_time)
updateTurnaroundTime(ready_q, exec_time)
updateBurstTimesInCPUs(cpus, exec_time)
proc.turnaround_time += exec_time
time += exec_time
# Print results
printBurstCompletion(proc,time)
# Add the current process to the reentry_q
if isinstance(proc,InteractiveProcess):
proc.num_bursts+=1
proc.updateTurnaround()
proc.updateWait()
proc.genNewBurstTime()
proc.reentry_time = random.randint(1000,4500)+time
reentry_q.append(proc)
else:
proc.updateTurnaround()
proc.updateWait()
if len(proc.burst_times) == 0:
complete += 1
completed_procs.append(proc)
else:
proc.reentry_time = random.randint(1000,4500)+time
reentry_q.append(proc)
i=0
while i < len(reentry_q):
if reentry_q[i].reentry_time <= time:
temp = reentry_q.pop(i)
temp.wait_time += time-temp.reentry_time
ready_q.append(temp)
continue
i+=1
ready_q.sort(key=lambda proc: proc.burst_times[0])
if len(ready_q) != 0:
cpu_min.curr_proc = ready_q.pop(0)
# No matter what append the cpu that just finished to the ran_cpus list
ran_cpus.append(cpu_min)
if complete < num_bound_process:
cpus = ran_cpus
if len(cpus) == 0:
break
if len(ready_q) == 0:
time = minArrivalTime(reentry_q)
i = 0
while i < len(reentry_q):
if reentry_q[i].reentry_time <= time:
temp = reentry_q.pop(i)
temp.wait_time += time-temp.reentry_time
ready_q.append(temp)
continue
i+=1
ready_q.sort(key=lambda proc: proc.burst_times[0])
for item in reentry_q:
completed_procs.append(item)
for item in ready_q:
completed_procs.append(item)
for c in ran_cpus:
if c.curr_proc is None:
continue
else:
completed_procs.append(c.curr_proc)
print "===== Preemptive SJF completed. ====="
completed_procs.sort(key=lambda proc: proc.id)
interactive_procs = [cpu.curr_proc for cpu in cpus if not cpu.curr_proc is None]
interactive_procs.extend([proc for proc in ready_q])
interactive_procs.extend([proc for proc in reentry_q])
all_cpus = cpus.extend(ran_cpus)
return completed_procs, interactive_procs, cpus, time
# Find the minimum amount of time remaining for all the cpu's. This assumes
# that the minimum exists.
def minTimeRemaining(cpus):
min_curr_burst = 10000
min_cpu = None
for cpu in cpus:
if cpu.curr_proc is None:
continue
else:
if cpu.curr_proc.burst_times[0] < min_curr_burst:
min_curr_burst = cpu.curr_proc.burst_times[0]
if min_curr_burst == 10000:
return cpus.pop(0)
# Find the process with the minimum burst time
for cpu in cpus:
if cpu.curr_proc is None:
continue
else:
if cpu.curr_proc.burst_times[0] == min_curr_burst:
# Find, remove from the list of cpu's, and return the cpu with the
# least amount of time remaining on it's current process
min_cpu = cpus.pop(cpus.index(cpu))
break
return min_cpu
# Find the minimum arrival time of the elements in the reentry_q
def minArrivalTime(reentry_q):
min_arrive = 0
for item in reentry_q:
if min_arrive == 0:
min_arrive = item.reentry_time
elif item.reentry_time < min_arrive:
min_arrive = item.reentry_time
return min_arrive
# Subtract the amount of time elapsed from the processes in the cpu's
def updateBurstTimesInCPUs(cpus, elapsed_time):
for c in cpus:
if c.curr_proc is None:
continue
else:
if c.curr_proc.burst_times[0] < elapsed_time:
c.curr_proc.turnaround_time += c.curr_proc.burst_times[0]
c.curr_proc.burst_times[0] = 0
c.utilization_time+=c.curr_proc.burst_times[0]
else:
c.curr_proc.turnaround_time += elapsed_time
c.curr_proc.burst_times[0] -= elapsed_time
c.utilization_time+=elapsed_time
# Updates the turnaround_time of everything in the queue.
def updateTurnaroundTime(ready_q, t):
for proc in ready_q:
proc.turnaround_time += t
# Update the total wait time and wait time
def updateWaitTime(procs, wait_time):
for proc in procs:
proc.wait_time += wait_time
proc.updateWait()
# Print that there was a context switch when a process was preempted
def printContextSwitch(proc_curr, proc_next, t):
print ("[time {0}ms] Context switch (swapping out process ID {1} "
"for process ID {2})").format(t, proc_curr.id, proc_next.id)
# Print that the burst was completed
def printBurstCompletion(proc, t):
proc_type = "CPU-bound" if isinstance(proc, BoundProcess) else "Interactive"
print ("[time {0}ms] {1} process ID {2} CPU burst done "
"(turnaround time {3}ms, total wait time {4}ms)").format(t, proc_type,
proc.id, proc.turnaround_time, proc.total_wait_time)
-------------- partea urm��toare --------------
import random
class Process(object):
def __init__(self, id, priority = 0, queue_order = 0, ready_time = 0):
self.id = id
self.priority = priority
self.original_priority = priority
self.num_bursts = 0
# Sum of the burst times
self.burst_sum = 0
# time the process reenters the ready_q
self.reentry_time = 0
# time the process entered ready queue
self.ready_time = ready_time
# times at which the process will age
self.age_times = []
# wait_time is the wait time for one burst
self.wait_time = 0
self.total_wait_time = 0
# turnaround_time is the turnaround time for one burst
self.turnaround_time = 0
self.total_turnaround_time = 0
self.min_turnaround = 1000000000
self.max_turnaround = 0
self.avg_turnaround = 0
self.min_wait = 1000000000
self.max_wait = 0
self.avg_wait = 0
# queue_order is the position in the priority queue for FCFS
self.queue_order = queue_order
def __str__(self):
burst = None if len(self.burst_times) == 0 else self.burst_times[-1]
return "Process {0} with priority level {1}, current burst {2}".format(
self.id, self.priority, burst)
def __repr__(self):
burst = None if len(self.burst_times) == 0 else self.burst_times[-1]
return "Process {0}: priority {1}, current burst {2}".format(
self.id, self.priority, burst)
def __cmp__(self, other):
if self.priority == other.priority:
if self.queue_order < other.queue_order:
return 1
elif self.queue_order > other.queue_order:
return -1
else:
return 0
elif self.priority < other.priority:
return 1
else:
return -1
# Determine and update the min, max and avg turnaround times for the process.
def updateTurnaround(self):
self.total_turnaround_time += self.turnaround_time
if self.min_turnaround is None:
self.min_turnaround = self.turnaround_time
self.max_turnaround = self.turnaround_time
self.avg_turnaround = self.turnaround_time
elif self.turnaround_time < self.min_turnaround:
self.min_turnaround = self.turnaround_time
elif self.turnaround_time > self.max_turnaround:
self.max_turnaround = self.turnaround_time
if self.num_bursts > 0:
self.avg_turnaround = (self.avg_turnaround * (self.num_bursts-1) +
self.turnaround_time)/self.num_bursts
self.turnaround_time = 0
# Determine and update the min, max and avg wait times for the process.
def updateWait(self):
self.total_wait_time += self.wait_time
if self.min_wait is None:
self.min_wait = self.wait_time
self.max_wait = self.wait_time
self.avg_wait = self.wait_time
elif self.wait_time < self.min_wait:
self.min_wait = self.wait_time
elif self.wait_time > self.max_wait:
self.max_wait = self.wait_time
if self.num_bursts > 0:
self.avg_wait = (self.avg_wait * (self.num_bursts-1) +
self.wait_time)/self.num_bursts
self.wait_time = 0
class InteractiveProcess(Process):
def __init__(self, id, priority = 0, queue_order = 0):
Process.__init__(self, id, priority)
# make some random value (possibly generate randomly for every burst)
self.burst_times = [random.randint(20, 200)]
self.time_in_wait_q = None
self.total_burst_time = self.burst_times[0]
def genNewBurstTime(self):
if len(self.burst_times) == 0:
self.burst_times = [random.randint(20, 200)]
self.total_burst_time += self.burst_times[0]
else:
raise BurstError("The burst_times list is not empty but it should be.")
class BoundProcess(Process):
def __init__(self, id, bursts = 8, priority = 0, queue_order = 0):
Process.__init__(self, id, priority)
# make some random value (possibly generate randomly for every burst)
self.burst_times = [random.randint(200, 3000) for _ in xrange(bursts)]
self.total_burst_time = sum(self.burst_times)
self.num_bursts = bursts
class BurstError(Exception):
def __init__(self, value):
self.value = value
def __str__(self):
return __repr__(self.value)
-------------- partea urm��toare --------------
# round_robin.py
from cpu import CPU
from collections import deque
from copy import deepcopy
from processes import *
import random
import sys
def roundRobin(procs, num_cpus, t_slice, context_switch_time):
print "===== Running Round Robin with timeslice of {}ms =====".format(t_slice)
ready_q = deque(procs)
completed_procs = []
time = 0
exec_time = 0
reentry_q = deque([])
cpu_list = [CPU(n) for n in xrange(1, num_cpus + 1)]
num_bound_procs = len([proc for proc in procs if isinstance(proc,
BoundProcess)])
for proc in ready_q:
printProcessEnteredReadyQueue(proc, time)
# Start the Round Robin algorithm.
while len(completed_procs) < num_bound_procs:
# Sort the reentry queue by next process to reenter.
reentry_q = deque(sorted(reentry_q))
# Go through the reentry_q and pop anything with a reentry time greater than
# or equal to the current time, meaning it should reenter the ready queue.
while len(reentry_q) > 0 and reentry_q[0][0] <= time:
proc = reentry_q.popleft()[1]
ready_q.append(proc)
printProcessEnteredReadyQueue(proc, time)
# If the ready_q and all CPUs are empty fastforward to when the process will
# go into the ready_q
if len(ready_q) == 0 and allCPUsEmpty(cpu_list):
time = reentry_q[0][0]
cpu_list[0].curr_proc = reentry_q.popleft()[1]
cpu_list[0].finish_time = time + min(cpu_list[0].curr_proc
.burst_times[-1], t_slice)
cpu_list[0].utilization_time += cpu_list[0].finish_time - time
printProcessEnteredReadyQueue(cpu_list[0].curr_proc, time)
continue
# Refill the CPUs.
fillCPUs(cpu_list, ready_q, t_slice, time)
# Find the CPU with the process that will finish soonest.
filtered = [cpu for cpu in cpu_list if not (cpu.curr_proc is None)]
soonest_proc_cpu = min(filtered,
key=lambda x: (x.finish_time,
x.curr_proc.burst_times[-1]))
exec_time = soonest_proc_cpu.finish_time - time
updateWaitTime(ready_q, exec_time)
updateTurnaroundTime(ready_q, exec_time)
# Update the turnaround and burst times of every currently executing process
for cpu in cpu_list:
if cpu.curr_proc:
cpu.curr_proc.burst_times[-1] -= exec_time
cpu.curr_proc.turnaround_time += exec_time
time = soonest_proc_cpu.finish_time
# Check if the process is done with its burst.
if soonest_proc_cpu.curr_proc.burst_times[-1] <= 0:
soonest_proc_cpu.curr_proc.burst_times.pop()
# print " -->Added to reentry_q {}".format(soonest_proc_cpu.curr_proc)
# Check if the process is to be terminated.
if len(soonest_proc_cpu.curr_proc.burst_times) == 0 and isinstance(soonest_proc_cpu.curr_proc, BoundProcess):
handleTermination(soonest_proc_cpu, completed_procs, reentry_q, time)
# If not, then it needs to be added to the reentry_q
else:
addToReentryQ(soonest_proc_cpu, reentry_q, time)
# Otherwise the process is not done with its burst and goes back straight
# back into the ready_q
else:
# print " Added to ready_q {}".format(soonest_proc_cpu.curr_proc)
addToReadyQ(soonest_proc_cpu, ready_q, t_slice, context_switch_time, time)
print "===== Round Robin completed. ====="
interactive_procs = [cpu.curr_proc for cpu in cpu_list if not cpu.curr_proc is None]
interactive_procs.extend([proc[1] for proc in ready_q])
interactive_procs.extend([proc[1] for proc in reentry_q])
return completed_procs, interactive_procs, cpu_list, time
# printStuff(completed_procs, reentry_q, ready_q, cpu_list, time)
def handleTermination(cpu, completed_procs, reentry_q, time):
printBurstCompletion(cpu.curr_proc, time)
# The process is a BoundProcess
if isinstance(cpu.curr_proc, BoundProcess):
printProcessTermination(cpu.curr_proc, time)
completed_procs.append(cpu.curr_proc)
finishCPU(cpu)
# The process is an InteractiveProcess
else:
reentry_q.append((time + random.randint(1000, 4500), cpu.curr_proc))
cpu.curr_proc.genNewBurstTime()
finishCPU(cpu)
def addToReentryQ(cpu, reentry_q, time):
printBurstCompletion(cpu.curr_proc, time)
# The process is a BoundProcess
if isinstance(cpu.curr_proc, BoundProcess):
reentry_time = time + random.randint(1200, 3200)
reentry_q.append((reentry_time, cpu.curr_proc))
finishCPU(cpu)
# The process is an InteractiveProcess
else:
reentry_time = time + random.randint(1000, 4500)
reentry_q.append((reentry_time, cpu.curr_proc))
cpu.curr_proc.genNewBurstTime()
finishCPU(cpu)
def addToReadyQ(cpu, ready_q, t_slice, t_cs, time):
printProcessEnteredReadyQueue(cpu.curr_proc, time)
ready_q.append(cpu.curr_proc)
handleContextSwitch(cpu.curr_proc, ready_q[0], t_cs, time)
cpu.curr_proc = ready_q.popleft()
cpu.finish_time = time + min(cpu.curr_proc.burst_times[-1], t_slice)
# Handles a CPU and its process after the process is finished executing.
def finishCPU(cpu):
# These first 3 lines do not matter for InteractiveProcesses.
cpu.curr_proc.num_bursts += 1
cpu.curr_proc.updateTurnaround()
cpu.curr_proc.updateWait()
# These last 2 lines are important for any Process.
cpu.curr_proc = None
cpu.finish_time = None
# Fill the CPUs with processes
def fillCPUs(cpus, ready_q, t_slice, time,):
for cpu in cpus:
if cpu.curr_proc is None and len(ready_q) != 0:
cpu.curr_proc = ready_q.popleft()
cpu.finish_time = time + min(cpu.curr_proc.burst_times[-1], t_slice)
cpu.utilization_time += cpu.finish_time - time
def printStuff(comp, reentry, ready, cpus, time):
print "\ntime: {}".format(time)
print "-> completed"
for proc in comp:
print proc
print "-> reentry_q"
for proc in reentry:
print proc
print "-> ready_q"
for proc in ready:
print proc
print "-> CPUs"
for cpu in cpus:
print cpu.curr_proc
print
def allCPUsEmpty(cpus):
for cpu in cpus:
if not cpu.curr_proc is None:
return False
return True
# Updates the turnaround_time of everything in the queue.
def updateTurnaroundTime(ready_q, t):
for proc in ready_q:
proc.turnaround_time += t
# Updates the wait_time of everything in the queue.
def updateWaitTime(procs, wait_time):
for proc in procs:
proc.wait_time += wait_time
def handleContextSwitch(proc_curr, proc_next, t_cs, t):
proc_curr.turnaround_time += t_cs/2
proc_next.turnaround_time += t_cs/2
print ("[time {0}ms] Context switch (swapping out process ID {1} "
"for process ID {2})").format(t, proc_curr.id, proc_next.id)
def printBurstCompletion(proc, t):
proc_type = "CPU-bound" if isinstance(proc, BoundProcess) else "Interactive"
print ("[time {0}ms] {1} process ID {2} CPU burst done "
"(turnaround time {3}ms, total wait time {4}ms)").format(t, proc_type,
proc.id, proc.turnaround_time, proc.total_wait_time)
def printProcessTermination(proc, t):
proc_type = "CPU-bound" if isinstance(proc, BoundProcess) else "Interactive"
print ("[time {0}ms] {1} process ID {2} terminated (avg turnaround time "
"{3:.3f}ms, avg total wait time {4:.3f}ms)").format(
t, proc_type, proc.id, proc.avg_turnaround, proc.avg_wait)
def printProcessEnteredReadyQueue(proc, t):
proc_type = "CPU-bound" if isinstance(proc, BoundProcess) else "Interactive"
print ("[time {0}ms] {1} process ID {2} entered ready queue "
"(requires {3}ms CPU time; priority {4})").format(t, proc_type,
proc.id, proc.burst_times[-1], proc.priority)
-------------- partea urm��toare --------------
# simulation.py
from collections import deque
from copy import deepcopy
from cpu import CPU
import getopt
from preemptive_priority import preemptivePriority
from processes import *
import random
from round_robin import roundRobin
import sys
from nonpreemptiveSJF import sjfNoPreemption
from preemptiveSJF import sjfPreemption
CONTEXT_SWITCH_TIME = 2
MAX_PRIORITY = 4
NUM_CPUS = 4
NUM_PROCS = 12
TIME_SLICE = 100
# Command line parsing.
try:
options, remainder = getopt.getopt(sys.argv[1:], '',
['context_switch=',
'num_cpus=',
'num_procs=',
'time_slice='])
except getopt.GetoptError as err:
print str(err)
sys.exit(2)
for opt, arg in options:
if opt == '--context_switch':
CONTEXT_SWITCH_TIME = arg
elif opt == 'num_cpus':
NUM_CPUS = arg
elif opt == 'num_procs':
NUM_PROCS = arg
elif opt == 'time_slice':
TIME_SLICE = arg
def main():
procs = generateProcessList(NUM_PROCS)
procs_preemp_sjf = deepcopy(procs)
procs_nopreemp_sjf = deepcopy(procs)
procs_rr = deepcopy(procs)
procs_pp = deepcopy(procs)
sjfp_complete, sjfp_interactive, sjfp_cpus, sjfp_t = sjfPreemption(
procs_preemp_sjf, NUM_CPUS)
print
printFinalStats(sjfp_complete, sjfp_interactive, sjfp_cpus, sjfp_t)
print
sjfnp_complete, sjfnp_interactive, sjfnp_cpus, sjfnp_t = sjfNoPreemption(
procs_nopreemp_sjf, NUM_CPUS)
print
printFinalStats(sjfnp_complete, sjfnp_interactive, sjfnp_cpus, sjfnp_t)
print
rr_complete, rr_interactive, rr_cpus, rr_t = roundRobin(
procs_rr, NUM_CPUS, TIME_SLICE, CONTEXT_SWITCH_TIME)
print
printFinalStats(rr_complete, rr_interactive, rr_cpus, rr_t)
print
pp_complete, pp_interactive, pp_cpus, pp_t = preemptivePriority(
procs_pp, NUM_CPUS, CONTEXT_SWITCH_TIME)
print
printFinalStats(pp_complete, pp_interactive, pp_cpus, pp_t)
print
# Print the final analysis stats for each algorithm
def printFinalStats(completed, interactive, cpus, time):
min_turnaround = min(completed, key=lambda x: x.min_turnaround).min_turnaround
max_turnaround = max(completed, key=lambda x: x.max_turnaround).max_turnaround
avg_turnaround = sum([proc.avg_turnaround for proc in completed])/len(completed)
min_wait = min(completed, key=lambda x: x.min_wait).min_wait
max_wait = max(completed, key=lambda x: x.max_wait).max_wait
avg_wait = sum([proc.avg_wait for proc in completed])/len(completed)
avg_utilization = sum([(cpu.utilization_time*1.0) for cpu in cpus])/time
print "Turnaround time: min {0} ms; avg {1:.3f} ms; max {2} ms".format(
min_turnaround, avg_turnaround, max_turnaround)
print "Total wait time: min {0} ms; avg {1:.3f} ms; max {2} ms".format(
min_wait, avg_wait, max_wait)
print "Average CPU utilization: {0:.3f}%".format(
(avg_utilization*100.0)/len(cpus))
# Compile a list of all the processes and sort them by pid.
all_procs = completed
all_procs.extend(interactive)
all_procs = list(set(all_procs))
all_procs.sort(key= lambda x: x.id)
print "Average CPU utilization per process:"
for proc in all_procs:
print " process ID {0}: {1:.3f}%".format(proc.id,
(proc.total_burst_time*100.0)/(proc.total_turnaround_time))
# Generate a random list of prioritized processes and print that they've been
# added to the ready queue
def generateProcessList(n):
procs = []
queue_order = 0
procs.append(BoundProcess(1, priority=random.randint(0, MAX_PRIORITY),
queue_order=queue_order))
for id in xrange(2, n+1):
queue_order += 1
rand = random.random()
priority = random.randint(0,MAX_PRIORITY);
if(rand < 0.8):
procs.append(InteractiveProcess(id, priority=priority,
queue_order=queue_order))
else:
procs.append(BoundProcess(id, priority=priority,
queue_order=queue_order))
queue_order += 1
return procs
if __name__ == '__main__':
main()
More information about the Python-ro
mailing list