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

/*	This module contains the routines to
	simulate clock2Q.
	accumulate previous references, age by decrementing.
	Put new pages in A1, managed as a FIFO.
	Put pages from A1 into A2in, managed as a FIFO.
        When a page is removed from A2in and it isn't
        referenced, remove it from memory and put a reference in
	A2out, mark the page entry.
        When a page is removed from A2in and it is referenced,
        put it in Am.
        When you fault on an item that is marked as
        being in A2out, put it in Am.
        If you run low on free pages, clean them from Am.

       note: When I manipulate a FIFO, I add to the head and remove from the
	     tail.

	Note: I don't manage A2 the way A1out is managed in 2Q.
	    If a reference is made to an A2in item, that means that
	    it will be put in Am when it gets bumped out of A2in
	    (don't take an expensive action on a page hit).
            If a reference is made to a page in A2out, I put the
	    item in Am.  But, I don't clean A2out, since that is
	    complex and expensive.  Instead, I make a consistency
            check when I remove item tags from A2out.
            This might affect the heuristic a little, but there are
            no correctness problems and its only a heuristic.	
*/

#include<stdio.h>
#include "def.h"


struct item_st item[MAXITEM];  /* Keep track of the items to be referenced
				  Analogous to the page table.	*/

struct page_st page[MAXITEM]; /* Keep track of the page frames  */

/*	Note: Sorry about the confusion between pages, frames	*/

int a2out[MAXITEM];  /* Store A2out	*/

/*	Keep statistics		*/
int survive_histo[50];
int hits1,hits2,hitsmany,missout,missout2;

/*	Various state variables - to be explained later	*/
int freehead,N,b,numfree,cleantrig,sweep_no,scans,noclean,max_surv;
int fastload;

int AMlo,AMhi,numAM,cleanAM;

extern int in1size,in2size,out2size;

int a1head,a1tail,a2inhead,a2intail,a2outhead,amhead,amtail;
int numa1,numa2in,numam;

init_queue(pN,pb,pclean_trig,psweepno,pmaxs,pAMhi,pAMlo)
 int pN,pb,pclean_trig,psweepno,pmaxs;
{

  int j;

	printf("**** Clock2Q, age by decrementing algorithm **** \n");


/*	Initialize the items by setting their state to OUT (of memory)
       and initializing their reference statistics	*/
    for(j=0;j<pN;j++){
	item[j].touchcount=0;	/* keep track of # accesses */
	item[j].fifohit=0;      /* keep track of # hits	    */
        item[j].hitcount=0;
	item[j].state=OUT;	/* out, lru. fifo1, fifo2   */
        item[j].pageno=(-1);	/* If in memory, which page frame	*/
    }

   for(j=0;j<pb;j++){
    page[j].next=j+1;	/* maintain a list, initially the free list 	*/
    page[j].item=(-1);	/* Which item the page frame holds	*/
    page[j].reference=0;	/* page reference bit	*/
    page[j].survive=0;		/* survive history count	*/
    page[j].free=OUT;		/* Keep track of the state of the page */
   }
  page[pb-1].item=(-1);	/* end the free list	*/

  for(j=0;j<out2size;a2out[j++]=0);	/* initialize A2out  */

  for(j=0;j<50;survive_histo[j++]=0);	/* histogram of survive counts
					   when referenced	*/
  hits1=hits2=hitsmany=missout=missout2=0;	/* variaous statistics */

  freehead=0;		/* head of the free page frame list	*/
  a1head=a1tail=(-1);	/* head and tail of the A1 page FIFO	*/
  a2inhead=a2intail=(-1);	/* head and tail of the A2in page FIFO */
  a2outhead=0;		/* maintain A2out as a circular buffer	*/
  amhead=amtail=(-1);	/* Am is a circular list, but I manage it as a FIFO */
		        /* (details to be made clear later */


  N=pN;	
  b=pb;
  fastload=1;	/* Load pages into Am quickly on startup */

  numfree=b;
  numa1=numa2in=numam=0; /* number of pages in the different states */

  scans=0; noclean=0;

  cleantrig=pclean_trig;
  sweep_no=psweepno;
  max_surv=pmaxs;
  
}

