/* METHUSELA: a simulator for evaluating migration policies
*      Author: Allen B. Downey, downey@cs.berkeley.edu
*      December 15, 1995
* 
* Copyright 1993 Regents of the University of California
* Permission to use, copy, modify, and distribute this
* software and its documentation for any purpose and without
* fee is hereby granted, provided that this copyright
* notice appears in all copies.  The University of California
* makes no representations about the suitability of this
* software for any purpose.  It is provided "as is" without
* express or implied warranty.
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <float.h>
#include <math.h>

extern srandom(int seed);
extern long random();

#define HOSTS 6                 /* number of hosts in simulated network */
#define LAMBDA_INTERVAL .1      /* used for arrival rate estimation */
#define CHECK_INTERVAL 1        /* time between system checks */
#define IMBALANCE 1.0           /* for random placement of jobs, this
				   parameter controls the skew of the
				   arrival process -- not currently used */
#define MAX_MIGS 3              /* maximum number of times a process can
				   be migrated */

#define RUNNING 0               /* process status */
#define DONE 1
#define MIGRATING 2

#define NEWPROC 0               /* event types */
#define MIGRATION 1
#define HOST_CHECK 2
#define SYS_CHECK 3
#define COUNT_CHECK 4

#define MAX_LOAD 20             /* used for summary statistics */

typedef struct proc {
  int pid;
  short status, times_migrated;
  short host, migrable;
  double age, dur, mem;
  char name[16];
  double load_seen;
  double time_started;
  double time_finished;
} Proc;

typedef struct event {
  double time;
  int type;
  Proc *proc;
  int host, dest;
  struct migration *migration;
  struct event *next;
} Event;

typedef struct list {
  Proc *proc;
  struct list *next;
} List;

typedef struct migration {
  int from, to;
  double start_load[HOSTS];
  double arr_rate[HOSTS];
  double pre_surv[HOSTS];
  double pre_arr[HOSTS];
  double mig_time;
} Migration;


/* GLOBAL VARIABLES */

Event *event_list;
List *array[HOSTS+1];
int prob[HOSTS];
int lambda[HOSTS][2];
double last_lambda;
double procs_assigned[HOSTS+1];
double load[HOSTS+1];
double incoming[HOSTS+1];
double load_sum[HOSTS+1];
int tprob = 0;
double Time;
double StartTime;
int lambda_flag = 0;
int procs_started = 0;
int procs_finished = 0;
FILE *loadfp = NULL;
FILE *migfp = NULL;

int mig_pol;
int place_pol;
int load_def;
double param1;
double param2;
double rexec_cost;
double fixed_cost;
double mem_trans_cost;
char *filename;

double total_load = 0.0;
double total_var = 0.0;
double total_time = 0.0;

/* DRANDOM : returns a random double in the range [0, 1] */

double drandom ()
{
  return (double) (random() & 0xffffff) / (double) 0xffffff;
}

/* CHOOSE_MEMORY_SIZE : returns a random double chosen from
   a distribution with shape 1/m and mean roughly 1.0 */

double choose_memory_size ()
{
  double x = 0.1 / drandom ();
  return x;
}

/* IS_MIGRABLE: takes the name of a process as an arg; returns 1 if
   the process is eligible for migration, 0 otherwise.

   Many of these are interactive jobs, and might not be good candidates
   for migration in a real system, but in this model, the behavior of
   these jobs is divorced from their real-world behavior. */

int is_migrable (char *name)
{
  switch (name[0]) {
  case 'c':
    if (!strncmp (name, "cc1", 3)) return 1;
    if (!strncmp (name, "co", 2)) return 1;
    break;
  case 'e':
    if (!strncmp (name, "emacs", 5)) return 1;
    break;
  case 'g':
    if (!strncmp (name, "gdb", 3)) return 1;
    break;
  case 'j':
    if (!strncmp (name, "jove", 4)) return 1;
    break;
  case 'l':
    if (!strncmp (name, "ln", 2)) return 1;
    if (!strncmp (name, "login", 5)) return 1;
    break;
  case 'm':
    if (!strncmp (name, "make", 4)) return 1;
    if (!strncmp (name, "micro", 5)) return 1;
    break;
  case 'n':
    if (!strncmp (name, "nachos", 6)) return 1;
    break;
  case 'o':
    if (!strncmp (name, "pine", 4)) return 1;
    break;
  case 'r':
    if (!strncmp (name, "rn", 2)) return 1;
    break;
  case 't':
    if (!strncmp (name, "trn", 3)) return 1;
    if (!strncmp (name, "tr", 2)) return 1;
    break;
  case 'v':
    if (!strncmp (name, "vi", 2)) return 1;
    break;
  default:
    return 0;
  }
  return 0;
}
  
