src/simdag/sd_task.c

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