Programming Assignment III

Due on Friday, April 26, 2019 @ 11pm

100 points

Objectives

Implement a virtual memory simulator in C.

Introduction

Suppose a virtual memory system has the following specifications:

The physical address space is 24-bit.
Virtual address is 32-bit.
There is no TLB nor cache.
The page table is stored in a separate space rather than in the physical address space.
Page size is 4K.
Each item is an address trace file has a form of a 0x1ffffff8, where a is either l for load or s for store, and 0x1ffffff8 is a 32-bit virtual address in hexadecimal. Therefore, s 0x1ffffec8 indicates storing data to address 0x1ffffec8. Address trace files are available here. Or, you may copy it to your local directory from /classes/cs4411.ck/common/traces.tar.gz.
You may assume that the addresses in an address trace file are generated from executing a single process.
Use various page replacement algorithms to simulate virtual memory page-in and page-out. Note that from "l/s" you should be able to know whether a page has been referenced and/or modified.
For each page replacement algorithm, calculate the total number of references, the total number of page faults, hit ratio and miss ratio. Other additional statistics will be discussed in each page replacement algorithm.
For each address trace file, use a a plot system to generate a diagram as follows:

Here, the horizoontal axis indicates execution time from 0 to maximum. You may assume each address is executed at a unique time, and, as a result, the sequence 0, 1, 2, 3, .... is execution time. The vertical axis is memory address. You may use page number (rather than page frame number) as memory address.

Page Replacement Algorithms

The following page replacement algorithms have to be implemented.

FIFO: Simulate the First-In-First-Out page replacement algorithm.
LRU: Simulate the Least Recently Used page replacement algorithm.
MIN: Simulate the Optimal page replacement algorithm MIN. Note that the optimal algorithm requires scanning the address trace forward.
2CHANCE: Simulate the Second Chance.
CLOCK: Simulate the Clock algorithm.

Do the above again for a 20-bit physical address (i.e., less number of page frames). Does any of the above algorithms exhibit Belady Anomaly? Report this in details in your report.

Submitting Your Assignment

The following is a guideline for submission:

For each trace file, do the following:
1. Generate a time-space diagram with your favorite plotting program.
2. For each page replacement algorithm, run it under 20-bit address space and 24-bit address space. Report the number of address accesses, the number of page faults, hit ratio, and miss ratio.
3. Report any Belady Anomaly, and indicate where this anomaly occurs.
I suggest you write five programs, FIFO.c, LRU.c, MIN.c, 2CHANCE.c and CLOCK.c, and provide the needed Makefile for compiling all five programs. Note that you may add additional files, but the main() has to be named as indicated.
A README text file explains how to compile and execute your programs. In particular, provide a detailed account of and explain the meaning of the output of each program.
A report file report.pdf in PDF format. Your report should include your results and findings of your investigation. In particular, for each address trace file, present the time-space diagram, discuss any pattern you may find from this diagram (i.e., locality and trasition), and present the results under a page replacement algorithm with 20-bit physical address and 24-bit physical address. Also include any possible Belady anomaly.
Your report should include the following components:
1. An introduction discussing the content of this report
2. A description of the implementation of each page replacement algorirhtm, in particular, data structures, implementation, anything important, etc.
3. A discussion of your results and findings.
4. A conclusion section that summarizes all of your findings.
All of your program files should be in a tar ball and named as prog3.tar.gz. Therefore, the needed files are prog3.tar.gz, report.pdf and README.

Click here to see how your program will be graded.