/* MAKE_PROC: returns newly-minted proc structure.  Chooses a memory
   size for the new proc and sets its status to RUNNING */

Proc *make_proc (int host, double time, double dur, char *name)
{
  static pid = 0;

  Proc *new = (Proc *) malloc (sizeof (Proc));
  new->pid = pid++;
  new->status = RUNNING;
  new->times_migrated = 0;
  new->host = host;
  new->age = 0.0;
  new->dur = dur;
  strncpy (new->name, name, 15);
  new->name[15] = 0;
  new->migrable = is_migrable (name);
  new->mem = choose_memory_size ();
  new->time_started = time;
  new->time_finished = -1;
  return new;
}

/* MAKE_EVENT: host is the host the proc is assigned to.  For migrating
   procs, dest is the target host. */

Event *make_event (double time, int type, Proc *proc, int host, int dest)
{
  Event *new = (Event *) malloc (sizeof (Event));
  new->time = time;
  new->type = type;
  new->proc = proc;
  new->host = host;
  new->dest = dest;
  new->migration = NULL;
  return new;
}

/* MAKE_MIGRATION */

Migration *make_migration (int from, int to)
{
  Migration *new = (Migration *) malloc (sizeof (Migration));
  new->from = from;
  new->to = to;
  return new;
}  

/* ADD_EVENT returns 1 if the new item is at the end of the
   list; 0 otherwise */

int add_event (Event *e)
{
  Event *l;

  if (event_list == NULL || e->time < event_list->time) { 
    e->next = event_list;
    event_list = e;
    return 0;
  }

  for (l = event_list; l->next != NULL; l=l->next) {
    if (e->time < l->next->time) {
      e->next = l->next;
      l->next = e;
      return 0;
    }
  }
  l->next = e;
  e->next = NULL;
  return 1;
}

/* GET_NEXT_EVENT : removes the head from the event list and
   returns it; the head must be the elt in the list with the
   earliest time */

Event *get_next_event ()
{
  Event *e = event_list;
  if (e != NULL) {
    event_list = e->next;
  }
  return e;
}

/* GOOD NAME: Removes from the traces any processes which can
   be identified by name as shells.  This change has little effect
   on the results, since the behavior of shells is no different
   in this model than the behavior of any other processes.

   But it seems to make people happy when we say we removed shells
   from the traces, so here we are. */

int good_name (char *name)
{
  switch (name[0]) {
  case 'c':
    if (!strncmp (name, "csh", 3)) return 0;
    break;
  case 's':
    if (!strncmp (name, "sh", 2)) return 0;
    break;
  case 't':
    if (!strncmp (name, "tcsh", 4)) return 0;
    break;
  default:
    return 1;
  }
  return 1;
}

/* READ_PROC : the first time read_proc is called, it opens the
   trace file and sets the global clock to the start time of the
   first process */

Proc *read_proc()
{
  static FILE *fp = NULL;
  int host;
  double min, sec, time, dur;
  char name[100];

  if (fp == NULL) {
    fp = fopen (filename, "r");
    if (fp == NULL) { printf ("Couldn't open data file.\n"); exit (1); }
    do {
      if (fscanf (fp, "%lf %lf %d %lf %s",
		  &min, &sec, &host, &dur, name) == EOF) return NULL;
    } while (!good_name (name));
    StartTime = Time = min * 60.0 + sec;
  } else {
    do {
      if (fscanf (fp, "%lf %lf %d %lf %s",
		  &min, &sec, &host, &dur, name) == EOF) return NULL;
    } while (!good_name (name));
  }

  time = min * 60.0 + sec;
  return make_proc (host, time, dur, name);
}
		   
