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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
|
#ifndef TASKS_H
#define TASKS_H
#ifndef SWIG
#include <vector>
#include <algorithm>
#include <math.h>
#include "time-types.h"
#endif
class Task
{
private:
unsigned long period;
unsigned long wcet;
unsigned long deadline;
unsigned long prio_pt;
public:
/* construction and initialization */
void init(unsigned long wcet, unsigned long period, unsigned long deadline = 0, unsigned long prio_pt = 0);
Task(unsigned long wcet = 0,
unsigned long period = 0,
unsigned long deadline = 0,
unsigned long prio_pt = 0) { init(wcet, period, deadline, prio_pt); }
/* getter / setter */
unsigned long get_period() const { return period; }
unsigned long get_wcet() const { return wcet; }
/* defaults to implicit deadline */
unsigned long get_deadline() const {return deadline; }
unsigned long get_prio_pt() const { return prio_pt; }
void set_period(unsigned long period) { this->period = period; }
void set_wcet(unsigned long wcet) { this->wcet = wcet; }
void set_deadline(unsigned long deadline) { this->deadline = deadline; }
/* properties */
bool has_implicit_deadline() const;
bool has_constrained_deadline() const;
bool is_feasible() const;
void get_utilization(fractional_t &util) const;
void get_density(fractional_t &density) const;
// Demand bound function (DBF) and LOAD support.
// This implements Fisher, Baker, and Baruah's PTAS
unsigned long bound_demand(unsigned long time) const
{
if (time <= deadline)
return 0;
else
{
unsigned long jobs;
time -= deadline;
jobs = time / period; // implicit floor in integer division
jobs += 1;
return jobs * wcet;
}
}
void bound_demand(const integral_t &time, integral_t &demand) const
{
if (time <= deadline)
demand = 0;
else
{
demand = time;
demand -= deadline;
demand /= period; // implicit floor in integer division
demand += 1;
demand *= wcet;
}
}
void bound_load(const integral_t &time, fractional_t &load) const
{
integral_t demand;
if (time > 0)
{
bound_demand(time, demand);
load = demand;
load /= time;
}
else
load = 0;
}
unsigned long approx_demand(unsigned long time, unsigned int k) const
{
if (time < k * period + deadline)
return bound_demand(time);
else
{
double approx = time - deadline;
approx *= wcet;
approx /= period;
return wcet + (unsigned long) ceil(approx);
}
}
void approx_demand(const integral_t &time, integral_t &demand,
unsigned int k) const
{
if (time < k * period + deadline)
bound_demand(time, demand);
else
{
integral_t approx;
approx = time;
approx -= deadline;
approx *= wcet;
mpz_cdiv_q_ui(demand.get_mpz_t(), approx.get_mpz_t(), period);
demand += wcet;
}
}
void approx_load(const integral_t &time, fractional_t &load,
unsigned int k) const
{
integral_t demand;
if (time > 0)
{
approx_demand(time, demand, k);
load = demand;
load /= time;
}
else
load = 0;
}
};
typedef std::vector<Task> Tasks;
class TaskSet
{
private:
Tasks tasks;
unsigned long k_for_epsilon(unsigned int idx, const fractional_t &epsilon) const;
public:
TaskSet();
TaskSet(const TaskSet &original);
virtual ~TaskSet();
void add_task(unsigned long wcet, unsigned long period,
unsigned long deadline = 0, unsigned long prio_pt = 0)
{
tasks.push_back(Task(wcet, period, deadline, prio_pt));
}
unsigned int get_task_count() const { return tasks.size(); }
Task& operator[](int idx) { return tasks[idx]; }
const Task& operator[](int idx) const { return tasks[idx]; }
bool has_only_implicit_deadlines() const;
bool has_only_constrained_deadlines() const;
bool has_only_feasible_tasks() const;
bool is_not_overutilized(unsigned int num_processors) const;
void get_utilization(fractional_t &util) const;
void get_density(fractional_t &density) const;
void get_max_density(fractional_t &max_density) const;
void bound_demand(const integral_t &time, integral_t &demand) const;
void approx_load(fractional_t &load, const fractional_t &epsilon = 0.1) const;
/* wrapper for Python access */
unsigned long get_period(unsigned int idx) const
{
return tasks[idx].get_period();
}
unsigned long get_wcet(unsigned int idx) const
{
return tasks[idx].get_wcet();
}
unsigned long get_deadline(unsigned int idx) const
{
return tasks[idx].get_deadline();
}
};
#endif
|
