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