/* MAKE_LIST */

List *make_list (Proc *proc, List *next)
{
  List *new = (List *) malloc (sizeof (List));
  new->proc = proc;
  new->next = next;
  return new;
}

/* SORT_LOAD : sort the load array, putting the result into sload.
   The number of elements is HOSTS */

void sort_load (double load[], double sload[])
{
  int i, j;
  double t;

  for (i=0; i<HOSTS; i++) {
    sload[i] = load[i];
  }

  for (j=1; j<HOSTS; j++) {
    t = sload[j];
    i = j - 1;
    while (i >= 0 && sload[i] > t) {
      sload[i+1] = sload[i];
      i--;
    }
    sload[i+1] = t;
  }
}

/* PERCENTILE_LOAD: return the load of the machine at the ptile mark */

double percentile_load (double ptile)
{
  int index = (int) (HOSTS * ptile + 0.5);
  double sload[HOSTS];

  sort_load (load, sload);
  return sload[index];
}

/* MIN_LOAD_HOST: find the host with the minumum current load (including
   incoming jobs) */

int min_load_host ()
{
  int i;
  int winner = -1;
  double tload;
  double min_load = FLT_MAX;

  for (i=0; i<HOSTS; i++) {
    tload = load[i] + incoming[i];
    if (tload < min_load) {
      winner = i;
      min_load = tload;
    }
  }
  return winner;
}

/* RANDOM_MIN_LOAD_HOST : of the hosts with the minimum current load,
   including incoming jobs, choose one at random */

int random_min_load_host ()
{
  int host;
  int x, count;
  double tload;

  int min = min_load_host();
  double best = load[min] + incoming[min];
  
  /* find out how many minimally loaded hosts */
  count = 0;
  for (host=0; host<HOSTS; host++) {
    tload = load[host] + incoming[host];
    if (tload == best) count++;
  }

  /* choose one of the hosts randomly */
  x = random () % count;
  for (host=0; host<HOSTS; host++) {
    tload = load[host] + incoming[host];
    if (tload == best) {
      if (x-- == 0) break;
    }
  }
  assert (load[host] + incoming[host] == best);
  return host;
}

/* MAX_LOAD_HOST: find the host with the maximum current load */

int max_load_host ()
{
  int i;
  int winner = -1;
  double min_load = -1.0;

  for (i=0; i<HOSTS; i++) {
    if (load[i] > min_load) {
      winner = i;
      min_load = load[i];
    }
  }
  return winner;
}

/* CALC LOAD_SUM: sets the array load_sum to the total age of all
   processes on each host */

void calc_load_sum ()
{
  int i;
  List *l;

  for (i=0; i<HOSTS; i++) {
    load_sum[i] = 0.0;
    for (l = array[i]; l!=NULL; l=l->next) {
      load_sum[i] += l->proc->age;
    }
  }
}

/* MIN_TOTAL_AGE_HOST: find the host with the lowest total age */

int min_total_age_host ()
{
  int i;
  int winner = -1;
  double min_load = FLT_MAX;

  calc_load_sum ();

  for (i=0; i<HOSTS; i++) {
    if (load_sum[i] < min_load) {
      winner = i;
      min_load = load_sum[i];
    }
  }
  return winner;
}

/* PROB_SURVIVAL: probability that a process will survive an additional
dt seconds, given its age (assumes drop = 0.5) */

double prob_survival (double age, double dt)
{
  return age / (age + dt);
}

/* ARRIVAL_RATE : returns the recent arrival rate for a host */

int arrival_rate (int host)
{
  double dt = LAMBDA_INTERVAL + Time - last_lambda;
  int arrivals = lambda[host][0] + lambda[host][1];

  assert (dt >= LAMBDA_INTERVAL-.00001 && dt <= 2.0 * LAMBDA_INTERVAL);
  return (double) arrivals / dt;
}

/* EXPECT_ARRIVALS: expected number of arrivals during an interval dt
   which will survive until the end of the interval.  Depends on global
   time information and the array procs_assigned */

