C++
mike05
prog-04.zipprog-04/pagestream.sim
2 3 2 1 5 2 4 5 3 2 5 2
__MACOSX/prog-04/._pagestream.sim
prog-04/pagestream-lru-3.res
__MACOSX/prog-04/._pagestream-lru-3.res
prog-04/pagestream-lru-4.res
__MACOSX/prog-04/._pagestream-lru-4.res
prog-04/prog-04.pdf
Programming Assignment #4
CSci 430 Summer I 2019
Dates: Assigned: Monday June 24, 2019 Due: Friday June 28, 2019 (before Midnight)
Objectives:
• Better understand page replacement memory management properties through implementation of page replacement schemes.
• Implement basic page replacement schemes, such as least recently used and first-in-first-out (FIFO)
• Practice C/C++ usage and implementation of queues and stacks needed for memory management algorithms.
• Be able to compare, contrast and understand the relative performance of different replacement schemes.
Description:
In programming assignment #4 you are to write a simulation of a page replacement memory management system. You will be implementing least recently used (LRU) and first-in-first-out (FIFO) page replacement schemes (Chapter 8, pg 369).
Your program should read from a file to get information about the se- quence of page faults that occur. I will provide a simple example of such a text file. It consists simply of one integer value per line, which represent a sequence of page faults that occur in the simulation. For example:
1
----------- Begin Input File pagestream.txt -------- 2 3 2 1 5 2 4 5 3 2 5 2 ------------ End Input File -------------------------
represents the sequence of page address faults/requests for the Figure 8.15 example from our text book.
Your program should read 3 pieces of information from the command line: simulation file name, replacement scheme [lru or fifo], and the number of physical frames in memory. For example:
$ p3.exe pagestream.sim lru 3
To get you started, I have included a main() function and a main event loop in a file called p3-start.cpp, that can open and read in the page stream file into an array. Your main job is to implement the least recently used (LRU )and first-in-first-out FIFO page replacement algorithms. The FIFO page replacement should be the simplier of the two, so I would suggest you get that scheme working first. In FIFO, of course, when there is a page reference ’miss’, you simply need to keep a pointer or index into your frames indicating the next physical frame number that should be replaced.
Your program should take the indicated stream of page addresses (a file name) as the first parameters. The second parameter indicates the total number of frames that the system is simulating (in the above example this is 3, the same as the example shown in Figure 8.15). Your implementa- tion should be able to simulate systems with up to 10 physical frames at a maximum.
The output for your simulation should be formatted in exactly the fol- lowing format. To get exact output format and correct answers for the include pagestream.sim input file, look at the results in the zip file called pagestream-lru-3.out and pagestream-fifo-3.out.
2
Time: 0 Page: 2 Frame1: 2 Frame2: 0 Frame3: 0 Hit ratio: 0 / 12 (0)
Time: 1 Page: 3 Frame1: 2 Frame2: 3 Frame3: 0 Hit ratio: 0 / 12 (0)
Time: 2 Page: 2 Frame1: 2 Frame2: 3 Frame3: 0 Hit ratio: 1 / 12 (0.0833333)
etc.
To interpret, for each page reference in the pagestream, you will print out the time, the page that was referenced (time starts at 0), the Page reference that was made at that time, and the state of the system frames after that page is processed.
If you use the pagestream sequence from figure 8.15 with a system frame size of 3 you should be able to reproduce the LRU and FIFO results shown. I have given you example correct outputs for both FIFO and LRU page replacement, for systems with both 3 and 4 physical frames of memory. Use these correct example outputs to test that your implementation is working correctly. I will test your program using different pagestream sequences and different system frame sizes, so make sure you thoroughly test your algorithm yourself before submitting.
3
__MACOSX/prog-04/._prog-04.pdf
prog-04/p4-start.cpp
prog-04/p4-start.cpp
/**
@file
p4-start.c
*
*
@author
Your Name
*
@assg
Programming Assignment #4
*
@date
March 8, 2019
*/
#include
<
stdlib
.
h
>
#include
<
iostream
>
#include
<
fstream
>
#include
<
string
>
using
namespace
std
;
// guarantee simulations have no more than this number of page references
// and we guarantee that you don't need to simulate a memory of more
// than this number of physical pages
const
int
MAX_PAGE_REFERENCES
=
50
;
const
int
MAX_PHYSICAL_PAGES
=
10
;
/** fifo page replacement simulation
* Perform first-in first-out (FIFO) page replacement simulation.
*
*
@arg
framesize The number of physical frames of memory to simulate.
*
@arg
numref The number of page references in the simulated page address
* stream. There should be pagestream[0] to pagestream[numref-1]
* pages in the pagestream.
*
@arg
pagestream An array of integers. The value indicates a references
* page, and the index is the time when the page was referenced.
*/
void
fifo
(
int
framesize
,
int
numref
,
int
*
pagestream
)
{
// implement fifo (first-in-first-out) page replacement here
// an example of stepping through time and the pagestream to get
// you going
for
(
int
time
=
0
;
time
<
numref
;
time
++
)
{
cout
<<
"Time: "
<<
time
<<
endl
;
cout
<<
"Page: "
<<
pagestream
[
time
]
<<
endl
;
cout
<<
endl
;
}
}
/** lru page replacement simulation
* Perform least recently used (LRU) page replace simulation.
*
*
@arg
framesize The number of physical frames of memory to simulate.
*
@arg
numref The number of page references in the simulated page address
* stream. There should be pagestream[0] to pagestream[numref-1]
* pages in the pagestream.
*
@arg
pagestream An array of integers. The value indicates a references
* page, and the index is the time when the page was referenced.
*/
void
lru
(
int
framesize
,
int
numref
,
int
*
pagestream
)
{
// implement lru (least recently used) page replacement here
// an example of stepping through time and the pagestream to get
// you going
for
(
int
time
=
0
;
time
<
numref
;
time
++
)
{
cout
<<
"Time: "
<<
time
<<
endl
;
cout
<<
"Page: "
<<
pagestream
[
time
]
<<
endl
;
cout
<<
endl
;
}
}
/** Load page references from file
* Load the stream of simulated page references from the indicate file.
* return the references in a simple array of integers.
*
*
@param
simfilename The name of the file to open and read page references
* from.
*
@param
pagestream Should be a pointer to an array of integers. The array
* is filled with the page references on return. The index of each
* reference indicates time when the page references occurs in
* simulation.
*
@returns
int The number of page references in the page stream.
*/
int
loadPageStream
(
char
*
simfilename
,
int
*
pagestream
)
{
ifstream pagestreamfile
(
simfilename
);
int
pageref
;
int
time
;
// If we can't open file, abort and let the user know problem
if
(
!
pagestreamfile
.
is_open
())
{
cout
<<
"Error: could not open page simulation file: "
<<
simfilename
<<
endl
;
exit
(
1
);
}
// Load simulated page references into integer array
time
=
0
;
while
(
!
pagestreamfile
.
eof
())
{
pagestreamfile
>>
pageref
;
pagestream
[
time
]
=
pageref
;
time
++
;
pagestreamfile
>>
ws
;
// extract newlines from end of line
}
return
time
;
}
/** Main entry point of simulator
* The main entry point of the page replacement simulator. Process
* command line arguments and call appropriate simulation. We expect
* three command line arguments: pageref.sim [fifo|lru] framesize
*
*
@param
argc The argument count
*
@param
argv The command line argument values. We expect argv[1] to be the
* name of a file in the current directory holding page file
* references, argv[2] to indicate [fifo|lru] and argv[3] to be
* an integer indicating size of memory in frames.
*/
int
main
(
int
argc
,
char
**
argv
)
{
int
framesize
=
0
;
int
pagestream
[
MAX_PAGE_REFERENCES
];
int
numref
;
string scheme
;
// If not all parameters not provided, abort and let user know of problem
if
(
argc
!=
4
)
{
cout
<<
"Usage: "
<<
argv
[
0
]
<<
" pageref.sim [lru|fifo] framesize"
<<
endl
;
exit
(
1
);
}
// load page stream and parse command line arguments
numref
=
loadPageStream
(
argv
[
1
],
pagestream
);
scheme
.
assign
(
argv
[
2
]);
framesize
=
atoi
(
argv
[
3
]);
// perform simulation of indicated replacement scheme
if
(
scheme
==
"lru"
)
{
lru
(
framesize
,
numref
,
pagestream
);
}
else
if
(
scheme
==
"fifo"
)
{
fifo
(
framesize
,
numref
,
pagestream
);
}
else
{
cout
<<
"Error: unknown page replacement scheme: "
<<
scheme
<<
endl
;
exit
(
1
);
}
}
__MACOSX/prog-04/._p4-start.cpp
prog-04/pagestream-fifo-3.res
__MACOSX/prog-04/._pagestream-fifo-3.res
prog-04/pagestream-fifo-4.res
