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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
|
import schedcat.locking.native as cpp
# assumes mutex constraints
def get_cpp_model(all_tasks, use_task_period=False):
rsi = cpp.ResourceSharingInfo(len(all_tasks))
for t in all_tasks:
rsi.add_task(t.period,
t.period if use_task_period else t.response_time,
t.partition,
t.locking_prio)
for req in t.resmodel:
req = t.resmodel[req]
rsi.add_request_rw(req.res_id, req.max_requests, req.max_length, cpp.WRITE)
return rsi
def get_cpp_model_rw(all_tasks, use_task_period=False):
rsi = cpp.ResourceSharingInfo(len(all_tasks))
for t in all_tasks:
rsi.add_task(t.period,
t.period if use_task_period else t.response_time,
t.partition,
t.locking_prio)
for req in t.resmodel:
req = t.resmodel[req]
if req.max_writes > 0:
rsi.add_request_rw(req.res_id, req.max_writes, req.max_write_length, cpp.WRITE)
if req.max_reads > 0:
rsi.add_request_rw(req.res_id, req.max_reads, req.max_read_length, cpp.READ)
return rsi
def assign_edf_locking_prios(all_tasks):
all_deadlines = set([t.deadline for t in all_tasks])
prio = {}
for i, dl in enumerate(sorted(all_deadlines)):
prio[int(dl)] = i
for t in all_tasks:
t.locking_prio = prio[int(t.deadline)]
def assign_prio_pt_locking_prios(all_tasks):
all_prio_pts = set([t.prio_pt for t in all_tasks])
prio = {}
for i, pp in enumerate(sorted(all_prio_pts)):
prio[int(pp)] = i
for t in all_tasks:
t.locking_prio = prio[int(t.prio_pt)]
def assign_fp_locking_prios(all_tasks):
# prioritized in index order
for i, t in enumerate(all_tasks):
t.locking_prio = i
# S-aware bounds
def apply_mpcp_bounds(all_tasks, use_virtual_spin=False):
model = get_cpp_model(all_tasks)
res = cpp.mpcp_bounds(model, use_virtual_spin)
if use_virtual_spin:
for i,t in enumerate(all_tasks):
# no suspension time
t.suspended = 0
# all blocking, including arrival blocking
t.blocked = res.get_blocking_term(i)
# remote blocking increases CPU demand (s-oblivious)
t.cost += res.get_remote_blocking(i)
else:
for i,t in enumerate(all_tasks):
# remote blocking <=> suspension time
t.suspended = res.get_remote_blocking(i)
# all blocking, including arrival blocking
t.blocked = res.get_blocking_term(i)
t.locally_blocked = res.get_local_blocking(i)
return res
def get_round_robin_resource_mapping(num_resources, num_cpus,
dedicated_irq=cpp.NO_CPU):
"Default resource assignment: just assign resources to CPUs in index order."
loc = {}
for res_id in xrange(num_resources):
cpu = res_id % num_cpus
if cpu == dedicated_irq:
cpu = (cpu + 1) % num_cpus
loc[res_id] = cpu
return loc
def get_cpp_topology(res_mapping):
map = cpp.ResourceLocality()
for res_id in res_mapping:
map.assign_resource(res_id, res_mapping[res_id])
return map
def apply_dpcp_bounds(all_tasks, resource_mapping,
use_text_book_definition=False):
# The DPCP bounds are expressed in terms of task periods,
# not response time, in the original definition.
model = get_cpp_model(all_tasks, use_text_book_definition)
topo = get_cpp_topology(resource_mapping)
res = cpp.dpcp_bounds(model, topo)
for i,t in enumerate(all_tasks):
# remote blocking <=> suspension time
t.suspended = res.get_remote_blocking(i)
# all blocking, including arrival blocking
t.blocked = res.get_blocking_term(i)
return res
def apply_part_fmlp_bounds(all_tasks, preemptive=True):
model = get_cpp_model(all_tasks)
res = cpp.part_fmlp_bounds(model, preemptive)
for i,t in enumerate(all_tasks):
# remote blocking <=> suspension time
t.suspended = res.get_remote_blocking(i)
# all blocking, including local blocking
t.blocked = res.get_blocking_term(i)
t.local_blocking_count = res.get_local_count(i)
return res
# S-oblivious bounds
def apply_suspension_oblivious(all_tasks, res):
for i,t in enumerate(all_tasks):
# s-oblivious <=> no suspension
t.suspended = 0
# might be zero
t.arrival_blocked = res.get_arrival_blocking(i)
# all blocking, including arrival blocking
t.blocked = res.get_blocking_term(i)
# s-oblivious: charge it as execution cost
t.cost += t.blocked
def apply_global_fmlp_sob_bounds(all_tasks):
model = get_cpp_model(all_tasks)
res = cpp.global_fmlp_bounds(model)
apply_suspension_oblivious(all_tasks, res)
return res
def apply_global_omlp_bounds(all_tasks, num_cpus):
model = get_cpp_model(all_tasks)
res = cpp.global_omlp_bounds(model, num_cpus)
apply_suspension_oblivious(all_tasks, res)
return res
def apply_clustered_omlp_bounds(all_tasks, procs_per_cluster,
dedicated_irq=cpp.NO_CPU):
model = get_cpp_model(all_tasks)
res = cpp.clustered_omlp_bounds(model, procs_per_cluster, dedicated_irq)
apply_suspension_oblivious(all_tasks, res)
return res
def apply_clustered_rw_omlp_bounds(all_tasks, procs_per_cluster,
dedicated_irq=cpp.NO_CPU):
model = get_cpp_model_rw(all_tasks)
res = cpp.clustered_rw_omlp_bounds(model, procs_per_cluster, dedicated_irq)
apply_suspension_oblivious(all_tasks, res)
return res
def apply_clustered_kx_omlp_bounds(all_tasks, procs_per_cluster,
replication_degrees = {},
dedicated_irq=cpp.NO_CPU):
model = get_cpp_model(all_tasks)
replica_info = cpp.ReplicaInfo()
for res_id in replication_degrees:
replica_info.set_replicas(res_id, replication_degrees[res_id])
res = cpp.clustered_kx_omlp_bounds(model, replica_info, procs_per_cluster,
dedicated_irq)
apply_suspension_oblivious(all_tasks, res)
return res
# spinlocks are charged similarly to s-oblivious analysis
def apply_task_fair_mutex_bounds(all_tasks, procs_per_cluster,
dedicated_irq=cpp.NO_CPU):
model = get_cpp_model(all_tasks)
res = cpp.task_fair_mutex_bounds(model, procs_per_cluster, dedicated_irq)
apply_suspension_oblivious(all_tasks, res)
return res
def apply_task_fair_rw_bounds(all_tasks, procs_per_cluster,
dedicated_irq=cpp.NO_CPU):
model = get_cpp_model_rw(all_tasks)
# mutex equivalent model
model_mtx = get_cpp_model(all_tasks)
res = cpp.task_fair_rw_bounds(model, model_mtx, procs_per_cluster, dedicated_irq)
apply_suspension_oblivious(all_tasks, res)
return res
def apply_phase_fair_rw_bounds(all_tasks, procs_per_cluster,
dedicated_irq=cpp.NO_CPU):
model = get_cpp_model_rw(all_tasks)
res = cpp.phase_fair_rw_bounds(model, procs_per_cluster, dedicated_irq)
apply_suspension_oblivious(all_tasks, res)
return res
### S-aware LP-based analysis of distributed locking protocols
try:
import schedcat.locking.linprog.native as lp_cpp
lp_cpp_available = True
except ImportError:
lp_cpp_available = False
import schedcat.locking.linprog.dflp as dflp
import schedcat.locking.linprog.dpcp as dpcp
def apply_py_lp_bounds(bounds, all_tasks, resource_mapping, *args):
for t in all_tasks:
lp = bounds.get_lp_for_task(resource_mapping,
all_tasks, t, *args)
lp.kill_non_positive_vars()
solution = lp.solve()
# total blocking
t.blocked = int(solution(lp.objective_function))
t.suspended = int(solution(lp.remote_objective))
def apply_lp_dflp_bounds(all_tasks, resource_mapping,
use_py=False):
if use_py or not lp_cpp_available:
apply_py_lp_bounds(dflp, all_tasks, resource_mapping)
else:
model = get_cpp_model(all_tasks)
topo = get_cpp_topology(resource_mapping)
res = lp_cpp.lp_dflp_bounds(model, topo)
for i, t in enumerate(all_tasks):
t.suspended = res.get_remote_blocking(i)
t.blocked = res.get_blocking_term(i)
return res
def apply_lp_dpcp_bounds(all_tasks, resource_mapping,
use_rta = True, use_py=False):
if use_py or not lp_cpp_available:
apply_py_lp_bounds(dpcp, all_tasks, resource_mapping, use_rta)
else:
model = get_cpp_model(all_tasks)
topo = get_cpp_topology(resource_mapping)
res = lp_cpp.lp_dpcp_bounds(model, topo, use_rta)
for i, t in enumerate(all_tasks):
t.suspended = res.get_remote_blocking(i)
t.blocked = res.get_blocking_term(i)
return res
def apply_lp_mpcp_bounds(all_tasks):
model = get_cpp_model(all_tasks)
res = lp_cpp.lp_mpcp_bounds(model)
for i,t in enumerate(all_tasks):
# remote blocking <=> self-suspension time
t.suspended = res.get_remote_blocking(i)
# all blocking, including local blocking
t.blocked = res.get_blocking_term(i)
t.locally_blocked = res.get_local_blocking(i)
return res
def apply_lp_part_fmlp_bounds(all_tasks):
# LP-based analysis of the partitioned, preemptive FMLP+
model = get_cpp_model(all_tasks)
res = lp_cpp.lp_part_fmlp_bounds(model)
for i,t in enumerate(all_tasks):
# remote blocking <=> self-suspension time
t.suspended = res.get_remote_blocking(i)
# all blocking, including local blocking
t.blocked = res.get_blocking_term(i)
t.locally_blocked = res.get_local_blocking(i)
return res
def apply_omip_bounds(all_tasks, num_cpus, procs_per_cluster):
model = get_cpp_model(all_tasks)
res = lp_cpp.lp_omip_bounds(model, num_cpus, procs_per_cluster)
apply_suspension_oblivious(all_tasks, res)
return res
|