double expected_arrivals (int host, double dt)
{
  double rate = (double) lambda[host][lambda_flag];
  double arrivals = rate * dt;
  double load_plus = load[host] + 1.0;

  return .5 * (log (dt) - log (.5));
}

/* CALC_EXPECTED_LOAD: computes the expected load at a host dt seconds in
   the future */

double calc_expected_load (int host, double dt)
{
  double eload = 0.0;
  List *l;

  if (load[host] == 0.0) return 0.0;

  for (l=array[host]; l!=NULL; l=l->next) {
    if (l->proc->status == RUNNING) {
      eload += prob_survival (l->proc->age, dt / load[host]);
    }
  }
  return eload;
}

/* MIN_EXPECTED_LOAD_HOST: the host with minimal expected load dt seconds
   in the future */

int min_expected_load_host (double dt)
{
  int i, winner = -1;
  double eload;
  double min_eload = FLT_MAX;

  for (i=0; i<HOSTS; i++) {
    eload = calc_expected_load (i, dt);
    /* don't forget to add expected arrivals */
    if (eload < min_eload) {
      winner = i;
      min_eload = eload;
    }
  }
  return winner;
}

/* CALC_STATS: find the mean and std of an array */

void calc_stats (double a[], int n, double *mean, double *std)
{
  int i;
  double sum = 0.0;
  double sumsq = 0.0;

  for (i=0; i<n; i++) {
    sum += a[i];
    sumsq += a[i] * a[i];
  }
  *mean = sum / n;
  *std = sqrt (sumsq / n - (*mean) * (*mean));
}

/* CHECK_LOAD: check the variance in the load of the hosts, update
   summary statistics and print results, if required.  This proc
   should be called immediately before any action that affects the
   load in the system: process creation, migration, and termination */

void check_load (double time)
{
  double mean, std;
  static double last_time = -1.0;
  static FILE *avgfp = NULL;
  double dt;

  if (last_time == -1) last_time = time;
  if (time == last_time) return;
  dt = time - last_time;
  last_time = time;
  assert (dt > 0.0);

  calc_stats (load, HOSTS, &mean, &std);
  total_load += dt * mean;
  total_var += dt * std;
  total_time += dt;

#ifdef DETAILS
  if (avgfp == NULL) {
    avgfp = fopen ("load_avg", "w");
  }

  fprintf (avgfp, "%lf\t%.2lf\n", time, mean);
#endif
}

/* ASSIGN_PROC: adds a proc to a host's run queue and updates the global
   load, procs_started, and procs_assigned variables */

void assign_proc (Proc *proc, int host)
{
  assert (host != HOSTS || proc->status == DONE);
  array[host] = make_list (proc, array[host]);

  load[host] += 1.0;
}

/* REMOVE_PROC: removes a procs from a host's run queue and updates
   global info */

int remove_proc (Proc *proc, int host, double time) 
{
  List *i = array[host];

  load[host] -= 1.0;
  assert (load[host] >= 0.0);

  if (i->proc == proc) {
    array[host] = i->next;
    return 0;
  }

  for (; i!=NULL; i=i->next) {
    if (i->next == NULL) return 1;
    if (i->next->proc == proc) {
      i->next = i->next->next;
      return 0;
    }
  }
  assert (0);
  return 1;
}

/* CHOOSE_A_HOST: picks a host according to the distribution 'prob' */

int choose_a_host ()
{
  int i, tot=0;
  int n = random() % tprob;

  for (i=0; i<HOSTS; i++) {
    tot += prob[i];
    if (tot > n) return i;
  }
  assert (0);
  return -1;
}

/* GENERATE_EVENTS : establishes the invariant that the last event
   on the event queue is a NEW_PROC event.  Returns 1 if there are no
   more procs in the file; 0 otherwise. */

int generate_events ()
{
  Proc *proc;
  Event* event;
  int host;
  double time;

  do {
    proc = read_proc ();
    if (proc == NULL) return 1;
    event = make_event (proc->time_started, NEWPROC, proc, -1, -1);
  } while (add_event (event) == 0);

  time = proc->time_started;

  do {
    proc = read_proc ();
    if (proc == NULL) return 1;
    add_event (make_event (proc->time_started, NEWPROC, proc, -1, -1));
  } while (proc->time_started == time);
  return 0;
}

