Rev 1107 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1085 | pj | 1 | /* |
2 | * Project: S.Ha.R.K. |
||
3 | * |
||
4 | * Coordinators: |
||
5 | * Giorgio Buttazzo <giorgio@sssup.it> |
||
6 | * Paolo Gai <pj@gandalf.sssup.it> |
||
7 | * |
||
8 | * Authors : |
||
9 | * Paolo Gai <pj@gandalf.sssup.it> |
||
10 | * Massimiliano Giorgi <massy@gandalf.sssup.it> |
||
11 | * Luca Abeni <luca@gandalf.sssup.it> |
||
12 | * (see the web pages for full authors list) |
||
13 | * |
||
14 | * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy) |
||
15 | * |
||
16 | * http://www.sssup.it |
||
17 | * http://retis.sssup.it |
||
18 | * http://shark.sssup.it |
||
19 | */ |
||
20 | |||
21 | /** |
||
22 | ------------ |
||
1123 | pj | 23 | CVS : $Id: slsh.c,v 1.4 2003-01-07 17:10:18 pj Exp $ |
1085 | pj | 24 | |
25 | File: $File$ |
||
1123 | pj | 26 | Revision: $Revision: 1.4 $ |
27 | Last update: $Date: 2003-01-07 17:10:18 $ |
||
1085 | pj | 28 | ------------ |
29 | |||
30 | This file contains the scheduling module for Slot-Shifting. |
||
31 | |||
32 | Read slsh.h for further details. |
||
33 | |||
34 | **/ |
||
35 | |||
36 | /* |
||
37 | * Copyright (C) 2000 Paolo Gai |
||
38 | * |
||
39 | * This program is free software; you can redistribute it and/or modify |
||
40 | * it under the terms of the GNU General Public License as published by |
||
41 | * the Free Software Foundation; either version 2 of the License, or |
||
42 | * (at your option) any later version. |
||
43 | * |
||
44 | * This program is distributed in the hope that it will be useful, |
||
45 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
46 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
||
47 | * GNU General Public License for more details. |
||
48 | * |
||
49 | * You should have received a copy of the GNU General Public License |
||
50 | * along with this program; if not, write to the Free Software |
||
51 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
||
52 | * |
||
53 | */ |
||
54 | |||
55 | |||
56 | #include "slsh.h" |
||
57 | #include <ll/stdio.h> |
||
58 | #include <ll/stdlib.h> |
||
59 | #include <ll/string.h> |
||
60 | #include <ll/math.h> /* for ceil(...) */ |
||
61 | #include <ll/ll.h> /* for memcpy(...) */ |
||
62 | #include <kernel/model.h> |
||
63 | #include <kernel/descr.h> |
||
64 | #include <kernel/var.h> |
||
65 | #include <kernel/func.h> |
||
1123 | pj | 66 | #include <kernel/trace.h> |
1085 | pj | 67 | |
68 | //#define eslsh_printf kern_printf |
||
69 | #define slsh_printf printk |
||
70 | |||
71 | /* Keeps information about static and guaranteed tasks */ |
||
72 | typedef struct { |
||
73 | int est; |
||
74 | int dabs; |
||
75 | int interval; |
||
76 | } SLSH_task; |
||
77 | |||
78 | /*+ Status used in the level +*/ |
||
79 | #define SLSH_READY MODULE_STATUS_BASE |
||
80 | #define SLSH_WAIT MODULE_STATUS_BASE + 1 |
||
81 | #define SLSH_IDLE MODULE_STATUS_BASE + 2 |
||
82 | #define SLSH_WCET_VIOLATED MODULE_STATUS_BASE + 3 |
||
83 | |||
84 | /*+ defines +*/ |
||
85 | #define MAX_INTERVALS 1000 /* 1000 intervals is max, for now */ |
||
86 | |||
87 | /******+ the level redefinition for the SLOT SHIFT level +*******/ |
||
88 | typedef struct { |
||
89 | level_des l; /*+ the standard level descriptor+*/ |
||
90 | |||
91 | /* task lists */ |
||
92 | SLSH_task tasks[MAX_PROC]; /* est and dl's for static and guaranteed task */ |
||
93 | |||
1107 | pj | 94 | IQUEUE idle_statics; /* finished static tasks */ |
1085 | pj | 95 | |
1107 | pj | 96 | IQUEUE unspecified; /* tasks with only a wcet */ |
1085 | pj | 97 | |
98 | /* the Intervals list */ |
||
99 | SLSH_interval intervals[MAX_INTERVALS]; |
||
100 | int current; /* current interval */ |
||
101 | int last; /* last interval */ |
||
102 | |||
103 | int slot; /* slot shifting time */ |
||
104 | TIME slot_length; /* slothlength in real system time*/ |
||
105 | int LCM; /* length (in slots) of ofline schedule */ |
||
106 | |||
107 | int slot_event; /* save the event */ |
||
108 | } SLSH_level_des; |
||
109 | |||
110 | |||
111 | /* check if some tasks are ready, return 0 if ready, -1 otherwise */ |
||
112 | static int SLSH_R(SLSH_task* tasks) |
||
113 | { |
||
114 | int s; |
||
115 | |||
116 | /* for all static tasks */ |
||
117 | for(s = 0; tasks[s].est != -1; ++s) |
||
118 | { |
||
119 | if(proc_table[s].status == SLSH_READY) |
||
120 | return 0; |
||
121 | } |
||
122 | return -1; |
||
123 | } |
||
124 | |||
125 | /* check if unspecified exists, return 0 if it exists, -1 otherwise */ |
||
1107 | pj | 126 | static int SLSH_T(IQUEUE *unspecified) |
1085 | pj | 127 | { |
1107 | pj | 128 | if(!iq_isempty(unspecified)) |
1085 | pj | 129 | return 0; |
130 | else |
||
131 | return -1; |
||
132 | } |
||
133 | |||
134 | /* return the sc in an interval */ |
||
135 | static int SLSH_sc(SLSH_interval* intervals, int i) |
||
136 | { |
||
137 | return intervals[i].sc; |
||
138 | } |
||
139 | /* return a static task from current interval or a guaranted task */ |
||
140 | static PID SLSH_staticOrGuaranteed(SLSH_level_des* lev) |
||
141 | { |
||
142 | int lowest_dl = 0; /* lowest dl found */ |
||
143 | PID pid = 0; /* static or guaranteed task */ |
||
144 | int t; |
||
145 | |||
146 | /* Decide according to EDF, go through all static & guaranteed tasks */ |
||
147 | for(t = 0; t < MAX_PROC; ++t) |
||
148 | { |
||
149 | /* static tasks */ |
||
150 | if(proc_table[t].pclass == STATIC_PCLASS) |
||
151 | { |
||
152 | /* static task must belong to current interval */ |
||
153 | if(lev->tasks[t].interval == lev->current) |
||
154 | { |
||
155 | /* only ready tasks */ |
||
156 | if(proc_table[t].status == SLSH_READY) |
||
157 | { |
||
158 | /* a new lower dl was found */ |
||
159 | if(lev->tasks[t].dabs < lowest_dl) |
||
160 | { |
||
161 | lowest_dl = lev->tasks[t].dabs; |
||
162 | pid = t; |
||
163 | } |
||
164 | } |
||
165 | } |
||
166 | } /* guaranteed tasks */ |
||
167 | else if(proc_table[t].pclass == HARD_PCLASS) |
||
168 | { |
||
169 | /* only ready tasks */ |
||
170 | if(proc_table[t].status == SLSH_READY) |
||
171 | { |
||
172 | /* a new lower dl was found */ |
||
173 | if(lev->tasks[t].dabs < lowest_dl) |
||
174 | { |
||
175 | lowest_dl = lev->tasks[t].dabs; |
||
176 | pid = t; |
||
177 | } |
||
1123 | pj | 178 | } |
1085 | pj | 179 | } |
180 | }/* for all tasks */ |
||
181 | |||
182 | return pid; |
||
183 | } |
||
184 | |||
185 | /* return a static task among the candidates, all ready statics */ |
||
186 | static PID SLSH_candidates(SLSH_task* tasks) |
||
187 | { |
||
188 | int lowest_dl = 0; |
||
1123 | pj | 189 | PID pid = -1; |
1085 | pj | 190 | int t; |
191 | |||
192 | /* Use the EDL algorithm again to decide which task to run */ |
||
193 | for(t = 0; t < MAX_PROC; ++t) |
||
194 | { |
||
195 | /* only static tasks */ |
||
196 | if(proc_table[t].pclass == STATIC_PCLASS) |
||
197 | { |
||
198 | /* only ready tasks */ |
||
199 | if(proc_table[t].status == SLSH_READY) |
||
200 | { |
||
201 | /* a new lower dl was found */ |
||
202 | if(tasks[t].dabs < lowest_dl) |
||
203 | { |
||
204 | lowest_dl = tasks[t].dabs; |
||
205 | pid = t; |
||
206 | } |
||
207 | }/* all ready tasks */ |
||
208 | }/* all static tasks */ |
||
209 | }/* for all tasks */ |
||
210 | |||
211 | return pid; |
||
212 | } |
||
213 | |||
214 | /* decrease the sc in a interval by amount */ |
||
215 | void SLSH_decSc(SLSH_interval* intervals, int i, int amount) |
||
216 | { |
||
217 | intervals[i].sc -= amount; |
||
218 | } |
||
219 | |||
220 | void SLSH_incSc(SLSH_interval* intervals, int i, int amount) |
||
221 | { |
||
222 | intervals[i].sc += amount; |
||
223 | } |
||
224 | |||
225 | /* swap the sc between intervals, also consider intervals with negative sc */ |
||
226 | void SLSH_swapSc(SLSH_interval* intervals, int current, int task_interval) |
||
227 | { |
||
228 | /* decrease the sc in the current interval */ |
||
229 | SLSH_decSc(intervals, current, 1); |
||
230 | |||
231 | /* update the other interval(s) */ |
||
232 | if(intervals[task_interval].sc < 0) /* negative sc */ |
||
233 | { |
||
234 | /* special case, increase next interval sc by 1 and also current interval (borrowing) */ |
||
235 | if(task_interval == current + 1) |
||
236 | { |
||
237 | SLSH_incSc(intervals, task_interval, 1); |
||
238 | SLSH_incSc(intervals, current, 1); |
||
239 | } |
||
240 | else /* increase every interval sc that is negative between current and task_interval */ |
||
241 | { |
||
242 | while(task_interval > current && intervals[task_interval].sc < 0) |
||
243 | { |
||
244 | SLSH_incSc(intervals, task_interval, 1); |
||
245 | task_interval--; |
||
246 | } |
||
247 | } |
||
248 | } |
||
249 | else /* ordinary swapping */ |
||
250 | SLSH_incSc(intervals, task_interval, 1); |
||
251 | } |
||
252 | |||
253 | /* The scheduler, decides which task to run. */ |
||
1123 | pj | 254 | static PID SLSH_public_scheduler(LEVEL l) |
1085 | pj | 255 | { |
256 | SLSH_level_des* lev = (SLSH_level_des *)(level_table[l]); |
||
257 | PID pid; |
||
258 | |||
259 | /* The scheduler choses among static, guaranteed (hard aperiodic) and |
||
260 | unspecified (soft aperiodic) tasks */ |
||
261 | /* no ready tasks and no sc, execute idle task */ |
||
262 | if(SLSH_R(lev->tasks) == 0 && SLSH_sc(lev->intervals, lev->current) == 0) |
||
263 | return NIL; |
||
264 | /* must execute a static from current intervall or a guaranteed task */ |
||
265 | else if(SLSH_R(lev->tasks) > 0 && SLSH_sc(lev->intervals, lev->current) == 0) |
||
266 | return SLSH_staticOrGuaranteed(lev); |
||
267 | /* sc available... */ |
||
268 | else if(SLSH_R(lev->tasks) > 0 && SLSH_sc(lev->intervals, lev->current) > 0) |
||
269 | { |
||
270 | /* If unspecified exist, execute it according to FIFO order */ |
||
1107 | pj | 271 | if(SLSH_T(&lev->unspecified) == 0) |
1085 | pj | 272 | { |
273 | SLSH_decSc(lev->intervals, lev->current, 1); /* decrease sc by 1 */ |
||
1107 | pj | 274 | return iq_getfirst(&lev->unspecified); |
1085 | pj | 275 | } |
276 | else /* No unspecified, execute task from candidates (statics) */ |
||
277 | { |
||
278 | pid = SLSH_candidates(lev->tasks); |
||
279 | |||
280 | /* sc needs to be swapped */ |
||
281 | if(lev->tasks[pid].interval != lev->current) |
||
282 | SLSH_swapSc(lev->intervals, lev->tasks[pid].interval, lev->current); |
||
283 | |||
284 | return pid; |
||
285 | } |
||
286 | } |
||
287 | |||
288 | kern_printf("(SLSH s)"); |
||
289 | return NIL; |
||
290 | } |
||
291 | |||
292 | /* not used, slot-shifting handles all guarantees itself, it handles all bandwidth */ |
||
1123 | pj | 293 | static int SLSH_public_guarantee(LEVEL l, bandwidth_t *freebandwidth) |
1085 | pj | 294 | { |
295 | *freebandwidth = 0; |
||
296 | return 1; |
||
297 | } |
||
298 | |||
299 | /* get the interval that x is in */ |
||
300 | static int SLSH_getInterval(SLSH_interval* intervals, int x, int last) |
||
301 | { |
||
302 | int i; |
||
303 | |||
304 | /* search through the intervals */ |
||
305 | for(i = 0; i <= last; ++i) |
||
306 | { |
||
307 | /* I is in the interval where start is smaller or equal and end is bigger */ |
||
308 | if(intervals[i].start <= x && x < intervals[i].end) |
||
309 | return i; |
||
310 | } |
||
311 | return -1; |
||
312 | } |
||
313 | |||
314 | /* get the start of the interval I */ |
||
315 | static int SLSH_intervalStart(SLSH_interval* intervals, int I) |
||
316 | { |
||
317 | return intervals[I].start; |
||
318 | } |
||
319 | |||
320 | /* split interval I into two parts, slow because of copying. OBS!!! no check if there is |
||
321 | enough space in the intervals array */ |
||
322 | static void SLSH_splitInterval(SLSH_level_des* lev, int I, int dabs) |
||
323 | { |
||
324 | SLSH_interval left_interval; |
||
325 | int i; |
||
326 | |||
327 | |||
328 | lev->last++; |
||
329 | |||
330 | /* move every interval above and including I */ |
||
331 | for(i = lev->last; i > I; --i) |
||
332 | memcpy(&lev->intervals[i], &lev->intervals[i - 1], sizeof(SLSH_interval)); |
||
333 | |||
334 | /* Left interval start, end and length */ |
||
335 | left_interval.start = lev->intervals[I].start; |
||
336 | left_interval.end = dabs; |
||
337 | left_interval.length = left_interval.end - left_interval.start; |
||
338 | |||
339 | /* Right interval (uses old interval struct) start and length end remains as the old value */ |
||
340 | lev->intervals[I + 1].start = dabs; |
||
341 | lev->intervals[I + 1].length = lev->intervals[I + 1].end - lev->intervals[I + 1].start; |
||
342 | |||
343 | /* check if sc still exists in the right interval */ |
||
344 | if(lev->intervals[I + 1].length - lev->intervals[I + 1].maxt > 0) |
||
345 | { |
||
346 | lev->intervals[I + 1].sc = lev->intervals[I + 1].length - lev->intervals[I + 1].maxt; |
||
347 | left_interval.sc = left_interval.length; /* the whole interval is free, for now... */ |
||
348 | } |
||
349 | else /* no sc in the right interval */ |
||
350 | { |
||
351 | lev->intervals[I + 1].maxt = lev->intervals[I + 1].length; |
||
352 | left_interval.sc = lev->intervals[I + 1].sc; /* all sc in left interval */ |
||
353 | lev->intervals[I + 1].sc = 0; |
||
354 | } |
||
355 | |||
356 | /* insert the new interval */ |
||
357 | memcpy(&lev->intervals[I], &left_interval, sizeof(SLSH_interval)); |
||
358 | } |
||
359 | |||
360 | /* Reduce the sc from back to front by the wcet amount, interval splitting may be neccesary */ |
||
361 | static void SLSH_updateSc(SLSH_level_des* lev, HARD_TASK_MODEL* h) |
||
362 | { |
||
363 | int dabs = ceil((lev->slot + h->drel)/lev->slot_length); /* absolute deadline of request */ |
||
364 | int dabs_interval = SLSH_getInterval(lev->intervals, dabs, lev->last); /* interval where dabs is */ |
||
365 | int C = ceil(h->wcet/lev->slot_length); /* amount of sc to reduce */ |
||
366 | int sc = 0; |
||
367 | int i; |
||
368 | |||
369 | /* check if interval splitting is neccesary */ |
||
370 | if(lev->intervals[dabs_interval].end != dabs) |
||
371 | SLSH_splitInterval(lev, dabs_interval, dabs); |
||
372 | |||
373 | /* decrease sc in all intervals that are neccesary from dabs_interval o current */ |
||
374 | for(i = dabs_interval; i >= lev->current && C > 0; --i) |
||
375 | { |
||
376 | if((sc = SLSH_sc(lev->intervals, i)) >= 0) /* only decrease where sc exists */ |
||
377 | { |
||
378 | if(sc > C) /* the last sc dec */ |
||
379 | { |
||
380 | SLSH_decSc(lev->intervals, i, C); |
||
381 | C = 0; |
||
382 | } |
||
383 | else /* to little sc in this interval, decrease it to 0 */ |
||
384 | { |
||
385 | C -= SLSH_sc(lev->intervals, i); |
||
386 | SLSH_decSc(lev->intervals, i, SLSH_sc(lev->intervals, i)); |
||
387 | } |
||
388 | } |
||
389 | }/* for all intervals */ |
||
390 | } |
||
391 | |||
392 | /* the guarantee algorithm for hard aperiodic requests */ |
||
393 | static int SLSH_guarantee(SLSH_level_des* lev, HARD_TASK_MODEL* h) |
||
394 | { |
||
395 | int total_sc = 0; |
||
396 | int temp, i; |
||
397 | int dabs = ceil((lev->slot + h->drel)/lev->slot_length); /* absolute deadline of request */ |
||
398 | int dabs_interval = SLSH_getInterval(lev->intervals, dabs, lev->last); /* interval where dabs is */ |
||
399 | |||
400 | /* check if the sc up until request deadline is >= request wcet */ |
||
401 | /* 1. the sc of the current interal */ |
||
402 | total_sc = SLSH_sc(lev->intervals, lev->current); |
||
403 | |||
404 | /* 2. the sc for all whole intervals between current and the interval |
||
405 | with the request deadline */ |
||
406 | for(i = (lev->current) + 1; i < dabs_interval; ++i) |
||
407 | { |
||
408 | if((temp = SLSH_sc(lev->intervals, i)) > 0) |
||
409 | total_sc += temp; |
||
410 | } |
||
411 | |||
412 | /* 3. the min of sc or the execution need in the last interval */ |
||
413 | total_sc += min(SLSH_sc(lev->intervals, dabs_interval), |
||
414 | dabs - SLSH_intervalStart(lev->intervals, |
||
415 | dabs_interval)); |
||
416 | |||
417 | if(total_sc >= h->wcet) |
||
418 | { /* update the sc in the intervals from back to front */ |
||
419 | SLSH_updateSc(lev, h); |
||
420 | return 0; |
||
421 | } |
||
422 | else |
||
423 | return -1; |
||
424 | } |
||
425 | |||
426 | /* check if task model is accepted and store nessecary parameters */ |
||
1123 | pj | 427 | static int SLSH_public_create(LEVEL l, PID p, TASK_MODEL *m) |
1085 | pj | 428 | { |
429 | SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]); |
||
430 | STATIC_TASK_MODEL* s; |
||
431 | HARD_TASK_MODEL* h; |
||
432 | SOFT_TASK_MODEL* u; |
||
433 | |||
1123 | pj | 434 | |
435 | /* Check the models */ |
||
436 | switch(m->pclass) |
||
437 | { |
||
438 | case STATIC_PCLASS: /* offline scheduled tasks */ |
||
439 | break; |
||
440 | case HARD_PCLASS: /* hard aperiodic tasks */ |
||
441 | h = (HARD_TASK_MODEL *) m; |
||
442 | if (h->drel == 0 || h->wcet == 0) /* must be set */ |
||
443 | return -1; |
||
444 | break; |
||
445 | case SOFT_PCLASS: /* soft aperiodic tasks */ |
||
446 | u = (SOFT_TASK_MODEL *) m; |
||
447 | if(u->wcet == 0) /* must be set */ |
||
448 | return -1; |
||
449 | break; |
||
450 | default: |
||
451 | return -1; |
||
452 | } |
||
453 | |||
454 | |||
1085 | pj | 455 | /* if the SLSH_task_create is called, then the pclass must be a |
456 | valid pclass. Slot-shifting accepts STATIC_TASK, HARD_TASK |
||
457 | and SOFT_TASK models with some restrictions */ |
||
458 | |||
459 | /* est, dl and wcet is saved in slotlengths */ |
||
460 | switch(m->pclass) |
||
461 | { |
||
462 | case STATIC_PCLASS: /* offline scheduled tasks */ |
||
463 | s = (STATIC_TASK_MODEL *) m; |
||
464 | lev->tasks[p].est = ceil(s->est/lev->slot_length); |
||
465 | lev->tasks[p].dabs = ceil(s->dabs/lev->slot_length); |
||
466 | lev->tasks[p].interval = s->interval; |
||
467 | proc_table[p].avail_time = s->wcet; |
||
468 | proc_table[p].wcet = s->wcet; |
||
469 | break; |
||
470 | case HARD_PCLASS: /* hard aperiodic tasks */ |
||
471 | h = (HARD_TASK_MODEL *) m; |
||
472 | if(SLSH_guarantee(lev, h) == 0) |
||
473 | { |
||
474 | /* convert drel to dabs */ |
||
475 | lev->tasks[p].dabs = ceil((lev->slot + h->drel)/lev->slot_length); |
||
476 | proc_table[p].avail_time = h->wcet; |
||
477 | proc_table[p].wcet = h->wcet; |
||
478 | } |
||
479 | else /* task not guaranteed */ |
||
480 | return -1; |
||
481 | break; |
||
482 | case SOFT_PCLASS: |
||
483 | u = (SOFT_TASK_MODEL *) m; |
||
484 | proc_table[p].avail_time = u->wcet; |
||
485 | proc_table[p].wcet = u->wcet; |
||
1107 | pj | 486 | iq_insertlast(p, &lev->unspecified); /* respect FIFO order */ |
1085 | pj | 487 | break; |
488 | default: /* a task model not supported */ |
||
489 | return -1; |
||
490 | } |
||
491 | /* enable wcet check in the kernel */ |
||
492 | proc_table[p].control |= CONTROL_CAP; |
||
493 | |||
494 | return 0; |
||
495 | } |
||
496 | |||
497 | /************* The slot end event handler *************/ |
||
498 | static void SLSH_slot_end(void* p) |
||
499 | { |
||
500 | SLSH_level_des* lev = (SLSH_level_des *) p; |
||
501 | PID pid; |
||
502 | int i; |
||
503 | |||
504 | /* increase slot "time" by 1 */ |
||
505 | if(lev->slot < lev->LCM) |
||
506 | { |
||
507 | lev->slot++; |
||
508 | /* check if new statics are ready */ |
||
509 | for(i = 0; lev->tasks[i].interval != -1; ++i) |
||
510 | { |
||
511 | if(lev->tasks[i].est <= lev->slot && proc_table[i].status == SLSH_WAIT) |
||
512 | proc_table[i].status = SLSH_READY; |
||
513 | } |
||
514 | |||
515 | /* check if current (interval) needs updating */ |
||
516 | if(lev->current < SLSH_getInterval(lev->intervals, lev->slot, lev->last)) |
||
517 | lev->current++; |
||
518 | |||
519 | } |
||
520 | else /* restart from the beginning of the offline schedule */ |
||
521 | { |
||
522 | lev->slot = 0; |
||
523 | |||
1107 | pj | 524 | while((pid = iq_getfirst(&lev->idle_statics)) != NIL) |
1085 | pj | 525 | { |
526 | if(lev->tasks[pid].est <= lev->slot) |
||
527 | proc_table[pid].status = SLSH_READY; |
||
528 | else |
||
529 | proc_table[pid].status = SLSH_WAIT; |
||
530 | } |
||
531 | } |
||
532 | |||
533 | /* call for a rescheduling, reset event flag and increase slot by 1 */ |
||
534 | lev->slot_event = -1; |
||
535 | kern_printf("*"); |
||
536 | event_need_reschedule(); |
||
537 | } |
||
538 | |||
539 | /* when a task becomes executing (EXE status) */ |
||
1123 | pj | 540 | static void SLSH_public_dispatch(LEVEL l, PID pid, int nostop) |
1085 | pj | 541 | { |
542 | SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]); |
||
543 | struct timespec t; |
||
544 | |||
545 | /* the task state is set EXE by the scheduler() |
||
546 | we extract the task from the unspecified queue. |
||
547 | NB: we can't assume that p is the first task in the queue!!! */ |
||
548 | |||
549 | if(proc_table[pid].pclass == SOFT_PCLASS) |
||
1107 | pj | 550 | iq_extract(pid, &lev->unspecified); |
1085 | pj | 551 | |
552 | /* also start the timer for one slot length */ |
||
553 | lev->slot_event = kern_event_post(&TIME2TIMESPEC(lev->slot_length, t), |
||
554 | SLSH_slot_end, (void*) lev); |
||
555 | } |
||
556 | |||
557 | /* called when task is moved from EXE status */ |
||
1123 | pj | 558 | static void SLSH_public_epilogue(LEVEL l, PID pid) |
1085 | pj | 559 | { |
560 | SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]); |
||
561 | |||
562 | /* check if the wcet is finished... */ |
||
563 | if (proc_table[pid].avail_time <= 0) |
||
564 | { |
||
565 | /* if it is, raise a XWCET_VIOLATION exception */ |
||
566 | kern_raise(XWCET_VIOLATION, pid); |
||
567 | proc_table[pid].status = SLSH_WCET_VIOLATED; |
||
568 | } |
||
569 | else /* the end of a slot. the task returns into the ready queue... */ |
||
570 | { |
||
571 | if(proc_table[pid].pclass == SOFT_PCLASS) |
||
1107 | pj | 572 | iq_insertfirst(pid,&lev->unspecified); |
1085 | pj | 573 | |
574 | proc_table[pid].status = SLSH_READY; |
||
575 | } |
||
576 | } |
||
577 | |||
578 | /* when task go from SLEEP to SLSH_READY or SLSH_WAIT */ |
||
1123 | pj | 579 | static void SLSH_public_activate(LEVEL l, PID pid) |
1085 | pj | 580 | { |
581 | SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]); |
||
582 | WORD type = proc_table[pid].pclass; |
||
583 | |||
584 | /* Test if we are trying to activate a non sleeping task */ |
||
585 | /* Ignore this; the task is already active */ |
||
586 | if (proc_table[pid].status != SLEEP && proc_table[pid].status != SLSH_WCET_VIOLATED) |
||
587 | return; |
||
588 | |||
589 | /* make task ready or waiting, dependong on slot (the time) for static tasks only*/ |
||
590 | if(type == STATIC_PCLASS && lev->tasks[pid].est <= lev->slot) |
||
591 | proc_table[pid].status = SLSH_READY; |
||
592 | else |
||
593 | proc_table[pid].status = SLSH_WAIT; |
||
594 | |||
595 | if(type == HARD_PCLASS) |
||
596 | proc_table[pid].status = SLSH_READY; |
||
597 | |||
598 | /* insert unspecified tasks in QQUEUE and make it ready */ |
||
599 | if(type == SOFT_PCLASS) |
||
600 | { |
||
1107 | pj | 601 | iq_insertlast(pid ,&lev->unspecified); |
1085 | pj | 602 | proc_table[pid].status = SLSH_READY; |
603 | } |
||
604 | } |
||
605 | |||
606 | /* when a task i returned to module from a semaphore, mutex ... */ |
||
1123 | pj | 607 | static void SLSH_public_unblock(LEVEL l, PID pid) |
1085 | pj | 608 | { |
609 | SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]); |
||
610 | |||
611 | /* change staus of task */ |
||
612 | proc_table[pid].status = SLSH_READY; |
||
613 | |||
614 | if(proc_table[pid].pclass == SOFT_PCLASS) |
||
1107 | pj | 615 | iq_insertfirst(pid ,&lev->unspecified); |
1085 | pj | 616 | } |
617 | |||
618 | /* when a semaphore, mutex ... taskes a task from module */ |
||
1123 | pj | 619 | static void SLSH_public_block(LEVEL l, PID pid) |
1085 | pj | 620 | { |
621 | /* Extract the running task from the level |
||
622 | . we have already extract it from the ready queue at the dispatch time. |
||
623 | . the capacity event have to be removed by the generic kernel |
||
624 | . the wcet don't need modification... |
||
625 | . the state of the task is set by the calling function |
||
626 | . the deadline must remain... |
||
627 | |||
628 | So, we do nothing!!! |
||
629 | */ |
||
630 | } |
||
631 | |||
632 | /* the task has finihed its wcet, kill task (dont kill static tasks) */ |
||
1123 | pj | 633 | static void SLSH_public_end(LEVEL l, PID pid) |
1085 | pj | 634 | { |
635 | SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]); |
||
636 | |||
637 | if(proc_table[pid].pclass == SOFT_PCLASS) |
||
638 | { |
||
639 | if (proc_table[pid].status == SLSH_READY) |
||
1107 | pj | 640 | iq_extract(pid, &lev->unspecified); |
1085 | pj | 641 | } |
642 | else if(proc_table[pid].pclass == HARD_PCLASS) |
||
643 | { |
||
644 | if (proc_table[pid].status == SLSH_READY) |
||
645 | lev->tasks[pid].dabs = 0; |
||
646 | |||
647 | } |
||
648 | /* static tasks: put them in idle QUEUE, reset status and avail_time */ |
||
649 | else if(proc_table[pid].pclass == STATIC_PCLASS) |
||
650 | { |
||
651 | proc_table[pid].avail_time = proc_table[pid].wcet; |
||
652 | proc_table[pid].status = SLSH_IDLE; |
||
1107 | pj | 653 | iq_priority_insert(pid, &lev->idle_statics); |
1085 | pj | 654 | } |
655 | |||
656 | proc_table[pid].status = FREE; |
||
657 | } |
||
658 | |||
659 | /* called when a task should sleep but not execute for awhile, mabe a mode change */ |
||
1123 | pj | 660 | //static void SLSH_task_sleep(LEVEL l, PID pid) |
661 | //{ |
||
662 | // |
||
663 | // /* the task has terminated his job before it consume the wcet. All OK! */ |
||
664 | // proc_table[pid].status = SLEEP; |
||
665 | // |
||
666 | // /* we reset the capacity counters... only for static tasks */ |
||
667 | // if (proc_table[pid].pclass == STATIC_PCLASS) |
||
668 | // proc_table[pid].avail_time = proc_table[pid].wcet; |
||
669 | // |
||
670 | //} |
||
1085 | pj | 671 | |
672 | |||
673 | /** Guest Functions, slot shifing accepts no guests, so all generates exceptions **/ |
||
674 | |||
675 | /******* Registration functions *******/ |
||
676 | |||
677 | /*+ Registration function: */ |
||
1123 | pj | 678 | LEVEL SLSH_register_level() |
1085 | pj | 679 | { |
680 | LEVEL l; /* the level that we register */ |
||
681 | SLSH_level_des *lev; /* for readableness only */ |
||
682 | PID i; /* a counter */ |
||
683 | |||
684 | kern_printf("SLSH_register_level\n"); |
||
685 | |||
1123 | pj | 686 | /* request an entry in the level_table */ |
687 | l = level_alloc_descriptor(sizeof(SLSH_level_des)); |
||
1085 | pj | 688 | |
1123 | pj | 689 | lev = (SLSH_level_des *)level_table[l]; |
1085 | pj | 690 | |
1123 | pj | 691 | printk(" lev=%d\n",(int)lev); |
1085 | pj | 692 | |
1123 | pj | 693 | /* fill the standard descriptor */ |
694 | lev->l.public_scheduler = SLSH_public_scheduler; |
||
695 | lev->l.public_guarantee = SLSH_public_guarantee; |
||
696 | lev->l.public_create = SLSH_public_create; |
||
697 | lev->l.public_end = SLSH_public_end; |
||
698 | lev->l.public_dispatch = SLSH_public_dispatch; |
||
699 | lev->l.public_epilogue = SLSH_public_epilogue; |
||
700 | lev->l.public_activate = SLSH_public_activate; |
||
701 | lev->l.public_unblock = SLSH_public_unblock; |
||
702 | lev->l.public_block = SLSH_public_block; |
||
1085 | pj | 703 | |
704 | /* fill the SLSH descriptor part */ |
||
705 | for(i = 0; i < MAX_PROC; i++) |
||
706 | { |
||
707 | lev->tasks[i].est = -1; |
||
708 | lev->tasks[i].dabs = 0; |
||
709 | lev->tasks[i].interval = -1; |
||
710 | } |
||
711 | |||
712 | for(i = 0; i < MAX_INTERVALS; i++) |
||
713 | { |
||
714 | lev->intervals[i].start = -1; |
||
715 | lev->intervals[i].end = -1; |
||
716 | lev->intervals[i].length = 0; |
||
717 | lev->intervals[i].maxt = 0; |
||
718 | lev->intervals[i].sc = 0; |
||
719 | } |
||
720 | |||
721 | lev->current = 0; |
||
722 | lev->last = NIL; |
||
723 | lev->slot = 0; |
||
724 | lev->slot_length = 0; |
||
725 | lev->slot_event = -1; |
||
1123 | pj | 726 | |
727 | return l; |
||
1085 | pj | 728 | } |
729 | |||
730 | |||
731 | void SLSH_set_interval(LEVEL l, int start, int end, int maxt) |
||
732 | { |
||
733 | SLSH_level_des* lev = (SLSH_level_des *)(level_table[l]); |
||
734 | static int i = -1; |
||
735 | |||
736 | i++; |
||
737 | lev->intervals[i].start = start; |
||
738 | lev->intervals[i].end = end; |
||
739 | lev->intervals[i].length = end - start; |
||
740 | lev->intervals[i].maxt = maxt; |
||
741 | lev->intervals[i].sc = lev->intervals[i].length - maxt; |
||
742 | |||
743 | lev->last = i; |
||
744 | } |
||
745 | |||
746 | void SLSH_set_variables(LEVEL l, TIME length) |
||
747 | { |
||
748 | SLSH_level_des* lev = (SLSH_level_des *)(level_table[l]); |
||
749 | |||
750 | lev->slot_length = length; |
||
751 | } |