PriD.py 2.06 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12
"""
Implementation of the PriD scheduler as introduced by Goossens et al. in
Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors.
"""
from simso.core import Scheduler
from math import ceil


class PriD(Scheduler):
    """EDF(k) scheduler"""
    def init(self):
        self.ready_list = []
13
        self.km1first = []
14 15 16 17 18

        tasks = sorted(self.task_list, key=lambda x: -x.wcet / x.period)
        kmin = 1
        mmin = None
        u = sum(x.wcet / x.period for x in tasks)
19
        for km1, task in enumerate(tasks):
20
            u -= task.wcet / task.period
21
            m = km1 + ceil(u / (1 - task.wcet / task.period))
22
            if mmin is None or mmin > m:
23
                kmin = km1 + 1
24 25
                mmin = m

26 27
        # The k-1 first tasks are given the highest priority.
        self.km1first = tasks[:kmin - 1]
28 29

    def on_activate(self, job):
30
        if job.task in self.km1first:
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
            job.priority = 0
        else:
            job.priority = job.absolute_deadline
        self.ready_list.append(job)
        job.cpu.resched()

    def on_terminated(self, job):
        if job in self.ready_list:
            self.ready_list.remove(job)
        else:
            job.cpu.resched()

    def schedule(self, cpu):
        if self.ready_list:
            # Key explanations:
            # First the free processors
            # Among the others, get the one with the greatest deadline
            # If equal, take the one used to schedule
            key = lambda x: (
                1 if not x.running else 0,
                x.running.priority if x.running else 0,
                1 if x is cpu else 0
            )
            cpu_min = max(self.processors, key=key)

            job = min([j for j in self.ready_list if j.is_active()],
                      key=lambda x: x.priority)

            if (cpu_min.running is None or
                    cpu_min.running.priority > job.priority):
                self.ready_list.remove(job)
                if cpu_min.running:
                    self.ready_list.append(cpu_min.running)
                return (job, cpu_min)