PD2.py 5.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 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 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184
# coding=utf-8

from simso.core import Scheduler, Timer
from math import ceil


def rounded_wcet(job, q=None):
    return rounded_wcet_cycles(job, q) / job.sim.cycles_per_ms


def rounded_wcet_cycles(job, q=None):
    if q is None:
        q = PD2.quantum
    wcet_cycles = job.wcet * job.sim.cycles_per_ms
    if wcet_cycles % q:
        return wcet_cycles + q - (wcet_cycles % q)
    else:
        return wcet_cycles


class VirtualJob(object):
    """
    A Virtual Job contains the list of the pseudo jobs for an actual job.
    """
    def __init__(self, job):
        self.job = job
        self.pseudo_jobs = []
        self.cur = 0
        seq = 0

        # Create pseudo jobs:
        while seq * PD2.quantum <= job.wcet * job.sim.cycles_per_ms:
            self.pseudo_jobs.append(PseudoJob(job, seq + 1))
            seq += 1

    def get_next_job(self):
        if self.cur < len(self.pseudo_jobs) - 1:
            self.cur += 1
            job = self.pseudo_jobs[self.cur]
            return job

    def get_current_job(self):
        if self.cur < len(self.pseudo_jobs):
            return self.pseudo_jobs[self.cur]


class PseudoJob(object):
    def __init__(self, job, seq):
        self.job = job
        self.release_date = int(job.deadline * (seq - 1) / rounded_wcet(job)
                                ) * PD2.quantum
        self.deadline = int(ceil(job.deadline * seq / rounded_wcet(job))
                            ) * PD2.quantum
        self.seq = seq
        self.succ_bit = PseudoJob.succ_bit(job, seq)
        if rounded_wcet(job) / job.deadline < 0.5:
            self.group_deadline = 0
        else:
            j = seq + 1
            while (j * PD2.quantum <= rounded_wcet_cycles(job) and
                    PseudoJob.succ_bit(job, j - 1) == 1 and
                    PseudoJob.win_size(job, j) == 2):
                # while the window size is 2 and succ_bit of the prev is 1
                j += 1
            self.group_deadline = int(ceil(
                job.deadline * (j - 1) / rounded_wcet(job)
                * job.sim.cycles_per_ms))

    @property
    def absolute_releasedate(self):
        return self.release_date + \
            self.job.activation_date * self.job.sim.cycles_per_ms

    def cmp_key(self):
        # Si le premier parametre est identique, il regarde le second, etc.
        cycles_per_ms = self.job.sim.cycles_per_ms
        return (self.deadline + self.job.activation_date * cycles_per_ms,
                -self.succ_bit,
                -(self.job.activation_date + self.group_deadline))

    @staticmethod
    def succ_bit(job, seq):
        return int(ceil(seq * job.deadline / rounded_wcet(job))) \
            - int(seq * job.deadline / rounded_wcet(job))

    @staticmethod
    def win_size(job, seq):
        return int(ceil(seq * job.deadline / rounded_wcet(job))) \
            - int((seq - 1) * job.deadline / rounded_wcet(job))


class PD2(Scheduler):
    quantum = 100000  # cycles

    def init(self):
        self.ready_list = []
        self.timers = []
        self.terminate_timers = []
        self.waiting_schedule = False
        self.running_vjobs = []

        # PD2.quantum = 1000000
        # while not self.is_schedulable() and PD2.quantum > 1000:
        #     PD2.quantum /= 2
            
        PD2.quantum = self.sim.cycles_per_ms // 10

        self.timer = Timer(
            self.sim, PD2.reschedule, (self, ), PD2.quantum,
            cpu=self.processors[0], in_ms=False, one_shot=False)
        self.timer.start()

    def is_schedulable(self, q=None):
        load = 0.0
        cycles_per_ms = self.sim.cycles_per_ms
        for task in self.task_list:
            wcet = rounded_wcet_cycles(task, q)
            load += wcet / task.period
            if wcet > task.period * cycles_per_ms \
                    or load > len(self.processors) * cycles_per_ms:
                return False
        return True

    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 virtual_terminate(self, virtual_job):
        pjob = virtual_job.get_next_job()
        if not pjob or not virtual_job.job.is_active():
            self.ready_list.remove(virtual_job)

    def on_activate(self, job):
        virtual_job = VirtualJob(job)
        self.ready_list.append(virtual_job)

        if self.sim.now() == 0:
            self.reschedule()

    def schedule(self, cpu):
        self.waiting_schedule = False

        decisions = []

        for vjob in self.running_vjobs:
            self.virtual_terminate(vjob)

        vjobs = [vjob for vjob in self.ready_list if vjob.job.is_active() and
                 self.sim.now() >= vjob.get_current_job().absolute_releasedate]

        self.running_vjobs = sorted(
            vjobs,
            key=lambda x: x.get_current_job().cmp_key()
        )[:len(self.processors)]

        selected_jobs = [vjob.job for vjob in self.running_vjobs]
        remaining_jobs = selected_jobs[:]
        available_procs = []

        # Remove from the list of remaining jobs the jobs that already runs.
        for proc in self.processors:
            if proc.running in selected_jobs:
                # This processor keeps running the same job.
                remaining_jobs.remove(proc.running)
            else:
                # This processor is not running a selected job.
                available_procs.append(proc)

        # Jobs not currently running
        for vjob in self.running_vjobs:
            if vjob.job in remaining_jobs:
                decisions.append((vjob.job, available_procs.pop()))

        # Unused processors
        for proc in available_procs:
            decisions.append((None, proc))

        return decisions