src/simdag/sd_task.c

   1 #include "private.h"
   2 #include "simdag/simdag.h"
   3 #include "xbt/sysdep.h"
   4 #include "xbt/dynar.h"
   5
   6 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
   7                                 "Logging specific to SimDag (task)");
   8
   9 static void __SD_task_remove_dependencies(SD_task_t task);
  10 static void __SD_task_destroy_scheduling_data(SD_task_t task);
  11
  12 /**
  13  * \brief Creates a new task.
  14  *
  15  * \param name the name of the task (can be \c NULL)
  16  * \param data the user data you want to associate with the task (can be \c NULL)
  17  * \param amount amount of the task
  18  * \return the new task
  19  * \see SD_task_destroy()
  20  */
  21 SD_task_t SD_task_create(const char *name, void *data, double amount)
  22 {
  23
  24   SD_task_t task;
  25   SD_CHECK_INIT_DONE();
  26
  27   task = xbt_new(s_SD_task_t, 1);
  28
  29   /* general information */
  30   task->data = data;            /* user data */
  31   if (name != NULL)
  32     task->name = xbt_strdup(name);
  33   else
  34     task->name = NULL;
  35
  36   task->state_hookup.prev = NULL;
  37   task->state_hookup.next = NULL;
  38   task->state_set = sd_global->not_scheduled_task_set;
  39   task->state = SD_NOT_SCHEDULED;
  40   xbt_swag_insert(task, task->state_set);
  41
  42   task->amount = amount;
  43   task->remains = amount;
  44   task->start_time = -1.0;
  45   task->finish_time = -1.0;
  46   task->surf_action = NULL;
  47   task->watch_points = 0;
  48
  49   /* dependencies */
  50   task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
  51   task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
  52
  53   /* scheduling parameters */
  54   task->workstation_nb = 0;
  55   task->workstation_list = NULL;
  56   task->computation_amount = NULL;
  57   task->communication_amount = NULL;
  58   task->rate = 0;
  59
  60   sd_global->task_number++;
  61
  62   return task;
  63 }
  64
  65 /**
  66  * \brief Returns the user data of a task
  67  *
  68  * \param task a task
  69  * \return the user data associated with this task (can be \c NULL)
  70  * \see SD_task_set_data()
  71  */
  72 void *SD_task_get_data(SD_task_t task)
  73 {
  74   SD_CHECK_INIT_DONE();
  75   xbt_assert0(task != NULL, "Invalid parameter");
  76   return task->data;
  77 }
  78
  79 /**
  80  * \brief Sets the user data of a task
  81  *
  82  * The new data can be \c NULL. The old data should have been freed first
  83  * if it was not \c NULL.
  84  *
  85  * \param task a task
  86  * \param data the new data you want to associate with this task
  87  * \see SD_task_get_data()
  88  */
  89 void SD_task_set_data(SD_task_t task, void *data)
  90 {
  91   SD_CHECK_INIT_DONE();
  92   xbt_assert0(task != NULL, "Invalid parameter");
  93   task->data = data;
  94 }
  95
  96 /**
  97  * \brief Returns the state of a task
  98  *
  99  * \param task a task
 100  * \return the current \ref e_SD_task_state_t "state" of this task:
 101  * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_READY, #SD_RUNNING, #SD_DONE or #SD_FAILED
 102  * \see e_SD_task_state_t
 103  */
 104 e_SD_task_state_t SD_task_get_state(SD_task_t task)
 105 {
 106   SD_CHECK_INIT_DONE();
 107   xbt_assert0(task != NULL, "Invalid parameter");
 108   return task->state;
 109 }
 110
 111 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
 112  */
 113 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
 114 {
 115   xbt_swag_remove(task, task->state_set);
 116   switch (new_state) {
 117   case SD_NOT_SCHEDULED:
 118     task->state_set = sd_global->not_scheduled_task_set;
 119     break;
 120   case SD_SCHEDULED:
 121     task->state_set = sd_global->scheduled_task_set;
 122     break;
 123   case SD_READY:
 124     task->state_set = sd_global->ready_task_set;
 125     break;
 126   case SD_IN_FIFO:
 127     task->state_set = sd_global->in_fifo_task_set;
 128     break;
 129   case SD_RUNNING:
 130     task->state_set = sd_global->running_task_set;
 131     task->start_time =
 132       surf_workstation_model->common_public->action_get_start_time(task->
 133                                                                    surf_action);
 134     break;
 135   case SD_DONE:
 136     task->state_set = sd_global->done_task_set;
 137     task->finish_time =
 138       surf_workstation_model->common_public->action_get_finish_time(task->
 139                                                                     surf_action);
 140     task->remains = 0;
 141     break;
 142   case SD_FAILED:
 143     task->state_set = sd_global->failed_task_set;
 144     break;
 145   default:
 146     xbt_assert0(0, "Invalid state");
 147   }
 148   xbt_swag_insert(task, task->state_set);
 149   task->state = new_state;
 150
 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 */
 155   }
 156 }
 157
 158 /**
 159  * \brief Returns the name of a task
 160  *
 161  * \param task a task
 162  * \return the name of this task (can be \c NULL)
 163  */
 164 const char *SD_task_get_name(SD_task_t task)
 165 {
 166   SD_CHECK_INIT_DONE();
 167   xbt_assert0(task != NULL, "Invalid parameter");
 168   return task->name;
 169 }
 170
 171 /**
 172  * \brief Returns the total amount of a task
 173  *
 174  * \param task a task
 175  * \return the total amount of this task
 176  * \see SD_task_get_remaining_amount()
 177  */
 178 double SD_task_get_amount(SD_task_t task)
 179 {
 180   SD_CHECK_INIT_DONE();
 181   xbt_assert0(task != NULL, "Invalid parameter");
 182   return task->amount;
 183 }
 184
 185 /**
 186  * \brief Returns the remaining amount of a task
 187  *
 188  * \param task a task
 189  * \return the remaining amount of this task
 190  * \see SD_task_get_amount()
 191  */
 192 double SD_task_get_remaining_amount(SD_task_t task)
 193 {
 194   SD_CHECK_INIT_DONE();
 195   xbt_assert0(task != NULL, "Invalid parameter");
 196
 197   if (task->surf_action)
 198     return task->surf_action->remains;
 199   else
 200     return task->remains;
 201 }
 202
 203 /* temporary function for debbuging */
 204 static void __SD_print_dependencies(SD_task_t task)
 205 {
 206   xbt_dynar_t dynar;
 207   int length;
 208   int i;
 209   SD_dependency_t dependency;
 210
 211   INFO1("The following tasks must be executed before %s:",
 212         SD_task_get_name(task));
 213   dynar = task->tasks_before;
 214   length = xbt_dynar_length(dynar);
 215
 216
 217   for (i = 0; i < length; i++) {
 218     xbt_dynar_get_cpy(dynar, i, &dependency);
 219     INFO1(" %s", SD_task_get_name(dependency->src));
 220   }
 221
 222   INFO1("The following tasks must be executed after %s:",
 223         SD_task_get_name(task));
 224
 225   dynar = task->tasks_after;
 226   length = xbt_dynar_length(dynar);
 227   for (i = 0; i < length; i++) {
 228     xbt_dynar_get_cpy(dynar, i, &dependency);
 229     INFO1(" %s", SD_task_get_name(dependency->dst));
 230   }
 231   INFO0("----------------------------");
 232 }
 233
 234 /* Destroys a dependency between two tasks.
 235  */
 236 static void __SD_task_dependency_destroy(void *dependency)
 237 {
 238   if (((SD_dependency_t) dependency)->name != NULL)
 239     xbt_free(((SD_dependency_t) dependency)->name);
 240   xbt_free(dependency);
 241 }
 242
 243 /**
 244  * \brief Adds a dependency between two tasks
 245  *
 246  * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
 247  * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_READY.
 248  *
 249  * \param name the name of the new dependency (can be \c NULL)
 250  * \param data the user data you want to associate with this dependency (can be \c NULL)
 251  * \param src the task which must be executed first
 252  * \param dst the task you want to make depend on \a src
 253  * \see SD_task_dependency_remove()
 254  */
 255 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
 256                             SD_task_t dst)
 257 {
 258   xbt_dynar_t dynar;
 259   int length;
 260   int found = 0;
 261   int i;
 262   SD_dependency_t dependency;
 263
 264   SD_CHECK_INIT_DONE();
 265   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
 266
 267   dynar = src->tasks_after;
 268   length = xbt_dynar_length(dynar);
 269
 270
 271
 272   if (src == dst)
 273     THROW1(arg_error, 0,
 274            "Cannot add a dependency between task '%s' and itself",
 275            SD_task_get_name(src));
 276
 277   if (!__SD_task_is_not_scheduled(src)
 278       && !__SD_task_is_scheduled_or_ready(src))
 279     THROW1(arg_error, 0,
 280            "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
 281            SD_task_get_name(src));
 282
 283   if (!__SD_task_is_not_scheduled(dst)
 284       && !__SD_task_is_scheduled_or_ready(dst))
 285     THROW1(arg_error, 0,
 286            "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
 287            SD_task_get_name(dst));
 288
 289   DEBUG2("SD_task_dependency_add: src = %s, dst = %s", SD_task_get_name(src),
 290          SD_task_get_name(dst));
 291   for (i = 0; i < length && !found; i++) {
 292     xbt_dynar_get_cpy(dynar, i, &dependency);
 293     found = (dependency->dst == dst);
 294     DEBUG2("Dependency %d: dependency->dst = %s", i,
 295            SD_task_get_name(dependency->dst));
 296   }
 297
 298   if (found)
 299     THROW2(arg_error, 0,
 300            "A dependency already exists between task '%s' and task '%s'",
 301            SD_task_get_name(src), SD_task_get_name(dst));
 302
 303   dependency = xbt_new(s_SD_dependency_t, 1);
 304
 305   if (name != NULL)
 306     dependency->name = xbt_strdup(name);
 307   else
 308     dependency->name = NULL;
 309
 310   dependency->data = data;
 311   dependency->src = src;
 312   dependency->dst = dst;
 313
 314   /* src must be executed before dst */
 315   xbt_dynar_push(src->tasks_after, &dependency);
 316   xbt_dynar_push(dst->tasks_before, &dependency);
 317
 318   /* if the task was ready, then dst->tasks_before is not empty anymore,
 319      so we must go back to state SD_SCHEDULED */
 320   if (__SD_task_is_ready(dst)) {
 321     DEBUG1("SD_task_dependency_add: %s was ready and becomes scheduled!",
 322            SD_task_get_name(dst));
 323     __SD_task_set_state(dst, SD_SCHEDULED);
 324   }
 325
 326   /*  __SD_print_dependencies(src);
 327      __SD_print_dependencies(dst); */
 328 }
 329
 330 /**
 331  * \brief Indacates whether there is a dependency between two tasks.
 332  *
 333  * \param src a task
 334  * \param dst a task depending on \a src
 335  */
 336 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
 337 {
 338   xbt_dynar_t dynar;
 339   int length;
 340   int i;
 341   SD_dependency_t dependency;
 342
 343   SD_CHECK_INIT_DONE();
 344   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
 345
 346   dynar = src->tasks_after;
 347   length = xbt_dynar_length(dynar);
 348
 349   for (i = 0; i < length; i++) {
 350     xbt_dynar_get_cpy(dynar, i, &dependency);
 351     if (dependency->dst == dst)
 352       return 1;
 353   }
 354   return 0;
 355 }
 356
 357 /**
 358  * \brief Remove a dependency between two tasks
 359  *
 360  * \param src a task
 361  * \param dst a task depending on \a src
 362  * \see SD_task_dependency_add()
 363  */
 364 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
 365 {
 366
 367   xbt_dynar_t dynar;
 368   int length;
 369   int found = 0;
 370   int i;
 371   SD_dependency_t dependency;
 372
 373   SD_CHECK_INIT_DONE();
 374   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
 375
 376   /* remove the dependency from src->tasks_after */
 377   dynar = src->tasks_after;
 378   length = xbt_dynar_length(dynar);
 379
 380   for (i = 0; i < length && !found; i++) {
 381     xbt_dynar_get_cpy(dynar, i, &dependency);
 382     if (dependency->dst == dst) {
 383       xbt_dynar_remove_at(dynar, i, NULL);
 384       found = 1;
 385     }
 386   }
 387   if (!found)
 388     THROW4(arg_error, 0,
 389            "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
 390            SD_task_get_name(src), SD_task_get_name(dst),
 391            SD_task_get_name(dst), SD_task_get_name(src));
 392
 393   /* remove the dependency from dst->tasks_before */
 394   dynar = dst->tasks_before;
 395   length = xbt_dynar_length(dynar);
 396   found = 0;
 397
 398   for (i = 0; i < length && !found; i++) {
 399     xbt_dynar_get_cpy(dynar, i, &dependency);
 400     if (dependency->src == src) {
 401       xbt_dynar_remove_at(dynar, i, NULL);
 402       __SD_task_dependency_destroy(dependency);
 403       found = 1;
 404     }
 405   }
 406   /* should never happen... */
 407   xbt_assert4(found,
 408               "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
 409               SD_task_get_name(dst), SD_task_get_name(src),
 410               SD_task_get_name(src), SD_task_get_name(dst));
 411
 412   /* if the task was scheduled and dst->tasks_before is empty now, we can make it ready */
 413   if (xbt_dynar_length(dst->tasks_before) == 0 && __SD_task_is_scheduled(dst))
 414     __SD_task_set_state(dst, SD_READY);
 415
 416   /*  __SD_print_dependencies(src);
 417      __SD_print_dependencies(dst); */
 418 }
 419
 420 /**
 421  * \brief Returns the user data associated with a dependency between two tasks
 422  *
 423  * \param src a task
 424  * \param dst a task depending on \a src
 425  * \return the user data associated with this dependency (can be \c NULL)
 426  * \see SD_task_dependency_add()
 427  */
 428 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
 429 {
 430
 431   xbt_dynar_t dynar;
 432   int length;
 433   int found = 0;
 434   int i;
 435   SD_dependency_t dependency;
 436
 437
 438   SD_CHECK_INIT_DONE();
 439   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
 440
 441   dynar = src->tasks_after;
 442   length = xbt_dynar_length(dynar);
 443
 444   for (i = 0; i < length && !found; i++) {
 445     xbt_dynar_get_cpy(dynar, i, &dependency);
 446     found = (dependency->dst == dst);
 447   }
 448   if (!found)
 449     THROW2(arg_error, 0, "No dependency found between task '%s' and '%s'",
 450            SD_task_get_name(src), SD_task_get_name(dst));
 451   return dependency->data;
 452 }
 453
 454 /* temporary function for debugging */
 455 static void __SD_print_watch_points(SD_task_t task)
 456 {
 457   static const int state_masks[] =
 458     { SD_SCHEDULED, SD_RUNNING, SD_READY, SD_DONE, SD_FAILED };
 459   static const char *state_names[] =
 460     { "scheduled", "running", "ready", "done", "failed" };
 461   int i;
 462
 463   INFO2("Task '%s' watch points (%x): ", SD_task_get_name(task),
 464         task->watch_points);
 465
 466
 467   for (i = 0; i < 5; i++) {
 468     if (task->watch_points & state_masks[i])
 469       INFO1("%s ", state_names[i]);
 470   }
 471 }
 472
 473 /**
 474  * \brief Adds a watch point to a task
 475  *
 476  * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
 477  * task becomes the one given in argument. The
 478  * watch point is then automatically removed.
 479  *
 480  * \param task a task
 481  * \param state the \ref e_SD_task_state_t "state" you want to watch
 482  * (cannot be #SD_NOT_SCHEDULED)
 483  * \see SD_task_unwatch()
 484  */
 485 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
 486 {
 487   SD_CHECK_INIT_DONE();
 488   xbt_assert0(task != NULL, "Invalid parameter");
 489
 490   if (state & SD_NOT_SCHEDULED)
 491     THROW0(arg_error, 0,
 492            "Cannot add a watch point for state SD_NOT_SCHEDULED");
 493
 494   task->watch_points = task->watch_points | state;
 495   /*  __SD_print_watch_points(task); */
 496 }
 497
 498 /**
 499  * \brief Removes a watch point from a task
 500  *
 501  * \param task a task
 502  * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
 503  * \see SD_task_watch()
 504  */
 505 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
 506 {
 507   SD_CHECK_INIT_DONE();
 508   xbt_assert0(task != NULL, "Invalid parameter");
 509   xbt_assert0(state != SD_NOT_SCHEDULED,
 510               "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
 511
 512   task->watch_points = task->watch_points & ~state;
 513   /*  __SD_print_watch_points(task); */
 514 }
 515
 516 /**
 517  * \brief Returns an approximative estimation of the execution time of a task.
 518  *
 519  * The estimation is very approximative because the value returned is the time
 520  * the task would take if it was executed now and if it was the only task.
 521  *
 522  * \param task the task to evaluate
 523  * \param workstation_nb number of workstations on which the task would be executed
 524  * \param workstation_list the workstations on which the task would be executed
 525  * \param computation_amount computation amount for each workstation
 526  * \param communication_amount communication amount between each pair of workstations
 527  * \param rate task execution speed rate
 528  * \see SD_schedule()
 529  */
 530 double SD_task_get_execution_time(SD_task_t task,
 531                                   int workstation_nb,
 532                                   const SD_workstation_t * workstation_list,
 533                                   const double *computation_amount,
 534                                   const double *communication_amount,
 535                                   double rate)
 536 {
 537   double time, max_time = 0.0;
 538   int i, j;
 539   SD_CHECK_INIT_DONE();
 540   xbt_assert0(task != NULL && workstation_nb > 0 && workstation_list != NULL
 541               && computation_amount != NULL
 542               && communication_amount != NULL, "Invalid parameter");
 543
 544   /* the task execution time is the maximum execution time of the parallel tasks */
 545
 546   for (i = 0; i < workstation_nb; i++) {
 547     time =
 548       SD_workstation_get_computation_time(workstation_list[i],
 549                                           computation_amount[i]);
 550
 551     for (j = 0; j < workstation_nb; j++) {
 552       time +=
 553         SD_route_get_communication_time(workstation_list[i],
 554                                         workstation_list[j],
 555                                         communication_amount[i *
 556                                                              workstation_nb +
 557                                                              j]);
 558     }
 559
 560     if (time > max_time) {
 561       max_time = time;
 562     }
 563   }
 564   return max_time * SD_task_get_amount(task);
 565 }
 566
 567 /**
 568  * \brief Schedules a task
 569  *
 570  * The task state must be #SD_NOT_SCHEDULED.
 571  * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
 572  * i.e. when its dependencies are satisfied.
 573  *
 574  * \param task the task you want to schedule
 575  * \param workstation_nb number of workstations on which the task will be executed
 576  * \param workstation_list the workstations on which the task will be executed
 577  * \param computation_amount computation amount for each workstation
 578  * \param communication_amount communication amount between each pair of workstations
 579  * \param rate task execution speed rate
 580  * \see SD_task_unschedule()
 581  */
 582 void SD_task_schedule(SD_task_t task, int workstation_nb,
 583                       const SD_workstation_t * workstation_list,
 584                       const double *computation_amount,
 585                       const double *communication_amount, double rate)
 586 {
 587
 588   int communication_nb;
 589
 590   SD_CHECK_INIT_DONE();
 591   xbt_assert0(task != NULL, "Invalid parameter");
 592   xbt_assert0(workstation_nb > 0, "workstation_nb must be positive");
 593
 594   if (!__SD_task_is_not_scheduled(task))
 595     THROW1(arg_error, 0, "Task '%s' has already been scheduled",
 596            SD_task_get_name(task));
 597
 598   task->workstation_nb = workstation_nb;
 599   task->rate = rate;
 600
 601   task->computation_amount = xbt_new(double, workstation_nb);
 602   memcpy(task->computation_amount, computation_amount,
 603          sizeof(double) * workstation_nb);
 604
 605   communication_nb = workstation_nb * workstation_nb;
 606   task->communication_amount = xbt_new(double, communication_nb);
 607   memcpy(task->communication_amount, communication_amount,
 608          sizeof(double) * communication_nb);
 609
 610   task->workstation_list = xbt_new(SD_workstation_t, workstation_nb);
 611   memcpy(task->workstation_list, workstation_list,
 612          sizeof(SD_workstation_t) * workstation_nb);
 613
 614   /* update the task state */
 615   if (xbt_dynar_length(task->tasks_before) == 0)
 616     __SD_task_set_state(task, SD_READY);
 617   else
 618     __SD_task_set_state(task, SD_SCHEDULED);
 619 }
 620
 621 /**
 622  * \brief Unschedules a task
 623  *
 624  * The task state must be #SD_SCHEDULED, #SD_READY, #SD_RUNNING or #SD_FAILED.
 625  * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
 626  * Call SD_task_schedule() to schedule it again.
 627  *
 628  * \param task the task you want to unschedule
 629  * \see SD_task_schedule()
 630  */
 631 void SD_task_unschedule(SD_task_t task)
 632 {
 633   SD_CHECK_INIT_DONE();
 634   xbt_assert0(task != NULL, "Invalid parameter");
 635
 636   if (task->state_set != sd_global->scheduled_task_set &&
 637       task->state_set != sd_global->ready_task_set &&
 638       task->state_set != sd_global->running_task_set &&
 639       task->state_set != sd_global->failed_task_set)
 640     THROW1(arg_error, 0,
 641            "Task %s: the state must be SD_SCHEDULED, SD_READY, SD_RUNNING or SD_FAILED",
 642            SD_task_get_name(task));
 643
 644   if (__SD_task_is_scheduled_or_ready(task))    /* if the task is scheduled or ready */
 645     __SD_task_destroy_scheduling_data(task);
 646
 647   if (__SD_task_is_running(task))       /* the task should become SD_FAILED */
 648     surf_workstation_model->common_public->action_cancel(task->surf_action);
 649   else
 650     __SD_task_set_state(task, SD_NOT_SCHEDULED);
 651   task->remains = task->amount;
 652   task->start_time = -1.0;
 653 }
 654
 655 /* Destroys the data memorised by SD_task_schedule. Task state must be SD_SCHEDULED or SD_READY.
 656  */
 657 static void __SD_task_destroy_scheduling_data(SD_task_t task)
 658 {
 659   SD_CHECK_INIT_DONE();
 660   if (!__SD_task_is_scheduled_or_ready(task) && !__SD_task_is_in_fifo(task))
 661     THROW1(arg_error, 0,
 662            "Task '%s' must be SD_SCHEDULED, SD_READY or SD_IN_FIFO",
 663            SD_task_get_name(task));
 664
 665   xbt_free(task->computation_amount);
 666   xbt_free(task->communication_amount);
 667 }
 668
 669 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
 670  * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
 671  * the task gets out of its fifos.
 672  */
 673 void __SD_task_really_run(SD_task_t task)
 674 {
 675
 676   int i;
 677   void **surf_workstations;
 678
 679   SD_CHECK_INIT_DONE();
 680   xbt_assert0(task != NULL, "Invalid parameter");
 681   xbt_assert2(__SD_task_is_ready_or_in_fifo(task),
 682               "Task '%s' is not ready or in a fifo! Task state: %d",
 683               SD_task_get_name(task), SD_task_get_state(task));
 684   xbt_assert1(task->workstation_list != NULL,
 685               "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
 686
 687
 688
 689   DEBUG1("Really running task '%s'", SD_task_get_name(task));
 690
 691   /* set this task as current task for the workstations in sequential mode */
 692   for (i = 0; i < task->workstation_nb; i++) {
 693     if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
 694         SD_WORKSTATION_SEQUENTIAL_ACCESS) {
 695       task->workstation_list[i]->current_task = task;
 696       xbt_assert0(__SD_workstation_is_busy(task->workstation_list[i]),
 697                   "The workstation should be busy now");
 698     }
 699   }
 700
 701   DEBUG1("Task '%s' set as current task for its workstations",
 702          SD_task_get_name(task));
 703
 704   /* start the task */
 705
 706   /* we have to create a Surf workstation array instead of the SimDag workstation array */
 707   surf_workstations = xbt_new(void *, task->workstation_nb);
 708
 709   for (i = 0; i < task->workstation_nb; i++) {
 710     surf_workstations[i] = task->workstation_list[i]->surf_workstation;
 711   }
 712
 713   task->surf_action = NULL;
 714   if ((task->workstation_nb == 1) && (task->communication_amount[0] == 0.0)) {
 715     task->surf_action =
 716       surf_workstation_model->extension_public->execute(surf_workstations[0],
 717                                                         task->
 718                                                         computation_amount
 719                                                         [0]);
 720   } else if ((task->workstation_nb == 1)
 721              && (task->computation_amount[0] == 0.0)) {
 722     task->surf_action =
 723       surf_workstation_model->
 724       extension_public->communicate(surf_workstations[0],
 725                                     surf_workstations[0],
 726                                     task->communication_amount[0],
 727                                     task->rate);
 728   } else if ((task->workstation_nb == 2)
 729              && (task->computation_amount[0] == 0.0)
 730              && (task->computation_amount[1] == 0.0)) {
 731     int nb = 0;
 732     double value = 0.0;
 733
 734     for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
 735       if (task->communication_amount[i] > 0.0) {
 736         nb++;
 737         value = task->communication_amount[i];
 738       }
 739     }
 740     if (nb == 1) {
 741       task->surf_action =
 742         surf_workstation_model->
 743         extension_public->communicate(surf_workstations[0],
 744                                       surf_workstations[1], value,
 745                                       task->rate);
 746     }
 747   }
 748   if (!task->surf_action) {
 749     double *computation_amount = xbt_new(double, task->workstation_nb);
 750     double *communication_amount = xbt_new(double, task->workstation_nb *
 751                                            task->workstation_nb);
 752
 753     memcpy(computation_amount, task->computation_amount, sizeof(double) *
 754            task->workstation_nb);
 755     memcpy(communication_amount, task->communication_amount,
 756            sizeof(double) * task->workstation_nb * task->workstation_nb);
 757
 758     task->surf_action =
 759       surf_workstation_model->extension_public->execute_parallel_task(task->
 760                                                                       workstation_nb,
 761                                                                       surf_workstations,
 762                                                                       computation_amount,
 763                                                                       communication_amount,
 764                                                                       task->
 765                                                                       amount,
 766                                                                       task->
 767                                                                       rate);
 768   } else {
 769     xbt_free(surf_workstations);
 770   }
 771
 772   surf_workstation_model->common_public->action_set_data(task->surf_action,
 773                                                          task);
 774
 775   DEBUG1("surf_action = %p", task->surf_action);
 776
 777   __SD_task_destroy_scheduling_data(task);      /* now the scheduling data are not useful anymore */
 778   __SD_task_set_state(task, SD_RUNNING);
 779   xbt_assert2(__SD_task_is_running(task), "Bad state of task '%s': %d",
 780               SD_task_get_name(task), SD_task_get_state(task));
 781
 782 }
 783
 784 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_READY
 785  * (ie when its dependencies are satisfied).
 786  * If one of the workstations where the task is scheduled on is busy (in sequential mode),
 787  * the task doesn't start.
 788  * Returns whether the task has started.
 789  */
 790 int __SD_task_try_to_run(SD_task_t task)
 791 {
 792
 793   int can_start = 1;
 794   int i;
 795   SD_workstation_t workstation;
 796
 797   SD_CHECK_INIT_DONE();
 798   xbt_assert0(task != NULL, "Invalid parameter");
 799   xbt_assert2(__SD_task_is_ready(task),
 800               "Task '%s' is not ready! Task state: %d",
 801               SD_task_get_name(task), SD_task_get_state(task));
 802
 803
 804   for (i = 0; i < task->workstation_nb; i++) {
 805     can_start = !__SD_workstation_is_busy(task->workstation_list[i]);
 806   }
 807
 808   DEBUG2("Task '%s' can start: %d", SD_task_get_name(task), can_start);
 809
 810   if (!can_start) {             /* if the task cannot start and is not in the fifos yet */
 811     for (i = 0; i < task->workstation_nb; i++) {
 812       workstation = task->workstation_list[i];
 813       if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
 814         DEBUG2("Pushing task '%s' in the fifo of workstation '%s'",
 815                SD_task_get_name(task), SD_workstation_get_name(workstation));
 816         xbt_fifo_push(workstation->task_fifo, task);
 817       }
 818     }
 819     __SD_task_set_state(task, SD_IN_FIFO);
 820     xbt_assert2(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
 821                 SD_task_get_name(task), SD_task_get_state(task));
 822     DEBUG1("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
 823   } else {
 824     __SD_task_really_run(task);
 825   }
 826
 827   return can_start;
 828 }
 829
 830 /* This function is called by SD_simulate when a task is done.
 831  * It updates task->state and task->action and executes if necessary the tasks
 832  * which were waiting in fifos for the end of `task'
 833  */
 834 void __SD_task_just_done(SD_task_t task)
 835 {
 836   int i, j;
 837   SD_workstation_t workstation;
 838
 839   SD_task_t candidate;
 840   int candidate_nb = 0;
 841   int candidate_capacity = 8;
 842   SD_task_t *candidates;
 843   int can_start = 1;
 844
 845   SD_CHECK_INIT_DONE();
 846   xbt_assert0(task != NULL, "Invalid parameter");
 847   xbt_assert1(__SD_task_is_running(task),
 848               "The task must be running! Task state: %d",
 849               SD_task_get_state(task));
 850   xbt_assert1(task->workstation_list != NULL,
 851               "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
 852
 853
 854   candidates = xbt_new(SD_task_t, 8);
 855
 856   __SD_task_set_state(task, SD_DONE);
 857   surf_workstation_model->common_public->action_free(task->surf_action);
 858   task->surf_action = NULL;
 859
 860   DEBUG0("Looking for candidates");
 861
 862   /* if the task was executed on sequential workstations,
 863      maybe we can execute the next task of the fifo for each workstation */
 864   for (i = 0; i < task->workstation_nb; i++) {
 865     workstation = task->workstation_list[i];
 866     DEBUG2("Workstation '%s': access_mode = %d",
 867            SD_workstation_get_name(workstation), workstation->access_mode);
 868     if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
 869       xbt_assert1(workstation->task_fifo != NULL,
 870                   "Workstation '%s' has sequential access but no fifo!",
 871                   SD_workstation_get_name(workstation));
 872       xbt_assert2(workstation->current_task =
 873                   task, "Workstation '%s': current task should be '%s'",
 874                   SD_workstation_get_name(workstation),
 875                   SD_task_get_name(task));
 876
 877       /* the task is over so we can release the workstation */
 878       workstation->current_task = NULL;
 879
 880       DEBUG0("Getting candidate in fifo");
 881       candidate =
 882         xbt_fifo_get_item_content(xbt_fifo_get_first_item
 883                                   (workstation->task_fifo));
 884
 885       if (candidate != NULL) {
 886         DEBUG1("Candidate: '%s'", SD_task_get_name(candidate));
 887         xbt_assert2(__SD_task_is_in_fifo(candidate),
 888                     "Bad state of candidate '%s': %d",
 889                     SD_task_get_name(candidate),
 890                     SD_task_get_state(candidate));
 891       }
 892
 893       DEBUG1("Candidate in fifo: %p", candidate);
 894
 895       /* if there was a task waiting for my place */
 896       if (candidate != NULL) {
 897         /* Unfortunately, we are not sure yet that we can execute the task now,
 898            because the task can be waiting more deeply in some other workstation's fifos...
 899            So we memorize all candidate tasks, and then we will check for each candidate
 900            whether or not all its workstations are available. */
 901
 902         /* realloc if necessary */
 903         if (candidate_nb == candidate_capacity) {
 904           candidate_capacity *= 2;
 905           candidates =
 906             xbt_realloc(candidates, sizeof(SD_task_t) * candidate_capacity);
 907         }
 908
 909         /* register the candidate */
 910         candidates[candidate_nb++] = candidate;
 911         candidate->fifo_checked = 0;
 912       }
 913     }
 914   }
 915
 916   DEBUG1("Candidates found: %d", candidate_nb);
 917
 918   /* now we check every candidate task */
 919   for (i = 0; i < candidate_nb; i++) {
 920     candidate = candidates[i];
 921
 922     if (candidate->fifo_checked) {
 923       continue;                 /* we have already evaluated that task */
 924     }
 925
 926     xbt_assert2(__SD_task_is_in_fifo(candidate),
 927                 "Bad state of candidate '%s': %d",
 928                 SD_task_get_name(candidate), SD_task_get_state(candidate));
 929
 930     for (j = 0; j < candidate->workstation_nb && can_start; j++) {
 931       workstation = candidate->workstation_list[j];
 932
 933       /* I can start on this workstation if the workstation is shared
 934          or if I am the first task in the fifo */
 935       can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS ||
 936         candidate ==
 937         xbt_fifo_get_item_content(xbt_fifo_get_first_item
 938                                   (workstation->task_fifo));
 939     }
 940
 941     DEBUG2("Candidate '%s' can start: %d", SD_task_get_name(candidate),
 942            can_start);
 943
 944     /* now we are sure that I can start! */
 945     if (can_start) {
 946       for (j = 0; j < candidate->workstation_nb && can_start; j++) {
 947         workstation = candidate->workstation_list[j];
 948
 949         /* update the fifo */
 950         if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
 951           candidate = xbt_fifo_shift(workstation->task_fifo);   /* the return value is stored just for debugging */
 952           DEBUG1("Head of the fifo: '%s'",
 953                  (candidate != NULL) ? SD_task_get_name(candidate) : "NULL");
 954           xbt_assert0(candidate == candidates[i],
 955                       "Error in __SD_task_just_done: bad first task in the fifo");
 956         }
 957       }                         /* for each workstation */
 958
 959       /* finally execute the task */
 960       DEBUG2("Task '%s' state: %d", SD_task_get_name(candidate),
 961              SD_task_get_state(candidate));
 962       __SD_task_really_run(candidate);
 963
 964       DEBUG4
 965         ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
 966          SD_task_get_name(candidate), candidate->state_set,
 967          sd_global->running_task_set, __SD_task_is_running(candidate));
 968       xbt_assert2(__SD_task_is_running(candidate),
 969                   "Bad state of task '%s': %d", SD_task_get_name(candidate),
 970                   SD_task_get_state(candidate));
 971       DEBUG0("Okay, the task is running.");
 972
 973     }                           /* can start */
 974     candidate->fifo_checked = 1;
 975   }                             /* for each candidate */
 976
 977   xbt_free(candidates);
 978 }
 979
 980 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
 981  */
 982 static void __SD_task_remove_dependencies(SD_task_t task)
 983 {
 984   /* we must destroy the dependencies carefuly (with SD_dependency_remove)
 985      because each one is stored twice */
 986   SD_dependency_t dependency;
 987   while (xbt_dynar_length(task->tasks_before) > 0) {
 988     xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
 989     SD_task_dependency_remove(dependency->src, dependency->dst);
 990   }
 991
 992   while (xbt_dynar_length(task->tasks_after) > 0) {
 993     xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
 994     SD_task_dependency_remove(dependency->src, dependency->dst);
 995   }
 996 }
 997
 998 /**
 999  * \brief Returns the start time of a task
1000  *
1001  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1002  *
1003  * \param task: a task
1004  * \return the start time of this task
1005  */
1006 double SD_task_get_start_time(SD_task_t task)
1007 {
1008   SD_CHECK_INIT_DONE();
1009   xbt_assert0(task != NULL, "Invalid parameter");
1010   if (task->surf_action)
1011     return surf_workstation_model->common_public->action_get_start_time(task->
1012                                                                         surf_action);
1013   else
1014     return task->start_time;
1015 }
1016
1017 /**
1018  * \brief Returns the finish time of a task
1019  *
1020  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1021  * If the state is not completed yet, the returned value is an
1022  * estimation of the task finish time. This value can fluctuate
1023  * until the task is completed.
1024  *
1025  * \param task: a task
1026  * \return the start time of this task
1027  */
1028 double SD_task_get_finish_time(SD_task_t task)
1029 {
1030   SD_CHECK_INIT_DONE();
1031   xbt_assert0(task != NULL, "Invalid parameter");
1032
1033   if (task->surf_action)        /* should never happen as actions are destroyed right after their completion */
1034     return surf_workstation_model->common_public->
1035       action_get_finish_time(task->surf_action);
1036   else
1037     return task->finish_time;
1038 }
1039
1040 /**
1041  * \brief Destroys a task.
1042  *
1043  * The user data (if any) should have been destroyed first.
1044  *
1045  * \param task the task you want to destroy
1046  * \see SD_task_create()
1047  */
1048 void SD_task_destroy(SD_task_t task)
1049 {
1050   SD_CHECK_INIT_DONE();
1051   xbt_assert0(task != NULL, "Invalid parameter");
1052
1053   DEBUG1("Destroying task %s...", SD_task_get_name(task));
1054
1055   __SD_task_remove_dependencies(task);
1056
1057   /* if the task was scheduled or ready we have to free the scheduling parameters */
1058   if (__SD_task_is_scheduled_or_ready(task))
1059     __SD_task_destroy_scheduling_data(task);
1060
1061   if (task->name != NULL)
1062     xbt_free(task->name);
1063
1064   if (task->surf_action != NULL)
1065     surf_workstation_model->common_public->action_free(task->surf_action);
1066
1067   if (task->workstation_list != NULL)
1068     xbt_free(task->workstation_list);
1069
1070   xbt_dynar_free(&task->tasks_before);
1071   xbt_dynar_free(&task->tasks_after);
1072   xbt_free(task);
1073
1074   sd_global->task_number--;
1075
1076   DEBUG0("Task destroyed.");
1077 }