Skip to content

Instantly share code, notes, and snippets.

@ericpauley
Created June 2, 2013 05:49
Show Gist options
  • Save ericpauley/5692748 to your computer and use it in GitHub Desktop.
Save ericpauley/5692748 to your computer and use it in GitHub Desktop.
A script that calculate process scheduling in a theoretical infinitely powerful computer.
import itertools
from decimal import Decimal
class Runtime:
def __init__(self, proc, start, end):
self.proc = proc
self.start = start
self.end = end
def __repr__(self):
return "From %s to %s" % (self.start, self.end)
@property
def length(self):
return self.end-self.start
class Process:
def __init__(self, pk, start, end, units):
self.pk = pk
self.start = start
self.end = end
self.units = units
self.runtimes = [Runtime(self, start, end)]
@property
def rate(self):
return (self.units / self.runtime) if self.runtime != 0 else Decimal("inf")
@property
def runtime(self):
return sum(runtime.length for runtime in self.runtimes)
def __repr__(self):
return "%d units of work between %ds and %ds (%s, %s)" % (self.units, self.start, self.end, self.rate, self.runtime)
class ProcList(list):
def get_conflict(self):
times = [item for proc in self for item in proc.runtimes]
ends = sorted(list(set([item.start for item in times]+[item.end for item in times])))
for i in range(len(ends)-1):
start = ends[i]
end = ends[i+1]
conflicts = [runtime for runtime in times if runtime.start < end and runtime.end > start]
if len(conflicts)>1:
return (start, end, conflicts)
def sanitize(self):
for proc in self:
proc.runtimes = [runtime for runtime in proc.runtimes if runtime.length != 0]
while True:
for r1 in proc.runtimes:
for r2 in proc.runtimes:
if r1.end == r2.start:
proc.runtimes.remove(r1)
proc.runtimes.remove(r2)
proc.runtimes.append(Runtime(proc, r1.start, r2.end))
continue
break
def balance(self):
runtimes = sorted([item for proc in self for item in proc.runtimes], key = lambda runtime:runtime.start)
changed = True
for i in range(100):
changed = False
for i in range(len(runtimes)-1):
first = runtimes[i]
second = runtimes[i + 1]
if first.proc.rate > second.proc.rate:
while first.proc.rate > second.proc.rate and first.end < first.proc.end and second.length > 0:
changed = True
first.end += Decimal(".01")
second.start += Decimal(".01")
else:
while first.proc.rate < second.proc.rate and second.start > second.proc.start and first.length > 0:
changed = True
first.end -= Decimal(".01")
second.start -= Decimal(".01")
def resolve(self):
while True:
conflict = self.get_conflict()
if conflict is None:
break
runtimes = []
for runtime in conflict[2]:
proc = runtime.proc
if runtime.end > conflict[1]:
proc.runtimes.append(Runtime(proc, conflict[1], runtime.end))
if runtime.start < conflict[0]:
proc.runtimes.append(Runtime(proc, runtime.start, conflict[0]))
proc.runtimes.remove(runtime)
test = Runtime(proc, conflict[0], conflict[0])
proc.runtimes.append(test)
runtimes.append(test)
for i in range(int(conflict[0]*100), int(conflict[1]*100)):
runtimes = sorted(runtimes, reverse=True, key=lambda runtime:runtime.proc.rate)
runtimes[0].end += Decimal(".01")
runtimes = sorted(runtimes, key=lambda runtime:runtime.proc.pk)
start = 0
for runtime in runtimes:
runtime.start += start
runtime.end += start
start += runtime.length
for proc in self:
proc.runtimes = [runtime for runtime in proc.runtimes if runtime.length != 0]
if __name__ == '__main__':
procs = ProcList()
#Load up the test case
pk = 1
while True:
i = raw_input()
if not i:
break
start, end, units = (Decimal(x) for x in i.split())
procs.append(Process(pk, start, end, units))
pk += 1
procs.resolve()
procs.sanitize()
procs.balance()
print [proc for proc in procs]
print [proc.runtimes for proc in procs]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment