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