def schedule(self, cpu):
        if len(self.ready_list) > 0:
            # Explication sur la key:
            # En priorité, on met tous les processeurs libres au début.
            # Ensuite, on trie tout par ordre décroissant de la deadline.
            # Et on départage en préférant le processeur "cpu".
            key = lambda x: (
                1 if (not x.running) or (not self.pseudo_job[x]) else 0,
                self.pseudo_job[x].cmp_key() if x.running and
                self.pseudo_job[x] else None,
                1 if x is cpu else 0
            )
            cpu_min = max(self.processors, key=key)

            pjob = min(self.ready_list, key=lambda x: x.cmp_key())

            if (cpu_min.running is None or
                    self.pseudo_job[cpu_min] is None or
                    self.pseudo_job[cpu_min].cmp_key() > pjob.cmp_key()):
                self.ready_list.remove(pjob)
                if cpu_min.running and self.pseudo_job[cpu_min]:
                    self.ready_list.append(self.pseudo_job[cpu_min])
                self.pseudo_job[cpu_min] = pjob

                timer = Timer(
                    self.sim, EPDF.pseudo_terminate, (self, pjob),
                    pjob.seq * self.quantum - pjob.job.computation_time,
                    cpu=cpu_min, in_ms=True)
                timer.start()
                self.timers.append(timer)

                return (pjob.job, cpu_min)
        elif self.pseudo_job[cpu] is None:
            return (None, cpu)

    def schedule(self, cpu):
        """
        Take the scheduling decisions.
        """
        self.waiting_schedule = False
        decisions = []
        self.h_c = [(d, t) for d, t in self.h_c if t.job.is_active()]
        heapify(self.h_c)

        if self.sim.now() == self.t_f:
            decisions = self.init_tl_plane()
        else:
            for task in self.activations:
                decisions += self.handle_evt_a(task)
            if self.evt_bc:
                decisions += self.handle_evt_bc()

        self.activations = []
        self.evt_bc = False

        if self.h_b:
            t_next = self.h_b[0][0]
            if self.h_c:
                t_next = min(t_next, self.h_c[0][0])

            self.timer = Timer(self.sim, LRE_TL.event_bc, (self,),
                               t_next - self.sim.now(),
                               cpu=self.processors[0], in_ms=False)
        else:
            self.timer = Timer(self.sim, LRE_TL.reschedule, (self,),
                               self.t_f - self.sim.now(),
                               cpu=self.processors[0], in_ms=False)
        self.timer.start()

        return decisions

class RR(Scheduler):
    def init(self):
        self.ready_list = Queue()
        self.running_job = None
        self.quantum = 1 # ms
        self.timer = Timer(self.sim, RR.reschedule,
                          (self, self.processors[0]), self.quantum, one_shot=False,
                          cpu=self.processors[0])
        self.timer.start()
        
    def reschedule(self, cpu):
        if not self.ready_list.empty():
            cpu.resched()

    def on_activate(self, job):
        self.ready_list.put(job)
        job.cpu.resched()

    def on_terminated(self, job):
        self.running_job = None
        job.cpu.resched()

    def schedule(self, cpu):
        if not self.ready_list.empty():
            job = self.ready_list.get()
            if self.running_job is not None:
                self.ready_list.put(self.running_job)
            self.running_job = job
        else:
            job = self.running_job
        return (job, cpu)

    def conf(self, next_deadline):
        if next_deadline > self.next_deadline:
            self.next_deadline = next_deadline
            self.migrating_task1, self.migrating_task2 = self.migrating_task2, self.migrating_task1
            if self.migrating_task1:
                time_a = ceil((next_deadline - self.sim.now()) * self.migrating_task1[1])
                self.timer_a = Timer(
                    self.sim, Modified_EDF.on_end_migrating1, (self,), time_a, cpu=self.processors[0], in_ms=False
                )
                self.timer_a.start()

            self.migrating_job2 = None
            if self.migrating_task2:
                time_b = int((next_deadline - self.sim.now()) * (1 - self.migrating_task2[1]))
                self.timer_b = Timer(
                    self.sim, Modified_EDF.on_start_migrating2, (self,), time_b, cpu=self.processors[0], in_ms=False
                )
                self.timer_b.start()
                self.processors[0].resched()

        if self.migrating_task1:
            self.migrating_job1 = self.migrating_task1[0].job
            self.processors[0].resched()
        else:
            self.migrating_job1 = None

    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