/* IS_DONE: returns 1 if the age of the process is nearly equal to or
   greater than its duration */

int is_done (Proc *proc)
{
  return ((proc->dur - proc->age) < .005);
}

/* FIND_FIRST_DECEDENT: of all active processes, returns
   the time remaining on the process closest to dying */

Proc *find_first_decedent (int *host)
{
  int i = 0;
  List *l;
  Proc *proc;
  Proc *winner = NULL;
  double rem_time;
  double min_time = FLT_MAX;

  for (i=0; i<HOSTS; i++) {
    for (l = array[i]; l != NULL; l = l->next) {
      proc = l->proc;
      if (proc->status != RUNNING) continue;

      rem_time = (proc->dur - proc->age) * load[i];
      if (rem_time < min_time) {
	winner = proc;
	*host = i;
	min_time = rem_time;
      }
    }
  }
  assert (min_time > 0.0);
  return winner;
}

/* UPDATE_PROCS: age each process on a give host by share seconds; if
   the process finishes, remove it from the queue and put it on the
   dead process queue */

int update_procs (double dt, double time)
{
  int i, dead = 0;
  List *l;
  Proc *proc;
  double share;

  for (i=0; i<HOSTS; i++) {
    share = dt / load[i];
    for (l = array[i]; l != NULL; l = l->next) {
      proc = l->proc;
      if (proc->status != RUNNING) continue;
      proc->age += share;

      if (is_done (proc)) {
	assert (proc->age - proc->dur < .01);

	proc->status = DONE;
	proc->time_finished = time;
	assert (proc->time_finished > proc->time_started);

	check_load (time);
	remove_proc (proc, i, time);
	assign_proc (proc, HOSTS);
	dead++;
	procs_finished++;
      }
    }
  }
  return dead;
}

/* AGE_EXISTING_PROCS: find the time since the last update and divide
   it, if necessary, into half-second chunks.  Find the time share
   allocated to each process and call update_procs */

void age_existing_procs ()
{
  int host, dead;
  Proc *proc;
  double dt, share;
  static double last_time = -1.0;
  double time;

  if (last_time == -1.0) last_time = Time;
  if (Time == last_time) return;
  time = last_time;

  while (1) {
    proc = find_first_decedent (&host);
    if (proc == NULL) goto end;

    dt = (proc->dur - proc->age) * load[host];
    if (dt > Time-time) break;

    time += dt;
    dead = update_procs (dt, time);
    assert (dead >= 1);
  }

  if (time == Time) goto end;
  dt = Time - time;
  assert (dt > 0.0);

  /* all remaining procs will survive until Time */
  dead = update_procs (dt, Time);
 end:
  last_time = Time;
}


/* SIM_INIT: initializes the distribution of processes onto hosts and
   seeds the random number generator */

void sim_init ()
{
  int i;

  srandom (23);

  for (i=0; i<HOSTS; i++) {
    array[i] = NULL;
    prob[i] = (int) 100.0 * pow (2.0, -i * IMBALANCE);
    tprob += prob[i];
    load[i] = 0.0;
    incoming[i] = 0.0;
    lambda[i][0] = 0;
    procs_assigned[i] = 0.0;
  }
  array[HOSTS] = NULL;
  procs_assigned[HOSTS] = 0.0;

  /* put a few events in the run queue, and start the clock */
  generate_events ();

  if (mig_pol == 3) {
    add_event (make_event (StartTime+0.31415926, SYS_CHECK, NULL, -1, -1));
  }

/*  add_event (make_event (StartTime+0.01, COUNT_CHECK, NULL, -1, -1)); */
  generate_events ();

  /* start the clock on the process ager */
  age_existing_procs ();
}

double migration_cost (Proc *proc)
{
  if (proc->age == 0.0) {
    return rexec_cost;
  } else {
    return fixed_cost + mem_trans_cost * proc->mem;
  }
}

/* OLD_ENOUGH: is the proc eligible for migration? */

