gs_htm.c

Go to the documentation of this file.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <unistd.h>

#include "gs_htm.h"

void dump_all_tasks(gs_htm_server *s);

#define fl_eq(a,b) (fabs((a)-(b)) < 0.0001)

static int
gs_htm_server_compare_function(const void *p1, const void *p2)
{
  gs_htm_server *s1, *s2;

  if(!p1 || !p2) return 0;

  s1 = *((gs_htm_server **) p1);
  s2 = *((gs_htm_server **) p2);

  if(s1->metric > s2->metric)
    return 1;
  if(s1->metric < s2->metric)
    return -1;

  return 0;
}

void
gs_htm_display_server(gs_htm_server * s)
{
  gs_htm_task *t;

  if(!s)
    return;
  for(t = s->first; t; t = t->next) {
    printf("%s\t%g\t%g\t%g\t%g\n", t->id, t->start, t->end, t->duration,
           t->remaining);
  }
}

double
gs_htm_first_event(gs_htm_server * s)
{
  gs_htm_task *t;
  double time;

  if(!s->current) {
    s->running = 0;
    return -1;
  }
  else {
    s->running = 0;
    time = s->current->start;
    for(t = s->current; t; t = t->next) {
      if(t->start == time) {
        s->running++;
        t->active = 1;
        if(!t->finished)
          t->remaining = t->duration;
      }
      else {
        t->active = 0;
      }
    }

    return time;
  }
}

double
gs_htm_next_event(gs_htm_server * s, double start)
{
  double next, event = 0.0, min_remaining;
  gs_htm_task *t, *c, *event_t;
  int ctype, type;

  /*
   * determine the date and type of next event
   */
  c = s->current;
  if(!c)
    return -1;

  next = -1;

  type = 0;
  event_t = NULL;
  for(t = c; t; t = t->next) {
    ctype = 0;
    if(t->active) {
      if(t->remaining) {
        event = start + t->remaining * s->running;
        ctype = END_TASK;
      }
      else {
        event = t->end;         /* task allready finished : do not simulate it
                                 * using share processus */
        ctype = FINISH_TASK;
      }
    }
    else {
      if((t->start >= start) && (t->duration)) {
        event = t->start;
        ctype = NEW_TASK;
      }
    }
    if(ctype) {
      if(next == -1) {
        next = event;
        event_t = t;
        type = ctype;
      }
      else if(next > event) {
        event_t = t;
        next = event;
        type = ctype;
      }
    }
  }

  min_remaining = 0;
  if((type == END_TASK) && (event_t))
    min_remaining = event_t->remaining;

  /* 
   * printf("start=%g, next=%g,\n",start,next);
   * gs_htm_display_server(s);
   */

  /*
   * update duration of active tasks up to next event
   */
  for(t = c; t; t = t->next) {
    if(!t->finished)
      if(t->active) {
        if((type == END_TASK)) {
          t->remaining -= min_remaining;
          t->end += min_remaining * s->running;
        }
        else {
          t->remaining -= ((next - start) / s->running);
          t->end += (next - start);
        }
      }
  }

  /*
   * update active task
   */
  s->running = 0;
  for(t = c; t; t = t->next) {
    if((fl_eq(t->end, next) && (t->remaining != 0.0))
       || ((t->start == next) && (t->duration != 0.0)) || ((t->start <= next)
                                                         && (t->end > next))) {
      if((!t->active) && (!t->finished))
        t->remaining = t->duration;
      t->active = 1;
      s->running++;
      if(fl_eq(t->end, next))
        t->end = next;
    }
    else {
      t->active = 0;
    }
  }

  for(t = c; t; t = t->next) {
    if((t->active) || (t->start > next))
      break;
  }
  s->current = t;

  return next;
}

void
gs_htm_simulate_server(gs_htm_server * s)
{
  double time1, time2;

  s->current = s->first;
  time1 = gs_htm_first_event(s);
  if(time1 == -1.0) {             /* server is empty */
    return;
  }
  while((time2 = gs_htm_next_event(s, time1)) != -1) {
    time1 = time2;
  }
}


gs_htm_task *
gs_htm_new_task(char *id, double start, double duration)
{
  gs_htm_task *res;

  res = (gs_htm_task *) malloc(sizeof(gs_htm_task));
  strcpy(res->id, id);
  res->start = start;
  res->duration = duration;
  res->end = start;
  res->remaining = 0;
  res->active = 0;
  res->finished = 0;
  res->next = NULL;
  res->agent_taskid = -1;

  return res;
}

gs_htm_task *
gs_htm_finished_task(char *id, double start, double end)
{
  gs_htm_task *res;

  res = (gs_htm_task *) malloc(sizeof(gs_htm_task));

  strcpy(res->id, id);
  res->start = start;
  res->duration = end - start;
  res->end = end;
  res->remaining = 0;
  res->active = 0;
  res->finished = 1;

  return res;
}

