BF.py 7.4 KB
Newer Older
1 2 3 4
"""
Implementation of the BF algorithm.
"""
from simso.core import Scheduler, Timer
5
from fractions import Fraction
6 7 8 9 10 11 12 13


class BF(Scheduler):
    def init(self):
        self.t_f = 0
        self.waiting_schedule = False
        self.allocations = []
        self.timers = {}
14 15
        self.rw = {t.identifier: 0 for t in self.task_list}
        self.pw = {}
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

    def reschedule(self, cpu=None):
        """
        Ask for a scheduling decision. Don't call if not necessary.
        """
        if not self.waiting_schedule:
            if cpu is None:
                cpu = self.processors[0]
            cpu.resched()
            self.waiting_schedule = True

    def on_activate(self, job):
        self.reschedule()

    def alpha_plus_one(self, job):
        deadlines = sorted([x.job.absolute_deadline for x in self.task_list])
        bk2 = deadlines[1]
        bk1 = deadlines[0]
        ui = job.wcet / job.deadline
        val = bk2 * ui - int(bk1 * ui) - bk2 + bk1
        if val == 0:
            return 0
        if val > 0:
            return 1
        return -1

    def uf_plus_one(self, job):
        bk1 = min([x.job.absolute_deadline for x in self.task_list])
        ui = job.wcet / job.deadline
        return (1. - (bk1 * ui - int(bk1 * ui))) / ui

    def nuf_plus_one(self, job):
        bk1 = min([x.job.absolute_deadline for x in self.task_list])
        ui = 1 - (job.wcet / job.deadline)
        return (1. - (bk1 * ui - int(bk1 * ui))) / ui

    def compare(self, job_i, job_j):
        ai = self.alpha_plus_one(job_i)
        aj = self.alpha_plus_one(job_j)
        if ai > aj:
            return -1
        elif ai < aj:
            return 1
59
        elif ai == 0 == aj:
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
            return -1
        elif ai == -1:
            if self.uf_plus_one(job_i) > self.uf_plus_one(job_j):
                return 1
            else:
                return -1
        else:
            if self.nuf_plus_one(job_i) >= self.nuf_plus_one(job_j):
                return -1
            else:
                return 1

    def init_interval(self):
        """
        Determine the end of the interval and compute allocation of the jobs
        to the processors using the McNaughton algorithm.
        """
        self.allocations = [[0, []] for _ in self.processors]
        self.t_f = int(min([x.job.absolute_deadline for x in self.task_list])
                       * self.sim.cycles_per_ms)
        # Duration that can be allocated for each processor.
        w = int(self.t_f - self.sim.now())
82 83
        available = w * len(self.processors)

84 85 86 87
        p = 0  # Processor id.
        mand = {}
        eligible = []

88 89 90
        print("{:#^60}".format(
            " Scheduling Interval [{},{}) ".format(self.sim.now()/self.sim.cycles_per_ms,
                self.t_f/self.sim.cycles_per_ms)))
91
        for task in self.task_list:
92 93 94
            if not task.job.is_active():
                self.rw[task.identifier]=0
                self.pw[task.identifier]=0
95 96
                continue

97
            rw = self.rw[task.identifier]
98 99 100
            m_pure = ((Fraction(rw) + Fraction(w * task.job.wcet)
                       / Fraction(task.job.period))
                      / Fraction(self.sim.cycles_per_ms))
101 102 103 104
            m = int(m_pure)
            self.pw[task.identifier] = m_pure-m
            mand[task.identifier] = max(0, m*self.sim.cycles_per_ms)

105 106 107 108
#            print("rw: {:>4}".format(rw))
#            print("{}:, w: {},  m_pure: {:>4}, m: {:>2}, pw: {:>4}, mand: {}".format(
#                task.name, w/self.sim.cycles_per_ms, m_pure, m,
#                self.pw[task.identifier], mand[task.identifier]))
109

110
            available -= mand[task.identifier]
111
            if mand[task.identifier] < w and  self.pw[task.identifier] > 0:
112 113
                eligible.append(task)

114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
            self.rw[task.identifier] = self.pw[task.identifier]*self.sim.cycles_per_ms

        print("{:#^60}".format(" Done "))

        while available >= self.sim.cycles_per_ms and eligible:
            task_m = eligible[0]
            for task_e in eligible[1:]:
                result = self.compare(task_m.job, task_e.job)

                if result == -1:
                    pass
                elif result == 1:
                    task_m = task_e
                else:
                    print("Warning: Couldn't find task for optional unit!")

            mand[task_m.identifier] += self.sim.cycles_per_ms
            available -= self.sim.cycles_per_ms
            self.rw[task_m.identifier] -= self.sim.cycles_per_ms
            eligible.remove(task_m)
134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161

        for task in self.task_list:
            # The "fair" duration for this job on that interval. Rounded to the
            # upper integer to avoid durations that are not multiples of
            # cycles.
            job = task.job
            if not job.is_active():
                continue
            duration = mand[task.identifier]
            if self.allocations[p][0] + duration <= w:
                self.allocations[p][1].append((job, duration))
                self.allocations[p][0] += duration
            else:
                # Add first part to the end of the current processor p:
                duration1 = w - self.allocations[p][0]
                if duration1 > 0:
                    self.allocations[p][1].append((job, duration1))
                    self.allocations[p][0] = w

                if p + 1 < len(self.processors):
                    # Add the second part:
                    duration2 = duration - duration1
                    self.allocations[p + 1][1].append((job, duration2))
                    self.allocations[p + 1][0] += duration2
                else:
                    # Because every durations are rounded to the upper value,
                    # the last job may have not enough space left.
                    # This could probably be improved.
162 163
                    print("Warning: didn't allowed enough time to %s (%d)." %
                          (task.name, duration - duration1))
164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213
                    break

                p += 1

        for allocation in self.allocations:
            if allocation[0] < w:
                allocation[1].append((None, w - allocation[0]))

    def end_event(self, z, job):
        """
        Called when a job's budget has expired.
        """
        del self.timers[job]
        l = self.allocations[z][1]
        if l and l[0][0] is job:
            l.pop(0)
        self.reschedule(self.processors[z])

    def schedule(self, cpu):
        """
        Schedule main method.
        """
        self.waiting_schedule = False
        # At the end of the interval:
        if self.sim.now() >= self.t_f:
            self.init_interval()

            # Stop current timers.
            for job, timer in self.timers.items():
                timer.stop()
            self.timers = {}

        # Set timers to stop the jobs that will run.
        for z, proc in enumerate(self.processors):
            l = self.allocations[z][1]
            if l and l[0][0] not in self.timers:
                timer = Timer(self.sim, BF.end_event,
                              (self, z, l[0][0]), l[0][1],
                              cpu=proc, in_ms=False)
                timer.start()
                self.timers[l[0][0]] = timer

        # Schedule the activated tasks on each processor.
        decisions = []
        for z, proc in enumerate(self.processors):
            l = self.allocations[z][1]
            if not l[0][0] or l[0][0].is_active():
                decisions.append((l[0][0] if l else None, proc))

        return decisions