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