syssim_driver2.c

目前最精确的磁盘模拟器的第3版

    fprintf(stderr,"ERROR:  Could not malloc memory for free_bandwitdh_stat\n");
    exit(-1);
  }
  
  stat_initialize(statfile, FREE_BANDWIDTH_STAT, free_bandwidth_stat);

  extra_seek_stat = (statgen *)malloc(sizeof(statgen));
  if(extra_seek_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for free_bandwitdh_stat\n");
    exit(-1);
  }
  
  stat_initialize(statfile,EXTRA_SEEK_STAT, extra_seek_stat);  

  total_latency_stat_inst = (statgen *)malloc(sizeof(statgen));
  if(total_latency_stat_inst == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for total_latency_stat_inst\n");
    exit(-1);
  }

  stat_initialize(statfile, LATENCY_STAT, total_latency_stat_inst);

  free_bandwidth_stat_inst = (statgen *)malloc(sizeof(statgen));
  if(free_bandwidth_stat_inst == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for free_bandwitdh_stat_inst\n");
    exit(-1);
  }
  
  stat_initialize(statfile, FREE_BANDWIDTH_STAT, free_bandwidth_stat_inst);

  extra_seek_stat_inst = (statgen *)malloc(sizeof(statgen));
  if(extra_seek_stat_inst == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for free_bandwitdh_stat_inst\n");
    exit(-1);
  }
  
  stat_initialize(statfile,EXTRA_SEEK_STAT, extra_seek_stat_inst);  

  for(i=0;i<(int)ceil(sim_length/(float)PERIOD);i++){
    latency_stat[i] = (statgen *)malloc(sizeof(statgen));
    if(latency_stat[i] == NULL){
      fprintf(stderr,"ERROR:  Could not malloc memory for latency_stat\n");
      exit(-1);
    }
    seek_dist_stat[i] = (statgen *)malloc(sizeof(statgen));
    if(seek_dist_stat[i] == NULL){
      fprintf(stderr,"ERROR:  Could not malloc memory for seek_dist_stat\n");
      exit(-1);
    }
    free_pop_stat[i] = (statgen *)malloc(sizeof(statgen));
    if(free_pop_stat[i] == NULL){
      fprintf(stderr,"ERROR:  Could not malloc memory for free_pop_stat\n");
      exit(-1);
    }

    free_cyl_pop_stat[i] = (statgen *)malloc(sizeof(statgen));
    if(free_cyl_pop_stat[i] == NULL){
      fprintf(stderr,"ERROR:  Could not malloc memory for free_cyl_pop_stat\n");
      exit(-1);
    }

    free_cyl_stat[i] = (statgen *)malloc(sizeof(statgen));
    if(free_cyl_stat[i] == NULL){
      fprintf(stderr,"ERROR:  Could not malloc memory for free_cyl_stat\n");
      exit(-1);
    }
    
    free_count_stat[i] = (statgen *)malloc(sizeof(statgen));
    if(free_count_stat[i] == NULL){
      fprintf(stderr,"ERROR:  Could not malloc memory for free_count_stat\n");
      exit(-1);
    }
    
    free_demand_count_stat[i] = (statgen *)malloc(sizeof(statgen));
    if(free_count_stat[i] == NULL){
      fprintf(stderr,"ERROR:  Could not malloc memory for free_demand_count_stat\n");
      exit(-1);
    }
    
    take_free_time_stat[i] = (statgen *)malloc(sizeof(statgen));
    if(take_free_time_stat[i] == NULL){
      fprintf(stderr,"ERROR:  Could not malloc memory for take_free_time_stat\n");
      exit(-1);
    }
    
    stat_initialize(statfile, LATENCY_STAT, latency_stat[i]);
    stat_initialize(statfile, SEEK_DIST_STAT, seek_dist_stat[i]);
    stat_initialize(statfile, FREE_POP_STAT, free_pop_stat[i]);
    stat_initialize(statfile, FREE_CYL_POP_STAT, free_cyl_pop_stat[i]);
    stat_initialize(statfile, FREE_CYL_STAT, free_cyl_stat[i]);
    stat_initialize(statfile, FREE_COUNT_STAT, free_count_stat[i]);
    stat_initialize(statfile, FREE_DEMAND_COUNT_STAT, free_demand_count_stat[i]);
    stat_initialize(statfile, TAKE_FREE_TIME_STAT, take_free_time_stat[i]);
  }

  //  if(algorithm ==  1 || algorithm ==  2 || algorithm ==  3){
  if(1){
    for(i=0;i<numsurfaces;i++){
      for(j=0;j<ANGLE_ENTRIES;j++){
	for(k=0;k<ndrives;k++){
	  free_blocks[k] = 0;
	}
      }
    }
  }
  
