1 /* Copyright (c) 2006, 2007, 2008, 2009, 2010. 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);
20 * \brief Creates a new task.
22 * \param name the name of the task (can be \c NULL)
23 * \param data the user data you want to associate with the task (can be \c NULL)
24 * \param amount amount of the task
25 * \return the new task
26 * \see SD_task_destroy()
28 SD_task_t SD_task_create(const char *name, void *data, double amount)
34 task = xbt_new(s_SD_task_t, 1);
36 /* general information */
37 task->data = data; /* user data */
38 task->name = xbt_strdup(name);
39 task->kind = SD_TASK_NOT_TYPED;
40 task->state_hookup.prev = NULL;
41 task->state_hookup.next = NULL;
42 task->state_set = sd_global->not_scheduled_task_set;
43 task->state = SD_NOT_SCHEDULED;
45 xbt_swag_insert(task, task->state_set);
47 task->amount = amount;
48 task->remains = amount;
49 task->start_time = -1.0;
50 task->finish_time = -1.0;
51 task->surf_action = NULL;
52 task->watch_points = 0;
55 task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
56 task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
57 task->unsatisfied_dependencies = 0;
58 task->is_not_ready = 0;
60 /* scheduling parameters */
61 task->workstation_nb = 0;
62 task->workstation_list = NULL;
63 task->computation_amount = NULL;
64 task->communication_amount = NULL;
67 sd_global->task_number++;
70 TRACE_sd_task_create(task);
77 * \brief Returns the user data of a task
80 * \return the user data associated with this task (can be \c NULL)
81 * \see SD_task_set_data()
83 void *SD_task_get_data(SD_task_t task)
86 xbt_assert(task != NULL, "Invalid parameter");
91 * \brief Sets the user data of a task
93 * The new data can be \c NULL. The old data should have been freed first
94 * if it was not \c NULL.
97 * \param data the new data you want to associate with this task
98 * \see SD_task_get_data()
100 void SD_task_set_data(SD_task_t task, void *data)
102 SD_CHECK_INIT_DONE();
103 xbt_assert(task != NULL, "Invalid parameter");
108 * \brief Returns the state of a task
111 * \return the current \ref e_SD_task_state_t "state" of this task:
112 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
113 * \see e_SD_task_state_t
115 e_SD_task_state_t SD_task_get_state(SD_task_t task)
117 SD_CHECK_INIT_DONE();
118 xbt_assert(task != NULL, "Invalid parameter");
122 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
124 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
126 xbt_swag_remove(task, task->state_set);
128 case SD_NOT_SCHEDULED:
129 task->state_set = sd_global->not_scheduled_task_set;
132 task->state_set = sd_global->schedulable_task_set;
135 task->state_set = sd_global->scheduled_task_set;
138 task->state_set = sd_global->runnable_task_set;
141 task->state_set = sd_global->in_fifo_task_set;
144 task->state_set = sd_global->running_task_set;
146 surf_workstation_model->action_get_start_time(task->surf_action);
149 task->state_set = sd_global->done_task_set;
151 surf_workstation_model->action_get_finish_time(task->surf_action);
154 jedule_log_sd_event(task);
158 task->state_set = sd_global->failed_task_set;
161 xbt_die( "Invalid state");
163 xbt_swag_insert(task, task->state_set);
164 task->state = new_state;
166 if (task->watch_points & new_state) {
167 XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
168 sd_global->watch_point_reached = 1;
169 SD_task_unwatch(task, new_state); /* remove the watch point */
174 * \brief Returns the name of a task
177 * \return the name of this task (can be \c NULL)
179 const char *SD_task_get_name(SD_task_t task)
181 SD_CHECK_INIT_DONE();
182 xbt_assert(task != NULL, "Invalid parameter");
186 /** @brief Allows to change the name of a task */
187 void SD_task_set_name(SD_task_t task, const char *name)
189 xbt_free(task->name);
190 task->name = xbt_strdup(name);
193 /** @brief Returns the dynar of the parents of a task
196 * \return a newly allocated dynar comprising the parents of this task
199 xbt_dynar_t SD_task_get_parents(SD_task_t task)
204 SD_CHECK_INIT_DONE();
205 xbt_assert(task != NULL, "Invalid parameter");
207 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
208 xbt_dynar_foreach(task->tasks_before, i, dep) {
209 xbt_dynar_push(parents, &(dep->src));
214 /** @brief Returns the dynar of the parents of a task
217 * \return a newly allocated dynar comprising the parents of this task
219 xbt_dynar_t SD_task_get_children(SD_task_t task)
222 xbt_dynar_t children;
224 SD_CHECK_INIT_DONE();
225 xbt_assert(task != NULL, "Invalid parameter");
227 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
228 xbt_dynar_foreach(task->tasks_after, i, dep) {
229 xbt_dynar_push(children, &(dep->dst));
235 * \brief Returns the amount of workstations involved in a task
237 * Only call this on already scheduled tasks!
240 int SD_task_get_workstation_count(SD_task_t task)
242 SD_CHECK_INIT_DONE();
243 xbt_assert(task != NULL, "Invalid parameter");
244 //xbt_assert(task->state_set != sd_global->scheduled_task_set,
245 // "Unscheduled task %s", task->name);
246 return task->workstation_nb;
250 * \brief Returns the list of workstations involved in a task
252 * Only call this on already scheduled tasks!
255 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
257 SD_CHECK_INIT_DONE();
258 xbt_assert(task != NULL, "Invalid parameter");
259 //xbt_assert(task->state_set != sd_global->scheduled_task_set,
260 // "Unscheduled task %s", task->name);
261 return task->workstation_list;
265 * \brief Returns the total amount of work contained in a task
268 * \return the total amount of work (computation or data transfer) for this task
269 * \see SD_task_get_remaining_amount()
271 double SD_task_get_amount(SD_task_t task)
273 SD_CHECK_INIT_DONE();
274 xbt_assert(task != NULL, "Invalid parameter");
279 * \brief Returns the remaining amount work to do till the completion of a task
282 * \return the remaining amount of work (computation or data transfer) of this task
283 * \see SD_task_get_amount()
285 double SD_task_get_remaining_amount(SD_task_t task)
287 SD_CHECK_INIT_DONE();
288 xbt_assert(task != NULL, "Invalid parameter");
290 if (task->surf_action)
291 return surf_workstation_model->get_remains(task->surf_action);
293 return task->remains;
296 int SD_task_get_kind(SD_task_t task)
301 /** @brief Displays debugging informations about a task */
302 void SD_task_dump(SD_task_t task)
304 unsigned int counter;
305 SD_dependency_t dependency;
308 XBT_INFO("Displaying task %s", SD_task_get_name(task));
309 statename = bprintf("%s %s %s %s %s %s %s %s",
310 (task->state & SD_NOT_SCHEDULED ? "not scheduled" :
312 (task->state & SD_SCHEDULABLE ? "schedulable" : ""),
313 (task->state & SD_SCHEDULED ? "scheduled" : ""),
314 (task->state & SD_RUNNABLE ? "runnable" :
316 (task->state & SD_IN_FIFO ? "in fifo" : ""),
317 (task->state & SD_RUNNING ? "running" : ""),
318 (task->state & SD_DONE ? "done" : ""),
319 (task->state & SD_FAILED ? "failed" : ""));
320 XBT_INFO(" - state: %s", statename);
323 if (task->kind != 0) {
324 switch (task->kind) {
325 case SD_TASK_COMM_E2E:
326 XBT_INFO(" - kind: end-to-end communication");
328 case SD_TASK_COMP_SEQ:
329 XBT_INFO(" - kind: sequential computation");
332 XBT_INFO(" - (unknown kind %d)", task->kind);
335 XBT_INFO(" - amount: %.0f", SD_task_get_amount(task));
336 XBT_INFO(" - Dependencies to satisfy: %d", task->unsatisfied_dependencies);
337 if (xbt_dynar_length(task->tasks_before)) {
338 XBT_INFO(" - pre-dependencies:");
339 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
340 XBT_INFO(" %s", SD_task_get_name(dependency->src));
343 if (xbt_dynar_length(task->tasks_after)) {
344 XBT_INFO(" - post-dependencies:");
345 xbt_dynar_foreach(task->tasks_after, counter, dependency) {
346 XBT_INFO(" %s", SD_task_get_name(dependency->dst));
351 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
352 void SD_task_dotty(SD_task_t task, void *out)
354 unsigned int counter;
355 SD_dependency_t dependency;
356 fprintf(out, " T%p [label=\"%.20s\"", task, task->name);
357 switch (task->kind) {
358 case SD_TASK_COMM_E2E:
359 fprintf(out, ", shape=box");
361 case SD_TASK_COMP_SEQ:
362 fprintf(out, ", shape=circle");
365 xbt_die("Unknown task type!");
367 fprintf(out, "];\n");
368 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
369 fprintf(out, " T%p -> T%p;\n", dependency->src, dependency->dst);
373 /* Destroys a dependency between two tasks.
375 static void __SD_task_dependency_destroy(void *dependency)
377 if (((SD_dependency_t) dependency)->name != NULL)
378 xbt_free(((SD_dependency_t) dependency)->name);
379 xbt_free(dependency);
383 * \brief Adds a dependency between two tasks
385 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
386 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
388 * \param name the name of the new dependency (can be \c NULL)
389 * \param data the user data you want to associate with this dependency (can be \c NULL)
390 * \param src the task which must be executed first
391 * \param dst the task you want to make depend on \a src
392 * \see SD_task_dependency_remove()
394 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
401 SD_dependency_t dependency;
403 SD_CHECK_INIT_DONE();
404 xbt_assert(src != NULL && dst != NULL, "Invalid parameter");
406 dynar = src->tasks_after;
407 length = xbt_dynar_length(dynar);
411 "Cannot add a dependency between task '%s' and itself",
412 SD_task_get_name(src));
414 if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
415 && !__SD_task_is_scheduled_or_runnable(src))
417 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
418 SD_task_get_name(src));
420 if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
421 && !__SD_task_is_scheduled_or_runnable(dst))
423 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
424 SD_task_get_name(dst));
426 XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
427 SD_task_get_name(src), SD_task_get_name(dst));
428 for (i = 0; i < length && !found; i++) {
429 xbt_dynar_get_cpy(dynar, i, &dependency);
430 found = (dependency->dst == dst);
431 XBT_DEBUG("Dependency %d: dependency->dst = %s", i,
432 SD_task_get_name(dependency->dst));
437 "A dependency already exists between task '%s' and task '%s'",
438 SD_task_get_name(src), SD_task_get_name(dst));
440 dependency = xbt_new(s_SD_dependency_t, 1);
442 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
443 dependency->data = data;
444 dependency->src = src;
445 dependency->dst = dst;
447 /* src must be executed before dst */
448 xbt_dynar_push(src->tasks_after, &dependency);
449 xbt_dynar_push(dst->tasks_before, &dependency);
451 dst->unsatisfied_dependencies++;
454 /* if the task was runnable, then dst->tasks_before is not empty anymore,
455 so we must go back to state SD_SCHEDULED */
456 if (__SD_task_is_runnable(dst)) {
458 ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
459 SD_task_get_name(dst));
460 __SD_task_set_state(dst, SD_SCHEDULED);
463 /* __SD_print_dependencies(src);
464 __SD_print_dependencies(dst); */
468 * \brief Indacates whether there is a dependency between two tasks.
471 * \param dst a task depending on \a src
473 * If src is NULL, checks whether dst has any pre-dependency.
474 * If dst is NULL, checks whether src has any post-dependency.
476 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
478 unsigned int counter;
479 SD_dependency_t dependency;
481 SD_CHECK_INIT_DONE();
482 xbt_assert(src != NULL
484 "Invalid parameter: both src and dst are NULL");
488 xbt_dynar_foreach(src->tasks_after, counter, dependency) {
489 if (dependency->dst == dst)
493 return xbt_dynar_length(src->tasks_after);
496 return xbt_dynar_length(dst->tasks_before);
502 * \brief Remove a dependency between two tasks
505 * \param dst a task depending on \a src
506 * \see SD_task_dependency_add()
508 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
515 SD_dependency_t dependency;
517 SD_CHECK_INIT_DONE();
518 xbt_assert(src != NULL && dst != NULL, "Invalid parameter");
520 /* remove the dependency from src->tasks_after */
521 dynar = src->tasks_after;
522 length = xbt_dynar_length(dynar);
524 for (i = 0; i < length && !found; i++) {
525 xbt_dynar_get_cpy(dynar, i, &dependency);
526 if (dependency->dst == dst) {
527 xbt_dynar_remove_at(dynar, i, NULL);
533 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
534 SD_task_get_name(src), SD_task_get_name(dst),
535 SD_task_get_name(dst), SD_task_get_name(src));
537 /* remove the dependency from dst->tasks_before */
538 dynar = dst->tasks_before;
539 length = xbt_dynar_length(dynar);
542 for (i = 0; i < length && !found; i++) {
543 xbt_dynar_get_cpy(dynar, i, &dependency);
544 if (dependency->src == src) {
545 xbt_dynar_remove_at(dynar, i, NULL);
546 __SD_task_dependency_destroy(dependency);
547 dst->unsatisfied_dependencies--;
552 /* should never happen... */
554 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
555 SD_task_get_name(dst), SD_task_get_name(src),
556 SD_task_get_name(src), SD_task_get_name(dst));
558 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
560 if (dst->unsatisfied_dependencies == 0) {
561 if (__SD_task_is_scheduled(dst))
562 __SD_task_set_state(dst, SD_RUNNABLE);
564 __SD_task_set_state(dst, SD_SCHEDULABLE);
567 if (dst->is_not_ready == 0)
568 __SD_task_set_state(dst, SD_SCHEDULABLE);
570 /* __SD_print_dependencies(src);
571 __SD_print_dependencies(dst); */
575 * \brief Returns the user data associated with a dependency between two tasks
578 * \param dst a task depending on \a src
579 * \return the user data associated with this dependency (can be \c NULL)
580 * \see SD_task_dependency_add()
582 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
589 SD_dependency_t dependency;
592 SD_CHECK_INIT_DONE();
593 xbt_assert(src != NULL && dst != NULL, "Invalid parameter");
595 dynar = src->tasks_after;
596 length = xbt_dynar_length(dynar);
598 for (i = 0; i < length && !found; i++) {
599 xbt_dynar_get_cpy(dynar, i, &dependency);
600 found = (dependency->dst == dst);
603 THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
604 SD_task_get_name(src), SD_task_get_name(dst));
605 return dependency->data;
608 /* temporary function for debugging */
609 static void __SD_print_watch_points(SD_task_t task)
611 static const int state_masks[] =
612 { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE,
615 static const char *state_names[] =
616 { "schedulable", "scheduled", "running", "runnable", "done",
621 XBT_INFO("Task '%s' watch points (%x): ", SD_task_get_name(task),
625 for (i = 0; i < 5; i++) {
626 if (task->watch_points & state_masks[i])
627 XBT_INFO("%s ", state_names[i]);
632 * \brief Adds a watch point to a task
634 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
635 * task becomes the one given in argument. The
636 * watch point is then automatically removed.
639 * \param state the \ref e_SD_task_state_t "state" you want to watch
640 * (cannot be #SD_NOT_SCHEDULED)
641 * \see SD_task_unwatch()
643 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
645 SD_CHECK_INIT_DONE();
646 xbt_assert(task != NULL, "Invalid parameter");
648 if (state & SD_NOT_SCHEDULED)
650 "Cannot add a watch point for state SD_NOT_SCHEDULED");
652 task->watch_points = task->watch_points | state;
653 /* __SD_print_watch_points(task); */
657 * \brief Removes a watch point from a task
660 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
661 * \see SD_task_watch()
663 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
665 SD_CHECK_INIT_DONE();
666 xbt_assert(task != NULL, "Invalid parameter");
667 xbt_assert(state != SD_NOT_SCHEDULED,
668 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
670 task->watch_points = task->watch_points & ~state;
671 /* __SD_print_watch_points(task); */
675 * \brief Returns an approximative estimation of the execution time of a task.
677 * The estimation is very approximative because the value returned is the time
678 * the task would take if it was executed now and if it was the only task.
680 * \param task the task to evaluate
681 * \param workstation_nb number of workstations on which the task would be executed
682 * \param workstation_list the workstations on which the task would be executed
683 * \param computation_amount computation amount for each workstation
684 * \param communication_amount communication amount between each pair of workstations
687 double SD_task_get_execution_time(SD_task_t task,
689 const SD_workstation_t *
691 const double *computation_amount,
692 const double *communication_amount)
694 double time, max_time = 0.0;
696 SD_CHECK_INIT_DONE();
697 xbt_assert(task != NULL && workstation_nb > 0
698 && workstation_list != NULL, "Invalid parameter");
700 /* the task execution time is the maximum execution time of the parallel tasks */
702 for (i = 0; i < workstation_nb; i++) {
704 if (computation_amount != NULL)
706 SD_workstation_get_computation_time(workstation_list[i],
707 computation_amount[i]);
709 if (communication_amount != NULL)
710 for (j = 0; j < workstation_nb; j++) {
712 SD_route_get_communication_time(workstation_list[i],
714 communication_amount[i *
719 if (time > max_time) {
726 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
728 SD_CHECK_INIT_DONE();
730 if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task))
731 THROWF(arg_error, 0, "Task '%s' has already been scheduled",
732 SD_task_get_name(task));
734 /* update the task state */
735 if (task->unsatisfied_dependencies == 0)
736 __SD_task_set_state(task, SD_RUNNABLE);
738 __SD_task_set_state(task, SD_SCHEDULED);
742 * \brief Schedules a task
744 * The task state must be #SD_NOT_SCHEDULED.
745 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
746 * i.e. when its dependencies are satisfied.
748 * \param task the task you want to schedule
749 * \param workstation_nb number of workstations on which the task will be executed
750 * \param workstation_list the workstations on which the task will be executed
751 * \param computation_amount computation amount for each workstation
752 * \param communication_amount communication amount between each pair of workstations
753 * \param rate task execution speed rate
754 * \see SD_task_unschedule()
756 void SD_task_schedule(SD_task_t task, int workstation_count,
757 const SD_workstation_t * workstation_list,
758 const double *computation_amount,
759 const double *communication_amount, double rate)
761 int communication_nb;
762 task->workstation_nb = 0;
764 xbt_assert(workstation_count > 0, "workstation_nb must be positive");
766 task->workstation_nb = workstation_count;
769 if (computation_amount) {
770 task->computation_amount = xbt_realloc(task->computation_amount,
771 sizeof(double) * workstation_count);
772 memcpy(task->computation_amount, computation_amount,
773 sizeof(double) * workstation_count);
775 xbt_free(task->computation_amount);
776 task->computation_amount = NULL;
779 communication_nb = workstation_count * workstation_count;
780 if (communication_amount) {
781 task->communication_amount = xbt_realloc(task->communication_amount,
782 sizeof(double) * communication_nb);
783 memcpy(task->communication_amount, communication_amount,
784 sizeof(double) * communication_nb);
786 xbt_free(task->communication_amount);
787 task->communication_amount = NULL;
790 task->workstation_list =
791 xbt_realloc(task->workstation_list,
792 sizeof(SD_workstation_t) * workstation_count);
793 memcpy(task->workstation_list, workstation_list,
794 sizeof(SD_workstation_t) * workstation_count);
796 SD_task_do_schedule(task);
800 * \brief Unschedules a task
802 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
803 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
804 * Call SD_task_schedule() to schedule it again.
806 * \param task the task you want to unschedule
807 * \see SD_task_schedule()
809 void SD_task_unschedule(SD_task_t task)
811 SD_CHECK_INIT_DONE();
812 xbt_assert(task != NULL, "Invalid parameter");
814 if (task->state_set != sd_global->scheduled_task_set &&
815 task->state_set != sd_global->runnable_task_set &&
816 task->state_set != sd_global->running_task_set &&
817 task->state_set != sd_global->failed_task_set)
819 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
820 SD_task_get_name(task));
822 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
823 &&task->kind == SD_TASK_NOT_TYPED) /* Don't free scheduling data for typed tasks */
824 __SD_task_destroy_scheduling_data(task);
826 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
827 surf_workstation_model->action_cancel(task->surf_action);
829 if (task->unsatisfied_dependencies == 0)
830 __SD_task_set_state(task, SD_SCHEDULABLE);
832 __SD_task_set_state(task, SD_NOT_SCHEDULED);
834 task->remains = task->amount;
835 task->start_time = -1.0;
838 /* Destroys the data memorized by SD_task_schedule. Task state must be SD_SCHEDULED or SD_RUNNABLE.
840 static void __SD_task_destroy_scheduling_data(SD_task_t task)
842 SD_CHECK_INIT_DONE();
843 if (!__SD_task_is_scheduled_or_runnable(task)
844 && !__SD_task_is_in_fifo(task))
846 "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
847 SD_task_get_name(task));
849 xbt_free(task->computation_amount);
850 xbt_free(task->communication_amount);
851 task->computation_amount = task->communication_amount = NULL;
854 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
855 * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
856 * the task gets out of its fifos.
858 void __SD_task_really_run(SD_task_t task)
862 void **surf_workstations;
864 SD_CHECK_INIT_DONE();
865 xbt_assert(task != NULL, "Invalid parameter");
866 xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
867 "Task '%s' is not runnable or in a fifo! Task state: %d",
868 SD_task_get_name(task), SD_task_get_state(task));
869 xbt_assert(task->workstation_list != NULL,
870 "Task '%s': workstation_list is NULL!",
871 SD_task_get_name(task));
875 XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
877 /* set this task as current task for the workstations in sequential mode */
878 for (i = 0; i < task->workstation_nb; i++) {
879 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
880 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
881 task->workstation_list[i]->current_task = task;
882 xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
883 "The workstation should be busy now");
887 XBT_DEBUG("Task '%s' set as current task for its workstations",
888 SD_task_get_name(task));
892 /* we have to create a Surf workstation array instead of the SimDag workstation array */
893 surf_workstations = xbt_new(void *, task->workstation_nb);
895 for (i = 0; i < task->workstation_nb; i++)
896 surf_workstations[i] = task->workstation_list[i]->surf_workstation;
898 /* 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 */
899 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
901 task->surf_action = NULL;
902 if ((task->workstation_nb == 1)
903 && (cost_or_zero(task->communication_amount, 0) == 0.0)) {
905 surf_workstation_model->extension.
906 workstation.execute(surf_workstations[0],
907 cost_or_zero(task->computation_amount, 0));
908 } else if ((task->workstation_nb == 1)
909 && (cost_or_zero(task->computation_amount, 0) == 0.0)) {
912 surf_workstation_model->extension.
913 workstation.communicate(surf_workstations[0], surf_workstations[0],
914 cost_or_zero(task->communication_amount,
916 } else if ((task->workstation_nb == 2)
917 && (cost_or_zero(task->computation_amount, 0) == 0.0)
918 && (cost_or_zero(task->computation_amount, 1) == 0.0)) {
922 for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
923 if (cost_or_zero(task->communication_amount, i) > 0.0) {
925 value = cost_or_zero(task->communication_amount, i);
930 surf_workstation_model->extension.
931 workstation.communicate(surf_workstations[0],
932 surf_workstations[1], value, task->rate);
937 if (!task->surf_action) {
938 double *computation_amount = xbt_new(double, task->workstation_nb);
939 double *communication_amount = xbt_new(double, task->workstation_nb *
940 task->workstation_nb);
942 memcpy(computation_amount, task->computation_amount, sizeof(double) *
943 task->workstation_nb);
944 memcpy(communication_amount, task->communication_amount,
945 sizeof(double) * task->workstation_nb * task->workstation_nb);
948 surf_workstation_model->extension.
949 workstation.execute_parallel_task(task->workstation_nb,
952 communication_amount,
953 task->amount, task->rate);
955 xbt_free(surf_workstations);
958 surf_workstation_model->action_data_set(task->surf_action, task);
960 XBT_DEBUG("surf_action = %p", task->surf_action);
964 TRACE_surf_action(task->surf_action, task->category);
967 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
968 __SD_task_set_state(task, SD_RUNNING);
969 xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
970 SD_task_get_name(task), SD_task_get_state(task));
974 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_RUNNABLE
975 * (ie when its dependencies are satisfied).
976 * If one of the workstations where the task is scheduled on is busy (in sequential mode),
977 * the task doesn't start.
978 * Returns whether the task has started.
980 int __SD_task_try_to_run(SD_task_t task)
985 SD_workstation_t workstation;
987 SD_CHECK_INIT_DONE();
988 xbt_assert(task != NULL, "Invalid parameter");
989 xbt_assert(__SD_task_is_runnable(task),
990 "Task '%s' is not runnable! Task state: %d",
991 SD_task_get_name(task), SD_task_get_state(task));
994 for (i = 0; i < task->workstation_nb; i++) {
995 can_start = can_start &&
996 !__SD_workstation_is_busy(task->workstation_list[i]);
999 XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1001 if (!can_start) { /* if the task cannot start and is not in the fifos yet */
1002 for (i = 0; i < task->workstation_nb; i++) {
1003 workstation = task->workstation_list[i];
1004 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1005 XBT_DEBUG("Pushing task '%s' in the fifo of workstation '%s'",
1006 SD_task_get_name(task),
1007 SD_workstation_get_name(workstation));
1008 xbt_fifo_push(workstation->task_fifo, task);
1011 __SD_task_set_state(task, SD_IN_FIFO);
1012 xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1013 SD_task_get_name(task), SD_task_get_state(task));
1014 XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1016 __SD_task_really_run(task);
1022 /* This function is called by SD_simulate when a task is done.
1023 * It updates task->state and task->action and executes if necessary the tasks
1024 * which were waiting in fifos for the end of `task'
1026 void __SD_task_just_done(SD_task_t task)
1029 SD_workstation_t workstation;
1031 SD_task_t candidate;
1032 int candidate_nb = 0;
1033 int candidate_capacity = 8;
1034 SD_task_t *candidates;
1037 SD_CHECK_INIT_DONE();
1038 xbt_assert(task != NULL, "Invalid parameter");
1039 xbt_assert(__SD_task_is_running(task),
1040 "The task must be running! Task state: %d",
1041 SD_task_get_state(task));
1042 xbt_assert(task->workstation_list != NULL,
1043 "Task '%s': workstation_list is NULL!",
1044 SD_task_get_name(task));
1047 candidates = xbt_new(SD_task_t, 8);
1049 __SD_task_set_state(task, SD_DONE);
1050 surf_workstation_model->action_unref(task->surf_action);
1051 task->surf_action = NULL;
1053 XBT_DEBUG("Looking for candidates");
1055 /* if the task was executed on sequential workstations,
1056 maybe we can execute the next task of the fifo for each workstation */
1057 for (i = 0; i < task->workstation_nb; i++) {
1058 workstation = task->workstation_list[i];
1059 XBT_DEBUG("Workstation '%s': access_mode = %d",
1060 SD_workstation_get_name(workstation), workstation->access_mode);
1061 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1062 xbt_assert(workstation->task_fifo != NULL,
1063 "Workstation '%s' has sequential access but no fifo!",
1064 SD_workstation_get_name(workstation));
1065 xbt_assert(workstation->current_task =
1066 task, "Workstation '%s': current task should be '%s'",
1067 SD_workstation_get_name(workstation),
1068 SD_task_get_name(task));
1070 /* the task is over so we can release the workstation */
1071 workstation->current_task = NULL;
1073 XBT_DEBUG("Getting candidate in fifo");
1075 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1076 (workstation->task_fifo));
1078 if (candidate != NULL) {
1079 XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1080 xbt_assert(__SD_task_is_in_fifo(candidate),
1081 "Bad state of candidate '%s': %d",
1082 SD_task_get_name(candidate),
1083 SD_task_get_state(candidate));
1086 XBT_DEBUG("Candidate in fifo: %p", candidate);
1088 /* if there was a task waiting for my place */
1089 if (candidate != NULL) {
1090 /* Unfortunately, we are not sure yet that we can execute the task now,
1091 because the task can be waiting more deeply in some other workstation's fifos...
1092 So we memorize all candidate tasks, and then we will check for each candidate
1093 whether or not all its workstations are available. */
1095 /* realloc if necessary */
1096 if (candidate_nb == candidate_capacity) {
1097 candidate_capacity *= 2;
1099 xbt_realloc(candidates,
1100 sizeof(SD_task_t) * candidate_capacity);
1103 /* register the candidate */
1104 candidates[candidate_nb++] = candidate;
1105 candidate->fifo_checked = 0;
1110 XBT_DEBUG("Candidates found: %d", candidate_nb);
1112 /* now we check every candidate task */
1113 for (i = 0; i < candidate_nb; i++) {
1114 candidate = candidates[i];
1116 if (candidate->fifo_checked) {
1117 continue; /* we have already evaluated that task */
1120 xbt_assert(__SD_task_is_in_fifo(candidate),
1121 "Bad state of candidate '%s': %d",
1122 SD_task_get_name(candidate), SD_task_get_state(candidate));
1124 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1125 workstation = candidate->workstation_list[j];
1127 /* I can start on this workstation if the workstation is shared
1128 or if I am the first task in the fifo */
1129 can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS
1131 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1132 (workstation->task_fifo));
1135 XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1138 /* now we are sure that I can start! */
1140 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1141 workstation = candidate->workstation_list[j];
1143 /* update the fifo */
1144 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1145 candidate = xbt_fifo_shift(workstation->task_fifo); /* the return value is stored just for debugging */
1146 XBT_DEBUG("Head of the fifo: '%s'",
1148 NULL) ? SD_task_get_name(candidate) : "NULL");
1149 xbt_assert(candidate == candidates[i],
1150 "Error in __SD_task_just_done: bad first task in the fifo");
1152 } /* for each workstation */
1154 /* finally execute the task */
1155 XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1156 SD_task_get_state(candidate));
1157 __SD_task_really_run(candidate);
1160 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1161 SD_task_get_name(candidate), candidate->state_set,
1162 sd_global->running_task_set, __SD_task_is_running(candidate));
1163 xbt_assert(__SD_task_is_running(candidate),
1164 "Bad state of task '%s': %d",
1165 SD_task_get_name(candidate),
1166 SD_task_get_state(candidate));
1167 XBT_DEBUG("Okay, the task is running.");
1170 candidate->fifo_checked = 1;
1171 } /* for each candidate */
1173 xbt_free(candidates);
1176 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1178 static void __SD_task_remove_dependencies(SD_task_t task)
1180 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1181 because each one is stored twice */
1182 SD_dependency_t dependency;
1183 while (xbt_dynar_length(task->tasks_before) > 0) {
1184 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1185 SD_task_dependency_remove(dependency->src, dependency->dst);
1188 while (xbt_dynar_length(task->tasks_after) > 0) {
1189 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1190 SD_task_dependency_remove(dependency->src, dependency->dst);
1195 * \brief Returns the start time of a task
1197 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1199 * \param task: a task
1200 * \return the start time of this task
1202 double SD_task_get_start_time(SD_task_t task)
1204 SD_CHECK_INIT_DONE();
1205 xbt_assert(task != NULL, "Invalid parameter");
1206 if (task->surf_action)
1207 return surf_workstation_model->
1208 action_get_start_time(task->surf_action);
1210 return task->start_time;
1214 * \brief Returns the finish time of a task
1216 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1217 * If the state is not completed yet, the returned value is an
1218 * estimation of the task finish time. This value can fluctuate
1219 * until the task is completed.
1221 * \param task: a task
1222 * \return the start time of this task
1224 double SD_task_get_finish_time(SD_task_t task)
1226 SD_CHECK_INIT_DONE();
1227 xbt_assert(task != NULL, "Invalid parameter");
1229 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1230 return surf_workstation_model->
1231 action_get_finish_time(task->surf_action);
1233 return task->finish_time;
1237 * \brief Destroys a task.
1239 * The user data (if any) should have been destroyed first.
1241 * \param task the task you want to destroy
1242 * \see SD_task_create()
1244 void SD_task_destroy(SD_task_t task)
1246 SD_CHECK_INIT_DONE();
1247 xbt_assert(task != NULL, "Invalid parameter");
1249 XBT_DEBUG("Destroying task %s...", SD_task_get_name(task));
1251 __SD_task_remove_dependencies(task);
1252 /* if the task was scheduled or runnable we have to free the scheduling parameters */
1253 if (__SD_task_is_scheduled_or_runnable(task))
1254 __SD_task_destroy_scheduling_data(task);
1255 xbt_swag_remove(task, task->state_set);
1257 if (task->name != NULL)
1258 xbt_free(task->name);
1260 if (task->surf_action != NULL)
1261 surf_workstation_model->action_unref(task->surf_action);
1263 if (task->workstation_list != NULL)
1264 xbt_free(task->workstation_list);
1266 if (task->communication_amount)
1267 xbt_free(task->communication_amount);
1269 if (task->computation_amount)
1270 xbt_free(task->computation_amount);
1273 TRACE_sd_task_destroy(task);
1276 xbt_dynar_free(&task->tasks_before);
1277 xbt_dynar_free(&task->tasks_after);
1280 sd_global->task_number--;
1282 XBT_DEBUG("Task destroyed.");
1286 static XBT_INLINE SD_task_t SD_task_create_sized(const char *name,
1287 void *data, double amount,
1290 SD_task_t task = SD_task_create(name, data, amount);
1291 task->communication_amount = xbt_new0(double, ws_count * ws_count);
1292 task->computation_amount = xbt_new0(double, ws_count);
1293 task->workstation_nb = ws_count;
1294 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1298 /** @brief create a end-to-end communication task that can then be auto-scheduled
1300 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1301 * allows to specify the task costs at creation, and decorelate them from the
1302 * scheduling process where you just specify which resource should deliver the
1305 * A end-to-end communication must be scheduled on 2 hosts, and the amount
1306 * specified at creation is sent from hosts[0] to hosts[1].
1308 SD_task_t SD_task_create_comm_e2e(const char *name, void *data,
1311 SD_task_t res = SD_task_create_sized(name, data, amount, 2);
1312 res->communication_amount[2] = amount;
1313 res->kind = SD_TASK_COMM_E2E;
1317 /** @brief create a sequential computation task that can then be auto-scheduled
1319 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1320 * allows to specify the task costs at creation, and decorelate them from the
1321 * scheduling process where you just specify which resource should deliver the
1324 * A sequential computation must be scheduled on 1 host, and the amount
1325 * specified at creation to be run on hosts[0].
1327 SD_task_t SD_task_create_comp_seq(const char *name, void *data,
1330 SD_task_t res = SD_task_create_sized(name, data, amount, 1);
1331 res->computation_amount[0] = amount;
1332 res->kind = SD_TASK_COMP_SEQ;
1336 /** @brief Auto-schedules a task.
1338 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1339 * allows to specify the task costs at creation, and decorelate them from the
1340 * scheduling process where you just specify which resource should deliver the
1343 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1344 * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1348 * We should create tasks kind for the following categories:
1349 * - Point to point communication (done)
1350 * - Sequential computation (done)
1351 * - group communication (redistribution, several kinds)
1352 * - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1353 * - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1355 void SD_task_schedulev(SD_task_t task, int count,
1356 const SD_workstation_t * list)
1359 SD_dependency_t dep;
1361 xbt_assert(task->kind != 0,
1362 "Task %s is not typed. Cannot automatically schedule it.",
1363 SD_task_get_name(task));
1364 switch (task->kind) {
1365 case SD_TASK_COMM_E2E:
1366 case SD_TASK_COMP_SEQ:
1367 xbt_assert(task->workstation_nb == count);
1368 for (i = 0; i < count; i++)
1369 task->workstation_list[i] = list[i];
1370 SD_task_do_schedule(task);
1373 xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1374 SD_task_get_name(task));
1376 if (task->kind == SD_TASK_COMM_E2E) {
1377 XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1378 SD_task_get_name(task),
1379 SD_workstation_get_name(task->workstation_list[0]),
1380 SD_workstation_get_name(task->workstation_list[1]),
1381 task->communication_amount[2]);
1384 /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if runnable) */
1385 if (task->kind == SD_TASK_COMP_SEQ) {
1386 XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1387 SD_task_get_name(task),
1388 SD_workstation_get_name(task->workstation_list[0]),
1389 task->computation_amount[0]);
1391 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1392 SD_task_t before = dep->src;
1393 if (before->kind == SD_TASK_COMM_E2E) {
1394 before->workstation_list[1] = task->workstation_list[0];
1396 if (before->workstation_list[0] &&
1397 (__SD_task_is_schedulable(before)
1398 || __SD_task_is_not_scheduled(before))) {
1399 SD_task_do_schedule(before);
1401 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1402 SD_task_get_name(before),
1403 SD_workstation_get_name(before->workstation_list[0]),
1404 SD_workstation_get_name(before->workstation_list[1]),
1405 before->communication_amount[2]);
1409 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1410 SD_task_t after = dep->dst;
1411 if (after->kind == SD_TASK_COMM_E2E) {
1412 after->workstation_list[0] = task->workstation_list[0];
1413 //J-N : Why did you comment on these line (this comment add a bug I think)?
1414 if (after->workstation_list[1]
1415 && (__SD_task_is_not_scheduled(after)
1416 || __SD_task_is_schedulable(after))) {
1417 SD_task_do_schedule(after);
1419 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1420 SD_task_get_name(after),
1421 SD_workstation_get_name(after->workstation_list[0]),
1422 SD_workstation_get_name(after->workstation_list[1]),
1423 after->communication_amount[2]);
1431 /** @brief autoschedule a task on a list of workstations
1433 * This function is very similar to SD_task_schedulev(),
1434 * but takes the list of workstations to schedule onto as separate parameters.
1435 * It builds a proper vector of workstations and then call SD_task_schedulev()
1437 void SD_task_schedulel(SD_task_t task, int count, ...)
1440 SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1442 va_start(ap, count);
1443 for (i = 0; i < count; i++) {
1444 list[i] = va_arg(ap, SD_workstation_t);
1447 SD_task_schedulev(task, count, list);