Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
cf72e8b1a166ac7a38fd8f4289bb236aed5c642e
[simgrid.git] / src / simdag / sd_task.c
1 #include "private.h"
2 #include "simdag/simdag.h"
3 #include "xbt/sysdep.h"
4 #include "xbt/dynar.h"
5
6 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task,sd,
7                                 "Logging specific to SimDag (task)");
8
9 static void __SD_task_remove_dependencies(SD_task_t task);
10 static void __SD_task_destroy_scheduling_data(SD_task_t task);
11
12 /**
13  * \brief Creates a new task.
14  *
15  * \param name the name of the task (can be \c NULL)
16  * \param data the user data you want to associate with the task (can be \c NULL)
17  * \param amount amount of the task
18  * \return the new task
19  * \see SD_task_destroy()
20  */
21 SD_task_t SD_task_create(const char *name, void *data, double amount) {
22   SD_CHECK_INIT_DONE();
23
24   SD_task_t task = xbt_new0(s_SD_task_t, 1);
25
26   /* general information */
27   task->data = data; /* user data */
28   if (name != NULL)
29     task->name = xbt_strdup(name);
30   else
31     task->name = NULL;
32
33   task->state_set = sd_global->not_scheduled_task_set;
34   xbt_swag_insert(task,task->state_set);
35
36   task->amount = amount;
37   task->surf_action = NULL;
38   task->watch_points = 0;
39   task->state_changed = 0;
40
41   /* dependencies */
42   task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
43   task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
44
45   /* scheduling parameters */
46   task->workstation_nb = 0;
47   task->workstation_list = NULL;
48   task->computation_amount = NULL;
49   task->communication_amount = NULL;
50   task->rate = 0;
51
52   return task;
53 }
54
55 /**
56  * \brief Returns the user data of a task
57  *
58  * \param task a task
59  * \return the user data associated with this task (can be \c NULL)
60  * \see SD_task_set_data()
61  */
62 void* SD_task_get_data(SD_task_t task) {
63   SD_CHECK_INIT_DONE();
64   xbt_assert0(task != NULL, "Invalid parameter");
65   return task->data;
66 }
67
68 /**
69  * \brief Sets the user data of a task
70  *
71  * The new data can be \c NULL. The old data should have been freed first
72  * if it was not \c NULL.
73  *
74  * \param task a task
75  * \param data the new data you want to associate with this task
76  * \see SD_task_get_data()
77  */
78 void SD_task_set_data(SD_task_t task, void *data) {
79   SD_CHECK_INIT_DONE();
80   xbt_assert0(task != NULL, "Invalid parameter");
81   task->data = data;
82 }
83
84 /**
85  * \brief Returns the state of a task
86  *
87  * \param task a task
88  * \return the current \ref e_SD_task_state_t "state" of this task:
89  * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_READY, #SD_RUNNING, #SD_DONE or #SD_FAILED
90  * \see e_SD_task_state_t
91  */
92 e_SD_task_state_t SD_task_get_state(SD_task_t task) {
93   SD_CHECK_INIT_DONE();
94   xbt_assert0(task != NULL, "Invalid parameter");
95
96   if (task->state_set == sd_global->scheduled_task_set)
97     return SD_SCHEDULED;
98   if (task->state_set == sd_global->done_task_set)
99     return SD_DONE;
100   if (task->state_set == sd_global->running_task_set)
101     return SD_RUNNING;
102   if (task->state_set == sd_global->ready_task_set)
103     return SD_READY;
104   if (task->state_set == sd_global->not_scheduled_task_set)
105     return SD_NOT_SCHEDULED;
106   return SD_FAILED;
107 }
108
109 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
110  */
111 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state) {
112   xbt_swag_remove(task, task->state_set);
113   switch (new_state) {
114   case SD_NOT_SCHEDULED:
115     task->state_set = sd_global->not_scheduled_task_set;
116     break;
117   case SD_SCHEDULED:
118     task->state_set = sd_global->scheduled_task_set;
119     break;
120   case SD_READY:
121     task->state_set = sd_global->ready_task_set;
122     break;
123   case SD_RUNNING:
124     task->state_set = sd_global->running_task_set;
125     break;
126   case SD_DONE:
127     task->state_set = sd_global->done_task_set;
128     break;
129   case SD_FAILED:
130     task->state_set = sd_global->failed_task_set;
131     break;
132   default:
133     xbt_assert0(0, "Invalid state");
134   }
135   xbt_swag_insert(task, task->state_set);
136
137   if (task->watch_points & new_state) {
138     INFO1("Watch point reached with task '%s'!", SD_task_get_name(task));
139     sd_global->watch_point_reached = 1;
140     SD_task_unwatch(task, new_state); /* remove the watch point */
141   }
142 }
143
144 /**
145  * \brief Returns the name of a task
146  *
147  * \param task a task
148  * \return the name of this task (can be \c NULL)
149  */
150 const char* SD_task_get_name(SD_task_t task) {
151   SD_CHECK_INIT_DONE();
152   xbt_assert0(task != NULL, "Invalid parameter");
153   return task->name;
154 }
155
156 /**
157  * \brief Returns the total amount of a task
158  *
159  * \param task a task
160  * \return the total amount of this task
161  * \see SD_task_get_remaining_amount()
162  */
163 double SD_task_get_amount(SD_task_t task) {
164   SD_CHECK_INIT_DONE();
165   xbt_assert0(task != NULL, "Invalid parameter");
166   return task->amount;
167 }
168
169 /**
170  * \brief Returns the remaining amount of a task
171  *
172  * \param task a task
173  * \return the remaining amount of this task
174  * \see SD_task_get_amount()
175  */
176 double SD_task_get_remaining_amount(SD_task_t task) {
177   SD_CHECK_INIT_DONE();
178   xbt_assert0(task != NULL, "Invalid parameter");
179
180   if (task->surf_action)
181     return task->surf_action->remains;
182   else
183     return task->amount;
184 }
185
186 /* temporary function for debbuging */
187 static void __SD_print_dependencies(SD_task_t task) {
188   INFO1("The following tasks must be executed before %s:", SD_task_get_name(task));
189   xbt_dynar_t dynar = task->tasks_before;
190   int length = xbt_dynar_length(dynar);
191   int i;
192   SD_dependency_t dependency;
193   for (i = 0; i < length; i++) {
194     xbt_dynar_get_cpy(dynar, i, &dependency);
195     INFO1(" %s", SD_task_get_name(dependency->src));
196   }
197
198   INFO1("The following tasks must be executed after %s:", SD_task_get_name(task));
199
200   dynar = task->tasks_after;
201   length = xbt_dynar_length(dynar);
202   for (i = 0; i < length; i++) {
203     xbt_dynar_get_cpy(dynar, i, &dependency);
204     INFO1(" %s", SD_task_get_name(dependency->dst));
205   }
206   INFO0("----------------------------");
207 }
208
209 /* Destroys a dependency between two tasks.
210  */
211 static void __SD_task_dependency_destroy(void *dependency) {
212   if (((SD_dependency_t) dependency)->name != NULL)
213     xbt_free(((SD_dependency_t) dependency)->name);
214   xbt_free(dependency);
215 }
216
217 /**
218  * \brief Adds a dependency between two tasks
219  *
220  * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
221  * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_READY.
222  *
223  * \param name the name of the new dependency (can be \c NULL)
224  * \param data the user data you want to associate with this dependency (can be \c NULL)
225  * \param src the task which must be executed first
226  * \param dst the task you want to make depend on \a src
227  * \see SD_task_dependency_remove()
228  */
229 void SD_task_dependency_add(const char *name, void *data, SD_task_t src, SD_task_t dst) {
230   SD_CHECK_INIT_DONE();
231   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
232   xbt_assert1(src != dst, "Cannot add a dependency between task '%s' and itself", SD_task_get_name(src));
233   xbt_assert1(__SD_task_is_not_scheduled(src) || __SD_task_is_scheduled_or_ready(src),
234               "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY", SD_task_get_name(src));
235   xbt_assert1(__SD_task_is_not_scheduled(dst) || __SD_task_is_scheduled_or_ready(dst),
236               "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY", SD_task_get_name(dst));
237
238   xbt_dynar_t dynar = src->tasks_after;
239   int length = xbt_dynar_length(dynar);
240   int found = 0;
241   int i;
242   SD_dependency_t dependency;
243   for (i = 0; i < length && !found; i++) {
244     xbt_dynar_get_cpy(dynar, i, &dependency);
245     found = (dependency->dst == dst);
246   }
247   xbt_assert2(!found, "A dependency already exists between task '%s' and task '%s'",
248               SD_task_get_name(src), SD_task_get_name(dst));
249
250   dependency = xbt_new0(s_SD_dependency_t, 1);
251
252   if (name != NULL)
253     dependency->name = xbt_strdup(name);
254   dependency->data = data;
255   dependency->src = src;
256   dependency->dst = dst;
257
258   /* src must be executed before dst */
259   xbt_dynar_push(src->tasks_after, &dependency);
260   xbt_dynar_push(dst->tasks_before, &dependency);
261
262   /* if the task was ready, then dst->tasks_before is not empty anymore,
263      so we must go back to state SD_SCHEDULED */
264   if (__SD_task_is_ready(dst)) {
265     DEBUG1("SD_task_dependency_add: %s was ready and becomes scheduled!", SD_task_get_name(dst));
266     __SD_task_set_state(dst, SD_SCHEDULED);
267   }
268
269   /*  __SD_print_dependencies(src);
270       __SD_print_dependencies(dst); */
271 }
272
273 /**
274  * \brief Remove a dependency between two tasks
275  *
276  * \param src a task
277  * \param dst a task depending on \a src
278  * \see SD_task_dependency_add()
279  */
280 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst) {
281   SD_CHECK_INIT_DONE();
282   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
283
284   /* remove the dependency from src->tasks_after */
285   xbt_dynar_t dynar = src->tasks_after;
286   int length = xbt_dynar_length(dynar);
287   int found = 0;
288   int i;
289   SD_dependency_t dependency;
290   for (i = 0; i < length && !found; i++) {
291     xbt_dynar_get_cpy(dynar, i, &dependency);
292     if (dependency->dst == dst) {
293       xbt_dynar_remove_at(dynar, i, NULL);
294       found = 1;
295     }
296   }
297   xbt_assert4(found, "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
298               SD_task_get_name(src), SD_task_get_name(dst), SD_task_get_name(dst), SD_task_get_name(src));
299
300   /* remove the dependency from dst->tasks_before */
301   dynar = dst->tasks_before;
302   length = xbt_dynar_length(dynar);
303   found = 0;
304   
305   for (i = 0; i < length && !found; i++) {
306     xbt_dynar_get_cpy(dynar, i, &dependency);
307     if (dependency->src == src) {
308       xbt_dynar_remove_at(dynar, i, NULL);
309       __SD_task_dependency_destroy(dependency);
310       found = 1;
311     }
312   }
313   xbt_assert4(found, "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
314               SD_task_get_name(dst), SD_task_get_name(src), SD_task_get_name(src), SD_task_get_name(dst)); /* should never happen... */
315
316   /* if the task was scheduled and dst->tasks_before is empty now, we can make it ready */
317   if (xbt_dynar_length(dst->tasks_before) == 0 && __SD_task_is_scheduled(dst))
318     __SD_task_set_state(dst, SD_READY);
319
320   /*  __SD_print_dependencies(src); 
321       __SD_print_dependencies(dst);*/
322 }
323
324 /**
325  * \brief Returns the user data associated with a dependency between two tasks
326  *
327  * \param src a task
328  * \param dst a task depending on \a src
329  * \return the user data associated with this dependency (can be \c NULL)
330  * \see SD_task_dependency_add()
331  */
332 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst) {
333   SD_CHECK_INIT_DONE();
334   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
335
336   xbt_dynar_t dynar = src->tasks_after;
337   int length = xbt_dynar_length(dynar);
338   int found = 0;
339   int i;
340   SD_dependency_t dependency;
341   for (i = 0; i < length && !found; i++) {
342     xbt_dynar_get_cpy(dynar, i, &dependency);
343     found = (dependency->dst == dst);
344   }
345   xbt_assert2(found, "No dependency found between task '%s' and '%s'", SD_task_get_name(src), SD_task_get_name(dst));
346   return dependency->data;
347 }
348
349 /* temporary function for debugging */
350 static void __SD_print_watch_points(SD_task_t task) {
351   static const int state_masks[] = {SD_SCHEDULED, SD_RUNNING, SD_READY, SD_DONE, SD_FAILED};
352   static const char* state_names[] = {"scheduled", "running", "ready", "done", "failed"};
353
354   INFO2("Task '%s' watch points (%x): ", SD_task_get_name(task), task->watch_points);
355
356   int i;
357   for (i = 0; i < 5; i++) {
358     if (task->watch_points & state_masks[i])
359       INFO1("%s ", state_names[i]);
360   }
361 }
362
363 /**
364  * \brief Adds a watch point to a task
365  *
366  * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this task becomes the one given in argument. The
367  * watch point is then automatically removed.
368  * 
369  * \param task a task
370  * \param state the \ref e_SD_task_state_t "state" you want to watch (cannot be #SD_NOT_SCHEDULED)
371  * \see SD_task_unwatch()
372  */
373 void SD_task_watch(SD_task_t task, e_SD_task_state_t state) {
374   SD_CHECK_INIT_DONE();
375   xbt_assert0(task != NULL, "Invalid parameter");
376   xbt_assert0(state != SD_NOT_SCHEDULED, "Cannot add a watch point for state SD_NOT_SCHEDULED");
377
378   task->watch_points = task->watch_points | state;
379   /*  __SD_print_watch_points(task);*/
380 }
381
382 /**
383  * \brief Removes a watch point from a task
384  * 
385  * \param task a task
386  * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
387  * \see SD_task_watch()
388  */
389 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state) {
390   SD_CHECK_INIT_DONE();
391   xbt_assert0(task != NULL, "Invalid parameter");
392   xbt_assert0(state != SD_NOT_SCHEDULED, "Cannot have a watch point for state SD_NOT_SCHEDULED");
393   
394   task->watch_points = task->watch_points & ~state;
395   /*  __SD_print_watch_points(task);*/
396 }
397
398 /**
399  * \brief Returns an approximative estimation of the execution time of a task.
400  * 
401  * The estimation is very approximative because the value returned is the time
402  * the task would take if it was executed now and if it was the only task.
403  * 
404  * \param task the task to evaluate
405  * \param workstation_nb number of workstations on which the task would be executed
406  * \param workstation_list the workstations on which the task would be executed
407  * \param computation_amount computation amount for each workstation
408  * \param communication_amount communication amount between each pair of workstations
409  * \param rate task execution speed rate
410  * \see SD_schedule()
411  */
412 double SD_task_get_execution_time(SD_task_t task,
413                                   int workstation_nb,
414                                   const SD_workstation_t *workstation_list,
415                                   const double *computation_amount,
416                                   const double *communication_amount,
417                                   double rate) {
418   /* the task execution time is the maximum execution time of the parallel tasks */
419   double time, max_time = 0.0;
420   int i, j;
421   for (i = 0; i < workstation_nb; i++) {
422     time = SD_workstation_get_computation_time(workstation_list[i], computation_amount[i]);
423     
424     for (j = 0; j < workstation_nb; j++) {
425       time += SD_route_get_communication_time(workstation_list[i], workstation_list[j],
426                                               communication_amount[i * workstation_nb + j]);
427     }
428
429     if (time > max_time) {
430       max_time = time;
431     }
432   }
433   return max_time * SD_task_get_amount(task);
434 }
435
436 /**
437  * \brief Schedules a task
438  *
439  * The task state must be #SD_NOT_SCHEDULED.
440  * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
441  * i.e. when its dependencies are satisfied.
442  * 
443  * \param task the task you want to schedule
444  * \param workstation_nb number of workstations on which the task will be executed
445  * \param workstation_list the workstations on which the task will be executed
446  * \param computation_amount computation amount for each workstation
447  * \param communication_amount communication amount between each pair of workstations
448  * \param rate task execution speed rate
449  * \see SD_task_unschedule()
450  */
451 void SD_task_schedule(SD_task_t task, int workstation_nb,
452                      const SD_workstation_t *workstation_list, const double *computation_amount,
453                      const double *communication_amount, double rate) {
454   SD_CHECK_INIT_DONE();
455   xbt_assert0(task, "Invalid parameter");
456   xbt_assert1(__SD_task_is_not_scheduled(task), "Task '%s' has already been scheduled.", SD_task_get_name(task));
457   xbt_assert0(workstation_nb > 0, "workstation_nb must be positive");
458
459   task->workstation_nb = workstation_nb;
460   task->rate = rate;
461
462   task->computation_amount = xbt_new0(double, workstation_nb);
463   memcpy(task->computation_amount, computation_amount, sizeof(double) * workstation_nb);
464
465   int communication_nb = workstation_nb * workstation_nb;
466   task->communication_amount = xbt_new0(double, communication_nb);
467   memcpy(task->communication_amount, communication_amount, sizeof(double) * communication_nb);
468
469   /* we have to create a Surf workstation array instead of the SimDag workstation array */
470   task->workstation_list = xbt_new0(void*, workstation_nb);
471   int i;
472   for (i = 0; i < workstation_nb; i++) {
473     task->workstation_list[i] = workstation_list[i]->surf_workstation;
474   }
475
476   /* update the task state */
477   if (xbt_dynar_length(task->tasks_before) == 0)
478     __SD_task_set_state(task, SD_READY);
479   else
480     __SD_task_set_state(task, SD_SCHEDULED);
481 }
482
483 /**
484  * \brief Unschedules a task
485  *
486  * The task state must be #SD_SCHEDULED, #SD_READY, #SD_RUNNING or #SD_FAILED.
487  * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
488  * Call SD_task_schedule() to schedule it again.
489  *
490  * \param task the task you want to unschedule
491  * \see SD_task_schedule()
492  */
493 void SD_task_unschedule(SD_task_t task) {
494   SD_CHECK_INIT_DONE();
495   xbt_assert0(task != NULL, "Invalid parameter");
496   xbt_assert1(task->state_set == sd_global->scheduled_task_set ||
497               task->state_set == sd_global->ready_task_set ||
498               task->state_set == sd_global->running_task_set ||
499               task->state_set == sd_global->failed_task_set,
500               "Task %s: the state must be SD_SCHEDULED, SD_READY, SD_RUNNING or SD_FAILED",
501               SD_task_get_name(task));
502
503   if (__SD_task_is_scheduled_or_ready(task)) /* if the task is scheduled or ready */
504     __SD_task_destroy_scheduling_data(task);
505
506   if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
507     surf_workstation_resource->common_public->action_cancel(task->surf_action);
508   else
509     __SD_task_set_state(task, SD_NOT_SCHEDULED);
510 }
511
512 /* Destroys the data memorised by SD_task_schedule. Task state must be SD_SCHEDULED or SD_READY.
513  */
514 static void __SD_task_destroy_scheduling_data(SD_task_t task) {
515   SD_CHECK_INIT_DONE();
516   xbt_assert1(__SD_task_is_scheduled_or_ready(task),
517               "Task '%s' must be SD_SCHEDULED or SD_READY", SD_task_get_name(task));
518   xbt_free(task->workstation_list);
519   xbt_free(task->computation_amount);
520   xbt_free(task->communication_amount);
521 }
522
523 /* Runs a task. This function is called by SD_simulate() when a scheduled task can start
524  * (ie when its dependencies are satisfied).
525  */
526 surf_action_t __SD_task_run(SD_task_t task) {
527   SD_CHECK_INIT_DONE();
528   xbt_assert0(task != NULL, "Invalid parameter");
529   xbt_assert2(__SD_task_is_ready(task), "Task '%s' is not ready! Task state: %d",
530               SD_task_get_name(task), SD_task_get_state(task));
531
532   surf_action_t surf_action = surf_workstation_resource->extension_public->
533     execute_parallel_task(task->workstation_nb,
534                           task->workstation_list,
535                           task->computation_amount,
536                           task->communication_amount,
537                           task->amount,
538                           task->rate);
539
540   DEBUG1("surf_action = %p", surf_action);
541
542   __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
543   __SD_task_set_state(task, SD_RUNNING);
544
545   return surf_action;
546 }
547 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
548  */
549 static void __SD_task_remove_dependencies(SD_task_t task) {
550   /* we must destroy the dependencies carefuly (with SD_dependency_remove)
551      because each one is stored twice */
552   SD_dependency_t dependency;
553   while (xbt_dynar_length(task->tasks_before) > 0) {
554     xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
555     SD_task_dependency_remove(dependency->src, dependency->dst);
556   }
557
558   while (xbt_dynar_length(task->tasks_after) > 0) {
559     xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
560     SD_task_dependency_remove(dependency->src, dependency->dst);
561   }
562 }
563
564 /**
565  * \brief Destroys a task.
566  *
567  * The user data (if any) should have been destroyed first.
568  *
569  * \param task the task you want to destroy
570  * \see SD_task_create()
571  */
572 void SD_task_destroy(SD_task_t task) {
573   SD_CHECK_INIT_DONE();
574   xbt_assert0(task != NULL, "Invalid parameter");
575
576   DEBUG1("Destroying task %s...", SD_task_get_name(task));
577
578   __SD_task_remove_dependencies(task);
579
580   /* if the task was scheduled or ready we have to free the scheduling parameters */
581   if (__SD_task_is_scheduled_or_ready(task))
582     __SD_task_destroy_scheduling_data(task);
583
584   if (task->name != NULL)
585     xbt_free(task->name);
586
587   if (task->surf_action != NULL)
588     xbt_free(task->surf_action);
589
590   xbt_dynar_free(&task->tasks_before);
591   xbt_dynar_free(&task->tasks_after);
592   xbt_free(task);
593
594   DEBUG0("Task destroyed.");
595 }