Simulator Requirements In a C program, build a simulator that reads a memory tra
ID: 3722892 • Letter: S
Question
Simulator Requirements
In a C program, build a simulator that reads a memory trace and simulates the action of a virtual memory system with a single level page table. Your simulator should keep track of what pages are loaded into memory. As it processes each memory event from the trace, it should check to see if the corresponding page is loaded. If not, it should choose a page to remove from memory.
If the page to be replaced is “dirty” (that is, previous accesses to it included a Write access), it must be saved to disk. Finally, the new page is to be loaded into memory from disk, and the page table is updated. Assume that all pages and page frames are 4 KB (4096 bytes).
Of course, this is just a simulation of the page table, so you do not actually need to read and write data from disk. Just keep track of what pages are loaded. When a simulated disk read or write must occur, simply increment a counter to keep track of disk reads and writes, respectively.
Implement the following page replacement algorithms:
• LRU.
• FIFO.
• VMS' second chance page replacement policy.
Structure and write your simulator in any reasonable manner. You may need additional data structures to keep track of which pages need to be replaced depending on the algorithm implementation. Think carefully about which data structures you are going to use and make a reasonable decision.
You need to follow strict requirements on the interface to your simulator. The simulator (called memsim) should take the following arguments:
memsim
The first argument gives the name of the memory trace file to use. The second argument gives the number of page frames in the simulated memory. The third argument gives the page replacement algorithm to use. The fourth argument may be "debug" or "quiet" (explained below.)
If the fourth argument is "quiet", then the simulator should run silently with no output until the very end, at which point it should print out a few simple statistics like this (follow the format as closely as possible):
total memory frames: 12
events in trace: 1002050
total disk reads: 1751
total disk writes: 932
If the fourth argument is "debug", then the simulator should print out messages displaying the details of each event in the trace. You may use any format for this output, it is simply there to help you debug and test your code.
Use a separate functions for each algorithm, i.e.: your program must declare the following high level functions: lru(), fifo() and vms().
Memory Traces
You are provided with memory traces to use with your simulator. Each trace is a real recording of a running program, taken from the SPEC benchmarks. Real traces are enormously big: billions and billions of memory accesses. However, a relatively small trace will be more than enough to keep you busy. Each trace only consists of one million memory accesses taken from the beginning of each program.
The traces are:
• gcc.trace
• swim.trace
• bzip.trace
• sixpack.trace
Each trace is a series of lines, each listing a hexadecimal memory address followed by R or W to indicate a read or a write. For example:
0041f7a0 R
13f5e2c0 R
05e78900 R
004758a0 R
31348900 W
Note, to scan in one memory access in this format, you can use fscanf() as in the following:
unsigned addr;
char rw;
...
fscanf(file,"%x %c",&addr,&rw);
Explanation / Answer
Answer :
LRU Page Replacement :
#include<stdio.h>
int findLRU(int time[], int n){
int i, minimum = time[0], pos = 0;
for(i = 1; i < n; ++i){
if(time[i] < minimum){
minimum = time[i];
pos = i;
}
}
return pos;
}
int main()
{
int no_of_frames, no_of_pages, frames[10], pages[30], counter = 0, time[10], flag1, flag2, i, j, pos, faults = 0;
printf("Enter number of frames: ");
scanf("%d", &no_of_frames);
printf("Enter number of pages: ");
scanf("%d", &no_of_pages);
printf("Enter reference string: ");
for(i = 0; i < no_of_pages; ++i){
scanf("%d", &pages[i]);
}
for(i = 0; i < no_of_frames; ++i){
frames[i] = -1;
}
for(i = 0; i < no_of_pages; ++i){
flag1 = flag2 = 0;
for(j = 0; j < no_of_frames; ++j){
if(frames[j] == pages[i]){
counter++;
time[j] = counter;
flag1 = flag2 = 1;
break;
}
}
if(flag1 == 0){
for(j = 0; j < no_of_frames; ++j){
if(frames[j] == -1){
counter++;
faults++;
frames[j] = pages[i];
time[j] = counter;
flag2 = 1;
break;
}
}
}
if(flag2 == 0){
pos = findLRU(time, no_of_frames);
counter++;
faults++;
frames[pos] = pages[i];
time[pos] = counter;
}
printf(" ");
for(j = 0; j < no_of_frames; ++j){
printf("%d ", frames[j]);
}
}
printf(" Total Page Faults = %d", faults);
return 0;
}
c program to execute FIFO page substitution calculation :
i. Begin the procedure
ii. Proclaim the size as for page length
iii. Check the need of substitution from the page to memory
iv. Check the need of substitution from old page to new page in memory
v. Forma line to hold all pages
vi. Embed the page require memory into the line
vii. Check for terrible substitution and page blame
viii. Get the quantity of procedures to be embedded
ix. Show the qualities
x. Stop the procedure
PROGRAM:
#include<stdio.h>
int main()
{
int i,j,n,a[50],frame[10],no,k,avail,count=0;
printf(" ENTER THE NUMBER OF PAGES: ");
scanf("%d",&n);
printf(" ENTER THE PAGE NUMBER : ");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf(" ENTER THE NUMBER OF FRAMES :");
scanf("%d",&no);
for(i=0;i<no;i++)
frame[i]= -1;
j=0;
printf(" ref string page frames ");
for(i=1;i<=n;i++)
{
printf("%d ",a[i]);
avail=0;
for(k=0;k<no;k++)
if(frame[k]==a[i])
avail=1;
if (avail==0)
{
frame[j]=a[i];
j=(j+1)%no;
count++;
for(k=0;k<no;k++)
printf("%d ",frame[k]);
}
* In the Second Chance page substitution strategy, the competitor pages for expulsion are consider in a round robin matter, and a page that has been gotten to between back to back contemplations won't be supplanted.
The page supplanted is the one that - considered in a round robin matter - has not been gotten to since its last thought.
Usage:
Include "another opportunity" bit to every memory outline.
Each time a memory outline is referenced, set the "additional opportunity" bit to ONE (1) - this will give the edge another opportunity...
Another page read into a memory outline has the additional opportunity bit set to ZERO (0)
When you have to discover a page for expulsion, look in a round robin way in the memory outlines:
In the event that the additional opportunity bit is ONE, reset its additional opportunity bit (to ZERO) and proceed.
In the event that the additional opportunity bit is ZERO, supplant the page in that memory outline.
printf(" ");
}
printf("Page Fault Is %d",count);
return 0;
}