Simulating Clock Algorithm

[SnoBunny85]

My professor has given us the fifo algorithm program and asked us to modify it to become the clock algorithm by using reverse_map to find a page table entry and then checking its reference bit. If the reference bit is set, clear it and go on. I am just completely stuck on where to go with this coding. I have included the fifo code given to us and where he defines reverse_map. I think I am adding reverse_map correctly but not sure which parameters to use or where to quite go after that. i don't want the whole code written for me, just tips to head me in the right direction because he doesn't do a very good job of explaining things. I have also attached all of the files he gave us just in case those are needed as well. thanks

/*
 * Simulate clock algorithm
 *  -p <pagesize>	Page size offset bits, default 12
 *  -m <realmem>	Number of real memory pages.  Default 10
 *  -i <tracefile>	Input trace file name.  Default, standard input.
 *  -c <clrfreq>    Clear all the used bits each <clrfreq> references.
 *                     Default 10000
 */

#include <iostream>
using std::cout;
using std::endl;

#include "argval.h"
#include "memory_sys.h"
#include "trace_reader.h"

int main(int argc, const char **argv)
{
	// Collect the arguments and open the input file.
	ArgVal args(argc, argv);
	int pagebits = args.ival("-p", 12);
	int realmem = args.ival("-m", 10);
	RefReader tracereader;
	if(args.present("-i")) tracereader.open(args.cval("-i"));

	//add c to clear all the bit references
	int clrfreq = args.ival("-c", 10000);

	// The vm represents the page table and real memory.
	PageMapping vm(realmem);

	// Next page in FIFO ordering.
	unsigned int next = 0;

	// Various statistics we wish to collect.
	int nwrb = 0;		// Number of page write-backs.

	// Read the trace and process.
	Ref r;
	while(tracereader.read(r)) {
		// See how many pages the reference covers (almost always just
		// one), and the first page.  Then loop to process each of
		// those pages.
		int npage = r.npage(pagebits);
		unsigned int page = r.pageno(pagebits);
		while(npage--) {
			// Attempt the page reference.
			if(!vm.ref_page(page, r.is_write())) {
				// Fault.  Kick out old page and establish
				// new mapping.

--->this is my coding
            //using reverse_map to find the page table entry
            vm.reverse_map(next, , page);
---->
			PTE old_pte = vm.set_mapping(page, next);
			if(old_pte.mod) ++nwrb;

			// Repeat the reference.
			vm.ref_page(page, r.is_write());

			// Rotate next through the page numbers.
			if(++next >= realmem) next = 0;
			}
			++page;
		}
	}

	cout << "Clock replacement policy" << endl;
	cout << tracereader.ref_count() << " memory references produce "
	     << vm.get_numfault() << " page faults with " << nwrb
	     << " write-backs.\n" << vm.get_faultrate(tracereader.ref_count())
	     << " faults/reference." << endl;

}

#include <utility>

#include "memory_sys.h"

// Remove the entry for the indicated page.  Returns the old entry, which
// may have already been invalid.
PTE PageMapping::invalidate_pte(unsigned int pageno) 
{
	// Find the entry and invalidate it.
	map<unsigned int, PTE>::iterator i = table.find(pageno);
	if(i == table.end()) return PTE();

	// Make the return value, then erase the original
	PTE ret(i->second);
	table.erase(i);

	// Clear the reverse map.
	if(ret.valid)
		realmem[ret.realpage] = table.end();

	return ret;
}

// Set a new mapping in the table.  If the realpage is already in use,
// its existing mapping is cleared and a _copy_ of that _old_ PTE is
// returned.  If pageno is presently mapped, its old PTE is invalidated
// also, and not returned.  Then a new mapping is established with the
// referenced and modified bits clear
PTE PageMapping::set_mapping(unsigned int pageno, unsigned int realpage) 
{
	// If there is an existing mapping to realpage, create a return PTE
	// and invalidate the exising mapping.
	PTE ret;
	if(realmem[realpage] != table.end()) {
		ret = realmem[realpage]->second;
		table.erase(realmem[realpage]);
	}

	// If there is an existing mapping, invalidate it.  Otherwise,
	// insert a new entry and map it correctly.
	map<unsigned int, PTE>::iterator i = table.find(pageno);
	if(i == table.end()) {
		// No existing mapping.  Make one.
		i = table.insert(std::make_pair(pageno,PTE())).first;
		i->second.valid = true;
	} else {
		// Existing mapping.  Clear it.
		realmem[i->second.realpage] = table.end();
		i->second.ref = i->second.mod = false;
	}

	// Make the mapping (new or old) point to the require page, and
	// the page point back for the reverse map service.
	i->second.realpage = realpage;
	realmem[realpage] = i;

	return ret;
}

