3 * Reconsider command line arg style--confuses everyone.
7 * Add serial input support. Also, modify tests to redirect input from
8 /dev/null, to avoid stray keystrokes getting sent into the VM.
10 * Godmar: Introduce memory leak robustness tests - both for the
11 well-behaved as well as the mis-behaved case - that tests that the
12 kernel handles low-mem conditions well.
14 * Godmar: Another area is concurrency. I noticed that I had passed all
15 tests with bochs 2.2.1 (in reproducibility mode). Then I ran them
16 with qemu and hit two deadlocks (one of them in rox-*,
17 incidentally). After fixing those deadlocks, I upgraded to bochs
18 2.2.5 and hit yet another deadlock in reproducibility mode that
19 didn't show up in 2.2.1. All in all, a standard grading run would
20 have missed 3 deadlocks in my code. I'm not sure how to exploit
21 that for grading - either run with qemu n times (n=2 or 3), or run
22 it with bochs and a set of -j parameters. Some of which could be
23 known to the students, some not, depending on preference. (I ported
24 the -j patch to bochs 2.2.5 -
25 http://people.cs.vt.edu/~gback/pintos/bochs-2.2.5.jitter.patch but I
26 have to admit I never tried it so I don't know if it would have
27 uncovered the deadlocks that qemu and the switch to 2.2.5
30 * Godmar: There is also the option to require students to develop test
31 workloads themselves, for instance, to demonstrate the effectiveness
32 of a particular algorithm (page eviction & buffer cache replacement
33 come to mind.) This could involve a problem of the form: develop a
34 workload that you cover well, and develop a "worst-case" load where
35 you algorithm performs poorly, and show the results of your
36 quantitative evaluation in your report - this could then be part of
43 >> Describe a potential race in thread_set_priority() and explain how
44 >> your implementation avoids it. Can you use a lock to avoid this race?
46 I'm not sure what you're getting at here:
47 If changing the priority of a thread involves accessing the ready
48 list, then of course there's a race with interrupt handlers and locks
49 can't be used to resolve it.
51 Changing the priority however also involves a race with respect to
52 accessing a thread's "priority" field - this race is with respect to
53 other threads that attempt to donate priority to the thread that's
54 changing its priority. Since this is a thread-to-thread race, I would
55 tend to believe that locks could be used, although I'm not certain. [
56 I should point out, though, that lock_acquire currently disables
57 interrupts - the purpose of which I had doubted in an earlier email,
58 since sema_down() sufficiently establishes mutual exclusion. Taking
59 priority donation into account, disabling interrupts prevents the race
60 for the priority field, assuming the priority field of each thread is
61 always updated with interrupts disabled. ]
63 What answer are you looking for for this design document question?
67 >> Did any ambiguities in the scheduler specification make values in the
68 >> table uncertain? If so, what rule did you use to resolve them? Does
69 >> this match the behavior of your scheduler?
71 My guess is that you're referring to the fact the scheduler
72 specification does not prescribe any order in which the priorities of
73 all threads are updated, so if multiple threads end up with the same
74 priority, it doesn't say which one to pick. ("round-robin" order
75 would not apply here.)
81 One of my groups implemented priority donation with these data
82 structures in synch.cc:
86 struct list_elem elem; /* List element. */
87 int value; /* Item value. */
90 static struct value values[10];
91 static int start = 10;
92 static int numNest = 0;
94 In their implementation, the "elem" field in their "struct value" is
97 The sad part is that they've passed all tests that are currently in
98 the Pintos base with this implementation. (They do fail the additional
99 tests I added priority-donate-sema & priority-donate-multiple2.)
101 Another group managed to pass all tests with this construct:
105 struct thread *holder; /* Thread holding lock (for debugging). */
106 struct semaphore semaphore; /* Binary semaphore controlling access. */
107 //*************************************
109 int pri_delta; //Used for Priority Donation
110 /**************************************************/
113 where "pri_delta" keeps track of "priority deltas." They even pass
114 priority-donate-multiple2.
116 I think we'll need a test where a larger number of threads & locks
117 simultaneously exercise priority donation to weed out those
120 It may also be a good idea to use non-constant deltas for the low,
121 medium, and high priority threads in the tests - otherwise, adding a
122 "priority delta" might give - by coincidence - the proper priority for
125 - Godmar: Another thing: one group passed all tests even though they
126 wake up all waiters on a lock_release(), rather than just
127 one. Since there's never more than one waiter in our tests, they
128 didn't fail anything. Another possible TODO item - this could be
129 part a series of "regression tests" that check that they didn't
130 break basic functionality in project 1. I don't think this would
131 be insulting to the students.
135 - Get rid of rox--causes more trouble than it's worth
137 - Extra credit: specifics on how to implement sbrk, malloc.
139 - Godmar: We're missing tests that pass arguments to system calls
140 that span multiple pages, where some are mapped and some are not.
141 An implementation that only checks the first page, rather than all
142 pages that can be touched during a call to read()/write() passes
145 - Godmar: Need some tests that test that illegal accesses lead to
146 process termination. I have written some, will add them. In P2,
147 obviously, this would require that the students break this
148 functionality since the page directory is initialized for them,
149 still it would be good to have.
151 - Godmar: There does not appear to be a test that checks that they
152 close all fd's on exit. Idea: add statistics & self-diagnostics
153 code to palloc.c and malloc.c. Self-diagnostics code could be
154 used for debugging. The statistics code would report how much
155 kernel memory is free. Add a system call
156 "get_kernel_memory_information". User programs could engage in a
157 variety of activities and notice leaks by checking the kernel
160 - Godmar: is there a test that tests that they properly kill a process that
161 attempts to access an invalid address in user code, e.g. *(void**)0 =
164 It seems all of the robustness tests deal with bad pointers passed to
165 system calls (at least judging from test/userprog/Rubric.robustness),
166 but none deals with bad accesses by user code, or I am missing
169 ps: I found tests/vm/pt-bad-addr, which is in project 3 only, though.
171 For completeness, we should probably check read/write/jump to unmapped
172 user virtual address and to mapped kernel address, for a total of 6
173 cases. I wrote up some tests, see
174 http://people.cs.vt.edu/~gback/pintos/bad-pointers/
176 - process_death test needs improvement
178 - Godmar: In the wait() tests, there's currently no test that tests
179 that a process can only wait for its own children. There's only
180 one test that tests that wait() on an invalid pid returns -1 (or
181 kills the process), but no test where a valid pid is used that is
182 not a child of the current process.
184 The current tests also do not ensure that both scenarios (parent waits
185 first vs. child exits first) are exercised. In this context, I'm
186 wondering if we should add a sleep() system call that would export
187 timer_sleep() to user processes; this would allow the construction of
188 such a test. It would also make it easier to construct a test for the
189 valid-pid, but not-a-child scenario.
191 As in Project 4, the baseline implementation of timer_sleep() should
192 suffice, so this would not necessarily require basing Project 2 on
193 Project 1. [ A related thought: IMO it would not be entirely
194 unreasonable to require timer_sleep() and priority scheduling sans
195 donation from Project 1 working for subsequent projects. ]
199 - Godmar: Get rid of mmap syscall, add sbrk.
201 - Godmar: page-linear, page-shuffle VM tests do not use enough
202 memory to force eviction. Should increase memory consumption.
204 - Godmar: fix the page* tests to require swapping
206 - Godmar: make sure the filesystem fails if not properly
207 concurrency-protected in project 3.
209 - Godmar: Another area in which tests could be created are for
210 project 3: tests that combine mmap with a paging workload to see
211 their kernel pages properly while mmapping pages - I don't think
212 the current tests test that, do they?
216 - Need a better way to measure performance improvement of buffer
217 cache. Some students reported that their system was slower with
218 cache--likely, Bochs doesn't simulate a disk with a realistic
221 (Perhaps we should count disk reads and writes, not time.)
223 - Need lots more tests.
225 - Detect implementations that represent the cwd as a string, by
226 removing a directory that is the cwd of another process, then
227 creating a new directory of the same name and putting some files
228 in it, then checking whether the process that had it as cwd sees
231 - dir-rm-cwd should have a related test that uses a separate process
232 to try to pin the directory as its cwd.
234 - Godmar: I'm not sure if I mentioned that already, but I passed all
235 tests for the filesys project without having implemented inode
236 deallocation. A test is needed that checks that blocks are
237 reclaimed when files are deleted.
239 - Godmar: I'm in the middle of project 4, I've started by
240 implementing a buffer cache and plugging it into the existing
241 filesystem. Along the way I was wondering how we could test the
244 Maybe one could adopt a similar testing strategy as in project 1
245 for the MLQFS scheduler: add a function that reads
246 "get_cache_accesses()" and a function "get_cache_hits()". Then
247 create a version of pintos that creates access traces for a
248 to-be-determined workload. Run an off-line analysis that would
249 determine how many hits a perfect cache would have (MAX), and how
250 much say an LRU strategy would give (MIN). Then add a fudge
251 factor to account for different index strategies and test that the
252 reported number of cache hits/accesses is within (MIN, MAX) +/-
255 (As an aside - I am curious why you chose to use a clock-style
256 algorithm rather than the more straightforward LRU for your buffer
257 cache implementation in your sample solution. Is there a reason
258 for that? I was curious to see if it made a difference, so I
259 implemented LRU for your cache implementation and ran the test
260 workload of project 4 and printed cache hits/accesses. I found
261 that for that workload, the clock-based algorithm performs almost
262 identical to LRU (within about 1%, but I ran nondeterministally
263 with QEMU). I then reduced the cache size to 32 blocks and found
264 again the same performance, which raises the suspicion that the
265 test workload might not force any cache replacement, so the
266 eviction strategy doesn't matter.)
268 - Godmar: I haven't analyzed the tests for project 4 yet, but I'm
269 wondering if the fairness requirements your specification has for
270 readers/writers are covered in the tests or not.
275 - Add "Digging Deeper" sections that describe the nitty-gritty x86
276 details for the benefit of those interested.
278 - Add explanations of what "real" OSes do to give students some
281 * To add partition support:
283 - Find four partition types that are more or less unused and choose
284 to use them for Pintos. (This is implemented.)
286 - Bootloader reads partition tables of all BIOS devices to find the
287 first that has the "Pintos kernel" partition type. (This is
288 implemented.) Ideally the bootloader would make sure there is
289 exactly one such partition, but I didn't implement that yet.
291 - Bootloader reads kernel into memory at 1 MB using BIOS calls.
292 (This is implemented.)
294 - Kernel arguments have to go into a separate sector because the
295 bootloader is otherwise too big to fit now? (I don't recall if I
296 did anything about this.)
298 - Kernel at boot also scans partition tables of all the disks it can
299 find to find the ones with the four Pintos partition types
300 (perhaps not all exist). After that, it makes them available to
301 the rest of the kernel (and doesn't allow access to other devices,
304 - "pintos" and "pintos-mkdisk" need to write a partition table to
305 the disks that they create. "pintos-mkdisk" will need to take a
306 new parameter specifying the type. (I might have partially
307 implemented this, don't remember.)
309 - "pintos" should insist on finding a partition header on disks
310 handed to it, for safety.
312 - Need some way for "pintos" to assemble multiple disks or
313 partitions into a single image that can be copied directly to a
314 USB block device. (I don't know whether I came up with a good
315 solution yet or not, or whether I implemented any of it.)
317 * To add USB support:
319 - Needs to be able to scan PCI bus for UHCI controller. (I
320 implemented this partially.)
322 - May want to be able to initialize USB controllers over CardBus
323 bridges. I don't know whether this requires additional work or
324 if it's useful enough to warrant extra work. (It's of special
325 interest for me because I have a laptop that only has USB via
328 - There are many protocol layers involved: SCSI over USB-Mass
329 Storage over USB over UHCI over PCI. (I may be forgetting one.)
330 I don't know yet whether it's best to separate the layers or to
331 merge (some of) them. I think that a simple and clean
332 organization should be a priority.
334 - VMware can likely be used for testing because it can expose host
335 USB devices as guest USB devices. This is safer and more
336 convenient than using real hardware for testing.
338 - Should test with a variety of USB keychain devices because there
339 seems to be wide variation among them, especially in the SCSI
340 protocols they support. Should try to use a "lowest-common
341 denominator" SCSI protocol if any such thing really exists.
343 - Might want to add a feature whereby kernel arguments can be
344 given interactively, rather than passed on-disk. Needs some