1 /* Copyright (c) 2006, 2007, 2008, 2009, 2010, 2011. The SimGrid Team.
2 * All rights reserved. */
4 /* This program is free software; you can redistribute it and/or modify it
5 * under the terms of the license (GNU LGPL) which comes with this package. */
8 #include "simdag/simdag.h"
9 #include "xbt/sysdep.h"
10 #include "xbt/dynar.h"
11 #include "instr/instr_private.h"
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
14 "Logging specific to SimDag (task)");
16 static void __SD_task_remove_dependencies(SD_task_t task);
17 static void __SD_task_destroy_scheduling_data(SD_task_t task);
19 void* SD_task_new_f(void)
21 SD_task_t task = xbt_new0(s_SD_task_t, 1);
22 task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
23 task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
28 void SD_task_recycle_f(void *t)
30 SD_task_t task = (SD_task_t) t;
32 /* Reset the content */
33 task->kind = SD_TASK_NOT_TYPED;
34 task->state_hookup.prev = NULL;
35 task->state_hookup.next = NULL;
36 task->state_set = sd_global->not_scheduled_task_set;
37 xbt_swag_insert(task, task->state_set);
38 task->state = SD_NOT_SCHEDULED;
39 task->return_hookup.prev = NULL;
40 task->return_hookup.next = NULL;
44 task->start_time = -1.0;
45 task->finish_time = -1.0;
46 task->surf_action = NULL;
47 task->watch_points = 0;
50 xbt_dynar_reset(task->tasks_before);
51 xbt_dynar_reset(task->tasks_after);
52 task->unsatisfied_dependencies = 0;
53 task->is_not_ready = 0;
55 /* scheduling parameters */
56 task->workstation_nb = 0;
57 task->workstation_list = NULL;
58 task->computation_amount = NULL;
59 task->communication_amount = NULL;
63 void SD_task_free_f(void *t)
65 SD_task_t task = (SD_task_t)t;
67 xbt_dynar_free(&task->tasks_before);
68 xbt_dynar_free(&task->tasks_after);
73 * \brief Creates a new task.
75 * \param name the name of the task (can be \c NULL)
76 * \param data the user data you want to associate with the task (can be \c NULL)
77 * \param amount amount of the task
78 * \return the new task
79 * \see SD_task_destroy()
81 SD_task_t SD_task_create(const char *name, void *data, double amount)
83 SD_task_t task = xbt_mallocator_get(sd_global->task_mallocator);
85 /* general information */
86 task->data = data; /* user data */
87 task->name = xbt_strdup(name);
88 task->amount = amount;
89 task->remains = amount;
91 sd_global->task_number++;
94 task->category = NULL;
101 * \brief Destroys a task.
103 * The user data (if any) should have been destroyed first.
105 * \param task the task you want to destroy
106 * \see SD_task_create()
108 void SD_task_destroy(SD_task_t task)
110 XBT_DEBUG("Destroying task %s...", SD_task_get_name(task));
112 __SD_task_remove_dependencies(task);
113 /* if the task was scheduled or runnable we have to free the scheduling parameters */
114 if (__SD_task_is_scheduled_or_runnable(task))
115 __SD_task_destroy_scheduling_data(task);
116 if (task->state_set != NULL) /* would be null if just created */
117 xbt_swag_remove(task, task->state_set);
119 xbt_swag_remove(task, sd_global->return_set);
121 xbt_free(task->name);
123 if (task->surf_action != NULL)
124 surf_workstation_model->action_unref(task->surf_action);
126 xbt_free(task->workstation_list);
127 xbt_free(task->communication_amount);
128 xbt_free(task->computation_amount);
130 xbt_mallocator_release(sd_global->task_mallocator,task);
131 sd_global->task_number--;
134 if (task->category) xbt_free(task->category);
137 XBT_DEBUG("Task destroyed.");
141 * \brief Returns the user data of a task
144 * \return the user data associated with this task (can be \c NULL)
145 * \see SD_task_set_data()
147 void *SD_task_get_data(SD_task_t task)
153 * \brief Sets the user data of a task
155 * The new data can be \c NULL. The old data should have been freed first
156 * if it was not \c NULL.
159 * \param data the new data you want to associate with this task
160 * \see SD_task_get_data()
162 void SD_task_set_data(SD_task_t task, void *data)
168 * \brief Returns the state of a task
171 * \return the current \ref e_SD_task_state_t "state" of this task:
172 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
173 * \see e_SD_task_state_t
175 e_SD_task_state_t SD_task_get_state(SD_task_t task)
180 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
182 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
184 xbt_swag_remove(task, task->state_set);
186 case SD_NOT_SCHEDULED:
187 task->state_set = sd_global->not_scheduled_task_set;
190 task->state_set = sd_global->schedulable_task_set;
193 task->state_set = sd_global->scheduled_task_set;
196 task->state_set = sd_global->runnable_task_set;
199 task->state_set = sd_global->in_fifo_task_set;
202 task->state_set = sd_global->running_task_set;
204 surf_workstation_model->action_get_start_time(task->surf_action);
207 task->state_set = sd_global->done_task_set;
209 surf_workstation_model->action_get_finish_time(task->surf_action);
212 jedule_log_sd_event(task);
216 task->state_set = sd_global->failed_task_set;
219 xbt_die( "Invalid state");
221 xbt_swag_insert(task, task->state_set);
222 task->state = new_state;
224 if (task->watch_points & new_state) {
225 XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
226 sd_global->watch_point_reached = 1;
227 SD_task_unwatch(task, new_state); /* remove the watch point */
232 * \brief Returns the name of a task
235 * \return the name of this task (can be \c NULL)
237 const char *SD_task_get_name(SD_task_t task)
242 /** @brief Allows to change the name of a task */
243 void SD_task_set_name(SD_task_t task, const char *name)
245 xbt_free(task->name);
246 task->name = xbt_strdup(name);
249 /** @brief Returns the dynar of the parents of a task
252 * \return a newly allocated dynar comprising the parents of this task
255 xbt_dynar_t SD_task_get_parents(SD_task_t task)
261 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
262 xbt_dynar_foreach(task->tasks_before, i, dep) {
263 xbt_dynar_push(parents, &(dep->src));
268 /** @brief Returns the dynar of the parents of a task
271 * \return a newly allocated dynar comprising the parents of this task
273 xbt_dynar_t SD_task_get_children(SD_task_t task)
276 xbt_dynar_t children;
279 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
280 xbt_dynar_foreach(task->tasks_after, i, dep) {
281 xbt_dynar_push(children, &(dep->dst));
287 * \brief Returns the amount of workstations involved in a task
289 * Only call this on already scheduled tasks!
292 int SD_task_get_workstation_count(SD_task_t task)
294 return task->workstation_nb;
298 * \brief Returns the list of workstations involved in a task
300 * Only call this on already scheduled tasks!
303 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
305 return task->workstation_list;
309 * \brief Returns the total amount of work contained in a task
312 * \return the total amount of work (computation or data transfer) for this task
313 * \see SD_task_get_remaining_amount()
315 double SD_task_get_amount(SD_task_t task)
321 * \brief Returns the remaining amount work to do till the completion of a task
324 * \return the remaining amount of work (computation or data transfer) of this task
325 * \see SD_task_get_amount()
327 double SD_task_get_remaining_amount(SD_task_t task)
329 if (task->surf_action)
330 return surf_workstation_model->get_remains(task->surf_action);
332 return task->remains;
335 int SD_task_get_kind(SD_task_t task)
340 /** @brief Displays debugging informations about a task */
341 void SD_task_dump(SD_task_t task)
343 unsigned int counter;
344 SD_dependency_t dependency;
347 XBT_INFO("Displaying task %s", SD_task_get_name(task));
348 statename = bprintf("%s %s %s %s %s %s %s %s",
349 (task->state & SD_NOT_SCHEDULED ? "not scheduled" :
351 (task->state & SD_SCHEDULABLE ? "schedulable" : ""),
352 (task->state & SD_SCHEDULED ? "scheduled" : ""),
353 (task->state & SD_RUNNABLE ? "runnable" :
355 (task->state & SD_IN_FIFO ? "in fifo" : ""),
356 (task->state & SD_RUNNING ? "running" : ""),
357 (task->state & SD_DONE ? "done" : ""),
358 (task->state & SD_FAILED ? "failed" : ""));
359 XBT_INFO(" - state: %s", statename);
362 if (task->kind != 0) {
363 switch (task->kind) {
364 case SD_TASK_COMM_E2E:
365 XBT_INFO(" - kind: end-to-end communication");
367 case SD_TASK_COMP_SEQ:
368 XBT_INFO(" - kind: sequential computation");
371 XBT_INFO(" - (unknown kind %d)", task->kind);
374 XBT_INFO(" - amount: %.0f", SD_task_get_amount(task));
375 XBT_INFO(" - Dependencies to satisfy: %u", task->unsatisfied_dependencies);
376 if (!xbt_dynar_is_empty(task->tasks_before)) {
377 XBT_INFO(" - pre-dependencies:");
378 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
379 XBT_INFO(" %s", SD_task_get_name(dependency->src));
382 if (!xbt_dynar_is_empty(task->tasks_after)) {
383 XBT_INFO(" - post-dependencies:");
384 xbt_dynar_foreach(task->tasks_after, counter, dependency) {
385 XBT_INFO(" %s", SD_task_get_name(dependency->dst));
390 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
391 void SD_task_dotty(SD_task_t task, void *out)
393 unsigned int counter;
394 SD_dependency_t dependency;
395 fprintf(out, " T%p [label=\"%.20s\"", task, task->name);
396 switch (task->kind) {
397 case SD_TASK_COMM_E2E:
398 fprintf(out, ", shape=box");
400 case SD_TASK_COMP_SEQ:
401 fprintf(out, ", shape=circle");
404 xbt_die("Unknown task type!");
406 fprintf(out, "];\n");
407 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
408 fprintf(out, " T%p -> T%p;\n", dependency->src, dependency->dst);
412 /* Destroys a dependency between two tasks.
414 static void __SD_task_dependency_destroy(void *dependency)
416 xbt_free(((SD_dependency_t)dependency)->name);
417 xbt_free(dependency);
421 * \brief Adds a dependency between two tasks
423 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
424 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
426 * \param name the name of the new dependency (can be \c NULL)
427 * \param data the user data you want to associate with this dependency (can be \c NULL)
428 * \param src the task which must be executed first
429 * \param dst the task you want to make depend on \a src
430 * \see SD_task_dependency_remove()
432 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
439 SD_dependency_t dependency;
441 dynar = src->tasks_after;
442 length = xbt_dynar_length(dynar);
446 "Cannot add a dependency between task '%s' and itself",
447 SD_task_get_name(src));
449 if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
450 && !__SD_task_is_scheduled_or_runnable(src) && !__SD_task_is_running(src))
452 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE"
454 SD_task_get_name(src));
456 if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
457 && !__SD_task_is_scheduled_or_runnable(dst))
459 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
460 SD_task_get_name(dst));
462 XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
463 SD_task_get_name(src), SD_task_get_name(dst));
464 for (i = 0; i < length && !found; i++) {
465 xbt_dynar_get_cpy(dynar, i, &dependency);
466 found = (dependency->dst == dst);
467 XBT_DEBUG("Dependency %d: dependency->dst = %s", i,
468 SD_task_get_name(dependency->dst));
473 "A dependency already exists between task '%s' and task '%s'",
474 SD_task_get_name(src), SD_task_get_name(dst));
476 dependency = xbt_new(s_SD_dependency_t, 1);
478 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
479 dependency->data = data;
480 dependency->src = src;
481 dependency->dst = dst;
483 /* src must be executed before dst */
484 xbt_dynar_push(src->tasks_after, &dependency);
485 xbt_dynar_push(dst->tasks_before, &dependency);
487 dst->unsatisfied_dependencies++;
490 /* if the task was runnable, then dst->tasks_before is not empty anymore,
491 so we must go back to state SD_SCHEDULED */
492 if (__SD_task_is_runnable(dst)) {
494 ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
495 SD_task_get_name(dst));
496 __SD_task_set_state(dst, SD_SCHEDULED);
499 /* __SD_print_dependencies(src);
500 __SD_print_dependencies(dst); */
504 * \brief Indicates whether there is a dependency between two tasks.
507 * \param dst a task depending on \a src
509 * If src is NULL, checks whether dst has any pre-dependency.
510 * If dst is NULL, checks whether src has any post-dependency.
512 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
514 unsigned int counter;
515 SD_dependency_t dependency;
517 xbt_assert(src != NULL
519 "Invalid parameter: both src and dst are NULL");
523 xbt_dynar_foreach(src->tasks_after, counter, dependency) {
524 if (dependency->dst == dst)
528 return xbt_dynar_length(src->tasks_after);
531 return xbt_dynar_length(dst->tasks_before);
537 * \brief Remove a dependency between two tasks
540 * \param dst a task depending on \a src
541 * \see SD_task_dependency_add()
543 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
550 SD_dependency_t dependency;
552 /* remove the dependency from src->tasks_after */
553 dynar = src->tasks_after;
554 length = xbt_dynar_length(dynar);
556 for (i = 0; i < length && !found; i++) {
557 xbt_dynar_get_cpy(dynar, i, &dependency);
558 if (dependency->dst == dst) {
559 xbt_dynar_remove_at(dynar, i, NULL);
565 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
566 SD_task_get_name(src), SD_task_get_name(dst),
567 SD_task_get_name(dst), SD_task_get_name(src));
569 /* remove the dependency from dst->tasks_before */
570 dynar = dst->tasks_before;
571 length = xbt_dynar_length(dynar);
574 for (i = 0; i < length && !found; i++) {
575 xbt_dynar_get_cpy(dynar, i, &dependency);
576 if (dependency->src == src) {
577 xbt_dynar_remove_at(dynar, i, NULL);
578 __SD_task_dependency_destroy(dependency);
579 dst->unsatisfied_dependencies--;
584 /* should never happen... */
586 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
587 SD_task_get_name(dst), SD_task_get_name(src),
588 SD_task_get_name(src), SD_task_get_name(dst));
590 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
592 if (dst->unsatisfied_dependencies == 0) {
593 if (__SD_task_is_scheduled(dst))
594 __SD_task_set_state(dst, SD_RUNNABLE);
596 __SD_task_set_state(dst, SD_SCHEDULABLE);
599 if (dst->is_not_ready == 0)
600 __SD_task_set_state(dst, SD_SCHEDULABLE);
602 /* __SD_print_dependencies(src);
603 __SD_print_dependencies(dst); */
607 * \brief Returns the user data associated with a dependency between two tasks
610 * \param dst a task depending on \a src
611 * \return the user data associated with this dependency (can be \c NULL)
612 * \see SD_task_dependency_add()
614 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
621 SD_dependency_t dependency;
623 dynar = src->tasks_after;
624 length = xbt_dynar_length(dynar);
626 for (i = 0; i < length && !found; i++) {
627 xbt_dynar_get_cpy(dynar, i, &dependency);
628 found = (dependency->dst == dst);
631 THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
632 SD_task_get_name(src), SD_task_get_name(dst));
633 return dependency->data;
636 /* temporary function for debugging */
637 static void __SD_print_watch_points(SD_task_t task)
639 static const int state_masks[] =
640 { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE,
643 static const char *state_names[] =
644 { "schedulable", "scheduled", "running", "runnable", "done",
649 XBT_INFO("Task '%s' watch points (%x): ", SD_task_get_name(task),
653 for (i = 0; i < 5; i++) {
654 if (task->watch_points & state_masks[i])
655 XBT_INFO("%s ", state_names[i]);
660 * \brief Adds a watch point to a task
662 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
663 * task becomes the one given in argument. The
664 * watch point is then automatically removed.
667 * \param state the \ref e_SD_task_state_t "state" you want to watch
668 * (cannot be #SD_NOT_SCHEDULED)
669 * \see SD_task_unwatch()
671 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
673 if (state & SD_NOT_SCHEDULED)
675 "Cannot add a watch point for state SD_NOT_SCHEDULED");
677 task->watch_points = task->watch_points | state;
678 /* __SD_print_watch_points(task); */
682 * \brief Removes a watch point from a task
685 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
686 * \see SD_task_watch()
688 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
690 xbt_assert(state != SD_NOT_SCHEDULED,
691 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
693 task->watch_points = task->watch_points & ~state;
694 /* __SD_print_watch_points(task); */
698 * \brief Returns an approximative estimation of the execution time of a task.
700 * The estimation is very approximative because the value returned is the time
701 * the task would take if it was executed now and if it was the only task.
703 * \param task the task to evaluate
704 * \param workstation_nb number of workstations on which the task would be executed
705 * \param workstation_list the workstations on which the task would be executed
706 * \param computation_amount computation amount for each workstation
707 * \param communication_amount communication amount between each pair of workstations
710 double SD_task_get_execution_time(SD_task_t task,
712 const SD_workstation_t *
714 const double *computation_amount,
715 const double *communication_amount)
717 double time, max_time = 0.0;
719 xbt_assert(workstation_nb > 0, "Invalid parameter");
721 /* the task execution time is the maximum execution time of the parallel tasks */
723 for (i = 0; i < workstation_nb; i++) {
725 if (computation_amount != NULL)
727 SD_workstation_get_computation_time(workstation_list[i],
728 computation_amount[i]);
730 if (communication_amount != NULL)
731 for (j = 0; j < workstation_nb; j++) {
733 SD_route_get_communication_time(workstation_list[i],
735 communication_amount[i *
740 if (time > max_time) {
747 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
749 if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task))
750 THROWF(arg_error, 0, "Task '%s' has already been scheduled",
751 SD_task_get_name(task));
753 /* update the task state */
754 if (task->unsatisfied_dependencies == 0)
755 __SD_task_set_state(task, SD_RUNNABLE);
757 __SD_task_set_state(task, SD_SCHEDULED);
761 * \brief Schedules a task
763 * The task state must be #SD_NOT_SCHEDULED.
764 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
765 * i.e. when its dependencies are satisfied.
767 * \param task the task you want to schedule
768 * \param workstation_count number of workstations on which the task will be executed
769 * \param workstation_list the workstations on which the task will be executed
770 * \param computation_amount computation amount for each workstation
771 * \param communication_amount communication amount between each pair of workstations
772 * \param rate task execution speed rate
773 * \see SD_task_unschedule()
775 void SD_task_schedule(SD_task_t task, int workstation_count,
776 const SD_workstation_t * workstation_list,
777 const double *computation_amount,
778 const double *communication_amount, double rate)
780 int communication_nb;
781 task->workstation_nb = 0;
783 xbt_assert(workstation_count > 0, "workstation_nb must be positive");
785 task->workstation_nb = workstation_count;
788 if (computation_amount) {
789 task->computation_amount = xbt_realloc(task->computation_amount,
790 sizeof(double) * workstation_count);
791 memcpy(task->computation_amount, computation_amount,
792 sizeof(double) * workstation_count);
794 xbt_free(task->computation_amount);
795 task->computation_amount = NULL;
798 communication_nb = workstation_count * workstation_count;
799 if (communication_amount) {
800 task->communication_amount = xbt_realloc(task->communication_amount,
801 sizeof(double) * communication_nb);
802 memcpy(task->communication_amount, communication_amount,
803 sizeof(double) * communication_nb);
805 xbt_free(task->communication_amount);
806 task->communication_amount = NULL;
809 task->workstation_list =
810 xbt_realloc(task->workstation_list,
811 sizeof(SD_workstation_t) * workstation_count);
812 memcpy(task->workstation_list, workstation_list,
813 sizeof(SD_workstation_t) * workstation_count);
815 SD_task_do_schedule(task);
819 * \brief Unschedules a task
821 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
822 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
823 * Call SD_task_schedule() to schedule it again.
825 * \param task the task you want to unschedule
826 * \see SD_task_schedule()
828 void SD_task_unschedule(SD_task_t task)
830 if (task->state_set != sd_global->scheduled_task_set &&
831 task->state_set != sd_global->runnable_task_set &&
832 task->state_set != sd_global->running_task_set &&
833 task->state_set != sd_global->failed_task_set)
835 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
836 SD_task_get_name(task));
838 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
839 &&task->kind == SD_TASK_NOT_TYPED) /* Don't free scheduling data for typed tasks */
840 __SD_task_destroy_scheduling_data(task);
842 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
843 surf_workstation_model->action_cancel(task->surf_action);
845 if (task->unsatisfied_dependencies == 0)
846 __SD_task_set_state(task, SD_SCHEDULABLE);
848 __SD_task_set_state(task, SD_NOT_SCHEDULED);
850 task->remains = task->amount;
851 task->start_time = -1.0;
854 /* Destroys the data memorized by SD_task_schedule. Task state must be SD_SCHEDULED or SD_RUNNABLE.
856 static void __SD_task_destroy_scheduling_data(SD_task_t task)
858 if (!__SD_task_is_scheduled_or_runnable(task)
859 && !__SD_task_is_in_fifo(task))
861 "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
862 SD_task_get_name(task));
864 xbt_free(task->computation_amount);
865 xbt_free(task->communication_amount);
866 task->computation_amount = task->communication_amount = NULL;
869 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
870 * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
871 * the task gets out of its fifos.
873 void __SD_task_really_run(SD_task_t task)
877 void **surf_workstations;
879 xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
880 "Task '%s' is not runnable or in a fifo! Task state: %d",
881 SD_task_get_name(task), (int)SD_task_get_state(task));
882 xbt_assert(task->workstation_list != NULL,
883 "Task '%s': workstation_list is NULL!",
884 SD_task_get_name(task));
888 XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
890 /* set this task as current task for the workstations in sequential mode */
891 for (i = 0; i < task->workstation_nb; i++) {
892 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
893 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
894 task->workstation_list[i]->current_task = task;
895 xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
896 "The workstation should be busy now");
900 XBT_DEBUG("Task '%s' set as current task for its workstations",
901 SD_task_get_name(task));
905 /* we have to create a Surf workstation array instead of the SimDag workstation array */
906 surf_workstations = xbt_new(void *, task->workstation_nb);
908 for (i = 0; i < task->workstation_nb; i++)
909 surf_workstations[i] = task->workstation_list[i]->surf_workstation;
911 /* It's allowed to pass a NULL vector as cost to mean vector of 0.0 (easing user's life). Let's deal with it */
912 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
914 task->surf_action = NULL;
915 if ((task->workstation_nb == 1)
916 && (cost_or_zero(task->communication_amount, 0) == 0.0)) {
918 surf_workstation_model->extension.
919 workstation.execute(surf_workstations[0],
920 cost_or_zero(task->computation_amount, 0));
921 } else if ((task->workstation_nb == 1)
922 && (cost_or_zero(task->computation_amount, 0) == 0.0)) {
925 surf_workstation_model->extension.
926 workstation.communicate(surf_workstations[0], surf_workstations[0],
927 cost_or_zero(task->communication_amount,
929 } else if ((task->workstation_nb == 2)
930 && (cost_or_zero(task->computation_amount, 0) == 0.0)
931 && (cost_or_zero(task->computation_amount, 1) == 0.0)) {
935 for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
936 if (cost_or_zero(task->communication_amount, i) > 0.0) {
938 value = cost_or_zero(task->communication_amount, i);
943 surf_workstation_model->extension.
944 workstation.communicate(surf_workstations[0],
945 surf_workstations[1], value, task->rate);
950 if (!task->surf_action) {
951 double *computation_amount = xbt_new(double, task->workstation_nb);
952 double *communication_amount = xbt_new(double, task->workstation_nb *
953 task->workstation_nb);
955 memcpy(computation_amount, task->computation_amount, sizeof(double) *
956 task->workstation_nb);
957 memcpy(communication_amount, task->communication_amount,
958 sizeof(double) * task->workstation_nb * task->workstation_nb);
961 surf_workstation_model->extension.
962 workstation.execute_parallel_task(task->workstation_nb,
965 communication_amount,
966 task->amount, task->rate);
968 xbt_free(surf_workstations);
971 surf_workstation_model->action_data_set(task->surf_action, task);
973 XBT_DEBUG("surf_action = %p", task->surf_action);
977 TRACE_surf_action(task->surf_action, task->category);
980 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
981 __SD_task_set_state(task, SD_RUNNING);
982 xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
983 SD_task_get_name(task), (int)SD_task_get_state(task));
987 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_RUNNABLE
988 * (ie when its dependencies are satisfied).
989 * If one of the workstations where the task is scheduled on is busy (in sequential mode),
990 * the task doesn't start.
991 * Returns whether the task has started.
993 int __SD_task_try_to_run(SD_task_t task)
998 SD_workstation_t workstation;
1000 xbt_assert(__SD_task_is_runnable(task),
1001 "Task '%s' is not runnable! Task state: %d",
1002 SD_task_get_name(task), (int)SD_task_get_state(task));
1005 for (i = 0; i < task->workstation_nb; i++) {
1006 can_start = can_start &&
1007 !__SD_workstation_is_busy(task->workstation_list[i]);
1010 XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1012 if (!can_start) { /* if the task cannot start and is not in the fifos yet */
1013 for (i = 0; i < task->workstation_nb; i++) {
1014 workstation = task->workstation_list[i];
1015 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1016 XBT_DEBUG("Pushing task '%s' in the fifo of workstation '%s'",
1017 SD_task_get_name(task),
1018 SD_workstation_get_name(workstation));
1019 xbt_fifo_push(workstation->task_fifo, task);
1022 __SD_task_set_state(task, SD_IN_FIFO);
1023 xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1024 SD_task_get_name(task), (int)SD_task_get_state(task));
1025 XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1027 __SD_task_really_run(task);
1033 /* This function is called by SD_simulate when a task is done.
1034 * It updates task->state and task->action and executes if necessary the tasks
1035 * which were waiting in fifos for the end of `task'
1037 void __SD_task_just_done(SD_task_t task)
1040 SD_workstation_t workstation;
1042 SD_task_t candidate;
1043 int candidate_nb = 0;
1044 int candidate_capacity = 8;
1045 SD_task_t *candidates;
1048 xbt_assert(__SD_task_is_running(task),
1049 "The task must be running! Task state: %d",
1050 (int)SD_task_get_state(task));
1051 xbt_assert(task->workstation_list != NULL,
1052 "Task '%s': workstation_list is NULL!",
1053 SD_task_get_name(task));
1056 candidates = xbt_new(SD_task_t, 8);
1058 __SD_task_set_state(task, SD_DONE);
1059 surf_workstation_model->action_unref(task->surf_action);
1060 task->surf_action = NULL;
1062 XBT_DEBUG("Looking for candidates");
1064 /* if the task was executed on sequential workstations,
1065 maybe we can execute the next task of the fifo for each workstation */
1066 for (i = 0; i < task->workstation_nb; i++) {
1067 workstation = task->workstation_list[i];
1068 XBT_DEBUG("Workstation '%s': access_mode = %d",
1069 SD_workstation_get_name(workstation), (int)workstation->access_mode);
1070 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1071 xbt_assert(workstation->task_fifo != NULL,
1072 "Workstation '%s' has sequential access but no fifo!",
1073 SD_workstation_get_name(workstation));
1074 xbt_assert(workstation->current_task =
1075 task, "Workstation '%s': current task should be '%s'",
1076 SD_workstation_get_name(workstation),
1077 SD_task_get_name(task));
1079 /* the task is over so we can release the workstation */
1080 workstation->current_task = NULL;
1082 XBT_DEBUG("Getting candidate in fifo");
1084 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1085 (workstation->task_fifo));
1087 if (candidate != NULL) {
1088 XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1089 xbt_assert(__SD_task_is_in_fifo(candidate),
1090 "Bad state of candidate '%s': %d",
1091 SD_task_get_name(candidate),
1092 (int)SD_task_get_state(candidate));
1095 XBT_DEBUG("Candidate in fifo: %p", candidate);
1097 /* if there was a task waiting for my place */
1098 if (candidate != NULL) {
1099 /* Unfortunately, we are not sure yet that we can execute the task now,
1100 because the task can be waiting more deeply in some other workstation's fifos...
1101 So we memorize all candidate tasks, and then we will check for each candidate
1102 whether or not all its workstations are available. */
1104 /* realloc if necessary */
1105 if (candidate_nb == candidate_capacity) {
1106 candidate_capacity *= 2;
1108 xbt_realloc(candidates,
1109 sizeof(SD_task_t) * candidate_capacity);
1112 /* register the candidate */
1113 candidates[candidate_nb++] = candidate;
1114 candidate->fifo_checked = 0;
1119 XBT_DEBUG("Candidates found: %d", candidate_nb);
1121 /* now we check every candidate task */
1122 for (i = 0; i < candidate_nb; i++) {
1123 candidate = candidates[i];
1125 if (candidate->fifo_checked) {
1126 continue; /* we have already evaluated that task */
1129 xbt_assert(__SD_task_is_in_fifo(candidate),
1130 "Bad state of candidate '%s': %d",
1131 SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1133 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1134 workstation = candidate->workstation_list[j];
1136 /* I can start on this workstation if the workstation is shared
1137 or if I am the first task in the fifo */
1138 can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS
1140 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1141 (workstation->task_fifo));
1144 XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1147 /* now we are sure that I can start! */
1149 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1150 workstation = candidate->workstation_list[j];
1152 /* update the fifo */
1153 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1154 candidate = xbt_fifo_shift(workstation->task_fifo); /* the return value is stored just for debugging */
1155 XBT_DEBUG("Head of the fifo: '%s'",
1157 NULL) ? SD_task_get_name(candidate) : "NULL");
1158 xbt_assert(candidate == candidates[i],
1159 "Error in __SD_task_just_done: bad first task in the fifo");
1161 } /* for each workstation */
1163 /* finally execute the task */
1164 XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1165 (int)SD_task_get_state(candidate));
1166 __SD_task_really_run(candidate);
1169 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1170 SD_task_get_name(candidate), candidate->state_set,
1171 sd_global->running_task_set, __SD_task_is_running(candidate));
1172 xbt_assert(__SD_task_is_running(candidate),
1173 "Bad state of task '%s': %d",
1174 SD_task_get_name(candidate),
1175 (int)SD_task_get_state(candidate));
1176 XBT_DEBUG("Okay, the task is running.");
1179 candidate->fifo_checked = 1;
1180 } /* for each candidate */
1182 xbt_free(candidates);
1185 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1187 static void __SD_task_remove_dependencies(SD_task_t task)
1189 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1190 because each one is stored twice */
1191 SD_dependency_t dependency;
1192 while (!xbt_dynar_is_empty(task->tasks_before)) {
1193 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1194 SD_task_dependency_remove(dependency->src, dependency->dst);
1197 while (!xbt_dynar_is_empty(task->tasks_after)) {
1198 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1199 SD_task_dependency_remove(dependency->src, dependency->dst);
1204 * \brief Returns the start time of a task
1206 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1208 * \param task: a task
1209 * \return the start time of this task
1211 double SD_task_get_start_time(SD_task_t task)
1213 if (task->surf_action)
1214 return surf_workstation_model->
1215 action_get_start_time(task->surf_action);
1217 return task->start_time;
1221 * \brief Returns the finish time of a task
1223 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1224 * If the state is not completed yet, the returned value is an
1225 * estimation of the task finish time. This value can fluctuate
1226 * until the task is completed.
1228 * \param task: a task
1229 * \return the start time of this task
1231 double SD_task_get_finish_time(SD_task_t task)
1233 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1234 return surf_workstation_model->
1235 action_get_finish_time(task->surf_action);
1237 return task->finish_time;
1240 static XBT_INLINE SD_task_t SD_task_create_sized(const char *name,
1241 void *data, double amount,
1244 SD_task_t task = SD_task_create(name, data, amount);
1245 task->communication_amount = xbt_new0(double, ws_count * ws_count);
1246 task->computation_amount = xbt_new0(double, ws_count);
1247 task->workstation_nb = ws_count;
1248 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1252 /** @brief create a end-to-end communication task that can then be auto-scheduled
1254 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1255 * allows to specify the task costs at creation, and decorelate them from the
1256 * scheduling process where you just specify which resource should deliver the
1259 * A end-to-end communication must be scheduled on 2 hosts, and the amount
1260 * specified at creation is sent from hosts[0] to hosts[1].
1262 SD_task_t SD_task_create_comm_e2e(const char *name, void *data,
1265 SD_task_t res = SD_task_create_sized(name, data, amount, 2);
1266 res->communication_amount[2] = amount;
1267 res->kind = SD_TASK_COMM_E2E;
1271 /** @brief create a sequential computation task that can then be auto-scheduled
1273 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1274 * allows to specify the task costs at creation, and decorelate them from the
1275 * scheduling process where you just specify which resource should deliver the
1278 * A sequential computation must be scheduled on 1 host, and the amount
1279 * specified at creation to be run on hosts[0].
1281 SD_task_t SD_task_create_comp_seq(const char *name, void *data,
1284 SD_task_t res = SD_task_create_sized(name, data, amount, 1);
1285 res->computation_amount[0] = amount;
1286 res->kind = SD_TASK_COMP_SEQ;
1290 /** @brief Auto-schedules a task.
1292 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1293 * allows to specify the task costs at creation, and decorelate them from the
1294 * scheduling process where you just specify which resource should deliver the
1297 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1298 * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1302 * We should create tasks kind for the following categories:
1303 * - Point to point communication (done)
1304 * - Sequential computation (done)
1305 * - group communication (redistribution, several kinds)
1306 * - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1307 * - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1309 void SD_task_schedulev(SD_task_t task, int count,
1310 const SD_workstation_t * list)
1313 SD_dependency_t dep;
1315 xbt_assert(task->kind != 0,
1316 "Task %s is not typed. Cannot automatically schedule it.",
1317 SD_task_get_name(task));
1318 switch (task->kind) {
1319 case SD_TASK_COMM_E2E:
1320 case SD_TASK_COMP_SEQ:
1321 xbt_assert(task->workstation_nb == count,"Got %d locations, but were expecting %d locations",count,task->workstation_nb);
1322 for (i = 0; i < count; i++)
1323 task->workstation_list[i] = list[i];
1324 SD_task_do_schedule(task);
1327 xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1328 SD_task_get_name(task));
1330 if (task->kind == SD_TASK_COMM_E2E) {
1331 XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1332 SD_task_get_name(task),
1333 SD_workstation_get_name(task->workstation_list[0]),
1334 SD_workstation_get_name(task->workstation_list[1]),
1335 task->communication_amount[2]);
1338 /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if runnable) */
1339 if (task->kind == SD_TASK_COMP_SEQ) {
1340 XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1341 SD_task_get_name(task),
1342 SD_workstation_get_name(task->workstation_list[0]),
1343 task->computation_amount[0]);
1345 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1346 SD_task_t before = dep->src;
1347 if (before->kind == SD_TASK_COMM_E2E) {
1348 before->workstation_list[1] = task->workstation_list[0];
1350 if (before->workstation_list[0] &&
1351 (__SD_task_is_schedulable(before)
1352 || __SD_task_is_not_scheduled(before))) {
1353 SD_task_do_schedule(before);
1355 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1356 SD_task_get_name(before),
1357 SD_workstation_get_name(before->workstation_list[0]),
1358 SD_workstation_get_name(before->workstation_list[1]),
1359 before->communication_amount[2]);
1363 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1364 SD_task_t after = dep->dst;
1365 if (after->kind == SD_TASK_COMM_E2E) {
1366 after->workstation_list[0] = task->workstation_list[0];
1367 //J-N : Why did you comment on these line (this comment add a bug I think)?
1368 if (after->workstation_list[1]
1369 && (__SD_task_is_not_scheduled(after)
1370 || __SD_task_is_schedulable(after))) {
1371 SD_task_do_schedule(after);
1373 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1374 SD_task_get_name(after),
1375 SD_workstation_get_name(after->workstation_list[0]),
1376 SD_workstation_get_name(after->workstation_list[1]),
1377 after->communication_amount[2]);
1385 /** @brief autoschedule a task on a list of workstations
1387 * This function is very similar to SD_task_schedulev(),
1388 * but takes the list of workstations to schedule onto as separate parameters.
1389 * It builds a proper vector of workstations and then call SD_task_schedulev()
1391 void SD_task_schedulel(SD_task_t task, int count, ...)
1394 SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1396 va_start(ap, count);
1397 for (i = 0; i < count; i++) {
1398 list[i] = va_arg(ap, SD_workstation_t);
1401 SD_task_schedulev(task, count, list);
1406 * \brief Sets the tracing category of a task.
1408 * This function should be called after the creation of a
1409 * SimDAG task, to define the category of that task. The first
1410 * parameter must contain a task that was created with the
1411 * function #SD_task_create. The second parameter must contain
1412 * a category that was previously declared with the function
1415 * \param task The task to be considered
1416 * \param category the name of the category to be associated to the task
1418 * \see SD_task_get_category, TRACE_category, TRACE_category_with_color
1420 void SD_task_set_category (SD_task_t task, const char *category)
1423 if (!TRACE_is_enabled()) return;
1424 if (task == NULL) return;
1425 if (category == NULL){
1426 if (task->category) xbt_free (task->category);
1427 task->category = NULL;
1429 task->category = xbt_strdup (category);
1435 * \brief Gets the current tracing category of a task.
1437 * \param task The task to be considered
1439 * \see SD_task_set_category
1441 * \return Returns the name of the tracing category of the given task, NULL otherwise
1443 const char *SD_task_get_category (SD_task_t task)
1446 return task->category;