forked from LittlePetunia/CSC369
-
Notifications
You must be signed in to change notification settings - Fork 0
/
a2.html
332 lines (243 loc) · 14.7 KB
/
a2.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Assignment 2 - Page Tables and Replacement Algorithms</title>
<meta name="author" content="Karen Reid">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<!--
<link href="http://www.cdf.toronto.edu/~csc369h/winter/assets/themes/bootstrap/resources/bootstrap/css/bootstrap.min.css" rel="stylesheet">
<link href="http://www.cdf.toronto.edu/~csc369h/winter//assets/css/mystyle.css" rel="stylesheet">
-->
<link href="http://www.cdf.toronto.edu/~csc369h/winter//assets/css/stripped.css" rel="stylesheet">
<!--[if lt IE 9]>
<script src="http://www.cdf.toronto.edu/~csc369h/winter/assets/themes/bootstrap/resources/respond/Respond.min.js"></script>
<![endif]-->
<link href="/atom.xml" type="application/atom+xml" rel="alternate" title="Sitewide ATOM Feed">
<link href="/rss.xml" type="application/rss+xml" rel="alternate" title="Sitewide RSS Feed">
</head>
<body>
<nav class="navbar navbar-default" role="navigation">
<div class="container">
<div class="navbar-header">
<button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".navbar-ex1-collapse">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a class="navbar-brand" href="http://www.cdf.toronto.edu/~csc369h/winter/index.html">CSC369H: Operating Systems</a>
</div>
<div class="collapse navbar-collapse navbar-ex1-collapse">
<ul class="nav navbar-nav">
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/info.html" target="_blank">Syllabus</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/info.html">Syllabus</a></li>
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/lectures.html" target="_blank">Lectures</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/lectures.html">Lectures</a></li>
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/assignments.html" target="_blank">Assignments</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/assignments.html">Assignments</a></li>
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/tests.html" target="_blank">Tests</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/tests.html">Tests</a></li>
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/grades.html" target="_blank">Grades</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/grades.html">Grades</a></li>
<!-- <li><a href="http://www.cdf.toronto.edu/~csc369h/winter/feedback.html" target="_blank">Anonymous Feedback</a></li>
-->
<li><a href="http://www.cdf.toronto.edu/~csc369h/winter/feedback.html">Anonymous Feedback</a></li>
<!-- <li><a href="http://piazza.com/utoronto.ca/winter2015/csc369/home" target="_blank">Piazza</a></li>
-->
<li><a href="http://piazza.com/utoronto.ca/winter2015/csc369/home">Piazza</a></li>
<!-- <li><a href="https://markus.cdf.toronto.edu/csc369-2015-01/" target="_blank">MarkUs</a></li>
-->
<li><a href="https://markus.cdf.toronto.edu/csc369-2015-01/">MarkUs</a></li>
</ul>
</div>
</div>
</nav>
<div class="container">
<div class="page-header">
<h1>Assignment 2 - Page Tables and Replacement Algorithms </h1>
</div>
<div class="row">
<div class="col-xs-12">
<p><b>Due</b>: Friday, March 13 @ 10:00 p.m.</p>
<h2>Introduction</h2>
<p>You have three tasks in this assignment, which will be based on a
virtual memory simulator. The first task is to implement
virtual-to-physical address translation and demand paging using a
two-level page table. The second task is to implement four different
page replacement algorithms: <tt>FIFO</tt>, <tt>Clock</tt>, <tt>exact
LRU</tt>, and <tt>OPT</tt>. <strike>The third task is to create a memory
reference trace that illustrates Belady's anomoly.</strike>
</p>
<p>Before you start work, you should complete a set of readings about memory:<br />
<ul>
<li><a href="http://pages.cs.wisc.edu/~remzi/OSTEP/vm-paging.pdf">Paging: Introduction</a>
</ul>
<h2>Starter Code</h2>
The starter code for the simulator is found in the a2 directory of your repository. Running <code>svn up</code> in the top level of your working copy of you repository will fetch the code.
<h2>Requirements</h2>
<h3>Setup</h3>
<p> you will find the starter code in your repository already. Note that you may be generating some large trace files and must NOT commit any of the trace files that you generate to your repository or you will run into serious problems with disk quota. Most of the trace programs should be familiar to you from the Week 6 exercise. We have added a blocked version of matrix
multiply, <tt>blocked.c</tt> which should exhibit fewer page faults under at least some of the page replacement algorithms. The Makefile shows you exactly how to compile and run the traces. Note that it takes quite a while to run the trace collection.
</p>
<p> <em>Compile the trace programs and generate the traces.</em> </p>
<p>You may have noticed while doing the Exercise that the traces
generated by Valgrind are enormous since they contain every memory
reference from the entire execution. We have provided a program,
<tt>fastslim.py</tt> to reduce the traces by removing repeated
references to the same page that occur within a small window of each
other while preserving the important characteristics for virtual
memory simulation. (For example, a sequence of references to pages A
and B such as "ABABABABAB...AB" are reduced to just "AB".) The
<tt>runit</tt> script pipes the output of valgrind through this
program to create the reduced trace. If you wish, you can experiment
with <tt>fastslim.py</tt> to try omitting the instruction references
from the trace or using a smaller or larger window (<tt>fastslim.py
--help</tt>). You may also want to create traces from other programs, and you will definitely want to create small manual traces for testing.
</p>
<h3> Task 1 - Address Translation and Paging</h3>
<p><em>Implement virtual-to-physical address translation and demand paging using a two-level pagetable.
</em></p>
<p> The main driver for the memory simulator, <tt>sim.c</tt>, reads
memory reference traces in the format produced by the
<tt>fastslim.py</tt> tool from valgrind memory traces. For each line
in the trace, the program asks for the simulated physical address that
corresponds to the given virtual address by calling
<tt>find_physpage</tt>, and then reads from that location. If the
access type is a write ("M" for modify or "S" for store), it will also
write to the location. <em>You should read <tt>sim.c</tt> so that you understand how it works but you should not have to modify it.</em>.
</p>
<p> The simulator is executed as <tt>./sim -f <tracefile> -m
<memory size> -s <swapfile size> -a <replacement
algorithm> </tt> where memory size and swapfile size are the number
of frames of simulated physical memory and the number of pages that
can be stored in the swapfile, respectively. <em>The swapfile size
should be as large as the number of unique virtual pages in the trace,
which you should be able to determine easily.</em>
</p>
<p>There are four main data structures that are used:
<ol>
<li> <tt>char *physmem</tt>: This is the space for our simulated
physical memory. We define a simulated page size (and hence frame
size) of SIMPAGESIZE and allocate SIMPAGESIZE * "memory size" bytes
for <tt>physmem</tt>.</li>
<li><tt>struct frame *coremap</tt>: The <tt>coremap</tt> array
represents the state of (simulated) physical memory. Each element of
the array represents a physical page frame. It records if the
physical frame is in use and, if so, a pointer to the page table entry
for the virtual page that is using it.</li>
<li><tt>pgdir_entry_t pgdir[PTRS_PER_PGDIR]</tt>: We are using a
two-level page table design; the top-level is referred to as the page
directory, which is represented by this array. Each page directory
entry (<tt>pde_t</tt>) holds a pointer to a second-level page table
(which we refer to simply as page tables, for short). We use the
low-order bit in this pointer to record whether the entry is valid or
not. The page tables are arrays of page table entries (pte_t), which
consist of a frame number if the page is in (simulated) physical
memory and an offset into the swap file if the page has been written
out to swap. The format of a page table entry is shown here: <img
src="pte.jpg" alt="image of pte format" vspace=10px><br> Note that the
frame number and status bits share a word, with the low-order
PAGE_SHIFT bits (12 in our implementation) used for status (we only
have 4 status bits, but you can add more if you find it
useful). <em>Thus, for a given physical frame number (e.g. 7),
remember to shift it over to leave room for the status bits (e.g.,
<code>7 << PAGE_SHIFT</code>) when storing into the pte and to
shift it back when retrieving a frame number from a pte (e.g., <code>
p->frame >> PAGE_SHIFT</code>)</em>.
</li>
<li><tt>swap.c</tt>: The swapfile functions are all implemented
in this file, along with bitmap functions to track free and used space
in the swap file, and to move virtual pages between the swapfile and
(simulated) physical memory. <em>The <tt>swap_pagein</tt> and
<tt>swap_pageout</tt> functions take a frame number and a swap offset
as arguments. Be careful not to pass the frame field from a page table
entry (pte_t) directly, since that would include the extra status
bits.</em> The simulator code creates a temporary file in the current
directory where it is executed to use as the swapfile, and removes
this file as part of the cleanup when it completes. It does not,
however, remove the temporary file if the simulator crashes or exits
early due to a detected error. <em>You must manually remove the
<tt>swapfile.XXXXXX</tt> files in this case.</em>
</li>
</ol>
</p>
<p> To complete this task, you will have to write code in <tt>pagetable.c</tt>.
Read the code and comments in this file -- it should be clear where
implementation work is needed and what it needs to do. The <tt>rand</tt>
replacement algorithm is already implemented for you, so you can test your
translation and paging functionality independently of implementing the
replacement algorithms.
</p>
<h3>Task 2</h3>
<p><em>Using the starter code, implement each of the four different page replacement algorithms: FIFO, exact LRU, CLOCK (with one ref-bit), OPT.</em>
</p>
<p>You will find that you want to add fields to the <code>struct frame</code> for the different page replacement algorithms. You can add them in <code>pagetable.h</code>, but please label them clearly.</p>
<p>Once you're done implementing the algorithms, run all three programs from the provided <tt>traceprogs</tt>, plus a fourth program of your choosing with interesting memory reference behavior, using each of your algorithms (include rand as well). For each algorithm, run the programs on memory sizes 50, 100, 150, and 200. Use the data from these runs to create a set of tables that include the following columns. (Please label your columns in the following order,)
<ul>
<li>Hit rate</li>
<li>Hit count</li>
<li>Miss count</li>
<li>Overall eviction count</li>
<li>Clean eviction count</li>
<li>Dirty eviction count</li>
</ul>
</p>
<h3>Write up</h3>
<p>Include a file called README.txt or README.pdf that includes the following information.</p>
<ul>
<li>The tables prepared in Task 2
<li>One paragraph comparing the various algorithms in terms of the results you see in the tables.
<li>A second paragraph explaining the data you obtained for LRU as the size of memory increases.</li>
</ul>
<h2>Marking Scheme</h2>
<ul>
<li>Task 1: 35%</li>
<li>Task 2:
<ul>
<li>FIFO 5%</li>
<li>LRU 10%</li>
<li>CLOCK 10%</li>
<li>OPT 15%<br />
(must be able to run all traces in a reasonable amount of time)</li>
</ul>
</li>
<li>Tables 5%</li>
<li>Comparison paragraph 5% </li>
<li>LRU description 5%</li>
<li>Program readability and organization 10%</li>
</ul>
<h2>Submission</h2>
<p>The assignment will be committed to the <code>a2</code> directory in your svn repository. Don't forget to add and commit your updated simulator code and your <code>README</code> (in text or pdf format). We will pull the last commit before the deadline for marking.</p>
As for Assignment 1, after you have committed everything to your repo, but before your submission can be considered complete:
<ol>
<li>create an empty temporary directory in your cdf account (not in a subdirectory of your repo)</li>
<li>check out a copy of your repository for this assignment</li>
<li>verify that your README is included
<li>run <tt>make</tt> and ensure that you are able to build <tt>sim</tt> without any errors or warnings (This is an excellent way to verify that all files have been committed to the repo.)</li>
<li>run a few tests using the same traces you used to create the tables in your README, to ensure that your code behaves as you expect</li>
<li>congratulate yourself and enjoy a well-earned break, knowing that your strategy and hard work will pay off!</li>
</ol>
</div>
</div>
<hr>
<footer>
<p>
© 2015 Karen Reid
<span class="pull-right text-muted">
powered by
<a href="http://jekyllbootstrap3.tk" target="_blank" title="The Definitive Jekyll Blogging Framework">Jekyll-Bootstrap-3</a>
and <a href="http://getbootstrap.com" target="_blank">Twitter Bootstrap 3.0.3</a>
</span>
</p>
</footer>
</div>
<script src="http://www.cdf.toronto.edu/~csc369h/winter/assets/themes/bootstrap/resources/jquery/jquery.min.js"></script>
<script src="http://www.cdf.toronto.edu/~csc369h/winter/assets/themes/bootstrap/resources/bootstrap/js/bootstrap.min.js"></script>
</body>
</html>