void access(d)
int d; {
  int j,temp;


    item[d].touchcount++;   /* record the reference	*/

    switch(item[d].state){
     case OUT2:		/* fault, but the item is in A2out	*/
	missout2++;
/*		Get a free page and put item d in it,
		then attach to the head of Am.  First,
		clean Am to ensure that you have enough free pages.
*/
	if(numfree<=cleantrig){
	    fastload=0;		/* if we have to clean pages, we're done
				   with the startup period	*/
	    while(numfree<=cleantrig){
		/* Clean until we have at least cleantrig pages,
		   look through sweepno pages at a time	*/
	      for(j=0;j<sweep_no;j++){
	        scans++;
                survive_histo[page[amtail].survive]++; /* take statistics */
	        if(page[amtail].reference){
		    page[amtail].reference=0;
		    page[amtail].survive++;
                    if(page[amtail].survive>max_surv)
			  page[amtail].survive--;
/*	cycle through Am by taking the page from the tail, attach to head */
		    page[amhead].next=amtail;
		    amhead=amtail;
		    amtail=page[amtail].next;
	        }
	        else {
		    if(page[amtail].survive>0){
		      page[amtail].survive--;
/*	cycle through Am by taking the page from the tail, attach to head */
		      page[amhead].next=amtail;
		      amhead=amtail;
		      amtail=page[amtail].next;
		    }
		    else{
/*	We found a page to clean.  kink out this item, remove from
	the tail of Am, add to head of the freelist.
*/
		      temp=page[amtail].next;
		      item[page[amtail].item].state=OUT;
		      page[amtail].next=freehead;
		      page[amtail].free=OUT;
		      page[amtail].item=(-1);
		      freehead=amtail;
		      amtail=temp;
		      numfree++;
		      numam--;
		    }
	        }
	      }
	    }
	   }
/*		Finished cleaning, so load item d into a free
		page and attach to the head of Am.
*/
	numfree--; numam++;
	item[d].state=IN;
	item[d].pageno=freehead;
	freehead=page[freehead].next;
	page[item[d].pageno].item=d;
	page[item[d].pageno].free=INMANY;
	page[item[d].pageno].reference=1;
	page[item[d].pageno].survive=0;
	if(amhead==(-1))
	  amhead=amtail=item[d].pageno;
	else{
	  page[amhead].next=item[d].pageno;
	  amhead=item[d].pageno;
	}
   break;

    case OUT:		/* normal fault	*/
/* 		We want to add the page to the head of A1.  But first,
		find a page to hold it.  This triggers the following chain of
		events:  if A1 is its max size, transfer the page at the
		tail of A1 to the head of A2in.  if A2in was full,
		test the page at the tail of A2in. If not referenced, put it in
		the circular A2out queue, and put this page on the free page
		list.  Else (the page at the tail of A2in is referenced),
		clean Am to get free pages, then put it at te head of Am.
		Finally in either case you get a free page, put the item in
		it, then put it at the head of A1.
*/
	
	missout++;
	if(numa1==in1size){ /* If A1 is full, you have to do the cleaning */
/*  start by xfering the page at the tail of A1 to the head of A2in	*/
	  if(a2inhead==(-1)){
	    a2inhead=a2intail=a1tail;
	    a1tail=page[a1tail].next;
	  }else{
	    page[a2inhead].next=a1tail;
	    a2inhead=a1tail;
	    a1tail=page[a1tail].next;
	  }
	  page[a2inhead].reference=0;
	  page[a2inhead].free=IN2;
	  numa1--;  numa2in++;

	  if(numa2in>in2size){ /* if a2in  is full, you have to clean. */
	    if(!page[a2intail].reference && !fastload){
/*	not referenced -> put item onA2out and free up the page.
	fastload heuristic: during startup, put it on Am anyway 
*/
		noclean++;	/* collect statistics */
/*	revise the status of a page from OUT2 to OUT only if the
	the change is valid (during startup, you might not point
	to a valid page.  Also, the A2out queue is not modified when 
        a fault on an A2out page occurs - too complex, expensive.
*/
/*	Kick out the label at the tail (head)  of A2out	*/
	      if(a2out[a2outhead]>=0)
	          if(item[a2out[a2outhead]].state==OUT2)
		    item[a2out[a2outhead]].state=OUT;
	      a2out[a2outhead]=page[a2intail].item;
/*	add the new page label			*/
	      item[a2out[a2outhead]].state=OUT2;
	      a2outhead=(a2outhead+1)%out2size; /* update circular buffer */
  
/*	Put the page frame on the free list	*/
	      temp=page[a2intail].next;
              page[a2intail].next=freehead;
	      page[a2intail].free=OUT;
	      freehead=a2intail;
	      a2intail=temp;
	      numa2in--; numfree++;
	    }else{
/*	THe item was referenced.
	I want to put this page on Am.  First clean Am to get free pages.
*/
        if(numfree<=cleantrig){
	    fastload=0;
            while(numfree<=cleantrig){
              for(j=0;j<sweep_no;j++){
                scans++;
                survive_histo[page[amtail].survive]++;
                if(page[amtail].reference){
                    page[amtail].reference=0;
                    page[amtail].survive++;
                    if(page[amtail].survive>max_surv)
                          page[amtail].survive--;
                    page[amhead].next=amtail;
                    amhead=amtail;
                    amtail=page[amtail].next;
                }
                else {
                    if(page[amtail].survive>0){
                      page[amtail].survive--;
                      page[amhead].next=amtail;
                      amhead=amtail;
                      amtail=page[amtail].next;
                    }
                    else{
                      temp=page[amtail].next;
                      item[page[amtail].item].state=OUT;
                      page[amtail].next=freehead;
                      page[amtail].free=OUT;
                      page[amtail].item=(-1);
                      freehead=amtail;
                      amtail=temp;
                      numfree++;
                      numam--;
                    }
                }
              }
            }
           }
/*  cleaning is done, put the page at the tail of A2in on the head of Am.
*/
	  if(amhead==(-1))
		amhead=amtail=a2intail;
	  else{
	    page[amhead].next=a2intail;
	    amhead=a2intail;
	  }
	  page[amhead].free=INMANY;
	  a2intail=page[a2intail].next;
	  numam++; numa2in--;
	}
       }
      }
/*	Finally, put the newly referenced page in a free page, attach to the
	head of A1.
*/
	numfree--; numa1++;
	item[d].state=IN;
	item[d].pageno=freehead;
	freehead=page[freehead].next;
	page[item[d].pageno].item=d;
	page[item[d].pageno].free=IN1;
	page[item[d].pageno].reference=1;
	page[item[d].pageno].survive=0;
	if(a1head==(-1))
		a1head=a1tail=item[d].pageno;
	else{
	  page[a1head].next=item[d].pageno;
	  a1head=item[d].pageno;
	}
	break;

    case IN:
	/* collect statistics, set the reference bit	*/
	item[d].hitcount++;
	page[item[d].pageno].reference=1;
        if(page[item[d].pageno].free==IN1)  hits1++;
        if(page[item[d].pageno].free==IN2)  hits2++;
        if(page[item[d].pageno].free==INMANY)  hitsmany++;
    }
}
	