int old_enough (Proc *proc, int from, int to)
{
  /* if param2 is negative, use analytic age condition; ow,
     use parametric age condition */

  if (param2 < 0) {
    return (proc->age >= migration_cost (proc) / (load[from] - load[to] - 1));
  } else {
    return (proc->age >= param2 * migration_cost (proc));
  }
}

/* FIND_BEST_MIGRANT: of the processes in a host's run queue, choose
   the best one to migrate */

Proc *find_best_migrant (int from, int to)
{
  List *l;
  Proc *proc;
  Proc *winner = NULL;
  double score;
  double max = 0.0;

  for (l = array[from]; l!=NULL; l=l->next) {
    proc = l->proc;
    if (proc->status != RUNNING) continue;
    if (proc->times_migrated > MAX_MIGS) continue;
    if (!old_enough (proc, from, to)) continue;

    score = proc->age / migration_cost (proc);
    if (score > max) {
      winner = proc;
      max = score;
    }
  }
  return winner;
}

/* HIGH_LOAD: returns 1 if the given host has a high load, whatever
   that means */

int high_load (host)
{
  double mean, std;

  if (load_def == 0) {
    /* only threshold; no global info */
    assert (0);
    calc_stats (load, HOSTS, &mean, &std);
    return (load[host] > mean + param1 * std);
  } else {
    return (load[host] >= param1);
  }
}

/* CHOOSE_TARGET_HOST */

choose_target_host ()
{
  int to = -1;

  if (place_pol == 0) {
    to = random_min_load_host ();
  } else if (place_pol == 1) {
    assert (0);
    to = min_total_age_host ();
  } else {
    /* use expected future loads */
    assert (0);
  }
  assert (to >= 0 && to < HOSTS);
  return to;
}

/* MIGRATE_PROCESS: add an event to the queue such that proc
   gets migrated */

migrate_process (Proc *proc, int from, int to)
{
  double cost;
  Event *event;

  cost = migration_cost (proc);
  assert (proc->status == RUNNING);
  assert (mig_pol > 1 || Time == proc->time_started);
  proc->status = MIGRATING;
  incoming[to]++;

  event = make_event (Time+cost, MIGRATION, proc, from, to);
#ifdef DETAILS
  {
    int i;

    event->migration = make_migration (from, to);

    for (i=0; i<HOSTS; i++) {
      event->migration->start_load[i] = load[i];
/* TO REACTIVEATE arrival_rate, uncomment these lines, and restart
   the arrival_checks */
/*      event->migration->arr_rate[i] = arrival_rate (i);   */
      event->migration->arr_rate[i] = 0.0;
      event->migration->pre_surv[i] = calc_expected_load (i, cost);
      event->migration->pre_arr[i] = expected_arrivals (i, cost);
    }
    event->migration->mig_time = cost;
  }
#endif

  add_event (event);
  generate_events ();
}

int good_transfer (int from, int to)
{
  double tload_from = load[from] + incoming[from];
  double tload_to = load[to] + incoming[to];

  return (tload_from - tload_to > 2);
}

/* PERFORM_LOAD_BALANCING: the optional argument is the event that
   preceded the load balancing step.  The effect depends on the strategy
   Possible side effects: if a migration occurs, the status of a process
   is changed to MIGRATING, and an event is added to the event queue.
   There are no other side effects and e is unmodified */

void perform_load_balancing (Event *e)
{
  int to;
  Proc *migrant;

  if (mig_pol == 0 || mig_pol == 3) return;
  if (!high_load (e->host)) return;

  to = choose_target_host ();

  switch (mig_pol) {
  case -1:
    migrate_process (e->proc, e->host, to);
    break;
  case 1:
    if (e->proc->migrable && good_transfer (e->host, to)) {
      migrate_process (e->proc, e->host, to);
    }
    break;
  case 2:
    while (1) {
      migrant = find_best_migrant (e->host, to);
      if (migrant == NULL) break;
      migrate_process (migrant, e->host, to);

      to = choose_target_host ();
      break;   /* remove this line to migrate more than one job at a time */
    }
    break;
  case 4:
    add_event (make_event (Time+CHECK_INTERVAL, HOST_CHECK, NULL, e->host, 0));
    generate_events ();
    break;
  default:
    assert (0);
  }
  return;
}