gs_htm_server *
gs_htm_new_empty_server(char *id, gs_server_t *sptr)
{
  gs_htm_server *s;

  s = (gs_htm_server *) malloc(sizeof(gs_htm_server));
  s->current = s->first = s->last = NULL;
  s->sptr = sptr;
  s->running = 0;
  s->agent_assigned_score = 0.0;
  memcpy(s->id, id, CID_LEN);

  return s;
}

void
gs_htm_add_task(gs_htm_server * s, gs_htm_task * new_t)
{
  gs_htm_task *t, *prev;

  if(!s->first) {
    s->first = s->last = new_t;
    return;
  }

  if(new_t->start < s->first->start) {
    new_t->next = s->first;
    s->first = new_t;
  }

  t = s->first->next;
  prev = s->first;

  while(t) {
    if(new_t->start < t->start) {
      prev->next = new_t;
      new_t->next = t;
      break;
    }
    prev = t;
    t = t->next;
  }
  if(t == NULL) {
    prev->next = new_t;
    new_t->next = NULL;
    s->last = new_t;
  }
}

double
gs_htm_perturbation(gs_htm_server * s)
{
  gs_htm_task *t;
  double res = 0;

  for(t = s->first; t; t = t->next)
    res += t->end - t->start - t->duration;

  return res;
}

double
gs_htm_makespan(gs_htm_server * s)
{
  gs_htm_task *t;

  double res = 0;
  for(t = s->first; t; t = t->next)
    if(t->end > res)
      res = t->end;

  return res;
}

double
gs_htm_flow(gs_htm_server * s)
{
  gs_htm_task *t;

  double res = 0;
  for(t = s->first; t; t = t->next)
    res += t->end - t->start;

  return res;
}

double
gs_htm_length(gs_htm_server * s, double date)
{
  gs_htm_task *t;

  double res = 0;
  for(t = s->first; t; t = t->next) {
    if(t->end > date)
      res += min(t->end - date, t->end - t->start);
  }
  return res;
}

gs_htm_task *
gs_htm_clone_task(gs_htm_task * t)
{
  gs_htm_task *res;

  res = (gs_htm_task *) malloc(sizeof(gs_htm_task));
  strcpy(res->id, t->id);
  res->start = t->start;
  res->duration = t->duration;
  res->end = t->end;
  res->remaining = t->remaining;
  res->active = t->active;
  res->finished = t->finished;
  res->next = t->next;
  return res;
}

void
gs_htm_add_task_last(gs_htm_server * s, gs_htm_task * t)
{
  if(!s->first) {
    s->first = s->last = t;
    return;
  }

  s->last->next = t;
  t->next = NULL;
  s->last = t;
}

gs_htm_server *
gs_htm_clone_server(gs_htm_server * s)
{
  gs_htm_server *new_s;
  gs_htm_task *t, *new_t;;

  new_s = gs_htm_new_empty_server(s->id, s->sptr);
  for(t = s->first; t; t = t->next) {
    new_t = gs_htm_clone_task(t);
    gs_htm_add_task_last(new_s, new_t);
  }
  return new_s;
}

void
gs_htm_raz_simulation(gs_htm_server * s)
{
  gs_htm_task *t;

  for(t = s->first; t; t = t->next) {
    if(t->finished)
      t->end = t->start + t->duration;
    else
      t->end = t->start;
  }
}

void
gs_htm_remove_task(gs_htm_server * s, char *id)
{
  gs_htm_task *t, *prev = NULL;

  for(t = s->first; t; t = t->next) {
    if(!strcmp(t->id, id)) {
      if(!prev) {
        s->first = t->next;
      }
      else {
        prev->next = t->next;
      }
      free(t);
      return;
    }
    prev = t;
  }
}

int
gs_htm_ML(gs_htm_server **sl, int n, gs_htm_task * t)
{
  gs_htm_server *s;
  gs_htm_task *clone;
  int idx;
  double *scores;

  scores = (double *)malloc(n * sizeof(double));

  if(!scores)
    return -1;

  for(idx = 0; idx < n; idx++) {
    s = sl[idx];

    clone = gs_htm_clone_task(t);
    clone->duration = s->agent_assigned_score;
    gs_htm_add_task(s, clone);
    gs_htm_raz_simulation(s);
    gs_htm_simulate_server(s);
    s->metric = gs_htm_length(s, t->start);
    scores[idx] = clone->duration;
    gs_htm_remove_task(s, t->id);
  }

  /* set the scores as the task durations */
  for(idx=0;idx<n;idx++)
    sl[idx]->sptr->score = scores[idx];

  qsort(sl, n, sizeof(gs_htm_task *), gs_htm_server_compare_function);

  free(scores);

  return 0;
}