// Simulate a reference.  This returns true if the mapping is valid, or false
// if it creates a fault.  If it is not a fault, the referenced bit, and
// optionally the modified bit, are set.  If realpage is non-NULL, and the
// mapping was valid, the page number is returned through realpage.
bool PageMapping::ref_page(unsigned int pageno, unsigned int *realpage,
			   bool is_write /* = false */) {
	// Stats.
	if(is_write) ++nwrite;
	else ++nread;

	// Find the PTE.
	map<unsigned int, PTE>::iterator i = table.find(pageno);
	if(i == table.end()) {
		// No valid entry.  Count and return a fault.
		++nfault;
		return false;
	}

	// Valid.  Update flags and return required information.
	if(realpage) *realpage = i->second.realpage;
	i->second.ref = true;
	if(is_write) i->second.mod = true;
	return true;
}

// Pre-looked-up version.
bool PageMapping::ref_page(PTEptr pte, bool is_write /* = false */)
{
	// Stats.
	if(is_write) ++nwrite;
	else ++nread;

	// Find the PTE.
	if(pte == NULL) {
		// No valid entry.  Count and return a fault.
		++nfault;
		return false;
	}

	// Valid.  Update flags and return required information.
	pte.ref(true);
	if(is_write) pte.mod(true);
	return true;
}

// Reverse lookup.
bool PageMapping::reverse_map(unsigned int realpage, 
			      unsigned int *virtpage, PTEptr *pte)
{
	// Make sure the page number is in range, then find the
	// iterator recorded for the page, and see if it is valid.
	// If either test fails, return false.
	if(realpage >= nframes) return false;
	map<unsigned int, PTE>::iterator i = realmem[realpage];
	if(i == table.end()) return false;

	// Found one.  Fill in the return information.
	if(virtpage) *virtpage = i->first;
	if(pte) *pte = PTEptr(&i->second);
	return true;
}

// Following is a test program which is only compiled if the flag 
// -DMEMSYS_TEST is used.
#ifdef MEMSYS_TEST
#include <iostream>
#include <stdlib.h>

using namespace std;

bool PageMapping::conchk()
{
	bool bad = false;

	// Go through the PTEs and see if the reverse entries match.
	std::map<unsigned int, PTE>::iterator i;
	for(i = table.begin(); i != table.end(); ++i)
	{
		if(!i->second.valid) {
			cout << "Stored PTE for " << i->first << " invalid."
			     << endl;
			bad = true;
		}
		if(i->second.realpage >= nframes) {
			cout << "Page " << i->first << " maps to real page "
			     << i->second.realpage << ", whichis out of "
			     << "range." << endl;
			bad = true;
		}
		else if(realmem[i->second.realpage] != i) {
			cout << "Reverse map error: PTE " << i->first 
			     << " maps to " << i->second.realpage
			     << ", but that real page has wrong iterator." 
			     << endl;
			bad = true;
		}
	}

	// Check them the other way.
	for(unsigned int i = 0; i < nframes; ++i) {
		if(realmem[i] != table.end() && 
		   realmem[i]->second.realpage != i) {
			cout << "Real page " << i << " shows valid but "
			     << "maps back to " 
			     << realmem[i]->second.realpage << endl;
			bad = true;
		}
	}

	return !bad;
}

const unsigned int NFRAME = 200;
const unsigned int XMASK = 0x193;

// Computed target for mapping.
bool target(unsigned int page, unsigned int *_targ = NULL)
{
	unsigned int targ = page ^ XMASK;
	if(targ >= NFRAME) return false;
	if(_targ) *_targ = targ;
	return true;
}
unsigned int rtarg(unsigned int page)
{
	unsigned int targ = 0;
	target(page, &targ);
	return targ;
}