#ifdef DEBUG_MEMORY
  fprintf(stderr,"allocated %d bytes\n",6144 * 216 * sizeof(node_t));
  fprintf(stderr,"sizeof(cyl_node_t) = %d sizeof(node_t) = %d\n",sizeof(cyl_node_t),sizeof(node_t));
#endif /* DEBUG_MEMORY */

  //  init_locations();

  for(j=0;j<ndrives;j++) {
    nrequests[j] = 0;
  }
  for(j=0;j<ndrives;j++) {
    for(i=0;i<numblocks;i++) {
      map_blocknum(j,i,&cyl,&sector,&surface);
      free_block_request(cyl, sector,((float)sector/(float)sectorspercyl[cyl] * (float)MAX_ANGLE),surface,j);
    }
  }
}


void free_block_request(unsigned short cyl, unsigned short sector,  float angle, unsigned short surface, int devno){
  BITMAP_SET(devno,cyl,surface,sector);
  free_count[devno][cyl]++;
  free_count_track[devno][cyl][surface]++;
}

static long max_time = 0;
static float max_percent = 0.0;
static int max_cyl = 0;

void pickup_free_blocks(unsigned short cylinder, 
			unsigned short surface,
			int start_sector,
			int finish_sector,
			unsigned short source_cyl,
			unsigned short dest_cyl,
			unsigned short devno){
  int i;
  int count=0;
  unsigned short top_cyl,bottom_cyl;
  float extra_seek=0.0;
  int min_cyl = abs(source_cyl - cylinder);

  if(min_cyl > abs(dest_cyl - cylinder)){
    min_cyl = abs(dest_cyl - cylinder);
  }

  if(min_cyl > max_cyl){
    max_cyl = min_cyl;
  }

  if(source_cyl < dest_cyl){
    bottom_cyl = source_cyl;
    top_cyl = dest_cyl;
  }else{
    bottom_cyl = dest_cyl;
    top_cyl = source_cyl;
  }

  for(i=0;i<sectorspercyl[cylinder];i++){
    if(finish_sector < start_sector){
      if(i >= start_sector || i < finish_sector){
	if(BITMAP_CHECK(devno,cylinder,surface,i)){
	  free_count[devno][cylinder]--;
	  free_count_track[devno][cylinder][surface]--;
	  free_blocks[devno]++;
	  BITMAP_CLEAR(devno,cylinder,surface,i);
	  touchmap[devno][surface][cylinder].max = now;
	  touchmap[devno][surface][cylinder].touch = (now/
						      (float)
						      sectorspercyl[cylinder]);
	  touchmap[devno][surface][cylinder].squared = (now * now /
						      (float)
						      sectorspercyl[cylinder]);
	  count++;
	}
      }
    }else if(finish_sector > start_sector){
      if(i >= start_sector && i < finish_sector){
	if(BITMAP_CHECK(devno,cylinder,surface,i)){
	  free_count[devno][cylinder]--;
	  free_count_track[devno][cylinder][surface]--;
	  free_blocks[devno]++;
	  BITMAP_CLEAR(devno,cylinder,surface,i);
	  touchmap[devno][surface][cylinder].max = now;
	  touchmap[devno][surface][cylinder].touch = (now/
						      (float)
						      sectorspercyl[cylinder]);
	  touchmap[devno][surface][cylinder].squared = (now * now /
						      (float)
						      sectorspercyl[cylinder]);
	  count++;
	}
      }	  
    } else {
      if(BITMAP_CHECK(devno,cylinder,surface,i)){
	free_count[devno][cylinder]--;
	free_count_track[devno][cylinder][surface]--;
	free_blocks[devno]++;
	BITMAP_CLEAR(devno,cylinder,surface,i);
	touchmap[devno][surface][cylinder].max = now;
	touchmap[devno][surface][cylinder].touch = (now/
						    (float)
						    sectorspercyl[cylinder]);
	touchmap[devno][surface][cylinder].squared = (now * now /
						      (float)
						      sectorspercyl[cylinder]);
	count++;
      }
    }
  }
  if(count != 0){
    if(count > 1){
      //      fprintf(stderr,"picked up %d blocks from %d source %d dest %d time %f\n",count,cylinder,source_cyl,dest_cyl,(float)count/(float)sectorspercyl[cylinder]*oneRotation);
      //  fprintf(stderr,"pick finish sec %d start sec %d %d\n",finish_sector,start_sector,sectorspercyl[cylinder]);
    }
    free_bandwidth += ((float)count / (float) sectorspercyl[cylinder] * 
		       oneRotation);
    extra_seek = (seek_angle[abs(source_cyl-cylinder)] +
		  seek_angle[abs(dest_cyl-cylinder)] -
		  seek_angle[abs(source_cyl-dest_cyl)])*oneRotation;
    if(extra_seek < 0.0){
      extra_seek = 0.0;
    }
    stat_update(extra_seek_stat, extra_seek);
    stat_update(extra_seek_stat_inst, extra_seek);
    if(cylinder > top_cyl || cylinder < bottom_cyl){
      outside[devno]++;
    }else if(cylinder == source_cyl){
      sourcecyl[devno]++;
    }else if(cylinder == dest_cyl){
      destcyl[devno]++;
    }else{
      inside[devno]++;	
    }
  }else{
    zero[devno]++;
  }
}