class MLLF(Scheduler):
    """Modified Least Laxity First"""
    def init(self):
        self.ready_list = []
        self.timer = None

    def compute_laxity(self, cpu):
        if self.ready_list:
            for job in self.ready_list:
                job.laxity = (job.absolute_deadline - job.ret) * \
                    self.sim.cycles_per_ms - self.sim.now()
            cpu.resched()

    def on_activate(self, job):
        self.ready_list.append(job)
        self.compute_laxity(job.cpu)

    def on_terminated(self, job):
        self.ready_list.remove(job)
        self.compute_laxity(job.cpu)

    def schedule(self, cpu):
        decisions = []
        if self.ready_list:
            # Sort according to the laxity.
            self.ready_list.sort(
                key=lambda x: (x.laxity, x.absolute_deadline))

            # m : Nombre de processeurs.
            m = len(self.processors)

            # Available processors:
            l = (proc for proc in self.processors
                 if proc.running not in self.ready_list[:m])

            if len(self.ready_list) > m:
                ta = self.ready_list[m - 1]
                dmin = self.ready_list[m].absolute_deadline * \
                    self.sim.cycles_per_ms - self.sim.now()

                if self.timer:
                    self.timer.stop()
                self.timer = Timer(
                    self.sim, MLLF.compute_laxity,
                    (self, self.processors[0]), dmin - ta.laxity,
                    one_shot=True,
                    cpu=self.processors[0])
                self.timer.start()

            # The first m jobs should be running:
            for job in self.ready_list[:m]:
                if not job.is_running():
                    proc = next(l)
                    decisions.append((job, proc))

        return decisions