/* HANDLE_NEW_PROC: handle a new process event.  Assign the process
   to a randomly chosen host and perform a load-balancing step */

void handle_new_proc (Event *e)
{
  Proc *migrant;
  int dest;
  double cost;
  double mean, std;

  e->host = e->proc->host;

  procs_started++;
  procs_assigned[e->host] += 1.0;
  lambda[e->host][lambda_flag]++;
  e->proc->load_seen = load[e->host];

  /* do load balancing before assigning the new proc to the host
     so that decisions are based on a priori load info */
  perform_load_balancing (e);
  check_load (Time);
  assign_proc (e->proc, e->host);
}

/* HANDLE_MIGRATION: handle a migration event */

void handle_migration (Event *e)
{
#ifdef DEBUG
  printf ("Migrating from %d to %d, dur=%.2lf\n",
	  e->host, e->dest, e->proc->dur);
#endif

  e->proc->times_migrated++;

  check_load (Time);
  remove_proc (e->proc, e->host, Time);

  assert (e->proc->status == MIGRATING);
  e->proc->status = RUNNING;
  incoming[e->dest]--;

#ifdef DETAILS
  {
    int host, j, min_host;
    Migration *mig = e->migration;
    assert (mig != NULL);

    min_host = min_load_host ();

    if (loadfp == NULL) {
      loadfp = fopen ("load_info", "w");
      migfp = fopen ("mig_info", "w");
    }

    fprintf (migfp, "%.0lf\t%.0lf\t%.0lf\t%.0lf\t%.0lf\t%.2lf\t%.2lf\n",
	     mig->start_load[e->host], mig->start_load[e->dest],
	     load[e->host], load[e->dest],
	     load[min_host], e->proc->age, e->proc->dur);

    for (host=0; host<HOSTS; host++) {
      fprintf (loadfp, "%.0lf\t%.2lf\t%.3lf\t%.3lf\t%.2lf\t",
	       mig->start_load[host], mig->arr_rate[host],
	       mig->pre_surv[host], mig->pre_arr[host]);
      fprintf (loadfp, "%.2lf, %.0lf\n", mig->mig_time, load[host]);
    }
    free (mig);
  }
#endif
  assign_proc (e->proc, e->dest);
}

/* HANDLE_HOST_CHECK */

void handle_host_check (Event *e)
{
  int to;
  int from = e->host;
  Proc *migrant;

  if (high_load (from)) {
    to = choose_target_host ();
    if (high_load (to)) return;

    migrant = find_best_migrant (from, to);
    if (migrant == NULL) return;
    
    migrate_process (migrant, from, to);
  }
}

/* HANDLE_SYS_CHECK */

void handle_sys_check (Event *e)
{
  int from, to;
  Proc *migrant;
  static double dt = 1.0;

  from = max_load_host ();
  if (high_load (from)) {
    to = choose_target_host ();
    if (high_load (to)) return;

    migrant = find_best_migrant (from, to);
    if (migrant == NULL) return;
    
    migrate_process (migrant, from, to);
  }

  if (event_list != NULL) {
    add_event (make_event (Time+CHECK_INTERVAL, SYS_CHECK, NULL, -1, -1));
    generate_events ();
  }
}

/* HANDLE_COUNT_CHECK */

void handle_count_check (Event *e)
{
  int i;
  lambda_flag = lambda_flag ^ 1;
  
  for (i=0; i<HOSTS; i++) {
    lambda[i][lambda_flag] = 0;
  }
  last_lambda = Time;

  if (event_list != NULL) {
    add_event (make_event (Time+LAMBDA_INTERVAL, COUNT_CHECK, NULL, -1, -1));
    generate_events ();
  }
}

/* PRINT_STATS: at the end of the run, print all the summary statistics */

