1 PROJECT 4 GRADING ADVICE
2 ========================
4 This file contains advice for grading project 4. General advice for
5 Pintos grading is in README, which you should read first.
7 INDEXED AND EXTENSIBLE FILES
8 ============================
12 struct inode_disk should change here. Many students just present
13 the new version instead of the detailed changes, which is fine
14 because most of it changes. The typical result looks something
19 disk_sector_t sectors[SECTOR_CNT]; /* Sectors. */
20 enum inode_type type; /* FILE_INODE or DIR_INODE. */
21 off_t length; /* File size in bytes. */
22 unsigned magic; /* Magic number. */
27 - The "sectors" array might be divided into separate arrays or
28 scalars devoted to direct, indirect, and doubly indirect
29 blocks. That's fine, and arguably cleaner.
31 - The "magic" member should be retained, but some groups might
32 drop it because they don't understand its purpose. That's
35 - The "type" member might have been added to directory entries
36 instead, or its addition might be mentioned in the
37 subdirectories section instead, because it's more relevant
38 there. If it's missing, look in B1. If it's not mentioned
39 either place, take off points.
41 Many groups name "type" something like "is_dir".
43 - The "start" member should be dropped. If it's still there,
46 - The "unused" array should be dropped, because if there's
47 extra space then it can be used for more direct blocks, etc.
48 If there's an unused array that's between 0 and 3 bytes (not
49 elements) long, then that's fine--probably they needed to
50 pad out some "char" or "short" elements to make the whole
51 thing exactly 512 bytes long. Otherwise, take off points.
53 Most groups add a lock to struct inode that synchronizes file
58 Most groups use 123 or 124 direct blocks, 1 indirect block, and 1
59 doubly indirect block, which yield the following maximums:
61 123 direct: (123 + 128 + 128**2) * 512 = 8,517,120 bytes = 8,317.5 kB
62 124 direct: (124 + 128 + 128**2) * 512 = 8,517,632 bytes = 8,318 kB
64 Occasionally a group thinks that the "max file size" includes
65 metadata size. The metadata in either situation above would be of
68 (1 + 1 + (1 + 128)) * 512 = 67,072 bytes = 65.5 kB
70 so that the totals would then be
72 123 direct: 8,517,120 + 67,072 = 8,584,192 bytes = 8,383 kB
73 124 direct: 8,517,632 + 67,072 = 8,584,704 bytes = 8,383.5 kB
75 Check that their math is correct if it doesn't match one of these.
77 Students must "show their work" or at least give enough numbers in
78 A1, A2, or A6 to allow you to check their work. You shouldn't
79 have to look at the source code to check it. Take off points if
82 Some students think that their design has 128 indirect blocks or
83 128 doubly indirect blocks. That's not true. Take off points.
84 (However, the blocks that the doubly indirect blocks point to are
85 indirect blocks in their own right. But in that case they would
86 normally have 129, not 128, because of the indirect block that the
87 inode points to directly.)
93 One important fact here is that Pintos files can grow but never
94 shrink. (Although deletion might be thought of as "shrinking" to
95 size 0, this can never be observed by a user process, because the
96 file's contents are retained as long as a user process has it
101 1. The most common approach is to use a lock to make extending
102 a file into a critical section. A write first checks the
103 length of the file. A write that won't extend the file
104 doesn't need to take the lock and can proceed immediately.
105 A write that extends the file takes the lock.
107 The lock should be per-inode (per-file). Take off points
110 There are some subtleties to this approach. The first is
111 that checking and updating the length of the file has to be
112 synchronized. If two writers try to write 10 bytes
113 starting at the current EOF, they can both see the old file
114 length. Thus, the file length must be checked again after
115 obtaining the lock, e.g.
117 if (final_ofs > disk_inode->length) // First check.
119 lock_acquire (&inode->grow_lock);
120 if (final_ofs > disk_inode->length) // Second check.
124 lock_release (&inode->grow_lock);
127 Students who use this scheme must mention how they handle
128 this problem. If they don't, take off points.
130 An even more subtle problem is that of race-free reads of
131 the "length" member of disk_inode. There ideally should be
132 some locking around access to it, but a call to barrier()
133 or use of volatile would be sufficient also. However,
134 reading a single integer is normally atomic on modern
135 machines, so we'll just ignore this problem.
137 2. Use sector-based locking in the buffer cache. In this
138 approach, the buffer cache supports shared and exclusive
139 locking of sectors. To read or write a file normally can
140 use a shared lock on the inode sector; extending a file
141 requires an exclusive lock on the inode sector.
143 3. If all file accesses (or all write accesses) require a lock
144 and hold it during the entire read or write, then that's a
145 trivial solution, but it doesn't meet the requirements in
146 the Synchronization section of the assignment: "Multiple
147 reads of a single file must be able to complete without
148 waiting for one another. When writing to a file does not
149 extend the file, multiple processes should also be able to
150 write a single file at once." Take off points.
152 This is not the same as taking a lock across a couple of
153 lines of code to check or set a variable in a race-free
154 way, etc. That's fine.
158 The typical solution to A4 depends on the solution chosen for A3:
160 1. a. Typically, the process extending the file doesn't update
161 the file's length until the extension is fully
162 completed. Thus, before the extension is complete,
163 readers won't see that the file's length has increased
166 b. Another solution is to make reads past end-of-file wait
167 for file extension to be completed, by making read past
168 end-of-file take the lock needed to extend the file.
171 2. A process that wants to read the file will need to get a
172 shared lock on the inode sector, which it can't get until
173 the extending process has released its exclusive lock.
174 Thus, this approach will be correct as long as the
175 exclusive lock on the inode is held until the file
176 extension is complete.
178 3. This approach trivially solves the problem but doesn't
179 fulfill the synchronization requirements. Take off points.
183 Many answers are implicitly predicated on the fact that Pintos
184 locks and semaphores have fair, first-come, first-served queuing.
185 Most students don't mention it, though.
187 The typical answer depends on the answer to A4:
189 1. a. Readers, and writers not at end-of-file, don't have to
190 wait, so they have no fairness issues. Writers that
191 extend a file are waiting on a lock, which queues their
192 extensions fairly. After a file extension is complete,
193 subsequent reads and writes within the new file length
194 are completed fairly because there's no need for them to
197 b. Essentially the same as 1a, except that readers beyond
198 end-of-file are treated like writers beyond end-of-file.
199 Because the lock queuing is fair, readers get serviced
202 2. Fairness here depends on the fairness of locking in the
203 buffer cache. The group must explain how the buffer cache
204 provides fair locking. Generally, two rules are needed to
207 - A rule to prevent readers from waiting for writers
208 forever. For example: when the exclusive holder of
209 a lock releases it, any processes waiting for a
210 shared lock are preferred over processes waiting for
213 - A rule to prevent writers from waiting for readers
214 forever. For example: if one or more processes hold
215 a shared lock, and one or more processes are waiting
216 for an exclusive lock, then no more processes may
217 obtain a shared lock until at least one process has
218 obtained an exclusive lock.
220 The group must explain both rules; take off points
223 3. This approach trivially solves the problem but doesn't
224 fulfill the synchronization requirements. Take off points.
226 There should be no use of a timer to ensure fairness. That's not
229 Fairness is not a matter of what kind of file access is "rare" or
230 "common". Take off points from groups that argue, e.g., that
231 their implementation is unfair if a file is being extended but
232 that file extension happens "rarely".
236 I haven't seen a group try to use a non-multilevel index structure
237 yet. Such a choice would need good rationale.
239 Good answers include mention of advantages of multilevel indexes:
241 - Both random and sequential access are efficient.
243 - Large files can be supported, without imposing a penalty on
244 efficiency of small files.
246 - Works in presence of external fragmentation.
248 - Fast access to data for small files.
250 Some answers mention some disadvantages of multilevel indexes:
252 - It takes up to 3 disk accesses to find a data block in a big
253 file (although caching helps with sequential access
256 - Fixed maximum file size.
258 - High overhead for small files.
280 struct inode should drop inode_disk; if it doesn't, then take off
281 points. This might have been mentioned in A1 instead.
projects / pintos-anon / blob