gs_htm.c

Go to the documentation of this file.
00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <time.h>
00004 #include <math.h>
00005 #include <sys/types.h>
00006 #include <sys/uio.h>
00007 #include <unistd.h>
00008 
00009 #include "gs_htm.h"
00010 
00011 void dump_all_tasks(gs_htm_server *s);
00012 
00013 #define fl_eq(a,b) (fabs((a)-(b)) < 0.0001)
00014 
00026 static int
00027 gs_htm_server_compare_function(const void *p1, const void *p2)
00028 {
00029   gs_htm_server *s1, *s2;
00030 
00031   if(!p1 || !p2) return 0;
00032 
00033   s1 = *((gs_htm_server **) p1);
00034   s2 = *((gs_htm_server **) p2);
00035 
00036   if(s1->metric > s2->metric)
00037     return 1;
00038   if(s1->metric < s2->metric)
00039     return -1;
00040 
00041   return 0;
00042 }
00043 
00044 void
00045 gs_htm_display_server(gs_htm_server * s)
00046 {
00047   gs_htm_task *t;
00048 
00049   if(!s)
00050     return;
00051   for(t = s->first; t; t = t->next) {
00052     printf("%s\t%g\t%g\t%g\t%g\n", t->id, t->start, t->end, t->duration,
00053            t->remaining);
00054   }
00055 }
00056 
00057 double
00058 gs_htm_first_event(gs_htm_server * s)
00059 {
00060   gs_htm_task *t;
00061   double time;
00062 
00063   if(!s->current) {
00064     s->running = 0;
00065     return -1;
00066   }
00067   else {
00068     s->running = 0;
00069     time = s->current->start;
00070     for(t = s->current; t; t = t->next) {
00071       if(t->start == time) {
00072         s->running++;
00073         t->active = 1;
00074         if(!t->finished)
00075           t->remaining = t->duration;
00076       }
00077       else {
00078         t->active = 0;
00079       }
00080     }
00081 
00082     return time;
00083   }
00084 }
00085 
00086 double
00087 gs_htm_next_event(gs_htm_server * s, double start)
00088 {
00089   double next, event = 0.0, min_remaining;
00090   gs_htm_task *t, *c, *event_t;
00091   int ctype, type;
00092 
00093   /*
00094    * determine the date and type of next event
00095    */
00096   c = s->current;
00097   if(!c)
00098     return -1;
00099 
00100   next = -1;
00101 
00102   type = 0;
00103   event_t = NULL;
00104   for(t = c; t; t = t->next) {
00105     ctype = 0;
00106     if(t->active) {
00107       if(t->remaining) {
00108         event = start + t->remaining * s->running;
00109         ctype = END_TASK;
00110       }
00111       else {
00112         event = t->end;         /* task allready finished : do not simulate it
00113                                  * using share processus */
00114         ctype = FINISH_TASK;
00115       }
00116     }
00117     else {
00118       if((t->start >= start) && (t->duration)) {
00119         event = t->start;
00120         ctype = NEW_TASK;
00121       }
00122     }
00123     if(ctype) {
00124       if(next == -1) {
00125         next = event;
00126         event_t = t;
00127         type = ctype;
00128       }
00129       else if(next > event) {
00130         event_t = t;
00131         next = event;
00132         type = ctype;
00133       }
00134     }
00135   }
00136 
00137   min_remaining = 0;
00138   if((type == END_TASK) && (event_t))
00139     min_remaining = event_t->remaining;
00140 
00141   /* 
00142    * printf("start=%g, next=%g,\n",start,next);
00143    * gs_htm_display_server(s);
00144    */
00145 
00146   /*
00147    * update duration of active tasks up to next event
00148    */
00149   for(t = c; t; t = t->next) {
00150     if(!t->finished)
00151       if(t->active) {
00152         if((type == END_TASK)) {
00153           t->remaining -= min_remaining;
00154           t->end += min_remaining * s->running;
00155         }
00156         else {
00157           t->remaining -= ((next - start) / s->running);
00158           t->end += (next - start);
00159         }
00160       }
00161   }
00162 
00163   /*
00164    * update active task
00165    */
00166   s->running = 0;
00167   for(t = c; t; t = t->next) {
00168     if((fl_eq(t->end, next) && (t->remaining != 0.0))
00169        || ((t->start == next) && (t->duration != 0.0)) || ((t->start <= next)
00170                                                          && (t->end > next))) {
00171       if((!t->active) && (!t->finished))
00172         t->remaining = t->duration;
00173       t->active = 1;
00174       s->running++;
00175       if(fl_eq(t->end, next))
00176         t->end = next;
00177     }
00178     else {
00179       t->active = 0;
00180     }
00181   }
00182 
00183   for(t = c; t; t = t->next) {
00184     if((t->active) || (t->start > next))
00185       break;
00186   }
00187   s->current = t;
00188 
00189   return next;
00190 }
00191 
00192 void
00193 gs_htm_simulate_server(gs_htm_server * s)
00194 {
00195   double time1, time2;
00196 
00197   s->current = s->first;
00198   time1 = gs_htm_first_event(s);
00199   if(time1 == -1.0) {             /* server is empty */
00200     return;
00201   }
00202   while((time2 = gs_htm_next_event(s, time1)) != -1) {
00203     time1 = time2;
00204   }
00205 }
00206 
00207 
00208 gs_htm_task *
00209 gs_htm_new_task(char *id, double start, double duration)
00210 {
00211   gs_htm_task *res;
00212 
00213   res = (gs_htm_task *) malloc(sizeof(gs_htm_task));
00214   strcpy(res->id, id);
00215   res->start = start;
00216   res->duration = duration;
00217   res->end = start;
00218   res->remaining = 0;
00219   res->active = 0;
00220   res->finished = 0;
00221   res->next = NULL;
00222   res->agent_taskid = -1;
00223 
00224   return res;
00225 }
00226 
00227 gs_htm_task *
00228 gs_htm_finished_task(char *id, double start, double end)
00229 {
00230   gs_htm_task *res;
00231 
00232   res = (gs_htm_task *) malloc(sizeof(gs_htm_task));
00233 
00234   strcpy(res->id, id);
00235   res->start = start;
00236   res->duration = end - start;
00237   res->end = end;
00238   res->remaining = 0;
00239   res->active = 0;
00240   res->finished = 1;
00241 
00242   return res;
00243 }
00244 
00245 gs_htm_server *
00246 gs_htm_new_empty_server(char *id, gs_server_t *sptr)
00247 {
00248   gs_htm_server *s;
00249 
00250   s = (gs_htm_server *) malloc(sizeof(gs_htm_server));
00251   s->current = s->first = s->last = NULL;
00252   s->sptr = sptr;
00253   s->running = 0;
00254   s->agent_assigned_score = 0.0;
00255   memcpy(s->id, id, CID_LEN);
00256 
00257   return s;
00258 }
00259 
00260 void
00261 gs_htm_add_task(gs_htm_server * s, gs_htm_task * new_t)
00262 {
00263   gs_htm_task *t, *prev;
00264 
00265   if(!s->first) {
00266     s->first = s->last = new_t;
00267     return;
00268   }
00269 
00270   if(new_t->start < s->first->start) {
00271     new_t->next = s->first;
00272     s->first = new_t;
00273   }
00274 
00275   t = s->first->next;
00276   prev = s->first;
00277 
00278   while(t) {
00279     if(new_t->start < t->start) {
00280       prev->next = new_t;
00281       new_t->next = t;
00282       break;
00283     }
00284     prev = t;
00285     t = t->next;
00286   }
00287   if(t == NULL) {
00288     prev->next = new_t;
00289     new_t->next = NULL;
00290     s->last = new_t;
00291   }
00292 }
00293 
00294 double
00295 gs_htm_perturbation(gs_htm_server * s)
00296 {
00297   gs_htm_task *t;
00298   double res = 0;
00299 
00300   for(t = s->first; t; t = t->next)
00301     res += t->end - t->start - t->duration;
00302 
00303   return res;
00304 }
00305 
00306 double
00307 gs_htm_makespan(gs_htm_server * s)
00308 {
00309   gs_htm_task *t;
00310 
00311   double res = 0;
00312   for(t = s->first; t; t = t->next)
00313     if(t->end > res)
00314       res = t->end;
00315 
00316   return res;
00317 }
00318 
00319 double
00320 gs_htm_flow(gs_htm_server * s)
00321 {
00322   gs_htm_task *t;
00323 
00324   double res = 0;
00325   for(t = s->first; t; t = t->next)
00326     res += t->end - t->start;
00327 
00328   return res;
00329 }
00330 
00331 double
00332 gs_htm_length(gs_htm_server * s, double date)
00333 {
00334   gs_htm_task *t;
00335 
00336   double res = 0;
00337   for(t = s->first; t; t = t->next) {
00338     if(t->end > date)
00339       res += min(t->end - date, t->end - t->start);
00340   }
00341   return res;
00342 }
00343 
00344 gs_htm_task *
00345 gs_htm_clone_task(gs_htm_task * t)
00346 {
00347   gs_htm_task *res;
00348 
00349   res = (gs_htm_task *) malloc(sizeof(gs_htm_task));
00350   strcpy(res->id, t->id);
00351   res->start = t->start;
00352   res->duration = t->duration;
00353   res->end = t->end;
00354   res->remaining = t->remaining;
00355   res->active = t->active;
00356   res->finished = t->finished;
00357   res->next = t->next;
00358   return res;
00359 }
00360 
00361 void
00362 gs_htm_add_task_last(gs_htm_server * s, gs_htm_task * t)
00363 {
00364   if(!s->first) {
00365     s->first = s->last = t;
00366     return;
00367   }
00368 
00369   s->last->next = t;
00370   t->next = NULL;
00371   s->last = t;
00372 }
00373 
00374 gs_htm_server *
00375 gs_htm_clone_server(gs_htm_server * s)
00376 {
00377   gs_htm_server *new_s;
00378   gs_htm_task *t, *new_t;;
00379 
00380   new_s = gs_htm_new_empty_server(s->id, s->sptr);
00381   for(t = s->first; t; t = t->next) {
00382     new_t = gs_htm_clone_task(t);
00383     gs_htm_add_task_last(new_s, new_t);
00384   }
00385   return new_s;
00386 }
00387 
00388 void
00389 gs_htm_raz_simulation(gs_htm_server * s)
00390 {
00391   gs_htm_task *t;
00392 
00393   for(t = s->first; t; t = t->next) {
00394     if(t->finished)
00395       t->end = t->start + t->duration;
00396     else
00397       t->end = t->start;
00398   }
00399 }
00400 
00401 void
00402 gs_htm_remove_task(gs_htm_server * s, char *id)
00403 {
00404   gs_htm_task *t, *prev = NULL;
00405 
00406   for(t = s->first; t; t = t->next) {
00407     if(!strcmp(t->id, id)) {
00408       if(!prev) {
00409         s->first = t->next;
00410       }
00411       else {
00412         prev->next = t->next;
00413       }
00414       free(t);
00415       return;
00416     }
00417     prev = t;
00418   }
00419 }
00420 
00421 int
00422 gs_htm_ML(gs_htm_server **sl, int n, gs_htm_task * t)
00423 {
00424   gs_htm_server *s;
00425   gs_htm_task *clone;
00426   int idx;
00427   double *scores;
00428 
00429   scores = (double *)malloc(n * sizeof(double));
00430 
00431   if(!scores)
00432     return -1;
00433 
00434   for(idx = 0; idx < n; idx++) {
00435     s = sl[idx];
00436 
00437     clone = gs_htm_clone_task(t);
00438     clone->duration = s->agent_assigned_score;
00439     gs_htm_add_task(s, clone);
00440     gs_htm_raz_simulation(s);
00441     gs_htm_simulate_server(s);
00442     s->metric = gs_htm_length(s, t->start);
00443     scores[idx] = clone->duration;
00444     gs_htm_remove_task(s, t->id);
00445   }
00446 
00447   /* set the scores as the task durations */
00448   for(idx=0;idx<n;idx++)
00449     sl[idx]->sptr->score = scores[idx];
00450 
00451   qsort(sl, n, sizeof(gs_htm_task *), gs_htm_server_compare_function);
00452 
00453   free(scores);
00454 
00455   return 0;
00456 }
00457 
00458 int
00459 gs_htm_MSF(gs_htm_server **sl, int n, gs_htm_task * t)
00460 {
00461   gs_htm_server *s;
00462   gs_htm_task *clone;
00463   int idx;
00464   double *scores;
00465 
00466   scores = (double *)malloc(n * sizeof(double));
00467 
00468   if(!scores)
00469     return -1;
00470 
00471   for(idx = 0; idx < n; idx++) {
00472     s = sl[idx];
00473 
00474     clone = gs_htm_clone_task(t);
00475     clone->duration = s->agent_assigned_score;
00476     gs_htm_add_task(s, clone);
00477     gs_htm_raz_simulation(s);
00478     gs_htm_simulate_server(s);
00479     s->metric = gs_htm_flow(s);
00480     scores[idx] = clone->duration;
00481     gs_htm_remove_task(s, t->id);
00482   }
00483 
00484   /* set the scores as the task durations */
00485   for(idx=0;idx<n;idx++)
00486     sl[idx]->sptr->score = scores[idx];
00487 
00488   qsort(sl, n, sizeof(gs_htm_task *), gs_htm_server_compare_function);
00489 
00490   free(scores);
00491 
00492   return 0;
00493 }
00494 
00495 int
00496 gs_htm_HMCT(gs_htm_server **sl, int n, gs_htm_task * t)
00497 {
00498   gs_htm_server *s;
00499   gs_htm_task *clone;
00500   int idx;
00501   double *scores;
00502 
00503   scores = (double *)malloc(n * sizeof(double));
00504 
00505   if(!scores)
00506     return -1;
00507 
00508   for(idx = 0; idx < n; idx++) {
00509     s = sl[idx];
00510 
00511     clone = gs_htm_clone_task(t);
00512     clone->duration = s->agent_assigned_score;
00513     gs_htm_add_task(s, clone);
00514     gs_htm_raz_simulation(s);
00515     gs_htm_simulate_server(s);
00516     s->metric = clone->end;
00517     scores[idx] = clone->duration;
00518     gs_htm_remove_task(s, t->id);
00519   }
00520 
00521   /* set the scores as the task durations */
00522   for(idx=0;idx<n;idx++)
00523     sl[idx]->sptr->score = scores[idx];
00524 
00525   qsort(sl, n, sizeof(gs_htm_task *), gs_htm_server_compare_function);
00526 
00527   free(scores);
00528 
00529   return 0;
00530 }
00531 
00532 void
00533 dump_all_tasks(gs_htm_server *s)
00534 {
00535   gs_htm_task *t;
00536 
00537   printf("====== dumping all tasks ===\n");
00538   for(t = s->first; t; t = t->next) {
00539    printf("%s: e=%g, s=%g, d=%g r=%g, a=%d, f=%d\n", 
00540      s->sptr->hostname, t->end, t->start, t->duration, t->remaining,
00541      t->active, t->finished);
00542    if(t->remaining != 0.0 && t->active == 0) {
00543      printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");
00544      printf("@@@@@@   THIS IS NOT GOOD @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");
00545      printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");
00546    }
00547   }
00548   printf("====== done dumping all tasks ===\n");
00549 }
00550 
00551 int
00552 gs_htm_MP(gs_htm_server **sl, int n, gs_htm_task * t)
00553 {
00554   gs_htm_server *s;
00555   gs_htm_task *clone;
00556   int idx;
00557   double *scores;
00558 
00559   scores = (double *)malloc(n * sizeof(double));
00560 
00561   if(!scores)
00562     return -1;
00563 
00564   for(idx = 0; idx < n; idx++) {
00565     s = sl[idx];
00566 
00567     clone = gs_htm_clone_task(t);
00568     clone->duration = s->agent_assigned_score;
00569     gs_htm_add_task(s, clone);
00570     gs_htm_raz_simulation(s);
00571     gs_htm_simulate_server(s);
00572     s->metric = gs_htm_perturbation(s);
00573     scores[idx] = clone->duration;
00574     gs_htm_remove_task(s, t->id);
00575   }
00576 
00577   /* set the scores as the task durations */
00578   for(idx=0;idx<n;idx++)
00579     sl[idx]->sptr->score = scores[idx];
00580 
00581   qsort(sl, n, sizeof(gs_htm_task *), gs_htm_server_compare_function);
00582 
00583   free(scores);
00584 
00585   return 0;
00586 }
00587 
00588 void
00589 gs_rand_id(char id[CID_LEN])
00590 {
00591   int i;
00592 
00593   for(i=0;i<CID_LEN;i++)
00594     id[i] = (char) (random() % 256);
00595 }
00596 
00597 /***
00598 
00599 #define NUMSERV 5
00600 
00601 int
00602 main()
00603 {
00604   gs_htm_server *s;
00605   int i;
00606   gs_htm_task *t;
00607   gs_htm_server **sl;
00608   double fl = 0, ms = 0, per = 0;
00609   char id[CID_LEN], tid[TASK_ID_LEN];
00610 
00611   sl = (gs_htm_server **)malloc(NUMSERV * sizeof(gs_htm_server *));
00612 
00613   for(i = 0; i < NUMSERV; i++) {
00614     gs_rand_id(id);
00615     sl[i] = gs_htm_new_empty_server(id, NULL);
00616   }
00617 
00618   srandom(0);
00619 
00620   for(i = 0; i < 1000; i++) {
00621     sprintf(tid, "%d", i);
00622     t = gs_htm_new_task(tid, 0, random() % 20);
00623     gs_htm_MP(sl, NUMSERV, t);
00624   }
00625 
00626   for(i = 0; i < NUMSERV; i++) {
00627     char printable_id[CID_LEN*2+1];
00628 
00629     s = sl[i];
00630     proxy_cid_to_str(printable_id, s->id);
00631     gs_htm_raz_simulation(s);
00632     gs_htm_simulate_server(s);
00633     printf("%s flow: %g, perturbation: %g , makespan: %g\n", printable_id, 
00634            gs_htm_flow(s), gs_htm_perturbation(s), gs_htm_makespan(s));
00635     fl += gs_htm_flow(s);
00636     per += gs_htm_perturbation(s);
00637     ms += gs_htm_makespan(s);
00638   }
00639   printf("Sumflow : %g, Sum perturbation : %g , Sum makespan : %g\n", fl, per,
00640          ms);
00641 
00642   return 0;
00643 }
00644 
00645 ***/