The objective of this lab is to simulate and evaluate a virtual memory system, and experiment with different page replacement algorithms. You will need a threads package, e.g., pThreads thread package.

Assume that you have a 16-bit address space, 16 KB of main memory, and 2 KB page size. Virtual memory simulation consists of three components: a virtual address generation component, address translation component, and a statistics reporting component. Implement each component by a separate thread.

The virtual address generation component generates a sequence of 16-bit virtual addresses and writes them in an integer buffer inBuffer of size 10. Write a function getNextVirtualAddress( ) for generating virtual addresses. This function may generate virtual addresses at random or based on a trace obtained from some source.

The address translation component implements virtual address to physical address translation using a page replacement algorithm (select a page replacement algorithm). This component reads the next virtual address from inBuffer and translates that address to a physical address. It prints the virtual address and corresponding physical address in a file. It also increments an integer variable (numberOfPageFaults) on every page fault. Use appropriate bit operations (<<, >>, ~, |, &, etc.) to implement this address translation. Feel free to implement a separate version of this component for every page replacement algorithm you want to experiment with.

The statistics reporting component prints the total number of page faults (numberOfPageFaults) at the end.

*** Heres what I have so far ... any help will get points. Thanks.

#define NUM_ADDRESSES_TO_GENERATE 10000

#define IN_BUFFER_SIZE 10

#define PAGE_SIZE 2048

#define MAIN_MEMORY_SIZE 16384

#define VIRTUAL_MEMORY_SIZE 65536

#define NUM_PAGES MAIN_MEMORY_SIZE / PAGE_SIZE

int inBuffer[IN_BUFFER_SIZE];        // buffer to write/read virtual addresses

int inBufferCount;                   // Number of virtual addresses in the shared buffer

pthread_mutex_t inBufferMutex;       // Mutex used to synchronize access to the inBuffer

int numberOfPageFaults;              // Counter for the number of page faults

bool addressGenerationDone;          // Flag used to indicate the address generation is done

// I probably need some structures and variables to store information

// needed for page replacement and address translation

int getNextVirtualAddress(int addr)

{

// I need to Replace below with your own method of generating virtual addresses.

// I can just generate a random address if you want, which is probably the

// easiest thing to do.

return 0;

}

void* doAddressGeneration(void* pArg)

{

int addr = -1;

int addressCount = NUM_ADDRESSES_TO_GENERATE;

while (addressCount != 0) {

if (inBufferCount < IN_BUFFER_SIZE) {

addr = getNextVirtualAddress(addr);

// Write the next virtual address. Be careful to synchronize

// appropriately with the address translation thread.

pthread_mutex_lock(&inBufferMutex);

inBuffer[inBufferCount] = addr;

inBufferCount++;

pthread_mutex_unlock(&inBufferMutex);

addressCount--;

} else {

// The buffer is full. Yield to wait for it to empty.

sched_yield();

}

}

// Mark that address generation is done.

addressGenerationDone = true;

pthread_exit(NULL);

}

int translateAddress(int addr)

{

// maybe FIFO as the easiest to implementA????1FIFO would

// require a queue of page frames.

return 0;

}

void* doAddressTranslation(void* pArg)

{

int addr;

int physAddr;

ofstream outputFile;

ostream* pOutput;

outputFile.open("ilab6_output.txt");

if (outputFile.is_open()) {

pOutput = &outputFile;

} else {

cout << "Error opening ilab6_output.txt, using standard output"

<< endl;

outputFile.close();

pOutput = &cout;

}

*pOutput << "Virtual -> Physical" << endl

<< "--------------------" << endl;

// Keep translating addresses until none are left.

while (!addressGenerationDone) {

if (inBufferCount <= 0) {

// There are no addresses to read. Yield to wait for more.

sched_yield();

}

while (inBufferCount > 0) {

// Read the next virtual address. Be careful to synchronize

// appropriately with the address generation thread.

pthread_mutex_lock(&inBufferMutex);

inBufferCount--;

addr = inBuffer[inBufferCount];

pthread_mutex_unlock(&inBufferMutex);

// Translate the virtual address.

physAddr = translateAddress(addr);

*pOutput << "0x" << hex << setfill('0') << setw(4) << addr

<< " -> 0x" << hex << setfill('0') << setw(4) << physAddr

<< endl;

}

}

if (outputFile.is_open()) {

outputFile.close();

}

pthread_exit(NULL);

}

void* doStatistics(void* pArg)

{

pthread_t* pAddrTranThread = (pthread_t*)pArg;

// Wait until address translation thread exits.

pthread_join(*pAddrTranThread, NULL);

cout << "Total Number of Page Faults = " << numberOfPageFaults << endl;

pthread_exit(NULL);

}

int main(int argc, char* argv[])

{

pthread_attr_t attrs;

pthread_t addrGenThread;

pthread_t addrTranThread;

pthread_t statsThread;

// random number generator. If your getNextVirtualAddress

// function does not generate random numbers, the following line can be

// removed.

srand(time(NULL));

pthread_mutex_init(&inBufferMutex, NULL);

pthread_attr_init(&attrs);

pthread_attr_setdetachstate(&attrs, PTHREAD_CREATE_JOINABLE);

// Create three joinable threads, one for each component of the iLab.

pthread_create(&addrGenThread, &attrs, doAddressGeneration, NULL);

pthread_create(&addrTranThread, &attrs, doAddressTranslation, NULL);

pthread_create(&statsThread, &attrs, doStatistics, &addrTranThread);

pthread_attr_destroy(&attrs);

pthread_join(addrGenThread, NULL);

pthread_join(addrTranThread, NULL);

pthread_mutex_destroy(&inBufferMutex);

pthread_join(statsThread, NULL);

// Once all the component threads have exited, the program can exit.

return 0;