class EDF_modified(Scheduler):
    """
    An EDF mono-processor scheduler modified to accept migrating jobs.
    A migrating job has an infinite priority.
    """
    def init(self):
        self.ready_list = []
        self.migrating_job = None

    def _resched(self):
        self.processors[0].resched()

    def on_activate(self, job):
        self.ready_list.append(job)
        self._resched()

    def on_terminated(self, job):
        if job is self.migrating_job:
            self.migrating_job = None
        elif job in self.ready_list:
            self.ready_list.remove(job)
        self._resched()

    def accept_migrating_job(self, i, job, budget):
        self.migrating_job = job
        job.task.cpu = self.processors[0]

        # Set timer for end.
        self.timer = Timer(self.sim, EDF_modified.end_migrating_job,
                           (self, i), budget, cpu=self.processors[0],
                           in_ms=False)
        self.timer.start()

        self._resched()

    def end_migrating_job(self, i):
        self.processors[0].resched()
        if self.migrating_job and i < len(migrating_tasks[self.migrating_job.task]) - 1:
            ncpu, nbudget = migrating_tasks[self.migrating_job.task][i + 1]
            sched = map_cpu_sched[ncpu]
            sched.accept_migrating_job(i + 1, self.migrating_job, nbudget)
        self.migrating_job = None

    def schedule(self, cpu):
        if self.migrating_job:
            job = self.migrating_job
        elif self.ready_list:
            job = min(self.ready_list, key=lambda x: x.absolute_deadline)
        else:
            job = None

        return (job, cpu)

    def schedule(self, cpu):
        decisions = []
        if self.ready_list:
            # Sort according to the laxity.
            self.ready_list.sort(
                key=lambda x: (x.laxity, x.absolute_deadline))

            # m : Nombre de processeurs.
            m = len(self.processors)

            # Available processors:
            l = (proc for proc in self.processors
                 if proc.running not in self.ready_list[:m])

            if len(self.ready_list) > m:
                ta = self.ready_list[m - 1]
                dmin = self.ready_list[m].absolute_deadline * \
                    self.sim.cycles_per_ms - self.sim.now()

                if self.timer:
                    self.timer.stop()
                self.timer = Timer(
                    self.sim, MLLF.compute_laxity,
                    (self, self.processors[0]), dmin - ta.laxity,
                    one_shot=True,
                    cpu=self.processors[0])
                self.timer.start()

            # The first m jobs should be running:
            for job in self.ready_list[:m]:
                if not job.is_running():
                    proc = next(l)
                    decisions.append((job, proc))

        return decisions

    def on_activate(self, job):
        # First pseudo-activation
        pseudo_job = EPDF.PseudoJob(job, 1)

        self.pseudo_activate(pseudo_job)

        # Set next pseudo activations :
        while pseudo_job.seq * self.quantum < job.wcet:
            pseudo_job = EPDF.PseudoJob(job, pseudo_job.seq + 1)
            timer = Timer(self.sim, EPDF.pseudo_activate, (self, pseudo_job),
                          pseudo_job.release_date * self.quantum -
                          self.sim.now() / self.sim.cycles_per_ms +
                          job.activation_date, cpu=job.cpu,
                          in_ms=True)
            timer.start()
            self.timers.append(timer)

    def schedule(self):
        """
        Schedule this proper sub-system.
        """
        self.to_reschedule = False
        decision = []

        self.virtual = []
        jobs = select_jobs(self.root, self.virtual)

        wakeup_delay = min(self.virtual, key=lambda s: s.budget).budget
        if wakeup_delay > 0:
            self.timer = Timer(self.sim, ProperSubsystem.virtual_event,
                               (self, self.processors[0]), wakeup_delay,
                               cpu=self.processors[0], in_ms=False)
            self.timer.start()

        cpus = []
        for cpu in self.processors:
            if cpu.running in jobs:
                jobs.remove(cpu.running)
            else:
                cpus.append(cpu)

        for cpu in cpus:
            if jobs:
                decision.append((jobs.pop(), cpu))
            else:
                decision.append((None, cpu))

        return decision

 def init(self):
     self.ready_list = Queue()
     self.running_job = None
     self.quantum = 1 # ms
     self.timer = Timer(self.sim, RR.reschedule,
                       (self, self.processors[0]), self.quantum, one_shot=False,
                       cpu=self.processors[0])
     self.timer.start()

