Logo AND Algorithmique Numérique Distribuée

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