Rev 29 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
2 | 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 | ------------ |
||
38 | pj | 23 | CVS : $Id: ds.c,v 1.4 2003-01-07 17:07:50 pj Exp $ |
2 | pj | 24 | |
25 | File: $File$ |
||
38 | pj | 26 | Revision: $Revision: 1.4 $ |
27 | Last update: $Date: 2003-01-07 17:07:50 $ |
||
2 | pj | 28 | ------------ |
29 | |||
30 | This file contains the aperiodic server DS (Deferrable Server) |
||
31 | |||
32 | This module is directly derived from the Polling server one. |
||
33 | All the notes writed for the PS are valid for the DS. |
||
34 | |||
35 | The difference between DS and PS is that when there are not task to |
||
36 | schedule the capacity is not reset to 0... |
||
37 | |||
38 | **/ |
||
39 | |||
40 | /* |
||
41 | * Copyright (C) 2000 Paolo Gai |
||
42 | * |
||
43 | * This program is free software; you can redistribute it and/or modify |
||
44 | * it under the terms of the GNU General Public License as published by |
||
45 | * the Free Software Foundation; either version 2 of the License, or |
||
46 | * (at your option) any later version. |
||
47 | * |
||
48 | * This program is distributed in the hope that it will be useful, |
||
49 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
50 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
||
51 | * GNU General Public License for more details. |
||
52 | * |
||
53 | * You should have received a copy of the GNU General Public License |
||
54 | * along with this program; if not, write to the Free Software |
||
55 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
||
56 | * |
||
57 | */ |
||
58 | |||
59 | |||
60 | #include <modules/ds.h> |
||
61 | #include <ll/stdio.h> |
||
62 | #include <ll/string.h> |
||
63 | #include <kernel/model.h> |
||
64 | #include <kernel/descr.h> |
||
65 | #include <kernel/var.h> |
||
66 | #include <kernel/func.h> |
||
38 | pj | 67 | #include <kernel/trace.h> |
2 | pj | 68 | |
69 | /*+ Status used in the level +*/ |
||
70 | #define DS_WAIT APER_STATUS_BASE /*+ waiting the service +*/ |
||
71 | |||
72 | /*+ the level redefinition for the Total Bandwidth Server level +*/ |
||
73 | typedef struct { |
||
74 | level_des l; /*+ the standard level descriptor +*/ |
||
75 | |||
76 | /* The wcet are stored in the task descriptor's priority |
||
77 | field, so no other fields are needed */ |
||
78 | |||
79 | int nact[MAX_PROC]; /*+ number of pending activations +*/ |
||
80 | |||
81 | struct timespec lastdline; /*+ the last deadline assigned to |
||
82 | a DS task +*/ |
||
83 | |||
84 | int Cs; /*+ server capacity +*/ |
||
85 | int availCs; /*+ server avail time +*/ |
||
86 | |||
29 | pj | 87 | IQUEUE wait; /*+ the wait queue of the DS +*/ |
2 | pj | 88 | PID activated; /*+ the task inserted in another queue +*/ |
89 | |||
90 | int flags; /*+ the init flags... +*/ |
||
91 | |||
92 | bandwidth_t U; /*+ the used bandwidth by the server +*/ |
||
93 | int period; |
||
94 | |||
95 | LEVEL scheduling_level; |
||
96 | |||
97 | } DS_level_des; |
||
98 | |||
99 | /* This static function activates the task pointed by lev->activated) */ |
||
100 | static __inline__ void DS_activation(DS_level_des *lev) |
||
101 | { |
||
102 | PID p; /* for readableness */ |
||
103 | JOB_TASK_MODEL j; /* the guest model */ |
||
104 | LEVEL m; /* the master level... only for readableness*/ |
||
105 | |||
106 | p = lev->activated; |
||
107 | m = lev->scheduling_level; |
||
108 | job_task_default_model(j,lev->lastdline); |
||
109 | job_task_def_period(j,lev->period); |
||
38 | pj | 110 | level_table[m]->private_insert(m,p,(TASK_MODEL *)&j); |
2 | pj | 111 | // kern_printf("(%d %d)",lev->lastdline.tv_sec,lev->lastdline.tv_nsec); |
112 | } |
||
113 | |||
114 | static void DS_deadline_timer(void *a) |
||
115 | { |
||
116 | DS_level_des *lev = (DS_level_des *)(level_table[(LEVEL)a]); |
||
117 | |||
118 | ADDUSEC2TIMESPEC(lev->period, &lev->lastdline); |
||
119 | |||
120 | // kern_printf("(%d:%d %d)",lev->lastdline.tv_sec,lev->lastdline.tv_nsec, lev->period); |
||
121 | if (lev->availCs >= 0) |
||
122 | lev->availCs = lev->Cs; |
||
123 | else |
||
124 | lev->availCs += lev->Cs; |
||
125 | |||
126 | /* availCs may be <0 because a task executed via a shadow fo many time |
||
127 | lev->activated == NIL only if the prec task was finished and there |
||
128 | was not any other task to be put in the ready queue |
||
129 | ... we are now activating the next task */ |
||
130 | if (lev->availCs > 0 && lev->activated == NIL) { |
||
29 | pj | 131 | if (iq_query_first(&lev->wait) != NIL) { |
132 | lev->activated = iq_getfirst(&lev->wait); |
||
2 | pj | 133 | DS_activation(lev); |
134 | event_need_reschedule(); |
||
135 | } |
||
136 | } |
||
137 | |||
138 | kern_event_post(&lev->lastdline, DS_deadline_timer, a); |
||
139 | // kern_printf("!"); |
||
140 | } |
||
141 | |||
38 | pj | 142 | static PID DS_public_schedulerbackground(LEVEL l) |
2 | pj | 143 | { |
144 | /* the DS catch the background time to exec aperiodic activities */ |
||
145 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
146 | |||
147 | lev->flags |= DS_BACKGROUND; |
||
148 | |||
149 | if (lev->flags & DS_BACKGROUND_BLOCK) |
||
150 | return NIL; |
||
151 | else |
||
29 | pj | 152 | return iq_query_first(&lev->wait); |
2 | pj | 153 | } |
154 | |||
155 | /* The on-line guarantee is enabled only if the appropriate flag is set... */ |
||
38 | pj | 156 | static int DS_public_guaranteeEDF(LEVEL l, bandwidth_t *freebandwidth) |
2 | pj | 157 | { |
158 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
159 | |||
160 | if (*freebandwidth >= lev->U) { |
||
161 | *freebandwidth -= lev->U; |
||
162 | return 1; |
||
163 | } |
||
164 | else |
||
165 | return 0; |
||
166 | } |
||
167 | |||
38 | pj | 168 | static int DS_public_guaranteeRM(LEVEL l, bandwidth_t *freebandwidth) |
2 | pj | 169 | { |
170 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
171 | |||
172 | if (*freebandwidth > lev->U + RM_MINFREEBANDWIDTH) { |
||
173 | *freebandwidth -= lev->U; |
||
174 | return 1; |
||
175 | } |
||
176 | else |
||
177 | return 0; |
||
178 | } |
||
179 | |||
38 | pj | 180 | static int DS_public_create(LEVEL l, PID p, TASK_MODEL *m) |
2 | pj | 181 | { |
182 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
183 | |||
38 | pj | 184 | SOFT_TASK_MODEL *s; |
2 | pj | 185 | |
38 | pj | 186 | if (m->pclass != SOFT_PCLASS) return -1; |
187 | if (m->level != 0 && m->level != l) return -1; |
||
188 | s = (SOFT_TASK_MODEL *)m; |
||
189 | if (s->periodicity != APERIODIC) return -1; |
||
190 | |||
191 | s = (SOFT_TASK_MODEL *)m; |
||
192 | |||
2 | pj | 193 | if (s->arrivals == SAVE_ARRIVALS) |
194 | lev->nact[p] = 0; |
||
195 | else |
||
196 | lev->nact[p] = -1; |
||
197 | |||
198 | return 0; /* OK, also if the task cannot be guaranteed... */ |
||
199 | } |
||
200 | |||
38 | pj | 201 | static void DS_public_dispatch(LEVEL l, PID p, int nostop) |
2 | pj | 202 | { |
203 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
204 | struct timespec ty; |
||
205 | |||
206 | // if (nostop) kern_printf("NOSTOP!!!!!!!!!!!!"); |
||
207 | /* there is at least one task ready inserted in an EDF or similar |
||
208 | level note that we can't check the status because the scheduler set it |
||
209 | to exe before calling task_dispatch. we have to check |
||
210 | lev->activated != p instead */ |
||
211 | if (lev->activated != p) { |
||
29 | pj | 212 | iq_extract(p, &lev->wait); |
2 | pj | 213 | //kern_printf("#%d#",p); |
214 | } |
||
215 | else { |
||
216 | //if (nostop) kern_printf("(gd status=%d)",proc_table[p].status); |
||
217 | level_table[ lev->scheduling_level ]-> |
||
38 | pj | 218 | private_dispatch(lev->scheduling_level,p,nostop); |
2 | pj | 219 | } |
220 | |||
221 | /* set the capacity timer */ |
||
222 | if (!nostop) { |
||
223 | TIMESPEC_ASSIGN(&ty, &schedule_time); |
||
224 | ADDUSEC2TIMESPEC(lev->availCs,&ty); |
||
225 | cap_timer = kern_event_post(&ty, capacity_timer, NULL); |
||
226 | } |
||
227 | |||
228 | // kern_printf("(disp %d %d)",ty.tv_sec, ty.tv_nsec); |
||
229 | } |
||
230 | |||
38 | pj | 231 | static void DS_public_epilogue(LEVEL l, PID p) |
2 | pj | 232 | { |
233 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
234 | struct timespec ty; |
||
235 | TIME tx; |
||
236 | |||
237 | /* update the server capacity */ |
||
238 | if (lev->flags & DS_BACKGROUND) |
||
239 | lev->flags &= ~DS_BACKGROUND; |
||
240 | else { |
||
241 | SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty); |
||
242 | tx = TIMESPEC2USEC(&ty); |
||
243 | lev->availCs -= tx; |
||
244 | } |
||
245 | |||
246 | // kern_printf("(epil %d %d)",lev->availCs, proc_table[p].avail_time); |
||
247 | |||
248 | /* check if the server capacity is finished... */ |
||
249 | if (lev->availCs < 0) { |
||
250 | // kern_printf("(epil Cs%d %d:%d act%d p%d)", |
||
251 | // lev->availCs,proc_table[p].timespec_priority.tv_sec, |
||
252 | // proc_table[p].timespec_priority.tv_nsec, |
||
253 | // lev->activated,p); |
||
254 | /* the server slice has finished... do the task_end!!! |
||
255 | a first version of the module used the task_endcycle, but it was |
||
256 | not conceptually correct because the task didn't stop because it |
||
257 | finished all the work but because the server didn't have budget! |
||
258 | So, if the task_endcycle is called, the task remain into the |
||
259 | master level, and we can't wake him up if, for example, another |
||
260 | task point the shadow to it!!!*/ |
||
261 | if (lev->activated == p) |
||
262 | level_table[ lev->scheduling_level ]-> |
||
38 | pj | 263 | private_extract(lev->scheduling_level,p); |
29 | pj | 264 | iq_insertfirst(p, &lev->wait); |
2 | pj | 265 | proc_table[p].status = DS_WAIT; |
266 | lev->activated = NIL; |
||
267 | } |
||
268 | else |
||
269 | /* the task has been preempted. it returns into the ready queue or to the |
||
270 | wait queue by calling the guest_epilogue... */ |
||
271 | if (lev->activated == p) {//kern_printf("Û1"); |
||
272 | level_table[ lev->scheduling_level ]-> |
||
38 | pj | 273 | private_epilogue(lev->scheduling_level,p); |
2 | pj | 274 | } else { //kern_printf("Û2"); |
29 | pj | 275 | iq_insertfirst(p, &lev->wait); |
2 | pj | 276 | proc_table[p].status = DS_WAIT; |
277 | } |
||
278 | } |
||
279 | |||
38 | pj | 280 | static void DS_public_activate(LEVEL l, PID p) |
2 | pj | 281 | { |
282 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
283 | |||
284 | if (lev->activated == p || proc_table[p].status == DS_WAIT) { |
||
285 | if (lev->nact[p] != -1) |
||
286 | lev->nact[p]++; |
||
287 | } |
||
288 | else if (proc_table[p].status == SLEEP) { |
||
289 | |||
290 | if (lev->activated == NIL && lev->availCs > 0) { |
||
291 | lev->activated = p; |
||
292 | DS_activation(lev); |
||
293 | } |
||
294 | else { |
||
29 | pj | 295 | iq_insertlast(p, &lev->wait); |
2 | pj | 296 | proc_table[p].status = DS_WAIT; |
297 | } |
||
298 | } |
||
299 | else |
||
300 | { kern_printf("DS_REJ%d %d %d %d ",p, proc_table[p].status, lev->activated, lev->wait.first); |
||
301 | return; } |
||
302 | |||
303 | } |
||
304 | |||
38 | pj | 305 | static void DS_public_unblock(LEVEL l, PID p) |
2 | pj | 306 | { |
307 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
308 | |||
309 | lev->flags &= ~DS_BACKGROUND_BLOCK; |
||
310 | |||
311 | lev->activated = -1; |
||
312 | |||
313 | /* when we reinsert the task into the system, the server capacity |
||
314 | is always 0 because nobody executes with the DS before... */ |
||
29 | pj | 315 | iq_insertfirst(p, &lev->wait); |
2 | pj | 316 | proc_table[p].status = DS_WAIT; |
317 | } |
||
318 | |||
38 | pj | 319 | static void DS_public_block(LEVEL l, PID p) |
2 | pj | 320 | { |
321 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
322 | |||
323 | /* update the server capacity */ |
||
324 | lev->availCs = 0; |
||
325 | |||
326 | lev->flags |= DS_BACKGROUND_BLOCK; |
||
327 | |||
328 | if (lev->activated == p) |
||
329 | level_table[ lev->scheduling_level ]-> |
||
38 | pj | 330 | private_extract(lev->scheduling_level,p); |
2 | pj | 331 | } |
332 | |||
38 | pj | 333 | static int DS_public_message(LEVEL l, PID p, void *m) |
2 | pj | 334 | { |
335 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
336 | struct timespec ty; |
||
337 | TIME tx; |
||
338 | |||
339 | /* update the server capacity */ |
||
340 | if (lev->flags & DS_BACKGROUND) |
||
341 | lev->flags &= ~DS_BACKGROUND; |
||
342 | else { |
||
343 | SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty); |
||
344 | tx = TIMESPEC2USEC(&ty); |
||
345 | lev->availCs -= tx; |
||
346 | } |
||
347 | |||
348 | if (lev->activated == p) |
||
349 | level_table[ lev->scheduling_level ]-> |
||
38 | pj | 350 | private_extract(lev->scheduling_level,p); |
2 | pj | 351 | else |
29 | pj | 352 | iq_extract(p, &lev->wait); |
2 | pj | 353 | |
354 | if (lev->nact[p] > 0) |
||
355 | { |
||
356 | lev->nact[p]--; |
||
29 | pj | 357 | iq_insertlast(p, &lev->wait); |
2 | pj | 358 | proc_table[p].status = DS_WAIT; |
359 | } |
||
360 | else |
||
361 | proc_table[p].status = SLEEP; |
||
362 | |||
29 | pj | 363 | lev->activated = iq_getfirst(&lev->wait); |
2 | pj | 364 | if (lev->activated != NIL) |
365 | DS_activation(lev); |
||
38 | pj | 366 | |
367 | jet_update_endcycle(); /* Update the Jet data... */ |
||
368 | trc_logevent(TRC_ENDCYCLE,&exec_shadow); /* tracer stuff */ |
||
369 | |||
370 | return 0; |
||
2 | pj | 371 | } |
372 | |||
38 | pj | 373 | static void DS_public_end(LEVEL l, PID p) |
2 | pj | 374 | { |
375 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
376 | struct timespec ty; |
||
377 | TIME tx; |
||
378 | |||
379 | /* update the server capacity */ |
||
380 | if (lev->flags & DS_BACKGROUND) |
||
381 | lev->flags &= ~DS_BACKGROUND; |
||
382 | else { |
||
383 | SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty); |
||
384 | tx = TIMESPEC2USEC(&ty); |
||
385 | lev->availCs -= tx; |
||
386 | } |
||
387 | |||
388 | if (lev->activated == p) |
||
389 | level_table[ lev->scheduling_level ]-> |
||
38 | pj | 390 | private_extract(lev->scheduling_level,p); |
2 | pj | 391 | |
392 | proc_table[p].status = FREE; |
||
29 | pj | 393 | iq_insertfirst(p,&freedesc); |
2 | pj | 394 | |
29 | pj | 395 | lev->activated = iq_getfirst(&lev->wait); |
2 | pj | 396 | if (lev->activated != NIL) |
397 | DS_activation(lev); |
||
398 | } |
||
399 | |||
400 | /* Registration functions */ |
||
401 | |||
402 | |||
403 | /*+ This init function install the DS deadline timer |
||
404 | +*/ |
||
405 | static void DS_dline_install(void *l) |
||
406 | { |
||
407 | DS_level_des *lev = (DS_level_des *)(level_table[(LEVEL)l]); |
||
408 | |||
38 | pj | 409 | kern_gettime(&lev->lastdline); |
2 | pj | 410 | ADDUSEC2TIMESPEC(lev->period, &lev->lastdline); |
411 | |||
412 | kern_event_post(&lev->lastdline, DS_deadline_timer, l); |
||
413 | } |
||
414 | |||
415 | |||
416 | |||
417 | /*+ Registration function: |
||
418 | int flags the init flags ... see DS.h +*/ |
||
38 | pj | 419 | LEVEL DS_register_level(int flags, LEVEL master, int Cs, int per) |
2 | pj | 420 | { |
421 | LEVEL l; /* the level that we register */ |
||
422 | DS_level_des *lev; /* for readableness only */ |
||
423 | PID i; /* a counter */ |
||
424 | |||
425 | printk("DS_register_level\n"); |
||
426 | |||
427 | /* request an entry in the level_table */ |
||
38 | pj | 428 | l = level_alloc_descriptor(sizeof(DS_level_des)); |
2 | pj | 429 | |
38 | pj | 430 | lev = (DS_level_des *)level_table[l]; |
2 | pj | 431 | |
432 | printk(" lev=%d\n",(int)lev); |
||
433 | |||
434 | /* fill the standard descriptor */ |
||
435 | |||
436 | if (flags & DS_ENABLE_BACKGROUND) |
||
38 | pj | 437 | lev->l.public_scheduler = DS_public_schedulerbackground; |
2 | pj | 438 | |
439 | if (flags & DS_ENABLE_GUARANTEE_EDF) |
||
38 | pj | 440 | lev->l.public_guarantee = DS_public_guaranteeEDF; |
2 | pj | 441 | else if (flags & DS_ENABLE_GUARANTEE_RM) |
38 | pj | 442 | lev->l.public_guarantee = DS_public_guaranteeRM; |
2 | pj | 443 | else |
38 | pj | 444 | lev->l.public_guarantee = NULL; |
2 | pj | 445 | |
38 | pj | 446 | lev->l.public_create = DS_public_create; |
447 | lev->l.public_end = DS_public_end; |
||
448 | lev->l.public_dispatch = DS_public_dispatch; |
||
449 | lev->l.public_epilogue = DS_public_epilogue; |
||
450 | lev->l.public_activate = DS_public_activate; |
||
451 | lev->l.public_unblock = DS_public_unblock; |
||
452 | lev->l.public_block = DS_public_block; |
||
453 | lev->l.public_message = DS_public_message; |
||
2 | pj | 454 | |
455 | /* fill the DS descriptor part */ |
||
456 | |||
457 | for (i=0; i<MAX_PROC; i++) |
||
458 | lev->nact[i] = -1; |
||
459 | |||
460 | lev->Cs = Cs; |
||
461 | lev->availCs = 0; |
||
462 | |||
463 | lev->period = per; |
||
464 | |||
29 | pj | 465 | iq_init(&lev->wait, &freedesc, 0); |
2 | pj | 466 | lev->activated = NIL; |
467 | |||
468 | lev->U = (MAX_BANDWIDTH / per) * Cs; |
||
469 | |||
470 | lev->scheduling_level = master; |
||
471 | |||
472 | lev->flags = flags & 0x07; |
||
473 | |||
474 | sys_atrunlevel(DS_dline_install,(void *) l, RUNLEVEL_INIT); |
||
38 | pj | 475 | |
476 | return l; |
||
2 | pj | 477 | } |
478 | |||
479 | bandwidth_t DS_usedbandwidth(LEVEL l) |
||
480 | { |
||
481 | DS_level_des *lev = (DS_level_des *)(level_table[l]); |
||
38 | pj | 482 | return lev->U; |
2 | pj | 483 | } |
484 |