class LLF(Scheduler):
    """Least Laxity First"""
    def init(self):
        self.ready_list = []
        self.timer = Timer(self.sim, LLF.compute_laxity,
                           (self, self.processors[0]), 1, one_shot=False,
                           cpu=self.processors[0], overhead=.01)
        self.timer.start()

    def compute_laxity(self, cpu):
        if self.ready_list:
            for job in self.ready_list:
                job.laxity = job.absolute_deadline - \
                    (job.ret + self.sim.now_ms())
            cpu.resched()

    def on_activate(self, job):
        self.ready_list.append(job)
        self.compute_laxity(job.cpu)

    def on_terminated(self, job):
        self.ready_list.remove(job)
        self.compute_laxity(job.cpu)

    def schedule(self, cpu):
        decisions = []
        if self.ready_list:
            # Sort according to the laxity.
            self.ready_list.sort(key=lambda x: (x.laxity, x.task.identifier))

            # m : Nombre de processeurs.
            m = len(self.processors)

            # Available processors:
            l = (proc for proc in self.processors
                 if proc.running not in self.ready_list[:m])

            # The first m jobs should be running:
            for job in self.ready_list[:m]:
                if not job.is_running():
                    proc = next(l)
                    decisions.append((job, proc))

        return decisions

 def init(self):
     self.ready_list = []
     """
     However, LSTR
     scheduling algorithm operates on every basic time unit. Here, we consider the basic
     time unit of 1 (ms).
     """
     self.timer = Timer(self.sim, LSTR.virtual_event,
                        (self, self.processors[0]), 1, one_shot=False)
     self.timer.start()

    def accept_migrating_job(self, i, job, budget):
        self.migrating_job = job
        job.task.cpu = self.processors[0]

        # Set timer for end.
        self.timer = Timer(self.sim, EDF_modified.end_migrating_job,
                           (self, i), budget, cpu=self.processors[0],
                           in_ms=False)
        self.timer.start()

        self._resched()

    def schedule(self, cpu):
        now = self.sim.now_ms()
        remaining_time_in_window = self.windowsize - (now % self.windowsize)
        if now % self.windowsize == 0:
            self.reset_window(cpu)

        if remaining_time_in_window > 0:
            try:
                current_job = self.timeline[self.window_id][self.queue_index]
                # if job has still reserved cpu time
                if current_job.is_running() and now < current_job.absolute_burst:
                    return (current_job, cpu)
            except:
                pass            
            # burst has finished and next prioritary job is selected
            try:
                job = self.timeline[self.window_id][self.queue_index]
                priority = self.queue_index + 1
                burst = self.windowsize / 2**priority
            except Exception as e:
                available = [job for job in self.timeline[self.window_id] if job.is_active()] + self.ready_list
                if len(available):
                    # Slack time, choose random job
                    job = choice(available)
                    burst = self.default_quantum
                else:
                    # Idle
                    return (None, cpu)

            if burst == 0: # gain time
                if self.ready_list:
                    job = choice(self.ready_list)
                burst = min(self.default_quantum, remaining_time_in_window)
            else: # adjust burst
                burst = min(remaining_time_in_window, (min(burst, job.ret)))

            if burst == 0 and remaining_time_in_window > 0:
                burst = remaining_time_in_window

            #print "[{3}] JOB {0}, scheduled with burst {1} until {2}".format(job.name, burst, now+burst, now)
            self.preempt_timer = Timer(self.sim, DPSDy.reschedule,
                              (self, self.processors[0]), ceil(burst),
                              one_shot=True, cpu=self.processors[0])
            job.absolute_burst = now + burst
            self.preempt_timer.start()                    

            self.queue_index += 1
            return (job, cpu)

    def schedule(self, cpu):
        now = self.sim.now_ms()
        remaining_time_in_window = float("{0:.2f}".format(self.windowsize - (now % self.windowsize)))
        if now % self.windowsize == 0:
            self.reset_window(cpu)
            cpu.monitor.observe(ProcEvent(ProcEvent.SEPARATOR))

        if remaining_time_in_window > 0:
            try:
                current_job = self.timeline[self.window_id][self.queue_index][0]
                # if job has still reserved cpu time
                if current_job.is_running() and now < current_job.absolute_burst:
                    return (current_job, cpu)
            except:
                pass            
            # burst has finished and next prioritary job is selected
            try:
                job, burst = self.timeline[self.window_id][self.queue_index]
            except Exception as e:
                available = [job[0] for job in self.timeline[self.window_id] if job[0].is_active()] + self.ready_list
                if len(available):
                    # Slack time, choose random job
                    job = choice(available)
                    burst = self.default_quantum
                else:
                    # Idle
                    return (None, cpu)

            burst = float("{0:.2f}".format(burst))
            if burst == 0: # gain time
                if self.ready_list:
                    job = choice(self.ready_list)
                burst = self.default_quantum
            # adjust burst
            ret = float("{0:.2f}".format(job.ret))
            burst = min(remaining_time_in_window, burst, ret)

            if burst == 0 and remaining_time_in_window > 0:
                burst = remaining_time_in_window

            self.preempt_timer = Timer(self.sim, BDPS.reschedule,
                              (self, self.processors[0]), burst,
                              one_shot=True, cpu=self.processors[0])
            job.absolute_burst = now + burst
            self.preempt_timer.start()                    

            self.queue_index += 1
            return (job, cpu)

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

        ER_PD2.quantum = self.sim.cycles_per_ms // 10 # 0.1ms.

        #ER_PD2.quantum = 1000000
        #while not self.is_schedulable() and ER_PD2.quantum > 1000:
        #    ER_PD2.quantum /= 2

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

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

        # Sort the jobs by budgets.
        sorted_budgets = sorted(
            [(x, ceil(y)) for x, y in self.budget.items()],
            key=lambda x: (-x[1], x[0].name))
        selected = sorted_budgets[:len(self.processors)]
        not_selected = sorted_budgets[len(self.processors):]

        # Compute the (relative) date of the next event.
        next_event = self.date_next_event(selected, not_selected)
        if next_event > 0:
            # Set a timer to reschedule the system at that date.
            self.timer_a = Timer(self.sim, LLREF.reschedule, (self,),
                                 next_event, cpu=cpu, in_ms=False)
            self.timer_a.start()

        # Allocate the selected jobs to the processors.
        # The processors already running selected jobs are not changed.
        available_procs = []
        self.selected_jobs = [s[0] for s in selected if s[1] > 0]
        remaining_jobs = self.selected_jobs[:]
        for proc in self.processors:
            if proc.running in self.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)

        # The remaining processors are running the remaining jobs or None.
        padded_remaining_jobs = remaining_jobs + \
            [None] * (len(available_procs) - len(remaining_jobs))
        # zip create a list of couples (job, proc) using the list of remaining
        # jobs and the list of available processors.
        decisions = list(zip(padded_remaining_jobs, available_procs))

        return decisions