void print_stats ()
{
  List *l;
  Proc *proc;
  int i;
  int big_slowdown[5];
  double loads_seen[MAX_LOAD+1];
  double wtime;
  double slowdown;
  double sum_slowdown = 0.0;
  double sum_sq_slowdown = 0.0;
  double avg_slowdown, std_slowdown;
  double mean, std;

  double total_dur = 0.0;
  double total_dur_migrants = 0.0;

  int total_migrations = 0;
  int total_migrants = 0;
  int total_migrable = 0;

  FILE *detfp;

  for (i=0; i<5; i++) {
    big_slowdown[i] = 0;
  }

  for (i=0; i<= MAX_LOAD; i++) {
    loads_seen[i] = 0.0;
  }

#ifdef DETAILS
  detfp = fopen ("proc_info", "w");
#endif

  for (l = array[HOSTS]; l != NULL; l = l->next) {
    proc = l->proc;
    assert (proc->status == DONE);
   
    if (proc->load_seen >= MAX_LOAD) {
      loads_seen[MAX_LOAD] += 1.0;
    } else {
      loads_seen[(int) proc->load_seen] += 1.0;
    }

    if (proc->migrable) total_migrable++;

    if (proc->times_migrated > 0) {
      total_migrants ++;
      total_migrations += proc->times_migrated;
      total_dur_migrants += proc->dur;
    }
    total_dur += proc->dur;

    wtime = proc->time_finished - proc->time_started;
    slowdown = wtime / proc->dur;
    sum_slowdown += slowdown;
    sum_sq_slowdown += slowdown * slowdown;

    if (slowdown >= 3.0) big_slowdown[0]++;
    if (slowdown >= 5.0) big_slowdown[1]++;
    if (slowdown >= 7.0) big_slowdown[2]++;
    if (slowdown >= 9.0) big_slowdown[3]++;
    if (slowdown >= 11.0) big_slowdown[4]++;

#ifdef DETAILS
    fprintf (detfp, "%.3lf\t%.2lf\t%.0lf\t%d\t%s\n", proc->dur, slowdown,
	     proc->load_seen, proc->times_migrated, proc->name);
#endif

  }

#ifdef DETAILS
  fclose (detfp);
#endif

  avg_slowdown = sum_slowdown / procs_finished;
  std_slowdown = sqrt (sum_sq_slowdown / procs_finished -
		       avg_slowdown * avg_slowdown);

  printf ("%d\t%d\t", big_slowdown[0], big_slowdown[1]);

  printf ("%.4lf\t%.4lf\t", avg_slowdown, std_slowdown);

  printf ("%.2lf\t%.2lf\t%d\t%d\t",
	  total_dur / procs_finished, 
	  total_dur_migrants/total_migrants,
	  total_migrants,
	  total_migrations);
  printf ("%.2lf\t%.2lf\t", total_load / total_time, total_var / total_time);

  calc_stats (procs_assigned, HOSTS, &mean, &std);
  printf ("%.2lf\n", std);
}  

int main (int argc, char *argv[])
{
  double std, mean;
  Event *e;

  if (argc == 10) {
    filename = argv[1];
    mig_pol = atoi (argv[2]);
    place_pol = atoi (argv[3]);
    load_def = atoi (argv[4]);
    param1 = atof (argv[5]);
    param2 = atof (argv[6]);
    rexec_cost = atof (argv[7]);
    fixed_cost = atof (argv[8]);
    mem_trans_cost = atof (argv[9]);
  } else {
    printf (
"Wrong number of args: trace mig_pol place_pol load_def p1 p2 rc fc mtc.\n");
    exit (1);
  }

  sim_init ();

  for ( ; ; ) {
    e = get_next_event ();
    if (e == NULL) {
      if (generate_events ()) break;
      else continue;
    }
    Time = e->time;

    age_existing_procs ();

    switch (e->type) {
    case NEWPROC:
      handle_new_proc (e);
      break;
    case MIGRATION:
      handle_migration (e);
      break;
    case HOST_CHECK:
      handle_host_check (e);
      break;
    case SYS_CHECK:
      handle_sys_check (e);
      break;
    case COUNT_CHECK:
      handle_count_check (e);
      break;
    default:
      assert (0);
    }
    free (e);
  }

  printf ("%s\t%d %d %d   %.2f\t%.2f\t", filename, mig_pol, place_pol,
	  load_def, param1, param2);
  printf ("%.2f\t%.2f\t%.2f\t", rexec_cost, fixed_cost, mem_trans_cost);

  printf ("%d\t", procs_finished);

  print_stats ();

  return 0;
}