#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"

Include dependency graph for gs_htm.c:

Defines
#define	fl_eq(a, b) (fabs((a)-(b)) < 0.0001)
Functions
void	dump_all_tasks (gs_htm_server *s)
static int	gs_htm_server_compare_function (const void p1, const void p2)
	Comparison function for use in sorting.
void	gs_htm_display_server (gs_htm_server *s)
double	gs_htm_first_event (gs_htm_server *s)
double	gs_htm_next_event (gs_htm_server *s, double start)
void	gs_htm_simulate_server (gs_htm_server *s)
gs_htm_task *	gs_htm_new_task (char *id, double start, double duration)
gs_htm_task *	gs_htm_finished_task (char *id, double start, double end)
gs_htm_server *	gs_htm_new_empty_server (char id, gs_server_t sptr)
void	gs_htm_add_task (gs_htm_server s, gs_htm_task new_t)
double	gs_htm_perturbation (gs_htm_server *s)
double	gs_htm_makespan (gs_htm_server *s)
double	gs_htm_flow (gs_htm_server *s)
double	gs_htm_length (gs_htm_server *s, double date)
gs_htm_task *	gs_htm_clone_task (gs_htm_task *t)
void	gs_htm_add_task_last (gs_htm_server s, gs_htm_task t)
gs_htm_server *	gs_htm_clone_server (gs_htm_server *s)
void	gs_htm_raz_simulation (gs_htm_server *s)
void	gs_htm_remove_task (gs_htm_server s, char id)
int	gs_htm_ML (gs_htm_server *sl, int n, gs_htm_task t)
int	gs_htm_MSF (gs_htm_server *sl, int n, gs_htm_task t)
int	gs_htm_HMCT (gs_htm_server *sl, int n, gs_htm_task t)
int	gs_htm_MP (gs_htm_server *sl, int n, gs_htm_task t)
void	gs_rand_id (char id[CID_LEN])

Define Documentation

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

Definition at line 13 of file gs_htm.c.

Function Documentation

void dump_all_tasks ( gs_htm_server * s )

Definition at line 533 of file gs_htm.c.

{
  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");
}

void gs_htm_add_task	(	gs_htm_server *	s,
		gs_htm_task *	new_t
	)

Definition at line 261 of file gs_htm.c.

{
  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;
  }
}

Here is the caller graph for this function:

void gs_htm_add_task_last	(	gs_htm_server *	s,
		gs_htm_task *	t
	)

Definition at line 362 of file gs_htm.c.

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

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

Here is the caller graph for this function:

gs_htm_server* gs_htm_clone_server ( gs_htm_server * s )

Definition at line 375 of file gs_htm.c.

{
  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;
}

Here is the call graph for this function:

gs_htm_task* gs_htm_clone_task ( gs_htm_task * t )

Definition at line 345 of file gs_htm.c.

{
  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;
}

Here is the caller graph for this function:

void gs_htm_display_server ( gs_htm_server * s )

Definition at line 45 of file gs_htm.c.

{
  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);
  }
}

gs_htm_task* gs_htm_finished_task	(	char *	id,
		double	start,
		double	end
	)

Definition at line 228 of file gs_htm.c.

{
  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;
}

double gs_htm_first_event ( gs_htm_server * s )

Definition at line 58 of file gs_htm.c.

{
  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;
  }
}

Here is the caller graph for this function:

double gs_htm_flow ( gs_htm_server * s )

Definition at line 320 of file gs_htm.c.

{
  gs_htm_task *t;

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

  return res;
}

Here is the caller graph for this function:

int gs_htm_HMCT	(	gs_htm_server **	sl,
		int	n,
		gs_htm_task *	t
	)

Definition at line 496 of file gs_htm.c.

{
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

double gs_htm_length	(	gs_htm_server *	s,
		double	date
	)

Definition at line 332 of file gs_htm.c.

{
  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;
}

Here is the caller graph for this function:

double gs_htm_makespan ( gs_htm_server * s )

Definition at line 307 of file gs_htm.c.

{
  gs_htm_task *t;

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

  return res;
}

int gs_htm_ML	(	gs_htm_server **	sl,
		int	n,
		gs_htm_task *	t
	)

Definition at line 422 of file gs_htm.c.

{
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int gs_htm_MP	(	gs_htm_server **	sl,
		int	n,
		gs_htm_task *	t
	)

Definition at line 552 of file gs_htm.c.

{
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int gs_htm_MSF	(	gs_htm_server **	sl,
		int	n,
		gs_htm_task *	t
	)

Definition at line 459 of file gs_htm.c.

{
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

gs_htm_server* gs_htm_new_empty_server	(	char *	id,
		gs_server_t *	sptr
	)

Definition at line 246 of file gs_htm.c.

{
  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;
}

Here is the caller graph for this function:

gs_htm_task* gs_htm_new_task	(	char *	id,
		double	start,
		double	duration
	)

Definition at line 209 of file gs_htm.c.

{
  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;
}

Here is the caller graph for this function:

double gs_htm_next_event	(	gs_htm_server *	s,
		double	start
	)

Definition at line 87 of file gs_htm.c.

{
  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;
}

Here is the caller graph for this function:

double gs_htm_perturbation ( gs_htm_server * s )

Definition at line 295 of file gs_htm.c.

{
  gs_htm_task *t;
  double res = 0;

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

  return res;
}

Here is the caller graph for this function:

void gs_htm_raz_simulation ( gs_htm_server * s )

Definition at line 389 of file gs_htm.c.

{
  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;
  }
}

Here is the caller graph for this function:

void gs_htm_remove_task	(	gs_htm_server *	s,
		char *	id
	)

Definition at line 402 of file gs_htm.c.

{
  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;
  }
}

Here is the caller graph for this function:

static int gs_htm_server_compare_function	(	const void *	p1,
		const void *	p2
	)			`[static]`

Comparison function for use in sorting.

This function is used by quicksort.

Parameters:

	p1	-- A pointer to a server structure s1
	p2	-- A pointer to a server structure s2

Returns:: 1 if s1->metric > s2->metric, -1 if s1->metric < s2->metric, 0 otherwise

Definition at line 27 of file gs_htm.c.

{
  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;
}

Here is the caller graph for this function:

void gs_htm_simulate_server ( gs_htm_server * s )

Definition at line 193 of file gs_htm.c.

{
  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;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void gs_rand_id ( char id[CID_LEN] )

Definition at line 589 of file gs_htm.c.

{
  int i;

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

gs_htm.c File Reference

Defines

Functions

Define Documentation

Function Documentation