typedef struct alg_args_s{
  float rotate_angle;
  unsigned short devno;
  unsigned short source_cyl;
  float source_angle;
  unsigned short dest_cyl;
  float dest_angle;
  unsigned short source_surface;
  unsigned short dest_surface;
  unsigned short target_cyl;
  unsigned int inputflags;
  unsigned int outputflags;
  unsigned short surface;
  unsigned short start_sector;
  float new_angle;
  unsigned short best_cyl;
  unsigned short finish_sector;
} alg_args_t;

inline void location_info(float extra_time_angle,
			  float source_seek_angle,
			  alg_args_t *args,
			  int *stop_sector,
			  int *finish_sector,
			  int *extra_sectors){
  
  float temp_stop_sector;
  float temp_finish_sector;

  temp_stop_sector = args->source_angle + source_seek_angle;

  while(temp_stop_sector >= 1.0){
    temp_stop_sector -= 1.0;
  } 

  temp_stop_sector *= sectorspercyl[args->target_cyl];

  temp_finish_sector = temp_stop_sector + (extra_time_angle * 
					   sectorspercyl[args->target_cyl]);

  temp_stop_sector = ceil(temp_stop_sector);

  temp_finish_sector = floor(temp_finish_sector);

  *extra_sectors = min_sectors[args->target_cyl][((int)temp_finish_sector -
						  (int)temp_stop_sector)];

  *stop_sector = (min_sectors[args->target_cyl]
		  [(int)temp_stop_sector]);
  
  *finish_sector = (unsigned short)temp_finish_sector;


  while(*finish_sector >= sectorspercyl[args->target_cyl]){
    *finish_sector -= sectorspercyl[args->target_cyl];
  }


  *finish_sector = (min_sectors[args->target_cyl]
		    [*finish_sector]);
}

inline void seek_angles(alg_args_t *args,
			float *source_seek_angle,
			float *dest_seek_angle,
			float *extra_time_angle){

  float orig_seek_angle = (seek_angle[abs(args->source_cyl -
					  args->dest_cyl)]);
  float extra_seek_angle = 0.0;

  if (args->target_cyl == args->source_cyl) {
    *source_seek_angle = 0.0;
  } else {
    if(seek_angle[abs(args->target_cyl - args->source_cyl)] != 0.0){
      *source_seek_angle = (seek_angle[abs(args->target_cyl - 
					     args->source_cyl)]);
			      
    } else {
      fprintf(stderr,"ERROR: seek distance not in structure %d\n",
	      abs(args->target_cyl-args->source_cyl));
      abort();
    }
  }

  if (args->target_cyl == args->dest_cyl) {
    *dest_seek_angle = 0.0;
  } else {
    if(seek_angle[abs(args->target_cyl - args->dest_cyl)] != 0.0){
      *dest_seek_angle = (seek_angle[abs(args->target_cyl - 
					   args->dest_cyl)]);

    } else {
      fprintf(stderr,"ERROR: seek distance not in structure %d\n",
	      abs(args->target_cyl-args->dest_cyl));
      abort();
    }
  }

  extra_seek_angle = ((*source_seek_angle + 
			*dest_seek_angle + 
			 extra_settle_angle + extra_settle_angle) 
			- orig_seek_angle);

  *extra_time_angle = args->rotate_angle - extra_seek_angle;
}

