1 PROJECT 3 GRADING ADVICE
2 ========================
4 This file contains advice for grading project 3. General advice for
5 Pintos grading is in README, which you should read first.
12 This should include a description of the students' supplemental
13 page table. There are two common approaches:
15 - Hash table: a per-process hash table indexed on virtual
16 address. The hash table elements normally include:
20 * Location. At any given time, this is one of:
24 . File and offset (and in many implementations, a byte
25 count between 0 and 4,096 also, with the remaining
32 * Read-only or read/write flag.
34 * Often, a pointer back to the owning thread or page
35 directory, so one of these structures can be used to
36 evict its page (it must be possible to find the page's
37 PTE to mark it not-present before it can be evicted).
39 Students should mention that they added a hash table member
42 Students come up with various ways to break this table into
45 - Modify the page table implementation: 31 bits of each PTE
46 for a page that is not in a frame are available for use.
47 Some groups use these to point to the supplemental page
50 That still leaves us needing a way to find the supplemental
51 page table entry for a page that is in a frame. We can do
52 that with an array that has one entry for each physical
53 page, indexing it based on the frame number for the frame
54 pointed to by the PTE.
56 Some hybrid approaches are also possible.
58 A1 might also describe the frame table, swap table, and file
59 mapping table, but most students leave those for B1. Either way
64 The answer generally boils down to traversing the data structure
65 from A1. The answer should describe code, not data; the data
66 structures have already been explained in A1.
70 The most common answer is "We always access user data through the
71 user virtual address," which is simple and correct. Another
72 correct answer is "We check accessed and dirty bits for both user
73 and kernel virtual addresses."
75 If sharing is implemented, then the answer must explain how
76 accessed and dirty bits are coordinated. Sharing excludes the
77 possibility of avoiding aliasing.
79 Look for confusion between user and kernel addresses here. Unless
80 sharing is implemented, each user virtual address aliases exactly
81 one kernel virtual address.
83 Watch for the implication that an approximate idea of the dirty
84 status of a page is okay. It's not--if the OS thinks a page is
85 clean, but it's actually dirty, then it could throw away changes
86 without writing them back.
90 A typical answer is along these lines:
92 First we try to get a free frame with palloc_get_page(), which
93 does its own internal synchronization. If it succeeds, we're
96 Otherwise, we grab a lock needed to perform eviction. The
97 lock prevents other threads from trying to evict a page at the
102 If the students used a hash table, they should identify some of
103 the benefits of a hash table relative to alternative data
104 structures: an array would be sparse and thus too big, a list
105 would be slow to search, and so on. Mentioning that a hash table
106 has O(1) average lookup time is also good.
108 If the students modified the existing page tables, then they
109 typically explain that this saves memory because the PTEs are
110 needed anyway, and that lookup through the page table is fast.
112 Students may mention that making their data structure
113 thread-specific reduces the need for locking, or that it makes it
114 easier to find all the pages that belong to a given process (for
115 cleanup when a process dies).
117 PAGING TO AND FROM DISK
118 =======================
122 Expect to see the following global data:
126 - A lock for the swap bitmap. Sometimes swap synchronization
127 is handled by another lock, but sometimes it's forgotten
132 - A pointer to a frame, used for the clock hand. Not always
135 - A lock on the frame list.
137 There may be some structure definitions to go with the above.
139 Some of the data structures we expect to see here might have
140 already been described in A1.
144 This is normally a description of the second-chance or "clock"
145 algorithm, which sweeps around the list of frames looking for an
146 unset accessed bit, resetting those that are set as it goes.
148 Some students implement a preference to evict clean pages, to
149 reduce the needed I/O. Others use two clock hands, one that
150 checks accessed bits and another ahead of the checking hand that
151 resets bits. Those are nice touches.
153 The dirty bit should *not* be reset as part of the clock
154 algorithm. That will cause data corruption. Take off points if
155 the students say they do so.
157 Some students take the "clock" algorithm name too literally and
158 implement a thread that periodically resets all the accessed bits
159 in the system. That's bad: it's not any more useful to have all
160 the accessed bits unset than it is to have all of them set. It's
161 not a substitute for resetting accessed bits when we need a page,
162 either. If the students do this without providing good rationale,
167 This is a new question for this quarter, so it's hard to say what
168 the answers will look like.
170 I expect that the students will say that they reset the present
171 bit in the PTE for the page that was evicted and that they adjust
172 the supplementary page table for the page to point to its new
177 The heuristic should, roughly, check that the following are true:
181 - PHYS_BASE - STACK_LIMIT <= FA < PHYS_BASE
183 where FA is the faulting address, ESP is the user stack pointer,
184 PHYS_BASE is the macro defined in vaddr.h, and STACK_LIMIT is the
185 maximum size of the stack.
187 The first condition ensures that the fault is actually above the
188 stack pointer, allowing 32 bytes to allow the PUSHA instruction to
189 work. Deduct points if their condition allows more than 32 bytes;
190 the documentation is explicit.
192 The second condition ensures that the fault is in a reasonable
193 place for the stack. It prevents the stack from growing above
194 STACK_LIMIT in size. It also prevents access to kernel virtual
197 STACK_LIMIT should be at least 1 MB. Most students choose 8 MB.
199 Some students think that the "struct intr_frame" that the kernel
200 sees is pushed on the user stack. That's wrong; deduct points.
204 The answer must explain how the submitted code prevents one of the
205 4 conditions for deadlock from occurring. Typically this is by
206 making sure that locks are always acquired in a particular order.
209 - "Terminal" locks, that is, locks under which no further
210 locks are acquired. This is common, for example, for the
211 lock on the swap bitmap.
213 - Ranking locks: students describe the order in which locks
216 Wording that attempts to claim that the conditions for deadlock
217 are "rare" or that the window in which deadlock can occur is
218 "short" are not acceptable. In a proper design, deadlock is
219 impossible, not just rare. Deduct points.
223 This is a two-part question, and students must answer both parts.
225 Usually, a lock protects the page. To evict or to fault in a page
226 requires holding the lock. P holds the lock during the entire
227 eviction process, so Q has to wait for it to be released if it
228 wants to fault it back in.
230 To prevent Q from accessing or modifying its page, P marks its PTE
231 not-present before it starts evicting it, but *after* it acquires
232 the page lock. (If it marked it not-present before acquiring the
233 lock, it would race with Q faulting on the page and trying to
236 Disabling interrupts is not required anywhere. Deduct points from
237 solutions that disable interrupts.
241 Several possible answers:
243 - Same as B6: hold the page's lock while it is being read in,
244 so Q cannot acquire it until it's finished.
246 - Don't add the new page to the list of frames that are
247 candidates for eviction until its page-in is complete.
249 - Mark frames with a "non-evictable" bit while they're being
254 Several possible answers:
256 - Pre-lock all the pages that the system call will access,
257 then unlock them when the system call completes. There must
258 be a discussion of how to avoid deadlock among processes
259 that, among them have all of the user pool locked, and want
262 - Page fault in kernel.
264 - Acquire a global lock needed to evict pages. There should
265 be some additional explanation of how the system call makes
266 sure that those pages are in main memory in the first place.
270 Watch out for claims about deadlock here. Wording that attempts
271 to claim that the conditions for deadlock are "rare" or that the
272 window in which deadlock can occur is "short" are not acceptable.
273 In a proper design, deadlock is impossible, not just rare. Deduct
274 points. (This deduction is listed under B5 because similar claims
282 This usually includes a data structure that represents a mapped
283 file and adds a list of them to "struct thread". Sometimes,
284 students add a new counter for a mapid_t, analogous to the
285 counters added for file descriptors in project 2. The same
286 criteria apply as did in that project.
290 Usually the answer is basically "We reused lots of existing data
291 structures, but we had to deal with a few differences."
293 For some reason, students sometimes talk about permanently
294 assigning or pre-reserving memory mapped files to swap slots or to
295 frames in physical memory here. That's incorrect. The assignment
296 is explicit that mappings should be lazily loaded and written back
297 to their files, not to swap.
301 Basically, *each* page (not just the first) in the new mapping has
302 to be checked as to whether it overlaps any existing segment.
304 There should be some comment about interaction between stack
305 expansion and memory mapped files.
307 Memory mappings are per-process, so mappings in two different
308 processes do not "overlap".
312 Usually, this says how the similar bits of the implementation are
313 shared and the different bits are not. Just make sure it's a
314 reasonable rationale.