blob: 93701ddbd22585441650b0c46421b3dfe906485b (
plain) (
blame)
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
|
from __future__ import division
from math import floor
from fractions import Fraction
from schedcat.util.quantor import forall
ONE = Fraction(1)
def N(t_k, t_i):
# assumes integral time
return int(floor((t_k.deadline - t_i.deadline) / t_i.period)) + 1
def beta(t_k, t_i):
N_i = N(t_k, t_i)
C_i = t_i.cost
T_i = t_i.period
D_k = t_k.deadline
return Fraction(N_i * C_i + min(C_i, max(0, D_k - N_i * T_i)) , D_k)
def task_schedulable(T, t_k, m):
l_k = t_k.density_q()
cap = m * (ONE - l_k)
all_beta = [beta(t_k, t_i) for t_i in T if t_i != t_k]
beta_sum = sum([min(b, ONE - l_k) for b in all_beta])
return beta_sum < cap or \
(beta_sum == cap and any([0 < b <= ONE - l_k for b in all_beta]))
def is_schedulable(no_cpus, tasks):
return forall(tasks)(lambda t_k: task_schedulable(tasks, t_k, no_cpus))
|