// Check the pattern of bits created by the test driver.  Mod (both) set
// for multiples of 5, and ref for 3.
bool bittest(unsigned int p, PTEptr pte)
{
	bool ok = true;

	if(pte->mod != (p % 5 == 0)) {
		cout << "Bad mod bit " << pte->mod << " at " << p << endl;
		ok = false;
	}
	bool ref = (p % 5 == 0) || (p % 3 == 0);
	if(pte->ref != ref) {
		cout << "Bad ref bit " << pte->ref << " at " << p << endl;
		ok = false;
	}

	return ok;
}

class PS: public PageMapping::PageScanner {
public:
	int validct;
	bool ok;

	PS(): validct(0), ok(true) { }

	virtual void visit(unsigned int pageno, PTEptr pte)
	{
		++validct;

		unsigned int t;
		if(target(pageno,&t) && t == pte->realpage) {
			if(!bittest(pageno, pte)) ok = false;
		} else if(pte->realpage == (pageno+1) % NFRAME) {
			if(pte->ref || pte->mod) {
				cout << "Bad bits on scan" << endl;
				ok = false;
			}
		}
	}	
};

class MS: public PageMapping::FrameScanner {
public:
	int tot;
	bool ok;
	MS(): tot(0), ok(true) { }
	virtual void visit(unsigned int frameno, unsigned int mapsto,
			   PTEptr mapper)
	{
		if(mapper != NULL) {
			++tot;
			if(mapper->realpage != frameno) {
				cout << "GAK! Bad ref on frame scan "
				     << mapper->realpage << " " << frameno << endl;
				ok = false;
			}
		}
	}
};