inline void count_blocks(unsigned short stop_sector,
			 unsigned short finish_sector,
			 unsigned short extra_sectors,
			 int surface,
			 alg_args_t *args,
			 unsigned int *temp_count,
			 int *before_found,
			 unsigned int *last_found,
			 unsigned int *last_count){

  unsigned int old_count = 0;
  int j;
  if(extra_sectors > 0){
    *temp_count = 0;
    if(last_count != NULL){
      *last_count = 0;
      *last_found = 0;
    }
    if(before_found != NULL){
      *before_found = 0;
    }
    if(stop_sector > finish_sector){
      for(j=stop_sector;j<sectorspercyl[args->target_cyl];j++){
	(*temp_count) += BITMAP_CHECK(args->devno,args->target_cyl,surface,j);
	if(last_count != NULL){
	  if(*temp_count != old_count){
	    *last_found = j + 1;
	    *last_count = 0;
	  }else{
	    (*last_count)++;
	  }
	  old_count = *temp_count;
	}
	if(before_found != NULL){
	  if(*temp_count == 0){
	    (*before_found)++;
	  }
	}
      }
      for(j=0;j<finish_sector;j++){
	(*temp_count) += BITMAP_CHECK(args->devno,args->target_cyl,surface,j);
	if(last_count != NULL){
	  if(*temp_count != old_count){
	    *last_found = j + 1;
	    *last_count = 0;
	  }else{
	    (*last_count)++;
	  }
	  old_count = *temp_count;
	}
	if(before_found != NULL){
	  if(*temp_count == 0){
	    (*before_found)++;
	  }
	}
      }
    }else if(stop_sector == finish_sector){
      for(j=0;j<sectorspercyl[args->target_cyl];j++){
	(*temp_count) += BITMAP_CHECK(args->devno,args->target_cyl,surface,j);
	if(last_count != NULL){
	  if(*temp_count != old_count){
	    *last_found = j + 1;
	    *last_count = 0;
	  }else{
	    (*last_count)++;
	  }
	  old_count = *temp_count;
	}
	if(before_found != NULL){
	  if(*temp_count == 0){
	    (*before_found)++;
	  }
	}
      }	  
    }else{
      for(j=stop_sector;j<finish_sector;j++){
	(*temp_count) += BITMAP_CHECK(args->devno,args->target_cyl,surface,j);
	if(last_count != NULL){
	  if(*temp_count != old_count){
	    *last_found = j + 1;
	    *last_count = 0;
	  }else{
	    (*last_count)++;
	  }
	  old_count = *temp_count;
	}
	if(before_found != NULL){
	  if(*temp_count == 0){
	    (*before_found)++;
	  }
	}
      }
    }
    if(*temp_count > extra_sectors){
      fprintf(stderr,"ERROR: %d sectors picked up %d possible\n",
	      *temp_count,extra_sectors);
    }
  }
}

#define CYL_RANGE 10

int make_selection_GREEDY_BW_EDGE_COIN(alg_args_t *args){
  /* static vars */
  static float max_bandwidth;
  /* end static vars */

  float extra_angle = 0.0;
  float source_seekangle = 0.0;
  float dest_seekangle = 0.0;
  float temp_bandwidth =  0.0;
  unsigned int extra_sectors = 0;
  unsigned int stop_sector = 0;
  int i;
  int temp_count=0;
  float temp_max=0.0;
  int temp_surface=0;
  int temp_finish_sector = 0;
  
  if(args->inputflags & SCHED_INIT){
    max_bandwidth = 0.0;
  }
  
  if(args->target_cyl < numcyls && (max_bandwidth == 0.0 ||
				    (free_count[args->devno][args->target_cyl]
				     >= sectorspercyl[args->target_cyl] ||
				     sector_angle[args->target_cyl]
				     [free_count[args->devno]
				     [args->target_cyl]] >= 
				     max_bandwidth))){
    
    seek_angles(args,
		&source_seekangle,
		&dest_seekangle,
		&extra_angle);
    
    if(extra_angle > 0.0 && (max_bandwidth == 0.0 || extra_angle
			     >= max_bandwidth)){
      location_info(extra_angle,
		    source_seekangle,
		    args,
		    &stop_sector,
		    &temp_finish_sector,
		    &extra_sectors);
      
      for(i=0;i<numsurfaces;i++){

	count_blocks(stop_sector,
		     temp_finish_sector,
		     extra_sectors,
		     i,
		     args,
		     &temp_count,
		     NULL,
		     NULL,
		     NULL);

	temp_bandwidth = sector_angle[args->target_cyl][temp_count];
	
	if(temp_bandwidth > max_bandwidth || 
	   ((temp_bandwidth == max_bandwidth) && 
	    ((rand() & 0x1) == 1))){