/*	--------------  dump routines for debugging ------------------- */



dump(){
int i,j;

printf("numfree=%d, numa1=%d, numa2in=%d, freehead=%d, a1head=%d, a1tail=%d\n",numfree,numa1,numa2in,freehead,a1head,a1tail);
printf("a2inhead=%d, a2intail=%d. numam=%d, amhead=%d, amtail=%d, fastload=%d",a2inhead,a2intail,numam,amhead,amtail,fastload);

printf("\na2outhead=%d",a2outhead);
for(j=0;j<out2size;j++){
  if(j%10==0) printf("\n");
  printf("%d  ",a2out[j]);
}
printf("\n\n");


printf("\nBuffer state:\n");
for(i=0;i<b;i++)
  printf("%d: item=%d, reference=%d, survive=%d, free=%d next=%d\n",i,page[i].item,page[i].reference,page[i].survive,page[i].free,page[i].next);

printf("\nitem state:\n");
for(i=0;i<N;i++)
  printf("%d: page=%d, state=%d, touch=%d, hits=%d\n",i,item[i].pageno,item[i].state,item[i].touchcount,item[i].hitcount);

}
  

report_stats(){
  int j;

   printf("histogram of survive values");
   for(j=0;j<=max_surv;j++){
        if(j%8==0)
                printf("\n%d: ",j);
        printf("%8d ",survive_histo[j]);
   }

	printf("\n noclean=%d\n",noclean);
	printf("hits1=%d, hits2=%d, hitsmany=%d, missout=%d, missout2=%d\n",hits1,hits2,hitsmany,missout,missout2);
}