class ProperSubsystem(object):
    """
    Proper sub-system. A proper sub-system is the set of the tasks belonging to
    a unit server (server with utilization of 1) and a set of processors.
    """

    def __init__(self, sim, root, processors):
        self.sim = sim
        self.root = root
        self.processors = processors
        self.virtual = []
        self.last_update = 0
        self.to_reschedule = False
        self.timer = None

    def update_budget(self):
        """
        Update the budget of the servers.
        """
        time_since_last_update = self.sim.now() - self.last_update
        for server in self.virtual:
            server.budget -= time_since_last_update
        self.last_update = self.sim.now()

    def resched(self, cpu):
        """
        Plannify a scheduling decision on processor cpu. Ignore it if already
        planned.
        """
        if not self.to_reschedule:
            self.to_reschedule = True
            cpu.resched()

    def virtual_event(self, cpu):
        """
        Virtual scheduling event. Happens when a virtual job terminates.
        """
        self.update_budget()
        self.resched(cpu)

    def schedule(self):
        """
        Schedule this proper sub-system.
        """
        self.to_reschedule = False
        decision = []

        self.virtual = []
        jobs = select_jobs(self.root, self.virtual)

        wakeup_delay = min(self.virtual, key=lambda s: s.budget).budget
        if wakeup_delay > 0:
            self.timer = Timer(self.sim, ProperSubsystem.virtual_event,
                               (self, self.processors[0]), wakeup_delay,
                               cpu=self.processors[0], in_ms=False)
            self.timer.start()

        cpus = []
        for cpu in self.processors:
            if cpu.running in jobs:
                jobs.remove(cpu.running)
            else:
                cpus.append(cpu)

        for cpu in cpus:
            if jobs:
                decision.append((jobs.pop(), cpu))
            else:
                decision.append((None, cpu))

        return decision

 def init(self):
     self.ready_list = []
     self.timer = Timer(self.sim, LLF.compute_laxity,
                        (self, self.processors[0]), 1, one_shot=False,
                        cpu=self.processors[0], overhead=.01)
     self.timer.start()