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