From ted@cis.ufl.edu Tue Jan 25 13:27:32 1994
Received: from squall.cis.ufl.edu by SHASHA.CS.NYU.EDU (5.61/1.34)
	id AA26814; Tue, 25 Jan 94 13:27:25 -0500
From: ted@cis.ufl.edu
Received:  from localhost  by squall.cis.ufl.edu (8.6.4/4.11)
	id NAA13240; Tue, 25 Jan 1994 13:27:24 -0500
Date: Tue, 25 Jan 1994 13:27:24 -0500
Message-Id: <199401251827.NAA13240@squall.cis.ufl.edu>
To: doshi@summit.novell.com, shasha@SHASHA.CS.NYU.EDU
Status: R

/* 	This simulator exercises the buffer mgt. algorithms
	M is the number of references.  N is the number of data items.
	a is the skew of zipf distributeion.
	Allow scans.

	Warning: Its likely that this code contains artifacts from
	its previous incarnations.

	Note: I use this driver for all of the all of the page replacement
	algorithms, so I ask for the parameters for all of the algorithms.
*/

#define MAXSIZE 120000
#include<stdio.h>
#include<math.h>
#include"def.h"

extern float uniform();
extern int r_random();

extern struct item_st item[MAXITEM];
extern int scans;

int in1size,in2size,out2size;

int numhits[MAXSIZE],rank[MAXSIZE];
double probhit[MAXSIZE];