main()
{
	PageMapping pm(NFRAME);

	bool ok = pm.conchk();
	if(pm.get_nframes() != NFRAME) {
		cout << "Bad frame count " << pm.get_nframes() << " != "
		     << NFRAME << endl;
		ok = false;
	}

	// All pages should be invalid.
	for(unsigned int p = 0; p < 2*NFRAME; p += 13) {
		if(pm.valid(p) || pm.get_pte(p) != NULL) {
			cout << "Valid at empty " << p << endl;
			ok = false;
		}
	}

	// Set a bunch of mappings and check internal consistancy.
	int nvalid = 0;
	for(unsigned int p = 0; p < 2*NFRAME; ++p) {
		unsigned int t;
		if(!target(p,&t)) continue;
		PTE old = pm.set_mapping(p, t);
		if(old.valid) {
			cout << "Valid at first setting " << p << endl;
			ok = false;
		}
		++nvalid;
	}
	ok = pm.conchk() && ok;

	// Check the back references.
	int rev = 0;
	for(unsigned int r = 0; r < NFRAME; ++r) {
		unsigned int page;
		PTEptr pte;
		if(pm.reverse_map(r, &page, &pte)) {
			if(!pte->valid || pte->mod || pte->ref) {
				cout << "Bad flags on reverse PTE A" << endl;
				ok = false;
			}
			if(pte->realpage != r) {
				cout << "Bad reverse map failure A." << endl;
				ok = false;
			}
			++rev;
		}
	}
	if(rev != nvalid) {
		cout << "Forward and reverse map counts don't match." << endl;
		ok = false;
	}

	// Shadow counts to test the ones in the object.
	int nread = 0, nwrite = 0, nfault = 0;

	// Do some references.
	for(unsigned int p = 0; p < 2*NFRAME; p += 3) {
		++nread;
		bool valid = pm.ref_page(p);
		if(!valid) ++nfault;
		if(valid != target(p)) {
			cout << "Bad validity at ref_page(" << p << ")" << endl;
			ok = false;
		}
	}

	// Do some modification refs.
	for(unsigned int p = 0; p < 2*NFRAME; p += 5) {
		++nwrite;
		bool valid = pm.ref_page(p, true);
		if(!valid) ++nfault;
		if(valid != target(p)) {
			cout << "Bad validity at mod ref_page(" << p << ")" 
			     << endl;
			ok = false;
		}
	}

	// See if it's all ok.
	ok = pm.conchk() && ok;
	for(unsigned int p = 0; p < 2*NFRAME; ++p) {
		unsigned int t;
		bool v = target(p,&t);
		PTEptr pte = pm.get_pte(p);

		if(v != (pte != NULL)) {
			cout << "Bad validity at get_pte(" << p << ")" << endl;
			ok = false;
			continue;
		}

		if(pte == NULL) continue;

		if(pte->realpage != t) {
			cout << "Bad target for " << p << ": should be "
			     << v << " instead of " << pte->realpage << endl;
			ok = false;
		}
		
		ok = bittest(p, pte) && ok;

		// Check the reverse mapping.
		unsigned int vp;
		PTEptr revpte;
		if(!pm.reverse_map(pte->realpage,&vp,&revpte) || vp != p ||
		   revpte != pte) {
			cout << "Reverse map failure B." << endl;
			ok = false;
		}
	}

	// Some random tests
	int origvalid = nvalid;
	int changed = 0;
	for(int n = 1; n <= 500; ++n)
	{
		unsigned int p = rand() % (2*NFRAME);
		unsigned int t;
		bool v = target(p,&t);

		PTE old;
		PTEptr oldptr = pm.get_pte(p);
		if(oldptr != NULL) old = *oldptr;
		PTE pte = pm.set_mapping(p,(p+1)%NFRAME);

		// Account for destroyed entries, and for one created.
		if(oldptr != NULL && old.realpage != (p+1)%NFRAME) --nvalid;
		if(pte.valid) --nvalid;
		++nvalid;

		if(oldptr == NULL) {
			// There was not a previous mapping from p.
			if(!v) {
				// There was no old mapping, so there
				// reason for suspicion.
			} else {
				// If this happens, it should have been
				// a replacement by a new one.  See if there
				// is a new-style mapping to t.  It can also be
				// knocked out by a forward mapping from the same
				// virtual page, which then gets replaced by
				// a different multiple of NFRAME.
				unsigned int oldfrom = 
					t == 0 ? NFRAME - 1 : t - 1;
				unsigned int altfrom = p % NFRAME;
				bool found = false;
				while(!found && oldfrom < 2*NFRAME) {
					PTEptr altmap = pm.get_pte(oldfrom);
					found = (altmap != NULL && 
						 altmap->realpage == t);
					if(found) break;
					oldfrom += NFRAME;

					altmap = pm.get_pte(altfrom);
					found = (altmap != NULL && 
						 altmap->realpage == (altfrom+1)%NFRAME);
					altfrom += NFRAME;
				}
				if(!found) {
					cout << "Missing old mapping from "
					     << p << " t = " << t 
					     << " oldfrom = " << oldfrom
					     << endl;
					ok = false;
				}
			}
		} else {
			// Might have replaced an old one or a new one.
			if(v && old.realpage == t) {
				// Bits must be unchanged from earlier test
				ok = bittest(p, &old) && ok;
			} else if(old.realpage == (p+1)%NFRAME) {
				// New entry.  Must be zero.
				if(old.mod || old.ref) {
					cout << "Bad bits on new entry at "
					     << p << endl;
					ok = false;
				}
				++changed;
			} else {
				cout << "Bad target maps " << p << " to "
				     << old.realpage << endl;
				ok = false;
			}
		}

		// Check the reverse mapping.
		unsigned int vp;
		PTEptr revpte;
		if(!pm.reverse_map((p+1)%NFRAME,&vp,&revpte) || vp != p ||
		   revpte == NULL || revpte->realpage != (p+1)%NFRAME) {
			cout << "Reverse map failure C." << endl;
			ok = false;
		}

		if(n % 10 == 0)
			ok = pm.conchk() && ok;
	}

	cout << origvalid << " original valid entries; "
	     << nvalid << " final valid entries." << endl;
	cout << changed << " observed redirects" << endl;

	PS pscanner;
	pscanner.scan(pm);
	if(pscanner.validct != nvalid) {
		cout << "Scan valid count mismatch " << pscanner.validct
		     << " != " << nvalid << endl;
		ok = false;
	}

	MS mscanner;
	mscanner.scan(pm);
	if(mscanner.tot != nvalid) {
		cout << "Tot use count incorrect " << mscanner.tot 
		     << " != " << nvalid << endl;
		ok = false;
	}

	ok = pm.conchk() && pscanner.ok && mscanner.ok && ok;

	if(pm.get_numread() != nread || pm.get_numwrite() != nwrite || 
	   pm.get_numfault() != nfault) {
		cout << "Count error: " 
		     << pm.get_numread() << " " << nread  << " "
		     << pm.get_numwrite() << " " << nwrite << " " 
		     << pm.get_numfault() << " " << nfault << endl;
		ok = false;
	}

	if(ok) {
		cout << "All tests okay." << endl;
		exit(0);
	} else
		exit(1);
}
#endif