1 /* Copyright (c) 2007-2009 Da SimGrid Team. All rights reserved. */
3 /* This program is free software; you can redistribute it and/or modify it
4 * under the terms of the license (GNU LGPL) which comes with this package. */
7 #include "simdag/simdag.h"
8 #include "xbt/sysdep.h"
11 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
12 "Logging specific to SimDag (task)");
14 static void __SD_task_remove_dependencies(SD_task_t task);
15 static void __SD_task_destroy_scheduling_data(SD_task_t task);
18 * \brief Creates a new task.
20 * \param name the name of the task (can be \c NULL)
21 * \param data the user data you want to associate with the task (can be \c NULL)
22 * \param amount amount of the task
23 * \return the new task
24 * \see SD_task_destroy()
26 SD_task_t SD_task_create(const char *name, void *data, double amount)
32 task = xbt_new(s_SD_task_t, 1);
34 /* general information */
35 task->data = data; /* user data */
36 task->name = xbt_strdup(name);
38 task->state_hookup.prev = NULL;
39 task->state_hookup.next = NULL;
40 task->state_set = sd_global->not_scheduled_task_set;
41 task->state = SD_NOT_SCHEDULED;
42 xbt_swag_insert(task, task->state_set);
44 task->amount = amount;
45 task->remains = amount;
46 task->start_time = -1.0;
47 task->finish_time = -1.0;
48 task->surf_action = NULL;
49 task->watch_points = 0;
52 task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
53 task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
55 /* scheduling parameters */
56 task->workstation_nb = 0;
57 task->workstation_list = NULL;
58 task->computation_amount = NULL;
59 task->communication_amount = NULL;
62 sd_global->task_number++;
68 * \brief Returns the user data of a task
71 * \return the user data associated with this task (can be \c NULL)
72 * \see SD_task_set_data()
74 void *SD_task_get_data(SD_task_t task)
77 xbt_assert0(task != NULL, "Invalid parameter");
82 * \brief Sets the user data of a task
84 * The new data can be \c NULL. The old data should have been freed first
85 * if it was not \c NULL.
88 * \param data the new data you want to associate with this task
89 * \see SD_task_get_data()
91 void SD_task_set_data(SD_task_t task, void *data)
94 xbt_assert0(task != NULL, "Invalid parameter");
99 * \brief Returns the state of a task
102 * \return the current \ref e_SD_task_state_t "state" of this task:
103 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_READY, #SD_RUNNING, #SD_DONE or #SD_FAILED
104 * \see e_SD_task_state_t
106 e_SD_task_state_t SD_task_get_state(SD_task_t task)
108 SD_CHECK_INIT_DONE();
109 xbt_assert0(task != NULL, "Invalid parameter");
113 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
115 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
117 xbt_swag_remove(task, task->state_set);
119 case SD_NOT_SCHEDULED:
120 task->state_set = sd_global->not_scheduled_task_set;
123 task->state_set = sd_global->scheduled_task_set;
126 task->state_set = sd_global->ready_task_set;
129 task->state_set = sd_global->in_fifo_task_set;
132 task->state_set = sd_global->running_task_set;
134 surf_workstation_model->action_get_start_time(task->surf_action);
137 task->state_set = sd_global->done_task_set;
139 surf_workstation_model->action_get_finish_time(task->surf_action);
143 task->state_set = sd_global->failed_task_set;
146 xbt_assert0(0, "Invalid state");
148 xbt_swag_insert(task, task->state_set);
149 task->state = new_state;
151 if (task->watch_points & new_state) {
152 INFO1("Watch point reached with task '%s'!", SD_task_get_name(task));
153 sd_global->watch_point_reached = 1;
154 SD_task_unwatch(task, new_state); /* remove the watch point */
159 * \brief Returns the name of a task
162 * \return the name of this task (can be \c NULL)
164 const char *SD_task_get_name(SD_task_t task)
166 SD_CHECK_INIT_DONE();
167 xbt_assert0(task != NULL, "Invalid parameter");
171 /** @brief Returns the dynar of the parents of a task
174 * \return a newly allocated dynar comprising the parents of this task
177 xbt_dynar_t SD_task_get_parents(SD_task_t task)
182 SD_CHECK_INIT_DONE();
183 xbt_assert0(task != NULL, "Invalid parameter");
185 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
186 xbt_dynar_foreach(task->tasks_before, i, dep){
187 xbt_dynar_push(parents, &(dep->src));
192 /** @brief Returns the dynar of the parents of a task
195 * \return a newly allocated dynar comprising the parents of this task
197 xbt_dynar_t SD_task_get_children(SD_task_t task)
200 xbt_dynar_t children;
202 SD_CHECK_INIT_DONE();
203 xbt_assert0(task != NULL, "Invalid parameter");
205 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
206 xbt_dynar_foreach(task->tasks_after, i, dep){
207 xbt_dynar_push(children, &(dep->dst));
213 * \brief Returns the amount of workstations involved in a task
215 * Only call this on already scheduled tasks!
218 int SD_task_get_workstation_count(SD_task_t task)
220 SD_CHECK_INIT_DONE();
221 xbt_assert0(task != NULL, "Invalid parameter");
222 // xbt_assert1( task->state_set != sd_global->scheduled_task_set,
223 // "Unscheduled task %s", task->name);
224 return task->workstation_nb;
228 * \brief Returns the list of workstations involved in a task
230 * Only call this on already scheduled tasks!
233 SD_workstation_t* SD_task_get_workstation_list(SD_task_t task)
235 SD_CHECK_INIT_DONE();
236 xbt_assert0(task != NULL, "Invalid parameter");
237 //xbt_assert1( task->state_set != sd_global->scheduled_task_set,
238 // "Unscheduled task %s", task->name);
239 return task->workstation_list;
243 * \brief Returns the total amount of a task
246 * \return the total amount of this task
247 * \see SD_task_get_remaining_amount()
249 double SD_task_get_amount(SD_task_t task)
251 SD_CHECK_INIT_DONE();
252 xbt_assert0(task != NULL, "Invalid parameter");
257 * \brief Returns the remaining amount of a task
260 * \return the remaining amount of this task
261 * \see SD_task_get_amount()
263 double SD_task_get_remaining_amount(SD_task_t task)
265 SD_CHECK_INIT_DONE();
266 xbt_assert0(task != NULL, "Invalid parameter");
268 if (task->surf_action)
269 return surf_workstation_model->get_remains(task->surf_action);
271 return task->remains;
274 /** @brief Displays debugging informations about a task */
275 void SD_task_dump(SD_task_t task)
277 unsigned int counter;
278 SD_dependency_t dependency;
280 INFO1("Displaying task %s",SD_task_get_name(task));
281 INFO1(" - amount: %.0f",SD_task_get_amount(task));
284 case SD_TASK_COMM_E2E:
285 INFO0(" - kind: end-to-end communication");
287 case SD_TASK_COMP_SEQ:
288 INFO0(" - kind: sequential computation");
291 INFO1(" - (unknown kind %d)",task->kind);
294 if (xbt_dynar_length(task->tasks_before)) {
295 INFO0(" - pre-dependencies:");
296 xbt_dynar_foreach(task->tasks_before,counter,dependency) {
297 INFO1(" %s",SD_task_get_name(dependency->src));
300 if (xbt_dynar_length(task->tasks_after)) {
301 INFO0(" - post-dependencies:");
302 xbt_dynar_foreach(task->tasks_after,counter,dependency) {
303 INFO1(" %s",SD_task_get_name(dependency->dst));
307 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
308 void SD_task_dotty(SD_task_t task,void* out) {
309 unsigned int counter;
310 SD_dependency_t dependency;
311 fprintf(out, " T%d [label=\"%.10s\"",(unsigned int)task,task->name);
313 case SD_TASK_COMM_E2E:
314 fprintf(out,", shape=box");
316 case SD_TASK_COMP_SEQ:
317 fprintf(out,", shape=circle");
321 xbt_dynar_foreach(task->tasks_before,counter,dependency) {
322 fprintf(out," T%d -> T%d;\n",(unsigned int)dependency->src,(unsigned int)dependency->dst);
326 /* Destroys a dependency between two tasks.
328 static void __SD_task_dependency_destroy(void *dependency)
330 if (((SD_dependency_t) dependency)->name != NULL)
331 xbt_free(((SD_dependency_t) dependency)->name);
332 xbt_free(dependency);
336 * \brief Adds a dependency between two tasks
338 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
339 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_READY.
341 * \param name the name of the new dependency (can be \c NULL)
342 * \param data the user data you want to associate with this dependency (can be \c NULL)
343 * \param src the task which must be executed first
344 * \param dst the task you want to make depend on \a src
345 * \see SD_task_dependency_remove()
347 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
354 SD_dependency_t dependency;
356 SD_CHECK_INIT_DONE();
357 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
359 dynar = src->tasks_after;
360 length = xbt_dynar_length(dynar);
364 "Cannot add a dependency between task '%s' and itself",
365 SD_task_get_name(src));
367 if (!__SD_task_is_not_scheduled(src)
368 && !__SD_task_is_scheduled_or_ready(src))
370 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
371 SD_task_get_name(src));
373 if (!__SD_task_is_not_scheduled(dst)
374 && !__SD_task_is_scheduled_or_ready(dst))
376 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
377 SD_task_get_name(dst));
379 DEBUG2("SD_task_dependency_add: src = %s, dst = %s", SD_task_get_name(src),
380 SD_task_get_name(dst));
381 for (i = 0; i < length && !found; i++) {
382 xbt_dynar_get_cpy(dynar, i, &dependency);
383 found = (dependency->dst == dst);
384 DEBUG2("Dependency %d: dependency->dst = %s", i,
385 SD_task_get_name(dependency->dst));
390 "A dependency already exists between task '%s' and task '%s'",
391 SD_task_get_name(src), SD_task_get_name(dst));
393 dependency = xbt_new(s_SD_dependency_t, 1);
395 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
396 dependency->data = data;
397 dependency->src = src;
398 dependency->dst = dst;
400 /* src must be executed before dst */
401 xbt_dynar_push(src->tasks_after, &dependency);
402 xbt_dynar_push(dst->tasks_before, &dependency);
404 /* if the task was ready, then dst->tasks_before is not empty anymore,
405 so we must go back to state SD_SCHEDULED */
406 if (__SD_task_is_ready(dst)) {
407 DEBUG1("SD_task_dependency_add: %s was ready and becomes scheduled!",
408 SD_task_get_name(dst));
409 __SD_task_set_state(dst, SD_SCHEDULED);
412 /* __SD_print_dependencies(src);
413 __SD_print_dependencies(dst); */
417 * \brief Indacates whether there is a dependency between two tasks.
420 * \param dst a task depending on \a src
422 * If src is NULL, checks whether dst has any pre-dependency.
423 * If dst is NULL, checks whether src has any post-dependency.
425 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
427 unsigned int counter;
428 SD_dependency_t dependency;
430 SD_CHECK_INIT_DONE();
431 xbt_assert0(src != NULL || dst != NULL, "Invalid parameter: both src and dst are NULL");
435 xbt_dynar_foreach(src->tasks_after,counter,dependency) {
436 if (dependency->dst == dst)
440 return xbt_dynar_length(src->tasks_after);
443 return xbt_dynar_length(dst->tasks_before);
449 * \brief Remove a dependency between two tasks
452 * \param dst a task depending on \a src
453 * \see SD_task_dependency_add()
455 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
462 SD_dependency_t dependency;
464 SD_CHECK_INIT_DONE();
465 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
467 /* remove the dependency from src->tasks_after */
468 dynar = src->tasks_after;
469 length = xbt_dynar_length(dynar);
471 for (i = 0; i < length && !found; i++) {
472 xbt_dynar_get_cpy(dynar, i, &dependency);
473 if (dependency->dst == dst) {
474 xbt_dynar_remove_at(dynar, i, NULL);
480 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
481 SD_task_get_name(src), SD_task_get_name(dst),
482 SD_task_get_name(dst), SD_task_get_name(src));
484 /* remove the dependency from dst->tasks_before */
485 dynar = dst->tasks_before;
486 length = xbt_dynar_length(dynar);
489 for (i = 0; i < length && !found; i++) {
490 xbt_dynar_get_cpy(dynar, i, &dependency);
491 if (dependency->src == src) {
492 xbt_dynar_remove_at(dynar, i, NULL);
493 __SD_task_dependency_destroy(dependency);
497 /* should never happen... */
499 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
500 SD_task_get_name(dst), SD_task_get_name(src),
501 SD_task_get_name(src), SD_task_get_name(dst));
503 /* if the task was scheduled and dst->tasks_before is empty now, we can make it ready */
504 if (xbt_dynar_length(dst->tasks_before) == 0 && __SD_task_is_scheduled(dst))
505 __SD_task_set_state(dst, SD_READY);
507 /* __SD_print_dependencies(src);
508 __SD_print_dependencies(dst); */
512 * \brief Returns the user data associated with a dependency between two tasks
515 * \param dst a task depending on \a src
516 * \return the user data associated with this dependency (can be \c NULL)
517 * \see SD_task_dependency_add()
519 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
526 SD_dependency_t dependency;
529 SD_CHECK_INIT_DONE();
530 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
532 dynar = src->tasks_after;
533 length = xbt_dynar_length(dynar);
535 for (i = 0; i < length && !found; i++) {
536 xbt_dynar_get_cpy(dynar, i, &dependency);
537 found = (dependency->dst == dst);
540 THROW2(arg_error, 0, "No dependency found between task '%s' and '%s'",
541 SD_task_get_name(src), SD_task_get_name(dst));
542 return dependency->data;
545 /* temporary function for debugging */
546 static void __SD_print_watch_points(SD_task_t task)
548 static const int state_masks[] =
549 { SD_SCHEDULED, SD_RUNNING, SD_READY, SD_DONE, SD_FAILED };
550 static const char *state_names[] =
551 { "scheduled", "running", "ready", "done", "failed" };
554 INFO2("Task '%s' watch points (%x): ", SD_task_get_name(task),
558 for (i = 0; i < 5; i++) {
559 if (task->watch_points & state_masks[i])
560 INFO1("%s ", state_names[i]);
565 * \brief Adds a watch point to a task
567 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
568 * task becomes the one given in argument. The
569 * watch point is then automatically removed.
572 * \param state the \ref e_SD_task_state_t "state" you want to watch
573 * (cannot be #SD_NOT_SCHEDULED)
574 * \see SD_task_unwatch()
576 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
578 SD_CHECK_INIT_DONE();
579 xbt_assert0(task != NULL, "Invalid parameter");
581 if (state & SD_NOT_SCHEDULED)
583 "Cannot add a watch point for state SD_NOT_SCHEDULED");
585 task->watch_points = task->watch_points | state;
586 /* __SD_print_watch_points(task); */
590 * \brief Removes a watch point from a task
593 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
594 * \see SD_task_watch()
596 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
598 SD_CHECK_INIT_DONE();
599 xbt_assert0(task != NULL, "Invalid parameter");
600 xbt_assert0(state != SD_NOT_SCHEDULED,
601 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
603 task->watch_points = task->watch_points & ~state;
604 /* __SD_print_watch_points(task); */
608 * \brief Returns an approximative estimation of the execution time of a task.
610 * The estimation is very approximative because the value returned is the time
611 * the task would take if it was executed now and if it was the only task.
613 * \param task the task to evaluate
614 * \param workstation_nb number of workstations on which the task would be executed
615 * \param workstation_list the workstations on which the task would be executed
616 * \param computation_amount computation amount for each workstation
617 * \param communication_amount communication amount between each pair of workstations
618 * \param rate task execution speed rate
621 double SD_task_get_execution_time(SD_task_t task,
623 const SD_workstation_t * workstation_list,
624 const double *computation_amount,
625 const double *communication_amount,
628 double time, max_time = 0.0;
630 SD_CHECK_INIT_DONE();
631 xbt_assert0(task != NULL && workstation_nb > 0 && workstation_list != NULL
632 && computation_amount != NULL
633 && communication_amount != NULL, "Invalid parameter");
635 /* the task execution time is the maximum execution time of the parallel tasks */
637 for (i = 0; i < workstation_nb; i++) {
639 SD_workstation_get_computation_time(workstation_list[i],
640 computation_amount[i]);
642 for (j = 0; j < workstation_nb; j++) {
644 SD_route_get_communication_time(workstation_list[i],
646 communication_amount[i *
651 if (time > max_time) {
655 return max_time * SD_task_get_amount(task);
657 static inline void SD_task_do_schedule(SD_task_t task) {
658 SD_CHECK_INIT_DONE();
660 if (!__SD_task_is_not_scheduled(task))
661 THROW1(arg_error, 0, "Task '%s' has already been scheduled",
662 SD_task_get_name(task));
664 /* update the task state */
665 if (xbt_dynar_length(task->tasks_before) == 0)
666 __SD_task_set_state(task, SD_READY);
668 __SD_task_set_state(task, SD_SCHEDULED);
672 * \brief Schedules a task
674 * The task state must be #SD_NOT_SCHEDULED.
675 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
676 * i.e. when its dependencies are satisfied.
678 * \param task the task you want to schedule
679 * \param workstation_nb number of workstations on which the task will be executed
680 * \param workstation_list the workstations on which the task will be executed
681 * \param computation_amount computation amount for each workstation
682 * \param communication_amount communication amount between each pair of workstations
683 * \param rate task execution speed rate
684 * \see SD_task_unschedule()
686 void SD_task_schedule(SD_task_t task, int workstation_count,
687 const SD_workstation_t * workstation_list,
688 const double *computation_amount,
689 const double *communication_amount, double rate)
691 xbt_assert0(workstation_count > 0, "workstation_nb must be positive");
693 int communication_nb;
695 task->workstation_nb = workstation_count;
698 task->computation_amount = xbt_new(double, workstation_count);
699 memcpy(task->computation_amount, computation_amount,
700 sizeof(double) * workstation_count);
702 communication_nb = workstation_count * workstation_count;
703 task->communication_amount = xbt_new(double, communication_nb);
704 memcpy(task->communication_amount, communication_amount,
705 sizeof(double) * communication_nb);
707 task->workstation_list = xbt_new(SD_workstation_t, workstation_count);
708 memcpy(task->workstation_list, workstation_list,
709 sizeof(SD_workstation_t) * workstation_count);
711 SD_task_do_schedule(task);
714 * \brief Unschedules a task
716 * The task state must be #SD_SCHEDULED, #SD_READY, #SD_RUNNING or #SD_FAILED.
717 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
718 * Call SD_task_schedule() to schedule it again.
720 * \param task the task you want to unschedule
721 * \see SD_task_schedule()
723 void SD_task_unschedule(SD_task_t task)
725 SD_CHECK_INIT_DONE();
726 xbt_assert0(task != NULL, "Invalid parameter");
728 if (task->state_set != sd_global->scheduled_task_set &&
729 task->state_set != sd_global->ready_task_set &&
730 task->state_set != sd_global->running_task_set &&
731 task->state_set != sd_global->failed_task_set)
733 "Task %s: the state must be SD_SCHEDULED, SD_READY, SD_RUNNING or SD_FAILED",
734 SD_task_get_name(task));
736 if (__SD_task_is_scheduled_or_ready(task)) /* if the task is scheduled or ready */
737 __SD_task_destroy_scheduling_data(task);
739 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
740 surf_workstation_model->action_cancel(task->surf_action);
742 __SD_task_set_state(task, SD_NOT_SCHEDULED);
743 task->remains = task->amount;
744 task->start_time = -1.0;
747 /* Destroys the data memorised by SD_task_schedule. Task state must be SD_SCHEDULED or SD_READY.
749 static void __SD_task_destroy_scheduling_data(SD_task_t task)
751 SD_CHECK_INIT_DONE();
752 if (!__SD_task_is_scheduled_or_ready(task) && !__SD_task_is_in_fifo(task))
754 "Task '%s' must be SD_SCHEDULED, SD_READY or SD_IN_FIFO",
755 SD_task_get_name(task));
757 xbt_free(task->computation_amount);
758 xbt_free(task->communication_amount);
761 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
762 * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
763 * the task gets out of its fifos.
765 void __SD_task_really_run(SD_task_t task)
769 void **surf_workstations;
771 SD_CHECK_INIT_DONE();
772 xbt_assert0(task != NULL, "Invalid parameter");
773 xbt_assert2(__SD_task_is_ready_or_in_fifo(task),
774 "Task '%s' is not ready or in a fifo! Task state: %d",
775 SD_task_get_name(task), SD_task_get_state(task));
776 xbt_assert1(task->workstation_list != NULL,
777 "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
781 DEBUG1("Really running task '%s'", SD_task_get_name(task));
783 /* set this task as current task for the workstations in sequential mode */
784 for (i = 0; i < task->workstation_nb; i++) {
785 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
786 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
787 task->workstation_list[i]->current_task = task;
788 xbt_assert0(__SD_workstation_is_busy(task->workstation_list[i]),
789 "The workstation should be busy now");
793 DEBUG1("Task '%s' set as current task for its workstations",
794 SD_task_get_name(task));
798 /* we have to create a Surf workstation array instead of the SimDag workstation array */
799 surf_workstations = xbt_new(void *, task->workstation_nb);
801 for (i = 0; i < task->workstation_nb; i++) {
802 surf_workstations[i] = task->workstation_list[i]->surf_workstation;
805 task->surf_action = NULL;
806 if ((task->workstation_nb == 1) && (task->communication_amount[0] == 0.0)) {
808 surf_workstation_model->extension.
809 workstation.execute(surf_workstations[0], task->computation_amount[0]);
810 } else if ((task->workstation_nb == 1)
811 && (task->computation_amount[0] == 0.0)) {
813 surf_workstation_model->extension.
814 workstation.communicate(surf_workstations[0], surf_workstations[0],
815 task->communication_amount[0], task->rate);
816 } else if ((task->workstation_nb == 2)
817 && (task->computation_amount[0] == 0.0)
818 && (task->computation_amount[1] == 0.0)) {
822 for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
823 if (task->communication_amount[i] > 0.0) {
825 value = task->communication_amount[i];
830 surf_workstation_model->extension.
831 workstation.communicate(surf_workstations[0], surf_workstations[1],
835 if (!task->surf_action) {
836 double *computation_amount = xbt_new(double, task->workstation_nb);
837 double *communication_amount = xbt_new(double, task->workstation_nb *
838 task->workstation_nb);
840 memcpy(computation_amount, task->computation_amount, sizeof(double) *
841 task->workstation_nb);
842 memcpy(communication_amount, task->communication_amount,
843 sizeof(double) * task->workstation_nb * task->workstation_nb);
846 surf_workstation_model->extension.
847 workstation.execute_parallel_task(task->workstation_nb,
848 surf_workstations, computation_amount,
849 communication_amount, task->amount,
852 xbt_free(surf_workstations);
855 surf_workstation_model->action_data_set(task->surf_action, task);
857 DEBUG1("surf_action = %p", task->surf_action);
859 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
860 __SD_task_set_state(task, SD_RUNNING);
861 xbt_assert2(__SD_task_is_running(task), "Bad state of task '%s': %d",
862 SD_task_get_name(task), SD_task_get_state(task));
866 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_READY
867 * (ie when its dependencies are satisfied).
868 * If one of the workstations where the task is scheduled on is busy (in sequential mode),
869 * the task doesn't start.
870 * Returns whether the task has started.
872 int __SD_task_try_to_run(SD_task_t task)
877 SD_workstation_t workstation;
879 SD_CHECK_INIT_DONE();
880 xbt_assert0(task != NULL, "Invalid parameter");
881 xbt_assert2(__SD_task_is_ready(task),
882 "Task '%s' is not ready! Task state: %d",
883 SD_task_get_name(task), SD_task_get_state(task));
886 for (i = 0; i < task->workstation_nb; i++) {
887 can_start = !__SD_workstation_is_busy(task->workstation_list[i]);
890 DEBUG2("Task '%s' can start: %d", SD_task_get_name(task), can_start);
892 if (!can_start) { /* if the task cannot start and is not in the fifos yet */
893 for (i = 0; i < task->workstation_nb; i++) {
894 workstation = task->workstation_list[i];
895 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
896 DEBUG2("Pushing task '%s' in the fifo of workstation '%s'",
897 SD_task_get_name(task), SD_workstation_get_name(workstation));
898 xbt_fifo_push(workstation->task_fifo, task);
901 __SD_task_set_state(task, SD_IN_FIFO);
902 xbt_assert2(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
903 SD_task_get_name(task), SD_task_get_state(task));
904 DEBUG1("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
906 __SD_task_really_run(task);
912 /* This function is called by SD_simulate when a task is done.
913 * It updates task->state and task->action and executes if necessary the tasks
914 * which were waiting in fifos for the end of `task'
916 void __SD_task_just_done(SD_task_t task)
919 SD_workstation_t workstation;
922 int candidate_nb = 0;
923 int candidate_capacity = 8;
924 SD_task_t *candidates;
927 SD_CHECK_INIT_DONE();
928 xbt_assert0(task != NULL, "Invalid parameter");
929 xbt_assert1(__SD_task_is_running(task),
930 "The task must be running! Task state: %d",
931 SD_task_get_state(task));
932 xbt_assert1(task->workstation_list != NULL,
933 "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
936 candidates = xbt_new(SD_task_t, 8);
938 __SD_task_set_state(task, SD_DONE);
939 surf_workstation_model->action_unref(task->surf_action);
940 task->surf_action = NULL;
942 DEBUG0("Looking for candidates");
944 /* if the task was executed on sequential workstations,
945 maybe we can execute the next task of the fifo for each workstation */
946 for (i = 0; i < task->workstation_nb; i++) {
947 workstation = task->workstation_list[i];
948 DEBUG2("Workstation '%s': access_mode = %d",
949 SD_workstation_get_name(workstation), workstation->access_mode);
950 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
951 xbt_assert1(workstation->task_fifo != NULL,
952 "Workstation '%s' has sequential access but no fifo!",
953 SD_workstation_get_name(workstation));
954 xbt_assert2(workstation->current_task =
955 task, "Workstation '%s': current task should be '%s'",
956 SD_workstation_get_name(workstation),
957 SD_task_get_name(task));
959 /* the task is over so we can release the workstation */
960 workstation->current_task = NULL;
962 DEBUG0("Getting candidate in fifo");
964 xbt_fifo_get_item_content(xbt_fifo_get_first_item
965 (workstation->task_fifo));
967 if (candidate != NULL) {
968 DEBUG1("Candidate: '%s'", SD_task_get_name(candidate));
969 xbt_assert2(__SD_task_is_in_fifo(candidate),
970 "Bad state of candidate '%s': %d",
971 SD_task_get_name(candidate),
972 SD_task_get_state(candidate));
975 DEBUG1("Candidate in fifo: %p", candidate);
977 /* if there was a task waiting for my place */
978 if (candidate != NULL) {
979 /* Unfortunately, we are not sure yet that we can execute the task now,
980 because the task can be waiting more deeply in some other workstation's fifos...
981 So we memorize all candidate tasks, and then we will check for each candidate
982 whether or not all its workstations are available. */
984 /* realloc if necessary */
985 if (candidate_nb == candidate_capacity) {
986 candidate_capacity *= 2;
988 xbt_realloc(candidates, sizeof(SD_task_t) * candidate_capacity);
991 /* register the candidate */
992 candidates[candidate_nb++] = candidate;
993 candidate->fifo_checked = 0;
998 DEBUG1("Candidates found: %d", candidate_nb);
1000 /* now we check every candidate task */
1001 for (i = 0; i < candidate_nb; i++) {
1002 candidate = candidates[i];
1004 if (candidate->fifo_checked) {
1005 continue; /* we have already evaluated that task */
1008 xbt_assert2(__SD_task_is_in_fifo(candidate),
1009 "Bad state of candidate '%s': %d",
1010 SD_task_get_name(candidate), SD_task_get_state(candidate));
1012 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1013 workstation = candidate->workstation_list[j];
1015 /* I can start on this workstation if the workstation is shared
1016 or if I am the first task in the fifo */
1017 can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS ||
1019 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1020 (workstation->task_fifo));
1023 DEBUG2("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1026 /* now we are sure that I can start! */
1028 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1029 workstation = candidate->workstation_list[j];
1031 /* update the fifo */
1032 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1033 candidate = xbt_fifo_shift(workstation->task_fifo); /* the return value is stored just for debugging */
1034 DEBUG1("Head of the fifo: '%s'",
1035 (candidate != NULL) ? SD_task_get_name(candidate) : "NULL");
1036 xbt_assert0(candidate == candidates[i],
1037 "Error in __SD_task_just_done: bad first task in the fifo");
1039 } /* for each workstation */
1041 /* finally execute the task */
1042 DEBUG2("Task '%s' state: %d", SD_task_get_name(candidate),
1043 SD_task_get_state(candidate));
1044 __SD_task_really_run(candidate);
1047 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1048 SD_task_get_name(candidate), candidate->state_set,
1049 sd_global->running_task_set, __SD_task_is_running(candidate));
1050 xbt_assert2(__SD_task_is_running(candidate),
1051 "Bad state of task '%s': %d", SD_task_get_name(candidate),
1052 SD_task_get_state(candidate));
1053 DEBUG0("Okay, the task is running.");
1056 candidate->fifo_checked = 1;
1057 } /* for each candidate */
1059 xbt_free(candidates);
1062 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1064 static void __SD_task_remove_dependencies(SD_task_t task)
1066 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1067 because each one is stored twice */
1068 SD_dependency_t dependency;
1069 while (xbt_dynar_length(task->tasks_before) > 0) {
1070 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1071 SD_task_dependency_remove(dependency->src, dependency->dst);
1074 while (xbt_dynar_length(task->tasks_after) > 0) {
1075 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1076 SD_task_dependency_remove(dependency->src, dependency->dst);
1081 * \brief Returns the start time of a task
1083 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1085 * \param task: a task
1086 * \return the start time of this task
1088 double SD_task_get_start_time(SD_task_t task)
1090 SD_CHECK_INIT_DONE();
1091 xbt_assert0(task != NULL, "Invalid parameter");
1092 if (task->surf_action)
1093 return surf_workstation_model->action_get_start_time(task->surf_action);
1095 return task->start_time;
1099 * \brief Returns the finish time of a task
1101 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1102 * If the state is not completed yet, the returned value is an
1103 * estimation of the task finish time. This value can fluctuate
1104 * until the task is completed.
1106 * \param task: a task
1107 * \return the start time of this task
1109 double SD_task_get_finish_time(SD_task_t task)
1111 SD_CHECK_INIT_DONE();
1112 xbt_assert0(task != NULL, "Invalid parameter");
1114 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1115 return surf_workstation_model->action_get_finish_time(task->surf_action);
1117 return task->finish_time;
1121 * \brief Destroys a task.
1123 * The user data (if any) should have been destroyed first.
1125 * \param task the task you want to destroy
1126 * \see SD_task_create()
1128 void SD_task_destroy(SD_task_t task)
1130 SD_CHECK_INIT_DONE();
1131 xbt_assert0(task != NULL, "Invalid parameter");
1133 DEBUG1("Destroying task %s...", SD_task_get_name(task));
1135 __SD_task_remove_dependencies(task);
1137 /* if the task was scheduled or ready we have to free the scheduling parameters */
1138 if (__SD_task_is_scheduled_or_ready(task))
1139 __SD_task_destroy_scheduling_data(task);
1141 if (task->name != NULL)
1142 xbt_free(task->name);
1144 if (task->surf_action != NULL)
1145 surf_workstation_model->action_unref(task->surf_action);
1147 if (task->workstation_list != NULL)
1148 xbt_free(task->workstation_list);
1150 xbt_dynar_free(&task->tasks_before);
1151 xbt_dynar_free(&task->tasks_after);
1154 sd_global->task_number--;
1156 DEBUG0("Task destroyed.");
1160 static inline SD_task_t SD_task_create_sized(const char*name,void*data,double amount,int ws_count) {
1161 SD_task_t task = SD_task_create(name,data,amount);
1162 task->communication_amount = xbt_new0(double,ws_count*ws_count);
1163 task->computation_amount = xbt_new0(double,ws_count);
1164 task->workstation_nb = ws_count;
1165 task->workstation_list = xbt_new0(SD_workstation_t,ws_count);
1168 /** @brief create a end-to-end communication task that can then be auto-scheduled
1170 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1171 * allows to specify the task costs at creation, and decorelate them from the
1172 * scheduling process where you just specify which resource should deliver the
1175 * A end-to-end communication must be scheduled on 2 hosts, and the amount
1176 * specified at creation is sent from hosts[0] to hosts[1].
1178 SD_task_t SD_task_create_comm_e2e(const char*name, void *data, double amount) {
1179 SD_task_t res = SD_task_create_sized(name,data,0,2);
1180 res->communication_amount[1] = amount;
1181 res->kind=SD_TASK_COMM_E2E;
1184 /** @brief create a sequential computation task that can then be auto-scheduled
1186 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1187 * allows to specify the task costs at creation, and decorelate them from the
1188 * scheduling process where you just specify which resource should deliver the
1191 * A sequential computation must be scheduled on 1 host, and the amount
1192 * specified at creation to be run on hosts[0].
1194 SD_task_t SD_task_create_comp_seq(const char*name, void *data, double amount) {
1195 SD_task_t res = SD_task_create_sized(name,data,0,1);
1196 res->computation_amount[0]=amount;
1197 res->kind=SD_TASK_COMP_SEQ;
1201 /** @brief Auto-schedules a task.
1203 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1204 * allows to specify the task costs at creation, and decorelate them from the
1205 * scheduling process where you just specify which resource should deliver the
1208 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1209 * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1213 * We should create tasks kind for the following categories:
1214 * - Point to point communication (done)
1215 * - Sequential computation (done)
1216 * - group communication (redistribution, several kinds)
1217 * - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1218 * - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1220 void SD_task_schedulev(SD_task_t task, int count, const SD_workstation_t*list) {
1222 xbt_assert1(task->kind != 0,"Task %s is not typed. Cannot automatically schedule it.",SD_task_get_name(task));
1223 switch(task->kind) {
1224 case SD_TASK_COMM_E2E:
1225 case SD_TASK_COMP_SEQ:
1226 xbt_assert(task->workstation_nb==count);
1227 for (i=0;i<count;i++)
1228 task->workstation_list[i]=list[i];
1229 SD_task_do_schedule(task);
1232 xbt_die(bprintf("Kind of task %s not supported by SD_task_schedulev()",
1233 SD_task_get_name(task)));
1235 /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if ready) */
1236 if (task->kind == SD_TASK_COMP_SEQ) {
1237 SD_dependency_t dep;
1239 xbt_dynar_foreach(task->tasks_before,cpt,dep) {
1240 SD_task_t before = dep->src;
1241 if (before->kind == SD_TASK_COMM_E2E) {
1242 before->workstation_list[1] = task->workstation_list[0];
1243 if (before->workstation_list[0])
1244 SD_task_do_schedule(before);
1247 xbt_dynar_foreach(task->tasks_after,cpt,dep) {
1248 SD_task_t after = dep->dst;
1249 if (after->kind == SD_TASK_COMM_E2E) {
1250 after->workstation_list[0] = task->workstation_list[0];
1251 if (after->workstation_list[1])
1252 SD_task_do_schedule(after);
1258 /** @brief autoschedule a task on a list of workstations
1260 * This function is very similar to SD_task_schedulev(),
1261 * but takes the list of workstations to schedule onto as separate parameters.
1262 * It builds a proper vector of workstations and then call SD_task_schedulev()
1264 void SD_task_schedulel(SD_task_t task, int count, ...) {
1266 SD_workstation_t *list=xbt_new(SD_workstation_t,count);
1269 for (i=0;i<count;i++) {
1270 list[i] = va_arg(ap,SD_workstation_t);
1273 SD_task_schedulev(task,count,list);