int
gs_htm_MSF(gs_htm_server **sl, int n, gs_htm_task * t)
{
  gs_htm_server *s;
  gs_htm_task *clone;
  int idx;
  double *scores;

  scores = (double *)malloc(n * sizeof(double));

  if(!scores)
    return -1;

  for(idx = 0; idx < n; idx++) {
    s = sl[idx];

    clone = gs_htm_clone_task(t);
    clone->duration = s->agent_assigned_score;
    gs_htm_add_task(s, clone);
    gs_htm_raz_simulation(s);
    gs_htm_simulate_server(s);
    s->metric = gs_htm_flow(s);
    scores[idx] = clone->duration;
    gs_htm_remove_task(s, t->id);
  }

  /* set the scores as the task durations */
  for(idx=0;idx<n;idx++)
    sl[idx]->sptr->score = scores[idx];

  qsort(sl, n, sizeof(gs_htm_task *), gs_htm_server_compare_function);

  free(scores);

  return 0;
}

int
gs_htm_HMCT(gs_htm_server **sl, int n, gs_htm_task * t)
{
  gs_htm_server *s;
  gs_htm_task *clone;
  int idx;
  double *scores;

  scores = (double *)malloc(n * sizeof(double));

  if(!scores)
    return -1;

  for(idx = 0; idx < n; idx++) {
    s = sl[idx];

    clone = gs_htm_clone_task(t);
    clone->duration = s->agent_assigned_score;
    gs_htm_add_task(s, clone);
    gs_htm_raz_simulation(s);
    gs_htm_simulate_server(s);
    s->metric = clone->end;
    scores[idx] = clone->duration;
    gs_htm_remove_task(s, t->id);
  }

  /* set the scores as the task durations */
  for(idx=0;idx<n;idx++)
    sl[idx]->sptr->score = scores[idx];

  qsort(sl, n, sizeof(gs_htm_task *), gs_htm_server_compare_function);

  free(scores);

  return 0;
}

void
dump_all_tasks(gs_htm_server *s)
{
  gs_htm_task *t;

  printf("====== dumping all tasks ===\n");
  for(t = s->first; t; t = t->next) {
   printf("%s: e=%g, s=%g, d=%g r=%g, a=%d, f=%d\n", 
     s->sptr->hostname, t->end, t->start, t->duration, t->remaining,
     t->active, t->finished);
   if(t->remaining != 0.0 && t->active == 0) {
     printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");
     printf("@@@@@@   THIS IS NOT GOOD @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");
     printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");
   }
  }
  printf("====== done dumping all tasks ===\n");
}

int
gs_htm_MP(gs_htm_server **sl, int n, gs_htm_task * t)
{
  gs_htm_server *s;
  gs_htm_task *clone;
  int idx;
  double *scores;

  scores = (double *)malloc(n * sizeof(double));

  if(!scores)
    return -1;

  for(idx = 0; idx < n; idx++) {
    s = sl[idx];

    clone = gs_htm_clone_task(t);
    clone->duration = s->agent_assigned_score;
    gs_htm_add_task(s, clone);
    gs_htm_raz_simulation(s);
    gs_htm_simulate_server(s);
    s->metric = gs_htm_perturbation(s);
    scores[idx] = clone->duration;
    gs_htm_remove_task(s, t->id);
  }

  /* set the scores as the task durations */
  for(idx=0;idx<n;idx++)
    sl[idx]->sptr->score = scores[idx];

  qsort(sl, n, sizeof(gs_htm_task *), gs_htm_server_compare_function);

  free(scores);

  return 0;
}

void
gs_rand_id(char id[CID_LEN])
{
  int i;

  for(i=0;i<CID_LEN;i++)
    id[i] = (char) (random() % 256);
}

/***

#define NUMSERV 5

int
main()
{
  gs_htm_server *s;
  int i;
  gs_htm_task *t;
  gs_htm_server **sl;
  double fl = 0, ms = 0, per = 0;
  char id[CID_LEN], tid[TASK_ID_LEN];

  sl = (gs_htm_server **)malloc(NUMSERV * sizeof(gs_htm_server *));

  for(i = 0; i < NUMSERV; i++) {
    gs_rand_id(id);
    sl[i] = gs_htm_new_empty_server(id, NULL);
  }

  srandom(0);

  for(i = 0; i < 1000; i++) {
    sprintf(tid, "%d", i);
    t = gs_htm_new_task(tid, 0, random() % 20);
    gs_htm_MP(sl, NUMSERV, t);
  }

  for(i = 0; i < NUMSERV; i++) {
    char printable_id[CID_LEN*2+1];

    s = sl[i];
    proxy_cid_to_str(printable_id, s->id);
    gs_htm_raz_simulation(s);
    gs_htm_simulate_server(s);
    printf("%s flow: %g, perturbation: %g , makespan: %g\n", printable_id, 
           gs_htm_flow(s), gs_htm_perturbation(s), gs_htm_makespan(s));
    fl += gs_htm_flow(s);
    per += gs_htm_perturbation(s);
    ms += gs_htm_makespan(s);
  }
  printf("Sumflow : %g, Sum perturbation : %g , Sum makespan : %g\n", fl, per,
         ms);

  return 0;
}

***/