Logo AND Algorithmique Numérique Distribuée

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