
/*	This module contains the routines to
	simulate the clock/class algorithm.
	accumulate previous references, age by decrementing.
	Keep two classes of pages: A1 and Am.  Don't clean Am pages
	unless there are too many of them.
	The drivers are attached seperately.

*/

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


	/* these are the items being referenced	*/
struct item_st item[MAXITEM];
	/* these are the page frames	*/
struct page_st page[MAXITEM];

int freehead,N,b,numfree,cleantrig,sweep_no,scan_ptr,scans,max_surv;
int AMlo,AMhi,numAM,cleanAM;
int inhit=0,in1hit=0,inmanyhit=0;

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

  int j;

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


/*	Initialize the items	*/
    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);	/* page frame that holds the item	*/
    }

/*	initialize the page frames	*/
   for(j=0;j<pb;j++){
    page[j].item=j+1;		/* point to item stored, or use for a
				   free list (initially, free list)*/
    page[j].reference=0;	/* reference bit */
    page[j].survive=0;		/*	survive count	*/
    page[j].free=OUT;		/* state of the page	*/
   }

  page[pb-1].item=(-1);		/* end the free list	*/

  freehead=0;			/* head of the free list	*/
  N=pN;
  b=pb;
  numfree=pb;
  cleantrig=pclean_trig;
  sweep_no=psweepno;
  max_surv=pmaxs;
  scan_ptr=0;
  scans=0;

  AMlo=pAMlo;
  AMhi=pAMhi;
  numAM=0;
  cleanAM=0;
  
}

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


    item[d].touchcount++;

    switch(item[d].state){
     case OUT:		/* fault	*/
	while(numfree<=cleantrig){
		/* not enough free frames => clean	*/
	  for(j=0;j<sweep_no;j++){
		/* look at sweepno frames at a time	*/
	    scan_ptr=(scan_ptr+1)%b;	/* circular cleaning	*/
	    scans++;

	    switch(page[scan_ptr].free){
	    case IN:	/* new page, lets see if it is reference again */
		page[scan_ptr].reference=0;
		page[scan_ptr].free=IN1;
		break;

	    case IN1:	/* we're testing this page for the 2nd reference */
	      if(page[scan_ptr].reference){
		  page[scan_ptr].reference=0;
		  page[scan_ptr].survive=1;
		  page[scan_ptr].free=INMANY;
		  numAM++;
/*	If there are too many Am pages, turn on the Am cleaning	*/
		  if(!cleanAM && numAM==AMhi)	
			cleanAM=1;
	      }
	      else {
		  item[page[scan_ptr].item].state=OUT;
		  page[scan_ptr].item=freehead;
		  page[scan_ptr].free=OUT;
		  freehead=scan_ptr;
		  numfree++;
		}
		break;


	      case INMANY:
/*	Even if we don't clean, keep track of the history	*/
	        if(page[scan_ptr].reference){
		    page[scan_ptr].reference=0;
		    page[scan_ptr].survive++;
                    if(page[scan_ptr].survive>max_surv)
			  page[scan_ptr].survive--;
	        }
	        else {
		    if(page[scan_ptr].survive>0)
		      page[scan_ptr].survive--;
		    else if(cleanAM){	
/*	reference=0 and survive=0.
	only clean this page if there are too many Am pages.	*/
		      item[page[scan_ptr].item].state=OUT;
		      page[scan_ptr].item=freehead;
		      page[scan_ptr].free=OUT;
		      freehead=scan_ptr;
		      numfree++;
		      numAM--;
/*	If there are too few Am pages, turn off Am cleaning	*/
		      if(numAM==AMlo)  cleanAM=0;
		    }
	        }
		break;

	      case OUT:
		break;
              }

	    }
        }

	numfree--;
	item[d].state=IN;
	item[d].pageno=freehead;
	freehead=page[freehead].item;
	page[item[d].pageno].item=d;
	page[item[d].pageno].free=IN;
	page[item[d].pageno].reference=1;
	page[item[d].pageno].survive=0;
	
	break;

    case IN:
/*	set the reference bit and collect statistics	*/
	item[d].hitcount++;
	page[item[d].pageno].reference=1;
        if(page[item[d].pageno].free==IN)  inhit++;
        if(page[item[d].pageno].free==IN1)  in1hit++;
        if(page[item[d].pageno].free==INMANY)  inmanyhit++;
    }
}
	





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



dump(){
int i;

printf("numfree=%d, scan_ptr=%d, freehead=%d\n",numfree,scan_ptr,freehead);

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

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(){
   printf("inhit=%d, in1hit=%d, inmanyhit=%d\n",inhit,in1hit,inmanyhit);
}