main()
{
int M,N,t,thit,ranking,lo,hi,oprobe,probe,i,iter,min,max,maxrank;
int xc,nexec,seed,rcount,dum,interval;
float hit,a,normalize,tprob,c,aa,Ex,V;
int n,k,k2,numlru,numfifo2,numfifo,histsize,numtouch,j;
int Ksize,fifosum,ksum;
int scanfreq,scanlen,scanmin,Nminor,scan[MAXITEM],slen,found,sample;
int majorscan,minorscan;
float scanloc,s_pool;
int clean_trig,sweepno,maxs,AMhi,AMlo,numhit,b;
int stopafter;

  stopafter=0;

  printf("Simulator to test buffer algorithms.  Zipf distribution\n");

/*	Get the number of references to make		*/
  printf("Number of iterations?\n");
  scanf("%d",&M);
  printf("M=%d\n",M);

/*	Main database - both random referrences and scans are selected
	from this database
*/
  printf("Database size?\n");
  scanf("%d",&N);
  if((N>=MAXITEM) || (N>=MAXITEM)){
	printf("max size limited to min of %d, %d\n",MAXSIZE,MAXITEM);
	exit(0);
  }
  printf("N=%d\n",N);

/*	A scan-only database				*/
  printf("size of minor pool?\n");
  scanf("%d",&Nminor);
  printf("minor pool is %d buffers\n",Nminor);

       printf("Number of buffers?\n");
       scanf("%d",&b);
       printf("b=%d\n",b);

/*	find free pages if fewer than clean_trig free pages exist
	after servicing a fault
*/
       printf("cleaning trigger?\n");
       scanf("%d",&clean_trig);
       printf("clean_trig=%d\n",clean_trig);

/*	continue cleaning until there are at least this many free pages */
       printf("pages per sweep?\n");
       scanf("%d",&sweepno);
       printf("sweepno=%d\n",sweepno);

/*	maximum value of the survive history count		*/
       printf("max survive?\n");
       scanf("%d",&maxs);
       printf("maxs=%d\n",maxs);

/* 	clkclass parameter - largest possible number of Am pages	*/
       printf("AMhi?\n");
       scanf("%d",&AMhi);
       printf("AMhi=%d\n",AMhi);

/*	clkclass parameter - smallest possible number of Am pages	*/
       printf("AMlo?\n");
       scanf("%d",&AMlo);
       printf("AMlo=%d\n",AMlo);


       init_queue(N,b,clean_trig,sweepno,maxs,AMhi,AMlo);

/*	clock2q parameter	*/
    printf("in1size?\n");
    scanf("%d",&in1size);
    printf("in1size=%d\n",in1size);

/*	clock2q parameter	*/
    printf("in2size?\n");
    scanf("%d",&in2size);
    printf("in2size=%d\n",in2size);

/*	clock2q parameter	*/
    printf("out2size?\n");
    scanf("%d",&out2size);
    printf("out2size=%d\n",out2size);

/*--------------  Next, specify the reference string	--------*/


/*	parameter for the zipf distribution		*/
  printf("what is a?\n");
  scanf("%f",&a);
  printf("a=%f\n",a);

/*	how often to initiate a scan			*/
  printf("Scan Frequency?\n");
  scanf("%d",&scanfreq);
  printf("one scan after an average of %d random references\n",scanfreq);

/*	next 2 parameters bound the length of the scan	*/
  printf("max scan length?\n");
  scanf("%d",&scanlen);
  printf("max scan length=%d\n",scanlen);

  printf("min scan length?\n");
  scanf("%d",&scanmin);
  printf("min scan length=%d\n",scanmin);

/*	sometimes scan in main database, sometimes in minor pool	*/
  printf("prob that the scan is in the major pool?\n");
  scanf("%f",&scanloc);
  printf("prob scan in major pool=%f\n",scanloc);

  printf("seed?\n");
  scanf("%d",&seed);
  printf("seed=%d\n",seed);
    stream(seed);

/*	The following code sets up the zipf distribution.
	1) load the zipf distribution function into probhit
	2) to make a reference, sample from a uniform (0,1) distribution
           then do a binary search in probhit to find the item to reference.
*/

  normalize=0.0;
  for(i=1;i<=N;i++){
    probhit[i]=(float)pow((double)i,(double)(-1.0)*a);
    normalize+=probhit[i];
  }

  probhit[0]=0.0;
  for(i=1;i<=N;i++)
    probhit[i]/=normalize;

  for(i=1;i<=N;i++)
    probhit[i]+=probhit[i-1];
  probhit[N]=1.1;





  interval=M/10;	/* I want a running snapshot of the hit rate 	*/
  majorscan=0;minorscan=0;

  for(iter=0;iter<M;iter++){

/*	to set breakpoints when debugging	*/
    if(iter==stopafter)
	stopafter=stopafter;

    if(r_random(1,scanfreq)==(scanfreq/2)){	/* start a scan */

	slen=r_random(scanmin,scanlen);
        if(slen+iter>=M) slen=M-iter-1;
	
        s_pool=uniform(0.0,1.0);

	if(s_pool<=scanloc){	/*access primary pool*/
	  for(i=0;i<slen;i++){
	    found=0;
	    while(!found){
	      sample=r_random(1,N);
	      found=1;
	      for(j=0;j<i;j++){
		  if(scan[j]==sample){
		    found=0;
		    break;
		  }
	      }
	    }
	    scan[i]=sample;
	    access(sample);
	    iter++;
	    majorscan++;
	  }
	}
	else{	/*	access an otherwise unused pool	*/
	  for(i=0;i<slen;i++){
	    found=0;
	    while(!found){
	      sample=r_random(1,Nminor);
	      found=1;
	      for(j=0;j<i;j++){
		  if(scan[j]==sample){
		    found=0;
		    break;
		  }
	      }
	    }
	    scan[i]=sample;
	    access(sample+N);
	    iter++;
	    minorscan++;
	   }
	}

  if((iter%interval)==0 && iter){
    numhit=0;
    for(i=0;i<N;i++){
        numhit+=item[i].hitcount;
    }
    printf("Total of %d hits out of %d accesses (%f)\n",numhit,iter,(float)numhit/(
float)iter);
    printf("scanned through %d pages\n\n",scans);
    }

  }




    hit=uniform(0.0,1.0);

    min=1;max=N;probe=(min+max)/2,oprobe=0;

    while(probe!=oprobe){
        if(probhit[probe]<hit)
          min=probe;
        else
          max=probe;
	oprobe=probe;
        probe=(min+max)/2;
    }
    if(!((probhit[probe-1]<hit) && (probhit[probe]>=hit)))
	probe++;

    access(probe);


  if((iter%interval)==0 && iter){
     numhit=0;
    for(i=0;i<N;i++){
        numhit+=item[i].hitcount;
    }
    printf("Total of %d hits out of %d accesses (%f)\n",numhit,iter,(float)numhit/(
float)iter);
    printf("scanned through %d pages\n\n",scans);
  }


  }


printf("**********************************\n\n");

  numhit=0;
  for(i=0;i<N;i++){
        numhit+=item[i].hitcount;
  }
    printf("Total of %d hits out of %d accesses (%f)\n",numhit,M,(float)numhit/(
float)M);
    printf("scanned through %d pages\n\n",scans);

  histsize=N/10;
  for(i=0;i<N;i+=histsize){
    numhit=0; numtouch=0;
    for(j=0;j<histsize && i+j<N; j++){
        numhit+=item[i+j].hitcount;
        numtouch+=item[i+j].touchcount;
    }
    printf("class %d, %d touch, %d hit\n",i,numtouch,numhit);
  }

/*	call into the page replacement algorithm to report
	algorithm-specific statistics
*/
report_stats();


}
	
	

